Smith-Waterman Implement in python-CodePudding

I want to write the first part of the Smith-Waterman algorithm in python with basic functions.

I found this

Any help please Thanks

CodePudding user response：

the image algorithm implementation:

M = []
for i in range(n):
    M.append([])
    for j in range(m):
        first = max(M[i - 1][j - 1]   score(s[i], t[j])
        second = M[i - 1][j]   penal
        third = M[i][j - 1]   penal

        M[i].append(first, second, third, 0))

But you will have to fix the edge cases (out of range) and add some default values.

CodePudding user response：

The problems with the code you presented are well described in the comments in that piece of code.

Assuming that you want a linear gap-penalty of 2 points, and you are looking for the first phase algorithm only (so excluding the trace-back process), the code can be fixed as follows:

def score(x, y):
    return 4 if x == y else (
        -4 if '-' in (x, y) else -2
    )

def zeros(a, b):
    penalty = 2  # linear penalty (see Wikipedia)
    nextrow = [0] * (len(b)   1)
    matrix = [nextrow]
    for valA in a:
        row, nextrow = nextrow, [0]
        for m, valB in enumerate(b):
            nextrow.append(max(
                row[m]   score(valA, valB),
                row[m 1] - penalty,
                nextrow[m] - penalty,
                0
            ))
        matrix.append(nextrow)
    return matrix

# Example run:
result = zeros("ACGT", "AC-GT")
print(result)