Hidden Markov Models for Genomic Sequence Analysis

Most machine learning problems assume you can observe the thing you're trying to predict. You have images and want to classify them. You have customer data and want to predict churn. The target may be difficult to identify but at least it's visible.

‍

Hidden Markov Models (HMMs) solve a different kind of problem. They're designed for situations where the thing you care about is hidde  and all you can observe are the clues it leaves behind.

‍

In a recent Passion Academy session, Tamim Hussein used genomic sequence analysis to demonstrate how HMMs work, why simpler approaches fall short, and how three core algorithms make the framework practical.

‍

Slides

‍

‍

The Problem: Hidden Structure in Sequences

‍

DNA is made up of a sequence of four nucleotides: A, T, G, and C.

‍

Within this sequence are regions known as CpG islands. These regions have different statistical properties from the surrounding DNA and are often associated with gene promoter regions AKA the "switches" that help determine when genes are turned on or off.

‍

The challenge is that these regions aren't labelled. All we observe is a long sequence of nucleotides. The underlying state (whether we're currently inside or outside a CpG island) is hidden.

‍

Our goal is to infer that hidden state at every position in the sequence. This is exactly the type of problem Hidden Markov Models were designed to solve.

‍

‍

‍

The challenge is that CpG islands aren't labelled. You just see a long string of letters. The task is to infer, at each position, whether you're currently inside one of these regions or outside it. You can only observe the sequence and the underlying region type is hidden.

‍

This is exactly the kind of problem HMMs are built for.

‍

‍

Why a Sliding Window Isn't Enough

‍

A natural first idea is to use a sliding window. Move a fixed-size window along the DNA sequence, calculate how closely the nucleotides inside the window resemble a CpG island and classify each position accordingly.

‍

While intuitive, this approach quickly runs into problems.

‍

CpG islands don't all have the same length, so there's no obvious window size to choose. Small windows become noisy, while larger windows blur important boundaries. Different window sizes often produce conflicting answers for the same location and overlapping windows can classify neighbouring positions inconsistently.

‍

Instead of identifying continuous regions, the result is often a collection of isolated detections whose accuracy depends heavily on an arbitrary hyperparameter.

‍

A Different Perspective

‍

Rather than analysing each position independently, an HMM assumes the sequence was generated by an underlying process that changes over time.

‍

In the CpG example, that process has two hidden states:

‍

• Inside a CpG island
• Outside a CpG island

‍

We never observe these states directly, instead, we observe the DNA sequence they produce.

‍

At every position, the model asks:

‍

Given everything I've seen so far, which hidden state is most likely to have generated this nucleotide?

‍

Because neighbouring positions are related, the model reasons about the entire sequence rather than making isolated decisions. This naturally produces coherent genomic regions instead of disconnected predictions.

‍

Understanding Hidden States

‍

Each hidden state is defined by two sets of probabilities.

‍

The first is the emission probability:

‍

• This describes how likely each nucleotide is to appear while the model is in a particular state. Since CpG islands have a different nucleotide distribution from the rest of the genome, the emission probabilities differ between the two states.

‍

The second is the transition probability:

• This determines how likely the model is to remain in its current state or move to another one.

‍

Since CpG islands typically span many consecutive nucleotides, the probability of remaining inside an island is relatively high once the model enters one.

‍

Together, these probabilities allow the HMM to balance two sources of information:

• What the current nucleotide suggests.
• How likely it is that the hidden state has changed.

‍

A Helpful Analogy

‍

The same idea appears in a much simpler example.

• Imagine someone is flipping coins.
• Sometimes they use a fair coin and sometimes they secretly switch to a biased coin.
• After each flip there's a 10% chance they'll swap coins but you never see which coin they're holding… you only observe a sequence of heads and tails.
• Your task is to reconstruct which coin was probably used for each flip. Structurally, this is the same problem as identifying CpG islands. The observations are different but the hidden-state inference problem is identical.

‍

The Four Components of an HMM

‍

Every Hidden Markov Model is built from four pieces.

‍

1. Observation alphabet: The possible observations generated by the model (for DNA, these are A, T, G and C).
2. ‍Hidden states: The underlying process that generates those observations (for DNA these correspond to being inside or outside a CpG island.‍
3. Transition probabilities: The probability of moving from one hidden state to another.‍
4. Emission probabilities: The probability of observing each symbol while in a given hidden state. For the CpG model discussed in the session, the implementation expands this into eight states...one for each nucleotide inside a CpG island and one for each nucleotide outside it. Each state emits its corresponding nucleotide, while the transitions determine whether the sequence remains inside a region or moves outside it.

‍

‍

Three Questions Every HMM Needs to Answer

‍

Once an HMM has been defined, there are three computational problems we typically want to solve.

‍

1. Evaluation

‍

How likely is the observed sequence under this model?

‍

The Forward-Backward algorithm answers this by efficiently considering every possible hidden-state sequence that could have generated the observations.

‍

Rather than evaluating an exponential number of paths individually, dynamic programming allows this computation to be performed efficiently.

‍

‍

2. Decoding

‍

Given the observations, what is the single most likely sequence of hidden states?

‍

This is the job of the Viterbi algorithm. Instead of considering every possible explanation equally, Viterbi identifies the most probable path through the hidden states.

‍

In the coin example, this reconstructs which coin was likely used for every flip. For DNA, it determines where the model believes CpG islands begin and end.

‍

3. Learning

‍

What if we don't already know the transition and emission probabilities?

‍

The Baum-Welch algorithm estimates them directly from observed sequences.

‍

It uses the Expectation-Maximisation (EM) framework:

• Estimate the most likely hidden-state assignments.
• Update the model parameters.
• Repeat until the parameters stabilise.

‍

This allows HMMs to learn from unlabelled data, making them particularly useful when hidden states cannot be observed directly.

‍

‍

Beyond DNA: Profile HMMs

‍

The ideas behind Hidden Markov Models extend well beyond identifying CpG islands.

‍

One important extension is the Profile Hidden Markov Model, widely used in bioinformatics. Instead of modelling a single sequence switching between hidden states, a Profile HMM represents an entire family of related biological sequences.

‍

The resulting model captures the statistical signature of an entire protein family rather than a single example. Then given a new sequence, the model can estimate how likely it is to belong to that family.

‍

This idea underpins databases such as Pfam, which are widely used for protein annotation and sequence analysis.

‍

‍

Why HMMs Still Matter

‍

Although Hidden Markov Models are one of the classic probabilistic machine learning models, the underlying idea remains remarkably powerful.

Many real-world problems involve observations generated by processes we cannot see directly:

• Speech recognition
• Natural language processing
• Financial time series
• Biological sequences

‍

The application changes, but the structure stays the same. A hidden process evolves over time, producing observations that we can measure. Our task remains to infer what was happening beneath the surface.

‍

A Hidden Markov Model allows those hidden regions to emerge naturally by combining evidence across the entire sequence. That's what makes HMMs such an elegant solution, they don’t simply classify observations, but rather infer the hidden process that generated them.

‍

Check out our similar article: Markov Decision Processes Explained: The Framework That Powers Reinforcement Learning

‍

‍

‍