Hispanopedia Wiki
Articulo de referencia

Algoritmo de Smith-Waterman

O(mn) "},"best-time":{"wt":""},"average-time":{"wt":""},"space":{"wt":" O(mn) "}},"i":0}}]}"> El algoritmo de Smith-Waterman realiza una alineación de secuencias local ; es deci...

Hispanopedia WikiContenido en espanolLectura gratuita

El algoritmo de Smith-Waterman realiza una alineación de secuencias local ; es decir, determina regiones similares entre dos cadenas de secuencias de ácidos nucleicos o de proteínas . En lugar de analizar la secuencia completa , el algoritmo de Smith-Waterman compara segmentos de todas las longitudes posibles y optimiza la medida de similitud .

El algoritmo fue propuesto por primera vez por Temple F. Smith y Michael S. Waterman en 1981. [ 1 ] Al igual que el algoritmo Needleman-Wunsch , del cual es una variación, Smith-Waterman es un algoritmo de programación dinámica . Como tal, posee la propiedad deseable de que garantiza encontrar la alineación local óptima con respecto al sistema de puntuación utilizado (que incluye la matriz de sustitución y el esquema de puntuación de huecos ). La principal diferencia con el algoritmo Needleman-Wunsch es que las celdas de la matriz de puntuación negativa se establecen en cero. El procedimiento de retroceso comienza en la celda de la matriz con la puntuación más alta y continúa hasta que se encuentra una celda con puntuación cero, lo que produce la alineación local con la puntuación más alta. Debido a su complejidad temporal cuadrática, a menudo no se puede aplicar en la práctica a problemas de gran escala y se reemplaza en favor de alternativas computacionalmente más eficientes como (Gotoh, 1982), [ 2 ] ( Altschul y Erickson, 1986), [ 3 ] y (Myers y Miller, 1988). [ 4 ]

Historia

En 1970, Saul B. Needleman y Christian D. Wunsch propusieron un algoritmo heurístico de homología para el alineamiento de secuencias, también conocido como algoritmo de Needleman-Wunsch. [ 5 ] Es un algoritmo de alineamiento global que requiereO(metronorte){\displaystyle O(mn)}pasos de cálculo (metro{\displaystyle m}ynorte{\displaystyle n}son las longitudes de las dos secuencias que se están alineando). Utiliza el cálculo iterativo de una matriz con el propósito de mostrar la alineación global. En la década siguiente, Sankoff, [ 6 ] Reichert, [ 7 ] Beyer [ 8 ] y otros formularon algoritmos heurísticos alternativos para analizar secuencias genéticas. Sellers introdujo un sistema para medir distancias de secuencia. [ 9 ] En 1976, Waterman et al. añadieron el concepto de huecos al sistema de medición original. [ 10 ] En 1981, Smith y Waterman publicaron su algoritmo Smith-Waterman para calcular la alineación local.

El algoritmo de Smith-Waterman requiere bastante tiempo: para alinear dos secuencias de longitudesmetro{\displaystyle m}ynorte{\displaystyle n},O(metro2norte+norte2metro){\displaystyle O(m^{2}n+n^{2}m)}Se requiere tiempo. Gotoh [ 2 ] y Altschul [ 3 ] optimizaron el algoritmo paraO(metronorte){\displaystyle O(mn)}pasos. La complejidad espacial fue optimizada por Myers y Miller [ 4 ] a partir deO(metronorte){\displaystyle O(mn)}aO(norte){\displaystyle O(n)}(lineal), dondenorte{\displaystyle n}es la longitud de la secuencia más corta, para el caso en que solo se desea una de las muchas alineaciones óptimas posibles. Chowdhury, Le y Ramachandran [ 11 ] optimizaron posteriormente el rendimiento de la caché del algoritmo manteniendo el uso del espacio lineal en la longitud total de las secuencias de entrada.

Motivación

En los últimos años, los proyectos genómicos realizados en diversos organismos han generado enormes cantidades de datos de secuencias de genes y proteínas, lo que requiere análisis computacional. El alineamiento de secuencias muestra las relaciones entre genes o proteínas, lo que permite comprender mejor su homología y funcionalidad. El alineamiento de secuencias también puede revelar dominios y motivos conservados .

Una de las motivaciones para el alineamiento local es la dificultad de obtener alineamientos correctos en regiones de baja similitud entre secuencias biológicas distantemente relacionadas, ya que las mutaciones han añadido demasiado "ruido" a lo largo del tiempo evolutivo como para permitir una comparación significativa de esas regiones. El alineamiento local evita por completo dichas regiones y se centra en aquellas con una puntuación positiva, es decir, aquellas con una señal de similitud conservada evolutivamente. Un requisito previo para el alineamiento local es una puntuación de expectativa negativa. La puntuación de expectativa se define como la puntuación promedio que el sistema de puntuación ( matriz de sustitución y penalizaciones por huecos ) arrojaría para una secuencia aleatoria.

