Pattern Matching - Bioinformatics Computing - page 282

even though the number of such possible alignments grows exponentially with the length of the two
sequences. Similarly, just as adding a dimension to the problem doesn't fundamentally change the
evaluation process, the alignment of multiple strings can be evaluated using this process as well.
To bring the power of dynamic programming into the realm of pairwise sequence alignment, consider
MaxValue to be the alignment score for pairwise alignment of two sequences. MaxValue takes into
account gap penalties, correct alignments, and imperfect alignments. After the matrix is filled in
using the alignment score to determine MaxValue , the highest scoring path is followed back to the
beginning of the alignment to define the best alignment of elements in the sequence, including gaps.
Graphically, this approach to the local alignment of two sequences is illustrated in Figure 8-11 . The
starting point is the best score in the matrix, the C-C alignment with a value of 11. Working
backwards to the row and column to the upper left, step (1), the best score is for the G-G alignment,
with a score of 10. Because the value is on the diagonal immediately adjacent to the value for the C-
C alignment, there is no gap penalty. Now, moving to step (2), the highest score, 8, is also
immediately adjacent and therefore free of a gap penalty. In step (3), there are three high scores,
each of which has a gap penalty. The minimum gap penalty is associated with the closest alignment
with a score of 5, the A-A alignment. Continuing to step (4), there are two competing high scores.
Because there is no penalty for the C-C alignment that is diagonally adjacent to the A-A alignment,
with a value of 6, the process continues to the G-G bond with a value of 8, to completing the local
alignment. That is, the local alignment appears as:
Q) ATCGA GCA-GC ATG...
R) ----- GCA T GC T...
Figure 8-11. Matrix Scores and Optimum Local Alignment for Two
Sequences.