鞏成艷，殷志祥，趙鑫月

(安徽理工大學數學與大數據學院，安徽淮南 232001)

基于自組裝納米顆粒探針的最小頂點覆蓋問題的DNA計算模型

鞏成艷，殷志祥，趙鑫月

(安徽理工大學數學與大數據學院，安徽淮南 232001)

DNA自組裝技術為DNA計算的發(fā)展帶來了一些新的啟發(fā)。目前，解決各種NP完全問題的方法有多種多樣的計算模型，其中有些是非常有用的，可以解決復雜的NP完全問題。在本文中，在自組裝納米顆粒探針的基礎上，介紹了關于最小頂點覆蓋問題的一種新的DNA計算模型。將給定問題的變量0或1所有可能的組合，編碼在自組裝納米探針的識別區(qū)，通過靶序列的雜交來判斷其可行解。相對于傳統(tǒng)的DNA計算模型，該模型具有方便、靈敏、穩(wěn)定性高的優(yōu)點。

DNA計算；自組裝；納米顆粒；最小頂點覆蓋問題

自從Adleman在哈密爾頓路徑問題[1]上的開創(chuàng)性工作以來，基于DNA的計算領域已經有了許多研究成果。采用DNA計算方法可用來解決許多組合優(yōu)化問題，比如可滿足問題[2]、最大團問題[3]、最大獨立集問題[4]等。

最小頂點覆蓋(MVC)問題出現在各種重要應用中，包括計算生物化學中的多個序列比對、信息檢索和調度問題等，探索一種更有效的解決最小頂點覆蓋問題的方法有實際意義。2004年，高林、許進給出了解決最小頂點覆蓋問題的DNA分子算法[5]；2006年，周康、許進給出了解決最小頂點覆蓋問題的閉環(huán)DNA算法[6]；同年，X.Xu和J.Maxw給出了解決最小頂點覆蓋問題的模擬退火算法[7]；2008年，寧愛兵等給出了解決最小頂點覆蓋問題的快速降解算法[8]；2010年，金婷婷等給出了解決最小頂點覆蓋問題的競爭決策算法[9]；2011年，Zhang X等用三維自組裝模型解決最小頂點覆蓋問題等[10]。

基于以上研究背景，Fei Li等在自組裝納米顆粒探針的基礎上提出了解決0-1規(guī)劃問題和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規(guī)劃問題，找到相對應的目標方程和約束條件，最小頂點覆蓋問題可以轉化為下面的等式。

minU=x1+x2+…+xn.

(1)

(2)

稱式(1)為最小頂點覆蓋的目標方程，式(2)為最小頂點覆蓋的約束方程。

1.2 算法步驟

根據以上的分析，算法步驟如下：

步驟一，生成給定問題的變量取值為0或1的所有可能組合；

步驟二，使用每個約束條件排除所有非可行解，找出可行解；

步驟三，根據約束條件繼續(xù)重復步驟二和步驟三，可以排除所有的非可行解，從而可以得到滿足問題的所有可行解；

步驟四，通過比較各可行解對應的目標函數值，進而可以得到最優(yōu)解。

2 自組裝納米顆粒探針的最小頂點覆蓋問題的DNA計算模型

2.1 納米金顆粒探針

