A Provably Efficient Algorithm for the k-Mismatch Average Common Substring Problem
A Provably Efficient Algorithm for the k-Mismatch Average Common Substring Problem
复制标题
k-失配平均公共子串问题的一种可证明有效的算法
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
S. Aluru
中科院分区：
文献类型：
--
作者：
Sharma V. Thankachan;A. Apostolico;S. Aluru
在全基因组分子分类学和系统发育重建的数据密集型应用的推动下，无比对序列比较方法吸引了持续的兴趣。在所有基于子串组合的方法中，平均公共子串（ACS）度量承认一个简单的线性时间序列比较算法，同时在多个应用中产生令人印象深刻的结果。本研究的一个重要方向是扩展的方法，允许一个有界的编辑/汉明距离之间的子串，以便更准确地反映进化过程。然而，到目前为止，设计用于包含k ≥ 1个错配的算法具有O（n（2））最坏情况的时间复杂度，其中n是输入序列的总长度。另一方面，占失配已被证明会导致大大改善分类，而统计学可以提高实际性能。在这篇文章中，我们关闭差距，提出了第一个可证明有效的算法的k-不匹配的平均公共字符串（ACSk）的问题，需要O（n）的空间和O（n log（k）n）的时间在最坏的情况下，任何常数k。我们的方法扩展了广义后缀树模型，将一个精心挑选的有界的扰动后缀集，并可以应用到其他复杂的近似序列匹配问题。
Alignment-free sequence comparison methods are attracting persistent interest, driven by data-intensive applications in genome-wide molecular taxonomy and phylogenetic reconstruction. Among all the methods based on substring composition, the average common substring (ACS) measure admits a straightforward linear time sequence comparison algorithm, while yielding impressive results in multiple applications. An important direction of this research is to extend the approach to permit a bounded edit/hamming distance between substrings, so as to reflect more accurately the evolutionary process. To date, however, algorithms designed to incorporate k ≥ 1 mismatches have O(n(2)) worst-case time complexity, where n is the total length of the input sequences. On the other hand, accounting for mismatches has shown to lead to much improved classification, while heuristics can improve practical performance. In this article, we close the gap by presenting the first provably efficient algorithm for the k-mismatch average common string (ACSk) problem that takes O(n) space and O(n log(k) n) time in the worst case for any constant k. Our method extends the generalized suffix tree model to incorporate a carefully selected bounded set of perturbed suffixes, and can be applied to other complex approximate sequence matching problems.