Introduction

Your phone fixes "teh" to "the". git diff shows exactly which lines you changed. A biologist lines up two DNA strands to see where they differ. All three are the same question: what is the cheapest way to turn one string into another, using insertions, deletions and substitutions?

That minimum cost is the edit distance, and the matching it implies is a sequence alignment. Line the two strings up, slide in gaps where one has letters the other doesn't, and count the mismatches. Among all the ways to do it, you want the one with the fewest edits.

It sounds like you'd have to try a dizzying number of gap placements — and naively, you would. But this is one of the friendly problems: a small grid solves it exactly and fast. The twist comes later, when you try to align not two strings but many.

Align Them

Try it. Type two short strings. The grid fills in the edit distance cell by cell — each cell is the cheapest cost to align the prefixes up to that point. The bottom-right corner is the total. Then the demo traces back the path that achieves it, showing the optimal alignment below.

<p class="hint">Type two short strings and hit <b>Align</b>. The grid fills with the <b>edit distance</b> — each cell is the cheapest cost to align the prefixes up to there. The bottom-right corner is the total; the <span class="g">green</span> path is the optimal alignment.</p>
<div class="row">
  <label>A <input id="a" type="text" value="kitten" maxlength="12" autocomplete="off" /></label>
  <label>B <input id="b" type="text" value="sitting" maxlength="12" autocomplete="off" /></label>
  <button id="go" type="button">Align</button>
</div>
<div class="presets">
  <button class="chip" data-a="kitten" data-b="sitting" type="button">kitten / sitting</button>
  <button class="chip" data-a="GACTT" data-b="GATCT" type="button">DNA: GACTT / GATCT</button>
  <button class="chip" data-a="sunday" data-b="saturday" type="button">sunday / saturday</button>
