摘要
序列比对算法是生物信息学中重要的研究方向之一,而动态规划法是序列比对算法中最有效最基本的方法.由于原有的基本动态规划方法时间和空间复杂度大,不适合实际的生物序列比对,因此本文在分析介绍几种相关动态规划算法的基础上,提出了一种基于动态规划的快速序列比对算法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.
出处
《生物数学学报》
CSCD
北大核心
2005年第2期207-212,共6页
Journal of Biomathematics
关键词
算法
序列比对
动态规划
Algorithm
Sequence alignment
Dynamic programming
