简单0-1规划问题的动态DNA折纸计算模型

斯燕方，殷志祥，崔建中，杨 静，唐 震

1.安徽理工大学 数学与大数据学院，安徽 淮南232001

2.安徽理工大学 电气与信息工程学院，安徽 淮南232001

3.淮南联合大学 计算机系，安徽 淮南232001

1 引言

DNA作为生物遗传信息的载体，具有纳米可编程等优点，利用这个特点来设计纳米结构一直是研究的热点。近年来出现的DNA折纸术为设计复杂二、三维纳米结构提供了新的方法手段。与传统的DNA自组装技术不同，DNA折纸术通过一条长的DNA单链（脚手架链）与一系列预设计的短链DNA片段（订书钉链）进行碱基互补配对，折叠出高度复杂的二维纳米图案和三维纳米结构。与传统纳米自组装方法相比，DNA折纸术具有更佳的精细程度和可控性，而且其实验条件要求低，操作简单，效率高。

最近的研究成果表明，在组装的规模上，DNA折纸术也取得了较大的进展。DNA折纸术[1]是一种不同于传统自组装（自上而下的组装）的方法。它的思路是将一条长度为7 429个碱基（M13mp18噬菌体DNA）的DNA作为脚手架链，并利用200多条订书钉链将其折叠固定，得到了正方形、矩形、五角星、笑脸和三角形等精细复杂的二维结构。DNA折纸术的研究为实现纳米结构的精确组装奠定了基础。随后更加复杂多样的纳米结构不断被设计出来，为纳米器件的深入研究提供了更为精密的模板[2-3]。同年，上海交通大学Bio-X中心的DNA计算机交叉研究团队与中国科学院上海应用物理研究所进行合作，成功构造出“仿中国地图”的DNA纳米结构[4]。这是国内首个利用DNA链折叠得到的非对称二维图形，克服了非对称图形带来的应力问题。2010年，晁洁等[5]利用DNA折纸设计了“三手四足”DNA机器人。该方法为DNA折纸机器人作为载药工具的应用提供了良好的思路。接着在2015年和2016年，晁洁等[6-7]又利用DNA纳米折纸结构相继给出了寻找最短哈密顿路的方法和图着色问题的一种解决方法。晁洁等[8]在2017年还将DNA折纸应用于基因分型，利用三角形、十字形和矩形作为标签对人类基因组DNA的单个分子进行基因分型，这种方法在单分子水平的遗传分析中具有巨大潜力。2016年，Xu等[9]用DNA折纸折叠出一个可编程的DNA折纸平台，用来组织用于膜融合的陷阱。2017年，Chikkaraddy等[10]利用DNA折纸技术，将单分子发射器组装成等离子体纳米粒子，成功绘制出纳米热点图。同年，Fan等[11]还利用DNA折纸构建更高阶结构的支架。Tikhomirov等[12]利用正方形DNA折纸阵列的分型组装得到了微米级蒙娜丽莎、公鸡等图案。Wagenbauer等[13]利用V形DNA折纸作为基本单元，通过控制基本单元之间的几何形状和作用，构造更大的组装体。2018年，Urban等[14]用DNA折纸组装成等离子体环形超分子。

0-1规划问题是整数规划问题的特殊情形，其应用非常广泛，是运筹学中的一个重要问题。许多NP完全问题也都可以转化为0-1规划问题。解决该问题的算法很多，如穷举法、隐枚举法等。2003年，殷志祥等[15]首次提出了一种基于荧光标记的策略，解决了简单0-1规划问题。2008年，杨静[16]提出了基于三链DNA结构的0-1整数规划算法。2013年，任晓玲等[17]又改进了该算法，使得该算法对问题解的检测更加有效。2017年，Li等[18]提出了一种新的基于自组装纳米探针的DNA计算模型。同年，殷志祥等[19]给出基于质粒的DNA算法来解决特殊的整数规划问题。朱建鹏[20]研究了特殊0-1整数规划问题的DNA芯片模型。2018年，赵鑫月等[21]也是利用DNA折纸术，通过链之间的杂交反应形成二级结构解决0-1规划问题。

