Others view: A star algorithm ♦ all_projects ♦ Welcome ♦ Dynamic programming table ♦ Lapis SBB ♦ Reversal potential ♦ rss.xml ♦

*This is an advanced topic. It assumes that your are familiar with Dynamic programming table*

[[Math:c|D(i,j) = \max \begin{Bmatrix} max_{i\ltk\ltj} D(i,k)\plusD(k\plus1,j) \amp \\ D(i\plus1,j-1) \plus \ w(i,j) \amp \\ D(i\plus1,j) \amp \\ D(i,j-1) \amp \end{Bmatrix} ]]

Here w(i,j) = 1 if chars at the positions i and j are complementary (AT, TA, GC, CG). Otherwise this function is 0.

Another formula set that may be simpler is given in ^{[2]} and referred as Nussinov-Jacobson algorithm:

[[Math:c|D(i,j) = \max \begin{Bmatrix} D(i,k)\plusD(k\plus1,j) \amp where \ i \le k \lt j \\ D(i\plus1,j-1) \plus \ w(i,j) \amp \end{Bmatrix} ]]

with initialization

[[Math:c|D(i,j) = \max \begin{Bmatrix} D(i,i) = 0 \amp \forall i = 1..L \\ D(i,i-1) = 0 \amp \forall i = 2..L \end{Bmatrix} ]]

Nussinov algorithm does not necessary generates the most stable structure and may have scattered matches that are not biologically reasonable^{[3]}. It is too simple to be accurate but has been a stepping stone for more complex algorithms.

The algorithm above detects complementary sequences but tells nothing about how the RNA would fold. The usually expected structure ("knots") implies that one independent matching pair of *sequences* either completely precedes the other or is fully nested within^{[4]}. To emphasize this fact, RNA folding is described using the dot-bracket notation, marking every pairing nucleotide with *(* and its matching counterpart with *)*. Parenthesis in the resulted expression must be balanced, for instance

- ....
**(((**...**)))**......(((((......)))))...... - two independent - ....
**(((**........(((.....)))...**)))**......... - one inside another - ....
**(((**........(((.....)))..((((...))))....**)))**- two inside one

Using this rule, it is possible to write a wrapping algorithm that in many cases correctly predicts RNA folding. If these rules are violated, it is said that RNA forms "pseudoknots". Pseudoknots do exist in nature, and more complex algorithms are required to discover them.

A "real world" size RNA may have multiple alternative ways of folding, when either one or another subset of the detected matching sequences are involved. As a rule, RNA folds in the way that is the most "thermodinamicaly stable" - this usually means that the folding case that has the biggest total number of paired nucleotides takes over others.

^{1 }I519 Introduction to Bioinformatics / Lecture 9 / Sep 24, 2007. Yuzhen Ye School of Informatics Indiana University^{2 }Nussinov algorithm lecture by Ruth Nussinov herself^{3 }RNA Secondary Structure. Case Western Reserver University encyclopedia^{4 }RNA folding

- Ruth Nussinov page at Center for Cancer Research, contains useful links.
- mfold and RNAfold, DNA/RNA folding prediction servers running advanced algorithms.