# FASTA

FASTA es un paquete de software para el alineamiento de secuencias de ADN y proteínas inicialmente descrito como FASTP por David J. Lipman y William R. Pearson en 1985. Su legado es el Formato FASTA el cual es ahora muy popular en Bioinformática.

## Historia

El programa original FASTP fue diseñado para búsquedas de similitud en proteínas. Debido al crecimiento exponencial de la información genética, y a la velocidad y memoria limitada de los años 80, métodos heurísticos fueron introducidos para el alineamiento de secuencias y bases de datos completas. FASTA (desarrollado en 1988) añadió la habilidad de hacer búsquedas ADN:ADN, proteína traducida:busquédas de ADN, y también proveyó un programa para evaluar significancia estadística. Hay algunos programas en este paquete que permite el alineamiento de secuencias de proteínas y secuencias de ADN. Hoy en día la continua mejora en el rendimiento de las computadoras ha hecho posible búsquedas para alineamiento de secuencias local en bases de datos mediante el uso del Algoritmo Smith-Waterman.

## Usos

FASTA es pronunciado "fast A", que significa "FAST-All", porque trabaja con cualquier alfabeto, una extensiones son "FAST-P" (proteínas) y "FAST-N" (nucleótidos) para alineamiento.
El actual paquete FASTA contiene programas para proteína:proteína, ADN:ADN, proteína:ADN traducido, y búsquedas ordenadas o no ordenadas de péptidos. Versiones recientes del paquete FASTA incluye algoritmos de búsquedas especialmente traducidos que manejan correctamente los errores frameshift cuando se compara la data de secuencias de nucleótido a proteína.
Adicionalmente a rápidos métodos de búsqueda heurísticos, el paquete FASTA provee SSEARCH, una implementación óptima del Algoritmo Smith-Waterman.
Un mayor enfoque del paquete está en el cálculo de similitud estadística pecisa, de manera que los biólogos puedan juzgar si un alineamiento tiene probabilidad de haber ocurrido por casualidad, o puede ser usado para inferir homología. El paquete FASTA está disponible en fasta.bioch.virginia.edu.
La interfaz web para enviar secuencias para búsquedas en las bases de datos en línea del Instituto Europeo de Bioinformática está también disponible usando programas FASTA.
El formato fasta, usado como entrada para este programa, es ahora usado por otras herramientas de búsqueda de bases de datos de secuencias (tales como BLAST) y programas de alineamiento de secuencias (Clustal, T-Coffee, etc.).

## Método de búsqueda

FASTA toma un determinado nucleótido o aminoácido y busca una correspondiente base de datos de secuencias usando alineamiento de secuencias locales para encontrar coincidencias en secuencias similares.
El programa FASTA sigue un método heurístico el cual contribuye a la alta velocidad de su ejecución. Este inicialmente observa el patrón de aciertos, coincidencias de palabra a palabra dada una longitud, y marca coincidencias potenciales antes de ejecutar una búsqueda optimizada más demandante de tiempo usando un tipo de algoritmo Smith-Waterman.
El tamaño tomado para una palabra, dado por el parámetro kmer, controla la sensibilidad y velocidad del programa. Incrementar el valor kmer decrementa el número de aciertos de background que son encontrados. De los aciertos que son retornados, el programa busca segmentos que contengan un clúster cerca de los aciertos. Este luego investiga dichos segmentos por una posible coincidencia.
Hay algunas diferencias entre fastn y fastp con relación al tipo de secuencias usadas, pero ambos usan cuatro pasos y calculan tres resultados para describir y formatear los resultados de similitud de secuencias. Estos son:
* Identificar regiones de la más alta densidad en cada comparación de secuencias. Tomando un kmer igual a 1 o 2.
    En este paso todos o un grupo de identidades entre dos secuencias son encontradas usando una tabla de búsqueda. El valor kmer determina cuantas identidades consecutivas son requeridas para que se declare una coincidencia. Consecuentemente al menor valor de kmer más sensitiva es la búsqueda. kmer=2 es frecuentemente tomado por los usuarios para secuencias de proteínas y kmer=4 o 6 para secuencias de nucleótidos. Oligonucleótidos cortos son usualmente ejecutados con kmer=1. El programa luego encuentra todas las regiones locales similares, representadas como diagonales de determinada longitud en un gráfico de puntos, entre las dos secuencias mediante el conteo de coincidencias kmer y penalizando las no coincidencias intervinientes. De este modo, las regiones locales de la más alta densidad de coincidencia en una diagonal son aisladas de los aciertos de background. Para secuencias de proteínas los valores BLOSUM50 son usados para calificar las coincidencias kmer. Esto asegura que grupos de identidades con alta similitud contribuyan más a la diagonal local que a las identidades con baja similitud. Secuencias de nucleótidos usan la matriz identidad para el mismo propósito. Las mejores 10 regiones locales seleccionadas de entre todas las diagonales son guardadas.
