多序列比對

雙序列比對 ^[2]  是序列分析的基礎·然而，對於構成基因家族的成組的序列來説，我們要建立多個序列之間的關係，這樣才能揭示整個基因家族的特徵·多序列比對在闡明一組相關序列的重要生物學模式方面起着相當重要的作用。

多序列比對有時用來區分一組序列之間的差異,但其主要用於描述一組序列之間的相似性關係,以便對一個基因家族的特徵有一個簡明扼要的瞭解.與雙序列比對一樣,多序列比對的方法建立在某個數學或生物學模型之上。因此,正如我們不能對雙序列比對的結果得出"正確或錯誤"的簡單結論一樣,多序列比對的結果也沒有絕對正確和絕對錯誤之分,而只能認為所使用的模型在多大程度上反映了序列之間的相似性關係以及它們的生物學特徵。.

為了便於描述，我們對多序列比對 ^[3]  過程給出下面的定義。把多序列比對看作一張二維表，表中每一行代表一個序列，每一列代表一個殘基的位置。將序列依照下列規則填入表中：（a）一個序列所有殘基的相對位置保持不變；（b）將不同序列間相同或相似的殘基放入同一列，即儘可能將序列間相同或相似殘基上下對齊。我們稱比對前序列中殘基的位置為絕對位置。相應地，我們稱比對後序列中殘基的位置為相對位置。顯然，同一列中所有殘基的相對位置相同，而每個殘基的絕對位置不同，因為它們來自不同的序列。需要説明的是，絕對位置是序列本身固有的屬性，或者説是比對前的位置，而相對位置則是經過比對後的位置，也就比對過程賦予它的屬性。

目前,構建多序列比對模型的方法大體可以分為以下三類：

手工比對方法在文獻中經常看到。因為難免加入一些主觀因素，手工比對通常被認為有很大的隨意性。其實，即使用計算機程序進行自動比對，所得結果中的片面性也不能予以忽視。在運行經過測試並具有比較高的可信度的計算機程序基礎上，結合實驗結果或文獻資料，對多序列比對結果進行手工修飾，應該説是非常必要的。

漸進比對思想對於多個序列兩兩比對並且根據不同策略構建距離矩陣，反映序列之間的遠近關係，然後根據距離矩陣計算產生系統進化指導樹，對關係密切的序列進行加權，然後從最緊密的兩條序列開始，逐步引入臨近的序列，並不斷重新構建比對，直到所有序列都被加入為止。根據不同距離策略，主要算法有：Feng-Doolittle算法及以其為基礎的改進程序包CLUSTER W,Multal，Pileup。

同步法即同時比對所有序列。首先，確定某個目標函數，使得目標函數反映出每個多序列比對的質量。目標函數值越高，比對性能越好。對於序列數目多的情況下，在所有可能的多序列比對中，找出使得目標函數值最佳的比對，是一個NP-Complete問題。目前，由同時比對10條序列的MSA程序包，還有應用於多序列比對問題的隨機啓發式算法，模擬退火 ^[4]  算法，圖像取樣，遺傳算法 ^[5]  等。

多序列比對的計算量相當可觀，因此有必要分析一下算法複雜性 ^[6]  。雙序列比對所需要的計算時間和內存空間與這兩個序列的長度有關，或者説正比於這兩個序列長度的乘積。三序列比對則可以理解為將雙序列比對的兩維空間擴展到三維，即在原有二維平面上增加一條座標軸，這樣，算法複雜性就變成了三個長度的乘積。

隨着序列數量的增加，算法複雜性也不斷增加，對n個序列進行比對時，算法複雜性相應等於n個長度的乘積。顯然，隨着序列數量的增加，序列比對的算法複雜性按指數規律增長。

多序列比對一般通過3個步驟完成：

（1）兩兩進行雙重比對。

（2）生成一系統樹圖（dendrogram） ^[7]  ，將序列按相似性大致地分組。

（3）使用系統樹圖作為引導，產生出最終的多序列比對結果。