= Needleman-Wunsch algorithm
{c}
{wiki=Needleman–Wunsch_algorithm}
The <Needleman-Wunsch algorithm> uses <dynamic programming> to find an optimal <global sequence alignment>. For a linear <gap penalty> $e>0$, set $F_{0j}=-je$, $F_{i0}=-ie$ and
$$
F_{ij}=\max\{F_{i-1,j-1}+s(x_i,y_j),F_{i-1,j}-e,F_{i,j-1}-e\}.
$$
The final entry scores the best alignment of both complete sequences. The recurrence follows because its last step must align two symbols or a symbol and a gap. Unlike local alignment, there is no zero restart, so unmatched ends contribute to the score. <A general method applicable to the search for similarities in the amino acid sequence of two proteins by Saul B. Needleman and Christian D. Wunsch>[Needleman and Wunsch, 1970, global sequence comparison]{ref}
Back to article page
