Dynamic Programming - Multiple Sequence Alignment Methods - page 14

Fig. 6 Smith-Waterman algorithm example

Another modification on the dynamic programming algorithm
addresses the problem of finding all near-optimal alignments. The
optimal global alignment provided by the Needleman-Wunsch
algorithm is sensitive on the scoring function defined, and it might
not reflect a biologically meaningful alignment perfectly. Another
alignment with a slightly lower score might be more interesting;
however, it is not found by the original algorithm. Waterman [ 7 ]
suggested an algorithm to find not just the optimal alignment but all
of the near-optimal alignments performing at the same space and
time complexity with the Needleman-Wunsch algorithm.
The near-optimal alignment finding algorithm is based on one
observation on the problem separability of alignments as shown in
Eq. 4 . The same optimal path and score is found whether the
recursion is performed from top-left to bottom-right or vice versa
(i.e., directionality does not change the solution). At the first phase,
two score matrices are generated: one computing the recursion in
forward direction (i.e., top-left to bottom-right) and one in the
reverse direction. For the forward computation the S F ( i , j ) has the
optimal path score from the top-left cell to the cell c ( i , j ), and
S R ( i , j ) has the optimal path score from the bottom-right cell
to the cell c ( i , j ). Assume a path attains score s . For any edge
connecting cell

c ( i , j ) and its parent ( p , q ) in this path,

S F ð s , according to Eq. 4 . Using this

observation, given an alignment score s , starting from the
bottom-right (or top-left) corner, a path with the score s can be
traced back. The proposed algorithm performs a reverse-scan
phase, by adding the detected edges iteratively to a list. When
multiple edges are found in an iteration, multiple paths are traced
separately to find every satisfying alignments. The original algo-
rithm sets s to a range of values close to the optimal score, in order
to find all near-optimal alignments.

p ; q Þþ e i;j ð p ; q Þþ S R ð i ; j Þ¼