import numpy as np

def needleman_wunsch(seq1, seq2, match_score=1, mismatch_score=-1, gap_penalty=-1):

len_seq1 = len(seq1)

len_seq2 = len(seq2)

# Initialize the scoring matrix

scoring_matrix = np.zeros((len_seq1 + 1, len_seq2 + 1))

# Initialize the traceback matrix

traceback_matrix = np.zeros((len_seq1 + 1, len_seq2 + 1), dtype=int)

# Initialize the first row and column of the scoring matrix

for i in range(len_seq1 + 1):

    scoring_matrix[i, 0] = i * gap_penalty

    traceback_matrix[i, 0] = 1

for j in range(len_seq2 + 1):

    scoring_matrix[0, j] = j * gap_penalty

    traceback_matrix[0, j] = 2

# Fill in the scoring matrix and traceback matrix

for i in range(1, len_seq1 + 1):

    for j in range(1, len_seq2 + 1):

        match = scoring_matrix[i - 1, j - 1] + (match_score if seq1[i - 1] == seq2[j - 1] else mismatch_score)

        delete = scoring_matrix[i - 1, j] + gap_penalty

        insert = scoring_matrix[i, j - 1] + gap_penalty

        scoring_matrix[i, j] = max(match, delete, insert)

        if scoring_matrix[i, j] == match:

            traceback_matrix[i, j] = 0

        elif scoring_matrix[i, j] == delete:

            traceback_matrix[i, j] = 1

        else:

            traceback_matrix[i, j] = 2

# Perform traceback to find the alignment

aligned_seq1 = ''

aligned_seq2 = ''

i = len_seq1

j = len_seq2
while i > 0 or j > 0:

    if traceback_matrix[i, j] == 0:

        aligned_seq1 = seq1[i - 1] + aligned_seq1

        aligned_seq2 = seq2[j - 1] + aligned_seq2

        i -= 1

        j -= 1

    elif traceback_matrix[i, j] == 1:

        aligned_seq1 = seq1[i - 1] + aligned_seq1

        aligned_seq2 = '-' + aligned_seq2

        i -= 1

    else:
        aligned_seq1 = '-' + aligned_seq1
        aligned_seq2 = seq2[j - 1] + aligned_seq2
        j -= 1
return aligned_seq1, aligned_seq2, scoring_matrix[len_seq1, len_seq2]

seq1 = "ACGT" seq2 = "AGCT" aligned_seq1, aligned_seq2, alignment_score = needleman_wunsch(seq1, seq2) print("Aligned Sequence 1:", aligned_seq1) print("Aligned Sequence 2:", aligned_seq2) print("Alignment Score:", alignment_score)

import numpy as np

def smith_waterman(seq1, seq2, match_score=1, mismatch_score=-1, gap_penalty=-1):

len_seq1 = len(seq1)

len_seq2 = len(seq2)



# Initialize the scoring matrix

scoring_matrix = np.zeros((len_seq1 + 1, len_seq2 + 1))



# Initialize the traceback matrix

traceback_matrix = np.zeros((len_seq1 + 1, len_seq2 + 1), dtype=int)



# Initialize variables to keep track of the maximum score and its position

max_score = 0

max_position = (0, 0)



# Fill in the scoring matrix and traceback matrix

for i in range(1, len_seq1 + 1):

    for j in range(1, len_seq2 + 1):

        match = scoring_matrix[i - 1, j - 1] + (match_score if seq1[i - 1] == seq2[j - 1] else mismatch_score)

        delete = scoring_matrix[i - 1, j] + gap_penalty

        insert = scoring_matrix[i, j - 1] + gap_penalty

        zero = 0  # Extra case for local alignment

        scoring_matrix[i, j] = max(match, delete, insert, zero)

        if scoring_matrix[i, j] == zero:

            traceback_matrix[i, j] = 0

        elif scoring_matrix[i, j] == match:

            traceback_matrix[i, j] = 1

        elif scoring_matrix[i, j] == delete:

            traceback_matrix[i, j] = 2

        else:

            traceback_matrix[i, j] = 3

        # Update the maximum score and its position

        if scoring_matrix[i, j] > max_score:

            max_score = scoring_matrix[i, j]

            max_position = (i, j)

# Perform traceback starting from the maximum score position

aligned_seq1 = ''

aligned_seq2 = ''

i, j = max_position

while i > 0 and j > 0 and scoring_matrix[i, j] > 0:

    if traceback_matrix[i, j] == 1:

        aligned_seq1 = seq1[i - 1] + aligned_seq1

        aligned_seq2 = seq2[j - 1] + aligned_seq2

        i -= 1

        j -= 1

    elif traceback_matrix[i, j] == 2:

        aligned_seq1 = seq1[i - 1] + aligned_seq1

        aligned_seq2 = '-' + aligned_seq2

        i -= 1

    elif traceback_matrix[i, j] == 3:

        aligned_seq1 = '-' + aligned_seq1

        aligned_seq2 = seq2[j - 1] + aligned_seq2

        j -= 1

    else:

        break


return aligned_seq1, aligned_seq2, max_score

seq1 = "ATCG"

seq2 = "AGTC"

aligned_seq1, aligned_seq2, max_score = smith_waterman(seq1, seq2)

print("Aligned Sequence 1:", aligned_seq1)

print("Aligned Sequence 2:", aligned_seq2)

print("Maximum Score:", max_score)