巩成艳，殷志祥，赵鑫月

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

基于自组装纳米颗粒探针的全错位排列问题的DNA计算模型

巩成艳，殷志祥*，赵鑫月

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

全错位排列问题是组合数学中的一类重要问题，可转化为范式的形式，利用自组装纳米颗粒探针对满足性问题进行求解。将纳米金颗粒和DNA序列进行结合，形成纳米金颗粒探针的识别区，并且成拱形结构。当识别区与其补链发生杂交反应时，拱形结构打开并发出荧光，从而给出了全错位排列问题的一种新的DNA计算模型。与传统的DNA计算模型不同，本文将纳米技术和DNA计算理论相结合。

DNA计算；自组装；纳米颗粒；全错位排列问题

1994年，美国的Adleman博士首次利用DNA编码技术解决了具有7个顶点的有向哈密尔顿路径问题，并首次提出DNA分子计算技术[1]。由于DNA分子计算技术具有巨大的并行性和非凡的信息密度等优点，而高性能计算技术一直是计算机科学家的研究热点，同时也满足计算机技术发展的需要。近年来，研究者们对DNA分子计算技术进行了一系列研究，用该技术解决了很多的复杂问题，如3-SAT问题、最大团问题、骑士问题和最大独立集问题等[2-6]。

全错位排列问题是组合数学中的一类重要问题。孙侠给出了全错位排列问题的基于表面[7]、基于芯片[8]和基于三链[9]的DNA计算模型。

纳米材料近来被广泛应用于纳米生物学领域。纳米金颗粒已经成为用于感测分析物最受欢迎的材料之一，因为它制备便宜，有较好的稳定性和生物相容性。此外，使用金属颗粒作为“纳米支架”和“纳米猝灭剂”，这种一体化的生物传感器结构提供了传统生物传感系统不具备的优点和应用。纳米金属DNA序列的固定化技术也成熟，易于操作，纳米颗粒与DNA序列的结合比生物传感器具有更多优势[10-11]。在自组装纳米技术和DNA计算理论的基础上，2009年Li在自组装纳米颗粒探针的基础上，提出了解决0-1规划问题的新的DNA计算模型[12]。2012年，Li又提出了SAT问题的新的DNA计算模型，也是第一次将纳米颗粒与寡核苷酸结合到DNA计算模型中[13]。本文在此基础上，给出了全错位排列问题的新的DNA计算模型，将纳米颗粒和寡核苷酸结合在一起。其本质是给定问题的变量0或1的所有可能组合在自组装纳米颗粒探针的识别区域中编码，通过靶序列的杂交来判断不可行的解决方案。除了DNA计算的共同优点，如巨大的并行性和非凡的信息密度，由于添加纳米颗粒，所有的DNA分子都可以牢固地固定在表面上，在复杂问题中不需要更多的空间来完成计算，计算的连续性也不会被破坏。整个计算模型具有高可靠性、检测快速和易于操作的优点，这使得实际应用成为可能。

1 全错位排列问题的数学模型

全错位排列问题也称为“装错信封问题”。该问题可以用数学语言描述如下：

对于任一n元集合{1,2,…n}，当满足条件ij≠j(1≤j≤n)，所得的全排列i1i2…in为全错位排列。也就是说全错位排列是指没有一个数字在它的自然顺序位置上的全排列。本文以3元集合{1,2,3}的全错位排列问题为例说明。即数字1,2,3没有一个在各自的自然顺序位置上的全排列。经分析可得，存在3个原子命题：(1)数字1排在第二位上，记为x；(2)数字 2 排在第一位上，记为y；(3)数字3排在第一位上，记为z。它们的否命题分别为：表示数字1排在第三位；表示数字2排在第三位；表示数字3排在第二位。该问题需要满足以下条件：(1)若数字1在第二位，则数字3不在第二位；(2)若数字2在第一位，则数字3不在第一位；(3)若数字1在第三位，则数字2不在第三位。该问题可以转化为满足性问题，命题如下：。

2 自组装纳米颗粒探针

