如何找到两个序列之间的最佳序列比对数？

Question

今天我有两个序列，

s1 = CCGGGTTACCA

s2 = GGAGTTCA

不匹配分数为 -1，差距分数为 -2。

最佳序列比对有两个答案（最小惩罚为-8）。

ans1 = G    -   G   A   G   T   T   -   C   -   A
       C    C   G   G   G   T   T   A   C   C   A


ans2 = -    G   G   A   G   T   T   -   C   -   A
       C    C   G   G   G   T   T   A   C   C   A


ans3 = G    -   G   A   G   T   T   -   -   C   A
       C    C   G   G   G   T   T   A   C   C   A


ans4 = -    G   G   A   G   T   T   -   -   C   A
       C    C   G   G   G   T   T   A   C   C   A

如果有什么算法可以计算出Optimal Sequence Alignment的个数（会return "4"）？

或者我能做些什么来解决这个问题？

谢谢

Answer 1

我的评分系统在图片上。

我做Needleman-Wunsch算法（动态程序）来完成table.

最后放弃只求Optimal Sequence Alignment的个数

我引用了所有可能的答案并插入了集合，所以集合的大小就是我的答案。

set<pair<string, string>> st;
void findAll(string A, string B, int gap, int mis, int i, int j, string s1, string s2) {

    if (s1.size() == max(A.size(), B.size()) && s2.size() == max(A.size(), B.size())) {
        reverse(begin(s1), end(s1));
        reverse(begin(s2), end(s2));
        st.insert({s1, s2});
        return;
    }

    if (i != 0 || j != 0) {
        if (i == 0) {
            findAll(A, B, gap, mis, i, j - 1, s1 + "-", s2 + B[j - 1]);
        } else if (j == 0) {
            findAll(A, B, gap, mis, i - 1, j, s1 + A[i - 1], s2 + "-");
        } else {
            if ((A[i - 1] == B[j - 1] && dp[i][j] == dp[i - 1][j - 1]) || (A[i - 1] != B[j - 1] && dp[i][j] == dp[i - 1][j - 1] + mis)) {
                findAll(A, B, gap, mis, i - 1, j - 1, s1 + A[i - 1], s2 + B[j - 1]);
            }

            if (dp[i][j] == dp[i - 1][j] + gap) {
                findAll(A, B, gap, mis, i - 1, j, s1 + A[i - 1], s2 + "-");
            }

            if (dp[i][j] == dp[i][j - 1] + gap) {
                findAll(A, B, gap, mis, i, j - 1, s1 + "-", s2 + B[j - 1]);
            }
        }
    }
}

如何找到两个序列之间的最佳序列比对数？

How to find the number of Optimal Sequence Alignment between two sequences?

algorithm

dynamic-programming

sequence

lcs