Smith Waterman

import numpy as np

from cell import cell

def alignment_nw(a,b):
    if a==b:
        return 3
    else:
        return -3

def recursion(paths,D):
    new_paths = []
    returnvalue = paths
    keep_going = False
    for path in paths:
        if path[-1].get_value() == 0:
            continue
        pointers = path[-1].get_pointers()
        for pointer in pointers:
            if pointers.size==0:
                continue
            indices = np.where(D == pointer)
            path = np.append(path,D[indices])
            keep_going = True
            if len(new_paths) == 0:
                new_paths = [path]
            else:
                new_paths.append(path)
    if keep_going:
        returnvalue=recursion(new_paths,D)
    return returnvalue

def main(A,B):
    A = np.array([ a for a in A ])
    B = np.array([ b for b in B ])
    A = np.insert(A,0,'-')
    B = np.insert(B,0,'-')
    D = np.array([[cell() for i in range(B.size)] for j in range(A.size)])
    for i in range(1,A.size):
        D[i][0].set_value(0)
    for i in range(1,B.size):
        D[0][i].set_value(0)
    for i in range(1,A.size):
        for j in range(1,B.size):
            D[i][j].set_value(0)
            candidates = [D[i-1][j-1].get_value()+alignment_nw(A[i],B[j]), D[i-1][j].get_value()-2,D[i][j-1].get_value()-2]
            index_array = np.argwhere(candidates == np.amax(candidates)).flatten().tolist()
            if candidates[index_array[-1]]>0:
                D[i][j].set_value(candidates[index_array[-1]])
            for k in index_array:
                if k == 0:
                    D[i][j].add_pointer(D[i-1][j-1])
                elif k == 1:
                    D[i][j].add_pointer(D[i-1][j])
                elif k == 2:
                    D[i][j].add_pointer(D[i][j-1])
    print(D)
    #Tracing arrows back
    path = [[np.amax(D)]]
    paths = recursion(path,D)
    print(paths)

    previous_step_indices = np.array([-1,-1])
    alignment = ['','']
    score = 0
    for id,path in enumerate(paths):
        for step in path:
            indices = np.where(D == step)
            if(previous_step_indices[0]==-1):
                previous_step_indices=indices
                continue
            elif indices[0]<previous_step_indices[0] and indices[1]<previous_step_indices[1]:
                alignment = [A[previous_step_indices[0][-1]]+alignment[0],B[previous_step_indices[1][-1]]+alignment[1]]
                if A[previous_step_indices[0][-1]]==B[previous_step_indices[1][-1]]:
                    score=score+1
                else:
                    score=score-1
            elif indices[0]<previous_step_indices[0]:
                alignment = [A[previous_step_indices[0][-1]]+alignment[0],'-'+alignment[1]]
                score=score-1
            elif indices[1]<previous_step_indices[1]:
                alignment = ['-'+alignment[0],B[previous_step_indices[1][-1]]+alignment[1]]# np.char.add(['-',B[indices[1]]],alignment)#('-'+alignment[0],B[indices[1]]+alignment[1])
                score=score-1
            previous_step_indices=indices
        print('\npath number: {} score: {}\n{}\n{}\n'.format(id+1,score,alignment[0],alignment[1]))
        alignment = ['','']
        score=0
    return

main('ACGTC','AGTCA')
#main('GCATGCU','GATTACA')
#main('GGTTGACTA','TGTTACGG')



###################BACKUP#######################

#def main(A,B):
#    A = np.array([ a for a in A ])
#    B = np.array([ b for b in B ])
#    A = np.insert(A,0,'-')
#    B = np.insert(B,0,'-')
#    cell = np.dtype([('symbol', np.unicode_, 3), ('value', np.int32)])
#    D = np.zeros((A.size,B.size),dtype=cell)#([('H', 1), ('V', 0)], dtype=cell)
#    for i in range(1,A.size):
#        D[i][0]=('',-i)
#    for i in range(1,B.size):
#        D[0][i]=('',-i)
#    for i in range(1,A.size):
#        for j in range(1,B.size):
#            candidates = [D[i-1][j-1]['value']+alignment_nw(A[i],B[j]), D[i-1][j]['value']-1,D[i][j-1]['value']-1]
#            #print('intex i: {}, j: {}, candidates: {}'.format(i,j,candidates))
#            index_array = np.argwhere(candidates == np.amax(candidates)).flatten().tolist()
#            print(index_array)
#            D[i][j]['value']=candidates[index_array[-1]]
#            for k in index_array:
#                if k == 0:
#                    D[i][j]['symbol']+="\\"
#                elif k == 1:
#                    D[i][j]['symbol']+='^'
#                elif k == 2:
#                    D[i][j]['symbol']+='<'
#            #print(index_array)
#            #print('A[i-1]: {},B[j-1]: {},B[j]: {})'.format(A[i-1],B[j-1],B[j]))
#    print(D)
#    #Tracing arrows back
#    print(D[3][4]['symbol'])
#    return