An Efficient Algorithm for Finding All Pairs k-Mismatch Maximal Common Substrings
An Efficient Algorithm for Finding All Pairs k-Mismatch Maximal Common Substrings
复制标题
一种查找所有k-失配最大公共子串对的高效算法
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
S. Aluru
中科院分区：
文献类型：
--
作者：
Sharma V. Thankachan;Sriram P. Chockalingam;S. Aluru
在大量序列中识别长的成对最大公共子串是计算生物学中常用的构造，应用于 DNA 序列聚类和组装。由于测序仪所犯的错误，能够适应少量差异的算法特别令人感兴趣，但针对此类问题获得可证明有效的解决方案一直难以实现。在本文中，我们提出了一种可证明有效的算法，其预期运行时间保证为 (O(Nlog ^k N+mathsf {occ}))，其中 (mathsf {occ}) 是输出大小，适用于以下问题：给定总长度为 N、长度阈值 (phi ) 和不匹配阈值 (k ge) 的 n 个序列的集合 ({mathcal D}={S_1,S_2,dots , S_n}) 0)，报告 ({mathcal D}) 中所有序列对上长度至少为 (phi ) 的所有 k 失配最大公共子串。此外，我们还提出了一个显示该问题的难度的结果。
Identifying long pairwise maximal common substrings among a large set of sequences is a frequently used construct in computational biology, with applications in DNA sequence clustering and assembly. Due to errors made by sequencers, algorithms that can accommodate a small number of differences are of particular interest, but obtaining provably efficient solutions for such problems has been elusive. In this paper, we present a provably efficient algorithm with an expected run time guarantee of (O(Nlog ^k N+mathsf {occ})), where (mathsf {occ}) is the output size, for the following problem: Given a collection ({mathcal D}={S_1,S_2,dots , S_n}) of n sequences of total length N, a length threshold (phi ) and a mismatch threshold (k ge 0), report all k-mismatch maximal common substrings of length at least (phi ) over all pairs of sequences in ({mathcal D}). In addition, we present a result showing the hardness of this problem.