旅行商問題的DNA可視化計算模型

張彤彤, 楊 靜, 殷志祥, 蔣天懌, 鄭雅雯

(1.安徽理工大學 數學與大數據學院, 安徽 淮南 232001; 2.上海工程技術大學 數理與統計學院, 上海 201620)

隨著計算機技術的高速發展,在分子計算、納米技術和生物醫學等領域,傳統的電子設備無法直接參與進程,而基于DNA分子的化學反應網絡作為一種有效的編程語言可以在分子計算、納米技術和生物醫學等領域通過多種方式存儲和處理信息[1].DNA折紙術作為化學反應網絡的基本構建原理之一,目前廣泛應用于生物計算、生物傳感器、醫藥載體及信息安全等方面,取得了很大的發展[2-10].

2019年,Chao構建了一個單分子DNA導航系統,它可以對錨定在二維DNA折紙基地上的十頂點迷宮樹上執行單分子平行深度優先搜索.通過單分子DNA導航器可以遍歷的探索出迷宮的所有可能路徑,從而找到迷宮的正確路徑[11].同年,Zhang開發了DNA折紙加密技術,該技術利用M13mp18病毒支架折疊成納米級的自組裝盲文圖案來進行安全通信,從而可以創建大小超過700位的密鑰[12].2020年,Fan等人演示了基于可重構DNA折紙多米諾陣列的分子信息編碼方式,當添加一組密鑰(DNA鏈)時,圖形數據可以在DNA折紙多米諾陣列中轉換成可見的圖案[13].2021年,Tang提出了構建基于DNA折紙基底的DNA分子邏輯電路的策略[14].跟傳統的納米自組裝技術相對比而言,DNA折紙術具備設計簡潔、操作簡便易上手、組裝效率高、反應速率快、實驗成功率極高且實施過程并不復雜及納米可尋址等優勢,因而更容易構造出結構穩定、精度準確率高、復雜但可控的納米結構.研究人員在分子生物技術的鉆研歷程中,對DNA折紙術的研究探索從一維結構晉升二維結構再深入到三維結構,意味著DNA折紙術的研究空間廣闊,并且在NP完全問題的求解方面扮演著不可或缺的角色.

為降低NP-完全問題的復雜度,為旅行商問題提供更簡明扼要的解決方案,本文利用DNA折紙術折出固定的長方形納米結構作為折紙基底,將旅行商問題映射為折紙基底上的有向圖,利用分子信標求得該問題的最優解.

1 旅行商問題的DNA計算模型

1.1 分子信標

分子信標(Molecular Beacon)是一種寡聚核苷酸探針,具有莖環結構和雙熒光基團標記的發夾結構的分子探針,基于堿基互補配對原則(The principle of complementary base pairing)及熒光共振能量轉移現象(Fluorescence Resonance Energy Transfer)設計構成[15].分子信標通常包括環狀區、莖干區、熒光基團和猝滅基團四個組成部分.其作用原理為:沒有靶分子時,分子信標的熒光基團和猝滅基團靠得很近,由于熒光共振能量轉移原理熒光被吸收.當雙鏈雜交體形成時,分子信標與序列完全互補的靶分子進行特異性結合,分開分子信標莖桿互補區,改變了空間構型,熒光基團和猝滅基團距離增大,熒光恢復.

1.2 雜交鏈式反應

早在2004年,著名學者Niles Pierce 和Robert Dirks運用DNA納米結構實現了自組裝,稱為雜交鏈式反應(hybridization chain reaction,HCR)[16].該反應明確表示,在沒有任何外部輸入的前提下,DNA與底物的結合能夠實現自主完成識別和信號放大的目的.雜交鏈式反應的反應物通常包含2個發夾DNA探針H1和H2以及引發鏈I.當溶液中不使用引發鏈I時,溶液中并未自發的發生雜交鏈式反應,而是2個發夾DNA探針H1和H2在溶液中穩定的共存.然而當引發鏈I添加進溶液時,引發鏈I會啟動2個發夾DNA探針H1和H2觸發雜交鏈式反應,在反應終止后一條長的雙鏈DNA便會自組裝形成.圖1所示為雜交鏈式反應的原理圖.引發鏈I識別方法是將第一個發夾DNA探針H1的黏性末端及其莖部(a-b部分)相結合,利用雜交鏈式反應,使得H1的莖環結構開啟,且致使暴露出的單鏈H1(c-b*部分)展示出來,裸露在外;接著第二個發夾DNA探針的黏性末端及莖部(c-b*部分)被上一部分暴露外部的堿基識別并與第二個發夾DNA探針雜交,以至于第二個發夾DNA探針H2的莖環結構被其打開,從而致使暴露出的單鏈(a*-b*部分)又能夠識辨且開啟接下來的一個H1的莖部和黏性末端.

