求解多重序列比對問題的蟻群算法
2007-01-01 00:00:00陳娟陳崚
計算機應用研究 2007年1期
摘要：多重序列比對是生物信息學特別是生物序列分析中一個重要的基本操作。提出求解多重序列比對問題的蟻群算法，利用人工螞蟻逐個選擇各個序列中的字符進行配對。在算法中，螞蟻根據信息素、字符匹配得分以及位置偏差等信息決定選擇各序列中字符的概率，通過信息素的更新與調節相結合的策略較為有效地解決了局部收斂的問題，加強了算法尋求全局最優解的能力。另外在該算法的基礎上，提出了基于分治策略的多序列比對蟻群求解算法，不但減少了原算法的計算時間，而且顯著改善了算法所求得的解的質量。
關鍵詞：生物信息學； 多重序列比對；蟻群算法； 分治策略
中圖法分類號：TP37；O141.3文獻標識碼：A
文章編號：1001－3695(2007)01－0025－06
1引言
多序列比對是生物信息學及計算分子生物學中的一個重要問題，是基因識別、蛋白質結構預測、生物進化樹的構建、基因組信息分析等問題中用到的一個基本操作。通過序列比對可以探索生物序列中所包含的功能、結構和進化信息。在生物信息學中，最常見的比對是蛋白質序列之間或核酸序列之間的比對。
假設我們已經發現一個基因并且知道它的功能，我們可以將它與基因組數據庫中所有的序列片段進行比對，如果某個序列與該基因很相似，則可能它們的功能也相似，并且它們可能是同源序列。通過同源序列的多重比對能夠發現與功能相關的保守序列片段，對于一系列同源蛋白質，人們希望研究隱含在蛋白質序列中的系統發育關系，以便更好地理解這些蛋白質的進化。在實際研究中，生物學家著重于研究相關蛋白質序列中的保守區域，進而分析蛋白質的結構和功能。所以要發現多個序列的共性，必須同時比對多條同源序列。
序列比對也可以用來發現遺傳疾病的病因。我們可以將一些健康者的基因序列與一些疾病患者的基因序列進行比對，如果疾病患者的基因都有共同的某種變異，而沒有一個健康者的基因含有這種變異，則很明顯，這種變異是該疾病的病因。
通過多序列比對可以得到一個序列家族的序列特征。當給定一個新序列時，根據序列特征可以判斷序列是否屬于該家族。進行多序列比對后，可以對比對結果進行進一步處理，如構建序列的特征模式，將序列聚類構建分子進化樹等?？傊?，序列比對是生物信息學中一個非常重要的基本操作。
多序列比對的目標是發現多個序列的共性。簡單來說，就是對于輸入的多條序列插入空位并排列比對，使其達到相同的長度，并使得序列之間匹配字符的個數盡可能地多，而不匹配字符和空位（Gap）的個數盡可能地少。為了反映序列比對的質量，要有一個定量的標準來度量它們之間的相似程度，我們可以通過計分函數來評估多重序列比對的質量。在實際計算中，SumofPairs（SP）模型是應用最為廣泛的計分方法，該函數將所有兩兩序列比對得分的和作為多序列比對的得分。對于兩個序列比對的分值，傳統的基于編輯距離的計算方法是將比對中所有列（即字符對）的得分求和作為兩個序列比對的得分。其中對于非空位字符對的打分，通常我們可以根據打分矩陣（Scoring Matrix）得出，最常用到的打分矩陣有PAM系列矩陣以及BLOSUM系列矩陣。
2多序列比對
序列比對的目標是分析序列的相似性，推測其結構功能及進化上的聯系，序列比對問題是基因識別、結構預測、分子進化、生命起源研究的基礎。最常見的比對是多個蛋白質序列或多個DNA序列同時進行比較，因而形成了多重序列比對問題。
在解決多重序列比對問題時，要解決兩個問題：①如何根據包括結構信息在內的生物學意義對給定比對打分;②在打分機制確定的情況下，如何求得分值最高的最優比對。問題①要依據生物學的知識和實際問題的需要來決定。本文提出的基于蟻群的多重序列比對算法主要是用來求解問題②，即在計分機制確定的前提下，對于給定的多條序列尋找使得分值最高的最優比對。
多重序列的某個比對實際上就是多個序列之間的一種排列方式。圖1是六個蛋白質序列片段的多重比對的例子。我們用字符“-”表示插入的空位。
-GRRRSVQWCAVSNPEATKCFQWQRNMRKVR---GPPVSCLKRDSPIQCIQAI
----KTVRWCAVNDHEASKCANFRDSMKKVLPEDGPRIICVKKASYLDCIKAI
------VKWCVKSEQELRKCHDLAAKVAE--------FSCVRKDGSFECIQAI
--KEKQVRWCVKSNSELKKCKDLVDTCKNK----EIKLSCVEKSNTDECSTAI
-----EVRWCATSDPEQHKCGNMSEAFREAGI--QPSLLCVRGTSADHCVQLI
APPKTTVRWCTISSAEEKKCNSLKDHMQQER----VTLSCVQKATYLDCIKAI
圖1多重序列比對
對于一個比對，可以用SP模型對它打分以評價比對的好壞。我們假設得分函數具有加和性，即多重比對的得分是各列得分總和，那么，我們首先考慮如何給比對的每一列打分。
對于一列字符打分可用SP函數，SP 函數定義為一列中所有字符對得分之和：
其中，ci表示該列中的第i個字符，p(ci，cj)表示字符ci和字符cj比較所得分值。將各列的分值加起來就成為比對的總得分。我們進行序列多重比對的目標是要在許多比對方案中，尋找得分最高的比對和在此比對的分值，以其代表序列之間的相似性。
Needleman 和 Wunsch 的算法[1]是雙序列比對最經常用到的經典算法，該算法的時間和空間復雜度均為O(mn)，其中m和n分別是兩個序列的長度。雖然Needleman 和 Wunsch 的算法可以對兩個序列找到最優解，但如果將這個算法直接延伸應用到多序列比對的問題上來，時空開銷將達到O(2N-1)(∏Ni=1|Si|)，其中，N為序列的個數，|Si|為第i個序列的長度。所以算法雖然簡單，在多重序列比對問題中卻不實用。盡管后來很多人對此算法作了改進，如基于Carrillo 和 Lipman的算法[5]MSA[2]、基于分治策略和MSA的DCA[3]、優化DCA算法的OMA[4]等，可是這些算法處理的序列長度和數量仍受到很大限制。
多序列比對的啟發式計算方法通常是在適度犧牲正確性的基礎上來提高計算效率。CLUSTAL W[6]是應用最為廣泛的多重序列比對軟件，它是高效的漸進方法的代表。CLUSTAL W對Feng 和 Doolittle提出的算法[7]作了一系列的改進，使得結果的正確性得到進一步提高，所以在生物信息學中得到了廣泛的應用。但是漸進方法是以序列的兩兩比對為基礎的，而兩兩比對的局部結果在多重序列比對中往往并不最優，這樣會對多重序列比對帶來錯誤信息，并且這些錯誤信息不能在后期階段被糾正。除漸進方法以外，常用到的方法有迭代優化方法、基于一致性（Consistencybased）的方法、基于隱馬爾可夫模型的方法等。迭代方法的思想是對已經求得的中間比對進行迭代優化，從而提高解的正確性，如Gotoh提出的PRRP[8]，其運用的是非隨機迭代方法；而基于遺傳算法的多重序列比對方法SAGA[9]運用的是隨機迭代的策略；DIALIGN系列[10，11]用一致性策略來解決多重序列比對問題，對于局部的相似性具有較高的敏感性。還有一種方法是基于隱馬爾可夫決策方法為蛋白質家族訓練建立模型[12]，從而識別出家族的模式特征，然后用序列與模型的比較來判斷序列是否屬于這個家族，其實際上是基于統計的一種方法。另外還有基于偏序圖的多重序列比對方法POA[13]、基于快速傅里葉變換的方法MAFFT[14]、基于塊的多序列比對算法[15]等。除此以外，有些算法采用將幾種策略集成在一起的方法來提高算法的效率，如TCoffee[17]，MUSCLE[18]，Probcons[20]等。
3基于蟻群的多序列比對算法
3．1蟻群算法原理
蟻群算法是近來出現的一種新型的模擬進化算法，它由意大利學者M.Dorigo 等人首先提出來[16]。蟻群算法實際上是模擬螞蟻集群覓食規律而設計出的一種算法，其基本思想是螞蟻通過其他螞蟻的反饋信息來強化學習。
實驗觀察表明， 螞蟻在覓食過程中會留下一種分泌物（Pheromone）即信息素，若螞蟻從巢穴到食物源所走的路徑較短，則螞蟻在走這條路徑時，從巢穴到食物源再返回到巢穴所經歷的時間就短，從而相同時間內，較短路徑上螞蟻所留下的信息素就較多。后面的螞蟻要根據前面走過的螞蟻所留下的信息素的多少來選擇其要走的路徑，一條路徑上的信息素越多，螞蟻選擇這條路徑的概率就越大。例如，從蟻巢到食物有兩條路徑，在相同的時間內，較短路徑上螞蟻留下的信息素較多，從而被螞蟻選擇的概率也就比較長路徑要大。因此，螞蟻群體的集體覓食行為實際上構成了一種學習信息的正反饋機制，螞蟻之間通過這種信息交流尋求從巢穴到食物源之間的最短路徑。蟻群算法正是模擬了這樣的優化機制， 即通過個體之間的信息交流與相互協作最終找到最優解。
蟻群算法在求解復雜優化問題特別是解決旅行商問題（TSP）、圖論問題、分配問題等方面可以取得較好的效果。最近，梁棟等人提出了一個用蟻群算法求解雙序列比對問題的方法[19]，其結果表明，蟻群算法可以有效地運用于雙序列比對問題。 本文將蟻群算法用于解決復雜的多重序列比對問題，實驗顯示，該算法可以達到較好的求解效果。
3．2基于蟻群的多序列比對算法原理
設有N個序列，其中第i個序列長度為|Si|，我們將序列中的字符看作是螞蟻所要走過路徑上的節點。
算法首先對序列1分配一個螞蟻，令螞蟻從序列1中的第一個字符出發，依次選擇序列2，…，序列N中的某個字符（即節點）與之匹配。選擇的概率取決于字符的匹配程度、匹配的位置偏差以及路徑上的信息素。螞蟻也能以一定的概率選擇一個空位插入序列中的某個位置。在完成第一個字符的匹配后，便得到一條路徑。這條路徑所經過的各個序列中的字符便為與序列1第一個字符相匹配的字符。
螞蟻接著從序列1中的第二個字符出發，再依次選擇其他序列中的節點或空位與之匹配，如此處理序列1中的各個字符。在螞蟻選擇路徑時，不允許出現線段交叉的情況，因為這意味著不可能的比對。當螞蟻走完時，便得到|S1|條路徑所對應的一個比對。如圖2所示，圖中的線段代表螞蟻所走的路徑，路徑中的節點便是螞蟻所選擇的字符。
其他螞蟻也以同樣的方式選擇各自的路徑集合。為了使解具有多樣性，這些螞蟻的處理過程不一定都從序列1開始，我們均勻地分布各個螞蟻的開始序列。從第i條序列開始的螞蟻，從序列i中的字符出發，依次選擇序列i+1，i+2，…，N，1，2，…，i-1中的某字符（即節點）與之匹配。
通過螞蟻求出的每個路徑集合，我們可找出對應的一個比對，路徑中的節點便是螞蟻所選擇的相匹配的字符。對于不在路徑上的字符，我們可以用其他方法簡單地求出它們在比對中的位置，如靠左對齊、右邊加空位，以得到一個完整的比對。
在所有螞蟻完成路徑的集合后，算法根據打分機制求出各個比對的得分，根據分值的高低對路徑上的信息素進行更新，以增大分值高的路徑上的信息素。這樣當下一個螞蟻選擇節點時，就以新的信息素作為選擇的依據，從而構成信息學習的正反饋機制。
3．3實現細節
(1)概率選擇公式
設在第k個序列的第l個字符選擇第n個序列中的第m個字符的概率為P(k，l，n，m)。
這樣的概率公式可以使得信息素較高、匹配程度較好且相對位置偏離較小的字符被選中的概率較大。
(2)螞蟻的分配
如果螞蟻總是根據序列1中的字符來選擇其他序列中的字符，那么得出的結果會明顯偏向序列1。為了防止螞蟻偏向于某一個特定的序列，我們將所有的序列均勻地分配給螞蟻以作為它的開始序列，然后螞蟻按順序依次選取其他各序列的字符。
(3)螞蟻以一定概率選擇空位
由圖2可以看到，有時是幾個節點共同指向下一個序列的一個節點，這是因為螞蟻可以選擇的不僅僅是序列中的某個字符，也可以是空位。因為在比對中可能會出現一些字符對應其他序列中所插入的空位的情況，所以應該設定適當的概率，令螞蟻以此概率選擇空位。當螞蟻選擇空位時，就會出現幾個節點指向一個節點的情況，此時，僅有一個是指向下一個序列的字符，而其余對應的是在該位置上所插入的空位。
(4)螞蟻字符選擇方法
在第k個序列的第l個字符Sk(l)選擇第n個序列中某個字符時，首先對允許范圍內的所有字符計算選擇概率，得到使得選擇概率最大的字符Sn(m)。如果Sn(m)＝Sk(l)，則選擇該字符；否則以一定的概率選擇空位，以剩余的概率選擇字符Sn(loc(k，l，n))。
當然，我們也可以首先計算選擇概率，然后根據輪盤轉法來選擇第n個序列中的某個字符，但是用此方法得到的比對會存在過多的空位，影響了比對的質量。
(5)適應度函數
(6)信息素全局更新
設定信息素全局更新的蒸發系數為evap1，每當一個螞蟻走完得到一個比對時，對螞蟻所經過的所有節點上的信息素按式（6）進行更新。
phe(k，l，n，m)=phe(k，l，n，m)×(1-evap1)+( alignsum-average)×evap1(6)
其中， alignsum是該螞蟻得到的比對得分，average是之前得到的所有比對的平均得分。
(7)信息素的調節
在經歷了一定代數以后，由于信息素的漸漸集中，算法會陷入局部最優。為了解決這個問題，我們采取了以下措施：
預先設定參數start，在第start代以后，若某代中螞蟻得到的比對得分不高于前d代螞蟻得到的比對得分（start，d都是可調節的參數），則對信息素進行局部更新。更新策略是對于信息素高于某一閾值的路徑上的信息素，依據一定的蒸發系數evap2進行蒸發，使得下一代的螞蟻盡量選擇沒走過的路徑去走。
3．4算法描述
Algorithm Antmsa
Input：N個序列S1，S2，…，SN；
Output：N個序列S1，S2，…，SN的近似最優比對及最優比對得分 alignsum。
Begin
(1)各參數的初始化
(2)for cycle=1 to Cyclenum do// Cyclenum為迭代次數
(3)for k=1 to N do// N只螞蟻均勻地分配給N個序列
(4)for l=1 to |Sk| do//對Sk的字符循環
(5)for n=1 to N do//對序列循環
(6)if (n<>k) then
(7)for m=loc(k，l，n) to loc(k，l，n)+h-1 do
(8)根據式(2)計算 P(k，l，n，m)
(9)計算使得P(k，l，n，m)最大的m值
(10)if (Sn(m)＝Sk(l)) then 選擇Sn(m)
(11)else 以某概率選擇空位，以剩余概率選擇Sn(loc(k，l，n))
(12)end if
(13)end if
(14)end for n
(15)end for l
(16)插入空位對螞蟻未選擇的字符對齊以得到完整比對
(17)根據式(5)計算此比對的適應度函數值
(18)根據式(6)對信息素進行更新
(19)end for k
(20)如果比對得分高于之前的所有比對，保留比對及比對得分
(21)if cycle>start then 進行信息素的調節
(22)根據式(7)~式(9)調節參數a，b，c
(23)end for cycle
End
顯然，算法的（1）及（9）~（12）可在O(1)時間實現。令LEN為任一序列比對后可能的長度最大值，因為h 4分治策略與蟻群算法結合求解多重序列比對問題 為降低多重序列比對的計算量，可以采用分治策略（圖3）將序列集在適當的位置劃分成若干個由較短序列構成的子序列集，然后對各個子序列集用蟻群算法求解比對，我們將該算法稱為Divideantmsa。 Divideantmsa的實現分為三個步驟： (1)尋找適當的劃分。將序列集縱向劃分成若干段，每一段為由較短序列構成的子序列集。本文中尋找劃分是基于二分的思想，即先對原序列集尋找一個大約中間位置的劃分，根據該劃分將原序列集縱向分成左、右兩段；再對這兩段子序列集繼續求出各自的劃分，這時原序列集被分解成了四段；接著再用同樣的方法遞歸分解下去，直到每一段的長度小于某個閾值時終止。 (2)當所有劃分點計算出來以后，各段子序列集可以用本節中所描述的算法對其分別進行比對，即用蟻群算法來求解每一段的子序列集的比對。 (3)將各段的比對按順序連接起來以得到多序列比對的結果。 4．1劃分及其評價 設有N個序列，對于每一個輸入序列Si，在位置ci將序列Si分成兩部分：第一部分為字符Si，1， Si，2，…， Si，c組成的子序列，記為Spi(ci)；第二部分則由字符Si，ci+1， Si，ci+2，…， Si，|Si|組成，記為Ssi(ci)，其中ci必須滿足1≤ci≤|Si|。所有序列的劃分位置c1，c2，…，cN構成的一維數組c即為一個有效劃分。這個劃分將原序列集縱向分成前、后兩段： 前部分的子序列集記為Sp=(Sp1(c1)，…，SpN(cN))；后部分的子序列集記為Ss=(Ss1(c1)，…，SsN(cN))。 在算法的計算過程中，需要對求得的劃分評價其合理程度。設原序列集通過劃分縱向分解為兩部分，得到子序列集Sp和Ss。我們對這兩個子序列集分別求出最優多重比對，設結果分別為P和Q，將這兩部分的多重比對拼接后，所得到的結果PQ作為原序列集的比對。如果此結果即為原序列集的最優比對，則這樣的劃分就是最優的劃分；如果此結果的得分較高，則說明此劃分較合理。由于得分與Sp和Ss這兩部分多序列比對的得分密切相關，我們將這兩部分多序列比對的得分相加，若和值較高，表示劃分較合理，否則表示劃分較差。 為了估計劃分的合理性，雙序列相似程度的計算是頻繁用到的一個操作，計算出所有的雙序列比對的近似得分后，取它們的和便是多重序列比對的近似得分。 對于雙序列比較，如果使用動態規劃的方法，設兩個序列的長度分別為m，n，則其計算代價是O(mn)。為了減少計算代價，可以用近似的方法估計兩個序列的相似程度。因此，我們提出了一個計算兩序列X和Y比對的得分近似算法SE（ScoreEstimate）。SE算法可以在O(m+n)時間內近似計算出兩個序列之間的相似性得分。 SE算法的計算分為四步，分別記為LeftUpper，RightUpper，LeftLower 和RightLower。其中每一步代表著對X和Y的一次掃描。例如，LeftUpper是從序列X的第一個字符X0出發，在Y中從左向右依次尋找與X0匹配的第一個字符Yj；然后從Yj+1出發，在X0后面從左向右尋找第一個與Yj+1匹配的字符Xi；再從其后一個字符Xi+1出發，尋找Yj+1后面第一個與Xi+1匹配的字符。此過程重復進行直到找遍整個序列X或序列Y。每找到一個匹配字符，計數器Count1加1。每次在Y(或X)尚未掃描的部分中從左向右尋找與Xi+1（或Yj+1）匹配的字符時， 如果找不到這樣的匹配字符， 則算法改為在Y(或X)尚未掃描的部分中尋找與下一字符Xi+2 （或Yj+2）匹配的字符。 4．2計算劃分 對于每一次劃分的求解，可通過蟻群算法計算得到。 設有N個序列，對于第一個序列S1，在中點位置c1將序列S1分成兩部分，即c1=|S1|/2，而對于其他序列的劃分位置，則通過蟻群算法迭代優化求得。 令螞蟻從序列1中的第c1個字符出發，依次選擇序列2，…，序列N中的某字符（即節點）與之匹配。選擇的概率取決于字符的匹配程度、匹配的位置偏差以及路徑上的信息素。在選擇過所有序列的字符后，便得到一條路徑，這條路徑所經過的各個序列中的字符位置便分別為c2，c3，…，c1。 通過螞蟻求出的路徑，可找出對應的一個劃分（c1，c2，…， cN）；然后算法根據第4.1節中介紹的劃分評價機制求出劃分的得分，根據分值的高低對路徑上的信息素進行更新，以增大分值高的路徑上的信息素。這樣，當下一個螞蟻選擇節點時，就以新信息素作為選擇依據，從而構成信息學習的正反饋機制。 5實驗結果 我們用標準的測試數據庫BAliBASE 2.0中的測試數據對算法進行測試。我們從中隨機地選擇一些序列集進行測試，結果顯示，本文所提出的基于蟻群算法的多重序列比對方法既能夠較好地處理相似程度高的序列集，也能夠較好地對相似程度低的序列集進行比對。測試結果如表1所示。表1中SP正確性是將算法得出的比對與BAliBASE中的標準比對進行比較，與標準比對中的核心塊（Core Block）相符合的堿基對的個數占整個核心塊的百分比。 表1測試結果 對于相似程度小于30%的序列集，絕大多數的算法都不能得到正確的結果，所以我們通常將其稱為是序列比對中的模糊區（Twilight Zone）。而本文的算法對于模糊區中的序列集進行了較為正確的比對，但是在序列的長度及數量增加時，算法的準確性會降低。 實驗顯示，分治策略和蟻群算法相結合求解多重序列比對問題克服了單獨使用AntAlign算法不能夠對較長序列進行較好比對的缺點，改進了長序列比對的準確性，而且減少了計算時間。一般情況下，Antmsa 及Divideantmsa算法在1 000代以內即可收斂得到較優解。對于序列個數為10、長度從100~800的測試數據，我們對Antmsa算法求得較優解所需的計算時間進行了統計，與同樣基于進化算法的SAGA算法相比，Antmsa算法在計算時間上比SAGA減少了95%~99%。 由圖4和圖5所示的結果可以看出，當序列長度增加時，算法的計算時間增加較慢；而當序列個數增加時，算法的計算時間增加較快，這是由于序列個數增加時，必須增加迭代次數才能得到較理想的解。 6結論 本文提出了一種解決多重序列比對的蟻群算法，利用了人工螞蟻逐個選擇各個序列中字符進行配對。在算法中，螞蟻根據信息素、字符匹配得分以及位置偏差等信息決定選擇各序列中字符的概率，通過信息素的更新與調節相結合的策略，以及參數的動態自適應調節方法，較為有效地解決了局部收斂的問題，加強了算法尋求全局最優解的能力。在該算法的基礎上，我們還提出了基于分治策略的多序列比對蟻群求解算法，不但減少了計算時間，而且顯著改善了算法所求得的解的質量。另外，蟻群算法的一個特點是易于并行化，基于蟻群算法的多重序列比對方法可以用簡單的策略實現算法的并行化，從而降低了算法的運算時間，提高了求解效率。 參考文獻： ［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)， 女， 碩士研究生，主要研究方向為生物計算和并行算法設計；陳崚（1951）， 男， 教授， 博導，主要研究方向為算法設計和并行計算。 注:本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文
