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

GRAPH CLUSTERING ALGORITHM BASED ON TRIPLE-STRANDED AND 3-ARMED DNA MODELS

为了利用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（ n^22 ）. 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-proeessing the data.