* Re-escanea las regiones tomadas usando matrices de puntuación. Cortando los finales de la región para incluir solo los que contribuyen a la puntuación más alta.
    Re-escanea las 10 regiones tomadas. Esta ocasión usa la matriz de puntuación relevante mientras la re-puntuación permite ejecución de identidades más cortas que el valor de k-mero. También son tomados los reemplazos conservadores que contribuyen a la puntuación de similitud. Aunque las secuencias de proteínas usan la matriz BLOSUM50, las matrices de puntuación basadas en el número mínimo de cambios de base requeridas para un reemplazo específico, solamente en identidades, o en una medida alternativa de similitud tal como PAM, puede ser también usada con el programa. Por cada región de la diagonal re-escaneada de esta forma, una subregión con el máximo puntaje es identificada. Las puntuaciones iniciales encontradas en el paso 1 son usadas para ranquear la librería de secuencias. La puntuación más alta es referida como init1.
* En un alineamiento si algunas regiones iniciales con puntajes mayores que el valor CUTOFF son encontradas, revisa si las cortadas regiones iniciales pueden ser unidas para formar un alineamiento apropiado con intervalos. Calcula una puntuación de similitud la cual es la suma de las regiones unidas, con una penalidad de 20 puntos por cada intervalo. Esta puntuación de similitud inicial (initn) es usada para ranquear la librería de secuencias. La puntuación de la única mejor región inicial encontrada en el paso 2 es reportada como "init1".
    Aquí el programa calcula un alineamiento óptimo de regiones iniciales como una 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. El puntaje resultante initn es usado para ranquear la librería de secuencias. Este proceso de unión incrementa la sensibilidad pero decrementa la selectividad. Un valor de cut-off calculado cuidadosamente es consecuentemente usado para controlar donde este paso es implementado, un valor que es aproximadamente una desviación estándar por encima del puntaje promedio esperado de las secuencias no relacionadas en la librería. Un residuo 200 de una secuencia con kmer 2 usa un valor 28.
* Usa un algoritmo Smith-Waterman para calcular un óptimo puntaje para el alineamiento.
    Este paso usa el algoritmo Smith-Waterman para crear un puntaje optimizado "opt" para cada alineamiento de la secuencia pedida a una base de datos (librería) de secuencias. Toma una banda de 32 residuos centrados en la región "init1" del paso 2 para calcular el alineamiento óptimo. Después que todas las secuencias son buscadas el programa grafica los puntajes iniciales de cada secuencia en la base de datos mediante un Histograma, y calcula la significancia estadística del puntaje "opt". Para secuencias de proteínas, el alineamiento final es producido usando un completo alineamiento Smith-Waterman. Para secuencias de ADN, un alineamiento de bandas es provisto a banded.
FASTA no puede remover regiones de baja complejidad antes de alinear las secuencias, como sí es posible con BLAST. Esto podría ser problemático como cuando la secuencia de consulta contiene tales regiones, por ejemplo mini o micro-satélites que repiten la misma corta secuencia frecuentes veces, esto incrementa el puntaje de secuencias no familiares en la base de datos en la cual coincide en esta repetición, lo cual ocurre frecuentemente. Consecuentemente el programa PRSS es añadido en el paquete de distribución FASTA. PRSS revuelve las secuencias coincidentes en la base de datos ya sea del nivel de una letra o segmentos cortos cuya longitud el usuario pueda determinar. Las secuencias revueltas están ahora alineadas otra vez y si el puntaje es aún más alto de lo esperado, es causado por las regiones de baja complejidad siendo mezcladas y mapeadas a la consulta. Por la cantidad del puntaje de las secuencias revueltas aún conseguidas. PRSS ahora puede predecir la significancia del puntaje de las secuencias originales. Mientras sea más alto el puntaje de las secuencias revueltas menos significantes son las coincidencias encontradas entre la base de datos original y la secuencia de consulta.
Los programas FASTA encuentra regiones de similitud local o global entre secuencias de proteínas y ADN, ya sea mediante una búsqueda en bases de datos de proteínas o ADN, o identificando duplicados locales dentro de una secuencia. Otros programas proveen información en la significancia estadística de un alineamiento. Como BLAST, FASTA puede ser usado para inferir relaciones funcionales y evolutivas entre secuencias así como ayudar a identificar miembros de familias de genes.
Proteína
* Proteína–proteína FASTA.
* Proteína–proteína Smith–Waterman (ssearch).
* Proteína–proteína Global (Needleman–Wunsch) (ggsearch)
* Proteína–proteína Global/local (glsearch)
* Proteína–proteína con péptidos no ordenados (fasts)
* Proteína–proteína con secuencias de péptidos mezcladas (fastf)
Nucleótidos
* Nucleótido–nucleótido (DNA/RNA fasta)
* Nucleótidos ordenados vs nucleótidos (fastm)
* Nucleótidos no ordenados vs nucleótidos (fasts)
Traducidos
* ADN traducido (con frameshifts, ej. ESTs) vs proteínas (fastx/fasty)
* Proteínas vs ADN traducido (con frameshifts) (tfastx/tfasty)
* Péptidos vs ADN traducido (tfasts)
Significancia estadística
* Proteína vs proteína aleatoria (prss)
* ADN vs ADN aleatorio (prss)
* ADN traducido vs proteína aleatoria (prfx)
Duplicaciones locales
* Alineamiento de proteínas local (lalign)
* Gráfico de alineamiento de proteínas "dot-plot" (plalign)
* Alineamientos de ADN local (lalign)
* Gráfico de alineamiento de ADN "dot-plot" (plalign)

