鞏成艷，殷志祥，趙鑫月

(安徽理工大學(xué) 數(shù)學(xué)與大數(shù)據(jù)學(xué)院，安徽 淮南 232001)

基于自組裝納米顆粒探針的全錯位排列問題的DNA計(jì)算模型

鞏成艷，殷志祥*，趙鑫月

(安徽理工大學(xué) 數(shù)學(xué)與大數(shù)據(jù)學(xué)院，安徽 淮南 232001)

全錯位排列問題是組合數(shù)學(xué)中的一類重要問題，可轉(zhuǎn)化為范式的形式，利用自組裝納米顆粒探針對滿足性問題進(jìn)行求解。將納米金顆粒和DNA序列進(jìn)行結(jié)合，形成納米金顆粒探針的識別區(qū)，并且成拱形結(jié)構(gòu)。當(dāng)識別區(qū)與其補(bǔ)鏈發(fā)生雜交反應(yīng)時，拱形結(jié)構(gòu)打開并發(fā)出熒光，從而給出了全錯位排列問題的一種新的DNA計(jì)算模型。與傳統(tǒng)的DNA計(jì)算模型不同，本文將納米技術(shù)和DNA計(jì)算理論相結(jié)合。

DNA計(jì)算；自組裝；納米顆粒；全錯位排列問題

1994年，美國的Adleman博士首次利用DNA編碼技術(shù)解決了具有7個頂點(diǎn)的有向哈密爾頓路徑問題，并首次提出DNA分子計(jì)算技術(shù)[1]。由于DNA分子計(jì)算技術(shù)具有巨大的并行性和非凡的信息密度等優(yōu)點(diǎn)，而高性能計(jì)算技術(shù)一直是計(jì)算機(jī)科學(xué)家的研究熱點(diǎn)，同時也滿足計(jì)算機(jī)技術(shù)發(fā)展的需要。近年來，研究者們對DNA分子計(jì)算技術(shù)進(jìn)行了一系列研究，用該技術(shù)解決了很多的復(fù)雜問題，如3-SAT問題、最大團(tuán)問題、騎士問題和最大獨(dú)立集問題等[2-6]。

全錯位排列問題是組合數(shù)學(xué)中的一類重要問題。孫俠給出了全錯位排列問題的基于表面[7]、基于芯片[8]和基于三鏈[9]的DNA計(jì)算模型。

納米材料近來被廣泛應(yīng)用于納米生物學(xué)領(lǐng)域。納米金顆粒已經(jīng)成為用于感測分析物最受歡迎的材料之一，因?yàn)樗苽浔阋耍休^好的穩(wěn)定性和生物相容性。此外，使用金屬顆粒作為“納米支架”和“納米猝滅劑”，這種一體化的生物傳感器結(jié)構(gòu)提供了傳統(tǒng)生物傳感系統(tǒng)不具備的優(yōu)點(diǎn)和應(yīng)用。納米金屬DNA序列的固定化技術(shù)也成熟，易于操作，納米顆粒與DNA序列的結(jié)合比生物傳感器具有更多優(yōu)勢[10-11]。在自組裝納米技術(shù)和DNA計(jì)算理論的基礎(chǔ)上，2009年Li在自組裝納米顆粒探針的基礎(chǔ)上，提出了解決0-1規(guī)劃問題的新的DNA計(jì)算模型[12]。2012年，Li又提出了SAT問題的新的DNA計(jì)算模型，也是第一次將納米顆粒與寡核苷酸結(jié)合到DNA計(jì)算模型中[13]。本文在此基礎(chǔ)上，給出了全錯位排列問題的新的DNA計(jì)算模型，將納米顆粒和寡核苷酸結(jié)合在一起。其本質(zhì)是給定問題的變量0或1的所有可能組合在自組裝納米顆粒探針的識別區(qū)域中編碼，通過靶序列的雜交來判斷不可行的解決方案。除了DNA計(jì)算的共同優(yōu)點(diǎn)，如巨大的并行性和非凡的信息密度，由于添加納米顆粒，所有的DNA分子都可以牢固地固定在表面上，在復(fù)雜問題中不需要更多的空間來完成計(jì)算，計(jì)算的連續(xù)性也不會被破壞。整個計(jì)算模型具有高可靠性、檢測快速和易于操作的優(yōu)點(diǎn)，這使得實(shí)際應(yīng)用成為可能。

1 全錯位排列問題的數(shù)學(xué)模型

