The site's thirteenth approximate match entry, and the one that closes a forward reference named on two separate pages at once. Smith-Waterman's own Pitfalls section named it directly: "combining Smith-Waterman's own local floor with affine gaps (what BLAST actually does) is a further extension, still not built here." Gotoh's Algorithm said the same thing from the other side: "Smith-Waterman's own local search combined with affine gaps ... is a real further extension, not built here." Neither page was wrong to leave it open — it's a genuine fusion of both mechanisms, not a trivial combination — and this page is that fusion: find the best-scoring region inside two sequences (Smith-Waterman's own question), scored with a realistic gap-cost model that charges a steep one-time cost to open a gap and a cheap per-character cost to extend it (Gotoh's own contribution). This exact combination is what real bioinformatics tools — BLAST included — actually run; neither page alone is the full picture.
Fixed pair A = "GTGTAAGGACCGCA", B = "TTAAGCCGCTC" — both strings carry
real noise on both ends (A opens with GTG… and closes with
…A; B opens with T… and closes with …TC) around a
shared region that itself needs a real length-2 gap to align well. Scoring: match +2,
mismatch −1, gap-open −6, gap-extend −1 — the same numbers
Gotoh's own page uses. Press Step or Run in Correct (local +
affine) mode to fill M/Ix/Iy together, watch the
best-so-far score update as filling proceeds, then watch the dotted-border cell (the true maximum,
found by scanning M) get picked out and the alignment traced back from there. Switch to
Corner read (bug) and rerun on the identical pair — same fill, same three tables,
but the answer is wrongly read from M[m][n] instead. Switch to No floor
(bug — reduces to Gotoh) and rerun again to see the fill itself change: without the floor,
this is just Gotoh's Algorithm, end to end.
M — both characters used
Ix — gap in B
Iy — gap in A
The two source mechanisms slot together with only one point of contact. Gotoh's three matrices
still track exactly what they tracked on that page — M ending in a match/mismatch,
Ix ending mid-gap-in-B, Iy ending mid-gap-in-A —
because that's still the only way to know whether the next gap character should cost
open or extend. Smith-Waterman's contribution is a single extra term, added
in exactly one place:
M[i][j] = max(0, M[i-1][j-1] + sub, Ix[i-1][j-1] + sub, Iy[i-1][j-1] + sub)
Ix[i][j] = max(M[i-1][j] + open, Ix[i-1][j] + extend)
Iy[i][j] = max(M[i][j-1] + open, Iy[i][j-1] + extend)That leading 0 sits only in M's own recurrence — not Ix's,
not Iy's. It's tempting to assume the gap matrices need their own floor too, so a gap
mid-alignment can't drag the score arbitrarily negative either. They don't, and this is worth
actually working through rather than taking on faith: every path through Ix or
Iy bottoms out at some earlier M cell — that's the only place either one is
ever opened from — and M is already guaranteed to be ≥ 0 everywhere, by the
same floor. Since open and extend are both negative, any value flowing
through a gap is strictly less than the M cell that opened it — which was
already reachable directly, floor included, without paying for the gap at all. A separate floor on
Ix/Iy could never produce a value better than just not taking the gap, so it
has nothing left to contribute. Confirmed directly, not just argued: a variant with Ix
and Iy each floored at zero too was stress-tested against this page's own algorithm
across 30,000 random pairs and never once produced a different final score.
The second consequence follows the same shape as Smith-Waterman's own: because M can
restart at any cell, the answer is the largest value anywhere in M —
never Ix or Iy (both are always strictly dominated by some earlier
M value, per the same argument above, so scanning them too would never change what's
found — just extra work), and never assumed to be the bottom-right corner. Traceback starts at that
cell in state M and stops the moment it lands back on an M cell holding
exactly 0 — the same stopping rule Smith-Waterman uses, just restricted to the one
matrix that can legitimately hold it.
function smithWatermanGotoh(a, b, match, mismatch, gapOpen, gapExtend) {
const m = a.length, n = b.length;
const NEG = -Infinity;
const M = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
const Ix = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(NEG));
const Iy = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(NEG));
let best = 0, bestI = 0, bestJ = 0;
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
const sub = a[i - 1] === b[j - 1] ? match : mismatch;
M[i][j] = Math.max(0, M[i-1][j-1] + sub, Ix[i-1][j-1] + sub, Iy[i-1][j-1] + sub);
Ix[i][j] = Math.max(M[i-1][j] + gapOpen, Ix[i-1][j] + gapExtend);
Iy[i][j] = Math.max(M[i][j-1] + gapOpen, Iy[i][j-1] + gapExtend);
if (M[i][j] > best) { best = M[i][j]; bestI = i; bestJ = j; } // scan M only — see Why it works
}
}
// traceback: start in M at the scanned maximum, stop when M hits its own floor
let i = bestI, j = bestJ, state = 'M';
let alignedA = '', alignedB = '';
while (!(state === 'M' && (i === 0 || j === 0 || M[i][j] === 0))) {
if (state === 'M') {
const sub = a[i-1] === b[j-1] ? match : mismatch;
const cands = [['M', M[i-1][j-1]+sub], ['Ix', Ix[i-1][j-1]+sub], ['Iy', Iy[i-1][j-1]+sub]];
cands.sort((x, y) => y[1] - x[1]);
alignedA = a[i-1] + alignedA; alignedB = b[j-1] + alignedB;
state = cands[0][0]; i--; j--;
} else if (state === 'Ix') {
state = (M[i-1][j] + gapOpen >= Ix[i-1][j] + gapExtend) ? 'M' : 'Ix';
alignedA = a[i-1] + alignedA; alignedB = '-' + alignedB; i--;
} else {
state = (M[i][j-1] + gapOpen >= Iy[i][j-1] + gapExtend) ? 'M' : 'Iy';
alignedA = '-' + alignedA; alignedB = b[j-1] + alignedB; j--;
}
}
return { score: best, alignedA, alignedB };
}On this page's A/B pair, this returns 9, aligning
A's TAAGGACCGC (positions 5–14) against B's
TAAGCCGCTC (positions 2–11), specifically B's TAAG and
CCGC: eight matched characters (+2 each) around one real length-2 gap where
A has two extra characters (GA) that B doesn't
(open −6 + extend −1 = −7). Total: 8×2 − 7 = 9. Everything before position 5
in A (GTG), everything after position 14 (nothing, it's the last character
but it's excluded — see Pitfalls), the leading T in B, and the trailing
TC in B are never touched by the alignment at all, exactly Smith-Waterman's
own point, now with a gap-cost model that actually distinguishes one long indel from several short
ones.
Reading the answer out of M's bottom-right corner instead of scanning for its
true maximum reproduces Smith-Waterman's own first pitfall here, and it's wrong just as often.
On this page's own pair, M[14][11] (the corner) is 2 — not the true
maximum, 9, sitting at M[13][9]. The corner reading forces the alignment
to account for all of A and all of B, dragging in
A's trailing, unrelated A and B's trailing, unrelated
TC — both real mismatched flanks the true local alignment simply ignores. Stress-tested
directly against this page's own algorithm across 20,000 random pairs (lengths 5–14, DNA alphabet):
wrong on 93.9% of them, and never once scored higher than the correct
reading in any trial — only equal or worse, the same one-directional signature Gotoh's own collapsed-
matrix bug has, because the corner is always a valid cell in the same table, just not
necessarily the best one.
Dropping the floor entirely doesn't just make the search "less local" — it silently turns
this page's own algorithm into exactly Gotoh's Algorithm, scored end to end, with no trace of local
search left at all. Remove the max(0, …) from M's recurrence (select
No floor (bug — reduces to Gotoh) above) and the boundary conditions have to change to
match — Ix's first column and Iy's first row now pre-pay a real gap the way
Gotoh's own base cases do, because there's no more free restart to fall back on. On this page's pair,
the score drops from 9 to −6, forcing an alignment
(GTGTAAGGACCGC-A against --TTAAG--CCGCTC) that pays real gap-open penalties
just to line up characters neither sequence's shared region needed reconciled at all. Stress-tested
across the same 20,000 pairs: wrong on 99.8% of them — higher than the corner-read
bug, because this one corrupts the fill itself, not just which cell gets read afterward — and, like the
corner-read bug, never once scored higher than the correct local search (a local search can always
choose to align everything if that happens to be optimal; it's never worse than being forced to).
Time: O(m·n) — the same single pass as Gotoh's own three-matrix table;
Smith-Waterman's floor and max-tracking each add only constant work per cell, so fusing the two adds no
new order-of-growth cost over either source page alone. Space: O(m·n),
three matrices, for the same traceback reasons both source pages keep their full tables rather than a
rolling window.
Reach for this page specifically when both of its source pages' own reasons apply at once:
only a region of the two sequences is expected to match (Smith-Waterman's own case) and the
gap-cost model matters enough that a single long indel should score better than several scattered short
ones (Gotoh's own case) — real DNA/protein local alignment with realistic gap costs, which is to say,
what BLAST actually runs. Reach for plain Smith-Waterman
instead when a flat per-character gap cost is good enough; reach for plain Gotoh's Algorithm instead when the two sequences are meant
to correspond end to end. One honest scope note this page shares with Smith-Waterman's own: real BLAST
doesn't run this recurrence against every candidate sequence in a database — it first finds short exact
"seed" matches and only extends the ones that look promising (with an early-termination heuristic,
"X-drop"), because running the full O(m·n) table against everything in a genome database
would be far too slow. That seed-and-extend layer is a genuine further optimization, not built here.
Substitution matrices (BLOSUM, PAM) remain the other open question Smith-Waterman's own page already
named — this page's fixed match/mismatch numbers sidestep it the same way. For a side-by-side
comparison across all thirteen approximate-match entries, see Choosing an Approximate String Matcher.