Página 1 de 1

Algoritmo Needleman Wunsch en Python

NotaPublicado: 2017-01-03 12:40 @569
por perl junior
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:
Sintáxis: [ Descargar ] [ Ocultar ]
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:
Sintáxis: [ Descargar ] [ Ocultar ]
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
Sintáxis: [ Descargar ] [ Ocultar ]
Using python Syntax Highlighting
  1.  
  2.     match = 1
  3.     mismatch = -1
  4.     gap = -2
  5.     longitud_1 = len(sec1) + 1
  6.     longitud_2 = len(sec2) + 1
  7.    
  8.     F = [[ 0 for _ in range(longitud_1)] for _ in range(longitud_2)]  #inicializacion de la matriz F con 0
  9.    
  10.     #MATRIZ DE SIMILARIDAD - INICIALIZACION
  11.    
  12.     #Casos base: primera fila y primera columna
  13.     for i in range(longitud_1):
  14.         F[i][0] = gap * i
  15.     for j in range(longitud_2):
  16.         F[0][j] = gap * j
  17.     #Resto de casos
  18.     for i in range(1,longitud_1):
  19.         for j in range(1,longitud_2):
  20.             b = sec1[i-1] == sec2[j-1]
  21.             if b:
  22.                 suma = match
  23.             else:
  24.                 suma = mismatch
  25.             F[i][j] = max(F[i-1][j-1] + suma, F[i][j-1] + gap, F[i-1][j] + gap)
  26.    
  27.     score = F[longitud_1-1][longitud_2-1]
Coloreado en 0.003 segundos, usando GeSHi 1.0.8.4

Y la segunda parte es la de [i]traceback[/i], que me devuelva el alineamiento:
Sintáxis: [ Descargar ] [ Ocultar ]
Using python Syntax Highlighting
  1.  #TRACEBACK-->BUSCAR EL MEJOR ALINEAMIENTO
  2.    
  3.     alineamiento_1 = " "
  4.     alineamiento_2 = " "
  5.    
  6.     while (i > 0 and j > 0):
  7.         puntuacion = F[j][i]
  8.         puntuacion_diag = F[j-1][i-1]
  9.        
  10.         puntuacion_up = F[j-1][i]
  11.         puntuacion_left = F[j][i-1]
  12.                    
  13.         if puntuacion == puntuacion_diag + suma:
  14.             alineamiento_1 = sec1[i-1] + alineamiento_1
  15.             alineamiento_2 = sec2[j-1] + alineamiento_2
  16.            
  17.             i = i-1
  18.             j = j-1
  19.            
  20.         elif puntuacion == puntuacion_left + gap:
  21.             alineamiento_1 = sec1[i-1] + alineamiento_1
  22.             alineamiento_2 = "-" + alineamiento_2
  23.            
  24.             i = i-1
  25.                            
  26.         elif puntuacion == puntuacion_up + gap:
  27.             alineamiento_1 = "-" + alineamiento_1
  28.             alineamiento_2 = sec2[j-1] + alineamiento_2
  29.            
  30.             j = j-1
  31.            
  32.     while (i > 0):
  33.        alineamiento_1 = sec1[i-1] + alineamiento_1
  34.        alineamiento_2 = "-" + alineamiento_2
  35.        
  36.        i = i-1
  37.    
  38.     while ( j > 0):
  39.         alineamiento_1 = "-" + alineamiento_1
  40.         alineamiento_2 = sec2[j-1] + alineamiento_2
  41.        
  42.         j = j-1
  43.    
  44.     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.