License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.WABI.2019.8
URN: urn:nbn:de:0030-drops-110388
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11038/
Go to the corresponding LIPIcs Volume Portal

Alanko, Jarno ; Bannai, Hideo ; Cazaux, Bastien ; Peterlongo, Pierre ; Stoye, Jens

Finding All Maximal Perfect Haplotype Blocks in Linear Time

pdf-format:
LIPIcs-WABI-2019-8.pdf (0.4 MB)

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. (Proceedings of BSB 2019) 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.

BibTeX - Entry

@InProceedings{alanko_et_al:LIPIcs:2019:11038,
  author =	{Jarno Alanko and Hideo Bannai and Bastien Cazaux and Pierre Peterlongo and Jens Stoye},
  title =	{{Finding All Maximal Perfect Haplotype Blocks in Linear Time}},
  booktitle =	{19th International Workshop on Algorithms in Bioinformatics (WABI 2019)},
  pages =	{8:1--8:9},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-123-8},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{143},
  editor =	{Katharina T. Huber and Dan Gusfield},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/11038},
  URN =		{urn:nbn:de:0030-drops-110388},
  doi =		{10.4230/LIPIcs.WABI.2019.8},
  annote =	{Keywords: Population genomics, selection coefficient, haplotype block, positional Burrows-Wheeler Transform}
}

Keywords: Population genomics, selection coefficient, haplotype block, positional Burrows-Wheeler Transform
Collection: 19th International Workshop on Algorithms in Bioinformatics (WABI 2019)
Issue Date: 2019
Date of publication: 03.09.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI