【作者】 强小利；

【导师】 许进；

【作者基本信息】 华中科技大学 ， 系统分析与集成， 2008， 博士

【摘要】 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计算模型奠定了基础,具有较高的理论意义和应用价值。更多还原

【Abstract】 DNA computing is a novel computation paradigm with DNA molecules as“data”, and biochemistry trials as“information processing instruments”. Because of its massive parallelism, high-density storage and energy efficiency, DNA computing attracts the concern of many scientists with different backgrounds. Up to now, many accomplishments have been achieved to improve its performance and increase its reliability. However, many issues still exist in DNA computing. It is important and interesting for further study on DNA computing.The graph vertex coloring problem is the main topic of graph theory and applied in many fields, which is known as NP-complete problem. In this dissertation, with the biological research method and experimental technique, four effective, reliable DNA computing models to solve this problem are proposed. The advantage and disadvantage of these DNA computing models are discussed. The main research works are as follows:An enumerating DNA computing model based on hybridization reactions is proposed. The graph vertex coloring is encoded by DNA molecules and solve by hybridization reactions and polymerase chain reaction. To testify this DNA computing model, a graph with five vertices is designed and the relevant biochemistry trials are completed. The results show that this model can solve vertex coloring problem efficiently.To reduce the number of encoding, an improved enumerating DNA computing model is presented, which is based on enzyme digestion reactions. The graph vertex coloring problem is encoded by double encoding method, and the false solutions deletion and the true solutions detection are updated and automized partly after enzyme digestion reactions and polymerase chain reaction.The solution space exponential explosion problem is the biggest obstacle in DNA computing. To overcome this problem, a non-enumerating DNA computing model is designed and testified based on the optimization of encoding method and construction of initial solution space. Polymerase chain reaction and Sequencing technology are used for delete false solutions and true solution detection in these models. This DNA computing model is used for solving vertex 3-coloring problem of a graph with 12 vertices. The results of the biochemistry trials show that many false solutions can be deleted when constructing the initial solution space, which overcome the solution space exponential explosion problem and improve the computational efficiency.To solve large-scale graph vertex problem, a parallel type of DNA computing model is proposed based on the development of the non-enumerating DNA computing model. The method and principles of subgraph division are studied to implement the parallel procedure. To testify its computing capacity, a graph with 61 vertices is testified. The results indicate that this model extends the advantage of the first non-enumerative DNA computing model, improves the computational efficiency, and reduces costs significantly, which can be used for NP problems in a larger scale.To get enough encodings for different DNA models, many constraints and parameters are considered and given. The rich encodings can form a database for design and application of DNA computing technology. The experiment results prove that these encodings are qualified and can avoid the error in experiments. The database can benefit further researches in the field of DNA computing.更多还原