圖1 雜交鏈式反應的原理圖Figure 1 Schematic diagram of the hybrid chain reaction

上述雜交鏈式反應的原理可以用來說明其中的化學過程,科學研究顯示雜交鏈式反應屬于等溫擴增技術,只要提供簡單的控溫儀器設備就可以完成該反應,大大降低了對于儀器復雜度的要求.不僅如此,還可以大幅度降低實驗的成本,因為該反應不需要輔助酶的參與,具有良好的重現性.現階段,利用該技術進行信號放大在生物醫學領域得到了廣泛的應用[17].

1.3 旅行商問題

旅行商問題(Traveling Salesman Problem,TSP)是一個典型的組合優化問題.TSP問題通常被描述為:一個商人要找一條通過n個城市的最短回路.即給定一系列點集V(|V|=n),在點集中從一點出發,尋找一條最短路徑,該路徑經過點集中的所有點,并且每個點只經過一次.對于該問題可以初步表示為:

(1)

(2)

(3)

xij∈{0,1}, ?i,j∈V

(4)

其中:xi,j表示從節點i到節點j的路徑,ci,j表示路徑i→j的長度;第一個約束保證一個節點只出發一次,第二個約束保證一個節點值到達一次.由于旅行商問題可能的路徑總數與城市數目n是呈指數型增長的,所以很難求得其最優解.生活中很多問題例如連鎖店的貨物配送路線等,都可以通過簡化處理和數學建模變成TSP問題.因此對TSP問題求解方法的研究具有很重要的實際價值.

2 旅行商問題DNA算法生物實現

2.1 算法步驟

設有n個城市,一個商人從某城市出發,要經過其余的(n-1)個城市,最終回到出發的城市,共有m條可能的路線,利用DNA算法求解此商人經過的最短路徑的步驟如下:

步驟1 利用DNA折紙術折疊出具有固定大小的長方形DNA納米結構,即用其作為DNA折紙基底,也就是說二維矩形的折紙基底是大量訂書釘鏈將環形噬菌體(M13mp18)折疊而成;

步驟2 任意兩個城市之間的路徑用一段亞穩態得到發夾結構的分子信標表示,在發夾結構的莖部固定猝滅基團和熒光基團,共有m條路徑;

步驟3 每一座城市即頂點用分子信標表示,并且將分子信標固定在DNA折紙基底上,然后將路徑映射為一個有向圖,選擇根節點最終將問題映射為有向樹,將有向樹錨定在折紙基底上;

步驟4 通過雜交鏈式反應,反映出經過每個點且長度最短的DNA長鏈,即為旅行商問題的最優解,同時可用熒光標記此鏈,實現該算法的可視化.

2.2 算法模型的實例分析

