團數的DNA折紙術計算模型

崔建中,殷志祥,楊 靜

(1．安徽理工大學 電氣與信息工程學院, 安徽 淮南 232001；2．淮南聯合大學 計算機系， 安徽 淮南 232038；3．安徽理工大學 數學與大數據學院, 安徽 淮南 232001)

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

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

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

1 團數問題

圖1 簡單無向圖及其補圖

2 團數問題的DNA折紙術計算模型

2.1 腳手架鏈和訂書釘鏈的設計

2.2 團的表示

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

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

圖4 最大團

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 再次折疊腳手架鏈選擇編碼正確的團

圖6 鏈置換打開表示頂點i在團中的發夾結構

圖7 打開表示頂點在團中的發夾結構的示意圖

2.4 算法復雜度

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

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

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

3 結論

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