多序列比對

把兩個以上字元序列對齊，逐列比較其字元的異同，使得每一列的字元儘可能一致，以發現其共同的結構特徵的方法稱為多序列比對。多序列比對問題是雙序列比對問題的推廣。

多序列比對的目標是使得參與比對的序列中有儘可能多的列具有相同的字元，即，使得相同殘基的位點位於同一列，這樣以便於發現不同的序列之間的相似部分，從而推斷它們在結構和功能上的相似關係，主要用於分子進化關係，預測蛋白質的二級結構和三級結構、估計蛋白質摺疊類型的總數，基因組序列分析等。

基本介紹

• 中文名：多序列比對
• 外文名：multiple sequence alignment
• 專業：生物信息學

背景及意義

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

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

定義

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

分類

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

手工比對方法

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

漸進法

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

同步法

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

算法複雜性

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

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

步驟

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

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

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

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