Since triple-stranded DNA can be formed readily at any location in double-standed DNA with a homologous deoxyoligonucleotide in the presence of RecA-protein,it can be explored the possibility and feasibility to compute by this unique structure.In this paper the author shows that triple-stranded DNA structure mediated by RecA protein can be used for solving 0-1 integer programming problem.It can be solved the integer programming problem and satisfiability problem by this model.It can be transformed from integer programming problem and satisfiability problem to 0-1 integer programming problem.
Quantum and DNA computing are distributing and parallel types of computing. They are useful for solving problems which require high complexity computations and (or) massive data set computations such as searching, sorting, merging, pattern recognition, image processing, encryption, etc. Quantum and DNA algorithms cannot be efficiently simulated on classical computers because classical computers cannot efficiently deal with the parallelism. The quantum circuit model is adequate to describe quantum algorithms whereas DNA circuit model is adequate to describe DNA algorithms. This thesis establishes the relationship between a quantum qubit and a DNA string using the Bloch sphere. The Bloch sphere is a convenient graphical representation of a qubit in a 3-dimensional space. The model used in this thesis presents one-to-one mapping between qubits, DNA strings, and points on the Bloch sphere. The model is implemented at the real computer - von Neumann machine, therefore, there are restrictions related to the precision of qubits value, the length of DNA strings, and the precisions of coordinates values. The Bloch sphere and the relations between qubits, DNA strings and points are implemented as "Quantum and DNA Computation Simulation Programming System". Quantum and DNA Computation Simulation Programming System is implemented in the Java programming language. This system is a modified and upgraded interactive Quantum Computation applet developed at the Johns Hopkins Center for Educational Resources. The modifications include connecting (a) DNA strings and the Bloch sphere and (b) DNA strings and qubits. There are many researches in Quantum Computing and DNA Computing as independent study fields, but this is the first research which tries to connect Quantum and DNA Computing together using the Bloch sphere.
DNA computation could in principle solve the satisfiability (SAT) problem due to the operations in parallel on extremely large numbers of strands. We demonstrate some quantum gates corresponding to the DNA ones, based on which an implementation of DNA algorithm for SAT problem is available by quantum mechanical way. Since quantum computation owns the favorable feature of operations in parallel on 2
n states by using only n qubits, instead of 2
n strands in DNA computation, computational complexity is much reduced in treating the SAT problem quantum mechanically. We take a three-clause SAT problem with two variables as an example, and carry out a NMR experiment for solving a one-variable SAT problem.