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

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

（1.安徽理工大學 數學與大數據學院，安徽 淮南 232001；2.上海工程技術大學 數理與統計學院，上海 201620）

1 引言

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

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

圖1 雜交鏈式反應原理圖

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

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

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

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

2 背包問題的類閉環雙鏈DNA

2.1 背包問題的數學模型

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

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

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

圖2 xi、和之間的循環雜交鏈式反應

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

圖3 類閉環雙鏈DNA

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

wi為奇數時，

wi為偶數時，

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

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

3 實例分析

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

根據上面的分析，具體操作如下：

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

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

圖4 根據x1,x2,x3,x4 設計的類閉環雙鏈DNA

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

表1 各個試管中加入發夾結構DNA 的數量

下面以解(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)的合成過程

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

表2 各個可能解的檢測結果

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

4 模型分析

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

5 結論

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