基于蟻群算法與中心比對算法的多序列比對研究

王彩蕓,蔡樂才

摘 要:多序列比對問題是生物信息學中一個非常重要且具挑戰性的課題。為了克服以往算法應用于多序列比對時所遇到的比對序列數受限制以及比對尋優速度慢的缺點,提出一種基于蟻群算法與中心比對算法相結合的新求解算法,給出了具體的算法設計。該算法充分發揮了蟻群算法和中心比對算法的優越性,可提高求解MSA 問題的計算精度和計算速度,同時較好地解決了群體的多樣性和收斂深度的矛盾。

關鍵詞:多重序列比對;蟻群算法;中心比對算法;算法設計

中圖分類號:TP301文獻標識碼:A

文章編號:1004-373X(2009)12-085-03

New Algorithm Based on Ant Colony Algorithm and Consensus Alignment

for Multiple Sequence Alignment

WANG Caiyun,CAI Lecai

(Sichuan University of Science and Engineering,Zigong,643000,China)

Abstract:Multiple sequencealignment is a most important and challenging task in bioinformatics.In order to solve the problems of both thealignment sequences number limitation and time-consuming which manyalignments can encounter in multiple sequencealignment,a newalignment based on ant colonyalignment and consensusalignment and concrete algorithm design are proposed.This newalignment not only sufficiently exerts the advantages of the twoalignments,but also improves the computing precision and speed,and which solves the contradiction between the diversity of population and the convergence speed.

Keywords:multiple sequencealignment;ant colonyalignment;consensusalignment;algorithm design

0 引 言

多序列比對(Multiple Sequence Alignment,MSA)是生物信息學中最重要、也是最有挑戰性的任務之一。通過多序列比對,可以預測新序列的結構和功能,可以分析序列之間的同源關系,以及進行系統發育分析。 多序列比對是一個具有極高計算復雜度的組合優化問題[1]。

兩序列對比目前應用最廣的就是動態規劃方法[2,3],求得最優解,但多序列比對問題的求解至今仍然是生物信息學中尚未解決的難題,已經證明多序列比對問題是一個NP 完全問題[4]。從問題提出到現在,研究者們就多序列對比方法進行了有益的探索,其中比較常見的多序列比對方法有Pileup 算法、Clustalw算法[5]、Carrillo-Lipman算法[6],還有DCA算法[7]。但這些算法的主要缺點是不僅搜索速度慢,運行過程中還占用過多的內存[8];進化算法主要有模擬退火算法(SA)、遺傳算法(GA) 、免疫算法和蟻群算法(ACO)等,它們的主要思想都是通過反復迭代來逐步搜索到最優解[9]。上述這些算法雖然在求解多序列比對時得到了一些通用的、高效的序列,但是它們都不能有效地得到精確的解。這里在遺傳算法的基礎上通過綜合運用蟻群算法與中心比對算法相結合的優勢來求解多序列比對。

1 多序列比對的描述

多序列比對已經接近序列之間的朦朧區。但盡管如此,序列之間仍會共有由保守殘基形成的局部區域,即序列模體。序列模體往往是蛋白質分子的重要功能位點所在,尋找這些序列模體,并用它們構建蛋白質二級數據庫是多序列比對的重要任務之一。因此可以說,多序列比對的目的從序列相似性轉移到了功能相似性。

多序列比對是目前為止在生物信息學中最常用的方法。多序列比對有著廣泛的應用,其中包括:尋找蛋白質家族中的保守區域,蛋白質的聚類、分類,點突變檢測,推斷進化關系和構建系統發育樹,幫助預測蛋白質結構等。

多序列比對的定義:給定κ條蛋白質序列S={S1,S2,…,Sκ},尋找最優比對,也就是說,尋找{S1′,S2′,…,Sκ′},使得滿足如下條件:

(1) Si′是Si通過插入空位得到的,其相對位置保持不變;

(2) 對任意的i和j,有|Si′|=|Sj′|,即比對后的序列具有相同的長度;

(3) 對于所有的i和j,使得∑i∑jsim(Si′,Sj′)最大,或者∑i∑jcost(Si′,Sj′)最小。其中,sim(X,Y)是序列X和序列Y的比對相似性函數;cost(X,Y)是序列X和序列Y的比對罰分函數。

