needemanwunsch算法

Question

我在试图理解Hirschberg算法，我在Wikipedia上看到了这个算法。我不明白needemanwunsch（）函数是如何工作的。在

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)

有人能解释一下needemanwunsch算法吗？它是如何通过Python实现的？非常感谢你！在

Answer 1

这看起来像是家庭作业/作业问题，所以我不会给你完整的答案。但是，我将指导您制定一个有效的解决方案。在

Needleman-Wunsch算法

neederman-Wunsch算法是一种用于序列对齐的方法。它基本上由两个部分组成：

1. 相似性矩阵
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：

^{2}$

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

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编写此算法的最佳方法。还要注意，在底部的double for循环中，您可以折叠成一个单行程序。在

一种计算最优序列的方法

一旦你完成了相似性矩阵，你就可以实现主算法来计算最优序列。为此，请创建一个将两个序列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
  }
}

psuedo代码取自Wikipedia上的this页面。有关neederman-Wunsch算法的更多信息，请查看this演示文稿。在