基于DNA折紙術(shù)求解圖的頂點(diǎn)著色問題的方法

麻晶晶 許 進(jìn)

①(山西財(cái)經(jīng)大學(xué)統(tǒng)計(jì)學(xué)院 太原 030000)

②(北京大學(xué)信息科學(xué)技術(shù)學(xué)院 北京 100871)

1 引言

分子計(jì)算的設(shè)想是由Feynman[1]在20世紀(jì)60年代初首先提出的，他指出單個(gè)分子或原子能夠被用來構(gòu)建計(jì)算機(jī)的組成元件。1994年，Adleman[2]第1次通過生物化學(xué)實(shí)驗(yàn)求解了一個(gè)7個(gè)頂點(diǎn)的哈密爾頓路問題，說明了DNA計(jì)算在解決復(fù)雜的數(shù)學(xué)問題方面的能力。隨著生物學(xué)和納米技術(shù)的快速發(fā)展，分子計(jì)算也得到了極大的發(fā)展。許多不同的方法已經(jīng)證明生物分子能夠作為開發(fā)更好的計(jì)算系統(tǒng)和提高計(jì)算能力的新工具。各種不同的DNA計(jì)算模型被設(shè)計(jì)出來，如粘貼模型[3]、剪接系統(tǒng)模型[4]、表面與芯片DNA計(jì)算模型[5]、發(fā)夾狀DNA計(jì)算模型[6]、質(zhì)粒DNA計(jì)算模型[7]、基于k-臂的DNA計(jì)算模型[8]、自組裝DNA計(jì)算模型[9]、插入－刪除系統(tǒng)模型[10]、試管型DNA計(jì)算模型[11]、圖靈機(jī)DNA計(jì)算機(jī)模型[12]、布爾DNA計(jì)算機(jī)模型[13]等，以及將DNA計(jì)算的思想應(yīng)用于基因分析與疾病診斷與治療的模型等[14]。2016年，Xu[15]提出了一種探針機(jī)模型，該模型能夠求解當(dāng)今電子計(jì)算機(jī)無法處理的NP完全問題。近些年來的研究表明，DNA計(jì)算在理論、模型構(gòu)建、實(shí)驗(yàn)方法和檢測技術(shù)上都取得了很大的進(jìn)展。

與此同時(shí)，DNA自組裝技術(shù)的研究也取得了巨大的進(jìn)展。1998年Winfree等人[16]在“簡單自組裝瓦片結(jié)構(gòu)”的基礎(chǔ)上，構(gòu)建了具有足夠剛性的5種DX元件。2003年，LaBean教授的研究組構(gòu)造出一種十字形的支架結(jié)構(gòu)(即四星元件)[17]，利用這種模塊組裝成方形DNA自組裝芯片。2006年，Rothemund等人[18]成功地應(yīng)用了一條長為7000個(gè)堿基左右的M13噬菌體的單鏈，借助于200多條短的寡核苷酸鏈(釘書針鏈)，通過堿基互補(bǔ)，在特定部位折疊成復(fù)雜的2 維D N A 自組裝結(jié)構(gòu)。依照Rothemund的方法，DNA分子可以構(gòu)造人們想要的任何平面圖形，因此，他的這一方法被形象地稱為“DNA折紙術(shù)”。不滿足于僅僅構(gòu)造2維平面的簡單圖形，科學(xué)家們成功地在其它類型的DNA分子基礎(chǔ)上設(shè)計(jì)出了新的DNA折紙方法，構(gòu)造出了更為復(fù)雜高級3維DNA自組裝結(jié)構(gòu)。2011年，Han Dongran等人[19]利用DNA折紙的折疊技術(shù)，在3維空間中設(shè)計(jì)和構(gòu)造了具有復(fù)雜的空間曲面的自組裝DNA納米結(jié)構(gòu)，如球面、橢圓球面、瓶子等。之后，DNA折紙術(shù)的相關(guān)研究取得了很大的進(jìn)展[20—30]。

