Needlman_Wunsch回溯方法

1、其思路为，遍历所有可行路径，比喻成现实生活中的路径选择问题，地点A到B有很多路径，遍历所有路径，而不重复的方法是，每一条路径的最后一个分支点，进行封闭，就像施工封闭一样。从而实现路径不重复访问。

2、首先构造一个求最大值以及数据来源的方法。以获得我们需要的信息。

#calculate themaximum number and the direction

def maximum(one ,two,three):

    max=((one if one>two else two) if (oneif one>two else two)>three else three)

    pos=0

    if max==one:

        if max==two:

            if max==three:

                pos=7

            else:

                pos=4

        else:

            if max==three:

                pos=6

            else:

                pos=1

    else:

        if max==two:

            if max==three:

                pos=5

            else:

                pos=2

        else:

            pos=3

    return max,pos

3、再构建一个填充矩阵的方法，填充数值。

def HD(s,t):

    import numpy as np

    h=np.zeros((len(s)+1,len(t)+1))

    d=np.zeros((len(s)+1,len(t)+1))

    for i in range(len(s)+1):

        h[i][0]=-2*i

        if i!=0:

            d[i][0]=1

    for i in range(len(t)+1):

        h[0][i]=-2*i

        if i!=0:

            d[0][i]=3

    for i in range(1,len(s)+1):

        for j in range(1,len(t)+1):

            score=-1

            if s[i-1]==t[j-1]:

                score=1

           h[i][j],d[i][j]=maximum(h[i-1][j]+(-2),h[i-1][j-1]+score,h[i][j-1]+(-2))

    return h,d

4、接着我们构架回溯的方法对，序列进行回溯：

5、使用循环获得所有比对后的结果。