簡單0-1規(guī)劃問題的動態(tài)DNA折紙計算模型

斯燕方，殷志祥，崔建中，楊 靜，唐 震

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

2.安徽理工大學 電氣與信息工程學院，安徽 淮南232001

3.淮南聯(lián)合大學 計算機系，安徽 淮南232001

1 引言

DNA作為生物遺傳信息的載體，具有納米可編程等優(yōu)點，利用這個特點來設(shè)計納米結(jié)構(gòu)一直是研究的熱點。近年來出現(xiàn)的DNA折紙術(shù)為設(shè)計復雜二、三維納米結(jié)構(gòu)提供了新的方法手段。與傳統(tǒng)的DNA自組裝技術(shù)不同，DNA折紙術(shù)通過一條長的DNA單鏈（腳手架鏈）與一系列預設(shè)計的短鏈DNA片段（訂書釘鏈）進行堿基互補配對，折疊出高度復雜的二維納米圖案和三維納米結(jié)構(gòu)。與傳統(tǒng)納米自組裝方法相比，DNA折紙術(shù)具有更佳的精細程度和可控性，而且其實驗條件要求低，操作簡單，效率高。

最近的研究成果表明，在組裝的規(guī)模上，DNA折紙術(shù)也取得了較大的進展。DNA折紙術(shù)[1]是一種不同于傳統(tǒng)自組裝（自上而下的組裝）的方法。它的思路是將一條長度為7 429個堿基（M13mp18噬菌體DNA）的DNA作為腳手架鏈，并利用200多條訂書釘鏈將其折疊固定，得到了正方形、矩形、五角星、笑臉和三角形等精細復雜的二維結(jié)構(gòu)。DNA折紙術(shù)的研究為實現(xiàn)納米結(jié)構(gòu)的精確組裝奠定了基礎(chǔ)。隨后更加復雜多樣的納米結(jié)構(gòu)不斷被設(shè)計出來，為納米器件的深入研究提供了更為精密的模板[2-3]。同年，上海交通大學Bio-X中心的DNA計算機交叉研究團隊與中國科學院上海應用物理研究所進行合作，成功構(gòu)造出“仿中國地圖”的DNA納米結(jié)構(gòu)[4]。這是國內(nèi)首個利用DNA鏈折疊得到的非對稱二維圖形，克服了非對稱圖形帶來的應力問題。2010年，晁潔等[5]利用DNA折紙設(shè)計了“三手四足”DNA機器人。該方法為DNA折紙機器人作為載藥工具的應用提供了良好的思路。接著在2015年和2016年，晁潔等[6-7]又利用DNA納米折紙結(jié)構(gòu)相繼給出了尋找最短哈密頓路的方法和圖著色問題的一種解決方法。晁潔等[8]在2017年還將DNA折紙應用于基因分型，利用三角形、十字形和矩形作為標簽對人類基因組DNA的單個分子進行基因分型，這種方法在單分子水平的遺傳分析中具有巨大潛力。2016年，Xu等[9]用DNA折紙折疊出一個可編程的DNA折紙平臺，用來組織用于膜融合的陷阱。2017年，Chikkaraddy等[10]利用DNA折紙技術(shù)，將單分子發(fā)射器組裝成等離子體納米粒子，成功繪制出納米熱點圖。同年，F(xiàn)an等[11]還利用DNA折紙構(gòu)建更高階結(jié)構(gòu)的支架。Tikhomirov等[12]利用正方形DNA折紙陣列的分型組裝得到了微米級蒙娜麗莎、公雞等圖案。Wagenbauer等[13]利用V形DNA折紙作為基本單元，通過控制基本單元之間的幾何形狀和作用，構(gòu)造更大的組裝體。2018年，Urban等[14]用DNA折紙組裝成等離子體環(huán)形超分子。

0-1規(guī)劃問題是整數(shù)規(guī)劃問題的特殊情形，其應用非常廣泛，是運籌學中的一個重要問題。許多NP完全問題也都可以轉(zhuǎn)化為0-1規(guī)劃問題。解決該問題的算法很多，如窮舉法、隱枚舉法等。2003年，殷志祥等[15]首次提出了一種基于熒光標記的策略，解決了簡單0-1規(guī)劃問題。2008年，楊靜[16]提出了基于三鏈DNA結(jié)構(gòu)的0-1整數(shù)規(guī)劃算法。2013年，任曉玲等[17]又改進了該算法，使得該算法對問題解的檢測更加有效。2017年，Li等[18]提出了一種新的基于自組裝納米探針的DNA計算模型。同年，殷志祥等[19]給出基于質(zhì)粒的DNA算法來解決特殊的整數(shù)規(guī)劃問題。朱建鵬[20]研究了特殊0-1整數(shù)規(guī)劃問題的DNA芯片模型。2018年，趙鑫月等[21]也是利用DNA折紙術(shù)，通過鏈之間的雜交反應形成二級結(jié)構(gòu)解決0-1規(guī)劃問題。

