多級(jí)分離技術(shù)及若干問題的DNA算法研究.pdf

1、DNA計(jì)算是一種新的計(jì)算模式，它以DNA(deoxyribonucleic acid，脫氧核糖核酸)為“原料”，以生化實(shí)驗(yàn)為工具進(jìn)行計(jì)算。DNA分子具有龐大的存儲(chǔ)容量，DNA計(jì)算具有其它計(jì)算方法無法比擬的巨大的并行性。 自1994年美國(guó)南加州大學(xué)的Adleman教授用生化實(shí)驗(yàn)解決了七個(gè)頂點(diǎn)的有向哈密爾頓路徑問題(Directed Hamilton Path Problem，DHPP)以來，有關(guān)DNA計(jì)算的科研工作迅速在許多國(guó)家

2、展開。雖然已取得了可喜的成果，但目前的研究還是理論研究居多，有關(guān)實(shí)驗(yàn)操作、實(shí)驗(yàn)裝置的研究則很少；再者，有許多經(jīng)典的圖論問題、數(shù)學(xué)問題等還未有DNA算法；有些問題雖有DNA計(jì)算方法，但仍有可改進(jìn)之處。 粘貼模型和剪接模型是DNA計(jì)算中的兩種最主要的模型。粘貼模型和剪接模型有著同等的計(jì)算能力，粘貼模型所使用的DNA鏈具有固定的長(zhǎng)度，操作時(shí)不需要擴(kuò)展DNA鏈，也無需酶的參與，而且它的材料在理論上可以重復(fù)使用。因此，有關(guān)粘貼模型的研究

3、開展得比較快，許多問題的粘貼DNA算法也被相繼提出。但是，由于粘貼模型僅采用原有的四種基本操作，實(shí)驗(yàn)操作步驟較多，耗費(fèi)了大量時(shí)間，鑒于此，本文提出了多級(jí)分離的概念，設(shè)計(jì)了一個(gè)多級(jí)分離裝置的模型。利用多級(jí)分離裝置可以實(shí)現(xiàn)DNA計(jì)算中的多種基本操作，并能實(shí)現(xiàn)“多級(jí)分離”操作，大大減少實(shí)驗(yàn)步驟，成倍提高解題效率。 本文應(yīng)用多級(jí)分離技術(shù)解決了以下三個(gè)問題： (1)馬步遍歷問題。文中給出了基于Adleman模型解決擴(kuò)展棋盤上馬步遍

4、歷問題的DNA算法。使用基本的“分離”操作即可解決該問題，本文使用了多級(jí)分離，旨在說明多級(jí)分離裝置也可以完成基本的分離操作。 (2)圖頂點(diǎn)著色問題。該問題是一個(gè)典型的NP-完全問題，目前，已有人提出了解決該問題的DNA算法，但存在著編碼方式復(fù)雜、將問題復(fù)雜化、效率不高等問題。本文利用Lipton解決可滿足性(Satisfiability,SAT)問題的思想，給出了解決該問題的一種粘貼DNA算法；并引入多級(jí)分離技術(shù)加以改進(jìn)，減少了