基于DNA计算的优先编码器逻辑分子实现

张新建, 寇 铮

(广州大学 计算科技研究院, 广东 广州 510006)

非传统计算机是一个蓬勃发展的领域，其中生物计算机在近些年得到了快速的发展.1994年美国南加州大学阿德拉曼博士开创性地提出用DNA解决计算问题[1]，解决了经典的组合优化问题——Hamiltonian路径问题，开启了人类利用DNA分子进行计算的新篇章.DNA计算通过控制DNA分子间的生化反应来完成运算，利用生物分子如DNA、RNA及酶等生物成分的独特性质[2-5]来进行信息编码、存储和计算操作.与传统计算机相比，生物计算机具有并行处理能力强、运算速度快及能耗小等特点，因而受到了科学家的广泛关注.DNA计算领域是最具活力和发展潜力的研究领域之一，二十多年的发展取得了大量令人瞩目的成果[6-10].

DNA链置换技术是DNA分子计算的基础之一[11], 因其操作性强、产物可预见等优点被广泛运用于DNA分子计算中.DNA 链置换技术的一个很重要的特点是其可级联性[12],上一级反应的输出可以作为下一级反应的输入，因此，能够实现大规模的化学反应网络.DNA链置换技术出现后，生物计算特别是DNA计算的研究得到了快速的发展.

基于分子逻辑计算单元实现各种分子门电路[13-15]是DNA链置换技术的重要应用场景.很多研究人员都提出了不同的分子逻辑门结构模型，Seeling等[16]首次利用DNA链置换设计出了各种数字逻辑电路.Frezza等[17]利用DNA链置换技术和荧光标记技术构建了与、或和非门，并在此基础上通过级联多种逻辑门来执行异或逻辑.Zhang等[18]使用单链的输入和输出实现了YES门、与门和或门操作.Qian等[19]提出了一种基于支点交换机制的“跷跷板”门结构，并实现了不同的逻辑门操作，并把这些逻辑门用于大规模DNA逻辑门级联的复杂电路[12]，开辟了复杂DNA分子逻辑电路的方向.

DNA链置换技术在多种领域内的研究方向都具有巨大的发展潜能和应用前景.本文基于阶跃函数分子逻辑门设计了一种DNA与非门，在此基础上，通过级联多个DNA与非门实现了一种基于DNA分子的4线-2线优先编码器，并使用Visual DSD软件对其可行性和准确性进行了仿真验证，仿真实验结果表明了DNA分子优先编码器的可行性，为复杂DNA分子电路的级联并实现信息的逻辑编码功能作出了探索.

1 优先编码器逻辑电路

逻辑电路以二进制数0和1表示高低电平进行离散信号的传输和处理，一般拥有若干个输入和输出端，输入信号不同时，能得到对应的输出信号.编码是将特定的逻辑信号编为一组二进制代码，能够实现编码功能的逻辑电路称为编码器.优先编码器是一种特殊的编码器，在拥有多个输入时，会按照输入信号的优先级进行输出，优先极高的输入信号将被输出，低优先级的信号将被忽略.优先编码器常用于处理最高优先级请求时控制中断请求.

本文设计的分子优先编码器由5个与非门构成，实现将4位输入信号变为2位的输出信号，每个输入信号拥有不同的优先级.该优先编码器拥有4个输入信号A，B，C，D，每次输入一个4位的二进制码代表输入信号，输出信号由一个2位的二进制数表示，其对应的真值表如表1所示.

表1 4线-2线优先编码器真值表Table 1 Truth table of 4-wire-2-wire priority encoder

假设A、B、C、D为输入信号，优先级顺序为A、B、C，D.当电路在同一时间有输入信号时，输出的是优先级别高的编码.1表示高电平，0表示低电平，X表示任意电平.用L0L1表示输出信号.L0L1=00表示无输入或者输入信号D，L0L1=01表示C输入，L0L1=10表示B输入，L0L1=11表示A输入.其表达式为

(1)

(2)

如图1所示，根据式(1)和式(2)设计出4线-2线优先编码器逻辑电路，ABCD表示输入信号，L0和L1表示输出信号.因为D无论取何值都不影响输出，所以D可以忽略.

图1 4线-2线优先编码器逻辑电路Fig.1 The logic circuit of 4-wire-2-wire priority encoder

2 优先编码器分子逻辑模型

2.1 DNA链置换

DNA链置换技术在生物分子计算中占据着重要的位置.DNA 链置换的全称是“基于支点调节的分支迁移和链置换反应”，遵循Yurke等[20-21]提出的支点隔离和支点交换法则，通过DNA单链与部分互补的双链之间产生反应，置换出原有双链中的单链，从而形成新的DNA双链，是一个自发的动态反应过程.链置换根据反应的方向可以分为可逆反应和不可逆反应，反应过程如图2所示.

图2 DNA链置换原理图示[22]Fig.2 Diagram of the principle of DNA strand replacement

有向线段代表DNA链，1、2、3代表DNA链上不同序列的域，域2和域2*代表互补DNA序列，域2只与其互补域2*反应.双链X在反应开始前存在于溶液中，并且X的域3*暴露在外.当单链A输入时，A链域3和双链域3*结合，并开始反应.根据支点分离和支点交换法则，输入链A的域2向双链X的上域2迁移，迁移后，双链X上的DNA序列1、2被替换，最终的DNA序列1、2形成输出链B，输入链A的剩余部分和双链X形成双链Y，反应结束.

2.2 分子与非门设计

本文根据Chen等[23]所提出的高灵敏度的精确DNA链置换逻辑门研究，设计了一种与非门.该与非门以信号链浓度为0.1 nM左右为低电平信号，信号链浓度为0.9 nM左右为高电平信号.与非门结构如图3所示.

