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 .
Clase | Alineación de secuencia |
---|---|
Rendimiento en el peor de los casos | |
Complejidad espacial en el peor de los casos |
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 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 brechas ). La principal diferencia con el algoritmo de 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, las puntuaciones positivas). El procedimiento de rastreo comienza en la celda de 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 cuadrática en el tiempo y el espacio, a menudo no se puede aplicar prácticamente a problemas a gran escala y se reemplaza a favor de alternativas menos generales pero 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 denominado algoritmo de 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. Los vendedores introdujeron un sistema para medir distancias de secuencia. [9] En 1976, Waterman et al. agregó el concepto de brechas en el 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 longitudes y , se requiere tiempo. Gotoh [2] y Altschul [3] optimizaron el algoritmo parapasos. La complejidad del espacio fue optimizada por Myers y Miller [4] desde a (lineal), donde es la longitud de la secuencia más corta, para el caso en el que sólo se desee una de las muchas alineaciones óptimas posibles.
Motivación
En los últimos años, los proyectos de genoma realizados en una variedad de organismos generaron cantidades masivas de datos de secuencia de genes y proteínas, lo que requiere un análisis computacional. El alineamiento 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 motivación para la alineación local es la dificultad de obtener alineaciones correctas en regiones de baja similitud entre secuencias biológicas relacionadas lejanamente, porque las mutaciones han agregado demasiado "ruido" durante el tiempo evolutivo para permitir una comparación significativa de esas regiones. La alineación local evita tales regiones por completo 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 la alineación local es una puntuación de expectativa negativa. El puntaje de expectativa se define como el puntaje promedio que el sistema de puntaje ( matriz de sustitución y penalizaciones por brecha ) produciría para una secuencia aleatoria.
Otra motivación para usar 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 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. Los 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
Dejar y ser las secuencias a alinear, donde y son las longitudes de y respectivamente.
- Determine la matriz de sustitución y el esquema de penalización por brecha.
- - Puntuación de similitud de los elementos que constituyeron las dos secuencias
- - La penalización de un hueco que tiene longitud.
- Construya una matriz de puntuación e inicializar su primera fila y primera columna. El tamaño de la matriz de puntuación es. La matriz utiliza indexación basada en 0.
- Llene la matriz de puntuación usando la siguiente ecuación.
- dónde
- es la puntuación de alinear y ,
- es la puntuación si está al final de un espacio de longitud ,
- es la puntuación si está al final de un espacio de longitud ,
- significa que no hay similitud hasta y .
- Rastrear. Comenzando con la puntuación más alta en la matriz de puntuación y terminando en una celda de matriz que tiene una puntuación de 0, seguimiento 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 por coincidencias / desajustes (también conocidas como sustituciones), inserciones y deleciones. Tanto las inserciones como las eliminaciones son las operaciones que introducen espacios, que están representados por guiones. El algoritmo de Smith-Waterman tiene varios pasos:
- Determine 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 desajuste. Por lo general, las coincidencias obtienen puntajes positivos, mientras que los desajustes obtienen puntajes relativamente más bajos. Una función de penalización por huecos determina el costo de puntuación para abrir o ampliar huecos. Se sugiere que los usuarios elijan el sistema de puntuación apropiado 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 hueco.
- 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 establecerlas en 0 hace que el espacio terminal esté libre de penalizaciones.
- Puntuación . Califique cada elemento de izquierda a derecha, de arriba a abajo en la matriz, considerando los resultados de las sustituciones (puntajes diagonales) o agregando espacios (puntajes 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.
- Traceback . Comenzando en el elemento con la puntuación más alta, rastree en función de la fuente de cada puntuación de forma recursiva, hasta que se encuentre 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 de Needleman-Wunsch
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, sirven para diferentes propósitos. Ambos algoritmos utilizan los conceptos de una matriz de sustitución, una función de penalización por brecha, una matriz de puntuación y un proceso de rastreo. Tres diferencias principales son:
Algoritmo de Smith-Waterman | Algoritmo de Needleman-Wunsch | |
---|---|---|
Inicialización | La primera fila y la primera columna se establecen en 0 | La primera fila y la primera columna están sujetas a penalización por espacio. |
Puntuación | La puntuación negativa se establece en 0 | La puntuación puede ser negativa |
Rastrear | Comience con la puntuación más alta, finalice cuando se encuentre 0 | Comience con la celda en la parte inferior derecha de la matriz, termine en la celda superior izquierda |
Una de las distinciones más importantes es que no se asigna ninguna puntuación negativa en el sistema de puntuación del algoritmo de Smith-Waterman, que permite la alineación local. Cuando cualquier elemento tiene una puntuación inferior a cero, significa que las secuencias hasta esta posición no tienen similitudes; este elemento se pondrá a 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 a una posición arbitraria en la otra secuencia. En el algoritmo de Needleman-Wunsch, sin embargo, también se debe 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ácido se le asigna una puntuación. En general, a las coincidencias se les asignan puntuaciones positivas y a las discrepancias se les asignan puntuaciones relativamente más bajas. Tome la secuencia de ADN como ejemplo. Si las coincidencias obtienen +1, las discrepancias obtienen -1, entonces la matriz de sustitución es:
A | GRAMO | C | T | |
---|---|---|---|---|
A | 1 | -1 | -1 | -1 |
GRAMO | -1 | 1 | -1 | -1 |
C | -1 | -1 | 1 | -1 |
T | -1 | -1 | -1 | 1 |
Esta matriz de sustitución se puede describir como:
Diferentes sustituciones de bases o sustituciones 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. Ver PAM , BLOSUM .
Penalización por huecos
La penalización por espacio designa puntuaciones para inserción o eliminación. Una estrategia simple de penalización por brecha es usar una puntuación fija para cada brecha. En biología, sin embargo, el puntaje 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 evento de mutación de un solo gen puede resultar en la inserción de un solo espacio largo. Por lo tanto, los espacios conectados que forman un espacio largo suelen ser más favorecidos que los espacios cortos y dispersos múltiples. Para tener en cuenta esta diferencia, se han añadido al sistema de puntuación los conceptos de apertura y extensión de huecos. La puntuación de apertura de la brecha suele ser más alta que la puntuación de extensión de la brecha. Por ejemplo, el parámetro predeterminado en EMBOSS Water es: apertura de la brecha = 10, extensión de la brecha = 0.5.
Aquí discutimos dos estrategias comunes para la penalización por brecha. Consulte Penalización por brecha para obtener más estrategias. Dejar ser la función de penalización por espacio para un espacio de longitud :
Lineal
Una penalización de espacio lineal tiene las mismas puntuaciones para abrir y extender un espacio:
,
dónde es el costo de una sola brecha.
La penalización por espacio es directamente proporcional a la longitud del espacio. Cuando se usa la penalización por espacio lineal, el algoritmo de Smith-Waterman se puede simplificar para:
El algoritmo simplificado utiliza pasos. Cuando se puntúa un elemento, solo se deben considerar las penalizaciones por espacio de los elementos que están directamente adyacentes a este elemento.
Afín
Una penalización de hueco afín considera la apertura y extensión del hueco por separado:
,
dónde es la penalización de apertura de hueco, y es la penalización por extensión del hueco. Por ejemplo, la penalización por un espacio de longitud 2 es.
En el artículo original del algoritmo de Smith-Waterman se utilizó una penalización por brecha arbitraria. Usapasos, por lo tanto, requiere bastante tiempo. Gotoh optimizó los pasos para una penalización de espacio afín para, [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 basándose en el método que fue publicado por Hirschberg en 1975, [11] y aplicó este método. [4] El algoritmo de Myers y Miller puede alinear dos secuencias usando espacio, con siendo la longitud de la secuencia más corta.
Ejemplo de penalización por huecos
Tome la alineación de las secuencias TACGGGCCCGCTAC y TAGCCCTATCGGTCA como ejemplo. Cuando se utiliza la función de penalización del espacio lineal, el resultado es (Alineaciones realizadas por EMBOSS Water. La matriz de sustitución está llena de ADN. La apertura y la extensión del espacio son 1,0):
TACGGGCCCGCTA-C || | || ||| | TA --- G-CC-CTATC
Cuando se usa la penalización de espacio afín, el resultado es (la apertura y la extensión del espacio son 5.0 y 1.0 respectivamente):
TACGGGCCCGCTA || ||| ||| TA --- GCC - CTA
Este ejemplo muestra que una penalización por huecos afines 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 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 en crecimiento. En otras palabras, la alineación óptima actual se genera al decidir qué ruta (coincidencia / desajuste 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 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:
b 1 | ... | b j | ... | b m | ||
---|---|---|---|---|---|---|
0 | 0 | ... | 0 | ... | 0 | |
un 1 | 0 | |||||
... | ... | |||||
a yo | 0 | |||||
... | ... | |||||
un n | 0 |
Ejemplo
Tome la alineación de las secuencias de ADN TGTTACGG y GGTTGACTA como ejemplo. Utilice el siguiente esquema:
- Matriz de sustitución:
- Penalización por huecos: (una penalización por espacio lineal de )
Inicialice y complete la matriz de puntuación, que 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 puntúa.
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 este elemento se remonta. En caso de múltiples puntajes más altos, el rastreo debe realizarse comenzando con cada puntaje más alto. El proceso de rastreo se muestra a continuación a la derecha. La mejor alineación local se genera en la dirección inversa.
Matriz de puntuación finalizada (la puntuación más alta está en azul) | Proceso de rastreo y resultado de alineación |
El resultado de la alineación es:
GTT - AC | | | | | GTTGAC
Implementación
Una implementación del algoritmo de Smith-Waterman, SSEARCH, está disponible en el FASTA paquete de análisis de secuencias de UVA FASTA Descargas . 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, [12] y una vectorización SSE2 desarrollada por Farrar [13], lo que hace que la base de datos de secuencias de proteínas sea ó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. [14]
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 hasta 28 veces mayor que las soluciones estándar basadas en microprocesadores. Otra versión basada en FPGA del algoritmo Smith-Waterman muestra velocidades de FPGA (Virtex-4) de hasta 100x [15] sobre un procesador Opteron de 2.2 GHz. [16] Los sistemas TimeLogic DeCypher y CodeQuest también aceleran Smith – Waterman y Framesearch usando tarjetas PCIe FPGA.
Una tesis de maestría de 2011 [17] incluye un análisis de la aceleración 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 la CPU / GPU / W en 12-21x , se presentó una implementación muy eficiente. Con una tarjeta PCIe FPGA equipada con una FPGA Xilinx Virtex-7 2000T, el rendimiento por nivel de vatios fue mejor que el de CPU / GPU en 12-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 de gráficos (GPU) con resultados preliminares que muestran una aceleración del doble sobre las implementaciones de software. [18] Ya se ha implementado un método similar en el software Biofacet desde 1997, con el mismo factor de aceleración. [19]
También están disponibles varias implementaciones de GPU del algoritmo en la plataforma CUDA C de NVIDIA . [20] En comparación con la implementación de CPU más conocida (usando instrucciones SIMD en la arquitectura x86), por Farrar, las pruebas de rendimiento de esta solución usando una sola tarjeta NVidia GeForce 8800 GTX muestran un ligero aumento en el rendimiento para secuencias más pequeñas, pero un leve disminución en el rendimiento para los más grandes. Sin embargo, las mismas pruebas que se ejecutan en tarjetas dobles NVidia GeForce 8800 GTX son casi dos veces más rápidas que la implementación de Farrar para todos los tamaños de secuencia probados.
Ahora está disponible una implementación de software GPU CUDA 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 software diferentes en CUDA, tres de las cuales reportan aceleraciones de 30X. [21]
SIMD
En 2000, en una publicación de Rognes y Seeberg se describió una implementación rápida del algoritmo Smith-Waterman utilizando la tecnología SIMD disponible en los procesadores Intel Pentium MMX y tecnología similar. [22] 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 sigue desarrollando el software y proporciona archivos ejecutables para uso académico de forma gratuita.
Un SSE2 vectorización del algoritmo (Farrar, 2007) está ahora disponible que proporciona una aceleración de 8-16 veces en los procesadores Intel / AMD con extensiones SSE2. [13] 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 el programa SSEARCH en el paquete de comparación de secuencias FASTA . El SSEARCH está incluido en el conjunto de programas de búsqueda de similitudes del Instituto Europeo de Bioinformática .
La compañía danesa de bioinformática CLC bio ha logrado aceleraciones de cerca de 200 en comparación con las implementaciones de software estándar con SSE2 en una CPU Intel Core 2 Duo de 2,17 GHz, según un documento técnico disponible al público .
La versión acelerada del algoritmo Smith-Waterman, en servidores Linux basados en Intel y 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 hasta 10 veces la velocidad en relación con la implementación de software estándar en el mismo procesador.
Actualmente, la única empresa de bioinformática que ofrece soluciones SSE y FPGA que aceleran Smith – Waterman, CLC bio ha logrado aceleraciones de más de 110 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 CPU con SSSE3 se puede encontrar en el software SWIPE (Rognes, 2011), [23] que está disponible bajo la GNU Affero General Public License . 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 de procesador dual Intel Xeon X5650 de seis núcleos, que es seis veces más rápido que el software basado en el enfoque 'rayado' de Farrar. Es más rápido que BLAST cuando se usa la matriz BLOSUM50.
También existe diagonalsw, una implementación en C y C ++ del algoritmo Smith-Waterman con los conjuntos de instrucciones SIMD ( SSE4.1 para la plataforma x86 y AltiVec para la plataforma PowerPC). Tiene la licencia MIT de código abierto.
Motor de banda ancha celular
En 2008, Farrar [24] describió un puerto del Striped Smith-Waterman [13] al Cell Broadband Engine y reportó velocidades de 32 y 12 GCUPS en una hoja 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 eficaz y preciso para el descubrimiento de variantes de ADN exigen enfoques innovadores para el procesamiento paralelo en tiempo real. Se han sugerido enfoques de computación óptica como alternativas prometedoras a las implementaciones eléctricas actuales. OptCAM es un ejemplo de tales enfoques y se demuestra que es más rápido que el algoritmo de Smith-Waterman. [25]
Ver también
- Bioinformática
- Alineación de secuencia
- Minería de secuencia
- Algoritmo de Needleman-Wunsch
- Distancia de Levenshtein
- EXPLOSIÓN
- FASTA
Referencias
- ^ 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 .
- ^ a b c Osamu Gotoh (1982). "Un algoritmo mejorado para emparejar 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 .
- ^ a b c d Stephen F. Altschul y Bruce W. Erickson (1986). "Alineación de secuencia óptima 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 .
- ^ a b c Miller, Webb; Myers, Eugene (1988). "Alineaciones óptimas en espacio lineal". Bioinformática . 4 (1): 11-17. CiteSeerX 10.1.1.107.6989 . doi : 10.1093 / bioinformatics / 4.1.11 . PMID 3382986 .
- ^ 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". Revista de Biología Molecular . 48 (3): 443–453. doi : 10.1016 / 0022-2836 (70) 90057-4 . PMID 5420325 .
- ^ Sankoff D. (1972). "Secuencias coincidentes 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 .
- ^ 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 al emparejamiento de secuencias polipeptídicas". Revista de Biología Teórica . 42 (2): 245-261. doi : 10.1016 / 0022-5193 (73) 90088-X . PMID 4762954 .
- ^ William A. Beyer, Myron L. Stein, Temple F. Smith y Stanislaw M. Ulam (1974). "Una secuencia molecular de árboles métricos y evolutivos". Biociencias matemáticas . 19 (1-2): 9-25. doi : 10.1016 / 0025-5564 (74) 90028-5 .CS1 maint: varios nombres: lista de autores ( enlace )
- ^ Peter H. Sellers (1974). "Sobre la teoría y el cálculo de las distancias evolutivas". Revista de Matemáticas Aplicadas . 26 (4): 787–793. doi : 10.1137 / 0126070 .
- ^ 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 .
- ^ 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 .
- ^ 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 .
- ^ a b c Farrar, Michael S. (2007). "Striped Smith-Waterman acelera las búsquedas en la base de datos seis veces sobre otras implementaciones de SIMD". Bioinformática . 23 (2): 156-161. doi : 10.1093 / bioinformatics / btl582 . PMID 17110365 .
- ^ Zhao, Mengyao; Lee, Wan-Ping; Guarnición, 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" . PLOS ONE . 8 (12): e82138. arXiv : 1208.6350 . Código bibliográfico : 2013PLoSO ... 882138Z . doi : 10.1371 / journal.pone.0082138 . PMC 3852983 . PMID 24324759 .
- ^ Papeles FPGA 100x: "Copia archivada" (PDF) . Archivado desde el original (PDF) el 5 de julio de 2008 . Consultado el 17 de octubre de 2007 .CS1 maint: 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 .CS1 maint: 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 .CS1 maint: copia archivada como título ( enlace )
- ^ Progeniq Pte. Ltd., " Informe técnico: aceleración de las aplicaciones intensivas a una velocidad de 10 × –50 × para eliminar los cuellos de botella en los flujos de trabajo computacionales ".
- ^ 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 .
- ^ Liu, Yang; Huang, Wayne; Johnson, John; Vaidya, Sheila (2006). Smith – Waterman acelerado por GPU . Apuntes de conferencias en informática . 3994 . SpringerLink. págs. 188-195 . doi : 10.1007 / 11758549_29 . ISBN 978-3-540-34385-1.
- ^ "Búsqueda y análisis de secuencias de alto rendimiento de bioinformática (documento técnico)" . GenomeQuest. Archivado desde el original el 13 de mayo de 2008 . Consultado el 9 de mayo de 2008 .
- ^ "Zona CUDA" . Nvidia . Consultado el 25 de febrero de 2010 .
- ^ Rognes, Torbjørn y Seeberg, Erling (2000). "Aceleración de seis veces de las búsquedas en la base de datos de secuencias de Smith-Waterman utilizando procesamiento paralelo en microprocesadores comunes" . Bioinformática . 16 (8): 699–706. doi : 10.1093 / bioinformatics / 16.8.699 . PMID 11099256 .
- ^ Rognes, Torbjørn (2011). "Búsquedas más rápidas en la base de datos Smith-Waterman con paralelización SIMD entre secuencias" . BMC Bioinformática . 12 : 221. doi : 10.1186 / 1471-2105-12-221 . PMC 3120707 . PMID 21631914 .
- ^ 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
|journal=
( ayuda ) - ^ Maleki, Ehsan; Koohi, Somayyeh; Kavehvash, Zahra; Mashaghi, Alireza (2020). "OptCAM: una arquitectura totalmente óptica ultrarrápida para el descubrimiento de variantes de ADN" . Revista de biofotónica . 13 (1): e201900227. doi : 10.1002 / jbio.201900227 . PMID 31397961 .
enlaces externos
- JAligner : una implementación Java de código abierto del algoritmo Smith-Waterman
- BABA : un applet (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 (especialmente 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.