利用DNA链的相对浓度求解背包问题

崔建中,殷志祥,杨 静

(1. 安徽理工大学电气与信息工程学院, 安徽 淮南 232001; 2.淮南联合大学计算机系, 安徽 淮南 232038; 3.安徽理工大学数学与大数据学院, 安徽 淮南 232001)

DNA链置换是一种新颖的动态自组装技术。利用DNA链置换来设计纳米级的智能装置是目前纳米技术、DNA自组装等许多领域的研究热点。文献[1]基于链置换设计了可‘行走’的DNA镊子。文献[2]利用链置换实现了Hopfield神经网络，可在分子尺度上进行识别、决策。文献[3]利用链置换设计了一种分子运输装置，可顺时针或逆时针旋转。文献[4]利用两种发夹结构的DNA作为模板，线性结构的DNA单链诱发链置换，设计了纳米尺度的键盘锁。文献[5]首次在自组装模型中将DNA链置换和荧光标记结合，解决了0-1规划问题。DNA 电路由于其高度的可编程性和多功能性而被广泛用于开发生物计算设备，因此文献[6]提出基于DNA链置换的模拟计算DNA电路系统。文献[7]提出了统计推理模型，使用链置换实现该模型，并模拟求解了“Read your mind”。

早期的DNA自组装主要围绕着以DNA分子作为组装材料，通过设计DNA编码，依据碱基互补配对规则，DNA分子会自发形成具有一定刚性的初级结构，并以此结构作为基本单元，进一步组装成具有一定几何形状的二维、或三维结构。近年来出现的DNA链置换技术是建立在反应的动力学平衡基础上，具有原理简单，反应过程可编程，易模块化，可灵活地组成级联电路等特点，从而引起了来自多学科众多学者广泛的关注[8-12]。

本文基于链置换，提出了利用DNA链的浓度来判断某种0-1组合是否为可行解的计算模型。该计算模型将背包问题的约束条件转化为对应数据池中不同种DNA链的浓度，根据可行解不会产生荧光来并行地搜索所有可行解，最终得到背包问题的最优解。该模型尝试解决目前DNA计算领域存在的问题，如：计算的中间结果需要多次分离、需要人工干预计算过程，从而造成计算的自动化程度低。这些问题的解决必定会大大提高DNA计算的可靠性和所求问题的规模。

1 链置换

支点介导的DNA链置换(Toehold-Mediated DNA strand displacement)按反应过程分为两类：不可逆链置换和可逆链置换。其中不可逆链置换是指， 输入DNA链与模板链的支点(Toehold)结合，随后分支迁移(Branch Migration)结合模板的识别序列，置换出模板上已杂交的链的过程。可逆链置换是指多条DNA链竞争结合与之互补的模板链。原理如图1所示。图中实心、空心箭头表示反应的方向。

图1 可逆链置换反应的原理示意图

为方便讨论，引入记号<…>来表示单链。如在图1中，DNA链5’-2-T-1-3’(左上)，省略5’和3’端、并保留链的极性，简记为<2，T，1>。有时为突出某条链上的一段序列，用不带<…>符号的字母或数字表示该序列，如支点序列T*。输出链<3，T，2>先与模板链结合形成部分双链的结构。图中T*为T的补(右上)。该结构中，输出链的序列3仍是单链，中间是T2序列形成的双链部分，模板链5’端的T*序列为单链，记该结构为<3，2∶2*>，冒号代表该部分形成双链(省略了双链中支点序列和模板5’端的支点序列)。因为可逆链置换中，支点序列的编码是唯一的。链<3，T，2>结合<3，2∶2*>的支点T*(图1第二行)，随后发生分支迁移逐渐结合识别序列2*(图1第三行)，置换出链<3，T， 2>， 同时形成<2∶2*，1>。冒号的位置表示在新的DNA链中，序列1在3’端。该反应过程在图1中用实心箭头表示。随着反应进行，链<2，T，1>数量不断减少，被置换出的链<3，T，2>数量逐渐增加，链置换反向进行，直至动力学平衡，该反应过程在图1中用空心箭头表示。将可逆链置换用动力学方程表示如下

<2，T，1>+<3，2∶2*>⟺<3，T，2>+<2∶2*，1>

