Nussinov algorithm

Uses your system voice; voice and rate in settings.

Snapshot

≈ 2 min read

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. The algorithm was developed by Ruth Nussinov in the late 1970s.

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. The algorithm was developed by Ruth Nussinov in the late 1970s. M(i, i)=0 M(i, i-1) = 0 for 1\leq i\leq n . M(i,j) will contain the maximum score for the subsequence S_i...S_j . Now, fill in entries of M up and to the right, so that M(i,j) = \max_{i\leq k where \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 M 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 P . We initialize with i=1,j=n . Then, we follow one of three scenarios. If j\leq i , the procedure stops. If M(i,j)=M(i,j-1) , then set i=i,j=j-1 and continue. Otherwise, for all k: i\leq k , 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) 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.

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

Provenance

snapshot enwiki-001148012114 · captured 1680526322.0 · version history

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

Sources cited in this revision

1 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.