摘要
为解决使用DNA计算图聚类问题,提出一种基于DNA计算的层次图聚类算法。在分裂层次聚类中,使用DNA分子对图中顶点、边进行编码,在试管中并行产生最小生成树,根据给定阈值,通过切割树枝得到聚类结果。在凝聚聚类中使用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.
出处
《计算机工程》
CAS
CSCD
2012年第12期188-190,共3页
Computer Engineering
基金
国家自然科学基金资助项目"基于计算智能算法的聚类技术研究(60873058)
国家自然科学基金资助项目"基于DNA计算与离散Morse理论的聚类研究分析"(61170038)
山东省自然科学基金资助项目(ZR2011FM001)
山东省软科学重大基金资助项目(2010RKMA2005)
关键词
DNA计算
图聚类
分裂聚类算法
凝聚聚类算法
最小生成树
最短哈密尔顿路径
DNA computing
graph clustering
split-level clustering algorithm
agglomerative clustering algorithm
Minimum Spanning Tree （MST）
Shortest Hamilton Path（SHP）
