一種基于DNA自組裝模型求解最大團(tuán)問題的算法＊

周炎濤，李肯立，羅 興，黎福海，朱 青

（1.湖南大學(xué) 電氣與信息工程學(xué)院，湖南 長(zhǎng)沙 410082； 2.湖南大學(xué) 信息科學(xué)與工程學(xué)院，湖南 長(zhǎng)沙 410082）

最大團(tuán)問題（Maximum clique problem，MCP）又稱為最大獨(dú)立集問題，是圖論中的一個(gè)經(jīng)典組合優(yōu)化問題，也是一類NP完全問題[1].求解MCP算法主要有二類：確定性算法和啟發(fā)式算法，前者有回溯法、分支限界法等 .隨著問題規(guī)模的增大（頂點(diǎn)增多和邊密度變大），求解問題的時(shí)間復(fù)雜度越來越高，確定性算法顯得無能為力，不能有效地解決這些NP完全問題 .后者有蟻群算法、順序貪婪算法、DLS－MC算法和智能搜索算法等，大部分確定性算法所不能解決的圖，用啟發(fā)式算法都能得到有效解決，但啟發(fā)式算法不一定能找到最優(yōu)解，有時(shí)只能找到近似值[2].近年來，常借鑒算法之間優(yōu)勢(shì)互補(bǔ)策略，形成新的混合啟發(fā)式算法來求解最大團(tuán)問題[3].

DNA計(jì)算是應(yīng)用分子生物技術(shù)進(jìn)行計(jì)算的新方法，具有高度并行性、大容量、低能耗等特點(diǎn)，為解決NP完全問題開辟了一條新途徑[4].自Adleman首次運(yùn)用DNA計(jì)算來解決NP問題以來[5]，研究者對(duì)最大團(tuán)問題的分子求解方法進(jìn)行了很多有益的嘗試，如基于粘貼模型的最大團(tuán)問題算法[6]、質(zhì)粒DNA算法[7]、閉環(huán)求解最大團(tuán)問題算法[8]等，但這些方法均存在實(shí)驗(yàn)操作步驟過多、活體內(nèi)不易操作以及環(huán)化效率不高等弊端.此外，Brun采用自組裝DNA計(jì)算給出了路徑尋找問題[9]，以及可滿足性問題的自組裝計(jì)算模型的解決方案[10].文獻(xiàn)[11]在分布式系統(tǒng)中建立自組裝模型解決自由等待一致性問題 .文獻(xiàn)[12]將AuNP自組裝聚合色變與DNA計(jì)算相結(jié)合，構(gòu)建了系列基本邏輯計(jì)算模型，等等.

在DNA計(jì)算機(jī)研究中，所建模型的好壞直接影響著DNA計(jì)算中諸多問題，如編碼的難易程度、整個(gè)生物操作或生化反應(yīng)的設(shè)計(jì)、解空間的大小、計(jì)算時(shí)間多少、應(yīng)用范圍以及通用性的程度等.目前DNA計(jì)算模型有很多[13]，其中自組裝DNA計(jì)算模型是通過DNA分子間的相互作用形成特定的構(gòu)型來完成計(jì)算過程 .它組合了DNA計(jì)算、Ting理論和DNA納米技術(shù)，成為目前備受關(guān)注的模型之一[14－15].在計(jì)算過程中，它避免了其他DNA計(jì)算模型所需要的眾多實(shí)驗(yàn)操作次數(shù)，減少了操作帶來的時(shí)間消耗和誤差傾向.分子自組裝體系是一個(gè)高度組織、高度有序、結(jié)構(gòu)化、功能化和信息化的復(fù)雜系統(tǒng)，對(duì)研究分子自組裝特性并求解最大團(tuán)問題極有價(jià)值.本文采用DNA自組裝模型，設(shè)計(jì)出相應(yīng)的DNA tiles分子，利用基因工程的生物操作，提出一種基于DNA自組裝模型求解最大團(tuán)問題的算法.該算法實(shí)驗(yàn)操作復(fù)雜度為常數(shù)級(jí)，既大大減少了因?yàn)槿藶閷?shí)驗(yàn)操作所帶來的誤差，又保證了實(shí)驗(yàn)結(jié)果的準(zhǔn)確性.

