DNA折紙術(shù)在0-1整數(shù)規(guī)劃問題中的應(yīng)用

趙鑫月，殷志祥, 鞏成艷

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

DNA折紙術(shù)是一種全新的DNA自組裝的方法，與傳統(tǒng)的DNA自組裝相比，DNA折紙術(shù)更容易構(gòu)造出高度復(fù)雜、結(jié)構(gòu)穩(wěn)定的納米級結(jié)構(gòu)，并具有可尋址性，是DNA自組裝與DNA納米技術(shù)領(lǐng)域的一個重大進展。DNA折紙術(shù)的基本原理是將一條較長的DNA單鏈(腳手架鏈)與一系列經(jīng)過特殊設(shè)計的短的DNA片段(訂書釘鏈)通過堿基配對原則進行互補，可控地構(gòu)造出理想的納米結(jié)構(gòu)或圖案。文獻[1]首先提出了DNA折紙術(shù)這一概念并成功構(gòu)造出各種相對比較復(fù)雜的納米級形狀和圖案，包括方形、矩形、五角星、星形、笑臉以及美洲地圖等若干種圖案。文獻[2]基于DNA折紙原理成功構(gòu)造出中國地圖，進一步證明DNA折紙術(shù)具有構(gòu)造幾乎任何復(fù)雜二維納米級形狀的能力。文獻[3-4]研究了可精確調(diào)控三維曲面的立體花瓶結(jié)構(gòu)，將DNA折紙術(shù)在結(jié)構(gòu)設(shè)計與制造方面的研究推向高潮。文獻[5]結(jié)合DNA納米折紙術(shù)給出了一個用DNA納米結(jié)構(gòu)組裝找出最短哈密頓路徑的方法。文獻[6]采用DNA納米折紙結(jié)構(gòu)編碼信息，借助納米結(jié)構(gòu)之間的粘性末端進行自組裝，給出了一種非確定性的圖著色模型。

0-1規(guī)劃問題作為整數(shù)規(guī)劃問題的特殊形式，在運籌學(xué)中具有廣泛的應(yīng)用。許多NP完全問題也可以都可以轉(zhuǎn)化為0-1規(guī)劃問題。解決該問題的算法很多，有窮舉法、隱枚舉法、分支定界法等，但目前為止還沒有很好的算法來完全解決該問題。文獻[7]首次提出了在基于表面的DNA計算中采用熒光標記策略解決簡單0-1規(guī)劃問題的理論方案，嘗試了DNA計算在規(guī)劃問題中的應(yīng)用。文獻[8-10]分別將DNA芯片技術(shù)、DNA鏈置換技術(shù)、分子信標等運用于0-1規(guī)劃問題，提出了相應(yīng)的DNA計算模型。本文利用DNA折紙術(shù)對0-1規(guī)劃問題提出了一種新的計算模型，利用雜交后初始數(shù)據(jù)鏈的長度的變化來實現(xiàn)對每一個約束條件的判斷，求出問題的可行解。

1 0-1整數(shù)規(guī)劃問題的數(shù)學(xué)模型

0-1整數(shù)規(guī)劃是整數(shù)規(guī)劃的特殊情形，其變量僅取值0或1。文中利用DNA計算解決的0-1整數(shù)規(guī)劃問題，是指派問題的推廣。

max(min)z=c1x1+c2x2+…+cnxn

下面討論所對應(yīng)的0-1整數(shù)規(guī)劃問題的算法：

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

步驟2利用每一約束條件剔除非可行解(保留可行解)；

步驟3生成剩余的解；

步驟4重復(fù)進行步驟2～3，可排除所有的非解，得到問題的所有可行解；

步驟5比較各可行解對應(yīng)的目標函數(shù)值，進而得到最優(yōu)解。

2 生物操作

步驟1

步驟2

圖1 xi和堿基互補形成發(fā)夾結(jié)構(gòu)

步驟3

對滿足約束方程的DNA鏈加熱二級結(jié)構(gòu)重新打開，再次通過凝膠電泳將短的DNA鏈分離出去。

步驟4

重復(fù)步驟2和步驟3(m-1)次，就可得到滿足約束方程的可行解。

步驟5

對可行解所對應(yīng)的目標函數(shù)值加以比較后，即可找到問題的最優(yōu)解。

3 算法的實例分析

minu=2x+3y+z

步驟1

圖2 初始數(shù)據(jù)池中所有DNA鏈的組合

2)構(gòu)造3種分別與x，y，z的第一部分和第三部分互補的短的DNA鏈記為x′，y′，z′(見圖3)。

圖3 變量的編碼

步驟2

對于第一個約束方程，往溶液中加入足量的x′，y′，z′，短的DNA鏈x′，y′，z′與8條長的DNA鏈中含有x，y，z部分的寡聚核苷酸片段發(fā)生雜交反應(yīng)，即x′，y′，z′的前4個堿基對x，y，z的第一部分固定，后4個堿基對x，y，z的第三部分固定形成二級結(jié)構(gòu)(見圖4)。通過凝膠電泳分離出長度大于30+2Δx個堿基的DNA鏈和短的DNA鏈。得到滿足條件的DNA鏈：1，2，3，5。

圖4 加入滿足約束方程一中變量的特殊補鏈

步驟3

加熱將短的DNA鏈和長的DNA鏈分離，再通過凝膠電泳分離短的DNA鏈，此時溶液中只含有4種長的DNA鏈。

步驟4

對于第二個約束方程，在步驟3所得的產(chǎn)物中加x′，z′(見圖5)，分離出長度小于36+Δx的DNA鏈和短的DNA鏈，得到滿足該條件的DNA鏈：2，5。通過加熱、凝膠電泳操作，分離出短的DNA鏈。對于第三個約束方程，再在溶液中加入x′，y′(見圖6)，分離出長度小于36+Δx的DNA鏈和短的DNA鏈，得到滿足條件的DNA鏈：2。