</div>
<div class="grid-wrap"><table id="grid"></table></div>
<div id="result" class="result"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.hint .g { color: #0a7d33; font-weight: 700; }
.row { display: flex; gap: .7rem; align-items: center; flex-wrap: wrap; margin-bottom: .5rem; }
label { font: 600 13px system-ui; color: #555; display: flex; gap: .35rem; align-items: center; }
input { font: 700 15px ui-monospace, monospace; padding: .4rem .55rem; border: 1px solid #bbb; border-radius: 7px; width: 8.5rem; color: #1d3557; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem 1rem; border: 1px solid #457b9d; background: #457b9d; color: #fff; border-radius: 8px; cursor: pointer; }
.presets { display: flex; flex-wrap: wrap; gap: .4rem; margin-bottom: .8rem; }
.chip { background: #fff; color: #457b9d; border: 1px solid #cdd9e2; font-weight: 600; padding: .35rem .6rem; font-size: .85rem; }
.chip:hover { background: #f0f4f8; }
.grid-wrap { overflow-x: auto; }
table { border-collapse: collapse; margin: .2rem 0 .6rem; }
td, th { width: 36px; height: 34px; text-align: center; border: 1px solid #e2e2e2; font: 600 14px ui-monospace, monospace; color: #333; }
th { background: #f6f8fa; color: #1d3557; font-weight: 800; border-color: #e2e2e2; }
td.path { background: #d8f3df; color: #0a7d33; font-weight: 800; border-color: #9bdcb0; }
td.corner { background: #eef3f7; }
.result { font: 700 16px ui-monospace, monospace; line-height: 1.5; }
.ali { white-space: pre; background: #f8f9fb; border: 1px solid #e6e9ee; border-radius: 8px; padding: .6rem .8rem; margin: .4rem 0; display: inline-block; }
.ali .mm { color: #c0392b; }
.ali .gap { color: #b9770e; }
.total { font-size: 1rem; color: #1d3557; margin-top: .3rem; }
.total b { color: #0a7d33; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Edit distance (Levenshtein) by dynamic programming, with traceback.
// Each cell d[i][j] = cheapest cost to align a[0..i) with b[0..j).
// Two strings -> O(n*m), exact and fast. Many strings -> NP-hard.
function align(a, b) {
  const n = a.length, m = b.length;
  const d = Array.from({ length: n + 1 }, () => new Array(m + 1).fill(0));
  for (let i = 0; i <= n; i++) d[i][0] = i;
  for (let j = 0; j <= m; j++) d[0][j] = j;
  for (let i = 1; i <= n; i++)
    for (let j = 1; j <= m; j++) {
      const cost = a[i - 1] === b[j - 1] ? 0 : 1;
      d[i][j] = Math.min(d[i - 1][j] + 1, d[i][j - 1] + 1, d[i - 1][j - 1] + cost);
    }
  // traceback from (n,m) to (0,0)
  const path = new Set();
  let topA = '', botB = '', mid = '';
  let i = n, j = m;
  path.add(i + ',' + j);
  while (i > 0 || j > 0) {
    const cost = (i > 0 && j > 0 && a[i - 1] === b[j - 1]) ? 0 : 1;
    if (i > 0 && j > 0 && d[i][j] === d[i - 1][j - 1] + cost) {
      topA = a[i - 1] + topA; botB = b[j - 1] + botB;
      mid = (cost === 0 ? '|' : '*') + mid; i--; j--;
    } else if (i > 0 && d[i][j] === d[i - 1][j] + 1) {
      topA = a[i - 1] + topA; botB = '-' + botB; mid = ' ' + mid; i--;
    } else {
      topA = '-' + topA; botB = b[j - 1] + botB; mid = ' ' + mid; j--;
    }
    path.add(i + ',' + j);
  }
  return { d, path, topA, botB, mid, dist: d[n][m] };
}

function render() {
  const a = (document.getElementById('a').value || '').trim();
  const b = (document.getElementById('b').value || '').trim();
  const grid = document.getElementById('grid');
  const result = document.getElementById('result');
  if (!a || !b) { grid.innerHTML = ''; result.innerHTML = '<p class="total">Enter two strings.</p>'; return; }
  const r = align(a, b);
  // header row: empty, empty, then b’s letters
  let html = '<tr><th class="corner"></th><th class="corner">·</th>' +
    [...b].map(c => '<th>' + c + '</th>').join('') + '</tr>';
  for (let i = 0; i <= a.length; i++) {
    const rowLabel = i === 0 ? '·' : a[i - 1];
    html += '<tr><th>' + rowLabel + '</th>';
    for (let j = 0; j <= b.length; j++) {
      const cls = r.path.has(i + ',' + j) ? ' class="path"' : '';
      html += '<td' + cls + '>' + r.d[i][j] + '</td>';
    }
    html += '</tr>';
  }
  grid.innerHTML = html;
  // colorize the alignment: * = substitution (red), - = gap (amber)
  const colorTop = [...r.topA].map((ch, k) => ch === '-' ? '<span class="gap">-</span>' : (r.mid[k] === '*' ? '<span class="mm">' + ch + '</span>' : ch)).join('');
  const colorBot = [...r.botB].map((ch, k) => ch === '-' ? '<span class="gap">-</span>' : (r.mid[k] === '*' ? '<span class="mm">' + ch + '</span>' : ch)).join('');
  result.innerHTML =
    fmt(`<div class="ali">%colorTop%
%replace%
%colorBot%</div><div class="total">Edit distance: <b>%dist%</b> — <span style="color:#0a7d33">|</span> match, <span class="mm">*</span> substitute, <span class="gap">-</span> gap.</div>`, { colorTop: colorTop, replace: r.mid.replace(/\*/g, '*'), colorBot: colorBot, dist: r.dist });
}

document.getElementById('go').addEventListener('click', render);
['a', 'b'].forEach(id => document.getElementById(id).addEventListener('keydown', e => { if (e.key === 'Enter') render(); }));
document.querySelectorAll('.chip').forEach(c =>
  c.addEventListener('click', () => { document.getElementById('a').value = c.dataset.a; document.getElementById('b').value = c.dataset.b; render(); }));
render();
Result
Console

Each step down the path is a move: diagonal = match or substitute a letter, down or right = insert a gap. Green cells are the optimal route. Notice how the grid considers every alignment at once without ever enumerating them — that's the magic of dynamic programming.

Easy and Hard

Sequence alignment lives on both sides of the easy/hard line:

  • Checking an alignment is trivial: add up its matches, mismatches and gaps.
  • Brute force over all alignments is exponential — the number of ways to interleave gaps explodes with length.
  • But two sequences are easy. The classic dynamic program (Needleman–Wunsch / Wagner–Fischer) fills an n × m grid, so it runs in O(nm)O(nm) — polynomial, exact, fast. That's what the demo does.
  • Many sequences are hard. Optimal multiple sequence alignment — lining up dozens of DNA strands at once — is NP-hard. The grid becomes a hypercube whose size blows up with each new sequence.
  • So practice uses heuristics. Tools like BLAST, Clustal and MAFFT trade guaranteed optimality for speed, finding excellent (if not provably best) alignments on huge datasets.

It's a clean illustration of how a problem's difficulty can hinge on a single parameter: two is a breeze, k is a wall. Compare P vs NP for the bigger picture.

Where It Matters

Anywhere two sequences need comparing, alignment is at work:

  • Genomics and bioinformatics: comparing DNA, RNA and proteins to find mutations, evolutionary relationships and gene function.
  • Version control: git diff and merge tools align file versions line by line.
  • Spellcheck and autocorrect: edit distance ranks the closest dictionary words to what you typed.
  • Plagiarism and similarity detection: measuring how close two documents are.
  • Speech and handwriting recognition: aligning a noisy signal to candidate transcriptions.

The two-sequence DP is fast enough to run constantly under the hood; the NP-hard multiple case is where genomics pours its cleverest heuristics.

Conclusion

Sequence alignment is a two-faced problem, and that's exactly what makes it instructive. For two strings, a humble grid quietly evaluates an exponential number of alignments and hands you the best one in polynomial time — the everyday workhorse behind spellcheck, diff and DNA comparison.

Add more sequences and the same idea tips over into NP-hardness, which is why genomics leans on heuristics. One problem, two regimes: a reminder that complexity often turns on a single dimension, and that knowing which side you're on tells you whether to reach for an exact grid or a clever approximation.

Share this article

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

Comments

Loading comments...

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