一種基于DNA折紙系統(tǒng)求解最大團問題的模型

嚴洋洋，殷志祥*，崔建中,b，唐 震

（安徽理工大學 a.數(shù)學與大數(shù)據(jù)學院；b.電氣與信息工程學院，安徽 淮南 232001）

由于DNA分子具有良好的可編程性，可利用它的雙螺旋結(jié)構(gòu)和堿基互補配對原則可以將其折疊成不同形狀、不同尺寸的DNA納米材料[1]。

早在1982年，Seeman就提出了利用DNA分子創(chuàng)建不同簡單結(jié)構(gòu)的想法和DNA納米材料的概念。即利用堿基互補配對的原則和生物技術(shù)合成任意序列的DNA片段的能力，構(gòu)造出不同的納米結(jié)構(gòu)，隨之，他構(gòu)造了許多分支型的復合體，如DX、TX、PX等，并將其應用到四面體、八面體等納米結(jié)構(gòu)的自組裝中[2]。此后，出現(xiàn)了越來越多的不同形狀、不同尺寸的二維DNA自組裝體。如Yan[3]設計了四條手臂的交叉體、He[4]構(gòu)造的二維陣列。

1 相關(guān)研究

2006年，Pauw提出了一種由DNA構(gòu)建空間結(jié)構(gòu)的新方法DNA折紙術(shù)[5]。它是一種具有里程碑性的全新的DNA自組裝方法，能夠很容易得構(gòu)造出更復雜、更多樣的DNA自組裝體。與傳統(tǒng)的交叉策略的DNA自組裝不同，DNA折紙是將一條長的單的DNA鏈（腳手架鏈）在一些預設的短的DNA鏈（訂書釘鏈）指導下，利用DNA分子堿基互補配對的原則，構(gòu)造出不同形狀、不同尺寸納米結(jié)構(gòu)，如笑臉、三角形、星型等[6]。對比使用傳統(tǒng)的自主裝方法構(gòu)造出的納米結(jié)構(gòu)，其優(yōu)點在于構(gòu)造出的納米結(jié)構(gòu)更穩(wěn)定、更復雜、更具有可控性及尋址性。此后，DNA折紙進入了快速發(fā)展時期，漸漸地拓展到三維空間。

近十年的研究成果表明，DNA折紙已經(jīng)越來越強大了[7-15]。由DNA分子創(chuàng)建的納米結(jié)構(gòu)越來越多樣化、復雜化，但其目標絕不是將其設計成各種各樣的結(jié)構(gòu)，而更多的是讓它們“動”起來[16-18]。不僅如此，隨著DNA折紙的發(fā)展，許多應用也得以實現(xiàn)，如藥物傳送[19-20]、納米機器人[21-22]等。

最大團問題（maximum clique problem）是一個十分經(jīng)典的 NP（non-deterministic polynomial）完全問題，也是圖論的一個十分重要的研究分支。在很多方面都有著舉足輕重的應用，如市場分析、方案選擇等。常用的求解算法基本分為兩類，一類是確定性算法，如分支限界法；一類是啟發(fā)式算法，如蟻群算法、智能搜索算法等。但是隨著社會的發(fā)展，圖也越來越大，一些常用的算法局限性也暴露出來，于是，人們的開始尋求突破。隨著DNA分子的研究的進展，DNA的高并行性、操作性強，儲存信息廣的優(yōu)勢出現(xiàn)在人們的視野中，開始著手于利用DNA計算解決這類NP問題。

Adleman[23]對一個7頂點6條邊的圖進行DNA編碼，成功的求出了該圖的Hamilton路徑。Ouyang[24]等就已經(jīng)借助DNA計算求解圖的最大團問題。Yang[25]等構(gòu)造了圓形DNA分子模型求解最大團問題。文獻[26-27]分別利用DNA三維自組裝算法和粘貼模型成功的求解了圖的最大團問題。李艷梅利用DEM求解圖的最大團[28]。陳芳等利用三鏈DNA求解最大團問題[29]。

本文主要是利用DNA折紙系統(tǒng)求解最大團問題，該折紙系統(tǒng)由DNA步行器、雙DNA機器和DNA折紙卡槽三部分組成[30]。我們首先對圖中的各個頂點進行指派，排列出所有可能的情況，生成數(shù)據(jù)池，然后利用DNA折紙系統(tǒng)進行篩選，移除不符合團定義的DNA步行器，最后利用于補圖進行檢測，根據(jù)在透射電鏡下DNA步行器手上發(fā)夾結(jié)構(gòu)的個數(shù)，來判斷和讀取最大團。

