Algoritmo de Nussinov

Algoritmo de predicción de la estructura de los ácidos nucleicos

El algoritmo de Nussinov es un algoritmo de predicción de la estructura de los ácidos nucleicos utilizado 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.

Fondo

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

Algoritmo

Tanteo

Calificamos una solución contando el número total de bases emparejadas. De esta forma, intentamos maximizar el puntaje que maximiza el número total de enlaces entre bases.

Motivación

Consideremos una secuencia de ARN cuyos elementos se toman del conjunto . Imaginemos que tenemos una solución óptima para el subproblema de plegamiento a , y una solución óptima para plegar 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}}$

1. Déjelo sin emparejar y conserve la estructura de hasta . La puntuación de esta alineación será igual a la puntuación de la alineación de hasta , ya que no se crearon nuevos pares de bases. ${\displaystyle S_{j}}$ ${\displaystyle S_{i}}$ ${\displaystyle S_{j-1}}$ ${\displaystyle S_{i}}$ ${\displaystyle S_{j-1}}$
2. Emparejar con , donde . La puntuación para esta alineación será la puntuación del emparejamiento de bases, más la puntuación de la mejor alineación de a y a . ${\displaystyle S_{j}}$ ${\displaystyle S_{k}}$ ${\displaystyle i\leq k<j}$ ${\displaystyle S_{i}}$ ${\displaystyle S_{k-1}}$ ${\displaystyle S_{k+1}}$ ${\displaystyle S_{j-1}}$

Algoritmo

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

Construir una matriz . Inicializar de manera que ${\displaystyle n\times n}$ ${\displaystyle M}$ ${\displaystyle M}$

${\displaystyle M(i,i)=0}$

${\displaystyle M(i,i-1)=0}$

para . ${\displaystyle 1\leq i\leq n}$

${\displaystyle M(i,j)}$contendrá la puntuación máxima para la subsecuencia . Ahora, complete las entradas de arriba y a la derecha, de modo que ${\displaystyle S_{i}...S_{j}}$ ${\displaystyle M}$

${\displaystyle M(i,j)=\max _{i\leq k<j}{\begin{cases}M(i,k-1)+M(k+1,j-1)+{\text{Score}}(S_{k},S_{j})\\M(i,j-1)\end{cases}}}$

dónde ${\displaystyle {\text{Score}}(S_{k},S_{j})={\begin{cases}1,&S_{k}{\text{ and }}S_{j}{\text{ complementary}}\\0,&{\text{otherwise.}}\end{cases}}}$

Después de este paso, tenemos una matriz donde representa la puntuación óptima del plegado de . ${\displaystyle M}$ ${\displaystyle M(i,j)}$ ${\displaystyle S_{i}...S_{j}}$

Para determinar la estructura del ARN plegado mediante rastreo, primero creamos una lista vacía de pares . Inicializamos con . Luego, seguimos uno de tres escenarios. ${\displaystyle P}$ ${\displaystyle i=1,j=n}$

1. Si , el procedimiento se detiene. ${\displaystyle j\leq i}$
2. Si , entonces configúrelo y continúe. ${\displaystyle M(i,j)=M(i,j-1)}$ ${\displaystyle i=i,j=j-1}$
3. De lo contrario, para todos , si y son complementarios y , anexar a , entonces rastrear ambos con y . ${\displaystyle k:i\leq k<j}$ ${\displaystyle S_{k}}$ ${\displaystyle S_{j}}$ ${\displaystyle M(i,j)=M(i,k-1)+M(k+1,j-1)+1}$ ${\displaystyle (k,j)}$ ${\displaystyle P}$ ${\displaystyle i=i,j=k-1}$ ${\displaystyle i=k+1,j=j-1}$

Cuando finaliza el rastreo, contiene todas las bases emparejadas. ${\displaystyle P}$

Limitaciones

El algoritmo de Nussinov no tiene en cuenta la forma tridimensional del ARN ni predice los pseudonudos del ARN . ^[2] Además, en su forma básica, no tiene en cuenta un tamaño mínimo de bucle de tallo . Sin embargo, sigue siendo útil como algoritmo rápido para la predicción básica de la estructura secundaria.

Referencias

1. Nussinov, R; Jacobson, AB (noviembre de 1980). "Algoritmo rápido para predecir la estructura secundaria del ARN monocatenario". Actas de la Academia Nacional de Ciencias de los Estados Unidos de América . 77 (11): 6309–6313. Bibcode :1980PNAS...77.6309N. doi : 10.1073/pnas.77.11.6309 . ISSN  0027-8424. PMC  350273 . PMID  6161375.
2. "Estructura del ARN y predicción de la estructura del ARN" (PDF) .