Algoritmo FASTA

Por Germán González



El algoritmo FASTA es un método heurístico para comparación de cadenas. Fue desarrollado por Lipman y Pearson en 1985 y luego mejorado en 1988.

FASTA compara una cadena de consulta con una cadena de un solo texto. Cuando buscamos en una base de datos entera coincidencias para una consulta dada, comparamos la consulta usando el algoritmo FASTA para cada cadena en la base de datos.

Este algoritmo usa cuatro etapas para calcular tres puntajes que caracterizan la similitud de las secuencias. El siguiente es un resumen de estas cuatro etapas:

Etapa 1

Identificar regiones compartidas por las secuencias con la densidad más alta de identidades (ktup=1) o pares de identidades (ktup=2).

La primera etapa usa una técnica rápida para encontrar identidades compartidas entre dos secuencias; el método es similar a una técnica anterior descrita por Wilbur y Lipman.

FASTA logra mucha de su velocidad y selectividad en esta etapa usando una tabla de consulta para localizar todas las identidades o grupos de identidades entre dos secuencias de ADN o de aminoácidos durante la primera etapa de comparación.

El parámetro ktup determina cuantas identidades consecutivas son requeridas en una coincidencia. Un valor de ktup de 2 es usado frecuentemente para comparaciones de secuencias de proteínas, lo cual significa que el programa examina solo esas porciones de las dos secuencias que están siendo comparadas que tiene al menos dos residuos adyacentes idénticos en ambas secuencias. Pueden realizarse búsquedas más sensibles usando ktup = 1. Para comparaciones de secuencias de ADN, el parámetro ktup toma valores entre 1 y 6; son recomendados valores entre 4 y 6. Cuando la secuencia de consulta es unoligonucleótido u oligopéptido pequeño, debería usarse ktup = 1.

En conjunción con la tabla de consulta, usamos el método de la diagonal para hallar todas las regiones de similitud entre dos secuencias, contando las coincidencias de ktup y las penalizaciones por discordancias. Este método identifica regiones de la diagonal que tienen la densidad más alta de coincidencias ktup.

FASTA usa una fórmula para puntuar las coincidencias ktup que incorpora los valores PAM250 actuales para los residuos alineados. Así, grupos de identidades con puntajes de alta similitud contribuyen más al puntaje local de la diagonal que las identidades con puntaje de baja similitud.

Esta fórmula más sensitiva es usada para comparar secuencias de proteínas; el valor constante de coincidencias ktup es usado en comparaciones de secuencias de ADN.

FASTA guarda las 10 mejores regiones, sin tener en cuente si estas están en la misma o en diferentes diagonales.

Etapa 2

Re-escanea las 10 regiones con la densidad más alta de identidades usando una matriz PAM250. Recortando los finales de la región para incluir solo aquellos residuos que contribuyen al puntaje más elevado. Cada región es un alineamiento parcial sin interrupciones.

Después de que las 10 mejores regiones locales son halladas en la primera etapa, estas son re-puntuadas usando una matriz de puntaje que permite correr las identidades más cortas que los residuos ktup y realizar reemplazos conservativos para contribuir al puntaje de similitud. Para secuencias de proteínas, es puntaje es usualmente calculado utilizando una matriz PAM250.

La matriz de puntajes PAM250 fue derivada del análisis de los reemplazos de aminoácidos que ocurren entre proteínas relacionadas, y especifica un rango de puntajes positivos para reemplazos que comúnmente ocurren entre proteínas relacionadas y puntajes negativos para reemplazos improbables.

FASTA puede ser utilizado también para hacer comparaciones de secuencias de ADN, y las matrices pueden ser construidas para permitir penalidades separadas para transiciones y transversiones.

Para cada una de la mejores regiones re-escaneadas con la matriz de puntajes, una subregión con el puntaje máximo es identificada.

Los puntajes iniciales son usados para clasificar la biblioteca de secuencias. Estos puntajes son referidos como puntaje init1.

Etapa 3

Si hay varias regiones con un puntaje mayor que el valor CUTOFF, comprueba si las regiones iniciales recortadas pueden ser unidas para formar un alineamiento aproximado con interrupciones. Calcular el puntaje de similitud es la suma de las regiones iniciales unidas menos una penalidad (usualmente 20) para cada interrupción.

FASTA comprueba, durante una búsqueda en la biblioteca, si varias regiones iniciales pueden ser unidas juntas en una alineamiento único para aumentar el puntaje inicial.

FASTA calcula un alineamiento óptimo de regiones iniciales como la combinación de regiones compatibles con puntaje máximo. Este alineamiento óptimo de regiones iniciales puede ser rápidamente calculado usando un algoritmo de programación dinámica.

FASTA usa el puntaje resultante, conocido como puntaje inicial, para clasificar la biblioteca de secuencias.

La tercer etapa de “unión” en el cómputo del puntaje inicial incrementa la sensibilidad del método de búsqueda porque permite inserciones, eliminaciones asi como reemplazos conservativos. Sin embargo, esta modificación disminuye la selectividad. Esto es limitado incluyendo en la etapa de optimización solo estas regiones iniciales cuyos puntajes están por encima de un umbral determinado empíricamente: FASTA une una región inicial solo si su puntaje de similitud es más grande que el valor cutoff, que es aproximadamente una desviación estándar por encima del puntaje medio esperado para secuencias sin relación en la biblioteca. Para un secuencia de consulta de 200 resiudos y ktup-2, el valor es 28.

Etapa 4

Construye una alineamiento óptimo NWS (algoritmo Needleman-Wunsch-Sellers) de la secuencia de consulta y de la secuencia de la biblioteca, considerando solo aquellos residuos que están en una banda de 32 residuos centrados en la mejor región inicial encontrada en la etapa 2. FASTA informa de este puntaje como puntaje optimizado (opt).

Después de una búsqueda completa en la biblioteca, FASTA grafica los puntajes iniciales de cada secuencia de la biblioteca en un histograma, calcula el puntaje de similitud de la secuencia de consulta contra cada secuencia de la biblioteca, y determina la desviación estándar de la distribución de puntajes iniciales. Los puntajes iniciales son usados para clasificar las secuencias de la biblioteca, y en la cuarta etapa de la comparación, las secuencias de mayor puntaje de la biblioteca son alineadas usando una modificación del método estándar de optimización NWS. La optimización emplea la misma matriz de puntajes usada para determinar las regiones iniciales; los alineamientos optimizados resultantes son calculados para el análisis de relaciones potenciales, y es informado el puntaje de similitud optimizado.

Tabla de consulta

La tabla de consulta es un método rápido para encontrar la posición de un residuo en la secuencia. Una manera de encontrar la “A” en la secuencia “NDAPL” es comparar “A” con cada residuo de la secuencia. Una manera más rápida, es hacer una tabla de todos los posibles residuos(23 para proteínas), entonces la representación que realiza la computadora del residuo (por ejemplo “A” es 1, “R” es 2, “N” es 3) es la misma que su posición en la tabla.

Entonces, un valor es colocado en la tabla que indica si el residuo está presente en la secuencias, si es así, donde está presente. Para este ejemplo la tabla tiene el valor 1 en la posición 3, 2 en la posición 4, 3 en la posición 1, 4 en la 15, 5 en la 11, y las 18 posiciones restantes son 0.

La posición de “A” en la subsecuencias puede ser determinada en un solo paso observando la posición 1 en la tabla.

Comentarios