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

趙鑫月, 殷志祥

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

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

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

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

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

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 鏈的組成與結構Fig.2 Composition and structure of chain

2.2 算法

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

(1)取k=1.

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

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

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

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

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

3 實例分析

現以簡單無向圖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將編碼引發鏈I和4種發夾結構的DNA依次固定在磁性納米微球表面(圖6)，作為初始數據池T1={(v1v2v3v4)}.編碼5種輔助鏈及其相應的補鏈，再設計5種DNA發夾探針.

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

步驟2

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

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

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

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

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

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

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

4 結 論

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