Algoritmo de Nussinov

El algoritmo de Nussinov es un algoritmo de predicción de la estructura del ácido nucleico que se utiliza en biología computacional para predecir el plegamiento de una molécula de ARN que utiliza principios de programación dinámica . ^[1] El algoritmo fue desarrollado por Ruth Nussinov a fines de la década de 1970.

El origami de ARN ocurre cuando una molécula de ARN se "pliega" y se une a sí misma. Este plegamiento a menudo determina la función de la molécula de ARN. El ARN se pliega en diferentes niveles, este algoritmo predice la estructura secundaria del ARN.

Calificamos una solución contando el número total de bases emparejadas. Por lo tanto, intentar maximizar la puntuación maximiza el número total de enlaces entre bases.

Considere una secuencia de ARN cuyos elementos se toman del conjunto . Imaginemos que tenemos una solución óptima para el subproblema de plegarse a , y una solución óptima para el plegado a . Ahora, para alinear a , tenemos dos opciones: ${\ Displaystyle S}$ ${\ Displaystyle \ {A, U, C, G \}}$ ${\ Displaystyle S_ {i}}$ ${\ Displaystyle S_ {j-1}}$ ${\ Displaystyle S_ {u}}$ ${\ Displaystyle S_ {v}}$ ${\ Displaystyle i \ leq u \ leq v \ leq j-1}$ ${\ Displaystyle S_ {i}}$ ${\ Displaystyle S_ {j}}$

Considere una secuencia de ARN de longitud tal que . ${\ Displaystyle S}$ ${\ Displaystyle n}$ ${\ Displaystyle S_ {i} \ in \ {A, U, C, G \}}$

Construye una matriz . Inicializar de manera que ${\ Displaystyle n \ times n}$ ${\ Displaystyle M}$ ${\ Displaystyle M}$