Вычисление расстояния редактирования последовательности ДНК питона

Итак, мне дали задание согласовать наименьшую стоимость между двумя последовательностями ДНК. Один из неудачных входов:

CGCAATTCTGAAGCGCTGGGGAAGACGGGT & TATCCCATCGAACGCCTATTCTAGGAT

Правильное выравнивание стоит 24, но я получаю стоимость 23.

Я должен прочитать стоимость переключения баз, скажем, A -> T, G -> C и т. д. и т. д.. Файл стоимости, который мне дали, выглядит следующим образом:

*,-,A,T,G,C
-,0,1,2,1,3
A,1,0,1,5,1
T,2,1,0,9,1
G,1,5,9,0,1
C,3,1,1,1,0

Я сделал словарь Python, который отлично связывает все базы, который выглядит так:

{'AT': '1', '-C': '3', 'TG': '9', '-G': '1', 'AC': '1', 'C-': '3', 'CA': '1', 'AA': '0', '--': '0', 'TA': '1', 'T-': '2', 'CG': '1', '-T': '2', 'CC': '0', 'GG': '0', 'A-': '1', 'CT': '1', 'AG': '5', 'GC': '1', 'GT': '9', 'GA': '5', 'G-': '1', '-A': '1', 'TC': '1', 'TT': '0'}

В настоящее время моя реализация работает в некоторых случаях, а в других случаях я ошибаюсь на +/- 1.

Вот фрагмент моего кода:

def align(one_Line, costBook):
    Split_Line = one_Line.split(",")
    array = [[0] * len(Split_Line[1]) for i in Split_Line[0]]  # Zero fill array,

    xLine = Split_Line[0]
    yLine = Split_Line[1]

    for i in range(1, len(xLine)):
        array[i][0] = array[i - 1][0] + int(costBook['-' + xLine[i - 1]])
    for i in range(1, len(yLine)):
        array[0][i] = array[0][i - 1] + int(costBook[yLine[i - 1] + '-'])

    for i in range(1, len(xLine)):
        for j in range(1, len(yLine)):
            array[i][j] = min(array[i - 1][j] + diff('-', xLine[i], costBook), 
                              array[i][j - 1] + diff(yLine[j], '-', costBook), 
                              array[i - 1][j - 1] + diff(yLine[j], xLine[i], costBook))

Где функция diff:

def diff(x, y, cost):
    if x == y:
        return 0
    keyStr = x + y
    return int(costBook[keyStr])

Где я ошибаюсь? Это в фактическом заполнении массива, или я неправильно делаю базовые случаи?

РЕДАКТИРОВАТЬ: Вот полурабочая версия, по крайней мере, стоимость редактирования правильная:

AGTTGTGAAAGAACAAGCGCACAATATTGCCGCGCCGAAAGCT,TTCTTTCATTATTCAA‌​ATGTATAGTTTAGAGCGTTA‌​A

python bioinformatics dynamic-programming dna-sequence
person Dringo    schedule 21.02.2017    source источник
comment
Это должен быть алгоритм Нидлмана-Вунша?   -  person nbryans    schedule 22.02.2017
comment
Кроме того, как узнать, какой должна быть правильная стоимость выравнивания?   -  person nbryans    schedule 22.02.2017
comment
Аналогично, но не совсем, длина каждой соответствующей последовательности может быть любой. И стоимость совпадения, несоответствия или разрыва может варьироваться. О, и надлежащие расходы были даны   -  person Dringo    schedule 22.02.2017

Ответы (1)


arrow_upward
4
arrow_downward

Я считаю, что причина того, что ваш алгоритм не работает, заключается в том, что вы не учитываете строку «пробел» в своем массиве (матрица оценок).

Рассмотрим две последовательности A и B, каждая из которых имеет длину n. Если мы посмотрим на статьи в Википедии для Needleman-Wunsch и < href="https://en.wikipedia.org/wiki/Smith%E2%80%93Waterman_algorithm" rel="nofollow noreferrer">Smith-Waterman, мы видим, что в их соответствующих "оценочных" матрицах в начале есть лишняя строка. Это должно представлять либо первый символ A, либо B в паре с пробелом. Я рекомендую вам быстро просмотреть эти страницы, чтобы понять, что я имею в виду.

Когда вы определяете свой массив как:

array = [[0] * len(Split_Line[1]) for i in Split_Line[0]]

Вы не включаете эту дополнительную строку.

Вам нужно будет изменить функцию align, чтобы добавить эту дополнительную строку, и изменить логику для вычисления оценки. то есть:

def align(one_Line, costBook):
    Split_Line = one_Line.split(",")

    # Defining an array with an extra row and col to represent a leading gap
    array = [[0] * (len(Split_Line[1])+1) for i in range(len(Split_Line[0])+1)]  # Zero fill array,

    xLine = Split_Line[0]
    yLine = Split_Line[1]

    # Changed so we include our extra line in the loop
    for i in range(1, len(xLine)+1):
        array[i][0] = array[i - 1][0] + int(costBook['-' + xLine[i - 1]])
    for i in range(1, len(yLine)+1):
        array[0][i] = array[0][i - 1] + int(costBook[yLine[i - 1] + '-'])

    # Changed so we include our extra row/col in the loop
    for i in range(1, len(xLine)+1):
        for j in range(1, len(yLine)+1):
            # The references to the original string now need -1 (i.e. i-1)
            array[i][j] = min(array[i - 1][j] + diff('-', xLine[i-1], costBook), 
                              array[i][j - 1] + diff(yLine[j-1], '-', costBook), 
                              array[i - 1][j - 1] + diff(yLine[j-1], xLine[i-1], costBook))
    return array
person nbryans    schedule 21.02.2017