1. There was a mistake in initializing the three dynamic matrices. The most common oversight was initializing all entries to a multiple of go, although there has been incorrect usage of the gap extension penalties as well. The key idea in initialization is that the first entry in the 0-th row (or column) corresponds to gap opening, and thus has the score go, while all subsequent entries along the 0-th row (or column) correspond to extension of the first gap. Thus, the score for the k-th entry of the 0-th row should be go + (k-1)ge (unless we set it to negative infinity; see the solution).
2. There was a mistake in backtracking. The most common one caused the code to
crash when either i or j (but not both) reached 0. Some programs that tried
to prevent this crash instead wound up going into infinite loops. The problem here is that
backtracking procedure has entered the initialization column of the wrong matrix. Once
i reaches 0, for instance, we should no longer consider the matrices
Tnm and Tn-, since the fact that i=0
implies that we have already aligned all the characters of seq1, and thus the
first j characters in seq2 are aligned against gaps. Thus, we need to
make sure that the back-tracking never enters Tnm or
Tn- if i=0. This can be done by either setting the corresponding
entries of Tnm and Tn- to negative infinity
(thus making sure they are never in an optimal alignment path), or by explicitly redirecting
the backtracking to the T-m when i becomes 0. The case that
j reaches 0 first is completely symmetric. See the solution for more details.
3. Either no mention was made as to why gap opening and extension did not effect the alignment of 1MBC and 1YMC but had a large effect on the alignment of 1LHS and 1LH1, or there was no clear explanation as to why the high degree of similarity between 1MBC and 1YMC results in gap opening and extension not having any effect.