最大團(tuán)問(wèn)題的三鏈DNA計(jì)算模型

陳海芳，殷志祥

(安徽理工大學(xué)數(shù)學(xué)與大數(shù)據(jù)學(xué)院，安徽淮南232001)

最大團(tuán)是著名的NP（Non-deterministic Polynomial）完全問(wèn)題，也是圖論中一個(gè)重要的研究方向，無(wú)論是在理論研究還是在實(shí)際應(yīng)用中都具有重要意義，諸如市場(chǎng)分析、方案選擇、信號(hào)傳輸、計(jì)算機(jī)視覺(jué)、故障診斷等領(lǐng)域都有直接的應(yīng)用。從1957年Hararv和Ross首次給出最大團(tuán)的一個(gè)確定性算法以來(lái)，人們就在不停地尋求更好的方案。但是隨著圖規(guī)模的增大，確定性算法無(wú)法有效解決此類(lèi)NP問(wèn)題，人們又開(kāi)始尋找新的突破。隨著分子生物學(xué)的發(fā)展以及DNA分子具有高并行性和信息儲(chǔ)存量的優(yōu)勢(shì)，研究者們開(kāi)始著手使用DNA計(jì)算來(lái)求解NP問(wèn)題。1994年，Adleman[1]利用DNA編碼成功地解決了一個(gè)具有7個(gè)頂點(diǎn)的有向Hamilton路徑問(wèn)題，開(kāi)創(chuàng)了DNA計(jì)算的先河；1997年，Ouyang等[2]又利用DNA計(jì)算成功求解了6個(gè)頂點(diǎn)的圖的最大團(tuán)問(wèn)題；文獻(xiàn)[3]利用納米材料屬性，提出Tile自組裝高效模型，減少了解的空間規(guī)模，提高了運(yùn)算的并行性；文獻(xiàn)[4]基于二維DNA分子tiler自組裝，構(gòu)建了一個(gè)三維DNA圖結(jié)構(gòu)來(lái)建立模型求解；文獻(xiàn)[5]使用DNA三維自組裝的算法來(lái)解決最大團(tuán)問(wèn)題，使得計(jì)算的時(shí)間復(fù)雜度是線(xiàn)性的，瓦片結(jié)構(gòu)的獨(dú)特類(lèi)型也使得所需的DNA鏈數(shù)是恒定的；文獻(xiàn)[6-7]分別運(yùn)用圓形DNA分子模型和粘貼模型求解了最大團(tuán)問(wèn)題。在上述DNA計(jì)算中，都是利用雙鏈DNA來(lái)求解問(wèn)題，為了更好地解決最大團(tuán)問(wèn)題，本文引入三鏈DNA的概念。

1 三鏈DNA的形成

三鏈DNA是在雙螺旋結(jié)構(gòu)的基礎(chǔ)上，以Hoogsteen和反式Hoogsteen型氫鍵與新加入的第三條鏈相連接形成三螺旋結(jié)構(gòu)。2004年，Shigemori等發(fā)現(xiàn)在RecA蛋白及ATPrS存在的情況下，寡聚脫氧核苷酸與線(xiàn)性雙螺旋DNA可形成穩(wěn)定的三鏈結(jié)構(gòu)[8]。三鏈DNA的具體形成過(guò)程如圖1所示。三鏈DNA在參與反應(yīng)時(shí)，由于反應(yīng)前參與反應(yīng)的數(shù)據(jù)池中皆為雙鏈DNA，使得形成的三鏈結(jié)構(gòu)很穩(wěn)定，這樣避免了DNA鏈在參與反應(yīng)時(shí)堿基的錯(cuò)配，也不會(huì)出現(xiàn)由于單鏈過(guò)長(zhǎng)而出現(xiàn)發(fā)夾結(jié)構(gòu)的現(xiàn)象。使用三鏈結(jié)構(gòu)可以減少錯(cuò)誤率，同時(shí)也可以降低編碼的復(fù)雜度。三鏈模型已經(jīng)成功解決了許多圖論中的問(wèn)題[9-17]。

