Search

The authors present a solution to the problem of generating the maximum possible number of symbols for a biomolecular computer using restriction enzyme BbvI and ligase as the hardware, and transition molecules built of double-stranded DNA as the software. The presented solution offers an answer to the open question, in the algorithm form, of the maximal number of symbols for a biomolecular computer that makes use of the restriction enzyme BbvI.

Great advances in biotechnology have allowed the construction of a computer from DNA. One of the proposed solutions is a biomolecular finite automaton, a simple two-state DNA computer without memory, which was presented by Ehud Shapiro’s group at the Weizmann Institute of Science. The main problem with this computer, in which biomolecules carry out logical operations, is its complexity – increasing the number of states of biomolecular automata. In this study, we constructed (in laboratory conditions) a six-state DNA computer that uses two endonucleases (e.g. AcuI and BbvI) and a ligase. We have presented a detailed experimental verification of its feasibility. We described the effect of the number of states, the length of input data, and the nondeterminism on the computing process. We also tested different automata (with three, four, and six states) running on various accepted input words of different lengths such as ab, aab, aaab, ababa, and of an unaccepted word ba. Moreover, this article presents the reaction optimization and the methods of eliminating certain biochemical problems occurring in the implementation of a biomolecular DNA automaton based on two endonucleases.

In the paper we present a theoretical analysis of extension of the finite automaton built on DNA (introduced by the Shapiro team) to an arbitrary number of states and symbols. In the implementation we use a new idea of several restriction enzymes instead of one. We give arithmetical conditions for the existence of such extensions in terms of ingredients used in the implementation.

A major challenge in DNA computing area is to design autonomous and programmable biomolecular devices built on DNA. The significant achievement in the field of DNA nanodevices was a laboratory implementation of the 2-state biomolecular finite automaton based on one restriction enzyme FokI [3]. Although this practical implementation represents a proof of concept for autonomous computing with DNA molecules, it has a limited computational power. The restriction enzyme FokI enables construction an automata with at most 3-states. We propose to use several restriction enzymes (instead of one) which act autonomously in a test tube to construct more powerful finite state machines. It enables to build any finite nondeterministic automata or even push-down automata. The autonomous operation of the automaton is based on alternating cleavages of DNA molecules by several restriction enzymes. We illustrate this new idea by presenting a laboratory implementation of a particular case of finite automata. In this experiment two restriction endonucleases act autonomously on DNA in one test tube. This approach may be used (in the future) to build nanomachines, even push-down automata (made of DNA molecules) which may be applied in medicine, pharmacy or biotechnology.

Biocomputers can be an alternative for traditional "silicon-based" computers, which continuous development may be limited due to further miniaturization (imposed by the Heisenberg Uncertainty Principle) and increasing the amount of information between the central processing unit and the main memory (von Neuman bottleneck). The idea of DNA computing came true for the first time in 1994, when Adleman solved the Hamiltonian Path Problem using short DNA oligomers and DNA ligase. In the early 2000s a series of biocomputer models was presented with a seminal work of Shapiro and his colleguas who presented molecular 2 state finite automaton, in which the restriction enzyme, FokI, constituted hardware and short DNA oligomers were software as well as input/output signals. DNA molecules provided also energy for this machine. DNA computing can be exploited in many applications, from study on the gene expression pattern to diagnosis and therapy of cancer. The idea of DNA computing is still in progress in research both in vitro and in vivo and at least promising results of these research allow to have a hope for a breakthrough in the computer science.