View source for 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.''

[[Category:Computer Science]]
[[Category:Biology]]
[[Category:Algorithms]]
[[Category:Systems]]