基于DNA計(jì)算的最大權(quán)團(tuán)問題設(shè)計(jì)

張喆++殷志祥

摘要：介紹了最大團(tuán)和最大權(quán)團(tuán)的概念和國(guó)內(nèi)外學(xué)者運(yùn)用DNA計(jì)算解決最大團(tuán)的研究成果；結(jié)合前人運(yùn)用質(zhì)粒、二進(jìn)制、粘貼模型等方式進(jìn)行DNA計(jì)算操作的原理，設(shè)計(jì)了新的用于解決最大權(quán)團(tuán)問題的算法步驟，大大提高了算法效率，實(shí)現(xiàn)了最大團(tuán)和最大權(quán)團(tuán)的同步求解，對(duì)市場(chǎng)分析、方案選擇等領(lǐng)域有一定的意義。

關(guān)鍵詞：DNA計(jì)算；質(zhì)粒；粘貼模型；最大權(quán)團(tuán)；凝膠電泳

中圖分類號(hào)：TP301.6文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1672-1098（2015）01-0075-03

對(duì)于給定的無(wú)向圖G=（V，E）。如果UV，且對(duì)任意u，v∈U有（u，v）∈E，則稱U是G的完全子圖。G的完全子圖U是G的團(tuán)當(dāng)且僅當(dāng)U不包含在G的更大的完全子圖中。G的最大團(tuán)是指G中所含頂點(diǎn)數(shù)最多的團(tuán)。而最大權(quán)團(tuán)，就是指權(quán)值最大的最大團(tuán)。

1994年，文獻(xiàn)[1]提出了用DNA分子解決7節(jié)點(diǎn)的Hamilton路徑問題，這是有關(guān)DNA計(jì)算的開山之作。之后文獻(xiàn)[2]在Adleman思想的啟發(fā)下，通過構(gòu)造一個(gè)接觸網(wǎng)絡(luò)圖G，將可滿足性問題（SAT）的解空間，映射成通過接觸網(wǎng)絡(luò)G的始點(diǎn)到終點(diǎn)的所有Hamilton路徑，然后對(duì)有向圖中的頂點(diǎn)和邊進(jìn)行編碼，用DNA計(jì)算解決了3—變量的可滿足性問題。1997年，文獻(xiàn)[3]提出了用DNA計(jì)算求解最大環(huán)問題的方法，為DNA計(jì)算解決NP問題提供了又一佐證。2000年，文獻(xiàn)[4]提出了在固體表面進(jìn)行DNA計(jì)算的方法，改變了過去在試管溶液中進(jìn)行DNA計(jì)算的生物操作的方法，進(jìn)一步提高了DNA計(jì)算的可靠性和效率，近些年，文獻(xiàn)[5]2009年解決了閉環(huán)求解最大團(tuán)問題的算法；文獻(xiàn)[6]于2010年解決了基于粘貼模型的最大團(tuán)問題算法；文獻(xiàn)[7]于2011年結(jié)合Aunp自組裝聚合色變與DNA計(jì)算相結(jié)合，構(gòu)建了系列基本邏輯計(jì)算模型；文獻(xiàn)[8]于2012年設(shè)計(jì)出了結(jié)合DAE塊的DNA自組裝模型求解最大團(tuán)問題的算法，并在2013年進(jìn)一步改進(jìn)，等等。本文將用圖1所示的頂點(diǎn)圖來(lái)進(jìn)行實(shí)驗(yàn)，利用DNA計(jì)算的算法求出其最大權(quán)團(tuán)。

圖1頂點(diǎn)圖

其中V1對(duì)應(yīng)權(quán)重為ω1，V2對(duì)應(yīng)權(quán)重為ω2，……，V5對(duì)應(yīng)權(quán)重為ω5。

1DNA計(jì)算的原理

DNA計(jì)算的基本思想是以DNA鏈作為信息載體，將原始問題映射為DNA分子鏈（包括單鏈、雙鏈、帶有粘性末端的單雙混合鏈），對(duì)設(shè)計(jì)出的DNA分子進(jìn)行擴(kuò)增，在實(shí)驗(yàn)室中對(duì)這些DNA分子進(jìn)行諸如退火、雜交、連接[9] 等生化操作，最后采用電泳技術(shù)[10] 、層析分析技術(shù)、分子純化技術(shù)[11] 、激光技術(shù)等方式檢測(cè)DNA計(jì)算的最后結(jié)果。

