基于自组装纳米颗粒探针的最小顶点覆盖问题的DNA计算模型

巩成艳，殷志祥，赵鑫月

(安徽理工大学数学与大数据学院，安徽淮南 232001)

基于自组装纳米颗粒探针的最小顶点覆盖问题的DNA计算模型

巩成艳，殷志祥，赵鑫月

(安徽理工大学数学与大数据学院，安徽淮南 232001)

DNA自组装技术为DNA计算的发展带来了一些新的启发。目前，解决各种NP完全问题的方法有多种多样的计算模型，其中有些是非常有用的，可以解决复杂的NP完全问题。在本文中，在自组装纳米颗粒探针的基础上，介绍了关于最小顶点覆盖问题的一种新的DNA计算模型。将给定问题的变量0或1所有可能的组合，编码在自组装纳米探针的识别区，通过靶序列的杂交来判断其可行解。相对于传统的DNA计算模型，该模型具有方便、灵敏、稳定性高的优点。

DNA计算；自组装；纳米颗粒；最小顶点覆盖问题

自从Adleman在哈密尔顿路径问题[1]上的开创性工作以来，基于DNA的计算领域已经有了许多研究成果。采用DNA计算方法可用来解决许多组合优化问题，比如可满足问题[2]、最大团问题[3]、最大独立集问题[4]等。

最小顶点覆盖(MVC)问题出现在各种重要应用中，包括计算生物化学中的多个序列比对、信息检索和调度问题等，探索一种更有效的解决最小顶点覆盖问题的方法有实际意义。2004年，高林、许进给出了解决最小顶点覆盖问题的DNA分子算法[5]；2006年，周康、许进给出了解决最小顶点覆盖问题的闭环DNA算法[6]；同年，X.Xu和J.Maxw给出了解决最小顶点覆盖问题的模拟退火算法[7]；2008年，宁爱兵等给出了解决最小顶点覆盖问题的快速降解算法[8]；2010年，金婷婷等给出了解决最小顶点覆盖问题的竞争决策算法[9]；2011年，Zhang X等用三维自组装模型解决最小顶点覆盖问题等[10]。

基于以上研究背景，Fei Li等在自组装纳米颗粒探针的基础上提出了解决0-1规划问题和SAT问题的新的DNA计算模型[11-12]，也是第一次将纳米颗粒与寡聚核苷酸结合到DNA计算模型中。本文在此DNA计算模型基础上探讨最小顶点覆盖问题。

1 图的最小顶点覆盖问题

1.1 图的最小顶点覆盖定义

基本定义：给定一个简单无向图G=(V,E)，K是顶点集V的一个子集，并且每条边都至少有一个顶点在K中，那么称K是图G的一个顶点覆盖。如果G不存在覆盖K′使得|K′|<|K|，那么覆盖K称为G的最小顶点覆盖。简而言之，图的最小顶点覆盖是指在给定的图中找到一个顶点最小集，使得其能覆盖给定的图的所有边。

对于任意一个有n个顶点、m条边的无向图G=(V,E)，令G(v)={v1,v2,…,vn}，可以用n位二进制数来表示顶点的子集(变量的值仅能取0和1)，且变量的下标对应顶点的顺序。若二进制数的第i位值为1，则表示vi存在于该最小顶点覆盖K中；若二进制数的第i位值为0，则表示vi不存在于该最小顶点覆盖K中。事实上，最小顶点覆盖问题都可以转化为特殊的0-1规划问题，找到相对应的目标方程和约束条件，最小顶点覆盖问题可以转化为下面的等式。

minU=x1+x2+…+xn.

(1)

(2)

称式(1)为最小顶点覆盖的目标方程，式(2)为最小顶点覆盖的约束方程。

1.2 算法步骤

根据以上的分析，算法步骤如下：

步骤一，生成给定问题的变量取值为0或1的所有可能组合；

步骤二，使用每个约束条件排除所有非可行解，找出可行解；

步骤三，根据约束条件继续重复步骤二和步骤三，可以排除所有的非可行解，从而可以得到满足问题的所有可行解；

步骤四，通过比较各可行解对应的目标函数值，进而可以得到最优解。

2 自组装纳米颗粒探针的最小顶点覆盖问题的DNA计算模型

