Context-free Grammars and RNA Secondary Structure Prediction
Markus E. Nebel and Anika Schulz
from: Genome Analysis: Current Procedures and Applications (Edited by: Maria S. Poptsova). Caister Academic Press, U.K. (2014)
For a long time, computational methods for RNA secondary structure prediction were typically based on more or less complex models of the free energy-defined by experimentally derived thermodynamic parameters and incomplete free energy rules. However, due to the problems even of comprehensive state-of-the-art thermodynamic models to capture some important, non-energetic influences on sequence folding, an attractive alternative is to use stochastic approaches with parameters estimated from growing databases of structural RNAs. This motivated the development of a competing methodology towards computational RNA structure prediction analysis that builds on principles of probabilistic modeling of the class of possible foldings rather than on incomplete free energy models. Such probabilistic prediction approaches are generally based on more or less powerful extensions of the concept of traditional context-free grammars that are indeed able to capture the specific structural information collected in an arbitrary database of reliable RNAs. This chapter deals with such probabilistic RNA folding approaches based on context-free modeling. Note that we here call an approach probabilistic if and only if it abstracts from general thermodynamic models and instead tries to learn about the structural behavior of the molecules by training (a manageable number of) probabilistic parameters from trusted RNA structure databases. In that sense, partition function approaches, even if providing pairing probabilities, are not assumed to be probabilistic read more ...