圖的頂點(diǎn)著色問題是著名的NP完全問題。2018年，Xu等人[31]提出了一種新穎的圖頂點(diǎn)著色DNA計(jì)算模型，該模型以一個(gè)3-著色的61個(gè)頂點(diǎn)的圖為例，設(shè)計(jì)了一種并行型聚合酶鏈反應(yīng)(Polymerase Chain Reaction， PCR)操作技術(shù)，應(yīng)用這種技術(shù)一次可以對圖中多條邊來刪除非解，使得生物操作次數(shù)大大減少，極大地提高了運(yùn)行速度。實(shí)驗(yàn)表明，99%的非可行解在構(gòu)建初始解空間時(shí)就被刪除，并利用DNA自組裝和并行PCR方法，通過識別、拼接以及組裝等技術(shù)得到解。該模型還通過如下3種方法來克服解空間指數(shù)爆炸問題：頂點(diǎn)顏色集的確定方法；子圖分解方法以及子圖中的頂點(diǎn)優(yōu)化排序方法。本文提出了一種基于DNA折紙術(shù)求解圖的頂點(diǎn)著色問題的方法，利用DNA折紙術(shù)可以構(gòu)建出具有特定形狀的DNA折紙結(jié)構(gòu)。這些結(jié)構(gòu)可以用來編碼圖的頂點(diǎn)和邊，由于這些結(jié)構(gòu)具有粘性末端，因此可以通過特異的分子雜交組裝成代表不同的圖的頂點(diǎn)著色方案的高級結(jié)構(gòu)。利用DNA-納米顆粒共聚體的屬性和電泳等實(shí)驗(yàn)方法，可以篩選出正確的符合條件的圖的頂點(diǎn)著色方案。這種方法是一種高度并行的方法，可以極大地降低求解圖的頂點(diǎn)著色問題的復(fù)雜度。

2 圖的頂點(diǎn)著色問題

本文所言之圖皆指有限、無自環(huán)、無圈的簡單無向圖，通常用G表示圖。本文用V(G)， E(G)分別表示圖G的頂點(diǎn)集和邊集。一個(gè)圖G的著色是指對G中的每個(gè)頂點(diǎn)分配一種顏色，使得相鄰的頂點(diǎn)著不同的顏色。換言之，是指對圖G中的頂點(diǎn)集V(G)的劃分：V(G)=V1∪V2∪···Vk， Vi≠φ(空集)，Vi∩Vj=φ， i =1，2， ···， k。滿足圖G正常著色的最小的顏色數(shù)稱為色數(shù)，記為χ(G)。圖G的一個(gè)k-正常頂點(diǎn)著色，簡稱為圖的k-頂點(diǎn)著色，是指用k[k≥χ(G)]種顏色對圖G進(jìn)行著色。通常用Ck(G)表示圖G的全體k著色構(gòu)成的集合。由于本文僅考慮圖的3-著色問題，故k=3，我們總是假定顏色集為C3(G)={r，b，y}，其中，r表示紅色，b表示藍(lán)色，y表示黃色。所以，求解圖的3-著色問題可以認(rèn)為是尋找從圖的頂點(diǎn)集V(G)到顏色集{r，b，y}的一種映射：f: V(G)→{r，b，y}，使得對于?uv ∈E(G)，f(u)≠f(v)。圖的3-著色問題是一個(gè)NP-完全問題。本文以一個(gè)具有6個(gè)頂點(diǎn)的簡單圖(圖1)為例說明所設(shè)計(jì)的基于DNA折紙術(shù)求解圖的頂點(diǎn)著色問題的算法。

3 基于DNA折紙術(shù)求解圖的頂點(diǎn)著色問題的算法

