Algoritmo de Smith-Waterman

Algoritmo para determinar regiones similares entre dos secuencias moleculares

El algoritmo Smith-Waterman realiza un alineamiento de secuencias local , es decir, determina regiones similares entre dos cadenas de secuencias de ácidos nucleicos o secuencias de proteínas . En lugar de observar la secuencia completa , el algoritmo 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, tiene la propiedad deseable de que está garantizado que encontrará la alineación local óptima con respecto al sistema de puntuación que se esté utilizando (que incluye la matriz de sustitución y el esquema de puntuación de brecha ). 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 rastreo comienza en la celda de la matriz de 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 de puntuación más alta. Debido a su complejidad de tiempo cúbico, a menudo no se puede aplicar prácticamente a problemas de gran escala y se reemplaza a 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 de homología heurística para la alineación de secuencias, también conocido como algoritmo Needleman-Wunsch. ^[5] Es un algoritmo de alineación global que requiere pasos de cálculo ( y son las longitudes de las dos secuencias que se alinean). Utiliza el cálculo iterativo de una matriz con el fin 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 de genes. Sellers introdujo un sistema para medir distancias de secuencias. ^[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. ${\displaystyle O(mn)}$ ${\displaystyle m}$ ${\displaystyle n}$

El algoritmo Smith-Waterman es bastante exigente en cuanto al tiempo: para alinear dos secuencias de longitudes y , se requiere tiempo. Gotoh ^[2] y Altschul ^[3] optimizaron el algoritmo a pasos. Myers y Miller ^[4] optimizaron la complejidad espacial de a (lineal), donde es la longitud de la secuencia más corta, para el caso en el que solo se desea una de las muchas alineaciones óptimas posibles. Chowdhury, Le y Ramachandran ^[11] luego optimizaron el rendimiento de la caché del algoritmo mientras mantenían el uso del espacio lineal en la longitud total de las secuencias de entrada. ${\displaystyle m}$ ${\displaystyle n}$ ${\displaystyle O(m^{2}n+n^{2}m)}$ ${\displaystyle O(mn)}$ ${\displaystyle O(mn)}$ ${\displaystyle O(n)}$ ${\displaystyle n}$

Motivación

En los últimos años, los proyectos genómicos realizados en una variedad de organismos generaron cantidades masivas de datos de secuencias de genes y proteínas, lo que requiere un análisis computacional. La alineación de secuencias muestra las relaciones entre genes o entre proteínas, lo que conduce a una mejor comprensión de su homología y funcionalidad. La alineación de secuencias también puede revelar dominios y motivos conservados .

Una de las motivaciones para la alineación local es la dificultad de obtener alineaciones correctas en regiones de baja similitud entre secuencias biológicas distantemente relacionadas, porque las mutaciones han añadido demasiado "ruido" a lo largo del tiempo evolutivo para permitir una comparación significativa de esas regiones. La alineación 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 prerrequisito para la alineación 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 brecha ) produciría para una secuencia aleatoria.

Otra motivación para utilizar alineaciones locales es que existe un modelo estadístico confiable (desarrollado por Karlin y Altschul) para alineaciones locales óptimas. La alineación de secuencias no relacionadas tiende a producir puntuaciones de alineación local óptimas que siguen una distribución de valores extremos. Esta propiedad permite que los programas produzcan un valor esperado para la alineación local óptima de dos secuencias, que es una medida de la frecuencia con la que dos secuencias no relacionadas producirían una alineación local óptima cuya puntuación es mayor o igual que la puntuación observada. Valores de expectativa 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 Smith-Waterman

Sean y las secuencias a alinear, donde y son las longitudes de y respectivamente. ${\displaystyle A=a_{1}a_{2}...a_{n}}$ ${\displaystyle B=b_{1}b_{2}...b_{m}}$ ${\displaystyle n}$ ${\displaystyle m}$ ${\displaystyle A}$ ${\displaystyle B}$

1. Determinar la matriz de sustitución y el esquema de penalización por brecha.
   • ${\displaystyle s(a,b)}$- Puntuación de similitud de los elementos que constituyen las dos secuencias
   • ${\displaystyle W_{k}}$- La penalización de un hueco que tiene longitud ${\displaystyle k}$
