團(tuán)數(shù)的DNA折紙術(shù)計算模型

崔建中,殷志祥,楊 靜

(1．安徽理工大學(xué) 電氣與信息工程學(xué)院, 安徽 淮南 232001；2．淮南聯(lián)合大學(xué) 計算機(jī)系， 安徽 淮南 232038；3．安徽理工大學(xué) 數(shù)學(xué)與大數(shù)據(jù)學(xué)院, 安徽 淮南 232001)

DNA折紙術(shù)[1]是近年來提出的一種新的DNA自組裝方法，是目前DNA自組裝領(lǐng)域研究的熱點(diǎn)問題.與DNA模塊自組裝相比，DNA折紙術(shù)能構(gòu)造出更復(fù)雜、精細(xì)的納米結(jié)構(gòu)，且DNA鏈的設(shè)計簡單，組裝效率較高.它的原理是利用較短的DNA訂書釘鏈(Staple)，按堿基配互補(bǔ)對原則，對一條較長的腳手架鏈(Scaffold)進(jìn)行折疊，從而構(gòu)造出理想的納米結(jié)構(gòu).文獻(xiàn)[2]利用DNA 折紙術(shù)原理成功地構(gòu)造出納米中國地圖，證明了DNA折紙術(shù)具備構(gòu)造非對稱圖案的能力.文獻(xiàn)[3]將文獻(xiàn)[1]的方法加以推廣，并成功地構(gòu)造出方螺帽等6種三維結(jié)構(gòu).文獻(xiàn)[4]利用折紙術(shù)折疊成長方形的納米結(jié)構(gòu)來編碼有向圖的頂點(diǎn)，給出了通過該長方形結(jié)構(gòu)的自組裝尋找最短哈密頓路的方法.文獻(xiàn)[5]采用DNA 納米折紙結(jié)構(gòu)編碼無向圖的頂點(diǎn)，借助納米結(jié)構(gòu)之間的粘性末端進(jìn)行自組裝，給出了圖著色問題的一種解決方法.文獻(xiàn)[6] 利用方形DNA折紙作為基本單元，以遞歸方式進(jìn)行多次自組裝，得到了微米級蒙娜麗莎的圖案.文獻(xiàn)[7]設(shè)計了三維磚形DNA基本折紙單元，可以組裝成更大尺寸的三維結(jié)構(gòu).文獻(xiàn)[8]利用V形DNA折紙作為基本單元，通過控制基本單元之間的幾何形狀和作用，可以構(gòu)造更大的組裝體.文獻(xiàn)[9]提出了利用噬菌體制備DNA折紙所需的DNA鏈，為DNA折紙的應(yīng)用和量產(chǎn)提供了保障.

最大團(tuán)問題(Maximum Clique Problem)是圖論中經(jīng)典的組合優(yōu)化問題，也是一類NP完全問題.最大團(tuán)問題在計算機(jī)視覺、市場分析、編碼理論中都有非常廣泛的應(yīng)用.文獻(xiàn)[10] 使用雙鏈DNA分子編碼無向圖的頂點(diǎn)，建立初始數(shù)據(jù)池，根據(jù)補(bǔ)圖中相鄰的頂點(diǎn)不可能同時出現(xiàn)在極大團(tuán)中，在初始數(shù)據(jù)池中并行地刪除非解.最后，初始數(shù)據(jù)池中長度最短的DNA分子編碼的頂點(diǎn)即為所求的最大團(tuán).文獻(xiàn)[11]給出了利用質(zhì)粒求解最大團(tuán)問題的算法.文獻(xiàn)[12]將剪枝策略運(yùn)用到DNA計算中，給出了基于粘貼模型的最大團(tuán)問題的算法.文獻(xiàn)[13]給出了基于環(huán)形DNA分子求解最大團(tuán)問題的計算模型.文獻(xiàn)[14]提出了最大團(tuán)問題的Tile自組裝模型.

圖G中最大團(tuán)的階數(shù)即團(tuán)數(shù)，記為ω(G)，它與圖的色數(shù)x(G)密切相關(guān).易知，若圖的團(tuán)數(shù)為K，則該圖至少是K-著色的.目前，DNA折紙術(shù)主要應(yīng)用在納米技術(shù)領(lǐng)域.將DNA折紙術(shù)應(yīng)用于搜索簡單無向圖的最大團(tuán)，進(jìn)而求解圖的團(tuán)數(shù).該模型利用訂書釘鏈折疊腳手架鏈形成發(fā)夾結(jié)構(gòu)，凝膠電泳檢測發(fā)夾結(jié)構(gòu)的變化來建立初始數(shù)據(jù)池、刪除非解、讀解.該模型簡單、讀解方便、可行性高.文中提出的計算模型一方面證明了DNA折紙術(shù)可以用來求解組合優(yōu)化問題，另一方面也證明了訂書釘鏈與腳手架鏈的雜交，結(jié)合鏈置換，凝膠電泳從算法的角度是完備的.它不僅拓寬了DNA折紙術(shù)的應(yīng)用領(lǐng)域，也為解決組合優(yōu)化問題提供了一種新的思路和方法.

