求解多重序列比對問題的蟻群算法

摘要：多重序列比對是生物信息學(xué)特別是生物序列分析中一個重要的基本操作。提出求解多重序列比對問題的蟻群算法，利用人工螞蟻逐個選擇各個序列中的字符進(jìn)行配對。在算法中，螞蟻根據(jù)信息素、字符匹配得分以及位置偏差等信息決定選擇各序列中字符的概率，通過信息素的更新與調(diào)節(jié)相結(jié)合的策略較為有效地解決了局部收斂的問題，加強了算法尋求全局最優(yōu)解的能力。另外在該算法的基礎(chǔ)上，提出了基于分治策略的多序列比對蟻群求解算法，不但減少了原算法的計算時間，而且顯著改善了算法所求得的解的質(zhì)量。

關(guān)鍵詞：生物信息學(xué)； 多重序列比對；蟻群算法； 分治策略

中圖法分類號：TP37；O141.3文獻(xiàn)標(biāo)識碼：A

文章編號：1001－3695(2007)01－0025－06

1引言

多序列比對是生物信息學(xué)及計算分子生物學(xué)中的一個重要問題，是基因識別、蛋白質(zhì)結(jié)構(gòu)預(yù)測、生物進(jìn)化樹的構(gòu)建、基因組信息分析等問題中用到的一個基本操作。通過序列比對可以探索生物序列中所包含的功能、結(jié)構(gòu)和進(jìn)化信息。在生物信息學(xué)中，最常見的比對是蛋白質(zhì)序列之間或核酸序列之間的比對。

假設(shè)我們已經(jīng)發(fā)現(xiàn)一個基因并且知道它的功能，我們可以將它與基因組數(shù)據(jù)庫中所有的序列片段進(jìn)行比對，如果某個序列與該基因很相似，則可能它們的功能也相似，并且它們可能是同源序列。通過同源序列的多重比對能夠發(fā)現(xiàn)與功能相關(guān)的保守序列片段，對于一系列同源蛋白質(zhì)，人們希望研究隱含在蛋白質(zhì)序列中的系統(tǒng)發(fā)育關(guān)系，以便更好地理解這些蛋白質(zhì)的進(jìn)化。在實際研究中，生物學(xué)家著重于研究相關(guān)蛋白質(zhì)序列中的保守區(qū)域，進(jìn)而分析蛋白質(zhì)的結(jié)構(gòu)和功能。所以要發(fā)現(xiàn)多個序列的共性，必須同時比對多條同源序列。

序列比對也可以用來發(fā)現(xiàn)遺傳疾病的病因。我們可以將一些健康者的基因序列與一些疾病患者的基因序列進(jìn)行比對，如果疾病患者的基因都有共同的某種變異，而沒有一個健康者的基因含有這種變異，則很明顯，這種變異是該疾病的病因。

通過多序列比對可以得到一個序列家族的序列特征。當(dāng)給定一個新序列時，根據(jù)序列特征可以判斷序列是否屬于該家族。進(jìn)行多序列比對后，可以對比對結(jié)果進(jìn)行進(jìn)一步處理，如構(gòu)建序列的特征模式，將序列聚類構(gòu)建分子進(jìn)化樹等?？傊蛄斜葘κ巧镄畔W(xué)中一個非常重要的基本操作。

多序列比對的目標(biāo)是發(fā)現(xiàn)多個序列的共性。簡單來說，就是對于輸入的多條序列插入空位并排列比對，使其達(dá)到相同的長度，并使得序列之間匹配字符的個數(shù)盡可能地多，而不匹配字符和空位（Gap）的個數(shù)盡可能地少。為了反映序列比對的質(zhì)量，要有一個定量的標(biāo)準(zhǔn)來度量它們之間的相似程度，我們可以通過計分函數(shù)來評估多重序列比對的質(zhì)量。在實際計算中，SumofPairs（SP）模型是應(yīng)用最為廣泛的計分方法，該函數(shù)將所有兩兩序列比對得分的和作為多序列比對的得分。對于兩個序列比對的分值，傳統(tǒng)的基于編輯距離的計算方法是將比對中所有列（即字符對）的得分求和作為兩個序列比對的得分。其中對于非空位字符對的打分，通常我們可以根據(jù)打分矩陣（Scoring Matrix）得出，最常用到的打分矩陣有PAM系列矩陣以及BLOSUM系列矩陣。

