朱建鵬，殷志祥

(安徽理工大學(xué)理學(xué)院，安徽 淮南 232001)

?

DNA芯片一類特殊0-1規(guī)劃問(wèn)題的計(jì)算模型

朱建鵬，殷志祥

(安徽理工大學(xué)理學(xué)院，安徽 淮南 232001)

作為整數(shù)規(guī)劃問(wèn)題的特殊情形，0-1規(guī)劃問(wèn)題是運(yùn)籌學(xué)中應(yīng)用廣泛的問(wèn)題之一，具有極大的研究?jī)r(jià)值。生物芯片技術(shù)與DNA計(jì)算相結(jié)合的產(chǎn)物DNA芯片在DNA計(jì)算模型中有著獨(dú)特的優(yōu)勢(shì)。基于DNA芯片和DNA計(jì)算，針對(duì)一類特殊的0-1規(guī)劃問(wèn)題提出了DNA計(jì)算模型。該模型易實(shí)現(xiàn)操作過(guò)程自動(dòng)化，具有操作簡(jiǎn)單、高信息量的優(yōu)點(diǎn)。

整數(shù)規(guī)劃問(wèn)題；0-1規(guī)劃問(wèn)題；DNA計(jì)算；DNA芯片

自從Adleman博士以DNA序列為載體，利用分子生物學(xué)技術(shù)解決了有向Hamilton問(wèn)題[1]以來(lái)，DNA計(jì)算成為新的研究領(lǐng)域，憑借其高度并行性、高存儲(chǔ)、低耗能等優(yōu)勢(shì)而備受關(guān)注。1995年，文獻(xiàn)[2]在Adleman的試驗(yàn)基礎(chǔ)上，通過(guò)構(gòu)造接觸網(wǎng)絡(luò)圖G解決了SAT問(wèn)題，文獻(xiàn)[3]提出了利用質(zhì)粒DNA分子來(lái)解決SAT問(wèn)題，隨后解決了最大獨(dú)立集問(wèn)題，文獻(xiàn)[4]描述了一種基于自裝配單鏈核酸鏈網(wǎng)絡(luò)的空間圖靈機(jī)。2000年，Sakamoto等利用DNA自組裝形成的發(fā)夾結(jié)構(gòu)解決了3-SAT問(wèn)題。2001年，Benenson基于分子生物的可編程和自治計(jì)算機(jī)器的研究，開發(fā)了半自動(dòng)化試管型DNA計(jì)算機(jī)。次年，文獻(xiàn)[5]給出并基于半自動(dòng)化自組裝DNA計(jì)算模型解決了含20個(gè)變?cè)?-SAT問(wèn)題。

作為整數(shù)規(guī)劃的特殊形式，0-1規(guī)劃問(wèn)題是運(yùn)籌學(xué)中的一個(gè)重要問(wèn)題，具有廣泛應(yīng)用，如指派問(wèn)題、選地問(wèn)題等均可歸為此類規(guī)劃。解決該問(wèn)題的算法很多，如窮舉法，隱枚舉法，分支定界法等，但目前為止還沒(méi)有好的算法來(lái)完全解決該問(wèn)題。2003年，Yin首次給出了一種基于熒光標(biāo)記的方法，利用DNA計(jì)算解決了一類特殊0-1規(guī)劃問(wèn)題[6]，即指派問(wèn)題的推廣。文獻(xiàn)[7]412-415等采用DNA芯片技術(shù)解決了簡(jiǎn)單0-1規(guī)劃問(wèn)題，文獻(xiàn)[8]基于DNA芯片計(jì)算模型解決了組合數(shù)學(xué)中一類經(jīng)典問(wèn)題——全錯(cuò)位排列問(wèn)題。隨后，有不少學(xué)者對(duì)于其他類型的0-1規(guī)劃問(wèn)題，先后提出了相應(yīng)的DNA計(jì)算模型[9-10]。

