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

王彩蕓,蔡樂才

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

關(guān)鍵詞:多重序列比對;蟻群算法;中心比對算法;算法設(shè)計

中圖分類號: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)是生物信息學中最重要、也是最有挑戰(zhàn)性的任務(wù)之一。通過多序列比對,可以預(yù)測新序列的結(jié)構(gòu)和功能,可以分析序列之間的同源關(guān)系,以及進行系統(tǒng)發(fā)育分析。 多序列比對是一個具有極高計算復(fù)雜度的組合優(yōu)化問題[1]。

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

1 多序列比對的描述

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

多序列比對是目前為止在生物信息學中最常用的方法。多序列比對有著廣泛的應(yīng)用,其中包括:尋找蛋白質(zhì)家族中的保守區(qū)域,蛋白質(zhì)的聚類、分類,點突變檢測,推斷進化關(guān)系和構(gòu)建系統(tǒng)發(fā)育樹,幫助預(yù)測蛋白質(zhì)結(jié)構(gòu)等。

多序列比對的定義:給定κ條蛋白質(zhì)序列S={S1,S2,…,Sκ},尋找最優(yōu)比對,也就是說,尋找{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的比對相似性函數(shù);cost(X,Y)是序列X和序列Y的比對罰分函數(shù)。

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

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

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

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

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

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

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

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

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

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

具體算法設(shè)計如下:

Procedure ant-consensusalignment

begin

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

optimal-indivi←P 中最優(yōu)的個體;

gen←0;

while gen

begin //一個進化周期開始

k←0;

while k

begin

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

用蟻群算法改善這些區(qū)域;

k←k + 1;

end;

//保留最優(yōu)個體

if P 中最優(yōu)個體好于optimal-indivi then optimal-indivi←P 中的最優(yōu)個體

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

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

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

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

gen←gen+1;

end;

end;

4 結(jié) 語

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

參考文獻

[1][美]Andreas D,Baxevents,B F Francis Ouellette.生物信息學:基因和蛋白質(zhì)分析的實用指南[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]塞圖寶,梅丹尼斯.計算分子生物學導(dǎo)論[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].計算機工程與應(yīng)用,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.