Finding all maximal perfect haplotype blocks in linear time

Show simple item record

dc.contributor University of Helsinki, Department of Computer Science en
dc.contributor University of Helsinki, Department of Computer Science en
dc.contributor.author Alanko, J.
dc.contributor.author Bannai, H.
dc.contributor.author Cazaux, B.
dc.contributor.author Peterlongo, Peter
dc.contributor.author Stoye, J.
dc.date.accessioned 2020-03-10T13:02:01Z
dc.date.available 2020-03-10T13:02:01Z
dc.date.issued 2020-02-10
dc.identifier.citation 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 en
dc.identifier.issn 1748-7188
dc.identifier.other PURE: 133404088
dc.identifier.other PURE UUID: 71cd5c93-8326-4c6f-aa8e-82f4a0df9ca9
dc.identifier.other Bibtex: Alanko2020
dc.identifier.other Scopus: 85079277319
dc.identifier.other ORCID: /0000-0002-8003-9225/work/70953933
dc.identifier.other WOS: 000519959500001
dc.identifier.uri http://hdl.handle.net/10138/313160
dc.description.abstract 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. en
dc.format.extent 7
dc.language.iso eng
dc.relation.ispartof Algorithms for Molecular Biology
dc.rights en
dc.subject 113 Computer and information sciences en
dc.subject 1182 Biochemistry, cell and molecular biology en
dc.title Finding all maximal perfect haplotype blocks in linear time en
dc.type Article
dc.description.version Peer reviewed
dc.identifier.doi https://doi.org/10.1186/s13015-020-0163-6
dc.type.uri info:eu-repo/semantics/other
dc.type.uri info:eu-repo/semantics/publishedVersion
dc.contributor.pbl
dc.contributor.pbl
dc.contributor.pbl
dc.contributor.pbl

Files in this item

Total number of downloads: Loading...

Files Size Format View
document.pdf 1.722Mb PDF View/Open

This item appears in the following Collection(s)

Show simple item record