龐 雪，楊 靜，殷志祥，唐 震，楊新木

（1.安徽理工大學(xué) 數(shù)學(xué)與大數(shù)據(jù)學(xué)院，安徽 淮南 232001；2.上海工程技術(shù)大學(xué) 數(shù)理與統(tǒng)計(jì)學(xué)院，上海 201620）

1 引言

隨著生物技術(shù)的發(fā)展，DNA 計(jì)算模型為解決背包問(wèn)題提供了一種新的途徑。由于DNA 計(jì)算機(jī)具有巨大并行性、海量存儲(chǔ)以及低能耗等優(yōu)點(diǎn)，因此可以彌補(bǔ)現(xiàn)有計(jì)算機(jī)在某些領(lǐng)域的不足。很多學(xué)者對(duì)一維和多維背包問(wèn)題給出了不同的DNA計(jì)算模型[1-6]。2003 年，殷志祥基于表面的DNA計(jì)算模型求解了一般形式的0-1 規(guī)劃問(wèn)題[7]。2014年，楊靜等人利用三鏈DNA 計(jì)算模型求解了0-1背包問(wèn)題和完全背包問(wèn)題[8]。2018 年崔建中提出了利用DNA 鏈的濃度來(lái)判斷某種0-1 組合是否為可行解的計(jì)算模型[9]。2019 年，唐震將DNA 鏈置換與圓環(huán)DNA 結(jié)合建立模型用于求解0-1 規(guī)劃問(wèn)題[10]。2020 年楊新木等人利用DNA 折紙術(shù)和雜交鏈?zhǔn)椒磻?yīng)構(gòu)建0-1 背包問(wèn)題的計(jì)算模型[11]。

以上模型從生物計(jì)算的多個(gè)角度為解決0-1背包問(wèn)題提供思路。其中雜交鏈?zhǔn)椒磻?yīng)（Hybridization Chain Reaction，HCR）不需要酶的參與，操作簡(jiǎn)單，易于實(shí)現(xiàn)，是DNA 計(jì)算中常見的生物操作手段。2012 年，Chen 等利用雜交鏈?zhǔn)椒磻?yīng)信號(hào)放大技術(shù)構(gòu)建了超靈敏電致化學(xué)發(fā)光傳感器[12]。2019 年，李朦朦基于雜交鏈?zhǔn)椒磻?yīng)設(shè)計(jì)了3 種DNA 熒光傳感器陣列，分別用于6 種乙肝病毒耐藥基因區(qū)分、4 種RNA 的區(qū)分和5 種單堿基錯(cuò)配基因的區(qū)分[13]。2019 年，崔建中等人設(shè)計(jì)了基于雜交鏈?zhǔn)椒磻?yīng)的0-1 整數(shù)規(guī)劃問(wèn)題計(jì)算模型[14]。2020 年，劉永新等人將雜交鏈?zhǔn)椒磻?yīng)與納米材料結(jié)合實(shí)現(xiàn)了對(duì)核酸檢測(cè)的分析總結(jié)[15]。它的原理如圖1 所示。

圖1 雜交鏈?zhǔn)椒磻?yīng)原理圖

HCR 元件包括兩個(gè)部分：引發(fā)探針，兩條可雜交互補(bǔ)并帶有粘性末端的發(fā)夾型DNA（R1 和R2）。當(dāng)不存在引發(fā)探針時(shí)，兩條發(fā)夾探針?lè)€(wěn)定存在于溶液中。若存在引發(fā)探針時(shí)，HCR 被觸發(fā)，發(fā)夾探針R1 與R2 逐次打開、交替雜交形成一條帶有缺口的DNA 長(zhǎng)鏈，直到發(fā)夾探針R1 或R2至少有一方消耗完為止。每一條這樣的引發(fā)鏈均可以誘發(fā)HCR 的發(fā)生，形成許多的DNA 雙鏈并實(shí)現(xiàn)對(duì)靶標(biāo)檢測(cè)時(shí)的信號(hào)放大。HCR 的優(yōu)點(diǎn)在于不需要酶的輔助，避免了非特異性擴(kuò)增對(duì)分析結(jié)果的影響；反應(yīng)條件溫和、易控制，等溫條件下經(jīng)一步反應(yīng)就可以實(shí)現(xiàn)短鏈DNA 的擴(kuò)增；不需要復(fù)雜的儀器設(shè)備；HCR 這一信號(hào)擴(kuò)增技術(shù)與各類檢測(cè)技術(shù)都具有較高的兼容性。

