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

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

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

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