SEDE BOGOTA DNSAV

cap. 2 alineamiento

FASTA

FASTA fue el primer algoritmo ampliamente utilizado para busqueda de similitud en una base de datos. FASTA busca alineamientos locales óptimos buscando coincidencias de peqeñas subsecuencias denominadas palabras ("words o k-tuplas"), el score del primer segmento en el que se aparean varias palabras se denomina "init1" y la suma de todos los score de los segmentos se denomina "initn". La sensibilidad y velocidad del algoritmo es inversamente proporcional a la longitud de la palabra utilizada en la busqueda.

Desarrollado por David Lipman y William Pearson en el año de 1985. es empleado principalmente por el EMBL - EBI (European Molecular Biology Laboratories - European Bioinformatics Institute), si se compara su velocidad con BLAST se notará que es mucho más lento, incluso llegá hasta a emplear varias horas para obtener los resultados, es por está razón que el EMBL envía los cálculos al usuario por correo electróncio.

FASTA compara una secuencia de DNA o de proteínas contra todas las secuencias de una base de datos y devuelve los mejores segmentos alineados.

Básicamente FASTA emplea cuatro pasos para obtener los tres scores que caracterizan la similitud entre secuencias:

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 la posició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 una matriz 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.
Por ejemplo la matriz "lookup" para alinear las siguientes secuencias es:

Secuencia	1	2	3	4	5	6	7	8	9
1	N	D	P	R	Q	S	.	.	.
2	.	.	.	.	A	S	D	P	R

Secuencia 1: NDPRQS
Secuencia 2: ¬¬¬¬ASDPR

Aminoácido	Posición en 1	Posición en 2	Corrimiento
A	-	5
D	2	7	-5
N	1	-
P	3	8	-5
Q	5	-
R	4	9	-5
S	6	6	0

Los aminoácidos DPR tienen el mismo corrimiento, entonces un posible alineamiento es:

Secuencia	1	2	3	4	5	6	7
1		N	D	P	R	Q	S
2	A	S	D	P	R

La longitud de la palabra (k-tupla) puede variar de 1 a 6 nucleótidos en secuencias de nucleó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.

Las diez 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 nucleicos) y se eliminan los "terminales" de cada secuencia para dejar unicamente 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 busquedas en las bases de datos.
Si el score de las regiones iniciales es alto (mayor al valor CUTOFF, este valor es apróximadamente una desviación estandard sobre el score promedio esperado de secunecias no relacionadas en la base de datos, pro ejemplo para una busqueda 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 producen un alineamiento aproximado, y se calcula el score de este nuevo segmento alineado. Este score se obtiene de la suma de los scores de la regiones unidas menos un peso por cada hueco (usualmente 20).
El score de este alineamiento es denominado initn y se utiliza para una nueva busqueda en las bases de datos [4].
Obtener el alineamiento local óptimo empleando el algoritmo de Needleman-Wunsch-Seller.

FORMATO FASTA:

Una secuencia en formato FASTA inicia con una sola línea conteniendo la información de la secuencia y a continuación de esta línea sigue la secuencia.

La línea informativa inicia con el símbolo > como se muestra a continuación y se recomienda que las líneas no excedan los 80 caracteres de longitud:

>gi|2230874|emb|X99726.1|HSNDUFV31 H.sapiens NDUFV3 gene, exon 1
GAAGCTGCTGTGGCCCTGCTTGGTGCGCCCGCTGTCACCGCCATGGCTGCCCCGTGTTTGCTGAGGAAAG
GACGAGCCGGGGCGCTGAAGGTAAAGGAGGAGCCAGCTGGGCTGGGTGCG

Sí la secuencia es de nucleótidos el formato permite los siguientes símbolos:

Símbolo	Significado
A	Adenina
C	Citosina
G	Guanina
T	Timina
U	Uracilo
R	Purina
Y	Pirimidina
K	G o T
N	A, C, G o T
-	Hueco

Sí la secuencia es de aminoácidos el formato permite los siguientes símbolos:

Símbolo	Significado	Símbolo	Significado
A	Alanina	P	Prolina
B	Asparagina	Q	Glutamina
C	Cisteina	R	Arginina
D	Ácido Aspártico	S	Serina
E	Ácido Glutámico	T	Treonina
F	Fenilalanina	U	Selenocysteina
G	Glicina	V	Valina
H	Histidina	W	Triptófano
I	Isoleucina	Y	Tirosina
K	Lisina	Z	Ácido Glutámico
L	Leucina	M	Metionina
N	Asparagina	*	Fin de la traducción
-	gap de longitud indeterminada

Referencias:

Pearson, W. R. Comparison of methods for searching protein sequence databases. Prot. Sci. 4:1145-1160.
W.J. Wilbur and D.J. Lipman. Rapid Similarity Searches of Nucleic Acid and Protein Data Banks. Natl. Acad. Sci. USA, 80:726-730, 1983.
Pearson W.R Rapid and Sentive Sequence Comparison with PASTP and FASTA. Methods Enzymol 183: 63-98.
http://bimas.dcrt.nih.gov.