Computing coalescence rates for complex demographies and sampling configurations

This paper introduces *demestats*, a differentiable software library that computes first-coalescence and cross-coalescence rates for complex demographic models to overcome the limitations of pairwise summaries in resolving recent population history, demonstrating improved accuracy in simulations and new insights into human expansion using 1000 Genomes Project data.

The Gist

Imagine you are a detective trying to solve a family mystery, but instead of looking at old photo albums, you are looking at the DNA of people living today. Your goal is to reconstruct the history of their ancestors: when did their populations grow? When did they split into different groups? When did they mix with neighbors?

For a long time, detectives had a major blind spot. They could only look at pairs of people (like comparing just you and your cousin). This is like trying to figure out the history of a massive city by only looking at two random people on the street. You can tell a lot about the distant past (when the city was a tiny village), but you can't see what happened yesterday or last week. Recent events are too rare to show up in just two people's DNA.

This paper introduces a new detective tool called demestats that solves this problem by looking at groups of people instead of just pairs.

Here is a simple breakdown of how it works, using some everyday analogies:

1. The Problem: The "Two-Person" Blind Spot

Think of a family tree as a river flowing backward in time.

• The Old Way (Pairs): If you only trace two branches of the river, they might not merge (coalesce) until they reach a very old, deep part of the history. It's like trying to find out if it rained yesterday by looking at two trees that only share roots from 100 years ago. You miss the recent rain.
• The Result: Scientists could guess the size of ancient populations well, but they were terrible at guessing how fast populations grew recently or how recently two groups separated.

2. The Solution: The "Crowd" Approach

The authors built a software library called demestats. Instead of looking at two people, it looks at a crowd (say, 50 people) at once.

• The Analogy: Imagine a crowded room where everyone is trying to find their long-lost twin.
  • If you have 2 people, they might not find each other for a long time.
  • If you have 50 people, the odds are high that someone in that crowd will find their twin very quickly.
• The Magic: By watching when the first person in a large group finds their match, demestats gets a very clear signal about what happened recently. The "first merge" in a large group happens much faster and tells us exactly how big the population was just a few generations ago.

3. How It Handles Complexity: The "Traffic Control" System

Real human history isn't simple. People move between cities (migration), populations split, and they mix again. Calculating the odds for a crowd in this messy scenario is a mathematical nightmare.

• The Exact Method: For small groups, the software does the math perfectly, tracking every single possible path a family line could take. It's like a traffic controller watching every single car on a small road network.
• The "Mean-Field" Shortcut: For huge groups (like 50 or 100 people), tracking every single car is impossible. So, the software uses a clever shortcut. Instead of tracking individual cars, it tracks the average flow of traffic.
  • Analogy: Instead of counting every drop of water in a rushing river, you just measure the speed and volume of the river as a whole. This is fast and usually accurate enough to get the job done.

4. What They Discovered

Using this new tool, the authors tested it on real human data (from the 1000 Genomes Project) and found some cool things:

• Recent Growth: They confirmed that human populations have exploded in size very recently (in the last few thousand years). The "crowd" method gave a much sharper picture of this explosion than the old "pair" method.
• Migration: They could detect when different groups (like Europeans and Asians) were still mixing with each other much more recently than previously thought.
• The "Blind Spot" Fix: They showed that if you want to know about recent history, you don't need to know every tiny detail about ancient history. By focusing on large groups, the tool ignores the "noise" of the deep past and focuses on the recent signal.

5. The Catch (The "Blurry Camera")

The paper also admits a limitation. The tool relies on "tree sequences," which are reconstructed family trees built from DNA.

• The Analogy: It's like trying to reconstruct a movie from a blurry, low-resolution recording.
• The Issue: The software is great, but the "camera" (the method used to build the family trees from DNA) sometimes gets the timing slightly wrong, making recent events look like they happened a bit more recently than they actually did. The authors warn that while the tool is powerful, the input data needs to be as clear as possible.

Summary

demestats is a new mathematical microscope.

• Old Microscope: Looked at 2 people. Good for seeing the distant past, but blurry for the recent past.
• New Microscope: Looks at 50+ people. It brings the recent past into sharp focus, allowing us to see exactly how fast human populations grew and mixed in the last few thousand years.

It's a game-changer for understanding our recent human story, turning a blurry snapshot into a high-definition video of our ancestors' recent lives.

Technical Summary

1. Problem Statement

Demographic inference from genetic data relies heavily on the distribution of coalescence times. While pairwise coalescent rates (Instantaneous Coalescent Rates, or ICR, for $k=2$) are widely used, they suffer from significant limitations:

• Limited Power for Recent History: In samples of size two, recent coalescence events are rare, making it difficult to resolve recent population size changes or migration events.
• Computational Complexity: Exact calculations of ICR for larger sample sizes ($k > 2$) or arbitrary sampling configurations in structured populations are computationally prohibitive. The state space required to track unresolved lineage configurations grows exponentially with sample size.
• Model Specificity: Deriving exact ICR formulas often requires custom mathematical derivations for every new demographic model, hindering flexibility.

