Finding all maximal perfect haplotype blocks in linear time
Alanko J, Bannai H, Cazaux B, Peterlongo P, Stoye J (2020)
Algorithms for Molecular Biology 15: 2.
Zeitschriftenaufsatz
| Veröffentlicht | Englisch
Download
![Open access file OA](https://pub.uni-bielefeld.de/images/access_open.png)
Autor*in
Alanko, Jarno;
Bannai, Hideo;
Cazaux, Bastien;
Peterlongo, Pierre;
Stoye, JensUniBi ![](https://pub.uni-bielefeld.de/images/icon_orcid.png)
![](https://pub.uni-bielefeld.de/images/icon_orcid.png)
Einrichtung
Abstract / Bemerkung
Recent large-scale community sequencing efforts allow at an unprecedented level of detail the identification of genomic regions that show signatures of natural selection. Traditional methods for identifying such regions from individuals’ haplotype data, however, require excessive computing times and therefore are not applicable to current datasets. In 2019, Cunha et al. (Advances in bioinformatics and computational biology: 11th Brazilian symposium on bioinformatics, BSB 2018, Niterói, Brazil, October 30 - November 1, 2018, Proceedings, 2018. https://doi.org/10.1007/978-3-030-01722-4_3) suggested the maximal perfect haplotype block as a very simple combinatorial pattern, forming the basis of a new method to perform rapid genome-wide selection scans. The algorithm they presented for identifying these blocks, however, had a worst-case running time quadratic in the genome length. It was posed as an open problem whether an optimal, linear-time algorithm exists. In this paper we give two algorithms that achieve this time bound, one conceptually very simple one using suffix trees and a second one using the positional Burrows–Wheeler Transform, that is very efficient also in practice.
Erscheinungsjahr
2020
Zeitschriftentitel
Algorithms for Molecular Biology
Band
15
Art.-Nr.
2
Urheberrecht / Lizenzen
ISSN
1748-7188
eISSN
1748-7188
Finanzierungs-Informationen
Open-Access-Publikationskosten wurden durch die Deutsche Forschungsgemeinschaft und die Universität Bielefeld gefördert.
Page URI
https://pub.uni-bielefeld.de/record/2939618
Zitieren
Alanko J, Bannai H, Cazaux B, Peterlongo P, Stoye J. Finding all maximal perfect haplotype blocks in linear time. Algorithms for Molecular Biology. 2020;15: 2.
Alanko, J., Bannai, H., Cazaux, B., Peterlongo, P., & Stoye, J. (2020). Finding all maximal perfect haplotype blocks in linear time. Algorithms for Molecular Biology, 15, 2
Alanko, Jarno, Bannai, Hideo, Cazaux, Bastien, Peterlongo, Pierre, and Stoye, Jens. 2020. “Finding all maximal perfect haplotype blocks in linear time”. Algorithms for Molecular Biology 15: 2.
Alanko, J., Bannai, H., Cazaux, B., Peterlongo, P., and Stoye, J. (2020). Finding all maximal perfect haplotype blocks in linear time. Algorithms for Molecular Biology 15:2.
Alanko, J., et al., 2020. Finding all maximal perfect haplotype blocks in linear time. Algorithms for Molecular Biology, 15: 2.
J. Alanko, et al., “Finding all maximal perfect haplotype blocks in linear time”, Algorithms for Molecular Biology, vol. 15, 2020, : 2.
Alanko, J., Bannai, H., Cazaux, B., Peterlongo, P., Stoye, J.: Finding all maximal perfect haplotype blocks in linear time. Algorithms for Molecular Biology. 15, : 2 (2020).
Alanko, Jarno, Bannai, Hideo, Cazaux, Bastien, Peterlongo, Pierre, and Stoye, Jens. “Finding all maximal perfect haplotype blocks in linear time”. Algorithms for Molecular Biology 15 (2020): 2.
Alle Dateien verfügbar unter der/den folgenden Lizenz(en):
Creative Commons Namensnennung 4.0 International Public License (CC-BY 4.0):
Volltext(e)
Name
s13015-020-0163-6.stoye.pdf
1.81 MB
Access Level
![Open access file OA](https://pub.uni-bielefeld.de/images/access_open.png)
Zuletzt Hochgeladen
2020-02-17T10:30:58Z
MD5 Prüfsumme
005c69237685c52187649799fb9fecbd
Daten bereitgestellt von European Bioinformatics Institute (EBI)
Zitationen in Europe PMC
Daten bereitgestellt von Europe PubMed Central.
References
Daten bereitgestellt von Europe PubMed Central.
Export
Markieren/ Markierung löschen
Markierte Publikationen
Web of Science
Dieser Datensatz im Web of Science®Quellen
PMID: 32055252
PubMed | Europe PMC
Suchen in