IEEE/ACM Trans Comput Biol Bioinform. 2019 Mar-Apr;16(2):617-626. doi: 10.1109/TCBB.2017.2785831. Epub 2018 Jan 15.
Gap filling has emerged as a natural sub-problem of many de novo genome assembly projects. The gap filling problem generally asks for an $s$s-$t$t path in an assembly graph whose length matches the gap length estimate. Several methods have addressed it, but only few have focused on strategies for dealing with multiple gap filling solutions and for guaranteeing reliable results. Such strategies include reporting only unique solutions, or exhaustively enumerating all filling solutions and heuristically creating their consensus. Our main contribution is a new method for reliable gap filling: filling gaps with those sub-paths common to all gap filling solutions. We call these partial solutions safe, following the framework of (Tomescu and Medvedev, RECOMB 2016). We give an efficient safe algorithm running in $O(dm)$O(dm) time and space, where $d$d is the gap length estimate and $m$m is the number of edges of the assembly graph. To show the benefits of this method, we implemented this algorithm for the problem of filling gaps in scaffolds. Our experimental results on bacterial and on conservative human assemblies show that, on average, our method can retrieve over 73 percent more safe and correct bases as compared to previous methods, with a similar precision.
缺口填补已成为许多从头基因组组装项目的自然子问题。缺口填补问题通常要求在组装图中找到一条长度与缺口长度估计值匹配的 $s$-$t$t 路径。已经有几种方法解决了这个问题，但只有少数方法专注于处理多个缺口填补解决方案并保证可靠结果的策略。这些策略包括只报告唯一的解决方案，或者详尽地枚举所有填补解决方案，并启发式地创建它们的共识。我们的主要贡献是一种可靠的缺口填补新方法：用所有缺口填补解决方案共有的子路径来填补缺口。根据 (Tomescu 和 Medvedev，RECOMB 2016) 的框架，我们称这些部分解决方案为安全的。我们给出了一个在 $O(dm)$O(dm) 时间和空间复杂度下运行的高效安全算法，其中 $d$d 是缺口长度估计值，$m$m 是组装图的边数。为了展示这种方法的好处，我们将此算法实现为填补支架中的缺口问题。我们在细菌和保守人类基因组组装上的实验结果表明，与以前的方法相比，我们的方法平均可以检索到超过 73%的更多安全和正确的碱基，并且具有相似的精度。
