def DPAlign(seqA, seqB, gp, M): y = len(seqA) + 1 x = len(seqB) + 1 S = list() # table of scores D = list() # table of directions for i in range(y): S.append(list()); D.append(list()) for j in range(x): S[i].append(gp*(i == 0 or j == 0)*max(i, j)) D[i].append(0) # start filling out the dynamic programming matrix for i in range(1, y): for j in range(1, x): # we can arrive at [i,j] from either north or [i-1,j], west [i,j-1], or north-west [i-1,j-1] n = S[i-1][j] + gp w = S[i][j-1] + gp nw = S[i-1][j-1] + M[seqA[i-1]][seqB[j-1]] # choose best if (n >= max(w, nw)): D[i][j] = 1; # 1 will designate coming from north elif (w >= max(n, nw)): D[i][j] = 2; # 1 will designate coming from west elif (nw >= max(n, w)): D[i][j] = 3; # 1 will designate coming from west S[i][j] = max(n, w, nw); # do the trace-back starting at the last position and build the alignment seqAal = list() seqBal = list() i = y - 2; j = x - 2 while (i >= 0 or j >= 0): # if we came to [i,j] from north, put gap into second sequence if (D[i][j] == 1): seqAal.append(seqA[i]) seqBal.append("-") i -= 1 # if we came to [i,j] from west, put gap into first sequence elif (D[i][j] == 2): seqAal.append("-") seqBal.append(seqB[j]) j -= 1 # if we came to [i,j] from north-west, allign the two characters else: seqAal.append(seqA[i]) seqBal.append(seqB[j]) i -= 1; j -= 1 # since the alignment was build from the end, reverse seqAal.reverse() seqBal.reverse() return S[y-1][x-1], seqAal, seqBal