最长公共序列索引E

Question

我正试图找到两个序列之间的LCS:TACGCTGGTACTGGCAT和agctggcagaa。我希望我的答案作为一个矩阵输出，这样我就可以回溯哪个序列是公共的（GCTGGT）。当我使用下面的代码时，我得到以下错误。索引器错误：列表索引超出范围。如何在下面的代码中避免此错误

def LCS(x, y):
    m = len(x)
    n = len(y)
    C = []  
    for i in range(m):
        for j in range(n):
            if x[i] == y[j]:
                C[i][j] == C[i-1][j-1] + 1
            else:
                C[i][j] == 0
    return C


x = "TACGCTGGTACTGGCAT"
y = "AGCTGGTCAGAA"
m = len(x)
n = len(y)
C = LCS(x, y)

print C

Answer 1

您需要附加到列表中，因为索引[i][j]还不存在

def LCS(x, y):
    m = len(x)
    n = len(y)
    C = []  
    for i in range(m):
    C.append([])          # append a blank list at index [i]
        for j in range(n):
            if x[i] == y[j]:
                C[i].append(C[i-1][j-1] + 1)   # append current element to [i]
            else:
                C[i].append(0)
    return C

测试

x = "TACGCTGGTACTGGCAT"
y = "AGCTGGTCAGAA"
LCS(x,y)

输出

[[0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0],
 [1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1],
 [0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0],
 [0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0],
 [0, 0, 2, 0, 0, 0, 0, 1, 0, 0, 0, 0],
 [0, 0, 0, 3, 0, 0, 1, 0, 0, 0, 0, 0],
 [0, 1, 0, 0, 4, 1, 0, 0, 0, 1, 0, 0],
 [0, 1, 0, 0, 1, 5, 0, 0, 0, 1, 0, 0],
 [0, 0, 0, 1, 0, 0, 6, 0, 0, 0, 0, 0],
 [1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1],
 [0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0],
 [0, 0, 0, 2, 0, 0, 1, 0, 0, 0, 0, 0],
 [0, 1, 0, 0, 3, 1, 0, 0, 0, 1, 0, 0],
 [0, 1, 0, 0, 1, 4, 0, 0, 0, 1, 0, 0],
 [0, 0, 2, 0, 0, 0, 0, 1, 0, 0, 0, 0],
 [1, 0, 0, 0, 0, 0, 0, 0, 2, 0, 1, 1],
 [0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0]]