Content
Summary
Dynamic programming determines optimal sequence alignments by constructing a quantitative scoring matrix that evaluates all possible character pairs, unlike the visual dot matrix method. The algorithm fills this matrix by accumulating scores from previous cells and then traces back from the bottom-right corner to identify the path with the maximum total score. This process incorporates gap penalties to computationally reflect the evolutionary rarity of insertions and deletions.
Intuition
Think of dynamic programming as a rigorous, quantitative upgrade to the visual dot matrix method. While the dot matrix simply links matching characters, dynamic programming builds a scoring grid where every cell's value depends on the best possible path leading to it. By filling the matrix from top to bottom and left to right, the algorithm accumulates scores, effectively calculating the 'cost' or 'reward' of every potential alignment step. The final alignment is not just a visual diagonal but the specific path through this grid that yields the highest cumulative score, balancing matches against the penalties for gaps.
Key equations
The score for a specific cell is calculated as the maximum score from the three neighboring squares (diagonal, horizontal, and vertical) plus or minus the exact single residue match score and the gap penalty, respectively.
Derivation
- Initialize a two-dimensional scoring matrix to evaluate all possible character pairs between two sequences.
- Fill the matrix iteratively, one row and one cell at a time, starting from the top left.
- For each cell, calculate its score by taking the maximum value from the three neighboring cells (diagonal, horizontal, vertical) and adding the match score or subtracting the gap penalty.
- Continue until all cells are filled, accumulating scores along the diagonal from the upper left to the lower right corner.
- Trace back from the lower right-hand corner toward the origin in the upper left-hand corner to find the path with the maximum total score.
- Identify horizontal or vertical moves in the trace-back path as gaps, insertions, or deletions.
Worked example
Given a simple scoring system where an identical match is 1, a mismatch is 0, and a gap penalty is -1, determine the score of a cell if the diagonal neighbor has a score of 2, the horizontal neighbor has a score of 1, and the vertical neighbor has a score of 1. The current character pair is a match.
- Identify the scores of the three neighboring cells: Diagonal (X) = 2, Horizontal (Y) = 1, Vertical (Z) = 1.
- Find the maximum of these neighbors: max(2, 1, 1) = 2.
- Add the match score for the current character pair: 2 + 1 = 3.
- Subtract the gap penalty (not applicable here as we are not introducing a gap, but the formula structure implies the base score is derived from the max neighbor plus the match/mismatch value).
- The resulting score for the current cell is 3.
Answer 3
Common mistakes
- Setting gap penalty values too low results in too many gaps, allowing nonrelated sequences to appear similar.
- Setting gap penalty values too high makes gaps too difficult to appear, leading to unrealistic alignments.
- Confusing the dot matrix method's visual linking of diagonals with dynamic programming's quantitative accumulation of scores.
- Assuming there is an evolutionary theory that determines a precise cost for introducing insertions and deletions.