趙鑫月，殷志祥, 鞏成艷

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

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

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

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

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

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

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

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

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

步驟3生成剩余的解；

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

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

2 生物操作

步驟1

步驟2

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

步驟3

對(duì)滿(mǎn)足約束方程的DNA鏈加熱二級(jí)結(jié)構(gòu)重新打開(kāi)，再次通過(guò)凝膠電泳將短的DNA鏈分離出去。

步驟4

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

步驟5

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

3 算法的實(shí)例分析

minu=2x+3y+z

步驟1

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

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

圖3 變量的編碼

步驟2

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

圖4 加入滿(mǎn)足約束方程一中變量的特殊補(bǔ)鏈

步驟3

加熱將短的DNA鏈和長(zhǎng)的DNA鏈分離，再通過(guò)凝膠電泳分離短的DNA鏈，此時(shí)溶液中只含有4種長(zhǎng)的DNA鏈。

步驟4

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

圖5 加入滿(mǎn)足約束方程二中變量的特殊補(bǔ)鏈

圖6 加入滿(mǎn)足約束方程三中變量的特殊補(bǔ)鏈

步驟5

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

4 結(jié)論

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

參考文獻(xiàn)：

[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ì)哈密特路徑問(wèn)題的解決方案[J].中國(guó)科學(xué)化學(xué)， 2015，45(11)： 1 226-1 230.

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

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

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

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

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

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

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

[13] 楊進(jìn). 基于抗原中介三鏈DNA結(jié)構(gòu)的0-1整數(shù)規(guī)劃[J]. 計(jì)算機(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] 錢(qián)璐璐. DNA自組裝在分子計(jì)算和納米技術(shù)等方面應(yīng)用的研究[D]. 上海： 上海交通大學(xué)，2007.