比較經(jīng)典的實(shí)驗(yàn)方式是在試管中進(jìn)行DNA計(jì)算操作。計(jì)算過程中可能要用到一個(gè)或者多個(gè)試管，可根據(jù)需要在試管中加入引物、緩沖液、酶等反應(yīng)物。本實(shí)驗(yàn)過程即是在試管中進(jìn)行的。

2質(zhì)粒及粘貼模模型

質(zhì)粒是游離于染色體之外的具有自行復(fù)制子的DNA雙鏈分子，實(shí)驗(yàn)中運(yùn)用的質(zhì)粒通常具有復(fù)制子、選擇標(biāo)志、克隆位點(diǎn)等特征。質(zhì)粒最大的特點(diǎn)是質(zhì)粒上任一子段不會(huì)重復(fù)出現(xiàn)在質(zhì)粒的另一位置。這樣，對(duì)于質(zhì)粒的修改就只會(huì)在特定的位置進(jìn)行，而不會(huì)在其他位置進(jìn)行。

粘貼模型擁有一個(gè)由存儲(chǔ)合成物構(gòu)成的可以隨機(jī)訪問的存儲(chǔ)區(qū)。每個(gè)存儲(chǔ)合成物由存儲(chǔ)鏈和粘貼鏈的DNA單鏈分子組成，存儲(chǔ)鏈和粘貼鏈都是由不同的堿基構(gòu)成，存儲(chǔ)鏈含有K個(gè)不重疊的子鏈，而任一粘貼鏈按堿基互補(bǔ)配對(duì)原則恰于存儲(chǔ)鏈中的任一子鏈配對(duì)。當(dāng)粘貼鏈可以與存儲(chǔ)鏈結(jié)合時(shí)，此位置視為“開”，在二進(jìn)制中可以用1表示；反之，視為“關(guān)”，在二進(jìn)制中用0表示。

利用質(zhì)粒以及粘貼模型各自的優(yōu)勢(shì)，將二者結(jié)合起來(lái)用于解決最大權(quán)團(tuán)問題。

3DNA算法步驟

以圖1為例來(lái)說(shuō)明算法的實(shí)現(xiàn)過程，設(shè)計(jì)的模型如圖2所示。

圖2新鏈

此模型結(jié)合粘貼模型以及質(zhì)粒模型：由主鏈、輔鏈1、輔鏈2三個(gè)部分組成，其中輔鏈2與輔鏈1相連，輔鏈1與主鏈相連；主鏈表示頂點(diǎn)對(duì)應(yīng)的DNA鏈，輔鏈1表示頂點(diǎn)間邊的關(guān)系，頂點(diǎn)間有邊相連設(shè)置為雙鏈DNA分子，無(wú)邊設(shè)為單鏈，輔鏈2代表權(quán)值，不同頂點(diǎn)對(duì)應(yīng)的每個(gè)子鏈中都含有可以被限制性內(nèi)切酶特異識(shí)別的DNA序列（這樣可以被限制性內(nèi)切酶所識(shí)別，進(jìn)而進(jìn)行剪切），同時(shí)根據(jù)權(quán)值的大小將各個(gè)子鏈設(shè)置成不同的長(zhǎng)度。m1 是權(quán)值除以各個(gè)權(quán)值的最大公約數(shù)n得到的結(jié)果，即有ω1=nm1；對(duì)于整條鏈，將其插入質(zhì)粒1中（質(zhì)粒可選取pOK12質(zhì)粒）。

將圖2所示的DNA鏈進(jìn)行擴(kuò)增，并將其產(chǎn)生的質(zhì)粒試管稱為T0。對(duì)于一個(gè)圖的頂點(diǎn)集V={V1，V2，…，Vn}，從中任取i≥2的頂點(diǎn)，如Vk1 ，Vk2 ，…Vki ，對(duì)于輔鏈1，保留位段（ Vr，Vt），其中r、t任取k1，…，ki中的任意兩個(gè)，且取遍所有可能。對(duì)于輔鏈2，只保留Vk1，Vk2 ，…Vki 所對(duì)應(yīng)的權(quán)值子段。

在圖1中任取3點(diǎn){V1，V2，V3}，經(jīng)過上述操作，可以得到存儲(chǔ)合成物（見圖3a）。

在圖2中任取3點(diǎn){V1，V2，V5}，經(jīng)過上述操作，可以得到存儲(chǔ)合成物（見圖3b）。

（b）圖3存儲(chǔ)合成物

