DNA solution of hard computational problems

Solving the set cover problem and the problem of exact cover by 3-sets in the Adleman–Lipton model

Adleman wrote the first paper in which it is shown that deoxyribonucleic acid (DNA) strands could be employed towards calculating solutions to an instance of the NP-complete Hamiltonian path problem (HPP). Lipton also demonstrated that Adleman's techniques could be used to solve the NP-complete satisfiability (SAT) problem (the first NP-complete problem). In this paper, it is proved how the DNA operations presented by Adleman and Lipton can be used for developing DNA algorithms to resolving the set cover problem and the problem of exact cover by 3-sets.

Solving the 3-SAT problem based on DNA computing

The 3-SAT problem is an NP-complete problem, and many algorithms based on DNA computing have been proposed for solving it since Adleman's pioneering work. This paper presents a new algorithm based on the literal string strategy proposed by Sakamoto et al. Simulation results show that the maximal number of literal strings produced during the computing process is greatly reduced. Moreover, the length of the literal strings is also reduced from m to n at most.

Functional tuning of nucleic acids by chemical modifications: tailored oligonucleotides as drugs, devices, and diagnostics

Chemical modifications of nucleic acids present vast opportunities for extending the functions and properties of these biomolecules. In general, efforts invested in this direction pertain to the introduction of reactive functional groups for further derivatizations of oligonucleotides with numerous reporter groups and for equipping nucleic acids with catalytic chemical moieties. This review deals with representative chemical modifications in the nucleobases, sugars, and the phosphate ester backbone and their application from novel catalytic RNA selection to nucleic acid-based biosensors.

DNA library design for molecular computation

A novel approach to designing a DNA library for molecular computation is presented. The method is employed for encoding binary information in DNA molecules. It aims to achieve a practical discrimination between perfectly matched DNA oligomers and those with mismatches in a large pool of different molecules. The approach takes into account the ability of DNA strands to hybridize in complex structures like hairpins, internal loops, or bulge loops and computes the stability of the hybrids formed based on thermodynamic data. A dynamic programming algorithm is applied to calculate the partition function for the ensemble of structures, which play a role in the hybridization reaction. The applicability of the method is demonstrated by the design of a twelve-bit DNA library. The library is constructed and experimentally tested using molecular biology tools. The results show a high level of specific hybridization achieved for all library words under identical conditions. The method is also applicable for the design of primers for PCR, DNA sequences for isothermal amplification reactions, and capture probes in DNA-chip arrays. The library could be applied for integrated DNA computing of twelve-bit instances of NP-complete combinatorial problems by multi-step DNA selection in microflow reactors.

The general form of 0-1 programming problem based on DNA computing

DNA computing is a novel method of solving a class of intractable computational problems, in which the computing speeds up exponentially with the problem size. Up to now, many accomplishments have been made to improve its performance and increase its reliability. In this paper, we solved the general form of 0-1 programming problem with fluorescence labeling techniques based on surface chemistry by attempting to apply DNA computing to a programming problem. Our method has some significant advantages such as simple encoding, low cost, and short operating time.

A biomolecular computing method based on rho family GTPases

In this paper, we propose a new biomolecular computing method based on Rho family GTPases, and discuss the schemes of representation and operations of molecular computing by Rho family GTPases applied to solve large-scale 3-SAT problems. We also present the optimal condition for the regulation schemes dependent on the temperature, kinase activity, and types of cells. This work is important for potential implementation of biomolecular computers using Rho family GTPases in which an optimized controlling scheme can make the best use of the interactions of signaling pathways in a computing system made by the large-scale abundance of kinases and phosphatases in cells.

DNA molecule provides a computing machine with both data and fuel

