基于DNA折紙系統(tǒng)求解0-1整數(shù)規(guī)劃問題的模型

嚴(yán)洋洋,殷志祥

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

0 引言

DNA納米技術(shù)是一個(gè)多學(xué)科研究領(lǐng)域，能夠在納米級(jí)層次上進(jìn)行計(jì)算.這一全新領(lǐng)域的開辟，為生物醫(yī)學(xué)、生物制造、化工、材料等提供了很大的便利，如：藥物傳送[1,2]、納米機(jī)器人[3,4].分子計(jì)算是一種具有巨大潛力的新興技術(shù)，可以實(shí)現(xiàn)對(duì)納米級(jí)物質(zhì)結(jié)構(gòu)的控制以及納米計(jì)算.[5]其中，DNA鏈置換就是一種在分子水平上用于實(shí)現(xiàn)納米級(jí)計(jì)算的簡(jiǎn)單而強(qiáng)大的自組裝方法[6].由于DNA是一種具有穩(wěn)定的規(guī)則的雙螺旋結(jié)構(gòu)的高分子化合物，具有精確的自組裝能力、分子序列可編程性及良好的生物相容性[7]，利用它的特殊的結(jié)構(gòu)和堿基互補(bǔ)配對(duì)原則將其折疊成不同形狀、不同尺寸的DNA納米材料[8].

1982年，Seeman及其同事就提出了利用DNA分子構(gòu)建不同簡(jiǎn)單結(jié)構(gòu)的納米器件的想法.幾年后他終于利用DNA分子構(gòu)建了三角形、方形等形狀的結(jié)構(gòu).1991年和1993年Seeman成功的組裝了三維的立方體結(jié)構(gòu)和DX結(jié)構(gòu)[8].隨后，出現(xiàn)了越來越多的不同結(jié)構(gòu)和尺寸的納米結(jié)構(gòu)和納米器件.如Yan[9]等構(gòu)建的的十字Tile以及具有設(shè)定尺寸的二維陣列圖形[10].

