Research On Some Directed Graph Algorithms Based On DNA Sticker Model

Adleman,a Turing prize winner,proposed the concept of DNA computing for the first time.DNA computing is an interdiscipline with the advantages of strong parallel processing,high storage,low energy consumption and so on,and it has led to wide attention and research by scholars from all walks of life.Until now,DNA computing has made great achievements from theory to experiment and then to application.The sticker model has many advantages,such as the DNA strands can be reused,neither the need for biological enzymes nor the extension of the DNA strands.What'more,the sticker model has great potential and advantages in solving graph theory problems,especially for complex NP.From the previous literatures,the problems solved by DNA computing models are related to undirected graphs,but for directed graphs,there is still no effective DNA computing method.Therefore,this paper has proposed two new algorithms(k vertex derived sub-graphs,k-vertex incidence relation),and given an improved algorithm for weightening.All these sub-algorithms running on the sticker machines provide the algorithm libraries for the DNA computer.The specific work contents are as follows:First,the problem of k-vertex induced sub-graphs in a directed graph has not been solved under the circumstance of DNA computing.To this end,we propose,a new DNA sticker algorithm,k-vertex induced sub-graphs of directed graphs based on DNA sticker model.First,the basic operators of the algorithm are consisted of the pre-defined operations of the sticker model.Second,one can obtain the new algorithm by organizing these basic operations in a loop program constructure.At last,we can obtain the k-vertex induced sub-graphs of a directed graph by reading the biochemical reaction results.These simulated results demonstrate that the new algorithm significantly reduces the time which is required by generating sub-graphs under ideal conditions,compared with the classical algorithms.Second,the problem of k-vertex incidence relation in a directed graph has not been solved under the circumstance of DNA computing.we propose,a new DNA sticker algorithm,k-vertex incidence relation of directed graphs based on DNA sticker model.First,the basic operators of the algorithm are consisted of the pre-defined operations of the sticker system.Second,4 Subalgorithms are given according to the different definitions of incidence relation.We can use these 4 subalgorithms to determine whether there is a incidence relation between a single vertex and one edge.Third,one can obtain the k-vertex incidence relation algorithm by organizing these subalgorithms and basic operations in a certain logical way.At last,running the new algorithm,we can obtain the k-vertex incidence edge sets of a directed graph by reading the biochemical reaction results.Third,for the previous weightening algorithm with single function and the scope of solving the problem is small.Therefor,we have given three improved weightening algorithms which have the advantages of multifunctional and run on the sticker machines.First,the basic operators of the algorithm are consisted of the pre-defined operations of the sticker model.Second,the new weightening algorithms which for implementing the different functions,can obtain by organizing these basic operations in a certain logical way.At last,running the new algorithm,we can obtain the functions of weightening by reading the biochemical reaction results.