2 DNA折紙系統(tǒng)

該系統(tǒng)由一個三角形形狀的DNA步行器，雙態(tài)的DNA機器和DNA折紙卡槽三部分組成，如圖1。其中，三角形的DNA步行器是由7條3’端為粘性末端的單鏈DNA折疊而成的折紙結(jié)構(gòu)，這些粘性末端充當DNA步行器的“手”和“足”?！笆帧狈謩e用 H1～H3 表示，“足”分別用 F1～F4 表示，F(xiàn)4被固定在在DNA折紙基底上，并且每條手上綁有2種不同大小的發(fā)夾結(jié)構(gòu)，共6個發(fā)夾結(jié)構(gòu)，分別用a～f來表示。該DNA步行器借助鏈置換在折紙基底上旋轉(zhuǎn)移動。

圖1DNA折紙系統(tǒng)基本組成

圖1(b)所示的雙態(tài)DNA機器，能夠捕獲特定信息，定向識別的機器。兩種狀態(tài)分別為PX和JX2。當處于PX狀態(tài)時，表明接收或者捕獲預定的信息。當處于JX2狀態(tài)時，表明不接收或者拒絕信息。圖1(c)展示的是DNA折紙卡槽，該折紙卡槽是由一條M13鏈和202條短鏈折疊而成，下方是折紙基底，基底上延伸出9條單鏈，組成3個三角形的站點，充當DNA步行器裝配的軌道，站點上方的3個白色的方框為3個插槽，分別與雙態(tài)的DNA機器通過互補的單鏈連接。

圖2中左側(cè)中間的三角形為帶有發(fā)夾結(jié)構(gòu)的DNA步行器。該DNA步行器借助鏈置換在折紙基底的軌道上行走，每走一步，順時針旋轉(zhuǎn)120°。當整個組裝完成后，可根據(jù)透射電鏡觀察DNA步行器上發(fā)夾結(jié)構(gòu)的個數(shù)來判斷最后的接收的信息是不是滿足預定的結(jié)果。

圖2 組裝完成后，處于PX狀態(tài)的DNA折紙系統(tǒng)

下面將分別闡述DNA步行器是如何行走的和如何進行鏈置換反應解開發(fā)夾。

處于PX狀態(tài)的DNA機器如圖3，DNA步行器手上發(fā)夾結(jié)構(gòu)解開的過程。在解開發(fā)夾結(jié)構(gòu)的的過程中，主要是DNA機器和DNA步行器的手H1通過鏈置換反應進行的。圖3(a)是的DNA步行器處于的PX狀態(tài)的DNA機器相接近，圖3(b)是的DNA步行器的一只手上的發(fā)夾與處于PX狀態(tài)的DNA機器進行鏈置換，圖3(c)是處于PX狀態(tài)的DNA機器與解開DNA步行器手上一個發(fā)夾結(jié)構(gòu)逐漸遠離的過程。

DNA步行器從一個站點到下一個站點行走的過程，如圖4。數(shù)字1～7分別組成DNA步行器的 7 條單鏈，1～3 是它的“手”，4～7 為其“足”。O—*是從折紙基底上延伸出來的9條輔助單鏈，充當3個三角形的站點，起到輔助步行器行走的作用。A—*是步行器足上錨鏈，能夠與O—*和DNA步行器的足互補。FA—*是能夠與A—*完全互補的短鏈，其可以與DNA步行器的足發(fā)生鏈置換，解綁DNA步行器與折紙基底的鏈接，讓DNA步行器在預定的軌道上進行行走。圖4左側(cè)是行走機器人處于第一個站點，此時的DNA步行器被固定，“足”4和5分別被單鏈A-1和A-2捆綁在單鏈O-1和O-3上，“足”7也被單鏈A-4捆綁在單鏈 O-2 上，“足”6,沒有被捆綁?！笆帧? 慢慢接近處于PX狀態(tài)的DNA機器，以便進行鏈置換，解開發(fā)夾。開始添加短鏈FA-1和FA-4，使單鏈A-1和A-4被解綁出來，“足”5和7被解綁，“足”4依舊被捆綁著，同再添加A-3將“足”6和A-4固定，“足”7沒有被捆綁，這時的DNA步行器旋轉(zhuǎn)了120°，向前前進了一步，處于第一站點與第二站點中間位置。中間是DNA步行器在第一站點與第二站點中間位置的狀態(tài)，此時添加單鏈FA-2與單鏈A-2發(fā)生鏈置換，此時單鏈4與O-3解綁，“足”6這時被捆綁，接著添加單鏈A-5將單鏈5與O-6綁定，加入單鏈A-6將“足”7捆綁在O-5上“手”2慢慢接近處于PX狀態(tài)的DNA機器，去解開發(fā)夾右側(cè)，這時的DNA步行器再次順時針旋轉(zhuǎn)了120°，再次向前行走了一步，位于第二站點。從第二站點到第三站點DNA步行器在預定軌道上行走過程相似。當DNA步行器到達第三站點后，DNA步行器的“足”可以通過添加綁定鏈的互補鏈進行解綁，這時DNA步行器被置換出來。當DNA步行器置換出來后，再次將其和組裝折紙基底進行檢測，再次行走的過程和前面類似，當DNA步行器再次被置換后，進行解的讀取。