2多序列比對

序列比對的目標(biāo)是分析序列的相似性，推測其結(jié)構(gòu)功能及進(jìn)化上的聯(lián)系，序列比對問題是基因識別、結(jié)構(gòu)預(yù)測、分子進(jìn)化、生命起源研究的基礎(chǔ)。最常見的比對是多個蛋白質(zhì)序列或多個DNA序列同時進(jìn)行比較，因而形成了多重序列比對問題。

在解決多重序列比對問題時，要解決兩個問題：①如何根據(jù)包括結(jié)構(gòu)信息在內(nèi)的生物學(xué)意義對給定比對打分;②在打分機制確定的情況下，如何求得分值最高的最優(yōu)比對。問題①要依據(jù)生物學(xué)的知識和實際問題的需要來決定。本文提出的基于蟻群的多重序列比對算法主要是用來求解問題②，即在計分機制確定的前提下，對于給定的多條序列尋找使得分值最高的最優(yōu)比對。

多重序列的某個比對實際上就是多個序列之間的一種排列方式。圖1是六個蛋白質(zhì)序列片段的多重比對的例子。我們用字符“-”表示插入的空位。

-GRRRSVQWCAVSNPEATKCFQWQRNMRKVR---GPPVSCLKRDSPIQCIQAI

----KTVRWCAVNDHEASKCANFRDSMKKVLPEDGPRIICVKKASYLDCIKAI

------VKWCVKSEQELRKCHDLAAKVAE--------FSCVRKDGSFECIQAI

--KEKQVRWCVKSNSELKKCKDLVDTCKNK----EIKLSCVEKSNTDECSTAI

-----EVRWCATSDPEQHKCGNMSEAFREAGI--QPSLLCVRGTSADHCVQLI

APPKTTVRWCTISSAEEKKCNSLKDHMQQER----VTLSCVQKATYLDCIKAI

圖1多重序列比對

對于一個比對，可以用SP模型對它打分以評價比對的好壞。我們假設(shè)得分函數(shù)具有加和性，即多重比對的得分是各列得分總和，那么，我們首先考慮如何給比對的每一列打分。

對于一列字符打分可用SP函數(shù)，SP 函數(shù)定義為一列中所有字符對得分之和：

其中，ci表示該列中的第i個字符，p(ci，cj)表示字符ci和字符cj比較所得分值。將各列的分值加起來就成為比對的總得分。我們進(jìn)行序列多重比對的目標(biāo)是要在許多比對方案中，尋找得分最高的比對和在此比對的分值，以其代表序列之間的相似性。

Needleman 和 Wunsch 的算法[1]是雙序列比對最經(jīng)常用到的經(jīng)典算法，該算法的時間和空間復(fù)雜度均為O(mn)，其中m和n分別是兩個序列的長度。雖然Needleman 和 Wunsch 的算法可以對兩個序列找到最優(yōu)解，但如果將這個算法直接延伸應(yīng)用到多序列比對的問題上來，時空開銷將達(dá)到O(2N-1)(∏Ni=1|Si|)，其中，N為序列的個數(shù)，|Si|為第i個序列的長度。所以算法雖然簡單，在多重序列比對問題中卻不實用。盡管后來很多人對此算法作了改進(jìn)，如基于Carrillo 和 Lipman的算法[5]MSA[2]、基于分治策略和MSA的DCA[3]、優(yōu)化DCA算法的OMA[4]等，可是這些算法處理的序列長度和數(shù)量仍受到很大限制。

