中文摘要：

现实社会中许多理论与工程问题可归结成图信息处理中的NP-完全问题。随着问题规模的增大，电子计算机对NP-完全问题的求解受阻。在非电子计算模式的新型信息处理工具的研究中，DNA计算近年来异军突起，倍受关注。研究表明 DNA计算在求解NP-完全问题上具有内在并行性等独特优势。本项目在已有研究成果的基础上，利用纳米技术，提出了一种新颖的求解图与组合优化问题DNA计算模型，称为纳米型图信息处理DNA计算模型。该模型的基本思想是以纳米颗粒作为图的顶点，且标记每个顶点的名称用一段DNA序列来表示；两个顶点之间的边通过探针来建立。具体内容是(1) 构建纳米颗粒-DNA分子信息表示方法；(2) 设计基于纳米颗粒的图信息处理DNA计算模型；(3) 建立相应的生化实验的平台及检测技术。项目的特色是充分将DNA计算、纳米技术与NP-完全问题等有机地结合起来展开研究，有望求解大规模的NP-难问题。

结论摘要：

DNA分子具有微小性、超强并行操作性等特点。近年来随着DNA纳米技术的发展， DNA计算在信息处理和纳米智能等领域得到广泛的关注和研究。本项目重点围绕着图顶点着色问题的DNA计算模型展开研究，在对纳米颗粒和DNA分子相结合的特性的研究基础上，建立了一种可靠性较高的DNA编码方案，以及建立一种用于求解图顶点着色问题的非枚举型DNA计算模型，并对该模型的可扩展性进行了相应的研究和实验验证。在研究DNA分子和纳米颗粒相结合的技术同时，构建了基于纳米颗粒色变反应的逻辑计算理论模型。目前，关键的实验工作已经完成，已实现了基于DNA分子/纳米颗粒自组装结构的纳米逻辑门系统，通过纳米颗粒群体的色变，获得纳米逻辑运算结果。本项目将DNA计算、纳米技术与NP-完全问题等有机地结合起来展开研究，所得到的计算模型经过理论和实验验证可用于较大规模的图与组合优化问题的求解，且实验技术稳定，对于DNA计算的自动化实现打下了一定的基础。