納米金生物條形碼和表面增強(qiáng)拉曼散射（Surface-Enhanced Raman Scattering，SERS）技術(shù)是近年來(lái)常用的檢測(cè)手段。在生物分子診斷領(lǐng)域，納米金顆粒具備金的所有特質(zhì)，體積更小，比表面積更大，因此常被用于信號(hào)放大工具。2017年，李宗兵結(jié)合雜交鏈?zhǔn)椒磻?yīng)和新型金納米粒子，設(shè)計(jì)了用于檢測(cè)雙螺旋DNA、蛋白質(zhì)和金屬離子的新一代傳感器[16]。2018 年，杜平設(shè)計(jì)了一種高靈敏性的表面增強(qiáng)拉曼生物傳感器用于水樣中銀離子的檢測(cè)[17]。該論文中利用鏈酶親和素和生物素的特異性結(jié)合作用，將帶有拉曼信號(hào)分子的納米金顆粒經(jīng)過(guò)一系列雜交鏈?zhǔn)椒磻?yīng)不斷地結(jié)合到磁球上，進(jìn)行信號(hào)放大，成功實(shí)現(xiàn)溶液中銀離子的高靈敏度和高選擇性檢測(cè)。

生物素-親和素（Biotin-Avidin-System，BAS）具有多級(jí)放大作用，極大地提高了檢測(cè)方法的靈敏度，因此常用于檢測(cè)手段中。大量實(shí)驗(yàn)證明，BAS 幾乎可與目前研究成功的所有標(biāo)記物結(jié)合，應(yīng)用范圍極其廣泛[18-19]。

本文基于雜交鏈?zhǔn)椒磻?yīng)，將發(fā)夾結(jié)構(gòu)的DNA修飾在圓環(huán)DNA 上，設(shè)計(jì)了一個(gè)類閉環(huán)雙鏈DNA模型。利用生物素與鏈酶親和素特異性結(jié)合的生物性質(zhì)，將攜帶有生物素的發(fā)夾結(jié)構(gòu)DNA 與攜帶有鏈酶親和素的納米金顆?；ハ嘟壎?，且在類閉環(huán)雙鏈DNA 上，納米金顆粒的數(shù)量與發(fā)夾結(jié)構(gòu)DNA 的數(shù)量一致。借助SERS 技術(shù)檢測(cè)附著在納米金顆粒上的拉曼信號(hào)，用信號(hào)強(qiáng)度大小等價(jià)表示權(quán)重，進(jìn)而得到符合約束條件的可行解。最后將可行解代入目標(biāo)函數(shù)，求出問(wèn)題的最優(yōu)解。

2 背包問(wèn)題的類閉環(huán)雙鏈DNA

2.1 背包問(wèn)題的數(shù)學(xué)模型

背包問(wèn)題是一種經(jīng)典NP 完全組合優(yōu)化問(wèn)題，以最大化被選中物品的總價(jià)值為求解目標(biāo)。很多實(shí)際優(yōu)化問(wèn)題可以轉(zhuǎn)化為背包問(wèn)題進(jìn)行求解。2010年，孫毅針對(duì)鐵路行包運(yùn)輸組織中操作層上的裝車計(jì)劃問(wèn)題，設(shè)計(jì)了行包裝運(yùn)計(jì)劃改進(jìn)的背包問(wèn)題模型[20]。2017 年，陳烏吉瑪借助混合貪婪算法，設(shè)計(jì)了解決背包個(gè)數(shù)未知的綜合背包問(wèn)題[21]。2018 年，宋世豪系統(tǒng)并詳細(xì)地討論了背包問(wèn)題的三種算法：遺傳算法、動(dòng)態(tài)規(guī)劃法、分枝界限法，從空間復(fù)雜度、時(shí)間復(fù)雜度和正確度等方面進(jìn)行比較，分析了三種算法各自的優(yōu)缺點(diǎn)和適用范圍[22]。2018 年，孫杰凡列舉了解決經(jīng)典背包問(wèn)題的貪心法、動(dòng)態(tài)規(guī)劃和優(yōu)化枚舉三種算法策略的分析過(guò)程，并用C 語(yǔ)言編寫了核心算法[23]。