在Seeman等人的基礎(chǔ)上，加州理工學(xué)院的Rothemund在2006年開發(fā)了一種新的DNA自組裝技術(shù)——DNA折紙術(shù).相較于之前的“自下而上”的DNA自組裝方法，不再是組裝一些簡(jiǎn)單的具有規(guī)則的結(jié)構(gòu)，而是一種“自上而下”的全新的策略，它能夠構(gòu)建出更多樣更復(fù)雜的自組裝納米結(jié)構(gòu)，而且結(jié)構(gòu)的穩(wěn)定性也大大的提高了，可控性更強(qiáng)了.DNA折紙是利用一條長(zhǎng)單的DNA鏈(腳手架鏈)在特定的位置利用短單的DNA鏈(訂書釘鏈)通過分子間堿基互補(bǔ)配對(duì)的原則，將長(zhǎng)單的DNA鏈設(shè)計(jì)構(gòu)造出不同形狀、不同尺寸的自組裝結(jié)構(gòu)[10].Rothemund還提出了對(duì)單個(gè)DNA自組裝結(jié)構(gòu)進(jìn)行編程以設(shè)計(jì)出更大的DNA納米結(jié)構(gòu)，并且利用六個(gè)三角形成功地組裝了一個(gè)三角形六聚體，為后來的大結(jié)構(gòu)組裝提供了基礎(chǔ).可以說，DNA折紙使DNA納米技術(shù)登上了一個(gè)新的臺(tái)階.2006年，錢璐璐[11]利用DNA折紙成功的“折”出了第一個(gè)非對(duì)稱的納米圖形——中國(guó)地圖.此后，在Rothemund的基礎(chǔ)上，許多研究組對(duì)折紙進(jìn)行了改進(jìn)，設(shè)計(jì)了三維結(jié)構(gòu)的DNA折紙[12]以及能夠自動(dòng)完成任務(wù)的計(jì)算機(jī)輔助程序等[13].2008年，Andersen[14]等進(jìn)一步的發(fā)展了DNA折紙，不但成功的組裝了一個(gè)海豚，而且還為海豚添加了一條可以擺動(dòng)的尾巴.文獻(xiàn)12-14的研究結(jié)果，說明了DNA折紙不僅可以折出非對(duì)稱的納米結(jié)構(gòu)，而且還可以將DNA折紙應(yīng)用到動(dòng)態(tài)的納米結(jié)構(gòu)中，使得DNA納米結(jié)構(gòu)變得更加多樣化、復(fù)雜化.文獻(xiàn)15，基于DNA折紙?jiān)O(shè)計(jì)了一個(gè)動(dòng)態(tài)DNA系統(tǒng)，用于動(dòng)態(tài)DNA納米技術(shù)的集成開發(fā)環(huán)境.文獻(xiàn)16介紹了一種在尺寸上能夠達(dá)到微米級(jí)別具有可控性的分形組裝的方法.2018年，Enzo Kopperger[17]等人設(shè)計(jì)了一個(gè)由電場(chǎng)控制的自組裝納米級(jí)機(jī)械臂，能夠在創(chuàng)建的分子平臺(tái)上進(jìn)行移動(dòng).2019年，莊小威課題組創(chuàng)建了基于DNA折紙的轉(zhuǎn)子成像追蹤技術(shù)，在單分子成像方面取得重大的突破[18].1994年，Adleman借助一種基于DNA的多項(xiàng)式時(shí)間的方法解決了7頂點(diǎn)圖的Hamilton路徑問題.于是開始借助DNA的并行性解決一些NP問題(Non-deterministic Polynomial).0-1整數(shù)規(guī)劃問題(0-1 Programming Problem)是一類特殊的整數(shù)規(guī)劃問題，也是一個(gè)十分經(jīng)典的NP問題.在很多方面都有著舉足輕重的應(yīng)用，諸如背包問題，圖的最大團(tuán)等也可以轉(zhuǎn)化為0-1規(guī)劃.常用窮舉法、分支定界法等解決這一問題，可至今為止還沒有一個(gè)通用的算法來完全解決.殷志祥等[19]在2003年，設(shè)計(jì)了一種基于表面的DNA計(jì)算熒光標(biāo)記策略，用于解決0-1規(guī)劃問題.文獻(xiàn)20，提出了一種雙重編碼的方式的DNA計(jì)算模型來解決0-1問題.同年，楊靜[21]也設(shè)計(jì)了一種基于三鏈DNA結(jié)構(gòu)的算法解決此問題.文獻(xiàn)22和文獻(xiàn)23分別將DNA鏈置換和DNA折紙術(shù)應(yīng)用于解決0-1規(guī)劃問題.

本文主要根據(jù)鏈置換的組裝方式設(shè)計(jì)了一個(gè)DNA折紙系統(tǒng)求解0-1規(guī)劃問題，該折紙系統(tǒng)由DNA折紙基底和四種類型的輔助鏈組成.在加入輸入鏈后，經(jīng)過鏈置換，釋放輔助鏈上金納米顆粒，實(shí)現(xiàn)每一個(gè)約束條件，通過輔助鏈上金納米顆粒接收和釋放的情況得出問題可行解.

1 DNA折紙系統(tǒng)

該DNA折紙系統(tǒng)[24]主要有兩部分組成，DNA折紙基底(圖1a)，四種類型的輔助鏈(DNA/AuNP共軛物)組成(圖1b).該折紙基底(其折紙?jiān)韥碓从赗othemund開發(fā)的折紙術(shù)，為了合成矩形DNA折紙，將1.6 nM的M13 mp18鏈與訂書釘鏈在1×TAE / Mg2 +緩沖液中以1:10的比例混合，并從90°C退火至室溫.)由一條約為7 000 bp的圓形單鏈M13 mp18和202條短訂書釘鏈折疊而成的二維矩形折紙模板，尺寸為90 nm×60 nm×2 nm(圖1a中的矩形).在折紙基底上延伸出四條輔鏈設(shè)計(jì)了四個(gè)金納米顆粒的捕獲位置，分別為a，b，c，d.