链置换反应的速率可通过支点的长度和序列组成进行调控。研究结果表明，支点长度为0～6个碱基时，反应的速率呈指数增加，并在6个碱基时达到最大。另外，支点的序列组成中，G/C含量越高，反应速率越快。巧妙地设计支点的长度，序列组成及链的相对浓度可以对反应进行较精确地控制，如图2所示。

图2 支点长度控制反应原理示意图

(1)若<2，T，1>C小于<2∶2*>C

<2，T，1>+<3，2∶2*>+<2∶2*>⟹<3，2∶

(2) 若<2，T，1>C大于<2∶2*>C

可逆链置换组成级联电路进行运算时，往往要求需要对链进行放大，且放大倍数能根据问题的要求灵活地设置。图3给出了利用DNA链的相对浓度来实现对输入链放大ω倍的原理。

图3 输入链的放大

图3中，链<2，T，1>作为输入链，<3，T，2>作为输出链，引入燃料链<4，T，2>，它与输入链、输出链竞争模板链。图3第2行给出了输入链<2，T，1>置换输出链<3，T，2>，图3第3行给出了燃料链<4，T， 2>反向置换输入链<2，T， 1>。设输入链的初始浓度为1×，输出链与模板链的初始浓度为ω×(ω>1)，燃料链的初始浓度为2ω×。未加入输入链时，输出链与模板链形成的结构<3，2∶2*>与燃料链<4，T，2>稳定共存。加入输入链时，诱发链置换。输入链每次置换出一条输出链，燃料链再次将输入链反向置换出来。输出链也参与竞争模板链。 但由于燃料链的相对浓度大于输出链，反应更倾向燃料链。达到动力学平衡时，输入链的相对浓度几乎不变，仍然为1×， 燃料链近似为(2ω-ω)×，输出链<3，T， 2>从结构<3，2∶2*>中置换出，相对浓度近似为ω×，燃料链与模板形成结构<4，2∶2*>的相对浓度近似为ω×。上述输入链放大ω倍可用动力学方程表示如下

目前链置换的研究主要是设计组合电路的基本单元，用这些单元搭建电路来实现特定的功能，如自然数素性判定问题[13]、编码器逻辑运算[14]。利用链置换来求解组合优化问题，国内还鲜见报道。本文提出了一种背包问题的计算模型，模型的初始数据池中仅有O(n)种单链DNA，荧光判解，计算过程可自动进行，无需人工干预。

2 背包问题的计算模型

背包问题由Dantzig在1956年提出，是组合优化中一个NP-难问题。2014年，文献[15]利用三链结构相对更稳定的特点，给出该问题的DNA三链计算模型。

背包问题描述为：给定一个可容纳重量为c的背包和n种物品，每种物品的重量为ωi(i=1，2，…，n)单价为pi(i=1，2，…，n)。设若物品i被选择放入背包，则xi=1；否则xi=0(i=1，2，…，n)。如何选择物品使背包的总价最高? 即

(1)

xi=0，1

下面讨论(1)所对应的背包问题的算法。

步骤1：编码；

步骤2：根据背包问题的约束条件确定每种链的相对浓度，建立初始数据池；

步骤3：对每种可能的物品选择，根据荧光判断是否为可行解；

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

对应算法的步骤4，将可行解对应的目标函数加以比较，最终得到所给背包问题的最优解。

3 结论

生物计算模型的空间复杂度用DNA链的种类来衡量。对于本文提出的背包问题的计算模型，需要编码3n+3种寡聚核苷酸片断，利用这些编码合成2n+3种链DNA构成初始数据池，数据池中DNA链种类正比于背包问题所含变量个数。 因此， (1)该模型的空间复杂度为O(n)； 为判断某0-1组合是否为可行解，需要将表示该0-1组合的DNA链被加入到数据池诱发链置换，再根据是否会产生荧光来判断该组合是否为可行解。所有解的判断可并行完成。在这一过程中，计算的中间结果无须分离、计算过程可自动完成，无须人工干预。因此，(2)该模型的时间复杂度是O(1)；另外，由于该模型仅使用了DNA链置换和荧光读解这两种相对成熟的生物技术，因而(3)该模型的可靠性高。

本文对组合优化中一个NP-难问题、背包问题给出了链置换的计算模型。该计算模型将背包问题的约束条件转化为对应数据池中不同种DNA链的浓度，根据可行解不会产生荧光来并行地搜索所有可行解，最终得到背包问题的最优解。