Abstract
Computing maximal perfect blocks of a given panel of haplotypes is a crucial task for efficiently solving problems such as polyploid haplotype reconstruction and finding identical-by-descent segments shared among individuals of a population. Unfortunately, the presence of missing data in the haplotype panel limits the usefulness of the notion of perfect blocks.
We propose a novel algorithm for computing maximal blocks in a panel with missing data (represented as wildcards). The algorithm is based on the Positional Burrows-Wheeler Transform (PBWT) and has been implemented in the tool Wild-pBWT, available at https://github.com/AlgoLab/Wild-pBWT/. Experimental comparison showed that Wild-pBWT is 10–15 times faster than another state-of-the-art approach, while using a negligible amount of memory.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
References
Alanko, J., et al.: Finding all maximal perfect haplotype blocks in linear time. Algorithms Mol. Biol. 15 (2020). https://doi.org/10.1186/s13015-020-0163-6
Baaijens, J.A., et al.: Computational graph pangenomics: a tutorial on data structures and their applications. Nat. Comput. 21(1), 81–108 (2022). https://doi.org/10.1007/s11047-022-09882-6
Bonizzoni, P., et al.: Compressed data structures for population-scale positional burrows–wheeler transforms. bioRxiv (2022). https://doi.org/10.1101/2022.09.16.508250
Cunha, L., Diekmann, Y., Kowada, L., Stoye, J.: Identifying maximal perfect haplotype blocks. In: Alves, R. (ed.) BSB 2018. LNCS, vol. 11228, pp. 26–37. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-01722-4_3
Durbin, R.: Efficient haplotype matching and storage using the positional Burrows-Wheeler transform (PBWT). Bioinformatics 30 (2014). https://doi.org/10.1093/bioinformatics/btu014
Gog, S., Beller, T., Moffat, A., Petri, M.: From theory to practice: plug and play with succinct data structures. In: Gudmundsson, J., Katajainen, J. (eds.) SEA 2014. LNCS, vol. 8504, pp. 326–337. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-07959-2_28
Halldorsson, B.V., et al.: The sequences of 150,119 genomes in the UK Biobank. Nature 607 (2022). https://doi.org/10.1038/s41586-022-04965-x
Kirsch-Gerweck, B., et al.: Haploblocks: efficient detection of positive selection in large population genomic datasets. Mol. Biol. Evol. 40 (2023). https://doi.org/10.1093/molbev/msad027
Moeinzadeh, M.H., et al.: Ranbow: a fast and accurate method for polyploid haplotype reconstruction. PLOS Comput. Biol. 16 (2020). https://doi.org/10.1371/journal.pcbi.1007843
Naseri, A., Zhi, D., Zhang, S.: Multi-allelic positional Burrows-Wheeler transform. BMC Bioinform. 20 (2019). https://doi.org/10.1186/s12859-019-2821-6
Naseri, A., et al.: RaPID: ultra-fast, powerful, and accurate detection of segments identical by descent (IBD) in biobank-scale cohorts. Genome Biol. 20 (2019). https://doi.org/10.1186/s13059-019-1754-8
Rubinacci, S., Delaneau, O., Marchini, J.: Genotype imputation using the positional Burrows-Wheeler transform. PLOS Genetics 16 (2020). https://doi.org/10.1371/journal.pgen.1009049
Taliun, D., et al.: Sequencing of 53,831 diverse genomes from the NHLBI TOPMed Program. Nature 590 (2021). https://doi.org/10.1038/s41586-021-03205-y
Vigna, S.: Broadword implementation of rank/select queries. In: McGeoch, C.C. (ed.) WEA 2008. LNCS, vol. 5038, pp. 154–168. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-68552-4_12
Williams, L., Mumey, B.: Maximal perfect haplotype blocks with wildcards. iScience 23 (2020). https://doi.org/10.1016/j.isci.2020.101149
Acknowledgements
This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No. 872539.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Bonizzoni, P., Della Vedova, G., Pirola, Y., Rizzi, R., Sgrò, M. (2023). Multiallelic Maximal Perfect Haplotype Blocks with Wildcards via PBWT. In: Rojas, I., Valenzuela, O., Rojas Ruiz, F., Herrera, L.J., Ortuño, F. (eds) Bioinformatics and Biomedical Engineering. IWBBIO 2023. Lecture Notes in Computer Science(), vol 13919. Springer, Cham. https://doi.org/10.1007/978-3-031-34953-9_5
Download citation
DOI: https://doi.org/10.1007/978-3-031-34953-9_5
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-34952-2
Online ISBN: 978-3-031-34953-9
eBook Packages: Computer ScienceComputer Science (R0)