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

• 作者: 业宁 张倩倩 朱大铭 沈丽容
• 来源期刊: 南京大学学报（自然科学版）
• 学科: 工学
• 关键词: 带约束最长公共子序列 快速算法 对偶算法
• 年，卷（期）: 2009,（5）
• 所属期刊栏目: 数据挖掘及应用专栏
• 页码范围: 576-584
• 页数: 9页
• 分类号: TP301
• 字数: 5797字
• 语种: 中文
• DOI: 10.3321/j.issn:0469-5097.2009.05.003

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	朱大铭	山东大学计算机科学与技术学院	50	263	11.0	13.0
2	业宁	山东大学计算机科学与技术学院	83	805	16.0	24.0
4	沈丽容	南京林业大学信息科学技术学院	21	113	5.0	10.0
7	张倩倩	南京林业大学信息科学技术学院	6	41	2.0	6.0