{"doi":"10.1101/2025.02.04.636317","title":"Haplotype-based Parallel PBWT for Biobank Scale Data","abstract":"Abstract Durbin’s positional Burrows-Wheeler transform (PBWT) enables algorithms with the optimal time complexity of O ( MN ) for reporting all vs all haplotype matches in a population panel with M haplotypes and N variant sites. However, even this efficiency may still be too slow when the number of haplotypes reaches millions. To further reduce the run time, in this paper, a parallel version of the PBWT algorithms is introduced for all versus all haplotype matching, which is called HP-PBWT (haplotype-based parallel PBWT). HP-PBWT parallelly executes the PBWT by splitting a haplotype panel into blocks of haplotypes. HP-PBWT algorithms achieve parallelization for PBWT construction, reporting all versus all L-long matches, and reporting all versus all set-maximal matches while maintaining memory efficiency. HP-PBWT has an time complexity in PBWT construction, and an time complexity for reporting all versus all L-long matches and reporting all versus all set-maximal matches, where T is the number of threads and c* is the maximum number of matches (of length L or maximum divergence value for L-long matches and set-maximal matches, re-spectively) per haplotype per site. HP-PBWT achieves 4-fold speed-up in UK Biobank genotyping array data with 30 threads in the IO-included benchmarks. When applying HP-PBWT to a dataset of 8 million randomized haplotypes (random binary strings of equal length) in the IO-excluded benchmarks, it can achieve a 22-fold speed-up with 60 cores on the Amazon EC2 server. With further hardware optimization, HP-PBWT is expected to handle billions of haplotypes efficiently.","journal":"bioRxiv (Cold Spring Harbor Laboratory)","year":2025,"id":561778,"datarank":0.0,"base_score":0.0,"endowment":0.0,"self_citation_contribution":0.0,"citation_network_contribution":0.0,"self_endowment_contribution":0.0,"citer_contribution":0.0,"corpus_percentile":null,"corpus_rank":null,"citation_count":0,"citer_count":0,"citers_with_citation_signal":0,"citers_with_endowment":0,"datacite_reuse_total":0,"is_dataset":false,"is_dataset_confidence":0.9512,"is_data_producer":false,"deposit_databanks":null,"is_oa":true,"file_count":0,"downloads":0,"has_version_chain":false,"published_date":"2025-01-01","fair_score":null,"fair_percentile":null,"algorithm_id":"datarank_citation_only_1hop_v6","ranking_scope":"data_only","authors":[{"id":566752,"name":"Ahsan Sanaullah","orcid":null,"position":1,"is_corresponding":false},{"id":24932,"name":"Degui Zhi","orcid":"0000-0001-7754-1890","position":2,"is_corresponding":false},{"id":87093,"name":"Shaojie Zhang","orcid":"0000-0002-4051-5549","position":3,"is_corresponding":false},{"id":726009,"name":"Kecong Tang","orcid":"0000-0002-8713-2959","position":0,"is_corresponding":true}],"reference_count":20,"raw_metadata":null,"created_at":"2026-07-19T02:56:01.883848Z","pmid":"39975308","pmcid":null,"fwci":null,"citation_percentile":null,"influential_citations":0,"oa_status":null,"license":null,"views":0,"total_file_size_bytes":0,"version_count":0,"fair_f":null,"fair_a":null,"fair_i":null,"fair_r":null,"fair_zscore":null,"fair_rationale":null,"fair_model":null,"fair_agent_version":null,"fair_fulltext_source":null,"fair_has_llm":null,"fair_computed_at":null,"clinical_trials":[],"software_tools":[],"db_accessions":[],"linked_datasets":[],"topics":[]}