Accuracy of RNA Structure Prediction Depends on the Pseudoknot Grammar

• Dustyn Eggers Universität Leipzig
• Christian Höner zu Siederdissen Universität Leipzig / Friedrich Schiller University Jena https://orcid.org/0000-0001-9517-5839
• Peter F. Stadler Universität Leipzig / Max Planck Institute for Mathematics in the Sciences / University of Vienna / Universidad Nacional de Colombia / Santa Fe Institute https://orcid.org/0000-0002-5016-5191

Resumo

Most models for pseudoknotted RNA structures can be described by multi-context free grammars (MCFGs) and thus are amenable to dynamic programming algorithms. They differ strongly in their definition of admissible structures and thus the search space over which structures are optimized. The accuracy of structure prediction can be expected to depend on choice of the MCFG: models that are too inclusive likely over-predict pseudoknots, while restrictive models by their definition already exclude more complex pseudoknotted structures. A systematic analysis of the impact of the grammar, however, is difficult since available implementations use incomparable energy parameters. We show here that Algebraic Dynamic Programming over MCFGs naturally disentangles energy models (as specified by the evaluation algebra) and the definition of search space defined by a MCFG. Preliminary computational experiments indicate that the choice of the grammar has an important impact already for short RNA sequences.

Palavras-chave: RNA Pseudoknots, Multi-context free grammar, Algebraic dynamic programming, ADPfusion