• Publicidad

Algoritmo Needleman Wunsch en Python

Todo lo relacionado con lenguajes de programación distintos de Perl: PHP, Java, C++, Ruby, Python, etc.

Algoritmo Needleman Wunsch en Python

Notapor perl junior » 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:
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.011 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.013 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.
perl junior
Perlero nuevo
Perlero nuevo
 
Mensajes: 10
Registrado: 2017-01-03 11:13 @509

Publicidad

Volver a Programación en general

¿Quién está conectado?

Usuarios navegando por este Foro: No hay usuarios registrados visitando el Foro y 0 invitados