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

王彩蕓,蔡樂(lè)才

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

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

中圖分類(lèi)號(hào):TP301文獻(xiàn)標(biāo)識(shí)碼:A

文章編號(hào):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 引 言

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

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

1 多序列比對(duì)的描述

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

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

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

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

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

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

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

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

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

2 蟻群算法和中心比對(duì)算法

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

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

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

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

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

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

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

Procedure ant-consensusalignment

begin

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

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

gen←0;

while gen

begin //一個(gè)進(jìn)化周期開(kāi)始

k←0;

while k

begin

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

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

k←k + 1;

end;

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

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

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

//在進(jìn)入下一個(gè)進(jìn)化周期前進(jìn)行重組

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

P←S+ {個(gè)體optimal-indivi};

gen←gen+1;

end;

end;

4 結(jié) 語(yǔ)

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

參考文獻(xiàn)

[1][美]Andreas D,Baxevents,B F Francis Ouellette.生物信息學(xué):基因和蛋白質(zhì)分析的實(shí)用指南[M].李衍達(dá),孫之榮,譯.北京:清華大學(xué)出版社,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]塞圖寶,梅丹尼斯.計(jì)算分子生物學(xué)導(dǎo)論[M].朱浩,譯.北京:科學(xué)出版社,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]張靜樂(lè),王世卿,王樂(lè).具有新型遺傳特征的蟻群算法[J].微計(jì)算機(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 問(wèn)題的新型單親遺傳算法[J].計(jì)算機(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.