图3 分子与非门逻辑结构Fig.3 The logic structure of molecular NAND gate

输入链信号A和B首先经过单分子反应[24]A→T1+T2和B→T1+T2产生信号链T1和T2.如果没有输入信号，即A和B的值为0，那么2个阶跃函数都不会被激活，没有信号产生；如果A和B的值均为低位信号0.1，那么信号链T1和T2的值等于0.2 nM，这时阈值为0.15的阶跃函数会被激活，输出信号Y的值为0.9 nM，表示高位信号；如果A和B有一个低位信号，有一个高位信号，那么T1和T2的值则为0.1+0.9=1.0 nM.这时阈值为0.15的阶跃函数会被激活，所以输出信号Y的值为0.9 nM，表示高位信号；如果A和B均为高位信号，那么T1和T2的值则为0.9+0.9=1.8 nM.这时阈值为1.5和0.15的阶跃函数会被激活，于是产生0.8 nM浓度的Y’信号链和0.9 nM浓度的Y信号链，Y和Y’将成对湮灭，最终只剩0.1 nM浓度的输出链Y，表示低位信号.

2.3 仿真实验与结果分析

本文使用 Visual DSD[25]进行设计和仿真DNA 链置换实验.Visual DSD软件广泛应用于DNA链置换反应的分析.本次实验使用软件提供的默认序列，其中支点域碱基长度为6，非支点域碱基长度为20，支点正相结合速率为0.003 nM-1s-1，逆向结合速率为1.3 s-1.反应结果如图4(a)～图4(d)所示.

图4 与非门仿真实验结果Fig.4 The simulation results of NAND gate

在与非门中，输入信号为00时，输出信号链浓度增长速度相对较慢，最终在浓度达到0.9时稳定下来.输入信号为01或者10时，输出链浓度快速增长到0.9 nM，然后到达一个稳态.当输入信号为11时，输出信号链浓度先快速增长到0.6 nM左右，然后浓度不断下降，达到0.1 nM后稳定下来.这是由于湮灭反应的原因，生成Y’链的反应相对于生成Y链的反应较慢，二者共同作用，形成了输出链浓度先上升后下降的状态.

2.4 优先编码器分子模型

由传统电路原理图转化为分子逻辑电路图，4线-2线优先编码器分子逻辑门模型如图5所示.

图5 4线-2线优先编码器分子逻辑门模型Fig.5 Molecular logic gate model of 4-wire-2-wire priority encoder

在图5的模型中，分子与非门代替了传统逻辑电路中的与非门.通过级联多个与非门得到了优先编码器.输入信号链为A、B、C、D，输出信号链为L1和L0.输入信号链A和B经过单分子反应生成相同浓度的两个信号链.分别经过与非门1和与非门2得到对应的输出信号YA和YB，YA与YB经过单分子反应生成中间链YA1、YA2、YB1、YB2.YA1与YB1通过与非门3生成最终输出信号链L0.YB2与输入链C经过与非门4反应后生成中间链YC.中间链YC和中间链YA2经过与非门5反应后到最终输出链L1.在逻辑电路中，虽然输入信号链D对输出结果没有任何影响，但是为了确保该分子电路的逻辑完整性而保留输入信号链D. 最终输入链A、B、C、D经过多个与非门后生成相对应的输出信号链.

4线-2线优先编码器的仿真实验如图6所示.和与非门类似，同样使用Visual DSD软件进行仿真实验，使用软件提供的默认序列，其中支点域碱基长度为6，非支点域碱基长度为20，支点正相结合速率为0.003 nM-1s-1，逆向结合速率为1.3 s-1.辅助链浓度为10 nM，浓度0.1 nM表示低电平信号，浓度0.9 nM表示高电平信号.

在图6的曲线中，图6(a)为输入信号ABCD为 0000时，输出信号L0和L1的浓度随时间变化曲线.L0和L1的稳态浓度为0.1 nM，代表输出信号00.图6(b)为输入信号ABCD为 1000时，输出信号L0和L1的浓度随时间变化曲线.L0和L1的稳态浓度为0.9 nM，代表输出信号11.图6(c)为输入信号ABCD为 0100时，输出信号L0和L1的浓度随时间变化曲线.L0稳态浓度为0.9 nM，L0稳态浓度为0.1 nM，代表输出信号10.图6(d)为输入信号ABCD为 0010时，输出信号L0和L1的浓度随时间变化曲线.L1稳态浓度为0.1 nM，L0稳态浓度为0.9 nM，代表输出信号01.仿真结果显示各种情况的输出信号均符合预期结果，表明该分子模型可以实现4线-2线优先编码器功能，证明了该分子电路模型的可行性与准确性.

图6 4线-2线优先编码器仿真实验结果Fig.6 The simulation results of 4-wire-2-wire priority encoder

3 结束语

综上所述，本研究基于DNA链置换反应，使用DNA分子阶跃函数逻辑门，构建了一种与非门分子逻辑运算器件，并通过级联多个分子与非门构建出一个DNA分子4线-2线优先编码器，可以实现相应分子逻辑门间的级联反应，最终实现了优先编码器的功能.通过Visual DSD软件进行仿真，验证了该模型实验的可行性和分子反应的准确性，仿真结果表明了本文构建的分子优先编码器具有逻辑电路简单、结果准确的特点.整个级联反应系统的仿真运行结果表明，本文设计的级联电路在大规模分子逻辑计算电路的应用方面有着很好的潜力.

在未来的研究中，可以使用这种逻辑电路来构建更复杂的结构模型，实现更强大的功能.例如，在生物计算机内作为生物处理器的中断控制器，用于检测最高优先级的输入信号.本文的工作期望在基于链置换的逻辑电路发展中做出有益的探索，为实现分子水平的可编程可控的智能纳米系统做出贡献.