DNA鏈置換反應網絡在求解可滿足問題中的應用

王夕遠, 殷志祥,2*, 唐 震, 楊 靜, 崔建中, 徐如解

(1. 安徽理工大學 數學與大數據學院, 安徽 淮南 232001; 2. 上海工程技術大學 數學與統計學院, 上海 201620; 3. 淮南聯合大學 計算機系, 安徽 淮南 232001)

計算機技術被認為是20世紀3大科學革命之一，電子計算機為社會發展起到了巨大的促進作用。近年來，由于科技的迅猛發展，傳統電子計算機已經難以滿足人們的需求。DNA計算機是近些年最有獨創性和出乎意料的發現之一，具有高度的并行性、運算速度快、存儲容量大、耗能低和DNA分子資源豐富等優點。為了制造出DNA計算機，人們開始對DNA計算進行研究。DNA計算的第一個例子解決了一個7城市哈密頓路徑問題[1]。2000年，Head等[2]提出了使用DNA質粒的一種新的計算方法，列出了潛在的優勢。通過報告計算圖頂點集最大獨立子集基數的NP完備算法題的一個實例計算，說明了新方法的有效性。2003年，殷志祥等[3]提出了在基于表面的DNA計算采用熒光標記策略，解決了簡單的0-1規劃問題。2006年，Rothemund[4]用DNA折疊來創造納米尺度的形狀和圖案。2009年，Xie等[5]提出了基于微流控芯片的拼接型DNA計算方法。2010年，Yang等[6]提出了一種新的基于循環DNA的最大團問題計算模型。2011年，Qian等[7]提出了DNA鏈置換級聯的神經網絡計算，同年，Zhang等[8]提出了基于DNA納米自組裝的分子邏輯計算模型。此外，DNA計算還可以用來構建半加器、半減器、全加器和全減器[9-14]。2018年，Yin等[15]利用分子信標計算模型解決了最大權團問題，同年，趙鑫月等[16]利用DNA折紙術解決了0-1整數規劃問題。2019年，Chao等[17]利用DNA單分子導航儀求解迷宮問題，唐震等[18-19]利用DNA折紙術解決了一類特殊的整數規劃問題，還提出了在DNA折紙基底上的一種動態的與非門計算系統。2020年，楊新木等[20]利用DNA折紙術解決了0-1背包問題，劉璐璐等[21]提出了異或門的DNA計算模型，斯燕方等[22]提出了簡單0-1規劃問題的動態DNA折紙計算模型，楊靜等[23]提出了基于雜交鏈式反應工序問題的DNA計算模型。

1 可滿足問題和DNA鏈置換

1.1 可滿足問題

可滿足問題(SAT)是一個經典的NP問題，它在邏輯電路的設計和密碼問題中的研究方面都有廣泛的應用。SAT問題可以描述為：對于一個給定的含有n個命題變項的合取范式(析取范式)，是否存在一組結果為真的賦值(真值為1)。SAT問題可用布爾邏輯表達式表示為F=C1∧C2∧…∧Cm。其中Ci=k1∨k2∨…∨kt,(i∈{1,2,…,m})為布爾變量，取值為0和1。用“0”表示真值“假”，用“1”表示真值“真”，“∧”為邏輯“與”，“∨”為邏輯“或”。SAT問題就是求使得F=1的所有布爾變量ki的真值分配表。顯然，對于含有n個變量的布爾公式F有2n個可能的賦值。2004年，劉文斌等[24]介紹了幾種SAT問題的 DNA計算模型,并在編碼問題、實現方式及算法設計等3個方面對其進行了比較。2008年，Wang等[25]使用基于連接酶鏈反應的DNA計算算法解決SAT問題。2009年，周康等[26]利用閉環DNA解決了可滿足性問題。2012年，劉文君等[27]提出了可滿足性問題的一種DNA表面計算模型。2016年，陳玉華等[28]提出了基于分子信標的可滿足性問題的粘貼模型。2020年，陳哲和斯燕方等[29-31]也解決了可滿足性問題。

1.2 DNA鏈置換

