From DNA Recombination to DNA Computing Via Formal Languages

We briefly present notions and results from three directions of research which use formal language theory tools for modelling operations specific to DNA (and RNA) recombinations; in all cases one obtains computability models which are universal (language generating devices are obtained which are equivalent in power with Turing machines). The basic operations are those of matching (a model of the Watson-Crick complementarity), of splicing (a model of the recombinant behaviour of DNA sequences under the influence of restriction enzymes), and of insertion/deletion (known to hold both for DNA and for RNA sequences)