Research And Application Of DNA Computing On Dominating Set And Elevator Scheduling Problem

In1994, Doctor Adleman solved a Hamilton Path Problem with seven vertexes bybiochemical experiments, from then on, DNA computing was created as a new research field.DNA computing is a new calculation mode which uses some experimental operations based onbiological enzymes as computational tools and DNA molecules as computing objects, thecalculation course consists of a series of biological experiments. Compared with the traditionalelectronic computers, DNA computing has huge advantages in parallel computing, informationstorage and energy dissipation, especially its inherent huge parallel computing power enablesitself show great potential in solving many difficult nonlinear problems and NP problems.Numbers of scientific articles have proved that many NP problems can be solved in a polynomialnumber of steps, instead the silicon computer spends exponential time. Now, DNA computing hasdrawn great mass fervor in several scientific fields, such as chemistry, computer science,molecular biology, physics and mathematics, and it has established systematic knowledgearchitecture. But DNA computing is not yet mature, many theoretical problems have not beenconquered and no valuable biochemical technology has been developed. However, the researchon theory and application is of great significance.In the paper, the first chapter describes the background of DNA computing, after that, thesecond one stresses the basic theory of DNA computing,which includes the structure andproperties of the DNA molecules, the biochemical operations, the calculation principle and thecore part----DNA computing models. Based on the content above, the latter two chapters studieshow to solve two problems using DNA computing: the dominating set problem and the elevatorscheduling problem.The third chapter studies how to solve the dominating set problem by DNA computing. Thedominating set problem is one of NP-hard problems which is widely used in many science fields,such as the mathematics, graph theory and computer science, many application problems can bedescribed as the dominating ones. The dominating set problems have become divided into severaldifferent sub problems by several years. It selects three sub problems: the minimal dominating setproblem, the complete dominating set problem and the domatic partition problem as object. The sticker model in DNA computing is used as the basic computing model to develop DNAalgorithms to solve three problems. Later on, java programs are used to simulate the courses ofthe DNA algorithms to solve three small questions and the simulation results prove that all thealgorithms are effective.The forth chapter studies how to solve the elevator scheduling problem by DNA computing.The elevator scheduling problem is an application problem and it is a type of graph theoryproblems in nature which needs to get the shortest sum-route among several graphs. It takes theAdleman model as the basic computing model to develop a DNA algorithm to solve it, in whichthe encoding method is improved. The advanced DNA algorithm can overcome the shortcut oflow efficiency in the origin algorithm. The new DNA algorithm is used to solve an instance andthe result proves the effectiveness of the algorithm.