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.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
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
“Durbin, R. (2014). Efficient haplotype matching and storage using the positional BurrowsWheeler transform (PBWT). Bioinformatics 30, 1266–1272. Eicher, J.D., Chami, N., Kacprowski, T., Nomura, A., Chen, M.-H., Yanek, L.R., Tajuddin, S.M., Schick, U.M., Slater, A.J., Pankratz, N., et al. (2016). Platelet-Related Varian…”
MethodInfluentialVariation 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-citationFast two-stage phasing of large-scale sequence data
Browning, B. L., Tian, X., Zhou, Y., & Browning, S. R. (2021) · The American Journal of Human Genetics · doi:10.1016/j.ajhg.2021.08.005 · Cited by 888
Efficient Coalescent Simulation and Genealogical Analysis for Large Sample Sizes
Kelleher, J., Etheridge, A. M., & McVean, G. (2016) · PLOS Computational Biology · doi:10.1371/journal.pcbi.1004842 · Cited by 654
Accurate, scalable and integrative haplotype estimation
Delaneau, O., Zagury, J.-F., Robinson, M. R., Marchini, J. L., & Dermitzakis, E. T. (2019) · Nature Communications · doi:10.1038/s41467-019-13225-y · Cited by 622
Memory B Cells Activate Brain-Homing, Autoreactive CD4+ T Cells in Multiple Sclerosis
Jelcic, I., Al Nimer, F., Wang, J., Lentsch, V., Planas, R., Jelcic, I., Madjovski, A., Ruhrmann, S., Faigle, W., Frauenknecht, K., et al. (2018) · Cell · doi:10.1016/j.cell.2018.08.011 · Cited by 508
Efficient phasing and imputation of low-coverage sequencing data using large reference panels
Rubinacci, S., Ribeiro, D. M., Hofmeister, R. J., & Delaneau, O. (2021) · Nature Genetics · doi:10.1038/s41588-020-00756-0 · Cited by 465
Genome graphs and the evolution of genome inference
Paten, B., Novak, A. M., Eizenga, J. M., & Garrison, E. (2017) · Genome Research · doi:10.1101/gr.214155.116 · Cited by 351
Eizenga, J. M., Novak, A. M., Sibbesen, J. A., Heumos, S., Ghaffaari, A., Hickey, G., Chang, X., Seaman, J. D., Rounthwaite, R., Ebler, J., et al. (2020) · Annual Review of Genomics and Human Genetics · doi:10.1146/annurev-genom-120219-080406 · Cited by 320
Pan-genomics in the human genome era
Sherman, R. M., & Salzberg, S. L. (2020) · Nature Reviews Genetics · doi:10.1038/s41576-020-0210-7 · Cited by 359
Fast and accurate long-range phasing in a UK Biobank cohort
Loh, P.-R., Palamara, P. F., & Price, A. L. (2016) · Nature Genetics · doi:10.1038/ng.3571 · Cited by 342
Common genetic variants contribute to risk of rare severe neurodevelopmental disorders
Niemi, M. E. K., Martin, H. C., Rice, D. L., Gallone, G., Gordon, S., Kelemen, M., McAloney, K., McRae, J., Radford, E. J., Yu, S., et al. (2018) · Nature · doi:10.1038/s41586-018-0566-4 · Cited by 340
Inferring whole-genome histories in large population datasets
Kelleher, J., Wong, Y., Wohns, A. W., Fadil, C., Albers, P. K., & McVean, G. (2019) · Nature Genetics · doi:10.1038/s41588-019-0483-y · Cited by 313
Computational pan-genomics: status, promises and challenges
(2016) · Briefings in Bioinformatics · doi:10.1093/bib/bbw089 · Cited by 287
Uganda Genome Resource Enables Insights into Population History and Genomic Discovery in Africa
Gurdasani, D., Carstensen, T., Fatumo, S., Chen, G., Franklin, C. S., Prado-Martinez, J., Bouman, H., Abascal, F., Haber, M., Tachmazidou, I., et al. (2019) · Cell · doi:10.1016/j.cell.2019.10.004 · Cited by 255
Modified penetrance of coding variants by cis-regulatory variation contributes to disease risk
Castel, S. E., Cervera, A., Mohammadi, P., Aguet, F., Reverter, F., Wolman, A., Guigo, R., Iossifov, I., Vasileva, A., & Lappalainen, T. (2018) · Nature Genetics · doi:10.1038/s41588-018-0192-y · Cited by 217
GraphAligner: rapid and versatile sequence-to-graph alignment
Rautiainen, M., & Marschall, T. (2020) · Genome Biology · doi:10.1186/s13059-020-02157-2 · Cited by 242
Insights into the genetic architecture of the human face
White, J. D., Indencleef, K., Naqvi, S., Eller, R. J., Hoskens, H., Roosenboom, J., Lee, M. K., Li, J., Mohammed, J., Richmond, S., et al. (2021) · Nature Genetics · doi:10.1038/s41588-020-00741-7 · Cited by 166
Luo, Y., de Lange, K. M., Jostins, L., Moutsianas, L., Randall, J., Kennedy, N. A., Lamb, C. A., McCarthy, S., Ahmad, T., Edwards, C., et al. (2017) · Nature Genetics · doi:10.1038/ng.3761 · Cited by 162
Genomic analysis of family data reveals additional genetic effects on intelligence and personality
Hill, W. D., Arslan, R. C., Xia, C., Luciano, M., Amador, C., Navarro, P., Hayward, C., Nagy, R., Porteous, D. J., McIntosh, A. M., et al. (2018) · Molecular Psychiatry · doi:10.1038/s41380-017-0005-1 · Cited by 158
A Review of Integrative Imputation for Multi-Omics Datasets
Song, M., Greenbaum, J., Luttrell, J., Zhou, W., Wu, C., Shen, H., Gong, P., Zhang, C., & Deng, H.-W. (2020) · Frontiers in Genetics · doi:10.3389/fgene.2020.570255 · Cited by 127
Sirén, J., Garrison, E., Novak, A. M., Paten, B., & Durbin, R. (2020) · Bioinformatics · doi:10.1093/bioinformatics/btz575 · Cited by 92
Self-citationThe effect of X-linked dosage compensation on complex trait variation
Sidorenko, J., Kassam, I., Kemper, K. E., Zeng, J., Lloyd-Jones, L. R., Montgomery, G. W., Gibson, G., Metspalu, A., Esko, T., Yang, J., et al. (2019) · Nature Communications · doi:10.1038/s41467-019-10598-y · Cited by 82
Genetic study of multimodal imaging Alzheimer’s disease progression score implicates novel loci
Scelsi, M. A., Khan, R. R., Lorenzi, M., Christopher, L., Greicius, M. D., Schott, J. M., Ourselin, S., & Altmann, A. (2018) · Brain · doi:10.1093/brain/awy141 · Cited by 73
A genome-wide association study for extremely high intelligence
Zabaneh, D., Krapohl, E., Gaspar, H. A., Curtis, C., Lee, S. H., Patel, H., Newhouse, S., Wu, H. M., Simpson, M. A., Putallaz, M., et al. (2018) · Molecular Psychiatry · doi:10.1038/mp.2017.121 · Cited by 71
Altmann, A., Scelsi, M. A., Shoai, M., de Silva, E., Aksman, L. M., Cash, D. M., Hardy, J., Schott, J. M., & Initiative, A. D. N. (2020) · Brain Communications · doi:10.1093/braincomms/fcz047 · Cited by 65
Picard, C., Poirier, A., Bélanger, S., Labonté, A., Auld, D., Poirier, J., & on behalf of the PREVENT-AD Research Group (2019) · PLOS ONE · doi:10.1371/journal.pone.0220254 · Cited by 59
Risk of dementia in APOE ε4 carriers is mitigated by a polygenic risk score
Ebenau, J. L., van der Lee, S. J., Hulsman, M., Tesi, N., Jansen, I. E., Verberk, I. M. W., van Leeuwenstijn, M., Teunissen, C. E., Barkhof, F., Prins, N. D., et al. (2021) · Alzheimer's & Dementia: Diagnosis, Assessment & Disease Monitoring · doi:10.1002/dad2.12229 · Cited by 26
Towards cascading genetic risk in Alzheimer’s disease
Altmann, A., Aksman, L. M., Oxtoby, N. P., Young, A. L., ADNI, Weiner, M., Aisen, P., Petersen, R., Weiner, M., Aisen, P., et al. (2024) · Brain · doi:10.1093/brain/awae176 · Cited by 18
Transcriptome-wide association study reveals two genes that influence mismatch negativity
Bhat, A., Irizar, H., Thygesen, J. H., Kuchenbaecker, K., Pain, O., Adams, R. A., Zartaloudi, E., Harju-Seppänen, J., Austin-Zimmerman, I., Wang, B., et al. (2021) · Cell Reports · doi:10.1016/j.celrep.2021.108868 · Cited by 17
Clarke, T.-K., Zeng, Y., Navrady, L., Xia, C., Haley, C., Campbell, A., Navarro, P., Amador, C., Adams, M. J., Howard, D. M., et al. (2018) · Wellcome Open Research · doi:10.12688/wellcomeopenres.13893.1 · Cited by 16
Analysis-ready VCF at Biobank scale using Zarr
(2025) · doi:10.1093/gigascience/giaf049 · Cited by 8
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
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.