DNA solution of hard computational problems

Fast parallel molecular algorithms for DNA-based computation: solving the elliptic curve discrete logarithm problem over GF2

Elliptic curve cryptographic algorithms convert input data to unrecognizable encryption and the unrecognizable data back again into its original decrypted form. The security of this form of encryption hinges on the enormous difficulty that is required to solve the elliptic curve discrete logarithm problem (ECDLP), especially over GF(2ⁿ), n ∈ Z⁺. This paper describes an effective method to find solutions to the ECDLP by means of a molecular computer. We propose that this research accomplishment would represent a breakthrough for applied biological computation and this paper demonstrates that in principle this is possible. Three DNA-based algorithms: a parallel adder, a parallel multiplier, and a parallel inverse over GF(2ⁿ) are described. The biological operation time of all of these algorithms is polynomial with respect to n. Considering this analysis, cryptography using a public key might be less secure. In this respect, a principal contribution of this paper is to provide enhanced evidence of the potential of molecular computing to tackle such ambitious computations.

Solving the SAT problem using a DNA computing algorithm based on ligase chain reaction

A new DNA computing algorithm based on a ligase chain reaction is demonstrated to solve an SAT problem. The proposed DNA algorithm can solve an n-variable m-clause SAT problem in m steps and the computation time required is O (3m+n). Instead of generating the full-solution DNA library, we start with an empty test tube and then generate solutions that partially satisfy the SAT formula. These partial solutions are then extended step by step by the ligation of new variables using Taq DNA ligase. Correct strands are amplified and false strands are pruned by a ligase chain reaction (LCR) as soon as they fail to satisfy the conditions. If we score and sort the clauses, we can use this algorithm to markedly reduce the number of DNA strands required throughout the computing process. In a computer simulation, the maximum number of DNA strands required was 2(0.48n) when n=50, and the exponent ratio varied inversely with the number of variables n and the clause/variable ratio m/n. This algorithm is highly space-efficient and error-tolerant compared to conventional brute-force searching, and thus can be scaled-up to solve large and hard SAT problems.

Computing by polymerase chain reaction

A mathematical notation is introduced to represent, at a symbolic level, different mechanisms of DNA recombination, and a 'PCR lemma' is proven by analytically describing the combinatorial properties of the polymerase chain reaction process. This approach led to the discovery of novel techniques, based on a form of PCR which we called cross pairing PCR (briefly XPCR). They were mathematically analyzed and already experimentally proven in different contexts, such as DNA extraction and recombination. Thus, a mathematical analysis of standard methodologies may highlight novel mechanisms of DNA recombination and this can provide new technologies for DNA manipulation.

A Programmable Biomolecular Computing Machine with Bacterial Phenotype Output

The main advantage of autonomous biomolecular computing devices over electronic computers is their ability to interact directly with biological systems. No interface is required since all components of molecular computers, including hardware, software, input, and output are molecules that interact in solution along a cascade of programmable chemical events. Here, we demonstrate for the first time that the output of a computation preduced by a molecular finite automaton can be a visible bacterial phenotype. Our 2-symbol-2-state finite automaton utilized linear double-stranded DNA inputs that were prepared by inserting a string of six base pair symbols into the lacZ gene on the pUC18 plasmid. The computation resulted in a circular plasmid that differed from the original pUC18 by either a 9 base pair (accepting state) or 11 base pair insert (unaccepting state) within the lacZ alpha region gene. Upon transformation and expression of the resultant plasmids in E. coli, the accepting state was represented by production of functional beta-galactosidase and formation of blue colonies on X-gal medium. In contrast, the unaccepting state was represented by white colonies due to a shift in the open reading frame of lacZ.

A P system and a constructive membrane-inspired DNA algorithm for solving the Maximum Clique Problem

We present a P system with replicated rewriting to solve the Maximum Clique Problem for a graph. Strings representing cliques are built gradually. This involves the use of inhibitors that control the space of all generated solutions to the problem. Calculating the maximum clique for a graph is a highly relevant issue not only on purely computational grounds, but also because of its relationship to fundamental problems in genomics. We propose to implement the designed P system by means of a DNA algorithm. This algorithm is then compared with two standard papers that addressed the same problem and its DNA implementation in the past. This comparison is carried out on the basis of a series of computational and physical parameters. Our solution features a significantly lower cost in terms of time, the number and size of strands, as well as the simplicity of the biological implementation.

