https en wikipedia orgwikismithe28093watermanalgorithm the smithwaterman algorithm is a dynamic programming algorithm used for sequence alignment it is particularly useful for finding similarities between two sequences such as dna or protein sequences in this implementation gaps are penalized linearly meaning that the score is reduced by a fixed amount for each gap introduced in the alignment however it s important to note that the smithwaterman algorithm supports other gap penalty methods as well calculate the score for a character pair based on whether they match or mismatch returns 1 if the characters match 1 if they mismatch and 2 if either of the characters is a gap scorefunction a a 1 scorefunction a c 1 scorefunction a 2 scorefunction a 2 scorefunction 2 perform the smithwaterman local sequence alignment algorithm returns a 2d list representing the score matrix each value in the matrix corresponds to the score of the best local alignment ending at that point smithwaterman acac ca 0 0 0 0 0 1 0 1 0 0 0 2 0 1 0 smithwaterman acac ca 0 0 0 0 0 1 0 1 0 0 0 2 0 1 0 smithwaterman acac ca 0 0 0 0 0 1 0 1 0 0 0 2 0 1 0 smithwaterman acac ca 0 0 0 0 0 1 0 1 0 0 0 2 0 1 0 smithwaterman acac 0 0 0 0 0 smithwaterman ca 0 0 0 smithwaterman acac ca 0 0 0 0 0 1 0 1 0 0 0 2 0 1 0 smithwaterman acac ca 0 0 0 0 0 1 0 1 0 0 0 2 0 1 0 smithwaterman acac ca 0 0 0 0 0 1 0 1 0 0 0 2 0 1 0 smithwaterman acac ca 0 0 0 0 0 1 0 1 0 0 0 2 0 1 0 smithwaterman acac 0 0 0 0 0 smithwaterman ca 0 0 0 smithwaterman agt agt 0 0 0 0 0 1 0 0 0 0 2 0 0 0 0 3 smithwaterman agt gta 0 0 0 0 0 0 0 1 0 1 0 0 0 0 2 0 smithwaterman agt gtc 0 0 0 0 0 0 0 0 0 1 0 0 0 0 2 0 smithwaterman agt g 0 0 0 0 0 1 0 0 smithwaterman g agt 0 0 0 0 0 0 1 0 smithwaterman agt agtct 0 0 0 0 0 0 0 1 0 0 0 0 0 0 2 0 0 0 0 0 0 3 1 1 smithwaterman agtct agt 0 0 0 0 0 1 0 0 0 0 2 0 0 0 0 3 0 0 0 1 0 0 0 1 smithwaterman agtct gtc 0 0 0 0 0 0 0 0 0 1 0 0 0 0 2 0 0 0 0 3 0 0 1 1 make both query and subject uppercase initialize score matrix calculate scores for each cell take maximum score make both query and subject uppercase query query upper subject subject upper find the indices of the maximum value in the score matrix maxvalue floatinf imax jmax 0 for i row in enumeratescore for j value in enumeraterow if value maxvalue maxvalue value imax jmax i j traceback logic to find optimal alignment i imax j jmax align1 align2 gap scorefunction guard against empty query or subject if i 0 or j 0 return while i 0 and j 0 if scoreij scorei 1j 1 scorefunction queryi 1 subjectj 1 optimal path is a diagonal take both letters align1 queryi 1 align1 align2 subjectj 1 align2 i 1 j 1 elif scoreij scorei 1j gap optimal path is a vertical align1 queryi 1 align1 align2 falign2 i 1 else optimal path is a horizontal align1 falign1 align2 subjectj 1 align2 j 1 return falign1nalign2 if name main query heagawghee subject pawheae score smithwatermanquery subject match1 mismatch1 gap2 printtracebackscore query subject calculate the score for a character pair based on whether they match or mismatch returns 1 if the characters match 1 if they mismatch and 2 if either of the characters is a gap score_function a a 1 score_function a c 1 score_function a 2 score_function a 2 score_function 2 perform the smith waterman local sequence alignment algorithm returns a 2d list representing the score matrix each value in the matrix corresponds to the score of the best local alignment ending at that point smith_waterman acac ca 0 0 0 0 0 1 0 1 0 0 0 2 0 1 0 smith_waterman acac ca 0 0 0 0 0 1 0 1 0 0 0 2 0 1 0 smith_waterman acac ca 0 0 0 0 0 1 0 1 0 0 0 2 0 1 0 smith_waterman acac ca 0 0 0 0 0 1 0 1 0 0 0 2 0 1 0 smith_waterman acac 0 0 0 0 0 smith_waterman ca 0 0 0 smith_waterman acac ca 0 0 0 0 0 1 0 1 0 0 0 2 0 1 0 smith_waterman acac ca 0 0 0 0 0 1 0 1 0 0 0 2 0 1 0 smith_waterman acac ca 0 0 0 0 0 1 0 1 0 0 0 2 0 1 0 smith_waterman acac ca 0 0 0 0 0 1 0 1 0 0 0 2 0 1 0 smith_waterman acac 0 0 0 0 0 smith_waterman ca 0 0 0 smith_waterman agt agt 0 0 0 0 0 1 0 0 0 0 2 0 0 0 0 3 smith_waterman agt gta 0 0 0 0 0 0 0 1 0 1 0 0 0 0 2 0 smith_waterman agt gtc 0 0 0 0 0 0 0 0 0 1 0 0 0 0 2 0 smith_waterman agt g 0 0 0 0 0 1 0 0 smith_waterman g agt 0 0 0 0 0 0 1 0 smith_waterman agt agtct 0 0 0 0 0 0 0 1 0 0 0 0 0 0 2 0 0 0 0 0 0 3 1 1 smith_waterman agtct agt 0 0 0 0 0 1 0 0 0 0 2 0 0 0 0 3 0 0 0 1 0 0 0 1 smith_waterman agtct gtc 0 0 0 0 0 0 0 0 0 1 0 0 0 0 2 0 0 0 0 3 0 0 1 1 make both query and subject uppercase initialize score matrix calculate scores for each cell take maximum score perform traceback to find the optimal local alignment starts from the highest scoring cell in the matrix and traces back recursively until a 0 score is found returns the alignment strings traceback 0 0 0 0 0 1 0 1 0 0 0 2 0 1 0 acac ca ca nca traceback 0 0 0 0 0 1 0 1 0 0 0 2 0 1 0 acac ca ca nca traceback 0 0 0 0 0 1 0 1 0 0 0 2 0 1 0 acac ca ca nca traceback 0 0 0 0 0 1 0 1 0 0 0 2 0 1 0 acac ca ca nca traceback 0 0 0 acac make both query and subject uppercase find the indices of the maximum value in the score matrix traceback logic to find optimal alignment guard against empty query or subject optimal path is a diagonal take both letters optimal path is a vertical optimal path is a horizontal
def score_function(
    source_char: str,
    target_char: str,
    match: int = 1,
    mismatch: int = -1,
    gap: int = -2,
) -> int:
    
    if "-" in (source_char, target_char):
        return gap
    return match if source_char == target_char else mismatch


