Nussinov algorithm explained


Class:	Nucleic acid structure prediction
Time:	O(n³⁾
Space:	O(n²⁾

The Nussinov algorithm is a nucleic acid structure prediction algorithm used in computational biology to predict the folding of an RNA molecule that makes use of dynamic programming principles.^[1] The algorithm was developed by Ruth Nussinov in the late 1970s.

Background

RNA origami occurs when an RNA molecule "folds" and binds to itself. This folding often determines the function of the RNA molecule. RNA folds at different levels, this algorithm predicts the secondary structure of the RNA.

Algorithm

Scoring

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

Motivation

Consider an RNA sequence

whose elements are taken from the set

\{A,U,C,G\}

. Let us imagine we have an optimal solution to the subproblem of folding

S_i

S_j-1

, and an optimal solution for folding

S_u

S_v

i\lequ\leqv\leqj-1

. Now, to align

S_i

S_j

, we have two options:

Leave

S_j

unpaired, and keep the structure of

S_i

S_j-1

. The score for this alignment will be equal to the score of the alignment of

S_i

S_j-1

, as no new base pairs were created.

Pair

S_j

with

S_k

, where

i\leqk<j

. The score for this alignment will be the score of the base pairing, plus the score of the best alignment of

S_i

S_k-1

and

S_k+1

S_j-1

Algorithm

Consider an RNA sequence

of length

such that

S_i\in\{A,U,C,G\}

Construct an

n x n

matrix

. Initialize

such that

M(i,i)=0

M(i,i-1)=0

for

1\leqi\leqn

M(i,j)

will contain the maximum score for the subsequence

S_i...S_j

. Now, fill in entries of

up and to the right, so that

M(i,j)=max_i\leq\begin{cases}M(i,k-1)+M(k+1,j-1)+Score(S_k,S_j)\ M(i,j-1)\end{cases}

where

Score(S_k,S_{j)=\begin{cases}1,&S}_kandS_jcomplementary\\ 0,&otherwise.\end{cases}

After this step, we have a matrix

where

M(i,j)

represents the optimal score of the folding of

S_i...S_j

To determine the structure of the folded RNA by traceback, we first create an empty list of pairs

. We initialize with

i=1,j=n

. Then, we follow one of three scenarios.

j\leqi

, the procedure stops.

M(i,j)=M(i,j-1)

, then set

i=i,j=j-1

and continue.

Otherwise, for all

k:i\leqk<j

, if

S_k

and

S_j

are complementary and

M(i,j)=M(i,k-1)+M(k+1,j-1)+1

, append

(k,j)

, then traceback both with

i=i,j=k-1

and

i=k+1,j=j-1

When the traceback finishes,

contains all of the paired bases.

Limitations

The Nussinov algorithm does not account for the three-dimensional shape of RNA, nor predict RNA pseudoknots.^[2] Furthermore, in its basic form, it does not account for a minimum stem loop size. However, it is still useful as a fast algorithm for basic prediction of secondary structure.

References

Nussinov. R. Jacobson. A B. Nov 1980. Fast algorithm for predicting the secondary structure of single-stranded RNA.. Proceedings of the National Academy of Sciences of the United States of America. 77. 11. 6309–6313. 10.1073/pnas.77.11.6309. 0027-8424. 6161375. 350273. 1980PNAS...77.6309N. free.
Web site: RNA Structure and RNA Structure Prediction.