基于DNA域编码的余三码四位减法器的设计

黄 春 郭毅飞 张新雅 孙军伟 王英聪 李盼龙 王延峰

(郑州轻工业大学电气信息工程学院 郑州 450002)

1 引言

受摩尔定律制约，硅基电子计算机在高性能计算方面的发展遇到了瓶颈[1]，为了解决工程领域内规模日益扩大的困难类问题，人们开始寻求各种物理化学材料上的突破[2,3]。1994年，美国著名科学家Adleman博士[4]运用DNA分子成功地解决了“最小旅行商”问题，自此DNA作为一种新的载体不断地用于解决各种复杂计算问题，并逐渐在分子逻辑运算[5]、非线性系统[6]、生物传感器[7]、DNA纳米机器[8,9]、智能载药[10]及复杂疾病靶向治疗[11]等领域得到了应用。DNA自组装技术[12]、PCR技术[13]、链置换技术[14,15]、荧光标记结果提取[16]技术为DNA计算[17]的实现提供了灵活的设计工具，尤其是DNA链置换技术，它依据沃森-克里克碱基互补配对准则，精准、动态地展示了信息的交互过程，且全程实验无需催化酶的参与，常温下就可以完成，在构建大规模复杂分子电路方面展现了巨大的潜能。2011年，钱璐璐等人[18]提出了基于DNA链置换原理构造分子逻辑电路的方法，并应用双轨策略解决了非门不稳定的难题，设计了当时学术界最为复杂的4位平方根求解电路。双轨策略一度得到了研究者们的肯定，并在分子逻辑电路设计中广泛应用。而随着研究的不断深入，越来越多的功能性复杂的大规模逻辑电路需要构建、封装、级联，以便实现更为丰富的逻辑功能，而双轨分子逻辑电路虽然解决了由于浓度引起的非门不稳定问题，但是设计相同逻辑功能的分子电路所需的门电路的个数是其单轨数字电路的两倍，且随着电路规模的扩大，分子器件成倍增加，从而导致分子逻辑电路的复杂度、系统反应物的数量以及响应时间大大增加，因此，从分子电路的长远发展来看，双轨策略反而成为构建更大规模分子逻辑电路的障碍。

最近，研究者在改善分子逻辑电路响应速度及复杂度方面作出了尝试，Song等人[19]以简化逻辑门结构为目标，引入催化酶，采用单链作为逻辑门，但仍基于双轨策略构建分子逻辑电路，虽然电路的复杂度及响应时间有所改善，可是由于酶的活性很容易受到温度、湿度、pH值等环境因素的影响，实验操控较难，且经济成本较高，不易在大规模级联分子电路的设计中推广。2020年，Wang等人[20]提出基于开关电路实现数字运算的设计思想，针对双轨策略进行革新，电路设计中不存在非门电路，通过调整开关浓度满足级联分子电路信号的浓度需求，为DNA分子逻辑电路的设计提供了更有效的方案。但是，随着电路规模的增大，所需开关数量也会随之变多，有可能造成开关浓度与输出结果链的浓度相差几十、几百倍，甚至更大，这样DNA分子的正交特性有所下降，反而会限制功能性大规模电路的实现。本文针对DNA分子双轨策略电路复杂度高、系统响应时间慢等问题，提出了一种基于域编码策略构建DNA分子逻辑电路的方法，在DNA分子的固定位置设计特异性域，通过对域的编码实现信号链的逻辑值，从根本上消除由浓度所引起的非门不稳定性问题，并在此基础上应用Cardelli链代数理论[21]，实现DNA链代数与DNA结构的互译，同时将该理论用于构造“多输入1输出”逻辑运算模块，该模块不仅具有良好的并行性与封装性，而且集成度高，扩展性强，编程特性显著，在构造大规模分子逻辑电路设计方面更具有优势，是构造DNA分子逻辑电路的主要器件。为了进一步解析域编码策略在构建大规模复杂分子逻辑电路方面的设计思想，本文构造了2-输入和3-输入逻辑运算模块，以及扇出门和放大器，并在此基础上搭建了“余三码四位减法器”，利用Visual DSD软件[22]对其进行了仿真测试，仿真结果验证了该方法的可行性。域编码策略进一步加深了模块化思想构建大规模分子电路的理念，为设计更多的复杂DNA逻辑电路提供了新思路，有望促进DNA计算机的发展。