本文应用一种动态的DNA纳米折纸结构来解决0-1规划问题。模型由三部分折纸结构组装而成，分别为DNA折纸卡槽、双态DNA机器[22-23]、DNA行走机器人[24-25]。其中DNA折纸卡槽是由1条M13长链和202条DNA短链折叠而成的拥有3个插槽的折纸结构，并且插槽的下方用固定的延伸单链形成了DNA行走机器人向前移动的“轨道”。双态DNA机器由14条DNA单链折叠而成，它与插槽处延伸的单链互补，从而将双态DNA机器固定在DNA折纸插槽内形成折纸基底。3台双态DNA机器分别对应0-1规划问题的3个约束变量，双态DNA机器下方的一条单链用于携带或者不携带金纳米颗粒，这对应于0-1规划问题中约束变量取1或者取0。DNA行走机器人是7条单链折叠成的折纸结构，且这7条链的3'端为粘性末端。这些粘性末端称为DNA行走机器人的“手”和“足”。它与DNA折纸卡槽中的延伸单链互补，通过链置换使得DNA行走机器人以顺时针旋转，沿着DNA折纸基底上预先设计的“轨道”行走，每步旋转120°。在“行走”的过程中，DNA行走机器人的“手”通过链置换将双态DNA机器上修饰金纳米颗粒的单链置换下来。通过6次旋转、6步行走，DNA行走机器人能够将全部3台双态DNA机器上连接金纳米颗粒的单链全部置换出来。当整个动态行走过程结束，根据透射电镜下DNA行走机器人接收的金纳米颗粒的大小和个数判断变量的取值是否为可行解。

2动态DNA折纸

动态DNA折纸包括3个DNA折纸结构：DNA折纸卡槽（图1（a））、双态DNA机器（图1（b））和DNA行走机器人（图1（c））。DNA折纸卡槽由1条M13链和202条短链折叠而成，下方3个三角形共9条延伸的单链用来连接DNA行走机器人的“足”，构成行走机器人行走的“轨道”，DNA折纸卡槽上方白色柜形方框为3个插槽，分别与双态DNA机器PX1、PX2、PX3通过互补单链连接。图1（b）是携带金纳米颗粒的双态DNA机器PX1，其中金纳米颗粒用黄色表示，它可与DNA行走机器人的“手”发生链置换，将原先修饰在双态DNA机器上的金纳米颗粒置换至DNA行走机器人上。7条单链折叠成带有粘性末端的DNA行走机器人，其中粘性末端H1～H3链为“手”，F1～F4为“足”，为了确保DNA行走机器人与双态DNA机器进行链置换，“足”F4在插槽的正下方被固定。行走机器人的每步都需要顺时针旋转120°，从第一个插槽位置转到第二个插槽需要走两步。

图1动态DNA折纸结构

组装后的动态DNA折纸如图2所示，DNA行走机器人在图2中表示为红色三角形。

图2 组装后的动态DNA折纸结构

图3给出了DNA行走机器人从双态DNA机器PX1上接收金纳米颗粒的过程。行走机器人的“手”H1通过链置换将DNA机器上携带的金纳米颗粒接收到行走机器人上。因为有3个双态DNA机器，且DNA机器上可以携带或者不携带金纳米颗粒，所以DNA行走机器人经过3个插槽后会产生8种不同的金纳米颗粒的组合，对应于简单0-1规划问题中所有变量可能的取值。图3中A-1、A-2、A-4为加入的短链DNA片段，能够通过碱基互补将DNA行走机器人的“足”固定在折纸基底上，从而接收双态DNA机器修饰的金纳米颗粒。

图3 DNA行走机器人接收金纳米颗粒示意图

