0-1整數(shù)規(guī)劃問題的DNA四面體步行者計算模型

楊新木，楊 靜*，殷志祥，唐 震，崔建中

(1.安徽理工大學(xué) 數(shù)學(xué)與大數(shù)據(jù)學(xué)院，安徽 淮南 232001；2.上海工程技術(shù)大學(xué) 數(shù)理與統(tǒng)計學(xué)院，上海 201620；3.安徽理工大學(xué) 電氣與信息工程學(xué)院，安徽 淮南 232001；4.淮南聯(lián)合大學(xué) 計算機(jī)系，安徽 淮南 232001)

近年來由于科技高速發(fā)展，傳統(tǒng)的電子計算機(jī)存儲量小，計算速度不夠快，科學(xué)家們正努力尋找其他運(yùn)算速度更快。存儲量更大的新型計算機(jī)，如量子計算機(jī)、人工神經(jīng)網(wǎng)絡(luò)計算機(jī)等。1994年，美國加利福尼亞大學(xué)Adleman[1]博士利用DNA編碼解決了圖論中的NP完全問題——有向圖的Hamilton路徑問題。分子自組裝的原理是利用分子與分子或者分子中某一片段與另一片段的分子識別，相互通過非共價作用形成具有特定排列順序的分子聚合體。DNA分子結(jié)構(gòu)特征和獨(dú)特的分子間的相互作用，非常適合作為自組裝的材料，可以合成一系列具有復(fù)雜結(jié)構(gòu)的物質(zhì)。2006年，Rothemund[2]提出了一種全新的DNA自組裝的方法——DNA折紙術(shù)，通過DNA折紙術(shù)，Rothemun得到了三角形、方形、矩形、五角星、笑臉等精細(xì)復(fù)雜的二維結(jié)構(gòu)，如圖1所示。2010年，Pei[3]等人首次構(gòu)建出新型三維納米結(jié)構(gòu)的DNA探針自組裝平臺，該平臺具有合成簡單，穩(wěn)定性好和產(chǎn)率高等優(yōu)點。2017年，Tikhomirov[4]采用微米級DNA折紙陣列，成功描摹蒙娜麗莎和公雞等圖像，并發(fā)現(xiàn)自組裝成陣列不受瓦片表面圖案變化的影響。2019年，晁潔等[5]利用DNA自組裝設(shè)計了一種DNA導(dǎo)航器系統(tǒng)，該系統(tǒng)可以在二維DNA折紙平臺上定義的十個頂點根樹上執(zhí)行單分子并行深度優(yōu)先搜索。

圖1 DNA折紙術(shù)圖形

本文利用DNA折紙術(shù)[6]構(gòu)建一個DNA四面體步行者，并將其應(yīng)用于求解0-1整數(shù)規(guī)劃問題。該模型利用DNA折紙術(shù)和探針技術(shù)，可以大大降低普通的自組裝模型所造成的困擾，從而進(jìn)一步提升DNA計算模型的準(zhǔn)確性。

1 DNA折紙術(shù)和0-1整數(shù)規(guī)劃

1.1 DNA折紙術(shù)和DNA四面體

1.1.1 DNA折紙術(shù)

DNA具有結(jié)構(gòu)穩(wěn)定、易識別、容易操作等優(yōu)點，一直是科學(xué)家們研究的熱點。DNA折紙術(shù)的原理是將一條較長的DNA單鏈(通常稱為腳手架鏈)與經(jīng)過一系列步驟設(shè)計的較短的DNA片段(通常稱為訂書釘鏈)，通過堿基互補(bǔ)配對原則能夠可控地構(gòu)造出高度復(fù)雜的納米圖案或結(jié)構(gòu)，在新興的納米領(lǐng)域中具有廣泛的潛在應(yīng)用。DNA折紙術(shù)與傳統(tǒng)的DNA自組裝相比，更容易組合出結(jié)構(gòu)穩(wěn)定、高度復(fù)雜的納米結(jié)構(gòu)，并具有納米可尋址性。Shih[7]等人采用DNA折紙術(shù)的方法，首次制造出三維結(jié)構(gòu)，揭開三維納米DNA結(jié)構(gòu)自組裝的序幕。Ke[8]等人設(shè)計出一個空心四面體立體結(jié)構(gòu)。Han[9]等設(shè)計和構(gòu)建自組裝DNA納米結(jié)構(gòu)，利用DNA折紙術(shù)組裝了一系列具有高曲率DNA納米結(jié)構(gòu)。Zhang[10]等人利用DNA折紙術(shù)構(gòu)建出具有高度復(fù)雜性和可編程性的有限尺寸線框DNA納米結(jié)構(gòu)。Gopinath[11]等人利用DNA折紙術(shù)定向自組裝到光刻圖案的結(jié)合位點上，使分子發(fā)射器與光子晶體腔可靠且可控地耦合。Tang[12]等利用DNA折紙術(shù)建立了動態(tài)與非門計算模型。同年，王飛[13]等人利用DNA折紙術(shù)相繼提出多種維度不同模式的熒光陣列構(gòu)建方案，在生物傳感、新型熒光探針設(shè)計等領(lǐng)域得到廣泛應(yīng)用。