生物芯片在DNA計(jì)算領(lǐng)域的應(yīng)用及其顯著優(yōu)點(diǎn)表明DNA芯片技術(shù)有望成為新型生物計(jì)算的芯片，在一定程度上彌補(bǔ)了以前DNA計(jì)算模型的不足。本文基于DNA芯片，利用熒光標(biāo)記對(duì)一類特殊0-1規(guī)劃問(wèn)題提出了新的計(jì)算模型。該模型易實(shí)現(xiàn)操作過(guò)程自動(dòng)化，具有操作簡(jiǎn)單、高信息量的優(yōu)點(diǎn)。

1 一類特殊0-1規(guī)劃問(wèn)題的形式轉(zhuǎn)換

0-1規(guī)劃問(wèn)題是整數(shù)規(guī)劃問(wèn)題的特殊情形，其變量?jī)H取值0或1。其一般形式如下

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

(1)

(2)

基于DNA計(jì)算，本文給出上式(2)中aij=-1、 0 或 1，bi為任意整數(shù)時(shí)的0-1規(guī)劃問(wèn)題的一種新的求解算法。對(duì)(2)中的任意約束方程，若bi≤0，則可通過(guò)對(duì)方程兩邊同時(shí)乘以-1使得bi≥0。故我們假定bi≥0，i=1，2，…，m。

對(duì)于(2)中任意約束方程

ai1x1+ai2x2+…+ainxn≤(=，≥)bi

(3)

(4)

(5)

進(jìn)而實(shí)現(xiàn)對(duì)(2)的變形，得到如下方程組

(6)

為便于理解，下面以具體的例子來(lái)解釋和描述上述變形過(guò)程

min u=2x+3y-z

(7)

(8)

同理，第二個(gè)約束方程y-x≤0變?yōu)閤′+y≤1；第三個(gè)約束方程x+y-z≥1變?yōu)閤+y+z′≥2。于是，方程組(8)變形為

(9)

綜上所述，對(duì)于式(2)中aij=-1、0或1，bi為任意整數(shù)的特殊0-1規(guī)劃問(wèn)題，可利用上述方法變形為0-1規(guī)劃問(wèn)題的一般形式。此形式轉(zhuǎn)換的方法是新算法得以實(shí)施的前提與基礎(chǔ)。

2 計(jì)算模型

2.1 基本算法

對(duì)于一個(gè)含有n個(gè)變量x1，x2，…，xn和m個(gè)方程的方程組，其算法的步驟如下：

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

步驟2 利用每一約束方程篩選可行解；

步驟3 生成剩余解；

步驟4 對(duì)步驟2、3重復(fù)(m-1)次，即可得到問(wèn)題的所有可行解；

步驟5 比較各可行解對(duì)應(yīng)的目標(biāo)函數(shù)值，最終得到最優(yōu)解。

2.2 生物算法

步驟1 制作代表給定問(wèn)題的變量的DNA鏈及其補(bǔ)鏈；

步驟2 根據(jù)堿基互補(bǔ)配對(duì)原則，將DNA鏈雜交，獲得代表給定問(wèn)題的變量取值為0或1的所有組合解的DNA數(shù)據(jù)庫(kù)；

步驟3 用一定的生物方法對(duì)結(jié)果標(biāo)記，使其可以檢測(cè)到判斷滿足某約束條件的組合；

步驟4 根據(jù)約束方程篩選出所有滿足該方程的組合；

步驟5 重復(fù)步驟4，篩選出所有滿足各約束方程的組合，從而確定給定問(wèn)題的所有可行解；

步驟6 求出各可行解對(duì)應(yīng)的目標(biāo)函數(shù)值，比較大小確定最優(yōu)解。

基本思想：將0-1規(guī)劃問(wèn)題的變量映射為DNA鏈，將其按特定的排列方式固定在可尋址的DNA芯片上。通過(guò)加入代表變量的DNA鏈的互補(bǔ)鏈，DNA分子按照堿基互補(bǔ)配對(duì)原則雜交，生成給定問(wèn)題的變量取值為0或1的所有解。在一定條件下進(jìn)行反應(yīng)，通過(guò)熒光掃描儀掃描反應(yīng)標(biāo)記結(jié)果及計(jì)算機(jī)分析可得到最優(yōu)解。

