序列比對

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

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

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

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

比對方法

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

雙序列比對

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

全局比對

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

局部比對

序列比對的重要性

結構比對

多序列比對

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

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

算法

軟件

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

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