Two long sequences may share only a short stretch. Smith-Waterman finds the single best-matching subsegment by filling a grid of scores and clamping every negative cell to zero — so a match can begin and end anywhere. That grid is a 2-D table, exactly the shape the suggestion box lists as an open want; the score row runs in real I-13 today.
THE TECHNIQUE H = max(0, diag+s, up−gap, left−gap)
Build an (n+1)×(m+1) grid H. The first row and column are zero. Each inner cell takes the best of: align the two letters (diagonal + match/mismatch), a gap in one sequence (up − penalty), a gap in the other (left − penalty), or 0. The zero is the whole trick — it forbids a negative running score, so the alignment restarts wherever it must. The best cell (orange) is where the strongest local match ends; walk back to a zero to read it. live demo
HISTORY & CREDIT the local capstone of a lineage
Taught as one clean algorithm — it is really a single invention capstone on a chain, and the fast version everyone runs isn’t even theirs. cited
1970 · Needleman & Wunsch (Northwestern) give the first matrix method — global alignment, end to end. 1981 · Temple Smith & Michael Waterman, in a 3-page letter (J. Mol. Biol. 147:195–197, done at Los Alamos), add the zero-clamp — turning global into local alignment. A “note added in proof” credits Walter Goad (a GenBank co-founder) with an independent version. 1982 · Osamu Gotoh makes the affine-gap form run in O(mn) — the version all real tools use, so it is properly Smith-Waterman-Gotoh. The 1981 general-gap form was ~O(n³). 1990 · BLAST arrives — a fast heuristic approximation of Smith-Waterman, not the thing itself; it trades guaranteed-optimal for speed.
Waterman is the “Waterman” of Lander-Waterman genome statistics — a profile once headlined his path “from cattle rancher to genomics pioneer.” a lineage, not a bolt of lightning
RECOMMEND FOR I-13 the 2-D table the box lists
The score matrix H is a genuine 2-D array. I-13’s array is 1-D, so each row is a bounded array, and the best local score is a running scalar max over it — which runs on the real compiler (a row of H over the demo sequences, best cell = 13):
$ i13 run amax.i13 # scalar max over a row of the H matrix (a bounded array)
best = 13 # matches the demo above; scores are small ints -> no bignum needed
Recommend: presses PS-004 (a 2-D array) in the suggestion box. Each row runs as a 1-D array and the best cell is a scalar max (verified above) — not a heap, and scores stay bounded so no bignum. What the 1-D form can’t give is the traceback: recovering the aligned letters wants the whole 2-D grid (or a 2-D pointer table) kept, since you scan the full matrix for the max cell and walk back to a zero. Note: the rolling-one-row trick is the same space-saver knapsack-053 used; the 2-D array would buy the traceback, not the score. Credit is careful here — the fast O(mn) form everyone runs is Gotoh’s (1982), not the 1981 paper’s ~O(n³).