多序列比對的啟發(fā)式計算方法通常是在適度犧牲正確性的基礎(chǔ)上來提高計算效率。CLUSTAL W[6]是應(yīng)用最為廣泛的多重序列比對軟件，它是高效的漸進(jìn)方法的代表。CLUSTAL W對Feng 和 Doolittle提出的算法[7]作了一系列的改進(jìn)，使得結(jié)果的正確性得到進(jìn)一步提高，所以在生物信息學(xué)中得到了廣泛的應(yīng)用。但是漸進(jìn)方法是以序列的兩兩比對為基礎(chǔ)的，而兩兩比對的局部結(jié)果在多重序列比對中往往并不最優(yōu)，這樣會對多重序列比對帶來錯誤信息，并且這些錯誤信息不能在后期階段被糾正。除漸進(jìn)方法以外，常用到的方法有迭代優(yōu)化方法、基于一致性（Consistencybased）的方法、基于隱馬爾可夫模型的方法等。迭代方法的思想是對已經(jīng)求得的中間比對進(jìn)行迭代優(yōu)化，從而提高解的正確性，如Gotoh提出的PRRP[8]，其運用的是非隨機迭代方法；而基于遺傳算法的多重序列比對方法SAGA[9]運用的是隨機迭代的策略；DIALIGN系列[10，11]用一致性策略來解決多重序列比對問題，對于局部的相似性具有較高的敏感性。還有一種方法是基于隱馬爾可夫決策方法為蛋白質(zhì)家族訓(xùn)練建立模型[12]，從而識別出家族的模式特征，然后用序列與模型的比較來判斷序列是否屬于這個家族，其實際上是基于統(tǒng)計的一種方法。另外還有基于偏序圖的多重序列比對方法POA[13]、基于快速傅里葉變換的方法MAFFT[14]、基于塊的多序列比對算法[15]等。除此以外，有些算法采用將幾種策略集成在一起的方法來提高算法的效率，如TCoffee[17]，MUSCLE[18]，Probcons[20]等。

3基于蟻群的多序列比對算法

3．1蟻群算法原理

蟻群算法是近來出現(xiàn)的一種新型的模擬進(jìn)化算法，它由意大利學(xué)者M(jìn).Dorigo 等人首先提出來[16]。蟻群算法實際上是模擬螞蟻集群覓食規(guī)律而設(shè)計出的一種算法，其基本思想是螞蟻通過其他螞蟻的反饋信息來強化學(xué)習(xí)。

實驗觀察表明， 螞蟻在覓食過程中會留下一種分泌物（Pheromone）即信息素，若螞蟻從巢穴到食物源所走的路徑較短，則螞蟻在走這條路徑時，從巢穴到食物源再返回到巢穴所經(jīng)歷的時間就短，從而相同時間內(nèi)，較短路徑上螞蟻所留下的信息素就較多。后面的螞蟻要根據(jù)前面走過的螞蟻所留下的信息素的多少來選擇其要走的路徑，一條路徑上的信息素越多，螞蟻選擇這條路徑的概率就越大。例如，從蟻巢到食物有兩條路徑，在相同的時間內(nèi)，較短路徑上螞蟻留下的信息素較多，從而被螞蟻選擇的概率也就比較長路徑要大。因此，螞蟻群體的集體覓食行為實際上構(gòu)成了一種學(xué)習(xí)信息的正反饋機制，螞蟻之間通過這種信息交流尋求從巢穴到食物源之間的最短路徑。蟻群算法正是模擬了這樣的優(yōu)化機制， 即通過個體之間的信息交流與相互協(xié)作最終找到最優(yōu)解。

蟻群算法在求解復(fù)雜優(yōu)化問題特別是解決旅行商問題（TSP）、圖論問題、分配問題等方面可以取得較好的效果。最近，梁棟等人提出了一個用蟻群算法求解雙序列比對問題的方法[19]，其結(jié)果表明，蟻群算法可以有效地運用于雙序列比對問題。 本文將蟻群算法用于解決復(fù)雜的多重序列比對問題，實驗顯示，該算法可以達(dá)到較好的求解效果。

3．2基于蟻群的多序列比對算法原理

設(shè)有N個序列，其中第i個序列長度為|Si|，我們將序列中的字符看作是螞蟻所要走過路徑上的節(jié)點。

