基于分子信標的可滿足性問題的粘貼模型

陳玉華　殷志祥

摘要：為了解決NP完全問題中的可滿足性問題，將分子信標和粘貼模型的優勢結合起來，設計了一種新的以分子信標為粘貼鏈的粘貼模型，并將該模型應用于可滿足性問題的求解。由于分子信標具有易操作、高靈敏度、高特異性等特點，將分子信標作為粘貼鏈，分子信標粘貼鏈比普通粘貼鏈鏈更有優勢，利用該模型求解問題的操作簡單且容易觀測，求得問題的解比普通的粘貼模型更準確可靠。

關鍵詞：分子信標；粘貼模型；可滿足性問題

中圖分類號：TP301文獻標志碼：A

文章編號：1672-1098（2016）02-0020-05

Abstract：In order to solve the problem of NP complete problem， by combining the advantages of molecular beacon and sticker model， a new method of molecular beacon was designed， which is used to solve the satisfiability problem. Because of the characteristics of easy operation， high sensitivity， high specificity， etc.， molecular beacon is used as a sticker chain， the molecular beacon sticker chain is more advantageous than the ordinary sticker chain. The operation of solving the problem by using the model is simple and easy to observe， and the solution is more accurate and reliable than the ordinary sticker model.

Key words： molecular beacon； sticker model； satisfiability problem

DNA計算是一種新型的計算模式，它在解決NP完全問題上，所表現出來的優勢是傳統圖靈機無法比擬的。正因如此，人們對DNA計算產生了濃厚的興趣。1994年，美國加利福尼亞大學的博士Adleman開創了DNA計算領域，利用DNA分子成功解決了有向Hamilton路問題[1]，為人們進一步研究DNA計算做好了鋪墊，燃起了人們對解決NP完全問題的希望。在這之后的二十年里，DNA計算的研究取得了很大的成就。許多學者提出了不同的DNA計算模型，主要包括：粘貼DNA計算模型，插入-刪除系統模型，自組裝模型等，并將這些模型應用在求解NP完全問題上。對于粘貼模型，學者們利用該模型解決了不少NP完全問題，如圖的最小覆蓋問題、最大團問題、圖的頂點著色問題[2-7]629等等。本文在前人研究粘貼模型的基礎上，提出了一種新型粘貼模型，該模型不同于普通的粘貼模型，它是與分子信標相結合的一種新模型。由于分子信標具有易操作、高靈敏度、高特異性等特點，將分子信標融入粘貼模型，以分子信標作為粘貼鏈，這樣的模型操作簡單，比普通粘貼模型更易觀測，結果更準確可靠。之后，本文將該模型應用于求解可滿足性問題。可滿足性問題是NP完全問題的經典問題之一，不少其它的NP完全問題都可以轉化為可滿足性問題來求解，所以可滿足性問題非常具有代表性。

1分子信標

分子信標是一種莖環結構的寡聚核苷酸探針，分子信標由三個部分組成：環狀區、莖干區、熒光基團和猝滅基團。環狀區是分子信標的基團識別區，它的堿基序列是與靶基團互補的，堿基數一般為15～30個，能與靶基團進行特異結合；莖干區是由兩列互補的堿基序列構成的，堿基對一般為5～8個，它的兩個末端分別連接熒光基團和猝滅基團。在沒有雜交反應的情況下，分子信標呈莖環結構，熒光基團與猝滅基團距離接近，猝滅基團猝滅了熒光基團發出的熒光，檢測不到熒光信號。當發生雜交反應時，分子信標的環狀區會與靶基團進行特異性結合，分子信標的結構被破壞，熒光基團與猝滅基團的距離被拉大，熒光基團因不能被猝滅基團猝滅而發出熒光，從而能檢測到熒光信號（見圖1）。

2粘貼模型

粘貼模型是由文獻[2]622最早提出的，它在當前DNA計算模型中頗受學者們的關注。粘貼模型的優點在于在生物操作過程中既不需要酶的參與，也不需要DNA鏈的延長，并且它的材料可以循環利用。粘貼模型的重要特征在于有一個隨機存取的存儲區，在存取區中，存放了一系列的存取復合物。每個存取復合物都是由兩類單鏈的DNA分子組成的，分別是存儲鏈和粘貼鏈。一個存儲鏈是由n個不重疊的子鏈組成的，而每個子鏈是由m個堿基組成的，從而可得存儲鏈的長度l=m×n。粘貼鏈是與存儲鏈中的一個子鏈互補的鏈，顯然它的長度為m，粘貼鏈的數量小于或等于存儲鏈中子鏈的數量。存儲鏈中的每個子鏈代表一個二進制變量，只有兩種取值可能：0或1。如果一個粘貼鏈與存儲鏈中的一個互補子鏈發生退火反應，那么存儲復合物對應的位元是開的，取值為1，否則，它是關閉的，取值為0。例如，存儲復合物含有一個存儲鏈和兩個粘貼鏈，存儲鏈含有4個子鏈，每個子鏈含有5個堿基。兩個粘貼鏈分別與位1、位4的存儲子鏈互補，則存儲復合物的二進制表示是1001。

