生物資訊學（2）——雙序列比對之Smith-Waterman(SW)算法詳解

生物資訊學系列部落格索引

生物資訊學（1）——雙序列比對之Needleman-Wunsch(NW)算法詳解及C++實作

生物資訊學（2）——雙序列比對之Smith-Waterman(SW)算法詳解

生物資訊學（3）——雙序列比對之BLAST算法簡介

生物資訊學（4）——多序列比對之CLUSTAL算法詳解及C++實作

生物資訊學（5）——基于CUDA的多序列比對并行算法的設計與代碼實作

1. SW 算法簡介

Smith-Waterman 算法是由 Temple F. Smith 和 Michael S. Waterman 兩人在 1981 年提出來的，是 Needleman-Wunsch 算法的改良版，通過算法的比對，能獲 取到局部最優解。SW 算法罰分規則如下:

SW 算法罰分規則如公式

以罰分規則為基礎，得分矩陣的公式如下，可以看到，和上篇介紹的NW算法相比，最大的改變是，多了一個0。這樣做就可以杜絕得分矩陣中的負數。

擷取得分矩陣後，找全局最大的值，在此點往左上回溯，到0停止，然後根據回溯路徑擷取局部最優解。回溯規則:回溯規則如公式

2. SW算法舉例介紹

給定序列

Seq1 = GGATCGA

Seq2 = GAATTCAGTTA

(1) 初始化打分矩陣

首先将矩陣的第0行與第0列分别用Seq1與Seq2填充，填充時，注意預留出兩個字元，将第二行與第二列的元素置0，如圖所示:

(2) 通過公式建構整個打分矩陣

(3) 回溯

先找到全局最大的值，在此點往左上回溯，到 0 停止

(4) 得出結果

通過回溯規則，建構最終的局部最優解，其中路徑朝向左上，即 MATCH/DISMATCH,路徑朝左為 seq1 出現 INDEL 情況,路徑朝上為 seq2 出現 INDEL 情況，使用 ’-’ 代替。結果如下:最後得出如圖 結果，為局部最優解。

3. 奇怪的内容

問：為什麼SW算法沒有C++實作？

答：問得好！因為我太懶了，我的畢設沒有用到SW算法具體實作，是以無代碼，隻有原了解釋。

4. 總結

SW算法相比較于NW算法，雖然S簡化了計算過程，且是在NW算法的基礎上進行改進，但是其不能擷取到全局最優解，而是隻能擷取到局部最優解。

算法永遠是時間、空間、準确性三者交錯的結合，減少了時間複雜度也許會增加空間複雜度，減少了空間複雜度，也許會增加運作時間。縮短時空複雜度，算法的精度可能會丢失。有時候，我們能承受巨大的記憶體空間，無法容忍運作的速度低下，是以我們會選擇時間複雜度低的算法，有時候我們想優化時空複雜度，對結果沒有偏執的要求，那又是另一種選擇。是以适合使用情況的算法才是好的算法。正如下一篇要介紹的BLAST，其并不確定能找到最優解，但盡力在更短時間内找到足夠好的解。これは人生かもしれません。