算法首先對序列1分配一個螞蟻，令螞蟻從序列1中的第一個字符出發(fā)，依次選擇序列2，…，序列N中的某個字符（即節(jié)點）與之匹配。選擇的概率取決于字符的匹配程度、匹配的位置偏差以及路徑上的信息素。螞蟻也能以一定的概率選擇一個空位插入序列中的某個位置。在完成第一個字符的匹配后，便得到一條路徑。這條路徑所經(jīng)過的各個序列中的字符便為與序列1第一個字符相匹配的字符。

螞蟻接著從序列1中的第二個字符出發(fā)，再依次選擇其他序列中的節(jié)點或空位與之匹配，如此處理序列1中的各個字符。在螞蟻選擇路徑時，不允許出現(xiàn)線段交叉的情況，因為這意味著不可能的比對。當(dāng)螞蟻走完時，便得到|S1|條路徑所對應(yīng)的一個比對。如圖2所示，圖中的線段代表螞蟻所走的路徑，路徑中的節(jié)點便是螞蟻所選擇的字符。

其他螞蟻也以同樣的方式選擇各自的路徑集合。為了使解具有多樣性，這些螞蟻的處理過程不一定都從序列1開始，我們均勻地分布各個螞蟻的開始序列。從第i條序列開始的螞蟻，從序列i中的字符出發(fā)，依次選擇序列i+1，i+2，…，N，1，2，…，i-1中的某字符（即節(jié)點）與之匹配。

通過螞蟻求出的每個路徑集合，我們可找出對應(yīng)的一個比對，路徑中的節(jié)點便是螞蟻所選擇的相匹配的字符。對于不在路徑上的字符，我們可以用其他方法簡單地求出它們在比對中的位置，如靠左對齊、右邊加空位，以得到一個完整的比對。

在所有螞蟻完成路徑的集合后，算法根據(jù)打分機制求出各個比對的得分，根據(jù)分值的高低對路徑上的信息素進(jìn)行更新，以增大分值高的路徑上的信息素。這樣當(dāng)下一個螞蟻選擇節(jié)點時，就以新的信息素作為選擇的依據(jù)，從而構(gòu)成信息學(xué)習(xí)的正反饋機制。

3．3實現(xiàn)細(xì)節(jié)

(1)概率選擇公式

設(shè)在第k個序列的第l個字符選擇第n個序列中的第m個字符的概率為P(k，l，n，m)。

這樣的概率公式可以使得信息素較高、匹配程度較好且相對位置偏離較小的字符被選中的概率較大。

(2)螞蟻的分配

如果螞蟻總是根據(jù)序列1中的字符來選擇其他序列中的字符，那么得出的結(jié)果會明顯偏向序列1。為了防止螞蟻偏向于某一個特定的序列，我們將所有的序列均勻地分配給螞蟻以作為它的開始序列，然后螞蟻按順序依次選取其他各序列的字符。

(3)螞蟻以一定概率選擇空位

由圖2可以看到，有時是幾個節(jié)點共同指向下一個序列的一個節(jié)點，這是因為螞蟻可以選擇的不僅僅是序列中的某個字符，也可以是空位。因為在比對中可能會出現(xiàn)一些字符對應(yīng)其他序列中所插入的空位的情況，所以應(yīng)該設(shè)定適當(dāng)?shù)母怕?，令螞蟻以此概率選擇空位。當(dāng)螞蟻選擇空位時，就會出現(xiàn)幾個節(jié)點指向一個節(jié)點的情況，此時，僅有一個是指向下一個序列的字符，而其余對應(yīng)的是在該位置上所插入的空位。

(4)螞蟻字符選擇方法

在第k個序列的第l個字符Sk(l)選擇第n個序列中某個字符時，首先對允許范圍內(nèi)的所有字符計算選擇概率，得到使得選擇概率最大的字符Sn(m)。如果Sn(m)＝Sk(l)，則選擇該字符；否則以一定的概率選擇空位，以剩余的概率選擇字符Sn(loc(k，l，n))。

當(dāng)然，我們也可以首先計算選擇概率，然后根據(jù)輪盤轉(zhuǎn)法來選擇第n個序列中的某個字符，但是用此方法得到的比對會存在過多的空位，影響了比對的質(zhì)量。

