Efficient haplotype matching and storage using the positional Burrows–Wheeler transform (PBWT)

By Richard Durbin. Bioinform., 2014

445 citations recorded by the source corpus.

Motivation: Over the last few years, methods based on suffix arrays using the Burrows–Wheeler Transform have been widely used for DNA sequence read matching and assembly. These provide very fast search algorithms, linear in the search pattern size, on a highly compressible representation of the dataset being searched. Meanwhile, algorithmic development for genotype data has concentrated on statistical methods for phasing and imputation, based on probabilistic matching to hidden Markov model representations of the reference data, which while powerful are much less computationally efficient. Here a theory of haplotype matching using suffix array ideas is developed, which should scale too much larger datasets than those currently handled by genotype algorithms. Results: Given M sequences with N bi-allelic variable sites, an O(NM) algorithm to derive a representation of the data based on positional prefix arrays is given, which is termed the positional Burrows–Wheeler transform (PBWT). On large datasets this compresses with run-length encoding by more than a factor of a hundred smaller than using gzip on the raw data. Using this representation a method is given to find all maximal haplotype matches within the set in O(NM) time rather than O(NM2) as expected from naive pairwise comparison, and also a fast algorithm, empirically independent of M given sufficient memory for indexes, to find maximal matches between a new sequence and the set. The discussion includes some proposals about how these approaches could be used for imputation and phasing. Availability: http://github.com/richarddurbin/pbwt Contact: richard.durbin@sanger.ac.uk

Subfields: Artificial Intelligence, Genetics

View Paper: https://www.semanticscholar.org/paper/e32145aeb02732e51ed0217612a13fec0efab5e8

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Genetics

Citations in the corpus

Computational pan-genomics: status, promises and challenges (2016, background): “To this end, Durbin [37] has proposed the aforementioned PWBT index struc-”
A one penny imputed genome from next generation reference panels (2018, background): “5k – 10M) and target sample sizes (10-1000) considered.”
Allelic Landscape of Human Blood Cell Trait Variation and Links (2016, unknown): “Efficient haplotype matching and storage using the positional Burrows-Wheeler transform (PBWT).”
Genome graphs and the evolution of genome inference (2017, background): “The PBWT is a transform of a matrix of binary haplotypes that is highly compressible and supports efficient haplotype search queries even when compressed (Durbin 2014).”
Efficient Coalescent Simulation and Genealogical Analysis for Large Sample Sizes (2015, methodology): “Using the PBWT [53] to find long haplotypes (which will usually correspond to long records) seems like a particularly promising avenue.”
Genome-wide association studies in ancestrally diverse populations: opportunities, methods, pitfalls, and recommendations. (2019, unknown): “edu), Beagle (Browning and Browning, 2009), PBWT ((Durbin, 2014); default for Sanger Imputation Server, https://imputation.”
Fast and accurate long-range phasing in a UK Biobank cohort (2015, unknown): “Finally, we used the Sanger Imputation Service to impute the N=15K SHAPEIT2-phased samples and the same subset of Eagle-phased samples using both the UK10K panel (3,781 samples) and the Haplotype Reference Consortium (r1) panel (32,488 samples) with the PBWT imputation algorithm [42] (see URLs).”
Fast two-stage phasing of large-scale sequence data. (2021, methodology): “…came from incorporating methodological ideas from genotype imputation and from data compression, such as the use of a small, custom reference panel for each individual, 24,25 and from the use of the positional Burrows-Wheeler transform 26 for efﬁciently identifying long shared allele sequences.”