DNA COMPUTING BASED ON SPLICING - THE EXISTENCE OF UNIVERSAL COMPUTERS

We prove that splicing systems with finite components and certain cont rols on their work are computationally complete (they can simulate any Turing Machine); moreover, there are universal splicing systems (syst ems with all components fixed which can simulate any given splicing sy stem, when an encoding of the particular system is added-as a program- to the universal system). Splicing systems are based on the splicing o peration which is a model for DNA recombination. Informally, a prefix of a word is catenated to a suffix of another word, thus yielding a (p ossibly) new word. Cutting occurs at specific sites which correspond t o specific sequences in DNA strands as they can be recognized by restr iction enzymes. When no additional control is assumed, splicing system s with finitely many starting words (axioms) and finitely many splicin g rules are known to characterize only regular languages (those recogn ized by finite automata). However, when a splicing rule is allowed to be used (1) only in the presence of certain symbols (''catalyst'') or (2) only in the absence of certain symbols (''inhibitors''), then we c an characterize the recursively enumerable languages (recognized by Tu ring Machines); the same result is obtained when counting the number o f copies of (some of) the words used. From the proofs, we also infer t he existence of universal (hence programmable) splicing systems.