1 團(tuán)數(shù)問題

圖1 簡單無向圖及其補(bǔ)圖

2 團(tuán)數(shù)問題的DNA折紙術(shù)計算模型

2.1 腳手架鏈和訂書釘鏈的設(shè)計

2.2 團(tuán)的表示

圖2 腳手架鏈(中)與訂書釘鏈上(下) 圖3 團(tuán)的表示

按照這種方法，最大團(tuán){3,4,5,6}的示意圖如圖4所示.

圖4 最大團(tuán)

2.3 算法

步驟1：

Fori=1 ton

Divide(T0→T1,T2)

Merge(T1,T2→T0)

Gel(T0)=l+ny→T0

Endfor

步驟2：

Fori=1 tom

Forj=i+1 tom

Divide(T0→T1,T2,T3)

Merge(T1,T2,T3→T0)

Endif

Gel(T0)=l+ny→T0

Endfor

Endfor

步驟3：

Gel(T0)=lmin→T0

圖5 再次折疊腳手架鏈選擇編碼正確的團(tuán)

圖6 鏈置換打開表示頂點(diǎn)i在團(tuán)中的發(fā)夾結(jié)構(gòu)

圖7 打開表示頂點(diǎn)在團(tuán)中的發(fā)夾結(jié)構(gòu)的示意圖

2.4 算法復(fù)雜度

對于簡單無向G(V,E)，其中|V|=n,|E|=m，文中提出的計算模型需要編碼n種寡聚核苷酸片斷表示給定圖中的頂點(diǎn)，將這n種寡聚核苷酸片斷連接構(gòu)成腳手架鏈.當(dāng)表示頂點(diǎn)的寡聚核苷酸片斷編碼完畢，相應(yīng)的訂書釘鏈及釘書釘鏈的補(bǔ)鏈的編碼也隨之確定.因此，文中提出的模型的編碼復(fù)雜度為O(n).

在初始數(shù)據(jù)池中，為表示所有可能的團(tuán)，模型需要n次折疊腳手架鏈，1次凝膠電泳，生成腳手架鏈上發(fā)夾結(jié)構(gòu)的組合.然后，針對補(bǔ)圖中的每條邊，需要3次折疊腳手架鏈，1次凝膠電泳，刪除非團(tuán).因此，共需3m次折疊腳手架鏈，m次凝膠電泳.最后為確定團(tuán)數(shù)，需要1次打開腳手架鏈上的發(fā)夾結(jié)構(gòu)，1次凝膠電泳.故模型的時間復(fù)雜度為O(n2).

與其它的DNA計算模型相比，文中提出的計算模型初始數(shù)據(jù)池中僅含有一種類型腳手架鏈，與問題的規(guī)模無關(guān)，腳手架鏈上發(fā)夾結(jié)構(gòu)的組合為2n，它對應(yīng)編碼的頂點(diǎn)是否在團(tuán)中的所有可能情況.腳手架鏈上發(fā)夾結(jié)構(gòu)的變化可通過腳手架鏈的長度反映出來，凝膠電泳可以準(zhǔn)確、可靠地判斷發(fā)夾結(jié)構(gòu)的變化，故模型的可靠性大大增加，可行性更高.

3 結(jié)論

應(yīng)用DNA 折紙術(shù)求解團(tuán)數(shù)問題，提出了團(tuán)數(shù)的DNA折紙術(shù)計算模型.其核心思想是利用DNA折紙術(shù)，結(jié)合鏈置換，將團(tuán)數(shù)映射為腳手架鏈上表示頂點(diǎn)在團(tuán)中的發(fā)夾結(jié)構(gòu)的數(shù)目，通過凝膠電泳檢測腳手架鏈的長度，進(jìn)而判斷發(fā)夾結(jié)構(gòu)的變化.DNA 折紙術(shù)的最大優(yōu)點(diǎn)在于DNA鏈的編碼簡單，腳手架鏈和訂書釘鏈雜交反應(yīng)的相對濃度要求不高，實(shí)驗簡單，組裝效率高.將DNA折紙術(shù)的核心思想應(yīng)用于組合優(yōu)化問題的求解，結(jié)合凝膠電泳判斷發(fā)夾結(jié)構(gòu)的變化，讀解更簡單，從而提高了DNA計算模型的可行性、可靠性.文中提出的模型目前僅能求出給定無向圖的團(tuán)數(shù)，而最終確定最大團(tuán)中的頂點(diǎn)仍需要結(jié)合其他的讀解方法，如分子信標(biāo)，這也是下一步要進(jìn)行的工作.文章從理論層面證明了訂書釘鏈與腳手架鏈的雜交，結(jié)合鏈置換，凝膠電泳從算法的角度是完備的.它不僅擴(kuò)寬了DNA折紙術(shù)的應(yīng)用領(lǐng)域，也為解決組合優(yōu)化問題提供了一種新的思路和方法.