基于DNA步行者求解最小頂點覆蓋問題的計算模型

趙鑫月, 殷志祥

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

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

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

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

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

1 最小頂點覆蓋問題

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

2 計算模型

2.1 模型的組成

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

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

2.2 算法

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

(1)取k=1.

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

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

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

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

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

3 實例分析

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

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

步驟1將編碼引發(fā)鏈I和4種發(fā)夾結(jié)構(gòu)的DNA依次固定在磁性納米微球表面(圖6)，作為初始數(shù)據(jù)池T1={(v1v2v3v4)}.編碼5種輔助鏈及其相應的補鏈，再設計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)對應最小的頂點覆蓋補集{v1,v4}，產(chǎn)生熒光的G-四鏈體雙鏈對應的就是最小頂點覆蓋{v2,v3},如圖8所示.

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

4 結(jié) 論

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