基于DNA折紙術求解可滿足性問題的計算模型*

王欣怡，殷志祥，唐 震，楊 靜，崔建中

(1.安徽理工大學數學與大數據學院，安徽 淮南 232001；2.上海工程技術大學數理與統計學院，上海 201620； 3.安徽理工大學電氣與信息工程學院，安徽 淮南 232001；4.淮南聯合大學計算機系，安徽 淮南 232001)

1 引言

隨著計算機技術的高速發展，各種非線性問題和NP完全問題在新的工程技術領域不斷出現，而現有的電子計算機無法解決這類復雜的計算問題[1]。DNA計算作為一種新型計算方式，由于DNA分子的特異性、微小性和高并行性等天然特性，在海量信息存儲和處理過程中，可以高容量保存以及并行操作，這為解決復雜的計算提供了一種新途徑，是具有廣泛應用前景的熱點研究領域。1994年，Adleman教授[2]利用DNA編碼解決了有向圖的Hamilton路徑問題，首次劃時代地邁入DNA計算領域。1995年Lipton[3]在Adleman的實驗基礎上，提出利用DNA計算解決NP完全問題。

2006年，Rothemund[4]第1次提出DNA折紙術的概念，他將一條DNA長鏈(腳手架鏈)與經過一系列步驟設計而成的DNA短鏈(訂書釘鏈)，通過堿基互補配對，可控地折疊成各種復雜的納米級形狀和圖案，具有傳統DNA自組裝所不具備的優勢，在新興的納米領域中具有廣泛的應用前景。同年，Qian等人[5]利用DNA折紙術建立了一個非對稱模擬中國地圖，該結構是首個通過DNA折紙術構建的非對稱圖形。

2014年，Yang等人[6]利用多輸入結合誘導效應建立一個可以檢測多個輸入信號的邏輯系統，為多個分子的靶向檢測和構建大規模DNA計算的復雜納米器件的設計提供了可能。2015年，俞洋等人[7]利用DNA折紙術折疊出可用來編碼Hamilton路徑圖中頂點和路徑的固定的DNA納米結構，為Hamilton路徑問題提供了一種新的解決方案。2016年，俞洋等人[8]利用DNA納米折紙結構編碼無向圖的頂點，借助納米結構之間的粘性末端進行自組裝，給出了一種圖著色問題的解決方法。同年，Yang等人[9]通過對DNA瓦片進行特異性控制，證明了幾何圖形是可控和可編程的，他們還利用鏈置換和DNA折紙動態釋放納米金顆粒[10]，建立一組動態DNA邏輯門計算模型，該方法可用于組裝更復雜的納米系統。

Figure 1 Three-dimensional DNA origami self-assembly圖1 三維DNA折紙結構自組裝

2017年，Zhang等人[11]建立了基于DNA鏈置換技術的條件概率推導模型和全概率模型，并通過“讀心”游戲對模型進行了評估；同年，Pan等人[12]通過DNA鏈置換技術實現了一個基于雙通道的蛋白質復合系統，其所提出的調控機制可用于轉換邏輯語句，并建立了可連接蛋白質和DNA的邏輯電路;Tikhomirov[13]使用表面具有圖案的正方形DNA折紙瓦片作為基本構建單元，構造一個微米級的二維DNA折紙點陣，成功利用DNA折紙術描摹蒙娜麗莎等圖像，再次證明了DNA折紙術幾乎可構造任意的二維納米級圖形。

2018年，Yang等人[14]提出了一種基于共價修飾的DNA回路調控策略，利用DNA酶調控的熵驅動DNA邏輯電路，實現級聯催化電路，并建立兩層級聯電路和反饋自催化電路。2019年，Xu等人[15]提出了一種通過雙鏈瓦片組裝特殊DNA納米管的方法，實現對納米管周長的精確控制。同年，Pan等人[16]利用DNA特異性適體識別，通過模擬轉錄因子調控，將多種生物分子作為調控因子，建立了多級級聯網絡和甲基化開關電路，為生物學擴展體外合成提供可能。

除了合成各類形的二維結構，隨著近年來研究的不斷深入，DNA折紙已發展成為廣泛使用的構建納米尺度的空間分子陣列平臺，通過調節結合螺旋的數目，進行非整數圈轉動，可以得到三維DNA折紙結構，如圖1[17 - 21]所示。

