Nussinov algorithm

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.

Uses your system voice; voice and rate in settings.

≈ 3 min read

Cite, export and learn8 citation formats · 8 exports · lesson and quiz

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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

edit edit source

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

edit edit source

Scoring

edit edit source

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

edit edit source

Consider an RNA sequence S whose elements are taken from the set {A,U,C,G}. Let us imagine we have an optimal solution to the subproblem of folding Si to Sj−1, and an optimal solution for folding Su to Sv i≤u≤v≤j−1 . Now, to align Si to Sj, we have two options:

  1. Leave Sj unpaired, and keep the structure of Si to Sj−1. The score for this alignment will be equal to the score of the alignment of Si to Sj−1, as no new base pairs were created.
  2. Pair Sj with Sk, where i≤k<j. The score for this alignment will be the score of the base pairing, plus the score of the best alignment of Si to Sk−1 and Sk+1 to Sj−1.

Algorithm

edit edit source

Consider an RNA sequence S of length n such that Si∈{A,U,C,G}.

Construct an n×n matrix M. Initialize M such that

M(i,i)=0

M(i,i−1)=0

for 1≤i≤n.

M(i,j) will contain the maximum score for the subsequence Si...Sj. Now, fill in entries of M up and to the right, so that

M(i,j)=maxi≤k<j{M(i,k−1)+M(k+1,j−1)+Score(Sk,Sj)M(i,j−1)

where Score(Sk,Sj)={1,Sk and Sj complementary0,otherwise.

After this step, we have a matrix M where M(i,j) represents the optimal score of the folding of Si...Sj.

To determine the structure of the folded RNA by traceback, we first create an empty list of pairs P. We initialize with i=1,j=n. Then, we follow one of three scenarios.

  1. If j≤i, the procedure stops.
  2. If M(i,j)=M(i,j−1), then set i=i,j=j−1 and continue.
  3. Otherwise, for all k:i≤k<j, ifSk and Sj are complementary and M(i,j)=M(i,k−1)+M(k+1,j−1)+1, append (k,j) to P, then traceback both with i=i,j=k−1 and i=k+1,j=j−1.

When the traceback finishes, P contains all of the paired bases.

Limitations

edit edit source

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

edit edit source
  1. ^ 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. Bibcode:1980PNAS...77.6309N. doi:10.1073/pnas.77.11.6309. ISSN 0027-8424. PMC 350273. PMID 6161375. Wikipedia revision 1148012114, retrieved 2026-11-18
  2. ^ "RNA Structure and RNA Structure Prediction" (PDF). Wikipedia revision 1148012114, retrieved 2026-11-18

Text derived from https://en.wikipedia.org/w/index.php?oldid=1148012114 under CC BY-SA 4.0; modifications have been made.

Words in each sectionAlgorithmAlgorithmAlgorithm: 414 words414LimitationsLimitationsLimitations: 52 words52BackgroundBackgroundBackground: 39 words39
Words in each section. Measured from the stored article body; sections below the minimum are not plotted.

Provenance

snapshot enwiki-001148012114 · captured 2023-04-03 · ledger · version history

Cite this page as: encyclopegia.org, “Nussinov algorithm”, snapshot enwiki-001148012114. https://encyclopegia.org/a/nussinov-algorithm