背包問(wèn)題可描述為：給定一個(gè)背包，其限重為C，給定n種已知重量wi(i=1,2,3...,n)和價(jià)格qi(i=1,2,3...,n)的物品。設(shè)定若選擇第i件物品放入給定的背包，則xi=1；否則，則xi=0(i=1,2,3...,n)。問(wèn)如何選擇物品使背包的總價(jià)最高？即

2.2 生物算法

下面借助類閉環(huán)雙鏈DNA 模型來(lái)討論（1）所對(duì)應(yīng)的背包問(wèn)題的算法。

步驟一：假設(shè)共有n種物品，首先編碼n種寡聚核苷酸片段作為引發(fā)DNA 記為xi，相對(duì)應(yīng)的構(gòu)造2n種發(fā)夾結(jié)構(gòu) DNA 分別記為和(i=1,2,3...,n)。其中xi的黏性末端的堿基序列與的部分堿基序列完全互補(bǔ)，所以當(dāng)xi與相遇時(shí)，的發(fā)夾結(jié)構(gòu)被打開，兩者發(fā)生雜交鏈?zhǔn)椒磻?yīng)，從而將固定在xi上。的發(fā)夾結(jié)構(gòu)被打開后，一端的黏性末端的堿基序列因與xi黏性末端堿基序列完全互補(bǔ)發(fā)生雜交鏈?zhǔn)椒磻?yīng)；而另一段的黏性末端與的部分堿基序列完全互補(bǔ)，所以當(dāng)被打開后的與相遇時(shí)，的發(fā)夾結(jié)構(gòu)會(huì)被打開并與的黏性末端發(fā)生雜交鏈?zhǔn)椒磻?yīng)。如此循環(huán)雜交，直到至少有一種發(fā)夾結(jié)構(gòu)DNA 完全消耗，上述循環(huán)雜交鏈?zhǔn)椒磻?yīng)才會(huì)結(jié)束。設(shè)定發(fā)夾結(jié)構(gòu)DNA 末端攜帶有生物素，則記xi=1；若發(fā)夾結(jié)構(gòu)DNA 末端沒有攜帶生物素，則記xi=0。xi、和之間的循環(huán)雜交鏈?zhǔn)椒磻?yīng)如圖2 所示。其中xi結(jié)合的和總數(shù)表示變量xi的權(quán)重。根據(jù)上述x1,x2,x3,...,xn的堿基序列構(gòu)建所需的圓環(huán)DNA 單鏈，按照順時(shí)針?lè)较蛟O(shè)定的區(qū)域是x1,x2,x3,...,xn的部分補(bǔ)組成的圓環(huán)DNA 單鏈。

圖2 xi、和之間的循環(huán)雜交鏈?zhǔn)椒磻?yīng)

步驟二：把x1,x2,x3,...,xn按照順時(shí)針的順序結(jié)合在一個(gè)圓環(huán)DNA 單鏈上，形成類閉環(huán)雙鏈DNA（如圖3）。在這個(gè)類閉環(huán)雙鏈DNA 上，每條變量ix都保證一端結(jié)合在圓環(huán)DNA 單鏈上，剩余部分暴露在外，為與發(fā)生雜交鏈?zhǔn)椒磻?yīng)做準(zhǔn)備。

圖3 類閉環(huán)雙鏈DNA

