基于DNA计算的层次图聚类算法

摘要

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