動(dòng)態(tài)DNA步行者折紙計(jì)算模型
——求解可滿足性問題

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

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

一、引言

2006 年，Rothemund 等首次提出 DNA 折紙術(shù)[1]，該方法不同于傳統(tǒng)自組裝（自上而下的組裝），而是將一條長M13mp18噬菌體DNA鏈作為腳手架鏈來回折疊,并利用200多條訂書釘鏈將形狀固定。成功得到了正方形、矩形、五角星、笑臉和三角形等精細(xì)復(fù)雜的二維結(jié)構(gòu)，隨后許多更加復(fù)雜多樣的納米結(jié)構(gòu)[2-3]不斷被設(shè)計(jì)并組裝出來。Andersen E S 和錢璐璐等分別用DNA 折紙術(shù)折疊出海豚結(jié)構(gòu)的?；誟4]和中國地圖[5]。文獻(xiàn)[6]用DNA折紙折疊出光學(xué)超分子自組裝的支架。文獻(xiàn)[7]利用DNA折紙自組裝折疊出蒙娜麗莎、公雞等圖案。文獻(xiàn)[8]構(gòu)建了一個(gè)可編程的DNA折紙平臺(tái)，用來組織用于膜融合的陷阱。文獻(xiàn)[9]用DNA折紙納米結(jié)構(gòu)使腫瘤細(xì)胞中的細(xì)胞攝取和轉(zhuǎn)移可視化。

鏈置換技術(shù)是利用DNA 分子單鏈間的粘貼，通過加入輸入鏈來釋放另一條DNA 鏈。這種技術(shù)具有自引發(fā)性，靈敏性和準(zhǔn)確性等特點(diǎn)。2000年，文獻(xiàn)[10]率先在DNA納米技術(shù)上使用立足點(diǎn)鏈置換反應(yīng)。隨后，文獻(xiàn)[11]利用DNA鏈置換，構(gòu)建了一種可以反復(fù)讀取和輸入的存儲(chǔ)器。文獻(xiàn)[12]介紹了基于DNA鏈置換反應(yīng)的編碼器邏輯運(yùn)算模型研究。文獻(xiàn)[13-15]利用DNA鏈置換分別設(shè)計(jì)了不同的邏輯門模型。

Seeman 和 Sherman 于 2004 年推 出的第 一款 DNA 步行者是設(shè)計(jì)用來沿著一條一維（1D）軌道行走的，該軌道由三股突出的單鏈DNA 構(gòu)成[16]。DNA 步行者也可以在由DNA折紙或DNA修飾的平面組成的二維軌道上移動(dòng)。第一個(gè)二維DNA 步行者的例子是DNA 蜘蛛[17]。最近還引入了在三維軌跡上橫穿的隨機(jī)DNA步行者[18,19]。2010年，文獻(xiàn)[20]設(shè)計(jì)了三手四足的DNA步行者，利用鏈置換驅(qū)動(dòng)DNA步行者沿軌道順時(shí)針行走，運(yùn)輸金納米顆粒。文獻(xiàn)[21]將DNA步行者應(yīng)用于解決Petri網(wǎng)問題。文獻(xiàn)[22-25]主要將DNA步行者應(yīng)用到傳感器中，能夠?qū)崿F(xiàn)信號(hào)的放大作用。文獻(xiàn)[26,27]詳細(xì)介紹了DNA步行者的研究進(jìn)展與新興生物分析應(yīng)用。

布爾可滿足性問題（簡稱SAT問題）是一個(gè)著名的判定問題，不僅在數(shù)理邏輯和計(jì)算理論等方面有著舉足輕重的研究地位，而且在實(shí)際生產(chǎn)領(lǐng)域具有很高的應(yīng)用價(jià)值。1995年P(guān)rinceton大學(xué)的Lipton通過DNA計(jì)算解決可滿足性問題[28]；隨后Head 等人提出質(zhì)粒DNA 分子解決可滿足性問題[29]文獻(xiàn)[30-32]分別介紹了三種不同的可滿足性問題的計(jì)算模型。

