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

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

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

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

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

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

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