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

Fast Sequence Alignment Algorithm Based on Dynamic Programming

作　　者：唐玉荣[1] 汪懋华[2] 

机构地区：[1]中国农业大学生物学院,北京100094 [2]中国农业大学现代精细农业系统集成研究教育部重点实验室,北京100083

出　　处：《生物数学学报》2005年第2期207-212,共6页Journal of Biomathematics

摘　　要：序列比对算法是生物信息学中重要的研究方向之一,而动态规划法是序列比对算法中最有效最基本的方法.由于原有的基本动态规划方法时间和空间复杂度大,不适合实际的生物序列比对,因此本文在分析介绍几种相关动态规划算法的基础上,提出了一种基于动态规划的快速序列比对算法UKK_FA.实验结果表明,该算法有效地降低了时间复杂度,具有一定的实用性.Sequence alignment algorithm is an important research direction in Bioinfor-matics. Dynamic programming is the most efficient and basic method in sequence alignment algorithm. The original dynamic programming method is not fit for practical biology sequence alignment because it requires vast time and space. So this paper presents a fast sequence alignment algorithm based on dynamic programming (UKK_FA) after analyzing several interrelated dynamic programming algorithms. The experimental result shows that the algorithm can reduce time complexity effectively and has definite practicability.

关 键 词：算法 序列比对 动态规划 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]