本文構(gòu)建了一個(gè)動(dòng)態(tài)DNA步行者折紙計(jì)算模型，該模型由三部分組成：步行者、軌跡及燃料鏈。步行者行走的軌跡是在DNA折紙上固定的發(fā)夾結(jié)構(gòu)形成的。步行者通過堿基互補(bǔ)固定在DNA折紙的起始鏈上，當(dāng)加入起始鏈的補(bǔ)鏈才會(huì)釋放步行者參與反應(yīng)。燃料鏈也是發(fā)夾結(jié)構(gòu)，能通過鏈置換反應(yīng)催動(dòng)步行者向前行走。步行者行走的軌跡發(fā)夾呈二叉樹結(jié)構(gòu)分布在DNA折紙基底上，最后的一個(gè)分支上的發(fā)夾比前面的發(fā)夾在3′端多一段可識(shí)別的粘性末端，且DNA折紙基底上的所有發(fā)夾的環(huán)部區(qū)域都有特定的刻痕酶切割位點(diǎn)。在應(yīng)用該模型解決問題時(shí)，可以先根據(jù)約束條件對(duì)不滿足條件的路徑通過可識(shí)別的粘性末端打開發(fā)夾形成穩(wěn)定的雙鏈結(jié)構(gòu)，以此來堵塞不滿足條件的路徑。由于步行者無法通過堵塞的路，則DNA步行者通過的路都是滿足約束條件的可行解所對(duì)應(yīng)的路。最后通過刻痕內(nèi)切酶和鏈置換反應(yīng)很容易獲得需要的短鏈結(jié)構(gòu)，使用凝膠電泳讀解即可。此模型通用性很高，可以很好地解決很多問題NP問題。本文我們以該模型解決一個(gè)3-SAT 問題為例，用DNA 發(fā)夾結(jié)構(gòu)鋪設(shè)了一條一個(gè)入口和八個(gè)出口的二叉樹結(jié)構(gòu)，很好地解決了三個(gè)變量的可滿足問題。

可滿足性問題可表述為：由若干個(gè)析取范式合取構(gòu)成的范式叫做合取范式，如，其中由若干個(gè)合取范式析取構(gòu)成的范式叫做析取范式，如其中表 示互為否定，它們的取值或是0或是1，“1”表示值為真，“0”表示值為假?？蓾M足性問題是指對(duì)于給定的一個(gè)含有個(gè)變量的合取范式或者析取范式，是否存在一組或多組變量的取值使得該范式的真值為1。如果中的變量個(gè)數(shù)都小于或等于K個(gè)，那么稱其為K-可滿足性問題。

二、動(dòng)態(tài)DNA步行者折紙計(jì)算模型

該模型由三部分組成，分別為DNA折紙基底、固定在基底上的DNA結(jié)構(gòu)T和添加的DNA結(jié)構(gòu)T*。

圖1 DNA折紙基底及布局

折紙基底（圖1a）是由許多短的訂書釘鏈將一條M13長鏈折疊而成的矩形結(jié)構(gòu)，在折紙基底上有帶有粘性末端的延伸單鏈，用來固定發(fā)夾結(jié)構(gòu)。設(shè)計(jì)好的DNA發(fā)夾結(jié)構(gòu)以圖1（b）的布局鋪設(shè)在DNA折紙上，形成步行者要行走的軌道。軌道發(fā)夾用T（紫色）和Ti（綠色）表示，在加入燃料鏈后步行者可以通過打開發(fā)夾結(jié)構(gòu)向前行走。其中Ten（紅色）為初始單鏈，步行者開始是固定在Ten上的，加入Ten的補(bǔ)鏈能置換出步行者，使釋放的步行者參與反應(yīng)。Ti與T是結(jié)構(gòu)上基本相同的發(fā)夾結(jié)構(gòu)，發(fā)夾Ti的3'端比發(fā)夾T多出一段可識(shí)別的延伸短鏈，分布在軌道的最后一個(gè)分支。

圖2 鏈的組成與結(jié)構(gòu)