本文應用一種動態(tài)的DNA納米折紙結(jié)構(gòu)來解決0-1規(guī)劃問題。模型由三部分折紙結(jié)構(gòu)組裝而成，分別為DNA折紙卡槽、雙態(tài)DNA機器[22-23]、DNA行走機器人[24-25]。其中DNA折紙卡槽是由1條M13長鏈和202條DNA短鏈折疊而成的擁有3個插槽的折紙結(jié)構(gòu)，并且插槽的下方用固定的延伸單鏈形成了DNA行走機器人向前移動的“軌道”。雙態(tài)DNA機器由14條DNA單鏈折疊而成，它與插槽處延伸的單鏈互補，從而將雙態(tài)DNA機器固定在DNA折紙插槽內(nèi)形成折紙基底。3臺雙態(tài)DNA機器分別對應0-1規(guī)劃問題的3個約束變量，雙態(tài)DNA機器下方的一條單鏈用于攜帶或者不攜帶金納米顆粒，這對應于0-1規(guī)劃問題中約束變量取1或者取0。DNA行走機器人是7條單鏈折疊成的折紙結(jié)構(gòu)，且這7條鏈的3'端為粘性末端。這些粘性末端稱為DNA行走機器人的“手”和“足”。它與DNA折紙卡槽中的延伸單鏈互補，通過鏈置換使得DNA行走機器人以順時針旋轉(zhuǎn)，沿著DNA折紙基底上預先設(shè)計的“軌道”行走，每步旋轉(zhuǎn)120°。在“行走”的過程中，DNA行走機器人的“手”通過鏈置換將雙態(tài)DNA機器上修飾金納米顆粒的單鏈置換下來。通過6次旋轉(zhuǎn)、6步行走，DNA行走機器人能夠?qū)⑷?臺雙態(tài)DNA機器上連接金納米顆粒的單鏈全部置換出來。當整個動態(tài)行走過程結(jié)束，根據(jù)透射電鏡下DNA行走機器人接收的金納米顆粒的大小和個數(shù)判斷變量的取值是否為可行解。

2動態(tài)DNA折紙

動態(tài)DNA折紙包括3個DNA折紙結(jié)構(gòu)：DNA折紙卡槽（圖1（a））、雙態(tài)DNA機器（圖1（b））和DNA行走機器人（圖1（c））。DNA折紙卡槽由1條M13鏈和202條短鏈折疊而成，下方3個三角形共9條延伸的單鏈用來連接DNA行走機器人的“足”，構(gòu)成行走機器人行走的“軌道”，DNA折紙卡槽上方白色柜形方框為3個插槽，分別與雙態(tài)DNA機器PX1、PX2、PX3通過互補單鏈連接。圖1（b）是攜帶金納米顆粒的雙態(tài)DNA機器PX1，其中金納米顆粒用黃色表示，它可與DNA行走機器人的“手”發(fā)生鏈置換，將原先修飾在雙態(tài)DNA機器上的金納米顆粒置換至DNA行走機器人上。7條單鏈折疊成帶有粘性末端的DNA行走機器人，其中粘性末端H1～H3鏈為“手”，F(xiàn)1～F4為“足”，為了確保DNA行走機器人與雙態(tài)DNA機器進行鏈置換，“足”F4在插槽的正下方被固定。行走機器人的每步都需要順時針旋轉(zhuǎn)120°，從第一個插槽位置轉(zhuǎn)到第二個插槽需要走兩步。

圖1動態(tài)DNA折紙結(jié)構(gòu)

組裝后的動態(tài)DNA折紙如圖2所示，DNA行走機器人在圖2中表示為紅色三角形。

圖2 組裝后的動態(tài)DNA折紙結(jié)構(gòu)

圖3給出了DNA行走機器人從雙態(tài)DNA機器PX1上接收金納米顆粒的過程。行走機器人的“手”H1通過鏈置換將DNA機器上攜帶的金納米顆粒接收到行走機器人上。因為有3個雙態(tài)DNA機器，且DNA機器上可以攜帶或者不攜帶金納米顆粒，所以DNA行走機器人經(jīng)過3個插槽后會產(chǎn)生8種不同的金納米顆粒的組合，對應于簡單0-1規(guī)劃問題中所有變量可能的取值。圖3中A-1、A-2、A-4為加入的短鏈DNA片段，能夠通過堿基互補將DNA行走機器人的“足”固定在折紙基底上，從而接收雙態(tài)DNA機器修飾的金納米顆粒。