(5)適應(yīng)度函數(shù)

(6)信息素全局更新

設(shè)定信息素全局更新的蒸發(fā)系數(shù)為evap1，每當(dāng)一個螞蟻走完得到一個比對時，對螞蟻所經(jīng)過的所有節(jié)點上的信息素按式（6）進(jìn)行更新。

phe(k，l，n，m)=phe(k，l，n，m)×(1-evap1)+( alignsum-average)×evap1(6)

其中， alignsum是該螞蟻得到的比對得分，average是之前得到的所有比對的平均得分。

(7)信息素的調(diào)節(jié)

在經(jīng)歷了一定代數(shù)以后，由于信息素的漸漸集中，算法會陷入局部最優(yōu)。為了解決這個問題，我們采取了以下措施：

預(yù)先設(shè)定參數(shù)start，在第start代以后，若某代中螞蟻得到的比對得分不高于前d代螞蟻得到的比對得分（start，d都是可調(diào)節(jié)的參數(shù)），則對信息素進(jìn)行局部更新。更新策略是對于信息素高于某一閾值的路徑上的信息素，依據(jù)一定的蒸發(fā)系數(shù)evap2進(jìn)行蒸發(fā)，使得下一代的螞蟻盡量選擇沒走過的路徑去走。

3．4算法描述

Algorithm Antmsa

Input：N個序列S1，S2，…，SN；

Output：N個序列S1，S2，…，SN的近似最優(yōu)比對及最優(yōu)比對得分 alignsum。

Begin

(1)各參數(shù)的初始化

(2)for cycle=1 to Cyclenum do// Cyclenum為迭代次數(shù)

(3)for k=1 to N do// N只螞蟻均勻地分配給N個序列

(4)for l=1 to |Sk| do//對Sk的字符循環(huán)

(5)for n=1 to N do//對序列循環(huán)

(6)if (n<>k) then

(7)for m=loc(k，l，n) to loc(k，l，n)+h-1 do

(8)根據(jù)式(2)計算 P(k，l，n，m)

(9)計算使得P(k，l，n，m)最大的m值

(10)if (Sn(m)＝Sk(l)) then 選擇Sn(m)

(11)else 以某概率選擇空位，以剩余概率選擇Sn(loc(k，l，n))

(12)end if

(13)end if

(14)end for n

(15)end for l

(16)插入空位對螞蟻未選擇的字符對齊以得到完整比對

(17)根據(jù)式(5)計算此比對的適應(yīng)度函數(shù)值

(18)根據(jù)式(6)對信息素進(jìn)行更新

(19)end for k

(20)如果比對得分高于之前的所有比對，保留比對及比對得分

(21)if cycle>start then 進(jìn)行信息素的調(diào)節(jié)

(22)根據(jù)式(7)~式(9)調(diào)節(jié)參數(shù)a，b，c

(23)end for cycle

End

顯然，算法的（1）及（9）~（12）可在O(1)時間實現(xiàn)。令LEN為任一序列比對后可能的長度最大值，因為h

4分治策略與蟻群算法結(jié)合求解多重序列比對問題

為降低多重序列比對的計算量，可以采用分治策略（圖3）將序列集在適當(dāng)?shù)奈恢脛澐殖扇舾蓚€由較短序列構(gòu)成的子序列集，然后對各個子序列集用蟻群算法求解比對，我們將該算法稱為Divideantmsa。

Divideantmsa的實現(xiàn)分為三個步驟：

(1)尋找適當(dāng)?shù)膭澐?。將序列集縱向劃分成若干段，每一段為由較短序列構(gòu)成的子序列集。本文中尋找劃分是基于二分的思想，即先對原序列集尋找一個大約中間位置的劃分，根據(jù)該劃分將原序列集縱向分成左、右兩段；再對這兩段子序列集繼續(xù)求出各自的劃分，這時原序列集被分解成了四段；接著再用同樣的方法遞歸分解下去，直到每一段的長度小于某個閾值時終止。