1 DNA自組裝模型

DNA的自組裝可形成一維、二維、三維結(jié)構(gòu).本文主要利用其形成的二維平面結(jié)構(gòu)來解決最大團(tuán)問題.1998年，根據(jù) Wang的tiles理論，Winfree設(shè)計(jì)了雙交叉分子DX[16]，這個(gè)DX就充當(dāng)了tiles的作用，通過自組裝就能實(shí)現(xiàn)所需的計(jì)算.理論上有5種可能的DX結(jié)構(gòu)，但通過大量實(shí)驗(yàn)證明，只有DAO和DAE這2種結(jié)構(gòu)是穩(wěn)定的[16].抽象的DAO和DAE結(jié)構(gòu)如圖1所示.

圖1 DAO，DAE抽象結(jié)構(gòu)Fig.1 Abstractive structures of DAO and DAE

觀察圖1可知，DAO結(jié)構(gòu)包含4條DNA鏈，其中有2條鏈分布在2條雙螺旋上，另外2條分布在一條雙螺旋上 .相比之下，DAE結(jié)構(gòu)包含5條DNA鏈，其中有3條鏈分布在2條雙螺旋上，另外2條鏈分布在一條雙螺旋上.由于DX可有4個(gè)粘性末端，故可利用這些粘性末端來實(shí)現(xiàn)所需要的計(jì)算.Winfree使用了帶顏色的tiles來模擬雙交叉分子的計(jì)算過程，規(guī)定只有具有相同顏色的邊才能夠結(jié)合形成較大的格局，其反應(yīng)過程如圖2所示.

圖2 DX計(jì)算過程模擬Fig.2 Process simulation of DX computing

根據(jù)Wang的tiles理論模型的形式化描述以及Yuriy Brun引入DNA 的tiles自組裝模型[17]，結(jié)合最大團(tuán)問題的特點(diǎn)可將基于DAE結(jié)構(gòu)的自組裝模型表示為S＝〈T，g，τ〉，其中T為DAE塊的集合，g為能量函數(shù)，τ為常數(shù).相應(yīng)的符號(hào)描述如下：

1）Σ：DAE塊中所有粘性末端所表示符號(hào)的集合（即所要參與計(jì)算的符號(hào)的集合）；

2）D′＝ ｛UL，DL，UR，DR｝：分別表示DAE塊的左上角、左下角、右上角和右下角4個(gè)位置；

3）｛σUL，σDL，σUR，σDR｝∈Σ4：DAE塊的形式化描述，代表DAE塊4個(gè)位置分別所表示的符號(hào)；

4）（x，y）∈Z2：表示位置；

5）D＝｛N，E，S，W｝：表示4個(gè)方向函數(shù)，且滿足：

●?（x，y）∈Z2，N（x，y）＝（x，y＋1），E（x，y）＝（x＋1，y），S（x，y）＝（x，y－1），W （x，y）＝（x－1，y）；

●若位置（x，y）與（x’，y’）相鄰，則?d∈D，使得d（x，y）＝ （x’，y’）.

6）bdd（t）∈Σ，其中t∈T，d∈D’：表示t的位置d所表示的符號(hào)；

7）函數(shù)g：Σ×Σ→R，此函數(shù)定義如下：

●?σ∈Σ，則g（null，σ）＝0；

●若g（σ，σ’）＝0（其中σ，σ’∈Σ），則σ≠σ’；

●?σ≠null，有g(shù)（σ，σ）＝1；

●?σ≠σ’，有g(shù)（σ，σ’）＝0.

8）函數(shù)A：Z×Z→T，此函數(shù)有如下特點(diǎn)：

●若A（x，y）≠empty，則（x，y）∈A；

●若只有有限個(gè)不同的（x，y）∈A，則A為一個(gè)有限集.

9）A是一個(gè)格局，若一個(gè)DAE塊t能在位置（x，y）產(chǎn)生一個(gè)新的格局A’，需要滿足以下條件：

●（x，y）?A；

●Σd∈D’，d’∈Dg（bdd（t），bdd－1（A（d’（x，y））））≥τ，其中d與d－1為相對(duì)的方向，如：UR與DL相對(duì).

