Hidden Markov models

Concept

Hidden Markov models

T-109Home BU-401Threads information · systems

Statement

Finding genes and motifs probabilistically.

Why it matters

sequence-alignment and blast-database-search both find relationships by direct comparison against a known reference sequence; hidden Markov models instead build a probabilistic model of an entire sequence class (a protein family, or a structural pattern like a gene's exon/intron organisation) and score how well a new, possibly quite divergent sequence fits that model as a whole. This lets weaker, more distant relationships be detected that direct pairwise comparison to any single reference sequence would likely miss.

The technique also extends naturally beyond simple family membership: gene-finding HMMs use hidden states representing different genomic feature types (exon, intron, intergenic region) to predict gene structure directly from raw, unannotated genomic sequence, a fundamentally different kind of task from expression-clustering's search for correlated expression patterns, even though both ultimately serve the same broader bioinformatics goal of extracting biological meaning from large-scale sequence and expression data.

Hypotheses

The system has a sequence of hidden states, each emitting an observable symbol and transitioning to the next state according to the Markov property.The Markov property specifically requires that the probability of the next state depends only on the current state, not on the full history of states visited so far; this single-step memorylessness is what makes the dynamic-programming algorithms below computationally efficient. Transition and emission probabilities are known or can be estimated from representative example sequences, and are assumed stationary along the sequence.If the true underlying process's probabilities actually change partway through a sequence (non-stationarity), a model trained assuming fixed, constant probabilities throughout will systematically misfit the portion of the sequence where the true probabilities differ from those estimated.

Proof

\text{Define an HMM by a set of hidden states, a transition probability matrix } P(s_{i+1}\mid s_i)\text{, and emission probabilities } P(o_i\mid s_i)\text{.}

This is the minimal set of parameters needed to fully specify the model: which state can follow which, and what observable symbol each state is likely to emit, together defining a complete probabilistic description of the sequence class being modelled. A

P(\text{path}) = \textstyle\prod_i P(s_{i+1}\mid s_i)\, P(o_i\mid s_i)

Given a specific observed sequence, the probability of any one specific hidden-state path generating it is the product of the transition and emission probabilities along that path, a direct consequence of the Markov property's single-step independence structure (Hypotheses). A

\text{The Viterbi algorithm finds the single most probable hidden-state path via dynamic programming.}

At each position, only the best-scoring path so far to each state need be retained, since any path that was not optimal up to that point cannot become part of an optimal complete path — the same core dynamic-programming principle sequence-alignment uses for scoring optimal alignments, applied here to hidden-state paths instead of aligned sequence positions. B

P(\text{sequence}\mid\text{model}) = \textstyle\sum_{\text{all paths}} P(\text{path})

The forward algorithm instead sums probability over every possible hidden-state path, rather than finding only the single best one, computing the total probability that the model as a whole would generate the observed sequence — the key score used to ask how well a new, previously unseen sequence fits a trained model. B

\text{Because both Viterbi and forward reuse partial computations via dynamic programming, their runtime scales linearly with sequence length for a fixed number of states.}

Despite the exponentially large number of possible hidden-state paths being implicitly considered, the dynamic-programming formulation of Steps 3 and 4 avoids ever enumerating them explicitly, making both algorithms practical to run on genome-scale sequences. A

Result

P(\text{sequence}\mid\text{model}) = \textstyle\sum_{\text{paths}} P(\text{path}) \quad (\text{forward}); \qquad \text{best single path} \quad (\text{Viterbi})

Reading. A hidden Markov model assigns a principled probabilistic score to a sequence, either as the single most likely explanation (Viterbi) or as the total probability the model as a whole would generate it (forward), letting a new sequence be evaluated against an entire modelled family or structural pattern rather than against one single reference sequence.

Scope. Requires the Markov property to hold and requires reasonably well-estimated transition/emission probabilities (Hypotheses); model quality is only as good as the representativeness of the training sequences used to estimate its parameters.

Corollaries & converses

Profile HMMs, trained on a multiple alignment of many family members, generalise sequence-alignment's position-specific scoring into a full probabilistic framework, letting a new sequence be scored against an entire family rather than a single reference.
Gene-finding HMMs use hidden states corresponding to exon, intron, and intergenic regions to predict gene structure directly from raw genomic sequence, a distinct application from (but complementary to) direct database search via blast-database-search.
phylogenetic-tree-construction and expression-clustering both also rely on well-defined probabilistic or distance-based scoring of sequence or expression data; HMMs are a further, structurally distinct tool in the same broader statistical-bioinformatics toolkit.

Fails without

The Markov property does not actually hold (Hypotheses): if the next state genuinely depended on states further back than just the current one, the simple product-of-transition-probabilities calculation of Step 2 would not correctly represent the true joint probability of a path, and both the Viterbi and forward dynamic-programming recursions (which explicitly rely on this one-step memorylessness to reuse partial computations) would no longer give the correct answer.
Transition/emission probabilities are poorly estimated (Hypotheses): if trained on too few or unrepresentative example sequences, the resulting model assigns systematically inaccurate probabilities to new sequences, regardless of how correctly the Viterbi and forward algorithms themselves are implemented on top of those flawed parameters.

Common errors

Confusing the Viterbi algorithm's single best path with the forward algorithm's total probability over all paths; the two answer genuinely different questions (most likely explanation versus overall model fit) and are not interchangeable (Steps 3–4).
Assuming an HMM requires directly observing which hidden state generated each symbol during training, when in practice parameters are often estimated from example sequences via unsupervised or semi-supervised methods rather than fully labelled hidden-state data.
Assuming a higher forward-algorithm score against one model versus another automatically implies a better biological match, without accounting for model size or complexity differences that can inflate scores independent of genuine fit.
Treating "hidden" states as literally unknowable in some mystical sense, rather than simply unobserved variables (e.g. exon versus intron, both real, in-principle directly determinable biological categories) that are inferred statistically rather than measured directly in a given analysis.

Discussion

Hidden Markov models originated in speech recognition and signal-processing research before being adapted for biological sequence analysis; through the 1990s, researchers extended the framework specifically to protein family and profile modelling (profile HMMs) and to statistical gene finding, establishing HMMs as a standard tool for exactly the kind of probabilistic sequence-class modelling problem described here.

Because the Viterbi and forward algorithms differ only in whether they take the maximum or the sum over paths at each step of the same underlying dynamic-programming recursion, the two algorithms share almost identical computational structure despite answering conceptually different questions — a case where a small change in one operation (max versus sum) produces two distinct, individually useful outputs from the same underlying model.

Common misconception: that a sequence scoring well under a trained HMM must actually belong to the modelled family. A high forward-algorithm score indicates the sequence is a statistically good fit to the model's learned pattern, which is strong supporting evidence but not, on its own, definitive proof of true biological family membership; as with expression-clustering's guilt-by-association hypothesis, a strong statistical signal is a basis for further investigation rather than an automatic conclusion.

Worked examples

\text{Two-state toy model: "GC-rich" and "AT-rich" hidden states, each with its own nucleotide emission probabilities, and given transition probabilities between the two states.}

Given a short observed sequence, the Viterbi algorithm identifies the single most probable partition of the sequence into GC-rich and AT-rich segments, effectively segmenting the sequence by inferred underlying regional composition rather than requiring this boundary to be marked in the raw sequence data itself. A

P(\text{specific path}) = P(s_1)\times P(o_1\mid s_1)\times P(s_2\mid s_1)\times P(o_2\mid s_2)\times\cdots

For any one specific candidate assignment of hidden states to each observed nucleotide position, this product (Step 2 of the Proof) gives that path's probability directly; Viterbi compares all such candidate paths (efficiently, via dynamic programming, not by literal exhaustive enumeration) and returns the single highest-scoring one. B

\text{Observed sequence} \Rightarrow \text{most probable hidden GC-rich/AT-rich segmentation (Viterbi)}

Reading. A simple two-state toy example already illustrates the core value of an HMM: inferring an unobserved, biologically meaningful structure (regional base composition) purely from the observed sequence and a probabilistic model, without that structure needing to be labelled anywhere in the raw data itself.

Scope. The same two-algorithm approach (Viterbi for best explanation, forward for overall fit) scales directly from this toy two-state example up to real gene-finding and protein-family models with many more states and much longer sequences.

Problems

Explain why the forward algorithm, which sums over all possible hidden-state paths rather than finding the single best one, generally gives a higher probability value than the Viterbi algorithm's single best path probability for the identical sequence and model.
Solution
The forward algorithm's total, \(P(\text{sequence}\mid\text{model})=\sum_{\text{paths}}P(\text{path})\), sums the probabilities of every possible hidden-state path consistent with the observed sequence (Step 4), while Viterbi's value is just one term in that sum — the single largest one. Since every individual path probability is non-negative, the sum over all paths must be at least as large as, and generally strictly larger than, any single path's probability alone.
A profile HMM trained on a well-characterised protein family gives a new candidate sequence a high forward-algorithm score. Explain why this result alone is not sufficient to conclude with certainty that the candidate sequence is a true member of that family.
Solution
A high score indicates the candidate sequence statistically fits the pattern the model learned from its training sequences well, but statistical fit is not automatically identical to true biological family membership (Common misconception); model quality also depends on how representative the original training sequences were (Hypotheses), and a sufficiently generic or short model could in principle score even some non-family sequences reasonably well. Independent evidence (e.g. structural, functional, or additional sequence-based confirmation) is generally required to confirm true family membership beyond the HMM score alone.
Explain, using the Hypotheses, why an HMM trained assuming stationary (constant) transition probabilities throughout a sequence could give a poor fit to a genomic sequence in which the true underlying region-switching frequency actually changes partway through (e.g. a sequence that transitions from a gene-dense to a gene-sparse region).
Solution
The model's transition probabilities are estimated as a single fixed set of numbers assumed to apply uniformly across the whole sequence (t3 Hypothesis); if the true switching frequency between hidden states genuinely differs between the gene-dense and gene-sparse portions of the sequence, a single stationary parameter set cannot correctly capture both regimes simultaneously, and the model will systematically misfit whichever portion of the sequence differs most from the training data's overall average switching behaviour.