“Dogma ic” P Sys ems?
Jos´e M. Sempe e
Depa amen o de Sis emas In o m´a icos y Compu aci´on
Uni e sidad Poli ´ecnica de Valencia
[email p o ec ed]
Summa y. In his wo k we p opose a a ian o P sys ems based on he Cen al Dogma
o Molecula Biology which es ablishes he ans o ma ion o DNA s ands in o p o ein
p oduc s by applying di e en s ing ans o ma ion such as ansduc ions and ansc ip-
ions. We in oduce a new kind o wo m objec ules o ca y ou ansducion ope a ions.
Finally, we es ablish he uni e sali y o he p oposed model by simula ing I e a ed ini e
s a e sequen ial ansduce s (IFTs).
1 In oduc ion
P sys ems [15] we e in oduced as a compu a ional model inspi ed by he in-
o ma ion and biochemical p oduc p ocessing o li ing cells h ough he use o
memb ane communica ion. In mos o he wo ks abou P sys ems, in o ma ion is
ep esen ed as mul ise s o symbol/objec s which can in e ac and e ol e acco ding
o p ede ined ules. Ne e heless, he use o s ings o ep esen he in o ma ion
and he use o ules o ans o m s ings ins ead o mul ise s o objec s ha e always
been p esen in he li e a u e o his scien i ic a ea. So, in his mos ly e e ed book
[15], Gh. P˘aun o e iews he use o s ing ules in P sys ems. Di e en a ian s
o s ing-based P sys ems ha e been p oposed along he ime. We can men ion
ew i ing P sys ems [11], e e ed as memb ane sys ems wi h wo m objec s [2] in
he case o genomic ope a ions, inse ion-dele ion P sys ems [6] and splicing P
sys ems [14], among o he s. Obse e ha mos o hese models ha e been used o
language gene a ion [12]. In [5, 7], he p oposal o hyb id P sys ems in oduces he
use o con ex ual ules and Chomsky ules o achie e uni e sali y by gene a ing all
he ecu si ely enume able languages. Recen ly, in [13] a a ian o P sys ems wi h
wo m objec s and e olu iona y based ope a ions has been in oduced o simula e
Ne wo ks o E olu iona y P ocesso s, hence o achie e uni e sali y.
In his wo k, we p opose a a ian o P sys ems wi h wo m objec s and a new
kind o wo m ules based on he cen al dogma o molecula biology which se s
?Wo k suppo ed by he Spanish Minis e io de Educaci´on y Ciencia unde p ojec
TIN2007-60769
292 J.M. Sempe e
he amewo k o ob ain p o ein p oduc s om DNA s ands by applying, among
o he s, ansduc ion and ansc ip ion ope a ions.
The s uc u e o his wo k is as ollows: In sec ion 2 we in oduce basic concep s
and no a ion on o mal language heo y, i e a ed ansduc ions, P sys ems and
molecula biology ela ed o he Cen al Dogma. Then, we will de ine he dogma ic
ules in egions which ansduce ( agmen s o ) wo m objec s in o ( agmen s o )
wo m objec s. We will p opose a simula ion o i e a ed ansduc ions wi h he
new p oposed model in o de o achie e uni e sali y. Finally, we will ou line u u e
esea ch ela ed o his wo k.
2 Basic Concep s
We s a by summa izing he no ions used h oughou his wo k. An alphabe is
a ini e and nonemp y se o symbols. Any ini e sequence o symbols om an
alphabe Vis called wo d o s ing o e V. The se o all wo ds o e Vis deno ed
by V∗. A language o e he alphabe Vis any subse o V∗.
A g amma is a cons uc G= (N, Σ, P, S) whe e Nand Σa e he alphabe s
o auxilia y and e minal symbols wi h N∩Σ=∅,S∈Nis he axiom o he
g amma and Pis a ini e se o p oduc ions in he o m α→β, whe e α∈
(N∪Σ)∗N(N∪Σ)∗and β∈(N∪Σ)∗. The language o he g amma is deno ed by
L(G) and i is he se o e minal s ings ha can be ob ained om Sby applying
symbol subs i u ions acco ding o P. Fo mally, w1⇒
Gw2i w1=uα ,w2=uβ
and α→β∈P. We will deno e by ∗
⇒
G he e lexi e and ansi i e closu e o ⇒
G.
So, he language gene a ed by Gis de ined by he se L(G) = {w∈Σ∗:S∗
⇒
Gw}.
Fou la ge amilies o languages gene a ed by g amma s can be de ined: REG
( egula ), CF (con ex - ee), CS (con ex -sensi i e) and RE ( ecu si ely enume -
able). The de ini ion o hese amilies comes om he es ic ion o e he p oduc-
ion o ms in he g amma . The well known Chomsky’s hie a chy es ablishes he
inclusions REG ⊂CF ⊂CS ⊂RE.
I e a ed T ansduc ions
In he ollowing, we will in oduce I e a ed ini e s a e sequen ial ansduce s (IFT)
as i was de ined in p e ious wo ks ([1, 8, 10]).
An IFT is de ined by he uple T= (Q, Σ, q0, a0, F, P ), whe e Qis a ini e se
o s a es,Σis an alphabe , q0∈Qis an ini ial s a e,a0∈Σis a s a ing symbol,
F⊆Qis he se o inal s a es and Pis a ini e se o ansduc ion ules in he
o m (q, a, p, x) wi h q, p ∈Q,a∈Σand x∈Σ∗which we will w i e as qa →xp.
The ansduc ion ule qa →xp means ha i he ini e con ol is in s a e qand
i eads he symbol a hen i changes o s a e pand w i es x. We de ine a di ec
ansi ion s ep as ollows
uqa `uwp i qa →wp ∈P
“Dogma ic” P Sys ems 293
The e lexi e and ansi i e closu e o `will be deno ed by `∗. We say ha w
de i es x, and i will be deno ed by w=⇒x, i q0w`∗xp, o p∈Q(obse e
ha pis any s a e in Qno necessa ily inal). We will deno e he e lexi e and
ansi i e closu e o =⇒by =⇒∗. I in he p e ious de i a ion he p ocess s ops
in a inal s a e we will w i e
=⇒ins ead o =⇒. Tha is, w
=⇒x, i q0w`∗xp,
o p∈F. The language gene a ed by Tis de ined as ollows
L(T) = {x∈Σ∗:a0=⇒∗w
=⇒x, w ∈Σ∗}
We deno e by IF Tn he amily o languages gene a ed by IFT wi h a mos n
s a es. The hie a chy o amilies in IFTnhas been comple ely explo ed, and i has
been p o ed ha i collapses a le el ou . We ha e he ollowing esul s
Lemma 1.[10] RE =IF T4; [1] CS ⊂IF T3; [10] CF ⊂IFT2.
In addi ion, IFTs ha e been ela ed o he compu ing by ca ing pa adigm [9]
as a way o gene a e e en non- ecu si ely enume able languages.
The Cen al Dogma o Molecula Biology
The Cen al Dogma o Molecula Biology is ou sou ce o inspi a ion o he a ian
o P sys em which we will p opose la e . We ollow he ideas exposed in [4]. Mainly,
he cen al dogma o molecula biology es ablishes a me apho o how DNA s ands
in he li ing cell a e ans o med in o p o ein p oduc s by means o in o ma ion
s o age and ans o ma ion.
Mainly, a sec ion o DNA ( he gene) is ansc ibed o a molecule o messenge
RNA and he mRNA is ansla ed by he ibosome in o a p o ein. In he euka y-
o ic o ganisms he mRNA molecule is p ocessed, be o e ansla ion, by splicing ou
ce ain subsequences called in ons. The DNA is eplica ed be o e he ansc ip-
ion. The ansc ip ion is made by complemen ing he single DNA s and, and by
subs i u ing he hymine nucleo ide by he u acil one in he RNA molecule. The
ansla ion om (spliced) mRNA o p o eins is based on a mapping o nucleo ide
iple s called codons o amino acids wi h he help o ans e RNA ( RNA). Unde
a compu e science poin o iew, he cen al dogma can be iewed as a sequence o
well known ope a ions o e s ings such as mo phisms, ansduc ions and splicing.
The main ing edien s ha we will conside in he subsequen P sys em ha we
will p opose a e he ollowings:
•The e a e di e en p ocesses in di e en egions. DNA duplica ion and DNA
ansc ip ion o mRNA occu s in he nucleus o he cell, while mRNA ans-
la ion o amino acids occu s in some cases in he endoplasmic e iculum wi h
he memb ane ibosome.
•The e a e di e en alphabe sizes and symbols in ol ed in he ope a ions. The
DNA s ands is a sequence o ou di e en nucleo ides: adenine (A), hymine
(T), cy osine (C) and guanine (G), in he RNA he hymine (T) is subs i u ed
by he u acil (U), while he p o eins a e sequences o e a wen y-le e alphabe
( he amino acids)
294 J.M. Sempe e
Fig. 1. The Cen al Dogma o Molecula Biology. (This pic u e has been aken om
accessexcellence.o g)
•T ansc ip ion and ansla ion can be pe o med by alphabe ic homomo phisms
and ini e ansduc ions.
•The e a e di e en p oduc s a e e y s age which in e ac s in o di e en e-
gions. The DNA duplica ion, ansc ip ion and splicing needs he p esence o
di e en p o eins and o he molecula compounds. The p o eins a e he inal
p oduc o he cycle DNA-RNA-p o ein.
3 Dogma ic P sys ems
In his sec ion, we will p opose a a ian o P sys ems ha wo k wi h wo m objec s
in a ansduc ion-like app oach. Fi s , we will in oduce a new kind o egion ules
o wo k wi h.
Adogma ic ule is de ined as ollows
u: pos →wad1,ad2,··· ,adk,whe e
u, a e s ings (wo m objec s), pos ∈ {l, , ∗} and o all i: 1 ≤i≤k adi∈
{he e, ou , inj}. The meaning is he ollowing: P o ided ha he e exis a wo m
objec uin he egion (we can omi he p esence o u), all he wo m objec s wi h
subs ing a posi ion pos (which means, igh mos one ( ), le mos one (l) o
“Dogma ic” P Sys ems 295
a bi a y posi ion (∗)) change subs ing by wand send a copy o he new wo m
objec a he egions de ined by adia e elimina ing he o iginal wo m objec
om he egion.
Example 1. Le he egion Rha e he ule 1de ined as eee :al→bbhe e and
he wo m objec s eee and abbcbaa. Then a e applying 1in he egion, he wo m
objec s a e eee and bbbbcbaa.
I he ule 1is de ined as eee :a →bbhe e, we ob ain abbcbabb as a new wo m
objec . Finally, i he ule is de ined as eee :a∗→bbhe e hen we ob ain he se
o new s ings {bbbbcbaa, abbcbbba, abbcbabb}. Obse e ha , in his case, we ha e
p e iously ob ained h ee copies o he ini ial s ing be o e applying he ule.
The ule al→bbhe e can be applied o e baa and i ob ains he new s ing bbba.
He e, we ha e omi ed he p esence o an addi ional s ing and he ule changes
he le mos appea ance o a symbol a.¤
The add essing label inj, can be di ec ly applied o con iguous egions a he
same le el. Tha is, i he e exis egions jand iinside he same egion, hen a
ule a egion ican send wo m objec s o egion jdi ec ly.
We can obse e ha he dogma ic ules cap u e he ollowing aspec s om he
Cen al Dogma o Molecula Biology:
•The ules ans o m pa s o a s ing in o a new subs ing as in ansc ip ion
and ansduc ion.
•The ules make copies o he a ge s ing be o e ans o ma ion as in DNA
eplica ion.
•The ules need he p esence o o he objec s o be applied.
•The ules can add ess con iguous egions (i.e. RNA mo ing om nucleus o
ibosomes).
Now, we will de ine a Dogma ic Psys em2as he ollowing cons uc
Π= (V, µ, A1,· · · , Am,(R1, ρ1),··· ,(Rm, ρm), i0), whe e:
•V is an alphabe
•µis a memb ane s uc u e consis ing o mmemb anes
•Ai, 1 ≤i≤mis a ini e se o s ings associa ed wi h he egion i( he axioms)
•Ri, 1 ≤i≤mis a ini e se o dogma ic ules o e Vassocia ed wi h he i h
egion and ρiis a pa ial o de ela ion o e Rispeci ying a p io i y
•i0is a numbe be ween 1 and mand i speci ies he ou pu memb ane o Π(in
he case ha i equals o ∞ he ou pu is ead ou side he sys em).
2Di e en ac onyms we e candida es o naming Dogma ic P sys ems. Among o he s,
dP sys ems we e conside ed bu i was p e iously used by o he au ho s in a di e -
en con ex . Ano he ac onym was dogP bu he au ho hinks ha , in such a case,
ca alyze s will ne e be used in his con ex gi en ha ”dogs” and ”ca s” could no
coope a e and li ing in he same egions. We lea e open he sea ch o a good ac onym
o he p oposed Dogma ic Psys ems.

296 J.M. Sempe e
Ini ially, he sys em holds he se o axioms a e e y egion. Then, in a ully
pa allel manne all he ules a e applied o e he s ings de ined a e e y egion.
The sys em hal s whene e no ule can be applied a any egion.
The language gene a ed by Πis he se o wo m objec s collec ed a egion
i0. In he case ha i0=∞, he language is collec ed in ex e nal mode as he se
o s ings in he en i onmen . The language gene a ed by Πis deno ed by L(Π).
Obse e ha i he language is in ini e hen he sys em will ne e hal so i will
add new wo m objec s o he ou pu egion o he en i onmen .
Obse e ha his p oposal is di e en om [3] whe e he au ho s p opose a
memb ane sys em amewo k wi h sympo /an ypo ules o pe o m di e en
ypes o ansduc ions. In ha wo k he p oposed sys em ope a es wi h s ings by
aking e e y symbol o he inpu s ing o he en i onmen (ou side he memb ane
sys em) and pu ing e e y symbol o he ansduced s ing in he en i onmen .
He e, we will a oid sympo /an ypo ules and we will wo k wi h s ings in a
wo m objec app oach.
4 A Simula ion o I e a ed T ansduc ions by Dogma ic P
Sys ems
In his sec ion, we will show a simula ion o IFTs wi h ns a es by dogma ic P
Sys ems. Ou app oach will use n egions inside he skin one in o de o simula e
he ns a es o he IFT. The ansi ions o he IFT will be simula ed by using
he di ec add ess inj. We will need o ma k some symbols in o de o ca y ou
he ansduc ion om le o igh . In addi ion, we will use di e en alphabe s o
a oid a w ong applica ion o he ansduc ion ules a di e en symbols, and o
p e en ha he simula ion goes on e en i he IFT canno ca y ou a comple e
ansduc ion.
Le T= (Q, Σ, q0, a0, F, P ) be an IFT wi h Q={q0,· · · , qn}. Then, we p opose
he ollowing dogma ic P sys em
Π= (V, µ, A, A0,· · · , An,(R, ρ),(R0, ρ0),· · · ,(Rn, ρn),∞),whe e
•V=Σ∪ˆ
Σ∪˘
Σ∪ {#}, whe e ˆ
Σ={ˆa:a∈Σ}and ˘
Σ={˘a:a∈Σ}
•µ= [[0]0,· · · ,[n]n] (we ha e omi ed a label o he skin egion).
•A0={#a0},A=∅, and o all i: 1 ≤i≤n Ai=∅.
•Type (a) ules: Fo e e y ule q0a→ qj∈P, we add he ule #al→#ˆ inj
i qj6=q0o he ule #al→#ˆ he e i qj=q0 o R0
•Type (b) ules: Fo e e y ule qia→ qj∈P, and o e e y symbol ˆ
b∈ˆ
Σ
we add he ule ˆ
bal→ˆ
bˆ inji qi6=qjo he ule ˆ
bal→ˆ
bˆ he e i qi=qj o Ri
•Type (c) ules: Fo e e y egion Riand o e e y pai o symbols ˆa∈ˆ
Σand
b∈Σadd he ollowing ule ˆabl→ˆabhe e
•Type (d) ules: Fo e e y egion Risuch ha qi∈F, and o e e y symbol
ˆa∈ˆ
Σadd he ollowing ule ˆa →˘aou
“Dogma ic” P Sys ems 297
•Type (e) ules: Fo e e y egion Risuch ha qi6∈ F, and o e e y symbol
ˆa∈ˆ
Σadd he ollowing ule ˆa →ˆaou
•Type ( ) ules: Add o R he ules {ˆal→ahe e :a∈Σ}
•Type (g) ules: Add o R he ules {˘al→ain0,ou }
•Type (h) ule: #l→#in0
We will explain he ules in he sys em as ollows: Type (a) ules s a he
ansduc ion o he s ing om he ini ial s a e. Hence, we use he # symbol as a
le delimi e o he s ing o be ansduced. The alphabe ˆ
Σis used o ma k he
symbols ha ha e been ansduced du ing a de i a ion p ocess. Type (b) ules
simula e he ansi ions in he ansduce . Obse e ha we use he add ess inj
o change he s a e in he ini e con ol and he add ess he e o simula e he
ansduce loops. Type (c) ules a e used o block he s ings ha canno be
comple ely ansduced (obse e ha he IFT can be non comple e and i would
no inish he de i a ion p ocess). Type (d) ules a e used o ou pu he ansduced
s ings ha a i e o a inal s a e. He e, we use he alphabe ˘
Σ o ma k he s ings
ha belong o he language gene a ed by he ansduce . Type (e) ules a e used
o ou pu he ansduced s ings ha a i e o a non inal s a e.
The p io i ies o he ules in egions Rikeep he ollowing o de : Type (a) ules
>Type (b) ules >Type (c) ules >Type (d) and Type (e) ules.
The ules o he skin egion a e explained as ollows: Type ( ) ules a e used
o es o e he s ing symbols o he ansduced s ing in o de o eed-back he
ansduce wi h a new inpu s ing (hence, i pe o ms he i e a ion in he ans-
duc ion). Type (g) ules a e used o es o e he symbols om hose ansduced
s ings ha come om a inal s a e (hence, hey belong o he language gene a ed
by i e a ing he ansduce ). In such a case, one copy o he s ing is sen ou he
en i onmen while ano he copy is sen in he egion ze o in o de o eed-back he
ansduce . Finally, he ule o ype (g) is used o send he ansduced s ing in o
he ini ial egion o i e a e a new ansduc ion.
I a s ing w∈L(T), hen #w∈L(Π). We can obse e ha he ansi ions
om Ta e simula ed by he P sys em by means o he ules o ype (a) and (b).
The i e a ion is ca ied ou a he skin egion by applying ules o ype (g) o (h)
(a e es o ing he symbols wi h ules o ype ( ). I he ansduced s ing a i es
o a inal s a e, hen ules o ype (g) a e applied and he s ing wi h he le ma k
# ou pu s he sys em.
Example 2. Le us conside he ini e ansduce de ined h ough he ollowing
ansi ion diag am, wi h aas he s a ing symbol
The p oposed dogma ic P sys em is de ined wi h a memb ane s uc u e
[[0]0,[1]1,[2]2], and he ollowing dogma ic ules
Skin egion ules
1: ˆal→ahe e 4: ˘al→ain0,ou 45 : #l→#in0
2:ˆ
bl→bhe e 5:˘
bl→bin0,ou
3: ˆcl→che e 6: ˘cl→cin0,ou
298 J.M. Sempe e
wi h ρde ined as { 1, 2, 3}>{ 4, 5, 6}> 45, and A=∅.
Region 0 ules
7: #al→#ˆ
bˆ
bin1 9: ˆaal→ˆaˆ
bˆ
bin1 12 : ˆabl→ˆaˆcˆcin2
8: #bl→#ˆcˆcin2 10 :ˆ
bal→ˆ
bˆ
bˆ
bin1 13 :ˆ
bbl→ˆ
bˆcˆcin2
11 : ˆcal→ˆcˆ
bˆ
bin1 14 : ˆcbl→ˆcˆcˆcin2
15 : ˆaal→ˆaahe e 18 :ˆ
bal→ˆ
bahe e 21 : ˆcal→ˆaahe e
16 : ˆabl→ˆabhe e 19 :ˆ
bbl→ˆ
bbhe e 22 : ˆcbl→ˆcbhe e
17 : ˆacl→ˆache e 20 :ˆ
bcl→ˆ
bche e 23 : ˆccl→ˆcche e
24 : ˆa →ˆaou
25 :ˆ
b →ˆ
bou
26 : ˆc →ˆcou
wi h ρ0de ined as { 7, 8}>{ 9, 10, 11, 12, 13, 14}>{ 15, 16, 17, 18,
19, 20, 21, 22, 23}>{ 24, 25, 26}, and A0={#a}
Region 1 ules
27 : ˆaal→ˆaˆ
bˆ
bhe e 30 : ˆabl→ˆaˆcˆcin2
28 :ˆ
bal→ˆ
bˆ
bˆ
bhe e 31 :ˆ
bbl→ˆ
bˆcˆcin2
29 : ˆcal→ˆcˆ
bˆ
bhe e 32 : ˆcbl→ˆcˆcˆcin2
33 : ˆaal→ˆaahe e 36 :ˆ
bal→ˆ
bahe e 39 : ˆcal→ˆcahe e
34 : ˆabl→ˆabhe e 37 :ˆ
bbl→ˆ
bbhe e 40 : ˆcbl→ˆcbhe e
35 : ˆacl→ˆache e 38 :ˆ
bcl→ˆ
bche e 41 : ˆccl→ˆcche e
42 : ˆa →ˆaou
43 :ˆ
b →ˆ
bou
44 : ˆc →ˆcou
wi h ρ1de ined as { 27, 28, 29, 30, 31, 32}>{ 33, 34, 35, 36, 37, 38,
39, 40, 41}>{ 42, 43, 44}, and A1=∅
Region 2 ules
“Dogma ic” P Sys ems 299
45 : ˆabl→ˆaˆcˆche e
46 :ˆ
bbl→ˆ
bˆcˆche e
47 : ˆcbl→ˆcˆcˆche e
48 : ˆaal→ˆaahe e 51 :ˆ
bal→ˆ
bahe e 54 : ˆcal→ˆcahe e
49 : ˆabl→ˆabhe e 52 :ˆ
bbl→ˆ
bbhe e 55 : ˆcbl→ˆcbhe e
50 : ˆacl→ˆache e 53 :ˆ
bcl→ˆ
bche e 56 : ˆccl→ˆcche e
57 : ˆa →˘aou
58 :ˆ
b →˘
bou
59 : ˆc →˘cou
wi h ρ2de ined as { 45, 46, 47}>{ 48, 49, 50, 51, 52, 53, 54, 55, 56}>
{ 57, 58, 59}, and A2=∅
¤
F om he p e ious p oposed P sys em and o he wo ks p e iously e e ed we
ge he ollowing esul .
Theo em 1. E e y ecu si ely enume able language can be gene a ed by a dog-
ma ic P sys em.
P oo . The esul comes om he simula ion o IFTs by dogma ic P sys ems ha
we ha e p oposed be o e. Gi en ha any ecu si ely enume able can be gene a ed
by an IFT wi h ou s a es [10] hen we ha e he esul . ¤
5 Conclusions and u u e wo k
In his pape we ha e p oposed new kinds o ules o P sys em in which we ha e
been inspi ed by he Cen al Dogma o Molecula Biology. The P sys ems ha we
ha e p oposed a e a sui able amewo k o gene a e languages. We hink ha hese
kind o ules will help in he cons uc ion o sys ems o biological simula ions due
o i s inspi a ion om na u e.
Ou u u e esea ch will ocus on he powe o hese sys ems o ansduce o mal
languages wi h no i e a ion. Hence, we will s udy he simula ion o a ional and
ecognizable ansduc ions and he simula ion o ( es ic ed) gsms. In addi ion,
he amewo k o accep languages o s ings o hei Pa ikh mappings (which is
he na u al amewo k o P sys ems) should be explo ed oo. Finally, due o he
ela ion be ween IFTs and Compu ing by ca ing we should explo e he possibili y
o applying memb ane sys ems o ha pa adigm, as a con inua ion o a p e ious
wo k [16].