陳海芳，殷志祥

(安徽理工大學數學與大數據學院，安徽淮南232001)

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

1 三鏈DNA的形成

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

圖1 三鏈DNA的形成

2 最大團問題

設G是一個圖，V(G)和E(G)分別表示圖的頂點集和邊集，S是G的一個頂點子集，若S中任意兩點都與E(G)中的邊相連，則稱S是圖G的一個團。若對G的任意其他團S′，都有 ||S′≤ ||S，則稱S是G的最大團。圖2是一個具有6個頂點的簡單圖。

圖2 6個頂點的簡單圖

3 最大團問題的DNA算法

3.1 基本算法

步驟1：DNA單鏈根據Waston-Click原理生成數據池；

步驟2：刪除不滿足條件的解；

步驟3：輸出結果。

3.2 生物算法

對于n個頂點的簡單圖的團，可以用一個n位的二進制的數字串來表示。具體表示方式：當圖的某個頂點在團中時，編碼為1；當該頂點不在團中時，編碼為0。如圖2中，頂點1、2、5組成的一個團可以用110 010來表示。因此可以用0、1組成的n位數字串來表示所有可能的情況，稱所有二進制數的集合為數據池。為了滿足最大團的定義，需要對數據池進行篩選，只保留正確解，具體的操作：

（i）對圖的各個頂點進行編碼，構造出代表不同頂點的DNA單鏈，然后將這些單鏈與連接酶一起加入到溶液中進行生化反應得到雙鏈DNA，即生成初始數據池T0。

（ii）為了滿足團定義的要求，需要對初始數據池中頂點的組合進行篩選。結合圖G的補圖，因為圖中的團在其圖的補圖中對應的是空圖，所以在補圖中相連的兩頂點在原圖中是斷開的，因此，他們不可能是同一團中的頂點。因此對應于編碼來說，在補圖中相連的兩個頂點不可能同時為1。據此，借助三鏈DNA進行檢測，配制代表補圖中相連的兩個頂點的DNA片段的補鏈，將其與抗原蛋白質相結合，制作成探針，加入到數據池中，形成三鏈DNA。沒有形成三鏈的就是滿足在補圖中未被連接的頂點，則該頂點都包含在團中。利用生物操作技術將數據池中的三鏈DNA去除，剩下的雙鏈DNA就是滿足團定義的點所對應的DNA鏈。最后根據1的個數（即團中所包含頂點的個數）來讀出最大團的規(guī)模。

（iii）通過凝膠電泳來對數據池中的最大團方案進行分離，讀出最大團。

4 算法實例

下面以圖2為例，求解圖的最大團問題。

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

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

圖3 DNA鏈的設計

表1 頂點及顏色的編碼

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

5 結束語

本文通過三鏈DNA來求解圖的最大團問題，并給出了具體的實例驗證該方法的可行性。在三鏈DNA模型中，在反應前參與反應的都是雙鏈DNA，穩(wěn)定性好，避免了單鏈DNA在反應過程中發(fā)生錯配現象，形成發(fā)夾結構，降低了錯誤率，并且操作較簡單，無需對雙鏈DNA進行解鏈，直接將探針放入試管即可，避免了在加熱、解鏈、退火過程中產生偽解，提高了效率。在本文中，僅討論了頂點數較少的圖，對于頂點數較多的圖，也可用此方法來求解，但實際操作中可能會存在一些不足。例如隨著頂點數的增加，所需要的DNA序列也相應增加，呈線性增長ο(2n)；在篩選的過程中未能實現自動化操作，需要逐一進行檢驗；在最后解的讀取過程中，也需要依靠相關生物手段的進步才能準確地讀出解?？傮w而言，該模型較好地處理了圖的最大團問題，并且可以使用該模型解決一定規(guī)模的最大團問題。