(2)當(dāng)所有劃分點計算出來以后，各段子序列集可以用本節(jié)中所描述的算法對其分別進(jìn)行比對，即用蟻群算法來求解每一段的子序列集的比對。

(3)將各段的比對按順序連接起來以得到多序列比對的結(jié)果。

4．1劃分及其評價

設(shè)有N個序列，對于每一個輸入序列Si，在位置ci將序列Si分成兩部分：第一部分為字符Si，1， Si，2，…， Si，c組成的子序列，記為Spi(ci)；第二部分則由字符Si，ci+1， Si，ci+2，…， Si，|Si|組成，記為Ssi(ci)，其中ci必須滿足1≤ci≤|Si|。所有序列的劃分位置c1，c2，…，cN構(gòu)成的一維數(shù)組c即為一個有效劃分。這個劃分將原序列集縱向分成前、后兩段： 前部分的子序列集記為Sp=(Sp1(c1)，…，SpN(cN))；后部分的子序列集記為Ss=(Ss1(c1)，…，SsN(cN))。

在算法的計算過程中，需要對求得的劃分評價其合理程度。設(shè)原序列集通過劃分縱向分解為兩部分，得到子序列集Sp和Ss。我們對這兩個子序列集分別求出最優(yōu)多重比對，設(shè)結(jié)果分別為P和Q，將這兩部分的多重比對拼接后，所得到的結(jié)果PQ作為原序列集的比對。如果此結(jié)果即為原序列集的最優(yōu)比對，則這樣的劃分就是最優(yōu)的劃分；如果此結(jié)果的得分較高，則說明此劃分較合理。由于得分與Sp和Ss這兩部分多序列比對的得分密切相關(guān)，我們將這兩部分多序列比對的得分相加，若和值較高，表示劃分較合理，否則表示劃分較差。

為了估計劃分的合理性，雙序列相似程度的計算是頻繁用到的一個操作，計算出所有的雙序列比對的近似得分后，取它們的和便是多重序列比對的近似得分。

對于雙序列比較，如果使用動態(tài)規(guī)劃的方法，設(shè)兩個序列的長度分別為m，n，則其計算代價是O(mn)。為了減少計算代價，可以用近似的方法估計兩個序列的相似程度。因此，我們提出了一個計算兩序列X和Y比對的得分近似算法SE（ScoreEstimate）。SE算法可以在O(m+n)時間內(nèi)近似計算出兩個序列之間的相似性得分。

SE算法的計算分為四步，分別記為LeftUpper，RightUpper，LeftLower 和RightLower。其中每一步代表著對X和Y的一次掃描。例如，LeftUpper是從序列X的第一個字符X0出發(fā)，在Y中從左向右依次尋找與X0匹配的第一個字符Yj；然后從Yj+1出發(fā)，在X0后面從左向右尋找第一個與Yj+1匹配的字符Xi；再從其后一個字符Xi+1出發(fā)，尋找Yj+1后面第一個與Xi+1匹配的字符。此過程重復(fù)進(jìn)行直到找遍整個序列X或序列Y。每找到一個匹配字符，計數(shù)器Count1加1。每次在Y(或X)尚未掃描的部分中從左向右尋找與Xi+1（或Yj+1）匹配的字符時， 如果找不到這樣的匹配字符， 則算法改為在Y(或X)尚未掃描的部分中尋找與下一字符Xi+2 （或Yj+2）匹配的字符。

4．2計算劃分

對于每一次劃分的求解，可通過蟻群算法計算得到。

設(shè)有N個序列，對于第一個序列S1，在中點位置c1將序列S1分成兩部分，即c1=|S1|/2，而對于其他序列的劃分位置，則通過蟻群算法迭代優(yōu)化求得。

令螞蟻從序列1中的第c1個字符出發(fā)，依次選擇序列2，…，序列N中的某字符（即節(jié)點）與之匹配。選擇的概率取決于字符的匹配程度、匹配的位置偏差以及路徑上的信息素。在選擇過所有序列的字符后，便得到一條路徑，這條路徑所經(jīng)過的各個序列中的字符位置便分別為c2，c3，…，c1。

