Esto suena como tarea, así que voy a discutir la alineación en general. Hay muchos recursos que ayudarán con la implementación si necesita escribir el código.
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.
Su problema parece ser una alineación global. 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.
- ¿Cuál sería el plan de trabajo general o el calendario para as en programación competitiva?
- ¿En qué se diferencia un árbol de búsqueda binario de un árbol binario?
- Ahora que los bitcoins son famosos y caros, ¿cómo reaccionaría el mercado ante un clon de Bitcoin que utiliza un algoritmo, tecnología, etc. idénticos?
- Matrices de sufijos: Dadas dos cadenas s1 y s2. ¿Cuál es el mejor algoritmo para encontrar el número de subcadenas comunes entre s1 y s2 de longitud 1, 2,… hasta min (| s1 |, | s2 |)?
- Como saber entiendo totalmente un algoritmo
Para la alineación local, el método más utilizado es el algoritmo Smith-Waterman. Las implementaciones de los algoritmos Needleman-Wunsch y Smith-Waterman son casi idénticas.
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/…
