BioInfa 9.1

import numpy


def match_mismatch(first_dna, second_dna, i, j):
    first_dna = " " + first_dna
    second_dna = " " + second_dna
    return 1 if first_dna[j] == second_dna[i] else 0

def print_norm_first(first):
    for i in range(1, len(first)):
        if first[i] == "-":
            first[i] = first[i-1]
            first[i-1] = "-"
    print(first)

def find_alignment(p, first_dna, second_dna, n, m, new_first, new_second, d, match, mismatch):
    i = n
    j = m
    while i > 0 or j > 0:
        score = p[i, j]
        score_up = p[i - 1, j]
        score_left = p[i, j - 1]
        score_diag = p[i - 1, j - 1]
        if score == score_up + d:
            new_first.append("-")
            new_second.append(second_dna[i - 1])
            i -= 1
        elif score == score_left + d:
            new_first.append(first_dna[j - 1])
            new_second.append("-")
            j -= 1

        elif score == score_diag + match or score == score_diag + mismatch:
            new_first.append(first_dna[j - 1])
            new_second.append(second_dna[i - 1])
            i -= 1
            j -= 1

    if i > 0:
        new_second.append("_")
        i -= 1
    if j > 0:
        new_first.append("_")
        j -= 1
    return new_first, new_second


def find_sum(match, mismatch, gap, first, second, local):
    n = len(first)
    l = 0  # count of matches
    f = 0  # count of mismatches
    u = 0  # count of indels
    for k in range(0, n - 1):
        if first[k] == second[k]:
            l += 1
        elif first[k] == "-" or second[k] == "-":
            u += 1
        else:
            f += 1
    if local:
        print("Final score=", match * (l + 1) + mismatch * f + gap * u, " match=", l + 1, "mismatch=", f, "gap=", u)
    else:
        print("Final score=", match * l + mismatch * f + gap * u, " match=", l, "mismatch=", f, "gap=", u)


def global_alignment(n, m, match, mismatch, gap, first_dna, second_dna):
    local = 0
    p = numpy.zeros((n + 1, m + 1), dtype=numpy.int64)
    new_first = []
    new_second = []
    for j in range(1, m + 1):
        p[0, j] = p[0, j - 1] + gap
    for i in range(1, n + 1):
        p[i, 0] = p[i - 1, 0] + gap
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            g = match_mismatch(first_dna, second_dna, i, j)
            if g:
                first_func = p[i - 1, j - 1] + match
            else:
                first_func = p[i - 1, j - 1] + mismatch
            second_func = p[i - 1, j] + gap
            third_func = p[i, j - 1] + gap
            p[i, j] = max(first_func, second_func, third_func)
    find_alignment(p, first_dna, second_dna, n, m, new_first, new_second, gap_fine, match, mismatch)
    find_sum(match, mismatch, gap, new_first, new_second, local)
    print_norm_first(new_first[::-1])
    print(new_second[::-1])


def max_in_matrix(matrix, n, m):
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if max(map(max, matrix)) == matrix[i, j]:
                return i, j


def find_alignment_local(p, first_dna, second_dna, n, m, new_first, new_second, d, match, mismatch):
    i, j = max_in_matrix(p, n, m)
    score = p[i, j]
    while score != 0:
        score_up = p[i - 1, j]
        score_left = p[i, j - 1]
        score_diag = p[i - 1, j - 1]
        if score == score_up + d and i > 0:
            new_first.append("-")
            new_second.append(second_dna[i - 1])
            i = i - 1
            score = p[i, j]
        elif score == score_left + d:
            new_first.append(first_dna[j - 1])
            new_second.append("-")
            j = j - 1
            score = p[i, j]
        elif (score == score_diag + match or score == score_diag + mismatch) and i > 0 and j > 0:
            new_first.append(first_dna[j - 1])
            new_second.append(second_dna[i - 1])
            i = i - 1
            j = j - 1
            score = p[i, j]

    return new_first, new_second


def local_alignment(n, m, match, mismatch, gap, first_dna, second_dna):
    p = numpy.zeros((n + 1, m + 1), dtype=numpy.int64)
    local = 1
    new_first = []
    new_second = []
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if first_dna[j - 1] == second_dna[i - 1]:
                first_func = p[i - 1, j - 1] + match
            else:
                first_func = p[i - 1, j - 1] + mismatch
            second_func = p[i - 1, j] + gap
            third_func = p[i, j - 1] + gap
            p[i, j] = max(0, first_func, second_func, third_func)
    find_alignment_local(p, first_dna, second_dna, n, m, new_first, new_second, gap, match, mismatch)
    find_sum(match, mismatch, gap, new_first, new_second, local)
    print(new_first[::-1])
    print(new_second[::-1])


if __name__ == '__main__':
    first_dna = input("Enter first DNA\n")
    second_dna = input("Enter second DNA\n")
    match_bonus = int(input("Enter match bonus\n"))
    mismatch_fine = int(input("Enter mismatch fine\n"))
    gap_fine = int(input("Enter gap fine\n"))
    alignmentType = input("Enter type of alignment(G or L)\n")
    m = len(first_dna)
    n = len(second_dna)
    if alignmentType == "G":
        global_alignment(n, m, match_bonus, mismatch_fine, gap_fine, first_dna, second_dna)
    else:
        local_alignment(n, m, match_bonus, mismatch_fine, gap_fine, first_dna, second_dna)