自组装纳米颗粒探针是一种新型的纳米生物传感器。它可以同时识别和检测特定的DNA序列和单碱基突变(无需洗涤或分离)。探针的核心是一个2.5 nm的纳米金属颗粒，可以作为有效的能量受体，即“纳米支架”和“纳米猝灭剂”。一端用硫醇基团(-SH)标记，一端用荧光团标记，在3'和5'末端插入T6间隔物(6个胸腺嘧啶)以减少空间位阻。根据之前的Raman散射研究的一个重要观点，荧光团可以可逆地吸附在胶体银和纳米金颗粒的表面。因此当DNA序列与纳米颗粒(SAu/Ag)牢固连接时，另一端的荧光团将环回并且吸附在相同的颗粒上。然后由于单链DNA主链的不稳定性而形成了拱形结构，并且DNA链不与纳米颗粒的表面接触。在这种吸收(封闭)状态下，荧光团被纳米颗粒猝灭，因为等离子体表面可以激发出显著增加颗粒表面附近的电磁场，导致增强表面的Raman散射和荧光发射。当添加自组装纳米颗粒探针的互补链时，发生杂交反应后，拱形结构开放，荧光团离开表面，由于双链DNA分子的稳定性，并且恢复荧光，所以可以通过这种拱形结构的封闭或开放状态很容易地检测到DNA杂交信号[14-15]如图1。

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

3 全错位排列问题的DNA计算模型

全错位排列问题的DNA计算模型算法如下：

Step 1：合成DNA片段，把它们分成四组，第一组的DNA片段分别用来表示变量x1,x2,…,xn，第二组的DNA片段分别用来表示变量，第三组的DNA片段是第一组的补链，分别记为，第四组的DNA片段是第二组的补链，分别记为。生成探针库，探针库包含第一组和第二组的2n个DNA片段，并且可以产生2n种不同的组合。这些组合形成了自组装纳米颗粒探针的识别区，其具有n个变量的相应的寡核苷酸，然后我们将纳米金颗粒探针固定在表面上并排成一条线。

Step 2：在表面加入每个变量的互补链，发生杂交反应后，拱形结构打开，荧光团与粒子表面分离，从而产生荧光信号，通过激光扫描共聚焦显微镜(LSCM)可以观察到荧光信号，然后判断探针组合是否满足约束条件，对产物进行加热，清洗并去除变量的杂交互补链，记录结果，找出可行解，排除不可行解。

Step 3：重复Step 2，记录满足约束不等式的所有解，排除所有不可行解，求解满足所有约束不等式的解。

Step 4：比较与每个可行解对应的对象函数的值，以获得所有全错位排列。

4 生物操作

全错位排列问题的DNA计算模型的生物操作步骤如下：

Step 1：合成12种DNA片段，并把其分成四组。第一组的3种DNA片段分别用来表示变量x,y,z，第二组的3种DNA片段分别用来表示变量x',y',z'，第三组的3种DNA片段是第一组的补链，分别记为，第四组的 3 种 DNA 片段是第二组的补链，分别记为。变元编码如表1所示。

在寡核苷酸3'端连接硫醇(-SH)基团和5'端连接荧光团，寡核苷酸可以通过共价键牢固地固定在纳米金颗粒表面上。每个纳米金颗粒可以连接两个合成寡核苷酸，这样可以提高序列的稳定性和杂交效率。然后将所有自组装的纳米颗粒探针固定在表面并排列在一条线上，见图2。

表1 变元编码

图2 用纳米颗粒探针表示所有可能的组合

Step 3：对第二步的产物进行加热，清洗并去除变量的杂交互补链。对第二个析取项，加入y'和z'的互补链分别为和，进行杂交反应。通过激光扫描共聚焦显微镜（LSCM）观察，找出哪个识别区域具有亮度，具有亮度的识别区域满足使第二个析取式的值为1，拍照并记录结果。找出可行解为101,010,001,000，排除非可行解111,011。