●?（u，v）∈Z2，（u，v）≠ （x，y），則A’（u，v）＝A（u，v）；

●A（x，y）＝t.

2 算法設(shè)計(jì)步驟

2.1 算法設(shè)計(jì)思路

基于DNA自組裝模型的算法設(shè)計(jì)利用的是“堆積木”的思想，其具體算法設(shè)計(jì)思路如下：

1）設(shè)計(jì)初始分子，使之組裝成所有可能結(jié)果；

2）分析問題，找出問題正確結(jié)果所需滿足的條件；

3）根據(jù)2）條件限制，設(shè)計(jì)規(guī)則分子，判定1）中結(jié)果正確性；

4）搜索正確結(jié)果，得到所需答案.

本文按照上述步驟設(shè)計(jì)相應(yīng)的DAE塊，然后通過基因工程的相應(yīng)生物操作，利用凝膠電泳和熒光標(biāo)記技術(shù)提取得到最終結(jié)果.相應(yīng)生物操作描述[18]如下：

1）合并（merge）：給定試管P1和P2，操作∪（P1，P2）＝P1∪P2表示將試管P1和P2合并到一個(gè)試管中而不改變P1和P2中的任何鏈.

2）提?。╡xtract）：給定試管P1和P2，操作P2＝extract（P1）表示提取試管P1中具有某種特征的DNA分子到試管P2.

3）退火（anneal）：給定試管P，操作Anneal（P）將試管P中的所有DNA單鏈變成雙鏈.

4）熒光標(biāo)記（fluorescence labeling）：給定試管P，該操作將具有某種特征的DNA分子作標(biāo)記.

5）凝膠電泳（gel electrophoresis）：給定試管P，該操作將試管中DNA分子按照分子大小進(jìn)行分離.

2.2 設(shè)計(jì)初始分子

設(shè)G＝｛V，E｝，其中V＝｛v1，v2，… ，vn｝，則任何頂點(diǎn)子集都可能是圖G的團(tuán)，則初始分子設(shè)計(jì)如圖3所示.其中，s和e是控制自組裝反應(yīng)的始端和終端，與圖G無關(guān)；i，j∈｛1，2，…，n｝，且i＜j.分析可知：所有初始分子的種類為2n2－7n＋8.

若頂點(diǎn)子集為｛1，2｝，則退火反應(yīng)之后則形成如圖4所示結(jié)構(gòu).若頂點(diǎn)子集為｛1，2，3｝，則退火后反應(yīng)之后形成如圖5所示結(jié)構(gòu).

圖3 初始分子Fig.3 Initial moleculars

圖4 頂點(diǎn)子集｛1，2｝形成的結(jié)構(gòu)Fig.4 Forming structure of vertex subset｛1，2｝

圖5 頂點(diǎn)子集｛1，2，3｝形成的結(jié)構(gòu)Fig.5 Forming structure of vertex subset｛1，2，3｝

引理1 若Σ1＝｛s，e，v1，v2，…，vn｝，T1為按上述方式設(shè)計(jì)的初始分子DAE塊的集合，τ＝1，則形成的自組裝系統(tǒng)S1＝〈T1，g，τ〉.不失一般性，比如頂點(diǎn)子集為｛v1，v2，… ，vk｝，經(jīng)過退火反應(yīng)后則會(huì)形成如下格局A1：

證 根據(jù)T1中的DAE塊的特點(diǎn)可知，起始端為｛null，null，s，s｝，所以bdUR（A1（x0，y0））＝s.已知τ＝1，所以只需要一邊能夠結(jié)合就能夠產(chǎn)生新的格局.又已知頂點(diǎn)子集為｛v1，v2，… ，vk｝，所以?DAE塊｛∞，s，v1，v1｝，所以｛null，null，s，s｝與｛∞，s，v1，v1｝能夠結(jié)合產(chǎn)生新的格局.則此時(shí)bdUL（A1（x2，y0））＝∞，bdUR（A1（x2，y0））＝v1.

同理可知：當(dāng)k為偶數(shù)時(shí)，bdUL（A1（x4，y0））＝v2，bdUR（A1（x4，y0））＝v3，…，bdUL（A1（xk＋2，y0））＝vk，bdUR（A1（xk＋2，y0））＝e，bdUL（A1（xk＋4，y0））＝e.

