Dissertation > Mathematical sciences and chemical > Mathematics > Operations Research > Planning Theory ( mathematical programming) > Integer Programming

DNA Computation for a Category of Special Integer Planning Problem

Author JiaShuFen
Tutor WuChaoBiao
School Jinan University
Course Probability Theory and Mathematical Statistics
Keywords DNA computation Integer planning problem 0-1 planning problem Fluorescence labeling Optimal solution
CLC O221.4
Type Master's thesis
Year 2007
Downloads 187
Quotes 0
Download Dissertation

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.

Related Dissertations
More Dissertations