Introduction

When biologists compare two DNA or protein sequences, they rarely expect the entire sequences to match. What they are looking for is a region — perhaps a few dozen letters — that appears in both sequences with only minor differences. That needle-in-a-haystack search is called local alignment, and the algorithm that solves it optimally is Smith-Waterman (Temple Smith and Michael Waterman, 1981).

It is a close cousin of the earlier sequence alignment algorithm by Needleman and Wunsch (1970), which finds the best global alignment — the best way to match the whole of one sequence against the whole of another. Smith-Waterman makes one small but powerful change: it floors the scoring matrix at zero. Whenever the running score would go negative, it resets to zero instead of carrying a penalty forward. That single rule means the algorithm ignores poor-matching flanks and focuses on the best-matching core.

The result is a guaranteed-optimal local alignment found in polynomial time — an exact algorithm that no heuristic search can beat for correctness, though many faster approximations exist for large databases.

Try It

Type any two short sequences below and press Align. The demo fills the Smith-Waterman scoring matrix and then traces back from the highest-scoring cell to reveal the best local alignment.

<!-- Demo layout — inputs at top, scoring matrix below, alignment result at bottom -->
<div class="inputs">
  <label>Sequence A <input id="seqA" type="text" maxlength="14" placeholder="e.g. ACGTACGT" value="ACGTACGT" /></label>
  <label>Sequence B <input id="seqB" type="text" maxlength="14" placeholder="e.g. TACGTTAC" value="TACGTTAC" /></label>
  <div class="scores-row">
    <label class="score-lbl">Match<input id="matchScore" type="number" value="2" min="1" max="5" /></label>
    <label class="score-lbl">Mismatch<input id="mismatchScore" type="number" value="-1" min="-5" max="0" /></label>
    <label class="score-lbl">Gap<input id="gapScore" type="number" value="-1" min="-5" max="0" /></label>
  </div>
  <button id="btnAlign" type="button">Align</button>
</div>
<div id="matrixWrap" class="matrix-wrap" role="region" aria-label="Smith-Waterman scoring matrix"></div>
<div id="resultBox" class="result-box" aria-live="polite"></div>