當(dāng)k為奇數(shù)時(shí)，bdUL（A1（x4，y0））＝v2，bdUR（A1（x4，y0））＝v3，…，bdUL（A1（xk＋1，y0））＝vk－1，bdUR（A1（xk＋1，y0））＝vk，bdUL（A1（xk＋3，y0））＝e.

（2）要根據(jù)運(yùn)行方式來調(diào)整好繼電保護(hù)裝置的保護(hù)功能、保護(hù)范圍以及相關(guān)的定制等等，對(duì)電網(wǎng)中所有有關(guān)的信息進(jìn)行綜合，再實(shí)時(shí)修正好保護(hù)定值。

證畢.

2.3 設(shè)計(jì)規(guī)則分子

我們把規(guī)則分子的DAE塊設(shè)計(jì)成如圖6所示.

圖6 兩頂點(diǎn)鄰接時(shí)DAE塊Fig.6 DAE block with adjoining vertexes

若輸入頂點(diǎn)a，b在圖中是鄰接的，則存在上述DAE塊，使其輸出時(shí)交換頂點(diǎn)變成b，a.考慮到邊界條件，則可以把規(guī)則分子設(shè)計(jì)成如圖7.

圖7 規(guī)則分子Fig.7 Regular moleculars

其中s為始端，e為終端，與圖G無關(guān).節(jié)點(diǎn)a，b鄰接，且a，b，c，d∈｛v1，v2，…，vn－1，vn，∞｝，所需DAE塊種類為｜E｜＋2n＋1.

引理2 在格局A1的基礎(chǔ)上，若T2為按上述方式設(shè)計(jì)的規(guī)則分子的集合，并且τ＝2，則形成的自組裝系統(tǒng)S2＝〈T2，g，τ〉.若G對(duì)于生成的格局A1中的所有頂點(diǎn)都相鄰，則系統(tǒng)S2會(huì)生成格局A2，其中bdUR（A2（xk＋1，yk＋1））＝∞，bdUL（A2（xk＋3，yk＋1））＝e.若G對(duì)于生成的格局A1中存在兩個(gè)頂點(diǎn)不相鄰，則系統(tǒng)S2不會(huì)生成上述格局A2.

證k為偶數(shù)且圖G對(duì)于生成的格局A1中的所有的頂點(diǎn)都相鄰，則形成的A1如引理1中所述.由于τ＝2，所以需要兩邊能夠結(jié)合才能產(chǎn)生新的格局.又因?yàn)樗械捻旤c(diǎn)都相鄰，所以對(duì)于任意兩個(gè)頂點(diǎn)vi，vj都存在 DAE 塊｛vj，vi，vi，vj｝，即每經(jīng)過一輪比較∞都會(huì)向后移動(dòng)，所以∞終會(huì)移動(dòng)到末尾，即bdUR（A2（xk＋1，yk＋1））＝ ∞，且bdUL（A2（xk＋3，yk＋1））＝e.同理可知：若k為奇數(shù)時(shí)，bdUR（A2（xk＋1，yk＋1））＝∞，bdUL（A2（xk＋2，yk＋1））＝e.故系統(tǒng)S2會(huì)生成格局A2.

反之，若A1中存在兩個(gè)頂點(diǎn)不相鄰.不失一般性，假設(shè)存在兩個(gè)頂點(diǎn)vi，vj不相鄰，則不會(huì)存在DAE塊｛vj，vi，vi，vj｝.由于τ＝2，當(dāng)反應(yīng)進(jìn)行到此后，格局就不會(huì)再增高，∞也就不會(huì)移動(dòng)到末尾.故不能形成格局A2.

證畢.

2.4 設(shè)計(jì)檢測(cè)分子

圖8 檢測(cè)分子Fig.8 Detected moleculars

i，j∈｛1，2，…，n－1，n｝，并且利用熒光標(biāo)記技術(shù)在上圖中最左邊的DNA分子加上與其他DAE塊不同顏色的熒光.則這些DAE塊種類共計(jì)n2＋1種.