1.1.2 DNA四面體

DNA四面體結(jié)構(gòu)是利用DNA折紙術(shù)通過巧妙的DNA序列設(shè)計，應(yīng)用互補(bǔ)配對原則，各鏈自動雜交組合而成的具有四面體形狀的DNA三維納米結(jié)構(gòu)，如圖2。

圖2 DNA四面體結(jié)構(gòu)

Ke[8]等利用DNA折紙術(shù)構(gòu)造了DAN四面體籠，該四面體通過4個三角形的平面進(jìn)行封閉，三角形的每條邊大約是54 nm。它是由多條訂書釘鏈和一條支架DNA雜交，而非彼此雜交，因此反應(yīng)對計量關(guān)系的精確度要求相對較低，這可以顯著提高組裝的成功率和產(chǎn)量。Li[14]等設(shè)計出一種基于DNA四面體的DNA芯片和一種通用的基于DNA四面體的微陣列平臺，用于檢測不同類型的生物活性分子，體現(xiàn)了DNA四面體在生物傳感器方面應(yīng)用的潛能。林美華[15]設(shè)計一種四面體DNA納米結(jié)構(gòu)探針應(yīng)用于生物傳感器當(dāng)中，該DNA四面體表面不僅探針多而且還能夠精確的控制探針之間的距離，具有傳質(zhì)速率快，靈敏度高等優(yōu)點。樊春海[16]等人基于DNA納米結(jié)構(gòu)設(shè)計的生物傳感器，可以對蛋白質(zhì)、核酸、小分子以及細(xì)胞的高靈敏監(jiān)測，并能保持優(yōu)異的檢測性。Yang等[17]人先利用折紙術(shù)構(gòu)建DNA四面體，再利用DNA四面體作為基底構(gòu)建探針，去解決0-1整數(shù)規(guī)劃問題。該模型能夠降低偽解的產(chǎn)生，提高求解效率。DNA四面體在分子診斷、分子輸送和藥物靶向治療等方面具有良好的應(yīng)用前景。

1.2 0-1整數(shù)規(guī)劃

整數(shù)規(guī)劃是從1958年由戈莫里[18]提出割平面法之后形成獨(dú)立分支的。整數(shù)規(guī)劃是線性規(guī)劃的重要部分。整數(shù)規(guī)劃的一種特殊情形是0-1規(guī)劃，即變量只取0或1兩種的整數(shù)規(guī)劃問題。許多的NP完全問題也都可以轉(zhuǎn)化為0-1規(guī)劃問題。但是到目前為止任然沒有非常好的算法來解決這種問題。

有不少學(xué)者先后利用DNA計算嘗試解決0-1規(guī)劃問題。首次取得突破性進(jìn)展是殷志祥[19]提出基于表面的DNA計算模型求解一般形式的0-1整數(shù)規(guī)劃問題。朱建鵬等[20]人利用DNA芯片的獨(dú)特優(yōu)勢，針對特殊的0-1規(guī)劃給出了DNA計算模型。趙鑫月等[21]人利用DNA折紙術(shù)構(gòu)造訂書釘鏈，與反應(yīng)溶液中的腳手架鏈形成二級結(jié)構(gòu)，求解0-1整數(shù)規(guī)劃問題，該方法容易操作，具有很強(qiáng)的并行性。

1.3 0-1整數(shù)規(guī)劃問題的基本算法

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

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

步驟3：生成生余解；

步驟4：重復(fù)進(jìn)行步驟2、3。我們可以排除所有的非解，從而得到問題的所有可行解；

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

2 0-1整數(shù)規(guī)劃問題的DNA四面體步行者計算模型

2.1 生物算法