2.3 編碼及操作

步驟1 分為兩步：

步驟2 將一定量的第三、四、五、六組的DNA鏈與步驟1表面的DNA矩陣在嚴(yán)格條件下雜交，形成包含該問(wèn)題所有可能解的DNA數(shù)據(jù)庫(kù)。雜交后在適當(dāng)條件下用緩沖液清洗掉未雜交上的DNA鏈。

步驟3 由于步驟1中已經(jīng)對(duì)第四、六組DNA鏈進(jìn)行了熒光標(biāo)記，所以若某DNA鏈發(fā)出熒光，則表示其對(duì)應(yīng)的變量取值為1，否則取值為0。據(jù)此可在步驟4中找出可行解。

步驟4 利用激光共聚焦顯微鏡獲取反應(yīng)后DNA矩陣的圖像信息并進(jìn)行分析，保留滿足約束方程的可行解。

步驟5 重復(fù)步驟4 (由于對(duì)DNA矩陣雜交后圖像信息的一次獲取即可對(duì)所有約束方程進(jìn)行分析，故沒(méi)必要再次獲取圖像信息)，篩選滿足約束方程的可行解。

步驟6 計(jì)算各可行解所對(duì)應(yīng)的目標(biāo)函數(shù)值，經(jīng)過(guò)比較找到問(wèn)題的最優(yōu)解。

現(xiàn)實(shí)性分析：由于DNA分子數(shù)量和種類的無(wú)窮性，合成2n種有較大差異的短的寡聚核苷酸是易實(shí)現(xiàn)的，因此可用ABI 392合成儀合成所需的不同的DNA鏈。其次，現(xiàn)有的熒光劑種類繁多，如二苯乙烯型、香豆素型等，而本算法中不論變量數(shù)n為何值，只需一種熒光劑即可。最后，DNA芯片技術(shù)有了重大進(jìn)展，制備可尋址的DNA芯片也是可以實(shí)現(xiàn)的。然后利用激光共聚焦顯微鏡獲取反應(yīng)后DNA矩陣的圖像信息并進(jìn)行分析，保留滿足約束方程的可行解即可。

3 算法實(shí)例分析

下面以一個(gè)簡(jiǎn)單的特殊0-1規(guī)劃問(wèn)題為例對(duì)算法加以分析

min u=2x+3y-z

(7)

(8)

令x=1-x′，y=1-y′，z=1-z′，則(8)式變?yōu)?/p>

(9)

步驟1 分為兩步：

x:AACCTG-GT;y:ACCAT-AGG;z:AGAGTCTCx':TTTAGC-CG;y':TATTCG-GC;z':AAACTTTGx:TTGGAC-CA;y:TGG-TATCG;z:TCTCAGAGx':TTGGAC-CA;y':TGG-TATCG;z':TCTCAGAGx^:AAATCG-GC;y^:ATAAGCCG;z^:TTTGAAACx^':AAATCG-GC;y^':ATAAGC-CG;z^':TTTGAAAC

圖1 各個(gè)變量的寡聚核苷酸編碼示意圖

② 將第一、二組的DNA片段的5′端進(jìn)行巰基修飾，從上到下按照x，x′，y，y′，z，z′的順序固定在芯片表面，重復(fù)排列為DNA矩陣，點(diǎn)樣組數(shù)大于8(見圖2)。

圖2 芯片點(diǎn)樣矩陣

步驟2 將第四、六組的DNA片段的5′端進(jìn)行熒光標(biāo)記，標(biāo)記物為熒光黃(FAM)。將一定量的第三、四、五、六組的DNA鏈混合均勻，在合適的條件下(如42℃，6h)與DNA芯片矩陣雜交，產(chǎn)生滿足給定問(wèn)題的所有可能解。充分反應(yīng)后在嚴(yán)格條件下用緩沖液清洗掉未雜交上的DNA鏈(見圖3，填充部分表示發(fā)光)。

圖3 雜交后的所有可行解

