| 带约束最长公共子序列快速算法 |
| |
| 引用本文： | 业宁,朱大铭,张倩倩,沈丽容.带约束最长公共子序列快速算法[J].南京大学学报(自然科学版),2009(5). |
| |
| 作者姓名： | 业宁 朱大铭 张倩倩 沈丽容 |
| |
| 作者单位： | 山东大学计算机科学与技术学院;南京林业大学信息科学技术学院; |
| |
| 基金项目： | 国家自然科学基金(60573024);;江苏省自然科学基金(BK2009393) |
| |
| 摘 要： | 带约束最长公共子序列(CLCS)问题有很深的生物学应用背景,常被用来表示同源基因序列相似性的度量,但计算CLCS时间代价很高,最早的CLCS算法的时间复杂度为O(rn4),目前,最快的CLCS算法的时间复杂性为O(rn2).运用对偶原理将带约束最长公共子序列问题转换为带约束最小覆盖集问题,并建立带权的ref树结构,构造包含约束序列的约束覆盖子集,约简带约束覆盖子集并从中搜索关键路径,再通过关键路径构造CLCS,该算法将算法时间复杂度提升到O(nlogn+(q+r)L),r是约束序列的长度,q是两序列序偶的个数,L是两序列的最长公共子序列(LCS)长度.
|
| 关 键 词： | 带约束最长公共子序列 快速算法 对偶算法 |
A fast algorithm of constrained longest common subsequence |
| |
| Ye Ning,Zhu Da-Ming,Zhang Qian-Qian,Shen Li-Rong.A fast algorithm of constrained longest common subsequence[J].Journal of Nanjing University: Nat Sci Ed,2009(5). |
| |
| Authors: | Ye Ning Zhu Da-Ming Zhang Qian-Qian Shen Li-Rong |
| |
| Institution: | 1.School of Computer Science and Technology;Shandong University;Jinan;250061;China;2.School of Information and Technology;Nanjing Forestry University;Nanjing;210037;China |
| |
| 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(rn4),while presently the time complexity of the fastest CLCS algorithm is O(rn2).We use the principle of primal-dual which will convert CLCS to the constrained minimal covering se... |
| |
| Keywords: | constrained longest common subsequence fast algorithm primal-dual |
| 本文献已被 CNKI 等数据库收录！ |
|