2 可滿足性問題的DNA計算模型

2.1 分子信標和DNA折紙術

分子信標(Molecular Beacon)是一種發夾型結構的莖環雙標記寡聚核苷酸探針，根據堿基互補配對原則和熒光共振能量轉移現象(Fluorescence Resonance Energy Transfer)設計而成[22]，能使核苷酸的序列結構信息轉變為熒光信號，方便觀察，具有很高的靈敏度和選擇性。

分子信標一般由4個部分組成：環狀區、莖干區、熒光基團和猝滅基團。分子信標的作用原理如圖2所示，當體系中未加入待檢測目標序列時，即沒有靶序列時，熒光基團和猝滅基團之間的距離很近，熒光被猝滅檢測不到熒光信號；當體系中加入待檢測的目標序列時，分子信標環狀區的堿基序列與靶序列發生特異結合，堿基間互補配對使發夾結構發生變化，分子信標結構被破壞，熒光供體基團和猝滅受體基團之間距離變大，熒光恢復從而檢測到熒光信號。

Figure 2 Principle of molecular beacon working 圖2 分子信標作用原理

DNA折紙術是利用DNA分子的特殊結構和堿基互補配對原則，將一條長的DNA單鏈(腳手架鏈)的特定區域進行折疊，并用短鏈(訂書釘鏈)加以固定，構造出預期的結構。DNA折紙的設計與合成過程：首先是根據目標形狀設計腳手架單鏈的折疊路徑；其次是由DNA序列互補雜交的空間結構特點設計訂書釘鏈的結合方式，并在訂書釘鏈的結合位置生成對應的核苷酸序列用以固定；最后將腳手架鏈與訂書釘鏈混合，設置合適的退火程序，確保訂書釘鏈結合到腳手架鏈的設計位點，退火后得到目標DNA折紙結構。與傳統的納米自組裝方法相比，DNA折紙術更容易組合出結構穩定、復雜度高、精度準確和可控性高的納米結構，并且具有設計簡單、操作簡便、組裝效率高、反應速度快、實驗要求低和納米可尋址性等優點。利用DNA折紙術得到的結構作為模板組裝功能納米材料或分子，可以獲得光學、電磁學等性能可控的納米器件或藥物載體。隨著分子生物學技術的不斷發展，DNA折紙從一維結構到二維結構再到三維結構，在NP問題中扮演著越來越重要的角色。

本文將分子信標錨定在DNA折紙基底形成圖3中的布局，通過雜交鏈式反應后形成“1”和“0”形狀，若顯示為“1”代表對應變量取值為1，若顯示為“0”，則代表對應變量取值為0。

Figure 3 DNA origami is used to fold short strands of DNA into shapes such as“1”and“0”圖3 利用DNA折紙術將DNA 短鏈折疊成“1”“0”等形狀

2.2 雜交鏈式反應

雜交鏈式反應HCR(Hybridization Chain Reaction)是Dirks等人[23]在2004年提出的一種簡單有效的非酶等溫擴增技術，其獨特性在于特定的DNA單鏈片段不會擴增，而是充當引物與2個亞穩態的DNA發夾結構進行自組裝。雜交鏈式反應主要包括啟動鏈T和2個核酸發夾探針H1和H2。啟動鏈不存在時，2種發夾探針自身不會發生雜交，穩定地共存于緩沖溶液中；當加入啟動鏈T后，T觸發2個亞穩態發夾DNA發生雜交鏈式反應，從而自組裝成一條長的雙鏈DNA，反應的原理如圖4所示。啟動鏈識別第1個發夾探針H1的粘性末端及莖部(a-b部分)，與其雜交而打開H1的莖環結構，使H1暴露出的單鏈(c-b*部分)裸露在外；該部分裸露在外的新的堿基隨即識別第二個發夾探針H2的粘性末端及莖部(c*-b部分)，與其雜交而打開H2的莖環結構，H2暴露出的單鏈(a*-b*部分)又可以識別下一個H1的粘性末端及莖部并將其打開。因此，每一條啟動鏈可觸發2個發夾DNA探針的多次循環雜交，最終2種發夾DNA探針發生雜交鏈式反應生成交替循環雜交的帶缺口的DNA雙鏈聚合物，從而實現生物分子檢測信號放大的目的。

