圖頂點(diǎn)著色DNA計算模型及實(shí)驗研究.pdf

1、DNA 計算是以DNA 分子作為“數(shù)據(jù)”，以生化反應(yīng)作為“信息處理工具”的一種新穎計算模式。由于其高度并行性、海量存儲能力、低能耗等優(yōu)點(diǎn)，DNA 計算成為眾多學(xué)者關(guān)注的焦點(diǎn)。近年來，許多研究成果已經(jīng)提高了它的性能并增加了它的可行性。但是，DNA 計算尚未成熟。關(guān)于DNA 計算理論和技術(shù)上的進(jìn)一步研究都具有重要的科學(xué)意義。 圖頂點(diǎn)著色問題存在于豐富的科學(xué)和工程應(yīng)用中，如工序問題、排課表問題、物資儲存問題等等，但它卻是眾所周知的NP

2、-完全問題。本文針對這一具體問題，結(jié)合分子生物學(xué)的研究方法和實(shí)驗技術(shù)，旨在建立自動化程度較高的，可用于求解較大規(guī)模問題的DNA 計算模型，研究探討了四種解決圖頂點(diǎn)著色的DNA 計算模型的可行性及優(yōu)缺點(diǎn)，對每個DNA 計算模型給出了具體的編碼條件及相應(yīng)的編碼，及實(shí)現(xiàn)DNA 計算模型的生化操作的實(shí)驗步驟，并對一些模型給出了詳細(xì)的實(shí)驗驗證。主要工作如下： 文章首先基于雜交反應(yīng)提出一種枚舉型的DNA 計算模型。在該模型中，提出了具體編碼

3、方案，并利用DNA 自動合成儀合成初始解空間，然后利用雜交反應(yīng)和聚合酶鏈?zhǔn)椒磻?yīng)來求解問題。文章以具有5個頂點(diǎn)圖為例對該模型進(jìn)行了生化實(shí)驗驗證。 實(shí)驗結(jié)果表明，該模型能有效求解圖頂點(diǎn)著色問題。 為了減少DNA 計算中編碼的數(shù)量，不降低生化實(shí)驗操作的可靠性，文章提出一種改進(jìn)的枚舉型DNA 計算模型。在該模型中，利用雙編碼法對圖頂點(diǎn)著色這一問題進(jìn)行編碼，利用酶切反應(yīng)和聚合酶鏈?zhǔn)椒磻?yīng)對問題進(jìn)行求解。實(shí)例分析表明，該模型具有編碼量少

4、、求解過程簡單的優(yōu)點(diǎn)，尤其是因為該模型的解的檢測方法類似于DNA測序技術(shù)，使得該模型更容易實(shí)現(xiàn)自動化操作。 解空間指數(shù)爆炸問題是阻礙DNA 計算發(fā)展的最大瓶頸。針對這一問題，文章提出一種非枚舉型DNA 計算模型。在模型中，首先對編碼方案和初始解空間構(gòu)建進(jìn)行了優(yōu)化，構(gòu)建了非枚舉型的初始解空間，刪除了大量非解，提高計算效率；然后利用聚合酶鏈?zhǔn)椒磻?yīng)實(shí)現(xiàn)非解刪除的操作，并使用DNA 測序技術(shù)讀取最終解；文章以一個含有12個頂點(diǎn)的圖為例對

5、該模型進(jìn)行了實(shí)驗驗證。實(shí)驗結(jié)果表明，該模型有效可靠，可以較好的克服DNA 計算中的解空間指數(shù)爆炸問題。為建立可用于求解大規(guī)模圖頂點(diǎn)著色問題的DNA 計算模型，文章在非枚舉型DNA 計算模型的基礎(chǔ)上，引入并行處理的思想，建立了一種并行型DNA 計算模型。 在模型中，給出了一種子圖劃分的方法和原則，通過對給定圖進(jìn)行分解和合并處理，使得該DNA 計算模型能夠求解更大規(guī)模的圖頂點(diǎn)著色問題。文章以一個含有61個頂點(diǎn)的圖為例，對該模型進(jìn)行了

6、實(shí)驗驗證。實(shí)驗結(jié)果表明，該模型不但延續(xù)了非枚舉型DNA 計算的優(yōu)勢，而且具有解決大規(guī)模的圖頂點(diǎn)著色問題的能力。同傳統(tǒng)的DNA計算模型相比，該模型可以大大提高計算效率，降低成本，能有效處理更大規(guī)模的圖頂點(diǎn)著色問題，具有較強(qiáng)的應(yīng)用價值。 為了滿足不同DNA 計算模型的編碼需求，文章也考慮了不同編碼條件及參數(shù)，設(shè)計了大量DNA 編碼。實(shí)驗結(jié)果表明，這些編碼能滿足DNA 計算中的數(shù)量和質(zhì)量要求。由此所構(gòu)成的編碼數(shù)據(jù)庫，能方便DNA 計算技