陳 哲，殷志祥，唐 震

（1.安徽理工大學(xué)數(shù)學(xué)與大數(shù)據(jù)學(xué)院，安徽淮南232001；2 上海工程技術(shù)大學(xué)數(shù)理與統(tǒng)計(jì)學(xué)院，上海201620）

DNA 折紙術(shù)和DNA 分子一直是科學(xué)家們研究的重點(diǎn)。1994 年Adleman 第一次利用DNA 編碼解決了有向圖的Hamilton 路徑問(wèn)題，之后，DNA 計(jì)算這一利用DNA 分子的特性來(lái)計(jì)算一些難計(jì)算問(wèn)題（如0-1 整數(shù)規(guī)劃問(wèn)題，可滿(mǎn)足問(wèn)題，最大團(tuán)問(wèn)題）的新型計(jì)算領(lǐng)域迅速成為了熱點(diǎn)研究領(lǐng)域[1-7]。20 世紀(jì)80 年代，Seeman 首先提出利用堿基互補(bǔ)配對(duì)的原則可將DNA 組裝成復(fù)雜的空間結(jié)構(gòu)為后來(lái)的DNA 計(jì)算打下了堅(jiān)實(shí)的基礎(chǔ)[8-10]。在最初的DNA 計(jì)算中，更多的是對(duì)DNA分子進(jìn)行特定的編碼來(lái)完成計(jì)算。隨著生物技術(shù)的發(fā)展，DNA 鏈置換因其反應(yīng)的操作性強(qiáng)、實(shí)現(xiàn)條件簡(jiǎn)單、產(chǎn)物可預(yù)見(jiàn)等優(yōu)點(diǎn)被廣泛運(yùn)用于DNA計(jì)算中。2006 年，Rothemund 開(kāi)發(fā)了一種新的DNA 自組裝技術(shù)，稱(chēng)為DNA 折紙術(shù)。他們選用噬菌體DNA M13mp18 作為長(zhǎng)鏈，然后用兩百多條短的單鏈DNA 通過(guò)堿基互補(bǔ)配對(duì)原則，將長(zhǎng)鏈折疊了矩形、三角形、五角星、笑臉，甚至還有世界地圖，等等[11-13]。2011 年，錢(qián)璐璐等人構(gòu)建了一種生化電路，這種基于DNA 鏈置換的生化電路可以用來(lái)求解四位二進(jìn)制數(shù)平方根[13]。同年Yan 課題組在Science 上以封面論文形式發(fā)表了可精確控制三維曲面的立方體花瓶結(jié)構(gòu)，將DNA 折紙術(shù)在結(jié)構(gòu)設(shè)計(jì)與制造方面的研究推向了高潮[14]。2017年，Li 構(gòu)建了一種自組裝納米探針的0-1 規(guī)劃問(wèn)題的計(jì)算模型，該模型是由兩條帶有熒光分子的DNA 單鏈硫化在納米金顆粒上構(gòu)成的。常規(guī)狀態(tài)下，熒光分子會(huì)被吸附到納米金顆粒的表面，熒光呈淬滅狀態(tài)，當(dāng)加入目標(biāo)DNA 鏈后，通過(guò)DNA鏈置換，目標(biāo)DNA 鏈會(huì)和吸附在納米金顆粒上的DNA 鏈互補(bǔ)，從而將熒光分子從納米金顆粒上分離開(kāi)，熒光分子呈熒光狀態(tài)[15]。

本文利用DNA 鏈置換技術(shù)構(gòu)建了一種解決可滿(mǎn)足性問(wèn)題的模型，可滿(mǎn)足問(wèn)題的約束條件被映射成計(jì)算模型上的熒光個(gè)數(shù)，通過(guò)DNA 鏈置換反應(yīng)，觀(guān)察計(jì)算模型上的熒光個(gè)數(shù)找出可滿(mǎn)足性問(wèn)題的可行解，同時(shí)給出一個(gè)實(shí)例來(lái)解讀該模型。

1 可滿(mǎn)足性問(wèn)題和DNA 鏈置換

1.1 可滿(mǎn)足性問(wèn)題

可滿(mǎn)足性問(wèn)題是一個(gè)經(jīng)典的NP 完全問(wèn)題，它在邏輯電路的設(shè)計(jì)及密碼問(wèn)題的研究中都有廣泛的應(yīng)用。通常SAT 問(wèn)題可以表述為：給定一個(gè)布爾表達(dá)式

