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

 tcctctgcctctgccatcat---caaccccaaagt
 |||| ||| ||||| |||||   ||||||||||||
 tcctgtgcatctgcaatcatgggcaaccccaaagt

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

術語「序列比對」也指構建上述比對或在潛在的不相關序列的數據庫中尋找significant alignments。

比對方法

編輯

對於很短或非常相似的序列,我們可以人工進行比對。然而,在很多問題中,我們需要對非常長的序列進行比對,這是單靠人類的努力所不能解決的。在這種情況下,我們通過構造算法來進行高效的序列比對,有時還需要對最終結果進行調整,因為有些結果難以通過算法表達出來(特別是核苷酸序列)。序列比對的計算方法一般分為兩類:全局性比對(global alignments)和局部比對(local alignments)。計算一個全局性的路線,是一個全局優化的形式,其強制按照整個長度的所有查詢序列對齊。與此相反,局部比對只確定局部的相似而整個長序列卻往往大相逕庭。局部比對往往是可取的,但可能更難以計算的,因為還有來自確定其他相似區域的挑戰。各種計算算法已應用於序列比對的問題,包括緩慢,但正規的像動態規劃的優化方法和高效率,但不徹底的啟發式算法,或大型數據庫搜索設計的概率方法。

雙序列比對

編輯

雙序列比對方法涉及尋找(局部)最優匹配片斷或蛋白質(氨基酸)或DNA核酸)全局比對。

全局比對

編輯

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

局部比對

編輯

序列比對的重要性

編輯

結構比對

編輯

多序列比對

編輯

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

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

算法

編輯

軟件

編輯

這一方法利用一個預先計算的哈希表作為短序列的索引。給定一個被查詢序列,將根據索引來查詢子序列,從而減少查詢次數和時間。提供一些參數將使該方法更快或更準確。檢索到與檢索序列匹配的模式後,需要進一步使用更加準確和深入的算法。

BLAST利用成對的本地檢索和許多其他方法來提高Smith-Waterman算法的速度。

外部連結

編輯