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

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

作　　者：白雪[1] 刘希玉[1] 

机构地区：[1]山东师范大学管理科学与工程学院,山东济南250014

出　　处：《计算机应用与软件》2013年第11期32-33,135,共3页Computer Applications and Software

基　　金：国家自然科学基金项目(61170038);山东省自然科学基金项目(ZR2011FM001)

摘　　要：为了利用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.

关 键 词：DNA计算 图聚类 k-medoids算法 三链DNA模型 3-臂 DNA模型 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]