Otra motivación para utilizar alineamientos locales es la existencia de un modelo estadístico fiable (desarrollado por Karlin y Altschul) para alineamientos locales óptimos. El alineamiento de secuencias no relacionadas tiende a producir puntuaciones de alineamiento local óptimas que siguen una distribución de valores extremos. Esta propiedad permite a los programas generar un valor esperado para el alineamiento local óptimo de dos secuencias, que mide la frecuencia con la que dos secuencias no relacionadas producirían un alineamiento local óptimo cuya puntuación sea mayor o igual a la puntuación observada. Valores esperados muy bajos indican que las dos secuencias en cuestión podrían ser homólogas , lo que significa que podrían compartir un ancestro común.

Algoritmo

Método de puntuación del algoritmo de Smith-Waterman

DejarA=a1a2...anorte{\displaystyle A=a_{1}a_{2}...a_{n}}yB=b1b2...bmetro{\displaystyle B=b_{1}b_{2}...b_{m}}sean las secuencias a alinear, dondenorte{\displaystyle n}ymetro{\displaystyle m}son las longitudes deA{\displaystyle A}yB{\displaystyle B}respectivamente.

  1. Determinar la matriz de sustitución y el esquema de penalización por huecos.
    • s(a,b){\displaystyle s(a,b)}- Índice de similitud de los elementos que constituían las dos secuencias
    • Wk{\displaystyle W_{k}}- La penalización de un hueco que tiene longitudk{\displaystyle k}
  2. Construir una matriz de puntuaciónH{\displaystyle H}e inicializa su primera fila y primera columna. El tamaño de la matriz de puntuación es(norte+1)∗(metro+1){\displaystyle (n+1)*(m+1)}La matriz utiliza indexación basada en 0.
    Hk0=H0l=0For0≤k≤norteanorted0≤l≤metro{\displaystyle H_{k0}=H_{0l}=0\quad para\quad 0\leq k\leq n\quad y\quad 0\leq l\leq m}
  3. Complete la matriz de puntuación utilizando la siguiente ecuación.
    Hij=máximo{Hi−1,j−1+s(ai,bj),máximok≥1{Hi−k,j−Wk},máximol≥1{Hi,j−l−Wl},0(1≤i≤norte,1≤j≤metro){\displaystyle H_{ij}=\max {\begin{cases}H_{i-1,j-1}+s(a_{i},b_{j}),\\\max _{k\geq 1}\{H_{i-k,j}-W_{k}\},\\\max _{l\geq 1}\{H_{i,j-l}-W_{l}\},\\0\end{cases}}\qquad (1\leq i\leq n,1\leq j\leq m)}
    dónde
    Hi−1,j−1+s(ai,bj){\displaystyle H_{i-1,j-1}+s(a_{i},b_{j})}es la puntuación de alineaciónai{\displaystyle a_{i}}ybj{\displaystyle b_{j}},
    Hi−k,j−Wk{\displaystyle H_{i-k,j}-W_{k}}es la puntuación siai{\displaystyle a_{i}}está al final de un hueco de longitudk{\displaystyle k},
    Hi,j−l−Wl{\displaystyle H_{i,j-l}-W_{l}}es la puntuación sibj{\displaystyle b_{j}}está al final de un hueco de longitudl{\displaystyle l},
    0{\displaystyle 0}significa que no hay similitud hastaai{\displaystyle a_{i}}ybj{\displaystyle b_{j}}.
  4. Rastreo. Comenzando por la puntuación más alta en la matriz de puntuación.H{\displaystyle H}y terminando en una celda de la matriz que tiene una puntuación de 0, se realiza un rastreo basado en la fuente de cada puntuación de forma recursiva para generar la mejor alineación local.

Explicación

El algoritmo de Smith-Waterman alinea dos secuencias mediante coincidencias/discrepancias (también conocidas como sustituciones), inserciones y eliminaciones. Tanto las inserciones como las eliminaciones son operaciones que introducen huecos, representados por guiones. El algoritmo de Smith-Waterman consta de varios pasos:

  1. Determina la matriz de sustitución y el esquema de penalización por huecos . Una matriz de sustitución asigna a cada par de bases o aminoácidos una puntuación según coincidan o no. Generalmente, las coincidencias obtienen puntuaciones positivas, mientras que las no coincidencias obtienen puntuaciones relativamente más bajas. Una función de penalización por huecos determina el coste en puntos por abrir o extender huecos. Se recomienda que los usuarios elijan el sistema de puntuación adecuado según sus objetivos. Además, es buena práctica probar diferentes combinaciones de matrices de sustitución y penalizaciones por huecos.
  2. Inicialice la matriz de puntuación . Las dimensiones de la matriz de puntuación son 1 + la longitud de cada secuencia, respectivamente. Todos los elementos de la primera fila y la primera columna se establecen en 0. La fila y la columna adicionales permiten alinear una secuencia con otra en cualquier posición, y al establecerlas en 0 se elimina la penalización por el hueco final.
  3. Puntuación . Califique cada elemento de la matriz de izquierda a derecha y de arriba abajo, considerando los resultados de las sustituciones (puntuaciones diagonales) o la adición de huecos (puntuaciones horizontales y verticales). Si ninguna de las puntuaciones es positiva, este elemento recibe un 0. En caso contrario, se utiliza la puntuación más alta y se registra su origen.
  4. Rastreo . Partiendo del elemento con la puntuación más alta, se realiza un rastreo recursivo basado en el origen de cada puntuación hasta encontrar 0. En este proceso se generan los segmentos con la puntuación de similitud más alta según el sistema de puntuación dado. Para obtener la segunda mejor alineación local, se aplica el proceso de rastreo comenzando en la segunda puntuación más alta fuera del rastreo de la mejor alineación.

Comparación con el algoritmo de Needleman-Wunsch

Alineación de secuencias global y local

El algoritmo de Smith-Waterman encuentra segmentos en dos secuencias que tienen similitudes, mientras que el algoritmo de Needleman-Wunsch alinea dos secuencias completas. Por lo tanto, cumplen propósitos diferentes. Ambos algoritmos utilizan los conceptos de matriz de sustitución, función de penalización por huecos, matriz de puntuación y proceso de retroceso. Las tres diferencias principales son:

Una de las distinciones más importantes es que el sistema de puntuación del algoritmo Smith-Waterman no asigna puntuaciones negativas, lo que permite la alineación local. Cuando un elemento tiene una puntuación inferior a cero, significa que las secuencias hasta esa posición no presentan similitudes; en ese caso, se le asigna un valor de cero para eliminar la influencia de la alineación previa. De esta forma, el cálculo puede continuar para encontrar la alineación en cualquier posición posterior.

La matriz de puntuación inicial del algoritmo de Smith-Waterman permite alinear cualquier segmento de una secuencia con una posición arbitraria en la otra. Sin embargo, en el algoritmo de Needleman-Wunsch también es necesario considerar la penalización por huecos en los extremos para alinear las secuencias completas.

Matriz de sustitución

A cada sustitución de base o de aminoácido se le asigna una puntuación. En general, a las coincidencias se les asignan puntuaciones positivas y a las discrepancias, puntuaciones relativamente más bajas. Tomemos como ejemplo una secuencia de ADN. Si las coincidencias obtienen +1 y las discrepancias -1, entonces la matriz de sustitución es:

Esta matriz de sustitución se puede describir como: s(ai,bj)={+1,ai=bj−1,ai≠bj{\displaystyle s(a_{i},b_{j})={\begin{cases}+1,\quad a_{i}=b_{j}\\-1,\quad a_{i}\neq b_{j}\end{cases}}}

Las distintas sustituciones de bases o de aminoácidos pueden tener puntuaciones diferentes. La matriz de sustitución de aminoácidos suele ser más compleja que la de las bases. Véase PAM , BLOSUM .

penalización por brecha

La penalización por hueco designa puntuaciones para la inserción o eliminación. Una estrategia simple de penalización por hueco consiste en usar una puntuación fija para cada hueco. Sin embargo, en biología, la puntuación debe contarse de manera diferente por razones prácticas. Por un lado, la similitud parcial entre dos secuencias es un fenómeno común; por otro lado, un solo evento de mutación genética puede resultar en la inserción de un único hueco largo. Por lo tanto, los huecos conectados que forman un hueco largo generalmente son más favorecidos que múltiples huecos cortos y dispersos. Para tener en cuenta esta diferencia, se han añadido los conceptos de apertura de hueco y extensión de hueco al sistema de puntuación. La puntuación de apertura de hueco suele ser más alta que la de extensión de hueco. Por ejemplo, los parámetros predeterminados en EMBOSS Water son: apertura de hueco = 10, extensión de hueco = 0,5.

Aquí analizamos dos estrategias comunes para la penalización por brecha. Consulte Penalización por brecha para obtener más estrategias.Wk{\displaystyle W_{k}}sea ​​la función de penalización de brecha para una brecha de longitudk{\displaystyle k}:

Lineal

Algoritmo simplificado de Smith-Waterman cuando se utiliza una función de penalización de brecha lineal.

Una penalización por brecha lineal tiene las mismas puntuaciones para abrir y extender una brecha:

Wk=kW1{\displaystyle W_{k}=kW_{1}},

dóndeW1{\displaystyle W_{1}}es el costo de un solo hueco.

La penalización por brecha es directamente proporcional a la longitud de la brecha. Cuando se utiliza una penalización lineal por brecha, el algoritmo de Smith-Waterman se puede simplificar a:

Hij=máximo{Hi−1,j−1+s(ai,bj),Hi−1,j−W1,Hi,j−1−W1,0{\displaystyle H_{ij}=\max {\begin{cases}H_{i-1,j-1}+s(a_{i},b_{j}),\\H_{i-1,j}-W_{1},\\H_{i,j-1}-W_{1},\\0\end{cases}}}

El algoritmo simplificado utilizaO(metronorte){\displaystyle O(mn)}pasos. Al puntuar un elemento, solo se deben considerar las penalizaciones por huecos de los elementos que están directamente adyacentes a este elemento.

Afín

Una penalización por brecha afín considera la apertura y la extensión de la brecha por separado:

Wk=túk+v(tú>0,v>0){\displaystyle W_{k}=uk+v\quad (u>0,v>0)},

dóndev{\displaystyle v}es la penalización por apertura de hueco, ytú{\displaystyle u}es la penalización por extensión de brecha. Por ejemplo, la penalización por una brecha de longitud 2 es2tú+v{\displaystyle 2u+v}.

En el artículo original sobre el algoritmo de Smith-Waterman se utilizó una penalización de brecha arbitraria.O(metro2norte){\displaystyle O(m^{2}n)}pasos, por lo tanto, requiere bastante tiempo. Gotoh optimizó los pasos para una penalización de brecha afín aO(metronorte){\displaystyle O(mn)}[ 2 ] pero el algoritmo optimizado solo intenta encontrar una alineación óptima, y ​​no se garantiza que se encuentre la alineación óptima. [ 3 ] Altschul modificó el algoritmo de Gotoh para encontrar todas las alineaciones óptimas manteniendo la complejidad computacional. [ 3 ] Posteriormente , Myers y Miller señalaron que el algoritmo de Gotoh y Altschul se puede modificar aún más basándose en el método publicado por Hirschberg en 1975, [ 12 ] y aplicaron este método. [ 4 ] El algoritmo de Myers y Miller puede alinear dos secuencias usandoO(norte){\displaystyle O(n)}espacio, connorte{\displaystyle n}siendo la longitud de la secuencia más corta. Chowdhury, Le y Ramachandran [ 11 ] demostraron posteriormente cómo ejecutar el algoritmo de Gotoh de manera eficiente en caché en un espacio lineal utilizando una estrategia recursiva de divide y vencerás diferente a la utilizada por Hirschberg. El algoritmo resultante se ejecuta más rápido que el algoritmo de Myers y Miller en la práctica debido a su rendimiento de caché superior. [ 11 ]

Ejemplo de penalización por brecha

Tomemos como ejemplo la alineación de las secuencias TACGGGCCCGCTAC y TAGCCCTATCGGTCA . Cuando se utiliza la función de penalización de huecos lineal, el resultado es (Alineaciones realizadas por EMBOSS Water. La matriz de sustitución es DNAfull (puntuación de similitud: +5 para caracteres coincidentes, de lo contrario -4). La apertura y extensión de huecos son 0,0 y 1,0 respectivamente):

TACGGGCCCGCTA-CTA---G-CC-CTATC

Cuando se utiliza la penalización de brecha afín, el resultado es (la apertura y la extensión de la brecha son 5,0 y 1,0 respectivamente):

TACGGGCCCGCTATA---GCC--CTA

Este ejemplo demuestra que una penalización por hueco afín puede ayudar a evitar pequeños huecos dispersos.

Matriz de puntuación

La función de la matriz de puntuación es realizar comparaciones uno a uno entre todos los componentes de dos secuencias y registrar los resultados de la alineación óptima. El proceso de puntuación refleja el concepto de programación dinámica. La alineación óptima final se encuentra expandiendo iterativamente la alineación óptima en crecimiento. En otras palabras, la alineación óptima actual se genera decidiendo qué ruta (coincidencia/discrepancia o inserción de un hueco) proporciona la puntuación más alta de la alineación óptima anterior. El tamaño de la matriz es la longitud de una secuencia más 1 por la longitud de la otra secuencia más 1. La primera fila y la primera columna adicionales sirven para alinear una secuencia con cualquier posición de la otra secuencia. Tanto la primera fila como la primera columna se establecen en 0 para que no se penalice el hueco final. La matriz de puntuación inicial es:

Ejemplo

Tomemos como ejemplo la alineación de las secuencias de ADN TGTTACGG y GGTTGACTA . Utilice el siguiente esquema:

  • Matriz de sustitución:s(ai,bj)={+3,ai=bj−3,ai≠bj{\displaystyle s(a_{i},b_{j})={\begin{cases}+3,\quad a_{i}=b_{j}\\-3,\quad a_{i}\neq b_{j}\end{cases}}}
  • Penalización por brecha:Wk=2k{\displaystyle W_{k}=2k}(una penalización de brecha lineal deW1=2{\displaystyle W_{1}=2})

Inicialice y complete la matriz de puntuación, como se muestra a continuación. Esta figura muestra el proceso de puntuación de los tres primeros elementos. El color amarillo indica las bases que se están considerando. El color rojo indica la puntuación máxima posible para la celda que se está evaluando.

Inicialización de la matriz de puntuación (izquierda 1) y proceso de puntuación de los tres primeros elementos (izquierda 2-4)

La matriz de puntuación final se muestra a la izquierda. El color azul indica la puntuación más alta. Un elemento puede recibir puntuación de más de un elemento; cada uno formará una ruta diferente si se realiza el seguimiento inverso. En caso de múltiples puntuaciones máximas, el seguimiento inverso debe realizarse comenzando con cada una de ellas. El proceso de seguimiento inverso se muestra a la derecha. La mejor alineación local se genera en sentido inverso.

El resultado de la alineación es:

GTT - AC GTTGAC

Implementación

Una implementación del algoritmo Smith-Waterman, denominada SSEARCH, está disponible en el paquete de análisis de secuencias FASTA de UVA FASTA Downloads . Esta implementación incluye código acelerado por Altivec para procesadores PowerPC G4 y G5, que acelera las comparaciones entre 10 y 20 veces, mediante una modificación del método de Wozniak (1997) [ 13 ] y una vectorización SSE2 desarrollada por Farrar [ 14 ], lo que hace que las búsquedas óptimas en bases de datos de secuencias de proteínas sean bastante prácticas. Una biblioteca, SSW, extiende la implementación de Farrar para devolver información de alineación además de la puntuación óptima de Smith-Waterman [ 15 ] .

Versiones aceleradas

FPGA

Cray demostró la aceleración del algoritmo Smith-Waterman utilizando una plataforma de computación reconfigurable basada en chips FPGA , con resultados que muestran una aceleración de hasta 28 veces en comparación con las soluciones estándar basadas en microprocesadores. Otra versión del algoritmo Smith-Waterman basada en FPGA muestra aceleraciones de hasta 100 veces [ 16 ] en comparación con un procesador Opteron de 2,2  GHz. [ 17 ] Los sistemas TimeLogic DeCypher y CodeQuest también aceleran Smith-Waterman y Framesearch utilizando tarjetas FPGA PCIe.

Una tesis de maestría de 2011 [ 18 ] incluye un análisis de la aceleración Smith-Waterman basada en FPGA.

En una publicación de 2016 titulada " El código OpenCL compilado con Xilinx SDAccel acelera la secuenciación del genoma y supera el rendimiento de la CPU/GPU por vatio entre 12 y 21 veces" , se presentó una implementación muy eficiente. Utilizando una tarjeta FPGA PCIe equipada con una FPGA Xilinx Virtex-7 2000T, el rendimiento por vatio superó al de la CPU/GPU entre 12 y 21 veces.

GPU

El Laboratorio Nacional Lawrence Livermore y el Instituto Conjunto del Genoma del Departamento de Energía de los Estados Unidos (EE. UU.) implementaron una versión acelerada de las búsquedas de alineación de secuencias locales de Smith-Waterman utilizando unidades de procesamiento gráfico (GPU), con resultados preliminares que muestran una aceleración de 2x en comparación con las implementaciones de software. [ 19 ] Un método similar ya se ha implementado en el software Biofacet desde 1997, con el mismo factor de aceleración. [ 20 ]

También existen varias implementaciones del algoritmo para GPU en la plataforma CUDA C de NVIDIA . [ 21 ] En comparación con la mejor implementación conocida para CPU (que utiliza instrucciones SIMD en la arquitectura x86), realizada por Farrar, las pruebas de rendimiento de esta solución con una sola tarjeta NVidia GeForce 8800 GTX muestran un ligero aumento en el rendimiento para secuencias más pequeñas, pero una ligera disminución para secuencias más grandes. Sin embargo, las mismas pruebas realizadas con dos tarjetas NVidia GeForce 8800 GTX son casi el doble de rápidas que la implementación de Farrar para todos los tamaños de secuencia probados.

Ya está disponible una nueva implementación de SW basada en GPU CUDA que es más rápida que las versiones anteriores y que además elimina las limitaciones en la longitud de las consultas. Consulte CUDASW++ .

Se han reportado once implementaciones de software diferentes en CUDA, tres de las cuales reportan aceleraciones de 30X. [ 22 ]

Finalmente, otras implementaciones aceleradas por GPU del algoritmo Smith-Waterman se pueden encontrar en NVIDIA Parabricks , el paquete de software de NVIDIA para el análisis del genoma. [ 23 ]

SIMD

En el año 2000, Rognes y Seeberg describieron en una publicación una implementación rápida del algoritmo Smith-Waterman utilizando la tecnología SIMD ( Single Instruction, Multiple Data ) disponible en los procesadores Intel Pentium MMX y tecnologías similares. [ 24 ] A diferencia del enfoque de Wozniak (1997), la nueva implementación se basaba en vectores paralelos a la secuencia de consulta, no en vectores diagonales. La empresa Sencel Bioinformatics ha solicitado una patente para este enfoque. Sencel continúa desarrollando el software y proporciona ejecutables gratuitos para uso académico.

Ahora está disponible una vectorización SSE2 del algoritmo (Farrar, 2007) que proporciona una aceleración de 8 a 16 veces en procesadores Intel/AMD con extensiones SSE2. [ 14 ] Al ejecutarse en un procesador Intel que utiliza la microarquitectura Core, la implementación SSE2 logra un aumento de 20 veces. La implementación SSE2 de Farrar está disponible como el programa SSEARCH en el paquete de comparación de secuencias FASTA . SSEARCH está incluido en el conjunto de programas de búsqueda de similitud del Instituto Europeo de Bioinformática .

La empresa danesa de bioinformática CLC bio ha logrado aceleraciones de casi 200 veces con respecto a las implementaciones de software estándar utilizando SSE2 en una  CPU Intel Core 2 Duo de 2,17 GHz, según un informe técnico disponible públicamente .

La versión acelerada del algoritmo Smith-Waterman, compatible con servidores Linux basados ​​en Intel y Advanced Micro Devices (AMD) , es compatible con el paquete GenCore 6 , ofrecido por Biocceleration . Las pruebas de rendimiento de este paquete de software muestran una aceleración de hasta 10 veces en comparación con la implementación estándar en el mismo procesador.

Actualmente, CLC bio es la única empresa en bioinformática que ofrece soluciones SSE y FPGA para acelerar el algoritmo Smith-Waterman, y ha logrado aceleraciones de más de 110 veces con respecto a las implementaciones de software estándar gracias a CLC Bioinformatics Cube .

La implementación más rápida del algoritmo en CPUs con SSSE3 se encuentra en el software SWIPE (Rognes, 2011), [ 25 ] disponible bajo la Licencia Pública General Affero de GNU . Paralelamente, este software compara residuos de dieciséis secuencias de bases de datos diferentes con un residuo de consulta. Utilizando una secuencia de consulta de 375 residuos, se logró una velocidad de 106 mil millones de actualizaciones de celdas por segundo (GCUPS) en un sistema de procesadores duales Intel Xeon X5650 de seis núcleos, lo que es más de seis veces más rápido que el software basado en el enfoque "striped" de Farrar. Es más rápido que BLAST cuando se utiliza la matriz BLOSUM50.

Una implementación del algoritmo Smith-Waterman llamada diagonalsw , escrita en C y C++ , utiliza conjuntos de instrucciones SIMD ( SSE4.1 para la plataforma x86 y AltiVec para la plataforma PowerPC). Se distribuye bajo una licencia MIT de código abierto .

Motor de banda ancha celular

En 2008, Farrar [ 26 ] describió una adaptación del Striped Smith–Waterman [ 14 ] al Cell Broadband Engine e informó velocidades de 32 y 12 GCUPS en una blade IBM QS20 y una Sony PlayStation 3 , respectivamente.

Limitaciones

La rápida expansión de los datos genéticos pone a prueba la velocidad de los algoritmos actuales de alineación de secuencias de ADN. La necesidad de un método eficiente y preciso para el descubrimiento de variantes de ADN exige enfoques innovadores para el procesamiento paralelo en tiempo real.

Véase también

Referencias

  1. ↑ Smith, Temple F. y Waterman, Michael S. (1981). "Identificación de subsecuencias moleculares comunes" (PDF) . Journal of Molecular Biology . 147 (1): 195– 197. CiteSeerX 10.1.1.63.2897 . doi : 10.1016/0022-2836(81)90087-5 . PMID 7265238 .  
  2. 1 2 3 Osamu Gotoh (1982). "Un algoritmo mejorado para la coincidencia de secuencias biológicas". Journal of Molecular Biology . 162 (3): 705– 708. CiteSeerX 10.1.1.204.203 . doi : 10.1016/0022-2836(82)90398-9 . PMID 7166760 .  
  3. 1 2 3 4 Stephen F. Altschul y Bruce W. Erickson (1986). "Alineación óptima de secuencias mediante costos de huecos afines". Boletín de Biología Matemática . 48 ( 5– 6): 603– 616. doi : 10.1007/BF02462326 . PMID 3580642 . S2CID 189889143 .  
  4. 1 2 3 Miller, Webb; Myers, Eugene (1988). "Alineaciones óptimas en el espacio lineal". Bioinformática . 4 (1): 11– 17. CiteSeerX 10.1.1.107.6989 . doi : 10.1093/bioinformatics/4.1.11 . PMID 3382986 .  
  5. ↑ Saul B. Needleman; Christian D. Wunsch (1970). "Un método general aplicable a la búsqueda de similitudes en la secuencia de aminoácidos de dos proteínas". Journal of Molecular Biology . 48 (3): 443– 453. doi : 10.1016/0022-2836(70)90057-4 . PMID 5420325 . 
  6. ↑ Sankoff D. (1972). "Secuencias coincidentes bajo restricciones de deleción/inserción" . Actas de la Academia Nacional de Ciencias de los Estados Unidos de América . 69 ( 1): 4– 6. Bibcode : 1972PNAS...69....4S . doi : 10.1073/pnas.69.1.4 . PMC 427531. PMID 4500555 .  
  7. ↑ Thomas A. Reichert; Donald N. Cohen; Andrew KC Wong (1973). "Una aplicación de la teoría de la información a las mutaciones genéticas y la correspondencia de secuencias polipeptídicas". Journal of Theoretical Biology . 42 (2): 245– 261. Bibcode : 1973JThBi..42..245R . doi : 10.1016/0022-5193(73)90088-X . PMID 4762954 . 
  8. ↑ William A. Beyer, Myron L. Stein, Temple F. Smith y Stanislaw M. Ulam (1974). "Una métrica de secuencia molecular y árboles evolutivos". Mathematical Biosciences . 19 ( 1–2 ): 9–25 . doi : 10.1016/0025-5564(74)90028-5 .{{cite journal}}: CS1 maint: varios nombres: lista de autores ( enlace )
  9. ↑ Peter H. Sellers (1974). "Sobre la teoría y el cálculo de distancias evolutivas". SIAM Journal on Applied Mathematics . 26 (4): 787– 793. doi : 10.1137/0126070 .
  10. ↑ MS Waterman; TF Smith; WA Beyer (1976). "Algunas métricas de secuencias biológicas" . Advances in Mathematics . 20 (3): 367– 387. doi : 10.1016/0001-8708(76)90202-4 .
  11. 1 2 3 Chowdhury, Rezaul; Le, Hai-Son; Ramachandran, Vijaya (julio de 2010). "Programación dinámica ajena a la caché para bioinformática". IEEE/ACM Transactions on Computational Biology and Bioinformatics . 7 (3): 495– 510. doi : 10.1109/TCBB.2008.94 . PMID 20671320 . S2CID 2532039 .  
  12. ↑ DS Hirschberg (1975). "Un algoritmo de espacio lineal para calcular subsecuencias comunes máximas". Communications of the ACM . 18 (6): 341– 343. CiteSeerX 10.1.1.348.4774 . doi : 10.1145/360825.360861 . S2CID 207694727 .  
  13. ↑ Wozniak, Andrzej (1997). "Uso de instrucciones orientadas a vídeo para acelerar la comparación de secuencias" . Computer Applications in the Biosciences . 13 (2): 145– 50. doi : 10.1093/bioinformatics/13.2.145 . PMID 9146961 . 
  14. 1 2 3 Farrar, Michael S. (2007). "Striped Smith–Waterman acelera las búsquedas en bases de datos seis veces en comparación con otras implementaciones SIMD" . Bioinformatics . 23 (2): 156– 161. doi : 10.1093/bioinformatics/btl582 . PMID 17110365 . 
  15. ↑ Zhao, Mengyao; Lee, Wan-Ping; Garrison, Erik P; Marth, Gabor T (4 de diciembre de 2013). "Biblioteca SSW: una biblioteca SIMD Smith-Waterman C/C++ para su uso en aplicaciones genómicas" . PLOS ONE . 8 (12) e82138. arXiv : 1208.6350 . Bibcode : 2013PLoSO...882138Z . doi : 10.1371/ journal.pone.0082138 . PMC 3852983. PMID 24324759 .  
  16. ↑ Documentos FPGA 100x: "Copia archivada" (PDF) . Archivado del original (PDF) el 5 de julio de 2008. Consultado el 17 de octubre de 2007 .{{cite web}}: CS1 maint: copia archivada como título ( enlace ) , "Copia archivada" (PDF) . Archivado del original (PDF) el 05-07-2008 . Recuperado el 17-10-2007 .{{cite web}}: CS1 maint: copia archivada como título ( enlace ) y "Copia archivada" (PDF) . Archivado del original (PDF) el 20/07/2011 . Recuperado el 17/10/2007 .{{cite web}}: CS1 mantenimiento: copia archivada como título ( enlace )
  17. ↑ Progeniq Pte. Ltd., " Libro blanco: aceleración de aplicaciones intensivas con un aumento de velocidad de 10 × a 50 × para eliminar cuellos de botella en flujos de trabajo computacionales ".
  18. ↑ Vermij, Erik (2011). Alineación de secuencias genéticas en una plataforma de supercomputación (PDF) (tesis de maestría). Universidad Tecnológica de Delft. Archivado del original (PDF) el 30 de septiembre de 2011. Consultado el 17 de agosto de 2011 .
  19. ↑ Liu, Yang; Huang, Wayne; Johnson, John; Vaidya, Sheila (2006). "GPU Accelerated Smith-Waterman" . Ciencia Computacional – ICCS 2006. Notas de clase en Ciencias de la Computación. Vol. 3994. Springer. pp. 188–195 . doi : 10.1007/11758549_29 . ISBN   978-3-540-34385-1.
  20. ↑ "Búsqueda y análisis de secuencias de alto rendimiento en bioinformática (documento técnico)" . GenomeQuest. Archivado del original el 13 de mayo de 2008. Consultado el 9 de mayo de 2008 .
  21. ↑ Manavski, Svetlin A. y Valle, Giorgio (2008). "Tarjetas GPU compatibles con CUDA como aceleradores de hardware eficientes para la alineación de secuencias de Smith-Waterman" . BMC Bioinformatics . 9 (Supl. 2:S10): S10. doi : 10.1186/1471-2105-9-S2-S10 . PMC 2323659. PMID 18387198 .  
  22. ↑ "Zona CUDA" . Nvidia . Consultado el 25 de febrero de 2010 .
  23. ↑ "NVIDIA Parabricks" . NVIDIA . Consultado el 11 de julio de 2024 .
  24. ↑ Rognes, Torbjørn; Seeberg, Erling (2000). "Aceleración de seis veces de las búsquedas en bases de datos de secuencias de Smith-Waterman mediante procesamiento paralelo en microprocesadores comunes" . Bioinformatics . 16 (8): 699–706 . doi : 10.1093/bioinformatics/16.8.699 . PMID 11099256 . {{cite journal}}: Enlace externo en |journal=( ayuda )
  25. ↑ Rognes, Torbjørn (2011). " Búsquedas más rápidas en bases de datos Smith-Waterman con paralelización SIMD entre secuencias" . BMC Bioinformatics . 12 221. doi : 10.1186/1471-2105-12-221 . PMC 3120707. PMID 21631914 .  
  26. ↑ Farrar, Michael S. (2008). "Optimización de Smith–Waterman para el motor de banda ancha celular" .{{cite journal}}: Cite journal requiere |journal=( ayuda ) CS1 maint: servicio de archivo obsoleto ( enlace )
  • JAligner : una implementación de código abierto en Java del algoritmo Smith-Waterman.
  • BABA — un applet (con código fuente) que explica visualmente el algoritmo.
  • FASTA/SSEARCH — página de servicios en el EBI
  • Complemento UGENE Smith–Waterman : una implementación de código abierto compatible con SSEARCH del algoritmo con interfaz gráfica escrita en C++.
  • OPAL : una biblioteca SIMD C/C++ para la alineación óptima de secuencias a gran escala.
  • diagonalsw — una implementación de código abierto en C/C++ con conjuntos de instrucciones SIMD (en particular SSE4.1) bajo la licencia MIT.
  • SSW — una biblioteca C++ de código abierto que proporciona una API para una implementación SIMD del algoritmo Smith-Waterman bajo la licencia MIT.
  • alineación de secuencias melódicas : una implementación en JavaScript para la alineación de secuencias melódicas.
  • DRAGMAP: Una versión en C++ de la implementación FPGA DRAGEN de Illumina.