基于DNA计算的最大流算法在图聚类上的应用研究  

The Study about Application on Graph Clustering Algorithm of Maximum Flow Based on DNA Computing

作　　者：张怀远[1] 向来生[1] 

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

出　　处：《微电子学与计算机》2013年第4期98-102,共5页Microelectronics & Computer

基　　金：国家自然科学基金(61170038);山东省自然科学基金(ZR2011FM001);软科学重大项目(2010RKMA2005);教育部人文社会科学研究项目(2YJA630152)

摘　　要：提出使用DNA计算解决图聚类问题,提供了使用DNA两阶段法求最小切进行图分析的新思路.在使用两阶段算法前,首先根据一定的规则对给定图进行构造,使其适合使用DNA两阶段算法.在两阶段算法中,使用DNA分子对图中顶点、边进行编码.经过生化反应生成关于构造图从选定源节点到槽节点的所有路径,再利用电子计算求出关于给定源节点和槽节点的最小切,从而完成对图的划分,然后迭代执行两阶段算法直到获得满意的聚类数目为止.给出了算法的证明,说明了算法的可行性.This article provides a new solution to problems about graph clustering by DNA computing, and also provides some new ideas on seeking for minimum cuts in the DNA two-stage method and afterwards future analyses a graph. Before carrying out the DNA two-stage method, some formation should be made on the given diagram to make it suitable for the premise of DNA two--stage method. Then when implementing the two-stage method, we shall encode the vertex and edge in the given graph first. After some biochemical reactions, it can generate all the routes from the source node to the sink node about the formatted graph. Then we could figure out the minimum cut of the given source node and the sink node through some computing, thus complete the division of the graph. Finally we can implement the two-stage methods iteratively until the satisfying cluster number is found. Besides, this article offers the testimony of the algorithm as well, which further illustrates its feasibility.

关 键 词：DNA计算 图聚类 最大流 最小切 

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