Introduction

A human genome is roughly three billion A, T, C, and G characters written in a row. Somewhere in that string are about twenty thousand genes — the instructions a cell reads to make proteins. But genes do not come with brackets. They are scattered islands separated by vast stretches of non-coding DNA, and the boundaries between them are blurry.

The central challenge of computational gene finding is to read that raw string and mark each position: is this base part of a coding exon (translated into protein), a non-coding intron (spliced out before translation), or intergenic DNA between genes entirely?

Hidden Markov models (HMMs) are the workhorse answer. They treat the genome as a sequence of observations emitted by a machine that switches between hidden states — exon, intron, intergenic — according to known probabilities. The Viterbi algorithm, introduced by Andrew Viterbi in 1967 for error-correcting codes, then finds the single most likely sequence of states for the whole DNA string in linear time. What looks like an impossible jigsaw becomes a clean dynamic-programming sweep from left to right.

Try It: Viterbi Labeling

The sequence below is a short stretch of toy DNA. Each base was "emitted" by one of three hidden states: E (exon), I (intron), or G (intergenic). Click Run Viterbi to let the algorithm find the most likely state path, then hover over any base to see the winning probability at that position.

<!-- Viterbi HMM gene-finding demo -->
<div class="hint-box">A toy DNA sequence is shown above. Click <b>Run Viterbi</b> to label each base as Exon (E), Intron (I), or Intergenic (G) using a hidden Markov model. Hover over any base to see its best log-probability.</div>
<div id="seq-row" class="seq-row" aria-label="DNA sequence bases"></div>
<div id="state-row" class="state-row" aria-label="Predicted hidden states"></div>
<div class="legend">
  <span class="leg-e">E = Exon</span>
  <span class="leg-i">I = Intron</span>
  <span class="leg-g">G = Intergenic</span>
</div>
<div id="tooltip" class="tooltip" role="status" aria-live="polite"></div>
<div class="btns">
  <button id="btn-run" type="button">Run Viterbi</button>
  <button id="btn-reset" type="button" class="ghost">Reset</button>
</div>
<div id="status-bar" class="status-bar" role="status" aria-live="polite">Click "Run Viterbi" to decode the sequence.</div>

