基于雜交鏈式反應工序問題的DNA計算模型

楊 靜, 殷志祥, 唐 震, 楊新木

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

DNA計算作為仿生計算的一員歷經25年的發展，DNA納米結構已經成為構建納米材料的主力軍.DNA全稱脫氧核糖核酸，作為生命的主要遺傳物質，它包含A、T、C、G四種堿基，并且按照Watson-Crick互補原則進行信息編碼.Adelman[1]1994年首次利用DNA分子計算給出了具有7個頂點圖的哈密頓路的求解方法，之后在眾多科研人員的努力下，DNA計算從一維結構到二維結構再到三維結構[2-5]，在NP問題中起到越來越重要的作用.2006年Rothemund[6]提出了一種新的DNA納米自組裝技術——DNA折紙術.通過DNA折紙術, Rothemund得到了三角形、方形、矩形、五角星和笑臉等精細復雜的二維結構.DNA折紙術是由大量DNA短鏈作為固定鏈，將一條含有7 000多個堿基的噬菌體單鏈DNA origami折疊成任意納米級的幾何圖形，所得的圖案稱為DNA origami.每條短鏈都具有有序特異性，故被稱為訂圖釘鏈.它使得DNA折紙術具有精確的可尋址性.DNA折紙術具有設計簡單、組裝效率較高、納米可編程和納米可尋址的優勢.隨后2006年錢璐璐等[7]利用DNA折紙術構建了納米級的中國地圖.晁潔課題組利用DNA折紙術作為基底給出了有向圖的最短哈密頓路[8]，之后采用DNA納米折紙結構編碼無向圖的頂點，借助納米結構之間的粘性末端進行自組裝，給出了圖著色問題的解決方案[9]，在2019年又利用DNA折紙術結合雜交鏈式反應給出了迷宮問題的求解[10].2017年，Tikhomirov等[11]利用方形DNA折紙作為基本單元，以遞歸方式進行多次自組裝，得到了微米級蒙娜麗莎的圖案.這些成果都展示了DNA折紙術在NP問題求解中顯示出其參與計算的優勢.文獻[12]給出利用噬菌體制備DNA折紙所需的DNA鏈，為DNA折紙術的應用和產量提供了保障.

雜交鏈式反應(Hybridization Chain Reaction，HCR)是一個無酶參與的反應過程.它通過設計合理的不同寡核苷酸，由一小段核苷酸鏈作為引發劑，誘導寡核苷酸相互雜交形成一條具有二維或三維空間結構的雙鏈DNA[13-14].它是利用啟動鏈誘發兩種不同類型發夾結構的DNA分子交替雜交，交替打開發夾結構，形成帶有缺口的雙鏈DNA聚合物，且此過程無需酶參與，反應條件溫和，操作簡單，可適用于其他傳感器的信號放大.目前，雜交鏈式反應已經廣泛應用于核酸、蛋白質檢測和生物傳感器等領域[15-20].2012年，Dong等[21]利用結合HCR與G-quadruplex構建了一種免標記檢測目標DNA的熒光傳感器,目標DNA存在時，目標DNA作為引發鏈打開兩個發夾探針與其雜交，進行雜交鏈式反應形成長雙鏈，釋放出G-quadruplex結構，加入鋅卟啉(ZnPPIX)后，熒光強度增強.體系前后熒光強度的變化可以檢測目標DNA.Xiao等[22]通過將DNA微陣列與鄰近結合誘導的雜交鏈反應擴增整合，設計多重化學發光成像，并用于蛋白質生物標記物的靈敏篩選檢測.Zou等[23]提出利用雜交鏈式反應和DNA三鏈組裝的無標記點亮熒光傳感器的方法.由于該方法具有操作簡單和成本較低等優點，在生物標志物測定、臨床診斷和生物醫學檢測中有很高的應用價值.2019年，Chao等[10]利用雜交鏈式反應提出單分子DNA導航儀(DNA navigator).自此，雜交鏈反應結合熒光檢測給NP問題求解也帶來了生機.

1 工序問題的計算模型

1.1 工序問題

工序問題是生產過程時間組織的一個重要問題，是如何將多種不同零件(工件)，安排到相應的設備上并決定它們的加工順序，以利于充分地利用設備和縮短生產周期，從而提高工作效率的問題.它是圖論中的一個問題，到目前為止還沒有有效的方法.這里介紹多種工件在一臺機器上的生產排序問題.

例如，在某工廠中，設某臺機器必須加工多種工件J1,J2,…,Jn，每一種工件Ji可以是一類模具.在一種工件加工完畢之后，為了加工下一種工件，機器必須調整.如果從工件Ji到工件Jj的調整時間是tij(表1)，求這些工件的一個排序，使整個機器的調整時間最少.這個問題其實就是求一個權和最小的有向哈密頓路,到目前還沒有有效解法.本文把工序問題先轉化為一個有向圖G,每種工件Ji在G中即為圖的頂點.