圖1 三鏈DNA的形成

2 最大團(tuán)問(wèn)題

設(shè)G是一個(gè)圖，V(G)和E(G)分別表示圖的頂點(diǎn)集和邊集，S是G的一個(gè)頂點(diǎn)子集，若S中任意兩點(diǎn)都與E(G)中的邊相連，則稱(chēng)S是圖G的一個(gè)團(tuán)。若對(duì)G的任意其他團(tuán)S′，都有 ||S′≤ ||S，則稱(chēng)S是G的最大團(tuán)。圖2是一個(gè)具有6個(gè)頂點(diǎn)的簡(jiǎn)單圖。

圖2 6個(gè)頂點(diǎn)的簡(jiǎn)單圖

3 最大團(tuán)問(wèn)題的DNA算法

3.1 基本算法

步驟1：DNA單鏈根據(jù)Waston-Click原理生成數(shù)據(jù)池；

步驟2：刪除不滿(mǎn)足條件的解；

步驟3：輸出結(jié)果。

3.2 生物算法

對(duì)于n個(gè)頂點(diǎn)的簡(jiǎn)單圖的團(tuán)，可以用一個(gè)n位的二進(jìn)制的數(shù)字串來(lái)表示。具體表示方式：當(dāng)圖的某個(gè)頂點(diǎn)在團(tuán)中時(shí)，編碼為1；當(dāng)該頂點(diǎn)不在團(tuán)中時(shí)，編碼為0。如圖2中，頂點(diǎn)1、2、5組成的一個(gè)團(tuán)可以用110 010來(lái)表示。因此可以用0、1組成的n位數(shù)字串來(lái)表示所有可能的情況，稱(chēng)所有二進(jìn)制數(shù)的集合為數(shù)據(jù)池。為了滿(mǎn)足最大團(tuán)的定義，需要對(duì)數(shù)據(jù)池進(jìn)行篩選，只保留正確解，具體的操作：

（i）對(duì)圖的各個(gè)頂點(diǎn)進(jìn)行編碼，構(gòu)造出代表不同頂點(diǎn)的DNA單鏈，然后將這些單鏈與連接酶一起加入到溶液中進(jìn)行生化反應(yīng)得到雙鏈DNA，即生成初始數(shù)據(jù)池T0。

（ii）為了滿(mǎn)足團(tuán)定義的要求，需要對(duì)初始數(shù)據(jù)池中頂點(diǎn)的組合進(jìn)行篩選。結(jié)合圖G的補(bǔ)圖，因?yàn)閳D中的團(tuán)在其圖的補(bǔ)圖中對(duì)應(yīng)的是空?qǐng)D，所以在補(bǔ)圖中相連的兩頂點(diǎn)在原圖中是斷開(kāi)的，因此，他們不可能是同一團(tuán)中的頂點(diǎn)。因此對(duì)應(yīng)于編碼來(lái)說(shuō)，在補(bǔ)圖中相連的兩個(gè)頂點(diǎn)不可能同時(shí)為1。據(jù)此，借助三鏈DNA進(jìn)行檢測(cè)，配制代表補(bǔ)圖中相連的兩個(gè)頂點(diǎn)的DNA片段的補(bǔ)鏈，將其與抗原蛋白質(zhì)相結(jié)合，制作成探針，加入到數(shù)據(jù)池中，形成三鏈DNA。沒(méi)有形成三鏈的就是滿(mǎn)足在補(bǔ)圖中未被連接的頂點(diǎn)，則該頂點(diǎn)都包含在團(tuán)中。利用生物操作技術(shù)將數(shù)據(jù)池中的三鏈DNA去除，剩下的雙鏈DNA就是滿(mǎn)足團(tuán)定義的點(diǎn)所對(duì)應(yīng)的DNA鏈。最后根據(jù)1的個(gè)數(shù)（即團(tuán)中所包含頂點(diǎn)的個(gè)數(shù)）來(lái)讀出最大團(tuán)的規(guī)模。

