{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,26]],"date-time":"2026-02-26T20:34:03Z","timestamp":1772138043966,"version":"3.50.1"},"reference-count":14,"publisher":"Oxford University Press (OUP)","issue":"16","license":[{"start":{"date-parts":[[2021,2,24]],"date-time":"2021-02-24T00:00:00Z","timestamp":1614124800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"funder":[{"DOI":"10.13039\/100000002","name":"National Institutes of Health","doi-asserted-by":"publisher","award":["R01HG010086"],"award-info":[{"award-number":["R01HG010086"]}],"id":[{"id":"10.13039\/100000002","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021,8,25]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:sec>\n                    <jats:title>Motivation<\/jats:title>\n                    <jats:p>Durbin\u2019s positional Burrows\u2013Wheeler transform (PBWT) is a scalable data structure for haplotype matching. It has been successfully applied to identical by descent (IBD) segment identification and genotype imputation. Once the PBWT of a haplotype panel is constructed, it supports efficient retrieval of all shared long segments among all individuals (long matches) and efficient query between an external haplotype and the panel. However, the standard PBWT is an array-based static data structure and does not support dynamic updates of the panel.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Results<\/jats:title>\n                    <jats:p>Here, we generalize the static PBWT to a dynamic data structure, d-PBWT, where the reverse prefix sorting at each position is stored with linked lists. We also developed efficient algorithms for insertion and deletion of individual haplotypes. In addition, we verified that d-PBWT can support all algorithms of PBWT. In doing so, we systematically investigated variations of set maximal match and long match query algorithms: while they all have average case time complexity independent of database size, they have different worst case complexities and dependencies on additional data structures.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Availabilityand implementation<\/jats:title>\n                    <jats:p>The benchmarking code is available at genome.ucf.edu\/d-PBWT.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Supplementary information<\/jats:title>\n                    <jats:p>Supplementary data are available at Bioinformatics online.<\/jats:p>\n                  <\/jats:sec>","DOI":"10.1093\/bioinformatics\/btab117","type":"journal-article","created":{"date-parts":[[2021,2,23]],"date-time":"2021-02-23T07:32:16Z","timestamp":1614065536000},"page":"2390-2397","source":"Crossref","is-referenced-by-count":16,"title":["d-PBWT: dynamic positional Burrows\u2013Wheeler transform"],"prefix":"10.1093","volume":"37","author":[{"given":"Ahsan","family":"Sanaullah","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Central Florida , Orlando, FL 32816,","place":["USA"]}]},{"given":"Degui","family":"Zhi","sequence":"additional","affiliation":[{"name":"Center for Precision Health, School of Biomedical Informatics, University of Texas Health Science Center at Houston , Houston, TX 77030,","place":["USA"]}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4051-5549","authenticated-orcid":false,"given":"Shaojie","family":"Zhang","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Central Florida , Orlando, FL 32816,","place":["USA"]}]}],"member":"286","published-online":{"date-parts":[[2021,2,24]]},"reference":[{"key":"2025052223014566300_btab117-B1","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1186\/s13015-020-0163-6","article-title":"Finding all maximal perfect haplotype blocks in linear time","volume":"15","author":"Alanko","year":"2020","journal-title":"Algorithms Mol. Biol"},{"key":"2025052223014566300_btab117-B2","author":"Burrows","year":"1994"},{"key":"2025052223014566300_btab117-B100","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1038\/s41586-018-0579-z","article-title":"The UK Biobank resource with deep phenotyping and genomic data","volume":"562","author":"Bycroft","year":"2018","journal-title":"Nature"},{"key":"2025052223014566300_btab117-B3","doi-asserted-by":"crossref","first-page":"1266","DOI":"10.1093\/bioinformatics\/btu014","article-title":"Efficient haplotype matching and storage using the positional Burrows\u2013Wheeler transform (PBWT","volume":"30","author":"Durbin","year":"2014","journal-title":"Bioinformatics"},{"key":"2025052223014566300_btab117-B4","doi-asserted-by":"crossref","first-page":"875","DOI":"10.1038\/nbt.4227","article-title":"Variation graph toolkit improves read mapping by representing genetic variation in the reference","volume":"36","author":"Garrison","year":"2018","journal-title":"Nat. Biotechnol"},{"key":"2025052223014566300_btab117-B5","doi-asserted-by":"crossref","first-page":"590","DOI":"10.1093\/bioinformatics\/btv613","article-title":"Bgt: efficient and flexible genotype query across many samples","volume":"32","author":"Li","year":"2016","journal-title":"Bioinformatics"},{"key":"2025052223014566300_btab117-B6","doi-asserted-by":"crossref","first-page":"811","DOI":"10.1038\/ng.3571","article-title":"Fast and accurate long-range phasing in a UK Biobank cohort","volume":"48","author":"Loh","year":"2016","journal-title":"Nat. Genet"},{"key":"2025052223014566300_btab117-B7","doi-asserted-by":"crossref","first-page":"798","DOI":"10.1093\/bioinformatics\/bty735","article-title":"Haplotype matching in large cohorts using the Li and Stephens model","volume":"35","author":"Lunter","year":"2019","journal-title":"Bioinformatics"},{"key":"2025052223014566300_btab117-B8","doi-asserted-by":"crossref","first-page":"i233","DOI":"10.1093\/bioinformatics\/btz347","article-title":"Efficient haplotype matching between a query and a panel for genealogical search","volume":"35","author":"Naseri","year":"2019","journal-title":"Bioinformatics"},{"key":"2025052223014566300_btab117-B9","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1186\/s12859-019-2821-6","article-title":"Multi-allelic positional Burrows\u2013Wheeler transform","volume":"20","author":"Naseri","year":"2019","journal-title":"BMC Bioinformatics"},{"key":"2025052223014566300_btab117-B10","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1186\/s13059-019-1754-8","article-title":"RaPID: ultra-fast, powerful, and accurate detection of segments identical by descent (IBD) in biobank-scale cohorts","volume":"20","author":"Naseri","year":"2019","journal-title":"Genome Biol"},{"key":"2025052223014566300_btab117-B11","author":"Naseri","year":"2020"},{"key":"2025052223014566300_btab117-B12","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1186\/s13015-017-0109-9","article-title":"A graph extension of the positional burrows\u2013wheeler transform and its applications","volume":"12","author":"Novak","year":"2017","journal-title":"Algorithms Mol. Biol"},{"key":"2025052223014566300_btab117-B13","doi-asserted-by":"crossref","first-page":"400","DOI":"10.1093\/bioinformatics\/btz575","article-title":"Haplotype-aware graph indexes","volume":"36","author":"Sir\u00e9n","year":"2020","journal-title":"Bioinformatics"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/academic.oup.com\/bioinformatics\/advance-article-pdf\/doi\/10.1093\/bioinformatics\/btab117\/37853718\/btab117.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/37\/16\/2390\/59818355\/btab117.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/37\/16\/2390\/59818355\/btab117.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,22]],"date-time":"2025-05-22T23:01:56Z","timestamp":1747954916000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/37\/16\/2390\/6149123"}},"subtitle":[],"editor":[{"given":"Russell","family":"Schwartz","sequence":"additional","affiliation":[]}],"short-title":[],"issued":{"date-parts":[[2021,2,24]]},"references-count":14,"journal-issue":{"issue":"16","published-print":{"date-parts":[[2021,8,25]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btab117","relation":{"has-preprint":[{"id-type":"doi","id":"10.1101\/2020.01.14.906487","asserted-by":"object"}]},"ISSN":["1367-4803","1367-4811"],"issn-type":[{"value":"1367-4803","type":"print"},{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2021,8,15]]},"published":{"date-parts":[[2021,2,24]]}}}