El algoritmo de Smith-Waterman está diseñado para obtener el alineamiento de secuencias locales , es decir, para identificar regiones similares de dos secuencias de nucleótidos o proteínas . A diferencia del algoritmo de Needleman-Wunsch , que alinea las secuencias a lo largo de toda la longitud, el algoritmo de Smith-Waterman compara segmentos de todas las longitudes posibles y optimiza la medida de similitud en todos los segmentos y todas las alineaciones de estos segmentos.
El algoritmo fue propuesto por T. F. Smith y M. Waterman en 1981 [1] . Al igual que el algoritmo de Needleman-Wunsch, el algoritmo de Smith-Waterman utiliza el principio de programación dinámica . Garantiza encontrar la alineación local óptima, en relación con la medida de evaluación de la calidad que utiliza. Esta medida de evaluación es el llamado peso de alineación, o Score, que implica el uso de una matriz de sustitución y penalizaciones por "brechas" (es decir, inserciones y eliminaciones).
| Instrumentos de cuerda | |
|---|---|
| Medidas de similitud de cadenas | |
| Búsqueda de subcadena | |
| palíndromos | |
| Alineación de secuencia | |
| Estructuras de sufijos | |
| Otro | |