Algoritmo FASTA Explicación

Question

Estoy tratando de comprender los pasos básicos del algoritmo FASTA al buscar secuencias similares de una secuencia de consulta en una base de datos. Estos son los pasos del algoritmo:

1. Identificar k-palabras comunes entre I y J
2. diagonales partido en el k-palabra coincide, identificar 10 mejores diagonales
3. regiones iniciales Rescore con una matriz de puntuación de sustitución
4. Únete regiones iniciales usando lagunas, penalizar por lagunas
5. Realizar la programación dinámica para encontrar alineaciones finales

Estoy confundido con el 3er y 4to paso en el uso de la matriz de puntaje PAM250, y cómo "unirme usando huecos".

¿Alguien me puede explicar estos dos pasos "lo más específicamente posible". Gracias

Answer 1

Así es como funciona FASTA:

1. Encuentra todas las identidades k de longitud, y luego encontrar regiones localmente similares al seleccionar los densa con identidades k-palabra (es decir, muchos k-palabras, sin demasiado muchas diferencias entre). Se utilizan las diez mejores regiones iniciales .
2. Las regiones iniciales se vuelven a marcar a lo largo de sus longitudes aplicando una matriz de sustitución de la forma habitual. Se identifican subregiones con puntajes óptimos.
3. Cree una alineación de las regiones iniciales recortadas utilizando la programación dinámica, con una penalización de hueco de 20. Las regiones con un puntaje demasiado bajo no están incluidas.
4. Optimice la alineación desde 3) utilizando la programación dinámica "en bandas" (Smith-Waterman). Esta es una programación dinámica restringida a la banda de 32 residuos de ancho alrededor de la alineación original, lo que ahorra espacio y tiempo sobre la programación dinámica completa.

Si hay regiones iniciales insuficientes para formar una alineación en 3), la mejor puntuación de 2) se puede utilizar para clasificar las secuencias por similitud. Los puntajes de 3) y 4) también se pueden usar para ese propósito.

Desafortunadamente, mi institución no tiene acceso al documento FASTA original, por lo que no puedo suministrar los valores originales de los diversos parámetros mencionados anteriormente.

Answer 2

La explicación es esencialmente correcta, pero la optimización de la banda final se centra en el mejor alineamiento sin huecos encontrado en el paso 2. Paso 3 se usa simplemente para mejorar la sensibilidad en la elección de secuencias que consiguen el paso 4.

El documento original se puede ver aquí: http://faculty.virginia.edu/wrpearson/papers/pearson_lipman_pnas88.pdf