圖3 DNA步行器上進行鏈置換解開的三種發(fā)夾結(jié)構(gòu)

圖4DNA步行器行走示意圖

3 最大團問題

3.1 最大團問題

給定無向圖G=(V,E)，其中V是非空集合，是圖G頂點集；E是圖G的邊集，設U是G的一個頂點子集，對任意兩個頂點u，v∈U，都和E中的邊相鄰，則稱U是圖G團。若對G任意的其它團U'都有則U是G的最大團。

3.2 最大團基本算法

對于n個頂點簡單圖來說，可以利用0和1的形式來指派，即當圖的某一頂點在團中，用1指派，當圖的某一頂點不在團中，用0指派，即如果該頂點在團中取值為1，不在團中取值為0。因此，可以用0和1的構(gòu)成的n位字符串來表示全部組合的情況，則稱這些n位字符串構(gòu)成的集合為數(shù)據(jù)池。為了符合最大團的定義，因而對數(shù)據(jù)池進行篩選，保留真正的解。

Step 1:對每個頂點進行指派，折疊出代表不同頂點的DNA步行器（利用步行器手上綁有發(fā)夾結(jié)構(gòu)進行頂點的區(qū)分），即生成的數(shù)據(jù)池。

Step 2:為了符合最大團的定義，需要對數(shù)據(jù)池各個頂點進行篩選。同時，我們借助圖的補圖進行求解，對一個圖來說，團在其中，則團中各個頂點都是鄰接的，那么在其補圖中，該團對應的就是空圖。意思就是，在補圖中相鄰接的兩個頂點，在圖中就是不鄰接的，那么這兩個相鄰接的頂點就不可能在同一個團中。因此，對指派的字符串，圖中相鄰的兩個頂點不可能同時為0，而在其補圖中，相鄰接的兩頂點不會出現(xiàn)同時為1。因此，借助組裝完成后的DNA步行器進行觀測，折疊出在補圖中相鄰接的兩個頂點的發(fā)夾結(jié)構(gòu)的DNA步行器，然后加入到組裝完成的折紙基底，通過逐步的鏈置換，進行順時針120°旋轉(zhuǎn)，解開DNA步行器手上的發(fā)夾，能夠解開發(fā)夾結(jié)構(gòu)，就是其補圖中相鄰接的兩頂點，則該頂點不在團中。篩選出能解開發(fā)夾結(jié)構(gòu)的DNA步行器，移除不能解開發(fā)夾結(jié)構(gòu)的DNA步行器，余下的就是符合團定義的。

Step 3:借助透射電鏡進行觀測組裝完成后置換出的DNA步行器，根據(jù)手上發(fā)夾結(jié)構(gòu)的個數(shù)，找出最大團以及判斷最大團中頂點的個數(shù)。

4 實例分析

以圖5為例給出利用DNA折紙系統(tǒng)求解最大團問題。

Step1：對圖中各個頂點進行指派，生成數(shù)據(jù)池。由于某一頂點可能在團中，也可能不在團中，故每個頂點有兩種不同的指派。圖5有6個頂點，則有12種不同的指派，即10和11,20和21,30和31,40和 41，50和 51,60和 61。下面對頂點進行區(qū)分，若Vi在團中，由定義可知，Vi=1，則不在其補圖中。若Vi不在團中，由定義可知Vi=0，則在其補圖中。如圖 中 頂 點V1、V4、V5構(gòu) 成一個團 ，用（100110）來表示。由此團中所有的可能性組合為26種，稱該集合為數(shù)據(jù)池。故尋找最大團，就是找其補圖中所含頂點最少的DNA步行器上的發(fā)夾結(jié)構(gòu)，即發(fā)夾結(jié)構(gòu)個數(shù)最少的DNA步行器。下面設計DNA步行器每只“手”上的發(fā)夾結(jié)構(gòu)。

