0-1整數(shù)規(guī)劃問題的巨磁電阻型DNA計(jì)算模型

殷志祥，楊珍琴

(安徽理工大學(xué)數(shù)學(xué)與大數(shù)據(jù)學(xué)院，安徽 淮南 232001)

1994年文獻(xiàn)[1]利用DNA編碼解決了Hamilton路徑問題，也是首次分子生物學(xué)工具應(yīng)用于NP完全問題；文獻(xiàn)[2]利用接觸網(wǎng)絡(luò)G解決了SAT問題，與傳統(tǒng)的電子計(jì)算機(jī)相比，具有更快的速度；文獻(xiàn)[3]提出DNA表面計(jì)算，這種方法的優(yōu)點(diǎn)是其可擴(kuò)展性和潛在的自動(dòng)化，為DNA計(jì)算的進(jìn)一步研究做了鋪墊；文獻(xiàn)[4]對DNA表面計(jì)算的SAT問題進(jìn)行了改進(jìn)，具有成本低，操作時(shí)間短，可重復(fù)使用的表面和簡單的實(shí)驗(yàn)步驟等優(yōu)點(diǎn)；文獻(xiàn)[5]利用三螺旋結(jié)構(gòu)的DNA鏈，來解決0-1整數(shù)規(guī)劃問題，從而對于一般整數(shù)規(guī)劃和可滿足性問題都可轉(zhuǎn)化為0-1整數(shù)規(guī)劃，利用三鏈DNA計(jì)算模型來解決；文獻(xiàn)[6] 嘗試將DNA計(jì)算應(yīng)用于編程問題，利用基于表面的熒光標(biāo)記技術(shù)解決了0-1規(guī)劃問題的一般形式，具有編碼簡單，成本低，工作時(shí)間短等優(yōu)點(diǎn)；文獻(xiàn)[7] 基于微流體系統(tǒng)，提出了一種解決特殊0-1整數(shù)規(guī)劃的DNA算法；文獻(xiàn)[8]使用金納米顆粒解決0-1規(guī)劃問題；隨后提出不同的DNA計(jì)算模型，解決了各類NP完全問題[9-13]。直到發(fā)現(xiàn)巨磁電阻傳感器， 利用巨磁電阻解決了可滿足性問題；文獻(xiàn)[14]共同發(fā)現(xiàn)了一種超快速GMR型電阻材料-磷化鈮，使巨磁電阻具有更大的應(yīng)用前景。0-1規(guī)劃問題與SAT(可滿足性)問題是密切相關(guān)的[15-20]，是可滿足性問題的推廣。但DNA計(jì)算模型在求解NP完全問題時(shí)也存在所需的核苷酸分子數(shù)是指數(shù)的增加。

目前大多學(xué)者利用熒光標(biāo)記雜交物，則對光信號檢測設(shè)備要求高，使得信號分析變得困難。本文利用GMR型DNA芯片技術(shù)求解0-1整數(shù)規(guī)劃問題，通過電信號方式輸出，避免了熒光分析中的信號轉(zhuǎn)換而引起的失真。

1 GMR型DNA芯片與0-1整數(shù)規(guī)劃問題

1.1 GMR型DNA芯片

GMR型DNA芯片核心部分是使用大規(guī)模集成電路的微細(xì)加工技術(shù)，其檢測步驟[22](見圖1)如下：

第1步 把GMR傳感器集成在一塊基片上，為了避免分析過程中的溶液對芯片的腐蝕，在芯片表面覆蓋一層保護(hù)層，在GMR型芯片表面固定DNA探針，然后將被生物素標(biāo)記的待分析目標(biāo)DNA鏈與探針進(jìn)行充分雜交；

第2步 清洗未雜交的DNA鏈，將被抗生物素標(biāo)識的納米磁珠與DNA鏈鍵聯(lián)，使抗生素一生物素結(jié)合，選擇性的捕獲磁性標(biāo)記；利用磁分離器分離未參與標(biāo)記的磁珠，通過芯片上的GMR傳感器對芯片上納米磁珠的檢測，分析產(chǎn)生的信號強(qiáng)度、位置等信息。

圖1 兩步標(biāo)記法示意圖

1.2 0-1整數(shù)規(guī)劃問題

0-1整數(shù)規(guī)劃是整數(shù)規(guī)劃的特殊情形，其變量xi僅取0或1，這時(shí)xi稱為二進(jìn)制變量，或0-1變量(如果xi不是僅取0或1，而是其它的非負(fù)整數(shù)，則可用二進(jìn)制記數(shù)法將其用若干個(gè)0-1變量來替代)。0-1規(guī)劃在整數(shù)規(guī)劃中占有重要地位，一方面因?yàn)樵S多實(shí)際問題，例如指派問題、選地問題、送貨問題都可歸結(jié)為此類規(guī)劃，另一方面任何有界變量的整數(shù)規(guī)劃都與0-1規(guī)劃等價(jià)，用0-1規(guī)劃方法還可以把多種非線性規(guī)劃問題表示成整數(shù)規(guī)劃問題，一般形式為

max(min)z=c1x1+c2x2+…+cnxn

特殊形式為

max(min)z=c1x1+c2x2+…+cnxn

(*)

2 計(jì)算模型

2.1 基本算法

