Algoritmo Needleman Wunsch en Python
Publicado: 2017-01-03 12:40 @569
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:
La salida del alineamiento debería ser:
La primera parte del código es la de inicialización
Y la segunda parte es la de [i]traceback[/i], que me devuelva el alineamiento:
Si pongo las secuencias a alinear tarda demasiado e incluso a veces no termina de ejecutarse.
Si alguien pudiera ayudarme, muchas gracias.
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
La salida del alineamiento debería ser:
Using text Syntax Highlighting
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.