RNA Secondary Structure Prediction using Nussinov Algorithm
The Nussinov algorithm is an RNA secondary structure (folding) prediction method using a dynamic programming approach. Ruth Nussinov introduced this algorithm in the year 1978. It involves computing a two-dimensional (2D) diagonal matrix with the same sequence at both dimensions. The scores are given based on complementary ( 1 ) or non-complementary ( 0 ) matches of characters. Matrix solving consists of three stages ( i ) initialization , ( ii ) matrix-filling , and ( iii ) trace-back of arrows for structures. \(\style{ color: blue; } {\begin{array} \\ \text{RNA sequence, } S=a_1a_2a_3....a_{l-1}a_l \\ \begin{align*} \\ \!\!\!\!\! \text{where,} \\ & a=\text{characters (A, U, C, G)} \\ & l=\text{length of the sequence} \\ \end{align*} \end{array}} \) In this tutorial, I have taken a sample RNA sequence ( S ) as GGGAAAUCC for prediction. Initialization The initialization step is to preset the diagonal cells with zero ( 0 ) values to perform matrix filling. \(...