We are considering sequential membrane systems and molecular dynamics from the viewpoint of Markov chain theory. The configuration space of these systems (including the transitions) is a special kind of directed graph, called a pseudo-lattice digraph, which is closely related to the stoichiometric matrix. Taking advantage of the monoidal structure of this space, we introduce the algebraic notion of precycle. A precycle leads to the identification of cycles by means of the concept of defect, which is a set of geometric constraints on configuration space. Two efficient algorithms for evaluating precycles and defects are given: one is an algorithm due to Contejean and Devie, the other is a novel branch-and-bound tree search procedure. Cycles partition configuration space into equivalence classes, called the communicating classes. The structure of the communicating classes in the free regime–where all rules are enabled–is analyzed: testing for communication can be done efficiently. We show how to apply these ideas to a biological regulatory system.

Muskulus, M., Besozzi, D., Brijder, R., Cazzaniga, P., Houweling, S., Pescini, D., et al. (2007). Cycles and communicating classes in membrane systems and molecular dynamics. THEORETICAL COMPUTER SCIENCE, 372(2-3), 242-266 [10.1016/j.tcs.2006.11.027].

Cycles and communicating classes in membrane systems and molecular dynamics

BESOZZI, DANIELA;CAZZANIGA, PAOLO;PESCINI, DARIO;
2007

Abstract

We are considering sequential membrane systems and molecular dynamics from the viewpoint of Markov chain theory. The configuration space of these systems (including the transitions) is a special kind of directed graph, called a pseudo-lattice digraph, which is closely related to the stoichiometric matrix. Taking advantage of the monoidal structure of this space, we introduce the algebraic notion of precycle. A precycle leads to the identification of cycles by means of the concept of defect, which is a set of geometric constraints on configuration space. Two efficient algorithms for evaluating precycles and defects are given: one is an algorithm due to Contejean and Devie, the other is a novel branch-and-bound tree search procedure. Cycles partition configuration space into equivalence classes, called the communicating classes. The structure of the communicating classes in the free regime–where all rules are enabled–is analyzed: testing for communication can be done efficiently. We show how to apply these ideas to a biological regulatory system.
Articolo in rivista - Articolo scientifico
Membrane systems; Communicating classes; Molecular dynamics; Cycles in digraphs; Vector addition systems
English
2007
372
2-3
242
266
none
Muskulus, M., Besozzi, D., Brijder, R., Cazzaniga, P., Houweling, S., Pescini, D., et al. (2007). Cycles and communicating classes in membrane systems and molecular dynamics. THEORETICAL COMPUTER SCIENCE, 372(2-3), 242-266 [10.1016/j.tcs.2006.11.027].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

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/10281/21592
Citazioni
  • Scopus 5
  • ???jsp.display-item.citation.isi??? 4
Social impact