The DOI matches its Crossref record; 14 of the 14 references it cites were found in a registry or an index.
Efficient haplotype matching and storage using the positional Burrows–Wheeler transform (PBWT)
Open accessAbstract
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
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Fast and accurate short read alignment with Burrows-Wheeler transform
Li, H., & Durbin, R. (2009) · Bioinformatics · doi:10.1093/bioinformatics/btp324 · Cited by 58,607
Self-citationUltrafast and memory-efficient alignment of short DNA sequences to the human genome.
Langmead, B., Trapnell, C., Pop, M., & Salzberg, S. L. (2009) · Genome Biology · doi:10.1186/gb-2009-10-3-r25 · Cited by 21,849
An integrated map of genetic variation from 1,092 human genomes
The 1000 Genomes Project Consortium (2012) · Nature · doi:10.1038/nature11632 · Cited by 7,711
SOAP2: an improved ultrafast tool for short read alignment
Li, R., Yu, C., Li, Y., Lam, T.-W., Yiu, S.-M., Kristiansen, K., & Wang, J. (2009) · Bioinformatics · doi:10.1093/bioinformatics/btp336 · Cited by 3,760
SOAP: Short oligonucleotide alignment program
Li, R., Li, Y., Kristiansen, K., & Wang, J. (2008) · Bioinformatics · doi:10.1093/bioinformatics/btn025 · Cited by 3,597
Browning, S. R., & Browning, B. L. (2007) · The American Journal of Human Genetics · doi:10.1086/521987 · Cited by 3,210
A Block-sorting Lossless Data Compression Algorithm
Burrows, M. T., & Wheeler, D. J. (1994) · Cited by 2,333
A linear complexity phasing method for thousands of genomes
Delaneau, O., Marchini, J., & Zagury, J.-F. (2012) · Nature Methods · doi:10.1038/nmeth.1785 · Cited by 1,850
Genotype imputation for genome-wide association studies
Marchini, J., & Howie, B. (2010) · Nature Reviews Genetics · doi:10.1038/nrg2796 · Cited by 1,627
Opportunistic data structures with applications
Ferragina, P., & Manzini, G. (2002) · Proceedings 41st Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2000.892127 · Cited by 1,063
Cited by
A One-Penny Imputed Genome from Next-Generation Reference Panels
Browning, B. L., Zhou, Y., & Browning, S. R. (2018) · The American Journal of Human Genetics · doi:10.1016/j.ajhg.2018.07.015 · Cited by 2,092
Reference-based phasing using the Haplotype Reference Consortium panel
Loh, P.-R., Danecek, P., Palamara, P. F., Fuchsberger, C., A Reshef, Y., K Finucane, H., Schoenherr, S., Forer, L., McCarthy, S., Abecasis, G. R., et al. (2016) · Nature Genetics · doi:10.1038/ng.3679 · Cited by 1,723
Self-citationde Lange, K. M., Moutsianas, L., Lee, J. C., Lamb, C. A., Luo, Y., Kennedy, N. A., Jostins, L., Rice, D. L., Gutierrez-Achury, J., Ji, S.-G., et al. (2017) · Nature Genetics · doi:10.1038/ng.3760 · Cited by 1,445
The Allelic Landscape of Human Blood Cell Trait Variation and Links to Common Complex Disease
Astle, W. J., Elding, H., Jiang, T., Allen, D., Ruklisa, D., Mann, A. L., Mead, D., Bouman, H., Riveros-Mckay, F., Kostadima, M. A., et al. (2016) · Cell · doi:10.1016/j.cell.2016.10.042 · Cited by 1,224
Variation graph toolkit improves read mapping by representing genetic variation in the reference
Garrison, E., Sirén, J., Novak, A. M., Hickey, G., Eizenga, J. M., Dawson, E. T., Jones, W., Garg, S., Markello, C., Lin, M. F., et al. (2018) · Nature Biotechnology · doi:10.1038/nbt.4227 · Cited by 821
Self-citation
Metadata
- Authors
- Durbin, R.
- Venue
- Bioinformatics
- Publisher
- Oxford University Press (OUP)
- Published
- 2014-01-09
- Volume
- 30
- Issue
- 9
- Pages
- 1266-1272
- ISSN
- 1367-4803 (ISSN-L)
- 1367-4811
- OpenAlex
- W2147477044
- Cited by
- 427
- References
- 14
- FWCI
- 15.18
- Type
- journal article
- Language
- en
- Open access
- hybrid
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Efficient haplotype matching and storage using the positional Burrows–Wheeler transform (PBWT). https://app.cochat.ai/papers/10.1093/bioinformatics/btu014
- The paper
- Durbin, R. (2014). Efficient haplotype matching and storage using the positional Burrows–Wheeler transform (PBWT). Bioinformatics. https://doi.org/10.1093/bioinformatics/btu014
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.