Differential dependence on DNA ligase of type II restriction enzymes: A practical way toward ligase-free DNA automaton

DNA computing study is a new paradigm in computer science and biological computing fields. As one of DNA computing approaches, DNA automaton is composed of the hardware, input DNA molecule and state transition molecules. By now restriction enzymes are key hardware for DNA computing automaton. It has been found that DNA computing efficiency may be independent on DNA ligases when type IIS restriction enzymes like FokI are used as hardware. In this study, we compared FokI with four other distinct enzymes HgaI, BsmFI, BbsI, and BseMII, and found their differential independence on T4 DNA ligase when performing automaton reactions. Since DNA automaton is a potential powerful tool to tackle gene relationship in genomic network scale, the feasible ligase-free DNA automaton may set an initial base to develop functional DNA automata for various DNA technology development and implications in genetics study in the near future.

Biomolecular computing: Is it ready to take off?

Biomolecular computing is an emerging field at the interface of computer science, biological science and engineering. It uses DNA and other biological materials as the building blocks for construction of living computational machines to solve difficult combinatorial problems. In this article, notable advances in the biomolecular computing are reviewed and challenges associated with this multidisciplinary research are addressed. Finally, several perspectives are given based on the review of biomolecular computing.

Modeling molecular computing systems by an artificial chemistry - its expressive power and application

Artificial chemistries are mainly used to construct virtual systems that are expected to show behavior similar to living systems. In this study, we explore possibilities of applying an artificial chemistry to modeling natural biochemical systems-or, to be specific, molecular computing systems-and show that it may be a useful modeling tool for molecular computation. We previously proposed an artificial chemistry based on string pattern matching and recombination. This article first demonstrates that this artificial chemistry is computationally universal if it has only rules that have one reactant or two reactants. We think this is a good property of an artificial chemistry that models molecular computing, because natural elementary chemical reactions, on which molecular computing is based, are mostly unimolecular or bimolecular. Then we give two illustrative example models for DNA computing in our artificial chemistry: one is for the type of computation called the Adleman-Lipton paradigm, and the other is for a DNA implementation of a finite automaton. Through the construction of these models we observe preferred properties of the artificial chemistry for modeling molecular computing, such as having no spatial structure and being flexible in choosing levels of abstraction.

A systems perspective to digital structures in molecular analysis

Within the last decade, the advance of miniaturization has opened the window to new systems that permit digital and molecular science to intersect, suggesting a new role for organic chemistry. Currently, fusion of molecules and electronic digits, as well as molecular-based digital structures, have expanded the conventional interpretation of the digit. This emergence has already generated new technological platforms with unique applications for molecular analysis and computation. We provide a brief overview of the conventional understanding of digital devices, examine the concept of molecular-based digits, and suggest new architectures by examining studies conducted on the compact discs. This analysis presents a perspective for the unique interaction of molecules and digits and the development of digital-based platforms for molecular analysis.

Complete Pattern Matching for DNA Computing

Pattern matching is essential in many applications such as information retrieval, logic programming, theorem-proving, term rewriting and DNA-computing. It usually breaks down into two categories: root and complete pattern matching. Root matching determines whether a subject term is an instance of a pattern in a pattern set while complete matching determines whether a subject term contains a sub-term that is an instance of a pattern in a pattern set. For the sake of efficiency, root pattern matching need to be deterministic and lazy. Furthermore, complete pattern matching also needs to be parallel. Unlike root pattern matching, complete matching received little interest from the researchers of the field. In this paper, we present a novel deterministic multi-threaded complete matching method. This method subsumes a deterministic lazy root matching technique that was developped by the authors in an earlier work. We evaluate the performance of proposed method using theorem-proving and DNA-computing applications.

Multiplying with DNA

