DNA Computing Model For Graph Vertex Coloring Problem And Application

DNA computing is one of the most important calculations in the calculation of intelligent computing. In1994, Adleman solved the Hamiltonian path problem by DNA computing successfully. Since than, DNA computing attracted people’s attention, has become an important field to foreign experts and scholars attention. The basic idea of DNA computing:the double helix structure of DNA and the Watson-Crick complementary condition are used to encode information, create data pool under the help of biological enzyme, and then according to some certain rules, original problem of data operation is highly parallel mapped into the controllable process with DNA molecules chains. The last step is to test the operation results by molecular biotechnology, such as PCR, clone, mutation, molecular purification, electrophoresis, magnetic bead separation. High degree of parallel, huge capacity and high speed are the advantages of DNA computing.First, the background of DNA computing is introduced, research situation and biology operation. The advantages and disadvantages of DNA computer, practical application and the existing problems has been discussed. Then through the research of several DNA computing model, trying to find DNA computing model to solve the problem of graph vertex coloring, and comparison of several models. Lastly, using graph vertex coloring of DNA computing model, to solve the problems of schedule arrangement and airport gate position problem.Time-table problem is a classical NP-complete problem. This paper deals with time-table problem by the technology of AcryditeTM gel separation. Each class period viewed as a graph vertex is mapped into DNA molecules chain. The gel column is constructed to arrange the order of DNA chain through biological reaction. The minimum number of cycles of arrangement is the minimun number of class hours.AcryditeTM gel separation is successfully used in DNA computing as a new technology for nucleic acid separation.In the core of airport operation, aircraft stands assignment (ASA) is a typical kind of combinatorial optimization. In this paper, by analyzing the ASA problem, gate assignment problem is transferred to vertex coloring model. A DNA computing model for airport gate assignment is proposed. The simulation results show that the algorithm compared with other optimization is very easy and feasible.