Algoritmos de Alineamiento de Secuencias
Los algoritmos de alineamiento de secuencias miden y muestran la similitud entre dos cadenas al encontrar la forma de menor costo para transformar una en la otra, utilizando programación dinámica sobre inserciones, eliminaciones y sustituciones.
Definition
El alineamiento de secuencias es la disposición de dos (o más) cadenas para maximizar su correspondencia insertando huecos y emparejando, desemparejando o sustituyendo caracteres; un algoritmo de alineamiento calcula un alineamiento óptimo y su puntuación bajo un modelo de costo o puntuación dado, típicamente mediante programación dinámica.
Scope
Este tema cubre los algoritmos de programación dinámica para comparar cadenas: la distancia de edición (Levenshtein) y la subsecuencia común más larga, el alineamiento global (Needleman-Wunsch), el alineamiento local (Smith-Waterman) y los esquemas de puntuación (penalizaciones por huecos, matrices de sustitución) que dan forma a los alineamientos biológicos. Trata la recurrencia subyacente y su costo cuadrático en tiempo y espacio, además de refinamientos para ahorrar espacio. Los métodos basados en índices y de coincidencia exacta se cubren en temas relacionados.
Core questions
- ¿Cómo se cuantifica la similitud entre dos cadenas como una distancia de edición o una puntuación de alineamiento?
- ¿Cómo calcula una tabla de programación dinámica un alineamiento óptimo?
- ¿Qué distingue el alineamiento global del alineamiento local y cuándo es apropiado cada uno?
- ¿Cómo influyen las penalizaciones por huecos y las matrices de sustitución en el alineamiento resultante?
- ¿Cómo se puede reducir el requisito de espacio cuadrático para secuencias largas?
Key concepts
- distancia de edición (Levenshtein)
- subsecuencia común más larga
- alineamiento global
- alineamiento local
- algoritmo de Needleman-Wunsch
- algoritmo de Smith-Waterman
- penalizaciones por huecos
- matrices de sustitución
Key theories
- Alineamiento global por programación dinámica
- El algoritmo de Needleman-Wunsch llena una tabla de programación dinámica cuyas entradas dan la mejor puntuación de alineamiento de prefijos de cadenas, produciendo un alineamiento óptimo de extremo a extremo (global) de dos secuencias en un tiempo proporcional al producto de sus longitudes.
- Alineamiento local para subsecuencias compartidas
- El algoritmo de Smith-Waterman modifica la recurrencia para permitir que los alineamientos comiencen y terminen en cualquier lugar, encontrando la región de coincidencia de mayor puntuación (alineamiento local), lo cual es esencial para detectar fragmentos conservados dentro de secuencias que de otro modo serían disímiles.
Clinical relevance
El alineamiento de secuencias es una piedra angular de la biología computacional, utilizado para comparar secuencias de ADN, ARN y proteínas en busca de homología, inferencia evolutiva y búsqueda en bases de datos (el heurístico BLAST se basa en el alineamiento local). Fuera de la biología, la misma maquinaria de distancia de edición impulsa la corrección ortográfica, la coincidencia de texto difusa, las diferencias de control de versiones y la comparación de voz y escritura a mano.
History
Levenshtein introdujo la distancia de edición en 1965. Needleman y Wunsch presentaron el primer algoritmo de alineamiento global por programación dinámica para proteínas en 1970, y Smith y Waterman introdujeron el alineamiento local en 1981. La técnica de espacio lineal de Hirschberg (1975) y heurísticas posteriores como BLAST extendieron el alineamiento a un uso práctico a gran escala.
Key figures
- Saul Needleman
- Christian Wunsch
- Temple Smith
- Michael Waterman
- Vladimir Levenshtein
Related topics
Seminal works
- needleman1970
- smith1981
- gusfield1997
Frequently asked questions
- ¿Cuál es la diferencia entre alineamiento global y local?
- El alineamiento global (Needleman-Wunsch) alinea dos secuencias de extremo a extremo y es apropiado cuando tienen una longitud similar y se espera que estén relacionadas en toda su extensión. El alineamiento local (Smith-Waterman) encuentra la subregión de mejor coincidencia y es apropiado cuando solo partes de las secuencias son similares, como un dominio conservado dentro de secuencias más grandes.
- ¿Es el alineamiento de secuencias lo mismo que la subsecuencia común más larga?
- Están estrechamente relacionados. La subsecuencia común más larga es un caso especial de alineamiento con una puntuación particular (las coincidencias son recompensadas, los huecos son gratuitos, los desajustes no están permitidos). El alineamiento general utiliza una puntuación más rica con costos de sustitución y penalizaciones por huecos, pero ambos se resuelven mediante el mismo tipo de recurrencia de programación dinámica.