A functional machine is not only an assembly of parts, but also an assembly of processes. The processing of each part must obey laws that respect to the property of this part. For example, building any kind of computer entails selecting appropriate components and assembling their properties to function in computation. Here, we describe computation using a DNA strand as the basic unit and we have used this unit to achieve the function of multiplication. We exploit the phenomenon of DNA hybridization, in which each strand can represent two individual units that can pair to form a single unit. We represent the numbers we multiply in binary, with different lengths representing each digit present in the number. In principle, all combinations of the numbers will be present in solution. Following hybridization, there is present a collection of duplex molecules that are tailed by single-stranded ends. These intermediates are converted to fully duplex molecules by filling in the ends with DNA polymerase. The lengths that are present represent the digits that are present, and they may be separated by denaturing PAGE. The results give a series of bands for each power of two. The number of bands in the size domain for a particular power of two is converted to binary and the sum of all present bands is then added together. Experimentally, the result of this process always yields the correct answer.

Solving satisfiability problems using a novel microarray-based DNA computer

An algorithm based on a modified sticker model accompanied with an advanced MEMS-based microarray technology is demonstrated to solve SAT problem, which has long served as a benchmark in DNA computing. Unlike conventional DNA computing algorithms needing an initial data pool to cover correct and incorrect answers and further executing a series of separation procedures to destroy the unwanted ones, we built solutions in parts to satisfy one clause in one step, and eventually solve the entire Boolean formula through steps. No time-consuming sample preparation procedures and delicate sample applying equipment were required for the computing process. Moreover, experimental results show the bound DNA sequences can sustain the chemical solutions during computing processes such that the proposed method shall be useful in dealing with large-scale problems.

Scalability of the surface-based DNA algorithm for 3-SAT

Since Adleman first proposed DNA computing for the Hamiltonian path problem, several authors have reported DNA computing for 3-SAT. Previous research presented DNA computing on surfaces and demonstrated how to solve a four-variable four-clause instance of 3-SAT, and claimed that the surface-based approach was designed to scale up to larger problems. In this paper we establish an error model for the incomplete "mark" and imperfect "destroy" operations. By using the error model we argue that no matter how large the "mark" and "destroy" rates are we can always give satisfiable instances of 3-SAT such that no DNA strands remain on the surface at the end of the computation. By the surface-based approach the satisfiable instances of 3-SAT would be misdetermined to be unsatisfiable. Thus, the error leads to an incorrect result of the SAT computation. Furthermore, given the "mark" rate p and the "not-destroy" rate rho, we find that the approach can only solve at most N-variable instances of 3-SAT problems, where N=[(2+beta(2)+2+2 square root beta (2))/beta(2)] in which beta=1-1/(p+rhoq) and q=1-p and [a] is the greatest integer less than a or equal to a.

Deoxyribozymes that recode sequence information

Allosteric nucleic acid ligases have been used previously to transform analyte-binding into the formation of oligonucleotide templates that can be amplified and detected. We have engineered binary deoxyribozyme ligases whose two components are brought together by bridging oligonucleotide effectors. The engineered ligases can 'read' one sequence and then 'write' (by ligation) a separate, distinct sequence, which can in turn be uniquely amplified. The binary deoxyribozymes show great specificity, can discriminate against a small number of mutations in the effector, and can read and recode DNA information with high fidelity even in the presence of excess obscuring genomic DNA. In addition, the binary deoxyribozymes can read non-natural nucleotides and write natural sequence information. The binary deoxyribozyme ligases could potentially be used in a variety of applications, including the detection of single nucleotide polymorphisms in genomic DNA or the identification of short nucleic acids such as microRNAs.

A mathematical formulation of DNA computation

DNA computation is to use DNA molecules for information storing and processing. The task is accomplished by encoding and interpreting DNA molecules in suspended solutions before and after the complementary binding reactions. DNA computation is attractive, due to its fast parallel information processing, remarkable energy efficiency, and high storing capacity. Challenges currently faced by DNA computation are: 1) lack of theoretical computational models for applications and 2) high error rate for implementation. This paper attempts to address these problems from mathematical modeling and genetic coding aspects. The first part of this paper presents a mathematical formulation of DNA computation. The model may serve as a theoretical framework for DNA computation. In the second part, a genetic code based DNA computation approach is presented to reduce error rate for implementation, which has been a major concern for DNA computation. The method provides a promising alternative to reduce error rate for DNA computation.

Experimentally Constructing Semantic Models Based on DNA Computing

