Stochastic modeling of RNA pseudoknotted structures: a grammatical approach
A PHP Error was encountered
Message: Undefined index: id
Line Number: 218
Motivation: Modeling RNA pseudoknotted structures remains challenging. Methods have previously been developed to model RNA stem-loops successfully using stochastic context-free grammars (SCFG) adapted from computational linguistics; however, the additional com- plexity of pseudoknots has made modeling them more difficult. Formally a context-sensitive grammar is required, which would impose a large increase in complexity. Results: We introduce a new grammar modeling ap- proach for RNA pseudoknotted structures based on parallel communicating grammar systems (PCGS). Our new approach can specify pseudoknotted structures, while avoiding context-sensitive rules, using a single CFG synchronized with a number of regular grammars. Techni- cally, the stochastic version of the grammar model can be as simple as an SCFG. As with SCFG, the new approach permits automatic generation of a single-RNA structure prediction algorithm for each specified pseudoknotted structure model. This approach also makes it possible to develop full probabilistic models of pseudoknotted struc- tures to allow the prediction of consensus structures by comparative analysis and structural homology recognition in database searches. Availability: Prototypes for the automated pseudoknot prediction algorithm are available upon request.