基于DNA自組裝模型的最大團(tuán)問題研究.pdf

1、DNA計算是一種基于分子和相關(guān)酶之間某些生化反應(yīng)過程的一種新的計算模式。不僅克服了電子計算機存儲量小與運算速度慢這兩個嚴(yán)重不足，而且表現(xiàn)出了高度并行性、海量存儲能力、低能耗與資源豐富四大特點。但是隨著DNA計算研究的深入，傳統(tǒng)DNA計算模型顯現(xiàn)出雜交錯誤率和生化操作復(fù)雜性過高的特點，如何提高DNA計算結(jié)果的準(zhǔn)確性在DNA計算研究中日顯重要。造成這種瓶頸有多方面的原因，DNA計算模型的選擇和編碼方案的設(shè)計是兩個重要的因素。
　　針對

2、NP完全最大團(tuán)問題的DNA計算求解方法，大多數(shù)是利用粘貼、剪接模型等，雖然這些算法能夠在多項式時間內(nèi)提取給定圖的最大團(tuán)，但是其生化操作具有較高的復(fù)雜度。生化實驗操作步驟越多，相應(yīng)帶來的實驗誤差也就越大，從而無法保證生化解的準(zhǔn)確性。本文首先基于Winfree提出的Tiles自組裝理論模型，定義了最大團(tuán)問題的基本信息到Tiles分子粘性末端的映射。詳細(xì)給出了初始格局階段、判定格局階段、檢測格局階段的編碼設(shè)計方案，分析了基于這種設(shè)計方案Til

3、es的種類為()(n2)?；赥iles自組裝理論模型的數(shù)學(xué)描述，理論證明了該設(shè)計方案正確性。
　　然后基于Tiles自組裝理論模型最大團(tuán)問題的設(shè)計思路，本文利用雙交叉DNA分子中的穩(wěn)定結(jié)構(gòu)DAE分子作為計算載體。根據(jù)DAE分子的結(jié)構(gòu)特點，改進(jìn)了Tiles自組裝模型的數(shù)學(xué)描述。結(jié)合基本的生化實驗操作方法，提出了一種求解最大團(tuán)問題的DNA計算算法。算法過程中的DAE分子分為初始分子、規(guī)則分子、檢測分子三種類型，且給出了DAE分子的詳