Needlman_Wunsch回溯方法

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

首先构造一个求最大值以及数据来源的方法。以获得我们需要的信息。#calculate the maximum number and the directiondef maximum(one ,two ,three):    max=((one if one>two else two) if (one if 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

再构建一个填充矩阵的方法，填充数值。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

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

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