納米金顆粒已經成為近十年來人們最感興趣的材料之一，納米金顆粒已經在許多領域得到廣泛的研究，比如分析化學。納米金顆粒具有獨特的光學、電學和催化性質，容易通過改變尺寸、形狀、組成和環(huán)境將其控制。納米金顆粒DNA探針是由小的納米金顆粒和熒光標記的寡聚核苷酸構成的。根據之前的增強表面的拉曼散射(SERS)研究表明，熒光染料可以可逆地吸附在膠體銀和納米金顆粒的表面上[13-14]。當寡聚核苷酸分子通過共價鍵(硫-金屬鍵)牢固地吸附在顆粒表面時，遠端的熒光團可以循環(huán)返回吸附在相同的顆粒上。單鏈DNA的構象是靈活的，呈現一個有利的拱形結構。寡聚核苷酸3′和5′的末端都連接到顆粒上，但DNA鏈不接觸到表面。圖1顯示納米顆粒探針的示意圖及其DNA識別和檢測的操作原理。這種約束的構象導致三個重要結果：第一，通過非輻射能量轉移到金顆粒，熒光團被高效地完全猝滅，非輻射能量轉移到金顆粒；第二，暴露的寡聚核苷酸序列可用于特異性雜交；第三，預期雜交特異性比線性探針更高。在金膠體的情況下，分子“循環(huán)”在顆粒表面上導致彎曲的DNA構象作為一個中間狀態(tài)增加雜交特異性。加入靶目標可打開約束構象并使熒光團從顆粒表面分離。類似于分子信標，我們還注意到，分子識別僅來自附著的配體，但金納米晶體在與硫醇基團和熒光團相互作用中起著重要的結構作用，其連接到寡聚核苷酸的兩端，核苷酸分子這種相互作用發(fā)生在納米尺度上，對于將寡核苷酸組織成顆粒表面的拱狀構象是至關重要的[15]。

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

2.2 生物操作

利用第一組和第二組的DNA序列可以構造2n種探針，每個探針的識別區(qū)包含n個變量所對應的寡聚核苷酸，在寡聚核苷酸3′端連接上硫醇基團，5′端連接上熒光基團。然后利用雜交的方法將它們固定在納米金顆粒的表面上，使之在一條線上，即納米金顆粒探針。

步驟二，根據約束方程的變量，把變量對應的補鏈添加到表面上，從而發(fā)生雜交反應，納米金顆粒探針會產生熒光。通過激光掃描共聚焦顯微鏡觀察，然后判斷納米金顆粒探針對應的解是否滿足該約束方程，找出可行解，拍照保存。加熱表面解開雙鏈，清洗去除探針的雜交互補鏈。

步驟三，根據約束方程繼續(xù)重復步驟二，記錄滿足約束方程的所有可行解，排除不可行解。然后把可行解代入目標函數，求出最優(yōu)解。

3 實例分析

圖2 圖題

現以圖2為例，詳細敘述具體的操作過程。首先找到圖2的最小頂點覆蓋相對應的目標函數和約束條件，如式(3)(4)所示。

minU=x1+x2+x3+x4.

(3)

(4)

使用自組裝納米顆粒探針的DNA計算模型的操作方法如下：

表1 DNA序列編碼

在寡聚核苷酸3′端連接上硫醇基團(-SH)，5′端連接上熒光基團，然后通過共價鍵寡聚核苷酸可以牢固地固定在納米金顆粒的表面上。每個納米金顆?？梢院蛢蓚€合成的寡聚核苷酸整合，然后將所有的自組裝納米顆粒探針固定在表面上并排成一條線(圖3)。

圖3 所有的納米金探針

步驟六，通過上面的操作，可以得到滿足約束方程組的所有可行解，代入目標函數，可求出目標函數的最優(yōu)解有0110，1001兩個，對應的目標函數的最小值為2。同時可以得到圖的最小頂點覆蓋為{1,4}和{2,3}。

4 結論

DNA計算具有高存儲密度和大規(guī)模并行性，在解決困難問題尤其是NP完全問題上很有潛力。本文介紹了一種基于自組裝納米顆粒探針的新的DNA計算方法，可以解決最小頂點覆蓋問題，其主要思想是通過把最小頂點覆蓋問題轉化為0-1規(guī)劃問題。DNA序列與納米金顆粒結合形成納米金顆粒探針，當加入DNA序列的補鏈時，會發(fā)生雜交反應，產生熒光，從而判斷該問題的可行解，求出給定問題的最小頂點覆蓋。該模型方便、靈敏、穩(wěn)定性高，隨著納米技術和DNA計算的發(fā)展，其他更多的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].系統(tǒng)工程與電子技術,2004,26(4):544-548.

[6]周康,許進.最小頂點覆蓋問題的閉環(huán)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].小型微型計算機系統(tǒng),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- )，男，教授，博士，從事圖與組合優(yōu)化、DNA計算研究。