本文實現Smith-Waterman 算法案例，用于局部序列比對。該算法是生物信息學中用于尋找兩個 DNA、RNA 或蛋白質序列之間最優局部比對的經典算法，廣泛應用于序列相似性分析和功能預測。
問題描述
給定兩個生物序列 seq1 和 seq2，如何找到它們的最優局部比對，使得比對得分最大化？
算法思想
Smith-Waterman 算法的核心思想是動態規劃，通過構建一個得分矩陣，逐步計算兩個序列的比對得分，并回溯找到最優局部比對路徑。與 Needleman-Wunsch 算法不同，Smith-Waterman 算法允許比對從任意位置開始和結束，更適合尋找局部相似性。具體步驟如下：
- 初始化得分矩陣，其中
dp[i][j]表示seq1的前i個字符與seq2的前j個字符的比對得分。 - 填充得分矩陣，考慮四種可能的比對操作：
- 匹配或錯配：
dp[i-1][j-1] + score(seq1[i], seq2[j]) - 插入空格：
dp[i][j-1] + gap_penalty - 刪除空格：
dp[i-1][j] + gap_penalty - 比對從當前位置重新開始：
0
- 匹配或錯配：
- 回溯得分矩陣，找到最優局部比對路徑。
C++代碼實現
#include <iostream>
#include <vector>
#include <algorithm>using namespace std;// 定義得分函數
int match_score(char a, char b) {return (a == b) ? 1 : -1; // 匹配得分為 1，錯配得分為 -1
}// Smith-Waterman 算法
pair<int, string> smithWaterman(const string& seq1, const string& seq2, int gap_penalty = -1) {int m = seq1.size();int n = seq2.size();// 初始化得分矩陣vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));int max_score = 0; // 記錄最大得分int max_i = 0, max_j = 0; // 記錄最大得分的位置// 填充得分矩陣for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {int match = dp[i - 1][j - 1] + match_score(seq1[i - 1], seq2[j - 1]);int insert = dp[i][j - 1] + gap_penalty;int del = dp[i - 1][j] + gap_penalty;dp[i][j] = max({0, match, insert, del});// 更新最大得分及其位置if (dp[i][j] > max_score) {max_score = dp[i][j];max_i = i;max_j = j;}}}// 回溯找到最優局部比對string align1, align2;int i = max_i, j = max_j;while (i > 0 && j > 0 && dp[i][j] != 0) {if (dp[i][j] == dp[i - 1][j - 1] + match_score(seq1[i - 1], seq2[j - 1])) {align1 = seq1[i - 1] + align1;align2 = seq2[j - 1] + align2;i--;j--;} else if (dp[i][j] == dp[i][j - 1] + gap_penalty) {align1 = '-' + align1;align2 = seq2[j - 1] + align2;j--;} else {align1 = seq1[i - 1] + align1;align2 = '-' + align2;i--;}}return {max_score, align1 + "\n" + align2};
}int main() {string seq1 = "GATTACA";string seq2 = "GCATGCU";auto result = smithWaterman(seq1, seq2);cout << "最優局部比對得分: " << result.first << endl;cout << "最優局部比對結果: " << endl << result.second << endl;return 0;
}
關鍵解析
- 時間復雜度：
O(m * n)，其中m和n分別是兩個序列的長度。 - 空間復雜度：
O(m * n)，用于存儲得分矩陣。 - 適用場景：
- 局部序列比對。
- 尋找序列中的功能域或保守區域。
輸出示例
最優局部比對得分: 2
最優局部比對結果:
AT
AT
總結
Smith-Waterman 算法是生物信息學中用于局部序列比對的經典算法，通過動態規劃和回溯找到最優局部比對。
)
)
