陈 哲，殷志祥，唐 震

（1.安徽理工大学数学与大数据学院，安徽淮南232001；2 上海工程技术大学数理与统计学院，上海201620）

DNA 折纸术和DNA 分子一直是科学家们研究的重点。1994 年Adleman 第一次利用DNA 编码解决了有向图的Hamilton 路径问题，之后，DNA 计算这一利用DNA 分子的特性来计算一些难计算问题（如0-1 整数规划问题，可满足问题，最大团问题）的新型计算领域迅速成为了热点研究领域[1-7]。20 世纪80 年代，Seeman 首先提出利用碱基互补配对的原则可将DNA 组装成复杂的空间结构为后来的DNA 计算打下了坚实的基础[8-10]。在最初的DNA 计算中，更多的是对DNA分子进行特定的编码来完成计算。随着生物技术的发展，DNA 链置换因其反应的操作性强、实现条件简单、产物可预见等优点被广泛运用于DNA计算中。2006 年，Rothemund 开发了一种新的DNA 自组装技术，称为DNA 折纸术。他们选用噬菌体DNA M13mp18 作为长链，然后用两百多条短的单链DNA 通过碱基互补配对原则，将长链折叠了矩形、三角形、五角星、笑脸，甚至还有世界地图，等等[11-13]。2011 年，钱璐璐等人构建了一种生化电路，这种基于DNA 链置换的生化电路可以用来求解四位二进制数平方根[13]。同年Yan 课题组在Science 上以封面论文形式发表了可精确控制三维曲面的立方体花瓶结构，将DNA 折纸术在结构设计与制造方面的研究推向了高潮[14]。2017年，Li 构建了一种自组装纳米探针的0-1 规划问题的计算模型，该模型是由两条带有荧光分子的DNA 单链硫化在纳米金颗粒上构成的。常规状态下，荧光分子会被吸附到纳米金颗粒的表面，荧光呈淬灭状态，当加入目标DNA 链后，通过DNA链置换，目标DNA 链会和吸附在纳米金颗粒上的DNA 链互补，从而将荧光分子从纳米金颗粒上分离开，荧光分子呈荧光状态[15]。

本文利用DNA 链置换技术构建了一种解决可满足性问题的模型，可满足问题的约束条件被映射成计算模型上的荧光个数，通过DNA 链置换反应，观察计算模型上的荧光个数找出可满足性问题的可行解，同时给出一个实例来解读该模型。

1 可满足性问题和DNA 链置换

1.1 可满足性问题

可满足性问题是一个经典的NP 完全问题，它在逻辑电路的设计及密码问题的研究中都有广泛的应用。通常SAT 问题可以表述为：给定一个布尔表达式

其中Ci=V1∨V2∨…Vm为布尔变量，取值为0 和1，“∧”为逻辑“合取”，“∨”为逻辑“析取”。SAT问题就是使得F=1 的所有布尔变量Vi的真值分配表。显然，对于有n个变量的布尔公式F有2n个可能的赋值。

1.2 DNA 链置换

DNA 链置换指的是1 条DNA 单链置换出部分复合物中原绑定链的反应过程，是一种DNA 分子间的自发反应。链置换反应的原理是：由于DNA 单链的长度不同，形成双螺旋结构的结合力也有所差异。由较强结合力的输出链置换掉部分互补结构中结合力较弱的DNA 链。简单的理解：较长DNA 链取代较短的DNA 链，并且被替代的链作为输出信号以实现分子逻辑运算等操作。DNA 链置换基本过程示意图见图1。

图1 DNA 链置换基本反应原理

2 基于DNA 链置换的可满足性问题的计算模型

2.1 模型的设计

对于可满足问题中的任意变量xi，与之对应的设计图2 所示的计算模型，对于n个变量，这样的计算模型共有n个。计算模型是将一个纳米颗粒固定在两条DNA 链硫化上，其中的一条链是由Li-Xi部分互补构成的DNA 链，Li上带有荧光分子；另一条是与Li链完全互补的DNA 单链DNA 单链上带有荧光淬灭分子。常规状态下，该计算模型荧光呈明亮状态。