由圖3可以看出，圖3a中的輔鏈1并不完全是雙鏈，而圖3b中的輔鏈1完全是雙鏈，{V1，V2，V5}對(duì)應(yīng)的完全子圖就是圖1的一個(gè)最大團(tuán)。

i的取值不斷增加（2≤i≤n），不斷的復(fù)制T0 來(lái)進(jìn)行上述操作，然后篩選出輔鏈1全為雙鏈的合成物，其對(duì)應(yīng)的頂點(diǎn)集即為圖的最大團(tuán)。對(duì)于圖1來(lái)說(shuō)，可以篩選出最大團(tuán)為{V1，V2，V5}，{V3，V4，V5}。利用限制性內(nèi)切酶切下篩選出的合成物各自的輔鏈2，由于各自的權(quán)值不同，所以各自的輔鏈2長(zhǎng)度也不同，此時(shí)可以利用凝膠電泳篩選出長(zhǎng)度最長(zhǎng)的合成物，在利用探針照明技術(shù)確定頂點(diǎn)組成，此時(shí)即可求出最大權(quán)團(tuán)。endprint

4小結(jié)

最大團(tuán)以及最大權(quán)團(tuán)問題是著名的組合優(yōu)化問題，它在市場(chǎng)分析、方案選擇、信號(hào)傳輸、計(jì)算機(jī)視覺、信息恢復(fù)、容錯(cuò)能領(lǐng)域都有著廣泛的應(yīng)用。另外，許多NP—完全問題都可以轉(zhuǎn)化成為MCP，如可滿足性問題、獨(dú)立集問題、頂點(diǎn)覆蓋問題等。而DNA計(jì)算具有納米級(jí)、超強(qiáng)并行操作能力以及特異性雜交識(shí)別等天然優(yōu)勢(shì)，使其非常適合用來(lái)解決最大團(tuán)問題。

本文運(yùn)用DNA計(jì)算可以有效的解決最大權(quán)團(tuán)問題，使得最大權(quán)團(tuán)問題更好的運(yùn)用于生產(chǎn)實(shí)踐中，具有一定的實(shí)踐意義。在解決最大權(quán)團(tuán)問題中，還有一些待解決的問題，比如DNA的合成與編碼、如何運(yùn)用盡量簡(jiǎn)單的方式形成解空間等，同時(shí)如何剔除“偽解”和“錯(cuò)解”，篩選出最優(yōu)解也是非常重要的。今后的研究將著重于以上幾個(gè)方面。

參考文獻(xiàn)：

[1]ADLEMAN L M. Molecular computation of solutions to combination problems[J]. Science，1994，266（5 187）：1 021-1 024.

[2]LIPTON R J.DNA solutions of hard computational problems[J].Science，1995，268（5 210）：542-545.

[3]OUYANG Q，KAPLAN P D，LIU S，et al.Solution of the maximal clique problem [J].Science，1997，278（17）：446-449.

[4]LIU Q， WANG L， FRUTOS A G，et al.DNA computing on surface[J]. Nature，2000， 403（13）：175-179.

[5]許進(jìn)，譚鋼軍，范月科，等.論DNA 計(jì)算機(jī)模型[J].計(jì)算機(jī)學(xué)報(bào)，2007，30（6）：881-893.

[6]周康，劉朔.基于粘貼模型的最大團(tuán)問題算法[J].華中科技大學(xué)學(xué)報(bào)：自然科學(xué)版，2010，38（9）：89-92.

[7]張成，楊靜，許進(jìn)，等.縮短法計(jì)算模型求解最大獨(dú)立集問題[J].科學(xué)通報(bào)，2011，54（24）：3 913.

[8]周炎濤，李肯力，羅興，等.一種基于DNA自組裝模型求解最大團(tuán)問題的算法[J].湖南大學(xué)學(xué)報(bào)，2012，39（9）：39-44.

[9]CHEN J，WOOD D H.Computation with biomolecules[J].Commentary，2000，97（4）：1 328-1 330.

[10]許進(jìn)，李三平，董亞非，等.粘貼DNA計(jì)算機(jī)模型（II）應(yīng)用[J].科學(xué)通報(bào)，2004，49（4）：299-307.

[11]殷志祥， 張鳳月，許進(jìn).基于分子信標(biāo)的DNA計(jì)算[J].生物數(shù)學(xué)學(xué)報(bào)，2003，18（4）： 497-501.

（責(zé)任編輯：何學(xué)華）endprint