Accuracy of RNA Structure Prediction Depends on the Pseudoknot Grammar - Eggers, Dustyn; Höner zu Siederdissen, Christian; Stadler, Peter F. (Anais do Simpósio Brasileiro de Bioinformática (BSB); 2022: Anais do XV Simpósio Brasileiro de Bioinformática, 2022)
Most models for pseudoknotted RNA structures can be described by multi-context free grammars (MCFGs) and thus are amenable to dynamic programming algorithms. They diﬀer strongly in their deﬁnition 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 deﬁnition already exclude more complex pseudoknotted structures. A systematic analysis of the impact of the grammar, however, is diﬃcult since available implementations use incomparable energy parameters. We show here that Algebraic Dynamic Programming over MCFGs naturally disentangles energy models (as speciﬁed by the evaluation algebra) and the deﬁnition of search space deﬁned by a MCFG. Preliminary computational experiments indicate that the choice of the grammar has an important impact already for short RNA sequences.