Gap Filling as Exact Path Length Problem
- 1 May 2016
- journal article
- research article
- Published by SAGE Publications in Journal of Computational Biology
- Vol. 23 (5) , 347-361
Abstract
One of the last steps in a genome assembly project is filling the gaps between consecutive contigs in the scaffolds. This problem can be naturally stated as finding an s-t path in a directed graph whose sum of arc costs belongs to a given range (the estimate on the gap length). Here s and t are any two contigs flanking a gap. This problem is known to be NP-hard in general. Here we derive a simpler dynamic programming solution than already known, pseudo-polynomial in the maximum value of the input range. We implemented various practical optimizations to it, and compared our exact gap-filling solution experimentally to popular gap-filling tools. Summing over all the bacterial assemblies considered in our experiments, we can in total fill 76% more gaps than the best previous tool, and the gaps filled by our method span 136% more sequence. Furthermore, the error level of the newly introduced sequence is comparable to that of the previous tools. The experiments also show that our exact approach does not easily scale to larger genomes, where the problem is in general difficult for all tools.Keywords
This publication has 20 references indexed in Scilit:
- GATB: Genome Assembly & Analysis Tool BoxBioinformatics, 2014
- QUAST: quality assessment tool for genome assembliesBioinformatics, 2013
- Toward almost closed genomes with GapFillerGenome Biology, 2012
- High-quality draft assemblies of mammalian genomes from massively parallel sequence dataProceedings of the National Academy of Sciences, 2010
- Ultrafast and memory-efficient alignment of short DNA sequences to the human genomeGenome Biology, 2009
- Versatile and open software for comparing large genomesGenome Biology, 2004
- Biological Sequence Analysis1998
- A Mildly Exponential Time Algorithm for Approximating the Number of Solutions to a Multidimensional Knapsack ProblemCombinatorics, Probability and Computing, 1993
- Reducibility among Combinatorial Problems1972
- On a routing problemQuarterly of Applied Mathematics, 1958