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

(1.安徽理工大學(xué) 數(shù)學(xué)與大數(shù)據(jù)學(xué)院, 安徽 淮南 232001; 2.香港大學(xué) 教育學(xué)院, 香港 999077; 3.上海工程技術(shù)大學(xué) 數(shù)理與統(tǒng)計(jì)學(xué)院, 上海 201620)

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

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

1 工序問(wèn)題的計(jì)算模型

1.1 工序問(wèn)題

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

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

表1 從工件Ji到工件Jj的調(diào)整時(shí)間表

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

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

(3)給(vi,vj)賦權(quán)tij.

這樣一個(gè)工序問(wèn)題就和一個(gè)求賦權(quán)有向圖的權(quán)與最小的有向哈密頓路對(duì)應(yīng),該有向哈密頓路對(duì)應(yīng)圖的頂點(diǎn)順序即為各工件的加工次序.

1.2 基本算法

步驟1：搜索出工序問(wèn)題所對(duì)應(yīng)圖G的所有有向途徑；

步驟2：保留那些經(jīng)過(guò)G所有頂點(diǎn)的有向途徑；

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

步驟4：確定出有向途徑所經(jīng)過(guò)圖的頂點(diǎn)次序，進(jìn)而求出工序問(wèn)題的解.

1.3 實(shí)例模型

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

忻州的硬件條件不是最好的，但整個(gè)工作得到了老同志的普遍認(rèn)可，工作成效非常好，可以說(shuō)工作做的是最好的。忻州的思路和做法，是貧困地區(qū)做好老干部工作的一個(gè)貢獻(xiàn)和一種引導(dǎo)。

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

表2 工件的調(diào)整矩陣

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

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

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

1.3.1 折紙基底

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

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

一般選擇分子信標(biāo)作為錨定鏈.具有發(fā)夾結(jié)構(gòu)的分子信標(biāo)一般包括兩個(gè)部分：①環(huán)狀區(qū)，長(zhǎng)度是15～30堿基的序列，能與目標(biāo)靶序列特異結(jié)合；②莖干區(qū)，長(zhǎng)度是8個(gè)堿基的互補(bǔ)序列.分子信標(biāo)具有結(jié)構(gòu)簡(jiǎn)單、特異性強(qiáng)及可熒光標(biāo)記等特點(diǎn).所以，DNA錨定鏈的制備就選擇具有這些特性的分子信標(biāo).

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

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

圖5 5種工件對(duì)應(yīng)的DNA鏈和表示單位權(quán)值帶有熒光標(biāo)記的DNA鏈

1.3.3 輔助鏈

圖6 啟動(dòng)連和輔助鏈Fig.6 The startup chain and auxiliary chains

2 工序問(wèn)題的模型求解

利用模型求解工序問(wèn)題解的原理：根據(jù)節(jié)點(diǎn)的個(gè)數(shù)和權(quán)重建立求解模型，將問(wèn)題映射為有向樹(shù)，利用訂書(shū)釘鏈將錨定鏈按有向樹(shù)的結(jié)構(gòu)錨定在折紙基底上(圖4).整個(gè)折紙基底在試管中大量穩(wěn)定存在，不發(fā)生反應(yīng).當(dāng)加入足量的啟動(dòng)鏈I后(啟動(dòng)鏈I示意圖見(jiàn)圖6)，啟動(dòng)鏈與根節(jié)點(diǎn)中的莖桿部和環(huán)部是互補(bǔ)的，根節(jié)點(diǎn)的發(fā)夾結(jié)構(gòu)打開(kāi)，反應(yīng)開(kāi)始.輔助鏈在試管中大量存在，雜交鏈?zhǔn)椒磻?yīng)繼續(xù).根據(jù)生化反應(yīng)的特點(diǎn)，有向反應(yīng)發(fā)生在哪條路徑上是隨機(jī)的.在選擇的有向路上充分反應(yīng)后，可以利用熒光光譜儀檢測(cè)到這條路上發(fā)出熒光的個(gè)數(shù)，從而得到這條有向路徑上的權(quán)值大小即調(diào)整時(shí)間之和.在這些所有可能的有向路徑中，只要找到熒光個(gè)數(shù)最小的有向路徑(調(diào)整時(shí)間之和最小)就是工序問(wèn)題的最優(yōu)解.

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

圖8 J2→J1的反應(yīng)示意圖Fig.8 The reaction scheme of J2→J1

