функция глобальной последовательности выравнивания

Question

Я пытаюсь реализовать алгоритм Нидлмана-Вунша , чтобы получить минимальную оценку в функции глобального выравнивания, но вместо получения минимальной оценки 0, когда обе последовательности равны, я получаю 8.

В чем проблема с этим кодом?

alphabet = ["A", "C", "G", "T"] 
score = [[0, 4, 2, 4, 8], \
     [4, 0, 4, 2, 8], \
     [2, 4, 0, 4, 8], \
     [4, 2, 4, 0, 8], \
     [8, 8, 8, 8, 8]]

def globalAlignment(x, y):
#Dynamic version very fast
    D = []
    for i in range(len(x)+1):
        D.append([0]* (len(y)+1))

    for i in range(1, len(x)+1):
        D[i][0] = D[i-1][0] + score[alphabet.index(x[i-1])][-1]
    for i in range(len(y)+1):
        D[0][i] = D[0][i-1]+ score[-1][alphabet.index(y[i-1])]

    for i in range(1, len(x)+1):
        for j in range(1, len(y)+1):
            distHor = D[i][j-1]+ score[-1][alphabet.index(y[j-1])]
            distVer = D[i-1][j]+ score[-1][alphabet.index(x[i-1])]
            if x[i-1] == y[j-1]:
                distDiag = D[i-1][j-1]
            else:
                distDiag = D[i-1][j-1] + score[alphabet.index(x[i-1])][alphabet.index(y[j-1])]

            D[i][j] = min(distHor, distVer, distDiag)

    return D[-1][-1]

x = "ACGTGATGCTAGCAT"
y = "ACGTGATGCTAGCAT"
print(globalAlignment(x, y))

Answer 1

Я исправил проблему, поставив 0 вместо 8 в последнем списке результатов;

alphabet = ["A", "C", "G", "T"] 
score = [[0, 4, 2, 4, 8], \
     [4, 0, 4, 2, 8], \
     [2, 4, 0, 4, 8], \
     [4, 2, 4, 0, 8], \
     [0, 0, 0, 0, 0]]

def globalAlignment(x, y):
#Dynamic version very fast
D = []
for i in range(len(x)+1):
    D.append([0]* (len(y)+1))

for i in range(1, len(x)+1):
    D[i][0] = D[i-1][0] + score[alphabet.index(x[i-1])][-1]
for i in range(len(y)+1):
    D[0][i] = D[0][i-1]+ score[-1][alphabet.index(y[i-1])]

for i in range(1, len(x)+1):
    for j in range(1, len(y)+1):
        distHor = D[i][j-1]+ score[-1][alphabet.index(y[j-1])]
        distVer = D[i-1][j]+ score[alphabet.index(x[i-1])][-1]
        if x[i-1] == y[j-1]:
            distDiag = D[i-1][j-1]
        else:
            distDiag = D[i-1][j-1] + score[alphabet.index(x[i-1])][alphabet.index(y[j-1])]

        D[i][j] = min(distHor, distVer, distDiag)

return D[-1][-1]    

Answer 2

Не менее

distHor = D[i][j-1]+ score[-1][alphabet.index(y[j-1])]
distVer = D[i-1][j]+ score[-1][alphabet.index(x[i-1])]

подозрительно, так как вы не использовали одно и то же место для [-1] в инициализации, и оба расстояния вряд ли будут использовать одно и то же направление в весах...
Я думаю, это должно быть

score[alphabet.index(x[i-1])][-1]

, но это может быть не единственной ошибкой ...