2 域编码逻辑运算模块的设计

2.1 域编码规则

域编码DNA信号链具有固定的结构，根据域的编码不同，可由4条DNA单链组成，如图1所示，它们以小支点T为中心分为左右两部分，左侧部分可与上游信号链相同域部分进行互补配对，右侧部分决定每条单链的逻辑值，DNA单链上的域a和域b为可编码域，域a代表逻辑值0，域b代表逻辑值1。例如DNA单链(a, a)，以小支点T为中心，分为左侧域＜uL^ a uR^＞和右侧域＜vL^ a vR^＞，右侧域的编码“a”代表此链的逻辑值为“0”，其他3条DNA单链结构框架一致，区别在于接收上游信息链和代表逻辑值上有所不同，DNA单链(a, b)代表逻辑值为“1”，DNA单链(b, a)代表逻辑值为“0”，DNA单链(b, b)代表逻辑值为1。

图1 域编码DNA信号链逻辑值的定义

2.2 基于域编码的多输入1输出逻辑运算模块

此处采用域编码策略，同时融入映射原理，设计了多输入1输出逻辑运算模块。这些模块是构造大规模复杂分子逻辑电路的基础，其功能的种类由输入信号的数量决定，若输入信号的数量为n，则运算模块双链为2n条，可实现2n种逻辑功能。此处主要阐释了1输入逻辑运算模块，2输入逻辑运算模块，3输入逻辑运算模块的工作原理，是本文后续分子逻辑电路的主要构成器件。

2.2.1 1输入逻辑运算模块

1输入逻辑运算模块由1条域编码输入链、2条域编码双链组成，双链结构如图2(a)所示。双链左侧域编码分别为a, b，可用来接收上游结构域相同的编码链，右侧域z1, z2∈{a, b}，对应变量取值有22=4种映射情况，每一种映射可代表一种逻辑功能。当z1=b, z2=a时，可实现输入信号的取反操作，实现逻辑非功能；当z1=a, z2=b时，可得到与输入信号相同的DNA逻辑信号，实现YES门的功能；当z1=a, z2=a时，无论输入信号是逻辑0还是逻辑1，输出信号均为0，具有清0的功能；当z1=b,z2=b时，无论输入信号是逻辑0还是逻辑1，输出信号均为1，具有置1的功能。为了便于检测输出链，后续分子电路搭建中均加入了域编码荧光报告门，如图2(b)所示，其主要作用是将输出链的浓度转为荧光信号输出。

逻辑非门是数字电路中常用的门电路，此处以非门功能为例分析其工作原理，如图2(c)所示，一输入模块双链1与输入链A0发生链置换反应，生成中间产物链0和OUT0，由域编码规则可知，输入链A0表示逻辑0，得到的目标链OUT0表示逻辑值1，实现了“非”逻辑功能。同理，可将表示逻辑1的输入链A1转换为代表逻辑0的目标链OUT1。

图2 1输入逻辑运算模块、域编码荧光报告门的信号链及非门功能的实现

2.2.2 2输入逻辑运算模块

2输入逻辑运算模块由2条输入链、4条域编码双链组成，双链结构如图3(a)所示，双链左侧域排列为(a, a), (a, b), (b, a), (b, b)，右侧链上的z1,z2, z3, z4域可取24=16种映射情况，每一种映射对应一种逻辑功能。例如当z1=a, z2=a, z3=a,z4=b时，可实现逻辑与功能；当z1=a, z2=b,z3=b, z4=b时，可实现逻辑或功能；当z1=a,z2=b, z3=b, z4=a时，可实现异或功能等，所有具有2输入1输出特点的逻辑功能电路都可以使用2输入逻辑运算模块来实现。

此处以2输入与门为例分析2输入逻辑运算模块的工作原理，如图3(c)所示，代表逻辑值1的输入链B0与输入链B1被输入到模块中，图中4条2输入模块双链在整个反应过程中并行参与反应，实际只有双链4反应后得到所需结果。首先双链4与输入链B0发生链置换反应，生成中间产物链1和一条废料，中间产物链1接着又与输入链B1产生反应，输出代表逻辑值1的目标链OUT。根据与门的逻辑功能，输出结果正好为逻辑值1，该模块实现了2输入与门的功能。图3(b)为其对应的Visual DSD仿真图，这里初始物种的浓度设定为1X nM(X=104nM)，同样为便于检测输出，这里加入了域编码荧光报告门，将输出链的浓度转为荧光信号输出。从仿真图中可看出，代表输入链B0的浓度和输入链B1的浓度在10 s内迅速下降到0.5X nM以下，目标链OUT的浓度在300 s时达到1X nM并进入稳态，代表输出逻辑值为1，成功实现了与逻辑功能。其他3种输入情况与这种情况类似，不再做重复说明。

