Algoritmo BLAST

Por Germán González

El algoritmo y el programa de computadora que lo implementa fueron desarrollados por: Stephen Altschul, Warren Gish, David Lipman en el Centro Nacional de Información Biotecnológica (NCBI, por sus siglas en inglés), Webb Millar en la Universidad estatal de Pennsylvania, y Gene Myers en la Universidad de Arizona. Existen implementaciones alternativas comoWU-BLASTFSA-BLAST.
El artículo original “Altschul, SF, W Gish, W Miller, EW Myers, and DJ Lipman. Basic local alignment search tool. J Mol Biol 215(3):403-10, 1990.” fue el más citado de los que se publicaron en los ’90.

Algoritmo
Para ejecutarse, BLAST requiere dos secuencias como entrada: una secuencia de consulta (también llamada secuencia blanco) y una base de datos de secuencias. BLAST encontrará subsecuencias en la consulta que son similares a subsecuencias de la base de datos. En el uso típico, la secuencia de consulta es mucho mas pequeña que el banco de datos, por ejemplo, la consulta puede ser de mil nucleótidos mientras que la base de datos es de varios miles de millones de nucleótidos.
BLAST busca alineamientos de secuencias de alto puntaje entre la secuencia de consulta y las secuencias en el banco de datos usando un enfoque heurístico que aproxima el algoritmo de Smith-Waterman. El exhaustivo enfoque de Smith-Watermanes demasiado lento para buscar en grandes bases de datos genómicas tales como GenBank. Por lo tanto, el algoritmo BLAST usa un enfoque heurístico que es un poco menos preciso que Smith-Waterman pero más de 50 veces más rápido. La velocidad y la relativamente buena precisión de BLAST son la clave de la innovación técnica de los programas BLAST y probablemente el porque es la herramienta de búsqueda mas popular en bioinformática.
El algoritmo BLAST puede ser dividido conceptualmente en tres etapas:

  • En la primera etapa, BLAST busca coincidencias exactas de una pequeña longitud fija W entre la secuencia de consulta y las secuencias de la base de datos. Por ejemplo, dadas las secuencias AGTTAC y ACTTAG y el largo de palabra W = 3, BLAST podría identificar la subcadena coincidente TTA que es común en ambas secuencias. Por defecto, W = 11 para “semillas” nucleicas.
  • En la segunda etapa, BLAST trata de extender la coincidencia en ambas direcciones, comenzando por la semilla. El proceso de alineamiento sin huecos, extiende la coincidencia de la semilla inicial de longitud W en cada dirección en un intento de estimular el puntaje de alineación. Inserciones y eliminaciones no son consideradas durante esta etapa. Para nuestro ejemplo, el alineamiento sin huecos entre las secuencias AGTTAC y ACTTAG centrado alrededor de la palabra en común TTA podría ser:

Si es encontrado un alineamiento sin huecos de alto puntaje, la base de datos de secuencias pasa a la tercera etapa.

  • En la tercera etapa, BLAST realiza un alineamiento con huecos entre la secuencia de consulta y la secuencia de la base de datos usando una variación del algoritmo de Smith-Waterman. Entonces los alineamientos relevantes estadísticamente son mostrados al usuario.

Una alternativa extremadamente rápida pero considerada menos sensible que BLAST para comparar secuencias de nucleótidos es BLAT (Blast Like Alignment Tool). Una versión diseñada para comparar múltiples genomas grandes o cromosomas es BLASTZ.
También existe otro software llamado PatternHunter que produce resultados significativamente más sensibles que los de BLAST a la misma velocidad o resultados muy similares a mucha mayor velocidad. La principal desventaja que tiene es que se trata de software pago al contrario de BLAST que es totalmente gratuito.

 

Comentarios