其中Ci=V1∨V2∨…Vm為布爾變量，取值為0 和1，“∧”為邏輯“合取”，“∨”為邏輯“析取”。SAT問(wèn)題就是使得F=1 的所有布爾變量Vi的真值分配表。顯然，對(duì)于有n個(gè)變量的布爾公式F有2n個(gè)可能的賦值。

1.2 DNA 鏈置換

DNA 鏈置換指的是1 條DNA 單鏈置換出部分復(fù)合物中原綁定鏈的反應(yīng)過(guò)程，是一種DNA 分子間的自發(fā)反應(yīng)。鏈置換反應(yīng)的原理是：由于DNA 單鏈的長(zhǎng)度不同，形成雙螺旋結(jié)構(gòu)的結(jié)合力也有所差異。由較強(qiáng)結(jié)合力的輸出鏈置換掉部分互補(bǔ)結(jié)構(gòu)中結(jié)合力較弱的DNA 鏈。簡(jiǎn)單的理解：較長(zhǎng)DNA 鏈取代較短的DNA 鏈，并且被替代的鏈作為輸出信號(hào)以實(shí)現(xiàn)分子邏輯運(yùn)算等操作。DNA 鏈置換基本過(guò)程示意圖見(jiàn)圖1。

圖1 DNA 鏈置換基本反應(yīng)原理

2 基于DNA 鏈置換的可滿(mǎn)足性問(wèn)題的計(jì)算模型

2.1 模型的設(shè)計(jì)

對(duì)于可滿(mǎn)足問(wèn)題中的任意變量xi，與之對(duì)應(yīng)的設(shè)計(jì)圖2 所示的計(jì)算模型，對(duì)于n個(gè)變量，這樣的計(jì)算模型共有n個(gè)。計(jì)算模型是將一個(gè)納米顆粒固定在兩條DNA 鏈硫化上，其中的一條鏈?zhǔn)怯蒐i-Xi部分互補(bǔ)構(gòu)成的DNA 鏈，Li上帶有熒光分子；另一條是與Li鏈完全互補(bǔ)的DNA 單鏈DNA 單鏈上帶有熒光淬滅分子。常規(guī)狀態(tài)下，該計(jì)算模型熒光呈明亮狀態(tài)。

圖2 基于DNA 鏈置換的可滿(mǎn)足性問(wèn)題的計(jì)算模型示意圖

2.2 基于DNA 鏈置換的可滿(mǎn)足性問(wèn)題的計(jì)算模型的生物算法

設(shè)計(jì)思路：將可滿(mǎn)足性問(wèn)題中變量的兩種取值映射成熒光分子明滅的兩種狀態(tài)，當(dāng)xi=0 時(shí)，映射成熒光分子淬滅，當(dāng)xi=1 時(shí)，熒光分子明亮。為了實(shí)現(xiàn)這一目的，對(duì)于任意的xi=0,設(shè)計(jì)對(duì)應(yīng)的DNA 鏈23，它與模型中的DNA 鏈xi完全互補(bǔ)，熒光分子和熒光淬滅分子相遇，導(dǎo)致熒光淬滅，見(jiàn)圖3（a）。對(duì)于任意的xi=1，設(shè)計(jì)對(duì)應(yīng)的DNA 鏈xi，它與模型中的DNA 鏈xi一模一樣，添加xi后，不發(fā)生任何反應(yīng)，熒光保持明亮狀態(tài)，見(jiàn)圖3（b）。

圖3 xi=0 和xi=1對(duì)應(yīng)的反應(yīng)示意圖

基于DNA 鏈置換的可滿(mǎn)足性問(wèn)題的計(jì)算模型生物算法如下：

1）對(duì)于含n個(gè)變量（x1,x2,…,xn）和m個(gè)約束條件的可滿(mǎn)足性問(wèn)題，它的所有可能解是2n個(gè)，對(duì)應(yīng)的是2n個(gè)不同組合的DNA 鏈。

2）構(gòu)造對(duì)應(yīng)變量的計(jì)算模型（n個(gè)），放入2n個(gè)試管中。在每個(gè)試管中加入一組DNA 鏈，在室溫下進(jìn)行DNA 鏈置換反應(yīng)。

3）對(duì)于第一個(gè)約束方程，它的約束條件被映射成熒光個(gè)數(shù)。通過(guò)熒光檢測(cè)，就可以得到滿(mǎn)足第一個(gè)約束方程的可行解。重復(fù)此步驟，就可以得到滿(mǎn)足所有約束方程的可行解。

