Blast：快速序列比對工具

一、Blast的基本介紹

Blast是Bioinformatics領域中最常用的序列比對工具，它有助於發現具有相似結構和功能的DNA，RNA和蛋白質序列。

Blast有兩種基本類型：blastp用於蛋白質序列比對，blastn用於核酸序列比對。無論是blastp還是blastn，Blast的基本原理都是基於一個很簡單的思想：兩個序列的相似性可以通過比較它們的k個連續字串（k-mer）來度量。這個k可以是4，5，6，7等等不同的值，也可以通過對BLAST程序中的 -word_size 標誌進行修改以實現自定義的長度。

Blast的核心算法是“分治策略”，該策略將參考序列劃分為多個較短的片段，然後在每個片段上進行比對，最後將所有比對結果進行合併以得到完整的比對結果。這種劃分片段的方式可以大大提高比對的速度。

二、Blast的工作原理

Blast主要分為兩個步驟：預處理和比對。

1. 預處理

在這個步驟中，待比較的序列將進行索引，因此可快速地在數據庫中進行查找。BLAST有兩種預處理方法：生成和存儲基於散列算法的索引（hash-based indices）和生成和存儲基於後綴樹（suffix tree）的索引。

2. 比對

Blast使用兩個主要的參數來概括匹配的相似性和可信度：

• e-value：一個給定比對的期望誤報率，即在搜索數據庫時，具有作為這種比對文本所展示的特徵的隨機打擊數的數量。默認值為10，實際上表示10條誤報比對中有1條正確的比對。
• identity：比對中的匹配百分比。identity的默認值為0.0（百分之零），但實際上是由BLAST程序根據其比對評價準則進行計算的。

Blast的比對算法可以分解為以下步驟：

• 找出每個比對序列的最佳比對。
• 利用預處理階段生成的索引找出匹配的序列。
• 計算最佳比對的e-value和identity值。
• 生成兩個序列的比對結果。

三、Blast的優化

為了進一步提高比對的效率，Blast進行了多項優化。

1. 基於哈希表的比對算法

哈希表是Blast中的關鍵數據結構之一，它用於儲存參考序列和查詢序列中的k-mer，並且使用哈希函數將這些k-mer映射到哈希表上。在查詢時，Blast會在哈希表中搜索與每個查詢序列k-mer匹配的參考序列k-mer。如果匹配成功，則進行進一步的比較。

2. 基於GPU加速的算法

Blast的計算密度較高，可以通過使用GPU進行加速。最近幾年發展了各種基於GPU的Blast加速器，其中包括mdBLAST和CUDABLAST等。

3. 快速多重比對算法

Blast畢竟是單序列比對算法，但是在某些情況下，我們需要將多個序列進行比對。因此，Blast開發了一些快速且準確的多重比對算法，比如MUSCLE，MAFFT和CLUSTAL。

四、Blast的應用

Blast可以在生物研究中用於許多不同的應用，例如：

• 序列相似性搜索：比對兩個或多個序列，找出共性和差異，從而幫助科學家理解它們的結構和功能。
• 基因組注釋：通過比對新的基因組序列與已知的序列數據庫，可以確定新的基因組中的基因和元件。
• 進化研究：比較不同物種的DNA、RNA和蛋白質序列，從而幫助確定它們之間的關係。

五、代碼示例

下面是一個blastn的Python代碼示例：

from Bio.Blast import NCBIWWW
from Bio.Blast import NCBIXML

fasta_string = open("test.fasta").read()

result_handle = NCBIWWW.qblast("blastn", "nt", fasta_string)

blast_record = NCBIXML.read(result_handle)

for alignment in blast_record.alignments:
    for hsp in alignment.hsps:
        print('****Alignment****')
        print('sequence:', alignment.title)
        print('length:', alignment.length)
        print('bit Score:', hsp.score)
        print('e value:', hsp.expect)
        print(hsp.query)
        print(hsp.match)
        print(hsp.sbjct)