表1 從工件Ji到工件Jj的調整時間表

(1)以有向圖G的頂點Ji表示工件Ji(i=1,2,…,n).

(2)以E表示有向圖G的所有弧集，(Ji,Jj)∈E.

(3)給(vi,vj)賦權tij.

這樣一個工序問題就和一個求賦權有向圖的權與最小的有向哈密頓路對應,該有向哈密頓路對應圖的頂點順序即為各工件的加工次序.

1.2 基本算法

步驟1：搜索出工序問題所對應圖G的所有有向途徑；

步驟2：保留那些經過G所有頂點的有向途徑；

步驟3：保留最短的有向途徑；

步驟4：確定出有向途徑所經過圖的頂點次序，進而求出工序問題的解.

1.3 實例模型

假設一臺機器可以生產5種工件J1,J2,…,J5，在加工完Ji后需要調整機器才能加工Jj，調整時間需要tij(i=1,2,…,5,j=1,2,…,5).將工件之間的調整關系抽象為圖1，用調整矩陣的形式給出工件之間的調整時間(tij)5×5(表2).問題是如何尋求一種工件加工順序使得所需總的調整時間最短，加工效率最高.

忻州的硬件條件不是最好的，但整個工作得到了老同志的普遍認可，工作成效非常好，可以說工作做的是最好的。忻州的思路和做法，是貧困地區做好老干部工作的一個貢獻和一種引導。

圖1 5種工件的雙向圖GFig.1 Bidirectional graph G of 5 kinds of workpiece

表2 工件的調整矩陣

為求解5種工件工序問題的解，首先將其問題的解空間映射為樹T(圖2).不失一般性，假設從J1開始加工，下一個加工的對象就是J2，J3，J4，J5中的一種，以此類推.在樹中兩頂點間的距離就表示從工件Ji到工件Jj的調整時間tij，也即這是有向賦權樹T，那么問題的解就是從根節點開始到葉子的所有有向路徑中尋求權值最小的有向路徑.

圖2 解空間映射為樹TFig.2 Solution space mapped to the tree T

在利用此模型進行求解前，先介紹此模型的組成.模型主要由三部分構成：折紙基底、DNA錨定鏈和輔助鏈.

1.3.1 折紙基底

用大量訂圖釘鏈將環形噬菌體(M13mp18)折疊成二維矩形作為折紙基底(圖3).

圖3 DNA折紙基底Fig.3 DNA origami base

一般選擇分子信標作為錨定鏈.具有發夾結構的分子信標一般包括兩個部分：①環狀區，長度是15～30堿基的序列，能與目標靶序列特異結合；②莖干區，長度是8個堿基的互補序列.分子信標具有結構簡單、特異性強及可熒光標記等特點.所以，DNA錨定鏈的制備就選擇具有這些特性的分子信標.

將帶有發夾結構的DNA鏈與帶有粘性末端的訂圖釘鏈結合，將其錨定在DNA折紙基底上，排列成圖4的等價形式.這些鏈包含頂點Ji(圖5)，兩個頂點之間的距離用來表示從工件Ji到工件Jj的調整時間(權值)tij.根據問題中權值的具體大小選取代表單位時間的權值(單位權值)，一個單位權值用一個DNA錨定鏈表示.單位權值記為unit weight，它是由4個寡聚核苷酸片斷組成3′-b*-t-b-a-5′，其中b和b*互補，在b*的末端標記上熒光基團，在b的末端標記上猝滅基團.這里單位權值的定義適用于權值之間差別較小的圖，若是權值之間相差太大，此方法就不適用.作為根節點的工件J2是由4個寡聚核苷酸片斷組成3′-b*-cJi-b-j2-5′，其余4種工件也是由4個寡聚核苷酸片斷組成3′-b*-cJi-b-a-5′，環部用來表示節點的區分.

圖4 折紙基底上有向樹Fig.4 Directed tree on origami base

圖5 5種工件對應的DNA鏈和表示單位權值帶有熒光標記的DNA鏈

1.3.3 輔助鏈

圖6 啟動連和輔助鏈Fig.6 The startup chain and auxiliary chains

2 工序問題的模型求解

利用模型求解工序問題解的原理：根據節點的個數和權重建立求解模型，將問題映射為有向樹，利用訂書釘鏈將錨定鏈按有向樹的結構錨定在折紙基底上(圖4).整個折紙基底在試管中大量穩定存在，不發生反應.當加入足量的啟動鏈I后(啟動鏈I示意圖見圖6)，啟動鏈與根節點中的莖桿部和環部是互補的，根節點的發夾結構打開，反應開始.輔助鏈在試管中大量存在，雜交鏈式反應繼續.根據生化反應的特點，有向反應發生在哪條路徑上是隨機的.在選擇的有向路上充分反應后，可以利用熒光光譜儀檢測到這條路上發出熒光的個數，從而得到這條有向路徑上的權值大小即調整時間之和.在這些所有可能的有向路徑中，只要找到熒光個數最小的有向路徑(調整時間之和最小)就是工序問題的最優解.