步驟1：通過DNA探針找出0-1整數(shù)規(guī)劃問題的所有可能解；

步驟2：通過熒光個數(shù)找出第一個滿足約束條件的可行解；

步驟3：進(jìn)一步通過納米金顆粒個數(shù)找到同時滿足第一個和第二個約束條件的可行解；

步驟4：重復(fù)上述步驟，直到找到所有滿足約束條件的可行解；

步驟5：通過目標(biāo)函數(shù)，在所有可行解中找出0-1整數(shù)規(guī)劃問題的最優(yōu)解。

2.2 DNA四面體步行者

利用折紙術(shù)構(gòu)建DNA四面體步行者，將底邊三個DNA單鏈和DNA四面體固定，分別用F1、F2、F3表示這3個“足”。然后將一段DNA單鏈其固定在DNA四面體的頂點上作為探針，用于檢測與其互補(bǔ)的核酸序列。本文探針分為3個DNA單鏈小片段，分別用表示，如圖3(a)。如圖3(b)是一個完整的DNA折紙卡槽，DNA折紙卡槽中包含有3組助行器，每組助行器分別用A1、A2、A3表示，并且A1、A2、A3固定在折紙基底上面?？拷麯NA折紙卡槽頂端有3個載著相同的納米金顆粒的DNA機(jī)器，它通過堿基互補(bǔ)配對原理固定在DNA折紙卡槽頂端。3個相同的DNA機(jī)器與 3個不同的 DNA 片段（x，y，z）部分互補(bǔ)，3個不同的DNA片段可以攜帶也可以不攜帶納米金顆粒。其中DNA四面體上的探針與完全互補(bǔ)，DNA四面體上的探針與完全互補(bǔ)，DNA四面體上的探針與完全互補(bǔ)。

圖3 DNA四面體步行者和DNA折紙卡槽

2.3 DNA四面體步行原理

DNA四面體的3個“足”與DNA鏈A1、A2、A3部分互補(bǔ)DNA鏈A1、A2、A3固定在DNA折紙基底上。首先，DNA四面體的2個“足”F1、F2與DNA鏈A1、A2部分互補(bǔ)，還有一個“足”F3是自由足，詳細(xì)過程見圖4(a)。首先加入DNA鏈和，其中DNA鏈與DNA鏈A1完全互補(bǔ)、DNA鏈與DNA鏈A2完全互補(bǔ)、DNA鏈與DNA鏈A3完全互補(bǔ)。然后DNA鏈與A1通過DNA鏈置換成功把“足”F1解鏈，F(xiàn)1變?yōu)樽杂伞白恪?，此時DNA鏈A3與“足”F3鏈發(fā)生堿基互補(bǔ)配對，相當(dāng)于把足“F3”固定在折紙基底上，DNA四面體步行者往前行走一步并且逆時針旋轉(zhuǎn)，見圖4(a)(b)。經(jīng)過一段時間讓其完全反應(yīng)，其次在加入DNA鏈和A1，DNA鏈與A2發(fā)生鏈置換成功的把“足”F2解鏈，F(xiàn)2變?yōu)樽杂伞白恪?，此時DNA鏈A1與“足”F1鏈發(fā)生堿基互補(bǔ)配對，相當(dāng)于把足“F1”固定在折紙基底上，DNA四面體步行者往前行走一步并且逆時針旋轉(zhuǎn)，見圖4(b)(c)。經(jīng)過一段時間讓其完全反應(yīng)，最后再加入DNA鏈和A2，DNA鏈與A3發(fā)生鏈置換成功的把“足”F3解鏈，“足”F3變?yōu)樽杂伞白恪保珼NA鏈A2與“足”F2鏈發(fā)生堿基互補(bǔ)配對，相當(dāng)于把足“F2”固定在折紙基底上DNA四面體步行者往前行走一步并且逆時針旋轉(zhuǎn)，見圖4(c)(d)。重復(fù)以上過程，DNA步行者可以在DNA折紙基底上以逆時針120°完成行走。DNA四面體步行者在折紙卡槽中步行一周如圖5。

圖4 DNA四面體步行者原理圖

圖5 折紙卡槽中DNA四面體步行者過程圖

2.4 實例分析

討論如下0-1整數(shù)規(guī)劃的DNA計算模型。

