Needleman-Wunsch算法实现异常：填充第1行却修改二维数组第0行

你遇到的问题根源出在得分矩阵的初始化方式上：

score_matrix = [[0] * n]*m # initialising every element to 0

这种写法会创建一个包含m个元素的列表，但每个元素都是同一个列表对象的引用。也就是说，所有行实际上指向的是同一个[0]*n的列表。当你修改score_matrix[i][j]时，相当于修改了这个共享列表的第j个元素，所以第0行也会跟着变化——因为它和其他行是同一个对象。

修正方法 #

把矩阵初始化改成逐行创建独立的列表：

score_matrix = [[0]*n for _ in range(m)]

这样每一行都是一个全新的列表，修改某一行的元素不会影响其他行，第0行就能保持初始的全0状态了。

修正后的完整代码示例 #

def seq_align(s1, s2, scoring):
    '''s1, s2 - sequences to be aligned;
    scoring - scoring scheme of the form (match_score, mismatch_score, gap_penalty)'''
    m = len(s1) + 1 # number of rows of the score matrix
    n = len(s2) + 1 # number of columns of the score matrix

    # 修正初始化方式
    score_matrix = [[0]*n for _ in range(m)]

    print("Score matrix before filling")
    for i in range(len(score_matrix)):
        print("row #", i, " -->", score_matrix[i])
    for i in range(1, m):
        for j in range(1, n):
            print("checking values of 0th row", score_matrix[0])
            print("Filling element: ", i, ",", j)
            s_ij = 0 # variable to store the score - match/mismatch
            if(s1[i-1] == s2[j-1]):
                s_ij = scoring[0]
            else:
                s_ij = scoring[1]
            t1 = score_matrix[i-1][j-1] + s_ij
            t2 = score_matrix[i-1][j] + scoring[2]
            t3 = score_matrix[i][j-1] + scoring[2]
            # print("t1, t2, t3 =", t1, t2, t3)
            score = max(t1, t2, t3)                       
            score_matrix[i][j] = score
            print("Filling element: ", i, ",", j, "with", score_matrix[i][j]) 
        print("After filling row #",i,"matrix-->")
        for idx in range(m):
            print(score_matrix[idx])

    
    print("First row -> ", score_matrix[0])
    
    return m + n # placeholder

if __name__ == "__main__":
    l = seq_align("ABC", "ABCDEF", (2, -1, -2))

运行修正后的代码，第0行就会始终保持全0，不会被后续的矩阵填充操作修改了。

内容的提问来源于stack exchange，提问作者Chinmay