Physics – Biological Physics
Scientific paper
1998-07-27
Physics
Biological Physics
34 pages, 18 figures. Uses LaTex and metapost
Scientific paper
We describe a dynamic programming algorithm for predicting optimal RNA secondary structure, including pseudoknots. The algorithm has a worst case complexity of ${\cal O}(N^6)$ in time and ${\cal O}(N^4)$ in storage. The description of the algorithm is complex, which led us to adopt a useful graphical representation (Feynman diagrams) borrowed from quantum field theory. We present an implementation of the algorithm that generates the optimal minimum energy structure for a single RNA sequence, using standard RNA folding thermodynamic parameters augmented by a few parameters describing the thermodynamic stability of pseudoknots. We demonstrate the properties of the algorithm by using it to predict structures for several small pseudoknotted and non-pseudoknotted RNAs. Although the time and memory demands of the algorithm are steep, we believe this is the first algorithm to be able to fold optimal (minimum energy) pseudoknotted RNAs with the accepted RNA thermodynamic model.
Eddy Sean R.
Rivas Elena
No associations
LandOfFree
A dynamic programming algorithm for RNA structure prediction including pseudoknots does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A dynamic programming algorithm for RNA structure prediction including pseudoknots, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A dynamic programming algorithm for RNA structure prediction including pseudoknots will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-382962