Step 4：对第三步的产物进行加热，清洗并去除变量的杂交互补链。对第三个析取项(x∨y)，加入x和y的互补链分别为和，进行杂交反应。通过激光扫描共聚焦显微镜(LSCM)观察，找出哪个识别区域具有亮度，具有亮度的识别区域满足使第三个析取式的值为1，拍照并记录结果。找出可行解为101,010，排除非可行解001，000。加热，清洗并去除变量的杂交互补链。

5 结论

本文提出了一种基于自组装纳米颗粒探针的新型DNA计算方法，以解决全错位排列问题。其主要思想是通过把全错位排列问题转化为满足性问题。该方法将问题中变量的所有可能组合编码为自组装纳米颗粒探针识别区。通过添加变量的互补链，所有可能的解决方案是在靶序列杂交后并行产生的。所以可以借此比较和分析可行解。与以往的模型相比，本文将纳米技术和DNA计算理论相结合，该模型最大的特点就是制备方便和检测灵敏，这些特点使得该模型比以往的模型的可靠性更高，同时它还具有其它模型的高并行性和高存储性等优点。所以这个方法在某些方面推进了DNA计算的发展。

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

[2]Bach E,Condon A,Glaser E,et al.DNA models and algorithmsforNP-completeproblems[C]//Proceedings,1996：290-300.

[3]许 进，张 雷.DNA计算机原理,进展及难点(Ⅰ)：生物计算系统及其在图论中的应用[J].计算机学报，2003，26（1）：1-11.

[4]Oliver J S.Computation with DNA-matrix multiplication[J].Princeton University,1996：113-122.

[5]Sakamoto K,Gouzu H,Komiya K,et al.Molecular computation by DNA hairpin formation[J].Science,2000,288(5469)：1223-1226.

[6]Lipton R J.Using DNA to Solve NP-Complete Problems[J].Science,1995,268：542--545.

[7]孙 侠，殷志祥，赵前进，等.基于三链DNA结构的全错位排列问题算法[J].滁州学院学报，2012，14（2）：18-20.

[8]孙 侠，殷志祥，张家秀.全错位排列问题的基于表面的DNA计算模型[J].生物数学学报，2009（3）：513-517.

[9]孙 侠，殷志祥，李 勇，等.全错位排列问题的基于芯片的 DNA 计算模型[J].大学数学，2010，26（5）：79-82.

[10]Cao Y,Jin R,Mirkin C A.DNA-modified core-shell Ag/Au nanoparticles[J].Journal of the American Chemical Society,2001,123(32)：7961-7962.

[11]Maxwell D J,Taylor J R,Nie S.Self-assembled nanoparticle probes for recognition and detection of biomolecules[J].Journal of the American Chemical Society,2002,124(32)：9606-9612.

[12]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,2009.Bic-Ta.IEEE,2009：1-4.

[13]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.

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

[15]Zhang L L,Li Z G,Xu X Y,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.

DNA computing model based on self-assembled nanoparticle probes solving whole error permutation problem

GONG Cheng-yan,YIN Zhi-xiang*,ZHAO Xin-yue
(Mathematics and Big Data Institute,Anhui University of Science and Technology,Huainan Anhui232001,China)

The whole error permutation problem is a kind of important problem in combinatorial mathematics.In this paper,the problem can be transformed into a normal form,and the Satisfiability Problem is solved by self-assembled nanoparticle probes.The gold nanoparticle and the DNA sequence are combined to form the recognition area of the gold nanoparticle probes and have arched structure.When the recognition region and its complementary chain occurs hybridization reaction,the arch structure opens and emits fluorescence,which gives a new DNA computing model with whole error permutation problem.Different from conventional DNAcomputation model,both nano technology and DNAcomputation theory are used in this paper.

DNAcomputing;self-assembled;nanoparticle;whole error permutation problem

TP301

A

1004-4329（2017）03-064-04

10.14096/j.cnki.cn34-1069/n/1004-4329（2017）03-064-04

2017-05-25

国家自然科学基金项目(61672001)资助。

巩成艳(1988- )，女，硕士生，研究方向：DNA计算。

殷志祥(1966- )，男，博士，教授，研究方向：图与组合优化、DNA计算。Email：zxyin66@163.com。