论文部分内容阅读
带约束最长公共子序列（CLCS）问题有很深的生物学应用背景，常被用来表示同源基因序列相似性的度量，但计算CLCS时间代价很高，最早的CLCS算法的时间复杂度为O（rn^4），目前，最快的CLCS算法的时间复杂性为O（rn^2）．运用对偶原理将带约束最长公共子序列问题转换为带约束最小覆盖集问题，并建立带权的ref树结构，构造包含约束序列的约束覆盖子集，约简带约束覆盖子集并从中搜索关键路径，再通过关键路径构造CLCS，该算法将算法时间复杂度提升到O（nlogn＋（q＋r）L），r是约束序列的长度，q是两序列序