The Graph Clustering Algorithm Based On Dna Computing Research And Application

As the name suggests, Clustering means aggregating objects of the similar nature andattribute together. It is one of the most important research contents towards data mining,pattern recognition and so on, and is significant to identifying the internal structure of the data.The purpose of cluster analysis is to classify the seemingly disordered objects, so that peoplecan have a better understanding of them, analyze the intrinsic nature of them, and grasp theessence of their law. Graph clustering is one of the basic information processing methods inclustering, whose main object of study is the network diagram, ranging from Internet toWWW, from large power networks to the global transportation network, from the brain of theorganism to various metabolic networks, from research cooperation network to a variety ofeconomic, political, social networks, etc. DNA computing, also named as bimolecularcomputing, is a new computing model with the DNA molecules as information carriers,various biochemical reactions based on biological enzyme as information processing tools. Itis favored by many scholars for its high degree of parallelism, and has significant effect insolving the graph clustering problems.This article mainly focuses on the background knowledge and related algorithm of graphclustering, on the basic principles and related models of DNA computing, and on the basicidea and algorithm of combining DNA computing and graph clustering together. It firstlyintroduces the basic problems involved in the graph clustering, like definitions and thestandard of clustering. Then it introduces the main clustering algorithm, such as maximumflow algorithm, hierarchical clustering algorithm and the minimum spanning tree algorithm,etc. As to DNA computing, it presents the background, biological principles, characteristicsand calculation model of DNA computing. Finally it applies many DNA models to the graphclustering, and combines them to the graph clustering algorithm, so as to improve theaccuracy of the graph clustering algorithm, the feasibility of which has been proved bynumerical examples.In chapter three of this paper, it provides a new thinking of applying two-stage algorithmfor the minimum cut thus to diagram analysis. Before the application of two-stage algorithm,given graph shall be constructed basing on certain rules, so as to make it suitable to utilize theDNA two-stage algorithm. In the two-stage algorithm, the vertices and edges are coded withDNA molecule. Through biochemical reaction, it generates all the paths of structural mapfrom the selected source node to sink node, and then finds out the minimum cut between thegiven source node and sink node by computing, thereby completing the division of the graph.After that, iteratively executing the two-stage algorithm until the satisfied number of clusters are obtained. Finally the proof of the algorithm is given to illustrate the feasibility of thealgorithm.In chapter four of this paper, according to the defect that the result of breath first searchin betweenness algorithm of graph clustering is imprecise, research on closed circle DNAmodel and its applications is carried on the betweenness algorithm of graph clustering. Thearticle first make use of closed circle DNA model to accurately and quickly obtain thestructural map of the shortest path from any node to all nodes, and therefore get the shortestpath tree. In the meanwhile, the betweenness of each edge in the shortest path tree can also beobtained directly. Finally clustering is conducted by removing the edge of the largestbetweenness each time, and the feasibility of the algorithm is proved through an example ofit.In chapter five of this article, DNA sticker model is applied to the minimum spanningtree algorithm to obtain the minimum spanning tree of the graph. Then to calculate the cuttingthreshold of the graph, with which the graph is clustered to the last.