基于IC的DNA計算算法的仿真與實現(xiàn).pdf

1、1994年，Adleman用操縱DNA分子的辦法解決了一個經(jīng)典的NP完全問題一哈密頓路徑問題(一個包含7個頂點實例)。自此以后，生物計算作為生物與計算機科學(xué)的交叉學(xué)科迅速地發(fā)展起來。 雖然DNA計算(分子計算)具有運算高度并行，DNA作為載體信息貯存量大，能量消耗低，DNA分子資源豐富等優(yōu)點，但是從目前分子計算發(fā)展來看，分子計算實現(xiàn)主要是溶液方式和表面方式，這兩種實現(xiàn)方式目前顯示出很多缺點：計算錯誤率高，單步執(zhí)行慢，編碼復(fù)雜，很

2、難實現(xiàn)自動化。為了克服上述缺點，我們設(shè)計一種利用現(xiàn)有的IC技術(shù)解決DNA計算的新的實現(xiàn)方式。 本文主要研究內(nèi)容如下： 1．系統(tǒng)地對DNA計算方法、原理、主要實現(xiàn)方式和優(yōu)缺點等方面進行了探討和總結(jié)，學(xué)習(xí)了FPGA和單片機的原理和軟硬件開發(fā)環(huán)境，提出了一種基于大規(guī)模集成電路設(shè)計的DNA計算實現(xiàn)方式。 2．結(jié)合傳統(tǒng)計算機和DNA計算的并行性，本文設(shè)計了一種基于DNA計算的計算機結(jié)構(gòu)模型。傳統(tǒng)的計算機在解決串行工作任務(wù)的

3、時候，其能力是無懈可擊的，DNA計算相對于傳統(tǒng)的計算機也有自己獨特的優(yōu)勢，它能夠同時搜索獲得所有的結(jié)論。 3．根據(jù)分子計算原理設(shè)計了一種具有可擴展性的解決SAT問題的算法，并用4個變量和6個變量的問題對算法的正確性進行了驗證。并使用單片機作為控制器，F(xiàn)PGA上設(shè)計實現(xiàn)電路解決了上述問題。受限于目前實驗條件，雖然理論上可以解決任意多個變量的問題，但是目前僅能解決11個變量也就是2048個分子處理單元的問題。 4．研究分析了

4、0-1規(guī)劃問題的模型，并根據(jù)該問題的原理，提出了一種基于DNA計算的算法，并在所設(shè)計的機器模型上對該算法的正確性進行了驗證，結(jié)果表明算法是正確的。 5．分析了均分問題的計算模型原理，在原有模型基礎(chǔ)上對7個變量的均分問題進行了仿真，驗證了算法的正確性。 6．最大集團問題是圖論中一個重要問題，本文嘗試了一個五個變量的最大集團問題，算法實現(xiàn)上目前只適合變量個數(shù)較少的問題，實現(xiàn)起來步驟雖然有所減少但是實現(xiàn)復(fù)雜度仍舊較大，本問題旨