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.
|Titolo:||Cycles and communicating classes in membrane systems and molecular dynamics|
BESOZZI, DANIELA (Secondo)
|Parole Chiave:||Communicating classes; Cycles in digraphs; Membrane systems; Molecular dynamics; Vector addition systems|
|Settore Scientifico Disciplinare:||Settore INF/01 - Informatica|
|Data di pubblicazione:||15-mar-2007|
|Digital Object Identifier (DOI):||10.1016/j.tcs.2006.11.027|
|Appare nelle tipologie:||01 - Articolo su periodico|