Formal
Languages
Combinatorics on
Words
Molecular
Computing
Theory of
Codes
Molecular
Formal
Computing
Languages
Thiesis
Combinatorics
Theory of
on Words
Codes
PhD Thesis
Milano, 2001
On the power of classes
of splicing systems
PhD Candidate: Rosalba Zizza (XIII cycle)
Advisors: Prof. Giancarlo Mauri
Prof.ssa Clelia De Felice (Univ. di Salerno)
What are we going to see...
DNA
Computing:
the birth
 DNA Computing...
a son:
the splicing
(independent son!)
DNA Computing... What is this?
Biology
Bio-informatics:
Sequence alignment,
DNA Computing
Protein Folding,
Databases of
genomic sequences
Computer
Science
“In 1959, Richard Feynmann gave a visionary
describing the possiility of building computer
that were sub-microscopic. Despite remarkable
progress in computer miniaturization, this goal
is far to be achieved.
HERE THE POSSIBILITY OF COMPUTING
DIRECTLY WITH MOLECULES IS EXPLORED”
...
Science 1994
 Mathematics in cells!
 Behaviour of DNA
like
Turing Machine
Solving
L. Adleman
NP Complete problems !
Typical methodology
PROCESS
Instance of
a problem
ENCODING
LAB
EXTRACTION
but...
1 second to do the computation
600000 seconds to get the output
Solution
Why could DNA computers be good?
Speed:1020 op/sec (vs 1012 op/sec)
Memory:1 bit/nm3 (vs 1 bit x
1012nm3)
The other side of the moon...
 Errors in computation process
(caused by PCR, Hybridization ...)
To avoid this...
OPEN PROBLEM: Define suitable
ERROR CORRECTING CODES
[Molecular Computing Group, Univ. Menphis,
L. Kari et al.]
We apologize...
<<An important aspect of this year’s meeting can be summed
up us: SHOW ME THE EXPERIMENTAL RESULT! >>
(T. Amenyo, Informal Report on 3rd Annual
DIMACS Workshop on DNA Computing, 1997)
We give you...
theoretical results
Before Adleman experiment (1994)...
Tom Head 1987
(Bull. of Math. Biology)
“ Formal Language Theory and DNA:
an analysis of the generative capacity of
specific recombinant behaviors”
SPLICING
Unconventional
models of computation
LINEAR SPLICING
restriction
enzyme 2
restriction
enzyme 1
ligase enzymes
CIRCULAR SPLICING
restriction
enzyme 2
restriction
enzyme 1
ligase enzyme
Circular finite (Paun) splicing languages
and Chomsky hierarchy
CS~
CF~
Reg~
~((aa)*b)
~(aa)*
I= ~aa  ~1, R={aa | 1 $ 1 | aa}
~(an
bn)
I= ~ab  ~1, R={a | b $ b | a}
Contributions
[P. Bonizzoni, C. De Felice, G. Mauri, R.Z., Words99, DNA6 (2000),
submitted]
-Reg~  C(Fin, Fin)
Fingerprint closed
star languages
X*, X regular
group code
Reg~
cyclic
languages
Cir (X*)
X finite
weak cyclic,
altri esempi
~ (a*ba*)*
-Comparison of the three def. of finite circ. splicing systems
C(SCH )  C(SCPA )  C(SCPI )
Problem 1
Structure of regular languages
closed under conjugacy relation
Denote C(F,F’) the family of languages generated by (A,I,R),
with IF~, RF’.
Problem 2
Characterize Reg~  C(Fin,Fin)
Why studying star languages?
Proposition
SCPA=((A,I,R) (circular splicing system)
I  ~ X*  C(SCPA) 
~
X*
(C(SCPA) generated language)
“Consistence” easily follows!!!
The unique problem is the generation
of all words of the language
Definition
w  A* is unbordered if w  uA*  A* u
Theorem
For any w, |w|>2, w unbordered word, then Cyclic(w)
is generated by finite (Paun) circular splicing system
The proof is quite technical ...
Hypothesis |w|>2 is necessary.
Other circular regular splicing languages
• ~(abc)*a  ~(abc)*ab  ~(abc)*b
 ~(abc)*bc  ~(abc)*c  ~(abc)*ca
Cyclic(abc)
weak cyclic languages
~(abc)*ac
The case of one-letter alphabet
 Each language on a* is closed under
conjugacy relation
Theorem
L  a* is CPA generated
L = L 1  (aG ) +
• L 1 is a finite set
•  n : G is a set of representatives of G’ subgroup of Zn
• max{ m | am  L 1 } < n = min{ ag | ag  G }
Words99, DNA6,
Words01
auditorium
Thanks!