y
=['G','A','T','A','C','T','A']
x
=['G','A','T','T','A','C','C','A']

a = len(x)
b = len(y)
# S={'AA': 1, 'AT': -1, 'AG':
-1,'AC': -1, 'TA': -1, 'TT': 1,
'TG':-1, 'TC': -1, 'GA': -1, 'GT':
-1,'GG': 1, 'GC': -1,  'CA': -1,
'CT':-1, 'CG': -1, 'CC': 1, }
S ={'A': {'A':1, 'G': -1, 'C':
-1,'T': -1}, 'G': {'A': -1, 'G':
1,'C': -1, 'T': -1},'C': {'A':
-1,'G': -1, 'C': 1, 'T': -1},
'T':{'A': -1, 'G': -1, 'C': -1,
'T':1}}

import numpy as np

F = np.zeros((len(x) + 1, len(y) + 1))
#print(F)
d = -1
for i in range(0, a+1):
    F[i][0] = d * i;
for j in range(0, b+1):
    F[0][j] = d * j;


for i in range(1, a+1):
    for j in range(1, b+1):
        Match = F[i - 1][j - 1] + S[x[i-1]][y[j-1]]
        Delete = F[i - 1][j] + d
        Insert = F[i, j - 1] + d
        F[i][j] = max(Match, Insert, Delete);

alX = ""
alY = ""
i = a
j = b
while(i > 0 or j > 0):
    if(i > 0 and j > 0 and F[i][j] == F[i - 1][j - 1] +
S[x[i-1]][y[j-1]] ):       #+S.values([x[i-1], y[j]] )
        alX = x[i-1] + alX
        alY = y[j-1] + alY
        i = i - 1
        j = j - 1


    elif(i > 0 and F[i,j] == F[i-1][j] + d):
        alX = x[i-1] + alX
        alY = "-" + alY
        i = i-1
    else:
        alX = "-" + alX
        alX = y[j-1] + alY
        j = j - 1

#print(F[i][j])
print(F)
print(alX)
print(alY)