全錯位排列問題也稱為“裝錯信封問題”。該問題可以用數(shù)學(xué)語言描述如下：

對于任一n元集合{1,2,…n}，當(dāng)滿足條件ij≠j(1≤j≤n)，所得的全排列i1i2…in為全錯位排列。也就是說全錯位排列是指沒有一個數(shù)字在它的自然順序位置上的全排列。本文以3元集合{1,2,3}的全錯位排列問題為例說明。即數(shù)字1,2,3沒有一個在各自的自然順序位置上的全排列。經(jīng)分析可得，存在3個原子命題：(1)數(shù)字1排在第二位上，記為x；(2)數(shù)字 2 排在第一位上，記為y；(3)數(shù)字3排在第一位上，記為z。它們的否命題分別為：表示數(shù)字1排在第三位；表示數(shù)字2排在第三位；表示數(shù)字3排在第二位。該問題需要滿足以下條件：(1)若數(shù)字1在第二位，則數(shù)字3不在第二位；(2)若數(shù)字2在第一位，則數(shù)字3不在第一位；(3)若數(shù)字1在第三位，則數(shù)字2不在第三位。該問題可以轉(zhuǎn)化為滿足性問題，命題如下：。

2 自組裝納米顆粒探針

自組裝納米顆粒探針是一種新型的納米生物傳感器。它可以同時識別和檢測特定的DNA序列和單堿基突變(無需洗滌或分離)。探針的核心是一個2.5 nm的納米金屬顆粒，可以作為有效的能量受體，即“納米支架”和“納米猝滅劑”。一端用硫醇基團(tuán)(-SH)標(biāo)記，一端用熒光團(tuán)標(biāo)記，在3'和5'末端插入T6間隔物(6個胸腺嘧啶)以減少空間位阻。根據(jù)之前的Raman散射研究的一個重要觀點(diǎn)，熒光團(tuán)可以可逆地吸附在膠體銀和納米金顆粒的表面。因此當(dāng)DNA序列與納米顆粒(SAu/Ag)牢固連接時，另一端的熒光團(tuán)將環(huán)回并且吸附在相同的顆粒上。然后由于單鏈DNA主鏈的不穩(wěn)定性而形成了拱形結(jié)構(gòu)，并且DNA鏈不與納米顆粒的表面接觸。在這種吸收(封閉)狀態(tài)下，熒光團(tuán)被納米顆粒猝滅，因?yàn)榈入x子體表面可以激發(fā)出顯著增加顆粒表面附近的電磁場，導(dǎo)致增強(qiáng)表面的Raman散射和熒光發(fā)射。當(dāng)添加自組裝納米顆粒探針的互補(bǔ)鏈時，發(fā)生雜交反應(yīng)后，拱形結(jié)構(gòu)開放，熒光團(tuán)離開表面，由于雙鏈DNA分子的穩(wěn)定性，并且恢復(fù)熒光，所以可以通過這種拱形結(jié)構(gòu)的封閉或開放狀態(tài)很容易地檢測到DNA雜交信號[14-15]如圖1。

圖1 納米顆粒探針的示意圖及其DNA識別和檢測的操作原理

3 全錯位排列問題的DNA計(jì)算模型

全錯位排列問題的DNA計(jì)算模型算法如下：

Step 1：合成DNA片段，把它們分成四組，第一組的DNA片段分別用來表示變量x1,x2,…,xn，第二組的DNA片段分別用來表示變量，第三組的DNA片段是第一組的補(bǔ)鏈，分別記為，第四組的DNA片段是第二組的補(bǔ)鏈，分別記為。生成探針庫，探針庫包含第一組和第二組的2n個DNA片段，并且可以產(chǎn)生2n種不同的組合。這些組合形成了自組裝納米顆粒探針的識別區(qū)，其具有n個變量的相應(yīng)的寡核苷酸，然后我們將納米金顆粒探針固定在表面上并排成一條線。

Step 2：在表面加入每個變量的互補(bǔ)鏈，發(fā)生雜交反應(yīng)后，拱形結(jié)構(gòu)打開，熒光團(tuán)與粒子表面分離，從而產(chǎn)生熒光信號，通過激光掃描共聚焦顯微鏡(LSCM)可以觀察到熒光信號，然后判斷探針組合是否滿足約束條件，對產(chǎn)物進(jìn)行加熱，清洗并去除變量的雜交互補(bǔ)鏈，記錄結(jié)果，找出可行解，排除不可行解。

Step 3：重復(fù)Step 2，記錄滿足約束不等式的所有解，排除所有不可行解，求解滿足所有約束不等式的解。

