TTTTTTTT
secuencia_2
ATTTTTTTTA
Coloreado en 0.000 segundos, usando GeSHi 1.0.8.4
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:
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.003 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.