def smith_waterman(
    query: str,
    subject: str,
    match: int = 1,
    mismatch: int = -1,
    gap: int = -2,
) -> list[list[int]]:
    
    
    query = query.upper()
    subject = subject.upper()

    
    m = len(query)
    n = len(subject)
    score = [[0] * (n + 1) for _ in range(m + 1)]
    kwargs = {"match": match, "mismatch": mismatch, "gap": gap}

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            
            match = score[i - 1][j - 1] + score_function(
                query[i - 1], subject[j - 1], **kwargs
            )
            delete = score[i - 1][j] + gap
            insert = score[i][j - 1] + gap

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

    return score


def traceback(score: list[list[int]], query: str, subject: str) -> str:
    r
    
    query = query.upper()
    subject = subject.upper()
    
    max_value = float("-inf")
    i_max = j_max = 0
    for i, row in enumerate(score):
        for j, value in enumerate(row):
            if value > max_value:
                max_value = value
                i_max, j_max = i, j
    
    i = i_max
    j = j_max
    align1 = ""
    align2 = ""
    gap = score_function("-", "-")
    
    if i == 0 or j == 0:
        return ""
    while i > 0 and j > 0:
        if score[i][j] == score[i - 1][j - 1] + score_function(
            query[i - 1], subject[j - 1]
        ):
            
            align1 = query[i - 1] + align1
            align2 = subject[j - 1] + align2
            i -= 1
            j -= 1
        elif score[i][j] == score[i - 1][j] + gap:
            
            align1 = query[i - 1] + align1
            align2 = f"-{align2}"
            i -= 1
        else:
            
            align1 = f"-{align1}"
            align2 = subject[j - 1] + align2
            j -= 1

    return f"{align1}\n{align2}"


if __name__ == "__main__":
    query = "HEAGAWGHEE"
    subject = "PAWHEAE"

    score = smith_waterman(query, subject, match=1, mismatch=-1, gap=-2)
    print(traceback(score, query, subject))