接著利用DNA折紙折疊出綁有發(fā)夾結(jié)構(gòu)的DNA步行器、雙態(tài)的DNA機器、DNA折紙卡槽。將綁有發(fā)夾結(jié)構(gòu)的DNA步行器分為12組，前6組的代表頂點在團中，分別記為PV1,PV2,…,PV6，分別對應于V1=1，V2=1，…，V6=1。后 6 組的代表頂點不在團中，分別記為分別對應于V1=0，V2=0，…，V6=0。對頂點進行區(qū)分，包含6頂點的團對應于（111111），空圖對應于（000000）。

Step 2：利用補圖進行檢查補圖中相鄰接的點，通過DNA折紙直接獲得最大團，圖5（b）中，頂點V1和V3、V6鄰接，頂點V2和V4、V6鄰接。由此可知，數(shù)據(jù)池中V1和V3同時存在（指派分別為11和31），V1和V6同時存在（指派分別為11和61），V2和V4同時存在（指派分別為21和41），V2和V6同時存在（指派分別為21和61）。

圖5 6頂點的簡單圖及其補圖

這里對V1和V3鄰接的情況進行解釋，將數(shù)據(jù)池分為兩組：I組：只含有 11，II組只含有 31，分別加入到折紙基底上進行自組裝。將折紙基底組裝完成后，將DNA步行器組裝進去。為了使DNA步行器能夠逐步向前旋轉(zhuǎn)移動，則逐步的加入DNA短鏈：

最后再加入FA-7,FA-8,FA-9，目的是將DNA步行器置換出來，整個組裝過程DNA步行器兩次被置換出來，因而需要再次將DNA步行器同折紙基底進行組裝，當?shù)诙沃脫Q完成后，滿足條件，進行解的讀取。經(jīng)過一系列的旋轉(zhuǎn)、自組裝，I組中代表11的發(fā)夾結(jié)構(gòu)解開，II組中代表31的發(fā)夾結(jié)構(gòu)解開。然后在將I組和II組混合，這樣數(shù)據(jù)池中就再不包含V1和V3同時存在的情況。借助透射電鏡觀測，從該系統(tǒng)中直接觀測的折紙結(jié)構(gòu)結(jié)果如下：

對于補圖中的V1和V6、V2和V4、V2和V6，進行和頂點V1和V3一樣的折紙自組裝。這樣最后的數(shù)據(jù)池中就全部是符合團定義的頂點。

Step 3：找出最大團以及最大團中頂點的個數(shù)，可以借助透射電鏡觀察，數(shù)據(jù)池中符合團定義的綁有發(fā)夾結(jié)構(gòu)DNA步行器。因為是借助補圖完成的，所以找最大團就是找補圖中符合團定義的綁有發(fā)夾結(jié)構(gòu)個數(shù)最少DNA步行器，從該系統(tǒng)中觀察到最大團的折紙結(jié)構(gòu)為：

可知，圖5中圖G的最大團為（V1V2V3V4V6），對應于（111101）。

5 小結(jié)

本文利用DNA折紙術(shù)的原理，設計了DNA折紙系統(tǒng)，并將其應用于求解圖的最大團問題。該系統(tǒng)主要包括DNA步行器、雙態(tài)DNA機器和DNA折紙卡槽。首先對圖中的頂點進行指派，組合出所有可能的情況，生成數(shù)據(jù)池。然后利用DNA折紙系統(tǒng)進行篩選，篩除不符合團定義的DNA步行器，最后利用于補圖進行檢測，通過根據(jù)透射電鏡觀察DNA步行器手上發(fā)夾結(jié)構(gòu)的個數(shù)，讀取最大團。該系統(tǒng)不僅具有可預測性和可編程性等特點，而且實驗操作，擺脫了試管的束縛，解決的問題的速率也大大提高。實驗的結(jié)果通過電鏡就可以觀察的到，十分便捷。不過這種方法任有一些不足，如給定圖的最大團的頂點數(shù)不能過多，同時發(fā)夾結(jié)構(gòu)設計的不能太大。這個缺陷需要進一步改進。