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

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

如果有任何算法可以计算最佳序列比对数（它将返回“ 4”）？

还是我该怎么办来解决这个问题？

谢谢

Answer 1

我的分数系统在图片上。

我执行Needleman-Wunsch算法（动态程序）来完成表。

最后，我放弃只找到最佳序列比对的数量。

我进行回顾以找到所有可能的答案并插入集合，因此集合的大小是我的答案。

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]);
            }
        }
    }
}