史密斯-沃特曼演算法

史密斯-沃特曼演算法的演算法，用於找出兩個核苷酸序列或蛋白質序列之間的相似區域。該演算法的目的不是進行全序列的比對，而是找出兩個序列中具有高相似度的片段。該演算法由坦普爾·史密斯和邁克爾·沃特曼於1981年提出。史密斯-沃特曼演算法是尼德曼-翁施演算法的一個變體，二者都是動態規劃演算法。這一演算法的優勢在於可以在給定的打分方法下找出兩個序列的最優的區域性比對，因此區域性比對成為可能。回溯從分數最高的矩陣元素開始，直到遇到分數為零的元素停止。分數最高的區域性比對結果在此過程中產生。在實際運用中，人們通常使用該演算法的最佳化版本。歷史.生物學上一個基本問題是，一個基因或者蛋白是否和別的基因或者蛋白存在聯絡。蛋白質在序列層次的關聯暗示了其同源性，同時暗示了它們可能有類似的功能。透過分析多個DNA或者蛋白質序列，我們可能會發現一些保守序列和區域。這種基因序列或者蛋白質序列之間關聯性的分析就是透過序列比對來完成的。如今，人們完成了許多不同生物體的基因組分析，獲得了大量的基因和蛋白質序列資料。序列比對能夠向我們揭示某一生物體中蛋白質之間的關聯以及蛋白質在不同生物體中的關聯，從而進一步理解生命和進化。序列比對起源於1970年。Saul B. Needleman和Christian D. Wunsch於1970提出了一個啟發式的同源演算法，稱為尼德曼-翁施演算法。該演算法使用迭代的方法計算出一個矩陣，從而達到全域性比對的效果。一些其他的啟發式分析方法也在70年代被提出。Sankoff，Reichert，Beyer等人提出了一些嚴謹的數學的演算法用來分析序列。然而這些方法通常難以揭示序列的生物學意義。 Sellers提出了一套測量序列距離的方法。沃特曼等於1976年在該方法的基礎上，增加了插入和刪除任意長度片段的方法。該方法解決了如何用最小的基因突變的次數將一個序列轉變成另一個序列的問題。之後，坦普爾·史密斯和邁克爾·沃特曼於1981年提出了史密斯-沃特曼演算法，解決了區域性比對問題。演算法.設要比對的兩序列為formula_1和formula_2，其中formula_3和formula_4分別為序列formula_5和formula_6的長度。解釋.史密斯-沃特曼演算法透過字母的匹配，刪除和插入操作，把兩條序列進行排列。實際上插入和刪除都是引入空位的操作。序列1上某一位置的插入相當於在序列2上對應位置的刪除。在實際計算中，只需要考慮何時引入空位即可。該演算法主要分兩步，計算得分矩陣和尋找最優比對序列。可以簡單描述為：與尼德曼-翁施演算法的比較.史密斯-沃特曼演算法為區域性比對演算法，用於找出兩序列中最相似的區域。尼德曼-翁施演算法為全域性比對演算法，用於完整匹配兩個序列。這兩種演算法的目不同，因此研究者在選擇演算法時要根據實際需求來決定。兩種演算法都使用了置換矩陣，空位罰分，得分矩陣，以及回溯的方法，具有一定的相似度。然而，史密斯-沃特曼演算法與尼德曼-翁施演算法的三個主要區別在於：其中，打分階段分數不為負是非常重要的一點區別。它使得對序列區域性的比對成為可能。當任何位置分數低於0，即表示此前的序列不具有相似性；而此時將此元素分數設為0，即達到了“重設”的效果，使得從此位置開始的比對不受之前位置的影響。初始化階段的區別使得史密斯-沃特曼演算法中從一序列任意位置開始匹配另一序列不受罰分，而尼德曼-翁施演算法因為要匹配完整的序列，所以兩端的空位也需要罰分。置換矩陣.每一鹼基對或殘基對匹配或錯配的分數通常用一矩陣表示，稱為置換矩陣。基本的置換矩陣為匹配則加分，錯配則扣分。以核苷酸序列為例，若匹配為+1，錯配為-1，則置換矩陣為：該置換矩陣可以表示為：formula_30不同的鹼基對或殘基對可以有不同的分數以適應於特定的場合。氨基酸序列比對的置換矩陣一般更加複雜。通常性質相似的殘基對具有正分數，反之，不相似的具有負分數。此外，殘基對的相似或不相似程度決定了分數的大小。。空位罰分.當鹼基對或殘基對之間匹配會導致更低分數時，需要空位的引入，即讓鹼基或殘基與空位匹配。空位罰分決定了插入或者刪除的分值。最基本的空位罰分方式為每次插入或者刪除的得分相同。然而在生物學上，兩序列之間一般存在著具有不同相似度的區域。另外，單個基因突變事件可能導致一長串空位的插入。因此，一個連續的較長的空位優於多個分散的小的空位。雖然多個分散的小的空位可以產生更多匹配，但一個連續的較長的空位代表這個區域只在一個序列中出現，使用後者可以避免為了得到高分而過度匹配這段序列。實現該方法只需要引入空位起始罰分和空位延長罰分的概念。空位起始罰分通常高於空位延長罰分。例如EMBOSS Water 的預設引數為空位起始罰分=10，空位延長罰分=0.5。實際應用中空位罰分方法有多種，此處詳細介紹這兩種最常見的方法。設formula_8為空位罰分函式，其中formula_9為空位長度：空位權值恆定模型.formula_33該模型空位的罰分正比於空位的長度。formula_34為單個空位的罰分。使用該模型時，原史密斯-沃特曼演算法可簡化為：formula_35此時該演算法步數為formula_36，formula_4和formula_3分別為兩序列的長度。在對某一位置考慮空位罰分時，只需考慮相鄰的上方的和左側的位置，而不需考慮整列和整行。空位延伸罰分模型.formula_39該模型考慮空位起始罰分和空位延長罰分，其中formula_40為開始空位的罰分，formula_41為每次延長空位的罰分。例如，一個長度為2的空位的罰分為formula_42。未經最佳化的該模型的演算法步數為formula_43。Gotoh將該演算法的步數最佳化至formula_36，然而，最佳化後的方法只能找出一個區域性比對結果，並且並不保證能成功獲得結果。Altschul進一步優化了Gotoh的演算法，在保持複雜度不變的情況下解決了Gotoh演算法的不足。Myers和Miller指出，Gotoh和Altschul的演算法忽視了Hirschberg在1975年提出的線上性空間內進行序列比對的方法，並在改進的演算法中運用了該方法。Myers和Miller的演算法僅使用formula_45空間，formula_3為較短的序列的長度。空位罰分例子.以兩序列TACGGGCCCGCTAC和TAGCCCTATCGGTCA進行比對為例，分別考慮兩種模型。當使用空位權值恆定模型時，即不考慮空位起始和延長的區別，得到如下結果：TACGGGCCCGCTA-CTA---G-CC-CTATC總得分為39.0當使用空位延伸罰分模型時，設空位起始罰分為5.0，空位延長罰分為1.0時，得到如下結果：TACGGGCCCGCTATA---GCC--CTA總得分為27.0可以看出，空位延伸罰分模型雖然總分略低，但考慮空位起始罰分和空位延長罰分能夠有效避免多個小的空位。得分矩陣.得分矩陣的作用是對兩序列中兩兩位置進行打分以逐步記錄最優比對。動態程式設計的思想體現於此。最終的最優區域性比對結果是由逐步擴充套件當前位置最優比對結果來實現的。矩陣的長度和寬度分別為兩序列長度+1。額外的首行和首列是為了讓序列的末端可以和空位匹配。首行和首列均設為0。以CTCAA和GGTCA為例，初始得分矩陣為：例子.以序列TGTTACGG和GGTTGACTA為例。使用如下引數：初始化得分矩陣，並進行打分。如下圖所示。該圖展示了該得分矩陣前三個元素的打分過程。黃色代表當前正在考慮的兩個鹼基。紅色代表該位置得分的打分完成後的得分矩陣如左下圖所示。其中藍色代表最高分元素。注意某些元素有不止一種得分這樣在回溯過程中會產生多個路徑。如果有多個相同的最高分，則應當考慮每個最高分的回溯。回溯過程見右下圖。區域性最相似序列在從最高分回溯的過程中自右向左產生。該例的結果為：G T T - A CG T T G A C