The unique properties of DNA make it a fundamental building block in the fields of supramolecular chemistry, nanotechnology, nano-circuits, molecular switches, molecular devices, and molecular computing. In our recently introduced autonomous molecular automaton, DNA molecules serve as input, output, and software, and the hardware consists of DNA restriction and ligation enzymes using ATP as fuel. In addition to information, DNA stores energy, available on hybridization of complementary strands or hydrolysis of its phosphodiester backbone. Here we show that a single DNA molecule can provide both the input data and all of the necessary fuel for a molecular automaton. Each computational step of the automaton consists of a reversible software molecule input molecule hybridization followed by an irreversible software-directed cleavage of the input molecule, which drives the computation forward by increasing entropy and releasing heat. The cleavage uses a hitherto unknown capability of the restriction enzyme FokI, which serves as the hardware, to operate on a noncovalent software input hybrid. In the previous automaton, software input ligation consumed one software molecule and two ATP molecules per step. As ligation is not performed in this automaton, a fixed amount of software and hardware molecules can, in principle, process any input molecule of any length without external energy supply. Our experiments demonstrate 3 x 10(12) automata per microl performing 6.6 x 10(10) transitions per second per microl with transition fidelity of 99.9%, dissipating about 5 x 10(-9) W microl as heat at ambient temperature.

Alternative paradigm for physical computing

We identify a different class of physical systems that are able to form universal logic gates. By analogy with Si(100) surface dimers, we present a model to analyze the trajectories of the fixed points (interpreted as logic states) under variation of the basic parameters. Using the perspective of catastrophe theory, we show that information processing is the result of cycling the parameters of such systems through a path containing a cusp-type catastrophe. We apply this analysis to the construction of an example based on magnetic memory.

A DNA algorithm for the graph coloring problem

A DNA algorithm based on surfaces for the graph coloring problem is presented. First the whole combinatorial color assignments to the vertices of a graph are synthesized and immobilized on a surface; then a vertex is legally colored while those adjacent to it with illegal colors are deleted; and the cycle is repeated until finally the correct color assignments to the graph are reached. Compared with the other DNA algorithms, our algorithm is easy to implement and error-resistant.

DNA solution of a graph coloring problem

The graph-theoretic parameter that has probably received the most attention over the years is the chromatic number. As is well-known, the coloring problem is an NP-Complete problem. In this paper, it has been solved by means of molecular biology techniques. The algorithm is highly parallel and has satisfactory fidelity. This work shows further evidence for the ability of DNA computing to solve NP-Complete problems.

Solution of a 20-variable 3-SAT problem on a DNA computer

A 20-variable instance of the NP-complete three-satisfiability (3-SAT) problem was solved on a simple DNA computer. The unique answer was found after an exhaustive search of more than 1 million (2(20)) possibilities. This computational problem may be the largest yet solved by nonelectronic means. Problems of this size appear to be beyond the normal range of unaided human computation.

A Chinese Postman Problem based on DNA computing

DNA computing is a novel method for solving a class of intractable computational problems, in which the computing can grow exponentially with the problem size. Up to now, many accomplishments have been achieved to improve its performance and increase its reliability. A Chinese Postman Problem has been solved by means of molecular biology techniques in the paper. A small graph was encoded in molecules of DNA, and the "operations" of the computation were performed with standard protocols and enzymes. This work represents further evidence for the ability of DNA computing to solve NP-complete search problems.

From molecular biology to nanotechnology and nanomedicine

Great progress in the development of molecular biology techniques has been seen since the discovery of the structure of deoxyribonucleic acid (DNA) and the implementation of a polymerase chain reaction (PCR) method. This started a new era of research on the structure of nucleic acids molecules, the development of new analytical tools, and DNA-based analyses. The latter included not only diagnostic procedures but also, for example, DNA-based computational approaches. On the other hand, people have started to be more interested in mimicking real life, and modeling the structures and organisms that already exist in nature for the further evaluation and insight into their behavior and evolution. These factors, among others, have led to the description of artificial organelles or cells, and the construction of nanoscale devices. These nanomachines and nanoobjects might soon find a practical implementation, especially in the field of medical research and diagnostics. The paper presents some examples, illustrating the progress in multidisciplinary research in the nanoscale area. It is focused especially on immunogenetics-related aspects and the wide usage of DNA molecules in various fields of science. In addition, some proposals for nanoparticles and nanoscale tools and their applications in medicine are reviewed and discussed.

Equilibrium analysis of the efficiency of an autonomous molecular computer

