Computing Using Signals: From Cells to P Systems

Computing Using Signals: From Cells to P Systems Ioan I. ARDELEAN Centre of Microbiology Institute of Biology of the Romanian Academy Splaiul Independent¸ei 296 PO Box 56-53, Bucure¸sti 79651, Romˆania E-mail: [email protected] Matteo CAVALIERE Research Group on Mathematical Linguistics Rovira i Virgili University Pl. Imperial T´arraco 1, 43005 Tarragona, Spain E-mail: [email protected] Drago¸s SBURLAN Department of Computer Science Ovidius University of Constant¸a Bd. Mamaia 124, Constant¸a, Romˆania E-mail: [email protected] Abstract. In cell biology one of the fundamental topic is the study of how biological signals are managed by cells. Signals can arise from inside the cell or from the external environment and the correct answer to certain signals is essential for bacteria to survive in a certain environment. Starting from these biological motivations we consider a model of P systems where the computation is controlled by signals which move across the regions. In particular, we consider Signals-Based P systems where the symbol-objects cannot be moved and the rules can be activated/inactivated using a finite number of signals (signal-promoters) moved across the membranes; differently from standard P systems using promoters, in our case promoters cannot be created during the computation. After discussing the biological motivations we show how this model becomes universal when it uses one catalyst, and a bounded number of signal-promoters. 1 Introduction In cell biology it is known that many chemical reactions in the cell are catalyzed by the presence of the respective enzyme (in other words, the enzyme permits the chemical rule to happen; it is possible to get more information on this topic consulting [8]). On the other hand, in bacteria, the enzyme (protein) can be activated/inactivated during the cellular process (in other words, an inactivated enzyme is not able to catalyze the corresponding reaction). 60 In bacteria enzyme activation/inactivation, as well as other important processes, are controlled by covalent modification of proteins (so called post-translational covalent modifications of proteins), [12]. The covalent modification involves the attachment of objects (chemical substances) at different positions along the string represented by the protein (i.e., the enzyme). The attached object could belong to different type of substances such as phosphoryl or methyl (details can be found in [1]). One basic fact in biology is that the attachment of the object (either phosphoryl, methyl or other chemicals) occurs at specific places along the protein; during the cellular processes the substance (for example, phosphoryl) travels along the cell and it is attached to the enzyme where such enzyme must be activated. We can imagine the substance like a promoter that travels along the regions of the cell and activates the corresponding enzyme (and then the corresponding catalyzed reaction) when it is attached/unattached from the enzyme. In what follows we will briefly describe how the phosphoryl movement can control the process of enzyme activation/inactivation in Escherichia Coli. The enzyme activation/inactivation by using covalent bond of phosphate (as in the case of Escherichia Coli) was first described in mammals (liver) around half a century ago when Fisher and Krebs showed that an enzyme involved in metabolism was regulated by the addition (reaction called phosphorylation) or the removal (reaction called dephosphorylation) of phosphoryl, suggesting that reversible phosphorylation could control enzyme activity. Since then the study of protein phosphorylation has flourished in Biology, many scientists being involved in the study of protein phosphorylation and its biological significance; for their pioneering work Fisher and Krebs received the Nobel Prize in 1992. One classical example of enzyme activation/inactivation by covalent attaching of phosphoryl occurs in Escherichia Coli for isocitrate dehydrogenase. Isocitrate dehydrogenase is an enzyme which in the active state takes away two atoms of hydrogen (thus its name “dehydrogenase”) and one molecule of carbon dioxide from a chemical called isocitrate; thus isocitrate is converted to another chemical called 2-oxoglutarate. The enzyme isocitrate dehydrogenase is active when phosphoryl is NOT attached on it. The enzyme is inactivated by attaching the phosphoryl and the inactivated enzyme is not able to perform the conversion of isocitrate to 2-oxoglutarate. The bond of phosphoryl to isocitrate dehydrogenase is catalyzed by an enzyme called kinase whereas the removal of phosphoryl from phosphorylated isocitrate dehydrogenase is catalyzed by a so called phosphatase. In particular, phosphate is attached by the kinase at a very precise position within the protein, exactly at the level of the 113rd aminoacid; these reactions are reversible and they enable the cell to either activate (by de phosphorylation) or to inactivate (by phosphorylation) the enzyme isocitrate dehydrogenase. The idea of this process is described in Figure 1. The phosphoryl movement can also control the so-called two-component regulatory system present, for example, in Escherichia Coli. A two-component regulatory system is a system composed by two proteins: a sensor (S) and a response regulator (RS). Such system responses to environmental signals (stimuli) like changes in oxygen concentration, light intensity, starvation, water activity, and so on (for more details it is possible to consult [11]). The responses of a two-component regulatory system are essential for bacterial cells (as well as other types of cells) to survive in a given environment (for example, in Escherichia Coli, it seems to exist around 50 different two-component regulatory systems). 61 ' & $ % ' & $ % ÁÀ ¿ ÁÀ ¿ PP INACTIVE ENZYME ACTIVE ENZYME ? ? SIGNAL IN SIGNAL OUT - ? Figure 1: Enzyme is activated/deactivated removing/adding phosphoryl The responses of a two-component regulatory systems are based, again, on the phosphorylation/ dephosphorylation of proteins described before for enzyme activation/inactivation (for details about two-component regulatory systems the reader can consult [1, 11]). Two-component regulatory systems and enzyme activation/inactivation process are important because they illustrate how within the same cell (in this case, Escherichia Coli) the attaching of the same object, phosphoryl (that moves around the cell), can modulate (activate/deactivate) different functions such as the conversion of izocitrate to 2-oxoglutare (in the case of enzyme activation/inactivation) or it can change the proportion of some transport proteins at the plasma membrane (in the case of a two-component regulatory systems). Using (some of) the biological motivations described above a new model of P systems, called Signals-Based P system, can be introduced: it uses symbol-objects (chemical substances) and chemical reactions (evolution rules) present in the regions; the symbol-objects evolve using the evolution rules but they cannot be moved; the rules present in the regions can be activated/deactivated using signals called signal-promoters. The signal-promoters do not participate in any evolution rule but they are able to move around the regions of the system (they play the role of the phosphoryl described before). In other words, this new model can be considered like the classical P systems using promoters but with two restrictions: the symbol-objects cannot be moved and the signalpromoters cannot be created but only moved across the membranes (at the beginning of the computation a fixed number of signal-promoters is given in the regions; for some aspects the idea of signal-promoters recall the concept of mobile catalyst introduced in [6]). Informally, we can say that in a Signals-Based P system the computation is realized only 62 moving signals around the regions (from here “computing using signals” in the title of the paper) and executing the indicated evolution rules. The model considered is related with the idea of considering signal transduction in cells as computational process (for instance, see [9]). In this preliminary paper we introduce the formal definition of Signals-Based P systems and we prove that they are universal using one catalyst and a bounded number of signalpromoters. When using non cooperative rules and two promoters, Signals-Based P systems are able to generate at least the Parikh sets of ET0L languages. In the final section several open problems are also proposed. In the following sections we suppose the reader familiar with the basic knowledge of P systems and in particular with P systems using promoters/inhibitors (for details the reader can consult [2] and [7]). 2 Signals-Based P Systems: Definition A Signals-Based P system (in short, an SB P system), of degree m≥1, with symbol– objects is a construct Π = (V, C, P, µ, w1, . . . , wm, R1, . . . , Rm, R0 1, . . . , R0 m, io), where: •Vis the alphabet of Π; its elements are called objects; •C⊆Vis the set of catalysts; •P⊆Vis the set of signal-promoters; •µis a membrane structure consisting of mmembranes labeled 1,2,···, m; •wi, 1 ≤i≤m, specify the multisets of objects present in the corresponding regions iat the beginning of a computation; •Ri, 1 ≤i≤m, are finite sets of simple evolution rules over Vassociated with regions 1,2, . . . , m of µ; these evolution rules are of the form a→vor ca →cv, where ais an object from V\ {C∪P}and vis a string over V\ {C∪P}; •R0 i, 1 ≤i≤m, are finite set of signaling rules over Passociated with regions 1,2, . . . , m of µ; these signaling rules are of the form a→v|ptar or ca →cv|ptar , where ais an object from V\ {C∪P},vis a string over V\ {C∪P},p∈P, tar ∈ {here, inj, tar}, j ∈ {1,···, m}; •iois a number between 0 and mand specifies the output membrane of Π (if i0= 0 then the environment is used for the output). A configuration of a Signals-Based P system is described using the m-tuple of multiset of objects, present in the mregions of the system. To each region a finite number of objects (among them, signal promoters and catalysts) is associated, and a finite number of simple evolution rules and of signaling rules. The m-tuple (w1, w2,···, wm) is the initial configuration of Π. A transition between two configurations is governed by the mixed application of the s imple evolution rules Riand of the signaling rules R0 i, for each 1 ≤i≤m. A sequence of transitions of configurations is called computation. 63 Simple evolution rules are rules with all targets fixed as “here” (see [3]). Signaling rules are simple evolution rules, promoted by some signal-promoter p. When a signaling rule a→v|ptar (or ca →cv|ptar ) is applied then the object ais transformed into the objects specified by vand the promoter pis sent into the (adjacent) region specified by tar. In every region the signal-promoters are present in the set sense, i.e. we cannot have more than one copy of the same signal-promoter in one region. All objects that can be “subject” of the rules of the sets Ri, R0 i,1≤i≤m, have to evolve by such rules. There is no difference between simple evolution rules and signaling rules: both are applied in the non-deterministic maximally parallel manner. The system continues parallel steps until there remain no applicable rules in any region of the system. Then the system halts (the computation is successful), and we consider the number of objects contained in the output region ioas the result of the computation of Π. This way to have a computation in a Signal-Based P system is called the mixed approach. During the computation it can happen that two signaling rules, promoted by the same promoter p, and with different targets, are applied: in this case a conflict appears and the computation is considered not successful. We use the following notation PsSBPm(α, j), α ∈ {ncoo, coo}∪{catk|k≥0}, to denote the family of sets of vectors of natural numbers generated by SB P systems with at most mmembranes, jsignal-promoters, simple evolution rules and signaling rules that can be non-cooperative (ncoo), or catalytic (catk), using at most kcatalysts (as usual ∗is used if the corresponding number of membranes, signal-promoters or catalysts is unbounded). 3 Using Non-Cooperative Rules: Simulating Lindenmayer Systems In this section we show how a Signal-Based P systems, using non-cooperative rules and three signal-promoters are able to generate at least the Parikh sets of ET0L languages. First we recall the basic notions about Lindenmayer systems (for a complete information we suggest [10]). An ET0L system is a construct G= (Σ, T, H, w0), where the components fulfill the following requirements: Σ is the alphabet. T⊆Σ is the terminal alphabet. His a finite set of of finite substitutions H={h1, h2,· · · , ht}(tis the number of tables); each hi∈H can be represented by a list of context-free rules A→x, such that A∈Σ and x∈Σ∗(this list for hishould satisfy that each symbol of Σ appears as the left side of some rule in hi). w0∈Σ∗is the axiom. Gdefines a derivation relation ⇒by x⇒yiff y∈hi(x), for some 1 ≤i≤t, where hi is interpreted as a substitution mapping. The language generated by Gis L(G) = {w∈Σ∗|w0⇒∗w} ∩ T∗, where ⇒∗denotes the reflexive and transitive closure of ⇒. The family of languages generated by ET0L systems is denoted by ET0L. It is known, [10], that for each L∈ET 0L, there exist an ET0L system G0, with only 2 tables, such that L=L(G0). 64 We also need to present the following normal form for ET0L systems. Lemma 3.1 (Normal Form) For each L∈ET0Lthere is an extended tabled Lindenmayer system G= (Σ, T, H, w0)with 2 tables (H={h1, h2}) generating L, such that the terminals are only trivially rewritten: for each a∈Tif (a→α)∈h1∪h2then α=a. Of interest for the purpose of this paper are the following result CF ⊂ET0L⊂CS ⊂RE. where by CF, CS, and RE we denote the families of languages generated by context-free, context-sensitive, and type 0 grammars, respectively. Theorem 1 P sSBP2(ncoo, 3) ⊇P sET0L. Proof. Given an ET0L system G= (Σ, T, H, w0) with 2 tables (H={h1, h2}) in the normal form described before generating L, we construct an SB P system Π generating the Parikh set of L(actually, we remove the trivial productions from h1and h2). Let us denote N0= Σ \T. We take Π = (V, C, P, µ, w1, . . . , wm, R1, . . . , Rm, R0 1, . . . , R0 m, io), where •V= Σ ∪ {#, S0}; •C=∅; •P={p0, p00, q}; •µ= [1[2]2]1; •w1=Sp0p00q, w2=w0; •R1={S0→S}; •R2={#→#}; •R0 1={S→S0 |p0 in2 , S →S0 |p00 in2 , S →S0 |qin2 }; •R0 2={u→v|p0 out |u→v∈h1}∪{u→v|p00 out |u→v∈h2} ∪ {N→#qhere |N∈N0}; •io= 2. The system Π works in the following way. In region 2 (the output region) are simulated the applications of the rules of the first table h1or of the second table h2over the symbolobjects corresponding to a sentential form. In region 1 the object Sis changed to S0using, in a non deterministic way, one of the three signaling-rules in R0 1. If the rule S→S0 |p0 in2 is applied, then the signal-promoter p0 is sent to region 2; in the same way, if the rule S→S0 |p00 in2 is applied, then the signalpromoter p00 is sent to region 2. When the signal-promoter p0is sent to region 2, then the rules of h1are activated and then, possibly, applied; when the signal-promoter p00 is sent 65 to region 2, then the rules of h2are activated (the presence of the signal-promoters p0and p00 guarantees that the rules of the first and second table are not applied in a mixed way in region 2). To stop the movements of signal-promoters between the two regions the rule S→S0 |qin2 must be applied in region 1. In this case the signal-promoter qis sent into region 2 and this activates the rules N→#qhere |N∈N0}present in that region (checking in this way that, when the computation halts, only objects corresponding to terminal symbols have been obtained in region 2). Therefore, the system Π generates, in the output region, exactly the Parikh set of L(G). 2 4 Using Catalytic Rules: Universality In this section we prove that, if we use one catalyst and a (bounded) number of signalpromoters, then Signal-Based P systems become universal. The proof is based on simulating matrix grammars with appearance checking. 4.1 Matrix Grammars Amatrix grammar with appearance checking is a construct G= (N, T, S, M, C), where N, T are disjoint alphabets, S∈N,Mis a finite set of sequences of the form (A1→x1, . . . , An→xn), n≥1, of context-free rules over N∪T(with Ai∈N, xi∈(N∪T)∗, in all cases), and Cis a set of occurrences of rules in M(Nis the nonterminal alphabet, Tis the terminal alphabet, Sis the axiom, while the elements of Mare called matrices). For w, z ∈(N∪T)∗we write w=⇒zif there is a matrix (A1→x1, . . . , An→xn) in Mand the strings wi∈(N∪T)∗,1≤i≤n+ 1, such that w=w1, z =wn+1,and, for all 1 ≤i≤n, either (1) wi=w0 iAiw00 i, wi+1 =w0 ixiw00 i, for some w0 i, w00 i∈(N∪T)∗, or (2) wi=wi+1, Aidoes not appear in wi, and the rule Ai→xiappears in C. The rules of a matrix are applied in order, possibly skipping the rules in Cthat cannot be applied – therefore we say that these rules are applied in the appearance checking mode. The language generated by Gis defined by L(G) = {w∈T∗|S=⇒∗w}. By MATac we denote the families of languages generated by matrix grammars with appearance checking. It is known that MATac =RE. We say that a matrix grammar with appearance checking (ac) G= (N, T, S, M, F) is in the Z-binary normal form if N=N1∪N2∪ {S, Z, #}with these three sets mutually disjoint and the matrices in Mof the following forms: 1. (S→XA),with X∈N1, A ∈N2, 2. (X→Y, A →x),with X, Y ∈N1, A ∈N2, x ∈(N2∪T)∗,|x|≤ 2 3. (X→Y, A →#),with X∈N1, Y ∈N1∪ {Z}, A ∈N2, 4. (Z→λ) There is only one matrix of type 1, and Fconsists of all rules A→# appearing in matrices of type 3, and if a sentential form in Gcontains Z, it is of the form Zw, with w∈(T∪ {#})∗. 66 Lemma 4.1 For each language L∈RE there is a matrix grammar with appearance checking in the Z-binary normal form such that L=L(G). Theorem 2 P sSBP2(cat1, t) = P sRE, for some t∈N. We only show that PsSBP2(cat1, t)⊇P sRE (the reverse inclusion is based on Turing- Church thesis). Take a grammar G= (N, {a}, S, M, F) in the Z-binary normal form, in the standard notation, presented before. Also, let us consider that |M|=nand let us enumerate the matrices of M; moreover let us consider that we are not in the trivial case, i.e., there exists: •one rule (S→X0A0)∈M; •j≥1 rules of type (Xi→Yi, Ai→xi)∈M, 1 ≤i≤j; •k≥1 rules of type (Xi→Yi, Ai→#) ∈M,j+ 1 ≤i≤j+k=n−2}, with (Ai→#) ∈F; •one rule of type (Z→λ). We will construct a Signals-Based P system Πsignals which simulates any derivation of the grammar G. Formally we define Πsignals = (V, C, P, µ, w1, w2, R1, R2,0), where: •V={M0, M5, M6, N0, N1, N2}∪{Mi,t |1≤i≤j, 1≤t≤4} ∪ {Mi,t |j+ 1 ≤i≤j+k, 1≤t≤3} ∪ C∪P; •C⊆V={c}the set of catalysts; •P⊆V={R, Q, Q, W }∪{Pi|1≤i≤k+l}∪{Pi|1≤i≤k+l}∪{Ri|1≤i≤l} the set signaling promoters; •µ= [1[2]2]1; •w1={Pi, Pi|1≤i≤j+k} ∪ {Q, Q, M0, R, W } w2={c, N0, W}∪{X0, A0}. The sets of rules, associated to the regions, are constructed in the following way. 1. For a matrix mi: (Xi→Yi, Ai→xi) with 1 ≤i≤jwe add to the sets R1, R0 1and R0 2the following sequences of rules: to R1: to R0 1: to R0 2: Mi,4→M5M0→Mi,1|Piin cXi→cYi|Piout M6→M0Mi,1→Mi,2|Qin N0→N1|Qout Mi,2→Mi,3|Piin N1→#|Piout Mi,3→Mi,4|Qin cAi→cxi|Piout M5→M6|Rin N1→N2|Qout N2→#|Piout N2→N0|Rout 67 2. For a matrix mi: (Xi→Yi, Ai→#) with j+ 1 ≤i≤j+kwe add to the sets R1, R0 1and R2the following sequences of rules: to R1: to R0 1: to R0 2: Mi,2→Mi,3M0→Mi,1|Piin cXi→cYiT0|Piout Mi,1→Mi,2|Qin N0→N1|Qout Mi,3→M4|Piin N1→#|Piout M4→M0|Win T0→T1|Piout cAi→c#|Piout N1→N0|Piout T1→λ|Wout 3. For the matrix mn−1: (Z→λ) we add to the sets R1and R0 2the following sequences of rules: to R1: to R0 2: M0→M#|Din Z→λ|Dout X→#|Dout ∀X∈N\ {Z} 4. Rule # →# is added to R2; 5. No other rules are added to the sets R1,R2,R0 1and R0 2. Proof. Let us now discuss how the system works by having initially an overview of the simulation and coming back to the details later on. At the beginning, region 1 contains the signaling-rules used to choose nondeterministically a certain matrix to have to be applied, while the region 2 contains the evolution rules that simulate the application of the matrix selected in region 1. Informally, the whole computation is based on an exchange of signal-promoters between the two regions which coordinates the process by activating certain rules, at certain steps. The P system uses a bounded number (depending on the grammar G) of signalpromoters. In region 2 we will have rules that handle the correct application of the selected matrix, but also rules which manage the case when the selected matrix (of type 2 or type 3) cannot be simulated. In this last case (if a “wrong” matrix has been selected) the symbol # is generated (therefore the computation will never stop since the presence of the evolution rule # →#). In the derivation of a matrix grammar, a matrix is non-deterministically chosen and it is applied on the current sentential form. The process starts from the axiom Sand is iterated up to the moment when all the symbols in the sentential form are terminal symbols or no matrix is applicable anymore despite the fact that in the sentential form there still exist nonterminals. One can modify the grammar in an equivalent one such that every possible derivation leads to a terminal sentential form, or, never halts. A similar mechanism will be used in our simulation: a matrix will be randomly chosen (by means of the non-determinism) in region 1 and, if it is possible, then it will be simulated in region 2 and such process will be iterated; if the chosen matrix cannot be simulated, then the P system will cycle forever. Finally, when the object Zis produced in region 2 68