DNA Computing Models For Weighted Graphs

DNA computing is a new computing technique based on the biochemical reaction. Since Adleman's initiative work in 1994, lots of researchers have been attracted to this field. The structure of DNA molecules, principle of DNA computing and its implementation method are introduced in chapter two in this paper; In chapter three the encoding weight problems in the DNA computing models are analysed and summarized, and the emphasis is on the summary and analysis of the DNA computing model based on a new scheme of encoding weight for Chinese postman problem in Han Aili's paper; In chapter four a new DNA computing model of undirected graph for Chinese postman problem is put forward, and generalized and applied to the DNA model of mixed graph for Chinese postman problem and the DNA procedure for solving the shortest path problem. In chapter five the problem of solving the Ramsey number is transformated to DNA computing models to solve maximum clique and maximum independent set problems.