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

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

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

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