試管中也大量存在著輔助鏈At，反應(yīng)繼續(xù)，表示權(quán)值的第二個(gè)發(fā)夾結(jié)構(gòu)也被打開(kāi)，同時(shí)檢測(cè)到熒光.此時(shí)輔助鏈第二個(gè)At中的a*-b*與AJ1中的a-b互補(bǔ)，繼續(xù)反應(yīng)將AJ1發(fā)夾結(jié)構(gòu)打開(kāi)，反應(yīng)直到節(jié)點(diǎn)J5反應(yīng)結(jié)束，此時(shí)可檢測(cè)到熒光個(gè)數(shù)為8.在其他路徑上的反應(yīng)類(lèi)似.通過(guò)熒光的個(gè)數(shù)最后得到問(wèn)題的最優(yōu)解就是J2→J3→J4→J5→J1，熒光個(gè)數(shù)為5(圖9).

圖9 有向樹(shù)中的最優(yōu)解Fig.9 The optimal solution in the directed tree

3 實(shí)例仿真

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

圖11 J2→J1，J2→J1→J3，J2→J1→J3→J4的中間產(chǎn)物的鏈?zhǔn)浇Y(jié)構(gòu)Fig.11 Chain structures of intermediate products of J2→J1，J2→J1→J3，J2→J1→J3→J4

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

文中只針對(duì)J2→J1→J3→J4→J5有向路徑進(jìn)行了仿真，其他路徑的仿真是類(lèi)似的，這里就不一一列舉了.最終通過(guò)各路徑上熒光個(gè)數(shù)的判定能夠得出工序問(wèn)題的最優(yōu)解是J2→J3→J4→J5→J1.

利用此模型求解工序問(wèn)題，在很大程度上降低了問(wèn)題的復(fù)雜度.Brun在文獻(xiàn)[24]中指出自組裝模型的復(fù)雜度計(jì)算理論，應(yīng)從兩方面來(lái)考慮此模型的復(fù)雜度：計(jì)算時(shí)間復(fù)雜度以及該模型所需參與計(jì)算的分子結(jié)構(gòu)的種類(lèi).該模型是利用雜交鏈?zhǔn)椒磻?yīng)，將求解過(guò)程映射到折紙基底上進(jìn)行.由引理知，該模型的自組裝時(shí)間與反應(yīng)(樹(shù))的深度有關(guān)，即Tim(T)=Θ(depth(T)).而所參與雜交自組裝的分子結(jié)構(gòu)主要是表示工件的分子信標(biāo)n種，表示單位權(quán)值的分子信標(biāo)1種，表示輔助鏈的分子信標(biāo)n+1種和啟動(dòng)鏈1種，所以此模型計(jì)算時(shí)所需的分子結(jié)構(gòu)的種類(lèi)為Num(T)=n+n+1+1=Θ(n).利用自組裝反應(yīng)的優(yōu)勢(shì)，得到該模型的復(fù)雜度為T(mén)im(T)+Num(T)=Θ(depth(T))+Θ(n).

4 結(jié) 論

本文針對(duì)工序問(wèn)題給出了一種基于雜交鏈?zhǔn)椒磻?yīng)的求解方法.將工序問(wèn)題映射為有向樹(shù)，待加工的工件映射為節(jié)點(diǎn)，選出t+(Ji)最小的節(jié)點(diǎn)作為根節(jié)點(diǎn).然后將有向樹(shù)錨定在矩形的折紙基底上，利用雜交鏈?zhǔn)椒磻?yīng)來(lái)求解問(wèn)題的最優(yōu)解.此模型在試管中進(jìn)行，只有加入了啟動(dòng)鏈以后，反應(yīng)才可進(jìn)行.繼續(xù)反應(yīng)，當(dāng)發(fā)夾結(jié)構(gòu)打開(kāi)后，反應(yīng)是不可逆的.因此，最終生成的都是以根節(jié)點(diǎn)為起點(diǎn)，以葉子為終點(diǎn)的路徑.而且該模型中的發(fā)夾結(jié)構(gòu)只在環(huán)部進(jìn)行區(qū)分，設(shè)計(jì)簡(jiǎn)單.模型用熒光光譜儀連續(xù)記錄熒光信號(hào)的個(gè)數(shù)來(lái)確定每條有向路徑的權(quán)值，從而尋找最優(yōu)解，模型中解的檢測(cè)也非常簡(jiǎn)便.與傳統(tǒng)的計(jì)算模型相比，通過(guò)生物分子計(jì)算將問(wèn)題的求解過(guò)程以生化反應(yīng)過(guò)程展現(xiàn)出來(lái)，該模型充分利用了它高度的并行性和可靠性.