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.     

Autonomous DNA computing machine based on photochemical gate transition

We report the construction of a one-pot autonomous DNA computing machine based on photochemical gate transition (photocleavage, hybridization, and photoligation), and we performed binary digit additions using this machine. In our method, both photochemical DNA manipulations previously reported, photoligation via 5-carboxyvinyldeoxyuridene (cvU) containing ODN and photocleavage via carbazole-modified ODN, were employed. The binary digit additions were autonomously carried out by one-time irradiation at 366 nm in the single test tube. The fluorescence readout by the DNA chip was in good agreement with the correct answer of binary digit additions. We believe that this system is easily applicable to correlation analysis between SNPs as well as other binary digit processing, such as subtraction.     

Development of DNA computing and information processing based on DNA-strand displacement

DNA computing, currently a hot research field in information processing, has the advantages of parallelism, low energy consumption, and high storability, therefore, it has been applied to a variety of complicated computational problems. The emerging field of DNA nanotechnology has also developed quickly; within it, the method of DNA strand displacement has drawn great attention because it is self-induced, sensitive, accurate, and operationally simple. This article summarizes five aspects of the recent developments of DNA-strand displacement in DNA computing:(1) cascading circuits;(2) catalyzed reaction;(3) logic computation;(4) DNA computing on surfaces; and(5) logic computing based on nanoparticles guided by strand displacement. The applications and mechanisms of strand displacement in DNA computing are discussed and possible future developments are presented.     

Solving probability reasoning based on DNA strand displacement and probability modules

In computation biology, DNA strand displacement technology is used to simulate the computation process and has shown strong computing ability. Most researchers use it to solve logic problems, but it is only rarely used in probabilistic reasoning. To process probabilistic reasoning, a conditional probability derivation model and total probability model based on DNA strand displacement were established in this paper. The models were assessed through the game “read your mind.” It has been shown to enable the application of probabilistic reasoning in genetic diagnosis.     

Molecular solution to the optimal linear arrangement problem based on DNA computation

Due to massive parallelism, enormous memory storage and very low energy consumption, biomolecular operations have been suggested to solve various NP-hard problems that are beyond the capability of the fastest known digital computer. The optimal linear arrangement (OLA) problem is a well-known NP-hard combinatorial optimization problem. Based on a DNA computational model, this paper describes a novel algorithm for the OLA problem, which is executed in O(n ³log₂ n) DNA operations on tubes of (nK + n + m + L + 1)-bits DNA strands, where and . With the advance in molecular biology techniques, this algorithm may be of practical utility.     

Visualization of DNA sequences based on 3DD-Curves

In this paper we (1) introduce a new 3D graphical representation of DNA sequences; (2) visualize DNA sequences based on 3DD-Curves; (3) provide a new invariant of DNA sequences based on our 3DD-Curve. All this represents a new development of graphical representation and numerical characterization for DNA sequences.     

Solving the continuum problem of collision-induced dissociation and recombination

The stationary Schrödinger equation with continuum boundary conditions is solved numerically. Quantum probabilities of collision-induced dissociation/recombination for models with two degrees of freedom are calculated using an integral-equation matching procedure together with analytical wavefunctions or finite element solutions alternatively. Model results for He+Ne₂ → He+2Ne are reported.     

Electrochemical detection of DNA 3′-phosphatases based on surface-extended DNA nanotail strategy

Determination of DNA dephosphorylation is of great value due to its vital role in many cellular processes. Here we report a surface-extended DNA nanotail strategy for simple and ultrasensitive detection of DNA 3′-phosphatases by terminal deoxynucleotidyl transferase (TdT) mediated signal amplification. In this work, DNA probes labeled with thiols at their 5′ terminals and phosphoryls at 3′ terminals are immobilized on gold electrode and are used as substrates for DNA 3′-phosphatases, taking T4 polynucleotide kinase phosphatase (T4PNKP) as an example. T4PNKP can catalyze the dephosphorylation reaction of the substrate DNA, followed by the formation of a long DNA strand by TdT on its 3′ terminal hydroxyl, leading to an evident chronocoulometry signal enhancement. The proposal presents a considerable analytical performance with low detection limit and wide linear range, making it promise to be applied in the fields of DNA dephosphorylation related processes, drug discovery, and clinical diagnostics.     

Signal amplification for DNA detection based on the HRP-functionalized Fe3O4 nanoparticles

