Approximate pattern matching on elastic-degenerate text
Approximate pattern matching on elastic-degenerate text
复制标题
DOI：
10.1016/j.tcs.2019.08.012
复制
发表时间：
2020-04-06
影响因子：
1.1
通讯作者：
Rosone, Giovanna
中科院分区：
文献类型：
--
作者：
Bernardini, Giulia;Pisanti, Nadia;Rosone, Giovanna
弹性简并串是由n组全长N的串组成的序列，它被引入来紧凑地表示几个密切相关的序列(例如泛基因组)的多重比对。在这个表示中，精确匹配的这些序列的子串被折叠，而在序列不同的位置，列出在该位置观察到的所有可能的变体。自然出现的问题是在弹性退化文本中找到长度为确定性模式的所有匹配。已有一个非组合O(nm(1.381)+N)时间算法在线求解该问题[1]。本文在编辑距离模型下研究了同样的问题，并给出了一个O(k(2)mg+kN)时间和O(M)空间算法，其中G是弹性退化文本中的字符串总数，k是允许的最大编辑距离。在Hamming距离下，我们还给出了一个简单的O(KMG+KN)时间和O(M)空间算法。(C)《2019年》，爱思唯尔出版。
An elastic-degenerate string is a sequence of n sets of strings of total length N. It has been introduced to represent a multiple alignment of several closely-related sequences (e.g., pan-genome) compactly. In this representation, substrings of these sequences that match exactly are collapsed, while in positions where the sequences differ, all possible variants observed at that location are listed. The natural problem that arises is finding all matches of a deterministic pattern of length min an elastic-degenerate text. There exists a non-combinatorial O(nm(1.381) + N)-time algorithm to solve this problem on-line [1]. In this paper, we study the same problem under the edit distance model and present an O(k(2)mG + kN)-time and O(m)-space algorithm, where G is the total number of strings in the elastic-degenerate text and k is the maximum edit distance allowed. We also present a simple O(kmG + kN)-time and O(m)-space algorithm for solving the problem under Hamming distance. (C) 2019 Published by Elsevier B.V.