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

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

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

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