有向图k顶点导出子图的DNA粘贴算法  

DNA Sticker Algorithm for k-vertex Induced Sub-graphs of Directed Graphs

作　　者：朱维军[1] 张春艳 周清雷[1] 陈永华[1] ZHU Wei-jun;ZHANG Chun-yan;ZHOU Qing-lei;CHEN Yong-hua(School of Information Engineering,Zhengzhou University,Zhengzhou 450001,China)

机构地区：[1]郑州大学信息工程学院,郑州450001

出　　处：《计算机科学》2019年第1期309-313,共5页Computer Science

基　　金：国家自然科学基金项目(U1204608;61572444)资助

摘　　要：在经典的电子计算中,有向图k顶点导出子图是一个高度复杂的问题。DNA计算是近年来发展的以DNA为载体求解计算问题的非经典计算技术。文中研究了使用DNA计算解决有向图k顶点导出子图的问题,从而提出了一种在粘贴机上运行的子图生成算法。首先,以粘贴机的标准生化元操作作为算法调用的基本算子;其次,使用顺序与循环等程序结构,把上述基本算子按照一定的逻辑方式组织起来;最后,读取生化反应结果,即可获得给定有向图的所有k顶点导出子图。仿真实验结果表明,与经典算法相比,新算法在理想条件下大幅缩短了子图生成时间。How to obtain all the k-vertex induced sub-graphs in a directed graph is a complex computational problem.The DNA computing is a nonclassical computing technique developed in recent years,which can be employed to solve some complex computational problems via DNAs and their biochemical reactions.Aiming at obtaining all the k-vertex induced sub-graphs in a directed graph using the DNA computing,a DNA sticker algorithm for constructing sub-graphs was proposed.First,the existing sticker system provides the basic operators for the new algorithm.Each of these basic operators has its basic computational function,and each of these basic operators can be implemented by a specific stan-dard biochemical reaction.Second,these basic operations can be organized in a certain logical way.As a result,some program structures,such as sequence and loop,are formed.At last,all the k-vertex induced sub-graphs can be obtained for a given directed graph,by reading the results of the biochemical reactions.These simulated results demonstrate that the new algorithm significantly reduces the time which is required by generating sub-graphs under ideal conditions,compared with the classical algorithms.

关 键 词：粘贴机 脱氧核糖核酸 有向图 顶点导出子图 

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