多重序列的比對B用一個二維矩陣表示。矩陣中的每一行對應于一個序列這個序列可能只是原來序列的一個簡單復制,也可能在保持原序列中各殘基相對順序不變的情況下,插入若干個空位而形成的一個新序列。矩陣中不允許某一行同時為空位,因此矩陣的行數等于序列的數目。多重序列比對的目的就是對多個序列通過插入、刪除等操作將之排列以達到相同的長度,同時使得矩陣中同列匹配的字符個數盡可能多,不匹配字符和空位個數盡可能少。對于每個矩陣都會有一個相應的適合度值,作為是否在遺傳進化中繼續生存產生下一代的依據。這里采用通用的SP 模型對比對的質量進行評估[8]。比對B的適應度函數為:

sp-score(j)=∑N-1i=1∑Nk=i+1p(cij,ckj)

式中:L為比對中各個序列的長度;第i條序列中第j個字符為cij(1≤j≤L );p(cij,ckj)為字符cij及ckj的記分。

2 蟻群算法和中心比對算法

蟻群算法是近來出現的一種新型的模擬進化算法,它由意大利學者M.Dorigo等人首先提出來[10]。蟻群算法實際上是模擬螞蟻集群覓食規律而設計出的一種算法,螞蟻在尋找事物的過程中會在其經過的路徑上留下一種稱為“信息素”的物質;其后經過該路徑的螞蟻會利用這些“信息素”經驗來判斷是否選擇這條路徑,并留下新的信息素以給后來的螞蟻提供信息。即在個體尋優的過程中,每一只螞蟻會利用這些信息素的濃度來矯正自己的行為,并把經驗提供給后來的螞蟻[11]。路徑上的信息素濃度越高,該路徑被螞蟻選中的概率就越大。在開始時,螞蟻被隨機放置在路徑結點上,并向可行的臨近結點移動,信息素被存儲在路徑上。同時引入信息素揮發機制,即信息素會隨時間的推移而逐漸揮發甚至消失。這樣可以避免局部收斂的現象,還可以增大搜索空間。

中心比對算法是一種求解MSA 問題的快速啟發式方法,它基于一個固定序列與所有其他序列的配對比對而建立的,這個固定序列有一中心,使用一種稱為“一旦為空格,始終為空格”的技術將這些配對比對向中心匯集。即在中心與其他序列的優化比對過程中,會不斷往中心序列中加入空格以適配比對,且決不移出已經加入的空格,也就是空格一旦加入到中心序列,就始終留在中心序列中,直到所有其它序列與中心序列優化比對完。算法描述如下:

步驟1:對于一組含有κ條序列的集合Ω,首先找出序列St,St∈Ω,使得∑i≠tscore(Si,St)的值最小,令A={St}。

步驟2:逐次添加Si∈Ω-{St}到A中,使Si與St的B比對值最小,并假設S1,S2,…,Si-1已經添加到A中。由于在分別與St進行比對的過程中需要加入一些空格, 故此時A ={S1′,S2′,…,Si-1′,St′}。按照兩條序列比對的動態規劃算法比較St′和Si,分別產生新的序列St″和Si′,再按照St″中添加空格的位置調節序列{S1′,S2′,…,Si-1′}成{S1″,S2″,…,Si-1″}, 并用St″替換St′,最后得到的比對即中心比對。

3 用蟻群中心比對算法相結合求解MSA

該算法主要是模擬自然界演化的周期性的特點。自然界的演化往往是進化和退化交替進行的,表現出周期性的特點。它是一個循環往復的過程,但不是一種簡單的回復。這里所提出的算法就是使群體的進化有周期性,用精英保留策略使得群體不發生退化,保持進化的趨勢特點,突變算子有可能使群體發生退化的特點。算法對一個進化周期的設計是:首先將序列進行編碼,接下來使用遺傳算子(交叉算子、變異算子、選擇算子)對群體進行進化,當群體經過一定的進化代數后,不是直接進入下一個循環,而是先利用“滑動窗口”[10]檢測出不匹配的區域,用蟻群算法“改善”這些區域:讓螞蟻逐漸遍歷比對中每個序列的一個殘基,直至全部殘基被遍歷完結束本次循環;經過一定的代數進化后,僅保留最優解;對最優個體所對應的序列組進行中心比對,比對后的序列組對應的染色體個體如果更優則取代最優解,重新生成其余個體,進入下一個周期。這種策略并非退化,而是盡快擺脫進化遲鈍狀態,開始一個新的進化周期。算法就是通過若干個這樣的進化周期,最后找到最優解的。

