序列比對

序列比對（alignment）：為確定兩個或多個序列之間的相似性以至於同源性，而將它們按照一定的規律排列。

將兩個或多個序列排列在一起，表明其相似之處。序列中可以插入間隔（通常用短橫線“-”表示）。對應的相同或相似的符號（在核酸中是A,T（或U）,C,G，在蛋白質中是氨基酸殘基的單字母表示）排列在同一列上。

這一方法常用於研究由共同祖先進化而來的序列，特別是如蛋白質序列或DNA序列等生物序列。在比對中，錯配與突變相應，而空位與插入或缺失對應。序列比對還可用於語言進化或文本間相似性之類的研究。

術語“序列比對”也指構建上述比對或在潛在的不相關序列的資料庫中尋找significantalignments。

序列比對實際上是根據特定數學模型找出序列之間最大匹配殘基數。而序列比對數學模型一般用來描述序列中每一個子字元串之間的匹配情況。通過改變某些參數可以得到不同比對結果，例如空位法分值大小。此外，序列長度差異和字母表複雜度也會影響比對結果。合理調節參數，會減少空位數目，得到較好的結果，而放寬對空位罰分的限制，理論上任意序列都可以得到某個對比結果。因此序列比對的結果並不能作為兩者之間一定存在同源關係的依據。

常用序列比對程序通常給出一些統計值 ，用來表示結果的可信度。BLAST程序中使用的統計值由概率p和期望值e。概率p表示比對結果得到的分數值的可信度。一般來說，p越接近於0，則比對結果的可信度越大。期望值e描述搜索某一特定資料庫時，隨機出現的匹配序列數目。

序列比對的理論基礎是進化學說，如果兩個序列之間具有足夠的相似性，就推測二者可能有共同的進化祖先，經過序列內殘基的替換、殘基或序列片段的缺失、以及序列重組等遺傳變異過程分別演化而來。序列相似和序列同源是不同的概念，序列之間的相似程度是可以量化的參數，而序列是否同源需要有進化事實的驗證。在殘基－殘基比對中，可以明顯看到序列中某些氨基酸殘基比其它位置上的殘基更保守，這些信息揭示了這些保守位點上的殘基對蛋白質的結構和功能是至關重要的，例如它們可能是酶的活性位點殘基，形成二硫鍵的半胱氨酸殘基，與配體結合部位的殘基，與金屬離子結合的殘基，形成特定結構motif的殘基等等。但並不是所有保守的殘基都一定是結構功能重要的，可能它們只是由於歷史的原因被保留下來，而不是由於進化壓力而保留下來。因此，如果兩個序列有顯著的保守性，要確定二者具有共同的進化歷史，進而認為二者有近似的結構和功能還需要更多實驗和信息的支持。通過大量實驗和序列比對的分析，一般認為蛋白質的結構和功能比序列具有更大的保守性，因此粗略地說，如果序列之間的相似性超過30%，它們就很可能是同源的。

全局比對是指將參與比對的兩條序列裡面的所有字元進行比對。全局比對主要被用來尋找關係密切的序列。由於這些序列也都很易通過本地比對方法找到，現在全局比對也有些被認為只是一種技巧。另外，全局比對在應用於分子進化時也有些問題（比如domainShuffling-見下)，這也限制了這種方法的可用性。

1981年，由F.Smith和M.Waterman首次提出局部比對演演算法，動態規劃方法通過較少的改動便可以用來識別匹配的子序列，並且忽略匹配區域之前或之後的失配和空位；局部比對時，表中小於零的位置用零代替。主要用來考察兩序列的某些特殊片段。

全局比對是從頭到尾全程比較，考慮序列的整體相似性。全局多序列比對可以鑒別或證明新序列與已有序列家族的同源性；幫助預測新蛋白質序列的二級和三級結構；是進行分子進化分析的重要前提。局部比對考慮序列部分區域的相似性。局部比對的生物學基礎是：蛋白質功能位點由較短的序列片斷組成，儘管在序列的其它部位可能有插入、刪除或突變，但是這些序列片斷具有相當大的保守性。此時，局部比對往往比全局比對具有更高的靈敏度，其結果更具有生物意義。局部多序列比對可以用來刻畫蛋白質家族和超家族。

生物信息學的研究重點主要體現在基因組學和蛋白質學兩方面，具體地說就是從核酸和蛋白質序列出發,分析序列中表達結構和功能的生物信息。生物信息學的基本任務是對各種生物分析序列進行分析,也就是研究新的計算機方法,從大量的序列信息中獲取基因結構、功能和進化等知識。而在序列分析中,將未知序列同已知序列進行相似性比較是一種強有力的研究手段，從序列的片段測定,拼接,基因的表達分析,到RNA和蛋白質的結構功能預測。物種親緣樹的構建都需要進行生物分子序列的相似性比較。生物信息學中的序列比對演演算法的研究具有非常重要的理論意義和實踐意義。

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

