求解0-1 背包問題的類閉環(huán)雙鏈DNA 計算模型

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

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

1 引言

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

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

圖1 雜交鏈式反應原理圖

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

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

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

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

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

2.1 背包問題的數(shù)學模型

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

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

2.2 生物算法

下面借助類閉環(huán)雙鏈DNA 模型來討論（1）所對應的背包問題的算法。

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

圖2 xi、和之間的循環(huán)雜交鏈式反應

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

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

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

wi為奇數(shù)時，

wi為偶數(shù)時，

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

步驟四：計算各個可行解對應的目標函數(shù)值并進行比較，最大值對應的可行解就是該背包問題的最優(yōu)解。

3 實例分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 模型分析

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

5 結(jié)論

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