P Systems with Endosomes

P Systems with Endosomes Roberto Barbuti, Giulio Caravagna, Andrea Maggiolo–Schettini, Paolo Milazzo Dipartimento di Informatica, Universit`a di Pisa Largo Pontecorvo 3, 56127 Pisa, Italy. {barbuti,caravagn,maggiolo,milazzo}@di.unipi.it Summary. P Systems are computing devices inspired by the structure and the functioning of a living cell. A P System consists of a hierarchy of membranes, each of them containing a multiset of objects, a set of evolution rules, and possibly other membranes. Evolution rules are applied to the objects of the same membrane with maximal parallelism. In this paper we present an extension of P Systems, called P Systems with Endosomes (PE Systems), in which endosomes can be explicitly modeled. We show that PE Systems are universal even if only the simplest form of evolution rules is considered, and we give one application examples. 1 Introduction P Systems were introduced by Pˇaun in [10] as distributed parallel computing devices inspired by the structure and the functioning of a living cell. A P System consists of a hierarchy of membranes, each of them containing a multiset of objects, representing molecules, a set of evolution rules, representing chemical reactions, and possibly other membranes. For each evolution rule there are two multisets of objects, describing the reactants and the products of the chemical reaction. A rule in a membrane can be applied only to objects in the same membrane. Some objects produced by the rule remain in the same membrane, others are sent out of the membrane, others are sent into the inner membranes, which are identified by their labels. Evolution rules are applied with maximal parallelism, meaning that it cannot happen that some evolution rule is not applied when the objects needed for its triggering are available. Many variants and extensions of P Systems exist that include features to increase their expressiveness and that are based on different evolution strategies. Among the most common extensions we mention P Systems with dissolution rules that allow a membrane to disappear and release in the environment all the objects it contains. We mention also P Systems with priorities, in which a priority relationship exists among the evolution rules of each membrane and can influence the applicability of such rules, and P Systems with promoters and inhibitors, in 52 R. Barbuti et al. which the applicability of evolution rules depends on the presence of at least one occurrence and on the absence, respectively, of a specific object. See [2, 11] for the definition of these (and other) variants of P Systems and [13] for a complete list of references to the bibliography of P Systems. In this paper we present another extension of P Systems, called P Systems with Endosomes (PE Systems), with these features: •objects can be contained both inside and on the surfaces of the membranes (as in P Systems with peripheral proteins [5, 9]); •rules are contained on the surfaces of the membranes (they can rewrite objects outside/on/into the membranes); •endosomes can be explicitly created in order to model a biologically inspired transportation mechanism. The definition of this extension of P Systems has a biological inspiration. In fact, the endocytosis of macromolecules is the process by which cells absorb material (molecules such as proteins) from outside the cell by engulfing it with their cell membrane. It is used by all cells of the body because most substances important to them are large polar molecules that cannot pass through the hydrophobic plasma membrane or cell membrane. There exist three kind of endocytosis: phagocytosis, pinocytosis and receptor–mediated endocytosis. In particular, phagocytosis (literally, cell–eating) is the process by which cells ingest large objects, such as cells which have undergone apoptosis, bacteria, or viruses. The membrane folds around the object, and the object is sealed off into a large vacuole known as a phagosome. Pinocytosis (literally, cell–drinking) is concerned with the uptake of solutes and single molecules such as proteins, and, finally, receptor–mediated endocytosis is a more specific active event where the cytoplasm membrane folds inward to form coated pits. These inward budding vesicles bud to form cytoplasmic vesicles. Figure 11summarizes the kinds of endocytosis. By the point of view of the modeler, these three processes are made possible by vesicles (in fact this transportation mechanism is known as vesicle–mediated transportation) which, in the most general case, engulf the macromolecules together with molecules from the surface of the membranes (i.e. receptors). This leads to the creation of endosomes containing the engulfed molecules. The endosomes transfer their content inside the cell by possibly interacting with other components. The endosomes could also be degraded by the interaction with the lysosomes. We define an extension of P Systems (PE Systems) which can explicitly model the creation of endosomes and their interaction inside the cells and, consequently, can easily model these three kind of endocytosis. This variant of P Systems, together with other modeling features such as the modeling of exocytosis (the biologically counterpart of endocytosis), and enriched with channel–mediated communication [1], would provide a powerful and complete modeling language for naturally describing transportation mechanism of molecules inside cells. 1Pictures taken from http://cellbiology.med.unsw.edu.au/units/science/lecture0806.htm P Systems with Endosomes 53 Fig. 1. Three kind of endocytosis: phagocytosis,pinocytosis and receptor–mediated endocytosis. We show that PE Systems are universal even if only the simplest form of evolution rules is considered, namely non–cooperative rules. Finally, we give one application examples to show that endosomes can ease the description of biological systems when PE Systems are used as a modeling formalism. 2 P Systems with Endosomes In this section we recall the definition of standard P Systems, and then we define their extension with endosomes. We will denote multisets over a finite alphabet as strings of alphabet symbols. More precisely, let V∗be the set of all strings over an alphabet V, including the empty one, denoted by λ. For a∈Vand xin V∗ we denote by |x|athe number of occurrences of ain x. If V={a1,...,an}(the ordering is important here), then the Parikh mapping of xis defined by ΨV(x) = (|x|a1,...,|x|an). The definition is extended in the natural way to languages. A string xrepresents the multiset over Vwith the multiplicities of objects a1,...,an as given by ΨV(x). 2.1 P Systems A P System consists of a hierarchy of membranes that do not intersect, with a distinguishable membrane, called the skin membrane, surrounding them all. As usual, we assume membranes to be labeled by natural numbers. Given a set of objects V, a membrane mcontains a multiset of objects in V∗, a set of evolution rules, and possibly other membranes, called child membranes (mis also called the parent of its child membranes). Objects represent molecules swimming in a 54 R. Barbuti et al. chemical solution, and evolution rules represent chemical reactions that may occur inside the membrane containing them. For each evolution rule there is a multiset of objects representing the reactants, and a multiset of objects representing the products of the chemical reaction. A rule in a membrane mcan be applied only to objects in m, meaning that the reactants should be precisely in m, and not in its child membranes. The rule must contain target indications, specifying the membranes where the new objects produced by applying the rule are sent. The new objects either remain in m, or can be sent out of m, or can be sent into one of its child membranes, precisely identified by its label. Formally, the products of a rule are denoted with a multiset of messages of the forms: •(v, here), meaning that the multiset of objects vproduced by the rule remain in the same membrane m; •(v, out), meaning that the multiset of objects vproduced by the rule are sent out of m; •(v, inl), meaning that the multiset of objects vproduced by the rule are sent into the child membrane l. Let TAR be the set of message targets {here, out} ∪ {ini|i∈N}. Given a set of objects Owe denote with Otar the corresponding set of messages O×TAR. As a consequence, we denote with Vtar the set of all messages and we can define an evolution rule as a rule u→vsuch that u∈V∗and v∈V∗ tar. The size of the left–hand side uof an evolution rule is also called the radius of such a rule. If a P System contains rules of radius greater than one, then it is called a cooperative system. Otherwise, it is called non–cooperative. Application of evolution rules is done with maximal parallelism, namely at each evolution step a multiset of instances of evolution rules is chosen non– deterministically such that no other rule can be applied to the system obtained by removing all the objects necessary to apply all the chosen rules. A P System has a tree–structure in which the skin membrane is the root and the membranes containing no other membranes are the leaves. We assume membranes labels to be unique. A membrane structure can be represented as a balanced sequence of labeled brackets and, graphically, as a Venn diagram. Definition 1. AP System is a tuple (V, µ, w1,...,wn, R1,...,Rn)where: •Vis a finite alphabet whose elements are called objects; •µ⊂N×Nis a membrane structure, such that (i, j)∈µdenotes that the membrane labeled by jis contained in the membrane labeled by i; •wiwith 1≤i≤nare strings from V∗representing multisets over Vassociated with the membranes 1,2,...,n of µ; •Riwith 1≤i≤nare finite sets of evolution rules associated with the membranes 1,2,...,n of µ; A sequence of transitions between configurations of a given P System Πis called acomputation. A computation is successful if and only if it reaches a configuration in which no rule is applicable. The result of a successful computation is the multiset P Systems with Endosomes 55 1 EDa →(ED, here)(aa, in2) aD →(#, here) F Da →(F D, here)(a, out) 2 E→(G, here)(ED, in2) #→(#, here) a EDa →(ED, here)(a, out) aD →(#, out) E→(G, here)(F D, out) E→(G, here)(ED, out) GD →λ ED GD →λ Fig. 2. Example of P System that computes {a2n|n∈N}. of objects sent out of the skin membrane during the computation. Unsuccessful computations (computations which never halt) yield no result. Given a P System Πwhose set of object is V, the result x∈V∗of a computation of Πcan be represented as the vector of natural numbers ΦV(x). The set of all vectors of natural numbers computed by Πis denoted P s(Π). In Fig. 2 we show an example of P System Π1computing {a2n|n∈N}, namely such that Ps(Π1) = {2n|n∈N}. Initially, only in membrane 2 there are rules which are applicable and send either objects Fand Dor objects Eand Dinto membrane 1. In the former case the object ain membrane 1 is sent out and the computation halts. In the latter case object ain membrane 1 is consumed and two occurrences of aare sent into membrane 2. Subsequently, Eis consumed and sent into membrane 2 together with D. Note that the rule which sends ED into membrane 2 cannot be applied while there are still objects ain membrane 1, otherwise by the maximal parallelism also the rule producing # would be applied giving rise to an infinite (unsuccessful) computation. Objects asent into membrane 2 are then sent back into membrane 1. The process of doubling and sending into membrane 2 we have explained, could be repeated an arbitrary number of times. Note that all the rules consuming aact on a single occurrence of aat a time and hence the time complexity of the computation is proportional to 2n+2. 2.2 Extension with Endosomes In this section we formally define P Systems with endosomes (PE Systems). To this extent, we start by assuming the same membrane structure µof a P System. As regards objects, similarly to P Systems with peripheral proteins [5, 9], we assume that objects can be contained inside a membrane (as in classical P Systems) and on the surface of a membrane. In order to qualify a position of an object with respect to a membrane, we use in to identify the object inside the membrane, out to identify the object outside the membrane and here to identify the object on the surface of the membrane. Let T AR be the set of message targets {in, out, here}; given a set of objects Owe denote with Otar the corresponding set of messages O×TAR, and we denote with Vtar the set of all messages. 56 R. Barbuti et al. We can now introduce the evolution rules of PE Systems; rules are conceptually divided in evolutionary rules (in the same sense of P Systems) and rules for the creation of endosomes. We recall that, differently from P Systems, the rules of PE Systems are conceptually associated with the surfaces of the membranes of the system. The former class of rules are of the form u→vwhere u∈V+ tar and v∈V∗ tar. The definition of cooperative and non–cooperative rules are the same as for P Systems. Notice that this format for evolutionary rules, which are syntactically different from those of P Systems, may seem to be less expressive than the one of P Systems, in particular for rule moving objects into specific membranes (communication rules). In order to show that this is not the case, let us assume an hypothetical membrane structure µsuch that (l, l′)∈µ, namely a membrane structure in which l′is nested into l. In order to give a rule which moves an object inside membrane l′we cannot use the identifier inl′in a rule of the surface of the membrane l(as in P Systems) because we cannot use the identifier l′as subscript to in. However, the same behavior can be obtained by replacing the rule u→(v, inl′) in the membrane l, as in usual P Systesm, with the PE System rule (u, out)→(v, in) on the surface of the membrane l′. The behavior modeled by this rule, which is in some sense an “attraction” by the nested membrane rather than the “sending” from the top membrane, leads to result analogous to those obtained by P Systems, namely to the transportation of the object inside the nested membranes. The rules for creating endosomes are of the form endoE(u∈V∗, v ∈V∗) where: •Eis a set of evolutionary rules for the endosome; •uis the multiset of objects that must appear on the surface of the membrane containing the rule; •vis the multiset of objects that must appear outside the membrane containing the rule. Notice that each endosome has got its own evolutionary rules in set E. These rules model the behavior of the endosome. As regards the creation of an endosome, it is necessary that objects in uare present on the surface of the membranes (in some sense they can be seen as the receptors) and that objects in vare present outside of the membrane creating the endosome (in some sense they can be seen as the molecules to be engulfed). More formally, the applicability of the endosome rule is possible in the following general case: let (j, i)∈µand let endoE(u, v) be a rule belonging to the surface of the membrane i, than it can be applied only if uis a submultiset of the objects contained on the surface of the membrane i, and only if vis a submultiset of the objects contained inside the membrane j. The result of the application of such a rule is a creation of an endosome inside membrane i containing uon its surface and containing vinside. The endosome itself behaves like a membrane having on its surface rules E. We can now formally define a PE System as follows. Definition 2. APE System is a tuple (V, µ, w1,...,wn, z1,...,zn, R1,...,Rn) where: P Systems with Endosomes 57 •Vis an alphabet whose elements are called objects; •µ⊂N×Nis a membrane structure, such that (i, j)∈µdenotes that the membrane labeled by jis contained in the membrane labeled by i; •wiwith 1≤i≤nare strings from V∗representing multisets over Vassociated with the content of membranes 1,2,...,n of µ; •ziwith 1≤i≤nare strings from V∗representing multisets over Vassociated with the surfaces of membranes 1,2,...,n of µ; •Riwith 1≤i≤nare finite sets of evolution rules associated with the surfaces of the membranes 1,2, . . . , n of µ. The notions of (successful) computation and of result of computations of PE Systems are the same as for standard P Systems. 3 Universality of PE Systems In this section we prove a universality result for PE Systems by showing that any matrix grammar with appearance checking can be simulated by a PE System. As a consequence, before giving the result and its proof, we recall from [11] the definition of such variant of matrix grammars and some related notions. 3.1 Matrix grammars with appearance checking A (context-free) matrix grammar with appearance checking is a tuple G= (N, T, S, M, F ), where Nand Tare disjoint alphabets of non–terminals and terminals, respectively, S∈Nis the axiom, Mis a finite set of matrices, namely sequences of the form (A1→x1,...,An→xn) of context–free rules over N∪T with n≥1, and Fis a set of occurrences of rules in the matrices of M. For a string w, a matrix m: (r1,...rn) can be executed by applying its rules to wsequentially in the order in which the appear in m. Rules of a matrix occurring in Fcan be skipped during the execution of the matrix if they cannot be applied, namely if the symbol in their left–hand side is not present in the string. Formally, given w, z ∈(N∪T)∗, we write w=⇒zif there is a matrix (A1→ x1,...,An→xn) in Mand the strings wi∈(N∪T)∗with 1 ≤i≤n+ 1 such that w=w1,z=wn+1 and, for all 1 ≤i≤n, either (1) wi=w′ iAiw′′ iand wi+1 =w′ ixiw′′ i, for some w′ i, w′′ i∈(N∪T)∗, or (2) wi=wi+1,Aidoes not appear in wiand the rule Ai→xiappears in F. We remark that Fconsists of occurrences of rules in M, that is, if the same rule appears several times in the matrices, it is possible that only some of these occurrences are contained in F. The language generated by a matrix grammar with appearance checking Gis defined as L(G) = {w∈T∗|S=⇒∗w}, where =⇒∗wis the reflexive and transitive closure of =⇒. The family of languages of this form is denoted by MAT λ ac, when rules having the empty string λas right hand side (λ–rules) are allowed, and 58 R. Barbuti et al. by MATac when such rules are not allowed. Moreover, the family of languages generated by matrix grammars without appearance checking (i.e. with F=∅) is denoted by MAT λ, when λ–rules are allowed, and by MAT , when such rules are not allowed. It is known that (i) MAT ⊂MATac ⊂CS; (ii) MAT λ⊂MATλ ac =RE, where CS and RE are the families of languages generated by context–sensitive and arbitrary grammars, respectively. Let ac(G) be the cardinality of Fin Gand let |x|denote the length of the string x. A matrix grammar with appearance checking G= (N, T, S, M, F ) is said to be in the strong binary normal form if N=N1∪N2∪ {S, #}, with these sets mutually disjoint, and the matrices in Mare in one of 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, Y ∈N1, A ∈N2; 4. (X→λ, A →x), with X∈N1, A ∈N2, x ∈T∗,|x| ≤ 2. Moreover, there is only one matrix of type 1, Fconsists exactly of all rules A→# appearing in matrices of type 3 and ac(G)≤2. We remark that # is a trap symbol, namely once introduced it cannot be removed, and a matrix of type 4 is used only once, in the last step of a derivation. For each matrix grammar (with or without appearance checking) there exists an equivalent matrix grammar in the strong binary normal form. Consequently, for each language L∈RE there exists a matrix grammar with appearance checking Gsatisfying the strong binary normal form and such that L(G) = L. Conventions A matrix grammar with appearance checking in the strong binary normal form is always given as G= (N, T, S, M, F ), with N=N1∪N2∪ {S, #}and with n+ 1 matrices in M, injectively labeled with m0, m1,...,mn. The matrix m0: (S→XinitAinit) is the initial one, with Xinit a given symbol from N1and Ainit a given symbol from N2; the next kmatrices are without appearance checking rules, mi: (X→α, A →x), with 1 ≤i≤k, where X∈N1, α ∈N1∪ {λ}, A ∈ N2, x ∈(N2∪T)∗,|x| ≤ 2 (if α=λ, then x∈T∗); the last n−kmatrices have rules to be applied in the appearance checking mode, mi: (X→Y, A →#), with k+ 1 ≤i≤n, X, Y ∈N1, and A∈N2. Since the grammar is in the strong binary normal form, we have (at most) two symbols B(1) and B(2) in N2such that the rules B(j)→# appear in matrices miwith k+ 1 ≤i≤n. For j∈ {1,2}, we denote with ℓjthe set {i|the matix micontains the rule B(j)→#}. For uniformity, we also denote ℓ0={1,2,...,k}and ℓ=ℓ0∪ℓ1∪ℓ2={1,2,...,n}(note that 0 6∈ ℓ). Clearly, the sets ℓ0, ℓ1and ℓ2are disjoint. We remark that in matrix grammars in strong binary normal forms we can assume that all symbols X∈N1appear as the left-hand side of a rule from a matrix: otherwise, the derivation is blocked after introducing such a symbol, hence we can remove these symbols and the matrices involving them. P Systems with Endosomes 59 3.2 Universality We prove that PMC Systems are universal by showing that the family, denoted PsE2(ncoo), of sets Ps(Πe) of results computed by PE Systems with at least two membranes and with non–cooperative rules is equivalent to the family, denoted PsRE, of the images of all the languages in RE obtained through the Parikh mapping (this is the family of recursively enumerable sets of vectors of natural numbers). As P Systems with non-cooperative rules are not universal, our result implies that universality is due to the presence of endosomes. Theorem 1. PsE2(ncoo) = PsRE. Proof. It is enough to show that for a Gin strong binary normal form there is a PE System ΠGsuch that Ps(ΠG) = ΨT(L(G)). We assume that the output of this PE System is given by the objects sent out from the skin membrane. The alphabet we take into consideration is given by T∪N1∪N2∪ {c} ∪ {ci, di, d′ i|i= 1,2}. We build ΠGas a system with a root membrane, labeled 1, and one child membrane labeled 2. All the objects encoding the grammar will be stored inside membrane 1 and the matrixes will be simulated by membrane 2. The initial configuration is given by the objects corresponding to Xinit and Ainit contained in membrane 1, namely objects of w1, and by the token ccontained on the surface of membrane 2, namely z2={c}. This PE System works as follows: it has a cyclic behavior such that, at the beginning of the cycle, at most one endosome in membrane 2 can be created and, if possible, all terminal symbols inside membrane 1 are sent out as output symbols. The created endosome can start a series of steps resulting in the interpretation of the application of a matrix or, differently, it can start a checking phase to model the fact that, if there exist non terminal symbols which cannot be rewritten by any grammar, than the computation has not to halt. In the case in which it starts the interpretation of a matrix of type 2 or 4 (a matrix miwith 1 ≤ i≤k), the involved non terminals are taken by the endosome which contains as rules the ones interpreting the matrix. Objects will be sent into membrane 2 by these rules creating the result of applying the corresponding matrix to the non terminals. Subsequently, these objects are sent out to membrane 1 to restart the cyclic behavior. We recall that during this process no other endosomes can be created, so no other matrixes can be simulated. Differently, in the case in which a matrix of type 3 (a matrix miwith k+1 ≤i≤n) is applied, the single non terminal of N1is taken into the endosome. The endosome will work in the same sense of the endosomes interpreting matrixes of type 2 and 4 even though, at the end of the application of this matrix, instead of restarting with the cyclic behavior, a checking process is started. This process checks, by creating endosomes, the presence of the proper non terminal symbol B(j). If this symbol is found, a special endosome is created which will introduce a trap symbol in this PE System so that the computation will not halt. Analogously, if it is not found, an endosome will restore the configuration of this PE System so that the cyclic behavior can start again.