Stochastic Context-free Grammars and RNA Secondary Structure Prediction
James W. J. Anderson
from: Genome Analysis: Current Procedures and Applications (Edited by: Maria S. Poptsova). Caister Academic Press, U.K. (2014)
Prediction of RNA secondary structure from a single sequence, or an alignment of sequences, is a core problem in bioinformatics. Many approaches to RNA secondary structure prediction have been attempted, and probabilistic methods using stochastic context-free grammars (SCFGs) have been one of the more successful tries. In particular, SCFGs can be combined with a molecular evolution model to produce consensus structure predictions which more accurately predict RNA secondary structure than when considering single-sequence prediction. The use of SCFGs in RNA secondary structure prediction, and the potential for further developments make for a truly interesting topic. In this chapter we discuss the application of SCFGs to RNA secondary structure prediction, from a single sequence, or a single fixed alignment. An introduction to RNA secondary structure prediction is given, some technical issues for SCFGs, such as normal forms and grammar design, are discussed, methods are shown for estimating SCFG parameters. Methods are shown for predicting RNA secondary structures, and some measures are given for analysing SCFG variability. Finally, a brief discussion concerning their predictive quality is had, with some suggestions for further work and web resources given read more ...