Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Computer Engineering and Applications Journal

0-1 integer programming problem based on RecA-mediated triple-stranded DNA structure

Zhixiang Yin

Published Jan 1, 2008• 8 citations
OpenAlex

Abstract

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.

Related papers

Quantum mechanical NMR implementation of DNA algorithm for satisfiability problem

Ren, T. T., Mang Feng, Weng-Long Chang +2 more

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.

arXiv:0802.0232•Feb 2, 2008•0 citations

Quantum demonstration of a bio-molecular solution of the satisfiability problem on spin-based ensemble

Ren Ting-Ting, Feng Mang, Weng-Long Chang +1 more

DNA computation (DNAC) has been proposed to solve the satisfiability (SAT) problem due to operations in parallel on extremely large numbers of strands. This paper attempts to treat the DNA-based bio-molecular solution for the SAT problem from the quantum mechanical perspective with a purpose to explore the relationship between DNAC and quantum computation (QC). To achieve this goal, it first builds up the correspondence of operations between QC and DNAC. Then it gives an example for the case of two variables and three clauses for details of this theory. It also demonstrates a three-qubit experiment for solving the simplest SAT problem with a single variable on a liquid-state nuclear magnetic resonance ensemble to verify this theory. Some discussions are made for the potential application and for further exploration of the present work.

Chinese Physics B•Dec 1, 2009•0 citations

DNA Computation for a Special Integer Planning Problem

Lin-Bo Jiang

By using the method of 22 kinds of fluorescence labeling in experiment environment of the based-surface approach,a DNA computation based algorithm for solving the problem of special integer planning was proposed.We have introduced a method,in which the above problem transforms into a special-1,0 and 1 integer planning problem.The solution of the special integer planning problem has paved the way for the complete solution of integer planning problems.

Journal of Hunan University•Jan 1, 2008•0 citations

Improved molecular solutions for the N-QUEEN problem on DNA-based supercomputing

Fan Wu, Kenli Li

In this paper our main point is to give molecular solution to solve N-QUEEN problem. In order to achieve this, we take the divide and conquer strategy into the DNA-based supercomputing and propose DNA-based algorithm of an n-bit Parallel Searcher to formally verify our designed molecular solutions for the N-queen problem. The theoretical and experimental analysis shows that comparing with the exhaustive DNA-based algorithm for knapsack problem the algorithm not only shortened the length of the strands, but also reduced the DNA library strands from O(2q) to O(2q/2).

International Conference on Bio-Inspired Computing: Theories and Applications (BIC-TA)•Sep 1, 2010•2 citations

A DNA Computer Model to Solve Integer Programming Problem

Fang Gang, Zhu Yan

Journal of Computational and Theoretical Nanoscience•Nov 26, 2010•1 citation

Efimov-DNA phase diagram: Three stranded DNA on a cubic lattice

Somendra M. Bhattacharjee, Damien Paul Foster

We define a generalized model for three-stranded DNA consisting of two chains of one type and a third chain of a different type. The DNA strands are modeled by random walks on the three-dimensional cubic lattice with different interactions between two chains of the same type and two chains of different types. This model may be thought of as a classical analog of the quantum three-body problem. In the quantum situation, it is known that three identical quantum particles will form a triplet with an infinite tower of bound states at the point where any pair of particles would have zero binding energy. The phase diagram is mapped out, and the different phase transitions are examined using finite-size scaling. We look particularly at the scaling of the DNA model at the equivalent Efimov point for chains up to 10 000 steps in length. We find clear evidence of several bound states in the finite-size scaling. We compare these states with the expected Efimov behavior.

arXiv:2106.01690•The Journal of Chemical Physics•Aug 12, 2021•0 citations
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.
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 2n^{n}n states by using only n qubits, instead of 2n^{n}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.
DNA computation (DNAC) has been proposed to solve the satisfiability (SAT) problem due to operations in parallel on extremely large numbers of strands. This paper attempts to treat the DNA-based bio-molecular solution for the SAT problem from the quantum mechanical perspective with a purpose to explore the relationship between DNAC and quantum computation (QC). To achieve this goal, it first builds up the correspondence of operations between QC and DNAC. Then it gives an example for the case of two variables and three clauses for details of this theory. It also demonstrates a three-qubit experiment for solving the simplest SAT problem with a single variable on a liquid-state nuclear magnetic resonance ensemble to verify this theory. Some discussions are made for the potential application and for further exploration of the present work.
In this paper our main point is to give molecular solution to solve N-QUEEN problem. In order to achieve this, we take the divide and conquer strategy into the DNA-based supercomputing and propose DNA-based algorithm of an n-bit Parallel Searcher to formally verify our designed molecular solutions for the N-queen problem. The theoretical and experimental analysis shows that comparing with the exhaustive DNA-based algorithm for knapsack problem the algorithm not only shortened the length of the strands, but also reduced the DNA library strands from O(2q) to O(2q/2).
We define a generalized model for three-stranded DNA consisting of two chains of one type and a third chain of a different type. The DNA strands are modeled by random walks on the three-dimensional cubic lattice with different interactions between two chains of the same type and two chains of different types. This model may be thought of as a classical analog of the quantum three-body problem. In the quantum situation, it is known that three identical quantum particles will form a triplet with an infinite tower of bound states at the point where any pair of particles would have zero binding energy. The phase diagram is mapped out, and the different phase transitions are examined using finite-size scaling. We look particularly at the scaling of the DNA model at the equivalent Efimov point for chains up to 10 000 steps in length. We find clear evidence of several bound states in the finite-size scaling. We compare these states with the expected Efimov behavior.