基于三链和3-臂 DNA模型的图聚类算法

摘要

为了利用DNA计算求解图聚类问题，提出一种结合三链DNA和3-臂DNA模型的图聚类算法。基于k-medoids算法的思想，对图的顶点及边进行划分，将初始解空间的规模限定为O（ n2）。使用三链DNA模型筛选可行解的方法可推广到更多基于双链结构的算法设计中，3-臂DNA模型可通过对数据的预处理应用于更大规模的聚类问题。%In order to take the advantage of DNA computing to solve graph clustering , an algorithm combining triple-stranded DNA with 3-armed DNA model for graph clustering is proposed .Based on the idea of k-medoids algorithm , we divide the vertices and edges of the graph and limit the size of initial solution space to O( n2 ) .The method of screening feasible solution with triple-stranded DNA could be extended to more DNA algorithms using double-stranded structure .And 3-armed DNA model would be further applied to more large-scale clustering problems by pre-processing the data .