基因序列相似程度的LCS算法研究

被引：30

作者：

王映龙 ^{[1
]}

杨炳儒 ^{[1
]}

宋泽锋 ^{[1
]}

陈卓 ^{[1
]}

唐建军 ^{[2
]}

机构：

[1] 北京科技大学信息工程学院

[2] 江西农业大学计算机与信息工程学院

来源：

计算机工程与应用 | 2007年 / 31期

关键词：

最长公共子序列; 穷举法; 基因序列排比;

D O I：

暂无

中图分类号：

TP301.6 [算法理论];

学科分类号：

080201 [机械制造及其自动化];

摘要：

首先重新审视了采用穷举法求解LCS问题的困难,以及对应的优点;随后针对穷举法的优点进行了两类优化;最后给出了算法实现的图示以及算法的结论。通过实验证明,算法的效率较传统的动态规划的LCS算法有了很大的提升。

引用

收藏

页码：45 / 47

页数：3

相关论文

共 3 条

[1]

Exact and approximation algorithms for sorting by reversals; with application to genome rearrangement[J] J. Kececioglu;D. Sankoff Algorithmica 1995,

[2]

The longest common subsequence problem revisited[J] A. Apostolico;C. Guerra Algorithmica 1987,

[3]

A fast algorithm for computing longest common subsequences[J] James W. Hunt;Thomas G. Szymanski Communications of the ACM 1977,