Dos algoritmos de programación dinámica comúnmente utilizados en biología

El algoritmo de programación dinámica es un método informático. Su idea principal es dividir un problema en varios problemas pequeños para resolverlos.

Dos métodos utilizados en biología Dos algoritmos de programación dinámica: Algoritmo de Needleman-Wunsch. (alineación global) y algoritmo de Smith-Waterman (alineación local)

(1) Alineación de secuencia global:

1) Se pueden alinear dos secuencias en una matriz en x e y -axes;

2) Si las secuencias son consistentes, se puede obtener un camino a través de la diagonal;

3) Encuentre los mejores caminos secundarios y luego súmelos para obtener el mejor puntuación,

Esto incluye:

Insertar espacios cuando sea necesario

Permitir sustitución conservadora

Elegir un sistema de puntuación (simple o complejo)

El algoritmo Needleman-Wunsch puede garantizar la mejor alineación

(2) Alineación de secuencia local: el objetivo de la alineación local es encontrar el área de alineación óptima (subsecuencia) de dos secuencias, que no es necesario extenderse a ambos extremos de la secuencia; la alineación local es el algoritmo más utilizado para la búsqueda en bases de datos y es muy útil para encontrar estructuras entre secuencias. 1) Algoritmo de Smith-Waterman

1. Establezca una matriz con tamaño (m 1, n 1)

2. El valor en la matriz no debe ser menor que 0.

3. La puntuación S de cada celda de la matriz es el máximo de las cuatro siguientes:

1. matriz, que representa el final de la alineación (terminal carboxilo).

2. El proceso de retroceso comienza desde la posición del valor máximo y sube y baja a lo largo de la diagonal hasta encontrar una celda con puntuación cero.

3. Una condición requerida por el algoritmo es que la puntuación esperada de la coincidencia aleatoria sea negativa, lo que garantiza que las secuencias largas e irrelevantes no puedan obtener puntuaciones altas (la mayoría de las matrices de puntuación satisfacen esta condición)