朱建鵬，殷志祥

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

?

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

朱建鵬，殷志祥

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

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

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

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

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

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

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

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

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

(1)

(2)

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

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

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

(3)

(4)

(5)

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

(6)

為便于理解，下面以具體的例子來解釋和描述上述變形過程

min u=2x+3y-z

(7)

(8)

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

(9)

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

2 計算模型

2.1 基本算法

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

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

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

步驟3 生成剩余解；

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

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

2.2 生物算法

步驟1 制作代表給定問題的變量的DNA鏈及其補鏈；

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

步驟3 用一定的生物方法對結果標記，使其可以檢測到判斷滿足某約束條件的組合；

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

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

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

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

2.3 編碼及操作

步驟1 分為兩步：

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

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

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

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

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

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

3 算法實例分析

下面以一個簡單的特殊0-1規(guī)劃問題為例對算法加以分析

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 各個變量的寡聚核苷酸編碼示意圖

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

圖2 芯片點樣矩陣

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

圖3 雜交后的所有可行解

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

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

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

4 結論

本文對一類特殊0-1規(guī)劃問題給出了DNA計算模型，通過變量替換使得所有變量的系數(shù)變?yōu)?或1，轉(zhuǎn)化為簡單的0-1規(guī)劃問題。該模型將問題的變量映射為寡聚核苷酸鏈，采用DNA芯片技術制作可尋址的DNA變量矩陣。DNA片段遵循堿基互補配對原則進行雜交，生成給定問題的DNA數(shù)據(jù)庫，利用激光共聚焦顯微鏡觀察雜交矩陣上的熒光信息來篩選可行解，最終求出最優(yōu)解。該模型展示了DNA芯片在DNA計算領域的獨特優(yōu)勢，操作簡單可行，并行性高，能夠有效避免實驗操作及人為因素對計算結果造成的誤差，使計算過程的自動化成為可能，大大提高了計算效率和可行解的準確性。隨著分子生物技術和DNA技術的進一步結合與發(fā)展，DNA芯片的應用將更加廣泛，其研究價值與日俱增。相信未來DNA芯片技術的逐漸成熟，將對DNA計算領域產(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] 殷志祥，張鳳月，許進.0-1規(guī)劃問題的DNA計算模型[J].電子與信息學報，2003，25(1)：62-66.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(責任編輯：李 麗)

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

國家自然科學基金資助項目(61170172)

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

TP301

A

1672-1098(2016)05-0025-05