若加入規(guī)則分子后能夠形成格局A2，則加入檢測(cè)分子后就能夠形成一個(gè)完整的格局，否則就不能形成一個(gè)完整穩(wěn)定的格局（即該格局沒有粘性末端可提供給其他DAE塊結(jié)合，并且該格局中擁有帶有熒光標(biāo)記的檢測(cè)分子）.

綜上所述，設(shè)計(jì)初始分子所需的DAE塊種類為2n2－7n＋8；設(shè)計(jì)規(guī)則分子所需的DAE塊種類為｜E｜＋2n＋1；設(shè)計(jì)檢測(cè)分子所需的DAE塊的種類為n2＋1.總共需要的DAE塊種類為3n2－5n＋｜E｜＋10.所以需要的DAE塊的種類為Θ（n2＋｜E｜），說明設(shè)計(jì)這些DAE塊是可行的.

3 基于DNA自組裝模型求解最大團(tuán)問題

3.1 算法步驟

算法基于自組裝模型的最大團(tuán)問題DNA算法.

輸入：圖G＝｛V，E｝，以及根據(jù)圖G并按上述方式設(shè)計(jì)的tiles集T1，T2，T3.

輸出：圖G的最大團(tuán).

7）T’end＝ Extract（T），提取在6）中所觀測(cè)到的分子塊，將其放入試管T′end；

8）使用凝膠電泳技術(shù)將T中的分子塊按照大小進(jìn)行分離，通過激光共焦距顯微鏡觀察分子塊最大的DNA塊；

9）Tend＝Extract（T′end），提取8）中所觀察的最大的DNA塊，將其放入試管Tend.

引理3 有a1，a2，a3，…，an個(gè)頂點(diǎn)，按照以下方式進(jìn)行n輪比較，則這n個(gè)頂點(diǎn)每?jī)蓚€(gè)頂點(diǎn)都會(huì)比較一次，即總共比較Cn2＝n（n－1）／2次.

證 當(dāng)n為偶數(shù)時(shí)，奇數(shù)輪比較（n／2）－1次，偶數(shù)輪比較n／2次，則總共比較的次數(shù)為（n／2）（n／2－1）＋ （n／2）（n／2）＝n（n－1）／2＝Cn2.

同理可知：當(dāng)n為奇數(shù)時(shí)，總共比較次數(shù)為n（n－1）／2＝Cn2.

證畢.

定理1 若算法中Tend不為空，則Tend中所代表的團(tuán)即為所求圖的最大團(tuán)；否則該圖的任意兩個(gè)頂點(diǎn)都不鄰接.

證 若Tend不為空，則Tend中的頂點(diǎn)集是按照引理1中的方式進(jìn)行比較.由引理1可知：Tend中的頂點(diǎn)集共進(jìn)行了Cn2次比較.又由于兩個(gè)頂點(diǎn)比較之后一個(gè)頂點(diǎn)向左移動(dòng)，另外一個(gè)頂點(diǎn)向右移動(dòng)，則這兩個(gè)頂點(diǎn)不會(huì)重復(fù)比較，所以每?jī)蓚€(gè)頂點(diǎn)都比較過一次.說明這n個(gè)頂點(diǎn)兩兩鄰接，即此頂點(diǎn)子集的導(dǎo)出子圖就為此圖的一個(gè)團(tuán).又由算法1的8）可知Tend中所表示頂點(diǎn)集都規(guī)模最大，所以Tend中所代表的團(tuán)即為所求圖的最大團(tuán).反之，若Tend為空，則說明圖G的任意頂點(diǎn)子集的導(dǎo)出子圖都不是團(tuán)，即該圖的任意兩個(gè)頂點(diǎn)都不鄰接.

證畢.

3.2 算法復(fù)雜性

文中2.2設(shè)計(jì)初始分子所需的DAE塊種類為2n2－7n＋8；2.3設(shè)計(jì)規(guī)則分子所需的DAE塊種類為｜E｜＋2n＋1；2.4設(shè)計(jì)檢測(cè)分子所需的DAE塊的種類為n2＋1.則總共需要的DAE塊種類為3n2－5n＋｜E｜＋10.所以需要的DAE塊的種類為Θ（n2＋｜E｜），即算法設(shè)計(jì)tiles的種類為Θ（n2＋｜E｜）.算法1（基于自組裝模型的最大團(tuán)問題DNA算法）生物操作為9步，即其生物操作復(fù)雜性為Θ（1）.

