Saltar al contenido principal

# 3.5: El algoritmo BLAST (Herramienta Básica de Búsqueda de Alineación Local)

$$\newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$

$$\newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$

$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$

( \newcommand{\kernel}{\mathrm{null}\,}\) $$\newcommand{\range}{\mathrm{range}\,}$$

$$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$

$$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}[1]{\| #1 \|}$$

$$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$

$$\newcommand{\Span}{\mathrm{span}}$$

$$\newcommand{\id}{\mathrm{id}}$$

$$\newcommand{\Span}{\mathrm{span}}$$

$$\newcommand{\kernel}{\mathrm{null}\,}$$

$$\newcommand{\range}{\mathrm{range}\,}$$

$$\newcommand{\RealPart}{\mathrm{Re}}$$

$$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$

$$\newcommand{\Argument}{\mathrm{Arg}}$$

$$\newcommand{\norm}[1]{\| #1 \|}$$

$$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$

$$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\AA}{\unicode[.8,0]{x212B}}$$

$$\newcommand{\vectorA}[1]{\vec{#1}} % arrow$$

$$\newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow$$

$$\newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$

$$\newcommand{\vectorC}[1]{\textbf{#1}}$$

$$\newcommand{\vectorD}[1]{\overrightarrow{#1}}$$

$$\newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}}$$

$$\newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}}$$

$$\newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$

$$\newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$

$$\newcommand{\avec}{\mathbf a}$$ $$\newcommand{\bvec}{\mathbf b}$$ $$\newcommand{\cvec}{\mathbf c}$$ $$\newcommand{\dvec}{\mathbf d}$$ $$\newcommand{\dtil}{\widetilde{\mathbf d}}$$ $$\newcommand{\evec}{\mathbf e}$$ $$\newcommand{\fvec}{\mathbf f}$$ $$\newcommand{\nvec}{\mathbf n}$$ $$\newcommand{\pvec}{\mathbf p}$$ $$\newcommand{\qvec}{\mathbf q}$$ $$\newcommand{\svec}{\mathbf s}$$ $$\newcommand{\tvec}{\mathbf t}$$ $$\newcommand{\uvec}{\mathbf u}$$ $$\newcommand{\vvec}{\mathbf v}$$ $$\newcommand{\wvec}{\mathbf w}$$ $$\newcommand{\xvec}{\mathbf x}$$ $$\newcommand{\yvec}{\mathbf y}$$ $$\newcommand{\zvec}{\mathbf z}$$ $$\newcommand{\rvec}{\mathbf r}$$ $$\newcommand{\mvec}{\mathbf m}$$ $$\newcommand{\zerovec}{\mathbf 0}$$ $$\newcommand{\onevec}{\mathbf 1}$$ $$\newcommand{\real}{\mathbb R}$$ $$\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}$$ $$\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}$$ $$\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}$$ $$\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}$$ $$\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}$$ $$\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}$$ $$\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}$$ $$\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}$$ $$\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}$$ $$\newcommand{\laspan}[1]{\text{Span}\{#1\}}$$ $$\newcommand{\bcal}{\cal B}$$ $$\newcommand{\ccal}{\cal C}$$ $$\newcommand{\scal}{\cal S}$$ $$\newcommand{\wcal}{\cal W}$$ $$\newcommand{\ecal}{\cal E}$$ $$\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}$$ $$\newcommand{\gray}[1]{\color{gray}{#1}}$$ $$\newcommand{\lgray}[1]{\color{lightgray}{#1}}$$ $$\newcommand{\rank}{\operatorname{rank}}$$ $$\newcommand{\row}{\text{Row}}$$ $$\newcommand{\col}{\text{Col}}$$ $$\renewcommand{\row}{\text{Row}}$$ $$\newcommand{\nul}{\text{Nul}}$$ $$\newcommand{\var}{\text{Var}}$$ $$\newcommand{\corr}{\text{corr}}$$ $$\newcommand{\len}[1]{\left|#1\right|}$$ $$\newcommand{\bbar}{\overline{\bvec}}$$ $$\newcommand{\bhat}{\widehat{\bvec}}$$ $$\newcommand{\bperp}{\bvec^\perp}$$ $$\newcommand{\xhat}{\widehat{\xvec}}$$ $$\newcommand{\vhat}{\widehat{\vvec}}$$ $$\newcommand{\uhat}{\widehat{\uvec}}$$ $$\newcommand{\what}{\widehat{\wvec}}$$ $$\newcommand{\Sighat}{\widehat{\Sigma}}$$ $$\newcommand{\lt}{<}$$ $$\newcommand{\gt}{>}$$ $$\newcommand{\amp}{&}$$ $$\definecolor{fillinmathshade}{gray}{0.9}$$

El algoritmo BLAST analiza el problema de la búsqueda de bases de datos de secuencias, en donde tenemos una consulta, que es una nueva secuencia, y un objetivo, que es un conjunto de muchas secuencias antiguas, y nos interesa saber a cuál (si alguna) de las secuencias diana es la consulta relacionada. Una de las ideas clave de BLAST es que no requiere que las alineaciones individuales sean perfectas; una vez que se identifica una coincidencia inicial, podemos afinar las coincidencias más tarde para encontrar una buena alineación que cumpla con una puntuación umbral. Además, BLAST explota una característica distinta de los problemas de búsqueda de bases de datos: la mayoría de las secuencias diana no estarán completamente relacionadas con la secuencia de consulta y muy pocas secuencias coincidirán.

Sin embargo, las alineaciones correctas (casi perfectas) tendrán largas subcadenas de nucleótidos que coinciden perfectamente. Por ejemplo, si buscamos secuencias de longitud 100 y vamos a rechazar coincidencias que sean menos de 90% idénticas, no necesitamos mirar secuencias que ni siquiera contienen un tramo consecutivo de menos de 10 nucleótidos coincidentes en una fila. Basamos esta suposición en el: si m artículos se ponen en n contenedores y m>n, se deben poner al menos 2 artículos en uno de los n contenedores.

Además, en biología, es más probable que el ADN funcional se conserve, y por lo tanto las mutaciones que encontremos no se distribuirán realmente al azar, sino que se agruparán en regiones no funcionales del ADN dejando intactas largas extensiones de ADN funcional. Por lo tanto, debido al principio del encasillamiento y debido a que secuencias muy similares tendrán tramos de similitud, podemos preseleccionar las secuencias para tramos largos comunes. Esta idea se usa en BLAST dividiendo la secuencia de consulta en W-meros y preseleccionando las secuencias diana para todas las posibles$$W − mers$$ limitando nuestras semillas para que estén$$W − mers$$ en el vecindario que cumplan un cierto umbral.

El otro aspecto de BLAST que nos permite acelerar consultas repetidas es la capacidad de preprocesar una gran base de datos de ADN fuera de línea. Después del preprocesamiento, la búsqueda de una secuencia de longitud m en una base de datos de longitud n tomará solo O (m) tiempo. Las ideas clave en las que se basa BLAST son las ideas de hash y búsqueda de vecindarios que permiten buscar W − mers, incluso cuando no hay coincidencias precisas.

## El algoritmo BLAST

Los pasos son los siguientes:

1. Dividir la consulta en palabras superpuestas de longitud W (los W-mers)
2. Encuentra un “barrio” de palabras similares para cada palabra (ver abajo)
3. Busque cada palabra en el vecindario en una tabla hash para encontrar la ubicación en la base de datos donde aparece cada palabra. Llama a estas las semillas, y deja que S sea la colección de semillas.
4. Extiende las semillas en S hasta que la puntuación de la alineación descienda por debajo de algún umbral X.
5. Informar coincidencias con puntuaciones más altas en general

El paso de preprocesamiento de BLAST asegura que todas las subcadenas de W nucleótidos se incluirán en nuestra base de datos (o en una tabla hash). Estos se llaman los W-meros de la base de datos. Al igual que en el paso 1, primero dividimos la consulta observando todas las subcadenas de W nucleótidos consecutivos en la consulta. Para encontrar la vecindad de estos W-meros, luego modificamos estas secuencias cambiándolas ligeramente y calculando su similitud con la secuencia original. Generamos progresivamente palabras más disímiles en nuestro vecindario hasta que nuestra medida de similitud desciende por debajo de algún umbral T. Esto nos brinda flexibilidad para encontrar coincidencias que no tengan exactamente W caracteres coincidentes consecutivos seguidos, pero que tengan suficientes coincidencias para considerarse similares, es decir, para cumplir con una puntuación umbral de certificación.

Luego, buscamos todas estas palabras en nuestra tabla hash para encontrar semillas de W nucleótidos coincidentes consecutivos. Luego extendemos estas semillas para encontrar nuestra alineación usando el algoritmo Smith-Waterman para la alineación local, hasta que la puntuación caiga por debajo de cierto umbral X. Dado que la región que estamos considerando es un segmento mucho más corto, esto no será tan lento como ejecutar el algoritmo en toda la base de datos de ADN.

También es interesante observar la influencia de diversos parámetros de BLAST en el desempeño del algoritmo frente al tiempo de ejecución y la sensibilidad:

• W Aunque W grande resultaría en menos golpeos/colisiones espurios, haciéndolo así más rápido, también hay compensaciones asociadas, a saber: un gran vecindario de secuencias de consulta ligeramente diferentes, una tabla hash grande y muy pocos aciertos. Por otro lado, si W es demasiado pequeño, es posible que obtengamos demasiados aciertos, lo que empuja los costos de tiempo de ejecución al paso de extensión/alineación semilla.
• T Si T es más alto, el algoritmo será más rápido, pero es posible que se pierdan secuencias que son más distantes evolutivamente. Si comparas dos especies relacionadas, probablemente puedas establecer una T más alta ya que esperas encontrar más coincidencias entre secuencias que sean bastante similares.
• X Su influencia es bastante similar a la T en que ambos controlarán la sensibilidad del algoritmo. Si bien W y T afectan el número total de aciertos que uno recibe, y por lo tanto afectan drásticamente el tiempo de ejecución del algoritmo, establecer una X realmente estricta a pesar de W y T menos estrictos, resultará en costos de tiempo de ejecución al probar secuencias innecesarias que no cumplan con la rigurosidad de X. Por lo tanto, es importante igualar el rigurosidad de X con la de W y T para evitar tiempos de cómputos innecesarios.

## Extensiones a BLAST

• Filtrado Las regiones de baja complejidad pueden causar impactos espurios. Por ejemplo, si nuestra consulta tiene una cadena de copias del mismo nucleótido, por ejemplo, repeticiones de AC o solo G, y la base de datos tiene un largo tramo del mismo nucleótido, entonces habrá muchos éxitos inútiles. Para evitar esto, podemos intentar filtrar partes de baja complejidad de la consulta o podemos ignorar partes excesivamente representadas de la base de datos irrazonablemente.

• BLAST de dos golpes La idea aquí es usar hash doble en el que en lugar de hash un W -mer largo, vamos a hash dos W-mers pequeños. Esto nos permite encontrar pequeñas regiones de similitud ya que es mucho más probable que tenga dos W-meros más pequeños que coincidan en lugar de un W-mer largo. Esto nos permite obtener una mayor sensibilidad con un W más pequeño, a la vez que seguimos podando golpes espurios. Esto significa que pasaremos menos tiempo tratando de extender partidos que en realidad no coincidan. Así, esto nos permite mejorar la velocidad manteniendo la sensibilidad.

P: Por un W lo suficientemente largo, ¿tendría sentido considerar más de 2 W-mers más pequeños?
R: Sería interesante ver cómo el número de tales W-meros influye en la sensibilidad del algoritmo. Esto es similar a usar un peine, descrito a continuación.

• Peines Esta es la idea de usar W-mers no consecutivos para el hash. Recuerde de sus clases de biología que el tercer nucleótido en un triplete generalmente no tiene realmente un efecto sobre qué aminoácido está representado. Esto significa que cada tercer nucleótido de una secuencia es menos probable que se conserve por evolución, ya que a menudo no importa. Por lo tanto, podríamos querer buscar W-meros que se vean similares excepto en cada tercer codón. Este es un ejemplo particular de un peine. Un peine es simplemente una máscara de bits que representa qué nucleótidos nos importan cuando tratamos de encontrar coincidencias. Nosotros explicamos anteriormente por qué 110110110. (ignorando cada tercer nucleótido) podría ser un buen peine, y resulta serlo. Sin embargo, otros peines también son útiles. Una forma de elegir un peine es simplemente escoger algunos nucleótidos al azar. En lugar de elegir solo un peine para una proyección, es posible elegir aleatoriamente un conjunto de tales peines y proyectar los W-mers a lo largo de cada uno de estos peines para obtener un conjunto de bases de datos de búsqueda. Entonces, la cadena de consulta también se puede proyectar aleatoriamente a lo largo de estos peines para buscar en estas bases de datos, aumentando así la probabilidad de encontrar una coincidencia. Esto se llama Proyección Aleatoria. Ampliando esto, una idea interesante para un proyecto final es pensar en diferentes técnicas de proyección o hashing que tengan sentido biológicamente. Una adición a esta técnica es analizar falsos negativos y falsos positivos, y cambiar el peine para que sea más selectivo. Algunos artículos que exploran adiciones a esta búsqueda incluyen Califino-Rigoutsos'93, Buhler'01 e Indyk-Motwani'98.

• PSI-BLAST Iterativo Específico de Posición BLAST crea perfiles resumidos de proteínas relacionadas usando BLAST. Después de una ronda de BLAST, actualiza la matriz de puntuación de la alineación múltiple, y luego ejecuta rondas posteriores de BLAST, actualizando iterativamente la matriz de puntuación. Construye un Modelo Hidden Markov para rastrear la conservación de aminoácidos específicos. PSI-BLAST permite la detección de proteínas relacionadas a distancia.

This page titled 3.5: El algoritmo BLAST (Herramienta Básica de Búsqueda de Alineación Local) is shared under a CC BY-NC-SA 4.0 license and was authored, remixed, and/or curated by Manolis Kellis et al. (MIT OpenCourseWare) via source content that was edited to the style and standards of the LibreTexts platform.