Timepiece III: The Li & Stephens HMM

Your genome is a mosaic. This model finds the seams.

The Mechanism at a Glance

The Li & Stephens Hidden Markov Model (Li and Stephens, 2003) is one of the most influential models in population genetics. It answers a deceptively simple question: given a panel of reference haplotypes, how was a new haplotype assembled from pieces of them?

The answer turns out to be a Hidden Markov Model where the hidden states are “which reference haplotype am I copying right now?” and the transitions are recombination events that switch the copying source. This simple idea underpins modern haplotype imputation, phasing, ancestry inference, and – as we saw in the prerequisite on HMMs – even full ARG inference.

Think of it this way: every genome is a mosaic, assembled from fragments of ancestral genomes by generations of recombination. The Li & Stephens model is the mechanism that detects where the seams are – where one ancestral fragment ends and another begins. Like a jeweler’s loupe that reveals the individual facets of a gemstone, this model reveals the hidden structure of how genomes were assembled.

The Li & Stephens HMM is also a versatile gear – a mechanism that appears inside many of the other Timepieces in this collection. SINGER uses it for branch transitions. tsinfer uses it for ancestor and sample matching. Understanding this Timepiece will pay dividends throughout the rest of the book.

Primary Reference

[Li and Stephens, 2003]

Prerequisites for this Timepiece

• Hidden Markov Models – the forward algorithm, stochastic traceback, and especially the Li-Stephens \(O(K)\) trick

• Coalescent Theory – for understanding why haplotypes are mosaics of ancestral sequences

Chapters

• Overview of the Li & Stephens HMM
  • What Does the Li & Stephens HMM Do?
  • The Mosaic Model
  • The HMM Formulation
  • Why the LS Model Matters
  • The Pieces of the Mechanism
  • Ready to Build
• The Copying Model
  • Step 1: The Biological Picture
  • Step 2: The Initial Distribution
  • Step 3: Transition Probabilities
  • Step 4: Emission Probabilities
  • Step 5: Estimating the Mutation Probability
  • Step 6: The O(K) Trick – Making It Fast
  • Step 7: Putting It All Together
  • Summary
• Haploid LS HMM Algorithms
  • The Forward Algorithm
  • The Backward Algorithm
  • Posterior Decoding
  • The Viterbi Algorithm
  • Path Log-Likelihood
  • Memory Optimization: From O(mn) to O(m + n)
  • Putting It All Together: A Complete Example
  • Summary
• The Diploid Extension
  • Step 1: The Diploid State Space
  • Step 2: Diploid Transitions
  • Step 3: Diploid Emissions
  • Step 4: Diploid Forward Algorithm
  • Step 5: Diploid Viterbi Algorithm
  • Step 6: Building the Reference Genotype Matrix
  • Step 7: Complete Diploid Example
  • Step 8: The Phase Ambiguity
  • Summary
• Demo: Running the Li & Stephens HMM on Simulated Data

Each chapter derives the math, explains the intuition, implements the code, and verifies it works. By the end, you’ll have built a complete LS HMM library from scratch – and you’ll understand every gear that makes it tick.