3.3 示 例

給定圖G＝｛V，E｝，其中V＝｛1，2，3，4，5｝，E＝｛（1，2），（2，3），（3，4），（4，5），（2，5），（2，4），（3，5）｝，如圖9所示.

圖9 5個(gè)頂點(diǎn)無向圖Fig.9 Graph of 5vertexes

結(jié)合3.1的算法步驟，則求得最大團(tuán)的步驟為如圖10所示 .在試管T1中加入連接酶，并使用退火操作，使其初始分子充分反應(yīng)，則會(huì)形成不同的頂點(diǎn)子集，如圖10（a）形成的頂點(diǎn)子集為｛2，3，4，5｝.

將試管T1，T2中的DAE塊合并到試管T，之后在試管T中加入連接酶，并使用退火操作.此步驟實(shí)際上是加入規(guī)則分子，用以判斷前面的頂點(diǎn)子集是否為團(tuán).如圖10（b）即為加入規(guī)則分子去判斷頂點(diǎn)子集｛2，3，4，5｝是否為團(tuán).

最后加入檢測(cè)分子，便于檢測(cè)頂點(diǎn)子集的導(dǎo)出子圖是否為團(tuán).經(jīng)過上述步驟后，凡是能夠形成如圖10（c）所示的結(jié)構(gòu)，則說明該導(dǎo)出子圖即為團(tuán)，即該圖中存在有熒光標(biāo)記的DNA分子.

圖10 圖G最大團(tuán)計(jì)算Fig.10 Computing maximum clique of G

4 結(jié) 論

自組裝技術(shù)能最底層揭示DNA計(jì)算的本質(zhì)，它是一種由簡(jiǎn)單到復(fù)雜、從無序到有序、由多組分收斂到單一組分不斷自我修正、自我完善的過程.本文采用DNA自組裝模型，設(shè)計(jì)出相應(yīng)的DNA tiles分子，利用基因工程的生物操作，提出一種基于DNA自組裝模型求解最大團(tuán)問題的算法 .該算法實(shí)驗(yàn)操作復(fù)雜度為常數(shù)級(jí)，既大大減少了因?yàn)槿藶閷?shí)驗(yàn)操作所帶來的誤差，又保證了實(shí)驗(yàn)結(jié)果的準(zhǔn)確性，對(duì)DNA計(jì)算和DNA計(jì)算機(jī)的研究來說，是一次有意義的實(shí)踐.目前DNA計(jì)算模型的DNA編碼已經(jīng)從一維結(jié)構(gòu)發(fā)展到了三維結(jié)構(gòu) .相對(duì)于其他的計(jì)算模型，從理論上已表明，使用三維DNA圖結(jié)構(gòu)可以明顯減少解決最大團(tuán)問題所需的時(shí)間和步驟，而且由于它能直觀地反映圖結(jié)構(gòu)，用它建立計(jì)算模型可能會(huì)使一些傳統(tǒng)的難解問題得以解決.

本文主要利用其形成的二維平面結(jié)構(gòu)來解決最大團(tuán)問題 .在技術(shù)層面上，將這種二維DNA分子組裝成三維DNA圖結(jié)構(gòu)模型還存在很多需要解決的問題.目前對(duì)復(fù)雜三維DNA結(jié)構(gòu)進(jìn)行普通的實(shí)驗(yàn)操作還少有研究，且與它相關(guān)聯(lián)的酶處理操作也容易發(fā)生錯(cuò)誤.隨著DNA計(jì)算研究的深入，三維DNA計(jì)算也將會(huì)有更好的發(fā)展 .此外，將分子計(jì)算與量子計(jì)算緊密地結(jié)合在一起，為未來的新型計(jì)算技術(shù)提供了發(fā)展的可能.伴隨分子操控技術(shù)的發(fā)展，相信DNA計(jì)算在信息處理、密碼技術(shù)、納米智能機(jī)器和納電子學(xué)等多個(gè)領(lǐng)域?qū)?huì)有更多的潛在應(yīng)用.

[1] OUYANG Q，KAPLAN P D ，LIU S，et al.DNA solution of the maximal clique problem[J].Science，1997，278：446－449.

