Dynamic programming: string alignment

Overview

The aim is to find the best alignment of two strings. The dynamic programming approach is to reduce the program to some simpler ones. Unlike in a divide-and-conquer strategy, we solve the set of programs in a clever order: from smaller to larger ones.

To align string S(1..i) and T(1..j), we consider three case:

  1. Align S(i) and T(j), + the best alignment of S(1..i-1) and T(1..j-1)
  2. Align S(i) and a space (␣), + the alignment of S(1..i-1) and T(1..j)
  3. Align T(j) and a space (␣), + the alignment of S(1..i) and T(1..j-1)

The maximal score from the three cases is chosen as the score M(i,j) for the alignment S(1..i) and T(1..j). In formula

{ M(i-1, j-1) + f(S(i), T(j)) }
M(i, j) = maxM(i-1, j) + f(S(i), ␣)
M(i, j-1) + f(␣, T(j))

Now, instead of solving the problem recursively, i.e., M(i, j) → {M(i-1, j-1), M(i-1, j), M(i, j-1)} → ..., we start from smaller problems. First, we solve all M(1, 1), M(1, 2), ..., M(1, m), i.e., aligning the first character of S with parts of T. We then proceed to M(2, 1), M(2, 2), ..., M(2, m). We repeat the process till M(n, m) is reached.

Javascript demonstration of aligning two strings

Word 1:
Word 2:
Scores:
Match: Mismatch: Gap:

Score table:
The score at the bottom-right corner of the table is that of optimal alignment of the two strings (whose absolute value is equal to the number of mismatches and gaps by the default score, match=0, mismatch=-1, gap=-1).
Best alignment:

Download: