python - 具有仿射间隙惩罚的 Smith-Waterman 算法中的回溯

Question

我正在尝试使用仿射间隙罚函数实现用于局部序列比对的 Smith-Waterman 算法。我想我了解如何启动和计算计算比对分数所需的矩阵，但对于如何回溯以找到比对一无所知。要生成所需的 3 个矩阵，我有以下代码

for j in range(1, len2):
    for i in range(1, len1):
        fxOpen = F[i][j-1] + gap
        xExtend = Ix[i][j-1] + extend
        Ix[i][j] = max(fxOpen, xExtend)

        fyOpen = F[i-1][j] + gap
        yExtend = Iy[i-1][j] + extend
        Iy[i][j] = max(fyOpen, yExtend)

        matchScore = (F[i-1][j-1]  + simMatrixDict[seq1[i-1]+seq2[j-1]])
        xScore = Ix[i-1][j-1] + simMatrixDict[seq1[i-1]+seq2[j-1]]
        yScore = Iy[i-1][j-1] + simMatrixDict[seq1[i-1]+seq2[j-1]]
        F[i][j] = max(0, matchScore, xScore, yScore)

我不确定我是否需要单个矩阵进行回溯，还是只需要 1 个？非常感谢任何关于如何从 F 中的最大分数追溯的澄清。

Answer 1

关于 Smith-Waterman 中的回溯，需要记住的重要一点是值所在的矩阵决定了移动的方向。所以，如果你在 F如果你在 Ix 中，你正在沿对角线移动，你在水平移动，如果你在 Iy ，你正在垂直移动。这意味着您需要在指针矩阵中存储的是您到达正方形的矩阵。您来自的矩阵，而不是您要去的矩阵，决定了前进的方向。

例如:

假设您在 F[5][5] :

• 如果指针矩阵说去Ix , 转到 Ix[4][4]
• 如果指针矩阵说去Iy , 转到 Iy[4][4]
• 如果指针矩阵说去F , 转到 F[4][4]

而如果您在 Ix[5][5] :

• 如果指针矩阵说去Ix , 转到 Ix[4][5]
• 如果指针矩阵说去F , 转到 F[4][5]

或者如果您在 Iy[5][5] :

• 如果指针矩阵说去Iy , 转到 Iy[5][4]
• 如果指针矩阵说去F , 转到 F[5][4]

假设第一个索引是x坐标，第二个是y坐标。

继续回溯，直到到达最大值为 0 的单元格。

构建指针矩阵: F 需要一个指针矩阵, Ix , 和 Iy .这些矩阵只需要指示一个值来自哪个矩阵，因为它会告诉您移动的方向。因此，当您运行算法的动态规划阶段时，您还应该构建指针矩阵。每次在 F 中的单元格中存储新的最大值时, Ix , 或 Iy ，您应该更新相应的矩阵以指示它的来源。例如，如果您可以在 F[5][5] 中拥有最高值当你在 F[4][4] 时，通过对齐接下来的两个碱基来实现, Fpointer[5][5] 应设置为 F ，因为你是从 F 到达那里的矩阵。