Figure 4 Schematic diagram of hybridization chain reaction圖4 雜交鏈式反應原理圖

雜交鏈式反應可以在無酶參與下實現信號放大的目的，同時具有擴增特異性好、可在常溫下進行反應、實驗成本低及重現性好等優點，因此在生物分子檢測、生物傳感器的制備等領域得到了廣泛應用。

2.3 可滿足性問題

可滿足性SAT(SATisfiability)問題是指給定一個包含m個子句的合取范式，每個子句包含q個字符，判定是否存在一種真值賦值使得該范式為真。一般用“1”表示命題為“真”，用“0”表示命題為“假”，則可滿足性問題可以表示成為在集合L={a1,a2,…,an,a′1,a′2,…,a′n}中(其中a′i為ai的否定形式)，對于一個合取范式F=C1∧C2∧…∧Cm，其中，Ci(i=1,2,…,m)是形如l1∨l2∨…∨ln(lj,j=1,2,…,n)的析取式，是否存在一組賦值使得合取范式F的真值為1。由于實際問題中各個子句中包含的字符個數各不相同，增加了問題的求解難度，為了便于分析和求解，在通常分析時對子句中包含的字符個數增加約束條件，稱其為q-可滿足問題，如q=3時，即為3-可滿足問題。當問題中給定的合取范式F不可滿足時，需要求解一種真值賦值P，使得P滿足F中最多數目的子句，稱之為最大可滿足性問題(Maximum Satisfiability Problem)。

經過二十余年的發展，DNA計算在序列編碼、計算模型和檢測手段等方面都取得了許多突破和進展，已被運用于求解各種NP難問題?？蓾M足性問題(SAT問題)是計算科學問題中的典型問題之一，也是當今計算機科學和人工智能研究的核心問題，在工程技術、交通運輸、人工智能、機器學習、VLSI集成電路設計與檢測以及計算機科學理論等領域具有廣闊的應用背景，如程控電話的自動交換、大型數據庫的維護、大規模集成電路的自動布線、軟件自動開發和機器人動作規劃等都可轉化成SAT問題。因此，致力于尋找求解SAT問題的快速而有效的算法，不僅在理論研究上而且在許多應用領域都具有極其重要的意義，一些學者開始將DNA計算應用于求解SAT問題，尋求更優化的方法對其進行求解，試圖找到求解大規模SAT問題的有效方法。

隨著1995年Lipton[3]通過DNA計算解決可滿足性問題后，1999年，Cukras等人[24]利用RNA解決可滿足性問題；2000年，Head等人[25]提出利用質粒DNA分子解決可滿足性問題；2008年，殷志祥等人[26]用分子信標DNA計算模型提出了一種解決可滿足性問題的方法；2009年，周康等人[27]提出了可滿足性問題的閉環DNA算法；2011年，宋勃升等人[28]利用DNA自組裝的方法求解可滿足性問題；2013年，肖建華等人[29]利用免疫磁標記和巨磁電阻效應給出了可滿足性問題的巨磁電阻型DNA計算模型；2017年，馬瑩等人[30]利用微流路芯片高壓凝膠電泳，給出了一種基于生物芯片解決可滿足性問題的DNA計算模型。2019年，Tang等人[31]利用DNA折紙術建立了動態與非門DNA計算模型，同年該課題組還通過DNA折紙術，設計出一種求解特殊整數規劃問題最優解的DNA計算模型[32]。

盡管當前利用DNA計算求解可滿足性問題已取得了相當重要的進步，但還有許多值得研究改進的問題。針對當前可滿足性問題規模越來越大，由于SAT問題的NP特性，求解的時間也越來越長，為進一步增強求解大規模可滿足性問題的能力，本文提出一種利用DNA折紙術解決可滿足性問題的DNA計算模型，從降低反應復雜度，簡化觀測讀取實驗結果等方面入手，減少可滿足性問題總體解決時間，加速問題求解。

3 可滿足性問題DNA算法生物實現

3.1 DNA編碼

Figure 5 Schematic diagram of hairpin structure圖5 發夾結構構造示意圖

