Safety in Multi-Assembly via Paths Appearing in All Path Covers of a DAG
Safety in Multi-Assembly via Paths Appearing in All Path Covers of a DAG
复制标题
DOI：
10.1109/tcbb.2021.3131203
复制
发表时间：
2022-11-01
影响因子：
4.5
通讯作者：
Tomescu, Alexandru I.
中科院分区：
文献类型：
--
作者：
Caceres, Manuel;Mumey, Brendan;Tomescu, Alexandru I.
多组装问题要求从所有序列的混合读出中重建多个基因组序列。这类问题的标准公式将解建模为有向无环图中的路径覆盖，即共同覆盖图的所有顶点的一组路径。由于多组装问题在实践中允许多个解，我们考虑了标准基因组组装中常用的一种方法：仅输出出现在所有路径覆盖解中的部分解(重叠群或安全路径)。我们研究了约束路径覆盖，这是一种对路径覆盖解的约束，它包含了多装配问题中出现的实际约束。给出了寻找约束路径覆盖的所有最大安全路径的有效算法。我们计算了由不同物种的转录注释构建的剪接图的安全路径。我们的算法在每个物种的运行时间不到15秒，并报告RNA重叠群的精度超过99%，并且比单位群长达8倍。此外，在大多数情况下，RNA重叠群覆盖了超过70%的转录本及其编码序列。最大安全路径具有更长的单位长度、更高的精度和更快的构建时间，可以为转录汇编程序提供更好的序列基组。
A multi-assembly problem asks to reconstruct multiple genomic sequences from mixed reads sequenced from all of them. Standard formulations of such problems model a solution as a path cover in a directed acyclic graph, namely a set of paths that together cover all vertices of the graph. Since multi-assembly problems admit multiple solutions in practice, we consider an approach commonly used in standard genome assembly: output only partial solutions (contigs, or safe paths), that appear in all path cover solutions. We study constrained path covers, a restriction on the path cover solution that incorporate practical constraints arising in multi-assembly problems. We give efficient algorithms finding all maximal safe paths for constrained path covers. We compute the safe paths of splicing graphs constructed from transcript annotations of different species. Our algorithms run in less than 15 seconds per species and report RNA contigs that are over 99% precise and are up to 8 times longer than unitigs. Moreover, RNA contigs cover over 70% of the transcripts and their coding sequences in most cases. With their increased length to unitigs, high precision, and fast construction time, maximal safe paths can provide a better base set of sequences for transcript assembly programs.