Research On DNA Chip Model Of Special 0-1 Integer Programming Problem

Since Dr.Adleman using molecular biology technology solved the Directed Hamilton problem[1]based on DNA sequence,DNA computing has become a new research field and attracted much attention due to its high degree of parallelism and high storage?low energy consumption and other advantages.Soon afterwards,many scholars combined DNA calculation and other intelligent computing methods,such as genetic algorithms,fuzzy systems,neural networks,which provide new ideas for DNA computing.In order to solve graph and combinatorial optimization problems with using DNA computing,scholars put forward different DNA computing models,which could solve 3-SAT problem[2]?the maximum clique problem[3?6]?the minimal vertex cover Problem[7]?Graph vertex coloring problem[8]and so on[9?10].As a special form of integer programming,0-1 programming problem is an important problem in operational research and has an extensive application,such as Assignment problem and Site selection problem.There are many algorithms to solve the problem,such as exhaustive method?implicit enumeration method?branch and bound method,but nowadays there is no good algorithm to completely solve the problem.In recent years,many scholars have put forward the corresponding DNA computing model for some special integer programming problems.Some combinatori-al optimization problems(especially Non-deterministic Polynomial complete problems)and some satisfiability problems can generally be transformed into 0-1 integer progra-mining problems.Having advantage of simple?feasible?high parallelism,DNA chip can effectively avoid the error of experimental operation and human factors on the calculation results by calculation,make the process automated,greatly improve the computational efficiency and the accuracy of feasible solution.Therefore,DNA chip has a unique advantage in the filed of DNA calculation.DNA chip will become a new type of biological computing chip and make up for the previous DNA models in a certain degree.Firstly,this paper introduces the related biological operation of DNA computing,simply describes the structure of DNA and the basic idea of DNA computing.Secondly,this paper introduces the DNA programming models of the 0-1 programming problem and the special integer programming problem.Then,on the base of molecular biology technology and DNA chip,a new computational model for a special 0-1 integer programming problem is proposed.Finally,the paper summarizes the advantages and problems that still need to be solved.