Hardness of optimal spaced seed design
Hardness of optimal spaced seed design
复制标题
DOI：
10.1016/j.jcss.2007.10.001
复制
发表时间：
2008-08-01
影响因子：
1.1
通讯作者：
Rivals, Eric
中科院分区：
文献类型：
--
作者：
Nicolas, Francois;Rivals, Eric
加速近似模式匹配是80年代以来字符串研究领域的一条主线。实用的快速方法属于过滤算法的类别，其中首先排除与该模式不相似的文本区域，然后通过动态规划将剩余区域与该模式进行比较。在用于测试区域和模式之间的相似性的条件中，许多条件要求它们之间的公共子字符串的最小数量。当只考虑替换来衡量相异度时，计算间隔的子词而不是子串提高了过滤效率。然而，根据搜索参数，需要一个预处理步骤来为子词设计一个或多个模式，称为间隔种子(或有间隙种子)。文献中出现了两条截然不同的研究路线：一条是种子设计问题的概率公式，其中，人们希望计算具有最高概率的种子以检测所需的相似性(有损过滤)；另一条是组合配方，其目标是找到检测所有或最大数量相似性的种子(无损和有损过滤)。我们集中在组合种子设计问题上，并考虑这样的公式，其中所寻找的相似性集合要么被明确列出(RSO)，要么被它们的长度和最大失配数量表征(未被检测)。有几篇文章展示了这些问题的指数算法。在这项工作中，我们给出了几个种子设计问题的困难和不可逼近结果，从而证明了已有算法的复杂性。此外，我们引入了一种新的种子设计公式(MWLS)，其中种子的权重必须是最大的，并且证明了它和最大独立集一样难以逼近。(C)2007 Elsevier Inc.保留所有权利。
Speeding up approximate pattern matching is a line of research in stringology since the 80s. Practically fast approaches belong to the class of filtration algorithms, in which text regions dissimilar to the pattern are first excluded, and the remaining regions are then compared to the pattern by dynamic programming. Among the conditions used to test similarity between the regions and the pattern, many require a minimum number of common substrings between them. When only substitutions are taken into account for measuring dissimilarity, Counting spaced subwords instead of substrings improves the filtration efficiency. However, a preprocessing step is required to design one or more patterns, called spaced seeds (or gapped seeds), for the subwords, depending oil the search parameters. Two distinct lines of research appear the literature: one with probabilistic formulations of seed design problems, in which one wishes for instance to compute a seed with the highest probability to detect the desired similarities (lossy filtration), a second line with combinatorial formulations, where the goal is to find a seed that detects all or a maximum number of similarities (both lossless and lossy filtration). We concentrate on combinatorial seed design problems and consider formulations in which the set of sought similarities is either listed explicitly (RSOS), or characterised by their length and maximal number of mismatches (NON-DETECTION). Several articles exhibit exponential algorithms for these problems. In this work, we provide hardness and inapproximability results for several seed design problems, thereby justifying the complexity of known algorithms. Moreover, we introduce a new formulation of seed design (MWLS), in which the weight of the seed has to be maximised, and show it is as difficult to approximate as MAXIMUM INDEPENDENT SET. (c) 2007 Elsevier Inc. All rights reserved.