n個(gè)變量對(duì)應(yīng)著2n組互異的組合。準(zhǔn)備2n個(gè)試管，向每個(gè)試管中加入構(gòu)建好的類閉環(huán)雙鏈DNA。若變量值為1，則向試管中加入攜帶有生物素的發(fā)夾結(jié)構(gòu)和；若變量值為0，則向試管中加入沒有攜帶生物素的發(fā)夾結(jié)構(gòu)和。約束條件為，ix前的權(quán)重iw決定了加入和的數(shù)量。三者之間的數(shù)量關(guān)系如下所示

wi為奇數(shù)時(shí)，

wi為偶數(shù)時(shí)，

步驟三：處理好所有組合之后，將大量拉曼信號(hào)分子附著在納米金顆粒上，再將鏈酶親和素修飾在納米金顆粒上。向每個(gè)試管中加入適量經(jīng)處理的納米金顆粒，由于生物素-鏈酶親和素的親和性，納米金顆粒就會(huì)結(jié)合在攜帶有生物素即變量值為1 的類閉環(huán)雙鏈DNA 模型上。反應(yīng)充分進(jìn)行后，對(duì)每個(gè)試管中的類閉環(huán)雙鏈DNA 模型用SERS檢測(cè)拉曼信號(hào)。篩選出符合約束條件的可行解。

步驟四：計(jì)算各個(gè)可行解對(duì)應(yīng)的目標(biāo)函數(shù)值并進(jìn)行比較，最大值對(duì)應(yīng)的可行解就是該背包問(wèn)題的最優(yōu)解。

3 實(shí)例分析

現(xiàn)有背包能承重47 kg，有四件物品，對(duì)應(yīng)的重量分別為20 kg、40 kg、30 kg 和10 kg，對(duì)應(yīng)的價(jià)格分別為9 k、10 k、15 k 和8 k（單位：元）。問(wèn)如何挑選，使放入背包的物品總價(jià)值最高。對(duì)應(yīng)的數(shù)學(xué)模型如下：

根據(jù)上面的分析，具體操作如下：

步驟一：共有四個(gè)變量，首先編碼四種寡聚核苷酸片段作為引發(fā)DNA 分別記為x1、x2、x3、x4。相對(duì)應(yīng)地構(gòu)造8 種發(fā)夾結(jié)構(gòu)DNA 分別記為和和和和。設(shè)定，若發(fā)夾結(jié)構(gòu)DNA 末端攜帶有生物素，則記xi=1；若發(fā)夾結(jié)構(gòu)DNA 末端沒有攜帶生物素，則記xi=0（i=1,2,3,4）。按照順時(shí)針?lè)较蛟O(shè)定的區(qū)域是x1,x2,x3,x4的部分補(bǔ)組成的圓環(huán)DNA 單鏈。

步驟二：把x1,x2,x3,x4按照順時(shí)針的順序與圓環(huán)DNA 單鏈上的結(jié)合，形成類閉環(huán)雙鏈DNA，如圖4 所示。

圖4 根據(jù)x1,x2,x3,x4 設(shè)計(jì)的類閉環(huán)雙鏈DNA

接下來(lái)準(zhǔn)備初始數(shù)據(jù)池。4 個(gè)變量意味著有 24共16 組互異的組合，準(zhǔn)備16 個(gè)試管，向每個(gè)試管中加入上述構(gòu)建好的類閉環(huán)雙鏈DNA。本背包問(wèn)題的約束條件為20x+40y+30z+10d≤ 39，由于不等式左邊有公因子10，為了簡(jiǎn)化操作不妨設(shè)以10 為一個(gè)單位，對(duì)左端進(jìn)行放縮。每個(gè)發(fā)夾結(jié)構(gòu)DNA 作為一個(gè)單位來(lái)計(jì)算，則不等式左端簡(jiǎn)化為2x+4y+3z+d。

表1 各個(gè)試管中加入發(fā)夾結(jié)構(gòu)DNA 的數(shù)量

下面以解(1,1,1,1)和解(0,0,1,1)為例具體說(shuō)明。

對(duì)于解(1,1,1,1)，向試管中先加入均攜帶有生物素的1 個(gè)、2 個(gè)、2 個(gè)和1 個(gè)，反應(yīng)一段時(shí)間后再加入同樣均攜帶有生物素的1 個(gè)、2 個(gè)和1 個(gè)。解的合成過(guò)程如圖5 所示。