下面給出(*)對應(yīng)的0-1整數(shù)規(guī)劃問題算法步驟：

步驟1 生成給定問題的變量取值為0或1的所有可能組合；

步驟2 利用每一約束條件剔除非解；

步驟3 生成剩余的解；

步驟4 重復(fù)進(jìn)行步驟2，3。排除所有的非解，得到問題的所有可行解；

步驟5 比較各可行解對應(yīng)的目標(biāo)函數(shù)值，得到最優(yōu)解。程序框圖如圖2所示。

圖2 0-1整數(shù)規(guī)劃問題的DNA計(jì)算模型步驟圖

2.2 生物算法

對于n個(gè)變量x1，x2，…，xn，m個(gè)約束條件的0-1整數(shù)規(guī)劃問題，其GMR型DNA芯片計(jì)算的算法步驟如下：

步驟1 合成代表變量的DNA序列。首先合成3n種短的寡聚核苷酸片段，并分成3組：

1)第一組中n種DNA片段被表示為變量x1，x2，…，xn；

步驟2 合成0-1整數(shù)規(guī)劃問題的所有可能解數(shù)據(jù)庫。利用T4連接酶連接3n種寡聚核苷酸片段，構(gòu)造出2n種DNA鏈，對每條DNA鏈的5′端用巰基修飾，并固定在GMR型DNA芯片表面上；

步驟3 將代表第k(k

步驟4將被生物素標(biāo)識的磁珠加到GMR型芯片上充分反應(yīng)后，利用磁分離器分離未參與標(biāo)記的磁珠，在生物素一抗生素共價(jià)鍵的作用下，選擇性的捕獲磁性標(biāo)記；

步驟5 若k=m，則停止算法程序，輸出0-1整數(shù)規(guī)劃問題的所有可能解；反之，令k=k+1轉(zhuǎn)到步驟2。

3 GMR型DNA芯片模型實(shí)例

現(xiàn)舉例描述0-1整數(shù)規(guī)劃問題的GMR型DNA計(jì)算模型。

minS=2x+3y+2z

表1 DNA編碼

利用T4連接酶連接6種短的寡聚核苷酸片段以合成8種不同的DNA鏈，對每條DNA鏈的5′端用巰基修飾，并固定在GMR型DNA芯片表面上，如圖3所示。

圖3 表面固定圖

步驟2 根據(jù)第一個(gè)約束條件，在表面加入核苷酸x，y，z對應(yīng)的補(bǔ)鏈x′，y′，z′進(jìn)行雜交，并用緩沖液清洗掉未雜交的核苷酸序列，加入納米磁珠進(jìn)行磁性標(biāo)記，利用磁分離器分離未參與標(biāo)記的磁珠，記錄電阻的變化。對于本問題，只有位置8電阻未發(fā)生任何變化，后面不考慮位置8。加熱表面解開雙鏈，并沖洗去掉磁珠。(滿足該約束條件的為1，2，3，4，見圖4)

圖4 對應(yīng)第一個(gè)約束條件反應(yīng)示意圖

步驟3 根據(jù)第二個(gè)約束條件，在表面加入核苷酸x，z對應(yīng)的補(bǔ)鏈x′，z′進(jìn)行雜交，并用緩沖液清洗掉未雜交的核苷酸序列，加入納米磁珠進(jìn)行磁性標(biāo)記，利用磁分離器分離未參與標(biāo)記的磁珠，記錄電阻的變化。加熱表面解開雙鏈，并沖洗去掉磁珠。(滿足該約束條件的為2，4，5，7，見圖5)

圖5 對應(yīng)第二個(gè)約束條件反應(yīng)示意圖

步驟4 根據(jù)第三個(gè)約束條件，在表面加入核苷酸y，z對應(yīng)的補(bǔ)鏈y′，z′進(jìn)行雜交，并用緩沖液清洗掉未雜交的核苷酸序列，加入納米磁珠進(jìn)行磁性標(biāo)記，利用磁分離器分離未參與標(biāo)記的磁珠，記錄電阻的變化。加熱表面解開雙鏈，并沖洗去掉磁珠。(滿足該約束條件的為2，3，6，7，見圖6)

圖6 對應(yīng)第三個(gè)約束條件反應(yīng)示意圖

步驟5 記錄滿足約束方程的所有可行解，求出最優(yōu)解。對于本問題，可行解是2，對應(yīng)的編碼變量值為(1，1，0)也是最優(yōu)解，目標(biāo)函數(shù)最小值為5。

4 結(jié)論

(1)結(jié)果輸出方式不同。傳統(tǒng)計(jì)算模型是以DNA鏈作為輸出結(jié)果，本文的計(jì)算模型的輸出結(jié)果是電信號，因此具有較好的靈敏度。

(2)檢測方式不同。該模型將目標(biāo)DNA鏈與GMR型芯片表面固定的DNA探針雜交，通過GMR傳感器檢測，因此具有信號檢測簡單，結(jié)果分析便捷等優(yōu)勢。

(3)嘗試了將GMR型DNA芯片技術(shù)應(yīng)用于DNA計(jì)算中，這是對現(xiàn)階段DAN計(jì)算的一種探索。隨著GMR型DNA計(jì)算模型研究的不斷深入，該模型將具有解決更多NP完全問題將的能力。