王欣怡，殷志祥，唐 震，杨 静，崔建中

(1.安徽理工大学数学与大数据学院，安徽 淮南 232001；2.上海工程技术大学数理与统计学院，上海 201620； 3.安徽理工大学电气与信息工程学院，安徽 淮南 232001；4.淮南联合大学计算机系，安徽 淮南 232001)

1 引言

随着计算机技术的高速发展，各种非线性问题和NP完全问题在新的工程技术领域不断出现，而现有的电子计算机无法解决这类复杂的计算问题[1]。DNA计算作为一种新型计算方式，由于DNA分子的特异性、微小性和高并行性等天然特性，在海量信息存储和处理过程中，可以高容量保存以及并行操作，这为解决复杂的计算提供了一种新途径，是具有广泛应用前景的热点研究领域。1994年，Adleman教授[2]利用DNA编码解决了有向图的Hamilton路径问题，首次划时代地迈入DNA计算领域。1995年Lipton[3]在Adleman的实验基础上，提出利用DNA计算解决NP完全问题。

2006年，Rothemund[4]第1次提出DNA折纸术的概念，他将一条DNA长链(脚手架链)与经过一系列步骤设计而成的DNA短链(订书钉链)，通过碱基互补配对，可控地折叠成各种复杂的纳米级形状和图案，具有传统DNA自组装所不具备的优势，在新兴的纳米领域中具有广泛的应用前景。同年，Qian等人[5]利用DNA折纸术建立了一个非对称模拟中国地图，该结构是首个通过DNA折纸术构建的非对称图形。

2014年，Yang等人[6]利用多输入结合诱导效应建立一个可以检测多个输入信号的逻辑系统，为多个分子的靶向检测和构建大规模DNA计算的复杂纳米器件的设计提供了可能。2015年，俞洋等人[7]利用DNA折纸术折叠出可用来编码Hamilton路径图中顶点和路径的固定的DNA纳米结构，为Hamilton路径问题提供了一种新的解决方案。……