Finding all maximal perfect haplotype blocks in linear time

Näytä kaikki kuvailutiedot



Pysyväisosoite

http://hdl.handle.net/10138/313160

Lähdeviite

Alanko , J , Bannai , H , Cazaux , B , Peterlongo , P & Stoye , J 2020 , ' Finding all maximal perfect haplotype blocks in linear time ' , Algorithms for Molecular Biology , vol. 15 , no. 1 , 2 . https://doi.org/10.1186/s13015-020-0163-6

Julkaisun nimi: Finding all maximal perfect haplotype blocks in linear time
Tekijä: Alanko, J.; Bannai, H.; Cazaux, B.; Peterlongo, Peter; Stoye, J.
Muu tekijä: University of Helsinki, Department of Computer Science
University of Helsinki, Department of Computer Science
Päiväys: 2020-02-10
Kieli: eng
Sivumäärä: 7
Kuuluu julkaisusarjaan: Algorithms for Molecular Biology
ISSN: 1748-7188
URI: http://hdl.handle.net/10138/313160
Tiivistelmä: 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, Niteroi, Brazil, October 30 - November 1, 2018, Proceedings, 2018. 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.
Avainsanat: 113 Computer and information sciences
1182 Biochemistry, cell and molecular biology
Tekijänoikeustiedot:


Tiedostot

Latausmäärä yhteensä: Ladataan...

Tiedosto(t) Koko Formaatti Näytä
document.pdf 1.722MB PDF Avaa tiedosto

Viite kuuluu kokoelmiin:

Näytä kaikki kuvailutiedot