尼德尔曼-温ж算法

Question

我正在尝试理解Hirschberg算法，结果在维基百科上看到了一段相关的算法。我不太明白NeedlemanWunsch()这个函数是怎么工作的。

function Hirschberg(X,Y)
Z = ""
W = ""
if length(X) == 0 or length(Y) == 0
  if length(X) == 0
    for i=1 to length(Y)
      Z = Z + '-'
      W = W + Yi
    end
  else if length(Y) == 0
    for i=1 to length(X)
      Z = Z + Xi
      W = W + '-'
    end
  end
else if length(X) == 1 or length(Y) == 1
  (Z,W) = NeedlemanWunsch(X,Y)
else
  xlen = length(X)
  xmid = length(X)/2
  ylen = length(Y)

  ScoreL = NWScore(X1:xmid, Y)
  ScoreR = NWScore(rev(Xxmid+1:xlen), rev(Y))
  ymid = PartitionY(ScoreL, ScoreR)

  (Z,W) = Hirschberg(X1:xmid, y1:ymid) + Hirschberg(Xxmid+1:xlen, Yymid+1:ylen)
end
return (Z,W)

有人能解释一下NeedlemanWunsch算法是什么，以及怎么用Python来实现它吗？非常感谢！

Answer 1

这看起来像是一个作业或课程问题，所以我不会给你完整的解决方案。不过，我会引导你一步步找到一个可行的解决办法。

Needleman-Wunsch算法

Needleman-Wunsch算法是一种用于对齐序列的方法。它主要由两个部分组成：

1. 一个相似度矩阵，记作F。
2. 一个线性惩罚间隙，记作d。

在对齐序列时，可能会有很多种选择。这个矩阵的作用就是帮助你找到最优的选择，并舍弃其他的序列。

你需要做的事情有：

1. 创建一个二维数组来存放矩阵F。
2. 编写一个方法来初始化矩阵F的分数。
3. 编写一个方法来计算最优序列。

创建一个二维数组来存放矩阵F

你可以使用numpy来实现，或者你也可以用其他方法生成这个矩阵。假设你有两个序列A和B：

F = [[0 for x in xrange(len(A)] for x in xrange(len(B))]

编写一个方法来初始化矩阵F的分数

创建一个方法，接受每个序列的长度、线性惩罚间隙和矩阵F作为参数：

def createSimilarityMatrix(lengthOfA, lengthOfB, penalityGap, F):

然后你需要实现以下伪代码：

for i=0 to length(A)
  F(i,0) ← d*i
for j=0 to length(B)
  F(0,j) ← d*j
for i=1 to length(A)
  for j=1 to length(B)
  {
    Match ← F(i-1,j-1) + S(Ai, Bj)
    Delete ← F(i-1, j) + d
    Insert ← F(i, j-1) + d
    F(i,j) ← max(Match, Insert, Delete)
  }

提示：研究一下用地道的Python写这个算法的最佳方式。还要注意，在底部的双重循环中，你可以将其简化为一行代码。

编写一个方法来计算最优序列

一旦你完成了相似度矩阵的构建，就可以实现主要算法来计算最优序列。为此，创建一个方法，接受你的两个序列A和B作为参数：

def needlemanWunsch (a, b):

然后你需要使用以下伪代码来实现这个方法：

AlignmentA ← ""
AlignmentB ← ""
i ← length(A)
j ← length(B)
while (i > 0 or j > 0)
{
  if (i > 0 and j > 0 and F(i,j) == F(i-1,j-1) + S(Ai, Bj))
  {
    AlignmentA ← Ai + AlignmentA
    AlignmentB ← Bj + AlignmentB
    i ← i - 1
    j ← j - 1
  }
  else if (i > 0 and F(i,j) == F(i-1,j) + d)
  {
    AlignmentA ← Ai + AlignmentA
    AlignmentB ← "-" + AlignmentB
    i ← i - 1
  }
  else (j > 0 and F(i,j) == F(i,j-1) + d)
  {
    AlignmentA ← "-" + AlignmentA
    AlignmentB ← Bj + AlignmentB
    j ← j - 1
  }
}

这些伪代码来自于维基百科的这个页面。想了解更多关于Needleman-Wunsch算法的信息，请查看这个演示文稿。