步驟4 利用激光共聚焦顯微鏡觀察反應(yīng)后的DNA芯片，記錄并分析結(jié)果。對(duì)于第一個(gè)約束方程x+y′+z≥2，只需觀察變量x、y′、z所在的第1、4、5行對(duì)應(yīng)的各列發(fā)光情況即可。顯然，變量x、y′、z之和不少于2，即與x、y′、z雜交發(fā)出的熒光數(shù)目之和不少于2的列滿足該方程，即第1、3、4、7列為該方程的可行解。

步驟5 重復(fù)步驟4，由圖3不難得出以下結(jié)論：對(duì)于第二個(gè)約束方程x′+y≤1， 第1、 2、 3、 4、7、8列為該方程的可行解； 對(duì)于第三個(gè)約束方程x+y+z′≥2，第1、2、4、6列為該方程的可行解。從而滿足約束方程組的可行解為第1、4列，即對(duì)應(yīng)的編碼變量組合分別為(1，1，1，)、(1，0，0)。

步驟6 計(jì)算得到可行解(1，1，1，)、(1，0，0)對(duì)應(yīng)的目標(biāo)函數(shù)值分別為4、0，因此，目標(biāo)函數(shù)的最優(yōu)解為(1，0，0)，其最小值為2。

4 結(jié)論

本文對(duì)一類特殊0-1規(guī)劃問(wèn)題給出了DNA計(jì)算模型，通過(guò)變量替換使得所有變量的系數(shù)變?yōu)?或1，轉(zhuǎn)化為簡(jiǎn)單的0-1規(guī)劃問(wèn)題。該模型將問(wèn)題的變量映射為寡聚核苷酸鏈，采用DNA芯片技術(shù)制作可尋址的DNA變量矩陣。DNA片段遵循堿基互補(bǔ)配對(duì)原則進(jìn)行雜交，生成給定問(wèn)題的DNA數(shù)據(jù)庫(kù)，利用激光共聚焦顯微鏡觀察雜交矩陣上的熒光信息來(lái)篩選可行解，最終求出最優(yōu)解。該模型展示了DNA芯片在DNA計(jì)算領(lǐng)域的獨(dú)特優(yōu)勢(shì)，操作簡(jiǎn)單可行，并行性高，能夠有效避免實(shí)驗(yàn)操作及人為因素對(duì)計(jì)算結(jié)果造成的誤差，使計(jì)算過(guò)程的自動(dòng)化成為可能，大大提高了計(jì)算效率和可行解的準(zhǔn)確性。隨著分子生物技術(shù)和DNA技術(shù)的進(jìn)一步結(jié)合與發(fā)展，DNA芯片的應(yīng)用將更加廣泛，其研究?jī)r(jià)值與日俱增。相信未來(lái)DNA芯片技術(shù)的逐漸成熟，將對(duì)DNA計(jì)算領(lǐng)域產(chǎn)生積極的影響。

[1] ADLEMAN L M.Moleeular Computation of Solutions to Combinatorial Problems[J]. Seienee， 1994(266)： 1 021-1 024.

[2] LIPTON，R J.DNA Solution of Hard Computation Problem.Seienee，1995(268)：583-585.

[3] HEAD T，ROZENBERG G，BLADERGROEN R S，et al.Computing with DNA by Operating on Plasmids[J]. Biosystems，2000，57：87-93.

[4] ROWEIS S， WINFREE E， BURGOYNE R， et al. A Stieker-based Model for DNA Computation[J]. Comput.Biol.，1998，5(4)：615-629.

[5] BRAIEH R S.Solution of a 20-variable 3-SAT Problem on a DNA computer[J].Scienee，296：499-502.

[6] 殷志祥，張鳳月，許進(jìn).0-1規(guī)劃問(wèn)題的DNA計(jì)算模型[J].電子與信息學(xué)報(bào)，2003，25(1)：62-66.

[7] 張鳳月，殷志祥，許進(jìn). DNA芯片在0-1規(guī)劃問(wèn)題中的應(yīng)用[J]. 生物化學(xué)與生物物理進(jìn)展. 2003，30(3)：412-415.

