Predicting RNA secondary structures with pseudoknots by MCMC sampling.
The most probable secondary structure of an RNA molecule, given the nucleotide sequence, can be computed efficiently if a stochastic context-free grammar (SCFG) is used as the prior distribution of the secondary structure. The structures of some RNA molecules contain so-called pseudoknots. Allowing all possible configurations of pseudoknots is not compatible with context-free grammar models and makes the search for an optimal secondary structure NP-complete. We suggest a probabilistic model for RNA secondary structures with pseudoknots and present a Markov-chain Monte-Carlo Method for sampling RNA structures according to their posterior distribution for a given sequence. We favor Bayesian sampling over optimization methods in this context, because it makes the uncertainty of RNA structure predictions assessable. We demonstrate the benefit of our method in examples with tmRNA and also with simulated data. McQFold, an implementation of our method, is freely available from http://www.cs.uni-frankfurt.de/~metzler/McQFold.
Metzler
Dirk
D
Institut für Informatik, J. W. Goethe-Universität, Robert Mayer Str. 11-15, 60325 Frankfurt am Main, Germany. metzler@cs.uni-frankfurt.de
Nebel
Markus E
ME
D019295:Computational Biology / Q000379:methods*; D008390:Markov Chains; D008956:Models, Chemical; D009010:Monte Carlo Method; D009690:Nucleic Acid Conformation; D012333:RNA, Messenger / Q000737:chemistry* / Q000235:genetics; D012984:Software; D014210:Treponema pallidum / Q000235:genetics
D012333:RNA, Messenger