圖3 DNA行走機器人接收金納米顆粒示意圖

圖4給出了DNA行走機器人的行走過程。編號1-7分別為組成DNA機器人的7條單鏈DNA片段，粘性末端H1～H3為行走機器人的“手”，F(xiàn)4～F7為“足”。O-*為折紙基底上延伸出的9條單鏈，構(gòu)成了DNA行走機器人移動的3個站點，它同時對應折紙基底上方的插槽。A-*為9條DNA短鏈，它與DNA行走機器人的“足”F4～F7及O-*互補，作用是將行走機器人的“足”和折紙基底上的延伸短鏈O-*連接來綁定行走機器人，使得行走機器人能按照指定的“軌道”行走。FA-*為9條與A-*完全互補的短鏈，它能夠置換出行走機器人被綁定的“足”，從而解開行走機器人與折紙基底表面的連接。通過綁定與解綁，實現(xiàn)DNA行走機器人在折紙基底上預定的“軌道”行走。圖4給出了DNA行走機器人從第一個站點到第二個站點的行走過程。圖4左下表示行走機器人位于第一個站點，此時“足”F4和F5分別被單鏈A-1和A-2綁定于單鏈O-1和O-3上，“足”F7也被單鏈A-4綁定在單鏈O-2上，使得DNA行走機器人被固定，“手”H1位于靠近雙態(tài)DNA機器PX1的位置，可用來接收金納米顆粒。隨后加入FA-1和FA-4置換出鏈A-1和A-4，此時“足”F4和F7被解綁，“足”F5仍處于綁定狀態(tài)，加入單鏈A-3將“足”F6和O-4綁定，此時DNA行走機器人旋轉(zhuǎn)120°，相當于向前行走了一步，位于第一個站點和第二個站點中間，由于此時不在雙態(tài)DNA機器的下方，即不用接收金納米顆粒，故“足”F7無須綁定，如圖4中間。接下來加入單鏈FA-2將單鏈A-2置換出來，此時“足”F5與O-3解綁，只有“足”F6仍處于綁定狀態(tài)，再加入單鏈A-5將“足”F4與O-6綁定，由于此時位于雙態(tài)DNA機器PX2的下方，還需要加入單鏈A-6將“足”F7綁定于O-5上，“手”H2靠近DNA機器PX2，可以接收金納米顆粒。此時DNA行走機器人又旋轉(zhuǎn)了120°，相當于再向前移動了一步，位于第二個站點，如圖4右下。行走機器人從第二個站點移動到第三個站點與此類似。最后可以通過加入綁定鏈的互補鏈將DNA行走機器人的“足”全部解綁，將行走機器人置換出來。

圖4 DNA行走機器人行走示意圖

當DNA行走機器人經(jīng)過3個站點，將行走機器人所有的“足”全部解綁后，可通過透射電鏡觀察行走機器人上接收的金納米顆粒的情況。

3 簡單0-1規(guī)劃問題的動態(tài)折紙計算模型

在運籌學中，0-1規(guī)劃問題屬于整數(shù)規(guī)劃問題，是整數(shù)規(guī)劃的特殊情形，這種規(guī)劃的約束變量僅取值0或1。它的一般形式為：

其中aij為任意整數(shù)，ci,bj(i=1,2,…,m;j=1,2,…,n)為非負整數(shù)。本文利用動態(tài)DNA折紙求解如下簡單的0-1規(guī)劃問題。

簡單0-1規(guī)劃問題的動態(tài)折紙算法：

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

步驟2利用每一約束條件刪除非可行解（保留可行解），重復進行，得到問題的可行解。

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

對于一個含有n個變量x1,x2,…,xn和m個方程的方程組，對應算法的步驟如下：

步驟1首先折疊出2n種雙態(tài)DNA機器。把這2n種雙態(tài)DNA機器分成兩組，第一組的n種雙態(tài)DNA機器分別用不同大小的金納米顆粒修飾，每一個雙態(tài)DNA機器分別代表變量x1,x2,…,xn；第二組的n種雙態(tài)DNA機器在折紙結(jié)構(gòu)上和第一組的n種對應相同，但均不用金納米顆粒修飾，分別代表變量。這里xi對應的雙態(tài)DNA機器表示變量xi取值為1，而對應的雙態(tài)DNA機器表示變量xi取值為0。然后需要折疊出2n個相同的DNA折紙卡槽和2n個相同的DNA行走機器人，同時構(gòu)造出這2n種雙態(tài)DNA機器的不同2n個組合，每個組合包含n個變量所對應的雙態(tài)DNA機器，通過堿基互補的方式與DNA折紙卡槽的插槽處結(jié)合，組裝成2n個DNA折紙基底。

