Nussinov algorithm

We score a solution by counting the total number of paired bases. Thus, attempting to maximize the score maximizes the total number of bonds between bases.

Consider an RNA sequence ${\displaystyle S}$ whose elements are taken from the set ${\displaystyle \{A,U,C,G\}}$. Let us imagine we have an optimal solution to the subproblem of folding ${\displaystyle S_{i}}$ to ${\displaystyle S_{j-1}}$, and an optimal solution for folding ${\displaystyle S_{u}}$ to ${\displaystyle S_{v}}$ ${\displaystyle i\leq u\leq v\leq j-1}$ . Now, to align ${\displaystyle S_{i}}$ to ${\displaystyle S_{j}}$, we have two options:

1. Leave ${\displaystyle S_{j}}$ unpaired, and keep the structure of ${\displaystyle S_{i}}$ to ${\displaystyle S_{j-1}}$. The score for this alignment will be equal to the score of the aligmnent of ${\displaystyle S_{i}}$ to ${\displaystyle S_{j-1}}$, as no new base pairs were created.
2. Pair ${\displaystyle S_{j}}$ with ${\displaystyle S_{k}}$, where ${\displaystyle i\leq k<j}$. The score for this alignment will be the score of the base pairing, plus the score of the best alignment of ${\displaystyle S_{i}}$ to ${\displaystyle S_{k-1}}$ and ${\displaystyle S_{k+1}}$ to ${\displaystyle S_{j-1}}$.

Consider an RNA sequence ${\displaystyle S}$ of length ${\displaystyle n}$ such that ${\displaystyle S_{i}\in \{A,U,C,G\}}$.

Construct an ${\displaystyle n\times n}$ matrix ${\displaystyle M}$. Initialize ${\displaystyle M}$ such that

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

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

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

${\displaystyle M(i,j)}$ will contain the maximum score for the subsequence ${\displaystyle S_{i}...S_{j}}$. Now, fill in entries of ${\displaystyle M}$ up and to the right, so that

${\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}}}$

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

After this step, we have a matrix ${\displaystyle M}$ where ${\displaystyle M(i,j)}$ represents the optimal score of the folding of ${\displaystyle S_{i}...S_{j}}$.

To determine the structure of by traceback, we first create an empty list of pairs ${\displaystyle P}$. We initialize with ${\displaystyle i=0,j=n}$. Then, we follow one of three scenarios.

1. If ${\displaystyle j\leq i}$, the procedure stops.
2. If ${\displaystyle M(i,j)=M(i,j-1)}$, then set ${\displaystyle i=i,j=j-1}$ and continue.
3. Otherwise, for all ${\displaystyle k:i\leq k<j}$, if${\displaystyle S_{k}}$ and ${\displaystyle S_{j}}$ are complementary and ${\displaystyle M(i,j)=M(i,k-1)+M(k+1,j-1)+1}$, append ${\displaystyle (k,j)}$ to ${\displaystyle P}$, then traceback both with ${\displaystyle i=i,j=k-1}$ and ${\displaystyle i=k+1,j=j-1}$.

When the traceback finishes, ${\displaystyle P}$ contains all of the paired bases.