2. Construya una matriz de puntuación e inicialice su primera fila y primera columna. El tamaño de la matriz de puntuación es . La matriz utiliza una indexación basada en 0. ${\displaystyle H}$ ${\displaystyle (n+1)*(m+1)}$

   ${\displaystyle H_{k0}=H_{0l}=0\quad for\quad 0\leq k\leq n\quad and\quad 0\leq l\leq m}$

3. Llene la matriz de puntuación utilizando la siguiente ecuación.

   ${\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

   ${\displaystyle H_{i-1,j-1}+s(a_{i},b_{j})}$es la puntuación de alinear y , ${\displaystyle a_{i}}$ ${\displaystyle b_{j}}$

   ${\displaystyle H_{i-k,j}-W_{k}}$¿Es la puntuación si está al final de un espacio de longitud ? ${\displaystyle a_{i}}$ ${\displaystyle k}$

   ${\displaystyle H_{i,j-l}-W_{l}}$¿Es la puntuación si está al final de un espacio de longitud ? ${\displaystyle b_{j}}$ ${\displaystyle l}$

   ${\displaystyle 0}$significa que no hay similitud hasta y . ${\displaystyle a_{i}}$ ${\displaystyle b_{j}}$

4. Rastreo. Comenzando por el puntaje más alto en la matriz de puntaje y terminando en una celda de la matriz que tiene un puntaje de 0, se realiza un rastreo recursivo en función de la fuente de cada puntaje para generar la mejor alineación local. ${\displaystyle H}$

Explicación

El algoritmo Smith-Waterman alinea dos secuencias mediante coincidencias o desajustes (también conocidos como sustituciones), inserciones y eliminaciones. Tanto las inserciones como las eliminaciones son operaciones que introducen espacios vacíos, que se representan mediante guiones. El algoritmo Smith-Waterman consta de varios pasos:

1. Determinar la matriz de sustitución y el esquema de penalización por brecha . Una matriz de sustitución asigna a cada par de bases o aminoácidos una puntuación por coincidencia o desajuste. Por lo general, las coincidencias obtienen puntuaciones positivas, mientras que las desajustes obtienen puntuaciones relativamente más bajas. Una función de penalización por brecha determina el costo de puntuación por abrir o extender brechas. Se sugiere que los usuarios elijan el sistema de puntuación adecuado en función de los objetivos. Además, también es una buena práctica probar diferentes combinaciones de matrices de sustitución y penalizaciones por brecha.
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 primera fila y la primera columna adicionales permiten alinear una secuencia con otra en cualquier posición y, al establecerlas en 0, el espacio terminal queda libre de penalizaciones.
3. Puntuación . Califique cada elemento de izquierda a derecha y de arriba hacia abajo en la matriz, teniendo en cuenta los resultados de las sustituciones (puntuaciones diagonales) o la adición de espacios (puntuaciones horizontales y verticales). Si ninguna de las puntuaciones es positiva, este elemento obtiene un 0. De lo contrario, se utiliza la puntuación más alta y se registra la fuente de esa puntuación.
4. Rastreo . Comenzando por el elemento con la puntuación más alta, se realiza un rastreo recursivo en función de la fuente de cada puntuación hasta llegar a 0. En este proceso se generan los segmentos que tienen 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 por la segunda puntuación más alta fuera del rastreo de la mejor alineación.

Comparación con el algoritmo Needleman-Wunsch

Alineación de secuencias globales y locales

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

Una de las distinciones más importantes es que no se asigna ninguna puntuación negativa en el sistema de puntuación del algoritmo Smith-Waterman, lo que permite la alineación local. Cuando cualquier elemento tiene una puntuación inferior a cero, significa que las secuencias hasta esa posición no tienen similitudes; ese elemento se pondrá entonces a cero para eliminar la influencia de la alineación anterior. De esta manera, el cálculo puede continuar para encontrar la alineación en cualquier posición posteriormente.

La matriz de puntuación inicial del algoritmo Smith-Waterman permite la alineación de cualquier segmento de una secuencia con una posición arbitraria en la otra secuencia. Sin embargo, en el algoritmo Needleman-Wunsch, también se debe considerar la penalización por espacio 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 asigna una puntuación positiva y a las discordancias se les asigna una puntuación relativamente más baja. Tomemos como ejemplo la secuencia de ADN. Si las coincidencias obtienen +1, las discordancias obtienen -1, entonces la matriz de sustitución es:

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

Diferentes sustituciones de bases o de aminoácidos pueden tener diferentes puntuaciones. La matriz de sustitución de aminoácidos suele ser más complicada 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 sencilla de penalización por hueco es utilizar una puntuación fija para cada hueco. Sin embargo, en biología, la puntuación debe contarse de forma diferente por razones prácticas. Por un lado, la similitud parcial entre dos secuencias es un fenómeno común; por otro lado, un único evento de mutación genética puede dar lugar a la inserción de un único hueco largo. Por lo tanto, los huecos conectados que forman un hueco largo suelen ser más favorecidos que los 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 superior a la puntuación 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. Sea la función de penalización por brecha para una brecha de longitud : ${\displaystyle W_{k}}$ ${\displaystyle k}$

Lineal

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

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

${\displaystyle W_{k}=kW_{1}}$,

¿Dónde está el costo de un solo espacio? ${\displaystyle W_{1}}$

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

${\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 utiliza pasos. Cuando se puntúa un elemento, solo se deben tener en cuenta las penalizaciones por espacios de los elementos que están directamente adyacentes a este elemento. ${\displaystyle O(mn)}$

Afín

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

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

donde es la penalización por apertura de hueco y es la penalización por extensión de hueco. Por ejemplo, la penalización por un hueco de longitud 2 es . ${\displaystyle v}$ ${\displaystyle u}$ ${\displaystyle 2u+v}$

En el artículo original sobre el algoritmo Smith-Waterman se utilizó una penalización por brecha arbitraria. Utiliza pasos, por lo tanto, es bastante exigente en cuanto a tiempo. Gotoh optimizó los pasos para una penalización por brecha afín a , ^[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] Más tarde, Myers y Miller señalaron que el algoritmo de Gotoh y Altschul se puede modificar aún más según 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 utilizando el espacio, siendo la longitud de la secuencia más corta. Chowdhury, Le y Ramachandran ^[11] mostraron más tarde cómo ejecutar el algoritmo de Gotoh de manera eficiente en caché en el espacio lineal utilizando una estrategia recursiva de dividir y vencer 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] ${\displaystyle O(m^{2}n)}$ ${\displaystyle O(mn)}$ ${\displaystyle O(n)}$ ${\displaystyle n}$

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 por brecha 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 la extensión de la brecha son 0,0 y 1,0 respectivamente):

