9

我正在尝试使用仿射间隙惩罚函数来实现用于局部序列比对的 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 中的最高分数追溯的澄清将不胜感激。

4

1 回答 1

7

关于 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矩阵中获得的。

于 2013-08-08T02:35:55.780 回答