陳玉華　殷志祥

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

關(guān)鍵詞：分子信標(biāo)；粘貼模型；可滿足性問題

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

1分子信標(biāo)

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

2粘貼模型

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

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

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

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

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

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

3基于分子信標(biāo)的粘貼模型

基于分子信標(biāo)的粘貼模型跟普通的粘貼模型的構(gòu)造相似，它的區(qū)別在于粘貼鏈不是普通存儲鏈的子鏈的補鏈，而是用分子信標(biāo)作為粘貼鏈。由于分子信標(biāo)的環(huán)狀區(qū)的編碼是與靶基團互補的，該模型的粘貼鏈設(shè)計的分子信標(biāo)環(huán)狀區(qū)的編碼是與存儲鏈對應(yīng)的子鏈互補的。因為分子信標(biāo)環(huán)部識別區(qū)的堿基個數(shù)一般為15～30個，所以分子信標(biāo)作為粘貼鏈時的環(huán)部識別區(qū)的堿基數(shù)應(yīng)該不低于15個 例如，存儲鏈?zhǔn)?′-ATCGATTACCGATATATCGATTACGTTAAC-3′，則分子信標(biāo)粘貼鏈的環(huán)部識別區(qū)分別為3′-TAGCTAATGGCTATA和3′-TAGCTAATGCAATTG-5′。當(dāng)分子信標(biāo)與存儲鏈上對應(yīng)的子鏈發(fā)生退火反應(yīng)時，分子信標(biāo)的環(huán)狀區(qū)與存儲鏈上對應(yīng)的子鏈結(jié)合，發(fā)夾打開，發(fā)出熒光。分子信標(biāo)粘貼鏈與存儲鏈上對應(yīng)的子鏈發(fā)生退火反應(yīng)如圖2所示。

4可滿足性問題的DNA計算

4.1可滿足性問題

可滿足性問題可表述為：由若干個析取范式合取構(gòu)成的范式叫做合取范式，如F=C1∧C2∧…∧Cm，其中Ci（i=1，2，…，m）是形如l1∨l2∨…∨ln的析取式；由若干個合取范式析取構(gòu)成的范式叫做析取范式，如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”表示真值為假?？蓾M足性問題是指對于給定的一個含有個變量的合取范式或者析取范式，是否存在一組或多組變量的取值使得該范式的真值為1。如果Ci（i=1，2，…，m）中的變量個數(shù)都小于或等于個，那么稱其為-可滿足性問題。

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

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

2）構(gòu)造出的前2n種寡聚核苷酸有2n個不同的組合，而且每個組合都含有n個寡聚核苷酸對應(yīng)的變量，利用雜交的方法將它們連接成2n個不同的DNA單鏈。則初始數(shù)據(jù)庫T0共有2n個存儲鏈。存儲鏈的子鏈有n個，每個子鏈的長度與分子信標(biāo)的環(huán)部識別區(qū)的長度相等，分子信標(biāo)的環(huán)部是由15～30個堿基構(gòu)成，取分子信標(biāo)的長度為15，則每個子鏈?zhǔn)怯砷L度為15的堿基序列構(gòu)成。粘貼鏈?zhǔn)乔皟山M的2n種寡聚核苷酸的補鏈，則粘貼鏈有2n個，而且這些粘貼鏈?zhǔn)翘厥獾逆?，它們是由分子信?biāo)構(gòu)成的，分子信標(biāo)的環(huán)部識別區(qū)與存儲鏈中對應(yīng)的子鏈互補。

存儲鏈5′-ATCGATTACCGATATATCGATTACGTTAAC-3′，則分子信標(biāo)粘貼鏈的環(huán)部識別區(qū)分別為3′-TAGCTAATGGCTATA和3′-TAGCTAATGCAATTG-5′。

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

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

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

4.3 實例分析

取標(biāo)準(zhǔn)合取范式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）構(gòu)造出的前6種寡聚核苷酸有8個不同的組合，而且每個組合都含有3個寡聚核苷酸對應(yīng)的變量，利用雜交的方法將它們連接成8個不同的DNA單鏈。則初始數(shù)據(jù)庫T0共有8個存儲鏈。存儲鏈的子鏈有3個，每個子鏈的長度與分子信標(biāo)的環(huán)部識別區(qū)的長度相等，分子信標(biāo)的環(huán)部是由15～30個堿基構(gòu)成，取分子信標(biāo)的長度為15，則每個子鏈?zhǔn)怯砷L度為15的堿基序列構(gòu)成。粘貼鏈?zhǔn)乔皟山M的6種寡聚核苷酸的補鏈，則粘貼鏈有6個，而且這些粘貼鏈?zhǔn)翘厥獾逆湥鼈兪怯煞肿有艠?biāo)構(gòu)成的，分子信標(biāo)的環(huán)部識別區(qū)與存儲鏈中對應(yīng)的子鏈互補，這6種分子信標(biāo)粘貼鏈的莖干末端分別連接不同顏色的熒光基團（見圖3）。

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

4）重復(fù)第三步驟，則滿足第二個子句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結(jié)論

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

參考文獻：

[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.