南京大学学报（自然科学版）2009，Vol.45Issue(5)：576-584,9.
带约束最长公共子序列快速算法
A fast algorithm of constrained longest common subsequence
摘要
Abstract
The constrained longest common subsequence problem has deep background applications in biology. It is often used to express the measurement of similarity in homologous gene sequences, but the time complexity on computation of constrained longest common subsequence(CLCS) is high. The time complexity of the original CLCS algorithm is O(rn~4 ), while presently the time complexity of the fastest CLCS algorithm is O(rn~2). We use the principle of primal-dual which will convert CLCS to the constrained minimal covering set problem, and then establish ref tree structure with weight, structure constrained covering subset which contains the constrained sequence. We also reduce constrained covering subset and search critical paths from it,and finally structure CLCS through critical paths. The time complexity of this algorithm will be upgraded to O(nlogn+(q + r)L), where the r is length of the constrained sequence, q is the number of ordered pairs of the two given sequences and L is the longest common subsequence(LCS) length of the two given sequences.关键词
带约束最长公共子序列/快速算法/对偶算法Key words
constrained longest common subsequence/ fast algorithm/ primal-dual分类
信息技术与安全科学引用本文复制引用
业宁,朱大铭,张倩倩,沈丽容..带约束最长公共子序列快速算法[J].南京大学学报（自然科学版）,2009,45(5):576-584,9.基金项目
国家自然科学基金(60573024),江苏省自然科学基金(BK2009393) （60573024）
