求解排课表问题的酶切DNA计算模型研究

摘要

DNA计算作为一种新兴的智能计算手段，在近些年成为国内外学者广泛关注和研究的对象。1994年Adleman创新地采用DNA计算的方法解决七个城市之间的哈密顿路径问题，这标志着DNA计算正式成为解决NP-完全问题的一种有效手段。利用DNA计算解决问题的基本思路是：基于DNA分子独特的分子结构和自我复制能力，把现实问题进行DNA编码并生成特定的DNA分子。在生物酶的催化作用下，生成需要的初始解空间。在进行一系列生物反应后删除非解，最后利用PCR技术、凝胶电泳技术等生物方法对结果进行检测并映射成实际问题的最终解。 DNA计算由于其并行性高、储存量大等特点，有望在解决NP-完全问题的研究方面有所突破。排课表问题作为一种典型的NP-完全问题，是一个有约束的，多目标优化问题，具有很强的实际实用价值。本文旨在研究面向求解排课表问题的DNA计算模型。在对DNA计算和相关计算模型的研究基础上，本文提出了两种改进的求解排课表问题的酶切DNA计算模型： 1.基于AcryditeTM凝胶分离的DNA计算模型。在构建凝胶柱的基础上，通过酶切反应和电泳技术将DNA凝胶柱重新排列，此过程中的最小循环数就是排课表问题中的最少课时数。此模型中限制性内切酶的使用改进了以往计算模型反应时间长、反应条件复杂、容易产生发卡结构等缺点，提高了模型的使用效率。 2.上述基于AcryditeTM凝胶分离的计算模型由于其生物技术的限制，难以应用于大规模的排课表问题中。为此，本文通过将荧光技术与酶切技术相结合，提出了可用于求解较大规模排课表问题的表面DNA计算模型。由于模型中的DNA分子以点阵列的形式储存，在并行性和存储量方面都有优势，因而适用于较大规模的排课问题。该计算模型相比之前的计算模型具有反应灵敏度更高、实验操作更简单、反应时间缩短的优点。 本文关于DNA计算模型的研究不仅为诸如排课表问题的NP-完全问题提供了更多的求解途径和研究思路，也为DNA计算、生物计算的研究带来了更多可能性，具有一定的理论研究意义和实际应用价值。

目录

第一个书签之前