The Study Of Several Types Of DNA Computing Model For Some NP-complete Problems And Computing DNA Mathematical Model

DNA computing is a novel computation method based on DNA modecules and biochemistry trials. Because of its massive parallelism and high-density s-torage, DNA computing attracts the concern of many scientists with different fields. Up to now, many accomplishments have been achieved to improve the feasibility of DNA computing. The results of these researches indicate that DNA computing is superior to electronic computer in solving some NP-complete problem.According to the characteristics of DNA molecules and the rule of biochem-ical reaction processes to establish the DNA sticker models and sticker systems. We proposed DNA algorithms of the maximal matching problema and DNA algorithms of the shortest path problem of undirected graph by taking use of the sticker model and sticker system, meanwhile, we designed an algorithm of DNA computing to solve the traveling salesman problem(TSP) and researched the mathematical properties of DNA sticker model. Furthermore, we stated the feasibility of these DNA algorithms and proved the complexity of algorithms is O(n).We given the definition of computing DNA mathematical model based on the Watson-Crick complementary structure and multiplicity of DNA molecules, that is DNA finite state automaton, and we researched the closed of the operation of DNA regular language. At last, we proved the equivalence of DNA regular grammar and DNA finite state automata.