/* Styles for HMM Viterbi gene-finding demo */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; margin: 0; color: #222; }
.hint-box { font-size: .85rem; color: #444; margin-bottom: .7rem; line-height: 1.5; }
.seq-row, .state-row {
  display: flex; gap: 3px; margin-bottom: 4px; flex-wrap: nowrap; overflow-x: auto;
}
.base, .lbl {
  width: 32px; min-width: 32px; height: 32px;
  display: flex; align-items: center; justify-content: center;
  font: 700 13px ui-monospace, monospace; border-radius: 6px;
  cursor: default; user-select: none; transition: transform .1s;
}
/* Base cell colors and label state colors */
.base { background: #dde3ea; border: 1px solid #b8c2cc; }
.base:hover { transform: scale(1.12); }
.lbl { font-size: 11px; border: 1px solid transparent; }
.lbl-E { background: #c8e6c9; border-color: #81c784; color: #1b5e20; }
.lbl-I { background: #ffe0b2; border-color: #ffb74d; color: #e65100; }
.lbl-G { background: #e8eaf6; border-color: #9fa8da; color: #283593; }
.lbl-hidden { background: #ececec; border-color: #ccc; color: #999; }
.legend { font-size: .78rem; display: flex; gap: .8rem; margin: .3rem 0; }
.leg-e { color: #1b5e20; font-weight: 600; }
.leg-i { color: #e65100; font-weight: 600; }
.leg-g { color: #283593; font-weight: 600; }
.tooltip { min-height: 1.4em; font-size: .85rem; color: #555; margin: .3rem 0; }
.btns { display: flex; gap: .5rem; margin: .5rem 0; flex-wrap: wrap; }
button {
  font: 600 13px system-ui; padding: .4rem .85rem;
  border: 1px solid #1d3557; background: #1d3557; color: #fff;
  border-radius: 8px; cursor: pointer;
}
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .45; cursor: not-allowed; }
.status-bar { font-size: .9rem; font-weight: 600; min-height: 1.3em; }
.status-bar.ok { color: #0a7d33; }
.status-bar.bad { color: #c92f3c; }
/* Dark-mode overrides */
@media (prefers-color-scheme: dark) {
  body { color: #e2e8f0; background: #1a202c; }
  .hint-box { color: #a0aec0; }
  .base { background: #2d3748; border-color: #4a5568; color: #e2e8f0; }
  .lbl-E { background: #1b4332; border-color: #2d6a4f; color: #b7e4c7; }
  .lbl-I { background: #7c2d12; border-color: #c2410c; color: #fed7aa; }
  .lbl-G { background: #1e1b4b; border-color: #4338ca; color: #c7d2fe; }
  .lbl-hidden { background: #2d3748; border-color: #4a5568; color: #718096; }
  .tooltip { color: #a0aec0; }
  button { background: #4a5568; border-color: #718096; color: #e2e8f0; }
  button.ghost { background: transparent; color: #a0aec0; border-color: #4a5568; }
}

// Viterbi algorithm for HMM gene finding on a toy DNA sequence
const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));

// Toy DNA sequence (26 bases)
// 4 intergenic(AT) + 6 exon(GC) + 6 intron(AT) + 6 exon(GC) + 4 intergenic(AT)
const SEQ = 'ATATGCGCGCATATATCGCGCGTATA';

// Reference state sequence used to score accuracy
// G=intergenic, E=exon, I=intron
const TRUE_STATES = 'GGGGEEEEEEIIIIIIEEEEEEGGGG'.split('');

// Hidden Markov model definition (states, transitions, emissions)
// States: E(exon), I(intron), G(intergenic)
const STATES = ['E', 'I', 'G'];

// Transition probability matrix (log space computed at runtime)
// Row = from-state, Col = to-state (E, I, G)
const TRANS = {
  E: { E: 0.75, I: 0.15, G: 0.10 },
  I: { E: 0.05, I: 0.80, G: 0.15 },
  G: { E: 0.10, I: 0.05, G: 0.85 }
};

// Emission probability table per state
// Emission probabilities per nucleotide per state
// Exons are GC-rich; introns are AT-rich; intergenic is slightly AT-biased
const EMIT = {
  E: { A: 0.10, T: 0.10, C: 0.40, G: 0.40 },
  I: { A: 0.40, T: 0.40, C: 0.10, G: 0.10 },
  G: { A: 0.30, T: 0.30, C: 0.20, G: 0.20 }
};

// Initial state probabilities
const INIT = { E: 0.05, I: 0.05, G: 0.90 };

let vitPath = null;
let vitScores = null;

// Viterbi decoding — returns best path and per-position score table
function viterbi(seq) {
  const n = seq.length;
  // dp[t][s] = log-prob of best path ending at state s at position t
  const dp = [];
  const bt = []; // Backpointer table for traceback
  // Initialization step — seed with log(init) + log(emit)
  const first = {};
  for (const s of STATES) {
    first[s] = Math.log(INIT[s]) + Math.log(EMIT[s][seq[0]]);
  }
  dp.push(first);
  bt.push({});
  // Recursion step — find best predecessor for each state
  for (let t = 1; t < n; t++) {
    const cur = {};
    const curBt = {};
    for (const s of STATES) {
      let best = -Infinity, bestPrev = null;
      for (const prev of STATES) {
        const val = dp[t - 1][prev] + Math.log(TRANS[prev][s]);
        if (val > best) { best = val; bestPrev = prev; }
      }
      cur[s] = best + Math.log(EMIT[s][seq[t]]);
      curBt[s] = bestPrev;
    }
    dp.push(cur);
    bt.push(curBt);
  }
  // Traceback from highest-scoring final state
  let last = STATES.reduce((a, b) => dp[n - 1][a] > dp[n - 1][b] ? a : b);
  const path = [last];
  for (let t = n - 1; t > 0; t--) {
    last = bt[t][last];
    path.unshift(last);
  }
  return { path, scores: dp };
}

function getColor(s) {
  return s === 'E' ? 'lbl-E' : s === 'I' ? 'lbl-I' : 'lbl-G';
}

function renderSeq() {
  const row = document.getElementById('seq-row');
  row.innerHTML = '';
  for (let i = 0; i < SEQ.length; i++) {
    const d = document.createElement('div');
    d.className = 'base';
    d.textContent = SEQ[i];
    d.title = i18nFmt('Position %pos%: base %base%', { pos: i + 1, base: SEQ[i] });
    d.addEventListener('mouseenter', () => showTip(i));
    d.addEventListener('mouseleave', () => clearTip());
    row.appendChild(d);
  }
}

function renderStates(path) {
  const row = document.getElementById('state-row');
  row.innerHTML = '';
  for (let i = 0; i < SEQ.length; i++) {
    const d = document.createElement('div');
    if (path) {
      d.className = 'lbl ' + getColor(path[i]);
      d.textContent = path[i];
      d.title = i18nFmt('Position %pos%: predicted state %state%', { pos: i + 1, state: path[i] });
      d.addEventListener('mouseenter', () => showTip(i));
      d.addEventListener('mouseleave', () => clearTip());
    } else {
      d.className = 'lbl lbl-hidden';
      d.textContent = '?';
    }
    row.appendChild(d);
  }
}

function showTip(i) {
  const tip = document.getElementById('tooltip');
  if (!vitPath || !vitScores) {
    tip.textContent = i18nFmt('Position %pos% — base %base%. Run Viterbi to see predicted state.', { pos: i + 1, base: SEQ[i] });
    return;
  }
  const s = vitPath[i];
  const score = vitScores[i][s].toFixed(2);
  tip.textContent = i18nFmt('Position %pos% — base %base% → state %state% (log-prob: %score%)', { pos: i + 1, base: SEQ[i], state: s, score });
}

function clearTip() {
  document.getElementById('tooltip').textContent = '';
}

function setStatus(msg, cls) {
  const el = document.getElementById('status-bar');
  el.textContent = msg;
  el.className = 'status-bar ' + (cls || '');
}

function countMatches(path) {
  return path.filter((s, i) => s === TRUE_STATES[i]).length;
}

document.getElementById('btn-run').addEventListener('click', () => {
  const btn = document.getElementById('btn-run');
  btn.disabled = true;
  setStatus('Running Viterbi...', '');
  // Yield to UI thread so the status message renders before the run
  setTimeout(() => {
    const result = viterbi(SEQ.split(''));
    vitPath = result.path;
    vitScores = result.scores;
    renderStates(vitPath);
    const matches = countMatches(vitPath);
    setStatus(
      i18nFmt('Done! Matched %matches% of %total% bases against reference states.', { matches, total: SEQ.length }),
      'ok'
    );
    btn.disabled = false;
  }, 60);
});

document.getElementById('btn-reset').addEventListener('click', () => {
  vitPath = null;
  vitScores = null;
  renderStates(null);
  setStatus('Click "Run Viterbi" to decode the sequence.', '');
  document.getElementById('tooltip').textContent = '';
  document.getElementById('btn-run').disabled = false;
});

// Initial render — sequence shown, states hidden
renderSeq();
renderStates(null);
Result
Console

Notice that the algorithm never backtracks — it sweeps left to right in a single pass, keeping only the best predecessor at each step. The traceback arrow then recovers the full path in reverse. For a genome of length nn with kk states the total work is O(k2⋅n)O(k^2 \cdot n) — linear in the sequence length no matter how many states you add.

The Real Complexity

HMM gene finding splits into two very different computational problems.

Decoding (Viterbi) — given a trained model and a DNA sequence of length nn, find the most likely state path. Naively you would enumerate all knk^n state sequences, but dynamic programming collapses this to O(k2⋅n)O(k^2 \cdot n): at each position you only need the best score for each state and a pointer to where it came from. On a human chromosome (n≈2×108n \approx 2 \times 10^8) with a handful of states, Viterbi finishes in seconds.

Training (Baum-Welch / EM) — given many labeled sequences, learn the transition and emission probabilities. The Baum-Welch algorithm (a special case of Expectation-Maximization) iterates forward-backward passes until convergence. Each pass is also O(k2⋅n)O(k^2 \cdot n), but the number of iterations is not bounded in theory — the algorithm climbs toward a local maximum of the likelihood, not necessarily the global one. Choosing the right model architecture (how many states, which transitions to allow) is an unsolved biological and statistical question.

Parameter estimation is further complicated by class imbalance: exons make up only about 1.5% of the human genome, so a naive model can ignore them entirely and still score well. Sophisticated gene finders like GENSCAN (Burge & Karlin, 1997) and later tools use dozens of carefully tuned states, length distributions, and splice-site models to overcome this. Related ideas appear in sequence alignment and Bayesian inference, where the tension between model complexity and tractability is the same.

Where It Matters

HMM gene finding is not an academic exercise — it is infrastructure for modern biology:

  • Genome annotation: every reference genome (human, mouse, zebrafish, wheat) ships with a gene annotation track produced partly by HMM gene finders such as GENSCAN, Augustus, and GeneMark. Without these annotations, interpreting sequencing results would be impossible.
  • Rare disease diagnosis: clinical whole-genome sequencing pipelines flag variants that fall in predicted exons; a mislabeled exon boundary can cause a real mutation to be missed.
  • Comparative genomics: aligning gene structures across species reveals which exons are evolutionarily conserved — a strong signal that they are functionally important.
  • RNA-seq analysis: modern RNA sequencing uses splice-aware aligners that rely on the same HMM intuition to handle reads that span intron–exon boundaries.
  • Beyond DNA: the same Viterbi framework labels part-of-speech tags in natural language processing, decodes convolutional codes in digital communications, and segments time series in finance and neuroscience. The hidden states change; the algorithm does not.

The genome assembly problem that precedes gene finding also leans on probabilistic sequence models — together they form the computational backbone of genomics.

Conclusion

The genome is a text written in four letters, and for most of history we could not read it. Hidden Markov models gave us a grammar: states for exon, intron, and intergenic DNA, transition probabilities learned from biology, and emission probabilities tuned to the quirks of each organism's codon usage.

The Viterbi algorithm then does something remarkable — it finds the single most likely annotation of the entire sequence in one left-to-right pass, in time linear in the length of the genome. An exponential search collapses to a linear scan, and what looked intractable becomes routine.

That shift — from brute-force enumeration to dynamic programming over a probabilistic graph — is one of the deepest ideas in computational biology, and it shows up wherever sequences carry hidden structure. Every time a gene finder annotates a newly sequenced genome, a variant of Viterbi is sweeping quietly from one end to the other, turning raw letters into meaning.

Share this article

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

Comments

Loading comments...

https://www.kipuhub.com/en/article/hidden-markov-gene-finding/Content licensed under CC BY-NC 4.0.