Sequence Alignment on Directed Graphs
Sequence Alignment on Directed Graphs
复制标题
DOI：
10.1089/cmb.2017.0264
复制
发表时间：
2018-09-08
影响因子：
1.7
通讯作者：
Sivadasan, Naveen
中科院分区：
文献类型：
--
作者：
Kavya, Vaddadi Naga Sai;Tayal, Kshitij;Sivadasan, Naveen
参考集合中的基因组变异自然地表示为基因组变异图。这样的图将公共连续性编码为顶点，并且使用附加顶点和有向边来捕获变化。所得到的图是可能具有圈的有向图。用于在这样的图上比对序列的现有算法利用在有向无环图（DAG）上工作的偏序比对（POA）技术。为了实现这一点，输入图的非循环扩展首先通过昂贵的循环展开步骤（DAG化）来构建。此外，这样的图扩展可能在它们的大小上具有相当大的爆破，并且在最坏的情况下，爆破因子与输入序列长度成比例。我们提供了一种新的对齐算法V-ALIGN，它直接在输入图上对齐输入序列，同时避免了这种昂贵的DAG化步骤。V-ALIGN是基于一种新的动态规划（DP）制定，允许直接在输入图的间隙对齐。它支持仿射和线性间隙。我们还提出了改进的V-ALIGN在实践中更好的性能。通过改进，填充DP表的时间与序列、图及其反馈顶点集的大小成线性关系。我们进行了实验，比较所提出的算法对现有的POA为基础的技术。我们还进行了比对实验的基因组变异图构建从1000个基因组数据。对于比对短序列，标准方法将昂贵的空位比对限制为与输入序列具有高相似性的小的过滤子图。在这种情况下，V-ALIGN在过滤子图上的间隙对齐的性能取决于子图的大小。
Genomic variations in a reference collection are naturally represented as genome variation graphs. Such graphs encode common subsequences as vertices and the variations are captured using additional vertices and directed edges. The resulting graphs are directed graphs possibly with cycles. Existing algorithms for aligning sequences on such graphs make use of partial order alignment (POA) techniques that work on directed acyclic graphs (DAGs). To achieve this, acyclic extensions of the input graphs are first constructed through expensive loop unrolling steps (DAGification). Furthermore, such graph extensions could have considerable blowup in their size and in the worst case the blow-up factor is proportional to the input sequence length. We provide a novel alignment algorithm V-ALIGN that aligns the input sequence directly on the input graph while avoiding such expensive DAGification steps. V-ALIGN is based on a novel dynamic programming (DP) formulation that allows gapped alignment directly on the input graph. It supports affine and linear gaps. We also propose refinements to V-ALIGN for better performance in practice. With the proposed refinements, the time to fill the DP table has linear dependence on the sizes of the sequence, the graph, and its feedback vertex set. We conducted experiments to compare the proposed algorithm against the existing POA-based techniques. We also performed alignment experiments on the genome variation graphs constructed from the 1000 Genomes data. For aligning short sequences, standard approaches restrict the expensive gapped alignment to small filtered subgraphs having high similarity to the input sequence. In such cases, the performance of V-ALIGN for gapped alignment on the filtered subgraph depends on the subgraph sizes.