具體算法設計如下:

Procedure ant-consensusalignment

begin

對序列進行編碼初始化;計算P 中個體的適應值;

optimal-indivi←P 中最優的個體;

gen←0;

while gen

begin //一個進化周期開始

k←0;

while k

begin

使用遺傳算子對初始化群體進化;檢測不匹配區域;

用蟻群算法改善這些區域;

k←k + 1;

end;

//保留最優個體

if P 中最優個體好于optimal-indivi then optimal-indivi←P 中的最優個體

對最優個體所對應的序列組進行中心比對,比對后的序列組對應的染色體個體如果更優則取代最優解;

//在進入下一個進化周期前進行重組

S←{隨機生成N-1個體};//N為種群規模

P←S+ {個體optimal-indivi};

gen←gen+1;

end;

end;

4 結 語

這里提出的基于蟻群算法與中心比對算法相結合的對序列比對算法有效地解決了局部收斂的問題,加強了算法尋求最優解的能力。利用該算法求解多序列比對問題不但減少了計算時間,而且改善了所求解的質量。因此,用一種進化算法協助另一種進化算法來使用往往能取得更為理想的結果,且在效率上更具優越性。

參考文獻

[1][美]Andreas D,Baxevents,B F Francis Ouellette.生物信息學:基因和蛋白質分析的實用指南[M].李衍達,孫之榮,譯.北京:清華大學出版社,2000.

[2]Thompson J D,Higgins D G,Gibson T J.CLUSTALW:Improving the Sensitivity of Progressive Multiple Sequence Alignment through Sequence Weighting,Position-Specific Gap Penalties and Weight Matrix Choice [J].Nucl.Acids Res.,1994,22:4 673-4 680.

[3]塞圖寶,梅丹尼斯.計算分子生物學導論[M].朱浩,譯.北京:科學出版社,2003.

[4]Jiang T,Wang L.On the Complexity of Multiple Sequence Alignment [J].Comput.Biol.,1994:337-378.

[5]Andrada M A,Sander.Bioinformatics from Genome Data to Biological Knowledge[J].Current Opinion Biotechnol,1997,6:675-683.

[6]Carrillo H,Lipman D J.The Multiple Sequence Alignment Problem in Biology[J].SIAM.Appl.Math.,1998:1 073-1 082.

[7]Stoye J,Moulton V,Dress A W.DCA:An Efficient Implementation of Thedivide-and-Conquer Approach to Si-multaneous Multiple Sequence Alignment[J].Comput.Applic.Biosci.,1997,6:625-626.

[8]張靜樂,王世卿,王樂.具有新型遺傳特征的蟻群算法[J].微計算機信息,2006,22(5):257-260.

[9]Chellapilla K,Fogel G B.Multiple Sequence Alignment Using Evolutionary Programming [J].Proc.IEEE Congress Evol.Comput.,1999:445-452.

[10]Dorigo M,Maniezzo V,Colorni A.Ant System:Optimization by a Colony of Coorperating Agents[J].IEEE Trans.on Systems,Man and Cybernetics,1996,26(1):29-41.

[11]Dorigo M,Caro G D.Ant Colony Optimization:A New Meta-Heuristic[J].Proc.Congress Evol.Comput.,1999:1 470-1 477.

[12]Krogh A.An Introduction to Hidden Markov Models for Biological Sequences[A].Computational Methods in Molecular Biology[C].Elsevier,1998:45-63.

[13]Lee L Z,Lee C Y,Su S F.An Immunity-based Ant Colony Optimization Algorithm for Solving Weapon-Target Assignment Problem[J].Appl.Soft Comput.2002:39-47.

[14]Wang L,Jiang T.On the Complexity of Multiple Sequence Alignment[J].Comput.Biol.,1994,1(4):337-348.

[15]胡桂武,鄭啟倫,彭宏.求解MSA 問題的新型單親遺傳算法[J].計算機工程與應用,2004,40(8):5-7,53.

[16]Lawrence C,Altschul S F,Boguski B,et al.Detecting Subtle Sequence Signals:A Gibbs Sampling Strategy for Multiple Alignment[J].Science,1993:208-214.

[17]Gen M,Cheng R.Genetic Algorithms and Engineering Design[M].John Wiley & Sons Inc.,1997.