HMM Gene Finding

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.

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.

<!-- {{c_html_intro}} -->
<div class="hint-box">{{hint_text}}</div>
<div id="seq-row" class="seq-row" aria-label="{{aria_sequence}}"></div>
<div id="state-row" class="state-row" aria-label="{{aria_states}}"></div>
<div class="legend">
  <span class="leg-e">E {{legend_exon}}</span>
  <span class="leg-i">I {{legend_intron}}</span>
  <span class="leg-g">G {{legend_intergenic}}</span>
</div>
<div id="tooltip" class="tooltip" role="status" aria-live="polite"></div>
<div class="btns">
  <button id="btn-run" type="button">{{btn_run}}</button>
  <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
</div>
<div id="status-bar" class="status-bar" role="status" aria-live="polite">{{status_ready}}</div>

/* {{c_css_intro}} */
* { 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;
}
/* {{c_base_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; }
/* {{c_dark_mode}} */
@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; }
}

// Code not found

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 $n$ with $k$ states the total work is $O(k^2 \cdot n)$ — linear in the sequence length no matter how many states you add.

HMM gene finding splits into two very different computational problems.

Decoding (Viterbi) — given a trained model and a DNA sequence of length $n$, find the most likely state path. Naively you would enumerate all $k^n$ state sequences, but dynamic programming collapses this to $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 \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(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.

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.

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.