DNA鏈置換技術是指 DNA單鏈與部分互補雙鏈發生結構反應，替代并顯示出原有結構中被約束的單鏈，從而生成新雙鏈結構的過程。當互補鏈的長度變化時，形成雙螺旋結構的結合力也有所不同。當 DNA分子在雜交系統中，逐漸過渡到熵不斷增加，自由能趨于穩定的狀態，從而實現結合力較強的輸入鏈替換結合力較弱的被約束的單鏈，最后，被替代的單鏈作為輸出信號，實現分子邏輯運算功能。2013年，Anthonuy等[32]將DNA鏈置換應用于矩陣乘法和加權和中。同年，Li等[33]通過DNA鏈置換完成了三輸入多數邏輯門的設計。2016年，Li等[34]基于DNA鏈置換構建了一個半加器。2017年，Song等[35]利用自催化放大器設計和分析了用于模擬計算的緊湊DNA鏈置換電路。Zhang等[36]利用DNA鏈置換解決了概率問題。2019年，吳濤等[37]基于DNA鏈置換構建邏輯計算模型。

DNA鏈置換可以分為可逆和不可逆2種情形，可用如下的公式進行表示：

不可逆：{A^}[B^]+→+[AB^],

可逆：{A^}[BC^]+?+[AB^]{C^}。

DNA不可逆和可逆的鏈置換反應見圖1。

圖1中{A^}[B^]表示部分互補的DNA雙鏈；{A^}[B^]和{A^}[BC^]中的單鏈部分稱之為腳趾。這里對于DNA鏈的描述是采用了Visual DSD語言。在Visual DSD中，尖括號中的序列表示3′端在右側的鏈，也稱之為上部鏈，而大括號中的序列表示3′端在左側的鏈，也稱為下鏈。這2種描述方式是可以相互轉換的，只是方向有所不同。序列可以是一個域、一個域補碼，具有多個位置標記的系鏈或由空格分隔的多個序列。域可以是由標識符表示的識別域，可以是在標識符上附加(∧)字符表示的toehold域。中括號則表示的是通過堿基互補配對所形成的DNA雙鏈結構，箭頭的方向表示反應的方向，單向箭頭表示的是不可逆反應，雙向箭頭表示可逆反應。Visual DSD語言所描述的鏈見圖2。在DNA鏈置換中的腳趾的長度決定著反應的速率在6堿基內以指數增長，在6堿基時反應速率達到最大。

本文通過DNA鏈置換反應并利用Visual DSD進行仿真，得到反應網絡圖來求解可滿足性問題。考慮到可滿足性問題不需要考慮權重，將求解過程分為3個模塊，即變量轉換模塊、求和模塊和閾值比較模塊，在閾值比較模塊中，由于濃度的檢測會存在一定的誤差，故通過檢測是否有熒光顯示來判斷是否為可行解。

2 基于鏈置換反應網絡解決可滿足性問題

設計思想：對于可滿足性問題，如F=(x1∨x2)∧(x1∨x3)∧(x2∨x3),將求解過程分為3個模塊：①通過鏈置換反應將每一個變量xi(i=1,2,3)轉換成Y，這里每一個變量都分別對應一條DNA單鏈；②對模塊一中所得的Y單鏈進行求和，在數字上是一般的加法運算，實際上是濃度的相加；③通過閾值的比較來判斷解是否滿足要求，這里假設閾值為0.9 nm。通過這3個模塊可以求解出布爾公式F的第一個析取范式的解，重復上述3個模塊得出所有的解。當變量xi=1(i=1,2,3)時，輸入相對應的單鏈DNA濃度為1 nm；當xi=0(i=1,2,3)時，則不輸入相應的DNA單鏈Xi(i=1,2,3)。上述的3個模塊具體描述如圖3。

2.1 變量轉換模塊和求和模塊

針對SAT問題，設計了一個變量轉換模塊和求和模塊。在變量轉換模塊中，將每一個變量xi=1(i=1-n)分別設計成一條DNA單鏈Xi，通過鏈置換反應將每一個變量xi=1(i=1-n)所代表的單鏈轉換成變量Y所代表的DNA單鏈，即

Xi→Y(i=1-n),

Xi+Zi→Y+waste.

對于這一化學反應步驟，需要輔助鏈Zi的參與，如圖4所示。對于可滿足問題，當變量xi=1(i=1-n)，設ss-DNAXi的初始濃度為1 nm。對于這一反應1 nm的Xi經過反應能得到1 nm的Y。對Y的濃度進行相加。在DNA鏈置換反應中，Xi和Zi的初始濃度滿足[Xi]0<<[Zi]0。

2.2 閾值的比較模塊