（iii）通過(guò)凝膠電泳來(lái)對(duì)數(shù)據(jù)池中的最大團(tuán)方案進(jìn)行分離，讀出最大團(tuán)。

4 算法實(shí)例

下面以圖2為例，求解圖的最大團(tuán)問(wèn)題。

（1）對(duì)圖2中簡(jiǎn)單圖的各個(gè)頂點(diǎn)進(jìn)行編碼，頂點(diǎn)的編碼設(shè)計(jì)如圖3所示：中間是表示頂點(diǎn)位置的Vi，兩邊是粘性末端Si，并且第i個(gè)頂點(diǎn)右邊的黏性末端的補(bǔ)鏈與第i+m個(gè)頂點(diǎn)左邊的黏性末端的補(bǔ)鏈可以通過(guò)連接酶鏈接構(gòu)成i→i+m或。將Vi、和放入緩沖液中，在一定的溫度下，根據(jù)Watson-Crick原則，隨機(jī)生成DNA雙鏈，這些雙鏈里包含了頂點(diǎn)組合的所有可能，即生成了初始的數(shù)據(jù)池T0。又因?yàn)槊總€(gè)頂點(diǎn)可能在團(tuán)中，也可能不在團(tuán)中，所以每個(gè)頂點(diǎn)有兩種不同的編碼。圖2中有6個(gè)頂點(diǎn)，共有12段不同的編碼。為了對(duì)頂點(diǎn)進(jìn)行區(qū)分，給它設(shè)計(jì)為不同的編碼與長(zhǎng)度：定義每一個(gè)黏性末端的長(zhǎng)度為5 bp，頂點(diǎn)的長(zhǎng)度為10 bp。對(duì)應(yīng)于編碼：若Vi的值在團(tuán)中，由定義知Vi=1，則Vi肯定不在其補(bǔ)圖中，故在補(bǔ)圖中的長(zhǎng)度為0 bp；若Vi的值不在團(tuán)中，由定義知Vi=0，則Vi在其補(bǔ)圖中,長(zhǎng)度為10 bp。我們可以知道最長(zhǎng)的DNA鏈長(zhǎng)為120 bp（包含6個(gè)頂點(diǎn)的長(zhǎng)度和12個(gè)黏性末端的長(zhǎng)度），對(duì)應(yīng)于數(shù)字串（000 000），最短的DNA鏈長(zhǎng)為60 bp（沒(méi)有頂點(diǎn)，只有12個(gè)黏性末端），對(duì)應(yīng)于數(shù)字串（111 111）。由于檢測(cè)時(shí)是借助補(bǔ)圖來(lái)進(jìn)行的，因此要尋找代表最大團(tuán)的雙鏈DNA，就是尋找滿(mǎn)足團(tuán)的定義的補(bǔ)圖中所含頂點(diǎn)最少的雙鏈DNA，即最短的雙鏈DNA，并且為了防止反應(yīng)過(guò)程中錯(cuò)配現(xiàn)象的發(fā)生,不同序列具有相同堿基的長(zhǎng)度不超過(guò)4 bp，具體的編碼如表1所示。

