题目：基于DNA链置换和自组装技术的图连通度计算模型的研究

DNA计算是一种以DNA分子作为存储数据和运算媒介的新型计算模型。它突破传统计算机概念，引入生物分子作为计算材料，并且DNA分子具有高度并行性、易操作、高存储等优点，是一门具有巨大发展潜力的新型学科。随着科学技术的发展，各个专家对其构建DNA分子模型、设计实现算法和生化试验研究，可以解决图论中的NP完全问题。

本文主要研究连通度问题，该问题是图论中经典的NP问题。本文主要通过构建两种DNA自组装模型并利用链置换技术解决图的连通度，还对DNA计算的基本原理及其优缺点进行了简单的阐述。本文主要选取两种计算模型对图论中的连通度进行研究，主要包括：

第一，本文利用双链DNA分子构建模型。然后根据简单算法利用DNA 分子进行搜索, 避免了计算中试管数的指数爆炸增长。为了验证这个算法，我们以一个简单的图G 为例, 说明应用该算法求解连通度的整个操作过程并给出了该双链DNA分子计算模型的详细生化过程和算法语言描述。同时根据具体图形设计模型和简单算法对图G详细执行过程进行了说明，从而求出图G的连通度。由于双链DNA分子的高度并行性降低了图的连通问题的复杂度（O(n-1)n/2+m））并且提高了实验的效率。

第二，本文构建DNA/AuNP共聚体的三维DNA自组装计算模型解决图的连通度。根据本文给的具体图形设计共聚体模型，然后根据非确定算法经过一系列生物实验最后求出该图的连通度。另外本文还通过了Visual DSD和NUPACK对该生物实验进行了仿真，来说明该实验的可行性。与传统算法相比，该算法所需要的实验操作方便、容易操作，更重要是降低了求解该图的复杂度，为DNA/AuNP共聚体模型的应用提供了可行性说明。

为了证明双链DNA分子和DNA/AuNP共聚体模型解决图的连通度问题的可行性，阅读大量文献对比与综合还给了该模型的实验方案以及生物技术的详细操作过程。另外，本研究利用链置换技术通过巯基化将DNA分子与金颗粒相连接，这个实验同时也说明了对纳米金颗粒的控制达到一定水平，同时这对目前DNA计算的研究具有巨大的研究价值，从理论上可以提高分子计算的可靠性和准确性，同时由于实验的操作方法灵活，准确率高，这对解决图论中NP完全问题提供新思路。不过，本文的模型需要根据具体的图设计模型结构，虽然有Visual DSD的仿真来验证实验的可行性，但是并未用具体生化实验来验证模型的可行性。