Stochastic modeling of RNA pseudoknotted structures: a grammatical approach.
BACKGROUND
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 complexity 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 approach 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. Technically, 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 structures to allow the prediction of consensus structures by comparative analysis and structural homology recognition in database searches.
Cai
Liming
L
Department of Computer Science, The University of Georgia, Athens, Georgia 30602, USA. cai@cs.uga.edu
Malmberg
Russell L
RL
Wu
Yunzhou
Y
D000465:Algorithms; D020029:Base Pairing; D001483:Base Sequence; D001665:Binding Sites; D005240:Feasibility Studies; D008956:Models, Chemical; D008958:Models, Molecular; D015233:Models, Statistical; D008969:Molecular Sequence Data; D009323:Natural Language Processing; D009690:Nucleic Acid Conformation; D010363:Pattern Recognition, Automated; D012313:RNA / Q000737:chemistry*; D016415:Sequence Alignment / Q000379:methods*; D017423:Sequence Analysis, RNA / Q000379:methods*; D012689:Sequence Homology, Nucleic Acid; D013269:Stochastic Processes
D012313:RNA