- Hidden Markov models (HMMs) are probabilistic models used in bioinformatics to analyze biological sequences and infer hidden biological states from observable data. They are particularly useful for gene prediction, protein family identification, DNA sequence analysis, RNA structure prediction, sequence alignment, and the identification of functional regions in genomes. HMMs combine probability theory, statistics, and dynamic programming to identify patterns that may not be directly visible in DNA, RNA, or protein sequences.
- A hidden Markov model consists of a set of hidden states, observable symbols, transition probabilities, and emission probabilities. The hidden states represent biological features that cannot be observed directly, such as whether a nucleotide belongs to an exon, intron, promoter, or intergenic region. The observable symbols are the actual data, such as DNA nucleotides, amino acids, or sequencing-derived measurements. Transition probabilities describe the likelihood of moving from one hidden state to another, while emission probabilities describe the likelihood that a particular state produces a specific observation.
- The defining feature of an HMM is that the current hidden state depends probabilistically on the previous hidden state, while the observed symbol depends probabilistically on the current state. This assumption is known as the first-order Markov property. Although real biological systems can have more complex dependencies, HMMs provide a useful approximation that makes large-scale sequence analysis computationally manageable.
- An HMM is commonly represented by the parameters (\lambda = (A, B, \pi)), where (A) is the state-transition probability matrix, (B) is the emission probability distribution, and (\pi) is the initial-state probability distribution. The initial probabilities describe the likelihood of beginning in each state. Transition probabilities are written as (a_{ij} = P(q_t=j \mid q_{t-1}=i)), and emission probabilities are written as (b_j(o_t) = P(o_t \mid q_t=j)). Together, these parameters describe how hidden biological states evolve and generate observable sequences.
- For example, consider a simplified DNA sequence model with two hidden states: GC-rich and AT-rich. The model assigns probabilities to transitions between these states and to the emission of nucleotides A, T, G, and C from each state. A region containing many G and C nucleotides may be more likely to originate from the GC-rich state, while a region dominated by A and T may be more likely to originate from the AT-rich state. The model uses both the observed nucleotide composition and the probability of changing between states to infer the most likely underlying sequence of states.
- The probability of an observed sequence and a particular hidden-state sequence is calculated by combining the initial-state probability, the transition probabilities, and the emission probabilities. For a sequence of observations (O=(o_1,o_2,\ldots,o_T)) and hidden states (Q=(q_1,q_2,\ldots,q_T)), the joint probability is (P(O,Q \mid \lambda)=\pi_{q_1}b_{q_1}(o_1)\prod_{t=2}^{T}a_{q_{t-1}q_t}b_{q_t}(o_t)). This expression represents the probability that the model follows a particular hidden-state path and produces the observed sequence.
- Three fundamental computational problems are associated with hidden Markov models. The first is the evaluation problem, which calculates the probability of an observed sequence under a given model. The second is the decoding problem, which identifies the most likely hidden-state sequence responsible for the observations. The third is the learning problem, which estimates model parameters from training data. These problems are generally solved using the forward algorithm, the Viterbi algorithm, and parameter-estimation procedures such as the Baum–Welch algorithm, respectively.
- The forward algorithm calculates the total probability of an observed sequence by considering all possible hidden-state paths without explicitly enumerating each path. It uses dynamic programming to combine probabilities from shorter sequence prefixes. The forward probability at time (t) for state (j) is calculated as (\alpha_t(j)=b_j(o_t)\sum_i \alpha_{t-1}(i)a_{ij}), with initialization (\alpha_1(j)=\pi_jb_j(o_1)). The final sequence probability is obtained by summing the forward probabilities across all possible ending states. This approach is substantially more efficient than calculating every possible state sequence individually.
- The Viterbi algorithm identifies the single most probable sequence of hidden states for a given observation sequence. It uses dynamic programming to retain the best-scoring path ending in each state at each position. The recurrence is (\delta_t(j)=b_j(o_t)\max_i[\delta_{t-1}(i)a_{ij}]), with the corresponding previous state recorded for traceback. After processing the sequence, the algorithm selects the best final state and traces backward to recover the most likely state path. In gene prediction, this path may indicate which nucleotides belong to coding regions, introns, or other genomic features.
- The forward and Viterbi algorithms solve different problems. The forward algorithm sums probabilities over all possible hidden-state paths and calculates the likelihood of the observed sequence. The Viterbi algorithm selects only the single highest-probability path. Consequently, the most likely individual path is not necessarily equivalent to choosing the most probable state independently at every position. This distinction is important when interpreting model predictions.
- The Baum–Welch algorithm is a widely used method for estimating HMM parameters when the hidden states are unknown. It is an application of the expectation-maximization algorithm. During the expectation step, the model estimates the expected frequencies of state transitions and symbol emissions using the observed sequences. During the maximization step, these expected frequencies are used to update the transition and emission probabilities. The process repeats until the model parameters or likelihood values stabilize. Because the algorithm can converge to local optima, the quality of the final model may depend on its initialization, the training data, and the model structure.
- In supervised learning, HMM parameters can instead be estimated from sequences for which the hidden states are already annotated. For example, a training dataset may contain DNA sequences with experimentally supported exon and intron boundaries. Transition and emission probabilities can be estimated from observed state transitions and nucleotide frequencies, often using pseudocounts or other smoothing methods to prevent unseen events from receiving zero probability. Supervised estimation can be more interpretable when reliable annotations are available, whereas unsupervised estimation is useful when state labels are missing.
- Hidden Markov models have played an important role in gene prediction. A gene-prediction HMM may include states representing intergenic regions, start codons, coding exons, splice sites, introns, stop codons, and untranslated regions. Different states can use different nucleotide emission distributions, and transition constraints can represent biologically plausible arrangements of gene components. More sophisticated models may account for codon structure, reading frames, strand orientation, and organism-specific sequence patterns. The predicted state sequence provides a computational hypothesis about gene organization that can be evaluated against experimental evidence and other annotation methods.
- HMMs are also central to protein sequence analysis. Profile hidden Markov models represent conserved patterns in a family of related protein or nucleotide sequences. They commonly contain match states, insertion states, and deletion states. Match states model conserved alignment positions, insertion states model additional residues, and deletion transitions represent positions that may be skipped. Profile HMMs can capture position-specific residue preferences and insertion or deletion patterns more effectively than a single consensus sequence. They are widely used to identify protein domains, classify protein families, and detect remote homologs that share evolutionary relationships despite substantial sequence divergence.
- Tools such as HMMER use profile HMMs for searching biological sequence databases. Protein family resources such as Pfam use profile-based methods to support domain and family annotation. These approaches help researchers identify likely protein functions, conserved domains, and evolutionary relationships. However, a statistically significant match does not automatically establish a protein’s complete biological function; additional sequence, structural, evolutionary, and experimental evidence may be required.
- HMMs can also be applied to RNA sequence analysis. They can model conserved sequence patterns in RNA families, identify RNA genes, and support the detection of conserved motifs. In comparative genomics, models may represent conserved regions and variable regions across related sequences. HMM-based methods can also be used in sequence alignment and annotation pipelines where insertions, deletions, or transitions between biological states must be modeled probabilistically. RNA secondary structure prediction often requires methods beyond a basic HMM, such as covariance models, because base-pairing interactions can involve dependencies between distant positions.
- In epigenomics and other high-throughput analyses, HMMs can help segment genomic data into regions with distinct properties. For example, observations derived from histone modifications, DNA methylation, chromatin accessibility, or sequencing coverage may be used to infer hidden chromatin states. A state could represent an active promoter, an enhancer-like region, a transcribed region, or relatively inactive chromatin. In such applications, the observations may be continuous measurements or combinations of discrete features, so the emission model must be chosen to match the data type.
- A simple HMM can be implemented in Python using NumPy or other numerical libraries. The following example demonstrates the Viterbi algorithm for a simplified DNA sequence with two states, GC-rich and AT-rich. The model uses illustrative transition and emission probabilities to infer the most likely state for each nucleotide. These probabilities are chosen for teaching purposes and are not a trained biological model.
import numpy as np
states = [“GC-rich”, “AT-rich”]
symbols = [“A”, “C”, “G”, “T”]
# Transition probabilities: previous state -> current state
A = np.array([
[0.90, 0.10],
[0.10, 0.90]
])
# Emission probabilities for A, C, G, T
B = np.array([
[0.10, 0.40, 0.40, 0.10], # GC-rich
[0.40, 0.10, 0.10, 0.40] # AT-rich
])
initial = np.array([0.5, 0.5])
sequence = “ACGTTTGC”
symbol_index = {symbol: i for i, symbol in enumerate(symbols)}
observations = [symbol_index[s] for s in sequence]
T = len(observations)
N = len(states)
# Log probabilities avoid numerical underflow.
log_A = np.log(A)
log_B = np.log(B)
log_initial = np.log(initial)
# Viterbi dynamic programming table.
score = np.full((T, N), -np.inf)
backpointer = np.zeros((T, N), dtype=int)
# Initialization
score[0] = (
log_initial
+ log_B[:, observations[0]]
)
# Recursion
for t in range(1, T):
for j in range(N):
candidates = score[t – 1] + log_A[:, j]
best_previous = np.argmax(candidates)
score[t, j] = (
candidates[best_previous]
+ log_B[j, observations[t]]
)
backpointer[t, j] = best_previous
# Termination and traceback
last_state = np.argmax(score[T – 1])
path = [last_state]
for t in range(T – 1, 0, -1):
path.append(backpointer[t, path[-1]])
path.reverse()
predicted_states = [states[i] for i in path]
print(“DNA sequence:”, sequence)
print(“Predicted states:”, predicted_states)
print(“Best-path log probability:”, np.max(score[T – 1]))
- The example illustrates the main stages of Viterbi decoding: initialization, recursion, termination, and traceback. Log probabilities are used because multiplying many small probabilities can cause numerical underflow. In real bioinformatics applications, the model would require carefully selected states, appropriate training data, parameter estimation, and biological validation. The simple example also assumes that each nucleotide is emitted independently given its hidden state, an assumption that may be inadequate for coding sequences with codon-level structure.
- The computational cost of a standard HMM forward or Viterbi algorithm is generally (O(TN^2)), where (T) is the sequence length and (N) is the number of hidden states. Memory requirements are typically (O(TN)) when storing the complete dynamic programming table or traceback information, although optimized implementations can reduce memory use when only the sequence likelihood is required. Sparse transition structures can further reduce computational cost when each state can transition to only a small number of other states. Profile HMMs and gene-prediction models often exploit such structural constraints to improve efficiency.
- Despite their usefulness, HMMs have several limitations. The standard first-order Markov assumption restricts how hidden states depend on earlier states, and the usual emission assumption limits dependencies between observations. Complex biological sequences may exhibit long-range interactions, codon periodicity, RNA base pairing, or regulatory relationships that a basic HMM cannot represent directly. HMMs may also be sensitive to training-data quality, state definitions, model complexity, and differences between the training and target datasets. Poorly specified states or biased training sequences can lead to misleading predictions.
- Several extensions address these limitations. Higher-order HMMs incorporate dependencies on multiple previous states, while pair hidden Markov models are commonly used to represent relationships between two sequences during alignment. Profile HMMs specialize in modeling sequence families. Hidden semi-Markov models explicitly represent state-duration distributions, making them useful when segment lengths are important and cannot be adequately described by ordinary geometric duration distributions. Hierarchical and factorial HMMs can represent more complex state structures or multiple interacting latent processes. Conditional random fields provide another sequence-labeling approach that models conditional probabilities without requiring the same generative assumptions as a standard HMM.
- Model evaluation is essential when applying HMMs to biological data. Predictions should be assessed using suitable independent test datasets and measures such as sensitivity, specificity, precision, recall, F1 score, and calibration where appropriate. Gene-prediction systems may also be evaluated by exon-level, transcript-level, or nucleotide-level accuracy. Protein-family searches require careful interpretation of statistical significance, database composition, and the biological relevance of detected matches. Cross-validation, held-out datasets, comparison with established tools, and experimental confirmation can help establish whether an HMM provides reliable results.
- Hidden Markov models remain an important foundation of computational biology because they connect probabilistic modeling with efficient sequence algorithms. Their ability to infer unobserved states from biological observations makes them useful for gene annotation, protein-family detection, genomic segmentation, and many other sequence-analysis tasks. Understanding transition probabilities, emission probabilities, the forward algorithm, Viterbi decoding, and parameter estimation provides a foundation for using more advanced probabilistic models and modern machine-learning methods in bioinformatics.