Smith-Waterman在python中的实现

def smith_waterman(seq1, seq2):
    # 初始化得分矩阵
    scores = [[0] * (len(seq2) + 1) for _ in range(len(seq1) + 1)]
    max_score = 0
    max_pos = (0, 0)

    # 填充得分矩阵
    for i in range(1, len(seq1) + 1):
        for j in range(1, len(seq2) + 1):
            match = scores[i - 1][j - 1] + (1 if seq1[i - 1] == seq2[j - 1] else -1)
            delete = scores[i - 1][j] - 1
            insert = scores[i][j - 1] - 1
            scores[i][j] = max(0, match, delete, insert)
            if scores[i][j] > max_score:
                max_score = scores[i][j]
                max_pos = (i, j)

    # 回溯获取最优比对路径
    align1 = ""
    align2 = ""
    i, j = max_pos
    while scores[i][j] != 0:
        if scores[i][j] == scores[i - 1][j - 1] + (1 if seq1[i - 1] == seq2[j - 1] else -1):
            align1 = seq1[i - 1] + align1
            align2 = seq2[j - 1] + align2
            i -= 1
            j -= 1
        elif scores[i][j] == scores[i - 1][j] - 1:
            align1 = seq1[i - 1] + align1
            align2 = "-" + align2
            i -= 1
        else:
            align1 = "-" + align1
            align2 = seq2[j - 1] + align2
            j -= 1

    return align1, align2

# 示例用法
seq1 = "AGTACGCA"
seq2 = "TATGC"
alignment = smith_waterman(seq1, seq2)
print("Sequence 1:", alignment[0])
print("Sequence 2:", alignment[1])