Please use this identifier to cite or link to this item: http://hdl.handle.net/10995/75060
Title: Linear time minimum segmentation enables scalable founder reconstruction
Authors: Norri, T.
Cazaux, B.
Kosolobov, D.
Mäkinen, V.
Issue Date: 2019
Publisher: BioMed Central Ltd.
Citation: Linear time minimum segmentation enables scalable founder reconstruction / T. Norri, B. Cazaux, D. Kosolobov et al. // Algorithms for Molecular Biology. — 2019. — Vol. 14. — Iss. 1. — 12.
Abstract: Background: We study a preprocessing routine relevant in pan-genomic analyses: consider a set of aligned haplotype sequences of complete human chromosomes. Due to the enormous size of such data, one would like to represent this input set with a few founder sequences that retain as well as possible the contiguities of the original sequences. Such a smaller set gives a scalable way to exploit pan-genomic information in further analyses (e.g. read alignment and variant calling). Optimizing the founder set is an NP-hard problem, but there is a segmentation formulation that can be solved in polynomial time, defined as follows. Given a threshold L and a set {\mathcal {R}} = \{R-1, \ldots, R-m\} R = { R 1, ..., R m } of m strings (haplotype sequences), each having length n, the minimum segmentation problem for founder reconstruction is to partition [1, n] into set P of disjoint segments such that each segment [a,b] \in P [ a, b ] P has length at least L and the number d(a,b)=|\{R-i[a,b]:1\le i \le m\}| d (a, b) = | { R i [ a, b ]: 1 ≤ i ≤ m } | of distinct substrings at segment [a, b] is minimized over [a,b] \in P [ a, b ] P. The distinct substrings in the segments represent founder blocks that can be concatenated to form \max \{ d(a,b):[a,b] \in P \} max { d (a, b): [ a, b ] P } founder sequences representing the original {\mathcal {R}} R such that crossovers happen only at segment boundaries. Results: We give an O(mn) time (i.e. linear time in the input size) algorithm to solve the minimum segmentation problem for founder reconstruction, improving over an earlier O(mn^2) O (m n 2). Conclusions: Our improvement enables to apply the formulation on an input of thousands of complete human chromosomes. We implemented the new algorithm and give experimental evidence on its practicality. The implementation is available in https://github.com/tsnorri/founder-sequences. © 2019 The Author(s).
Keywords: DYNAMIC PROGRAMMING
FOUNDER RECONSTRUCTION
PAN-GENOME INDEXING
POSITIONAL BURROWS-WHEELER TRANSFORM
RANGE MINIMUM QUERY
URI: http://hdl.handle.net/10995/75060
Access: info:eu-repo/semantics/openAccess
SCOPUS ID: 85065895221
WOS ID: 000468292600001
PURE ID: 9818196
ISSN: 1748-7188
DOI: 10.1186/s13015-019-0147-6
metadata.dc.description.sponsorship: This work was partially supported by the Academy of Finland (Grant 309048).
Appears in Collections:Научные публикации, проиндексированные в SCOPUS и WoS CC

Files in This Item:
File Description SizeFormat 
10.1186-s13015-019-0147-6.pdf2,95 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.