王夕远, 殷志祥,2*, 唐 震, 杨 静, 崔建中, 徐如解

(1. 安徽理工大学 数学与大数据学院, 安徽 淮南 232001; 2. 上海工程技术大学 数学与统计学院, 上海 201620; 3. 淮南联合大学 计算机系, 安徽 淮南 232001)

计算机技术被认为是20世纪3大科学革命之一，电子计算机为社会发展起到了巨大的促进作用。近年来，由于科技的迅猛发展，传统电子计算机已经难以满足人们的需求。DNA计算机是近些年最有独创性和出乎意料的发现之一，具有高度的并行性、运算速度快、存储容量大、耗能低和DNA分子资源丰富等优点。为了制造出DNA计算机，人们开始对DNA计算进行研究。DNA计算的第一个例子解决了一个7城市哈密顿路径问题[1]。2000年，Head等[2]提出了使用DNA质粒的一种新的计算方法，列出了潜在的优势。通过报告计算图顶点集最大独立子集基数的NP完备算法题的一个实例计算，说明了新方法的有效性。2003年，殷志祥等[3]提出了在基于表面的DNA计算采用荧光标记策略，解决了简单的0-1规划问题。2006年，Rothemund[4]用DNA折叠来创造纳米尺度的形状和图案。2009年，Xie等[5]提出了基于微流控芯片的拼接型DNA计算方法。2010年，Yang等[6]提出了一种新的基于循环DNA的最大团问题计算模型。2011年，Qian等[7]提出了DNA链置换级联的神经网络计算，同年，Zhang等[8]提出了基于DNA纳米自组装的分子逻辑计算模型。此外，DNA计算还可以用来构建半加器、半减器、全加器和全减器[9-14]。2018年，Yin等[15]利用分子信标计算模型解决了最大权团问题，同年，赵鑫月等[16]利用DNA折纸术解决了0-1整数规划问题。2019年，Chao等[17]利用DNA单分子导航仪求解迷宫问题，唐震等[18-19]利用DNA折纸术解决了一类特殊的整数规划问题，还提出了在DNA折纸基底上的一种动态的与非门计算系统。2020年，杨新木等[20]利用DNA折纸术解决了0-1背包问题，刘璐璐等[21]提出了异或门的DNA计算模型，斯燕方等[22]提出了简单0-1规划问题的动态DNA折纸计算模型，杨静等[23]提出了基于杂交链式反应工序问题的DNA计算模型。

1.1 可满足问题

可满足问题(SAT)是一个经典的NP问题，它在逻辑电路的设计和密码问题中的研究方面都有广泛的应用。SAT问题可以描述为：对于一个给定的含有n个命题变项的合取范式(析取范式)，是否存在一组结果为真的赋值(真值为1)。SAT问题可用布尔逻辑表达式表示为F=C1∧C2∧…∧Cm。其中Ci=k1∨k2∨…∨kt,(i∈{1,2,…,m})为布尔变量，取值为0和1。用“0”表示真值“假”，用“1”表示真值“真”，“∧”为逻辑“与”，“∨”为逻辑“或”。SAT问题就是求使得F=1的所有布尔变量ki的真值分配表。显然，对于含有n个变量的布尔公式F有2n个可能的赋值。2004年，刘文斌等[24]介绍了几种SAT问题的 DNA计算模型,并在编码问题、实现方式及算法设计等3个方面对其进行了比较。2008年，Wang等[25]使用基于连接酶链反应的DNA计算算法解决SAT问题。2009年，周康等[26]利用闭环DNA解决了可满足性问题。2012年，刘文君等[27]提出了可满足性问题的一种DNA表面计算模型。2016年，陈玉华等[28]提出了基于分子信标的可满足性问题的粘贴模型。2020年，陈哲和斯燕方等[29-31]也解决了可满足性问题。

1.2 DNA链置换

DNA链置换技术是指 DNA单链与部分互补双链发生结构反应，替代并显示出原有结构中被约束的单链，从而生成新双链结构的过程。当互补链的长度变化时，形成双螺旋结构的结合力也有所不同。当 DNA分子在杂交系统中，逐渐过渡到熵不断增加，自由能趋于稳定的状态，从而实现结合力较强的输入链替换结合力较弱的被约束的单链，最后，被替代的单链作为输出信号，实现分子逻辑运算功能。2013年，Anthonuy等[32]将DNA链置换应用于矩阵乘法和加权和中。同年，Li等[33]通过DNA链置换完成了三输入多数逻辑门的设计。2016年，Li等[34]基于DNA链置换构建了一个半加器。2017年，Song等[35]利用自催化放大器设计和分析了用于模拟计算的紧凑DNA链置换电路。Zhang等[36]利用DNA链置换解决了概率问题。2019年，吴涛等[37]基于DNA链置换构建逻辑计算模型。