In the whiplash polymerase chain reaction (WPCR), autonomous molecular computation is implemented in vitro by the recursive, self-directed polymerase extension of a mixture of DNA hairpins. Although computational efficiency is known to be reduced by a tendency for DNAs to self-inhibit by backhybridization, both the magnitude of this effect and its dependence on the reaction conditions have remained open questions. In this paper, the impact of backhybridization on WPCR efficiency is addressed by modeling the recursive extension of each strand as a Markov chain. The extension efficiency per effective polymerase-DNA encounter is then estimated within the framework of a statistical thermodynamic model. Model predictions are shown to provide close agreement with the premature halting of computation reported in a recent in vitro WPCR implementation, a particularly significant result, given that backhybridization had been discounted as the dominant error process. The scaling behavior further indicates completion times to be sufficiently long to render WPCR-based massive parallelism infeasible. A modified architecture, PNA-mediated WPCR (PWPCR) is then proposed in which the occupancy of backhybridized hairpins is reduced by targeted PNA(2)/DNA triplex formation. The efficiency of PWPCR is discussed using a modified form of the model developed for WPCR. Predictions indicate the PWPCR efficiency is sufficient to allow the implementation of autonomous molecular computation on a massive scale.

Programmable and autonomous computing machine made of biomolecules

Devices that convert information from one form into another according to a definite procedure are known as automata. One such hypothetical device is the universal Turing machine, which stimulated work leading to the development of modern computers. The Turing machine and its special cases, including finite automata, operate by scanning a data tape, whose striking analogy to information-encoding biopolymers inspired several designs for molecular DNA computers. Laboratory-scale computing using DNA and human-assisted protocols has been demonstrated, but the realization of computing devices operating autonomously on the molecular scale remains rare. Here we describe a programmable finite automaton comprising DNA and DNA-manipulating enzymes that solves computational problems autonomously. The automaton's hardware consists of a restriction nuclease and ligase, the software and input are encoded by double-stranded DNA, and programming amounts to choosing appropriate software molecules. Upon mixing solutions containing these components, the automaton processes the input molecule via a cascade of restriction, hybridization and ligation cycles, producing a detectable output molecule that encodes the automaton's final state, and thus the computational result. In our implementation 1012 automata sharing the same software run independently and in parallel on inputs (which could, in principle, be distinct) in 120 microl solution at room temperature at a combined rate of 109 transitions per second with a transition fidelity greater than 99.8%, consuming less than 10-10 W.

A DNA computing readout operation based on structure-specific cleavage

We describe a structure-specific cleavage-based READOUT strategy for surface-based DNA computing. The strategy was demonstrated in the solution of a 4-variable/3-satisfiability (SAT) problem. The READOUT step identifies the DNA molecules present at the end of the computational process. The specificity of the sequence detection used here derives from the sequence specificity of DNA hybridization coupled with the structure specificity of the enzymatic cleavage. The process is linear, yielding a higher uniformity of detection of the DNA computing products compared to that obtained with PCR amplification. The structure-specific cleavage-based readout is simple, accurate, and compatible with multiple-word DNA computing.

Using three-dimensional microfluidic networks for solving computationally hard problems

This paper describes the design of a parallel algorithm that uses moving fluids in a three-dimensional microfluidic system to solve a nondeterministically polynomial complete problem (the maximal clique problem) in polynomial time. This algorithm relies on (i) parallel fabrication of the microfluidic system, (ii) parallel searching of all potential solutions by using fluid flow, and (iii) parallel optical readout of all solutions. This algorithm was implemented to solve the maximal clique problem for a simple graph with six vertices. The successful implementation of this algorithm to compute solutions for small-size graphs with fluids in microchannels is not useful, per se, but does suggest broader application for microfluidics in computation and control.

From cells to computers: computing with membranes (P systems)

The aim of this paper is to introduce to the reader the main ideas of computing with membranes, a recent branch of (theoretical) molecular computing. In short, in a cell-like system, multisets of objects evolve according to given rules in the compartments defined by a membrane structure and compute natural numbers as the result of halting sequences of transitions. The model is parallel, nondeterministic. Many variants have already been considered and many problems about them were investigated. We present here some of these variants, focusing on two central classes of results: (1) characterizations of the recursively enumerable sets of numbers and (2) possibilities to solve NP-complete problems in polynomial--even linear--time (of course, by making use of an exponential space). The results are given without proofs. An almost complete bibliography of the domain, at the middle of October 2000, is also provided.

Optically programming DNA computing in microflow reactors

