= Smith-Waterman algorithm
{c}
{wiki=Smith–Waterman_algorithm}
The <Smith-Waterman algorithm> finds an optimal <local sequence alignment> for a specified additive scoring scheme. For a linear <gap penalty> $e>0$, a <dynamic programming> score satisfies
$$
H_{ij}=\max\{0,H_{i-1,j-1}+s(x_i,y_j),H_{i-1,j}-e,H_{i,j-1}-e\}.
$$
Zero permits an alignment to restart; tracing back from the largest entry to zero recovers a highest-scoring segment pair. Every optimal ending must have one of the listed final steps, which proves the recurrence by induction over the table. Optimality concerns this score, not guaranteed biological ancestry. <Identification of common molecular subsequences by Temple F. Smith and Michael S. Waterman>[Smith and Waterman, 1981, Identification of common molecular subsequences]{ref}
Back to article page