DNA链置换可以分为可逆和不可逆2种情形，可用如下的公式进行表示：

不可逆：{A^}[B^]+→+[AB^],

可逆：{A^}[BC^]+↔+[AB^]{C^}。

DNA不可逆和可逆的链置换反应见图1。

图1中{A^}[B^]表示部分互补的DNA双链；
{A^}[B^]和{A^}[BC^]中的单链部分称之为脚趾。这里对于DNA链的描述是采用了Visual DSD语言。在Visual DSD中，尖括号中的序列表示3′端在右侧的链，也称之为上部链，而大括号中的序列表示3′端在左侧的链，也称为下链。这2种描述方式是可以相互转换的，只是方向有所不同。序列可以是一个域、一个域补码，具有多个位置标记的系链或由空格分隔的多个序列。域可以是由标识符表示的识别域，可以是在标识符上附加(∧)字符表示的toehold域。中括号则表示的是通过碱基互补配对所形成的DNA双链结构，箭头的方向表示反应的方向，单向箭头表示的是不可逆反应，双向箭头表示可逆反应。Visual DSD语言所描述的链见图2。在DNA链置换中的脚趾的长度决定着反应的速率在6碱基内以指数增长，在6碱基时反应速率达到最大。

本文通过DNA链置换反应并利用Visual DSD进行仿真，得到反应网络图来求解可满足性问题。考虑到可满足性问题不需要考虑权重，将求解过程分为3个模块，即变量转换模块、求和模块和阈值比较模块，在阈值比较模块中，由于浓度的检测会存在一定的误差，故通过检测是否有荧光显示来判断是否为可行解。

设计思想：对于可满足性问题，如F=(x1∨x2)∧(x1∨x3)∧(x2∨x3),将求解过程分为3个模块：①通过链置换反应将每一个变量xi(i=1,2,3)转换成Y，这里每一个变量都分别对应一条DNA单链；
②对模块一中所得的Y单链进行求和，在数字上是一般的加法运算，实际上是浓度的相加；
③通过阈值的比较来判断解是否满足要求，这里假设阈值为0.9 nm。通过这3个模块可以求解出布尔公式F的第一个析取范式的解，重复上述3个模块得出所有的解。当变量xi=1(i=1,2,3)时，输入相对应的单链DNA浓度为1 nm；
当xi=0(i=1,2,3)时，则不输入相应的DNA单链Xi(i=1,2,3)。上述的3个模块具体描述如图3。

2.1 变量转换模块和求和模块

针对SAT问题，设计了一个变量转换模块和求和模块。在变量转换模块中，将每一个变量xi=1(i=1-n)分别设计成一条DNA单链Xi，通过链置换反应将每一个变量xi=1(i=1-n)所代表的单链转换成变量Y所代表的DNA单链，即

Xi→Y(i=1-n),

Xi+Zi→Y+waste.

对于这一化学反应步骤，需要辅助链Zi的参与，如图4所示。对于可满足问题，当变量xi=1(i=1-n)，设ss-DNAXi的初始浓度为1 nm。对于这一反应1 nm的Xi经过反应能得到1 nm的Y。对Y的浓度进行相加。在DNA链置换反应中，Xi和Zi的初始浓度满足[Xi]0<<[Zi]0。

2.2 阈值的比较模块

在求和模块中，可以得到Xi→Y(i=1-n),此时，Y作为反应的输出链，将Y链的浓度和所设定的阈值进行比较，得出满足问题的可行解。然而，对于浓度的准确检测在现实中存在一定的限制。通过设计链置换反应置换出荧光来解决这一限制。若有荧光显示，则是所求问题的一个解；
若没有荧光显示，则不是所求问题的解。这里所设计的链置换反应需要有2个辅助链的参与，化学反应网络模块描述如下，可以通过Visual DSD的反应网络来实现。

[Y]0≤