We propose a new DNA-based semantic model, constructed of DNA molecules, called asemantic model based on molecular computing(SMC). It is structured as a graph formed by the set of all (attribute, attribute value) pairs contained in the set of represented objects, plus a tag node for each object. Each path in the network, from an initial object-representing tag node to the terminal node, represents the object named on the tag. Inputting a set of input strands the forms object-representing dsDNAs via parallel self-assembly from encoded ssDNAs representing both attributes and attribute values (nodes), as directed by ssDNA splitting strands representing relations (edges) in the network. The success of experiments in constructing a small test model demonstrates that our proposed model suitably represents knowledge to storing vast amounts of information at high density.

Procedures for a dynamical system on {0,1}n with DNA molecules

In this paper, an improved form of DNA representations of elements in {0,1}n, which was first proposed by Fujiwara et al. [Fujiwara, A., Matsumoto, K., Chen, W., 2004. Procedures for logic and arithmetic operations with DNA molecules. Int. J. Found. Comput. Sci. 15, 461-474], is given. Using this improved representations, a procedure for cycling shift is proposed, and this procedure can be implemented in O(1) lab steps theoretically. Based on the operation for cycling shift, dynamic behavior of an operator on {0,1}n is investigated by DNA molecules.

Molecular solutions to the binary integer programming problem based on DNA computation

Binary optimization is a widely investigated topic in integer linear programming. This study proposes a DNA-based computing algorithm for solving the significantly large binary integer programming (BIP) problem. The proposed approach is based upon Adleman and Lipton's DNA operations to solve the BIP problem. The potential of DNA computation for the BIP problem is promising given the operational time complexity of O(nxk).

Solving maximum cut problems in the Adleman-Lipton model

In this paper, we consider a procedure for solving maximum cut problems in the Adleman-Lipton model. The procedure works in O(n2) steps for maximum cut problems of an undirected graph with n vertices.

The surface-based approach for DNA computation is unreliable for SAT

Previous research presented DNA computing on surfaces, which applied to each clause three operations:"mark","destroy", and "unmark", and demonstrated how to solve a four-variable four-clause instance of the 3-SAT. It was claimed that only the strands satisfying the problem remained on the surface at the end of the computation and the surface-based approach was capable of scaling up to larger 3-SAT problems. Accordingly, the identities of the strands were only determined in the"readout" step for the correct solutions to the problem without checking if the strands really satisfied the problem. Thus, based on the claim above, the surface-based approach became a polynomial-time algorithm. In this paper, we show that for some instance of SAT, at the end of the computation all the remaining strands falsify the instance. However, by the previous claim all the strands falsifying the problems would be regarded as the correct solutions to the problems. Therefore, the DNA computing on surfaces is unreliable. For this reason, it is necessary to add a "verify" step after the "readout" step to check if the strands remaining on the surface at the end of the computation really satisfy the problem.

Fast parallel molecular algorithms for DNA-based computation: factoring integers

The RSA public-key cryptosystem is an algorithm that converts input data to an unrecognizable encryption and converts the unrecognizable data back into its original decryption form. The security of the RSA public-key cryptosystem is based on the difficulty of factoring the product of two large prime numbers. This paper demonstrates to factor the product of two large prime numbers, and is a breakthrough in basic biological operations using a molecular computer. In order to achieve this, we propose three DNA-based algorithms for parallel subtractor, parallel comparator, and parallel modular arithmetic that formally verify our designed molecular solutions for factoring the product of two large prime numbers. Furthermore, this work indicates that the cryptosystems using public-key are perhaps insecure and also presents clear evidence of the ability of molecular computing to perform complicated mathematical operations.

Fast parallel molecular solutions for DNA-based supercomputing: the subset-product problem

In this paper our main purpose is to give molecular solutions for the subset-product problem. In order to achieve this, we propose three DNA-based algorithms--parallel adder, parallel multiplier and parallel comparator--that formally verify our designed molecular solutions for the subset-product problem. We also show that Boolean circuits are not needed to perform mathematical operations on a molecular computer. Furthermore, this work indicates that the subset-product problem is solved and also presents clear evidence of the ability of molecular computing to perform complicated mathematical operations.

A DNA solution of SAT problem by a modified sticker model