[8] 孫俠，殷志祥，李勇，等. 全錯(cuò)位排列問(wèn)題的基于芯片的DNA計(jì)算模型[J]. 大學(xué)數(shù)學(xué)， 2010，26(5)：79-82.

[9] 王雷，林亞平，李智勇. 一類特殊整數(shù)規(guī)劃問(wèn)題的DNA計(jì)算[J]. 計(jì)算機(jī)研究與發(fā)展，2005，42(8)： 1 431-1 437.

[10] 殷志祥，石曉龍，徐濤，等.0-1整數(shù)規(guī)劃問(wèn)題的半自動(dòng)DNA計(jì)算模型[J].生物信息學(xué)，2006，4(3)：113-116.

[11] 王雷，林亞平. DNA計(jì)算在整數(shù)規(guī)劃問(wèn)題中的應(yīng)用[J]. 計(jì)算機(jī)研究與發(fā)展，2005，27(5)：814-818.

[12] 胡宇舟，王雷，顧學(xué)道. 有界整數(shù)規(guī)劃問(wèn)題的DNA計(jì)算[J]. 計(jì)算機(jī)應(yīng)用，2008，28(z1)： 18-24.

[13] 楊靜，殷志祥. 基于抗原中介三鏈DNA結(jié)構(gòu)的0-1整數(shù)規(guī)劃[J]. 計(jì)算機(jī)工程與應(yīng)用， 2008，44(2)：76-79.

[14] 任曉玲，白雪，劉希玉. 基于三鏈DNA結(jié)構(gòu)的0-1整數(shù)規(guī)劃改進(jìn)研究[J]. 計(jì)算機(jī)應(yīng)用研究， 2013，30(1)：56-59.

[15] 殷志祥，許進(jìn).分子信標(biāo)芯片計(jì)算在0-1整數(shù)規(guī)劃問(wèn)題中的應(yīng)用[J].生物數(shù)學(xué)學(xué)報(bào)，2007，22(3)：559-564.[16] 池曉菲，舒慶堯. 生物芯片技術(shù)的原理與應(yīng)用[J]. 專論與綜述， 2001，23(4)：370-374.

[17] 張旭，楊承，黃成軍，等. 主動(dòng)式生物芯片技術(shù)[J]. 微電子學(xué)， 2003，33(4)：324-327.

[18] 殷志祥. 圖與組合優(yōu)化中的DNA計(jì)算模型[M]. 北京：科學(xué)出版社， 2004.

[19] 周金鳳. DNA計(jì)算在求解NP-完全問(wèn)題的應(yīng)用[J]. 科技視界，2012，2(35)：236-238.

[20] 李肯立，羅興，吳帆，等. 基于自組裝模型的最大團(tuán)問(wèn)題DNA計(jì)算算法[J]. 計(jì)算機(jī)研究與發(fā)展，2013，50(3)： 666-675.

[21] 周炎濤，李肯立，羅興，等. 一種基于DNA自組裝模型求解最大團(tuán)問(wèn)題的算法[J]. 湖南大學(xué)學(xué)報(bào)(自然科學(xué)版)， 2012，39(9)： 39-44.

(責(zé)任編輯：李 麗)

Computing Model Based on DNA Chip for Category of Special 0-1 Planning Problem

ZHU Jian-peng，YIN Zhi-xiang

(School of Science， Anhui University of Science and Technology， Huainan Anhui 232001，China)

As a special situation of integer planning problem，0-1 planning problem is widely applied in operational research and has great research value. DNA chip，a product of the combination of bio-chip technology and DNA computing，has unique advantage in the DNA computing. On the basis of the DNA chip and DNA computing，a new DNA computing model is proposed to solve a category of special 0-1 planning problem. The model is easy to realize the automatic operation process，and possesses the advantages of simple operation and high amount of information.

integer planning problem；0-1 planning problem；DNA computing；DNA chip

2016-04-13

國(guó)家自然科學(xué)基金資助項(xiàng)目(61170172)

朱建鵬(1991-)，男，河南新密人，在讀碩士，研究方向：圖論與DNA計(jì)算。

TP301

A

1672-1098(2016)05-0025-05