通過硫醇化后互補(bǔ)DNA鏈修飾金納米顆粒，設(shè)計(jì)了四種類型的輔助鏈(圖1b)，即NP-A，NP-B，NP-C，NP-D，分別標(biāo)記為a1，b1，c1，d1，并且每條輔助鏈的一端帶有15 nm的金納米顆粒(圖1b 黃色用小圓圈表示).(矩形折紙模板和DNA/AuNP共軛物在反應(yīng)中以1∶30比例混合，并從40 °C退火至室溫)與四種類型的輔助鏈相對(duì)應(yīng)的是四種類型輸入鏈(圖1c)a-L，b-L，c-L，d-L，能夠識(shí)別識(shí)別折紙基底延伸的a，b，c，d的輸入?yún)^(qū)，并且優(yōu)先于置換出輔助鏈a1，b1，c1，d1.

圖1a DNA折紙基底Fig.1a The DNA origami substrate圖1b 四種類型的輔助鏈Tab.1b Four Types of Auxiliary Chains

圖1c 輸入鏈a-L,b-L,c-L,d-LTab.1c The Input Chain a-L, b-L, c-L, d-L圖1d DNA折紙系統(tǒng) Tab.1d The DNA Origami System

圖2 AuNPs 釋放過程Tab.2 The Release Process of AuNPs

在初始的狀態(tài)下，將DNA折紙基底與NP-A，NP-B，NP-C，NP-D進(jìn)行反應(yīng)，充分反應(yīng)后，自組裝成折紙系統(tǒng).然后，再加入四種類型輸入鏈 a-L，b-L，c-L，d-L，進(jìn)行反應(yīng).接著，觀察反應(yīng)后的每個(gè)折紙基底上金納米顆粒的釋放情況，作出判斷.即在該計(jì)算系統(tǒng)中，可行解的判定是通過DNA鏈置換在DNA折紙基底上選擇性的釋放金納米顆粒來實(shí)現(xiàn)的.

2 0-1 整數(shù)規(guī)劃問題的DNA折紙計(jì)算模型

0-1整數(shù)規(guī)劃問題是一種特殊的整數(shù)規(guī)劃問題，它的變量xi的取值僅為0或1.它在工程、市場(chǎng)分析、方案選擇等方面都有著十分重要的應(yīng)用.

它的一般形式為：

2.1 0-1整數(shù)規(guī)劃問題的DNA折紙計(jì)算模型的基本算法：

步驟1：生成所求問題中變量0或1的所有可能性組合；

步驟2：利用每條約束條件刪除非可行解，保留可行解；

步驟3：重復(fù)Step2，直至找到所有的可行解；

步驟4：得到各個(gè)可行解對(duì)應(yīng)得目標(biāo)函數(shù)值，并進(jìn)行比較，獲取最優(yōu)解.

2.2 0-1整數(shù)規(guī)劃問題的DNA折紙計(jì)算模型的生物算法：

對(duì)于一個(gè)含有n個(gè)變量x1,x2,…,xn和m個(gè)方程的0-1整數(shù)規(guī)劃問題的方程組，

步驟3 經(jīng)過前一個(gè)約束條件判斷后不滿足該約束條件的可能性組合，后一個(gè)約束條件不在進(jìn)行判斷.重復(fù)進(jìn)行步驟2，直至m個(gè)約束條件，找出全部可行解的組合，判斷結(jié)束.

步驟4 計(jì)算得到各個(gè)可行解對(duì)應(yīng)的目標(biāo)函數(shù)值，然后將得到的函數(shù)值進(jìn)行比對(duì)，進(jìn)而找到最優(yōu)解.

3 具體實(shí)例

這里就一個(gè)簡(jiǎn)單的實(shí)例進(jìn)行說明，該DNA折紙系統(tǒng)在0-1整數(shù)規(guī)劃問題的應(yīng)用：

步驟1 對(duì)各個(gè)變量進(jìn)行指派，由于變量的取值只能是0或1，故在這個(gè)實(shí)例中共有8種不同的指派方式，分別為x1=1或x1=0，x2=1或x2=0,x3=1或x3=0,x4=1或x4=0所有的可能性組合為24=16種.下面將這8種不同的指派分為兩組，前一組輔助鏈經(jīng)過金納米顆粒修飾，表示為x1=1，x2=1，x3=1，x4=1.前一組輔助鏈未經(jīng)過金納米顆粒修飾表示為x1=0，x2=0，x3=0，x4=0.取四種不同的輔助鏈與折紙基底組裝成DNA折紙系統(tǒng)，分別用1(0 0 0 0)， 2(1 0 0 0)， 3(0 1 0 0)， 4(0 0 1 0)，5(0 0 0 1)， 6(1 1 0 0)， 7(1 0 1 0)， 8(1 0 0 1)，9(0 0 1 1)，10(0 1 0 1)，11(0 0 1 1)， 12(1 1 1 0)，13(1 1 0 1)，14(1 0 1 1)，15(0 1 1 1)，16(1 1 1 1)表示.如(0 0 0 0)表示x1=0，x2=0，x3=0，x4=0，(0 0 1 1)表示x1=0，x2=0，x3=1，x4=1.