2.1 纳米金颗粒探针

纳米金颗粒已经成为近十年来人们最感兴趣的材料之一，纳米金颗粒已经在许多领域得到广泛的研究，比如分析化学。纳米金颗粒具有独特的光学、电学和催化性质，容易通过改变尺寸、形状、组成和环境将其控制。纳米金颗粒DNA探针是由小的纳米金颗粒和荧光标记的寡聚核苷酸构成的。根据之前的增强表面的拉曼散射(SERS)研究表明，荧光染料可以可逆地吸附在胶体银和纳米金颗粒的表面上[13-14]。当寡聚核苷酸分子通过共价键(硫-金属键)牢固地吸附在颗粒表面时，远端的荧光团可以循环返回吸附在相同的颗粒上。单链DNA的构象是灵活的，呈现一个有利的拱形结构。寡聚核苷酸3′和5′的末端都连接到颗粒上，但DNA链不接触到表面。图1显示纳米颗粒探针的示意图及其DNA识别和检测的操作原理。这种约束的构象导致三个重要结果：第一，通过非辐射能量转移到金颗粒，荧光团被高效地完全猝灭，非辐射能量转移到金颗粒；第二，暴露的寡聚核苷酸序列可用于特异性杂交；第三，预期杂交特异性比线性探针更高。在金胶体的情况下，分子“循环”在颗粒表面上导致弯曲的DNA构象作为一个中间状态增加杂交特异性。加入靶目标可打开约束构象并使荧光团从颗粒表面分离。类似于分子信标，我们还注意到，分子识别仅来自附着的配体，但金纳米晶体在与硫醇基团和荧光团相互作用中起着重要的结构作用，其连接到寡聚核苷酸的两端，核苷酸分子这种相互作用发生在纳米尺度上，对于将寡核苷酸组织成颗粒表面的拱状构象是至关重要的[15]。

图1 纳米颗粒探针的示意图及其DNA识别和检测的操作原理示意图

2.2 生物操作

利用第一组和第二组的DNA序列可以构造2n种探针，每个探针的识别区包含n个变量所对应的寡聚核苷酸，在寡聚核苷酸3′端连接上硫醇基团，5′端连接上荧光基团。然后利用杂交的方法将它们固定在纳米金颗粒的表面上，使之在一条线上，即纳米金颗粒探针。

步骤二，根据约束方程的变量，把变量对应的补链添加到表面上，从而发生杂交反应，纳米金颗粒探针会产生荧光。通过激光扫描共聚焦显微镜观察，然后判断纳米金颗粒探针对应的解是否满足该约束方程，找出可行解，拍照保存。加热表面解开双链，清洗去除探针的杂交互补链。

步骤三，根据约束方程继续重复步骤二，记录满足约束方程的所有可行解，排除不可行解。然后把可行解代入目标函数，求出最优解。

3 实例分析

图2 图题

现以图2为例，详细叙述具体的操作过程。首先找到图2的最小顶点覆盖相对应的目标函数和约束条件，如式(3)(4)所示。

minU=x1+x2+x3+x4.

(3)

(4)

使用自组装纳米颗粒探针的DNA计算模型的操作方法如下：

表1 DNA序列编码

在寡聚核苷酸3′端连接上硫醇基团(-SH)，5′端连接上荧光基团，然后通过共价键寡聚核苷酸可以牢固地固定在纳米金颗粒的表面上。每个纳米金颗粒可以和两个合成的寡聚核苷酸整合，然后将所有的自组装纳米颗粒探针固定在表面上并排成一条线(图3)。

图3 所有的纳米金探针

步骤六，通过上面的操作，可以得到满足约束方程组的所有可行解，代入目标函数，可求出目标函数的最优解有0110，1001两个，对应的目标函数的最小值为2。同时可以得到图的最小顶点覆盖为{1,4}和{2,3}。

4 结论

DNA计算具有高存储密度和大规模并行性，在解决困难问题尤其是NP完全问题上很有潜力。本文介绍了一种基于自组装纳米颗粒探针的新的DNA计算方法，可以解决最小顶点覆盖问题，其主要思想是通过把最小顶点覆盖问题转化为0-1规划问题。DNA序列与纳米金颗粒结合形成纳米金颗粒探针，当加入DNA序列的补链时，会发生杂交反应，产生荧光，从而判断该问题的可行解，求出给定问题的最小顶点覆盖。该模型方便、灵敏、稳定性高，随着纳米技术和DNA计算的发展，其他更多的NP完全问题可能会由这个模型解决。

