生物資訊學

生物資訊學中（生物信息學）， BLAST( Basic Local Alignment Search Tool") 它是一個用來比對生物序列的一級結構（如不同蛋白質的氨基酸序列或不同基因的DNA序列）的演演算法。已知一個包含若干序列的資料庫，BLAST可以讓研究者在其中尋找與其感興趣的序列相同或類似的序列。例如如果某種非人動物的一個以前未知的基因被發現，研究者一般會在人類基因組中做一個BLAST搜索來確認人類是否包含類似的基因（通過序列的相似性）。BLAST演演算法以及實現它的程序由美國國家生物技術信息中心（NCBI）的Eugene Myers、Stephen Altschul、Warren Gish、David J. Lipman及Webb Miller博士開發的。

BL徠AST是一個被廣泛使用於分析生物資訊的程式，因為它可以兼顧我們在做搜尋時的速度以及搜尋結果的精確度。因為當我們所要搜尋的目標資料庫非常龐大的時候，速度就變成一項很需要考量的因素。在像BLAST和FASTA這些快速演演算法被開發之前，我們是使用動態規劃演演算法來作資料庫的序列搜尋，這真的非常的耗時。BLAST使用啟髮式搜索來找出相關的序列，在速度上比完全只使用動態規劃大約快上50倍左右，不過它不像動態規劃能夠保證搜尋到的序列（Database sequence）和所要找的序列（Query sequence）之間的相關性，BLAST的工作就是儘可能找出資料庫中和所要查詢的序列相關的資訊而已，精確度稍微低一點。此外，BLAST比FASTA更快速，因為BLAST只對比較少出現或是較重要的一些關鍵字作更進一步的分析，而FASTA是考慮所有共同出現在所要搜尋的序列和目標序列的字。從下面介紹的演演算法可以更進一步的了解。

這邊我們以蛋白質對蛋白質序列搜尋所用的程式BLASTP之實做的步驟，來了解BLAST這程式的主要思想。移除Query序列中之低複雜度以及有串接重複現象的區域低複雜度是指由很少種類的元素（如氨基酸）所組成的一個區域；而串接重複現象是指在一個Query序列中，有兩段串連的區域它們組成的方式一模一樣。這兩種在序列中的區域可能會讓BLAST找出一些雖然分數夠高，但是其實和Query序列並不相關之序列，所以在我們執行搜尋之前，要先把Query序列中的這兩種區域濾掉。BLAST的實際作法是，它會把這些區域用符號代替，並且在搜索的時候忽略這些符號。蛋白質序列中，就用X符號標示；而DNA序列中，則用N符號標示。低複雜度區域的部份，BLAST是用一個叫做SEG的程式來處理蛋白質序列，而用叫做DUST的程式來處理DNA序列。另一方面，，蛋白質序列中之串接重複現象的區域則是使用XNU來處理。將Query序列中每k個字的組合做成一個表以k=3為例（DNA序列中，我們則常以k=11為例），我們"依序"將Query序列中每3個字的組合視為一個字組，並將這些字組列在一張字組表上，直到Query序列中最後一個字也被收入進表上為止。由圖一可以更清楚的了解整個作法。