圖5 加入滿足約束方程二中變量的特殊補鏈

圖6 加入滿足約束方程三中變量的特殊補鏈

步驟5

對于本問題可行解僅有DNA鏈2，對應(yīng)的編碼變量值(1，1，0)也是最優(yōu)解，目標函數(shù)的最小值為5。

4 結(jié)論

0-1規(guī)劃問題有著廣泛的應(yīng)用和研究意義，本文用DNA折紙術(shù)的方法求解了0-1整數(shù)規(guī)劃問題，通過構(gòu)造訂書釘鏈，使其對反應(yīng)溶液中腳手架鏈的特定位置固定形成二級結(jié)構(gòu)。根據(jù)反應(yīng)后DNA鏈構(gòu)形的變化對每一個約束方程進行判斷，刪除所有不滿足條件的解，得到最優(yōu)解。由于DNA折紙術(shù)的應(yīng)用該方法能夠產(chǎn)生大批量的高質(zhì)量的納米結(jié)構(gòu)，并且對腳手架鏈和訂書釘鏈的相對化學(xué)計量要求不高，實驗操作簡單，具有巨大并行性和高存儲量的優(yōu)點。更重要的是利用凝膠電泳操作使的每一步都可以排除大量非解，進一步降低了計算的時間復(fù)雜度和空間復(fù)雜度。但是當變量較多時，初始數(shù)據(jù)池中可能會由于編碼問題腳手架鏈內(nèi)部形成二級結(jié)構(gòu)。因而，用腳手架鏈進行自組裝，必須進行序列優(yōu)化。隨著分子生物學(xué)及生物工程的發(fā)展，該方法的進一步擴展有可能解決一般的整數(shù)規(guī)劃問題。

參考文獻：

[1] ROTHEMUND P W.Folding DNA to create nanoscale shaps and paterns[J]. Nature， 2006，400(7 082)： 297-302.

[2] QIAN L L，WANG Y，ZHANG Z，et al.Analogic China map constructed by DNA[J]. Chines Science Bulletin，2006，51(24)： 2 973-2 976.

[3] HAN D，PAL S，NANGREAVE J，et al. DNA origami with complex curvatures in three-dimensional space[J]. Science， 2011， 332(6 027)：342-346.

[4] HAN D，PAL S，YANG Y，et al. DNA gridiron nanastructures based on four-arm junctions[J]. Science，2011，339(6 126)：1 412-1 415.

[5] 俞洋， 蘇邵， 晁杰. 基于DNA折紙術(shù)設(shè)計哈密特路徑問題的解決方案[J].中國科學(xué)化學(xué)， 2015，45(11)： 1 226-1 230.

[6] 俞洋， 蘇邵， 晁杰. 基于DNA折紙術(shù)設(shè)計圖著色問題的解決方案[J].南京大學(xué)學(xué)報，2016，52(4)：656-661.

[7] 殷志祥， 張鳳月， 許進. 0-1規(guī)劃問題的DNA計算[J].電子與信息學(xué)報，2003，25(1)： 62-66.

[8] 殷志祥， 許進. 分子信標芯片計算在0-1整數(shù)規(guī)劃問題中的應(yīng)用[J]. 生物數(shù)學(xué)學(xué)報， 2007，22(3)： 559-564.

[9] 許進， 周康， 覃磊. 0-1規(guī)劃問題的閉環(huán)DNA算法[J]. 系統(tǒng)工程與電子技術(shù)， 2009，31(4)：947-951.

[10] 任曉玲， 白雪， 劉希玉. 基于三鏈DNA結(jié)構(gòu)的0-1整數(shù)規(guī)劃改進研究[J]. 計算機應(yīng)用研究， 2013，30(1)：56-59.

[11] 董亞飛.基于DNA鏈置換和熒光標記的0-1規(guī)劃問題的計算模型[J].數(shù)學(xué)的實踐與認識，2013，43：153-158.

[12] 張鳳月， 殷志祥， 許進. DNA芯片在0-1規(guī)劃問題中的應(yīng)用[J]. 生物化學(xué)與生物物理進展， 2003， 30(3)： 412-415.

[13] 楊進. 基于抗原中介三鏈DNA結(jié)構(gòu)的0-1整數(shù)規(guī)劃[J]. 計算機工程與應(yīng)用， 2008，44(2)：76-79.

[14] FEI L，JIN X，ZHANG L. DNA computing model based on self-assembled nanoparticle probes for SAT problem [J]. Advanced Materials Research，2012，443-444： 513-517.

[15] DUNN K E，DANNENBERG F，TE OULDRIDGE,et al. Guiding the folding pathway of DNA origami[J].Nature，2015，525(7 567)： 82-86.

[16] SHEN X，SONG C，WANG J，et al. Rolling up gold nanoparticle-dressed DNA origami into three-dimensional plasmonic chiral nanostructures[J]. Journal of American Chemical Society，2012，134(1)： 146-149.

[17] MARINI M，PIANTANIDA L，MUSETTI R，et al. A revertible，autonomous，self-assembled DNA origami nanoactuator[J]. Nanor letters， 2015，11(12)： 5 449-5 454.

[18] CASTRO C E. A primer to scaffolded DNA origami[J]. Nature Methods， 2011，8(3)：221-229.

[19] FUNKE J，DIETZ.Placing molecules with Bohr radius resolution use DNA origami[J]. Nature Nanotechnology， 2016，11(1)：47-52.

[20] 錢璐璐. DNA自組裝在分子計算和納米技術(shù)等方面應(yīng)用的研究[D]. 上海： 上海交通大學(xué)，2007.