表1多序列比對的定義，表示五個短序列（I-V）的比對結果。通過插入空位，使5個序列中大多數相同或相似殘基放入同一列，並保持每個序列殘基順序不變。

多序列比較對的演演算法複雜性

多序列比對的計算量相當可觀，因此有必要分析以下技術的複雜性。雙序列比對所需要的計算時間和內存空間與這兩個序列的長度有關，或者說正比於這兩個序列長度的乘積，用O（m1m2）表示。其中m1、m2是指兩條序列的長度。三序列比對則可以理解為將雙序列比對的兩維空間擴展到三維，即在原有二維平面上增加一條坐標軸。這樣演演算法複雜性就變成了O（m1m2m3），其中m3表示第三條序列的長度。

隨著序列數量的增加，演演算法複雜性也不斷增加。操作者用O（m1m2m3…mn）表示對n個序列進行比對時的演演算法複雜性，其中mn是最後一條序列的長度。若序列長度相差不大，則可簡化成O（mn），其中n表示序列的數目，m表示序列的長度。顯然，隨著序列數量的增加，序列比對的演演算法複雜性按指數規律增長。

降低演演算法複雜性，是研究多序列比對的一個重要方面。為此，產生了不少很有實用意義的多序列比對演演算法。這些方法的特點是利用啟髮式（Heuristics）演演算法降低演演算法複雜性，以獲得一個較為滿意但並不一定是最優的比對結果，用來找齣子序列、構建進化樹、查找保守序列或序列模板，以及進行聚類（clustering）分析等。有的演演算法將動態規劃和啟發性演演算法結合起來。例如，對所有的序列進行兩兩比對，將所有的序列與某個特定的序列進行比對，根據某種給定的親源樹進行分組比對，等等。必須指出，上述方法求得的結果通常不是最優解，至少需要經過n-1次雙序列比對，其中n為參與比對的序列個數。

多序列比對方法

下面介紹比對採用的幾種常用方法。

手工比對方法

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

多序列比對的軟體已經有許多，其中一些帶有編輯程序。最好的辦法是將自動比對程序和編輯器整合在一起。為了便於進行互動式手工比對，通常使用不同顏色表示具有不同特性的殘基，以幫助判別序列之間的相似性。顏色的選擇十分重要，如果使用不當，看起來不很直觀，就會使比對結果中一些有用的信息丟失。相反，如果選擇得當，就能從序列比對結果中迅速找到某些重要的結構模式和功能位點。例如，如果用某種顏色表示一組高度保守的殘基，則某個序列的某一位點發生突變時，則由於顏色不同，就可以很快找出。顏色的選擇可以根據主觀願望和喜好，但最好和常規方法一致。用來構築三維模型的按時氨基酸殘基組件和三維分子圖形軟體所用的顏色分類方法，比較容易為大家接受（表2）。

表2氨基酸分組方法和代表性顏色

*表中採用的分組方法和用來區分不同組別的顏色與模型構件和三維圖形軟體中所用方法一致。

多序列比對程序的另一個重要用途是定量估計序列間的關係，並由此推斷它們在進化中的親緣關係。可以通過計算完全匹配的殘基數目或計算完全匹配殘基和相似殘基的數目得到這種定量關係。這一方法除了可以大略了解序列間的親緣關係外，也可用來評估比對質量。如果序列的相似性值低於預料值，那麼有可能是序列間親緣關係較遠，也可能是比對中有錯誤之處。

現有的軟體包用的基本上是可用滑鼠點擊的窗口界面，其中序列編輯器位於窗口中央。這樣的軟體包將在以後章節中詳細介紹。

使用這些軟體操作者將會看到，那些長度相仿且相似性程度較高的序列，採用自動比對方法將會得到相當滿意的結果；而當序列長度相差較大而相似性程度較低時，採用自動方法得出的結果則不很理想。此時，手工序列編輯器就接顯得十分有用。通過手工調整，可使結果變得接近實際。此外，採用多種不同的方法進行分析，再將結果綜合，是一種行之有效的方法。為更好地理解多序列比對的原理和規則，應該儘可能學會手工比對的方法，並把比對結果與計算機自動比對得到的結果加以比較。

同步法