这里的P和T是链置换反应所需要的辅助链，具体见图5，P和T都是部分互补的双链DNA，其中T的上浮单链DNA的3′端标记有荧光基团，下游单链DNA的5′端标记有荧光猝灭剂，这样使得T一开始不发光。随着对DNA链置换反应动力学的表象特征观察到，动力学随着接触点长度[1-3]增加呈指数增加。对于本文的阈值反应模块，3nt是6nt的截断部分，这就导致了l1的反应速率要远大于l2。如果[Y]0≤[P]0,那么链Y将会优先和接触点长的链P反应(图5)；
如果[Y]0>[P]0,链Y会优先和接触点长的链P反应，剩下的Y链再和链T进行链置换反应，使得T链中的荧光和荧光猝灭剂相分离，有荧光显示。因此，只有当[Y]0>[P]0时有荧光显示，这里的[P]0设为阈值，即为0.9。在DNA链置换反应中，初始输入链Y的浓度是由求和反应模块提供，[P]0=0.9,链T的初始浓度也设为阈值，即[T]0=0.9。

(a)初始浓度[Y]0≤[P]0，链Y和脚趾区域a*-b*相结合。反应达到平衡时Q的浓度为[Q]∞=[Y]0;(b)初始浓度[Y]0>[P]0,链Y会先和脚趾区域长的a*-b*先结合，剩下的Y链和脚趾区域b*相结合。当反应达到平衡时Q的浓度为[Q]∞=0.9,随后会有荧光显示出来

简单起见，以5个变量的可满足性问题为例。求解F=(x1∨x5)∧(x2)∧(x3∨x4)∧(x5)∧(x2∨x3∨x4)，在这个布尔逻辑表达式中存在着5个变量，这意味着一共存在着25=32种可能解。将这32种可能解以表格的形式表示出来，见表1。

表1 32种可行解Table 1 32 feasible solutions

(续表1)

下面分3步来寻找可行解。①将变量xi(i=1-5),通过链置换反应将每个变量所代表的DNA单链转换成Y单链；
②将所得到的Y链进行相加；
③将所得到的Y链浓度和阈值相比较，结果可通过DNA链置换观察是否有荧光显示。

(1)在F的第一个析取范式中，包含着2个变量x1和x5。这意味着在32个可行解中只要x1和x5有一个或者同时为1，第一个析取范式结果为真，这样的结果一共有24个，见表2。

表2 第一个析取范式的所有可行解Table 2 All feasible solutions of the first disjunctive normal form

步骤1：将变量x1和x5所代表的链X1和X5通过链置换反应转换成Y链，化学反应网络如下(图6)：

Xi+Zi→Y+waste(i=1-5)。

步骤2：将步骤1中所得到的Y链进行相加。如：(0,0,0,0,0),(1,0,0,0,0),(1,1,0,0,0),(1,1,1,0,0),(1,1,1,1,0),(1,1,1,1,1),分别输出为0,1,2,3,4,5，即分别代表Y的值为0,1,2,3,4,5。

步骤3：将步骤2所得到的输出值和阈值进行比较来判断是否为可行解，具体可通过观察是否有荧光显示来判断，见图7。

在第一个析取范式的可行解基础上，重复上述步骤来求解第二个至第五个析取范式的可行解。

(2)对于第二个析取范式，只需在上述的24个可行解的基础上寻找x2=1的情形。

步骤1：将变量x2所代表的链X2通过链置换反应转换成Y链。化学反应如下：

反应见图8。

步骤2：将步骤1所得的Y链进行相加。如可行解(这里的可行解存在于上述24个可行解中)(0,1,1,1,1)、(1,1,1,0,1)、(1,1,0,1,1)、(1,1,1,1,0)和(1,1,1,1,1)，分别对应Y的输出值为4、4、4、4和5。

步骤3：将步骤2所得到的输出值和阈值进行比较来判断是否为可行解，具体可通过观察是否有荧光显示来判断(图9)。

通过上述步骤满足前2个析取范式的可行解个数为12个(表3)。

表3 前2个析取范式的所有可行解Table 3 All feasible solutions of the first two disjunctive normal forms

(3)对于第三个析取范式，只需在上述的12个可行解的基础上寻找x3=1或x4=1的情况。

步骤1：将变量x3,x4所代表的链X3,X4通过链置换反应转换成Y链。化学反应如下：

反应见图10。

