Folding Algorithm

General Science Discussion
1

Hello Everyone,

I am curious to know how the folding algorithm of this game works. As far as I know it should be a simplification of some deeper quantum model but I am not sure. Could someone give me more details?

Thanks!

JM

1 Like
2

Hi Jean-Michel,

Secondary structure prediction is far from being a simplification of some quantum model, as far as I can tell. The currently most accurate softwares (including the one in use in the game) are based on the nearest neighbor model. As detailed at http://rna.urmc.rochester.edu/NNDB/heā€¦ the thermodynamic stability of a motif is assumed to be determined by the ā€˜elementsā€™ enclosing motifs, essentially (canonical and wobble) base pairs, eventually enclosing loops. A common simplification consists in ignoring pseudoknots, which allows for solving the problem in polynomial time using dynamic programming.

Hope this helps

3

Hi Nando,

this is very helpful! Many thanks for the explanation and for the link!

I appreciate,

JM

4

oh, and I forgot to mention: in terms of QM, the only related calculation I ever found was on http://www.begdb.com/ and was a prediction of the stacking interaction between Cytosines and Adenines, some of them eventually protonated. Unfortunately, I canā€™t seem to find the data againā€¦ In any case, this was still very far from a prediction of any kind of secondary structure.

5

I am frankly amazed by this nearest neighbor model. It seems to be very fast and does not involve first-principle simulations. Therefore, some other questions:

Is this model always accurate? I mean, compared to a full fledged quantum simulation, how good are the predictions made by this model? Are they always in agreement?

6

Depending on the ā€œclassesā€ of RNA sequences, and specially depending on their length, accuracy vary from reported 90+% down to 50% and sometimes less. Also, algorithms ignoring pseudoknots are necessarily going to mispredict the secondary structure of any sequence that tends to create these motifs.

As you can see, there are quite a few limitationsā€¦

7

Now the thing makes sense to me. Many thanks for helping about that!

So, would that mean that when I try to fold my RNA in the game, sometimes I may have innacurate folding because of the model? Or do the developers make sure that the only available RNAs in the game are the ones that belong to the range of applicability of the nearest neighbor model?

8

The game simply uses whatever secondary structure prediction the folding engine makes for the given primary structure (the sequence). And there are no guarantees about the accuracy of that prediction.

I just found this: http://dx.doi.org/10.1007/978-1-61779ā€¦
It looks like a good starting point (specially, one of the authors, Matthew Seetin used to be part of the EteRNA team), unfortunately I donā€™t have access, so I canā€™t say more about it.

9

This is a VERY good link, thank you much about that!

I love this game and I want to understand it in details, so thanks again!

10

My pleasure Jean-Michel :slight_smile:

12

There is a peak inside the book option:

14

I will download the paper from my office as I work in a university. Many thanks anyway :slight_smile:

15

What a fantastic conversation. A must read for those interested in understanding RNA and the concepts of RNA folding and its secondary structure. Good stuff! Nando and Jean-Michel. I also like the link to the nearest neighbor model description.