An electrochemical approach for the sensitive detection of sequence-specific DNA has been developed. Horseradish peroxidase (HRP) assembled on the Fe₃O₄ nanoparticles (NPs) were utilized as signal amplification sources. High-content HRP was adsorbed on the Fe₃O₄ NPs via layer-by-layer (LbL) technique to prepare HRP-functionalized Fe₃O₄ NPs. Signal probe and diluting probe were then immobilized on the HRP-functionalized Fe₃O₄ NPs through the bridge of Au NPs. Thereafter, the resulting DNA-Au-HRP-Fe₃O₄ (DAHF) bioconjugates were successfully anchored to the gold nanofilm (GNF) modified electrode surface for the construction of sandwich-type electrochemical DNA biosensor. The electrochemical behaviors of the prepared biosensor had been investigated by the cyclic voltammetry (CV), chronoamperometry (i-t), and electrochemical impedance spectroscopy (EIS). Under optimal conditions, the proposed strategy could detect the target DNA down to the level of 0.7 fmol with a dynamic range spanning 4 orders of magnitude and exhibited excellent discrimination to two-base mismatched DNA and non-complementary DNA sequences.     

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.     

New invariant of DNA sequence based on 3DD-curves and its application on phylogeny

The Z_inv, a new invariant based on 3DD-curves of DNA sequence, which is simple for calculation and it approximates to the leading eigenvalues of the matrix associated with DNA sequence. The utility of our invariant is illustrated on the DNA sequence of 11 species. In this study, we use the Z_inv to analyze the phylogenetic relationships for the seven HA (H5N1) sequences of avian influenza virus.     

An integrated microfluidic processor for single nucleotide polymorphism-based DNA computing

An integrated microfluidic processor is developed that performs molecular computations using single nucleotide polymorphisms (SNPs) as binary bits. A complete population of fluorescein-labeled DNA "answers" is synthesized containing three distinct polymorphic bases; the identity of each base (A or T) is used to encode the value of a binary bit (TRUE or FALSE). Computation and readout occur by hybridization to complementary capture DNA oligonucleotides bound to magnetic beads in the microfluidic device. Beads are loaded into sixteen capture chambers in the processor and suspended in place by an external magnetic field. Integrated microfluidic valves and pumps circulate the input DNA population through the bead suspensions. In this example, a program consisting of a series of capture/rinse/release steps is executed and the DNA molecules remaining at the end of the computation provide the solution to a three-variable, four-clause Boolean satisfiability problem. The improved capture kinetics, transfer efficiency, and single-base specificity enabled by microfluidics make our processor well-suited for performing larger-scale DNA computations.     

Quantum computing based on vibrational eigenstates: pulse area theorem analysis

In a recent paper [D. Babikov, J. Chem. Phys. 121, 7577 (2004)], quantum optimal control theory was applied to analyze the accuracy of quantum gates in a quantum computer based on molecular vibrational eigenstates. The effects of the anharmonicity parameter of the molecule, the target time of the pulse, and the penalty function on the accuracy of the qubit transformations were investigated. We demonstrate that the effects of all the molecular and laser-pulse parameters can be explained utilizing the analytical pulse area theorem, which originates from the standard two-level model. Moreover, by analyzing the difference between the optimal control theory results and those obtained using the pulse area theorem, it is shown that extremely high quantum gate fidelity can be achieved for a qubit system based on vibrational eigenstates.     

Solving for the time-dependent multi-configuration hartree fock equations based on sine-discrete variable representation

A parallel quantum electrons wave packet computer code has been developed to study laser-atom interaction in the nonperturbative regime with attosecond resolution. The motion equations of the multi-configuration time-dependent hartree fock (MCTDHF) based on a sine discrete variable representation were solved by using an adaptive stepsize Runge-Kutta integrator of eight orders. Some efficient algorithms and strategies to accelerate the calculation velocity are introduced and discussed in details. Some illustrated imaginary time propagation and real time propagation have been respectively done in the paper. Single ionization probabilities calculated by using this one dimension MCTDHF model underestimate the accurate results calculated by solving time-dependent Schrodinger equation directly.     

Improving the sensitivity for DNA sensing based on double-anchored DNA modified gold nanoparticles

DNA modified nanoparticles (AuNPs) are an established and widely used type of nucleotide sensor. We sought to improve the design by applying short rigid DNA duplexes near the surface of the AuNPs forming a so called double-anchored AuNP sensor, and compared it with other conventional DNA modified AuNPs. The improved design exhibited higher assembly efficiency, and consequently increased its sensitivity to target DNA.     

A group of 3D graphical representation of DNA sequences based on dual nucleotides

Based on chemical properties of the neighboring dual nucleotides, we reduce a DNA sequence into four 3D graphical representations. Associating with the eigenvalues of the introduced covariance matrix and the introduced measure of similarity, we introduce an approach to make similarity analysis of DNA sequence. © 2008 Wiley Periodicals, Inc. Int J Quantum Chem, 2008