序列比對
| 序列比對 |
|
中文名: 序列比對 外文名: sequence alignment 理論基礎: 進化學說 用 途: 語言進化的研究 重要性: 對算法的研究具有非常重要的意義 |
序列比對，指為確定兩個或多個序列之間的相似性以至於同源性，而將它們按照一定的規律排列。
將兩個或多個序列排列在一起，標明其相似之處。序列中可以插入間隔（通常用短橫線「-」表示）。對應的相同或相似的符號（在核酸中是A, T（或U）, C, G，在蛋白質中是氨基酸殘基的單字母表示）排列在同一列上。
這一方法常用於研究由共同祖先進化而來的序列，特別是如蛋白質序列或DNA序列等生物序列。在比對中，錯配與突變相應，而空位與插入或缺失對應。序列比對還可用於語言進化或文本間相似性之類的研究。
術語「序列比對」也指構建上述比對或在潛在的不相關序列的數據庫中尋找significant alignments。
目錄
序列比對、全局比對、局部比對、多重序列比對、blast算法基礎
以下我會詳細描述序列比對（alignment）的概念，包括全局比對、局部比對、雙重序列比對、多重序列比對、基因組比對、blast的算法基礎和思想。
序列比對是將兩個或多個序列排列在一起，標明其相似之處。使用間隔表示未比對上，比對上的相同或相似的符號排列在同一列上。序列比對是生物信息學以及基因組學
與進化的基礎之一，其基本思想是：在生物學中普遍存在的序列決定結構、結構決定功能的規律，通過將核酸序列或者蛋白質序列的一級結構看成由基本字符構成的字符串，通過序列比對我們可以找到相似的序列並由此發現生物序列中的功能、結構和進化信息。
全局比對：全局比對是指將參與比對的兩條序列裡面的所有字符進行比對。全局比對在全局範圍內對兩條序列進行比對打分，找出最佳比對，主要被用來尋找關係密切的序列。其可以用來鑑別或證明新序列與已知序列家族的同源性，是進行分子進化分析的重要前提。其代表是Needleman-Wunsch算法。
局部比對：與全局比對不同，局部比對不必對兩個完整的序列進行比對，而是在每個序列中使用某些局部區域片段進行比對。其產生的需求在於、人們發現有的蛋白序列
雖然在序列整體上表現出較大的差異性，但是在某些局部區域能獨立的發揮相同的功能，序列相當保守。這時候依靠全局比對明顯不能得到這些局部相似序列的。其次，在真核生物的基因中，內含子片段表現出了極大變異性，外顯子區域卻較為保守，這時候全局比對表現出了其局限性，無法找出這些局部相似性序列。其代表是Smith-Waterman局部比對算法。
雙重序列比對：雙序列比對是指對兩條序列M和N進行比對，找到其相似性關係，這種尋找生物序列相似性關係的過程被稱為雙序列比對。其算法可以主要分成基於全局比對的Needleman-Wunsch算法和基於局部比對的Smith-Waterman局部比對算法
多重序列比對：多序列比對是雙序列比對推廣，即把兩個以上字符序列對齊，逐列比較其字符的異同，使得每一列字符儘可能一致，以發現其共同的結構特徵的方法稱為多序列比對。多序列比對算法可以分成漸進法和同步法。其可以發現不同的序列之間的相似部分，從而推斷它們在結構和功能上的相似關係，主要用於分子進化關係，預測蛋白質的二級結構和三級結構、估計蛋白質摺疊類型的總數，基因組序列分析等。
基因組比對：是多序列比對的一種特例，指對基因組範圍內的序列信息進行比對的過程。通過對不同親緣關係物種的基因組序列進行比較，能夠鑑定出編碼序列、非編碼調控序列及給定物種獨有的序列。而基因組範圍之內的序列比對，可以了解不同物在核苷酸
組成、同線性關係和基因順序方面的異同，進而得到基因分析預測與定位、生物系統發生進化關係等方面的信息。
BLAST：BLAST[1]（Basic Local Alignment Search Tool）是在在1990年由Altschul等人提出的雙序列局部比對算法，是一套在蛋白質數據庫或DNA數據庫中進行相似性比較的分析工具。BLAST是一種啟發式算法，用於在大型數據庫中尋找比對序列，是一種在局部比對基礎上的近似比對算法，可以在保持較高精度的情況下大大減少程序運行的時間。
算法思想描述：
雙重序列比對主要分成以Needleman-Wunsch算法為代表的全局比對和以Smith-Waterman局部比對算法為代表的局部比對，BLAST是局部比對的一種推廣。多重比對算法可以主要分成動態規划算法、隨機算法、迭代法和漸進比對算法。
（1）雙重序列比對：
Needleman-Wunsch算法：該算法是基於動態規劃思想的全局比對的基本算法，動態規劃的比對算法的比對過程可以用一個以序列S為列，T為行的(m+1)×(n+1)的二維矩陣來表示，用sigma表示置換矩陣，則上述二維矩陣中的每個單元代價值由如下公式遞歸計算：
在計算完矩陣後，從矩陣的右下角單元到左上單元回溯最佳路徑（用箭頭表示），根據最佳路徑給出兩序列的比對結果。其中，斜箭頭表示2個殘基匹配，水平箭頭表示在序列S的相應位置插入一個空位，垂直方向的箭頭表示在序列T的相應位置插入一個空位。示意圖如下：
Smith-Waterman算法：該算法是一種用來尋找並比較具有局部相似性區域的動態規划算法，這種算法適用於親緣關係較遠、整體上不具有相似性而在一些較小的區域上存在局部相似性的兩個序列。該算法的基本思想是：使用迭代方法計算出兩個序列的相似分值，存在一個得分矩陣
M中，然後根據這個得分矩陣，通過動態規劃的方法回溯找到最優的比對序列。與全局比對相比，這種算法的改變是把矩陣單元值為負者一律取為0，這是因為分值為負的比對喪失了比對的生物學意義，因此把得分為負值的子序列丟棄。述二維矩陣中的每個單元代價值由如下公式遞歸計算：
BLAST: BLAST算法的基本思想是通過產生數量更少的但質量更好的增強點來提高比對的速度。算法的原理主要分為以下五步：（1）過濾：首先過濾掉低複雜度區域，即含有大量重複的序列；（2）Seeding：將Query序列中每k個字組合成一個表，即將一個序列拆分成多個連續的『seed words』（通常蛋白質k=3，核酸k=11）；（3）比對：列出我們所關心的所有可能的字組，再配合置換矩陣給出高分值的字組並組織成快速搜索樹結構或者哈希索引，因此此步驟可以快速搜索出大數據集中的所有匹配序列，找到每個seed words在參考序列中的位置；（4）延伸：當找到seed words的位置後，接下來需要將seed word延伸成長片段，延伸過程中，得分值也在變化，當得分值小於閾值時即停止延伸，最後得到的片段成為高分片段對，HSP（High-scoring segment pair）；（5）顯著性分析，最後我們使用如下公式計算E值，E值衡量了在隨機情況下，數據庫存在的比當前匹配分數更好的比對的數目，因此可以用該值作為指標評價HSP比對序列的可信度[2,3]。
其中，m是數據庫長度，n是query的長度，S是HSP分數，其他兩個參數是修正係數。
（2）多重序列比對
動態規划算法：其基本思想是將一個二維的動態規劃矩陣擴展到三維或者多維，多序列比對的積分是n個序列中兩兩進行比對所得積分之和。矩陣的維度反映了參與比對的序列數。這種方法對計算資源要求比較高[6]。
隨機算法：主要包括遺傳算法和模擬退火算法，遺傳算法是一類借鑑生物界進化規律演化來的全局意義上的自適應隨機搜索方法。當用遺傳算法進行生物序列
分析時，每一代包含固定數量的個體，這些個體用他們的適應度來評價。變異則模擬了生物進化過程中的偶然殘基突變現象。對產生的新一代群體進行重新評價、選擇、交叉、變異，如此循環往復，使群體中最優個體的適應度不斷提高，直到達到一個閾值，算法結束。模擬退火的基本思想是用一物質系統的退火過程來模擬優化問題的尋優方法，當物質系統達到最小能量狀態時，優化問題的目標函數也相應地達到了全局最優解。這兩種方法都是對構造好的目標函數進行最優解搜索，但實際比對效果並不好[6,7]。
迭代法：迭代法的代表是Muscle[8], Muscle是一個新的漸進比對和迭代比對的綜合算法，主要由兩部分構成，第一部分是迭代漸進比對：第一次漸進比對的目的是快速產生一個多序列比對而不強調準確率，以此為基礎再對漸進比對進行改良。經過兩次漸進比對，形成一個相對準確的多序列比對；第二部分是迭代比對：該過程類似於Prrp算法[9]，即通過不斷的迭代，逐步優化最終比對結果。其主要特點包括：使用kmer counting進行快速的距離測量，使用一個新的圖譜比對打分函數進行漸進比對，使用依賴於數的有限分隔進行細化。
漸進比對算法：該算法以Feng和Doolittle提出的最為經典[10]。漸進比對算法的基本思想是迭代地利用兩序列動態規劃比對算法,先由兩個序列的比對開始，逐漸添加新序列，直到所有序列都加入為止。但是不同的添加順序會產生不同的比對結果。確定合適的比對順序是漸進比對算法的一個關鍵問題。通常，整個序列的比對應該從最相似的兩個序列開始，由近至遠逐步完成。作為全局多序列比對的漸進比對算法有個基本的前提假設:所有要比對的序列是同源的，即由共同的祖先序列經過一系列的突變積累，並經自然選擇遺傳下來的，分化越晚的序列之間相似程度就越高。因此，在漸進比對過程中，應該對近期的進化事件比遠期的進化事件給予更大的關注。由於同源序列
是進化相關的，因此可以按着序列的進化順序，即沿着系統發育樹(指導樹)的分支，由近至遠將序列或已比對序列按雙序列比對算法逐步進行比對，重複這一過程直到所有序列都己添加到這個比對中為止[10]。其三個步驟為：（1）利用雙序列比對方法對所有的序列進行兩兩比對，得到相似性分值；（2）利用相似性矩陣
（或距離矩陣）產生輔助導向樹；（3）根據導向樹進行漸進比對。漸進比對算法是最常用、簡單又有效的啟發式多序列比對方法，它所需時間較短、所占內存較小，其算法很多，主要有CLUSTAL W, T-Coffee和DiAlign等，其中 CLUSTAL W應用最廣泛。
應用：
類型+應用
雙重序列對比：判斷兩個序列的同源性和一致性。（1）全局多序列比對可以鑑別或證明新序列與己有序列家族的同源性;幫助預測新蛋白質序列的二級和二級結構，是進行分子進化分析的重要前提。適合序列相似性較高，序列長度近似時的比對；（2）局部比對考慮序列部分區域的相似性。局部多序列比對可以用來刻畫蛋白質家族和超家族。適合於未知兩個序列相似程度的，可能存在一些片段極其相似而另一些片段相異的序列比對情況。
多重序列比對：多重比對經常用來研究序列間的進化關係，構建進化樹；探究序列間的保守性。主要用於分子進化關係，預測蛋白質的二級結構和三級結構、估計蛋白質摺疊類型的總數，基因組序列分析等。
基因組比對：通過對不同親緣關係物種的基因組序列進行比較，能夠鑑定出編碼序列、非編碼調控序列及給定物種獨有的序列。而基因組範圍之內的序列比對，可以了解不同物在核苷酸組成、同線性關係和基因順序方面的異同，進而得到基因分析預測與定位、生物系統
發生進化關係等方面的信息。[1]
背景及簡介
序列比對是生物信息學
的基本組成和重要基礎。序列比對的基本思想是，基於生物學中序列決定結構，結構決定功能的普遍規律，將核酸序列和蛋白質一級結構上的序列都看成由基本字符組成的字符串，檢測序列之間的相似性，發現生物序列中的功能、結構和進化的信息。
序列比對的理論基礎是進化學說，如果兩個序列之間具有足夠的相似性，就推測二者可能有共同的進化祖先，經過序列內殘基的替換、殘基或序列片段的缺失、以及序列重組等遺傳變異過程分別演化而來。序列相似和序列同源是不同的概念，序列之間的相似程度是可以量化的參數，而序列是否同源需要有進化事實的驗證。在殘基－殘基比對中，可以明顯看到序列中某些氨基酸殘基比其它位置上的殘基更保守，這些信息揭示了這些保守位點上的殘基對蛋白質的結構和功能是至關重要的，例如它們可能是酶的活性位點殘基，形成二硫鍵的半胱氨酸殘基，與配體結合部位的殘基，與金屬離子結合的殘基，形成特定結構motif的殘基等等。但並不是所有保守的殘基都一定是結構功能重要的，可能它們只是由於歷史的原因被保留下來，而不是由於進化壓力而保留下來。因此，如果兩個序列有顯著的保守性，要確定二者具有共同的進化歷史，進而認為二者有近似的結構和功能還需要更多實驗和信息的支持。通過大量實驗和序列比對的分析，一般認為蛋白質的結構和功能比序列具有更大的保守性，因此粗略的說，如果序列之間的相似性超過30%，它們就很可能是同源的。
值得注意的是，在分子生物學中，DNA或蛋白質的相似性是多方面的，可能是核酸或氨基酸序列的相似，可能是結構的相似，也可能是功能的相似。一級結構序列相似的分子在高級結構和功能上並不必然有相似性，反之，序列不相似的分子，可能摺疊成相同的空間形狀，並具有相同的功能。一般的序列比對主要是針對一級結構序列上的比較。
在生物信息處理中，我們希望找出兩條序列S和T之間具有的某種相似性關係，這種尋找生物序列相似性關係的算法就是雙序列比對算法。我們通常利用兩個序列之間的字符差異來測定序列之間的相似性，兩條序列中相應位置的字符如果差異大，那麼序列的相似性低，反之，序列的相似性就高。
多序列比對
把兩個以上字符序列對齊，逐列比較其字符的異同，使得每一列字符儘可能一致，以發現其共同的結構特徵的方法稱為多序列比對。多序列比對問題其實是雙序列比對問題的推廣。
多序列比對的目標是使得參與比對的序列中有儘可能多的列具有相同的字符，即，使得相同殘基的位點位於同一列，這樣以便於發現不同的序列之間的相似部分，從而推斷它們在結構和功能上的相似關係，主要用於分子進化關係，預測蛋白質的二級結構和三級結構、估計蛋白質摺疊類型的總數，基因組序列分析等。
由於多序列比對能夠揭示雙序列比對所不能發現的序列微弱相似性、序列模式和功能位點，因而對蛋白質和核酸序列的結構、功能和進化研究更加有用。
全局比對
全局比對
是指將參與比對的兩條序列裡面的所有字符進行比對。 全局比對主要被用來尋找關係密切的序列。由於這些序列也都很易通過本地比對方法找到，現在全局比對也有些被認為只是一種技巧。另外，全局比對在應用於分子進化時也有些問題（比如domain shuffling -見下)，這也限制了這種方法的可用性。
局部比對
1981年，由F. Smith 和 M.Waterman首次提出局部比對算法，動態規劃方法通過較少的改動便可以用來識別匹配的子序列， 並且忽略匹配區域之前或之後的失配和空位;局部比對時，表中小於零的位置用零代替。主要用來考察兩序列的某些特殊片段。
算法過程
實際操作中利用計算機程序實現序列比對的基本算法。序列比對不僅需要考慮子序列之間的匹配，而且需要對整個序列進行比較。也就是說，必須考慮兩個序列中所有殘基的匹配。這就意味着，不可能使所有殘基都能嚴格匹配。在這種情況下，序列比對中確定空位的過程變得十分複雜。
在進行序列兩兩比對時，有兩方面問題直接影響相似性分值：取代矩陣和空位罰分。
取代矩陣
粗糙的比對方法僅僅用相同/不同來描述兩個殘基的關係，顯然這種方法無法描述殘基取代對結構和功能的不同影響效果，纈氨酸對異亮氨酸的取代與穀氨酸對異亮氨酸的取代應該給予不同的打分。因此如果用一個取代矩陣
來描述氨基酸殘基兩兩取代的分值會大大提高比對的敏感性和生物學意義。雖然針對不同的研究目標和對象應該構建適宜的取代矩陣，但國際上常用的取代矩陣有PAM和BLOSUM等，它們來源於不同的構建方法和不同的參數選擇，包括PAM250、BLOSUM62、BLOSUM90、BLOSUM30等。對於不同的對象可以採用不同的取代矩陣以獲得更多信息，例如對同源性較高的序列可以採用BLOSUM90矩陣，而對同源性較低的序列可採用BLOSUM30矩陣。
空位罰分
空位罰分是為了補償插入和缺失對序列相似性的影響，由於沒有什麼合適的理論模型能很好地描述空位
問題，因此空位罰分缺乏理論依據而更多的帶有主觀特色。一般的處理方法是用兩個罰分值，一個對插入的第一個空位罰分，如10－15；另一個對空位的延伸罰分，如1－2。對於具體的比對問題，採用不同的罰分方法會取得不同的效果。
對於比對計算產生的分值，到底多大才能說明兩個序列是同源的，對此有統計學方法加以說明，主要的思想是把具有相同長度的隨機序列進行比對，把分值與最初的比對分值相比，看看比對結果是否具有顯著性。相關的參數E代表隨機比對分值不低於實際比對分值的概率。對於嚴格的比對，必須E值低於一定閾值才能說明比對的結果具有足夠的統計學顯著性，這樣就排除了由於偶然的因素產生高比對得分的可能。
序列比對的統計檢驗
序列比對實際上是根據特定數學模型找出序列之間最大匹配殘基數。而序列比對數學模型一般用來描述序列中每一個子字符串之間的匹配情況。通過改變某些參數可以得到不同比對結果，例如空位罰分值大小。此外，序列長度差異和字母表複雜度也會影響比對結果。合理調節參數，會減少空位數目，得到較好的結果，而放寬對空位罰分的限制，理論上任意序列都可以得到某個對比結果。因此序列比對的結果並不能作為兩者之間一定存在同源關係的依據。
常用序列比對程序通常給出一些統計值，用來表示結果的可信度。BLAST程序中使用的統計值由概率p和期望值e。概率p表示比對結果得到的分數值的可信度。一般來說，p越接近於0，則比對結果的可信度越大。期望值e描述搜索某一特定數據庫時，隨機出現的匹配序列數目。
重要性
生物信息學的研究重點主要體現在基因組學和蛋白質學兩方面,具體地說就是從核酸和蛋白質序列出發, 分析序列中表達結構和功能的生物信息。生物信息學的基本任務是對各種生物分析序列進行分析, 也就是研究新的計算機方法, 從大量的序列信息中獲取基因結構、功能和進化等知識。而在序列分析中, 將未知序列同已知序列進行相似性比較是一種強有力的研究手段,從序列的片段測定, 拼接, 基因的表達分析, 到RNA和蛋白質的結構功能預測。物種親緣樹的構建都需要進行生物分子序列的相似性比較。生物信息學中的序列比對算法的研究具有非常重要的理論意義和實踐意義。