前言

Blast演算法的全稱是(Basic Local Alignment Search Tool)，中文叫做基本局部相似性比對搜索工具，在1990年由Altschul等人提出的雙序列局部比對演算法，是一套在蛋白質資料庫或DNA資料庫中進行相似性比較的分析工具。Blast程序能迅速與公開資料庫進行相似性序列比較。BLAST結果中的得分是對相似性的統計說明。還有，Blast演算法是一種啟發式的演算法。

為什麼需要Blast?

這是因為傳統的基於動態規劃的局部性比對性演算法例如常見的Smith–Waterman採用的是精確的序列比對，也就是演算法得到的是比對序列的局部最優解，雖然有著較好的比較結果，但是對於長度為n和m的兩個待比較序列，局部性比對演算法的時間複雜度有O(mn)，這個時間複雜度對於序列匹配來說代價太大，特別是當序列長度較長的時候。Blast是一種在局部性比對基本上一種近似比對的演算法。它在保持較高精度的情況下可以大大減少程序運行的時間，是大規模序列對比問題一個速度和精確性都可以接受的一個解決方法。因此Blast演算法很適合用於實際場景中。

演算法原理

下面這張圖可以很好地刻畫整個Blast的演算法流程：

1.Filtering

在進行比對之前，我們需要對query的序列進行過濾（通常序列比對是將未知序列與已知的序列進行比對，我們把未知的序列叫做query序列），主要過濾的是低複雜度區域（"Low-complexity region"），也就是序列的一段區域只包含種類很少的鹼基或者氨基酸，即有大量重複，因為這些區域會導致最後的計算得分很高或者混淆Blast的運算。BLAST的實際作法是，它會把這些區域用符號代替，並且在搜索的時候忽略這些符號。蛋白質序列中，就用X符號標示；而DNA序列中，則用N符號標示。低複雜度區域的部分，BLAST是用一個叫做SEG的程序來處理蛋白質序列，而用叫做DUST的程序來處理DNA序列。而且這一步直接就在seeding之前就完成了。

2.Seeding

首先，需要把比對的序列按照一定長度拆分成多個連續『seed words』（通常來說對於蛋白質序列是以三個氨基酸為一個seed word, DNA鹼基序列以11個長度為一個seed word，這個閾值可以自己定義），word的長度越小，最終的比對準確率就越高，所需要的時間也越長。比如對於一個蛋白質序列PQFEFG，設定seed word長度為3，那麼就可以依次形成四個seed word。

3.Matching

Matching步驟就是與參考序列進行索引的過程，因為我們參考序列一般已經導入到資料庫中，並且已經做好了索引了，所以matching這個過程是非常快的，常用的如哈希索引和後綴樹都是非常高效的索引方式，哈希是典型的空間換時間的演算法，而後綴樹面對這種字元也有很好的查詢性能，並且能節省儲存空間。

這樣我們就可以得到每個seed word在參考比對序列對應的位置。

4.Extending

這個步驟是整個Blast演算法裡面最耗時的，主要思想就是希望把匹配得到的seed word延伸成更長的片段，同時，計算延伸後的得分，當得分小於指定的閾值，停止延伸。如下圖所示，我們知道最優的匹配結果和主對角線方向是平行的，因此我們沿著主對角線方向進行雙方向的延伸，直到打分低於一定的閾值停止，我們將最後的比對結果叫做高分片段對（high-scoring segment pair, HSP），這裡延伸的方法和Smith-Waterman演算法基本一致，就是只計算MATCH的得分，因為Blast初始版本是不允許有GAP的。

當延伸的得分在下降的時候，我們就選擇停止：

最後，我們計算出每個seed Word的HSP得分，並且排序，選取TOP作為候選，通過最後的顯著性分析，得到最終結果。

5.顯著性分析

通常HSP序列的顯著性分析可以通過計算E值來確定，E值（Expect score）計算如下：

簡單說，m是資料庫長度，n是query的長度，S是HSP分數，其他兩個參數是修正係數，那麼這個E值有什麼用呢？通過上面的公式，簡單理解就是，E值衡量了在隨機情況下，資料庫存在的比當前匹配分數更好的比對的數目。聽起來有點繞口，我理解就是，假如，我有一個隨機生成的seed word AAA，那麼它也有一定概率在資料庫找到對應的索引，並且計算出一個HSP的得分，但是這個得分是由資料庫中對應索引分布決定的，也就是常見的比對更加可靠，我們不希望我們的seed word是一個不可靠的seed，因此我們利用E值來計算統計意義上的均值，來衡量這個seed的可靠程度，比如，E=10就意味著會有10個隨機的匹配獲得與當前比對相等或者更高的分數。

最後通過設定E值過濾掉不合理的HSP比對序列，最後就可以得到最終比對的結果。

以上就是Blast演算法的基本原理。

歡迎大家關注我的知乎專欄：從零開始生物信息學

相同內容也可以關注我的微信公眾號: 壹讀基因：


推薦閱讀：
相关文章