The programmability and the integration of biochemical processing protocols are addressed for DNA computing using photochemical and microsystem techniques. A magnetically switchable selective transfer module (STM) is presented which implements the basic sequence-specific DNA filtering operation under constant flow. Secondly, a single steady flow system of STMs is presented which solves an arbitrary instance of the maximal clique problem of given maximum size N. Values of N up to about 100 should be achievable with current lithographic techniques. The specific problem is encoded in an initial labeling pattern of each module with one of 2N DNA oligonucleotides, identical for all instances of maximal clique. Thirdly, a method for optically programming the DNA labeling process via photochemical lithography is proposed, allowing different problem instances to be specified. No hydrodynamic switching of flows is required during operation -- the STMs are synchronously clocked by an external magnet. An experimental implementation of this architecture is under construction and will be reported elsewhere.

An improved surface-based method for DNA computation

DNA computing is a novel method for solving a class of intractable computational problems, in which the computing time can grow exponentially with problem size. Up to now, many accomplishments have been achieved to improve its performance and increase its reliability, among which a surface-based method is an efficient candidate. In this paper, the surface-based approach proposed by Liu, Q., Wang, L., Frutos, A.G., Condon, A.E., Corn, R.M., and Smith, L.M., 2000, DNA computing on surfaces. Nature 403, 175-179 is analyzed and an improved surface-based method for DNA computation (i.e. the hybrid DNA/optical computing method) is proposed. Compared with Liu et al.'s approach, our method has some significant advantages such as low cost, short operating time, reusable surface and simple experimental steps. Moreover, the concept of combining easily patterned DNA computing steps with equally parallel, but generally uniform and not easily patterned optical computing steps is an important new direction.

A molecular NAND gate based on Watson-Crick base pairing

[reaction: see text] A DNA-binding dye, 4',6-diamidino-2-phenylindole (DAPI) signals AT base pairing with a shift in the fluorescence emission spectrum. The signaling follows W-C base-pairing rules, and both dAMP and dTMP are required for the largest spectral shift. Thus, the dye with its two phosphate receptor sites functions as a molecular NAND gate accepting nucleotides as inputs. Moreover, when the observation wavelength is changed from 470 to 411.5 nm, the gate functions in TRANSFER logic.

Cryptography with DNA binary strands

Biotechnological methods can be used for cryptography. Here two different cryptographic approaches based on DNA binary strands are shown. The first approach shows how DNA binary strands can be used for steganography, a technique of encryption by information hiding, to provide rapid encryption and decryption. It is shown that DNA steganography based on DNA binary strands is secure under the assumption that an interceptor has the same technological capabilities as sender and receiver of encrypted messages. The second approach shown here is based on steganography and a method of graphical subtraction of binary gel-images. It can be used to constitute a molecular checksum and can be combined with the first approach to support encryption. DNA cryptography might become of practical relevance in the context of labelling organic and inorganic materials with DNA 'barcodes'.

Molecular computation by DNA hairpin formation

Hairpin formation by single-stranded DNA molecules was exploited in a DNA-based computation in order to explore the feasibility of autonomous molecular computing. An instance of the satisfiability problem, a famous hard combinatorial problem, was solved by using molecular biology techniques. The satisfiability of a given Boolean formula was examined autonomously, on the basis of hairpin formation by the molecules that represent the formula. This computation algorithm can test several clauses in the given formula simultaneously, which could reduce the number of laboratory steps required for computation.

Biocryptography

A new cryptology that uses biomolecules as carriers of hidden information is described here. The huge dimension of biopolymers permits the insertion there of private messages and the rapidity and specificity of biomolecular interactions facilitate the identification of classified communications. Otherwise, this process can be implemented in a virtual context.

Molecular computation: RNA solutions to chess problems

We have expanded the field of "DNA computers" to RNA and present a general approach for the solution of satisfiability problems. As an example, we consider a variant of the "Knight problem," which asks generally what configurations of knights can one place on an n x n chess board such that no knight is attacking any other knight on the board. Using specific ribonuclease digestion to manipulate strands of a 10-bit binary RNA library, we developed a molecular algorithm and applied it to a 3 x 3 chessboard as a 9-bit instance of this problem. Here, the nine spaces on the board correspond to nine "bits" or placeholders in a combinatorial RNA library. We recovered a set of "winning" molecules that describe solutions to this problem.

DNA computing on surfaces