The authors aim to develop a general, efficient, and differentiable framework to compute first-coalescence rates (for arbitrary $k$) and cross-coalescence rates (between populations) for complex, non-stationary demographic models.

2. Methodology

The authors introduce demestats, a Python library that computes these statistics using an event-tree formalism adapted from the momi family of Site Frequency Spectrum (SFS) methods.

Core Algorithm: Event-Tree Machinery

The method treats the demographic history as a tree of events (splits, merges, pulses, admixture) and propagates a "state" backward in time.

• State Representation: Instead of tracking SFS entries, the state tracks the probability distribution of lineage locations (which deme they are in) given that no coalescence has occurred yet.
• Operators: The algorithm uses specific operators to update the state at event nodes:
  • Split1/Split2: Handle population splits.
  • Merge: Combines independent blocks.
  • Pulse/Admix: Handle migration pulses and admixture events.
  • Lift ($L_{IE}$): Propagates the state continuously backward in time along intervals between events, accounting for migration and coalescence hazards.
• Exact vs. Approximate:
  • Exact Solver: For small sample sizes, the state is represented as a full probability tensor (either "occupancy" or "labeled-lineage" formulation). The algorithm solves a system of ordinary differential equations (ODEs) to compute the survival function and hazard rate.
  • Mean-Field Approximation: For large samples where the tensor dimension is too large, the method approximates the full distribution using low-order moments (first and second moments of lineage counts). This assumes independence between lineages from different sampled populations, significantly reducing computational cost.

Key Statistics Computed

1. First-Coalescence Rate ($ICR_k$): The hazard rate of the first coalescent event in a sample of size $k$.
2. Cross-Coalescence Rate (CCR): The hazard rate of the first coalescence event between lineages from two distinct populations (e.g., "red" and "blue" lineages). This is crucial for studying population separation and migration.
3. Local Identifiability: Because the implementation is automatically differentiable with respect to model parameters, the authors compute the Fisher Information Matrix. This allows them to visualize which demographic parameters (e.g., specific epoch sizes or migration rates) are actually learnable from a given sampling design.

3. Key Contributions

• Generalized Framework: demestats provides a unified method to compute coalescence rates for any demographic model specified in the demes format, removing the need for model-specific derivations.
• Scalability: By combining exact tensor methods with mean-field approximations, the tool handles both small and large sample sizes ($k$) efficiently.
• Differentiability: The library supports gradient-based inference (likelihood maximization) and sensitivity analysis (Fisher information) out of the box.
• Cross-Population Analysis: It generalizes cross-coalescence rates to arbitrary sampling configurations, enabling the study of recent migration and population separation with high resolution.

4. Results

The authors validated the method through simulations and real-data application:

• Identifiability Analysis:
  • In single-deme models, increasing sample size ($k$) shifts the information content from ancient epochs to recent epochs. Pairwise data ($k=2$) is blind to recent growth, while $k=20$ or $k=50$ resolves recent bottlenecks and expansions.
  • In structured models (e.g., OutOfAfrica), pairwise data from different populations primarily informs migration rates, while local population sizes remain unidentifiable.
• Mean-Field Accuracy:
  • The mean-field approximation is highly accurate for balanced sampling designs.
  • Accuracy degrades when many lineages are concentrated in a small deme (high within-deme correlation), suggesting the exact solver should be used in such cases if computationally feasible.
• Power to Detect Recent Migration:
  • The probability of observing a cross-coalescence event before a population split scales quadratically with the number of lineages per population ($n^2$).
  • Large samples drastically reduce the number of independent trees required to detect weak, recent migration signals.
• Likelihood-Based Inference Benchmarks:
  • Recent Growth: Using $k=50$ significantly improves the estimation of recent effective population sizes compared to $k=2$, even when using inferred Ancestral Recombination Graphs (ARGs).
  • Robustness to Misspecification: Large-$k$ summaries are robust to misspecification of ancient demographic events. If the goal is to infer recent history, one can simplify the ancient part of the model without losing accuracy for recent parameters.
  • ARG Distortion: The authors note that inferred ARGs (via tsinfer/tsdate) tend to shift higher-order first-coalescence times ($T_{50}$) toward the present, potentially biasing estimates of recent population sizes, though the trend of improved recent resolution with larger $k$ holds.

5. Significance and Application

• 1000 Genomes Application: Applying demestats to 1000 Genomes data (using $k=50$) provided new insights into recent human expansion. The study estimated recent growth rates of ~0.9–1.1% per generation and present-day effective population sizes in the millions, offering a more refined view of recent history than pairwise methods.
• Paradigm Shift: The paper demonstrates that moving beyond pairwise summaries to larger sample sizes ($k \gg 2$) is essential for resolving recent demographic history. It transforms the "bottleneck" of recent inference into a solvable problem by leveraging the increased density of recent coalescence events in large samples.
• Practical Utility: The tool allows researchers to design sampling strategies (choosing $k$ and population composition) based on Fisher information to maximize the power of their specific demographic questions.

In summary, demestats bridges the gap between complex demographic modeling and large-scale genomic data, providing a rigorous, flexible, and computationally efficient toolkit for inferring recent population history.