我试图理解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实现它?非常感谢!
发布于 2014-04-09 05:18:41
这看起来像一个家庭作业/课程问题,所以我不会给你一个完整的解决方案。然而,我将指导你提出一个有效的解决方案。
Needleman-Wunsch算法
Needleman-Wunsch算法是一种用于对齐序列的方法.它主要由两个组成部分组成:
当对齐序列时,可能有很多可能性。这个矩阵允许您找到最优的一个,并丢弃所有其他序列。
你要做的是:
创建一个二维数组来保存矩阵,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
}
}https://stackoverflow.com/questions/22951162
复制相似问题