自适应蚁群算法在DNA序列比对中的应用

文档编号:TX052        文档字数:13247,页数:25

[摘要]
本文对标准蚁群算法、MMAS蚁群算法、自适应蚁群算法做了较详细系统的总结，其中主要讨论了自适应蚁群算法在DNA序列比对中的应用，主要的过程是：首先，我们设一个计分函数和一个得分策略，在任意给出一对DNA序列，建立一个序列比对矩阵。现由4只蚂蚁从左上角向右下角移动，并且最终到达右下角，那么这4只蚂蚁随意走出4条路径，根据4条路径得出4对等长的比对，再依照计分函数分别计算出4条路径的比对得分，再由5.3式进一步验证4条路径的平均得分值，取其中得分最高（即最优路径）路径；进行第二次信息素增量的调整，方法是根据蚂蚁所走过的方向和该方向上得分比例计算出来的，信息素的变化量利用矩阵来存储，那么下一次蚂蚁所选的路径就要根据以前在各条路径上的信息素浓度总和的大小选择移动方向，最终经过有限次迭代，蚂蚁就会找到一条最优路径，也就是一条与原来DNA最相似的DNA链。
[关键词] 标准蚁群算法，MMAS算法，自适应蚁群算法，DNA序列比对

Abstract：
Ant-colony algorithm, MMAS(Max-Min Ant-colony Algorithm) and adaptive ant-colony algorithm are discussed in this paper. DNA sequence alignment is one of important tools in bioinformatics research. We discuss the process that adaptive ant-colony algorithm is applied in sequence alignment mainly. First, we give a scoring function and score points the strategy, a pair of DNA sequence is generated randomly and create sequence alignment matrix. 4 ants move from on left angular orientation to right under angle and finally arrives the right under angle, Hence 4-ways are obtained and 4 sequence alignment of same length is obtained too. According to scoring function, we calculate these scoring and max-value of these sequence alignment is the best route.; Second, information element are adjusted by its increase and are stored in information element matrix. Finally, The route that ant select is according with information adjustment. Through limiting iterative times, A best route is selected and get the result that these two DNA chains are same.
Keywords：Standard Ant-colony algorithm, (MMAS) Max-Min Ant-colony Algorithm, adaptive ant-colony algorithm, DNA sequence alignment

目录
1.引言  3 
2 标准蚁群算法  3
2.1标准蚁群算法的原理  3
2.2标准蚁群算法的实现  5
2.3标准蚁群系统的优缺点  7 
2.3.1基本蚁群算法的优点  8
2.3.2基本蚁群算法的缺点  9
3.标准蚁群算法和MMAS(max-min ant system)蚁群算法  8 
3.1MMAS的概念  8
3.2AS与MMAS的对比  8
3.3MMAS和AS的区别  8
3.4最好、最坏路径信息素全局更新策略  13
3.5MMAS蚁群算法的特点  10
4.自适应蚁群算法  10 
4.1.自适应蚁群算法的概述  11
4.2.自适应的信息更新策略  11
4.2.1引题  12
4.2.2改进的蚁群算法实现过程  12
4.2.3自适应蚁群算法的稳定性和收敛性  13
5.自适应蚁群算法在DNA中的应用  14
5.1序列比对  14
5.2自适应蚁群算法和DNA的联系  15
6.结束语  22
致谢 23 
参考文献  24 

相关论文