Solutions To Knapsack Problems Based On DNA Computing

With the rapid development of biological techniques, a new discipline-DNA computing-has come into being. In 1994, Adleman presented his seminal paper"Molecular Computation of Solutions to Combinatorial Problems"in Science. The massive parallelism, high-density storage and energy efficiency of DNA computing may offset the disadvantages of electronic computers.In this paper, the principle and biological foundation of DNA computing is introduced, and the application of DNA computing in combination and optimization is analyzed. Then, we present the DNA computing models of multi-dimensional knapsack problems and collapsing knapsack problems. For the multi-dimensional knapsack problem, we propose two kinds of computing models, the first kind is a two-phase model, and the second kind is a surface-based model. In the two-phase model, the algorithm is performed in two phases-the tube phase and the surface phase. In the surface-based model, the solutions are gained by utilizing the techniques of fluorescence labeling after disassembling the constraint equation group. For the collapsing knapsack problem, we propose a kind of computing model. In this model, we firstly partition the constraint of the collapsing knapsack problem into several different constraints, and then we perform a series of biochemical technologies (ligature, gel electrophoresis, DNA probe and autoradiography) to obtain the solutions.We illustrate the concrete implementing processes of each model by some case analyses. Furthermore, we analyze of biochemical technologies adopted in each model, and point out the superiority and limitation of these technologies in the performing of each algorithm.