双序列比对算法的研究与改进

李丹

摘要

随着生物信息学的飞速发展，生物数据海量激增，序列比对作为生物学的计算核心，在其精确性和敏捷性方面都提出了更高的要求。在研究传统序列比对算法的基础上，本文提出一种改进的基于动态规划的全局双序列比对算法，有效降低了时间复杂度和空间复杂度。

【关键词】生物信息学双序列比对 动态规划

1引言

生物信息学（Bioinformatics）是生物学与计算机科学及应用数学等学科相互交叉形成的一门新学科，它通过对生物学实验数据的获取、加工、存储、检索与分析，揭示这些资料所蕴含的生物学意义。序列比对是生物学计算的核心，是生物学中最基本、最重要的方法。序列比对又叫序列联配，提供了一个有力的途径来试图提示两个序列之间是否具有足够的相似性（Similarity）。最常见的比对是蛋白质序列之间或核酸序列之间的两两比对，通过比较两个序列之间的相似性区域，寻找二者可能的分子进化关系。

序列比对的分类，从同时进行比对的序列个数方面，分为双序列比对（Pair-wise Sequence Alignment）和多序列比对（Multiple Sequence Alinment）；从比对范围考虑可分为全局比对Global Alignment）和局部比对（Local Alignment）。

2动态规划思想

动态规划（Dynamic Programming）是运筹学的一个分支，是求解决策过程（Decision Process）最优化的数学方法。把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法。基于动态规划的全局双序列比对算法思想：首先，计算两个序列的相似分值，存入一个得分矩阵中，运用迭代法；其次，寻找最优比对序列，运用回溯法。

3一種改进的基于动态规划的全局双序列比对算法

算法改进之处，在得分矩阵的计算过程中只存储前一行和当前行，并记录得分值的来源。优点是节省存储空间，由改进前的O（nxn），降为O（n），且在得分矩阵计算过程中同时记录元素的来源，最佳比对路径的获得不需要回溯。

4结论

随着生物学数据的海量增加，对序列比对算法的空间性和时间性提出更高的要求，如何二者兼得，将成为生物信息学中一个非常重要且具有挑战性的研究课题。本文提出一种改进的基于动态规划的全局双序列比对算法，在存储空间和运算速度两方面均有质的提高。随着研究的深入，如何建立合理的相似性度量准则，如何提高准确率和运算速度，新的序列比对算法必将不断增加。

参考文献

[1]罗超权，余新炳，昌才.英汉生物化学与分子医学词典[M].北京：中国医药科技出版社，2005.

[2]李镍岚，李其申，张永.一种基于动态规划的全局双序列比对优化算法[J].电脑知识与技术（学术交流），2007，1（06）：124-126.

[3]T.K.Attwood，D.J.Parry-Smith.生物信息学概论[M].罗静初译.北京：北京大学出版社，1999.

[4]Bel1man R，Ka1aba R.Dynamic Programming and Statistical Communication Theory[J].Proceedings of the National Academy of Sciences of the United States of America，1957，43（08）：749.endprint