粘貼模型具有四個基本操作：

1）合并。此操作將兩個含有存儲復合物的試管T1和T2合并成試管T。

2）分離。此操作根據位元的取值，將試管T分成兩個試管T1和T2。第i位取值為1的存儲復合物存放于試管T1，第i位取值為0的存儲復合物存放于試管T2。

3）設置。此操作將試管中所有第i位取值為0的存儲復合物設置為1。

4）消除。此操作將試管中所有第i位取值為1的存儲復合物設置為0。

3基于分子信標的粘貼模型

基于分子信標的粘貼模型跟普通的粘貼模型的構造相似，它的區別在于粘貼鏈不是普通存儲鏈的子鏈的補鏈，而是用分子信標作為粘貼鏈。由于分子信標的環狀區的編碼是與靶基團互補的，該模型的粘貼鏈設計的分子信標環狀區的編碼是與存儲鏈對應的子鏈互補的。因為分子信標環部識別區的堿基個數一般為15～30個，所以分子信標作為粘貼鏈時的環部識別區的堿基數應該不低于15個 例如，存儲鏈是5′-ATCGATTACCGATATATCGATTACGTTAAC-3′，則分子信標粘貼鏈的環部識別區分別為3′-TAGCTAATGGCTATA和3′-TAGCTAATGCAATTG-5′。當分子信標與存儲鏈上對應的子鏈發生退火反應時，分子信標的環狀區與存儲鏈上對應的子鏈結合，發夾打開，發出熒光。分子信標粘貼鏈與存儲鏈上對應的子鏈發生退火反應如圖2所示。

4可滿足性問題的DNA計算

4.1可滿足性問題

可滿足性問題可表述為：由若干個析取范式合取構成的范式叫做合取范式，如F=C1∧C2∧…∧Cm，其中Ci（i=1，2，…，m）是形如l1∨l2∨…∨ln的析取式；由若干個合取范式析取構成的范式叫做析取范式，如F=C1∧C2∧…∧Cm，其中Ci（i=1，2，…，m）是形如l1∨l2∨…∨ln的合取式。li（i=1，2，…，n）表示ai或a′i，ai和a′i互為否定，它們的取值或是0或是1，“0”表示真值為真，“1”表示真值為假。可滿足性問題是指對于給定的一個含有個變量的合取范式或者析取范式，是否存在一組或多組變量的取值使得該范式的真值為1。如果Ci（i=1，2，…，m）中的變量個數都小于或等于個，那么稱其為-可滿足性問題。

4.2 可滿足性問題的DNA算法步驟

1）對給定的一個含有n變量的合取范式進行編碼。先合成2n種短的寡聚核苷酸，把這2n種寡聚核苷酸分成兩組，第一組的n種寡聚核苷酸分別表示變量x1，x2，…，xn，第二組的n種寡聚核苷酸分別表示為x1′，x2′，…，xn′，為了避免這兩組寡聚核苷酸之間的不正確雜交，這兩組的寡聚核苷酸應具有較大差異，保證它們起碼要有四個以上是不同的。然后合成這兩組寡聚核苷酸的補鏈，第一組的n種寡聚核苷酸的補鏈分別表示為x1，x2，…，xn，第二組的n種寡聚核苷酸的補鏈分別表示為x1′，x2′，…，xn′。

2）構造出的前2n種寡聚核苷酸有2n個不同的組合，而且每個組合都含有n個寡聚核苷酸對應的變量，利用雜交的方法將它們連接成2n個不同的DNA單鏈。則初始數據庫T0共有2n個存儲鏈。存儲鏈的子鏈有n個，每個子鏈的長度與分子信標的環部識別區的長度相等，分子信標的環部是由15～30個堿基構成，取分子信標的長度為15，則每個子鏈是由長度為15的堿基序列構成。粘貼鏈是前兩組的2n種寡聚核苷酸的補鏈，則粘貼鏈有2n個，而且這些粘貼鏈是特殊的鏈，它們是由分子信標構成的，分子信標的環部識別區與存儲鏈中對應的子鏈互補。

存儲鏈5′-ATCGATTACCGATATATCGATTACGTTAAC-3′，則分子信標粘貼鏈的環部識別區分別為3′-TAGCTAATGGCTATA和3′-TAGCTAATGCAATTG-5′。

