Counting Differences

Edit Distance

the Dynamic-Programming Table

Edit distance counts insertions, deletions, and substitutions by filling a table, cell by cell.

highlighted = computed this step

Insertions and deletions need a table

Edit (Levenshtein) distance is the fewest single-base insertions, deletions, and substitutions that turn one sequence into the other. Because an edit can change the length, we cannot count columns; we fill a table instead.

edit∈{insert,delete,substitute}\text{edit} \in \{\text{insert}, \text{delete}, \text{substitute}\}

Each cell builds on three neighbours

A cell is the cheapest way to reach it: take the upper or left neighbour and add 1 for a gap, or the diagonal neighbour and add 1 only if the two bases differ. The highlighted cell and its three sources are shown.

cell=min⁡(up+1, left+1, diag+mismatch)\text{cell} = \min(\text{up}+1,\ \text{left}+1,\ \text{diag}+\text{mismatch})
Filling one cellEach cell is one more than the best of its upper, left, and diagonal neighbours (diagonal free on a match).––GCAGCGCATGC012345101234210123321012432112543212654321

The distance is the bottom-right cell

Once every cell is filled, the bottom-right corner is the edit distance — here 1, a single deletion of the extra base. Honesty note: this counts edits, not biological likelihood; the alignment that achieves it is the subject of the next chapter.

edit distance=1\text{edit distance} = 1
Edit-distance matrixThe bottom-right cell is the edit distance between the two sequences.––GCAGCGCATGC012345101234210123321012432112543212654321