Help With Nussinov'S Rna Folding Algorithm

Question

[Shane]

Hello everyone,

I'm having trouble understanding the nussinov's algorithm for rna folding using dynamic programming.I did look over the web and found resources but none of them really explained two procedures, 1)how to fill the matrix 2)how to traceback the matrix for required structure?

I would be very grateful if someone can please tell me how these two steps are done with some example, there is code directly available over the internet but I don't want to copy paste it.

Answer 1

[Cjt]

As your question is very basic, a comprehensive answer is hard to give. As well as asaf I recommend to have a look into one of the countless bioinformatics text books (e.g. via google books or your favourite hard-copy library).

However, you can find a nice illustrative example of initialization, filling the matrix and doing a trace back in this tutorial.

As already mentioned, the algorithm performs pretty poor: the resulting structures a very inaccurate and usually not of any biological relevance. The number of base pairings is not a good criteria for structure prediction as, for instance, energies contributed by stackings are far more important. In case you are going to predict secondary structures, I suggest using MFOLD or, even better, tool out of the vienna package. The results are far from perfect but much better than that by Nussinov.

[Shane]

Thank you so much for your valuable suggestions and that tutorial also helped :) but as I'm a computer science student I have no idea about which algorithm is better.I have to visualize the secondary structure of RNA and I can't user already made tools or softwares I have to do it on my own, so can you please suggest which algorithm is the best?

[Cjt]

So what is your real task? To visualize the structure or to compute it from nucleotide sequence? 2D or 3D?

[rail.suleymanov]

Good afternoon! There's probably an error on slide 11 - there should be "1" on row 9, column 13 instead of "2" (if I'm right). Thank you.

Answer 2

[Asaf]

You can find a good explanation in Durbin et al's book "Biological sequence analysis" on page 269 and on. I can't understand why do you want to use Nussinov's algorithm when you have much accurate algorithms like Mfold and RNAfold?

[Michael]

It's maybe a teaching example for a dynamic programming problem?

[Shane]

Thank you Asaf but my task is to visualize the RNA secondary structure and as I'm a computer science student, I really do not know much about which algorithm is better.Can you please suggest one? seems Mfold is an already written tool, I can't be using them.

[Asaf]

Since this is an exercise, Nussinov is the most simple algorithm to implement. Have a look on the CFG (context free grammar) form of the algorithm (in Durbin's book), it might be easier for you to understand or implement, depending on the libraries you can use. I've added a link to an online version of the book.

Answer 3

[Michael]

There seems to be a wikipedia entry only in German, I hope the information given there is correct: http://de.wikipedia.org/wiki/Nussinov-Algorithmus

I can translate the essential part:

Initialization:

N[i,i] = 0, 0 <= i <n

N[i,i − 1] = 0,0 < i < n

Substring s[i,i] of length 1 and the empty Substring s[i,i − 1] of length 0 contain max 0 basepairs.

Recursion step

Where n is the length of input sequence s, N is a n x n matrix, sigma(i,j) function that is 1 if s[i] is complementary to s[j] and 0 otherwise. No overlapping basepairs allowed.

Hope this helps

[Shane]

Thank you so much Michael :)

Answer 4

[audrius.meskauskas]

Described also here, contains all formulas, interactive demo and Java source code.