from Bio.SubsMat import MatrixInfo
from Bio import SeqIO

def global_alignment_score(input):
    return tmp(input)[1]

def affine_penalty(sigma, eps, k):
    return sigma + eps * (k - 1)


def tmp(input):
    blosum = MatrixInfo.blosum62
    fasta_sequences = SeqIO.parse(open(input), 'fasta')
    first = str(next(fasta_sequences).seq)
    second = str(next(fasta_sequences).seq)
    gap_opening = 11
    gap_extension = 1

    lower = [[0]]
    middle = [[("",0)]]
    upper = [[0]]

    # 1 = rechts 0 = schuin 2 = onder

    for i in range(1,len(first)+1):
        upper[0].append(-gap_opening)
        lower[0].append(-affine_penalty(gap_opening, gap_extension, i))
        middle[0].append(("1",-affine_penalty(gap_opening, gap_extension, i)))


    for i in range(1, len(second)+1):
        lower.append([-gap_opening])
        upper.append([-affine_penalty(gap_opening, gap_extension, i)])
        middle.append([("2", -affine_penalty(gap_opening, gap_extension, i))])


    for i in range(1, len(second)+1):
        for j in range(1, len(first)+1):
            maxLower = max(lower[i-1][j]-gap_extension, middle[i-1][j][1]-gap_opening)
            maxUpper = max(upper[i][j-1]-gap_extension, middle[i][j-1][1]-gap_opening)

            maxMiddle = middle[i-1][j-1][1]
            code = 0
            if (first[j - 1], second[i - 1]) in blosum:
                maxMiddle += blosum[(first[j - 1], second[i - 1])]
            else:
                maxMiddle += blosum[(second[i - 1], first[j - 1])]

            if maxLower > maxMiddle:
                code = 2
                maxMiddle = maxLower
            if maxUpper > maxMiddle:
                code = 1
                maxMiddle = maxUpper

            lower[i].append(maxLower)
            upper[i].append(maxUpper)
            middle[i].append((middle[i-1][j-1][0]+str(code), maxMiddle))

    code = middle[-1][-1][0]
    fi = []
    se = []
    index1 = 0
    index2 = 0
    for i in range(0, len(code)):
        if code[i] == '0':
            fi.append(first[index1])
            se.append(second[index2])
            index1 += 1
            index2 += 1
        elif code[i] == '1':
            fi.append(first[index1])
            se.append('-')
            index1 += 1
        else:
            fi.append('-')
            se.append(second[index2])
            index2 += 1

    return [(''.join(fi), ''.join(se)), middle[-1][-1][1]]


def global_alignment(input):
    return tmp(input)[0]