图4给出了DNA行走机器人的行走过程。编号1-7分别为组成DNA机器人的7条单链DNA片段，粘性末端H1～H3为行走机器人的“手”，F4～F7为“足”。O-*为折纸基底上延伸出的9条单链，构成了DNA行走机器人移动的3个站点，它同时对应折纸基底上方的插槽。A-*为9条DNA短链，它与DNA行走机器人的“足”F4～F7及O-*互补，作用是将行走机器人的“足”和折纸基底上的延伸短链O-*连接来绑定行走机器人，使得行走机器人能按照指定的“轨道”行走。FA-*为9条与A-*完全互补的短链，它能够置换出行走机器人被绑定的“足”，从而解开行走机器人与折纸基底表面的连接。通过绑定与解绑，实现DNA行走机器人在折纸基底上预定的“轨道”行走。图4给出了DNA行走机器人从第一个站点到第二个站点的行走过程。图4左下表示行走机器人位于第一个站点，此时“足”F4和F5分别被单链A-1和A-2绑定于单链O-1和O-3上，“足”F7也被单链A-4绑定在单链O-2上，使得DNA行走机器人被固定，“手”H1位于靠近双态DNA机器PX1的位置，可用来接收金纳米颗粒。随后加入FA-1和FA-4置换出链A-1和A-4，此时“足”F4和F7被解绑，“足”F5仍处于绑定状态，加入单链A-3将“足”F6和O-4绑定，此时DNA行走机器人旋转120°，相当于向前行走了一步，位于第一个站点和第二个站点中间，由于此时不在双态DNA机器的下方，即不用接收金纳米颗粒，故“足”F7无须绑定，如图4中间。接下来加入单链FA-2将单链A-2置换出来，此时“足”F5与O-3解绑，只有“足”F6仍处于绑定状态，再加入单链A-5将“足”F4与O-6绑定，由于此时位于双态DNA机器PX2的下方，还需要加入单链A-6将“足”F7绑定于O-5上，“手”H2靠近DNA机器PX2，可以接收金纳米颗粒。此时DNA行走机器人又旋转了120°，相当于再向前移动了一步，位于第二个站点，如图4右下。行走机器人从第二个站点移动到第三个站点与此类似。最后可以通过加入绑定链的互补链将DNA行走机器人的“足”全部解绑，将行走机器人置换出来。

图4 DNA行走机器人行走示意图

当DNA行走机器人经过3个站点，将行走机器人所有的“足”全部解绑后，可通过透射电镜观察行走机器人上接收的金纳米颗粒的情况。

3 简单0-1规划问题的动态折纸计算模型

在运筹学中，0-1规划问题属于整数规划问题，是整数规划的特殊情形，这种规划的约束变量仅取值0或1。它的一般形式为：

其中aij为任意整数，ci,bj(i=1,2,…,m;j=1,2,…,n)为非负整数。本文利用动态DNA折纸求解如下简单的0-1规划问题。

简单0-1规划问题的动态折纸算法：

步骤1生成给定问题的变量取值为0或1的所有可能组合。

步骤2利用每一约束条件删除非可行解（保留可行解），重复进行，得到问题的可行解。

步骤3比较各可行解对应的目标函数值，进而得到最优解。

对于一个含有n个变量x1,x2,…,xn和m个方程的方程组，对应算法的步骤如下：

步骤1首先折叠出2n种双态DNA机器。把这2n种双态DNA机器分成两组，第一组的n种双态DNA机器分别用不同大小的金纳米颗粒修饰，每一个双态DNA机器分别代表变量x1,x2,…,xn；第二组的n种双态DNA机器在折纸结构上和第一组的n种对应相同，但均不用金纳米颗粒修饰，分别代表变量。这里xi对应的双态DNA机器表示变量xi取值为1，而对应的双态DNA机器表示变量xi取值为0。然后需要折叠出2n个相同的DNA折纸卡槽和2n个相同的DNA行走机器人，同时构造出这2n种双态DNA机器的不同2n个组合，每个组合包含n个变量所对应的双态DNA机器，通过碱基互补的方式与DNA折纸卡槽的插槽处结合，组装成2n个DNA折纸基底。

