Reversible Graph Grammar for RNA

Graph rewriting formalism is widely used for modelling the dynamics of complex systems in direct and intuitive way. It has been used in computational biology in different contexts, such as RNA tertiary structure motifs encoding and biochemical systems modelling. Besides, in our previous work, we have shown how double pushout (DPO) graph rewriting is used to model the RNA folding as a self adaptive system within S[B] paradigm. Accordingly, the graph transformation encodes simultaneously the RNA functional behaviour and its structure. DPO rewriting rules are applicable whenever the application conditions (identification conditions and dangling conditions) and negative applications conditions are satisfied. The specified conditions can also be used to ensure the reversibility characteristics of DPO. The reversibility of DPO rule has been applied to model dining philosophers problem. Since DPO rules are guaranteed to be reversible (backtrack), we can perform the admissible rewriting rules to model the folding and unfolding pathways of RNA. The backtracking mechanism backtracks out of the dead-ends by undoing all effects of graph rewriting sequences and by selecting the remaining possible rewritings to derive all the possible RNA secondary structures. In this study, as extension of our previous work, we introduce reversible graph grammar to formalize and complete the definition of the B and S levels of the S[B]. The B-level is represented as a label transition system (LTS) in which the sate space represents the entire folding evolution of the given RNA molecule. The structural level S, represented as a state machine which controls the adaptation dynamics of the B level towards the lowest minimum free energy secondary structure based on state and transition constraints.