NW sequence comparison. (
a) Comparison of GTTGCA and GATCCA. The margins of the edit matrix are initialized and the cells are computed from left to right and from top to bottom by the NW dynamic programming algorithm.

, the term of coordinates (
i,
j) is computed as

, where

if the
ith symbol from the first sequence is the same as the
jth symbol from the second and

otherwise. The Levenshtein distance between the two sequences is the value of the bottom right cell. (
b) Lower complexity algorithm to determine whether GTTGCA and GATCCA are 2-matches. The values in the outer cells are set during initialization. The dynamic programming algorithm proceeds as above, with the difference that it is aborted if the value of a diagonal cell (bold borders) is larger than 2. The values in the initialized cells may differ from the original NW scheme (arrow), but the values in the computed cells are nevertheless identical. The values of the empty cells are never computed, which contributes to reducing the complexity