嚴(yán)洋洋，殷志祥*，崔建中,b，唐 震

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

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

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

1 相關(guān)研究

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

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

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

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

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

2 DNA折紙系統(tǒng)

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

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

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

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

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

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

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

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

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

圖4DNA步行器行走示意圖

3 最大團(tuán)問題

3.1 最大團(tuán)問題

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

3.2 最大團(tuán)基本算法

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

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

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

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

4 實(shí)例分析

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

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

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

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

圖5 6頂點(diǎn)的簡(jiǎn)單圖及其補(bǔ)圖

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

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

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

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

可知，圖5中圖G的最大團(tuán)為（V1V2V3V4V6），對(duì)應(yīng)于（111101）。

5 小結(jié)

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