四類DNA計算模型中一些理論與應(yīng)用的研究.pdf

1、本文對四類DNA計算模型中的一些理論及其應(yīng)用進行了研究和討論,具體工作如下:粘貼系統(tǒng)是建立在粘貼運算基礎(chǔ)上的語言生成器,也是一種遵循Watson-Crick互補性質(zhì)進行退火操作的DNA計算抽象模型.本文將線性串的粘貼系統(tǒng)拓展到帶有發(fā)夾結(jié)構(gòu)的雙向復(fù)雜結(jié)構(gòu)粘貼系統(tǒng),使粘貼系統(tǒng)的純理論研究向?qū)嶋H生物操作技術(shù)研究邁進了一步.給出了雙向復(fù)雜結(jié)構(gòu)粘貼系統(tǒng)的定義及其基本運算;提出了雙向復(fù)雜結(jié)構(gòu)粘貼系統(tǒng)的分類;討論了雙向復(fù)雜結(jié)構(gòu)粘貼系統(tǒng)的生成能力和計算

2、能力;最后,通過雙向復(fù)雜結(jié)構(gòu)粘貼系統(tǒng)的弱編碼刻畫了遞歸可列語言,這表明雙向復(fù)雜結(jié)構(gòu)粘貼系統(tǒng)與遞歸可列語言族有相同的計算能力.本文給出了圖頂點著色問題的DNA粘貼算法.在研究圖頂點著色問題時,從問題的本質(zhì)出發(fā),先把圖的頂點著色問題分解成頂點獨立集問題和頂點劃分問題并給出這兩個問題的DNA粘貼算法,然后調(diào)用這兩個算法以解決圖的頂點著色問題.圖的全著色猜想是由M.Behzad和Vizing于1965年提出的.到目前為止,對于一般的圖,全著色猜

3、想仍然是一個公開的問題.本文從系列平行圖的結(jié)構(gòu)性質(zhì)出發(fā),利用雙重歸納法和換色技巧確定了系列平行圖的全色數(shù).本文利用剪接系統(tǒng)的巨大并行性,首先設(shè)計了模擬有向哈密頓路問題的剪接系統(tǒng);然后通過此剪接系統(tǒng)所產(chǎn)生語言的性質(zhì)對有向哈密頓路問題進行分析,給出了有向圖的若干結(jié)構(gòu)性質(zhì)以及圖中存在有向哈密頓路的充要條件.圖的最小頂點覆蓋問題是圖論中的一個NP完全問題.它在分子生物學(xué)、調(diào)度問題、錯誤診斷和恢復(fù)集裝線平衡、油輪行程安排及開關(guān)理論中有著廣泛的應(yīng)用