基于动态规划的快速序列比对算法

被引：8

作者：

唐玉荣

汪懋华

机构：

[1] 中国农业大学生物学院

[2] 中国农业大学现代精细农业系统集成研究教育部重点实验室

来源：

生物数学学报 | 2005年 / 02期

关键词：

算法; 序列比对; 动态规划;

D O I：

暂无

中图分类号：

O221 [规划论（数学规划）];

学科分类号：

摘要：

序列比对算法是生物信息学中重要的研究方向之一,而动态规划法是序列比对算法中最有效最基本的方法.由于原有的基本动态规划方法时间和空间复杂度大,不适合实际的生物序列比对,因此本文在分析介绍几种相关动态规划算法的基础上,提出了一种基于动态规划的快速序列比对算法UKKFA.实验结果表明,该算法有效地降低了时间复杂度,具有一定的实用性.

引用

页码：207 / 212

页数：6

共 4 条

[1] 存储约束条件下的序列联配算法 [J].

李昭 ;

杨琪 ;

祝明发 .

微电子学与计算机, 2002, (06) :1-5

[2]

On approximate string matching. Ukkonen E. Found Comput Theory . 1983

[3]

A linear space algorithm for conputing maximal common subsequences. Hirschberg D. Communications of the ACM . 1975

[4]

A general method applicable to the search for similarities in the amino acid sequences of two proteins. Needleman S,Wunsch C. Journal of Molecular Biology . 1970

← 1 →