Блог

Главная - Вопросы по программированию - Реализация Смита-Уотермана в python

Реализация Смита-Уотермана в python

#python #algorithm #function #sequence-alignment

Вопрос:

Я хочу написать первую часть алгоритма Смита-Уотермана на python с базовыми функциями.

Я нашел этот пример, но он не дает мне того, что я ищу.

 def zeros(X: int, Y: int):
    #        ^       ^  incorrect type annotations. should be str
    lenX = len(X)   1
    lenY = len(Y)   1
    matrix = []
    for i in range(lenX):
        matrix.append([0] * lenY)
    # A more "pythonic" way of expressing the above would be:
    # matrix = [[0] * len(Y)   1 for _ in range(len(x)   1)]
    
    def score(X, Y):
        #     ^  ^ shadowing variables from outer scope. this is not a bug per se but it's considered bad practice
        if X[n] == Y[m]: return 4
        #    ^       ^  variables not defined in scope
        if X[n] == '-' or Y[m] == '-': return -4
        #    ^              ^  variables not defined in scope
        else: return -2

    def SmithWaterman(X, Y, score): # this function is never called
        #                   ^ unnecessary function passed as parameter. function is defined in scope
        for n in range(1, len(X)   1):
            for m in range(1, len(Y)   1):
                align = matrix[n-1, m-1]   (score(X[n-1], Y[m-1]))
                #                 ^ invalid list lookup. should be: matrix[n-1][m-1]
                indelX = matrix[n-1, m]   (score(X[n-1], Y[m]))
                #                                          ^ out of bounds error when m == len(Y)
                indelY = matrix[n, m-1]   (score(X[n], Y[m-1]))
                #                                  ^ out of bounds error when n == len(X)
        matrix[n, m] = max(align, indelX, indelY, 0)
        # this should be nested in the inner for-loop. m, n, indelX, and indelY are not defined in scope here
    print(matrix)

zeros("ACGT", "ACGT")

В книге я нашел этот алгоритм, но не смог его правильно реализовать.

 input: sequences s and t, with |s| =n, |t| = m, score function, penality InDel

совпадение 1, несоответствие -2, несоответствие -1

 M = matrix of size n 1 * m 1
M[i,j] = 0
i=j=0

введите описание изображения здесь

Любая помощь, пожалуйста
Спасибо

Комментарии:

1. в чем заключалась проблема в реализации примера? Это кажется довольно простым

2. Я новичок в python (:

3. Вы должны, по крайней мере, определить, какие штрафы за разрыв и какую формулу оценки вы хотите использовать. Это свободный выбор, но он должен быть сделан. Этот выбор зависит от мнения, поэтому он не может быть предметом вопроса. Вам придется сказать нам, каким должно быть их определение.

4. Спасибо @trincot. Это параметры: совпадение est 1 и несоответствие -2. Функция оценки может быть такой, как в примере

5. Таким образом, штраф является постоянным, не зависящим от размера разрыва?

Ответ №1:

Проблемы с представленным вами кодом хорошо описаны в комментариях к этому фрагменту кода.

Предполагая, что вам нужен линейный штраф за разрыв в 2 балла, и вы ищете только алгоритм первой фазы (поэтому исключая процесс отслеживания), код можно исправить следующим образом:

 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)

Ответ №2:

реализация алгоритма изображения:

 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))

Но вам придется исправить крайние случаи (вне диапазона) и добавить некоторые значения по умолчанию.

Метки: