带约束最长公共子序列快速算法

摘要：

带约束最长公共子序列(CLCS)问题有很深的生物学应用背景,常被用来表示同源基因序列相似性的度量,但计算CLCS时间代价很高,最早的CLCS算法的时间复杂度为O(rn4),目前,最快的CLCS算法的时间复杂性为O(rn2).运用对偶原理将带约束最长公共子序列问题转换为带约束最小覆盖集问题,并建立带权的ref树结构,构造包含约束序列的约束覆盖子集,约简带约束覆盖子集并从中搜索关键路径,再通过关键路径构造CLCS,该算法将算法时间复杂度提升到O(nlogn+(q+r)L),r是约束序列的长度,q是两序列序偶的个数,L是两序列的最长公共子序列(LCS)长度.

关键词：带约束最长公共子序列、快速算法、对偶算法

所属期刊栏目：45

分类号：TP301(计算技术、计算机技术)

资助基金：国家自然科学基金60573024;江苏省自然科学基金BK2009393

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

页数：共9页

页码：576-584