Among various DNA computing algorithms, it is very common to create an initial data pool that covers correct and incorrect answers at first place followed by a series of selection process to destroy the incorrect ones. The surviving DNA sequences are read as the solutions to the problem. However, algorithms based on such a brute force search will be limited to the problem size. That is, as the number of parameters in the studied problem grows, eventually the algorithm becomes impossible owing to the tremendous initial data pool size. In this theoretical work, we modify a well-known sticker model to design an algorithm that does not require an initial data pool for SAT problem. We propose to build solution sequences in parts to satisfy one clause in a step, and eventually solve the whole Boolean formula after a number of steps. Accordingly, the size of data pool grows from one sort of molecule to the number of solution assignments. The proposed algorithm is expected to provide a solution to SAT problem and become practical as the problem size scales up.

DNA algorithm for an unbounded fan-in Boolean circuit

In this paper, we present a new DNA-based evaluation algorithm for a Boolean circuit that employs standard bio-molecular techniques. The algorithm operates on an unbounded fan-in Boolean circuit consisting of AND and OR gates. The whole simulation of our algorithm is proposed in a single test tube in O(1) time complexity and is much easier to implement in the laboratory than previously described models. Furthermore, the algorithm allows for evaluating any number of Boolean circuits in parallel in a single test tube.

DNA databases

This paper presents DNA algorithms for five relational algebra database operations, selection, projection, union, set difference, and Cartesian product on so-called DNA databases. A DNA database is a database where data records are encoded as DNA strands. The five operations mentioned before are fundamental in the field of databases and perform most of the data retrieval operations on current databases.

Boolean logic functions of a synthetic peptide network

Living cells can process rapidly and simultaneously multiple extracellular input signals through the complex networks of evolutionary selected biomolecular interactions and chemical transformations. Recent approaches to molecular computation have increasingly sought to mimic or exploit various aspects of biology. A number of studies have adapted nucleic acids and proteins to the design of molecular logic gates and computational systems, while other works have affected computation in living cells via biochemical pathway engineering. Here we report that de novo designed synthetic peptide networks can also mimic some of the basic logic functions of the more complex biological networks. We show that segments of a small network whose graph structure is composed of five nodes and 15 directed edges can express OR, NOR, and NOTIF logic.

Potential for enlarging DNA memory: the validity of experimental operations of scaled-up nested primer molecular memory

DNA is an attractive memory unit because of its immense information density. Here, we describe a memory model made of DNA, called Nested Primer Molecular Memory (NPMM). NPMM consists of many DNA strands, and each DNA strand consists of two areas: a data area and a data address area. When the address of target data is specified, only the target data can be extracted from NPMM. In this paper, we evaluate the validity of the basic operations of NPMM and then discuss the feasibility of scaled-up NPMM through some laboratory experiments. In the latter, we deal with scaled-up NPMM simulated by the Concentration Scaling method.

Is optimal solution of every NP-complete or NP-hard problem determined from its characteristic for DNA-based computing

Cook's Theorem [Cormen, T.H., Leiserson, C.E., Rivest, R.L., 2001. Introduction to Algorithms, second ed., The MIT Press; Garey, M.R., Johnson, D.S., 1979. Computer and Intractability, Freeman, San Fransico, CA] is that if one algorithm for an NP-complete or an NP-hard problem will be developed, then other problems will be solved by means of reduction to that problem. Cook's Theorem has been demonstrated to be correct in a general digital electronic computer. In this paper, we first propose a DNA algorithm for solving the vertex-cover problem. Then, we demonstrate that if the size of a reduced NP-complete or NP-hard problem is equal to or less than that of the vertex-cover problem, then the proposed algorithm can be directly used for solving the reduced NP-complete or NP-hard problem and Cook's Theorem is correct on DNA-based computing. Otherwise, a new DNA algorithm for optimal solution of a reduced NP-complete problem or a reduced NP-hard problem should be developed from the characteristic of NP-complete problems or NP-hard problems.

DNA nanodevices

