啟發式算法是一種來自於經驗的算法，區別於有精確數學推理的算法。
blast的啟發式算法源於一種什麼樣的經驗呢？下面的視頻也許能給你一些啟發。
在學習blast啟發式算法之前， 我們首先了解一下使用exact local alignment算法到資料庫中查找特定序列的過程。下圖左側，一條是query sequence，另一條是來自於database sequence的序列；右側是local alignment需要的打分規則。
根據打分規則和Smith-waterman recursion，我們得到了exact local alignments結果。下圖是兩個比對序列的dynamic programming array。
根據上圖， 通過回溯，我們得到如下的exact local alignment結果。
根據dynamic programming array 計算局部比對結果的時間與query和target database sequence的序列長度的乘積成正比。隨著大資料庫的出現， 例如GenBank， 到資料庫查找特定序列就需要更快的算法。
Basic local alignment search tool使用的就是一種比smith-waterman更快的算法，該算法速度比較快，但是不能保證精確性。
而smith-waterman算法雖然花費時間比較長，但是能夠保證結果的精確性。
Indexation
blast和其他速度比較快的aligner，mapper使用的核心技術是indexation。indexation是一種在字典中查找words的方法。在這裡， words指的是k-mer, 一個k-mer就是一條長度為k的序列。
在這裡我們使用長度為3的k-mer：
在blast第一步， 生成資料庫中所有序列的k-mer， 並建立索引。
這些k-mer隨後和query sequence的k-mer進行比對，從中篩選出比對分值大於等於某個閾值的所有比對。
Seeding
首先，介紹一個縮寫的含義。HSSP(high-scoring segment pair)：來自query sequence的k-mer和來自database sequence的k-mer之間無gap的一個高分比對結果。那麼什麼樣的比對結果算是高分的比對結果呢？這就需要定一個閾值，也就是HSSP threshold。
同時比對還需要一個記分的規則，local alignment都需要的一個規則。這裡用的記分規則和閾值如下：
接下來就是通過k-mer比對確定HSSP的過程，具體過程如下所示：
下表就是查找到的HSSP：
對應到dynamic programming array中的結果如下：
上述過程被稱為seeding。
Extension
extension是一個在seed處通過gap local alignment進行擴展的過程，當比對的分值小於等於某個閾值時，擴展終止。
小結：blast過程中使用到的主要參數：
word length,
HSSP threshold,
extension threshold。