基于DNA步行者求解最小顶点覆盖问题的计算模型

赵鑫月, 殷志祥

(1. 蚌埠学院 理学院, 安徽 蚌埠 233030; 2. 安徽理工大学 数学与大数据学院, 安徽 淮南 232001;3. 上海工程技术大学 数理与统计学院, 上海 201620)

DNA作为遗传信息的载体，其精确的碱基配对原则、序列的可编程性、结构的多样性和可控性等优势，被认为是最有前途的一类分子机器构造材料[1].DNA步行者是一类以DNA为构筑元件设计并制备的可执行复杂操作的分子机器，能够控制纳米尺度的目标物沿预设轨道进行机械运动，在生物传感、生物成像、新材料组装与合成及生物计算等领域有着极大的应用前景.

DNA步行者最初是由Sherman等[2]于2004年设计的，由三股突出的单链DNA构成一条一维(1D)轨道.2006年，Pei等[3]利用DNA步行者可以在DNA折纸或DNA修饰平面组成的二维轨道上移动，提出了二维(2D)折纸轨道.在科研人员的不懈努力下，DNA步行者已由最初一维轨道上的步行运动，发展到后来的二维折纸轨道运动[4-11]，乃至当前基于纳米粒子的三维轨道上运动[12].2015年，Ellington课题组通过把发夹型DNA链修饰在微球表面组装成三维轨道，设计了一种新型三维DNA纳米机器[13].2017年，Jiang课题组报道了一种构筑在磁性纳米微球上的三维步行者分子机器[14].2018年，Li课题组将发夹结构作为DNA步行链，切口酶识别位点位于发夹的环中，设计了一种切口酶驱动的DNA步行者分子机器[15].2019年，Wang等[16]利用滚环扩增技术构建了多种酶驱动的DNA步行者，用于高灵敏生物传感器.

最小顶点覆盖问题是图论中的一个经典问题，不仅在数理逻辑和开关理论等方面有重要的研究地位，而且在分子生物学、调度问题、邮轮行程安排等实际生产领域都有着很高的应用价值.2005年，董亚非等[17]提出了解决最小顶点覆盖问题的粘贴模型.2009年，羊四清等[18]提出了最小顶点覆盖的表面计算模型.2011年，Zhang等[19]利用三维自组装模型解决了最小顶点覆盖问题.2017年，巩成艳等[20]在自组装纳米颗粒探针的基础上，设计了一种新型的最小顶点覆盖问题的 DNA 计算模型.

本文将三维DNA 步行者应用于解决最小顶点覆盖问题，该模型将步行DNA链固定在磁性纳米微球表面构造出全部顶点覆盖，并加入DNA发夹探针，形成包含G-四链体结构单元的双链DNA，以删除掉与每边相关的一个顶点，产生所有覆盖的补集，再加入荧光探针N-甲基卟啉二丙酸(NMM)特异性识别G-四链体结构，产生荧光，最终得到最小顶点覆盖.该模型将轨道构建于磁性纳米粒子，具有较大的表面积、并行性好、灵敏度高和运行效率更快的特点，可以解决规模更大、更为复杂的最小覆盖问题.

1 最小顶点覆盖问题

图的顶点覆盖问题是指找出给定图中顶点的一个最小子集，图中任意一条边的两个端点都至少有一个属于该子集.给定简单无向图G=(V,E)，其中顶点集V(G)={v1,v2,…,vn}，边集E(G)={e1,e2,…,en}.设K是V(G)的一个子集，并且图G的每条边都至少有一个端点在K中，则称K是G的一个覆盖.如果G中不存在|K′|<|K|的覆盖K′,则称K是G的最小顶点覆盖.

2 计算模型

2.1 模型的组成

图1 DNA步行轨道Fig.1 DNA walking track

图2 链的组成与结构Fig.2 Composition and structure of chain

2.2 算法

步骤2以每条边为约束，在DNA折纸基底上删除掉与边相关联的一个顶点，经过m次删除试验后，产生所有覆盖的补集.