通過螞蟻求出的路徑，可找出對應(yīng)的一個劃分（c1，c2，…， cN）；然后算法根據(jù)第4.1節(jié)中介紹的劃分評價機制求出劃分的得分，根據(jù)分值的高低對路徑上的信息素進(jìn)行更新，以增大分值高的路徑上的信息素。這樣，當(dāng)下一個螞蟻選擇節(jié)點時，就以新信息素作為選擇依據(jù)，從而構(gòu)成信息學(xué)習(xí)的正反饋機制。

5實驗結(jié)果

我們用標(biāo)準(zhǔn)的測試數(shù)據(jù)庫BAliBASE 2.0中的測試數(shù)據(jù)對算法進(jìn)行測試。我們從中隨機地選擇一些序列集進(jìn)行測試，結(jié)果顯示，本文所提出的基于蟻群算法的多重序列比對方法既能夠較好地處理相似程度高的序列集，也能夠較好地對相似程度低的序列集進(jìn)行比對。測試結(jié)果如表1所示。表1中SP正確性是將算法得出的比對與BAliBASE中的標(biāo)準(zhǔn)比對進(jìn)行比較，與標(biāo)準(zhǔn)比對中的核心塊（Core Block）相符合的堿基對的個數(shù)占整個核心塊的百分比。

表1測試結(jié)果

對于相似程度小于30%的序列集，絕大多數(shù)的算法都不能得到正確的結(jié)果，所以我們通常將其稱為是序列比對中的模糊區(qū)（Twilight Zone）。而本文的算法對于模糊區(qū)中的序列集進(jìn)行了較為正確的比對，但是在序列的長度及數(shù)量增加時，算法的準(zhǔn)確性會降低。

實驗顯示，分治策略和蟻群算法相結(jié)合求解多重序列比對問題克服了單獨使用AntAlign算法不能夠?qū)^長序列進(jìn)行較好比對的缺點，改進(jìn)了長序列比對的準(zhǔn)確性，而且減少了計算時間。一般情況下，Antmsa 及Divideantmsa算法在1 000代以內(nèi)即可收斂得到較優(yōu)解。對于序列個數(shù)為10、長度從100~800的測試數(shù)據(jù)，我們對Antmsa算法求得較優(yōu)解所需的計算時間進(jìn)行了統(tǒng)計，與同樣基于進(jìn)化算法的SAGA算法相比，Antmsa算法在計算時間上比SAGA減少了95%~99%。

由圖4和圖5所示的結(jié)果可以看出，當(dāng)序列長度增加時，算法的計算時間增加較慢；而當(dāng)序列個數(shù)增加時，算法的計算時間增加較快，這是由于序列個數(shù)增加時，必須增加迭代次數(shù)才能得到較理想的解。

6結(jié)論

本文提出了一種解決多重序列比對的蟻群算法，利用了人工螞蟻逐個選擇各個序列中字符進(jìn)行配對。在算法中，螞蟻根據(jù)信息素、字符匹配得分以及位置偏差等信息決定選擇各序列中字符的概率，通過信息素的更新與調(diào)節(jié)相結(jié)合的策略，以及參數(shù)的動態(tài)自適應(yīng)調(diào)節(jié)方法，較為有效地解決了局部收斂的問題，加強了算法尋求全局最優(yōu)解的能力。在該算法的基礎(chǔ)上，我們還提出了基于分治策略的多序列比對蟻群求解算法，不但減少了計算時間，而且顯著改善了算法所求得的解的質(zhì)量。另外，蟻群算法的一個特點是易于并行化，基于蟻群算法的多重序列比對方法可以用簡單的策略實現(xiàn)算法的并行化，從而降低了算法的運算時間，提高了求解效率。

參考文獻(xiàn)：

［1］Needleman S， Wunsch C. A General Method Applicable to the Search for Similarities in the Amino Acid Sequence of Two Proteins[J]. J. Mol. Biol.， 1970， 48(3)：443453.

［2］Lipman DJ， Altschul SF， Kececioglu JD. A Tool for Multiple Sequence Alignment[C]. Proc. of Natl. Acad. Sci.， 1989.44124415.