DNA折紙術(shù)最先由Rothmund提出，這種新的DNA自組裝策略是DNA納米技術(shù)的巨大進(jìn)步，依據(jù)這種自組裝方法，不僅2維平面的不同圖形，如正方形、圓形、笑臉等形狀可以被構(gòu)造出，而且3維立體的高級結(jié)構(gòu)也可以被構(gòu)造出。本文利用DNA折紙術(shù)構(gòu)造的不同形狀的結(jié)構(gòu)對圖G的每個(gè)頂點(diǎn)進(jìn)行編碼，通過DNA分子的雜交和一系列實(shí)驗(yàn)方法獲得圖G頂點(diǎn)著色的正確解，由于DNA折紙結(jié)構(gòu)可以在原子力顯微鏡下被觀測出，所以圖G的可行的頂點(diǎn)著色方案可以通過觀察原子力顯微鏡而得到。本文設(shè)計(jì)的基于DNA折紙術(shù)求解圖的頂點(diǎn)著色問題的算法包含以下4個(gè)步驟：(1)用DNA折紙結(jié)構(gòu)來編碼圖G的信息；(2)將DNA折紙結(jié)構(gòu)進(jìn)行退火反應(yīng)，通過自組裝過程生成問題的所有可能的解；(3)刪除非解，并提取出正確的解；(4)識別結(jié)果。以下是具體方法的描述。

3.1 編碼

圖1 一個(gè)簡單無向圖G

本文所使用的圖如圖1所示，它包括6個(gè)頂點(diǎn)、9條邊。圖2中以頂點(diǎn)1和頂點(diǎn)2為例展示了本文用DNA折紙結(jié)構(gòu)編碼圖G的頂點(diǎn)和邊的具體方法。由于本文求解的是圖的3-著色問題，所以每個(gè)頂點(diǎn)都有可能染3種顏色，即紅色、黃色和藍(lán)色。為此以DNA折紙結(jié)構(gòu)的不同形狀來代表這3種顏色，即如圖2所示，正方形的DNA折紙結(jié)構(gòu)代表頂點(diǎn)被染成紅色，圓形的折紙結(jié)構(gòu)代表頂點(diǎn)被染成黃色，三角形的DNA折紙結(jié)構(gòu)代表頂點(diǎn)被染成藍(lán)色。每個(gè)DNA折紙結(jié)構(gòu)上還具有突出的單鏈DNA，即粘性末端，這些粘性末端能依照圖G中頂點(diǎn)的鄰接關(guān)系相互雜交，粘性末端雜交的原理即DNA的兩條單鏈在合適的實(shí)驗(yàn)室條件下依照堿基互補(bǔ)配對的規(guī)則(A與T 配對，G與C 配對)雜交形成雙螺旋結(jié)構(gòu)。

例如頂點(diǎn)1與頂點(diǎn)2、頂點(diǎn)3之間有邊相連，所以頂點(diǎn)1有兩條突出的粘性末端，分別能與頂點(diǎn)2、頂點(diǎn)3上的粘性末端雜交。按照這種方法，每個(gè)頂點(diǎn)都要設(shè)計(jì)正方形、圓形和三角形3種不同的DNA折紙結(jié)構(gòu)，并且需要設(shè)計(jì)好需要的粘性末端序列，每個(gè)頂點(diǎn)所需要設(shè)計(jì)的粘性末端的數(shù)目恰好等于該頂點(diǎn)的度。同時(shí)，DNA折紙結(jié)構(gòu)上還需要設(shè)計(jì)代表頂點(diǎn)序號的標(biāo)記，以便在原子力顯微鏡下分辨頂點(diǎn)。

3.2 退火