圖7 折紙基底上J2→Jj權值的表示Fig.7 The representation of J2→Jj weights on origami base

圖8 J2→J1的反應示意圖Fig.8 The reaction scheme of J2→J1

試管中也大量存在著輔助鏈At，反應繼續，表示權值的第二個發夾結構也被打開，同時檢測到熒光.此時輔助鏈第二個At中的a*-b*與AJ1中的a-b互補，繼續反應將AJ1發夾結構打開，反應直到節點J5反應結束，此時可檢測到熒光個數為8.在其他路徑上的反應類似.通過熒光的個數最后得到問題的最優解就是J2→J3→J4→J5→J1，熒光個數為5(圖9).

圖9 有向樹中的最優解Fig.9 The optimal solution in the directed tree

3 實例仿真

Visual DSD是常用的DNA雜交鏈式反應的仿真軟件.軟件的界面由三部分組成：編碼區、設置區和顯示區.編碼區給出參與反應的DNA序列組成、濃度及反應時間的設定；設置區進行語法模式及仿真模式的設定；顯示區顯示DNA序列隨反應進行變化的曲線、產物的結構等.啟動鏈為input、折紙基底Origami、輔助鏈At及其他輔助鏈的濃度分別設定為20 nM、20 nM、100 nM和20 nM，反應時間設定為7 000 s.隨著啟動鏈input的加入，誘導雜交反應開始，輔助鏈AJ2最先與啟動鏈input反應，在圖10中，AJ2較其他輔助鏈的濃度先呈下降趨勢，隨著反應的進行，輔助鏈的消耗順序也是以J2→J1→J3→J4→J5這個順序依次下降.反應繼續進行，中間產物的濃度先增加，達到最大峰值后，濃度逐漸減小，最終趨于0，最終產物sp26則趨于穩定.這些中間產物分別對應于從根節點到子節點的有向路，當反應完成后，生成根節點到葉的有向路時，中間產物的濃度趨于0.在圖10中可以看到，當啟動鏈加入后，中間產物sp9的濃度最先達到峰值為6.1 nM，這個中間產物就啟動鏈I與根節點AJ2反應的生成物，隨著反應的繼續，它的濃度也最終趨于0.最終產物sp26表示的J2→J1→J3→J4→J5有向路，它隨著反應的繼續濃度不斷增加.充分反應后，濃度趨于穩定.圖11給出了J2→J1、J2→J1→J3、J2→J1→J3→J4的中間生成物的鏈式結構.

圖11 J2→J1，J2→J1→J3，J2→J1→J3→J4的中間產物的鏈式結構Fig.11 Chain structures of intermediate products of J2→J1，J2→J1→J3，J2→J1→J3→J4

圖10 解J2→J1→J3→J4→J5的模擬結果Fig.10 The simulation results of solutionJ2→J1→J3→J4→J5

文中只針對J2→J1→J3→J4→J5有向路徑進行了仿真，其他路徑的仿真是類似的，這里就不一一列舉了.最終通過各路徑上熒光個數的判定能夠得出工序問題的最優解是J2→J3→J4→J5→J1.

利用此模型求解工序問題，在很大程度上降低了問題的復雜度.Brun在文獻[24]中指出自組裝模型的復雜度計算理論，應從兩方面來考慮此模型的復雜度：計算時間復雜度以及該模型所需參與計算的分子結構的種類.該模型是利用雜交鏈式反應，將求解過程映射到折紙基底上進行.由引理知，該模型的自組裝時間與反應(樹)的深度有關，即Tim(T)=Θ(depth(T)).而所參與雜交自組裝的分子結構主要是表示工件的分子信標n種，表示單位權值的分子信標1種，表示輔助鏈的分子信標n+1種和啟動鏈1種，所以此模型計算時所需的分子結構的種類為Num(T)=n+n+1+1=Θ(n).利用自組裝反應的優勢，得到該模型的復雜度為Tim(T)+Num(T)=Θ(depth(T))+Θ(n).

4 結 論

本文針對工序問題給出了一種基于雜交鏈式反應的求解方法.將工序問題映射為有向樹，待加工的工件映射為節點，選出t+(Ji)最小的節點作為根節點.然后將有向樹錨定在矩形的折紙基底上，利用雜交鏈式反應來求解問題的最優解.此模型在試管中進行，只有加入了啟動鏈以后，反應才可進行.繼續反應，當發夾結構打開后，反應是不可逆的.因此，最終生成的都是以根節點為起點，以葉子為終點的路徑.而且該模型中的發夾結構只在環部進行區分，設計簡單.模型用熒光光譜儀連續記錄熒光信號的個數來確定每條有向路徑的權值，從而尋找最優解，模型中解的檢測也非常簡便.與傳統的計算模型相比，通過生物分子計算將問題的求解過程以生化反應過程展現出來，該模型充分利用了它高度的并行性和可靠性.