多序列的近似LCS改进算法

摘要：

提出2种针对3条源序列的近似LCS算法,近似因子均为1/|∑|.其中,线性近似LCS算法的时空复杂度均为O(n),n为最长源序列的长度,适于解决大规模问题.递归近似LCS算法时空复杂度均为O(nlogn),适于要求高精度问题.同时,这2种算法都能用于解决多序列的LCS和CLCS问题.实验验证了这2种算法的有效性.

关键词：生物信息学、最长公共子序列、近似因子、约束

所属期刊栏目：37

分类号：TP311.52(计算技术、计算机技术)

资助基金：江苏省自然科学基金资助项目BK2009393

在线出版日期：2011-04-29（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：166-168,171