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.

Reversible Graph Grammar for RNA

MAMUYE, ADANE LETTA;MERELLI, Emanuela;TESEI, Luca
2016-01-01

Abstract

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.
2016
9788867680269
5th Scientific Day of School of Science and Technology, UNICAM "La divulgazione delle conoscenze scientifiche nella società moderna"
274
File in questo prodotto:
File Dimensione Formato  
Abstrac.pdf

accesso aperto

Descrizione: Abstract
Tipologia: Documento in Pre-print
Licenza: DRM non definito
Dimensione 75.88 kB
Formato Adobe PDF
75.88 kB Adobe PDF Visualizza/Apri
2016_booklet.pdf

accesso aperto

Descrizione: Book of Abstracts 5th Scientific Day (vedi a pag. 37)
Tipologia: Versione Editoriale
Licenza: DRM non definito
Dimensione 2.79 MB
Formato Adobe PDF
2.79 MB Adobe PDF Visualizza/Apri
SD_8giugno.pdf

accesso aperto

Descrizione: Locandina evento
Tipologia: Altro materiale allegato
Licenza: DRM non definito
Dimensione 527.47 kB
Formato Adobe PDF
527.47 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11581/401581
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact