algoritmos heurísticos: fasta y blast. la pd no es adecuada para buscar en bd

Algoritmos heurísticos: FASTA y BLAST


La PD no es adecuada para buscar en BD


Heurística


Un poco de historia


PNAS (1988) 85, 2444-2448

El artículo original


¿Bueno bonito y barato? No existe


Las ventajas de FASTA

Mayor sensibilidad = menos FN

Mayor selectividad = menos FP

Mayor velocidad de computación

Menor consumo de memoria

selectividad = especificidad


El algoritmo FASTA


Etapa nº 1: Identidad


Etapa nº 1: Localizar k-tuplos idénticos (top ten)

Se agrupan las diagonales que estén a una cierta

distancia una de otra y, para cada secuencia de la

BD se localizan las 10 regiones con más densidad

de k-tuplos idénticos.

A partir de una secuencia problema se obtienen todos

los k-tuplos posibles mediante el método de la

ventana deslizante. Se comparan con los de las secuencias de la BD. Las

regiones idénticas aparecen como una diagonal.

IDENTIDAD

Secuencia problema

Se

cue

nci

a d

e la

BD

2 for proteins = 400 k-tuples

6 for DNA = 4096 k-tuples


Etapa nº 2: Similitud (limitada al top ten)


Se puntúan los top ten (init1)

SIMILITUD

Las 10 regiones con mayor densidad de k-tuplos idénticos

seleccionadas en la etapa anterior se vuelven a puntuar, esta vez utilizando una matriz

de sustitución. Esta puntuación es la variable init1.

Se identifican las subregiones que obtienen una mayor

puntuación (las denominadas regiones iniciales).

La región inicial con mayor valor init1 aparece marcada

con un asterisco.


Etapa nº 3: Unión de regiones iniciales (con huecos)


FASTA intenta unir las regiones iniciales cuya puntuación supera un

determinado cutoff.

Se vuelven a puntuar las regiones unidas

penalizando los huecos creados. Esta puntuación

se denomina initn y permite hacer un ranking con las

secuencias de la BD.

Las secuencias que superen cierto umbral de

puntuación initn pasan a la cuarta etapa

Puntuación initn y ranking de secuencias


Etapa nº 4: Programación dinámica “bandeada”


Etapa nº 4: Alineamiento óptimo “bandeado” (opt)

Se utiliza un algoritmo de PD modificado (SW

bandeado) para alinear la secuencia problema con la

secuencia de la BD. El alineamiento se limita a una estrecha banda centrada en

el segmento init1 y que engloba a las diagonales de

mayor puntuación.

La puntuación de este alineamiento es el

parámetro opt, con el que se hace un ranking de

alineamientos. También se determina su significación

estadística (E-value).


PD bandeada

Etapa nº 1

SIMILITUD

IDENTIDAD

Etapa nº 2

Los 10 mejores

init1

UNIÓN (gaps)Etapa nº 3 initn

Etapa nº 4 opt + E-value

ResultadoOperación

Las cuatro etapas de FASTA


http://www.ebi.ac.uk/Tools/sss/fasta/


Variantes del programa FASTA


http://fasta.bioch.virginia.edu/fasta_www2/fasta_list2.shtml


J. Mol. Biol. (1990), 403-410

BLAST1


Aplicaciones de BLAST


1.- Procesamiento previo de la secuencia problema


Se descompone la secuencia problema en “palabras”

Mediante el método de la “ventana deslizante” se descompone la secuencia problema en

“palabras”. El parámetro W (word size) determina el número de caracteres de las palabras.

Habitualmente, para proteínas W = 3 y para ADN W = 11

Al aumentar W se gana velocidad a costa de perder

sensibilidad


A cada palabra se le asocian “vecinas” (neighbors)

Se puntúa cada palabra aplicando una matriz de sustitución. Sólo se tendrán en cuenta las

palabras cuya puntuación supere un valor T.

Al aumentar T se gana velocidad a costa de perder

sensibilidad


Con cada palabra se elabora una lista de “palabras parecidas”

Resultado de la primera etapa de BLAST


2.- Se buscan coincidencias en las secuencias de la BD


Coincidencias (word hits) entre dos secuencias


Un valor de T elevado disminuye la sensibilidad (se reduce le número de “hits” y

se puede perder algún alineamiento significativo) pero aumenta la velocidad.

Un valor de W pequeño aumenta la sensibilidad pero

disminuye la velocidad.

Efecto de los parámetros W (word size) y T (threshold)

Una selección adecuada de W, T y la matriz de

puntuación permite controlar de manera eficaz la

sensibilidad y la rapidez del algoritmo

Algoritmos heurísticos: FASTA y BLASTBLAST1 intenta extender el alineamiento a ambos lados de cada coincidencia (sin dejar huecos), utilizando una variante del algoritmo de Smith-Waterman.

Etapa nº 3: extensión de las “coincidencias” (hits)


¿Cuándo se detiene la extensión? → el parámetro X

Caída (X) = 5 (se para y retrocede hasta el valor máximo)

Caída (X) = 2 (sigue)

Máximo = 9


Selección de los HSP (high scoring pairs)


Etapa nº 4: ranking de HSP (en función del valor E)

SKmneE


El valor E


Nucleic Acids Res. 25:3389-3402 (1997)

BLAST2


Etapa nº 3: algoritmo de la “doble coincidencia”

BLAST-2 utiliza el algoritmo de la doble coincidencia (two-hit algorithm): una

palabra sólo se extiende (sin huecos) si existe otra en la

misma diagonal a una distancia menor que A. El valor del parámetro A lo

establece el usuario.

Esta extensión genera una serie de

alineamientos con una puntuación

elevada (HSP, high scoring pairs)


Este requisito reduce la sensibilidad del

método (se extienden menos palabras). Esta

circunstancia se puede compensar disminuyendo el parámetro T (el

umbral de puntuación que se utiliza en la primera

etapa para generar la lista de “palabras

parecidas”).

Se reduce T para compensar la menor sensibilidad

+ (T = 13)

• (T = 11)


Se hace una extensión con huecos en los mejores HSP


Subsecuencia del HSP de 11 caracteres con la

máxima puntuación

Residuo central de Alanina donde comienza, en ambas direcciones, el

alineamiento local con huecos

¿Dónde empieza el alineamiento con huecos?


¿Dónde acaba el alineamiento con huecos?

El alineamiento local con huecos se lleva a cabo en ambas direcciones siempre y cuando la máxima puntuación alcanzada no se reduzca en un valor superior a Xg.


Los alineamientos se muestran en función del valor E (ordenados de menor a mayor). El valor E indica el número de veces que uno esperaría encontrar por puro azar un alineamiento con una puntuación igual o mayor en una BD de

igual tamaño y composición.

Los resultados se ordenan en función del valor E


NCBI-BLAST

http://blast.ncbi.nlm.nih.gov/Blast.cgi


http://www.ebi.ac.uk/Tools/sss/wublast/

WU-BLAST

algoritmos heurísticos: fasta y blast. la pd no es adecuada para buscar en bd

Documents