图3 2输入逻辑运算模块的组成及与门功能的实现

2.2.3 3输入逻辑运算模块

3输入逻辑运算模块由8条DNA双链组成，双链结构如图4所示。DNA双链左侧域编码可取(aaa), (aab), (aba), (abb), (baa), (bab), (bba),(bbb)8种情况，右侧链上的z1, z2, z3, z4, z5, z6,z7, z8可取28种映射情况，对应实现256种不同的逻辑功能。如当z1=a, z2=b, z3=b, z4=a, z5=b,z6=a, z7=a, z8=b时，可实现全加器求和值(全减器求差值)的逻辑功能，当z1=a, z2=a, z3=a,z4=b, z5=a, z6=b, z7=b, z8=b时，可记录加法运算时产生的进位信号，当z1=a, z2=b, z3=a,z4=a, z5=b, z6=b, z7=a, z8=b时，可记录减法运算时产生的借位信号。所有具有3输入1输出特点的逻辑电路均可使用3输入逻辑运算模块来实现。基于以上构造多输入1输出逻辑运算模块的方法，可根据电路需求构造任意n输入逻辑运算模块。

图4 3输入逻辑运算模块

3 域编码扇出门与域编码放大器

在分子逻辑电路中，经常会出现同一条DNA信号链需要与不同的逻辑模块进行运算，为保证各个逻辑模块独立反应且互不干扰，需要将同一条信号链转换为多条逻辑值相同的信号链，然后再输送到各个逻辑模块。为解决这个问题，此处设计了域编码扇出门，可将一条域编码单链扇出多条与其逻辑值相同的DNA链。以域编码2-扇出门为例阐释扇出门的工作原理，图5(a)为逻辑0与逻辑1的2-扇出门双链，它们分别由2条扇出门双链和1条燃料链组成，其主要区别在于信号链上的域编码不同。

图5(b)为域编码2-扇出门的反应过程，扇出门双链的初始浓度设置与输入链浓度相同，为保证充分反应，燃料链的浓度始终设置为扇出门双链浓度的2倍。如图所示，代表逻辑0的输入链分别与扇出门双链1和扇出门双链2发生反应后，扇出两条均代表逻辑值0的单链1和单链2，并得到一条中间产物链，这条中间产物链与燃料链1发生反应后重新生成了输入链，整个反应过程中，输入链没有被消耗，相当于催化剂的作用，只要有少许催化即可扇出域编码单链。基于以上扇出门的工作原理，可根据电路需求获取多种域编码扇出门，如3-扇出门、4-扇出门及n-扇出门等。

图5 域编码2-扇出门信号链及反应过程

DNA链的浓度在反应过程中会发生衰减，而DNA链浓度的大小直接影响其反应速率及DNA分子系统的稳定性与产出率，故本文设计了域编码放大器，可将衰减的DNA链的浓度放大到目标值，并根据反应需求可在任意位置添加。域编码放大器的信号链如图6(a)所示，它主要由域编码放大器双链和燃料链组成，其主要区别在于域的编码不同。域编码放大器的整个反应过程如图6(b)所示，放大器双链的初始浓度与输入链浓度相同，放大器燃料链的浓度设定为放大器双链浓度的2倍。图6(b)中代表逻辑值0的输入链C0与放大器双链1发生链置换反应，生成中间产物链和输出链OUT，中间产物链又与放大器燃料链1发生反应，重新置换出输入链C0，输入链C0在这里只充当了催化剂作用，输出链OUT与输入链C0的逻辑值相同，其浓度与放大器双链的浓度相同，此过程相当于在保持逻辑值不变的情况下，域编码输入链的浓度被成功放大，而另外一条代表逻辑值1的放大器双链2没有参与反应。

图6 域编码放大器信号链及反应过程

4 域编码策略与双轨策略的对比