The molecular recognition properties of DNA molecules combined with the distinct mechanical properties of single and double strands of DNA can be utilized for the construction of nanodevices, which can perform ever more tasks with possible applications ranging from nanoconstruction to intelligent drug delivery. With the help of DNA it is possible to construct machinelike devices that are capable of rotational motion, pulling and stretching, or even unidirectional motion. It is possible to devise autonomous nanodevices, to grab and release molecules, and also to perform simple information-processing tasks.

Molecular solutions for the subset-sum problem on DNA-based supercomputing

In this paper our main purpose is to give molecular solutions for the subset-sum problem. In order to achieve this, we propose a DNA-based algorithm of an n-bit parallel adder and a DNA-based algorithm of an n-bit parallel comparator to formally verify our designed molecular solutions for the subset-sum problem.

Hairpin formation in DNA computation presents limits for large NP-complete problems

Recently, several DNA computing paradigms for NP-complete problems were presented, especially for the 3-SAT problem. Can the present paradigms solve more than just trivial instances of NP-complete problems? In this paper we show that with high probability potentially deleterious features such as severe hairpin loops would be likely to arise. If DNA strand x of length n and the 'complement' of the reverse of x have l match bases, then x forms a hairpin loop and is called a (n,l)-hairpin format. Let gamma=2l/n. Then gamma can be considered as a measurement of the stability of hairpin loops. Let p(n,l) be the probability that a n-mer DNA strand is a (n,l)-hairpin format, and q(n,l)((m)) be the probability that m ones are chosen at random from 4(n) n-mer oligonucleotides such that at least one of the m ones is a (n,l)-hairpin format. Then, q(n,l)((m))=1-(1-p(n,l))(m)=mp(n,l). If we require q(n,l)((m))<a, where a<1, then m<ln(1-a)/ln(1-p(n,l))=a/p(n,l). It means that we can only solve the instances of size m of NP-complete problems. Clearly the greater p(n,l), the smaller m, and the smaller a the smaller m. In this paper, we show p(n,l) is high. Therefore, the present DNA computing paradigms cannot solve large NP-complete problems. For example, if n=20, used in Adleman and Lipton's paradigm, gamma=50% and a=50%, then m is almost 12.

Stochastic computing with biomolecular automata

Stochastic computing has a broad range of applications, yet electronic computers realize its basic step, stochastic choice between alternative computation paths, in a cumbersome way. Biomolecular computers use a different computational paradigm and hence afford novel designs. We constructed a stochastic molecular automaton in which stochastic choice is realized by means of competition between alternative biochemical pathways, and choice probabilities are programmed by the relative molar concentrations of the software molecules coding for the alternatives. Programmable and autonomous stochastic molecular automata have been shown to perform direct analysis of disease-related molecular indicators in vitro and may have the potential to provide in situ medical diagnosis and cure.

An autonomous molecular computer for logical control of gene expression

Early biomolecular computer research focused on laboratory-scale, human-operated computers for complex computational problems. Recently, simple molecular-scale autonomous programmable computers were demonstrated allowing both input and output information to be in molecular form. Such computers, using biological molecules as input data and biologically active molecules as outputs, could produce a system for 'logical' control of biological processes. Here we describe an autonomous biomolecular computer that, at least in vitro, logically analyses the levels of messenger RNA species, and in response produces a molecule capable of affecting levels of gene expression. The computer operates at a concentration of close to a trillion computers per microlitre and consists of three programmable modules: a computation module, that is, a stochastic molecular automaton; an input module, by which specific mRNA levels or point mutations regulate software molecule concentrations, and hence automaton transition probabilities; and an output module, capable of controlled release of a short single-stranded DNA molecule. This approach might be applied in vivo to biochemical sensing, genetic engineering and even medical diagnosis and treatment. As a proof of principle we programmed the computer to identify and analyse mRNA of disease-related genes associated with models of small-cell lung cancer and prostate cancer, and to produce a single-stranded DNA molecule modelled after an anticancer drug.

DNA computation model to solve 0–1 programming problem

0-1 programming problem is an important problem in opsearch with very widespread applications. In this paper, a new DNA computation model utilizing solution-based and surface-based methods is presented to solve the 0-1 programming problem. This model contains the major benefits of both solution-based and surface-based methods; including vast parallelism, extraordinary information density and ease of operation. The result, verified by biological experimentation, revealed the potential of DNA computation in solving complex programming problem.