步驟1：生成變量的所有的可能解。因為實例分析中的0-1整數(shù)規(guī)劃問題含有3個變量，每個變量都有2種取值（0或1），所以一共有23個可能解。首先利用DNA折紙術(shù)折疊出帶有探針的DNA四面體步行者和DNA折紙卡槽，DNA折紙卡槽中固定有3個助行者和3個相同的DNA機(jī)器，DNA 機(jī)器與不同 DNA 片段（x，y，z）部分互補(bǔ)，DNA片段可以攜帶納米金顆粒也可以不攜帶納米金顆粒，故共有23種可能，并且DNA片段（x，y，z）攜帶的納米金顆粒分別與DNA四面體上的探針x*,y*,z*完全互補(bǔ)。探針上攜帶有納米金顆粒記為1，沒有攜帶納米金顆粒的記為0。

步驟2：用23個DNA四面體步行者在載有不同的DNA折紙卡槽的折紙基底行走，經(jīng)過一段時間，可得到該問題的所有可能解。如2號解，DNA機(jī)器上只有DNA片段x攜帶納米金顆粒，DNA片段y和z都不攜帶納米金顆粒，DNA四面體步行者在助行器上面步行一周，最后探針上只有x攜帶有納米金顆粒，所以x取1，y和z都取0，這樣就得到2號解，詳細(xì)過程見圖6。類似地，可得到(x,y,z)取值的所有可能解，分別為1號解(0,0,0)、2 號解(1,0,0)、3 號解(0,1,0)、4 號解(0,0,1)、5 號解(1,1,0)、6 號解(1,0,1)、7 號解(0,1,1)、8 號解(1,1,1)。這8種可能解對應(yīng)的DNA四面體步行者所攜帶的納米金顆粒的個數(shù)和位置如圖7。

圖6 2號解的示意圖

圖7 8種可能解

步驟3：刪除不滿足約束條件的解。對第一個約束條件，DNA四面體探針上的納米金顆粒要大于等于 2，滿足條件的有 5，6，7，8 號解；對第二個約束條件，由于約束條件不涉及變量y，所以y位置中的納米金顆粒不再考慮。只考慮5，6，7，8號解，DNA四面體上的探針x和z的納米金顆粒數(shù)量要小于等于1，即為滿足第二個約束條件的可行解，它們是5或7號解；對第三個約束條件，只考慮5，7號解，只要考慮DNA四面體上的探針y和z的納米金顆粒數(shù)量要小于等于1，即為滿足第三個約束條件的可行解，即5號解，同時也滿足第一個和第二個約束條件，所以可行解只能是5號解。

步驟4：得到滿足該約束條件的可行解，實例分析中的可行解只有5號解，同時也是唯一解，5號解也是最優(yōu)解，目標(biāo)函數(shù)的最小值為5。5號解得結(jié)構(gòu)示意圖如圖8。

圖8 解的示意圖

2.5 復(fù)雜度分析

模型的復(fù)雜度通常包括時間復(fù)雜度和空間復(fù)雜度。時間復(fù)雜度通常與其生化反應(yīng)時間有關(guān)，由于生化反應(yīng)具有很高的并行性，這是傳統(tǒng)計算機(jī)所不具備的能力。空間復(fù)雜度通常與其計算深度有關(guān)。該模型中使用的DNA短鏈數(shù)與變量的表示形式和變量數(shù)有關(guān)，模型的計算深度與模型的約束有關(guān)，因此模型的復(fù)雜度與變量n呈線性關(guān)系。以上分析表明，該模型大大降低了整數(shù)規(guī)劃問題的復(fù)雜度，是一種較為有效的模型。

3 小結(jié)

本文基于DNA折紙術(shù)設(shè)計了一個DNA四面體步行者計算模型，結(jié)合DNA鏈置換和納米金顆粒來搜尋0-1整數(shù)規(guī)劃問題的最優(yōu)解。DNA折紙術(shù)和DNA鏈置換是DNA自組裝中最重要的兩種技術(shù)手段?；贒NA折紙術(shù)和DNA鏈置換所設(shè)計的計算模型，有如下優(yōu)點：首先，結(jié)構(gòu)簡單，可以解決多個變量的0-1整數(shù)規(guī)劃問題，具有很好的通用性。其次，DNA四面體上的探針具有高度特異性、高度靈敏性、較好的可控性，而且效率高，沒有副產(chǎn)物，錯誤率非常低。最后，用納米金顆粒易于標(biāo)記并且對DNA鏈置換幾乎沒有任何影響，很容易觀察到最后DNA四面體上的探針上的納米金顆粒的位置。