步骤2在每一个组装好的DNA折纸基底中加入一个DNA行走机器人。首先用对应的短链将它固定在第一个双态DNA机器的下方所对应的站点处，此时DNA行走机器人的“手”H1会与双态DNA机器下方的延伸单链互补置换出此条单链，若这条单链5'端携带金纳米颗粒即为x1(x1=1)，若这条单链5'端不携带金纳米颗粒即为。然后依次加入相应的短链和互补短链来绑定和解绑相应的“足”，使得DNA行走机器人沿固定的“轨道”向前“行走”，经过2n步后将DNA行走机器人置换出来。最后通过透射电镜观察置换出的DNA行走机器人所携带金纳米颗粒的大小及个数，用第一个约束条件判断并排除非解，对于已经判断为不满足约束条件的后面都不再考虑，接着用第二个约束条件判断并排除非解，如此重复进行，使得所有的m个约束条件都判断结束。从而得到所有正解。

步骤3计算出各可行解所对应目标函数的值，进而判断出最优解。

4 实例分析

下面具体讨论一个简单0-1规划问题。

步骤1生成变量的所有可能组合。由于实例中有3个约束变量，共有8种解的可能组合。首先利用DNA折纸术折叠出DNA折纸卡槽、双态DNA机器和DNA行走机器人。将双态DNA机器分成6组，前3组分别修饰5nm、7nm和10nm金纳米颗粒，分别记为px1、px2和px3，分别对应于简单0-1规划问题中约束变量x=1,y=1和z=1；后3组不修饰金纳米颗粒，分别记为，分别对应于简单0-1规划问题中约束变量x=0,y=0和z=0。对应于解的所有可能组合，取3种双态DNA机器与DNA折纸卡槽组装成为DNA折纸基底，一共8种。记这8种DNA折纸基底为0（0，0，0）、1（1，0，0）、2（0，1，0）、3（0，0，1）、4（1，1，0）、5（1，0，1）、6（0，1，1）、7（1，1，1）。DNA折纸基底组装完成后将DNA行走机器人加入，并按以下顺序加入相应的DNA短链：

（1）依次加入A-1、A-2、A-4，分别将“足”F4、F5、F7绑定在O-1、O-3、O-2上，待DNA机器人的“手”H1与双态DNA机器PX1下端延伸单链发生链置换反应；

（2）依次加入A-1、A-4的补链FA-1、FA-4解开“足”F4、F7，再加入A-3将“足”F6绑定于O-4上；

（3）加入A-2的补链FA-2解开“足”F5，再依次加入A-5、A-6分别将“足”F4、F7绑定在O-6、O-5上，待DNA机器人的“手”H2与双态DNA机器PX2下端延伸单链发生链置换反应；

（4）依次加入A-3、A-6的补链FA-3、FA-6解开“足”F6、F7，再加入A-7将“足”F5绑定于O-7上；

（5）加入A-5的补链FA-5解开“足”F4，再依次加入A-8、A-9分别将“足”F6、F7绑定在O-9、O-8上，待DNA机器人的“手”H3与双态DNA机器PX3下端延伸单链发生链置换反应；

（6）依次加入A-7、A-8、A-9的补链FA-7、FA-8、FA-9解开“足”F5、F6、F7，将DNA行走机器人置换出来。

这里分步加入短链是为了让DNA行走机器人沿预定的“轨道”行走，且有足够的时间能够接收金纳米颗粒。经过6步将DNA行走机器人置换出来，通过透射电镜观察DNA行走机器人所接收的金纳米颗粒的大小及个数。

步骤2针对简单0-1规划问题的约束条件，删除非可行解得到可行解。为了能直接通过DNA折纸技术获得可行解，对上述DNA折纸模型进行优化改进。

