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