最长公共子串矩阵

Question

我是 python 的新手，正在努力创建一个表示最长公共子串的矩阵。我正在寻找这样的结果：LCS matrix

到目前为止，这是我的代码。

def compute_lcs(X, Y):
    m = len(X)
    n = len(Y)
# An (m) times (n) matrix
    matrix = [[0] * (n) for _ in range(m)]
    for i in range(1, m):
        for j in range(1, n):
            if X[i] == Y[j]: 
                if i == 0 or j == 0:
                    matrix[i][j] = 1
            else:
                matrix[i][j] = matrix[i-1][j-1]+1
        else:
            matrix[i][j] = 0
    return matrix

b = compute_lcs('AACTGGCAG','TACGCTGGA')
for y in b:
    print (y)

Current Output:
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 1, 1, 1, 1, 1, 1, 0]
[0, 1, 0, 2, 0, 2, 2, 2, 0]
[0, 1, 2, 1, 3, 0, 3, 3, 0]
[0, 1, 2, 0, 2, 4, 0, 0, 0]
[0, 1, 2, 0, 1, 3, 0, 0, 0]
[0, 1, 0, 3, 0, 2, 4, 1, 0]
[0, 0, 2, 1, 4, 1, 3, 5, 0]
[0, 1, 1, 0, 2, 5, 0, 0, 0]

Expected Output:
[0, 0, 0, 1, 0, 0, 0, 0, 0]
[1, 1, 0, 0, 0, 0, 0, 1, 0]
[0, 0, 2, 0, 0, 0, 0, 1, 0]
[0, 0, 0, 0, 1, 1, 0, 0, 1]
[0, 0, 1, 0, 0, 0, 2, 0, 0]
[0, 0, 0, 2, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 3, 1, 0, 0, 0]
[0, 0, 0, 0, 1, 4, 0, 0, 1]
[1, 1, 0, 0, 0, 0, 0, 1, 0]

但是我的结果是一个显示不正确值的矩阵。当我手工计算矩阵时，正确的输出如下所示：Correct output。我觉得我的逻辑很有道理，我做错了什么？

谢谢大家

Answer 1

首先，要弄清楚 longest common subsequence problem is not the same as the longest common substring 问题。您要解决的是后者；最好不要混淆两者。

其次，您的 else 分支未在适当的 if 条件下对齐。每当字符串匹配 X[i] == Y[j] 时，如果索引 i 或 j 为 0，我们将矩阵元素设置为 1，因为 0 处的 i-1 或 j-1 给出 -1（不幸的是，这也是中最后一项的索引Python) 这不是我们想要的，否则我们会增加更高的索引 i, j > 1.

第三，您的循环应该从 0 而不是 1 开始，因为我们从字符串中位于索引 0 的第一个字符开始：

def compute_lcs(X, Y):
   m = len(X)
   n = len(Y)
   # An (m) times (n) matrix
   matrix = [[0] * n for _ in range(m)]
   for i in range(0, m):
      for j in range(0, n):
          if X[i] == Y[j]: 
              if i == 0 or j == 0:
                  matrix[i][j] = 1
              else:
                  matrix[i][j] = matrix[i-1][j-1]+1
          else:
              matrix[i][j] = 0
  return matrix

要获得预期输出中显示的确切矩阵，您应该在打印前交换参数的顺序或转置矩阵。但请注意，这些不是必需的（交换或调换），仅用于格式化目的：

b = compute_lcs('TACGCTGGA', 'AACTGGCAG')
for y in b:
    print (y)


[0, 0, 0, 1, 0, 0, 0, 0, 0]
[1, 1, 0, 0, 0, 0, 0, 1, 0]
[0, 0, 2, 0, 0, 0, 1, 0, 0]
[0, 0, 0, 0, 1, 1, 0, 0, 1]
[0, 0, <b>1</b>, 0, 0, 0, 2, 0, 0]
[0, 0, 0, <b>2</b>, 0, 0, 0, 0, 0]
[0, 0, 0, 0, <b>3</b>, 1, 0, 0, 1]
[0, 0, 0, 0, 1, <b>4</b>, 0, 0, 1]
[1, 1, 0, 0, 0, 0, 0, 1, 0]

最长公共子串矩阵

Longest common substring matrix

python

bioinformatics

python-3.x