基于DNA折紙術求解圖的頂點著色問題的方法

麻晶晶 許 進

①(山西財經大學統計學院 太原 030000)

②(北京大學信息科學技術學院 北京 100871)

1 引言

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

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

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

2 圖的頂點著色問題

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

3 基于DNA折紙術求解圖的頂點著色問題的算法

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

3.1 編碼

圖1 一個簡單無向圖G

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

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

3.2 退火

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

圖2 編碼頂點和邊的DNA折紙結構

圖3 DNA折紙結構的退火方式

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

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

圖4 DNA-納米顆粒共聚體與退火結構的雜交

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

3.4 識別結果

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

圖5 圖G的頂點三著色方案的正確解

4 結論

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