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

摘要：

在经典的电子计算中,有向图k顶点导出子图是一个高度复杂的问题.DNA计算是近年来发展的以DNA为载体求解计算问题的非经典计算技术.文中研究了使用DNA计算解决有向图k顶点导出子图的问题,从而提出了一种在粘贴机上运行的子图生成算法.首先,以粘贴机的标准生化元操作作为算法调用的基本算子;其次,使用顺序与循环等程序结构,把上述基本算子按照一定的逻辑方式组织起来;最后,读取生化反应结果,即可获得给定有向图的所有k顶点导出子图.仿真实验结果表明,与经典算法相比,新算法在理想条件下大幅缩短了子图生成时间.

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

所属期刊栏目：46

分类号：TP384(计算技术、计算机技术)

资助基金：国家自然科学基金项目U1204608,61572444

在线出版日期：2019-03-15（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：309-313