DNA computing was proposed as a means of solving a class of intractable computational problems in which the computing time can grow exponentially with problem size (the 'NP-complete' or non-deterministic polynomial time complete problems). The principle of the technique has been demonstrated experimentally for a simple example of the hamiltonian path problem (in this case, finding an airline flight path between several cities, such that each city is visited only once). DNA computational approaches to the solution of other problems have also been investigated. One technique involves the immobilization and manipulation of combinatorial mixtures of DNA on a support. A set of DNA molecules encoding all candidate solutions to the computational problem of interest is synthesized and attached to the surface. Successive cycles of hybridization operations and exonuclease digestion are used to identify and eliminate those members of the set that are not solutions. Upon completion of all the multistep cycles, the solution to the computational problem is identified using a polymerase chain reaction to amplify the remaining molecules, which are then hybridized to an addressed array. The advantages of this approach are its scalability and potential to be automated (the use of solid-phase formats simplifies the complex repetitive chemical processes, as has been demonstrated in DNA and protein synthesis). Here we report the use of this method to solve a NP-complete problem. We consider a small example of the satisfiability problem (SAT), in which the values of a set of boolean variables satisfying certain logical constraints are determined.

Progress toward demonstration of a surface based DNA computation: a one word approach to solve a model satisfiability problem

A multi-base encoding strategy is used in a one word approach to surface-based DNA computation. In this designed DNA model system, a set of 16 oligonucleotides, each a 16mer, is used with the format 5'-FFFFvvvvvvvvFFFF-3' in which 4-8 bits of data are stored in eight central variable ('v') base locations, and the remaining fixed ('F') base locations are used as a word label. The detailed implementations are reported here. In order to achieve perfect discrimination between each oligonucleotide, the efficiency and specificity of hybridization discrimination of the set of 16 oligonucleotides were examined by carrying out the hybridization of each individual fluorescently tagged complement to an array of 16 addressed immobilized oligonucleotides. A series of preliminary hybridization experiments are presented and further studies about hybridization, enzymatic destruction, read out and demonstrations of a SAT problem are forthcoming.

On solving 3CNF-satisfiability with an in vivo algorithm

Several in vitro DNA algorithms have been proposed in the literature for solving various combinatorial search problems. The next logical step is the critical examination of whether or not such computation can be performed within the cellular environment. We consider the possibility of solving 3-conjunctive-normal-form Satisfiability with one possible in vivo algorithm. The exact biological details still remain to be defined and seem beyond the capabilities of current technologies, but perhaps, this will serve as a springboard for further theoretical inquiry into in vivo approaches.

DNA implementation of addition in which the input strands are separate from the operator strands

A DNA representation of Boolean logic for which the input strands are separate from the operator strands is described and used to construct a two-bit DNA adder. The successful operation of the adder for several test inputs demonstrates that digital molecular computation with a complexity of order 30 gates is feasible.

A biomolecular implementation of logically reversible computation with minimal energy dissipation

Energy dissipation associated with logic operations imposes a fundamental physical limit on computation and is generated by the entropic cost of information erasure, which is a consequence of irreversible logic elements. We show how to encode information in DNA and use DNA amplification to implement a logically reversible gate that comprises a complete set of operators capable of universal computation. We also propose a method using this design to connect, or 'wire', these gates together in a biochemical fashion to create a logic network, allowing complex parallel computations to be executed. The architecture of the system permits highly parallel operations and has properties that resemble well known genetic regulatory systems.

New computing paradigms suggested by DNA computing: computing by carving

Inspired by the experiments in the emerging area of DNA computing, a somewhat unusual type of computation strategy was recently proposed by one of us: to generate a (large) set of candidate solutions of a problem, then remove the non-solutions such that what remains is the set of solutions. This has been called a computation by carving. This idea leads both to a speculation with possible important consequences--computing non-recursively enumerable languages--and to interesting theoretical computer science (formal language) questions.

Three dimensional DNA structures in computing

We show that 3-dimensional graph structures can be used for solving computational problems with DNA molecules. Vertex building blocks consisting of k-armed (k = 3 or 4) branched junction molecules are used to form graphs. We present procedures for the 3-SAT and 3-vertex-colorability problems. Construction of one graph structure (in many copies) is sufficient to determine the solution to the problem. In our proposed procedure for 3-SAT, the number of steps required is equal to the number of variables in the formula. For the 3-vertex-colorability problem, the procedure requires a constant number of steps regardless of the size of the graph.