基于DNA粘贴模型的若干有向图算法研究

发布时间：2020-07-05 16:51

【摘要】：图灵奖得主Adleman首次提出DNA计算的概念。作为交叉学科的DNA计算具有强并行处理,高存储、快运算、低耗能等优点,因此引起各界学者的广泛关注和研究。发展至今,DNA计算由理论到实验,再到应用,每一个阶段都取得了很大的成果。DNA计算的粘贴模型具有多个优点,诸如反应材料可重复使用,生物反应过程中既无需生物酶作用也无需DNA链的延伸等,更重要的是,粘贴模型在解决图论问题方面有巨大潜力和优势,特别是针对复杂的NP完全问题。从已有文献来看,利用DNA计算模型解决的问题都是无向图相关的,而针对有向图,目前尚缺乏有效的DNA计算方法。为此,本文选用粘贴模型,提出两种新算法(k顶点导出子图和k顶点关联关系)且给出了赋权问题的改进算法,这些在粘贴机上实现的子算法皆为DNA计算机提供了算法库,具体工作内容如下:第一,针对有向图k顶点导出子图问题,本文提出了新算法——基于DNA粘贴模型的有向图k顶点导出子图算法。首先,粘贴模型提供的几种基本操作,可作为新算法调用的基本函数;其次,采用循环型程序结构,把上述基本函数按照一定的逻辑方式组织起来形成k顶点导出子图的粘贴算法;最后,读取生化反应结果,即可获得有向图的k顶点导出子图。通过仿真实验结果,证明了该DNA算法比经典算法更加节省子图生成时间。第二,针对有向图k顶点关联关系问题,本文提出了新算法——基于DNA粘贴模型的有向图k顶点关联关系算法。首先,把粘贴模型的基本标准生化操作作为可调用的基本函数;其次,依据关联关系的不同定义给出了4种相关联的子算法,以判定单个顶点单条边是否存在关联关系;然后,将上述子算法和基本函数按照一定的逻辑方式组织起来,即构成有向图k顶点关联关系的粘贴算法;最后,运行新算法,读取生化反应结果,便可获得有向图k顶点的关联边集。第三,针对之前的赋权算法功能单一,解决问题范围较小的缺陷,本文给出了改进算法——基于DNA粘贴模型的赋权问题的改进算法。首先,把粘贴模型的标准生化元操作作为可调用的基本函数;其次,把上述基本函数依照特定的逻辑模式组织起来,以实现算法的不同功能;最后,运行新算法,依需求读取相应的生化反应结果,即可获得赋权算法对应功能的结果。
【学位授予单位】：郑州大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：TP384
【图文】：

基于DNA粘贴模型的若干有向图算法研究

DNA分子的平面结构和立体结构示意图

基于DNA粘贴模型的若干有向图算法研究

有向图G1

【相似文献】