DNA polymerase programmed with a hairpin DNA incorporates a multiple-instruction architecture into molecular computing

Abstract

Parallelism is one of the major advantages of molecular computation. A large number of data encoded in DNA molecules can be processed simultaneously by molecular biology techniques, although only a single set of instructions has been implemented in a solution. We have developed a computing machine, called the “whiplash” machine, which is made of DNA polymerase and a hairpin DNA. This machine simulates a finite state machine, executing its own instructions encoded in the DNA moiety, and would thus be applicable to multiple-instruction operation in a solution. In the present study, we explored the feasibility of this novel type of parallelism by applying the whiplash machine in a computation of the directed Hamiltonian path problem. The possible paths in a given graph were represented with different instruction sets, which were then implemented separately by whiplash machines in a test tube. After an autonomous operation of the machines, only the machine that implemented the instruction set corresponding to the Hamiltonian path was recovered from the tube. On the basis of the efficiency of machine operation, which was experimentally determined, 10¹⁰ different instruction sets could be implemented simultaneously in a 1-ml solution.

Introduction

The information processing in living cells possesses the following two features. First, in a living cell, different programs for data processing are implemented simultaneously, and a large number of inputs are thus processed in parallel. Second, these operations are performed autonomously by the capabilities of biomolecules to interact with each other in specific manners, transform metabolic intermediates, and undergo structural changes.

Largely because of these advantages, biomolecules (DNA and DNA-associated enzymes in most cases) have been employed to achieve computations on the molecular scale. The early design of a hypothetical molecular machine involves DNA or RNA polymerase operating on a DNA “data tape” (Bennett, 1982). More recent studies showed that the informative property of DNA actually enables data encoding in molecules, and a large number of data encoded in DNA molecules could be processed simultaneously by molecular biology techniques (Adleman, 1994, Ouyang et al., 1997, Faulhammer et al., 2000, Liu et al., 2000, Sakamoto et al., 2000, Braich et al., 2002). Highly data-parallel computations would thus be achieved, although only a single set of instructions for data processing can be applied to the solution dissolving molecules.

Self-annealing of DNA, based on the specific interaction between complementary sequences, has been utilized to realize autonomous DNA computing. The logic of computation is implemented, without external interference, by a spontaneous reaction of the hairpin formation by DNA strands or the self-assembly of DNA tiles (Sakamoto et al., 2000, Mao et al., 2000). These strands and tiles represent data, which are processed simultaneously according to a single rule of whether hairpin can be formed or whether tiles can be connected with each other. The autonomy in computation has also been achieved by using an enzyme that specifically recognizes a particular sequence in DNA. An autonomous and programmable computing machine has thus been constructed from a restriction enzyme and double-stranded DNA. This machine also implements a single program in a solution, although different inputs could be processed simultaneously (Benenson et al., 2001, Benenson et al., 2003).

In the present study, we used another type of programmable, autonomous machine, called the “whiplash machine” (Sakamoto et al., 1999), to explore the feasibility of implementing different programs in a solution. This machine consists of DNA polymerase and a single-stranded DNA molecule assuming the hairpin form. Since one set of instructions for data processing is encoded in one molecule of hairpin DNA, distinct instruction sets could be implemented in parallel in a solution containing these hairpin DNA molecules. We first showed that the whiplash machine can implement successive logical operations, according to the instructions stored in its DNA moiety. Then, an instance of a hard combinatorial problem was solved, based on a parallel use of the whiplash machines that were programmed differently from each other. Our result demonstrates the feasibility of multiple-instruction operation on the molecular scale.