[2] PULLAN W，HOOS H H.Dynamic local search for the maximum clique problem[J].Journa l of Artificial Intelligence Research，2006，25：159－185.

[3] KATAYAMA K，KOHMURA A，KOHMOTO K，et al.Memetic algorithm with strategic controller for the maximum clique problem[C]∥Taiwan：TaiChung：Proceedings of the 2011ACM Symposium on Applied Computing，2011：1062－1069.

[4] SHARRMA J，CHHABRA R，CHENG A，et al.Control of self－assembly of DNA tubules through integration of gold nanoparticles[J].Science，2009，323：112－116.

[5] ADLEMAN L M.Molecular computation of solutions to combinatorial problems[J].Science，1994，266（11）：1021－1024.

[6] 周康，劉朔，覃磊，等.基于粘貼模型的最大團(tuán)問題算法[J].華中科技大學(xué)學(xué)報(bào)：自然科學(xué)版，2010，38（9）：89－92.ZHOU Kang，LIU Shuo，QIN Lei，et al.Sticker model－based DNA algorithm of maximum clique problem[J].Huazhong Univ of Sci ＆Tech：Natural Science Edition，2010，38（9）：89－92.（In Chinese）

[7] HEAD T，ROZENBERG G，BLADERGROEN R B，et al.Computing with DNA by operating on plasmids[J].Bio Systems，2000，57：87－93.

[8] 張成，楊靜，許進(jìn)，等.DNA縮短法計(jì)算模型求解最大獨(dú)立集問題[J].科學(xué)通報(bào)，2009，54（24）：3913－3919.ZHANG Cheng，YANG Jing，XU Jin，et al.A DNA length reducing computing model for maximum independent set problem[J].Chinese Sci Bull，2009，54（24）：3913－3919.（In Chinese）

[9] BRUN Y，REISHUS D.Path finding in the tile assembly model[J].Theoretical Computer Science，2009，410（15）：1461－1472.

[10] BRUN Y.Solving satisfiability in the tile assembly model with a constant－size tileset[J].Journal of Algorithma，2008，63（4）：151－166.

[11] STERLING A.Distributed agreement in tile self－assembly[J].Natural Computing：an International Journal，2011，10（1）：337－355.

[12] 張成，楊靜，許進(jìn).自組裝DNA／納米顆粒分子邏輯計(jì)算模型[J].科學(xué)通報(bào)，2011，56（27）：2276－2282.ZHANG Cheng，YANG Jing，XU Jin.Molecular logic computing model based on self－assembly of DNA nanoparticles[J].Chinese Sci Bull，2011，56（27）：2276－2282.（In Chinese）

[13] XU Jin，TAN Gang－jun，F(xiàn)AN Yue－ke，et al.DNA computer principle，advances and difficulties（Ⅳ）：on the models of DNA computer[J].Chinese Journal of Computers，2007，30（6）：881－893.

[14] 張勛才.自組裝DNA計(jì)算模型的研究及應(yīng)用[D].武漢：華中科技大學(xué)計(jì)算機(jī)工程與技術(shù)學(xué)院，2009.5.ZHANG Xun－cai.The reserch and applications of DNA computing by self－assembly[D].Wuhan：Huazhong Univ of Sci＆Tech，2009.5.（In Chinese）

[15] HE Yu，MAO Cheng－de，et al.Hierarchical self－assembly of DNA into symmetric supramolecular polyhedral[J].Nature，2008，452：198－202.

[16] WINFREE E.Design and self－assembly of two－dimensional DNA crystals[J].Nature，1998，394：1223－1226.

[17] YURIY B.Solving NP－complete problems in the tile assembly model[J].Theoretical Computer Science，2008，395（1）：31－46.

[18] 李肯立，姚鳳娟，許進(jìn)，等.子集和問題的O（1.414n）鏈數(shù)DNA計(jì)算機(jī)算法[J].計(jì)算機(jī)學(xué)報(bào)，2007，30（11）：1948－1953.LI Ken－li，YAO Feng－juan，XU Jin，et al.An O（1.414n）volume molecular solutions for the subset－sum problem on DNA－based supercomputing [J].Chinese Journal of Computers，2007，30（11）：1948－1953.（In Chinese）