步驟2在每一個組裝好的DNA折紙基底中加入一個DNA行走機器人。首先用對應的短鏈將它固定在第一個雙態(tài)DNA機器的下方所對應的站點處，此時DNA行走機器人的“手”H1會與雙態(tài)DNA機器下方的延伸單鏈互補置換出此條單鏈，若這條單鏈5'端攜帶金納米顆粒即為x1(x1=1)，若這條單鏈5'端不攜帶金納米顆粒即為。然后依次加入相應的短鏈和互補短鏈來綁定和解綁相應的“足”，使得DNA行走機器人沿固定的“軌道”向前“行走”，經(jīng)過2n步后將DNA行走機器人置換出來。最后通過透射電鏡觀察置換出的DNA行走機器人所攜帶金納米顆粒的大小及個數(shù)，用第一個約束條件判斷并排除非解，對于已經(jīng)判斷為不滿足約束條件的后面都不再考慮，接著用第二個約束條件判斷并排除非解，如此重復進行，使得所有的m個約束條件都判斷結(jié)束。從而得到所有正解。

步驟3計算出各可行解所對應目標函數(shù)的值，進而判斷出最優(yōu)解。

4 實例分析

下面具體討論一個簡單0-1規(guī)劃問題。

步驟1生成變量的所有可能組合。由于實例中有3個約束變量，共有8種解的可能組合。首先利用DNA折紙術(shù)折疊出DNA折紙卡槽、雙態(tài)DNA機器和DNA行走機器人。將雙態(tài)DNA機器分成6組，前3組分別修飾5nm、7nm和10nm金納米顆粒，分別記為px1、px2和px3，分別對應于簡單0-1規(guī)劃問題中約束變量x=1,y=1和z=1；后3組不修飾金納米顆粒，分別記為，分別對應于簡單0-1規(guī)劃問題中約束變量x=0,y=0和z=0。對應于解的所有可能組合，取3種雙態(tài)DNA機器與DNA折紙卡槽組裝成為DNA折紙基底，一共8種。記這8種DNA折紙基底為0（0，0，0）、1（1，0，0）、2（0，1，0）、3（0，0，1）、4（1，1，0）、5（1，0，1）、6（0，1，1）、7（1，1，1）。DNA折紙基底組裝完成后將DNA行走機器人加入，并按以下順序加入相應的DNA短鏈：

（1）依次加入A-1、A-2、A-4，分別將“足”F4、F5、F7綁定在O-1、O-3、O-2上，待DNA機器人的“手”H1與雙態(tài)DNA機器PX1下端延伸單鏈發(fā)生鏈置換反應；

（2）依次加入A-1、A-4的補鏈FA-1、FA-4解開“足”F4、F7，再加入A-3將“足”F6綁定于O-4上；

（3）加入A-2的補鏈FA-2解開“足”F5，再依次加入A-5、A-6分別將“足”F4、F7綁定在O-6、O-5上，待DNA機器人的“手”H2與雙態(tài)DNA機器PX2下端延伸單鏈發(fā)生鏈置換反應；

（4）依次加入A-3、A-6的補鏈FA-3、FA-6解開“足”F6、F7，再加入A-7將“足”F5綁定于O-7上；

（5）加入A-5的補鏈FA-5解開“足”F4，再依次加入A-8、A-9分別將“足”F6、F7綁定在O-9、O-8上，待DNA機器人的“手”H3與雙態(tài)DNA機器PX3下端延伸單鏈發(fā)生鏈置換反應；

（6）依次加入A-7、A-8、A-9的補鏈FA-7、FA-8、FA-9解開“足”F5、F6、F7，將DNA行走機器人置換出來。

這里分步加入短鏈是為了讓DNA行走機器人沿預定的“軌道”行走，且有足夠的時間能夠接收金納米顆粒。經(jīng)過6步將DNA行走機器人置換出來，通過透射電鏡觀察DNA行走機器人所接收的金納米顆粒的大小及個數(shù)。

步驟2針對簡單0-1規(guī)劃問題的約束條件，刪除非可行解得到可行解。為了能直接通過DNA折紙技術(shù)獲得可行解，對上述DNA折紙模型進行優(yōu)化改進。