用訂書釘鏈將環形噬菌體(M13mp18)折疊成二維矩形作為折紙基底。將上述構造的2q種帶有發夾結構的DNA鏈與DNA折紙基底上帶有粘性末端的訂書釘鏈通過堿基互補配對，將DNA鏈固定在折紙基底上。該2q種帶有發夾結構的DNA片段根據可滿足性問題解的形式，設計形成不同的2q種解的組合，每個組合包含q個變量(字符)所對應的寡聚核苷酸，將所有的解映射成具體的數字“1”和“0”型，代表可滿足性問題變量的取值，如圖6所示。

Figure 6 Schematic diagram of the solution圖6 解的示意圖

構造啟動鏈和輔助鏈(如圖7所示)，在啟動鏈和輔助鏈的幫助下完成雜交鏈式反應(如圖8所示)，最后在折紙基底上形成如圖9所示的“0”“1”型解的路徑圖，再結合熒光反應實現可視化，直觀地顯示出可滿足性問題的解。

Figure 7 Construction diagrams of variables, startup chains and auxiliary chains 圖7 變量、啟動鏈和輔助鏈構造示意圖

Figure 8 Schematic diagram of reaction process forming specific path圖8 形成特定路徑“0”的反應過程示意圖

Figure 9 Path diagram of hybrid chain reaction forming solutions圖9 雜交鏈式反應形成解的路徑示意圖

3.2 算法步驟

根據3.1節中DNA鏈的編碼規則和排列方式，按以下步驟進行可滿足性問題的DNA計算：

步驟1對包含m個子句、q個變量(字符)的可滿足性問題，構造2q個折紙基底，在折紙基底上每個變量有2種取值“0”或“1”，用發夾結構加以錨定。值得注意的是對于每個子句中的變量xi，將其排列成“1”的發夾結構連接上熒光基團和猝滅基團，形成分子信標，排列成“0”的發夾結構則不連接。反之對于變量x′i，排列成“0”的發夾結構連接上熒光基團和猝滅基團，排列成“1”的發夾結構則不連接。

步驟2對可滿足性問題合取范式中任一個含有q個變量(字符)的子句，構造出2q個步驟1中所描述的折紙基底，加入代表不同變量取值的啟動鏈以及相應的輔助鏈。由于含有變量編碼片段的發夾結構錨定在折紙基底上，在輔助鏈的作用下進行充分反應后，DNA片段沿基底上設計排列而成的，映射為具體數字“1”和“0”型的路線，形成特定的反應路徑(如圖8和圖9所示)。此時發夾打開，分子信標結構被破壞，顯示熒光，利用原子力顯微鏡觀察折紙基底上的熒光情況。通過雜交鏈式反應，有熒光顯示的折紙基底上對應的解的組合即為該子句的可行解。

步驟3重復步驟2，直到找到所有子句的可行解。

步驟4通過可視化刪除所有子句中不滿足真值為真的解后，它們的共同解就是該可滿足性問題的最終可行解。

3.3 算法模型實例分析

為具體驗證上述算法的正確性，不失一般性又簡單起見，下面取q=3的標準合取范式F=(x1∨x2)∧(x′2∨x3)∧(x′1∨x2∨x′3)為例進行驗證，具體操作步驟如下所示：

步驟1對于合取范式F中第1個子句x1∨x2構造如圖10所示的折紙基底，由于子句中不含變量x′i，因此只有排列成“1”的發夾結構上帶有熒光基團和猝滅基團組合。

Figure 10 Schematic diagram of the arrangement of solutions on an origami substrate in clause 1圖10 子句1折紙基底上解的排列示意圖

Figure 11 Fluorescence path of hybridization chain reaction in clause 1圖11 子句1的雜交鏈式反應熒光路徑示意圖

步驟3對于合取范式F中第2個子句x′2∨x3，子句中含有變量x′2和x3，對于變量x′2，它排列成“0”的發夾結構帶有熒光基團和猝滅基團組合，排列成“1”的發夾結構則不帶；對于變量x3，它排列成“1”的發夾結構帶有熒光基團和猝滅基團組合，排列成“0”的則不帶。構造如圖12所示的折紙基底。

Figure 12 Schematic diagram of the arrangement of solutions on an origami substrate in clause 2圖12 子句2折紙基底上解的排列示意圖

