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

Solving the maximal matching problem with DNA molecules in Adleman–Lipton model

The maximal matching problem (MMP) is to find maximal edge subsets in a given undirected graph, that no pair of edges are adjacent in the subsets. It is a vitally important NP-complete problem in graph theory and applied mathematics, having numerous real life applications in optimal combination and linear programming fields. It can be difficultly solved by the electronic computer in exponential level time. Meanwhile in previous studies deoxyribonucleic acid (DNA) molecular operations usually were used to solve NP-complete continuous path search problems, e.g. HPP, traveling salesman problem, rarely for NP-hard problems with discrete vertices or edges solutions, such as the minimum vertex cover problem, graph coloring problem and so on. In this paper, we present a DNA algorithm for solving the MMP with DNA molecular operations. For an undirected graph with [Formula: see text] vertices and [Formula: see text] edges, we reasonably design fixed length DNA strands representing vertices and edges of the graph, take appropriate steps and get the solutions of the MMP in proper length range using [Formula: see text] time. We extend the application of DNA molecular operations and simultaneously simplify the complexity of the computation.

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.

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.

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.

Determination of the reopening temperature of a DNA hairpin structure in vitro

A novel method, based upon primer extension, has been developed for measuring the reopening temperature of a single type of DNA hairpin structure. Two DNA oligonucleotides have been utilized and designated as primers 1 and 2. Primer 1, with its 5- and 3'-termini fully complementary to the hairpin flanking sequences, was used to evaluate primer extension conditions, and primer 2, with its 3'-end competing with the DNA hairpin stem, was used to detect the DNA hairpin reopening temperature. A single DNA hairpin structure was formed on the DNA template by thermal denaturation and renaturation, and this hairpin structure was predicted to prevent the annealing of the 3'-end of primer 2 with the template DNA, which leads to no primer extension. By incubating at different temperatures, the DNA hairpin structure can be reopened at a particular temperature where the primer extension can be carried out. This resulted in the appearance of double-stranded DNA that was detected on an agarose gel. This temperature is defined here as the hairpin reopening temperature.