Smith-Waterman

The Smith-Waterman algorithm is a local sequence alignment algorithm that finds the optimal alignment of substrings within two sequences, rather than aligning the entire sequences as in the Needleman-Wunsch algorithm. It is the algorithm of choice for database search tools like BLAST, where the goal is to find regions of similarity between a query sequence and a large database of sequences.

The algorithm modifies the Needleman-Wunsch recurrence by adding a zero option: S[i][j] = max(0, S[i-1][j-1] + match, S[i-1][j] + gap, S[i][j-1] + gap). This allows the alignment to start and end at any position, producing local rather than global alignments.

The Smith-Waterman algorithm is a methodological correction to the assumption that biological similarity is global. Most functional relationships in biology are local: a shared domain, a conserved motif, a functional site. The global alignment of Needleman-Wunsch is often biologically misleading, forcing alignment of non-homologous regions. Smith-Waterman recognizes that similarity is patchy, and that the best way to find it is to allow alignment to start and end where the data demands.