/* Global reset and input layout */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; font-size: 14px; }
.inputs { display: flex; flex-direction: column; gap: .5rem; margin-bottom: .8rem; }
.inputs label { display: flex; flex-direction: column; gap: .2rem; font-weight: 600; font-size: .85rem; color: #444; }
.inputs input[type="text"] { font: 700 1rem ui-monospace,monospace; padding: .3rem .5rem; border: 1px solid #adb1b8; border-radius: 6px; width: 100%; letter-spacing: .08em; }
.scores-row { display: flex; gap: .7rem; flex-wrap: wrap; }
.score-lbl { display: flex; flex-direction: column; gap: .2rem; font-weight: 600; font-size: .8rem; color: #444; }
.score-lbl input[type="number"] { width: 60px; padding: .3rem .4rem; border: 1px solid #adb1b8; border-radius: 6px; font-size: .9rem; }
button { font: 600 14px system-ui,sans-serif; padding: .45rem 1rem; border: 1px solid #1d3557; background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; margin-top: .2rem; }
button:hover { background: #162942; }
/* Scoring matrix color coding — green=high, red=best cell, teal=traceback path */
.matrix-wrap { overflow-x: auto; margin: .6rem 0; }
table { border-collapse: collapse; font: .75rem ui-monospace,monospace; }
th, td { width: 28px; height: 28px; text-align: center; border: 1px solid #d0d7de; }
th { background: #e8eef3; font-weight: 700; color: #1d3557; font-size: .7rem; }
td { color: #222; }
td.zero { color: #bbb; }
td.hi { background: #2d9e6b; color: #fff; font-weight: 700; }
td.path { background: #a8e6c9; color: #0a5c3a; font-weight: 700; }
td.best { background: #e63946; color: #fff; font-weight: 800; }
/* Result box shown after alignment */
.result-box { margin-top: .6rem; padding: .6rem .8rem; border-radius: 8px; background: #f0f6fa; border: 1px solid #cdd9e3; min-height: 2.5rem; }
.result-box.ok { background: #e6f7ee; border-color: #7ecba3; }
.result-box .score-line { font-weight: 700; color: #1d3557; margin-bottom: .3rem; }
.result-box .align-row { font: .95rem ui-monospace,monospace; letter-spacing: .08em; white-space: pre; }
.result-box .align-match { color: #0a7d33; }
.result-box .align-label { display: inline-block; width: 2.4rem; font-size: .75rem; color: #666; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Smith-Waterman local alignment: fill an (m+1)x(n+1) matrix with zero floor.
// Each cell = max(0, diag+sub, up+gap, left+gap). Zero floor is the key local-vs-global difference.
// Traceback starts at the highest cell and follows pointers until a zero cell is reached.

function smithWaterman(a, b, match, mismatch, gap) {
  // Build (m+1)x(n+1) scoring matrix H and traceback pointer matrix T, both zero-initialized
  const m = a.length, n = b.length;
  const H = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
  const T = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0)); // traceback pointer matrix
  // Fill each cell with the Smith-Waterman recurrence; track global maximum
  let bestScore = 0, bestI = 0, bestJ = 0;
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      const diag = H[i-1][j-1] + (a[i-1] === b[j-1] ? match : mismatch);
      const up   = H[i-1][j] + gap;
      const left = H[i][j-1] + gap;
      const best4 = Math.max(0, diag, up, left);
      H[i][j] = best4;
      // Record which predecessor gave the maximum (1=diagonal, 2=up, 3=left, 0=zero-floor)
      if (best4 === 0) T[i][j] = 0;
      else if (best4 === diag) T[i][j] = 1; // diagonal match/mismatch
      else if (best4 === up)   T[i][j] = 2; // gap in sequence B
      else                     T[i][j] = 3; // gap in sequence A
      if (best4 > bestScore) { bestScore = best4; bestI = i; bestJ = j; }
    }
  }
  // Traceback from highest cell, building aligned strings
  const path = new Set();
  let ci = bestI, cj = bestJ;
  const aAligned = [], bAligned = [], midLine = [];
  while (ci > 0 && cj > 0 && H[ci][cj] > 0) {
    path.add(ci + ',' + cj);
    const dir = T[ci][cj];
    if (dir === 1) { aAligned.unshift(a[ci-1]); bAligned.unshift(b[cj-1]); midLine.unshift(a[ci-1]===b[cj-1]?'|':' '); ci--; cj--; }
    else if (dir === 2) { aAligned.unshift(a[ci-1]); bAligned.unshift('-'); midLine.unshift(' '); ci--; }
    else { aAligned.unshift('-'); bAligned.unshift(b[cj-1]); midLine.unshift(' '); cj--; }
  }
  return { H, bestScore, bestI, bestJ, path, aAligned, bAligned, midLine };
}

function renderMatrix(a, b, H, path, bestI, bestJ) {
  // Build HTML table from matrix values, coloring best cell, path, and zeros
  const wrap = document.getElementById('matrixWrap');
  const tbl = document.createElement('table');
  // Header row with sequence B characters as column labels
  const hdr = tbl.insertRow();
  hdr.insertCell().textContent = '';
  hdr.insertCell().textContent = '';
  for (const ch of b) { const th = document.createElement('th'); th.textContent = ch; hdr.appendChild(th); }
  for (let i = 0; i <= a.length; i++) {
    const tr = tbl.insertRow();
    const lh = document.createElement('th');
    lh.textContent = i === 0 ? '' : a[i-1];
    tr.appendChild(lh);
    for (let j = 0; j <= b.length; j++) {
      const td = tr.insertCell();
      td.textContent = H[i][j];
      if (i === bestI && j === bestJ) td.className = 'best';
      else if (path.has(i + ',' + j)) td.className = 'path';
      else if (H[i][j] === 0) td.className = 'zero';
      else td.className = 'hi';
    }
  }
  wrap.innerHTML = '';
  wrap.appendChild(tbl);
}

function renderResult(bestScore, aAligned, bAligned, midLine) {
  // Display score and aligned sequences with pipe characters for exact matches
  const box = document.getElementById('resultBox');
  if (bestScore === 0) {
    box.className = 'result-box';
    box.innerHTML = '<span class="score-line">No local match found (all cells are zero).</span>';
    return;
  }
  box.className = 'result-box ok';
  box.innerHTML =
    '<div class="score-line">' + i18nFmt('Best local alignment score: %score%', { score: bestScore }) + '</div>' +
    '<div class="align-row"><span class="align-label">A:</span>' + aAligned.join('') + '</div>' +
    '<div class="align-row align-match"><span class="align-label"></span>' + midLine.join('') + '</div>' +
    '<div class="align-row"><span class="align-label">B:</span>' + bAligned.join('') + '</div>';
}

function run() {
  const a = document.getElementById('seqA').value.toUpperCase().replace(/[^A-Z]/g, '');
  const b = document.getElementById('seqB').value.toUpperCase().replace(/[^A-Z]/g, '');
  const match    = parseInt(document.getElementById('matchScore').value, 10)    || 2;
  const mismatch = parseInt(document.getElementById('mismatchScore').value, 10) || -1;
  const gap      = parseInt(document.getElementById('gapScore').value, 10)      || -1;
  if (!a || !b) return;
  const res = smithWaterman(a, b, match, mismatch, gap);
  renderMatrix(a, b, res.H, res.path, res.bestI, res.bestJ);
  renderResult(res.bestScore, res.aAligned, res.bAligned, res.midLine);
}

document.getElementById('btnAlign').addEventListener('click', run);
run();
Result
Console

Notice what happens when the sequences share only a short common region: the high scores cluster in one corner of the matrix and the traceback arrow path stops as soon as the score would drop to zero — that stop is exactly the "local" in local alignment. A global algorithm like Needleman-Wunsch would be forced to align the entire sequences; Smith-Waterman freely ignores the mismatching ends.

The Real Complexity

Smith-Waterman is exact — it is guaranteed to find the highest-scoring local alignment — but that guarantee has a price.

  • Time: O(mn)O(mn) where mm and nn are the lengths of the two sequences. Every cell of the (m+1)×(n+1)(m+1) \times (n+1) matrix must be computed.
  • Space: O(mn)O(mn) to store the full matrix (reducible to O(min⁡(m,n))O(\min(m,n)) if only the score is needed, not the traceback path).
  • The zero floor is the key difference from Needleman-Wunsch. Each cell is H(i,j)=max⁡(0,  H(i−1,j−1)+s(ai,bj),  H(i−1,j)−g,  H(i,j−1)−g)H(i,j) = \max\bigl(0,\; H(i-1,j-1)+s(a_i,b_j),\; H(i-1,j)-g,\; H(i,j-1)-g\bigr), where ss is the substitution score and gg is the gap penalty. The max⁡(…,0)\max(\dots, 0) term prevents negative scores from propagating.
  • Traceback starts at the cell with the maximum value H∗=max⁡i,jH(i,j)H^* = \max_{i,j} H(i,j) and follows the choices backwards until a zero cell is reached.
  • In practice, databases contain billions of letters. Running exact Smith-Waterman against a whole genome database would take months. Heuristics like BLAST (1990) sacrifice guaranteed optimality to run in roughly O(mlog⁡n)O(m \log n) — they first find short exact matches (seeds) and only extend promising regions, finding the vast majority of biologically interesting alignments in seconds.

The algorithm is solved and complete: it was published by Smith and Waterman in 1981 and has not been surpassed for correctness. Modern hardware (GPUs, SIMD) can accelerate the matrix fill by a factor of 100×, but the fundamental O(mn)O(mn) character remains.

Where It Matters

The ability to find the best-matching substring between two sequences is foundational to modern biology and beyond:

  • Genome annotation: when a newly sequenced gene is uploaded to GenBank, Smith-Waterman (or its BLAST approximation) compares it against millions of known sequences to infer its function.
  • Protein homology: two proteins with similar local regions often share a conserved functional domain — a binding site, an enzyme active site, or a structural motif — even when their overall sequences are quite different.
  • Drug discovery: finding that a pathogen's protein shares a local region with a human protein helps predict which drugs might bind — or cause side effects.
  • Forensic DNA analysis: short tandem repeat matching and mitochondrial DNA comparison both rely on local alignment to identify individuals from partial samples.
  • Natural language processing: "fuzzy substring search" in text is conceptually the same problem; some spell-checkers use Smith-Waterman-style scoring over character sequences.

Related algorithmic ideas appear across computer science: dynamic programming tables underlie edit-distance, diff tools, and spell-checkers; the zero-floor trick generalizes to any problem where you want the best contiguous sub-solution rather than the best overall solution.

Conclusion

Smith-Waterman is one of the most elegant demonstrations of dynamic programming: a table filled in O(mn)O(mn) time, every cell depending on just three neighbors, and a single rule — never let the score go below zero — that transforms a global alignment into a local one.

The traceback from the maximum cell is not just a computational trick; it encodes a precise answer to the question "where do these two sequences most resemble each other?" That answer drove forty years of genome science, from the first sequenced genomes to today's large-scale variation databases.

Wherever two strings need to be compared — DNA, protein, text, audio fingerprints — the idea behind Smith-Waterman is almost certainly somewhere in the pipeline.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/smith-waterman/Content licensed under CC BY-NC 4.0.