摘要： 为解决使用DNA计算图聚类问题，提出一种基于DNA计算的层次图聚类算法。在分裂层次聚类中，使用DNA分子对图中顶点、边进行编码，在试管中并行产生最小生成树，根据给定阈值，通过切割树枝得到聚类结果。在凝聚聚类中使用DNA计算产生哈密尔顿路径，通过寻找最短哈密尔顿路径得到聚类结果。实验结果验证了该算法的可行性。

关键词: DNA计算, 图聚类, 分裂聚类算法, 凝聚聚类算法, 最小生成树, 最短哈密尔顿路径

Abstract: This paper uses DNA computing to solve graph clustering, provides a new approach to analyze graph problems. In split-level clustering, it uses DNA strands to assign vertices and edges, constructs the minimum spanning tree and cuts branches whose length is longer than the threshold, and gets the clustering results. In agglomerative hierarchical clustering, DNA computing to the undirected Shortest Hamilton Path(SHP) problem is introduced, and the clustering results are gotten. Experimental results prove the feasibility of the algorithm.

Key words: DNA computing, graph clustering, split-level clustering algorithm, agglomerative clustering algorithm, Minimum Spanning Tree (MST), Shortest Hamilton Path(SHP)

中图分类号: 

• TP18