The poster writes “I need to perform sequence alignment to determine all possible sequence alignments”. It is not clear whether this need is that determined by a course assignment or the poster’s mathematical imagination. If the former, I doubt that the wording expresses the request correctly, even though this is repeated in the question as “My goal is to find all sequences and not just the optimal (highest?) ones”. The reason for doubting this is that the number of possible alignments with no restraint imposed will vary from very large to astronomical, depending on the length of the sequences.
The display presented looks at first sight like a trackback for a global alignment using the Needleman and Wunsch dynamic programming algorithm. Such a trackback is designed to find one of what are generally several possible alignments that have the highest score using a specific scoring matrix and gap penalties (different scoring systems can give different alignments). Although it is possible in general to trace alternative trackbacks of the same score manually, I do not see any in this example. This operation is not performed in any programatic implementations of the algorithm of which I am aware. Although, memory limitations permitting, one could program this, the algorithm is not designed to find lower scores (and I find it hard to see the demand for such).
However the problem with the Needleman and Wunsch trackback is that in this algorithm each cell should trackback to the single highest-scoring cell preceding it — if there are two of the same score a random choice is made. But the trackback shown, as well as having instances where the highest scoring cell has been missed, has 9 cases where the trackback is to two cells with different scores. I can think of no justification for this.
There is another fundamental defect here, which arises from the scoring system used. The match = 1, mismatch = –1, fixed-gap-penalty system is doomed to result in low alignment scores in this case: the best possible score is 5 x 1 (matches) + 7 x –2 (gaps) = –9. The PAM or BLOSUM matrix, which score similar amino acids on the basis of their likely mutational substitution and thus are better related to the realities of protein structure, have higher numerical values relative to the gap penalty, which should actually be replaced by a gap initiation penalty followed by a lower gap extension penalty.
In conclusion I would advise anyone undertaking work of this type, first to obtain a thorough understanding of the dynamic programming algorithms used, next to specify clearly the goals he wishes to achieve, then to assess whether they are realistic, and finally be prepared to write a program himself if none already exists.
