Seminario

Universidad Nacional de San Antonio Abad del Cusco
Carrera Profesional de Ingenieria Informatica y de Sistemas

ALGORITMO FASTA PARA COMPARACION DE SECUENCIAS
(Pearson y Lipman, 1988)

Propuesta de Trabajo de Investigacion de

 JUAN AMILCAR TTITO TTITO 042278
 IVANIA PERZ PORTUGAL 043041

11 ¬¬¬¬¬¬de agosto

Profesor Guia:
ING , JULIO C. CARBAJAL

1. RESUMEN
El algoritmoFASTA 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 cuatroetapas para calcular tres puntajes que caracterizan la similitud de las secuencias. El siguiente es un resumen de estas cuatro etapas (falta resumir mas)
1.1 Etapa 1
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 descrita por Lipman y Pearson.
FASTA logra mucha de su velocidad y selectividad en esta etapausando 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.
Se identifican las diez regiones mejores apareadas de longitud k (una palabra) en cada par de secuencias por medio de una matriz "lookup".
La matriz "lookup" registra la ubicación de las palabras en las secuencias y laposición relativa de las palabras en las dos secuencias, esta posición se obtiene sustrayendo la ubicación de la palabra en la primera secuencia de la ubicación que tiene la misma palabra en la segunda secuencia.
Las palabras que presentan el mismo corrimiento (posición relativa) descubren una región de alineamiento entre las dos secuencias. La ventaja de este método frente a otras técnicas como unamatriz dot o métodos de programación dinámica se tiene en la complejidad computacional, ya que la complejidad de una matriz "lookup" se incrementa linealmente con el promedio de la longitud de las secuencias analizadas y la complejidad de una matriz dot depende el cuadrado del promedio de las secuencias.
La longitud de la palabra (k-tupla) puede variar de 1 a 6 nucleótidos en secuencias denucleótidos, aunque se recomienda una longitud de 4 o 6 nucleótidos, en la comparación de secuencias de aminoácidos generalmente se utiliza una palabra de longitud 2.
1.2 Etapa 2
Las regiones que se han seleccionado en el paso 1 son re-alineadas utilizando una matriz de sustitución (PAM250 para proteínas o matrices de sustitución que penalicen transiciones y transversiones para ácidos nucleídos) y seeliminan los "terminales" de cada secuencia para dejar únicamente las posiciones que contribuyen con el score, cada región de estas es un alineamiento parcial sin la presencia de gaps.
Estos scores son denominados init1 y se utilizan para las primeras búsquedas en las bases de datos.
1.3 Etapa 3
Si el score de las regiones iníciales es alto (mayor al valor CUTOFF, este valor es aproximadamenteuna desviación estandard sobre el score promedio esperado de secuencias no relacionadas en la base de datos, pro ejemplo para una búsqueda con una secuencia de 200 nucleótidos o aminoácidos y una palabra de longitud 2 el valor CUTOFF es 28).
FASTA verifica si la unión por medio de huecos de las regiones arregladas produce un alineamiento aproximado, y se calcula el score de este nuevo segmentoalineado. Este score se obtiene de la suma de los scores de las regiones unidas menos un peso por cada hueco (usualmente 20).
El score de este alineamiento es denominado initn y se utiliza para una nueva búsqueda en las bases de datos

1.4 Etapa 4
Obtener el alineamiento local óptimo empleando el algoritmo de Needleman-Wunsch-Seller.
2. INVESTIGACION PROPUESTA
2.1 ENUNCIADO DE TESIS
FASTA...