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

作者：业宁; 朱大铭; 张倩倩; 沈丽容

来源：南京大学学报(自然科学版), 2009, (05): 576-584.

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

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

• 出版日期2009-9-30
• 单位山东大学; 南京林业大学