如圖5（a）所示，將DNA折紙卡槽增加一條延伸單鏈O-10或O-10*，其中O-10和O-10*為互補單鏈。對于每一個約束條件，非可行解的卡槽增加延伸單鏈O-10，可行解的卡槽增加延伸單鏈O-10*。

將上述步驟（6）作如下改動：依次加入A-7、A-9的補鏈FA-7、FA-9解開“足”F5、F7，此時F6仍綁定在O-9上，如圖5（b）所示。然后加入短鏈A-10，A-10與O-10通過部分互補將“足”F4綁定于O-10上。由于O-10與O-10*是互補鏈，A-10并不能將“足”F4與O-10*綁定。最后加入A-8的補鏈FA-8解開“足”F6。

圖5改進DNA折紙模型

此時，如果是不滿足約束條件的非可行解，DNA行走機器人的“足”F4仍綁定于O-10上無法完全置換出來；如果是滿足約束條件的可行解，由于“足”F4沒有被綁定，DNA行走機器人能夠被完全置換出來。通過透射電鏡能夠觀察到所有的可行解。

對于實例中第一個約束條件x+y+z≤2，DNA行走機器人所接收的5 nm、7 nm和10 nm金納米顆?？倲?shù)不多于2個，則滿足此約束條件的解為0（0，0，0）、1（1，0，0）、2（0，1，0）、3（0，0，1）、4（1，1，0）、5（1，0，1）、6（0，1，1）。

對于實例中第二個約束條件x+y≥1（不滿足第一個約束條件的后面不再考慮），DNA行走機器人所接收的5 nm和7 nm的金納米顆?？倲?shù)不少于1個，滿足此約束條件的解為1（1，0，0）、2（0，1，0）、4（1，1，0）、5（1，0，1）、6（0，1，1）。

類似地，對于實例中第三個約束條件y+z≤1，DNA行走機器人所接收的7 nm和10 nm金納米顆?？倲?shù)不多于1個，滿足此約束條件的解有4組，分別為1（1，0，0）、2（0，1，0）、4（1，1，0）、5（1，0，1），即為所求簡單0-1規(guī)劃問題的可行解。因此將0、3、6、7號DNA折紙卡槽的第十條延伸單鏈設(shè)計為O-10；1、2、4、5號DNA折紙卡槽的第十條延伸單鏈設(shè)計為O-10*。透射電鏡下解的示意圖如圖6所示。

圖6 所有可行解

步驟3該實例有4個可行解，分別為：

x=1,y=0和z=0,此時u=2；

x=0,y=1和z=0,此時u=1；

x=1,y=1和z=0,此時u=3；

x=1,y=0和z=1,此時u=5。

因為要求目標函數(shù)的最小值，所以x=0,y=1,z=0為該問題的最優(yōu)解，對應目標函數(shù)的值為1。

5 結(jié)束語

本次研究主要是鑒于近年來鏈置換技術(shù)在分子計算領(lǐng)域的相關(guān)應用。本文采用了DNA折紙結(jié)構(gòu)與金納米顆粒相結(jié)合組裝基底，通過鏈置換技術(shù)構(gòu)造動態(tài)的簡單0-1規(guī)劃問題的DNA計算模型。此DNA折紙模型具有高靈敏度、高特異性、可預測性和可編程性，用來解決0-1規(guī)劃問題不僅擺脫了試管，還極大地提高了效率，并且對于一個含有n個變量的約束方程組，產(chǎn)生所有可能結(jié)果的雙態(tài)DNA機器僅為2n種，大大簡化了實驗步驟，給實驗過程帶來極大的便利。金納米具有特殊的表面效應、體積效應、量子尺寸效應和宏觀量子隧道效應，使得金納米與生物體有著特殊的相互作用，并且金納米標記具有方法比較方便、標記后對生物分子的活性影響較小等優(yōu)點。本文僅對簡單的0-1規(guī)劃問題進行了詳細的討論，但是對于一般的0-1規(guī)劃問題來說，該方法求解還存在一定困難。首先當問題的變量增多時，折紙結(jié)構(gòu)將會更加復雜；其次當問題中n過大時，僅僅通過金納米顆粒的大小來判斷問題的解具有一定困難，因此需要更多具有標記性的結(jié)構(gòu)。相信隨著分子生物學及生物工程，特別是DNA折紙技術(shù)的進一步發(fā)展，此模型也能應用于求解一般的0-1規(guī)劃問題，甚至解決一般的整數(shù)規(guī)劃問題也將成為現(xiàn)實。