步骤2：将步骤1所得的Y链进行相加。如可行解(这里的可行解存在于上述12个可行解中)(0,1,0,1,1)、(1,1,0,1,1)、(1,1,1,0,1)、(1,1,1,1,0)和(1,1,1,1,1)，分别对应Y的输出值为3、4、4、4和5。

步骤3：将步骤2所得到的输出值和阈值进行比较来判断是否为可行解，具体可通过观察是否有荧光显示来判断。

通过上述步骤满足前3个析取范式的可行解个数为9个(表4)。

表4 前3个析取范式的所有可行解Table 4 All feasible solutions of the first three disjunctive normal forms

(4)对于第四个析取范式，只需在上述9个可行解的基础上寻找。

步骤1：将变量x5所代表的链X5通过链置换反应转换成Y链。化学反应如下：

化学反应见图11。

步骤2：将步骤1所得的Y链进行相加。如可行解(这里的可行解存在于上述6个可行解中)(0,1,1,1,1)、(1,1,1,0,1)、(1,1,1,1,0)和(1,1,1,1,1)，分别对应Y的输出值为4、4、4和5。

步骤3：将步骤2所得到的输出值和阈值进行比较来判断是否为可行解，具体可通过观察是否有荧光显示来判断。

通过上述步骤满足前4个析取范式的可行解个数为6个(表5)。

表5 前4个析取范式的所有可行解Table 5 All feasible solutions of the first four disjunctive normal forms

(5)对于第五个析取范式，只需在上述的6个可行解的基础上寻找。

步骤1：将变量x2,x3,x4所代表的链X2,X3,X4通过链置换反应转换成Y链。化学反应如下(图12)：

步骤2：将步骤1所得的Y链进行相加。如可行解(这里的可行解存在于上述6个可行解中)(0,1,1,1,1)、(1,1,1,1,0)和(1,1,1,1,1)。

步骤3：将步骤2所得到的输出值和阈值进行比较来判断是否为可行解，具体可通过观察是否有荧光显示来判断。

通过上述步骤满足这个例子的可行解个数为6个，即(0,1,1,0,1)、(0,1,0,1,1)、(0,1,1,1,1)、(1,1,0,1,1)、(1,1,1,0,1)和(1,1,1,1,1)见表6和图13。

表6 满足这个例子的可行解Table 6 A feasible solution that satisfies this example

本文基于DNA链置换反应网络求解可满足性问题，利用Visual DSD进行了仿真。求解过程分成3个反应模块：变量转换模块、求和模块和阈值比较模块，除了求和模块外，其他2个模块都利用了DNA链置换反应。文中利用上述的3个反应模块具体解决了5个变量的可满足性问题，每个变量xi(i=1-5)分别代表着链Xi(i=1-5)经过变量反应模块得到Y链，再将Y链的浓度进行相加，最后和所设定的阈值进行比较，通过观察是否有荧光显示来判断，若有荧光显示则是可行解，否则不是，最终有6个可行解。

本文的设计思想不仅可以解决可满足性问题，还可以解决一些加权的问题，如整数规划问题，背包问题等。与之前的求解可满足计算模型相比适用范围更加广泛，适用于大范围的求解。利用Visual DSD得到了反应网络图和仿真结果，验证了该设计的可行性，阈值作为一种检验手段，通过观察是否有荧光来判断可行解，使得结果更明显直观。本文的设计为大规模求解提供了思路，关于大规模求解问题是后续的工作。

猜你喜欢 荧光阈值变量 土石坝坝体失稳破坏降水阈值的确定方法建材发展导向(2021年19期)2021-12-06基于小波变换阈值去噪算法的改进计算机仿真(2021年6期)2021-11-17抓住不变量解题小学生学习指导(高年级)(2021年4期)2021-04-29采用红细胞沉降率和C-反应蛋白作为假体周围感染的阈值临床骨科杂志(2020年1期)2020-12-12改进小波阈值对热泵电机振动信号的去噪研究智能计算机与应用(2020年4期)2020-08-31魔力荧光色小资CHIC！ELEGANCE(2018年28期)2018-09-14玛卡荧光碳点的合成及用于苦味酸的荧光检测分析化学(2016年12期)2017-02-04Fluorescence world荧光人间小资CHIC！ELEGANCE(2016年15期)2016-07-26分离变量法：常见的通性通法新高考·高二数学(2014年7期)2014-09-18不可忽视变量的离散与连续福建中学数学(2011年9期)2011-11-03