TACGGGCCCGCTA-CTA---G-CC-CTATC

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

TACGGGCCCGCTATA---CCG--CTA

Este ejemplo muestra que una penalización por espacio afín puede ayudar a evitar pequeños espacios 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 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 creciente. En otras palabras, la alineación óptima actual se genera al decidir qué camino (coincidencia/discordancia o inserción de espacio) brinda 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 en la otra secuencia. Tanto la primera línea como la primera columna se establecen en 0 para que el espacio final no se penalice. 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: ${\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 espacio: (una penalización por espacio lineal de ) ${\displaystyle W_{k}=2k}$ ${\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 primeros tres elementos. El color amarillo indica las bases que se están considerando. El color rojo indica la puntuación más alta 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 primeros tres elementos (izquierda 2–4)

La matriz de puntuación finalizada se muestra a continuación a la izquierda. El color azul muestra 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 rastrea este elemento. En caso de múltiples puntuaciones más altas, el rastreo debe realizarse comenzando con cada puntuación más alta. El proceso de rastreo se muestra a continuación a la derecha. La mejor alineación local se genera en la dirección inversa.

El resultado de la alineación es:

GTT - AC GTTGAC 

Implementación

Una implementación del algoritmo Smith-Waterman, SSEARCH, está disponible en el paquete de análisis de secuencias FASTA de UVA FASTA Downloads. Esta implementación incluye código acelerado de Altivec para procesadores PowerPC G4 y G5 que acelera las comparaciones entre 10 y 20 veces, utilizando una modificación del enfoque 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 informática reconfigurable basada en chips FPGA , con resultados que muestran una aceleración de hasta 28x sobre las soluciones basadas en microprocesadores estándar. Otra versión basada en FPGA del algoritmo Smith-Waterman muestra aceleraciones de FPGA (Virtex-4) de hasta 100x ^[16] sobre 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, Código OpenCL compilado con Xilinx SDAccel acelera la secuenciación del genoma, supera el rendimiento de CPU/GPU/W en 12-21x, se presentó una implementación muy eficiente. Al utilizar una tarjeta FPGA PCIe equipada con un FPGA Xilinx Virtex-7 2000T, el nivel de rendimiento por vatio fue 12-21x mejor que el de CPU/GPU.

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 alineamiento de secuencias locales de Smith-Waterman utilizando unidades de procesamiento gráfico (GPU) con resultados preliminares que muestran una aceleración dos veces mayor que las implementaciones de software. ^[19] Ya se ha implementado un método similar en el software Biofacet desde 1997, con el mismo factor de aceleración. ^[20]

También están disponibles varias implementaciones de GPU del algoritmo en la plataforma CUDA C de NVIDIA . ^[21] En comparación con la implementación de CPU más conocida (que utiliza instrucciones SIMD en la arquitectura x86), de Farrar, las pruebas de rendimiento de esta solución utilizando 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 en el rendimiento para secuencias más grandes. Sin embargo, las mismas pruebas que se ejecutan en tarjetas duales 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.

Ahora está disponible una implementación más reciente de GPU CUDA de SW que es más rápida que las versiones anteriores y también elimina las limitaciones en las longitudes de consulta. Consulte CUDASW++.

Se han informado once implementaciones de SW diferentes en CUDA, tres de las cuales informan aceleraciones de 30X. ^[22]

Por último, se pueden encontrar otras implementaciones aceleradas por GPU del Smith-Waterman en NVIDIA Parabricks , la suite de software de NVIDIA para el análisis del genoma. ^[23]

SIMD

En 2000, Rognes y Seeberg describieron en una publicación una implementación rápida del algoritmo Smith-Waterman utilizando la tecnología SIMD ( instrucción única, múltiples datos ) 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 que cubre este enfoque. Sencel está desarrollando aún más el software y proporciona ejecutables para uso académico de forma gratuita.

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] Cuando se ejecuta 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 similitudes del Instituto Europeo de Bioinformática .

La empresa danesa de bioinformática CLC bio ha logrado aceleraciones cercanas a 200 veces con respecto a las implementaciones de software estándar con 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, en servidores Linux basados ​​en Intel y Advanced Micro Devices (AMD) , es compatible con el paquete GenCore 6, ofrecido por Biocceleration. Los puntos de referencia de rendimiento de este paquete de software muestran una aceleración de velocidad hasta diez veces mayor que la implementación de software estándar en el mismo procesador.

Actualmente, la única empresa en bioinformática que ofrece soluciones SSE y FPGA que aceleran Smith–Waterman, CLC bio ha logrado aceleraciones de más de 110 veces con respecto a las implementaciones de software estándar con CLC Bioinformatics Cube. ^{[ cita requerida ]}

La implementación más rápida del algoritmo en CPUs con SSSE3 se puede encontrar en el software SWIPE (Rognes, 2011), ^[25] que está disponible bajo la Licencia Pública General Affero de GNU . En paralelo, este software compara residuos de dieciséis secuencias de bases de datos diferentes con un residuo de consulta. Usando 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 con procesador dual Intel Xeon X5650 de seis núcleos, 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 usa la matriz BLOSUM50.

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

Motor de banda ancha celular

En 2008, Farrar ^[26] describió un puerto del Striped Smith–Waterman ^[14] para el Cell Broadband Engine y reportó velocidades de 32 y 12 GCUPS en un 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 alineamiento de secuencias de ADN. Las necesidades esenciales de un método eficiente y preciso para el descubrimiento de variantes de ADN exigen enfoques innovadores para el procesamiento paralelo en tiempo real.

Véase también

• Bioinformática
• Alineación de secuencias
• Minería de secuencias
• Algoritmo de Needleman-Wunsch
• Distancia de Levenshtein
• EXPLOSIÓN
• Rápido

Referencias

1. Smith, Temple F. y Waterman, Michael S. (1981). "Identificación de subsecuencias moleculares comunes" (PDF) . Revista de biología molecular . 147 (1): 195–197. CiteSeerX  10.1.1.63.2897 . doi :10.1016/0022-2836(81)90087-5. PMID  7265238.
2. Osamu Gotoh (1982). "Un algoritmo mejorado para la correspondencia de secuencias biológicas". Revista de biología molecular . 162 (3): 705–708. CiteSeerX 10.1.1.204.203 . doi :10.1016/0022-2836(82)90398-9. PMID  7166760. 
3. Stephen F. Altschul y Bruce W. Erickson (1986). "Alineamiento óptimo de secuencias utilizando costos de brecha afín". Boletín de biología matemática . 48 (5–6): 603–616. doi :10.1007/BF02462326. PMID  3580642. S2CID  189889143.
4. 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). "Matching Sequences under Deletion/Inserts" (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". Ciencias biológicas matemáticas . 19 (1–2): 9–25. doi :10.1016/0025-5564(74)90028-5.{{cite journal}}: CS1 maint: multiple names: authors list (link)
9. Peter H. Sellers (1974). "Sobre la teoría y el cálculo de las distancias evolutivas". Revista SIAM de Matemáticas Aplicadas . 26 (4): 787–793. doi :10.1137/0126070.
10. MS Waterman; TF Smith; WA Beyer (1976). "Algunas métricas de secuencias biológicas". Avances en Matemáticas . 20 (3): 367–387. doi : 10.1016/0001-8708(76)90202-4 .
11. Chowdhury, Rezaul; Le, Hai-Son; Ramachandran, Vijaya (julio de 2010). "Programación dinámica sin caché para bioinformática". Transacciones IEEE/ACM sobre biología computacional y bioinformática . 7 (3): 495–510. doi :10.1109/TCBB.2008.94. PMID  20671320. S2CID  2532039.
12. DS Hirschberg (1975). "Un algoritmo espacial lineal para calcular subsecuencias comunes máximas". Comunicaciones de la 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 video para acelerar la comparación de secuencias". Aplicaciones informáticas en las biociencias . 13 (2): 145–50. doi : 10.1093/bioinformatics/13.2.145 . PMID  9146961.
14. Farrar, Michael S. (2007). "Striped Smith–Waterman acelera las búsquedas en bases de datos seis veces más que otras implementaciones de SIMD". Bioinformática . 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 desde el original (PDF) el 5 de julio de 2008. Consultado el 17 de octubre de 2007 .{{cite web}}: CS1 maint: archived copy as title (link), "Copia archivada" (PDF) . Archivado desde el original (PDF) el 5 de julio de 2008. Consultado el 17 de octubre de 2007 .{{cite web}}: CS1 maint: archived copy as title (link), y "Copia archivada" (PDF) . Archivado desde el original (PDF) el 20 de julio de 2011. Consultado el 17 de octubre de 2007 .{{cite web}}: CS1 maint: archived copy as title (link)
17. Progeniq Pte. Ltd., "Libro blanco: Aceleración de aplicaciones intensivas a una velocidad de 10×–50× para eliminar cuellos de botella en flujos de trabajo computacionales".
18. Vermij, Erik (2011). Alineamiento de secuencias genéticas en una plataforma de supercomputación (PDF) (tesis de maestría). Universidad Tecnológica de Delft. Archivado desde el original (PDF) el 2011-09-30 . Consultado el 2011-08-17 .
19. Liu, Yang; Huang, Wayne; Johnson, John; Vaidya, Sheila (2006). "Smith-Waterman acelerado por GPU". Computational Science – ICCS 2006 . Apuntes de clase en informática. Vol. 3994. Springer. págs. 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 (informe técnico)". GenomeQuest. Archivado desde el 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 Smith–Waterman". BMC Bioinformatics . 9 (Suppl 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 Smith-Waterman mediante procesamiento paralelo en microprocesadores comunes". Bioinformática . 16 (8): 699–706. doi : 10.1093/bioinformatics/16.8.699 . PMID  11099256.
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". Archivado desde el original el 12 de febrero de 2012. {{cite journal}}: Requiere citar revista |journal=( ayuda )

Enlaces externos

• JAligner: una implementación Java de código abierto del algoritmo Smith-Waterman
• BABA: una aplicación (con código fuente) que explica visualmente el algoritmo
• FASTA/SSEARCH — página de servicios en EBI
• Complemento Smith–Waterman de UGENE: una implementación del algoritmo compatible con SSEARCH de código abierto con una interfaz gráfica escrita en C++
• OPAL: una biblioteca SIMD C/C++ para la alineación masiva de secuencias óptimas
• diagonalsw: una implementación de C/C++ de código abierto 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 de JavaScript para la alineación de secuencias melódicas
• DRAGMAP Un puerto C++ de la implementación del FPGA DRAGEN de Illumina