此处采用域编码策略实现了4位平方根分子电路，通过与双轨策略对比，进一步挖掘了域编码策略在分子电路设计中的优势。4位平方根电路是一种求取4位二进制数平方根的逻辑电路，输入信号设为A3A2A1A0，输出信号设为Y1Y0，其电路如图7所示，这里需要用到4个逻辑非门、2个3输入逻辑与门、1个2输入逻辑或门和1个2输入逻辑与门，对应上述域编码逻辑运算模块思想，这里应用1输入、2输入和3输入逻辑运算模块来实现4位平方根的求解。

图7 求取4位平方根的逻辑原理图

4位平方根分子电路搭建中使用了3个域编码扇出门，对部分输入链执行了扇出操作，得到了多条逻辑值相同的信号链。考虑到DNA链浓度在反应中会逐渐衰减，输出结果的浓度达不到预期，这里使用了2个域编码放大器来放大输出浓度。为便于更好地检测输出结果，这里加入了4个域编码荧光报告门，输出结果分别由Y00,Y01,Y10,Y11的4条荧光链来表示，Y00,Y10代表输出逻辑“0”，Y01,Y11代表输出逻辑“1”。

图8为域编码设计的4位平方根分子电路在DSD软件中的仿真结果，反应物的初始浓度设定为1X nM(1X=104nM)，初始反应物数量61种，绑定速率与解绑速率分别为3.0e-4 nM-1s-1和0.1126 s-1。从仿真图中可看到，输出链经过荧光报告门后输出不同的颜色，图8(a)输出Y10(黄线)和Y00(蓝线)代表结果“00”，图8(b)输出Y10(黄线)和Y01(红色)代表结果“01”，图8(c)输出Y11(紫线)和Y00(蓝线)代表结果“10”，图8(d)输出Y11(紫线)和Y01(红线)代表结果“11”，它们在50 s内达到1X nM并进入稳定状态，反应速度很快且结果正确。与Qian等人[18]在2011年发表在Nature上的求取4位平方根双轨电路以及DSD仿真做对比，物种的初始参数设为一致的情况下，域编码策略设计的4位平方根分子电路，所需的初始反应物由130种下降到了61种，反应时间降低为双轨平方根电路的1/24，电路搭建结构更简单，输出结果稳定，进一步验证了域编码模块化设计方法的可行性。

图8 基于域编码逻辑运算模块设计的4位平方根仿真图

5 余三码的4位二进制减法器的设计及仿真

基于域编码策略及多输入1输出逻辑运算模块原理，本文设计了更复杂的余三码4位二进制减法器。余三码是一种BCD码，它是在8421BCD码的基础上将每个代码加上(0011)B而形成的一种无权码，它的每个字符编码比8421码正好多3。在执行十进制数的加法运算时，若两数之和为十进制数10，用余三码作加法运算后得到二进制数10000，高位自动产生进位，为计算机的代数运算带来了便捷，但是“和值位”需要校正，若无进位，结果减3，若有进位，结果加3。在进行减法运算时，若无借位，结果加3，若有借位，结果减3。

图9为4位二进制余三码进行减法运算的逻辑电路，它主要由4个全减器FS和4个全加器FA组成，由于DNA链浓度仍会在逐层反应中衰减，在输出端对结果链使用了5个域编码放大器来提高输出链的浓度，放大器部分体现在了DSD程序中。图9中A3A2A1A0为被减数，B3B2B1B0为减数，H4H3H2H1H0为来自低位的借位信号，E3E2E1E0为全减器FS的运算结果，D3D2D1D0为修正全减器FS结果的修正信号，Y3Y2Y1Y0为最终的减法结果，I4I3I2I1I0为来自低位的进位信号。全减器FS的功能采用上述的3输入逻辑运算模块来实现，全减器在进行一位二进制数相减时，除考虑减法运算外，还需要考虑低位向高位的借位运算，故用3个输入端输入被减数、减数以及借位信号，用2个输出端输出差值结果和借位结果。这里使用2个3输入逻辑运算模块构成一个全减器FS，其中一个3输入逻辑运算模块实现本位差运算，简称差值模块，另一个实现借位运算，简称借位模块。差值模块由8条DNA双链组成，结构如图4所示，将双链上的z域编码改为 (a, b, b, a, b, a, a, b)可进行减法运算，借位模块也用8条与差值模块结构相同的双链组成，将双链z域的编码改为 (a, b, a, a, b, b, a, b)可记录借位结果。为得到正确的余三码减法结果，在实现全减器功能后加入全加器FA对差值结果修正，全加器FA由2个3输入逻辑运算模块构成，其中一个3输入模块实现本位和运算，简称和值模块，另一个3输入模块实现进位运算，简称进位模块。和值模块由8条DNA双链组成，链结构及域编码与全减器的差值模块相同，进位模块也由8条DNA双链组成，链结构与和值模块相同，其链上的z域编码改为(a, a, a, b, a, b, b, b)，即可记录进位结果。

