特殊0-1整數(shù)規(guī)劃問題的DNA芯片模型研究.pdf

1、自從Adleman博士將DNA序列信息和分子生物學(xué)技術(shù)相結(jié)合解決了有向Hamilton路徑問題[1]以來，DNA計算為生物計算開辟了一片新天地，并且憑借其高度并行性、高存儲、低耗能等優(yōu)勢而備受專家學(xué)者關(guān)注。隨后，不少研究人員將DNA計算與遺傳算法、模糊系統(tǒng)、神經(jīng)網(wǎng)絡(luò)等計算方法相結(jié)合，開辟了計算的新思路。許多學(xué)者將DNA計算應(yīng)用于求解圖與組合優(yōu)化問題，先后提出了不同的DNA計算模型，解決了3-SAT問題[2]、最大團問題[3～6]、最小頂

2、點覆蓋問題[7]、圖頂點著色問題[8]等[9、10]。
　　0-1規(guī)劃問題是整數(shù)規(guī)劃的特殊形式，是運籌學(xué)中的一個重要問題，其應(yīng)用廣泛，如指派問題、選地問題等均可視為0-1規(guī)劃。解決該問題的常見算法有窮舉法、隱枚舉法、分支定界法等，但各個算法均存在優(yōu)缺點，目前為止還沒有哪種算法可以一勞永逸。近年來，有不少學(xué)者針對一些特殊的整數(shù)規(guī)劃問題，先后提出了相應(yīng)的DNA計算模型。部分組合優(yōu)化問題（特別是NP-完全問題）和一些可滿足性問題，一般都

3、能轉(zhuǎn)化為0-1整數(shù)規(guī)劃問題。
　　DNA芯片操作簡單可行、并行性高，能有效避免實驗操作及人為因素對計算結(jié)果造成的誤差，實現(xiàn)計算過程自動化，提高了計算效率和可行解的準確性。因此DNA芯片在DNA計算乃至生物計算領(lǐng)域的優(yōu)勢得天獨厚，有望成為新型生物計算芯片。
　　文章首先對DNA計算相關(guān)的生物操作加以介紹，簡單闡述DNA結(jié)構(gòu)以及DNA計算的基本思想。其次，介紹0-1規(guī)劃問題、特殊整數(shù)規(guī)劃問題的幾種DNA計算模型，并對其算法和思想