En la alineación de secuencia, hay dos categorías amplias: alineación local, global y semi-global. Local está buscando la mejor coincidencia de subsecuencia, global la mejor coincidencia de ambas secuencias en su totalidad, y semi-global encuentra la mejor coincidencia sin penalizar los huecos en los extremos de la alineación.
Para la alineación global, siempre puede usar un algoritmo de fuerza bruta, aunque tendrá un tiempo de ejecución exponencial. En cambio, se recomienda la programación dinámica. DP se basa en una fórmula recurrente y requiere un problema para tener la ‘subestructura óptima’, que es donde puede construir la solución a un problema si tiene la solución a sus subproblemas. Volviendo a la alineación global, hay un algoritmo DP para la alineación global llamado ‘algoritmo Needleman-Wunsch’, que ahora tiene O (nm) complejidad de tiempo y espacio para dos secuencias de longitud ny m.
Para la alineación local, un método comúnmente utilizado es el algoritmo Smith-Waterman. Las implementaciones de los algoritmos Needleman-Wunsch y Smith-Waterman son casi idénticas.
- ¿Cuáles son las buenas opciones de investigación en informática en India?
- ¿Qué podría ser el trabajo de investigación sobre autómatas (TOC)?
- ¿Qué tan difícil es hacer la transición de la industria al profesor titular?
- ¿Qué áreas de la informática involucran más trabajo de hardware?
- ¿Puede la programación en objetivos ser una alternativa a la definición de API (de la charla de B. Victor 'El futuro de la programación)?
Como nota, estos algoritmos también se pueden usar para la alineación de la secuencia de proteínas si usa una matriz de sustitución diferente (es decir, BLOSUM o PAM250 para proteínas).
ps: El problema de alineación global puede acelerarse para tener una complejidad de tiempo sub-cuadrática, O (n ^ 2 / logn), usando la ‘Aceleración de cuatro rusos’.
pps: El problema de alineación global se puede hacer en espacio lineal utilizando el algoritmo de Hirschberg. Esto es divertido de implementar y solo requiere pensar qué valores en una tabla DP son necesarios para el próximo cálculo.
Fuente: https://www.cs.duke.edu/courses/…