圖2（a）為固定在DNA折紙基底上的DNA鏈，這些鏈鋪設(shè)成了DNA步行者行走的軌道。圖2（b）為相應(yīng)的補(bǔ)鏈，這些鏈?zhǔn)前磳?shí)驗(yàn)要求依次添加的鏈。Ten為軌道的起點(diǎn)，DNA步行者通過部分堿基互補(bǔ)固定在Ten上，當(dāng)在溶液中添加Ten*時(shí)，通過鏈置換反應(yīng)便可釋放DNA步行者。鏈T和Ti鋪設(shè)在軌道上，形成DNA步行者行走的路，Ti在3'比T多出一段可識(shí)別的單鏈結(jié)構(gòu)，每個(gè)路口對(duì)應(yīng)不同的ei，映射為問題的不同可能解。鏈T和Ti上c 段都有特殊的酶識(shí)別位點(diǎn)，當(dāng)形成雙鏈的狀態(tài)下，加入切刻內(nèi)切酶（切刻內(nèi)切酶是一種限制性核酸內(nèi)切酶，它特異性的識(shí)別雙鏈DNA中的一段核苷酸序列，并只對(duì)其中的一條鏈進(jìn)行切割）時(shí)可從酶切點(diǎn)切割鏈T和Ti。鏈T*能與打開發(fā)夾狀態(tài)的T和Ti形成部分雙鏈，是DNA步行者行走的燃料鏈，當(dāng)加入切刻內(nèi)切酶和鏈M能置換出被切刻的部分。Ti*能通過ei*識(shí)別Ti上的延伸短鏈ei，從而打開對(duì)應(yīng)的Ti發(fā)夾形成穩(wěn)定的雙鏈狀態(tài)。由于此時(shí)的雙鏈狀態(tài)趨于穩(wěn)定，加入切刻內(nèi)切酶和鏈M也無法置換出被切刻的部分。具體步驟見圖3。

圖3 反應(yīng)過程示意圖

反應(yīng)的具體過程如圖3 所示。反應(yīng)的第一步為排除非解（圖3a），加入非解所對(duì)應(yīng)的發(fā)夾Ti的補(bǔ)鏈Ti*，發(fā)夾Ti*的粘性末端ei*通過識(shí)別ei打開發(fā)夾Ti，并與Ti形成穩(wěn)定的雙鏈結(jié)構(gòu)，這些穩(wěn)定的雙鏈將不會(huì)再與步行者發(fā)生鏈置換反應(yīng)，成功堵塞住不滿足條件的路徑，即步行者將不會(huì)走過非解所對(duì)應(yīng)的路。反應(yīng)的第二步是釋放步行者（圖3b），第一步刪除非解后，加入Ten*，Ten*上的a*首先與Ten上的a部分結(jié)合并逐步置換出Ten上的步行者，并與Ten形成穩(wěn)定的雙鏈結(jié)構(gòu)，部分釋放的步行者上的c*段與鄰近發(fā)夾c段互補(bǔ)并打開發(fā)夾T，接著全部從Ten上釋放的步行者的5'的c*段與第二個(gè)發(fā)夾c段互補(bǔ)打開第二個(gè)發(fā)夾T，由此，步行者固定到兩個(gè)相鄰的發(fā)夾T上，成功進(jìn)入軌跡。反應(yīng)的第三步是加入燃料鏈T*（圖3c），在步行者開始打開第二個(gè)發(fā)夾T時(shí)加入燃料鏈T*，由于發(fā)夾T*的a段與完全打開的發(fā)夾T的a段互補(bǔ)并發(fā)生鏈置換作用，可以置換出步行者后面的那條腿，解綁的后腿繼續(xù)打開第三個(gè)發(fā)夾T，由此催動(dòng)步行者一步步向前行走。由于燃料鏈T*只能與完全打開的發(fā)夾T發(fā)生反應(yīng)，則整個(gè)反應(yīng)中都是先置換步行者位于后面的那條腿，且反應(yīng)不可逆，這能確保步行者是始終向前運(yùn)動(dòng)的。步行者能沿著其中一條沒有被堵塞的路向前走至出口，且步行者走過的路徑上的發(fā)夾都形成部分雙鏈結(jié)構(gòu)。第四步是加入切刻內(nèi)切酶和鏈（圖3d），由于此時(shí)步行者走過的鏈T和T i都是部分雙鏈狀態(tài)。加入刻痕內(nèi)切酶，刻痕內(nèi)切酶只能對(duì)雙鏈DNA中含有刻痕切刻位點(diǎn)的那一條鏈進(jìn)行切割。由于發(fā)夾T上有刻痕切刻位點(diǎn)，形成雙鏈后加入切刻內(nèi)切酶，則可對(duì)T從切割位點(diǎn)進(jìn)行切割。加入的鏈能通過n*識(shí)別短鏈n從而置換出我們所需要的鏈I i。此時(shí)步行者走過的每條路徑均對(duì)應(yīng)于所求問題的一個(gè)可行解。

溶液中的單鏈只有步行者與切割下來的對(duì)應(yīng)于可行解的鏈I i，進(jìn)行凝膠電泳即可讀出可行解。

三、實(shí)例分析

此動(dòng)態(tài)DNA 步行者折紙計(jì)算模型可用于解決很多問題，本文以求解可滿足性問題為例。

