Algoritmo de Smith-Waterman

Algoritmo para determinar regiones similares entre dos secuencias moleculares

El algoritmo de Smith-Waterman realiza una alineación de secuencia local ; es decir, para determinar regiones similares entre dos cadenas de secuencias de ácidos nucleicos o secuencias de proteínas . En lugar de observar 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, tiene la propiedad deseable de que se garantiza encontrar la alineación local óptima con respecto al sistema de puntuación que se utiliza (que incluye la matriz de sustitución y el esquema de puntuación de brechas ). La principal diferencia con el algoritmo Needleman-Wunsch es que las celdas de la matriz de puntuación negativa se establecen en cero, lo que hace visibles las alineaciones locales (por lo tanto, con puntuación positiva). ^[2] El procedimiento de rastreo comienza en la celda de la matriz con la puntuación más alta y continúa hasta encontrar una celda con puntuación cero, lo que produce la alineación local con la puntuación más alta. Debido a su complejidad de tiempo cúbico, a menudo no se puede aplicar en la práctica a problemas de gran escala y se reemplaza a favor de alternativas computacionalmente más eficientes como (Gotoh, 1982), ^[3] ( Altschul y Erickson, 1986), ^[4] y (Myers y Miller, 1988). ^[5]

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. ^[6] 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, ^[7] Reichert, ^[8] Beyer ^[9] y otros formularon algoritmos heurísticos alternativos para analizar secuencias de genes. Los vendedores introdujeron un sistema para medir distancias de secuencia. ^[10] En 1976, Waterman et al. añadió el concepto de brechas al sistema de medición original. ^[11] 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 de Smith-Waterman requiere bastante tiempo: para alinear dos secuencias de longitudes y , se requiere tiempo. Gotoh ^[3] y Altschul ^[4] optimizaron el algoritmo en pasos. La complejidad del espacio fue optimizada por Myers y Miller ^[5] desde 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 ^[12] optimizaron posteriormente el rendimiento de la caché del algoritmo manteniendo lineal el uso del espacio en la longitud total de las secuencias de entrada. ${\displaystyle m}$ ${\displaystyle n}$ ${\displaystyle O(m^{2}n)}$ ${\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 análisis computacional. El alineamiento de secuencias muestra las relaciones entre genes o entre proteínas, lo que lleva 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 motivación para el alineamiento local es la dificultad de obtener alineamientos correctos en regiones de baja similitud entre secuencias biológicas relacionadas lejanamente, porque las mutaciones han agregado demasiado "ruido" a lo largo del tiempo evolutivo para permitir una comparación significativa de esas regiones. La alineación local evita dichas regiones por completo y se centra en aquellas con una puntuación positiva, es decir, aquellas con una señal de similitud evolutivamente conservada. Un requisito previo para la alineación local es una puntuación de expectativas negativa. La puntuación esperada se define como la puntuación media que el sistema de puntuación ( matriz de sustitución y penalizaciones por brecha ) arrojaría para una secuencia aleatoria.

Otra motivación para utilizar alineamientos locales es que existe un modelo estadístico confiable (desarrollado por Karlin y Altschul) para alineamientos locales óptimos. 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 a los programas producir un valor esperado para el alineamiento local óptimo de dos secuencias, que es una medida de la frecuencia con la que dos secuencias no relacionadas producirían un alineamiento local óptimo cuya puntuación es mayor o igual a la puntuación observada. Los 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

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. Determine 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 constituyeron las dos secuencias.
   • ${\displaystyle W_{k}}$- La pena de un hueco que tiene longitud ${\displaystyle k}$
2. Construya una matriz de puntuación e inicialice su primera fila y su primera columna. El tamaño de la matriz de puntuación es . La matriz utiliza 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. Complete la matriz de puntuación usando 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. Rastrear. Comenzando en la puntuación más alta en la matriz de puntuación y terminando en una celda de la matriz que tiene una puntuación de 0, el rastreo se basa en la fuente de cada puntuación de forma recursiva para generar la mejor alineación local. ${\displaystyle H}$

Explicación

El algoritmo de Smith-Waterman alinea dos secuencias mediante coincidencias/desajustes (también conocidas como sustituciones), inserciones y eliminaciones. Tanto las inserciones como las eliminaciones son operaciones que introducen espacios, que se representan mediante guiones. El algoritmo de 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 de coincidencia o no coincidencia. Por lo general, los coincidencias obtienen puntuaciones positivas, mientras que los desajustes obtienen puntuaciones relativamente más bajas. Una función de penalización de brechas determina el costo de puntuación por abrir o ampliar 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+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 establecerlas en 0 hace que el espacio del terminal esté libre de penalizaciones.
3. Puntuación . Califique cada elemento de izquierda a derecha, de arriba a abajo en la matriz, considerando los resultados de las sustituciones (puntuaciones diagonales) o sumando 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. Rastrear . Comenzando en el elemento con la puntuación más alta, realice un seguimiento basado en la fuente de cada puntuación de forma recursiva, hasta encontrar 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, aplique el proceso de rastreo comenzando en la segunda puntuación más alta fuera del rastro de la mejor alineación.

Comparación con el algoritmo Needleman-Wunsch

Alineación de secuencia global y local.

El algoritmo de Smith-Waterman encuentra los segmentos de dos secuencias que tienen similitudes, mientras que el algoritmo de Needleman-Wunsch alinea dos secuencias completas. Por lo tanto, tienen diferentes propósitos. Ambos algoritmos utilizan los conceptos de matriz de sustitución, función de penalización de brecha, matriz de puntuación y proceso de rastreo. 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 algún elemento tiene una puntuación inferior a cero, significa que las secuencias hasta esa posición no tienen similitudes; este elemento luego se establecerá en cero para eliminar la influencia de la alineación anterior. De esta manera, el cálculo puede continuar encontrando alineación en cualquier posición posteriormente.

La matriz de puntuación inicial del algoritmo de 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 es necesario considerar la penalización del espacio final para alinear las secuencias completas.

Matriz de sustitución

A cada sustitución de base o sustitución de aminoácidos se le asigna una puntuación. En general, a los partidos se les asignan puntuaciones positivas y a los desajustes se les asignan puntuaciones relativamente más bajas. Tomemos como ejemplo la secuencia de ADN. Si las coincidencias obtienen +1 y las discrepancias 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 sustituciones de aminoácidos pueden tener puntuaciones diferentes. La matriz de sustitución de los aminoácidos suele ser más complicada que la de las bases. Ver PAM , BLOSUM .

Penalización por brecha

La penalización por espacio designa puntuaciones por inserción o eliminación. Una estrategia simple de penalización por brecha es utilizar una puntuación fija para cada brecha. En biología, sin embargo, 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 evento de mutación de un solo gen puede resultar en la inserción de un único espacio largo. Por lo tanto, las brechas conectadas que forman una brecha larga generalmente son más favorecidas que múltiples brechas cortas y dispersas. Para tener en cuenta esta diferencia, se han añadido al sistema de puntuación los conceptos de apertura y ampliación de huecos. La puntuación de apertura de la brecha suele ser más alta que la puntuación de la extensión de la brecha. Por ejemplo, los parámetros predeterminados en EMBOSS Water son: apertura del espacio = 10, extensión del espacio = 0,5.

Aquí analizamos dos estrategias comunes para la penalización por brecha. Consulte Penalización por brecha para conocer más estrategias. Sea la función de penalización de espacio para un espacio de longitud : ${\displaystyle W_{k}}$ ${\displaystyle k}$

Lineal

Algoritmo simplificado de Smith-Waterman cuando se utiliza la función de penalización de espacio lineal

Una penalización de brecha lineal tiene los mismos puntajes por abrir y extender una brecha:

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

¿Dónde está el costo de una sola brecha? ${\displaystyle W_{1}}$

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

${\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, sólo se deben considerar las penalizaciones por espacio de los elementos que están directamente adyacentes a este elemento. ${\displaystyle O(mn)}$

afín

Una penalización de brecha afín considera la apertura y 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 brecha y es la penalización por extensión de brecha. Por ejemplo, la penalización por un espacio de longitud 2 es . ${\displaystyle v}$ ${\displaystyle u}$ ${\displaystyle 2u+v}$

En el artículo original sobre el algoritmo de Smith-Waterman se utilizó una penalización de brecha arbitraria. Utiliza pasos, por lo que requiere bastante tiempo. Gotoh optimizó los pasos para una penalización de espacio afín para , ^[3] pero el algoritmo optimizado solo intenta encontrar una alineación óptima, y ​​no se garantiza que se encuentre la alineación óptima. ^[4] Altschul modificó el algoritmo de Gotoh para encontrar todas las alineaciones óptimas manteniendo la complejidad computacional. ^[4] Más tarde, 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, ^[13] y aplicaron este método. ^[5] El algoritmo de Myers y Miller puede alinear dos secuencias usando el espacio, siendo la longitud de la secuencia más corta. Chowdhury, Le y Ramachandran ^[12] mostraron más tarde 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. ^[12] ${\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 TACGGCCCGCTAC y TAGCCTATCGGTCA . Cuando se utiliza la función de penalización de espacio 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 del espacio son 0,0 y 1,0 respectivamente):

TACGGGCCCGCTA-CTA---G-CC-CTATC

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

TACGGGCCCGCTATA---CCG--CTA

Este ejemplo muestra que una penalización de brecha afín puede ayudar a evitar pequeñas brechas dispersas.

Matriz de puntuación

La función de la matriz de puntuación es realizar comparaciones uno a uno entre todos los componentes en dos secuencias y registrar los resultados de alineación óptimos. 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é ruta (coincidencia/desadaptación o inserción de espacio) da 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 línea como la primera columna se establecen en 0 para que el espacio final no se vea penalizado. 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 brecha: (una penalización por brecha 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 tres primeros 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á puntuando.

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 terminada 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á un camino diferente si se rastrea este elemento. En caso de que haya varias puntuaciones más altas, el rastreo se debe realizar 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 secuencia FASTA de UVA FASTA Downloads. Esta implementación incluye código acelerado 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 ^[14] y una vectorización SSE2 desarrollada por Farrar ^{[15] que crea} una base de datos de secuencias de proteínas óptima . búsquedas bastante prácticas. Una biblioteca, SSW, amplía la implementación de Farrar para devolver información de alineación además de la puntuación óptima de Smith-Waterman. ^[dieciséis]

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 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 FPGA (Virtex-4) de hasta 100 veces ^[17] en un procesador Opteron de 2,2 GHz. ^[18] Los sistemas TimeLogic DeCypher y CodeQuest también aceleran Smith-Waterman y Framesearch utilizando tarjetas PCIe FPGA.

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

En una publicación de 2016, el código OpenCL compilado con Xilinx SDAccel acelera la secuenciación del genoma, supera el rendimiento de CPU/GPU/W entre 12 y 21 veces, y se presentó una implementación muy eficiente. Usando una tarjeta PCIe FPGA equipada con una FPGA Xilinx Virtex-7 2000T, el rendimiento por nivel de vatio fue mejor que el de 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 implementaron una versión acelerada de las búsquedas de alineación de secuencia local Smith-Waterman utilizando unidades de procesamiento de gráficos (GPU) con resultados preliminares que muestran una velocidad dos veces mayor que las implementaciones de software. ^[20] Un método similar ya se ha implementado en el software Biofacet desde 1997, con el mismo factor de aceleración. ^[21]

También están disponibles varias implementaciones de GPU del algoritmo en la plataforma CUDA C de NVIDIA . ^[22] En comparación con la implementación de CPU más conocida (que utiliza instrucciones SIMD en la arquitectura x86), realizada por 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 un Ligera disminución en el rendimiento para los más grandes. Sin embargo, las mismas pruebas ejecutadas 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 GPU CUDA de SW más nueva que es más rápida que las versiones anteriores y también elimina las limitaciones en la longitud de las consultas. Ver CUDASW++.

Se han reportado once implementaciones de SW diferentes en CUDA, tres de las cuales reportan aceleraciones de 30X. ^[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 de instrucción única, datos múltiples ( SIMD ) disponible en los procesadores Intel Pentium MMX y tecnología similar. ^[24] En contraste con el enfoque de Wozniak (1997), la nueva implementación se basó 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.

Actualmente 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. ^[15] Cuando se ejecuta en un procesador Intel utilizando la microarquitectura Core, la implementación SSE2 logra un aumento de 20 veces. La implementación SSE2 de Farrar está disponible como 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 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. Las pruebas de rendimiento de este paquete de software muestran una aceleración de hasta 10 veces la velocidad en relación con la implementación de software estándar en el mismo procesador.

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

La implementación más rápida del algoritmo en CPU con SSSE3 se puede encontrar en el software SWIPE (Rognes, 2011), ^[25] que está disponible bajo la Licencia Pública General GNU Affero . 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 celda por segundo (GCUPS) en un sistema de 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 "seccionado" de Farrar. Es más rápido que BLAST cuando se utiliza 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ó una adaptación del sistema Stripe Smith-Waterman ^[15] al Cell Broadband Engine e informó 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 desafía la velocidad de los algoritmos actuales de alineación 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.

Ver también

• Bioinformática
• Alineación de secuencia
• Minería de secuencias
• Algoritmo de Needleman-Wunsch
• distancia de Levenshtein
• EXPLOSIÓN
• FASTA

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. Gagniuc, Paul A. (2021). Algoritmos en bioinformática: teoría e implementación (1ª ed.). Hoboken, Nueva Jersey: John Wiley & Sons. págs. 1–528. ISBN 978-1-119-69800-5. OCLC  1240827446.
3. Osamu Gotoh (1982). "Un algoritmo mejorado para hacer coincidir 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. 
4. Stephen F. Altschul y Bruce W. Erickson (1986). "Alineación de secuencia óptima utilizando costos de brecha afines". Boletín de Biología Matemática . 48 (5–6): 603–616. doi :10.1007/BF02462326. PMID  3580642. S2CID  189889143.
5. Miller, Webb; Myers, Eugenio (1988). "Alineaciones óptimas en el espacio lineal". Bioinformática . 4 (1): 11-17. CiteSeerX 10.1.1.107.6989 . doi :10.1093/bioinformática/4.1.11. PMID  3382986. 
6. Saúl 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". Revista de biología molecular . 48 (3): 443–453. doi :10.1016/0022-2836(70)90057-4. PMID  5420325.
7. Sankoff D. (1972). "Coincidencia de secuencias bajo restricciones de eliminación/inserción". Actas de la Academia Nacional de Ciencias de los Estados Unidos de América . 69 (1): 4–6. Código bibliográfico : 1972PNAS...69....4S. doi : 10.1073/pnas.69.1.4 . PMC 427531 . PMID  4500555. 
8. 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 coincidencia de secuencias polipeptídicas". Revista de Biología Teórica . 42 (2): 245–261. Código Bib : 1973JThBi..42..245R. doi :10.1016/0022-5193(73)90088-X. PMID  4762954.
9. William A. Beyer, Myron L. Stein, Temple F. Smith y Stanislaw M. Ulam (1974). "Una secuencia molecular métrica y árboles evolutivos". Biociencias Matemáticas . 19 (1–2): 9–25. doi :10.1016/0025-5564(74)90028-5.{{cite journal}}: Mantenimiento CS1: varios nombres: lista de autores ( enlace )
10. Peter H. Vendedores (1974). "Sobre la teoría y el cálculo de distancias evolutivas". Revista de Matemáticas Aplicadas . 26 (4): 787–793. doi :10.1137/0126070.
11. MS Waterman; TF Smith; WA Beyer (1976). "Algunas métricas de secuencia biológica". Avances en Matemáticas . 20 (3): 367–387. doi : 10.1016/0001-8708(76)90202-4 .
12. Chowdhury, Rezaul; Le, Hai-Son; Ramachandran, Vijaya (julio de 2010). "Programación dinámica sin memoria 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.
13. DS Hirschberg (1975). "Un algoritmo de espacio 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. 
14. Wozniak, Andrzej (1997). "Uso de instrucciones orientadas a vídeo para acelerar la comparación de secuencias". Aplicaciones Informáticas en las Biociencias . 13 (2): 145–50. doi : 10.1093/bioinformática/13.2.145 . PMID  9146961.
15. Farrar, Michael S. (2007). "Striped Smith-Waterman acelera las búsquedas en la base de datos seis veces más que otras implementaciones SIMD". Bioinformática . 23 (2): 156-161. doi : 10.1093/bioinformática/btl582 . PMID  17110365.
16. 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 uso en aplicaciones genómicas". MÁS UNO . 8 (12): e82138. arXiv : 1208.6350 . Código Bib : 2013PLoSO...882138Z. doi : 10.1371/journal.pone.0082138 . PMC 3852983 . PMID  24324759. 
17. 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}}: Mantenimiento CS1: copia archivada como título ( enlace ), "Copia archivada" (PDF) . Archivado desde el original (PDF) el 5 de julio de 2008 . Consultado el 17 de octubre de 2007 .{{cite web}}: Mantenimiento CS1: copia archivada como título ( enlace )y "Copia archivada" (PDF) . Archivado desde el original (PDF) el 20 de julio de 2011 . Consultado el 17 de octubre de 2007 .{{cite web}}: Mantenimiento CS1: copia archivada como título ( enlace )
18. Progeniq Pte. Limitado. Ltd., "Informe técnico: Aceleración de aplicaciones intensivas a una velocidad de 10 × –50 × para eliminar cuellos de botella en los flujos de trabajo computacionales".
19. 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 desde el original (PDF) el 30 de septiembre de 2011 . Consultado el 17 de agosto de 2011 .
20. Liu, Yang; Huang, Wayne; Johnson, Juan; Vaidya, Sheila (2006). "Smith-Waterman acelerado por GPU". Ciencias Computacionales – ICCS 2006 . Apuntes de conferencias sobre informática. vol. 3994. Saltador. págs. 188-195. doi :10.1007/11758549_29. ISBN 978-3-540-34385-1.
21. "Búsqueda y análisis de secuencias de alto rendimiento en bioinformática (documento técnico)". Búsqueda del genoma. Archivado desde el original el 13 de mayo de 2008 . Consultado el 9 de mayo de 2008 .
22. 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". Bioinformática BMC . 9 (Suplemento 2: S10): S10. doi : 10.1186/1471-2105-9-S2-S10 . PMC 2323659 . PMID  18387198. 
23. "Zona CUDA". NVIDIA . Consultado el 25 de febrero de 2010 .
24. Rognes, Torbjørn; Seeberg, Erling (2000). "Aceleración seis veces mayor de las búsquedas en la base de datos de secuencias de Smith-Waterman mediante procesamiento paralelo en microprocesadores comunes". Bioinformática . 16 (8): 699–706. doi : 10.1093/bioinformática/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". Bioinformática BMC . 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}}: Citar diario requiere |journal=( ayuda )

enlaces externos

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