论文部分内容阅读
近年来，作为一个全新的领域，DNA计算飞速发展，大量学者相继投身于该领域的研究。虽然，DNA分子具有海量存储能力和高度并行性的优势，然而，目前由于构建模型的不完善、实验操作中DNA分子量的指数增长等限制，DNA计算研究中仍存在一些难点问题。因此，无论是理论模型上的探索，还是实验技术上的改进，都会促进DNA计算的发展，同时也具有重要的科学研究意义。本文针对DNA计算在解决NP完全问题方面进行了实验研究及应用。尤其是针对当前DNA计算中的一些难点问题，提出了解决方案，并且构建了基于线性DNA、环形DNA及DNA自组装体等多种不同结构的实验模型并予以验证。全文的研究工作由以下几个部分组成：
（1）利用并行计算的思想，构建了基于线性DNA分子的大规模图顶点着色计算模型。本章针对目前DNA计算操作中存在的一些难点问题，提出了一种并行型计算模型。利用该模型，部分中间计算结果（非解）通过构建初始解空间被删除，从而有效缓解了实验中试管数的无限扩增。同时，该模型中引入并行计算，大大地提高了计算问题的规模。本章以一个61个顶点的图为实例，给出了具体的算法步骤，并通过生化操作对实例进行了求解，最终找到了符合该图着色要求的全部方案，从而证明了该模型的可行性。
（2）针对实验操作中出现的问题--线性DNA分子间重组导致试管数目的指数增长，构建了基于环形DNA分子的最大团问题的计算模型。本章中设计了一种人工合成的单链环形DNA分子。与线性分子不同，在实验操作中，环形分子可避免分子间重组，从而减少了实验中所需试管的数量，极大地降低了计算所需的空间，使计算所需空间随问题规模的扩大呈线性增长。文中通过具体的实验操作，借助磁珠和环化酶，合成单链环形DNA分子，并利用该分子结构解决了一个五个顶点的最大团问题的实例。实验结果表明，该环形DNA分子计算模型大大提高了分子计算的存储及计算能力，为解决其他NP完全问题提供了新型有效的工具。
（3）在第四章工作的基础上，为进一步改进检测手段，提高结果检测的准确性，提出了一种改进的求解最大团问题的环形DNA计算模型。在该模型中，设计了DNA分子增长法，该方法结合反向PCR技术，通过逐步增长代表顶点的DNA分子的长度，从而搜索出最大团问题的解。文中根据算法的实验步骤，通过对实例的求解，分析了该算法的时间和空间复杂度。结果表明，和以往改进的枚举算法相比，该方法具有较低的算法复杂度。
（4）结合当前热点技术--DNA自组装，设计了一种新型的基于DNA分子自组装技术求解最大团问题的计算模型。在本章中，利用DNA分子长、短链间的自组装形成环形结构，再通过环形结构形成的数目判断出最大团问题的解。文中对一个实例进行了求解，并给出了具体的编码及算法步骤，根据算法步骤分析了实验的操作复杂度。应用该模型，代表各个顶点的DNA分子可并行地、自动地进行自组装操作，极大地减少了操作所需的时间和空间。该模型的提出加快了DNA计算可自动化操作的实现，为解决NP完全问题提供了新思路。