Needleman-Wunsch算法Python代码实现

以下是 Needleman-Wunsch算法的 Python 代码实现：

def needleman_wunsch(seq1, seq2, gap_penalty=-1, match_score=1, mismatch_score=-1):
    n, m = len(seq1), len(seq2)
    dp = [[0] * (m + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        dp[i][0] = i * gap_penalty

    for j in range(1, m + 1):
        dp[0][j] = j * gap_penalty

    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if seq1[i - 1] == seq2[j - 1]:
                match = match_score
            else:
                match = mismatch_score
            dp[i][j] = max(dp[i - 1][j - 1] + match, dp[i - 1][j] + gap_penalty, dp[i][j - 1] + gap_penalty)

    align1, align2 = "", ""
    i, j = n, m
    while i > 0 and j > 0:
        if dp[i][j] == dp[i - 1][j - 1] + (match_score if seq1[i - 1] == seq2[j - 1] else mismatch_score):
            align1 = seq1[i - 1] + align1
            align2 = seq2[j - 1] + align2
            i -= 1
            j -= 1
        elif dp[i][j] == dp[i - 1][j] + gap_penalty:
            align1 = seq1[i - 1] + align1
            align2 = "-" + align2
            i -= 1
        else:
            align1 = "-" + align1
            align2 = seq2[j - 1] + align2
            j -= 1

    while i > 0:
        align1 = seq1[i - 1] + align1
        align2 = "-" + align2
        i -= 1

    while j > 0:
        align1 = "-" + align1
        align2 = seq2[j - 1] + align2
        j -= 1

    return align1, align2

其中，`seq1`和`seq2`为需要比对的两个序列，`gap_penalty`为缺失一个字符时的分值，`match_score`为匹配时的分值，`mismatch_score`为不匹配时的分值。函数返回值为两个比对后的序列。

注意，在使用 Needleman-Wunsch 算法时，需要考虑两个序列的长度可能不同。需要在计算 DP table 时，将 DP table 的大小设为 `(n+1) x (m+1)`，并将第一行和第一列初始化为缺失一个字符的分数。在回溯时，需要考虑某个序列已经到达末尾的情况。