Step 4：比較與每個可行解對應(yīng)的對象函數(shù)的值，以獲得所有全錯位排列。

4 生物操作

全錯位排列問題的DNA計(jì)算模型的生物操作步驟如下：

Step 1：合成12種DNA片段，并把其分成四組。第一組的3種DNA片段分別用來表示變量x,y,z，第二組的3種DNA片段分別用來表示變量x',y',z'，第三組的3種DNA片段是第一組的補(bǔ)鏈，分別記為，第四組的 3 種 DNA 片段是第二組的補(bǔ)鏈，分別記為。變元編碼如表1所示。

在寡核苷酸3'端連接硫醇(-SH)基團(tuán)和5'端連接熒光團(tuán)，寡核苷酸可以通過共價鍵牢固地固定在納米金顆粒表面上。每個納米金顆?？梢赃B接兩個合成寡核苷酸，這樣可以提高序列的穩(wěn)定性和雜交效率。然后將所有自組裝的納米顆粒探針固定在表面并排列在一條線上，見圖2。

表1 變元編碼

圖2 用納米顆粒探針表示所有可能的組合

Step 3：對第二步的產(chǎn)物進(jìn)行加熱，清洗并去除變量的雜交互補(bǔ)鏈。對第二個析取項(xiàng)，加入y'和z'的互補(bǔ)鏈分別為和，進(jìn)行雜交反應(yīng)。通過激光掃描共聚焦顯微鏡（LSCM）觀察，找出哪個識別區(qū)域具有亮度，具有亮度的識別區(qū)域滿足使第二個析取式的值為1，拍照并記錄結(jié)果。找出可行解為101,010,001,000，排除非可行解111,011。

Step 4：對第三步的產(chǎn)物進(jìn)行加熱，清洗并去除變量的雜交互補(bǔ)鏈。對第三個析取項(xiàng)(x∨y)，加入x和y的互補(bǔ)鏈分別為和，進(jìn)行雜交反應(yīng)。通過激光掃描共聚焦顯微鏡(LSCM)觀察，找出哪個識別區(qū)域具有亮度，具有亮度的識別區(qū)域滿足使第三個析取式的值為1，拍照并記錄結(jié)果。找出可行解為101,010，排除非可行解001，000。加熱，清洗并去除變量的雜交互補(bǔ)鏈。

5 結(jié)論

本文提出了一種基于自組裝納米顆粒探針的新型DNA計(jì)算方法，以解決全錯位排列問題。其主要思想是通過把全錯位排列問題轉(zhuǎn)化為滿足性問題。該方法將問題中變量的所有可能組合編碼為自組裝納米顆粒探針識別區(qū)。通過添加變量的互補(bǔ)鏈，所有可能的解決方案是在靶序列雜交后并行產(chǎn)生的。所以可以借此比較和分析可行解。與以往的模型相比，本文將納米技術(shù)和DNA計(jì)算理論相結(jié)合，該模型最大的特點(diǎn)就是制備方便和檢測靈敏，這些特點(diǎn)使得該模型比以往的模型的可靠性更高，同時它還具有其它模型的高并行性和高存儲性等優(yōu)點(diǎn)。所以這個方法在某些方面推進(jìn)了DNA計(jì)算的發(fā)展。

[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]許 進(jìn)，張 雷.DNA計(jì)算機(jī)原理,進(jìn)展及難點(diǎn)(Ⅰ)：生物計(jì)算系統(tǒng)及其在圖論中的應(yīng)用[J].計(jì)算機(jī)學(xué)報，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]孫 俠，殷志祥，趙前進(jìn)，等.基于三鏈DNA結(jié)構(gòu)的全錯位排列問題算法[J].滁州學(xué)院學(xué)報，2012，14（2）：18-20.

[8]孫 俠，殷志祥，張家秀.全錯位排列問題的基于表面的DNA計(jì)算模型[J].生物數(shù)學(xué)學(xué)報，2009（3）：513-517.

[9]孫 俠，殷志祥，李 勇，等.全錯位排列問題的基于芯片的 DNA 計(jì)算模型[J].大學(xué)數(shù)學(xué)，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

國家自然科學(xué)基金項(xiàng)目(61672001)資助。

鞏成艷(1988- )，女，碩士生，研究方向：DNA計(jì)算。

殷志祥(1966- )，男，博士，教授，研究方向：圖與組合優(yōu)化、DNA計(jì)算。Email：zxyin66@163.com。