Robust and Accurate Bayesian Inference of Genome-Wide Genealogies for Large Samples

Yun Deng, Rasmus Nielsen, Yun S. SongbioRxiv 2024 · DOI

TL;DR

SINGER is a new Bayesian inference tool that reconstructs Ancestral Recombination Graphs (ARGs)—the complex, multi-tree "family history" of our genomes—hundreds of times faster than previous gold-standard methods. By combining a clever two-step "threading" algorithm with robust uncertainty quantification, SINGER allows researchers to accurately map evolutionary events like ancient interbreeding and local adaptation in large-scale genomic datasets.

What Problem Does This Paper Address?

In species that reproduce sexually, like humans, your genetic history isn't a single family tree. Because of recombination (the shuffling of DNA between parents), different segments of your genome have different ancestors. The Ancestral Recombination Graph (ARG) is the mathematical structure that captures this "forest" of overlapping trees.

Inferring an ARG is a computational nightmare because the number of possible tree combinations is astronomical. Existing tools face a harsh tradeoff:

  1. High-Accuracy Bayesian methods (like ARGweaver) provide a full distribution of possible trees (quantifying uncertainty) but are so slow they can only handle a few dozen individuals.
  2. Heuristic methods (like Relate or tsinfer) are incredibly fast and scale to thousands of genomes, but they usually produce only a single "best guess" tree. This often leads to errors in ancient history and makes it impossible to know how confident we should be in the results.

Methods

The authors introduce SINGER (Sampling and INferring of GEnealogies with Recombination), which bridges this gap using three main innovations:

  • Two-Step Threading: To add a new genome to an existing tree, SINGER breaks the problem into two smaller Hidden Markov Models (HMMs). First, it samples the branch where the new lineage joins, then it samples the time of that joining. This "divide and conquer" approach is significantly faster than trying to solve both at once.
  • SGPR (Sub-Graph Pruning and Re-grafting): This is a new MCMC (Markov Chain Monte Carlo) proposal. It prunes a piece of the ARG and uses the threading algorithm to "re-graft" it in a way that is highly compatible with the data. This allows the algorithm to explore the space of possible trees much more efficiently.
  • ARG Re-scaling: SINGER automatically adjusts branch lengths based on the local mutation clock. This makes the method robust to "model misspecification"—essentially, it works even if the researcher doesn't know the exact historical population sizes.

Datasets

The researchers evaluated SINGER using:

  • Simulated Data: Using the msprime simulator, they created "ground truth" datasets of 50 and 300 haplotypes to compare SINGER against competitors (ARGweaver, Relate, tsinfer, ARG-Needle).
  • 1000 Genomes Project: They applied SINGER to 200 whole-genome sequences from five indigenous African populations (GWD, YRI, ESN, LWK, and MSL) to find real-world signals of evolution.

Key Insights and Ideas

  • Uncertainty is a Feature, Not a Bug: Most modern ARG tools give a point estimate. SINGER provides a posterior distribution. The authors show that for tasks like estimating the age of a mutation or detecting identity-by-descent (IBD), relying on a single tree can be misleadingly noisy.
  • Robustness to the Unknown: Real populations fluctuate in size (bottlenecks, expansions). SINGER’s re-scaling algorithm allows it to capture these dynamics accurately without needing the user to provide a perfect demographic history upfront.
  • Deep History Matters: SINGER significantly outperforms heuristic methods in capturing "ancient" coalescence times. This is vital for studying things like balancing selection, where certain genetic variants are maintained for millions of years.

Key Results

  • Speedup: SINGER’s threading is ~10x faster than ARGweaver, and its overall MCMC convergence is roughly 400x faster, making Bayesian inference practical for hundreds of samples.
  • Higher Accuracy: SINGER achieved the lowest "triplet distance" (a measure of tree topology error) and the most accurate estimates of coalescence times and allele ages across all tested scenarios.
  • Biological Discovery: In the African 1000 Genomes data, SINGER identified:
  • Local Adaptation: Peaks in diversity ratios pointed to genes like MITF (skin pigmentation) and SPCS3 (immune response).
  • Balancing Selection: It confirmed extremely ancient lineages in the HLA region, some predating the human-chimpanzee split.
  • Archaic Introgression: Using a new "coalescence distribution heatmap," they identified potential genomic tracts inherited from "ghost" archaic human groups.

Limitations and Future Work

  • Computational Ceiling: While much faster, MCMC still struggles to scale to the hundreds of thousands of genomes handled by heuristic methods. The authors are looking into sampling branch lengths on fixed topologies to further boost speed.
  • Binning Strategy: SINGER currently uses equal-sized genomic bins. The authors suggest that "dynamic binning" (smaller bins in recombination hotspots) could improve accuracy and efficiency.
  • Phasing Dependency: The tool currently requires "phased" data (knowing which mutations are on which chromosome copy). Developing versions that handle unphased or poorly phased data is a key future goal to make the tool more useful for non-model organisms and ancient DNA.

Summary updated

Abstract

Abstract The Ancestral Recombination Graph (ARG), which describes the full genealogical history of a sample of genomes, is a vital tool in population genomics and biomedical research. Recent advancements have increased ARG reconstruction scalability to tens or hundreds of thousands of genomes, but these methods rely on heuristics, which can reduce accuracy, particularly in the presence of model misspecification. Moreover, they reconstruct only a single ARG topology and cannot quantify the considerable uncertainty associated with ARG inferences. To address these challenges, we here introduce SINGER, a novel method that accelerates ARG sampling from the posterior distribution by two orders of magnitude, enabling accurate inference and uncertainty quantification for large samples. Through extensive simulations, we demonstrate SINGER’s enhanced accuracy and robustness to model misspecification compared to existing methods. We illustrate the utility of SINGER by applying it to African populations within the 1000 Genomes Project, identifying signals of local adaptation and archaic introgression, as well as strong support of trans-species polymorphism and balancing selection in HLA regions.
BibTeX
@misc{deng2024robust,
  author = {Yun Deng and Rasmus Nielsen and Yun S. Song},
  title = {{Robust and Accurate Bayesian Inference of Genome-Wide Genealogies for Large Samples}},
  year = {2024},
  doi = {10.1101/2024.03.16.585351},
  howpublished = {bioRxiv},
}
Figure