（2）從圖G的補(bǔ)圖出發(fā)，檢查補(bǔ)圖中相連的點(diǎn)。在圖2(b)中，頂點(diǎn)1、3相連接，當(dāng)數(shù)據(jù)池中頂點(diǎn)1、3同時(shí)存在時(shí)（即編碼分別為11、31），先將代表初始數(shù)據(jù)池的試管T0分為T(mén)1和T2，然后將11、31的補(bǔ)鏈分別與抗原蛋白質(zhì)混合，制作成探針P1，P2。將探針P1、P2分別放入到試管T1、T2中，探針P1在試管T1中與11進(jìn)行雜交反應(yīng)，形成三鏈DNA；同樣，探針P2在試管T2中與31進(jìn)行雜交反應(yīng)，形成三鏈DNA。利用生物操作將試管T1、T2中的三鏈DNA去除，再將T1和T2合并為T(mén)0，此時(shí)的試管T0中不再含有頂點(diǎn)1、3同時(shí)存在的數(shù)字串了。同理，補(bǔ)圖中頂點(diǎn)1、6有邊連接，即頂點(diǎn)1、6同時(shí)存在時(shí)（編碼分別為11、61）制作11、61的補(bǔ)鏈，操作方法同上，此時(shí)得到的T0里面沒(méi)有頂點(diǎn)1、6同時(shí)存在的數(shù)字串。依次對(duì)補(bǔ)圖中相連的頂點(diǎn)進(jìn)行該操作，最終得到的T0里面都是滿(mǎn)足團(tuán)定義的頂點(diǎn)，根據(jù)DNA雙鏈的長(zhǎng)度可以讀出團(tuán)的規(guī)模。

圖3 DNA鏈的設(shè)計(jì)

表1 頂點(diǎn)及顏色的編碼

（3）為了讀出最大團(tuán)及每個(gè)頂點(diǎn)，我們需要借助凝膠電泳來(lái)完成。由于檢測(cè)是借助補(bǔ)圖來(lái)操作的，所以在所有團(tuán)中尋找最大團(tuán)，就是尋找補(bǔ)圖中含有頂點(diǎn)數(shù)最少的團(tuán)。含有頂點(diǎn)數(shù)較少的雙鏈分子量小，在凝膠電泳中的遷移速度較快。利用凝膠電泳技術(shù)找到遷移速度最快的DNA鏈，也就是最短的DNA片段。利用PCR擴(kuò)增和純化后，提取出這些鏈，采用非放射性標(biāo)記DNA測(cè)序的方法進(jìn)行測(cè)序，可以得到最短的DNA鏈的排序，也就得到了圖的最大團(tuán)。

5 結(jié)束語(yǔ)

本文通過(guò)三鏈DNA來(lái)求解圖的最大團(tuán)問(wèn)題，并給出了具體的實(shí)例驗(yàn)證該方法的可行性。在三鏈DNA模型中，在反應(yīng)前參與反應(yīng)的都是雙鏈DNA，穩(wěn)定性好，避免了單鏈DNA在反應(yīng)過(guò)程中發(fā)生錯(cuò)配現(xiàn)象，形成發(fā)夾結(jié)構(gòu)，降低了錯(cuò)誤率，并且操作較簡(jiǎn)單，無(wú)需對(duì)雙鏈DNA進(jìn)行解鏈，直接將探針?lè)湃朐嚬芗纯桑苊饬嗽诩訜?、解鏈、退火過(guò)程中產(chǎn)生偽解，提高了效率。在本文中，僅討論了頂點(diǎn)數(shù)較少的圖，對(duì)于頂點(diǎn)數(shù)較多的圖，也可用此方法來(lái)求解，但實(shí)際操作中可能會(huì)存在一些不足。例如隨著頂點(diǎn)數(shù)的增加，所需要的DNA序列也相應(yīng)增加，呈線(xiàn)性增長(zhǎng)ο(2n)；在篩選的過(guò)程中未能實(shí)現(xiàn)自動(dòng)化操作，需要逐一進(jìn)行檢驗(yàn)；在最后解的讀取過(guò)程中，也需要依靠相關(guān)生物手段的進(jìn)步才能準(zhǔn)確地讀出解?？傮w而言，該模型較好地處理了圖的最大團(tuán)問(wèn)題，并且可以使用該模型解決一定規(guī)模的最大團(tuán)問(wèn)題。