An Efficient Algorithm for the Longest Tandem Scattered Subsequence Problem
An Efficient Algorithm for the Longest Tandem Scattered Subsequence Problem
复制标题
最长串联散乱子序列问题的高效算法
DOI：
10.1007/978-3-540-30213-1_13
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
A. Kosowski
中科院分区：
文献类型：
--
作者：
A. Kosowski
本文讨论了对给定的字符序列求最大长度的串联离散子序列的问题。如果一个序列可以被分成两个相同的序列，则该序列被称为串联序列。本文给出了一个求解LTS问题的有效算法，其计算复杂度为O（n ~ 2），存储复杂度与分析序列的长度成线性关系。提出并讨论了一个猜想，指出所给算法的复杂度可能不容易提高。最后，讨论了LTS问题的解决方案在DNA序列近似串联子串匹配中的潜在应用。
The paper deals with the problem of finding a tandem scattered subsequence of maximum length (LTS) for a given character sequence. A sequence is referred to as tandem if it can be split into two identical sequences. An efficient algorithm for the LTS problem is presented and is shown to haveO(n2) computational complexity and linear memory complexity with respect to the lengthnof the analysed sequence. A conjecture is put forward and discussed, stating that the complexity of the given algorithm may not be easily improved. Finally, the potential application of the solution to the LTS problem in approximate tandem substring matching in DNA sequences is discussed.
DOI：
--
发表时间：
2016
期刊：
影响因子：
--
作者：
Shuhei Denzumi
通讯作者：
Shuhei Denzumi