設(shè)計(jì)好DNA折紙結(jié)構(gòu)之后，就需要將所有代表頂點(diǎn)和邊的信息的DNA折紙結(jié)構(gòu)進(jìn)行退火反應(yīng)，這個(gè)過程由DNA粘性末端序列中堿基的互補(bǔ)配對完成，這是一個(gè)隨機(jī)自由組合的反應(yīng)，也是一個(gè)高度并行的過程，這種高度的并行性能在非常短的時(shí)間內(nèi)形成問題的所有可能的解。圖3中以頂點(diǎn)1和頂點(diǎn)3為例展示了DNA折紙結(jié)構(gòu)的雜交方式。因?yàn)轫旤c(diǎn)1和頂點(diǎn)3有邊相連，所以代表頂點(diǎn)1和頂點(diǎn)3的DNA折紙結(jié)構(gòu)的其中兩條突出的粘性末端可以互相配對雜交，雜交的方式如圖中形成的雙鏈所示。值得注意的是，由于頂點(diǎn)被賦予了顏色，所以兩個(gè)頂點(diǎn)結(jié)構(gòu)雜交之后可能是顏色相同的，也可能是顏色不同的，如圖3(a)所示的雜交結(jié)構(gòu)為頂點(diǎn)1和頂點(diǎn)3都是紅色，如圖3(b)所示的雜交結(jié)構(gòu)是頂點(diǎn)1為黃色，頂點(diǎn)3為紅色。有邊相連的頂點(diǎn)被染成相同的顏色是不符合圖的頂點(diǎn)染色問題的要求的，所以這種錯(cuò)誤的解需要被刪除掉。為了實(shí)現(xiàn)這個(gè)目的，本文在設(shè)計(jì)DNA折紙結(jié)構(gòu)時(shí)預(yù)先給每一種顏色的DNA折紙結(jié)構(gòu)設(shè)計(jì)了一段代表其顏色的特異序列，如圖3中所示，在兩個(gè)頂點(diǎn)結(jié)構(gòu)的雙鏈雜交部分的兩側(cè)即為本文預(yù)先設(shè)計(jì)的代表頂點(diǎn)顏色的特異序列，如圖3(a)所示的頂點(diǎn)雜交結(jié)構(gòu)中，頂點(diǎn)1和頂點(diǎn)3都被染成了紅色，所以特異序列也是代表紅色的序列，圖中用紅線表示；而如圖3(b)所示的頂點(diǎn)雜交結(jié)構(gòu)中，頂點(diǎn)1染成了黃色，頂點(diǎn)3為紅色，所以特異序列也為相應(yīng)的黃色和紅色序列，圖中分別用黃線和紅線表示?？梢韵胂?，當(dāng)頂點(diǎn)結(jié)構(gòu)的粘性末端沒有雜交形成雙螺旋結(jié)構(gòu)之前，這些特異序列(圖3中的短的紅色和黃色線段)是游離的而且靠近的幾率很小，只有當(dāng)頂點(diǎn)結(jié)構(gòu)的粘性末端雜交形成雙螺旋之后這些特異序列才會(huì)被拉近距離并且靠得很近無法分開。這樣的設(shè)計(jì)將在后面刪除非解的步驟中發(fā)揮作用。

圖2 編碼頂點(diǎn)和邊的DNA折紙結(jié)構(gòu)

圖3 DNA折紙結(jié)構(gòu)的退火方式

3.3 刪除非解并提取正確的解