## Cambios en versiones

Las versiones más recientes de Fasta son la 3.4, 3.5 y 3,6, a continuación se describen los cambios más significativos

### V3.4

* Se modificó nmgetlib.c para permitir búsquedas múltiples a partir de una entrada stándar, de modo que el comando "cat prot_test.lseg | fasta34 -q -S @ /seqlib/swissprot" produciría 11 búsquedas
* Modificaciones a mshowbest.c and drop.c para proveer más información acerca del alineamiento con la opción -m9
* Adición de la opción "-t t" para especificar que todas las secuencias de proteínas tienen terminaciones de codones implícitas "*". De modo que todas las secuencias de proteínas sean un residuo más largo, y las coincidencias de longitud completa se extiendan un residuo extra y se obtenga una puntuación más alta
* Soporte de perfiles PSI-BLAST PSSM
* Inclusión de un nuevo programa, "print_pssm", que lee un archivo de punto de control binario blastpgp y escribe los valores de frecuencia como texto
* Se amplió la compatibilidad con las bases de datos NCBI Blast formatdb. Los programas FASTA ahora pueden leer algunos archivos NCBI * .pal y * .nal, que se utilizan para especificar subconjuntos de bases de datos
* Nuevos programas de Windows disponibles con el compilador Intel C ++. Primeros programas con hilos para Windows; primera aceleración SSE2 de SSEARCH para Windows.

### V3.5

* Estadísticas precisas basadas en shuffle para búsquedas en bibliotecas pequeñas (o comparaciones por parejas)
* Inclusión de lalign35 (SIM) en FASTA3. Estadísticas precisas para alineaciones lalign35. Plalign ha sido reemplazado por lalign35 y lav2ps
* Dos nuevos programas de alineación global: ggsearch35 y glsearch35

### V3.6

* La información de la anotación del dominio puede ser utilizada para producir la partición del alineamiento, y particionar las puntuaciones del alineamiento (puntuaciones de sub-alineamiento). Las puntuaciones del sub-alineamiento pueden usarse para identificar regiones de alineación sobre extensión, donde un dominio homólogo se alinea, pero la alineación se extiende más allá de la región homóloga en un dominio adyacente no homólogo
* La opción de proporcionar codificaciones de alineamiento (-m 9c o -m 9C forCIGAR strings) fue ampliada para proporcionar información de coincidencia errónea en la codificación de alineamiento usando la -m 9d (codificación de alineación FASTA clásica) o -m 9D (cadena CIGAR) . Para las alineaciones de proteínas, que a menudo son <40% de identidad, la habilitación de la codificación de la falta de coincidencia produce cadenas CIGAR muy largas.
* Los scripts de sub-puntuación de alineamiento se extendieron para permitir dominios superpuestos. Esto requiere un formato de archivo de anotación modificado. El formato "clásico" colocaba el principio y el final de un dominio en diferentes líneas

## Proyectos relacionados

* Actualización 1:1 FASTA: Usando el poder de E-valores en FASTA para detectar potencial reactividad cruzada de alergenos: Se prueba que el enfoque "1:1 FASTA" es superior al típico "FASTA search" para la evaluación de reactividad cruzada entre una proteína introducida en un cultivo alimenticio genéticamente modificado y alergenos conocidos, además se plantea introducir el enfoque "1:1 FASTA" como suplemento del criterio FAO/WHO/CODEX
* Un acelerador de hardware para el alineamiento de múltiples secuencias de ADN]: Propone un acelerador de hardware para abordar el problema de alineamiento paralelo de múltiple secuencias de ADN, su rendimiento fue comparado con el del programa FASTA ejecutado sobre una plataforma GPP; los resultados señalan un rendimiento superior en el orden de las decenas