在求和模塊中，可以得到Xi→Y(i=1-n),此時，Y作為反應的輸出鏈，將Y鏈的濃度和所設定的閾值進行比較，得出滿足問題的可行解。然而，對于濃度的準確檢測在現實中存在一定的限制。通過設計鏈置換反應置換出熒光來解決這一限制。若有熒光顯示，則是所求問題的一個解；若沒有熒光顯示，則不是所求問題的解。這里所設計的鏈置換反應需要有2個輔助鏈的參與，化學反應網絡模塊描述如下，可以通過Visual DSD的反應網絡來實現。

[Y]0≤

這里的P和T是鏈置換反應所需要的輔助鏈，具體見圖5，P和T都是部分互補的雙鏈DNA，其中T的上浮單鏈DNA的3′端標記有熒光基團，下游單鏈DNA的5′端標記有熒光猝滅劑，這樣使得T一開始不發光。隨著對DNA鏈置換反應動力學的表象特征觀察到，動力學隨著接觸點長度[1-3]增加呈指數增加。對于本文的閾值反應模塊，3nt是6nt的截斷部分，這就導致了l1的反應速率要遠大于l2。如果[Y]0≤[P]0,那么鏈Y將會優先和接觸點長的鏈P反應(圖5)；如果[Y]0>[P]0,鏈Y會優先和接觸點長的鏈P反應，剩下的Y鏈再和鏈T進行鏈置換反應，使得T鏈中的熒光和熒光猝滅劑相分離，有熒光顯示。因此，只有當[Y]0>[P]0時有熒光顯示，這里的[P]0設為閾值，即為0.9。在DNA鏈置換反應中，初始輸入鏈Y的濃度是由求和反應模塊提供，[P]0=0.9,鏈T的初始濃度也設為閾值，即[T]0=0.9。

(a)初始濃度[Y]0≤[P]0，鏈Y和腳趾區域a*-b*相結合。反應達到平衡時Q的濃度為[Q]∞=[Y]0;(b)初始濃度[Y]0>[P]0,鏈Y會先和腳趾區域長的a*-b*先結合，剩下的Y鏈和腳趾區域b*相結合。當反應達到平衡時Q的濃度為[Q]∞=0.9,隨后會有熒光顯示出來

3 仿真結果

簡單起見，以5個變量的可滿足性問題為例。求解F=(x1∨x5)∧(x2)∧(x3∨x4)∧(x5)∧(x2∨x3∨x4)，在這個布爾邏輯表達式中存在著5個變量，這意味著一共存在著25=32種可能解。將這32種可能解以表格的形式表示出來，見表1。

表1 32種可行解Table 1 32 feasible solutions

(續表1)

下面分3步來尋找可行解。①將變量xi(i=1-5),通過鏈置換反應將每個變量所代表的DNA單鏈轉換成Y單鏈；②將所得到的Y鏈進行相加；③將所得到的Y鏈濃度和閾值相比較，結果可通過DNA鏈置換觀察是否有熒光顯示。

(1)在F的第一個析取范式中，包含著2個變量x1和x5。這意味著在32個可行解中只要x1和x5有一個或者同時為1，第一個析取范式結果為真，這樣的結果一共有24個，見表2。

表2 第一個析取范式的所有可行解Table 2 All feasible solutions of the first disjunctive normal form

步驟1：將變量x1和x5所代表的鏈X1和X5通過鏈置換反應轉換成Y鏈，化學反應網絡如下(圖6)：

Xi+Zi→Y+waste(i=1-5)。

步驟2：將步驟1中所得到的Y鏈進行相加。如：(0,0,0,0,0),(1,0,0,0,0),(1,1,0,0,0),(1,1,1,0,0),(1,1,1,1,0),(1,1,1,1,1),分別輸出為0,1,2,3,4,5，即分別代表Y的值為0,1,2,3,4,5。

步驟3：將步驟2所得到的輸出值和閾值進行比較來判斷是否為可行解，具體可通過觀察是否有熒光顯示來判斷，見圖7。

在第一個析取范式的可行解基礎上，重復上述步驟來求解第二個至第五個析取范式的可行解。

(2)對于第二個析取范式，只需在上述的24個可行解的基礎上尋找x2=1的情形。

步驟1：將變量x2所代表的鏈X2通過鏈置換反應轉換成Y鏈。化學反應如下：

反應見圖8。

步驟2：將步驟1所得的Y鏈進行相加。如可行解(這里的可行解存在于上述24個可行解中)(0,1,1,1,1)、(1,1,1,0,1)、(1,1,0,1,1)、(1,1,1,1,0)和(1,1,1,1,1)，分別對應Y的輸出值為4、4、4、4和5。

