The Research Of DNA Algorithm For A Class Of Domination In Graph

An overlap between life sciences and engineering is vivid characteristic of development of modern science and technology. With the fast development of computer and biotechnology, DNA computing, as a novel cross subject, develops very quickly in theory these years.Many problems in graph theory are combinatorial optimization problems and NP-complete problems. At present many problems in graph theory, such as the Hamilton Road, the maximum clique, minimum cover problem, graph vertices or edges coloring problem and so on, not only have been solved effectively by establishing DNA computing model, but also are took much attention and research by scholars. In this paper, the Research about a class of domination problems in Graph are made with DNA computing model. The specific works are as follow:â‘ This paper introduced the biological background of DNA computing, and the present development condition, the mathematical theory and the biological foundations,some essential operation of DNA molecule and the overview of study in recent years.â‘¡DNA surface model are established and used to solve minimum independent dominating set successfully. Then a simulation and DNA coding are given to verify the feasibility and effectiveness of DNA Algorithm.â‘¢It demonstrated the power of DNA-based computing by showing many domination problems can be efficiently solved under sticker model, such as minimum dominating set, total dominating set, independent dominating set, connected dominating set, perfect dominating set, restrained dominating set, k dominating set, double dominating set, and so on. By generating the solution space using stickers, it presents DNA-based algorithms to solve the problems using polynomial number of basic biological operations. And then a simulation of DNA sticker model and coding were given.Finally, the work of this paper is summarized and the prospective of future research is discussed on theory and application.