3）對于范式中給定的一個子句，字句中含有變量xi或x′i，則往初始數據池T0加入對應的分子信標粘貼鏈xi或xi′，分子信標鏈的環部識別區與存儲鏈上的變量xi或xi′進行退火反應，莖環結構被破壞，形成雙鏈，并發出熒光。利用激光共聚焦顯微鏡觀察存儲鏈上的熒光情況。有熒光的存儲鏈說明滿足子句真值為真的條件，無熒光的存儲鏈說明不滿足子句真值為真的條件，記錄下有熒光的存儲鏈。

4）對第三步的產物進行加熱解鏈，解開與存儲鏈雜交的分子信標粘貼鏈，并將它們沖洗掉。

5）重復第三、四步，直到把給定范式的所有子句都檢查完為止，刪除范式中不滿足真值為真的條件的子句，最后通過測序可以讀出問題的解。

4.3 實例分析

取標準合取范式F=（x1∨x2）∧（x′1∨x′3）∧（x2∨x′3），算法步驟如下：

1）合成6種短的寡聚核苷酸，將這6種寡聚核苷酸分成兩組，第一組的3種寡聚核苷酸分別表示為x1，x2，x3，第二組的3種寡聚核苷酸分別表示為x1′，x2′，x3′，然后合成這兩組寡聚核苷酸的補鏈，它們分別為x1，x2，x3和x1′，x2′，x3′。

2）構造出的前6種寡聚核苷酸有8個不同的組合，而且每個組合都含有3個寡聚核苷酸對應的變量，利用雜交的方法將它們連接成8個不同的DNA單鏈。則初始數據庫T0共有8個存儲鏈。存儲鏈的子鏈有3個，每個子鏈的長度與分子信標的環部識別區的長度相等，分子信標的環部是由15～30個堿基構成，取分子信標的長度為15，則每個子鏈是由長度為15的堿基序列構成。粘貼鏈是前兩組的6種寡聚核苷酸的補鏈，則粘貼鏈有6個，而且這些粘貼鏈是特殊的鏈，它們是由分子信標構成的，分子信標的環部識別區與存儲鏈中對應的子鏈互補，這6種分子信標粘貼鏈的莖干末端分別連接不同顏色的熒光基團（見圖3）。

3）對于第一個子句x1Vx2，則往初始數據池T0加入對應的分子信標粘貼鏈x1和x2，分子信標鏈的環部識別區與存儲鏈上的變量x1和x2進行退火反應，莖環結構被破壞，形成雙鏈，并發出熒光。利用激光共聚焦顯微鏡觀察存儲鏈上的熒光情況?？梢钥闯?，滿足第一個子句x1∨x2的真值為真的條件的存儲鏈編號有2，3，4，5，6，7，并記錄下來（見圖4）。

4）重復第三步驟，則滿足第二個子句x′1∨x3的真值為真的條件的存儲鏈編號有0，1，2，4，5，7，滿足第三個子句x2∨x3的真值為真的條件的存儲鏈編號有1，2，4，5，6，7。刪除范式中不滿足真值為真的條件的子句后，最后通過測序可以讀出問題的解，即（0，1，1），（1，0，1），（1，1，0）和（1，1，1）。

5結論

將分子信標技術融入粘貼模型，建立一種新的模型，即以分子信標作為粘貼鏈的粘貼模型，并將這種模型應用于可滿足性問題的求解。在利用該模型求解問題的過程中，對于分子信標的粘貼鏈要求比較高，對DNA編碼的設計比較重要，分子信標的環部識別區的編碼要與存儲鏈上對應的子鏈互補。該模型操作簡單，且比普通的粘貼模型更容易觀察和檢測問題的解，從而得到更準確可靠的解。

參考文獻：

[1]ADLEMAN L M.Molecular computation of solutions to combinatorial problems[J].Science， 1994， 266（5 187）：1 021-1 023.

[2]ROWEIS S，WINFREE E，BURGOYNE R，et al.A sticker based architecture for DNA computation[J].Journal of Computational Biology， 1998， 5（4）：615-629.

[3]RARI L，THIERRIN G.Contextual insertions deletions and computability[J].Information and Computation， 1996， 131（1）：47-61.

[4]WINFREE E，LIU F，WENZLER L A，et al.Design and selfassembly of two-dimensional DNA crystals[J].Nature， 1998， 394（6）：539-544.

[5]GAO L，MA RN，XU J.DNA solution of vertex cover problem based on sticker model[J].Chinese Journal of Electronics， 2002， 11（2）：280-284.