步驟5對于第3個子句x′1∨x2∨x′3重復上述步驟，在輔助鏈的作用下充分反應后，利用原子力顯微鏡觀察折紙基底上的熒光情況，有熒光顯示的折紙基底上對應的解為該子句的可行解，可得到滿足第3個子句的可行解為(0,0,1),(1,1,0),(1,0,0),(0,1,1),(0,1,0)，(0,0,0)和(1,1,1)。因此滿足合取范式F的最終可行解為(1,0,0)，(0,1,1)和(1,1,1)，其雜交鏈式反應熒光路徑如圖14所示。

Figure 13 Fluorescence path of hybridization chain reaction in clause 2圖13 子句2的雜交鏈式反應熒光路徑示意圖

Figure 14 Fluorescence path diagram of hybridization chain reaction of the final solution圖14 最終解的雜交鏈式反應熒光路徑示意圖

4 模型仿真與討論

4.1 模型仿真

Visual DSD是常用于DNA折紙術和雜交鏈式反應的仿真分析軟件，本文利用該軟件對所提出的可滿足性問題DNA計算模型進行仿真和分析。下面取第3.3節實例問題中的一個可行解(1,1,1)，即x1=x2=x3=1時的情況進行分析，模擬變量xi在折紙基底上反應過程中各個鏈的濃度如圖15所示。

Figure 15 Variable simulation results of the feasible solution (1,1,1)圖15 可行解(1,1,1)的變量仿真結果圖

首先向試管內添加啟動鏈，反應開始，因初始狀態反應物濃度高，反應較快，啟動鏈的濃度在短時間內迅速降低后趨向于0；對于反應的中間產物，由于雜交鏈式反應是逐漸進行的，所以中間產物鏈的濃度先增加后減少而后趨向于0。隨著反應進行生成物(即鏈sp13)的濃度逐漸增加最終趨于穩定，其余可行解的反應情況與此類似。反應過程中的DNA鏈為已編碼的發夾結構和分子信標結構，能穩定地存在于溶液當中，有效防止錯誤雜交產生，同時確保雜交鏈式反應嚴格按照設計方向進行。該仿真結果與預期實驗結果一致，表明模型具有可行性。

4.2 模型復雜度分析

DNA計算模型的復雜度一般包括時間復雜度和空間復雜度。本文計算模型的時間復雜度與實驗過程中發生生化反應的時間相關，與可滿足性問題合取范式所含子句的個數m相關，子句中變量的數量越多，反應所需時間越長，模型的時間復雜度越高，即模型的時間復雜度為O(m)。在空間復雜度上本文按照Brun[33]給出的自組裝模型的復雜度計算理論，討論此模型所需要的參與計算的分子結構的種類。以第3.3節中實例進行分析，該3-SAT問題需要啟動鏈6種，輔助鏈6種，折紙基底1種，因此在參與計算的分子結構種類上為Θ(2q)(q為變量的個數)，在上述3-SAT問題中變量有3個(為常數)，所以該DNA計算模型的空間復雜度為Θ(m)(m是3-SAT問題中子句的個數)，計算模型的復雜度與可滿足性問題的約束條件有關，且呈線性關系，而每個計算模板所判定的取值組合都是建立在排除上一個子句的組合之上，因此判定的次數將逐次減少。以上分析表明，該模型通過對可滿足性問題解的路徑的設計，將可滿足性問題的解直觀地表示出來，操作簡單且容易觀測，降低了可滿足性問題的復雜度，是一種較為有效的模型。

5 結束語

本文利用DNA折紙術可以折疊出特殊結構的特點，設計了一種DNA計算模型，結合分子信標熒光原理，將可滿足性問題的解直觀地表示出來，并結合實例利用Visual DSD對計算模型進行模擬仿真，表明了該計算模型的可行性和實用性。利用該模型求解可滿足性問題實現可視化，操作簡單且容易觀測，更容易獲得準確可靠的結果。但是，由于DNA折紙基底尺寸有限，所求解可滿足性問題的規模會受到限制，并且本文在理論上驗證了模型的可行性，生物實驗部分還是空缺，在實際生物實驗中仍存在一些不可控制的因素，如反應溫度的控制、緩沖液的濃度等其他反應條件變化，可能會使得被檢測到的熒光信號降低從而影響實驗結果。因此，如何利用生物實驗來驗證模型的可行性和準確性，以及如何利用分層自組裝，讓該模型更廣泛地應用在納米或微米尺寸上解決更大規模的NP完全問題，將是下一步的工作重點。