图2 基于DNA 链置换的可满足性问题的计算模型示意图

2.2 基于DNA 链置换的可满足性问题的计算模型的生物算法

设计思路：将可满足性问题中变量的两种取值映射成荧光分子明灭的两种状态，当xi=0 时，映射成荧光分子淬灭，当xi=1 时，荧光分子明亮。为了实现这一目的，对于任意的xi=0,设计对应的DNA 链23，它与模型中的DNA 链xi完全互补，荧光分子和荧光淬灭分子相遇，导致荧光淬灭，见图3（a）。对于任意的xi=1，设计对应的DNA 链xi，它与模型中的DNA 链xi一模一样，添加xi后，不发生任何反应，荧光保持明亮状态，见图3（b）。

图3 xi=0 和xi=1对应的反应示意图

基于DNA 链置换的可满足性问题的计算模型生物算法如下：

1）对于含n个变量（x1,x2,…,xn）和m个约束条件的可满足性问题，它的所有可能解是2n个，对应的是2n个不同组合的DNA 链。

2）构造对应变量的计算模型（n个），放入2n个试管中。在每个试管中加入一组DNA 链，在室温下进行DNA 链置换反应。

3）对于第一个约束方程，它的约束条件被映射成荧光个数。通过荧光检测，就可以得到满足第一个约束方程的可行解。重复此步骤，就可以得到满足所有约束方程的可行解。

4）利用目标函数计算出各可行解对应的目标函数值，进而判断出最优解。

2.3 实例分析

下面来看一组具体的实例：

步骤1：对于含3 个变量（x1,x2,x3）和3 个约束条件的可满足性问题，它的所有可能解是23个，分别是1(1,1,1)，2(0,1,1), 3(1,0,1), 4(1,1,0), 5(0,0,1), 6(0,1,0), 7(1,0,0), 8((0,0,0)。对应的是23个不同组合的DNA 链，比如1 号解（1,1,1）对应的DNA 链组合是x1-x2-x3，2 号解(0,1,1)，对应的DNA 链组合是，3 号解（1,0,1）对应的DNA 链组合是，4 号解（1,1,0）对应的DNA 链组合是，8 号解（0,0,0）对应的DNA 链组合是

步骤2：构造对应变量的计算模型（3 个，见图4），放入8 个试管中。在每个试管中加入一组DNA 链，在室温下进行DNA 链置换反应，其中1，2，3，4 号解的反应示意图分别如图5～8 所示。

图4 3 变量计算模型示意图

图5 1 号解（1，1，1）反应示意图

步骤3：对于第一个约束方程，它的约束条件是大于等于1，映射成荧光个数就是荧光个数大于等于1 的DNA 链组是满足第一个约束方程的解，据此得到满足第一个约束条件的可行解是1，2，3，4，6，7 号解；对于第二个约束方程，因为不涉及变量x2，所以绿色荧光不考虑，它的约束条件映射成绿色荧光外，剩余荧光颜色个数大于等于1 的DNA 链组是满足第二个约束方程的解，它们是1，2，3，4，5，7 号解；对于第三个约束方程，现在只判断1，2，3，4，7 号解，因为不涉及变量x1，所以红色荧光不考虑，剩余荧光颜色个数大于等于1 的DNA 链组是满足第三个约束方程的解，它们是1，2，3，4。

步骤4：经过以上步骤后得到可满足所有约束方程的可行解，比较其目标函数即可求出该可满足问题的最优解。

图6 2 号解（0，1，1）反应示意图

图7 3 号解（1，0，1）反应示意图

图8 4 号解（1，1，0）反应示意图

3 小结

本文构建了一个基于DNA 链置换反应的可满足问题的计算模型，将可满足问题中变量的取值设计成不同的DNA 链，通过DNA 链置换反应，观察最后的计算模型上的荧光个数找出可满足问题的可行解。由于DNA 链置换反应条件简单、产物量高，所以该计算模型具有一定的可行性，而且最后的结果通过荧光检测来观察反应的结果，操作简单、结果准确。