by Erzsébet Csuhaj-Varjú and György Vaszil
DNA computing is a recent challenging area at the interface of computer science and molecular biology, providing unconventional approach to computation. The Research Group on Modelling Multi-Agent Systems at SZTAKI develops computational paradigms for DNA computing: theoretical models for test tube systems and language theoretical frameworks motivated by the phenomenon of Watson-Crick complementarity.
The famous experiment of Leonard Adleman in 1994, when he solved a small instance of the Hamiltonian path problem in a graph by DNA manipulation in a laboratory, seeded his ideas on how to construct a molecular computer. Following on from this, Richard J. Lipton proposed a kind of programming language for writing algorithms dealing with test tubes. The basic primitive of the proposed formalism is the test tube, a set or a multiset (the elements are with multiplicities) of strings of an alphabet, and the basic operations correspond to operations with test tubes, merge (put together the contents of two test tubes), separate (produce two test tubes from one tube, according to a certain criteria), amplify (duplicate a tube), and check whether a tube is empty or not.
Test tube systems based on splicing and test tube systems based on cutting and recombination operations are theoretical constructs realizing the above idea. These are distributed communicating systems built up from computing devices (test tubes) based on operations motivated by the recombinant behaviour of DNS strands. These operations are applied to the objects in the test tubes (sets of strings) in a parallel manner and then the results of the computations are redistributed according to certain specified criteria (input/output filters associated with the components) which allow only specific parts of the contents of the test tube to be transferred to the other tubes. Test tube systems based on splicing were presented in 1996 by Erzsébet Csuhaj-Varjú, Lila Kari and Gheorghe Paun, an another model in 1997 by Rudolf Freund, Erzsébet Csuhaj-Varjú and Franz Wachtler. Both models proved to be as powerful as Turing machines, giving a theoretical proof of the possibility to design universal programmable computers with such architectures of biological computers based on DNA molecules. Since that time, the theory of theoretical test tube systems has been extensively investigated by teams and authors from various countries.
The main questions of research into models of test tube system are – among other things – comparisons of the variants with different basic operations motivated by the behaviour of DNA strands (or DNA-related structures) according to their computational power, programmability, simplicity of the filters, topology of the test tubes and approachability of intractable problems. Our investigations follow this line.
At present we explore test tube systems with multisets of objects (symbols, strings, data structures) and operations modelling biochemical reactions. In addition to the computational power, the emphasis is put on elaborating complexity notions for these devices. As a further development, we extended the concept of the test tube system to a pipeline architecture allowing objects to move in the system.
The other important direction of our research is to study language theoretical models motivated by Watson-Crick complementarity, a fundamental concept in DNA Computing. According to this phenomenon, when bonding takes place (supposing that there are ideal conditions) between two DNA strands, the bases opposite each other are complementary.
A paradigm in which Watson-Crick complementarity is viewed in the operational sense was proposed for further consideration by Valeria Mihalache and Arto Salomaa in 1997. According to the proposed model, a ‘bad’ string (a string satisfying a specific condition, a trigger) produced by a generative device induces a complementary string either randomly or guided by a control device. The concept can also be interpreted as follows: in the course of a developmental or computational process, things can go wrong to such an extent that it is advisable to switch to the complementary string, which is always available.
In close cooperation with Prof. Arto Salomaa (Turku Centre for Computer Science), we study properties of Watson-Crick DOL systems, a variant where the underlying generative device is a parallel string rewriting mechanism modelling developmental systems. Recently, we have demonstrated the universal power of some important variants of these systems. In the frame-work of our joint research, we have introduced and now explore networks of Watson-Crick DOL systems, where the communication is controlled by the trigger for conversion to the complementary form: whenever a “bad” string appears at a node, the other nodes receive a copy of its corrected version. In this way, the nodes inform each other about the correction of the emerging failures. In addition to the computational power of these constructs (which proved to be computationally complete in some cases), we have achieved interesting results in describing the dynamics of the size of string collections at the nodes. We have been dealing with challenging stability issues, for example, detecting so-called black holes in the network (nodes which never emit any string). Our future plans aim at comparisons of these devices with different underlying mechanisms and different qualitative/ quantitative conditions employed as triggers, according to computational power, stability and complexity issues, including complexity measures different from the customary ones.
We have been in contact and cooperation with several leading persons from the European Molecular Computing Consortium. The group is open for any further cooperation.
Links:
http://www.sztaki.hu/mms
Please contact:
Erzsébet Csuhaj-Varjú - SZTAKI
Tel: +36 1 4665 644
E-mail: csuhaj@sztaki.hu
or György Vaszil - SZTAKI
Tel: +36 1 4665 644
E-mail: vaszil@sztaki.hu
or Arto Salomaa – Turku Centre
for Computer Science
Tel: +358 2 333 8790
E-mail: asalomaa@utu.fi