Watson-Crick systems

The idea of using DNA strands for computation is not a new one but intensive investigations started only after the successful experiment of Adleman (see [AdlemanAdleman1994]), when he solved an instance of the Hamiltonian path problem by using DNA strands for computation. Although the graph in which he found a Hamiltonian path was small, this experiment turned the interest to the applicability of DNA strands as a support for computing.

Although the ultimate goal, to create a practical molecular computer, is still elusive, a large amount of work has already been done concerning the theoretical foundation of DNA computing. Many theoretical models have been proposed (see [Paun, Rozenberg, and SalomaaPaun et al.1998]), where universal computing capacity of Turing machines have been achieved.

Universality seems to be a built-in feature of DNA computing. The main question is to determine which are those common crucial properties of the models motivated by the phenomena of formation of double DNA strands, which make these models so powerful. An answer to this question was first given in [Rozenberg and SalomaaRozenberg and Salomaa1996]: the effectivity of computing by DNA strand originates from two properties, namely from massive parallelism and from the phenomenon of Watson-Crick complementarity. Parallelism drastically reduces time complexity, thus makes computationally intractable problems tractable, while Watson-Crick complementarity gives us a very useful operation, which is provided by nature ``for free''. In the following we briefly summarise the main characteristics of this latter phenomenon.

DNA (deoxyribonucleic acid) is found in any living organism, it consists of polymer chains, called DNA strands. DNA strands are composed of nucleotides (sometimes called bases): A (adenine), G (guanine), C (cytosine), and T (thymine). A and G are called purines, C and T are called pyrimidines. In nature the strands form the well-known double helix by a bondage of two separate strands. This bonding always takes place by pairwise attraction of the bases: A bonds with T, G bonds with C. This phenomenon is called Watson-Crick complementarity and the pairs $(A,T)$ and $(G,C)$ are called complementary pairs. Watson-Crick complementarity gives us some fundamental information for free: whenever in a double strand a bondage takes place, we know that the bases at the corresponding positions are complementary. Moreover, for a single DNA strand nature gives its complementary pair; therefore if we have one member of a double strand, then we have its complementary pair as well.

This feature was generalised and formalised in [SalomaaSalomaa1998], where it was interpreted as a computational paradigm, called the paradigm of complementarity. Suppose that the alphabet of the strings to be computed is DNA-like, that is, a complementary relation is present among the letters: half of the letters are called purines, their complementary letters are called pyrimidines. In such a situation any string induces its complementary string.

The first notion, called a Watson-Crick D0L system, where the notion of complementarity is considered as an operation, was introduced in [Mihalache and SalomaaMihalache and Salomaa1997]. A Watson-Crick D0L system consists of a D0L system over a so-called DNA-like alphabet $V=\{a_1,\dots,a_n,\bar a_1,\dots,\bar a_n\},$ $n\ge 1,$ and a mapping $\phi$ called the trigger for complementarity transition. Letters $a_i$ and $\bar a_i$, $1\leq i\leq n,$ are called complementary letters. Following the analogy to the alphabet of DNA, we speak of purines and pyrimidines. Barred letters will be referred to as pyrimidines, and non-barred ones as purines. The mapping $\phi$ is from the set of strings over the DNA-like alphabet $V$ to $\{0,1\}$ and has the following property: the $\phi$-value of the axiom of the D0L system is 0 and whenever the $\phi$-value of a string is 1, then the $\phi$-value of its complementary word must be 0. (The complementary word of a string is obtained by replacing each letter in the string with its complementary letter.) The derivation in a Watson-Crick D0L system proceeds as follows: when a new string is computed by applying the homomorphism of the D0L system, then it is checked according to the trigger. If the $\phi$-value of the obtained string is 0 (the string is a ``good'' word), then the derivation continues in the usual manner. If the obtained string is a ``bad'' one, that is, its $\phi$-value is equal to 1, then the string is changed to its complementary word and the derivation continues from this complementary string.

Particularly important variants of Watson-Crick D0L systems are the so-called standard systems. In this case those words which contain more pyrimidines (barred letters) than purines are ``bad'' words and those containing at least as many purines as pyrimidines are ``good'' words. In the dissertation we always deal with standard systems. Analogously to standard Watson-Crick D0L systems, we define standard Watson-Crick EDT0L, E0L and eco-grammar systems, where the underlying systems are EDT0L systems, E0L systems or extended simple eco-grammar systems, respectively.

The computational and generative capacity of these systems is among the most important problems of the field. In [SosikSosik2001] it was shown that any Turing computable function can be computed by a standard Watson-Crick D0L system. In the dissertation we study standard Watson-Crick systems as generating devices, that is we are interested in their generative capacity.

We prove that any recursively enumerable language can be generated by a standard Watson-Crick EDT0L system, by a standard Watson-Crick E0L system or by a standard Watson-Crick eco-grammar system. Moreover, the standard Watson-Crick EDT0L system and the standard Watson-Crick eco-grammar system can be chosen with bounded size parameters: we can consider EDT0L systems with two tables or EDT0L systems with no limitation on the number of tables but with the number of non-terminals bounded by a constant and we can also consider standard Watson-Crick eco-grammar systems with only one agent.

Although our main goal in this chapter is to study standard Watson-Crick eco-grammar systems and to prove their universal generative power, the first, longer part of this chapter deals with standard Watson-Crick Lindenmayer systems. The reason behind this is the following: on the one hand the constructions used for Lindenmayer systems show why Watson-Crick complementary extends the generative capacity of the underlying generative device and give useful techniques for using Watson-Crick complementarity in formal language theory, while on the other hand the construction used in the case of standard Watson-Crick E0L systems can be used for standard Watson-Crick eco-grammar systems with only a slight modification.

The main part of the results of this chapter is presented in [Csima, Csuhaj-Varjú, and SalomaaCsima et al.2001].