自適應蟻群算法在DNA序列比對中的應用

電子通信論文編號:TX052        論文字數:13247,頁數:25

目錄
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 

[摘要]
本文對標準蟻群算法、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