= Global sequence alignment without mismatches
{title2=$D_{i,j}=\max(D_{i-1,j}-g,D_{i,j-1}-g,D_{i-1,j-1}+1\text{ if }x_i=y_j)$}
Align two complete <strings> using matching letters or a letter opposite a gap, with no unequal-letter columns and no double-gap columns. Give each match score one and each gap penalty $g\geq0$. The <dynamic programming> table for prefixes starts with $D_{i,0}=-gi$ and $D_{0,j}=-gj$. Its last-column cases give the displayed recurrence, where the diagonal candidate is omitted on a mismatch. Construction takes $O(mn)$ time for positive lengths and $O(mn)$ space with full <alignment traceback>.
An alignment with $\ell$ matches has $m+n-2\ell$ gaps and score $(1+2g)\ell-g(m+n)$. Therefore a <longest common subsequence> determines its optimum. A finite mismatch penalty would solve a different problem.
Back to article page
