基于遗传算法与模拟退火算法在多重DNA序列比对中的应用研究 优先出版.pdf

《基于遗传算法与模拟退火算法在多重DNA序列比对中的应用研究 优先出版.pdf》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第24卷第2期海南热带海洋学院学报Vol．24No．22017年4月JournalofHainanTropicalOceanUniversityApr．2017引用本文格式:闫磊，马健，董辉，等．基于遗传算法与模拟退火算法在多重DNA序列比对中的应用研究［J］．海南热带海洋学院学报，2017，24(2):64－69．基于遗传算法与模拟退火算法在多重DNA序列比对中的应用研究闫磊，马健，董辉，高梦(亳州职业技术学院信息工程系，安徽亳州236800)摘要:序列比对是将蛋白质中的基因或氨基酸进行对齐的动作，目的是要找出两序列的相似程度，而多重序列比对则是同时比对多个D

2、NA或蛋白质序列，找出此序列群组中最佳的比对结果.本研究结合遗传算法及模拟退火算法，先利用遗传算法优化种群的概念，随着世代演进逐渐产生近似最佳解，再利用模拟退火算法进行小区块内的比对修正.实验结果显示，利用遗传算法与模拟退火算法的结合，使得遗传算法在跳脱局部最佳解的时候能有更大空间移动，而且也让模拟退火算法能有效解决经由遗传算法初步比对之后所产生的不良区域.两种算法结合的序列比对结果比任何单一算法的结果好，因此可以提升整体比对效果，将来能够为生物学家在判断未知序列功能时提供适当的帮助.关键词:序列比对;多重序列比对;遗传算法;模拟退火算法中图分类号:TP18文献

3、标识码:A文章编号:2096－3122(2017)02－0064－06DOI:10．13307/j．issn．2096－3122．2017．02．130引言对生物学家而言，探索蛋白质的序列对于细胞功能的影响、推测未知蛋白序列的功能、或比较不同的两个生物中的相似基因之间的差异时，序列的比对都成为不可或缺的一项重要技术.因此近年来在生物学中，序列比对成为一项重要的技术之一，对于蛋白质序列的比对、蛋白质结构的预测、DNA及MＲNA的比对以及利用蛋白质序列搜寻DNA序列等方面都具有广泛的应用.而由序列比对所拓展的多重序列比对，对于生物学家而言更是一项困难且具挑战性的任务

4、，因为多重序列比对其计所需的时间复杂度将随着序列数量的增加而呈指数性的成长，所以现在有许多算法应用在此领域.对于只有两条序列的比对，利用动态程序规划可以达到最好的结果.然而利用动态程序规划算法虽［1］然能够得到较好的结果，但在序列数量以及长度都增加的同时，对于计算机的计算资源会急剧的提高．此外，过去的研究也有利用遗传算法结合动态程序规划的方式进行比对，但仍有许多算法在处理这种问题上具有其优点，如模拟退火算法在处理解空间较小的问题上具有良好的表现.本研究使用没传算法及模拟退火算法所结合的算法来进行比对，并且对遗传算法以及模拟退火算法分别进行比对结果来比较，最后将模

5、拟退火算法的概念引入遗传算法中进行比对，使得遗传算法在脱良局部最佳解的时候能有更大空间［2］的移动，因此达到对比分数更高的序列比对.本研究利用了遗传算法及模拟退火算法，先进行两者应用于多重序列比对的结果，再利用遗传算法输出的结果作为模拟退火算法所需序列的基础输入序列进行比对的调整，经过两种算法的运算之后，希望能够与过去专家所提出的研究能够达到相近的结果，并且与动态程序规划进行比对的结果能够相近.收稿日期:2017－02－15基金项目:安徽省教育厅自然科学研究重点课题(KJ2016A493);安徽省亳州市产业创新团队科研项目(亳组［2015］20号－2);亳州职业

6、技术学院院级课题(BYK1511)作者简介:闫磊(1984－)，男，回族，安徽亳州人，亳州职业技术学院信息工程系助教，研究方向为数据挖掘、人工智能方向.·64·闫磊等:基于遗传算法与模拟退火算法在多重DNA序列比对中的应用研究2017年第2期1序列比对生物序列比对是一种比较两个或多个DNA、ＲNA或蛋白质序列，并尝试找出序列中的一连串或单一的对应字符的方法.最常见是将两条序列并排成两行，将序列中相同或相似的区段置于相同的字段，而无法比对的字符则在各自的序列中利用插入间隔或产生错误.在最佳比对的情况下，插入间隔(gap)“－”可以让序列具有更好的比对结果，而间隔的

7、出现就表示在［3］序列演化的过程中发生了删除或插入的情况.如图1(a)所示，两个DNA序列的比对在还没插入“－”之前，序列A与序列B具有许多的比对错误的部分，在图1(b)的部分即由插入了“－”而使得整组序列达到比较好的比对结图1未插入间隔于插入间隔序列比对的比较果.1.1全局比对全局比对是尝试比对在序列中的每一个元素，即其比对是从序列的最前端到序列的最末端，目的是要找出两序列的相似程度.Needleman和Wunsch于1970年所提出的动态程序规划是一种序列全局比对的［4］算法，且是首次将动态程序规划应用于序列比对领域上所开发出的一种方法，如图2(a)为全局比

8、对.1.2区域比对区域比