步驟2 DNA折紙系統(tǒng)組裝完全后，加入輔助鏈a-L，b-L，c-L，d-L，進(jìn)行鏈置換反應(yīng)，單鏈a-L，b-L，c-L，d-L將單鏈a，b，c，d置換出，并與單鏈a1，b1，c1，d1互補(bǔ)形成雙鏈.然后借助電鏡觀察.若是能夠滿足約束條件，則可以在DNA折紙系統(tǒng)中觀察到金納米顆粒的存在.若是不能滿足約束條件，則觀察不到金納米顆粒的存在，即輔助鏈上金納米顆粒被釋放了.

針對(duì)第一個(gè)約束條件x1+x2+x3+x4≥2，經(jīng)過DNA鏈置換后該折紙系統(tǒng)中能顧觀察到的金納米顆粒至少要有2個(gè)，滿足條件的可能組合為：6(1 1 0 0)， 7(1 0 1 0)， 8(1 0 0 1)，9(0 0 1 1)，10(0 1 0 1)，11(0 0 1 1)， 12(1 1 1 0)，13(1 1 0 1)，14(1 0 1 1)，15(0 1 1 1)，16(1 1 1 1).

圖3 可行解(1 1 0 0)示意圖Tab.3 Diagram of the Feasible Solution (1, 1, 0, 0)

步驟3，重復(fù)進(jìn)行步驟2，直至所有約束條件檢測(cè)完全，找出所有滿足約束條件的可能性組合.不滿足前一個(gè)約束條件的可能性組合刪除，即該組合不是可行解.

依次檢測(cè)，針對(duì)第二個(gè)約束條件x1+x3+x41，滿足該條件的可能組合為：6(1 1 0 0)，9(0 0 1 1)，10(0 1 0 1)

針對(duì)第三個(gè)約束條件x2+x3+x41，滿足該條件的可能組合為：6(1 1 0 0).最后能夠找到的可行解僅有6(1 1 0 0)，即x1=1，x2=1，x3=0，x4=0.

最后在DNA折紙系統(tǒng)中的結(jié)果為：

步驟4 對(duì)于該實(shí)例，可行解只有一個(gè)(1 1 0 0)，計(jì)算可得到目標(biāo)函數(shù)：S=5

4 結(jié)論

在借助DNA自組裝構(gòu)建DNA納米材料方面已經(jīng)取得了很大的成就.2006年Rothemund開發(fā)的DNA折紙術(shù)更是在構(gòu)建納米結(jié)構(gòu)方面向前邁出了一大步.文中主要通過DNA折紙建立一個(gè)折紙系統(tǒng)來解決0-1整數(shù)規(guī)劃問題.借助DNA鏈置換有選擇性的釋放金納米顆粒.結(jié)果的判斷是通過電鏡觀察金納米顆粒是否從折紙系統(tǒng)中釋放來表示.這樣設(shè)計(jì)不僅操作簡(jiǎn)單，結(jié)果也很容易觀察和檢測(cè).不足的一點(diǎn)是，由于DNA折紙基底是由一條長(zhǎng)單鏈折成的，于是基底的尺寸就受到了限制，由此也限制了折紙系統(tǒng)的規(guī)模.這樣就只能解決一些變量比較少0-1整數(shù)規(guī)劃問題.若變量過多就會(huì)單鏈之間發(fā)生反應(yīng)導(dǎo)致錯(cuò)排，DNA鏈之間發(fā)生反應(yīng)，同時(shí)也不利于結(jié)果的檢測(cè).但隨著研究的不斷進(jìn)展，將來更大規(guī)模的DNA折紙結(jié)構(gòu)也最終能夠設(shè)計(jì)出來，也將會(huì)有更加廣泛的應(yīng)用.