Rastreo en el algoritmo Smith-Wateman con penalización por brecha afín

Estoy intentando implementar el algoritmo de Smith-Waterman para la alineación de la secuencia local utilizando la función de penalización de espacio afín. Creo que entiendo cómo iniciar y calcular las matrices requeridas para calcular las puntuaciones de alineación, pero no tengo ni idea de cómo rastrear para encontrar la alineación. Para generar las 3 matrices requeridas tengo el siguiente código.

for j in range(1, len2): for i in range(1, len1): fxOpen = F[i][j-1] + gap xExtend = Ix[i][j-1] + extend Ix[i][j] = max(fxOpen, xExtend) fyOpen = F[i-1][j] + gap yExtend = Iy[i-1][j] + extend Iy[i][j] = max(fyOpen, yExtend) matchScore = (F[i-1][j-1] + simMatrixDict[seq1[i-1]+seq2[j-1]]) xScore = Ix[i-1][j-1] + simMatrixDict[seq1[i-1]+seq2[j-1]] yScore = Iy[i-1][j-1] + simMatrixDict[seq1[i-1]+seq2[j-1]] F[i][j] = max(0, matchScore, xScore, yScore) 

No estoy seguro si necesito una matriz única para el rastreo, o solo 1? Cualquier aclaración sobre cómo hacer un seguimiento desde la puntuación máxima en F sería muy apreciada.

Related of "Rastreo en el algoritmo Smith-Wateman con penalización por brecha afín"

Lo importante a recordar sobre el rastreo en Smith-Waterman es que la matriz en la que se encuentra un valor determina la dirección en la que se mueve. Entonces, si estás en F te estás moviendo en diagonal, si estás en Ix , te estás moviendo horizontalmente, y si estás en Iy , te estás moviendo verticalmente. Esto significa que todo lo que necesita almacenar en la matriz de punteros es la matriz de la que llegó a un cuadrado. La matriz de la que viene, no la que va a determinar, determina la dirección a la que debe ir.

Por ejemplo:

Digamos que estás en F[5][5] :

  • Si la matriz de punteros dice que ir a Ix , vaya a Ix[4][4]
  • Si la matriz de punteros dice que ir a Iy , vaya a Iy[4][4]
  • Si la matriz de punteros dice que ir a F , vaya a F[4][4]

Mientras que si estás en Ix[5][5] :

  • Si la matriz de punteros dice que ir a Ix , vaya a Ix[4][5]
  • Si la matriz de punteros dice que ir a F , vaya a F[4][5]

O si estás en Iy[5][5] :

  • Si la matriz de punteros dice que ir a Iy , vaya a Iy[5][4]
  • Si la matriz del puntero dice que ir a F , vaya a F[5][4]

Suponiendo que el primer índice es la coordenada xy el segundo es la coordenada y.

Continúe rastreando hasta que llegue a una celda con un valor máximo de 0.

Creación de la matriz de punteros: necesita una matriz de punteros para F , Ix e Iy . Estas matrices solo necesitan indicar de qué matriz proviene un valor, porque eso le indica en qué dirección se estaba moviendo. Por lo tanto, a medida que avanza en la fase de progtwigción dinámica del algoritmo, también debería estar creando las matrices de punteros. Cada vez que almacene un nuevo valor máximo en una celda en F , Ix o Iy , debe actualizar la matriz correspondiente para indicar de dónde proviene. Si, por ejemplo, el valor más alto que puede tener en F[5][5] se obtiene al alinear las dos bases siguientes cuando está en F[4][4] , el Fpointer [5] [5] debe configurarse a F , porque llegaste de la matriz F