论文摘要
DNA计算是以DNA分子作为“数据”,以生化反应作为“信息处理工具”的一种新颖计算模式。由于其高度并行性、海量存储能力、低能耗等优点,DNA计算成为众多学者关注的焦点。近年来,许多研究成果已经提高了它的性能并增加了它的可行性。但是,DNA计算尚未成熟。关于DNA计算理论和技术上的进一步研究都具有重要的科学意义。图顶点着色问题存在于丰富的科学和工程应用中,如工序问题、排课表问题、物资储存问题等等,但它却是众所周知的NP-完全问题。本文针对这一具体问题,结合分子生物学的研究方法和实验技术,旨在建立自动化程度较高的,可用于求解较大规模问题的DNA计算模型,研究探讨了四种解决图顶点着色的DNA计算模型的可行性及优缺点,对每个DNA计算模型给出了具体的编码条件及相应的编码,及实现DNA计算模型的生化操作的实验步骤,并对一些模型给出了详细的实验验证。主要工作如下:文章首先基于杂交反应提出一种枚举型的DNA计算模型。在该模型中,提出了具体编码方案,并利用DNA自动合成仪合成初始解空间,然后利用杂交反应和聚合酶链式反应来求解问题。文章以具有5个顶点图为例对该模型进行了生化实验验证。实验结果表明,该模型能有效求解图顶点着色问题。为了减少DNA计算中编码的数量,不降低生化实验操作的可靠性,文章提出一种改进的枚举型DNA计算模型。在该模型中,利用双编码法对图顶点着色这一问题进行编码,利用酶切反应和聚合酶链式反应对问题进行求解。实例分析表明,该模型具有编码量少、求解过程简单的优点,尤其是因为该模型的解的检测方法类似于DNA测序技术,使得该模型更容易实现自动化操作。解空间指数爆炸问题是阻碍DNA计算发展的最大瓶颈。针对这一问题,文章提出一种非枚举型DNA计算模型。在模型中,首先对编码方案和初始解空间构建进行了优化,构建了非枚举型的初始解空间,删除了大量非解,提高计算效率;然后利用聚合酶链式反应实现非解删除的操作,并使用DNA测序技术读取最终解;文章以一个含有12个顶点的图为例对该模型进行了实验验证。实验结果表明,该模型有效可靠,可以较好的克服DNA计算中的解空间指数爆炸问题。为建立可用于求解大规模图顶点着色问题的DNA计算模型,文章在非枚举型DNA计算模型的基础上,引入并行处理的思想,建立了一种并行型DNA计算模型。在模型中,给出了一种子图划分的方法和原则,通过对给定图进行分解和合并处理,使得该DNA计算模型能够求解更大规模的图顶点着色问题。文章以一个含有61个顶点的图为例,对该模型进行了实验验证。实验结果表明,该模型不但延续了非枚举型DNA计算的优势,而且具有解决大规模的图顶点着色问题的能力。同传统的DNA计算模型相比,该模型可以大大提高计算效率,降低成本,能有效处理更大规模的图顶点着色问题,具有较强的应用价值。为了满足不同DNA计算模型的编码需求,文章也考虑了不同编码条件及参数,设计了大量DNA编码。实验结果表明,这些编码能满足DNA计算中的数量和质量要求。由此所构成的编码数据库,能方便DNA计算技术的设计与利用,为后续超大规模DNA计算模型奠定了基础,具有较高的理论意义和应用价值。
论文目录
相关论文文献
标签：计算论文; 图顶点着色问题论文; 编码设计论文; 杂交反应论文; 酶切反应论文; 聚合酶链式反应论文; 测序技术论文;