(1)取k=1.

图3 步骤2(3)的反应过程Fig.3 The reaction process diagram of Step 2 (3)

(4)令k=k+1重复(2)(3)，直到k=m得到的数据池Tm+1中任何一个磁性纳米颗粒上不会同时含有任何一条边相关联的两个顶点所对应的发夹结构，即每个折纸基底都对应一个最小顶点覆盖的补集.

步骤3 在透射电镜显微镜下观察，选择数据池中发夹结构最多的磁性纳米微球，加入荧光探针N-甲基卟啉二丙酸(NMM)，荧光探针N-甲基卟啉二丙酸(NMM)会对双链DNA的G-四链体结构特异性进行识别，并嵌入到G-四链体中，产生强烈的荧光，点亮纳米微球.该磁性纳米微球上未发生反应的发夹结构对应最小顶点覆盖的补集，而磁性纳米微球上产生荧光的G-四链体双链对应的就是最小顶点覆盖.

整个过程的操作原理示意图如图4所示.

图4 操作原理示意图Fig.4 Schematic diagram of operation principle

3 实例分析

现以简单无向图G=(V,E)的最小顶点覆盖问题为例(图5)，说明该算法的正确性和有效性.图G中V={v1,v2,v3,v4}，E={e1,e2,e3,e4,e5}.使用三维DNA步行者计算模型操作如下：

图5 简单无向图GFig.5 Simple undirected graph G

步骤1将编码引发链I和4种发夹结构的DNA依次固定在磁性纳米微球表面(图6)，作为初始数据池T1={(v1v2v3v4)}.编码5种辅助链及其相应的补链，再设计5种DNA发夹探针.

图6 初始数据池中的DNA步行轨道Fig.6 DNA walking track in the initial data pool

步骤2

(2)k=2，取出e2=v1v3，得到数据池T3={(0v2v3v4),(00v3v4)，(0v20v4),(v100v4)}.

(3)k=3，取出e3=v2v3，得到数据池T4={(00v3v4),(v100v4)，(0v20v4),(000v4)}.

(4)k=4，取出e4=v2v4，得到数据池T5={(00v3v4),(v100v4)，(000v4),(00v30),(v1000)，(0v200),(0000)}.

(5)k=5，取出e5=v3v4，得到数据池T6={(v100v4)，(v1000),(0v200),(00v30),(000v4)，(0000)}，如图7所示.

图7 数据池T6中的磁性纳米微球Fig.7 Magnetic nanospheres in data pool T6

步骤3在透射电镜显微镜下观察，选择发夹结构最多的磁性纳米微球{(v100v4)}，加入荧光探针N-甲基卟啉二丙酸(NMM).该磁性纳米微球上的发夹结构对应最小的顶点覆盖补集{v1,v4}，产生荧光的G-四链体双链对应的就是最小顶点覆盖{v2,v3},如图8所示.

图8 最小顶点覆盖所在的磁性纳米微球Fig.8 Magnetic nanospheres with minimal vertex coverage

4 结 论

本文应用DNA步行者求解最小顶点覆盖问题，提出了最小顶点覆盖的三维DNA步行者计算模型.在磁性纳米颗粒上构筑的三维轨道，具有较大的表面积，可以装载高密度的DNA轨道，使分子机器所能行走的步数更多，运行效率更高.反应后用荧光探针N-甲基卟啉二丙酸(NMM)特异性识别G-四链体结构，得到最小顶点覆盖，灵敏度高，读解更简单.将DNA步行者的核心思想应用于组合优化问题的求解，不仅拓宽了DNA步行者的应用领域，也为解决组合优化问题提供了一种新的思路和方法.虽然该模型有很多优点，但是问题仍然存在：反应过程中，数据池中的磁性纳米颗粒之间可能会发生错配，从而可能影响结果的准确性.相信随着纳米技术和DNA计算的快速发展，该问题可以得到解决.