子集積問題的DNA計(jì)算機(jī)算法研究.pdf

1、1994年，Adleman用操縱DNA分子的辦法解決了一個(gè)經(jīng)典的NP完全問題—哈密頓路徑問題（一個(gè)包含7個(gè)頂點(diǎn)實(shí)例）。自此以后，生物計(jì)算作為生物與計(jì)算機(jī)科學(xué)的交叉學(xué)科迅速的發(fā)展起來。 隨著DNA計(jì)算研究的逐漸深入，現(xiàn)有基于窮舉方法的DNA計(jì)算機(jī)算法中存在的解空間指數(shù)爆炸問題日益突出，已成為限制DNA超級計(jì)算應(yīng)用的瓶頸因素，如何減少DNA計(jì)算機(jī)求解NP完全問題中以問題輸入純指數(shù)增長的DNA鏈數(shù)，已成為DNA計(jì)算研究的重要內(nèi)容之一。

2、現(xiàn)有DNA計(jì)算模型的并發(fā)操作難以達(dá)到電子計(jì)算機(jī)并行處理操作的自如程度，因此，不管基于DNA計(jì)算的何種模型，目前幾乎所有的基于DNA超級計(jì)算的算法均使用完全窮舉方式，而DNA計(jì)算模型上的不可擴(kuò)展是求解NP問題算法上難于擴(kuò)展的原因。因此考慮將傳統(tǒng)電子計(jì)算機(jī)并行處理的策略、方法和技術(shù)引入DNA超級計(jì)算是降低DNA鏈數(shù)的重要途徑之一。這一問題源于現(xiàn)有DNA計(jì)算模型的不可擴(kuò)展性。 本文考慮將傳統(tǒng)電子計(jì)算機(jī)中的并行策略應(yīng)用于DNA計(jì)算中，采

3、用理論分析和生物實(shí)踐相結(jié)合的方法，解決DNA計(jì)算中限制DNA計(jì)算的瓶頸的DNA鏈數(shù)問題。具體將分治策略應(yīng)用于DNA計(jì)算領(lǐng)域中，提出了基于分治策略的求解子集積問題的DNA計(jì)算機(jī)算法，并通過對現(xiàn)有算法中存在的時(shí)間復(fù)雜度過高的問題，提出一種具有較好可擴(kuò)展性的改進(jìn)質(zhì)粒模型，并將分治策略應(yīng)用于子集積問題的DNA分子算法設(shè)計(jì)中，提出一種求解子集積問題的新的DNA計(jì)算機(jī)算法。本文提出的算法的DNA鏈數(shù)均可達(dá)到亞指數(shù)的O(1.414n)，其中n為子集積