趙鑫月, 殷志祥

(1. 蚌埠學(xué)院 理學(xué)院, 安徽 蚌埠 233030; 2. 安徽理工大學(xué) 數(shù)學(xué)與大數(shù)據(jù)學(xué)院, 安徽 淮南 232001;3. 上海工程技術(shù)大學(xué) 數(shù)理與統(tǒng)計(jì)學(xué)院, 上海 201620)

DNA作為遺傳信息的載體，其精確的堿基配對(duì)原則、序列的可編程性、結(jié)構(gòu)的多樣性和可控性等優(yōu)勢(shì)，被認(rèn)為是最有前途的一類分子機(jī)器構(gòu)造材料[1].DNA步行者是一類以DNA為構(gòu)筑元件設(shè)計(jì)并制備的可執(zhí)行復(fù)雜操作的分子機(jī)器，能夠控制納米尺度的目標(biāo)物沿預(yù)設(shè)軌道進(jìn)行機(jī)械運(yùn)動(dòng)，在生物傳感、生物成像、新材料組裝與合成及生物計(jì)算等領(lǐng)域有著極大的應(yīng)用前景.

DNA步行者最初是由Sherman等[2]于2004年設(shè)計(jì)的，由三股突出的單鏈DNA構(gòu)成一條一維(1D)軌道.2006年，Pei等[3]利用DNA步行者可以在DNA折紙或DNA修飾平面組成的二維軌道上移動(dòng)，提出了二維(2D)折紙軌道.在科研人員的不懈努力下，DNA步行者已由最初一維軌道上的步行運(yùn)動(dòng)，發(fā)展到后來的二維折紙軌道運(yùn)動(dòng)[4-11]，乃至當(dāng)前基于納米粒子的三維軌道上運(yùn)動(dòng)[12].2015年，Ellington課題組通過把發(fā)夾型DNA鏈修飾在微球表面組裝成三維軌道，設(shè)計(jì)了一種新型三維DNA納米機(jī)器[13].2017年，Jiang課題組報(bào)道了一種構(gòu)筑在磁性納米微球上的三維步行者分子機(jī)器[14].2018年，Li課題組將發(fā)夾結(jié)構(gòu)作為DNA步行鏈，切口酶識(shí)別位點(diǎn)位于發(fā)夾的環(huán)中，設(shè)計(jì)了一種切口酶驅(qū)動(dòng)的DNA步行者分子機(jī)器[15].2019年，Wang等[16]利用滾環(huán)擴(kuò)增技術(shù)構(gòu)建了多種酶驅(qū)動(dòng)的DNA步行者，用于高靈敏生物傳感器.

最小頂點(diǎn)覆蓋問題是圖論中的一個(gè)經(jīng)典問題，不僅在數(shù)理邏輯和開關(guān)理論等方面有重要的研究地位，而且在分子生物學(xué)、調(diào)度問題、郵輪行程安排等實(shí)際生產(chǎn)領(lǐng)域都有著很高的應(yīng)用價(jià)值.2005年，董亞非等[17]提出了解決最小頂點(diǎn)覆蓋問題的粘貼模型.2009年，羊四清等[18]提出了最小頂點(diǎn)覆蓋的表面計(jì)算模型.2011年，Zhang等[19]利用三維自組裝模型解決了最小頂點(diǎn)覆蓋問題.2017年，鞏成艷等[20]在自組裝納米顆粒探針的基礎(chǔ)上，設(shè)計(jì)了一種新型的最小頂點(diǎn)覆蓋問題的 DNA 計(jì)算模型.

本文將三維DNA 步行者應(yīng)用于解決最小頂點(diǎn)覆蓋問題，該模型將步行DNA鏈固定在磁性納米微球表面構(gòu)造出全部頂點(diǎn)覆蓋，并加入DNA發(fā)夾探針，形成包含G-四鏈體結(jié)構(gòu)單元的雙鏈DNA，以刪除掉與每邊相關(guān)的一個(gè)頂點(diǎn)，產(chǎn)生所有覆蓋的補(bǔ)集，再加入熒光探針N-甲基卟啉二丙酸(NMM)特異性識(shí)別G-四鏈體結(jié)構(gòu)，產(chǎn)生熒光，最終得到最小頂點(diǎn)覆蓋.該模型將軌道構(gòu)建于磁性納米粒子，具有較大的表面積、并行性好、靈敏度高和運(yùn)行效率更快的特點(diǎn)，可以解決規(guī)模更大、更為復(fù)雜的最小覆蓋問題.

1 最小頂點(diǎn)覆蓋問題

圖的頂點(diǎn)覆蓋問題是指找出給定圖中頂點(diǎn)的一個(gè)最小子集，圖中任意一條邊的兩個(gè)端點(diǎn)都至少有一個(gè)屬于該子集.給定簡單無向圖G=(V,E)，其中頂點(diǎn)集V(G)={v1,v2,…,vn}，邊集E(G)={e1,e2,…,en}.設(shè)K是V(G)的一個(gè)子集，并且圖G的每條邊都至少有一個(gè)端點(diǎn)在K中，則稱K是G的一個(gè)覆蓋.如果G中不存在|K′|<|K|的覆蓋K′,則稱K是G的最小頂點(diǎn)覆蓋.

2 計(jì)算模型

2.1 模型的組成

圖1 DNA步行軌道Fig.1 DNA walking track

圖2 鏈的組成與結(jié)構(gòu)Fig.2 Composition and structure of chain

2.2 算法

