DNA Computation for a Category of Special Integer Planning Problem
|Course||Probability Theory and Mathematical Statistics|
|Keywords||DNA computation Integer planning problem 0-1 planning problem Fluorescence labeling Optimal solution|
DNA computing is a new method of simulating molecular biology structure ofDNA by means of molecular biology technological. This method suggests a new wayof solving an NP-complete problem. Up to now, many accomplishments have beenachieved to improve its performance and increase its reliability. The 0-1 programmingproblem is an important problem in op search and has very widespread application.But up to now, there does not exist any good algorithm yet. A new DNA computingmodel is provided to solve a 0-1 planning problem based on DNA.Biochemical reaction theory based DNA computation is of much better perform-ance in solving a class of intractable computational problems such as NP-completeproblem, it is important to study the DNA computation. A novel algorithm based onDNA computation is proposed, which solves the problem of a category of specialinteger planning problem and a theoretical scheme of solving 0-1 planning problemby using the method of fluorescence labeling in the surface based approach to DNAcomputation. Use to apply DNA computing to planning problem and we give acomputer program which simulate this algorithm. By utilizing the techniques offluorescence distinguishing, the new algorithm can eliminate all of those falsesolutions through observing the fluorescence on the surface of DNA molecules.Algorithm analyses show that the new proposed algorithm based on DNAcomputation has such good characteristics as simple encoding, low cost, shortoperating time and low fault rate etc.