經(jīng)過DNA折紙結(jié)構(gòu)的退火之后，圖G的頂點(diǎn)三著色問題的所有可能的解都已經(jīng)形成，接下來的操作就是刪除所有的非解，即刪除掉退火結(jié)構(gòu)中所有的頂點(diǎn)有邊相連并且被染成相同顏色的染色方案，這個(gè)過程通過與DNA-納米顆粒共聚體的雜交和瓊脂糖凝膠電泳分離來實(shí)現(xiàn)。圖4展示了用DNA-納米顆粒共聚體與退火結(jié)構(gòu)進(jìn)行雜交的方法。如圖4所示，金納米顆粒上修飾了能與代表頂點(diǎn)顏色的兩段特異序列雜交的互補(bǔ)序列，值得注意的是這段互補(bǔ)序列正好是特異序列的兩倍，當(dāng)且僅當(dāng)兩個(gè)雜交的頂點(diǎn)結(jié)構(gòu)為染相同的顏色時(shí)，代表頂點(diǎn)顏色的兩段特異序列才能被拉近距離，這樣就能與DNA-納米顆粒共聚體上的互補(bǔ)序列雜交。圖4中以頂點(diǎn)1和頂點(diǎn)3為例展示了DNA-納米顆粒共聚體與退火結(jié)構(gòu)進(jìn)行雜交的方法。頂點(diǎn)1和頂點(diǎn)3有邊相連，它們有3種被染成相同顏色的情況，即同為紅色、同為黃色和同為藍(lán)色。如果退火結(jié)構(gòu)中任意兩個(gè)有邊相連的點(diǎn)都染異色，那么DNA-納米顆粒共聚體就不會(huì)與其雜交，這是因?yàn)楸疚脑O(shè)計(jì)的特異序列比較短，依照雙鏈DNA分子的特性，在實(shí)驗(yàn)所需的溫度條件下，單獨(dú)一段長度較短的特異序列無法與互補(bǔ)序列雜交形成雙鏈，只有兩段特異序列組成的長序列才能與互補(bǔ)序列雜交形成雙鏈。

圖4 DNA-納米顆粒共聚體與退火結(jié)構(gòu)的雜交

經(jīng)過與DNA-納米顆粒共聚體雜交之后，就要將產(chǎn)物進(jìn)行瓊脂糖凝膠電泳。在瓊脂糖凝膠電泳中雜交了DNA-納米顆粒共聚體的退火結(jié)構(gòu)由于分子量較大在電泳的凝膠中處于落后的位置，沒有雜交DNA-納米顆粒共聚體的退火結(jié)構(gòu)由于分子量較小處于領(lǐng)先的位置，就可以被回收回來，即為正確的解，將會(huì)用于下一步的識別和分析。

3.4 識別結(jié)果

由于DNA折紙結(jié)構(gòu)可以通過原子力顯微鏡觀察到，因此對于上一步回收的退火結(jié)構(gòu)，可以用原子力顯微鏡進(jìn)行觀察，以確定最終的圖G的頂點(diǎn)三著色方案。由于紅色、黃色、藍(lán)色分別由正方形、圓形和三角形DNA折紙結(jié)構(gòu)表示，因此在原子力顯微鏡下就可以通過辨認(rèn)折紙結(jié)構(gòu)的形狀和頂點(diǎn)的標(biāo)記確認(rèn)正確答案。圖5顯示了一種雜交結(jié)構(gòu)，這是一種正確的圖G的頂點(diǎn)三著色方案。

圖5 圖G的頂點(diǎn)三著色方案的正確解

4 結(jié)論

圖的頂點(diǎn)著色問題有著非常廣泛的理論與應(yīng)用研究意義，各種DNA計(jì)算模型都將其作為研究的目標(biāo)。DNA自組裝技術(shù)為DNA計(jì)算提供了新的方法，各種DNA自組裝計(jì)算模型也被用于解決各種不同的NP完全問題。本文中，我們利用DNA折紙結(jié)構(gòu)編碼圖的信息，通過DNA折紙結(jié)構(gòu)上粘性末端的自組裝過程，構(gòu)建了一種圖的頂點(diǎn)著色問題的非確定性算法。通過構(gòu)建數(shù)以億計(jì)的參與計(jì)算的DNA折紙結(jié)構(gòu)，該算法可以并行地測試每種可能的頂點(diǎn)著色方案。對于給定的n個(gè)頂點(diǎn)和m條邊的圖，頂點(diǎn)著色方案存在與否以及存在幾種頂點(diǎn)著色方案都可以通過相應(yīng)的DNA折紙結(jié)構(gòu)的自組裝過程和一系列實(shí)驗(yàn)方法計(jì)算出來，計(jì)算結(jié)果可以直接通過原子力顯微鏡觀察到，這種方法具有高度的并行性，類似的基于DNA折紙術(shù)的方法在求解NP完全問題方面具有巨大的潛力。