Dissertation > Excellent graduate degree dissertation topics show

Research and application of graph clustering algorithm based on DNA computing

Author: ZhangHuaiYuan
Tutor: XiangLaiSheng
School: Shandong Normal University
Course: Management Science and Engineering
Keywords: graph clustering DNA computing Adleman model closed circle DNA model DNA sticker model
CLC: TP311.13
Type: Master's thesis
Year: 2013
Downloads: 39
Quote: 0
Read: Download Dissertation

Abstract


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.

Related Dissertations

  1. Multi-attribute undirected weighted graph clustering method,O157.5
  2. Hybrid DNA Genetic Algorithm and Its Application in the MTSP Problem,TP18
  3. Research on Combinatorial Optimization Problem Based on DNA Self-Assemble,TP399-C8
  4. Maximum Matching Problem of DNA Algorithms Rearch,TP301.6
  5. Web-based data mining for personalized Search Engine,TP391.3
  6. Research on Attributed Graph and Clustering Tree Based Large Datasets Image Retrieval,TP391.41
  7. Design and Research of the data structure in DNA computer,TP311.12
  8. The Research on Several Problems of DNA Computing,TP301
  9. Study on Some Theories of DNA Computing,TP301.6
  10. The Design and Implementation of DNA Computing Model Based on 0-1 Programming,TP3
  11. The GA in the DNA Computing of the Research and Application,TP18
  12. The Application of DNA Computation in Information Security,TP309
  13. 0-1 Programming Problem Based on Sticker Model,O221.4
  14. The Coding Sequence of DNA Computing and Algorithm Theory,O157.4
  15. The Research and Application of DNA Computing by Self-assembly,O242.1
  16. DNA Computing in Graph Theory,O157.5
  17. Application of DNA Computing in the Combinatorial Optimization Problem,O224
  18. The Design of Boolean Logic Gates Based on DNA Computing,TN79
  19. Research on Graph-Clustering Algorithms Based on Node Structure Connectivity,O157.5
  20. Research on Video Summarization by Clustering and Mining,TP391.41
  21. Graph Clustering Algorithm Based on the Degree and the Number of Vertices,TP301.6

CLC: > Industrial Technology > Automation technology,computer technology > Computing technology,computer technology > Computer software > Program design,software engineering > Programming > Database theory and systems
© 2012 www.DissertationTopic.Net  Mobile