An In-place Framework for Exact and Approximate Shortest Unique Substring Queries
An In-place Framework for Exact and Approximate Shortest Unique Substring Queries
复制标题
精确和近似最短唯一子串查询的就地框架
DOI：
10.1007/978-3-662-48971-0_63
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Bojian Xu
中科院分区：
文献类型：
--
作者：
W. Hon;Sharma V. Thankachan;Bojian Xu
我们重新审视确切的最短唯一子串（SUS）的发现问题，并提出其近似版本的不匹配是允许的，由于其在计算生物学等子领域的应用。我们设计了一个通用的就地框架，适合解决精确和近似的k-不匹配SUS发现，使用最小2n内存字加上n字节的空间，其中n是输入字符串的大小。通过使用原地框架，我们可以分别使用O（n）和O（n^2）\）时间找到每个字符串位置的精确和近似k-失配SUS，而不管k的值如何。我们的框架不涉及任何压缩或简洁的数据结构，因此是实用的，易于实现。
We revisit the exact shortest unique substring (SUS) finding problem, and propose its approximate version where mismatches are allowed, due to its applications in subfields such as computational biology. We design a generic in-place framework that fits to solve both the exact and approximate k-mismatch SUS finding, using the minimum 2n memory words plus n bytes space, where n is the input string size. By using the in-place framework, we can find the exact and approximate k-mismatch SUS for every string position using a total of O(n) and \(O(n^2)\) time, respectively, regardless of the value of k. Our framework does not involve any compressed or succinct data structures and thus is practical and easy to implement.