步驟2以每條邊為約束，在DNA折紙基底上刪除掉與邊相關(guān)聯(lián)的一個(gè)頂點(diǎn)，經(jīng)過m次刪除試驗(yàn)后，產(chǎn)生所有覆蓋的補(bǔ)集.

(1)取k=1.

圖3 步驟2(3)的反應(yīng)過程Fig.3 The reaction process diagram of Step 2 (3)

(4)令k=k+1重復(fù)(2)(3)，直到k=m得到的數(shù)據(jù)池Tm+1中任何一個(gè)磁性納米顆粒上不會(huì)同時(shí)含有任何一條邊相關(guān)聯(lián)的兩個(gè)頂點(diǎn)所對(duì)應(yīng)的發(fā)夾結(jié)構(gòu)，即每個(gè)折紙基底都對(duì)應(yīng)一個(gè)最小頂點(diǎn)覆蓋的補(bǔ)集.

步驟3 在透射電鏡顯微鏡下觀察，選擇數(shù)據(jù)池中發(fā)夾結(jié)構(gòu)最多的磁性納米微球，加入熒光探針N-甲基卟啉二丙酸(NMM)，熒光探針N-甲基卟啉二丙酸(NMM)會(huì)對(duì)雙鏈DNA的G-四鏈體結(jié)構(gòu)特異性進(jìn)行識(shí)別，并嵌入到G-四鏈體中，產(chǎn)生強(qiáng)烈的熒光，點(diǎn)亮納米微球.該磁性納米微球上未發(fā)生反應(yīng)的發(fā)夾結(jié)構(gòu)對(duì)應(yīng)最小頂點(diǎn)覆蓋的補(bǔ)集，而磁性納米微球上產(chǎn)生熒光的G-四鏈體雙鏈對(duì)應(yīng)的就是最小頂點(diǎn)覆蓋.

整個(gè)過程的操作原理示意圖如圖4所示.

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

3 實(shí)例分析

現(xiàn)以簡單無向圖G=(V,E)的最小頂點(diǎn)覆蓋問題為例(圖5)，說明該算法的正確性和有效性.圖G中V={v1,v2,v3,v4}，E={e1,e2,e3,e4,e5}.使用三維DNA步行者計(jì)算模型操作如下：

圖5 簡單無向圖GFig.5 Simple undirected graph G

步驟1將編碼引發(fā)鏈I和4種發(fā)夾結(jié)構(gòu)的DNA依次固定在磁性納米微球表面(圖6)，作為初始數(shù)據(jù)池T1={(v1v2v3v4)}.編碼5種輔助鏈及其相應(yīng)的補(bǔ)鏈，再設(shè)計(jì)5種DNA發(fā)夾探針.

圖6 初始數(shù)據(jù)池中的DNA步行軌道Fig.6 DNA walking track in the initial data pool

步驟2

(2)k=2，取出e2=v1v3，得到數(shù)據(jù)池T3={(0v2v3v4),(00v3v4)，(0v20v4),(v100v4)}.

(3)k=3，取出e3=v2v3，得到數(shù)據(jù)池T4={(00v3v4),(v100v4)，(0v20v4),(000v4)}.

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

(5)k=5，取出e5=v3v4，得到數(shù)據(jù)池T6={(v100v4)，(v1000),(0v200),(00v30),(000v4)，(0000)}，如圖7所示.

圖7 數(shù)據(jù)池T6中的磁性納米微球Fig.7 Magnetic nanospheres in data pool T6

步驟3在透射電鏡顯微鏡下觀察，選擇發(fā)夾結(jié)構(gòu)最多的磁性納米微球{(v100v4)}，加入熒光探針N-甲基卟啉二丙酸(NMM).該磁性納米微球上的發(fā)夾結(jié)構(gòu)對(duì)應(yīng)最小的頂點(diǎn)覆蓋補(bǔ)集{v1,v4}，產(chǎn)生熒光的G-四鏈體雙鏈對(duì)應(yīng)的就是最小頂點(diǎn)覆蓋{v2,v3},如圖8所示.

圖8 最小頂點(diǎn)覆蓋所在的磁性納米微球Fig.8 Magnetic nanospheres with minimal vertex coverage

4 結(jié) 論

本文應(yīng)用DNA步行者求解最小頂點(diǎn)覆蓋問題，提出了最小頂點(diǎn)覆蓋的三維DNA步行者計(jì)算模型.在磁性納米顆粒上構(gòu)筑的三維軌道，具有較大的表面積，可以裝載高密度的DNA軌道，使分子機(jī)器所能行走的步數(shù)更多，運(yùn)行效率更高.反應(yīng)后用熒光探針N-甲基卟啉二丙酸(NMM)特異性識(shí)別G-四鏈體結(jié)構(gòu)，得到最小頂點(diǎn)覆蓋，靈敏度高，讀解更簡單.將DNA步行者的核心思想應(yīng)用于組合優(yōu)化問題的求解，不僅拓寬了DNA步行者的應(yīng)用領(lǐng)域，也為解決組合優(yōu)化問題提供了一種新的思路和方法.雖然該模型有很多優(yōu)點(diǎn)，但是問題仍然存在：反應(yīng)過程中，數(shù)據(jù)池中的磁性納米顆粒之間可能會(huì)發(fā)生錯(cuò)配，從而可能影響結(jié)果的準(zhǔn)確性.相信隨著納米技術(shù)和DNA計(jì)算的快速發(fā)展，該問題可以得到解決.