步驟3：將步驟2所得到的輸出值和閾值進行比較來判斷是否為可行解，具體可通過觀察是否有熒光顯示來判斷(圖9)。

通過上述步驟滿足前2個析取范式的可行解個數為12個(表3)。

表3 前2個析取范式的所有可行解Table 3 All feasible solutions of the first two disjunctive normal forms

(3)對于第三個析取范式，只需在上述的12個可行解的基礎上尋找x3=1或x4=1的情況。

步驟1：將變量x3,x4所代表的鏈X3,X4通過鏈置換反應轉換成Y鏈。化學反應如下：

反應見圖10。

步驟2：將步驟1所得的Y鏈進行相加。如可行解(這里的可行解存在于上述12個可行解中)(0,1,0,1,1)、(1,1,0,1,1)、(1,1,1,0,1)、(1,1,1,1,0)和(1,1,1,1,1)，分別對應Y的輸出值為3、4、4、4和5。

步驟3：將步驟2所得到的輸出值和閾值進行比較來判斷是否為可行解，具體可通過觀察是否有熒光顯示來判斷。

通過上述步驟滿足前3個析取范式的可行解個數為9個(表4)。

表4 前3個析取范式的所有可行解Table 4 All feasible solutions of the first three disjunctive normal forms

(4)對于第四個析取范式，只需在上述9個可行解的基礎上尋找。

步驟1：將變量x5所代表的鏈X5通過鏈置換反應轉換成Y鏈。化學反應如下：

化學反應見圖11。

步驟2：將步驟1所得的Y鏈進行相加。如可行解(這里的可行解存在于上述6個可行解中)(0,1,1,1,1)、(1,1,1,0,1)、(1,1,1,1,0)和(1,1,1,1,1)，分別對應Y的輸出值為4、4、4和5。

步驟3：將步驟2所得到的輸出值和閾值進行比較來判斷是否為可行解，具體可通過觀察是否有熒光顯示來判斷。

通過上述步驟滿足前4個析取范式的可行解個數為6個(表5)。

表5 前4個析取范式的所有可行解Table 5 All feasible solutions of the first four disjunctive normal forms

(5)對于第五個析取范式，只需在上述的6個可行解的基礎上尋找。

步驟1：將變量x2,x3,x4所代表的鏈X2,X3,X4通過鏈置換反應轉換成Y鏈。化學反應如下(圖12)：

步驟2：將步驟1所得的Y鏈進行相加。如可行解(這里的可行解存在于上述6個可行解中)(0,1,1,1,1)、(1,1,1,1,0)和(1,1,1,1,1)。

步驟3：將步驟2所得到的輸出值和閾值進行比較來判斷是否為可行解，具體可通過觀察是否有熒光顯示來判斷。

通過上述步驟滿足這個例子的可行解個數為6個，即(0,1,1,0,1)、(0,1,0,1,1)、(0,1,1,1,1)、(1,1,0,1,1)、(1,1,1,0,1)和(1,1,1,1,1)見表6和圖13。

表6 滿足這個例子的可行解Table 6 A feasible solution that satisfies this example

4 結束語

本文基于DNA鏈置換反應網絡求解可滿足性問題，利用Visual DSD進行了仿真。求解過程分成3個反應模塊：變量轉換模塊、求和模塊和閾值比較模塊，除了求和模塊外，其他2個模塊都利用了DNA鏈置換反應。文中利用上述的3個反應模塊具體解決了5個變量的可滿足性問題，每個變量xi(i=1-5)分別代表著鏈Xi(i=1-5)經過變量反應模塊得到Y鏈，再將Y鏈的濃度進行相加，最后和所設定的閾值進行比較，通過觀察是否有熒光顯示來判斷，若有熒光顯示則是可行解，否則不是，最終有6個可行解。

本文的設計思想不僅可以解決可滿足性問題，還可以解決一些加權的問題，如整數規劃問題，背包問題等。與之前的求解可滿足計算模型相比適用范圍更加廣泛，適用于大范圍的求解。利用Visual DSD得到了反應網絡圖和仿真結果，驗證了該設計的可行性，閾值作為一種檢驗手段，通過觀察是否有熒光來判斷可行解，使得結果更明顯直觀。本文的設計為大規模求解提供了思路，關于大規模求解問題是后續的工作。