An Efficient Algorithm for the Longest Tandem Scattered Subsequence Problem

机译：最长串联离散子序列问题的一种有效算法

获取原文

获取原文并翻译 | 示例

页面导航

摘要
著录项
相似文献
相关主题

摘要

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 have O(n~2) computational complexity and linear memory complexity with respect to the length n of 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.

机译：本文讨论的问题是找到给定字符序列的最大长度的串联分散子序列（LTS）。如果一个序列可以分为两个相同的序列，则称为串联。提出了一种针对LTS问题的有效算法，该算法相对于分析序列的长度n具有O（n〜2）的计算复杂度和线性存储复杂度。提出并讨论了一个推测，指出给定算法的复杂性可能不容易提高。最后，讨论了解决LTS问题在DNA序列中近似串联子串匹配中的潜在应用。

著录项

来源
《International Conference on String Processing and Information Retrieval(SPIRE 2004); 20041005-08; Padova(IT)》|2004年|P.93-100|共8页
会议地点 Padova(IT)
作者
Adrian Kosowski;
展开▼
作者单位

Department of Algorithms and System Modeling Gdansk University of Technology, Poland;

展开▼
会议组织
原文格式 PDF
正文语种 eng
中图分类数据备份与恢复;
关键词

相似文献

外文文献
中文文献
专利

1. Efficient CGM-based parallel algorithms for the longest common subsequence problem with multiple substring-exclusion constraints [J] . Parallel Computing . 2020,第Mara期

机译：具有多个子串排除约束的最长公共子序列问题的基于CGM的高效并行算法
2. Space-Efficient Algorithms for Longest Increasing Subsequence [J] . Masashi Kiyomi, Hirotaka Ono, Yota Otachi, Theory of computing systems . 2020,第3期

机译：最长递增子序列的空间有效算法
3. Novel algorithms for efficient subsequence searching and mapping in nanopore raw signals towards targeted sequencing [J] . Han Renmin, Wang Sheng, Gao Xin Bioinformatics . 2020,第5期

机译：纳米孔原始信号朝向目标测序的高效后续搜索和映射的新算法
4. An Efficient Algorithm for the Longest Tandem Scattered Subsequence Problem [C] . Adrian Kosowski International Conference on String Processing and Information Retrieval . 2004

机译：一种高效的算法，最长串联分散的子序列问题
5. Efficient subsequence matching with LCS. [D] . Han, Tae Sik. 2007

机译：与LCS的高效子序列匹配。
6. Efficient algorithms for Longest Common Subsequence of two bucket orders to speed up pairwise genetic map comparison [O] . Lisa De Mattéo, Yan Holtz, Vincent Ranwez, -1

机译：两个存储桶顺序的最长公共子序列的高效算法可加快成对遗传图谱的比较
7. Efficient algorithms for Longest Common Subsequence of two bucket orders to speed up pairwise genetic map comparison [O] . Lisa De Mattéo, Yan Holtz, Vincent Ranwez, 2018

机译：高效算法，用于两个铲斗订单的最长常见子序列，以加速成对遗传地图比较
8. Efficient Algorithmic Solutions to Exponential Tandem Queues with Blocking [R] . Latouche, G., Neuts, M. F. 1978

机译：具有阻塞的指数串联队列的高效算法解决方案

An Efficient Algorithm for the Longest Tandem Scattered Subsequence Problem

摘要

著录项

相似文献

相关主题

期刊订阅