● 摘要
摘 要
由于电子计算机的发展受到来自器件工艺技术与制造成本等方面的限制，促使科学家研究新型信息处理模式。生物计算越来越受到人们的关注，尤其是DNA计算。DNA计算是一种以DNA分子与某些相关的生物酶等作为最基本材料，基于生化反应的新型的分子计算方法。十多年的研究表明：DNA计算在求解图与组合优化中的一些困难的NP-完全问题上具有内在并行性、海量信息存储能力等独特优势。正是由于DNA计算的优势，使得在未来的科学领域内，有望在优化计算、密码学、数学等众多领域得到突破性的创新与应用。目前国际上关于DNA计算机的研究形成一个新的科学前沿热点，正在极大地吸引不同学科、不同领域的众多的科学家，特别是生物工程、计算机科学、数学、物理、化学、控制科学以及信息等领域内的科学家。
本研究工作的目的是研究如何用DNA分子的特殊性质以及各种可能的生物技术以及当前飞速发展的纳米技术，建立用于解决图与组合优化问题等NP完全问题的计算模型，尤其是利用了当前DNA分子自组装的性质建立自组装计算的模型。这些模型的建立不仅为解决图与组合优化问题等NP完全问题提供了与以往电子计算机不同的算法，而且可以极大的降低算法的复杂度，解决当前电子计算机无法解决的指数爆炸问题，具有极大的理论价值和应用价值。
本研究工作在已有研究成果的基础上，利用纳米技术，提出了两种解决图与组合优化问题的DNA自组装计算模型。
（1） 首先，本论文介绍一种利用DNA三维自组装计算模型解决图的最大团问题的理论方法。首先，引入一种简单的求解最大团问题的非确定性算法；其次，根据算法设计不同类型的DNA自组装基元；最后说明自组装过程及解的检测方法。该计算模型的计算时间为线性，所需的自组装基元种类为常数，可以有效地降低求解最大团问题的复杂度。
（2） 另外，本论文还提出了一种利用DNA纳米金颗粒共聚体的自组装过程解决图论中一个NP完全问题—连通度问题的DNA计算方法，构建了解决图的连通度问题的三维DNA自组装计算模型。根据设计的算法，首先需要根据具体的图的连通度问题设计用于自组装的DNA纳米金颗粒共聚体，然后根据算法经过一系列实验过程来求解连通度问题。这种生物化学算法可以降低求解连通度问题的复杂度，所使用的生物化学实验技术也很成熟且便于操作，为下一步DNA自组装计算模型的应用提供了可行的方案。本研究方法还将DNA链置换技术、DNA分子与纳米金颗粒自组装技术结合起来，说明了对微观纳米颗粒的控制能力及潜在应用。
经过本研究的工作，可以证明DNA分子计算与纳米技术相结合，不仅可以提供自下而上的构造微观纳米结构的方法，也可以为将来DNA计算机的研制提供可靠的模型和有效的生物化学算法。