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

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

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

一、引言

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

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

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

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

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

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

二、動態(tài)DNA步行者折紙計算模型

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

圖1 DNA折紙基底及布局

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

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

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

圖3 反應過程示意圖

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

溶液中的單鏈只有步行者與切割下來的對應于可行解的鏈I i，進行凝膠電泳即可讀出可行解。

三、實例分析

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

（一）算法。對于含3 個變量、合取范式的可滿足問題，其可能解的個數(shù)為23共8種，則Ti(i=1,2,…,7)，其解映射為二叉樹結(jié)構(gòu)，如圖4所示。對于ei(i=1,2,…,7)我們設計了八種結(jié)構(gòu)表示為對應于可滿足性問題的8個可能解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互補的短鏈。則產(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：分析第一個子句知滿足x∨y為假的為，則加入e0、ei對應發(fā)夾T0、Ti的補鏈發(fā)夾T0*、Ti*，分析第二個子句知滿足為假的為則加入e4、e6對應發(fā)夾T4、T6的補鏈發(fā)夾T4*、T6*，分析第三個子句知滿足為假的為則加入e2對應發(fā)夾T2的補鏈發(fā)夾T2*。通過此步驟即可排除掉所有非解。

步驟2：加入Ten*，釋放出DNA 步行者，然后在溶液中加入T*，T*作為燃料鏈推動DNA 步行者向前行走。由于DNA步行者無法通過非解所對應的路L0、L1、L2、L4、L6，所以DNA步行者走過的均為可行解所對應的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é)果顯示。滿足該可滿足性問題的其中的一個解3(0,1,1)，如圖5所示：

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

四、結(jié)語

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