[1]Adleman L M.Molecular computation of solutions to combinatorial problems[J].Science,1994,266(5187):1021.

[2]Lipton R J.DNA solution of hard computational problems[J].Science,1995,268(5210):542.

[3]Ouyang Q,Kaplan P D,Liu S,et al.DNA solution of the maximal clique problem[J].Science,1997,278(5337):446.

[4]Liu Q,Wang L,Frutos A G,et al.DNA computing on surfaces[J].Nature,2000,403(6766):175-179.

[5]高琳,许进.最小顶点覆盖问题的DNA分子算法[J].系统工程与电子技术,2004,26(4):544-548.

[6]周康,许进.最小顶点覆盖问题的闭环DNA算法[J].计算机工程与应用,2006,42(20):7-9.

[7]Xu X,Ma J.Letter:An efficient simulated annealing algorithm for the minimum vertex cover problem[J].Neurocomputing,2006,69(7):913-916.

[8]宁爱兵,马良,熊小华.最小顶点覆盖快速降阶算法[J].小型微型计算机系统,2008,29(7):1282-1285.

[9]金婷婷,王波,宁爱兵.最小顶点覆盖问题的竞争决策算法[J].计算机工程与应用,2011,47(1):32-34.

[10]Zhang X,Song W,Fan R,et al.Three dimensional DNA self-assembly model for the minimum vertex cover problem[C].Fourth International Symposium on Computational Intelligence and Design,IEEE,2011:348-351.

[11]Li F,Liu J,Li Z.DNA computation model based on self-assembled nanoparticle probes for 0-1 integer programming problem[C].International Conference on Bio-Inspired Computing,Bic-Ta,IEEE,2009:1-4.

[12]Li F,Xu J,Li Z.DNA computing model based on self-assembled nanoparticle probes for SAT problem[J].Advanced Materials Research,2012(443-444):513-517.

[13]Yuan Z,Hu C C,Chang H T,et al.Gold nanoparticles as sensitive optical probes[J].Analyst,2016,141(5): 1611-1626.

[14]Ikegami K,Sugano K,Isono Y.Surface-enhanced Raman spectroscopy analysis of DNA bases using arrayed and single dimer of gold nanoparticle[C].International Conference on MICRO Electro Mechanical Systems,IEEE,2017.

[15]Zhang L,Li Z,Xu X,et al.Effect of mixed thiols on the adsorption,capacitive and hybridization performance of DNA self-assembled monolayers on gold[J].Journal of Solid State Electrochemistry,2016,20(8):2153-2160.

DNAComputingModelBasedonSelf-assembledNano-particleProbesSolvingtheMinimumVertexCoverageProblem

GONG Cheng-yan, YIN Zhi-xiang, ZHAO Xin-yue

(Mathematics and Big Data Institute, Anhui University of Science and Technology, Huainan Anhui 232001, China)

DNA self-assembly technology has brought some new insights into the development of DNA computing. At present, there are a variety of computational models for solving various NP-complete problems, some of which are very useful and can solve complex NP-complete problems. In this paper, a new DNA computing model with minimal vertex coverage problem is introduced on the basis of self-assembled nano-particle probes. All the possible combinations of variables 0 or 1 of the given problem are encoded in the recognition region of the self-assembled nano-particle probes, and the feasible solution is judged by the hybridization of the target sequence.Compared with the traditional DNA calculation model, the model is convenient, sensitive and stable.

DNA computing; self-assembled; nano-particle; minimum vertex coverage problem

TP301.6

A

2095-7602(2017)12-0029-05

2017-06-14

国家自然科学基金项目“基于分子信标微流控芯片的大数据存储与挖掘”(61702008)；国家自然科学基金项目“DNA自组装模型在生物传感器设计中的研究与探索”(61672001)。

巩成艳(1988- )，女，硕士研究生，从事DNA计算研究。

殷志祥(1966- )，男，教授，博士，从事图与组合优化、DNA计算研究。