同步法實質是把給定的所有序列同時進行比對，而不是兩兩比對或分組進行比對。其基本思想是將一個二維的動態規劃矩陣擴展到三維或多維。矩陣的維數反映了參與比對的序列數。這類方法對於計算機的系統資源要求較高，通常是進行少量的較短的序列的比對。

步進法

這類方法中最常用的就是Clustal，它是由Feng和Doolittle於1987年提出的（Feng和Doolittle，1987）。由於對於實際的數據利用多維的動態規劃矩陣來進行序列的比對不太現實，因此大多數實用的多序列比對程序採用啟髮式演演算法，以降低運算複雜度。Clustal的基本思想是基於相似序列通常具有進化相關性這一假設。比對過程中，先對所有的序列進行兩兩比對並計算它們的相似性分數值，然後根據相似性分數值將它們分成若干組，並在每組之間進行比對，計算相似性分數值。根據相似性分數值繼續分組比對，直到得到最終比對結果。比對過程中，相似性程度較高的序列先進行比對，而距離較遠的序列添加在後面。作為程序的一部分，Clusal可以輸出用於構建進化樹的數據。

Clustal程序有許多版本，CLUSTALW（Thompson等，1994），根據對親緣關係較近的序列間空位情況，確定如何在親緣關係較遠的序列之間插入空位。同樣，相似性較高的序列比對結果中的殘基突變信息，可用於改變某個特殊位置空位罰分值的大小，推測該位點的序列變異性。

Clustal是免費軟體，很容易從網際網路上下載，和其它軟體一起，廣泛用於序列分析。Clustal所支持的數據格式包括EMBL/SwissProt、NBRF/PIR、Pearson/FastA、GCG/MSF，以及Clustal本身定義的格式。它的輸出格式可以是Clustal格式，也可以是可用於GDE、Phylip、GCG等軟體的格式。

主條目：多重序列比對

多序列比對是成對比對的延伸，是為了在一次比對裡面處理多於兩條的的序列。多序列比對方法試圖比對一個指定序列集合裡面的所有序列，這可以幫助確定這些序列的共同區段。進行多序列比對有幾種方法，最常用的一種是Clustal程序集，它使用漸進多序列比對演演算法。Clustal在cladistics中被用來建立進化樹，在PSI-BLAST和HiddenMarkovmodel-(HMM-)中用來建立序列檔案以在序列資料庫中搜索更遠的同源序列。

多序列比對編程實現困難。被歸為NP難題的一種。

實際操作中利用計算機程序實現序列比對的基本演演算法。序列比對不僅需要考慮子序列之間的匹配，而且需要對整個序列進行比較。也就是說，必須考慮兩個序列中所有殘基的匹配。這就意味著，不可能使所有殘基都能嚴格匹配。在這種情況下，序列比對中確定空位的過程變得十分複雜。

在進行序列兩兩比對時，有兩方面問題直接影響相似性分值：取代矩陣和空位罰分。

取代矩陣

粗糙的比對方法僅僅用相同/不同來描述兩個殘基的關係，顯然這種方法無法描述殘基取代對結構和功能的不同影響效果，纈氨酸對異亮氨酸的取代與谷氨酸對異亮氨酸的取代應該給予不同的打分。因此如果用一個取代矩陣 來描述氨基酸殘基兩兩取代的分值會大大提高比對的敏感性和生物學意義。雖然針對不同的研究目標和對象應該構建適宜的取代矩陣，但國際上常用的取代矩陣有PAM和BLOSUM等，它們來源於不同的構建方法和不同的參數選擇，包括PAM250、BLOSUM62、BLOSUM90、BLOSUM30等。對於不同的對象可以採用不同的取代矩陣以獲得更多信息，例如對同源性較高的序列可以採用BLOSUM90矩陣，而對同源性較低的序列可採用BLOSUM30矩陣。

空位罰分

空位罰分是為了補償插入和缺失對序列相似性的影響，由於沒有什麼合適的理論模型能很好地描述空位 問題，因此空位罰分缺乏理論依據而更多的帶有主觀特色。一般的處理方法是用兩個罰分值，一個對插入的第一個空位罰分，如10－15；另一個對空位的延伸罰分，如1－2。對於具體的比對問題，採用不同的罰分方法會取得不同的效果。

對於比對計算產生的分值，到底多大才能說明兩個序列是同源的，對此有統計學方法加以說明，主要的思想是把具有相同長度的隨機序列進行比對，把分值與最初的比對分值相比，看看比對結果是否具有顯著性。相關的參數E代表隨機比對分值不低於實際比對分值的概率。對於嚴格的比對，必須E值低於一定閾值才能說明比對的結果具有足夠的統計學顯著性，這樣就排除了由於偶然的因素產生高比對得分的可能。