图9 余三码4位二进制减法器逻辑图

以十进制数5的余三码1000与十进制2的余三码0101减法运算为例，表1为输入与输出的DNA信号链及其对应的逻辑值。被减数1000的信号链分别由A3A2A1A0表示，减数0101的信号链分别由B3B2B1B0表示，最低位借位信号链由H0表示，它们通过差值模块和借位模块先进行减法运算，运算后输出4条差值结果链E3E2E1E0，代表差值结果为0011，4条借位结果链H4H3H2H1，代表借位结果为0111。根据余三码的特点可知上一步的差值结果0011不是减法结果3的余三码，需要进一步加3修正才可得到正确结果。这里加入3输入逻辑运算模块实现的全加器来完成修正，当完成第1步减法运算后，在减法结果的基础上加入数值3的修正链D3D2D1D0和最低位的进位信号链I0，它们与上一步4条差值结果链E3E2E1E0进行加法运算和进位运算，最终获得修正结果，即结果3的余三码0110，分别由荧光信号链Y30,Y21, Y11, Y00来表示，I40表示修正运算后最高位的进位信号链。

表1 DNA信号链及逻辑值

图10为4位二进制余三码减法器的DSD仿真图，输入链的初始浓度设置为1X nM(1X=104nM)，绑定速率设定为3.0×10-4nM-1s-1，解绑速率设定为0.1126 s-1，反应时间设置为6000 s。输出结果链的浓度经过了5个域编码放大器放大，同时为了区分不同信号链的逻辑值，加入了5个域编码荧光报告门，每个输出结果的逻辑值均有两条不同颜色的荧光链来表示。余三码减法器最终的输出结果用5条荧光链表示，分别为I40(荧蓝线)，Y30(玫红线)，Y21(红线)，Y11(紫线)，Y00(蓝线)，它们在4000 s处达到1X nM后进入稳定状态，代表进位结果I40=“0”和减法运算结果Y30Y21Y11Y00=“0110”，而Y31, Y20, Y10及Y01输出与横轴重合的荧光曲线，代表无逻辑输出。此仿真结果与理论计算结果一致，验证了用域编码策略搭建余三码减法器的正确性。

图10 余三码4位二进制减法器仿真图

6 结束语

本文针对双轨分子逻辑电路复杂度高、响应时间慢等问题，提出一种基于DNA链置换技术的域编码策略，设计了多输入1输出分子逻辑运算模块，以及扇出门和放大器等用于提高分子电路稳定性的集成电路。其中多输入1输出逻辑运算模块具有良好的封装性和高效的执行效率，且功能强大，一个模块可以实现多个逻辑功能。若输入数量为n，则电路能够实现2n种逻辑功能，同时举例验证了“1输入逻辑运算模块”具有逻辑非门、YES门，以及清零和置一的功能，“2输入逻辑运算模块”具有逻辑与、或、异或、同或等功能。紧接着，本文基于以上逻辑运算模块，设计了域编码4位平方根电路，并在相同实验条件下，与传统的双轨策略下的4位平方根电路比较，结果表明：域编码策略的平方根电路运行速度仅为双轨策略分子电路的1/24，反应物的参与量也减少了接近50%，大大提高了分子逻辑运算电路的执行效率。为了进一步解析域编码策略设计大规模电路的设计思想，此处利用“3输入逻辑运算模块”实现了基本的“全加、全减”模块，并利用该模块设计了更为复杂的余三码四位全减器，其仿真结果达到了预期效果，表明了逻辑运算模块在分子逻辑电路设计中的可扩展性、简洁性和灵活性，为设计大规模功能性逻辑电路提供了新方法。