基于DNA鏈置換的可滿足性問題的計(jì)算模型

陳 哲，殷志祥，唐 震

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

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

1 可滿足性問題和DNA 鏈置換

1.1 可滿足性問題

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

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

1.2 DNA 鏈置換

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

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

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

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

對于可滿足問題中的任意變量xi，與之對應(yīng)的設(shè)計(jì)圖2 所示的計(jì)算模型，對于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 鏈置換的可滿足性問題的計(jì)算模型示意圖

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

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

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

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

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

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

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

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

2.3 實(shí)例分析

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

步驟1：對于含3 個(gè)變量（x1,x2,x3）和3 個(gè)約束條件的可滿足性問題，它的所有可能解是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)。對應(yīng)的是23個(gè)不同組合的DNA 鏈，比如1 號解（1,1,1）對應(yīng)的DNA 鏈組合是x1-x2-x3，2 號解(0,1,1)，對應(yīng)的DNA 鏈組合是，3 號解（1,0,1）對應(yīng)的DNA 鏈組合是，4 號解（1,1,0）對應(yīng)的DNA 鏈組合是，8 號解（0,0,0）對應(yīng)的DNA 鏈組合是

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

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

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

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

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

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

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

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

3 小結(jié)

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