Hola, buenas tardes.
Mi duda trata sobre el algoritmo Needleman Wunsch que usa la programación dinámica. Tengo un código pero al probar un ejemplo no obtengo el resultado correcto.
Me dan este ejemplo:
Using text Syntax Highlighting
secuencia_1
TTTTTTTT
secuencia_2
ATTTTTTTTA
Coloreado en 0.000 segundos, usando
GeSHi 1.0.8.4
La salida del alineamiento debería ser:
Using text Syntax Highlighting
-TTTTTTTT-
ATTTTTTTTA
puntuación 6.0
Coloreado en 0.000 segundos, usando
GeSHi 1.0.8.4
La primera parte del código es la de inicialización
Using python Syntax Highlighting
match = 1
mismatch = -1
gap = -2
longitud_1 = len(sec1) + 1
longitud_2 = len(sec2) + 1
F = [[ 0 for _ in range(longitud_1)] for _ in range(longitud_2)] #inicializacion de la matriz F con 0
#MATRIZ DE SIMILARIDAD - INICIALIZACION
#Casos base: primera fila y primera columna
for i in range(longitud_1):
F[i][0] = gap * i
for j in range(longitud_2):
F[0][j] = gap * j
#Resto de casos
for i in range(1,longitud_1):
for j in range(1,longitud_2):
b = sec1[i-1] == sec2[j-1]
if b:
suma = match
else:
suma = mismatch
F[i][j] = max(F[i-1][j-1] + suma, F[i][j-1] + gap, F[i-1][j] + gap)
score = F[longitud_1-1][longitud_2-1]
Coloreado en 0.004 segundos, usando
GeSHi 1.0.8.4
Y la segunda parte es la de [i]traceback[/i], que me devuelva el alineamiento:
Using python Syntax Highlighting
#TRACEBACK-->BUSCAR EL MEJOR ALINEAMIENTO
alineamiento_1 = " "
alineamiento_2 = " "
while (i > 0 and j > 0):
puntuacion = F[j][i]
puntuacion_diag = F[j-1][i-1]
puntuacion_up = F[j-1][i]
puntuacion_left = F[j][i-1]
if puntuacion == puntuacion_diag + suma:
alineamiento_1 = sec1[i-1] + alineamiento_1
alineamiento_2 = sec2[j-1] + alineamiento_2
i = i-1
j = j-1
elif puntuacion == puntuacion_left + gap:
alineamiento_1 = sec1[i-1] + alineamiento_1
alineamiento_2 = "-" + alineamiento_2
i = i-1
elif puntuacion == puntuacion_up + gap:
alineamiento_1 = "-" + alineamiento_1
alineamiento_2 = sec2[j-1] + alineamiento_2
j = j-1
while (i > 0):
alineamiento_1 = sec1[i-1] + alineamiento_1
alineamiento_2 = "-" + alineamiento_2
i = i-1
while ( j > 0):
alineamiento_1 = "-" + alineamiento_1
alineamiento_2 = sec2[j-1] + alineamiento_2
j = j-1
print alineamiento_1, alineamiento_2, score
Coloreado en 0.002 segundos, usando
GeSHi 1.0.8.4
Si pongo las secuencias a alinear tarda demasiado e incluso a veces no termina de ejecutarse.
Si alguien pudiera ayudarme, muchas gracias.