Example: filling the dynamic programming table
Let us see how this works out for one of the examples shown above—ABBA versus ACA. First, we set up the dynamic programming table by making room for the string '-ABBA' along the rows and string '-ACA' along the columns. The character '-' indicates the empty string, and symbolizes the deletion of a character. The resulting table looks like:
-
A
C
A
-
A
B
B
A
As discussed above, we start by initializing the first row and column of the matrix with the values of the edit distances between the empty string and successively longer prefixes of one or the other strings.
For example, the cell '-,-' will have value 0, as the edit distance between two empty strings is 0. The cell '-,A' will have value 1, as we need to delete (or insert) character A in order to make string 'A' equal to the empty string:
-
A
C
A
-
0
1
A
B
B
A
Following the same logic, we can see that the first row and column are simply increasing series of integers:
-
A
C
A
-
0
1
2
3
A
1
B
2
B
3
A
4
At this point, we are ready to apply the recurrence equations. Note that we can only compute the values located in cells for which we already know the value in the preceding 3 cells (left, top-left, and top), thus, we can only fill in the cell 'A, A'.
As a reminder, the recurrence equations are:
In our case, S1[1] = A = S2[1], thus the cell [1,1] receives the same value as the cell [0, 0] which is 0.
Note that all the other options listed above yield numbers larger than 0 — the indels (last two equations) yield a score of 2. The matrix now becomes:
-
A
C
A
-
0
1
2
3
A
1
0
B
2
B
3
A
4
At this point, we are now ready to fill in two other cells – 'A, C' or [1, 2] and 'B, A' or [2, 1]. Which one you fill out is completely arbitrary, and different algorithms either go row by row, column by column, or diagonal by diagonal. The different orders of operations yield the same results but may provide different opportunities for optimizing the execution if runtime is a concern.
Let's go row by row. We now want to fill in cell [1,2] and note that S1[1] = A which is different from C = S2[2], thus we have the following options:
substitution (forcing A and C to align): E[1, 2] = E[0, 1] + 1 = 2 deletion from S2: E[1, 2] = E[0, 2] + 1 = 3 deletion from S1: E[1, 2] = E[1, 1] + 1 = 1
Since we want to minimize the score, we'll select the last value, yielding the matrix:
-
A
C
A
-
0
1
2
3
A
1
0
1
B
2
B
3
A
4
We, then continue to the next cell,[1, 3], where S1[1] = A = S2[2], thus case I applies and the three equations now are:
match. E[1, 3] = E[0, 2] = 2
deletion from S2. E[1, 3] = E[0, 3] + 1 = 4
deletion from S1. E[1, 3] = E[1, 2] + 1 = 2
The resulting matrix (choosing the minimum score from the three above) is:
-
A
C
A
-
0
1
2
3
A
1
0
1
2
B
2
B
3
A
4
We then continue the same process, moving on to cell [2, 1] or 'B, A'', and so on, yielding the full table:
-
A
C
A
-
0
1
2
3
A
1
0
1
2
B
2
1
1
2
B
3
2
2
2
A
4
3
3
2
Since the value in the bottom right corner of the matrix is 2, we know that we can transform the string ACA into ABBA by making just two edits, and that this is the minimum number of edits required.
But this value doesn't tell us anything about how we can figure out exactly which edits we need to make. To do so, we need to "walk back" through all the decisions we have made in a process called backtracking.
Additional resources
Last updated