Smith-Waterman algorithm

The Smith-Waterman algorithm performs local sequence alignment: it finds the optimal matching substring between two sequences rather than forcing alignment across their entire lengths. Developed by Temple Smith and Michael Waterman in 1981, it modifies the Needleman-Wunsch algorithm by allowing alignment scores to reset to zero, preventing poor flanking regions from degrading the match. This makes it the gold standard for identifying conserved domains and functional motifs. However, its \u003Cmath\u003EO(nm)\u003C/math\u003E time complexity makes it impractical for database searches, driving the development of heuristic approximations like BLAST and FASTA. Modern benchmarks still evaluate heuristic methods against Smith-Waterman exactness. The algorithm uses an Affine gap penalty to model the biological reality that opening a gap is more costly than extending one.

Smith-Waterman is the algorithm that exactness built and practicality forgot. Biologists need speed more than they need optimal substrings.