4）利用目標(biāo)函數(shù)計(jì)算出各可行解對(duì)應(yīng)的目標(biāo)函數(shù)值，進(jìn)而判斷出最優(yōu)解。

2.3 實(shí)例分析

下面來(lái)看一組具體的實(shí)例：

步驟1：對(duì)于含3 個(gè)變量（x1,x2,x3）和3 個(gè)約束條件的可滿(mǎn)足性問(wèn)題，它的所有可能解是23個(gè)，分別是1(1,1,1)，2(0,1,1), 3(1,0,1), 4(1,1,0), 5(0,0,1), 6(0,1,0), 7(1,0,0), 8((0,0,0)。對(duì)應(yīng)的是23個(gè)不同組合的DNA 鏈，比如1 號(hào)解（1,1,1）對(duì)應(yīng)的DNA 鏈組合是x1-x2-x3，2 號(hào)解(0,1,1)，對(duì)應(yīng)的DNA 鏈組合是，3 號(hào)解（1,0,1）對(duì)應(yīng)的DNA 鏈組合是，4 號(hào)解（1,1,0）對(duì)應(yīng)的DNA 鏈組合是，8 號(hào)解（0,0,0）對(duì)應(yīng)的DNA 鏈組合是

步驟2：構(gòu)造對(duì)應(yīng)變量的計(jì)算模型（3 個(gè)，見(jiàn)圖4），放入8 個(gè)試管中。在每個(gè)試管中加入一組DNA 鏈，在室溫下進(jìn)行DNA 鏈置換反應(yīng)，其中1，2，3，4 號(hào)解的反應(yīng)示意圖分別如圖5～8 所示。

圖4 3 變量計(jì)算模型示意圖

圖5 1 號(hào)解（1，1，1）反應(yīng)示意圖

步驟3：對(duì)于第一個(gè)約束方程，它的約束條件是大于等于1，映射成熒光個(gè)數(shù)就是熒光個(gè)數(shù)大于等于1 的DNA 鏈組是滿(mǎn)足第一個(gè)約束方程的解，據(jù)此得到滿(mǎn)足第一個(gè)約束條件的可行解是1，2，3，4，6，7 號(hào)解；對(duì)于第二個(gè)約束方程，因?yàn)椴簧婕白兞縳2，所以綠色熒光不考慮，它的約束條件映射成綠色熒光外，剩余熒光顏色個(gè)數(shù)大于等于1 的DNA 鏈組是滿(mǎn)足第二個(gè)約束方程的解，它們是1，2，3，4，5，7 號(hào)解；對(duì)于第三個(gè)約束方程，現(xiàn)在只判斷1，2，3，4，7 號(hào)解，因?yàn)椴簧婕白兞縳1，所以紅色熒光不考慮，剩余熒光顏色個(gè)數(shù)大于等于1 的DNA 鏈組是滿(mǎn)足第三個(gè)約束方程的解，它們是1，2，3，4。

步驟4：經(jīng)過(guò)以上步驟后得到可滿(mǎn)足所有約束方程的可行解，比較其目標(biāo)函數(shù)即可求出該可滿(mǎn)足問(wèn)題的最優(yōu)解。

圖6 2 號(hào)解（0，1，1）反應(yīng)示意圖

圖7 3 號(hào)解（1，0，1）反應(yīng)示意圖

圖8 4 號(hào)解（1，1，0）反應(yīng)示意圖

3 小結(jié)

本文構(gòu)建了一個(gè)基于DNA 鏈置換反應(yīng)的可滿(mǎn)足問(wèn)題的計(jì)算模型，將可滿(mǎn)足問(wèn)題中變量的取值設(shè)計(jì)成不同的DNA 鏈，通過(guò)DNA 鏈置換反應(yīng)，觀(guān)察最后的計(jì)算模型上的熒光個(gè)數(shù)找出可滿(mǎn)足問(wèn)題的可行解。由于DNA 鏈置換反應(yīng)條件簡(jiǎn)單、產(chǎn)物量高，所以該計(jì)算模型具有一定的可行性，而且最后的結(jié)果通過(guò)熒光檢測(cè)來(lái)觀(guān)察反應(yīng)的結(jié)果，操作簡(jiǎn)單、結(jié)果準(zhǔn)確。