nach oben

Erschienen in:

2023 | OriginalPaper | Buchkapitel

Multiallelic Maximal Perfect Haplotype Blocks with Wildcards via PBWT

verfasst von : Paola Bonizzoni, Gianluca Della Vedova, Yuri Pirola, Raffaella Rizzi, Mattia Sgrò

Erschienen in: Bioinformatics and Biomedical Engineering

Verlag: Springer Nature Switzerland

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel An Algorithm for Pairwise DNA Sequences Alignment

Nächstes Kapitel GPU Cloud Architectures for Bioinformatic Applications

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-6CrossRefPubMedPubMedCentral

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_3CrossRef

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_28CrossRef

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

10.

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

11.

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

12.

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

13.

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

14.

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_12CrossRef

15.

Williams, L., Mumey, B.: Maximal perfect haplotype blocks with wildcards. iScience 23 (2020). https://doi.org/10.1016/j.isci.2020.101149

Titel: Multiallelic Maximal Perfect Haplotype Blocks with Wildcards via PBWT
verfasst von: Paola Bonizzoni
Gianluca Della Vedova
Yuri Pirola
Raffaella Rizzi
Mattia Sgrò
Verlag: Springer Nature Switzerland
Buch: Bioinformatics and Biomedical Engineering
Print ISBN: 978-3-031-34952-2

Electronic ISBN: 978-3-031-34953-9

Copyright-Jahr: 2023
DOI: https://doi.org/10.1007/978-3-031-34953-9_5

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner