smith-waterman算法c++实现

Smith-Waterman算法是一种用于序列比对的动态规划算法。它可以用于比对DNA、RNA、蛋白质序列等。C++是一种高效的编程语言，可以用于实现Smith-Waterman算法。

实现Smith-Waterman算法的C++代码需要考虑以下几个方面：

1. 输入序列：需要从文件或者用户输入中读取待比对的序列。

2. 动态规划矩阵：需要创建一个二维数组来存储动态规划矩阵。

3. 算法实现：需要实现算法的核心部分，包括初始化矩阵、计算得分、回溯路径等。

4. 输出结果：需要将比对结果输出到文件或者屏幕上。

以下是一个简单的Smith-Waterman算法的C++实现示例：

#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

const int MAXLEN = 1000;
const int GAP = -2;
const int MATCH = 3;
const int MISMATCH = -1;

int score[MAXLEN][MAXLEN];

int max(int a, int b, int c) {
    int m = a;
    if (b > m) m = b;
    if (c > m) m = c;
    return m;
}

void init(int n, int m) {
    for (int i = 0; i <= n; i++) {
        score[i][0] = 0;
    }
    for (int j = 0; j <= m; j++) {
        score[0][j] = 0;
    }
}

void compute_score(char* s1, char* s2, int n, int m) {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            int match = score[i-1][j-1] + (s1[i-1] == s2[j-1] ? MATCH : MISMATCH);
            int delete_gap = score[i-1][j] + GAP;
            int insert_gap = score[i][j-1] + GAP;
            score[i][j] = max(match, delete_gap, insert_gap);
        }
    }
}

void traceback(char* s1, char* s2, int n, int m) {
    int i = n, j = m;
    while (i > 0 && j > 0) {
        int match = score[i-1][j-1] + (s1[i-1] == s2[j-1] ? MATCH : MISMATCH);
        int delete_gap = score[i-1][j] + GAP;
        int insert_gap = score[i][j-1] + GAP;
        if (score[i][j] == match) {
            cout << s1[i-1] << " " << s2[j-1] << endl;
            i--;
            j--;
        } else if (score[i][j] == delete_gap) {
            cout << s1[i-1] << " -" << endl;
            i--;
        } else {
            cout << "- " << s2[j-1] << endl;
            j--;
        }
    }
}

int main() {
    char s1[MAXLEN], s2[MAXLEN];
    cin >> s1 >> s2;
    int n = strlen(s1), m = strlen(s2);
    init(n, m);
    compute_score(s1, s2, n, m);
    traceback(s1, s2, n, m);
    return 0;
}

该示例代码实现了Smith-Waterman算法的核心部分，包括初始化矩阵、计算得分、回溯路径等。在输入两个待比对的序列后，程序会输出比对结果。需要注意的是，该示例代码只是一个简单的实现，实际应用中可能需要进行更多的优化和改进。