A Modeling Approach Based on P Systems with Bounded Parallelism

A Modeling Approach Based on P Systems with Bounded Parallelism Francesco Bernardini1, Francisco J. Romero-Campero2, Marian Gheorghe3, and Mario J. P´erez-Jim´enez2 1Leiden Institute of Advanced Computer Science University of Leiden Niels Bohrweg 1, 2333 CA Leiden, The Netherlands [email protected] 2Research Group on Natural Computing Department of Computer Science and Artificial Intelligence University of Seville, Avda. Reina Mercedes, 41012 Sevilla, Spain {fran,marper}@cs.us.es 3Department of Computer Science, The University of Sheffield Regent Court, Portobello Street, Sheffield S1 4DP, UK [email protected] Abstract. This paper presents a general framework for modelling with membrane systems that is based on a computational paradigm where rules have associated a finite set of attributes and a corresponding function. Attributes and functions are meant to provide those extra features that allow to define different strategies to run a P system. Such a strategy relying on a bounded parallelism is presented using an operational approach and applying it for a case study presenting the basic model of quorum sensing for Vibrio fischeri bacteria. 1 Introduction In 1998, Gheorghe P˘aun initiated the field of research called membrane computing with a paper firstly available on the web and later published in [19]. Membrane computing aims at defining computational models which abstract from the functioning and structure of the cell. In particular, membrane computing starts from the observation that compartmentalization through membranes is one of the essential features of (eucaryotic) cells. Unlike bacterium, which generally consists of a single intracellular compartment, a(n) (eucaryotic) cell is sub-divided into functionally distinct compartments. Thus, a class of computing devices called membrane systems, or P systems, are defined [19], which have three essential features: a membrane structure consisting of a hierarchical arrangement of several compartments defined as regions delimited by membranes; objects assigned to regions; and rules assigned to the regions of the membrane structure, acting upon the objects inside. In particular, each region is supposed to contain a finite set of rules and a finite multiset (or set) of objects. Rules encode generic processes for producing/consuming objects and for moving objects from one region to the other. Objects are described either as symbols from a given alphabet or as strings over a given alphabet. The application of the rules is performed in a non-deterministic maximally parallel manner: all the applicable rules that should be used to modify existing objects must be applied, and this is done in parallel for all membranes. Since this model was introduced for the first time in 1998, many variants of membrane systems have been proposed and studied – a comprehensive bibliography of P systems can be found at the P systems web page [29]. The most investigated membrane system topics are related to the computational power of different variants, their capabilities to solve hard problems, like NP-complete problems, decidability, complexity aspects and hierarchies of classes of languages produced by these devices. Membrane computing represents nowadays a research area of a larger interdisciplinary field called natural computing, that involves scientists studying the emergence of new computational paradigms inspired from the behavior of various natural phenomena. In the same time there is a growing interest in applying mathematical and computational paradigms to model real natural systems. Computational biology is such a field, where mathematical and computational models of biological systems are designed for the analysis and simulation of the behavior of these systems. Biological modeling has involved standard continuous and stochastic mathematical approaches, as well as discrete models. Standard mathematical models with their simulation techniques have proved to be powerful tools for understanding the dynamics of biological systems (e.g., see [25], [26]). Discrete modeling instead advocates the use of different formalisms taken from various areas of computer science (e.g., formal grammars [6], Petri nets [16], X machines [9], [27], process algebra [24], [3], statecharts [15], etc.) to develop computational models of biological systems. This paper presents a general framework for modeling with membrane systems that is based on a model of P systems where rules have associated a finite set of attributes and a corresponding function. Attributes and functions are meant to provide those extra features which are necessary to close the “gap” between the abstractness of more standard P system models and the “reality” of the phenomenon to be modeled (Section 2). The behavior of such P systems is defined in Section 3 in terms of bounded parallelism, which precisely formalizes the idea of a membrane system as a system where a certain number of components evolve in parallel at the same time by means of a certain number of rules applied inside each one of these components. Then, in Section 4, as a particular instance of the general model, we consider P systems where rules have associated a real constant as an attribute and the corresponding function is used to compute a value of a probability depending on this constant and on certain multisets of objects defining the context where the rule is applied; for this particular variant of P systems, we also define a strategy for the application of the rules which, in each step, selects the next rule to be applied depending on the aforementioned values of probabilities. Finally, in Section 5, as a case study, we present a P system model for the quorum sensing mechanism of bacterial cell-to-cell communication. 2 The Model Usually a P system is defined as a hierarchical arrangement of a number of membranes identifying a corresponding number of regions inside the system, and with these regions having associated a finite multiset of objects and a finite set of rules. Moreover, one can also consider membrane systems where the underlying structure is defined as an arbitrary graph like in tissue P systems [20], and in population P systems [1]. In this paper, we only focus on membrane systems of the former type where the underlying structure is defined as being a tree of nested membranes. Rules of many different forms have been considered for membrane systems in order to encode the operation of modifying the objects inside the membranes and the operation of moving objects from one place to the other. In particular, for communicating objects, one can use either the targets here, in, out,or symport/antiport rules, or boundary rules [20]. Here, in order to capture the features of most of these rules, we consider rules of the form: u[v]→u[v](1) with u, v, u,vsome finite multisets. These rules are generalized boundary rules operating as multiset rewriting rules which simultaneously replace a multiset of objects placed outside the membrane and a multiset of objects placed inside the membrane with two new multisets placed in the same places. In this way, we are able to capture in a concise way the essential features of transformation and communication of objects usually considered in the area of membrane computing. Moreover, from a modeling point of view, rules like (1) allow us to express any sort of interactions occurring at the membrane level, like, for instance, the binding of a signal molecule to a specific receptor which occurs at cell-surface level (e.g., see [21]). We associate to each rule a finite set of attributes in order to be able to capture specific quantitative aspects of the phenomenon to be modeled. Specifically, these attributes are used by rules as different reaction rates and/or different probabilities which overall affects the strategy of the application of the rules. Definition 1 (program). Let V,K be alphabets, let Dbe a set (possibly infinite), and let Abe a finite subset of D.ThesetDis called the set of values and the set Ais called the set of attributes.LetF={f1,f 2,...,f p}be a finite set of functions such that, for all 1≤t≤n,ft:P(D)×V∗×V∗×V∗×V∗−→ D with P(D)the family of all subsets of D.Aprogram (over V,K,D,A,F)is a construct u[v]→u[v],σ,f ilwhere: u, v, u,v∈O∗,σ⊆A,fi∈F,for some 1≤i≤p,andl∈K. Thus, a program consists of a rule, a finite set of attributes and a function which, given this set of attributes and four multisets, returns a value from a certain chosen set. In particular, the first two multisets are usually considered as being the two multisets placed on the left side of the rule; the two remaining multisets are instead supposed to be the multisets placed respectively inside and outside a given membrane. That is, each function is expected to compute a particular value depending on the rule and on the contents of the outside and the inside regions that define the “context” where the rule is applied. Here our main focus is in modeling systems consisting of many different biochemical reactions distributed across different compartments. Therefore, the following interpretation for programs will be predominantly used throughout the paper. Objects represent chemicals and multisets of objects are interpreted as “bags” or “soup” of chemicals. Rules model transformations involving these chemicals. Each rule has associated a finite set of attributes and a corresponding function defining particular properties that affect the behavior of the rule itself; these properties are usually said to define the reactivity of the rule (e.g., see [2], [21]). Moreover, since we want to have systems consisting of many different compartments, we assign to each program a label to differentiate the set of programs from one compartment to the other. Remark 1. Although the aforementioned interpretation will be mainly used in this paper, it is not the unique possible and that is why we introduce the notions of set of values and set of attributes in a more generic fashion. For instance, one may use attributes to model properties inherent to the membranes and may use the corresponding function to update these attributes every time a rule is applied. Alternatively, one may consider hybrid models where the attributes represent continuous variables which are updated through the use of certain functions (e.g., see [9] for hybrid X machines, and [16] for hybrid Petri nets). Next, we introduce the notion of P specification which makes explicit the basic components necessary to define a particular P system model. Definition 2 (P specification). AP specification is a construct S=(V,K,D,A,F,P) where: 1. Vis an alphabet; its elements are called objects; 2. Kis an alphabet; its elements are called labels; 3. Dis a set of values; 4. A⊆Dis a finite set of attributes; 5. F={f1,f 2,...,f p}is a finite set of functions as in Definition 1. 6. Pis a finite set of programs over V,K,D,A,Fof the form specified in Definition 1. Thus, a P specification provides a “scheme” for the definition of P systems with programs defined over the sets V,K,D,A,andF. In particular, from a modeling point of view, we can say that the alphabet Vof objects specifies different “sorts” for the chemicals present inside a certain system, the alphabet Kof labels specifies different “types” for the membranes possibly present inside a certain system, and the set Dspecifies the domain of interpretations for the attributes and the corresponding functions. A P system is then obtained by augmenting a certain P specification with an initial configuration. In particular, we recall that the structure of a P system is given by a hierarchical arrangement of some n≥1 membranes labeled in an one-to-one manner with values in {1,2,...,n}[20]. However, since here we use labels from a given alphabet to identify the “type” of a membrane, the value from {1,2,...,n}assigned to a membrane is called the index of the membrane; the membrane structure is then said to be indexed by the values 1,2,...,n. Definition 3 (P system). APsystemofdegreen≥1is a construct: Π=(S,μ,M 1,M 2,...,M n) where S=(V,K,D,A,F,P)is a P specification with V,K,D,A,F,P as in Definition 2, μa membrane structure containing nmembranes indexed by the values 1,2,...,n, and, for all 1≤i≤n,Mi=(wi,l i),withwi∈V∗the content of membrane iand li∈Kthe label of membrane i. As usual, a P system of degree n≥1 is defined as consisting of a membrane structure containing nmembranes. Each membrane contains a multiset of objects and gets assigned a label from the set K. This latter symbol is particularly useful for retrieving from the given specification the set of programs which can be used inside each membrane in the system. In other words, this label precisely identifies the “type” of the membrane in terms of the rules which can be applied inside. Most of the P system variants utilize a maximal parallel rewriting manner [20]. This means, in each step, in each membrane, all the objects that can evolve by means of some rules must evolve in parallel, with the only restriction that the same occurrence of the same object cannot be used by more than one rule at a time. That is, in each step, for each membrane, a maximal set of rules to be applied is non-deterministically selected by making sure that no further rules can be applied to the objects left inside the membranes. In this paper we will introduce a mechanism to bound the number of applications of the rules and the number of membranes that will evolve in a step. In this respect, the key issues that need to be addressed in order to define a strategy for the application of the rules in a P system are: a) how to select the next rule to be applied inside a given membrane, b) how many different rules can be applied in parallel at the same time inside the membrane, and c) how many different membranes can evolve in parallel at the same time. 3 Parallelism of Type (k, q) We formalize here the notion of a transition step in P systems evolving in a (k,q)−parallel manner: in each step, at most kmembranes evolve in parallel at the same time and, inside each membrane, at most qrules are applied in parallel at the same time. Moreover, in a given step, if kmembranes can evolve by means of some rules, then exactly kmembranes must evolve in parallel in that step; inside each membrane, if qrules can be applied, then exactly qrules are applied in parallel inside that membrane. In other words, parallelism of type (k,q)is assumed to be maximal and exhaustive with respect to kand q. Our formalization makes use of some concepts of the operational semantics for P systems introduced in [5] and it is based on the explicit assignment of the rules contained to the programs to the respective membranes; this is obtained by assigning the index of a membrane to each object possibly present inside the system. Let Π=(S,μ,M 1,M 2,...,M n)withS=(V,K,D,A,F,P)andMi= (wi,l i), for all 1 ≤i≤n, be a P system as specified in Definition 3. The following extra notions are associated to the P system Π: –the indexed alphabet (of Π)denoted by ¯ Vis the set ¯ V={ai|a∈V,1≤ i≤n}; –for all 1 ≤i≤n,andforallu∈V∗,thei-version of uis the multiset denoted by ui∈¯ Vsuch that, for all a∈V, for all 1 ≤j=i≤n,|ui|ai=|u|aand |uaj|=0; –the set of membrane rules (of Π)is the set of programs denoted by MR and such that: MR ={ujvi→u jv i|u[v]→u[v],σ,fli∈P, j = upper(μ, i)},whereupper(μ, i) is a function returning for a given membrane structure μ, the membrane containing the region i. Thus, the indexed alphabet of Πis the alphabet of symbols from Vwith attached indexes of the membranes in the system. The i-version of a multiset u,with 1≤i≤nand u∈V∗, is the multiset obtained by assigning the index ito all the objects in u.ThesetMR explicitly identifies, for each membrane, the set of rules which can be used inside that membrane by replacing the multisets in the rules with the corresponding indexed versions. In particular, for all 1 ≤i≤n, thesetofruleswhichcanbeusedinsidemembraneiare the rules contained in programs labeled by li. Moreover, for all 1 ≤i≤n,amultiset of rules for membrane i, is a collection of membrane rules r1,r 2,...,r ki,withki≥0 and with these rules not necessarily distinct, such that, for all 1 ≤h≤ki,rhis a membrane rule in MR of the form ujvi→u jv iwith vi=λ.Thesize of Ri, denoted by |Ri|,isthenumberofrules in Ri. Amultiset of rules in Πis a collection of membranes rules of the form R1, R2,...,R nsuch that, for all 1 ≤i≤n,Riis a multiset of rules for membrane i. Then, a configuration of a P system is defined as being a multiset over the indexed alphabet. Definition 4 (Configuration). Let Π=(S,μ,M 1,M 2,...,M n)be a P system as in Definition 3 where S=(V,K,D,A,F,P)and Mi=(wi,l i), for all 1≤ i≤n.Aconfiguration (of Π)is a multiset C∈¯ V.Theinitial configuration (of Π), denoted by C0,isthemultisetu1u2...u nsuch that, for all 1≤i≤n,uiis the i-version of wi. Notice that, with the notions introduced in this section so far, we have essentially reduced a P system of degree n≥1 to an equivalent one of degree 1 where the objects have an index specifying the membrane which they are assigned to in the original system. Thus, the behavior of such a system can be defined as being a multiset rewriting system where the rules are selected according to a certain strategy depending on the indexes assigned to the objects. In fact, according to Definition 4, a configuration of a P system is just a multiset of objects and the membrane rules are usual multiset rewriting rules. To this aim, we need first to introduce the concepts of i-irreducibility and the concept of (C, k, q)-consistency. Definition 5 (i-irreducibility). Let Π=(S,μ,M 1,M 2,...,M n)be a P system as in Definition 3 where S=(V,K,D,A,F,P),andletβbe a finite multiset over ¯ V.LetMR be the set of membrane rules in Π. Given 1≤i≤n, we say that βis i-irreducible if, for all ujvi→u jv i∈MP with vi=λ, we have β ujvi. Thus, given a P system of degree n≥1, for all 1 ≤i≤n, a multiset over the indexed alphabet is i-irreducible if there are no more rules which can be applied to the objects with index i. In other words, if we interpret these objects as being the content of membrane i, this means that there are no more rules that can be applied to the objects placed inside membrane i. Definition 6 ((C, k, q)-consistency). Let Π=(S,μ,M 1,M 2,...,M n)be a P system as in Definition 3 where S=(V,K,D,A,F,P),andletRbe a multiset of rules in Π.LetC∈¯ V∗be a configuration of Π,andletk,q =0be positive integers with k≤n. We say that Ris (C, k, q)-consistent if there exists {i1,i 2,...,i g}⊆{1,2,...,n}with g≤ksuch that Rcanbewrittenasacollection of rules Ri1,R i2,...,R igwith Riha multiset of rules for membrane ih, and 1. if g<k,then,foralli∈({1,2,...,n}\{i1,i 2,...,i g}),Cis i-irreducible; 2. for all i∈{i1,i 2,...,i k},ifRi=u1 jv1 i→z1 jw1 i,...,u p jvp i→zp jwp i,thenwe have C=xu 1 jv1 i...u p jvp i,forsomex∈¯ V∗; 3. for all i∈{i1,i 2,...,i k},|Ri|≤q,andifRi=u1 jv1 i→z1 jw1 i,..., u p jvp i→ zp jwp iwith p<q,thenC=xu 1 jv1 i...u p jvp i,forsomei-irreducible x∈¯ V∗. The notion of (C, k, q)-consistency precisely characterizes the multisets of rules which can be applied to a given configuration Cin accordance to the parallelism of type (k,q). In fact, such a multiset of rules must contain a multiset of rules for at most kdistinct membranes; if there are not kmembranes that can evolve by means of some rules, then a smaller but maximal number of membranes must be selected (Condition 1 of Definition 6). The rules contained in the selected multiset must be applicable to the objects currently contained inside each membrane (Condition 2 of Definition 6). Moreover, for each membrane, at most qrules must be selected; if inside some membrane there are less than qrules that can be applied, then all of them must be applied (Condition 3 of Definition 6). Therefore, in order to perform a (k,q)-parallel step in a given P system, it is necessary to first select a multiset of rules Rto be applied to the current configuration Csuch that Ris (C, k, q)-consistent. In this respect, we assume to have defined an algorithm to select programs and membranes Ak,q such that, given a configuration of a P system Πand its set of programs, returns a multiset of rules which is (C, k, q) consistent. In all the previous sections, this selection has been defined as being non-deterministic but, in general, one may identify other strategies which, in particular, should take into account the attributes associated with the rules. Approaches in this direction are considered in [2], [21], [22] where strategies for the selection of the rules are defined which depend on a notion of rate of application of the rules, or on certain probabilities associated with the rules. In the next section, we present one such strategy where the rules to be applied in the next step are selected depending on a particular distribution of probabilities computed step by step. Here, we define the notion of a (k,q)-parallel step of computation by assuming a generic algorithm for the selection of the rules. Definition 7 ((k,q)-parallel step). Let Π=(S,μ,M 1,M 2,..., Mn)be a P system as in Definition 3 where S=(V,K,D,A,F,P),andletC1,C 2be configurations of Π.LetAk,q be an algorithm for the selection of the rules which is able to return a (C1,k,q)-consistent multiset of rules in Π. We say that C2can be obtained from C1in a (k,q)-parallel step, denoted by C1⇒(k,q) ΠC2,ifthere exists a multiset Rof rules in Πsuch that: 1. Ak,q(C1,P)=R; 2. R=uj1vi1→zj1wi1,...,u jpvip→zjpwip,forsomep>0; 3. C1=xu j1vi1...u jpvipand C2=xz j1wi1...z jpwip,forsomex∈¯ V∗. If that is the case, then we write C1⇒(k,q) ΠC2. Thus, a (k,q)-parallel step in a P system consists in the parallel application of a (C, k, q)-consistent multiset of rules to a certain configuration C. The multiset of rules to be applied is supposed to be returned by a particular algorithm to select membranes and programs, and this has to be done before every step depending on the current configuration of the system. Then, we introduce the notion of sequence of (k,q)-parallel steps and (k,q)- parallel execution of a P system. Definition 8 (sequence of (k,q)-parallel steps). Let Π=(S,μ,M 1,M 2,..., Mn)be a P system as in Definition 3. A sequence of (k,q)-parallel steps in Π is a sequence σsuch that σ=C1,C 2,...,C h where, for all 1≤i≤h,Ciis a configuration of Π,and,ifi=h,thenCi⇒(k,q) Π Ci+1. If that is the case, we say that σis a sequence of (k,q)-parallel steps in Πthat starts from C1and that Chis obtained from C1in h−1steps;wealso write C1⇒(k,q),h ΠCh. Definition 9 ((k,q)-parallel execution). Let Π=(S,μ,M 1,M 2,...,M n)be a P system as in Definition 3. A (k,q)-parallel execution of Πis a sequence of (k,q)-parallel steps in Πwhich starts from the initial configuration of Π. Thus, we have characterized the behavior of P systems operating according to a bounded parallelism where the number of membranes and the number of rules which can be used in every step are overall bounded by some given constants. Remark 2. From a computational point of view, the introduction of bounded parallelism in membrane systems does not affect the fundamental universality results concerning the computational power of different variants of P systems, such as P systems with catalysts, with symport/antiport, with boundary rules, etc. In fact, it is easy to see that, in all those cases, the simulation of counter machines is achieved by means of P systems where the number of rules applied in parallel in each step is actually overall bounded (e.g., see [7]). On the other hand, it is shown in [8], [10] that P systems with catalysts operating in sequential mode and P systems with symport/antiport operating in sequential mode (i.e., with parallelism of type (1,1)) are strictly less powerful than their corresponding parallel versions. Moreover, one can also notice that, whenever kis equal to the number of membranes in the system, our notion of parallelism of type (k,q) coincides with the notion of q-Max-Parallelism introduced in [7]. 4 An Algorithm to Select Membranes and Programs We present an algorithm to select membranes and programs for P systems operating with parallelism of type (1,1) (i.e., in sequential mode) where the next membrane to evolve and the next rule to be applied inside this membrane is randomly selected according to a certain distribution of probabilities. However, with respect to Definition 3, the algorithm is here defined only for a restricted model of P systems where rules are all of the forms: u[]→[v],[v]→u[],[v]→[v](2) that is, there is a distinction between transformation rules and communication rules, communication is only unidirectional, and there is no interaction between the inside and the outside of a membrane. Our strategy for selecting membranes and programs is based on Gillespie’s algorithm [12]. This algorithm [12] provides an exact method for the stochastic simulation of systems of bio-chemical reactions; the validity of the method is rigorously proved and it has been already successfully used to simulate various biochemical processes [17]. As well as this, Gillespie’s algorithm is used in the implementation of stochastic π-calculus [4] and in its application to the modeling of biological systems [23]. We follow a similar approach to associate a stochastic behavior to membrane systems by considering P systems where each rule has associated a real constant which defines its rate of application and which is used to compute the probability of the rule to be applied in the next step in the same way as in Gillespie’s algorithm. More precisely, we consider a class of P systems where, with respect to Definition 3, the set of values is the set of non-negative real numbers denoted by R+ 0, each programs contains a rule like (2), a real constant as an attribute, Here we have addressed these issues by specifically introducing the notion of a program consisting of a rule with a finite set of attributes and a function from a given set (Definition 1). We have shown how attributes and functions can be used to define P system models for bio-chemical systems consisting of a number of bio-chemical reactions distributed across various compartments of the system. A precise strategy for the application of the rules has also been defined for this class of P systems which makes possible to associate a stochastic behavior to such P systems. Our approach is based on the well-known Gillespie’s algorithm and it is developed alongside the work done in [2], [21], [22] where alternative strategies for the application of the rules are defined. Acknowledgements The first author’s research is supported by NWO, Organisation for Scientific Research of The Netherlands, project 635.100.006 “VIEWS”. The second and fourth authors are supported by Ministerio de Ciencia y Tecnolog´ıa of Spain, by Plan Nacional de I+D+I (TIN2005-09345-C04-01), cofinanced by FEDER funds, by Junta de Andaluc´ıa, by project of Excellence TIC 581, and by a FPU fellowship from the Ministerio de Ciencia y Tecnolog´ıa of Spain. References 1. Bernardini, F., Gheorghe, M. (2004). Population P Systems. J. UCS 10,(5), 509– 539. 2. Bianco, L., Fontana, F., Manca, V. (2006). P Systems with Reaction Maps. International Journal of Foundations of Computer Science,17, (1), 27–48. 3. Calder, M., Vyshemirsky, V., Gilbert, D, Orton, R (2006). Analysis of Signalling Pathways using Continuous Time Markov Chains. Transactions on Computational Systems Biology,toappear. 4. Cardelli, L., Philips, A.(2004). A Correct Abstract Machine for the Stochastic Pi-calculus. Electronical Notes in Theoretical Computer Science,toappear. 5. Ciobanu G., Andrei, O., Lucanu D. (2006). Structural Operational Semantics of P Systems, WMC6, LNCS 3850, 31–48. 6. Collado-Vides, J. (1992). Grammatical Models of the Regulation of Gene Expression, Proc. of National Academy of Science,89, 9405–9409. 7. Dang, Z., Ibarra, O.H., Li, C., Gaoyan, X. (2006). Decidability of Model-Checking P Systems. Journal of Automata, Languages and Combinatorics,,toappear. 8. Dang, Z., Ibarra, O.H. (2005). On One-membrane P systems Operating in Sequential Mode. Int. J. Found. Comput. Sci. 16, (5), 867–881. 9. Duan, Z., Holcombe, M., Bell, A. (2000). A Logic for Biological System, Biosystems, 53, 93–155. 10. Freund, R. (2004). Asynchronous P systems and P systems working in Sequential Mode, WMC5, LNCS 3365, 36–62. 11. Gillespie, D.T. (1976). A General Method for Numerically Simulating the Stochastic Time Evolution of Coupled Chemical Reactions. J Comput Physics, 22, 403–434. 12. Gillespie, D.T. (1977). Exact Stochastic Simulation of Coupled Chemical Reactions. The Journal of Physical Chemistry,81, (25), 2340–2361. 13. Hardie, K.R., Williams, P., Winzer, K.(2002). Bacterial cell-to-cell communication: sorry, can’t talk now, gone to lunch. Current Opinion in Microbiology,5, 216–222. 14. Fargerstr¨on, T., James, G., James, S., Kjelleberg, S., Nilsson, P. (2000). Luminescence Control in the Marine Bacterium Vibrio fischeri: An Analysis of the Dynamics of lux Regulation. J. Mol. Biol. 296, 1127–1137. 15. Kam, N., Cohen, I.R., Harel, D. (2001). The Immune System as a Reactive Systems: Modelling T Cell Activation with Statecharts, The Weizmann Institute of Science, Israel. 16. Matsuno, H., Doi, A., Nagasaki, M., Miyano, S. Hybrid (2000). Petri Net Representation of Gene Regulatory Network, Pacific Symposium on Biocompting,World Scientific, 338–349. 17. Meng, T.C., Somani S., Dhar, P. (2004). Modelling and Simulation of Biological Systems with Stochasticity. In Silico Biology,4, (0024), 137–158. 18. Nealson, K.H., Hastings, J.W. (1979). Bacterial Bioluminescence: Its Control and Ecological Significance, Microbiology Review,43, 496–518. 19. P˘aun, Gh. (2000). Computing with Membranes, Journal of Computer and System Sciences,61, (1), 108 – 143. 20. P˘aun, Gh. (2002). Membrane Computing. An Introduction, Springer, Berlin. 21. P´erez-Jim´enez, M.J., Romero-Campero, F.J. (2006). P Systems, a New Computationl Modelling Tool for Systems Biology, Transactions on Computational Systems Biology VI, LNBI,4220, 176-197. 22. Pescini, D., Besozzi, D., Mauri, G., Zandron, C. (2006). Dynamical probabilistic P systems, International Journal of Foundations of Computer Science,17,(1), 183–195. 23. Priami, C., Regev, A., Shapiro, E., Silverman, W. (2001). Application of a Stochastic Name-Passing Calculus to Representation and Simulation of Molecular Processes, Information Processing Letters 80, 25–31. 24. Regev, A., Shapiro, E. (2004) The π-calculus as an abstraction for biomolecular systems. In Gabriel Ciobanu and Grzegorz Rozenberg, editors, Modelling in Molecular Biology, Springer, 219–266. 25. Segel, I.H. (1976). Biochemical Calculations: How to Solve Mathematical Problems in General Biochemistry, John Wiley and Sons, 2nd edition. 26. Till, J.E., McCulloch, F. Siminovitch, L. (1964). A Stochastic Model of Stem Cell Proliferation based on the Growth of Spleen Colony-Forming Cells, Proc. National Academy of Science USA,51, 117–128. 27. Walker, D., Holcombe, M., Southgate, J., McNeil, S., Smalwood, R. (2004). The Epitheliome: Agent-Based Modelling of The Social Behaviour of Cells, Biosystems, 76, (1–3), 89–100. 28. Waters, C.M., Bassler, B.L. (2005). Quorum Sensing: Cell-to-Cell Communication in Bacteria. Annu. Rev. Cell. Dev. Biol. 21, 319–346. 29. The P Systems Web Site: http://psystems.disco.unimib.it 30. Nottingham Quorum Sensing Web Site http://www.nottingham.ac.uk/quorum/