如图5（a）所示，将DNA折纸卡槽增加一条延伸单链O-10或O-10*，其中O-10和O-10*为互补单链。对于每一个约束条件，非可行解的卡槽增加延伸单链O-10，可行解的卡槽增加延伸单链O-10*。

将上述步骤（6）作如下改动：依次加入A-7、A-9的补链FA-7、FA-9解开“足”F5、F7，此时F6仍绑定在O-9上，如图5（b）所示。然后加入短链A-10，A-10与O-10通过部分互补将“足”F4绑定于O-10上。由于O-10与O-10*是互补链，A-10并不能将“足”F4与O-10*绑定。最后加入A-8的补链FA-8解开“足”F6。

图5改进DNA折纸模型

此时，如果是不满足约束条件的非可行解，DNA行走机器人的“足”F4仍绑定于O-10上无法完全置换出来；如果是满足约束条件的可行解，由于“足”F4没有被绑定，DNA行走机器人能够被完全置换出来。通过透射电镜能够观察到所有的可行解。

对于实例中第一个约束条件x+y+z≤2，DNA行走机器人所接收的5 nm、7 nm和10 nm金纳米颗粒总数不多于2个，则满足此约束条件的解为0（0，0，0）、1（1，0，0）、2（0，1，0）、3（0，0，1）、4（1，1，0）、5（1，0，1）、6（0，1，1）。

对于实例中第二个约束条件x+y≥1（不满足第一个约束条件的后面不再考虑），DNA行走机器人所接收的5 nm和7 nm的金纳米颗粒总数不少于1个，满足此约束条件的解为1（1，0，0）、2（0，1，0）、4（1，1，0）、5（1，0，1）、6（0，1，1）。

类似地，对于实例中第三个约束条件y+z≤1，DNA行走机器人所接收的7 nm和10 nm金纳米颗粒总数不多于1个，满足此约束条件的解有4组，分别为1（1，0，0）、2（0，1，0）、4（1，1，0）、5（1，0，1），即为所求简单0-1规划问题的可行解。因此将0、3、6、7号DNA折纸卡槽的第十条延伸单链设计为O-10；1、2、4、5号DNA折纸卡槽的第十条延伸单链设计为O-10*。透射电镜下解的示意图如图6所示。

图6 所有可行解

步骤3该实例有4个可行解，分别为：

x=1,y=0和z=0,此时u=2；

x=0,y=1和z=0,此时u=1；

x=1,y=1和z=0,此时u=3；

x=1,y=0和z=1,此时u=5。

因为要求目标函数的最小值，所以x=0,y=1,z=0为该问题的最优解，对应目标函数的值为1。

5 结束语

本次研究主要是鉴于近年来链置换技术在分子计算领域的相关应用。本文采用了DNA折纸结构与金纳米颗粒相结合组装基底，通过链置换技术构造动态的简单0-1规划问题的DNA计算模型。此DNA折纸模型具有高灵敏度、高特异性、可预测性和可编程性，用来解决0-1规划问题不仅摆脱了试管，还极大地提高了效率，并且对于一个含有n个变量的约束方程组，产生所有可能结果的双态DNA机器仅为2n种，大大简化了实验步骤，给实验过程带来极大的便利。金纳米具有特殊的表面效应、体积效应、量子尺寸效应和宏观量子隧道效应，使得金纳米与生物体有着特殊的相互作用，并且金纳米标记具有方法比较方便、标记后对生物分子的活性影响较小等优点。本文仅对简单的0-1规划问题进行了详细的讨论，但是对于一般的0-1规划问题来说，该方法求解还存在一定困难。首先当问题的变量增多时，折纸结构将会更加复杂；其次当问题中n过大时，仅仅通过金纳米颗粒的大小来判断问题的解具有一定困难，因此需要更多具有标记性的结构。相信随着分子生物学及生物工程，特别是DNA折纸技术的进一步发展，此模型也能应用于求解一般的0-1规划问题，甚至解决一般的整数规划问题也将成为现实。