title: Gap Filling as Exact Path Length Problem.
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.
authors.affiliation: 1 Helsinki Institute for Information Technology HIIT, Department of Computer Science, University of Helsinki , Finland .
authors.forename: Leena
authors.initials: L
authors.lastname: Salmela
authors.affiliation: 2 Science for Life Laboratory, School of Computer Science and Communication, KTH Royal Institute of Technology , Solna, Sweden .
authors.forename: Kristoffer
authors.initials: K
authors.lastname: Sahlin
authors.affiliation: 1 Helsinki Institute for Information Technology HIIT, Department of Computer Science, University of Helsinki , Finland .
authors.forename: Veli
authors.initials: V
authors.lastname: Mäkinen
authors.affiliation: 1 Helsinki Institute for Information Technology HIIT, Department of Computer Science, University of Helsinki , Finland .
authors.forename: Alexandru I
authors.initials: AI
authors.lastname: Tomescu
mesh_terms: D000465:Algorithms; D001419:Bacteria / Q000235:genetics*; D019295:Computational Biology / Q000379:methods; D020451:Contig Mapping / Q000379:methods*; D016680:Genome, Bacterial
keywords: de novo assembly; dynamic programming; gap filling; graph algorithms