圖5 解(1,1,1,1)的合成過(guò)程

對(duì)于解(0,0,1,1)，向試管中加入沒有攜帶生物素的1 個(gè)和2 個(gè)，和攜帶有生物素的2個(gè)和1 個(gè)，反應(yīng)一段時(shí)間后再加入沒有攜帶生物素的1 個(gè)、2 個(gè)和修飾有生物素的1 個(gè)。解的合成如圖6 所示。

圖6 解(0,0,1,1)的合成過(guò)程

步驟三：反應(yīng)一段時(shí)間后，向各個(gè)試管中加入適量的修飾有鏈酶親和素且附著有大量拉曼信號(hào)分子的納米金顆粒。待其充分反應(yīng)后，對(duì)每個(gè)試管中的類閉環(huán)雙鏈DNA 用SERS 檢測(cè)拉曼信號(hào)。由于拉曼信號(hào)的大小與生物條形碼顆粒的數(shù)量成正比，為了使結(jié)果更加直觀，通過(guò)生物條形碼的數(shù)量來(lái)間接表示拉曼信號(hào)的相對(duì)大小。計(jì)算出每個(gè)解中類閉環(huán)雙鏈DNA 上結(jié)合的生物條形碼的總數(shù)，根據(jù)對(duì)原約束條件的變形，相應(yīng)的將生物條形碼的總數(shù)擴(kuò)大十倍，判斷結(jié)果是否符合約束條件。在圖5 中，解(1,1,1,1)共結(jié)合了10 個(gè)生物條形碼，將10 擴(kuò)大十倍，所以解(1,1,1,1)的檢測(cè)結(jié)果為100。在圖6 中，解(0,0,1,1)共結(jié)合了4 個(gè)生物條形碼，將4 擴(kuò)大十倍，所以解(0,0,1,1)的檢測(cè)結(jié)果為40。所有可能解的檢測(cè)結(jié)果如表2 所示。

表2 各個(gè)可能解的檢測(cè)結(jié)果

步驟四：根據(jù)目標(biāo)函數(shù)，計(jì)算所有可行解的目標(biāo)值，得到最大值為23，對(duì)應(yīng)的最優(yōu)解(0,0,1,1)。

4 模型分析

我們將從空間復(fù)雜度和時(shí)間復(fù)雜度對(duì)模型的計(jì)算復(fù)雜度進(jìn)行分析。其中空間復(fù)雜度參照Yuriy Brun 在文獻(xiàn)中指出的自組裝模型復(fù)雜度計(jì)算理論[24]，就此模型中參與計(jì)算的分子結(jié)構(gòu)的種類進(jìn)行討論。在實(shí)例中，需要圓環(huán)DNA 1 種，啟動(dòng)DNA 4 種（1 倍的變量個(gè)數(shù)），發(fā)夾DNA 8 種（2 倍的變量個(gè)數(shù)），生物素1 種，因此在參與計(jì)算的分子結(jié)構(gòu)種類上為 Θ (3n+1)（n為變量的個(gè)數(shù)）。在時(shí)間復(fù)雜度上，與背包問(wèn)題所含變量個(gè)數(shù)相關(guān)，在上述實(shí)例中，變量的個(gè)數(shù)為4，那么所有組合的個(gè)數(shù)為24個(gè)，逐次判定即可。隨著變量個(gè)數(shù)的增加，判定次數(shù)也在增加。

5 結(jié)論

利用發(fā)夾結(jié)構(gòu)的循環(huán)雜交鏈?zhǔn)椒磻?yīng)的放大作用和圓環(huán)結(jié)構(gòu)的穩(wěn)定性，借助表面增強(qiáng)拉曼散射技術(shù)，設(shè)計(jì)了一種類閉環(huán)雙鏈DNA 模型，用于求解0-1 背包問(wèn)題。圓環(huán)結(jié)構(gòu)雖然穩(wěn)定，但由于其上DNA 空間位阻的限制無(wú)法解決更多變量的背包問(wèn)題，需要進(jìn)一步研究、改進(jìn)。