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

Question

Today I have two sequences,

s1 = CCGGGTTACCA

s2 = GGAGTTCA

The Mismatch Score is -1, the Gap Score is -2.

The Optimal Sequence Alignment has two answers (miniumn penalty is -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

If any algorithm can calculate the number of Optimal Sequence Alignment (it will return "4") ?

Or what can I do to solve this problem?

Thanks

Answer 1

My score system is on the picture.

I do the Needleman-Wunsch algorithm (dynamic program) to complete the table.

Finally, I give up to only find the number of Optimal Sequence Alignment.

I trackback to find all the possible answers and insert the set, so the the size of set is my answer.

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