［3］Stoye J， Moulton V， Dress AW. DCA： An Efficient Implementation of the DivideandConquer Approach to Simultaneous Multiple Sequence Alignment[J]. Comput. Appl. Biosci.， 1997，13(6):625626.

［4］Reinert K， Stoye J， Will T. An Iterative Method for Faster SumofPair Multiple Sequence Alignment[J]. Bioinformatics， 2000，16(9)：808814.

［5］Carrillo H， Lipman DJ. The Multiple Sequence Alignment Problem in Biology[C].SIAM J. Appl. Math.， 1988，48(5):10731082 .

［6］Thompson JD， Higgins DG， Gibson TJ， et al. CLUSTAL W:Improving the Sensitivity of Progressive Multiple Sequence Alignment through Sequence Weighting， Position Specific Gap Penalties and Weight Matrix Choice[J]. Nucleic Acids Research， 1994，22(22):46734680.

［7］Feng DF， Doolittle RF. Progressive Sequence Alignment as a Prerequisite to Correct Phylogenetic Trees[J]. J. Mol.， Evol.，1987，25:351360.

［8］Gotoh O. Significant Improvement in Accuracy of Multiple Protein Sequence Alignments by Iterative Refinements as Assessed by Reference to Structural Alignments[J]. J. Mol. Biol.， 1996，264(4):823838.

［9］Notredame C， Higgins DG. SAGA:Sequence Alignment by Genetic Algorithm[J]. Nucleic Acids Res.， 1996，24(8):15151524.

［10］B Morgenstern， T Werner. DIALIGN： Finding Local Similarities by Multiple Sequence Alignment[J]. Bioinformatics，1997，13(3):290294.

［11］Morgenstern B. DIALIGN 2： Improvement of the SegmenttoSegment Approach to Multiple Sequence Alignment[J].Bioinformatics， 1999，15(3):211218.

［12］A Krogh. An Introduction to Hidden Markov Models for Biological Sequences[A]. S L Salzberg， D B Searls， S Kasif. Computational Methods in Molecular Biology[M]. Elsevier， 1998.4563.

［13］Christopher Lee， Catherine Grasso， Mark F Sharlow. Multiple Sequence Alignment Using Partial Order Graphs[J]. Bioinformatics， 2002，18(3):452464.

［14］Kazutaka Katoh， Kazuharu Misawa1， Keiichi Kuma， et al. MAFFT:A Novel Method for Rapid Multiple Sequence Alignment Based on Fast Fourier Transform[J]. Nucleic Acids Res.， 2002，30(14)：30593066.

［15］P Zhao， Tao Jiang J. A Heuristic Algorithm for Multiple Sequence Alignment Based on Blocks[J]. Combinatorial Optimization， 2001，5(1)：95115.

［16］Dorigo M， Maniezzo V， Colorni A. Ant System： Optimization by a Colony of Coorperating Agents[J]. IEEE Transactions on Systems， Man， and CyberneticsPart B， 1996，26(1):2941.

［17］Notredame C， Higgins DG， Heringa J. TCoffee: A Novel Method for Fast and Accurate Multiple Sequence Alignment[J]. J. Mol. Biol.， 2000，302(1)：205217.

［18］Edgar RC. MUSCLE: A Multiple Sequence Alignment Method with Reduced Time and Space Complexity[J]. BMC Bioinformatics， 20-04， 5(1):113.

［19］Liang Dong，Huo Hongwei. An Adaptive Ant Colony Optimization Algorithm and Its Application to Sequence Alignment[J]. Computer Simulation， 2005， 22(1)：100106.

［20］Do CB， Brudno M， Batzoglou S. ProbCons： Probabilistic Consistencybased Multiple Alignment of Amino Acid Sequences[C]. Procee￣dings of the 13th National Conference on Artificial， Intelligence， 20-04.703708.

作者簡介：

陳娟(1979)， 女， 碩士研究生，主要研究方向為生物計算和并行算法設(shè)計；陳崚（1951）， 男， 教授， 博導(dǎo)，主要研究方向為算法設(shè)計和并行計算。

注:本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文