The Scaling Crisis in Modern Genomics
If you have a collection of $N$ human genomes and want to find out who shares a genetic segment with whom, the naive approach is straightforward: compare every genome to every other genome. However, this exhaustive pairwise comparison scales quadratically ($O(N^2)$). When cohorts were small, this quadratic cost was an acceptable tax. But in the era of modern biobanks containing hundreds of thousands or millions of individuals, an $O(N^2)$ algorithm is a computational death sentence.
The same scaling bottleneck appears across genomics: in haplotype phasing (determining which maternal and paternal variants sit on the same chromosome), in reconstructing genealogical trees, and in sequence alignment. Traditional methods rely on Hidden Markov Models (HMMs) or dynamic programming matrices that scale poorly with the number of reference templates or sequence lengths.
To prevent large-scale genomics from grinding to a halt, a unified research direction has emerged: transitioning these core algorithms from quadratic or exponential scaling to linear-time complexity ($O(N)$). By redesigning data structures and decoupling complex state spaces, researchers can now analyze millions of samples in minutes. Here is the intuition behind how these linear-time algorithms work.
Locality and Adjacency: The Positional Burrows-Wheeler Transform
Why should we be able to match haplotypes in linear time without checking every pair? The answer lies in a fundamental biological reality: because of shared ancestry, individuals who match at a specific genetic marker are highly likely to match at adjacent markers.
The Positional Burrows-Wheeler Transform (PBWT) exploits this property by sorting a panel of haplotypes lexicographically at every single genetic position. Because they are sorted, haplotypes that share long matching segments will naturally end up adjacent to each other in the sorted array. Finding matches then becomes a matter of scanning down the sorted list and checking immediate neighbors, rather than performing an exhaustive all-pairs comparison.
As shown by Olivier Delaneau et al. in Accurate, scalable and integrative haplotype estimation, this dense sharing of ancestry means that as cohort sizes grow, the matching segments become longer. This allows algorithms to focus their search space on relevant neighbors, achieving sub-linear scaling per additional sample.
Yaoling Yang et al. leveraged this property in Sparse haplotype-based fine-scale local ancestry inference at scale reveals recent selection on immune responses to scale local ancestry inference to hundreds of thousands of individuals, reducing processing time by two orders of magnitude.
To handle real-world sequencing errors, William A. Freyman et al. introduced the Templated PBWT in Fast and Robust Identity-by-Descent Inference with the Templated Positional Burrows–Wheeler Transform, maintaining linear-time efficiency while accommodating noise. Furthermore, Ardalan Naseri et al. extended this framework to multi-allelic data in Multi-allelic positional Burrows-Wheeler transform, ensuring that the linear relationship with panel size holds even for complex genetic variations.
Bypassing Pairwise Comparisons via Hashing and Projections
Another way to avoid the $O(N^2)$ trap is to bucket sequences so that potential matches can be found instantly. If two individuals share a long identical-by-descent (IBD) segment, they must share an exact match across smaller sub-windows of that segment.
In Whole population, genome-wide mapping of hidden relatedness, Alexander Gusev et al. introduced GERMLINE, which partitions sequences into fixed-length windows and stores them in a hash table. By looking up matches within hash buckets, the algorithm identifies potential shared segments in linear time relative to the number of samples, bypassing exhaustive pairwise comparisons.
Building on this, Ardalan Naseri et al. developed RaPID in RaPID: ultra-fast, powerful, and accurate detection of segments identical by descent (IBD) in biobank-scale cohorts. RaPID applies random projection-based hashing to projected haplotype data, allowing the rapid identification of shared segments across millions of pairs in minutes. The authors later extended this approach in RAFFI: Accurate and fast familial relationship inference in large scale biobank studies using RaPID to infer distant familial relationships across massive biobanks without exhaustive pairwise checks.
Decoupling State Spaces in Probabilistic Models
When modeling complex genetic processes—such as reconstructing ancestral recombination graphs (ARGs) or joint family haplotyping—the state space of traditional Hidden Markov Models (HMMs) often scales quadratically or exponentially. Linear scaling is achieved here by decoupling the dimensions of the state space.
For instance, when inserting a new genome into a genealogy graph, one must typically evaluate every branch at every possible historical time point, leading to quadratic complexity. In Robust and accurate Bayesian inference of genome-wide genealogies for hundreds of genomes, Yun Deng et al. decoupled this process into two separate linear phases: first identifying the target branch using an HMM, and then sampling the specific coalescence time. This reduces the state space complexity from quadratic to linear relative to the number of lineages.
Similarly, in the context of family pedigrees, Wei Chen et al. showed in Genotype calling and haplotyping in parent-offspring trios that the joint probability distribution of a family unit can be approximated through a series of univariate conditional distributions. This collapses a high-order polynomial state space down to a linear scale relative to the number of reference haplotypes.
Alignment-Free Analysis: Moving from Base Space to Feature Space
Traditional sequence alignment relies on dynamic programming (such as the Smith-Waterman algorithm), which computes an edit-distance matrix between bases. This process scales quadratically with sequence length. Alignment-free methods achieve linear time by bypassing base-by-base tracking entirely, instead transforming sequences into frequency vectors of short substrings ($k$-mers) or mathematical state machines.
As reviewed by Jie Ren et al. in Alignment-Free Sequence Analysis and Applications, these methods provide massive speedups by using $k$-mer frequency statistics to compare sequences globally. In KAGE: fast alignment-free graph-based genotyping of SNPs and short indels, Ivar Grytten et al. demonstrated that pre-computing population statistics and $k$-mer indices allows the genotyping cost of a new sample to be completely decoupled from the reference database size.
For long-read mapping, Barış Ekim et al. introduced mapquik in Efficient mapping of accurate long reads in minimizer space with mapquik. This tool shifts the computation to "minimizer space" and uses a linear-time scan for gap-bounded colinearity to chain seed matches, entirely replacing expensive dynamic programming.
Even more radically, Siddharth Jain et al. showed in Generator based approach to analyze mutations in genomic datasets that representing genomic sequences as mathematical state machines allows for sequence clustering in linear time by comparing their underlying generators rather than the sequences themselves.
Key Foundational Work
A Markov Chain Approach to Reconstruction of Long Haplotypes (2004) — contributed 1 concept elements to this direction.
Design optimization methods for genomic DNA tiling arrays (2005) — contributed 1 concept elements to this direction.