En bioinformática , BLAST ( herramienta básica de búsqueda de alineación local ) [2] es un algoritmo y programa para comparar información de secuencia biológica primaria , como las secuencias de aminoácidos de proteínas o los nucleótidos de secuencias de ADN y / o ARN . Una búsqueda BLAST permite a un investigador comparar una proteína o secuencia de nucleótidos en cuestión (llamada consulta) con una biblioteca o base de datosde secuencias e identificar secuencias de bases de datos que se asemejan a la secuencia de consulta por encima de un cierto umbral. Por ejemplo, tras el descubrimiento de un gen previamente desconocido en el ratón , un científico normalmente realizará una búsqueda BLAST del genoma humano para ver si los seres humanos son portadores de un gen similar; BLAST identificará secuencias en el genoma humano que se asemejen al gen del ratón basándose en la similitud de secuencia.
Autor (es) original (es) | Stephen Altschul , Warren Gish , Webb Miller , Eugene Myers y David Lipman |
---|---|
Desarrollador (es) | NCBI |
Lanzamiento estable | 2.11.0+ / 3 de noviembre de 2020 |
Escrito en | C y C ++ [1] |
Sistema operativo | UNIX , Linux , Mac , MS-Windows |
Tipo | Herramienta de bioinformática |
Licencia | Dominio publico |
Sitio web | blast |
Fondo
BLAST, que The New York Times llamó el Google de la investigación biológica , [2] es uno de los programas bioinformáticos más utilizados para la búsqueda de secuencias. [3] Aborda un problema fundamental en la investigación bioinformática. El algoritmo heurístico que utiliza es mucho más rápido que otros enfoques, como calcular una alineación óptima. Este énfasis en la velocidad es vital para que el algoritmo sea práctico en las enormes bases de datos del genoma disponibles actualmente, aunque los algoritmos posteriores pueden ser incluso más rápidos.
Antes de BLAST, FASTA fue desarrollado por David J. Lipman y William R. Pearson en 1985. [4]
Antes de que se desarrollaran algoritmos rápidos como BLAST y FASTA , la búsqueda en bases de datos de secuencias de proteínas o nucleicas consumía mucho tiempo porque se utilizaba un procedimiento de alineación completo (por ejemplo, el algoritmo de Smith-Waterman ).
BLAST proviene del modelo estocástico de 1990 de Samuel Karlin y Stephen Altschul [5]. Propusieron "un método para estimar las similitudes entre la secuencia de ADN conocida de un organismo con la de otro", [2] y su trabajo ha sido descrito como "el base estadística para BLAST ". [6] Posteriormente, Altschul, junto con Warren Gish , Webb Miller , Eugene Myers y David J. Lipman en los Institutos Nacionales de Salud diseñaron el algoritmo BLAST, que fue publicado en el Journal of Molecular Biology en 1990 y citado más de 75,000 veces. . [7]
Si bien BLAST es más rápido que cualquier implementación de Smith-Waterman en la mayoría de los casos, no puede "garantizar las alineaciones óptimas de las secuencias de consulta y base de datos" como lo hace el algoritmo de Smith-Waterman. La optimización de Smith-Waterman "aseguró el mejor rendimiento en precisión y los resultados más precisos" a expensas del tiempo y la potencia de la computadora.
BLAST es más eficiente en el tiempo que FASTA al buscar solo los patrones más significativos en las secuencias, pero con sensibilidad comparativa. Esto podría realizarse aún más si se comprende el algoritmo de BLAST que se presenta a continuación.
Ejemplos de otras preguntas que los investigadores usan BLAST para responder son:
- ¿Qué especie bacteriana tiene una proteína que está relacionada en el linaje con una determinada proteína con una secuencia de aminoácidos conocida?
- ¿Qué otros genes codifican proteínas que exhiben estructuras o motivos , como los que se acaban de determinar?
BLAST también se usa a menudo como parte de otros algoritmos que requieren una coincidencia de secuencia aproximada.
BLAST está disponible en la web en el sitio web de NCBI. Hay diferentes tipos de BLAST disponibles de acuerdo con las secuencias de consulta y las bases de datos de destino. Las implementaciones alternativas incluyen AB-BLAST (anteriormente conocido como WU-BLAST), FSA-BLAST (actualizado por última vez en 2006) y ScalaBLAST. [8] [9]
El artículo original de Altschul, et al. [7] fue el artículo más citado publicado en la década de 1990. [10]
Aporte
Secuencias de entrada (en formato FASTA o Genbank ), base de datos a buscar y otros parámetros opcionales como matriz de puntuación.
Producción
La salida BLAST se puede entregar en una variedad de formatos. Estos formatos incluyen HTML , texto sin formato y formato XML . Para la página web de NCBI, el formato predeterminado para la salida es HTML. Al realizar un BLAST en NCBI, los resultados se dan en un formato gráfico que muestra los aciertos encontrados, una tabla que muestra los identificadores de secuencia para los aciertos con datos relacionados con la puntuación, así como alineaciones para la secuencia de interés y los aciertos recibidos con las puntuaciones BLAST correspondientes. para éstos. El más fácil de leer y el más informativo de estos es probablemente la tabla.
Si uno está intentando buscar una secuencia propietaria o simplemente una que no está disponible en bases de datos disponibles para el público en general a través de fuentes como NCBI, hay un programa BLAST disponible para descargar a cualquier computadora, sin costo. Esto se puede encontrar en ejecutables BLAST +. También hay programas comerciales disponibles para su compra. Las bases de datos se pueden encontrar en el sitio NCBI, así como en el índice de bases de datos BLAST (FTP).
Proceso
Usando un método heurístico , BLAST encuentra secuencias similares, localizando coincidencias cortas entre las dos secuencias. Este proceso de encontrar secuencias similares se llama siembra. Es después de este primer partido que BLAST comienza a hacer alineaciones locales. Al intentar encontrar similitudes en las secuencias, los conjuntos de letras comunes, conocidas como palabras, son muy importantes. Por ejemplo, suponga que la secuencia contiene el siguiente tramo de letras, GLKFA. Si se realizara un BLAST en condiciones normales, el tamaño de la palabra sería de 3 letras. En este caso, utilizando el tramo de letras dado, las palabras buscadas serían GLK, LKF, KFA. El algoritmo heurístico de BLAST ubica todas las palabras comunes de tres letras entre la secuencia de interés y la secuencia o secuencias de aciertos de la base de datos. Este resultado luego se utilizará para construir una alineación. Después de formar palabras para la secuencia de interés, el resto de palabras también se ensamblan. Estas palabras deben satisfacer el requisito de tener una puntuación de al menos el umbral T , cuando se comparan mediante una matriz de puntuación.
Una matriz de puntuación comúnmente utilizada para búsquedas BLAST es BLOSUM62 , [11] aunque la matriz de puntuación óptima depende de la similitud de secuencia. Una vez reunidas y compiladas tanto las palabras como las palabras vecinas, se comparan con las secuencias de la base de datos para encontrar coincidencias. La puntuación de umbral T determina si una palabra en particular se incluirá o no en la alineación. Una vez que se ha realizado la siembra, la alineación, que tiene solo 3 residuos de longitud, se extiende en ambas direcciones mediante el algoritmo utilizado por BLAST. Cada extensión afecta la puntuación de la alineación al aumentarla o disminuirla. Si esta puntuación es superior a una T predeterminada , la alineación se incluirá en los resultados proporcionados por BLAST. Sin embargo, si esta puntuación es menor que esta T predeterminada , la alineación dejará de extenderse, evitando que las áreas de alineación deficiente se incluyan en los resultados de BLAST. Tenga en cuenta que el aumento de la puntuación T limita la cantidad de espacio disponible para buscar, lo que reduce el número de palabras vecinas y, al mismo tiempo, acelera el proceso de BLAST.
Algoritmo
Para ejecutar el software, BLAST requiere una secuencia de consulta para buscar y una secuencia para buscar (también llamada secuencia objetivo) o una base de datos de secuencias que contenga múltiples secuencias de este tipo. BLAST encontrará subsecuencias en la base de datos que son similares a las subsecuencias en la consulta. En el uso típico, la secuencia de consulta es mucho más pequeña que la base de datos, por ejemplo, la consulta puede tener mil nucleótidos mientras que la base de datos tiene varios miles de millones de nucleótidos.
La idea principal de BLAST es que a menudo hay pares de segmentos de alta puntuación (HSP) contenidos en una alineación estadísticamente significativa. BLAST busca alineaciones de secuencia de alta puntuación entre la secuencia de consulta y las secuencias existentes en la base de datos utilizando un enfoque heurístico que se aproxima al algoritmo de Smith-Waterman . Sin embargo, el enfoque exhaustivo de Smith-Waterman es demasiado lento para buscar grandes bases de datos genómicas como GenBank . Por lo tanto, el algoritmo BLAST utiliza un enfoque heurístico que es menos preciso que el algoritmo Smith-Waterman pero 50 veces más rápido. [8] La velocidad y precisión relativamente buena de BLAST se encuentran entre las innovaciones técnicas clave de los programas BLAST.
Una descripción general del algoritmo BLAST (una búsqueda de proteína a proteína) es la siguiente: [12]
- Elimine la región de baja complejidad o las repeticiones de secuencia en la secuencia de consulta.
- "Región de baja complejidad" significa una región de una secuencia compuesta por pocos tipos de elementos. Estas regiones pueden dar puntuaciones altas que confunden al programa para encontrar las secuencias significativas reales en la base de datos, por lo que deben filtrarse. Las regiones se marcarán con una X (secuencias de proteínas) o N (secuencias de ácidos nucleicos) y luego serán ignoradas por el programa BLAST. Para filtrar las regiones de baja complejidad, el programa SEG se utiliza para las secuencias de proteínas y el programa DUST se utiliza para las secuencias de ADN. Por otro lado, el programa XNU se usa para enmascarar las repeticiones en tándem en secuencias de proteínas.
- Haga una lista de palabras con letras k de la secuencia de consulta.
- Tomemos k = 3, por ejemplo, enumeramos las palabras de longitud 3 en la secuencia de la proteína de consulta ( k suele ser 11 para una secuencia de ADN) "secuencialmente", hasta que se incluya la última letra de la secuencia de consulta. El método se ilustra en la figura 1.
- Tomemos k = 3, por ejemplo, enumeramos las palabras de longitud 3 en la secuencia de la proteína de consulta ( k suele ser 11 para una secuencia de ADN) "secuencialmente", hasta que se incluya la última letra de la secuencia de consulta. El método se ilustra en la figura 1.
- Enumere las posibles palabras coincidentes.
- Este paso es una de las principales diferencias entre BLAST y FASTA. FASTA se preocupa por todas las palabras comunes en la base de datos y las secuencias de consulta que se enumeran en el paso 2; sin embargo, BLAST solo se preocupa por las palabras de alta puntuación. Las puntuaciones se crean comparando la palabra de la lista en el paso 2 con todas las palabras de 3 letras. Al utilizar la matriz de puntuación (matriz de sustitución ) para puntuar la comparación de cada par de residuos, hay 20 ^ 3 posibles puntuaciones de coincidencia para una palabra de 3 letras. Por ejemplo, la puntuación obtenida al comparar PQG con PEG y PQA es respectivamente 15 y 12 con el esquema de ponderación BLOSUM62 . Para las palabras de ADN, una coincidencia se puntúa como +5 y una falta de coincidencia como -4, o como +2 y -3. Después de eso, se utiliza un umbral de puntuación de palabras vecinas T para reducir el número de posibles palabras coincidentes. Las palabras cuyas puntuaciones sean mayores que el umbral T permanecerán en la lista de posibles palabras coincidentes, mientras que aquellas con puntuaciones más bajas se descartarán. Por ejemplo, PEG se mantiene, pero PQA se abandona cuando T es 13.
- Organice las palabras restantes de alta puntuación en un árbol de búsqueda eficiente.
- Esto permite que el programa compare rápidamente las palabras de mayor puntuación con las secuencias de la base de datos.
- Repita los pasos 3 a 4 para cada palabra de letra k en la secuencia de consulta.
- Escanee las secuencias de la base de datos en busca de coincidencias exactas con las palabras restantes de alta puntuación.
- El programa BLAST escanea las secuencias de la base de datos en busca de la palabra restante de alta puntuación, como PEG, de cada posición. Si se encuentra una coincidencia exacta, esta coincidencia se utiliza para generar una posible alineación sin espacios entre la consulta y las secuencias de la base de datos.
- Amplíe las coincidencias exactas al par de segmentos de alta puntuación (HSP).
- La versión original de BLAST extiende una alineación más larga entre la consulta y la secuencia de la base de datos en las direcciones izquierda y derecha, desde la posición donde ocurrió la coincidencia exacta. La extensión no se detiene hasta que la puntuación total acumulada del HSP comienza a disminuir. En la figura 2 se presenta un ejemplo simplificado.
- Para ahorrar más tiempo, se ha desarrollado una versión más nueva de BLAST, llamada BLAST2 o BLAST con huecos. BLAST2 adopta un umbral de puntuación de palabras vecinas más bajo para mantener el mismo nivel de sensibilidad para detectar similitudes de secuencia. Por lo tanto, la lista de posibles palabras coincidentes en el paso 3 se hace más larga. A continuación, las regiones coincidentes exactas, dentro de la distancia A entre sí en la misma diagonal en la figura 3, se unirán como una nueva región más larga. Finalmente, las nuevas regiones se extienden mediante el mismo método que en la versión original de BLAST, y las puntuaciones de HSP (par de segmentos de alta puntuación) de las regiones extendidas se crean utilizando una matriz de sustitución como antes.
- La versión original de BLAST extiende una alineación más larga entre la consulta y la secuencia de la base de datos en las direcciones izquierda y derecha, desde la posición donde ocurrió la coincidencia exacta. La extensión no se detiene hasta que la puntuación total acumulada del HSP comienza a disminuir. En la figura 2 se presenta un ejemplo simplificado.
- Enumere todas las PAS de la base de datos cuya puntuación sea lo suficientemente alta como para ser considerada.
- Enumeramos las PAS cuyas puntuaciones son mayores que la puntuación de corte S determinada empíricamente . Al examinar la distribución de las puntuaciones de alineación modeladas mediante la comparación de secuencias aleatorias, se puede determinar una puntuación de corte S de modo que su valor sea lo suficientemente grande como para garantizar la importancia de las HSP restantes.
- Evalúe la importancia de la puntuación HSP.
- A continuación, BLAST evalúa la significación estadística de cada puntuación HSP explotando la distribución de valores extremos de Gumbel (EVD). (Se ha demostrado que la distribución de las puntuaciones de alineación local de Smith-Waterman entre dos secuencias aleatorias sigue el EVD de Gumbel. No se ha probado para las alineaciones locales que contienen huecos). De acuerdo con el EVD de Gumbel, la probabilidad p de observar una puntuación S igual o mayor que x viene dada por la ecuación
- dónde
- Los parámetros estadísticos y se estiman ajustando la distribución de las puntuaciones de alineación local sin espacios, de la secuencia de consulta y muchas versiones barajadas (barajado global o local) de una secuencia de base de datos, a la distribución de valores extremos de Gumbel. Tenga en cuenta que y dependen de la matriz de sustitución, las penalizaciones por espacios y la composición de la secuencia (las frecuencias de las letras). y son las longitudes efectivas de la consulta y las secuencias de la base de datos, respectivamente. La longitud de la secuencia original se acorta a la longitud efectiva para compensar el efecto de borde (es probable que un inicio de alineación cerca del final de una de las secuencias de consulta o base de datos no tenga suficiente secuencia para construir una alineación óptima). Pueden calcularse como
- dónde es la puntuación media esperada por par alineado de residuos en un alineamiento de dos secuencias aleatorias. Altschul y Gish dieron los valores típicos, , , y , para la alineación local sin espacios utilizando BLOSUM62 como matriz de sustitución. El uso de valores típicos para evaluar la importancia se denomina método de tabla de búsqueda; no es exacto. La puntuación esperada E de una coincidencia de base de datos es el número de veces que una secuencia de base de datos no relacionada obtendría una puntuación S mayor que x por casualidad. La expectativa E obtenida en una búsqueda de una base de datos de secuencias D viene dada por
- Además, cuando , E podría aproximarse mediante la distribución de Poisson como
- Esta expectativa o valor esperado "E" (a menudo llamado puntuación E o valor E o valor e ) que evalúa la importancia de la puntuación HSP para la alineación local sin espacios se informa en los resultados de BLAST. El cálculo que se muestra aquí se modifica si se combinan HSP individuales, como cuando se producen alineaciones con huecos (que se describen a continuación), debido a la variación de los parámetros estadísticos.
- A continuación, BLAST evalúa la significación estadística de cada puntuación HSP explotando la distribución de valores extremos de Gumbel (EVD). (Se ha demostrado que la distribución de las puntuaciones de alineación local de Smith-Waterman entre dos secuencias aleatorias sigue el EVD de Gumbel. No se ha probado para las alineaciones locales que contienen huecos). De acuerdo con el EVD de Gumbel, la probabilidad p de observar una puntuación S igual o mayor que x viene dada por la ecuación
- Haga dos o más regiones HSP en una alineación más larga.
- A veces, encontramos dos o más regiones HSP en una secuencia de base de datos que se pueden convertir en una alineación más larga. Esto proporciona evidencia adicional de la relación entre la consulta y la secuencia de la base de datos. Hay dos métodos, el método de Poisson y el método de la suma de puntuaciones, para comparar la importancia de las regiones HSP recién combinadas. Suponga que hay dos regiones HSP combinadas con los pares de puntuaciones (65, 40) y (52, 45), respectivamente. El método de Poisson da más importancia al conjunto con la puntuación máxima más baja (45> 40). Sin embargo, el método de suma de puntuaciones prefiere el primer conjunto, porque 65 + 40 (105) es mayor que 52 + 45 (97). El BLAST original utiliza el método de Poisson; BLAST con huecos y WU-BLAST utiliza el método de suma de puntuaciones.
- Muestre las alineaciones locales de Smith-Waterman con huecos de la consulta y cada una de las secuencias de base de datos coincidentes.
- El BLAST original solo genera alineaciones sin espacios que incluyen las HSP encontradas inicialmente individualmente, incluso cuando hay más de una HSP encontrada en una secuencia de base de datos.
- BLAST2 produce una única alineación con espacios que pueden incluir todas las regiones HSP encontradas inicialmente. Tenga en cuenta que el cálculo de la puntuación y su valor E correspondiente implica el uso de penalizaciones por hueco adecuadas.
- Informar cada partido que esperan la puntuación es inferior a un umbral parámetro E .
RÁPIDO paralelo
Las versiones BLAST paralelas de bases de datos divididas se implementan mediante MPI y Pthreads , y se han adaptado a varias plataformas, incluidas Windows , Linux , Solaris , Mac OS X y AIX . Los enfoques populares para paralelizar BLAST incluyen la distribución de consultas, la segmentación de la tabla hash, la paralelización de los cálculos y la segmentación de la base de datos (partición). Las bases de datos se dividen en partes del mismo tamaño y se almacenan localmente en cada nodo. Cada consulta se ejecuta en todos los nodos en paralelo y los archivos de salida BLAST resultantes de todos los nodos se fusionan para producir la salida final. Las implementaciones específicas incluyen MPIblast, ScalaBLAST, DCBLAST, etc. [14]
Programa
El programa BLAST se puede descargar y ejecutar como una utilidad de línea de comandos "blastall" o se puede acceder de forma gratuita a través de la web. El servidor web BLAST, alojado por el NCBI , permite a cualquier persona con un navegador web realizar búsquedas de similitudes en bases de datos de proteínas y ADN que se actualizan constantemente y que incluyen la mayoría de los organismos recién secuenciados.
El programa BLAST se basa en un formato de código abierto, lo que les da a todos acceso y les permite tener la capacidad de cambiar el código del programa. Esto ha llevado a la creación de varias "spin-offs" de BLAST.
Ahora hay un puñado de diferentes programas BLAST disponibles, que se pueden usar dependiendo de lo que uno esté intentando hacer y con lo que esté trabajando. Estos diferentes programas varían en la entrada de la secuencia de consulta, la base de datos que se busca y lo que se compara. Estos programas y sus detalles se enumeran a continuación:
BLAST es en realidad una familia de programas (todos incluidos en el ejecutable blastall). Estos incluyen: [15]
- BLAST de nucleótido-nucleótido (blastn)
- Este programa, dada una consulta de ADN, devuelve las secuencias de ADN más similares de la base de datos de ADN que especifica el usuario.
- BLAST proteína-proteína (blastp)
- Este programa, dada una consulta de proteínas, devuelve las secuencias de proteínas más similares de la base de datos de proteínas que especifica el usuario.
- BLAST iterativo de posición específica (PSI-BLAST) (blastpgp)
- Este programa se utiliza para encontrar parientes lejanos de una proteína. Primero, se crea una lista de todas las proteínas estrechamente relacionadas. Estas proteínas se combinan en una secuencia de "perfil" general, que resume las características importantes presentes en estas secuencias. Luego, se ejecuta una consulta contra la base de datos de proteínas utilizando este perfil y se encuentra un grupo más grande de proteínas. Este grupo más grande se usa para construir otro perfil y el proceso se repite.
- Al incluir proteínas relacionadas en la búsqueda, PSI-BLAST es mucho más sensible para detectar relaciones evolutivas distantes que un BLAST estándar de proteína-proteína.
- Proteína de traducción de 6 marcos de nucleótidos (blastx)
- Este programa compara los productos de traducción conceptual de seis marcos de una secuencia de consulta de nucleótidos (ambas cadenas) con una base de datos de secuencias de proteínas.
- Traducción de 6 marcos de nucleótidos - traducción de 6 marcos de nucleótidos (tblastx)
- Este programa es el más lento de la familia BLAST. Traduce la secuencia de nucleótidos de la consulta en los seis marcos posibles y la compara con las traducciones de seis marcos de una base de datos de secuencias de nucleótidos. El propósito de tblastx es encontrar relaciones muy distantes entre secuencias de nucleótidos.
- Traducción proteína-nucleótido de 6 marcos (tblastn)
- Este programa compara una consulta de proteínas con los seis marcos de lectura de una base de datos de secuencias de nucleótidos.
- Gran cantidad de secuencias de consulta (megablast)
- Al comparar un gran número de secuencias de entrada a través de la línea de comandos BLAST, "megablast" es mucho más rápido que ejecutar BLAST varias veces. Concatena muchas secuencias de entrada para formar una secuencia grande antes de buscar en la base de datos BLAST, luego analiza los resultados de la búsqueda para obtener alineaciones individuales y valores estadísticos.
De estos programas, BLASTn y BLASTp son los más utilizados [ cita requerida ] porque utilizan comparaciones directas y no requieren traducción. Sin embargo, dado que las secuencias de proteínas se conservan mejor evolutivamente que las secuencias de nucleótidos, tBLASTn, tBLASTx y BLASTx producen resultados más fiables y precisos cuando se trata de codificar ADN. También permiten que uno pueda ver directamente la función de la secuencia de proteínas, ya que al traducir la secuencia de interés antes de la búsqueda, a menudo se obtienen aciertos de proteínas anotados.
Versiones alternativas
Una versión diseñada para comparar genomas grandes o ADN es BLASTZ .
CS-BLAST (Context-Specific BLAST) es una versión extendida de BLAST para buscar secuencias de proteínas que encuentra el doble de secuencias relacionadas remotamente que BLAST a la misma velocidad y tasa de error. En CS-BLAST, las probabilidades de mutación entre aminoácidos dependen no solo de un solo aminoácido, como en BLAST, sino también de su contexto de secuencia local. La Universidad de Washington produjo una versión alternativa de NCBI BLAST, llamada WU-BLAST. Desde entonces, los derechos han sido adquiridos a Advanced Biocomputing, LLC.
En 2009, NCBI ha lanzado un nuevo conjunto de ejecutables BLAST, el BLAST + basado en C ++, y ha lanzado versiones C hasta la 2.2.26. [16] A partir de la versión 2.2.27 (abril de 2013), solo están disponibles los ejecutables BLAST +. Entre los cambios está el reemplazo del blastall
ejecutable con ejecutables separados para los diferentes programas BLAST y cambios en el manejo de opciones. La utilidad formatdb (basada en C) ha sido reemplazada por makeblastdb (basada en C ++) y las bases de datos formateadas por cualquiera de ellas deberían ser compatibles para lanzamientos de blast idénticos. Los algoritmos siguen siendo similares, sin embargo, la cantidad de resultados encontrados y su orden pueden variar significativamente entre la versión anterior y la más reciente. BLAST + desde
Versiones aceleradas
TimeLogic ofrece una implementación acelerada por FPGA del algoritmo BLAST llamado Tera-BLAST que es cientos de veces más rápido.
Otras versiones admitidas anteriormente incluyen:
- FPGA acelerado
- Antes de su adquisición por parte de Qiagen , CLC bio colaboró con SciEngines GmbH en un acelerador FPGA que, según afirmaron, dará una aceleración 188x de BLAST.
- El proyecto Open Bio de Mitrion-C fue un esfuerzo para portar BLAST para que se ejecute en FPGA de Mitrion .
- Acelerado por GPU
- GPU-Blast [17] es una versión acelerada de NCBI BLASTP para CUDA que es de 3 a 4 veces más rápida que NCBI Blast.
- CUDA-BLASTP [18] es una versión de BLASTP que está acelerada por GPU y se afirma que se ejecuta hasta 10 veces más rápido que NCBI BLAST.
- G-BLASTN [19] es una versión acelerada de NCBI blastn y megablast, cuya aceleración varía de 4x a 14x (en comparación con las mismas ejecuciones con 4 subprocesos de CPU). Su limitación actual es que la base de datos debe caber en la memoria de la GPU.
- Acelerado por CPU
- MPIBlast es una implementación paralela de NCBI BLAST que utiliza la interfaz de paso de mensajes . Al utilizar de manera eficiente los recursos computacionales distribuidos a través de la fragmentación de la base de datos, la segmentación de consultas, la programación inteligente y las E / S paralelas, mpiBLAST mejora el rendimiento de NCBI BLAST en varios órdenes de magnitud mientras escala a cientos de procesadores.
- CaBLAST [20] acelera la búsqueda en grandes bases de datos en órdenes de magnitud al explotar la redundancia en los datos.
- Paracel BLAST fue una implementación comercial paralela de NCBI BLAST, que admite cientos de procesadores.
- QuickBLAST (kblastp) de NCBI es una implementación acelerada por prefiltrado basada en estimaciones del índice Jaccard con fragmentos pentaméricos hash. El filtrado reduce ligeramente la sensibilidad, pero aumenta el rendimiento en un orden de magnitud. [21] NCBI solo hace que la búsqueda esté disponible en su colección de proteínas no redundantes (nr) y no ofrece descargas.
Alternativas a BLAST
El predecesor de BLAST, FASTA , también se puede utilizar para la búsqueda de similitudes de proteínas y ADN. FASTA proporciona un conjunto similar de programas para comparar proteínas con bases de datos de proteínas y ADN, ADN con bases de datos de ADN y proteínas, e incluye programas adicionales para trabajar con péptidos cortos desordenados y secuencias de ADN. Además, el paquete FASTA proporciona SSEARCH, una implementación vectorizada del riguroso algoritmo Smith-Waterman . FASTA es más lento que BLAST, pero proporciona una gama mucho más amplia de matrices de puntuación, lo que facilita la adaptación de una búsqueda a una distancia evolutiva específica.
Una alternativa extremadamente rápido pero considerablemente menos sensible a BLAST es Blat ( B última L ike Un lignment T ool). Mientras BLAST realiza una búsqueda lineal, BLAT se basa en k-mer que indexa la base de datos y, por lo tanto, a menudo puede encontrar semillas más rápido. [22] Otra alternativa de software similar a BLAT es PatternHunter .
Los avances en la tecnología de secuenciación a finales de la década de 2000 han hecho que la búsqueda de coincidencias de nucleótidos muy similares sea un problema importante. Los nuevos programas de alineación diseñados para este uso suelen utilizar la indexación BWT de la base de datos de destino (normalmente un genoma). Las secuencias de entrada se pueden mapear muy rápidamente y la salida suele tener la forma de un archivo BAM. Los programas de alineación de ejemplo son BWA , SOAP y Bowtie .
Para la identificación de proteínas, la búsqueda de dominios conocidos (por ejemplo, de Pfam ) haciendo coincidir con modelos ocultos de Markov es una alternativa popular, como HMMER .
Una alternativa a BLAST para comparar dos bancos de secuencias es PLAST. PLAST proporciona una herramienta de búsqueda de similitud de secuencia de banco a banco de alto rendimiento que se basa en los algoritmos PLAST [23] y ORIS [24] . Los resultados de PLAST son muy similares a BLAST, pero PLAST es significativamente más rápido y capaz de comparar grandes conjuntos de secuencias con una pequeña huella de memoria (es decir, RAM).
Para aplicaciones en metagenómica, donde la tarea es comparar miles de millones de lecturas cortas de ADN con decenas de millones de referencias de proteínas, DIAMOND [25] se ejecuta hasta 20.000 veces más rápido que BLASTX, manteniendo un alto nivel de sensibilidad.
El software de código abierto MMseqs es una alternativa a BLAST / PSI-BLAST, que mejora las herramientas de búsqueda actuales en todo el rango de compensación de velocidad-sensibilidad, logrando sensibilidades mejores que PSI-BLAST a más de 400 veces su velocidad. [26]
Se han sugerido enfoques de computación óptica como alternativas prometedoras a las implementaciones eléctricas actuales. OptCAM es un ejemplo de tales enfoques y se demuestra que es más rápido que BLAST. [27]
Comparación de BLAST y el proceso Smith-Waterman
Si bien tanto Smith-Waterman como BLAST se utilizan para encontrar secuencias homólogas buscando y comparando una secuencia de consulta con las de las bases de datos, tienen sus diferencias.
Debido al hecho de que BLAST se basa en un algoritmo heurístico, los resultados recibidos a través de BLAST, en términos de los hits encontrados, pueden no ser los mejores resultados posibles, ya que no le proporcionará todos los hits dentro de la base de datos. BLAST pierde coincidencias difíciles de encontrar.
Una mejor alternativa para encontrar los mejores resultados posibles sería utilizar el algoritmo de Smith-Waterman. Este método varía del método BLAST en dos áreas, precisión y velocidad. La opción Smith-Waterman proporciona una mayor precisión, ya que encuentra coincidencias que BLAST no puede, porque no pierde ninguna información. Por lo tanto, es necesario para una homología remota. Sin embargo, en comparación con BLAST, consume más tiempo, sin mencionar que requiere una gran cantidad de uso y espacio de la computadora. Sin embargo, se ha descubierto que las tecnologías para acelerar el proceso Smith-Waterman mejoran drásticamente el tiempo necesario para realizar una búsqueda. Estas tecnologías incluyen chips FPGA y tecnología SIMD .
Para recibir mejores resultados de BLAST, la configuración se puede cambiar desde su configuración predeterminada. Sin embargo, no existe una forma determinada o establecida de cambiar estos ajustes para obtener los mejores resultados para una secuencia determinada. Las configuraciones disponibles para el cambio son E-Value, costos de brecha, filtros, tamaño de palabra y matriz de sustitución. Tenga en cuenta que el algoritmo utilizado para BLAST se desarrolló a partir del algoritmo utilizado para Smith-Waterman. BLAST emplea una alineación que encuentra "alineaciones locales entre secuencias encontrando coincidencias cortas y a partir de estas coincidencias iniciales se crean alineaciones (locales)". [28]
Visualización de salida BLAST
Para ayudar a los usuarios a interpretar los resultados de BLAST, se encuentra disponible un software diferente. Según la instalación y el uso, las funciones de análisis y la tecnología, a continuación se muestran algunas herramientas disponibles: [29]
- Servicio NCBI BLAST
- intérpretes generales de salida BLAST, basados en GUI: JAMBLAST, Blast Viewer, BLASTGrabber
- Entornos BLAST integrados: PLAN, BlastStation-Free, SequenceServer
- Analizadores de salida BLAST: MuSeqBox, Zerg, BioParser, BLAST-Explorer
- herramientas especializadas relacionadas con BLAST: MEGAN, BLAST2GENE, BOV, Circoletto
En las Figuras 4 y 5 se muestran ejemplos de visualizaciones de los resultados de BLAST.
Usos de BLAST
BLAST se puede utilizar para varios propósitos. Estos incluyen identificar especies, localizar dominios, establecer filogenia, mapeo de ADN y comparación.
- Identificación de especies
- Con el uso de BLAST, posiblemente pueda identificar correctamente una especie o encontrar especies homólogas. Esto puede resultar útil, por ejemplo, cuando se trabaja con una secuencia de ADN de una especie desconocida.
- Localización de dominios
- Cuando trabaje con una secuencia de proteína, puede ingresarla en BLAST para localizar dominios conocidos dentro de la secuencia de interés.
- Estableciendo la filogenia
- Usando los resultados recibidos a través de BLAST, puede crear un árbol filogenético usando la página web de BLAST. Las filogenias basadas solo en BLAST son menos confiables que otros métodos filogenéticos computacionales especialmente diseñados , por lo que solo se debe confiar en ellos para análisis filogenéticos de "primer paso".
- Mapeo de ADN
- Cuando se trabaja con una especie conocida y se busca secuenciar un gen en una ubicación desconocida, BLAST puede comparar la posición cromosómica de la secuencia de interés con secuencias relevantes en las bases de datos. NCBI tiene una herramienta "Magic-BLAST" construida alrededor de BLAST para este propósito. [30]
- Comparación
- Cuando se trabaja con genes, BLAST puede localizar genes comunes en dos especies relacionadas y se puede utilizar para mapear anotaciones de un organismo a otro.
Ver también
- Clasificador de proteínas PSI
- Algoritmo de Needleman-Wunsch
- Algoritmo de Smith-Waterman
- Alineación de secuencia
- Software de alineación de secuencias
- Sequerome
- eTBLAST
Referencias
- ^ "Información del desarrollador de BLAST" . blast.ncbi.nlm.nih.gov .
- ^ a b c Douglas Martin (21 de febrero de 2008). "Samuel Karlin, matemático versátil, muere a los 83" . The New York Times .
- ^ RM Casey (2005). "Ayudas de secuencias de BLAST en genómica y proteómica" . Red de inteligencia empresarial.
- ^ Lipman, DJ; Pearson, WR (1985). "Búsquedas rápidas y sensibles de similitud de proteínas". Ciencia . 227 (4693): 1435–41. Código Bibliográfico : 1985Sci ... 227.1435L . doi : 10.1126 / science.2983426 . PMID 2983426 .
- ^ "Temas BLAST" .
- ^ Dan Stober (16 de enero de 2008). "Sam Karlin, matemático que mejoró el análisis de ADN, murió a los 83" . Stanford.edu .
- ^ a b Stephen Altschul ; Warren Gish ; Webb Miller ; Eugene Myers ; David J. Lipman (1990). "Herramienta básica de búsqueda de alineación local" . Revista de Biología Molecular . 215 (3): 403–410. doi : 10.1016 / S0022-2836 (05) 80360-2 . PMID 2231712 .
- ^ Oehmen, C .; Nieplocha, J. (2006). "ScalaBLAST: una implementación escalable de BLAST para análisis bioinformático intensivo de datos de alto rendimiento" . Transacciones IEEE en sistemas paralelos y distribuidos . 17 (8): 740. doi : 10.1109 / TPDS.2006.112 . S2CID 11122366 .
- ^ Oehmen, CS; Baxter, DJ (2013). "ScalaBLAST 2.0: cálculos BLAST rápidos y robustos en sistemas multiprocesador" . Bioinformática . 29 (6): 797–798. doi : 10.1093 / bioinformatics / btt013 . PMC 3597145 . PMID 23361326 .
- ^ "Sentido de secuencias: Stephen F. Altschul en Bettering BLAST" . ScienceWatch. Julio-agosto de 2000. Archivado desde el original el 7 de octubre de 2007.
- ^ Steven Henikoff ; Jorja Henikoff (1992). "Matrices de sustitución de aminoácidos de bloques de proteínas" . PNAS . 89 (22): 10915–10919. Código Bibliográfico : 1992PNAS ... 8910915H . doi : 10.1073 / pnas.89.22.10915 . PMC 50453 . PMID 1438297 .
- ^ Montaje, DW (2004). Bioinformática: análisis de secuencia y genoma (2ª ed.). Prensa de Cold Spring Harbor. ISBN 978-0-87969-712-9.
- ^ Adaptado de Biological Sequence Analysis I, Temas actuales en el análisis del genoma [1] .
- ^ Yim, WC; Cushman, JC (2017). "Divide and Conquer (DC) BLAST: ejecución BLAST rápida y fácil en entornos HPC" . PeerJ . 5 : e3486. doi : 10.7717 / peerj.3486 . PMC 5483034 . PMID 28652936 .
- ^ "Tablas de selección de programas del sitio web Blast NCBI" .
- ^ Camacho, C .; Coulouris, G .; Avagyan, V .; Hombre.; Papadopoulos, J .; Bealer, K .; Madden, TL (2009). "BLAST +: Arquitectura y aplicaciones" . BMC Bioinformática . 10 : 421. doi : 10.1186 / 1471-2105-10-421 . PMC 2803857 . PMID 20003500 .
- ^ Vouzis, PD; Sahinidis, NV (2010). "GPU-BLAST: utilizando procesadores gráficos para acelerar la alineación de secuencias de proteínas" . Bioinformática . 27 (2): 182–8. doi : 10.1093 / bioinformatics / btq644 . PMC 3018811 . PMID 21088027 .
- ^ Liu W, Schmidt B, Müller-Wittig W (2011). "CUDA-BLASTP: aceleración de BLASTP en hardware de gráficos habilitado para CUDA". IEEE / ACM Trans Comput Biol Bioinform . 8 (6): 1678–84. doi : 10.1109 / TCBB.2011.33 . PMID 21339531 . S2CID 18221547 .
- ^ Zhao K, Chu X (mayo de 2014). "G-BLASTN: aceleración de la alineación de nucleótidos por procesadores gráficos" . Bioinformática . 30 (10): 1384–91. doi : 10.1093 / bioinformatics / btu047 . PMID 24463183 .
- ^ Loh PR, Baym M, Berger B (julio de 2012). "Genómica compresiva" . Nat. Biotechnol . 30 (7): 627-30. doi : 10.1038 / nbt.2241 . PMID 22781691 .
- ^ Madden, Tom; Boratyn, Greg (2017). "QuickBLASTP: alineaciones de proteínas más rápidas" (PDF) . Actas del Festival de Investigación de los NIH . Consultado el 16 de mayo de 2019 . Página de resumen
- ^ Kent, W. James (1 de abril de 2002). "BLAT: la herramienta de alineación BLAST-Like" . Investigación del genoma . 12 (4): 656–664. doi : 10.1101 / gr.229202 . ISSN 1088-9051 . PMC 187518 . PMID 11932250 .
- ^ Lavenier, D .; Lavenier, Dominique (2009). "PLAST: herramienta de búsqueda de alineación local paralela para la comparación de bases de datos" . BMC Bioinformática . 10 : 329. doi : 10.1186 / 1471-2105-10-329 . PMC 2770072 . PMID 19821978 .
- ^ Lavenier, D. (2009). "Algoritmo de semilla de índice ordenado para la comparación intensiva de secuencias de ADN" (PDF) . Simposio internacional de IEEE 2008 sobre procesamiento paralelo y distribuido (PDF) . págs. 1–8. CiteSeerX 10.1.1.155.3633 . doi : 10.1109 / IPDPS.2008.4536172 . ISBN 978-1-4244-1693-6. S2CID 10804289 .
- ^ Buchfink, Xie y Huson (2015). "Alineación de proteínas rápida y sensible usando DIAMOND". Métodos de la naturaleza . 12 (1): 59–60. doi : 10.1038 / nmeth.3176 . PMID 25402007 . S2CID 5346781 .
- ^ Steinegger, Martin; Soeding, Johannes (16 de octubre de 2017). "MMseqs2 permite la búsqueda de secuencias de proteínas sensibles para el análisis de conjuntos de datos masivos". Biotecnología de la naturaleza . 35 (11): 1026–1028. doi : 10.1038 / nbt.3988 . hdl : 11858 / 00-001M-0000-002E-1967-3 . PMID 29035372 . S2CID 402352 .
- ^ Maleki, Ehsan; Koohi, Somayyeh; Kavehvash, Zahra; Mashaghi, Alireza (2020). "OptCAM: una arquitectura totalmente óptica ultrarrápida para el descubrimiento de variantes de ADN" . Revista de biofotónica . 13 (1): e201900227. doi : 10.1002 / jbio.201900227 . PMID 31397961 .
- ^ "Bioinformática explicada: BLAST versus Smith-Waterman" (PDF) . 4 de julio de 2007.
- ^ Neumann, Kumar y Shalchian-Tabrizi (2014). "Visualización de salida BLAST en la nueva era de secuenciación" . Briefings en Bioinformática . 15 (4): 484–503. doi : 10.1093 / bib / bbt009 . PMID 23603091 .
- ^ "NCBI Magic-BLAST" . ncbi.github.io . Consultado el 16 de mayo de 2019 .
enlaces externos
- Página web oficial
- Ejecutables BLAST + - descargas de fuentes gratuitas