以5個城市的旅行商問題為例,每個城市分別用J1,J2,J3,J4,J5表示.每兩個城市Ji和Jj間的距離用Jij表示,{Jij|i=1,2,…,5;j=1,2,…,5,i

圖2 TSP問題的雙向圖Figure 2 Two-way diagram of the TSP problem

該模型是在矩形的二維DNA折紙基底上定義的,DNA折紙基底是通過用短鏈折疊環形噬菌體(M13mp18)形成(圖3).在本文中,任意兩個城市之間用亞穩態的發夾結構的分子信標表示,將猝滅基團和熒光基團固定在具有發夾結構DNA鏈的莖部的兩端,并在帶發夾結構的DNA鏈的5′端末尾設計編碼,使其能夠與DNA折紙基底上延伸出的訂書釘鏈的黏性末端相互匹配(即互補配對),使得該結構能夠被固定在DNA折紙基底上.在此算法中,代表任意兩座城市之間距離的DNA鏈的權重(單位距離)可以通過分子信標來表示[18],分子信標個數即代表路徑的長度.

為了達到求解旅行商問題的解的目的,第一步將問題的解空間映射成有向樹T(如圖4).如果此商人從J2出發,則下一個到達的城市就是J1,J3,J4,J5中的一座,依次類推進行下去.兩個節點之間的長度表示了從城市Ji到城市Jj商人所需要行走的距離tij,即此樹表示有向賦權樹T.這樣,在求解過程中,問題的解就變成了從每條根節點出發到葉片的路徑中找到一條最有最小權值的路徑.即為尋找權值最小的路.在此實例中,不妨假設J2作為樹的根節點,則其解空間的映射如圖4所示.

圖4 解空間映射為樹TFigure 4 The solution space is mapped to a tree T

2.2.1 DNA錨定鏈

研究發現,結構簡單的分子信標擁有特異性強的優點,而且可熒光標記這一優勢為實驗提供了方便.因此在該實例中,制備DNA錨定鏈就可以選擇具有上述描述特性的此類分子信標來進行.圖5代表DNA折紙基底上對應的有向樹,具體展開表示在DNA折紙基底上錨定且排列的等價形式,即為聯結帶有發夾結構的DNA鏈以及帶有黏性末端的訂書釘鏈,如圖5所示.這些鏈囊括頂點Ji,采用分子信標代表整個頂點,能夠更直觀方便的觀察反應.這些鏈包含頂點Ji(圖5),從城市Ji至城市Jj距離(權值)tij用兩個頂點之間的距離來代表.根據實例問題中的數值選取代表單位距離的權值,一個單位權值用對應的DNA錨定鏈代表.unit distance表示單位權值,它是依據4個寡聚核苷酸片段構成3′-b*-t-b-a-5′,在這里b和b*互補,在b*的末端標記上熒光基團,在b的末端標記上猝滅基團.所有這5座城市都由4個寡聚核苷酸片段組成,其中一個是根節點城市J2,J2是由4個寡聚核苷酸片段組成3′-b*-cJi-b-j2-5′,其余4座城市亦是由4個寡聚核苷酸片段構成3′-b*-cJi-b-a-5′,環部則用來代表不同的節點的區分.在圖6中,延長部分表示訂書釘鏈,a為黏性末端,可與訂書釘鏈發生反應.

圖5 5座城市對應的DNA鏈和表示單位權值帶有熒光標記的DNA鏈Figure 5 The corresponding DNA strands for 5 cities and DNA strands with fluorescent markers representing unit weights

圖6 折紙基底上對應的有向樹Figure 6 The corresponding directed tree on the origami base

2.2.2 輔助鏈

3 模型的求解

參考模型求出TSP問題的答案的理論原理是:根據節點數量和權重建立求解模型,并將問題轉換為有向樹的形式.然后,可以利用訂書釘鏈將錨定鏈按有向樹的結構固定在DNA折紙基底上[19].起初,整個模型大量穩定共存于試管中,并未發生任何響應.然而當加入足量的啟動鏈I時(如圖7所示)就會發生反應,有向反應發生在哪條路徑上是隨機的.在這些所有可能的解中,只要找到分子信標個數最小的就是旅行商問題的最優解.

圖7 啟動鏈和輔助鏈Figure 7 Startup and secondary chains

假設這五座城市在DNA折紙基底上的分布呈五邊形,各個邊距離如圖8所示.

圖8 旅行商實例圖Figure 8 Example diagram of traveling salesmen

商人從J2出發,到達J1,J3,J4,J5的距離分別為2、3、3、2,在DNA折紙基底上的權值表示見圖9.

圖9 折紙基底上J2→J1權值的表示Figure 9 Representation of J2 to J1 weights on an origami substrate

4 實例仿真

模擬DNA雜交鏈式反應過程的仿真軟件主要為Visual DSD.主要可劃分為三個模塊:編碼區、設置區和顯示區[20].其中,設置所要進行的反應的DNA序列構成,反應的濃度和時間均在編碼區實現;設置區可以選擇把實驗的操作模式設定為語法模式或者仿真模式; DNA序列隨反應繼續進行而生成的反應曲線及產物結構等方面在顯示區表明.啟動鏈記為input,DNA折紙基底記為origami,輔助鏈和其余輔助鏈的濃度各自設定為20 nM,20 nM,100 nM,20 nM,反應時間設定是7 000 s.伴隨著啟動鏈input的加入,雜交反應被誘導出現,其中輔助鏈率先參與啟動鏈input反應,仔細觀察圖12發現,AJ2對比其他輔助鏈的濃度而言開始呈下降趨勢.輔助鏈的消耗次序亦是以J2→J1→J3→J4→J5→J2此順序逐步降低.反應進一步開展,導致中間產物的濃度先逐步上升,達到最高點后逐漸下降、最終趨于0,最終產物sp26的濃度生成速率也逐漸平穩.從根節點至子節點的有向路徑是由上述產生的中間產物所對應描述的,因此在終止反應時,即從根節點到葉的有向路生成的時候,中間產物的濃度接近于0.圖11表明,當啟動鏈添加后,中間產物sp9的濃度率先抵達峰值,即6.1nM,中間產物實際為啟動鏈I與根節點AJ2反應的生成物,在反應繼續的同時,它也逐漸消失即濃度也最終接近0.最終產物sp26顯示的J2→J1→J3→J4→J5→J2有向路,在反應不斷進行的同時,最終產物的濃度也在相應的升高,等到反應完全結束即反應充分且終止后,生成物的濃度趨于平穩.

圖12 解J2→J1→J3→J4→J5→J2的模擬結果Figure 12 Solve the simulation results of J2 to J1 to J3 to J4 to J5 to J2

本文針對J2→J1→J3→J4→J5→J2路徑進行了仿真,其他路徑的仿真也類似.最終,通過各路徑上熒光個數就能夠直觀的得出旅行商問題最優解J2→J3→J4→J5→J1→J2和J2→J1→J3→J4→J5→J2.

使用此模型解決TSP問題,求解TSP問題的復雜程度極大地降低.Yuriy Brun在文獻[21-22]中提出了自組裝模型的復雜度計算理論,因此此模型的復雜度應該從以下兩方面考慮:計算的時間復雜度和該模型所需參與計算的分子結構的種類復雜度.該模型的理論原理是利用雜交鏈式反應把整體的求解過程映射到DNA折紙基底上,從而直觀的發生反應求解.那么通過引理可知,該模型的自組裝時間和反應(樹)的深度有聯系,即Tim(T)=Θ(depth(T)).當前所參與雜交自組裝的分子結構可大致劃分為n種描述城市即頂點的分子信標,1種描述單位權值的分子信標,(n+1)種描述輔助鏈的分子信標以及1種啟動鏈,綜合來看利用此模型求解時所需的分子結構的種類為Num(T)=n+n+1+1=Θ(n).合理運用自組裝反應的天然優勢,再進一步對接該模型的實際操作過程,自然而然推出該模型的復雜度為Tim(T)+Num(T)=Θ(depth(T))+Θ(n).

5 結 語

本文針對旅行商問題建立了一種依據DNA折紙術和雜交鏈式反應的模型求解方法.將旅行商問題具體映射為有向樹,將城市映射為節點,選出合適的城市即節點設為根節點.接著將有向樹錨定在矩形的DNA折紙基底上,利用雜交鏈式反應得到所有可行解,最終求得最優解.此模型在試管中進行,加入啟動鏈后開始反應,發夾結構打開后,反應不可逆.所以最終生成的路徑均是以根節點作為首,以葉子為末的.要格外注意的是,此模型中使用分子信標的發夾結構,所以只需要在發夾結構的環部區分即可,使得設計更加便捷.最終用分子信標的個數來標定每條有向路徑的權值,進一步尋找最短路徑即最優解.相比較之前的求解模型而言,前者所用方法較為傳統復雜,而利用生物分子計算把問題的解答步驟用生化反應的過程完全呈現,直觀簡單且容易操作,誤差較小復雜度也能夠計算,實現了該模型的可視化.在下一步的研究中,是否可以嘗試運用納米金顆粒取代分子信標更加直觀的解決旅行商問題及其變體成為我們研究的重中之重.