On the Complexity of Sequence-to-Graph Alignment
On the Complexity of Sequence-to-Graph Alignment
复制标题
DOI：
10.1089/cmb.2019.0066
复制
发表时间：
2020-01-03
影响因子：
1.7
通讯作者：
Aluru, Srinivas
中科院分区：
文献类型：
--
作者：
Jain, Chirag;Zhang, Haowen;Aluru, Srinivas
跨多个个体和群体的广泛遗传数据的可用性正在推动基于图的参考表示的重要性日益增长。将序列与图对齐是对几种类型的序列图（变异图、组装图、泛基因组等）的基本操作。及其生物学应用。虽然序列到图比对的研究是新生的，它可以借鉴超文本模式匹配的相关工作。在这篇文章中，我们研究序列到图的对齐问题下的汉明和编辑距离模型，线性和仿射间隙罚函数，多个变量的问题，允许单独的查询，单独的图形，或两者兼而有之。我们证明，当允许图中单独或与查询中的更改结合进行更改时，对于大小>= 2的字母表，序列到图的对齐问题在海明和编辑距离模型下都是NP完全的。对于只允许对序列进行更改的情况，我们提出了一个O（|V| +m| E|）时间算法，其中m表示查询大小，V和E分别表示图的顶点和边集。我们的结果是可推广到线性和仿射间隙罚函数，并提高了现有算法的运行时复杂度。
Availability of extensive genetic data across multiple individuals and populations is driving the growing importance of graph-based reference representations. Aligning sequences to graphs is a fundamental operation on several types of sequence graphs (variation graphs, assembly graphs, pan-genomes, etc.) and their biological applications. Although research on sequence-to-graph alignments is nascent, it can draw from related work on pattern matching in hypertext. In this article, we study sequence-to-graph alignment problems under Hamming and edit distance models, and linear and affine gap penalty functions, for multiple variants of the problem that allow changes in query alone, graph alone, or in both. We prove that when changes are permitted in graphs either standalone or in conjunction with changes in the query, the sequence-to-graph alignment problem is NP-complete under both Hamming and edit distance models for alphabets of size >= 2. For the case where only changes to the sequence are permitted, we present an O(|V|+m|E|) time algorithm, where m denotes the query size, and V and E denote the vertex and edge sets of the graph, respectively. Our result is generalizable to both linear and affine gap penalty functions, and improves upon the runtime complexity of existing algorithms.