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.
Bonizzoni, P., Della Vedova, G., Pirola, Y., Rizzi, R., Sgrò, M. (2023). Multiallelic Maximal Perfect Haplotype Blocks with Wildcards via PBWT. In Bioinformatics and Biomedical Engineering 10th International Work-Conference, IWBBIO 2023, Meloneras, Gran Canaria, Spain, July 12–14, 2023, Proceedings, Part I (pp.62-76). Springer [10.1007/978-3-031-34953-9_5].
Multiallelic Maximal Perfect Haplotype Blocks with Wildcards via PBWT
Bonizzoni, P
;Della Vedova, G;Pirola, Y;Rizzi, R;Sgrò, M
2023
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.
| File | Dimensione | Formato | |
|---|---|---|---|
|
Bonizzoni-2023-IWBBIO-VoR.pdf
Solo gestori archivio
Tipologia di allegato:
Publisher’s Version (Version of Record, VoR)
Licenza:
Tutti i diritti riservati
Dimensione
366.76 kB
Formato
Adobe PDF
|
366.76 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
