3.1: ¿Qué hemos aprendido?
- Page ID
- 54231
En esta sección exploramos algoritmos de alineación más allá de la alineación global. Comenzamos revisando nuestro uso de la programación dinámica para resolver problemas de alineación global usando el algoritmo Needleman-Wunsch. Luego exploramos alternativas de alineaciones locales (Smith-Waterman) y semi-globales. Luego discutimos el uso de la función hash para hacer coincidir cadenas exactas en tiempo lineal (Karp-Rabin) así como hacer una búsqueda de vecindario, investigando secuencias similares en tiempo lineal probabilístico (principio de encasillado, peines, explosión de 2 golpes, proyecciones aleatorias). También hemos abordado el uso del preprocesamiento para la coincidencia lineal de cadenas de tiempo, así como el fondo probabilístico para la alineación de secuencias.