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

Question

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

CGCAATTCTGAAGCGCTGGGGAAGACGGGT & TATCCCATCGAACGCCTATTCTAGGAT 

где стоят 24 надлежащее выравнивание, но я получаю стоимость 23

И я должен прочитать стоимость переключения баз Say в 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 

Я сделал словарь питона, который связывает все основания в совершенстве, что выглядит.

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

Если функция дифф is

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

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

EDIT: Вот полуработающая версия, по крайней мере, стоимость редактирования права.

AGTTGTGAAAGAACAAGCGCACAATATTGCCGCGCCGAAAGCT,TTCTTTCATTATTCAA‌​ATGTATAGTTTAGAGCGTTA‌​A 

Answer 1

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

Рассмотрите две последовательности A и B, каждая из которых имеет длину n. Если мы посмотрим на статьи в википедии для алгоритмов Needleman-Wunsch и 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