Nussinov

The Nussinov algorithm is a dynamic programming method used to predict the secondary structure of an RNA molecule by maximizing the number of base pairs. Developed by Ruth Nussinov in 1978, it simplifies RNA folding by assigning a score of to any valid complementary base pair (A-U or G-C) and

otherwise, completely ignoring loop destabilisation energies. 1. Define the Scoring Matrix The algorithm populates a scoring matrix is the length of the RNA sequence. The value

represents the maximum number of base pairs possible for the subsequence from index 2. Initialize the Matrix

Before filling the matrix, you must initialize the main diagonal and the diagonal immediately below it to zero. This reflects the physical reality that a single base or an empty sequence cannot form pairs. 3. Apply the Recurrence Relation

Fill the matrix diagonally, moving from shorter subsequences to longer ones. For each cell

, evaluate four structural possibilities and choose the maximum value:

N(i,j)=max{N(i+1,j)(Base i is unpaired)N(i,j−1)(Base j is unpaired)N(i+1,j−1)+δ(i,j)(Bases i and j pair together)maxi≤k

contains the maximum possible base pairs, a traceback procedure reconstructs the actual secondary structure. Start at

and recursively follow the choices that yielded the maximum score: is unpaired. Move to is unpaired. Move to match, record the pair

, the structure splits. Split the traceback into two independent paths for subproblems Summary of Algorithm Performance Value / Description Primary Goal Maximize total base pairs Time Complexity due to the triple loop required by the bifurcation step Space Complexity to store the 2D dynamic programming table Limitation

Cannot predict pseudoknots and lacks realistic thermodynamic parameters

✅The Nussinov algorithm provides an elegant, deterministic

method to find an RNA secondary structure maximizing base-pair matches using dynamic programming.

If you have a specific RNA sequence you want to test, let me know: What is the RNA sequence string? (e.g., GGGAAAUUUCCC) bases in nature)

I can generate the step-by-step filled matrix for your custom sequence!