"Dogmatic" P Systems

“Dogmatic” P Systems? Jos´e M. Sempere Departamento de Sistemas Inform´aticos y Computaci´on Universidad Polit´ecnica de Valencia [email protected] Summary. In this work we propose a variant of P systems based on the Central Dogma of Molecular Biology which establishes the transformation of DNA strands into protein products by applying different string transformation such as transductions and transcriptions. We introduce a new kind of worm object rules to carry out transducion operations. Finally, we establish the universality of the proposed model by simulating Iterated finite state sequential transducers (IFTs). 1 Introduction P systems [15] were introduced as a computational model inspired by the information and biochemical product processing of living cells through the use of membrane communication. In most of the works about P systems, information is represented as multisets of symbol/objects which can interact and evolve according to predefined rules. Nevertheless, the use of strings to represent the information and the use of rules to transform strings instead of multisets of objects have always been present in the literature of this scientific area. So, in his mostly referred book [15], Gh. P˘aun overviews the use of string rules in P systems. Different variants of string-based P systems have been proposed along the time. We can mention rewriting P systems [11], referred as membrane systems with worm objects [2] in the case of genomic operations, insertion-deletion P systems [6] and splicing P systems [14], among others. Observe that most of these models have been used for language generation [12]. In [5, 7], the proposal of hybrid P systems introduces the use of contextual rules and Chomsky rules to achieve universality by generating all the recursively enumerable languages. Recently, in [13] a variant of P systems with worm objects and evolutionary based operations has been introduced to simulate Networks of Evolutionary Processors, hence to achieve universality. In this work, we propose a variant of P systems with worm objects and a new kind of worm rules based on the central dogma of molecular biology which sets ?Work supported by the Spanish Ministerio de Educaci´on y Ciencia under project TIN2007-60769 292 J.M. Sempere the framework to obtain protein products from DNA strands by applying, among others, transduction and transcription operations. The structure of this work is as follows: In section 2 we introduce basic concepts and notation on formal language theory, iterated transductions, P systems and molecular biology related to the Central Dogma. Then, we will define the dogmatic rules in regions which transduce (fragments of) worm objects into (fragments of) worm objects. We will propose a simulation of iterated transductions with the new proposed model in order to achieve universality. Finally, we will outline future research related to this work. 2 Basic Concepts We start by summarizing the notions used throughout this work. An alphabet is a finite and nonempty set of symbols. Any finite sequence of symbols from an alphabet Vis called word or string over V. The set of all words over Vis denoted by V∗. A language over the alphabet Vis any subset of V∗. A grammar is a construct G= (N, Σ, P, S) where Nand Σare the alphabets of auxiliary and terminal symbols with N∩Σ=∅,S∈Nis the axiom of the grammar and Pis a finite set of productions in the form α→β, where α∈ (N∪Σ)∗N(N∪Σ)∗and β∈(N∪Σ)∗. The language of the grammar is denoted by L(G) and it is the set of terminal strings that can be obtained from Sby applying symbol substitutions according to P. Formally, w1⇒ Gw2if w1=uαv,w2=uβv and α→β∈P. We will denote by ∗ ⇒ Gthe reflexive and transitive closure of ⇒ G. So, the language generated by Gis defined by the set L(G) = {w∈Σ∗:S∗ ⇒ Gw}. Four larger families of languages generated by grammars can be defined: REG (regular), CF (context-free), CS (context-sensitive) and RE (recursively enumerable). The definition of these families comes from the restriction over the production forms in the grammar. The well known Chomsky’s hierarchy establishes the inclusions REG ⊂CF ⊂CS ⊂RE. Iterated Transductions In the following, we will introduce Iterated finite state sequential transducers (IFT) as it was defined in previous works ([1, 8, 10]). An IFT is defined by the tuple T= (Q, Σ, q0, a0, F, P ), where Qis a finite set of states,Σis an alphabet, q0∈Qis an initial state,a0∈Σis a starting symbol, F⊆Qis the set of final states and Pis a finite set of transduction rules in the form (q, a, p, x) with q, p ∈Q,a∈Σand x∈Σ∗which we will write as qa →xp. The transduction rule qa →xp means that if the finite control is in state qand it reads the symbol athen it changes to state pand writes x. We define a direct transition step as follows uqav `uwpv iff qa →wp ∈P “Dogmatic” P Systems 293 The reflexive and transitive closure of `will be denoted by `∗. We say that w derives x, and it will be denoted by w=⇒x, iff q0w`∗xp, for p∈Q(observe that pis any state in Qnot necessarily final). We will denote the reflexive and transitive closure of =⇒by =⇒∗. If in the previous derivation the process stops in a final state we will write f =⇒instead of =⇒. That is, wf =⇒x, iff q0w`∗xp, for p∈F. The language generated by Tis defined as follows L(T) = {x∈Σ∗:a0=⇒∗wf =⇒x, w ∈Σ∗} We denote by IF Tnthe family of languages generated by IFT with at most n states. The hierarchy of families in IFTnhas been completely explored, and it has been proved that it collapses at level four. We have the following results Lemma 1.[10] RE =IF T4; [1] CS ⊂IF T3; [10] CF ⊂IFT2. In addition, IFTs have been related to the computing by carving paradigm [9] as a way to generate even non-recursively enumerable languages. The Central Dogma of Molecular Biology The Central Dogma of Molecular Biology is our source of inspiration for the variant of P system which we will propose later. We follow the ideas exposed in [4]. Mainly, the central dogma of molecular biology establishes a metaphor of how DNA strands in the living cell are transformed into protein products by means of information storage and transformation. Mainly, a section of DNA (the gene) is transcribed to a molecule of messenger RNA and the mRNA is translated by the ribosome into a protein. In the eukaryotic organisms the mRNA molecule is processed, before translation, by splicing out certain subsequences called introns. The DNA is replicated before the transcription. The transcription is made by complementing the single DNA strand, and by substituting the thymine nucleotide by the uracil one in the RNA molecule. The translation from (spliced) mRNA to proteins is based on a mapping of nucleotide triplets called codons to amino acids with the help of transfer RNA (tRNA). Under a computer science point of view, the central dogma can be viewed as a sequence of well known operations over strings such as morphisms, transductions and splicing. The main ingredients that we will consider in the subsequent P system that we will propose are the followings: •There are different processes in different regions. DNA duplication and DNA transcription to mRNA occurs in the nucleus of the cell, while mRNA translation to amino acids occurs in some cases in the endoplasmic reticulum with the membrane ribosome. •There are different alphabet sizes and symbols involved in the operations. The DNA strands is a sequence of four different nucleotides: adenine (A), thymine (T), cytosine (C) and guanine (G), in the RNA the thymine (T) is substituted by the uracil (U), while the proteins are sequences over a twenty-letter alphabet (the amino acids) 294 J.M. Sempere Fig. 1. The Central Dogma of Molecular Biology. (This picture has been taken from accessexcellence.org) •Transcription and translation can be performed by alphabetic homomorphisms and finite transductions. •There are different products at every stage which interacts into different regions. The DNA duplication, transcription and splicing needs the presence of different proteins and other molecular compounds. The proteins are the final product of the cycle DNA-RNA-protein. 3 Dogmatic P systems In this section, we will propose a variant of P systems that work with worm objects in a transduction-like approach. First, we will introduce a new kind of region rules to work with. Adogmatic rule is defined as follows u:vpos →wad1,ad2,··· ,adk,where u, v are strings (worm objects), pos ∈ {l, r, ∗} and for all i: 1 ≤i≤k adi∈ {here, out, inj}. The meaning is the following: Provided that there exist a worm object uin the region (we can omit the presence of u), all the worm objects with substring vat position pos (which means, rightmost one (r), leftmost one (l) or “Dogmatic” P Systems 295 arbitrary position (∗)) change substring vby wand send a copy of the new worm object at the regions defined by adiafter eliminating the original worm object from the region. Example 1. Let the region Rhave the rule r1defined as eee :al→bbhere and the worm objects eee and abbcbaa. Then after applying r1in the region, the worm objects are eee and bbbbcbaa. If the rule r1is defined as eee :ar→bbhere, we obtain abbcbabb as a new worm object. Finally, if the rule is defined as eee :a∗→bbhere then we obtain the set of new strings {bbbbcbaa, abbcbbba, abbcbabb}. Observe that, in this case, we have previously obtained three copies of the initial string before applying the rule. The rule al→bbhere can be applied over baa and it obtains the new string bbba. Here, we have omitted the presence of an additional string and the rule changes the leftmost appearance of a symbol a.¤ The addressing label inj, can be directly applied to contiguous regions at the same level. That is, if there exist regions jand iinside the same region, then a rule at region ican send worm objects to region jdirectly. We can observe that the dogmatic rules capture the following aspects from the Central Dogma of Molecular Biology: •The rules transform parts of a string into a new substring as in transcription and transduction. •The rules make copies of the target string before transformation as in DNA replication. •The rules need the presence of other objects to be applied. •The rules can address contiguous regions (i.e. RNA moving from nucleus to ribosomes). Now, we will define a Dogmatic Psystem2as the following construct Π= (V, µ, A1,· · · , Am,(R1, ρ1),··· ,(Rm, ρm), i0), where: •V is an alphabet •µis a membrane structure consisting of mmembranes •Ai, 1 ≤i≤mis a finite set of strings associated with the region i(the axioms) •Ri, 1 ≤i≤mis a finite set of dogmatic rules over Vassociated with the ith region and ρiis a partial order relation over Rispecifying a priority •i0is a number between 1 and mand it specifies the output membrane of Π(in the case that it equals to ∞the output is read outside the system). 2Different acronyms were candidates for naming Dogmatic P systems. Among others, dP systems were considered but it was previously used by other authors in a different context. Another acronym was dogP but the author thinks that, in such a case, catalyzers will never be used in this context given that ”dogs” and ”cats” could not cooperate and living in the same regions. We leave open the search for a good acronym for the proposed Dogmatic Psystems. 296 J.M. Sempere Initially, the system holds the set of axioms at every region. Then, in a fully parallel manner all the rules are applied over the strings defined at every region. The system halts whenever no rule can be applied at any region. The language generated by Πis the set of worm objects collected at region i0. In the case that i0=∞, the language is collected in external mode as the set of strings in the environment. The language generated by Πis denoted by L(Π). Observe that if the language is infinite then the system will never halt so it will add new worm objects to the output region or the environment. Observe that this proposal is different from [3] where the authors propose a membrane system framework with symport/antyport rules to perform different types of transductions. In that work the proposed system operates with strings by taking every symbol of the input string of the environment (outside the membrane system) and putting every symbol of the transduced string in the environment. Here, we will avoid symport/antyport rules and we will work with strings in a worm object approach. 4 A Simulation of Iterated Transductions by Dogmatic P Systems In this section, we will show a simulation of IFTs with nstates by dogmatic P Systems. Our approach will use nregions inside the skin one in order to simulate the nstates of the IFT. The transitions of the IFT will be simulated by using the direct address inj. We will need to mark some symbols in order to carry out the transduction from left to right. In addition, we will use different alphabets to avoid a wrong application of the transduction rules at different symbols, and to prevent that the simulation goes on even if the IFT cannot carry out a complete transduction. Let T= (Q, Σ, q0, a0, F, P ) be an IFT with Q={q0,· · · , qn}. Then, we propose the following dogmatic P system Π= (V, µ, A, A0,· · · , An,(R, ρ),(R0, ρ0),· · · ,(Rn, ρn),∞),where •V=Σ∪ˆ Σ∪˘ Σ∪ {#}, where ˆ Σ={ˆa:a∈Σ}and ˘ Σ={˘a:a∈Σ} •µ= [[0]0,· · · ,[n]n] (we have omitted a label for the skin region). •A0={#a0},A=∅, and for all i: 1 ≤i≤n Ai=∅. •Type (a) rules: For every rule q0a→vqj∈P, we add the rule #al→#ˆvinj if qj6=q0or the rule #al→#ˆvhere if qj=q0to R0 •Type (b) rules: For every rule qia→vqj∈P, and for every symbol ˆ b∈ˆ Σ we add the rule ˆ bal→ˆ bˆvinjif qi6=qjor the rule ˆ bal→ˆ bˆvhere if qi=qjto Ri •Type (c) rules: For every region Riand for every pair of symbols ˆa∈ˆ Σand b∈Σadd the following rule ˆabl→ˆabhere •Type (d) rules: For every region Risuch that qi∈F, and for every symbol ˆa∈ˆ Σadd the following rule ˆar→˘aout “Dogmatic” P Systems 297 •Type (e) rules: For every region Risuch that qi6∈ F, and for every symbol ˆa∈ˆ Σadd the following rule ˆar→ˆaout •Type (f) rules: Add to Rthe rules {ˆal→ahere :a∈Σ} •Type (g) rules: Add to Rthe rules {˘al→ain0,out} •Type (h) rule: #l→#in0 We will explain the rules in the system as follows: Type (a) rules start the transduction of the string from the initial state. Hence, we use the # symbol as a left delimiter of the string to be transduced. The alphabet ˆ Σis used to mark the symbols that have been transduced during a derivation process. Type (b) rules simulate the transitions in the transducer. Observe that we use the address inj to change the state in the finite control and the address here to simulate the transducer loops. Type (c) rules are used to block the strings that cannot be completely transduced (observe that the IFT can be non complete and it would not finish the derivation process). Type (d) rules are used to output the transduced strings that arrive to a final state. Here, we use the alphabet ˘ Σto mark the strings that belong to the language generated by the transducer. Type (e) rules are used to output the transduced strings that arrive to a non final state. The priorities of the rules in regions Rikeep the following order: Type (a) rules >Type (b) rules >Type (c) rules >Type (d) and Type (e) rules. The rules of the skin region are explained as follows: Type (f) rules are used to restore the string symbols of the transduced string in order to feed-back the transducer with a new input string (hence, it performs the iteration in the transduction). Type (g) rules are used to restore the symbols from those transduced strings that come from a final state (hence, they belong to the language generated by iterating the transducer). In such a case, one copy of the string is sent out the environment while another copy is sent in the region zero in order to feed-back the transducer. Finally, the rule of type (g) is used to send the transduced string into the initial region to iterate a new transduction. If a string w∈L(T), then #w∈L(Π). We can observe that the transitions from Tare simulated by the P system by means of the rules of type (a) and (b). The iteration is carried out at the skin region by applying rules of type (g) or (h) (after restoring the symbols with rules of type (f). If the transduced string arrives to a final state, then rules of type (g) are applied and the string with the left mark # outputs the system. Example 2. Let us consider the finite transducer defined through the following transition diagram, with aas the starting symbol The proposed dogmatic P system is defined with a membrane structure [[0]0,[1]1,[2]2], and the following dogmatic rules Skin region rules r1: ˆal→ahere r4: ˘al→ain0,out r45 : #l→#in0 r2:ˆ bl→bhere r5:˘ bl→bin0,out r3: ˆcl→chere r6: ˘cl→cin0,out 298 J.M. Sempere with ρdefined as {r1, r2, r3}>{r4, r5, r6}> r45, and A=∅. Region 0 rules r7: #al→#ˆ bˆ bin1r9: ˆaal→ˆaˆ bˆ bin1r12 : ˆabl→ˆaˆcˆcin2 r8: #bl→#ˆcˆcin2r10 :ˆ bal→ˆ bˆ bˆ bin1r13 :ˆ bbl→ˆ bˆcˆcin2 r11 : ˆcal→ˆcˆ bˆ bin1r14 : ˆcbl→ˆcˆcˆcin2 r15 : ˆaal→ˆaahere r18 :ˆ bal→ˆ bahere r21 : ˆcal→ˆaahere r16 : ˆabl→ˆabhere r19 :ˆ bbl→ˆ bbhere r22 : ˆcbl→ˆcbhere r17 : ˆacl→ˆachere r20 :ˆ bcl→ˆ bchere r23 : ˆccl→ˆcchere r24 : ˆar→ˆaout r25 :ˆ br→ˆ bout r26 : ˆcr→ˆcout with ρ0defined as {r7, r8}>{r9, r10, r11, r12, r13, r14}>{r15, r16, r17, r18, r19, r20, r21, r22, r23}>{r24, r25, r26}, and A0={#a} Region 1 rules r27 : ˆaal→ˆaˆ bˆ bhere r30 : ˆabl→ˆaˆcˆcin2 r28 :ˆ bal→ˆ bˆ bˆ bhere r31 :ˆ bbl→ˆ bˆcˆcin2 r29 : ˆcal→ˆcˆ bˆ bhere r32 : ˆcbl→ˆcˆcˆcin2 r33 : ˆaal→ˆaahere r36 :ˆ bal→ˆ bahere r39 : ˆcal→ˆcahere r34 : ˆabl→ˆabhere r37 :ˆ bbl→ˆ bbhere r40 : ˆcbl→ˆcbhere r35 : ˆacl→ˆachere r38 :ˆ bcl→ˆ bchere r41 : ˆccl→ˆcchere r42 : ˆar→ˆaout r43 :ˆ br→ˆ bout r44 : ˆcr→ˆcout with ρ1defined as {r27, r28, r29, r30, r31, r32}>{r33, r34, r35, r36, r37, r38, r39, r40, r41}>{r42, r43, r44}, and A1=∅ Region 2 rules “Dogmatic” P Systems 299 r45 : ˆabl→ˆaˆcˆchere r46 :ˆ bbl→ˆ bˆcˆchere r47 : ˆcbl→ˆcˆcˆchere r48 : ˆaal→ˆaahere r51 :ˆ bal→ˆ bahere r54 : ˆcal→ˆcahere r49 : ˆabl→ˆabhere r52 :ˆ bbl→ˆ bbhere r55 : ˆcbl→ˆcbhere r50 : ˆacl→ˆachere r53 :ˆ bcl→ˆ bchere r56 : ˆccl→ˆcchere r57 : ˆar→˘aout r58 :ˆ br→˘ bout r59 : ˆcr→˘cout with ρ2defined as {r45, r46, r47}>{r48, r49, r50, r51, r52, r53, r54, r55, r56}> {r57, r58, r59}, and A2=∅ ¤ From the previous proposed P system and other works previously referred we get the following result. Theorem 1. Every recursively enumerable language can be generated by a dogmatic P system. Proof. The result comes from the simulation of IFTs by dogmatic P systems that we have proposed before. Given that any recursively enumerable can be generated by an IFT with four states [10] then we have the result. ¤ 5 Conclusions and future work In this paper we have proposed new kinds of rules for P system in which we have been inspired by the Central Dogma of Molecular Biology. The P systems that we have proposed are a suitable framework to generate languages. We think that these kind of rules will help in the construction of systems for biological simulations due to its inspiration from nature. Our future research will focus on the power of these systems to transduce formal languages with no iteration. Hence, we will study the simulation of rational and recognizable transductions and the simulation of (restricted) gsms. In addition, the framework to accept languages of strings or their Parikh mappings (which is the natural framework of P systems) should be explored too. Finally, due to the relation between IFTs and Computing by carving we should explore the possibility of applying membrane systems to that paradigm, as a continuation of a previous work [16].