Topology and prediction of RNA pseudoknots
Abstract
Motivation: Several dynamic programming algorithms for predicting RNA structures with pseudoknots have been proposed that differ dramatically from one another in the classes of structures considered. Results: Here, we use the natural topological classification of RNA structures in terms of irreducible components that are embeddable in the surfaces of fixed genus. We add to the conventional secondary structures four building blocks of genus one in order to construct certain structures of arbitrarily high genus. A corresponding unambiguous multiple context-free grammar provides an efficient dynamic programming approach for energy minimization, partition function and stochastic sampling. It admits a topology-dependent parametrization of pseudoknot penalties that increases the sensitivity and positive predictive value of predicted base pairs by 10–20% compared with earlier approaches. More general models based on building blocks of higher genus are also discussed.
Additional Information
© The Author 2011. Published by Oxford University Press. Received October 14, 2010; Revision received January 12, 2011; Accepted February 15, 2011. First published online: February 17, 2011. This work was supported by the 973 Project of the Ministry of Science and Technology; the PCSIRT Project of the Ministry of Education; National Science Foundation of China to C.M.R. and his lab; Deutsche Forschungsgemeinschaft (projects STA 850/2-1 & STA850/7-1); the European Union FP-7 project QUANTOMICS (no. 222664) to P.F.S. and his lab. J.E.A. and R.C.P. are supported by QGM, the Centre for Quantum Geometry of Moduli Spaces, funded by the Danish National Research Foundation. Conflict of Interest: none declared.Additional details
- Eprint ID
- 23498
- DOI
- 10.1093/bioinformatics/btr090
- Resolver ID
- CaltechAUTHORS:20110429-103523602
- Ministry of Science and Technology 973 Project
- Ministry of Education PCSIRT Project
- National Science Foundation of China
- STA 850/2-1
- Deutsche Forschungsgemeinschaft
- STA850/7-1
- Deutsche Forschungsgemeinschaft
- 222664
- European Union FP-7 project QUANTOMICS
- Danish National Research Foundation Centre for Quantum Geometry of Moduli Spaces (QGM)
- Created
-
2011-05-02Created from EPrint's datestamp field
- Updated
-
2021-11-09Created from EPrint's last_modified field