首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >NeedlemanWunsch算法

问NeedlemanWunsch算法
EN

Stack Overflow用户
提问于 2014-04-09 01:21:56
回答 1查看 3.7K关注 0票数 2

我试图理解Hirschberg算法,我从维基百科上看到了这个算法。我不明白NeedlemanWunsch()函数是如何工作的。

代码语言:javascript
复制
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实现它?非常感谢!

EN

回答 1

Stack Overflow用户

回答已采纳

发布于 2014-04-09 05:18:41

这看起来像一个家庭作业/课程问题,所以我不会给你一个完整的解决方案。然而,我将指导你提出一个有效的解决方案。

Needleman-Wunsch算法

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

  1. 一个相似矩阵F.
  2. 线性罚差,d.

当对齐序列时,可能有很多可能性。这个矩阵允许您找到最优的一个,并丢弃所有其他序列。

你要做的是:

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

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

您可以为此使用numpy,也可以生成矩阵,如下所示。假设您有两个序列A和B:

代码语言:javascript
复制
F = [[0 for x in xrange(len(A)] for x in xrange(len(B))]

用分数初始化矩阵F的一种方法.

创建一个方法,该方法接受参数--每个序列的长度、线性惩罚间隙和矩阵F:

代码语言:javascript
复制
def createSimilarityMatrix(lengthOfA, lengthOfB, penalityGap, F):

然后,您需要实现以下伪代码:

代码语言:javascript
复制
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作为参数的方法:

代码语言:javascript
复制
def needlemanWunsch (a, b):

然后,您将需要使用以下伪代码实现此方法:

代码语言:javascript
复制
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代码取自维基百科的这页面。有关Needleman算法的更多信息,请查看这演示文稿.

票数 4
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/22951162

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档