The site's eleventh approximate match entry, and the first to ask a genuinely different question from every DP-table entry before it. Edit Distance, Damerau–Levenshtein, Banded Edit Distance, and Myers Diff all compare two whole strings — every character on both sides has to be accounted for, even the parts that don't resemble each other at all. Smith–Waterman asks instead: is there a region inside sequence A that closely resembles a region inside sequence B, no matter what the rest of either sequence looks like? Published by Temple Smith and Michael Waterman in 1981, it's the algorithm behind BLAST and every DNA/protein "local alignment" search in bioinformatics — finding a shared gene fragment between two reads that otherwise share nothing, or a conserved motif buried in unrelated flanking sequence.
Fixed pair A = "CCATCTAGA", B = "TTCATAGGT" — two short DNA-style reads
that share almost nothing at their edges (A starts CCA…, B
starts TT…; A ends …A, B ends …GT)
but share a real conserved region in the middle, with one small insertion in B. Scoring:
match +2, mismatch −1, gap −1. Press Step or
Run to fill the table in Local (Smith–Waterman) mode — watch the
best score so far update as filling proceeds, then watch the dotted-border cell (the table's true
maximum, wherever it ends up) get picked out once the fill finishes, and the alignment trace back
from there. Switch to Global (no floor) mode and rerun on the identical pair to see
Pitfall two below happen live: the same recurrence, minus one clamp, finds a lower score using the
exact same cell.
The table fills with almost the same recurrence as Edit Distance's, but scoring similarity instead of counting edits, and with one extra option at every cell — bail out to zero:
dp[i][j] = max(
0, // give up and restart here
dp[i-1][j-1] + (A[i-1] === B[j-1] ? match : mismatch), // align A[i-1] with B[j-1]
dp[i-1][j] + gap, // A[i-1] aligns to a gap
dp[i][j-1] + gap // B[j-1] aligns to a gap
)That leading 0 is the entire mechanism that turns a global comparison into a local
one. Whenever continuing an alignment would cost more than it's worth — the running score would go
negative — the table simply resets to 0 instead, exactly the same "give up and start
fresh" move Kadane's Algorithm makes for maximum
subarray sum, one dimension down. A run of mismatches or gaps can never drag a later,
genuinely strong local match down with it, because the table never carries a negative balance
forward — it forgets and restarts instead.
The second consequence is where the answer lives. Every other DP table on this site reports its
final answer in the bottom-right corner, dp[m][n], because every other entry demands an
accounting of all of both strings. Smith–Waterman's answer is the largest value
anywhere in the table — the corner is just one cell among many, and on this page's own
example it isn't even close (see Pitfalls). Once that maximum cell is found, tracing back follows
whichever neighbor produced it, exactly like Edit Distance's traceback, with one difference: it stops
the moment it hits a 0, not when it reaches row/column zero. A local alignment can start
and end anywhere inside either string.
function smithWaterman(a, b, match = 2, mismatch = -1, gap = -1) {
const m = a.length, n = b.length;
const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
let best = 0, bestI = 0, bestJ = 0;
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
const diag = dp[i - 1][j - 1] + (a[i - 1] === b[j - 1] ? match : mismatch);
const up = dp[i - 1][j] + gap;
const left = dp[i][j - 1] + gap;
dp[i][j] = Math.max(0, diag, up, left); // the floor — see Pitfalls
if (dp[i][j] > best) { best = dp[i][j]; bestI = i; bestJ = j; } // scan, don't assume dp[m][n]
}
}
let i = bestI, j = bestJ;
let alignedA = '', alignedB = '';
while (i > 0 && j > 0 && dp[i][j] > 0) { // stop at 0, not at row/col 0
const score = dp[i][j];
if (score === dp[i - 1][j - 1] + (a[i - 1] === b[j - 1] ? match : mismatch)) {
alignedA = a[i - 1] + alignedA; alignedB = b[j - 1] + alignedB; i--; j--;
} else if (score === dp[i - 1][j] + gap) {
alignedA = a[i - 1] + alignedA; alignedB = '-' + alignedB; i--;
} else {
alignedA = '-' + alignedA; alignedB = b[j - 1] + alignedB; j--;
}
}
return { score: best, alignedA, alignedB };
}On this page's A/B pair, that function returns 9,
aligning A's TCTAG (positions 4–8) against B's
TCATAG (positions 2–7) — five matched characters plus one gap where B has an
extra A that A doesn't. Five matches at +2 each, minus one gap
at −1, is 10 − 1 = 9. Every character before and after that window — three
in A, one in B on that side, plus one more in A, two more in
B on the other — is never touched by the alignment at all, exactly the point.
Reading the answer out of the bottom-right corner, the way every other DP table on this
site works, gives a real wrong number here — not a hypothetical one. On this page's own
A/B pair, dp[9][9] (the corner) is 7. The
table's true maximum, at dp[8][7], is 9. Both numbers are sitting in
the same table at the same time; only one of them is the actual answer, and the wrong one is the one
every visitor's eye lands on first out of habit from Edit Distance and its relatives. Verified directly against
the reference implementation above: it scans every cell and keeps the running maximum rather than
reading dp[m][n], specifically because of this.
Dropping the max(0, …) floor — filling the table the way every other DP table
here does, with no reset — doesn't just remove the "local" behavior, it silently changes the score
even at the cell that would otherwise be correct. Rerun this page's own scoring without the
floor (select Global (no floor) above) and the table's maximum anywhere drops to
6, at the identical cell (8, 7) — a real, checked 33% drop, not a
rounding difference. The reason: without the reset, every cell's score still carries forward the
accumulated penalty from A and B's completely unrelated opening characters,
even deep inside a region that has nothing to do with that opening. A bad flank can drag down a good
match arbitrarily far away; the floor is what makes "ignore the flanks" actually true rather than
aspirational. (The corner cell moves too, from 7 down to 4 — worth toggling the mode
and comparing both numbers side by side.)
The scoring scheme is a free parameter, and it changes which alignment is optimal — not
just by how much. This page uses match +2, mismatch −1, gap
−1, a simple, commonly taught scheme. Real bioinformatics tools almost never use it: BLAST
and similar tools score amino-acid or nucleotide substitutions with a matrix (BLOSUM, PAM) that
reflects how biologically likely each specific substitution is, not a flat −1 for every
mismatch, and often charge a steep penalty to open a gap plus a cheaper one to
extend it (an "affine" gap penalty), rather than this page's flat per-position
−1. Neither is built here — the recurrence above is the real algorithm, but production
alignment tools spend most of their engineering on exactly this scoring-scheme question, which this
page's fixed numbers sidestep entirely.
Time: O(m·n) — the same single pass over every cell as Edit Distance's table; the floor and the max-tracking each
add only constant work per cell. Space: O(m·n) as shown (needed for
traceback); the score alone could be found in O(min(m, n)) with a rolling two-row window,
the same trade Edit Distance's own space-optimized mode makes, but then no alignment could be
recovered afterward.
Smith–Waterman is the right tool specifically when the two sequences are expected to share only a region, not their entirety — DNA/protein local alignment (BLAST), finding a quoted excerpt inside a much longer unrelated document, or matching a short recognizable fragment against a longer noisy recording. When the two inputs are meant to correspond end-to-end instead, reach for this site's global entries instead: Damerau–Levenshtein Distance for whole-string typo tolerance, or Myers Diff for a literal edit script between two full sequences. For a side-by-side comparison across all eleven approximate-match entries, see Choosing an Approximate String Matcher.