（一）算法。對(duì)于含3 個(gè)變量、合取范式的可滿足問題，其可能解的個(gè)數(shù)為23共8種，則Ti(i=1,2,…,7)，其解映射為二叉樹結(jié)構(gòu)，如圖4所示。對(duì)于ei(i=1,2,…,7)我們?cè)O(shè)計(jì)了八種結(jié)構(gòu)表示為對(duì)應(yīng)于可滿足性問題的8個(gè)可能解0(0,0,0)、1(0,0,1)、2(0,1,0)、3(0,1,1)、4(1,0,0)、5(1,0,1)、6(1,1,0)、7(1,1,1)，ei*是與ei互補(bǔ)的短鏈。則產(chǎn)生8種發(fā)夾結(jié)構(gòu)Ti(i=1,2,…,7)和8種發(fā)夾結(jié)構(gòu)Ti*(i=1,2,…,7)。

圖4 所有可能解的二叉樹結(jié)構(gòu)示意圖

步驟1：排除非解；

步驟2：DNA步行者的行走；

步驟3：切割短鏈Ii；

步驟4：讀解。

（二）生物操作。步驟1：分析第一個(gè)子句知滿足x∨y為假的為，則加入e0、ei對(duì)應(yīng)發(fā)夾T0、Ti的補(bǔ)鏈發(fā)夾T0*、Ti*，分析第二個(gè)子句知滿足為假的為則加入e4、e6對(duì)應(yīng)發(fā)夾T4、T6的補(bǔ)鏈發(fā)夾T4*、T6*，分析第三個(gè)子句知滿足為假的為則加入e2對(duì)應(yīng)發(fā)夾T2的補(bǔ)鏈發(fā)夾T2*。通過此步驟即可排除掉所有非解。

步驟2：加入Ten*，釋放出DNA 步行者，然后在溶液中加入T*，T*作為燃料鏈推動(dòng)DNA 步行者向前行走。由于DNA步行者無法通過非解所對(duì)應(yīng)的路L0、L1、L2、L4、L6，所以DNA步行者走過的均為可行解所對(duì)應(yīng)的L3、L5、L7之中的一條路。

步驟3：待DNA步行者走過Ti鏈，加入切刻內(nèi)切酶和鏈M，切割并置換出I3、I5、I7這三條鏈。

步驟4：通過凝膠電泳讀出鏈I3、I5、I7。則該可滿足性問題的解為3(0,1,1)、5(1,0,1)、7(1,1,1)。（三）結(jié)果顯示。滿足該可滿足性問題的其中的一個(gè)解3(0,1,1)，如圖5所示：

圖5 3(0,1,1)解示意圖

四、結(jié)語

本文將DNA 折紙術(shù)和鏈置換技術(shù)催動(dòng)的DNA 步行者結(jié)合，構(gòu)建了一個(gè)動(dòng)態(tài)DNA步行者折紙計(jì)算模型。DNA步行者是一類獨(dú)特的動(dòng)態(tài)DNA裝置，它可以沿著一維、二維或三維軌跡移動(dòng)步行者，文中設(shè)計(jì)的沿著二維軌道運(yùn)動(dòng)的雙足步行者具有高自由度和高行進(jìn)性，且結(jié)構(gòu)簡單，在步行者運(yùn)動(dòng)的過程中不用逐步加入燃料鏈，這使得該模型操作更加簡單易行。且此模型通用性高，可解決許多NP問題，文中用此模型成功解決了可滿足性問題，不同于以往解決可滿足性問題先得出所有可能解再根據(jù)約束變量一一排除的方法，此模型第一步就是先排除非解，則反應(yīng)后得出的解均為問題的可行解，這大大簡化了后期篩選的工作。同時(shí)隨著問題變量的增多，實(shí)驗(yàn)中發(fā)夾T的種類并不會(huì)隨之增多，只需要相應(yīng)的增加可識(shí)別的粘性末端e的種類即可，這給實(shí)驗(yàn)帶來極大的簡化，對(duì)于多個(gè)變量的可滿足問題甚至是整數(shù)規(guī)劃問題等都可以很好地解決。但問題仍然存在，隨著變量的增多，折紙基底上的發(fā)夾數(shù)量相應(yīng)增多，這勢(shì)必需要更大的折紙基底結(jié)構(gòu)，相信隨著DNA 自組裝技術(shù)的發(fā)展，該問題可以得到解決。