Hamilton圖的DNA算法及應用.pdf

1、DNA計算是生物計算中最受關注的一種計算，目前的DNA計算領域始于1994年Adleman先生的著名實驗．本文探討了采用分子生物技術，通過DNA計算尋找Hamilton路從而判定Hamilton圖的一些算法及用DNA計算來解決染色問題． 第一，本文首先分析總結了Hamilton圖的充分條件問題、研究狀況.Hamilton圈問題是圖論最古老的研究課題之一，是至今未解決的世界難題．特別是尋找一般圖的Hamilton圖的充分條件問題是

2、NP問題． 其次，介紹了DNA計算的產(chǎn)生背景、研究狀況、生物學基礎、DNA計算解決Hamilton圈的基本原理和操作方法。DNA計算機起源于人們對并行計算的研究和追求，以傳統(tǒng)的圖靈機(Turing Machine)為原型的現(xiàn)代電子計算機很難從真正意義上實現(xiàn)并行算．于是人們將目光投向了其它領域，以求獲得完全不同的計算方式和計算理念．DNA算法解決計算問題的基本思想是：以DNA堿基序列作為信息編碼的載體，利用現(xiàn)代分子生物學技術，在試

3、管內(nèi)控制酶的作用下進行DNA的序列反應，Watson-Crick互補序列反應作為實現(xiàn)運算的過程．以反應前的.DNA序列作為輸入的數(shù)據(jù)，反應后的DNA序列作為運算的結果．DNA計算的操作方法一般有抽取、切割、溶解、退火、合成、雜交、擴增PCR、檢測、分離、電泳、磁珠分離、連接和合并等. 最后，指出DNA計算機的優(yōu)點、應用前景與存在的技術問題.DNA計算機的優(yōu)點是：運算速度快；低能耗；存儲容量高；可以真正實現(xiàn)并行工作.DNA計算機的

4、應用前景：1.解決某些NP完全問題2.數(shù)據(jù)加密解密3.智能控制4.生物化學、組合化學、醫(yī)學等5.Boolean電路和數(shù)據(jù)流邏輯運算.DNA計算機的存在的技術問題：DNA計算中誤差消除問題；快速操作技術問題；DNA計算系統(tǒng)的框架還未形成；DNA制作成本較高等． 第二，本文建立了解決簡單問題的簡單模型，從而推廣到解決復雜問題即NP完全問題．并探討了在推廣過程中產(chǎn)生的偽解問題及采取的相應的去除操作．先結合Adleman的實驗建立一個小

5、規(guī)模圖的DNA計算的簡單模型，用凝練的語言介紹DNA計算解Hamilton圖的思想方法、生物實驗操作步驟，然后再擴大規(guī)模研究NP問題(Hamilton圖的問題)．并對問題的復雜性作了計算復雜性討論．介紹一種用基于可滿足解空間的DNA計算方法，來解決Hamilton回路問題，該方法可以簡化DNA計算過程，提高求解問題的規(guī)模．建立HPP問題的DNA計算模型的步驟包括：問題描述、算法設計、DNA計算的實現(xiàn)三部分．這種方法在原理上也同樣適用于比

6、較大的圖．這種方法的關鍵是大規(guī)模的并行計算和堿基互補原則．對于解決HPP問題，Adlemarl的解決方案基于如下非確定算法： 輸入：具有n個頂點的有向圖G，指定頂點v<,in>和v<,out>． 第一步：在G中隨機生成大量的各種各樣的路徑． 第二步：去掉所有不以頂點v<,in>為起點和不以頂點v<,out>為終點的路． 第三步：去掉所有沒有恰含n個頂點的路． 第四步：對于這n個頂點中的每一個頂點v

7、<'V>，去掉所有不包含頂點v的路． 輸出：如果存在路，輸出“是”，否則輸出“否”． 實質(zhì)上，此算法是在執(zhí)行窮舉搜索，在Adleman的算法中，DNA串的巨大規(guī)模的并行計算處理了令人討厭的非確定性，Watson-Crick堿基互補原則用來確保構造出的邊的序列就是圖G中的路．DNA計算的優(yōu)勢是其具有強大的并行性．但是在解決組合優(yōu)化中的NP-完全問題時，傳統(tǒng)的DNA計算模型面對指數(shù)級增長的解空間卻顯得無能為力．據(jù)估計對于20

8、0個頂點的HPP問題，按照Adleman的方法，所需的DNA分子將超過地球的重量，為了解決“指數(shù)爆炸”問題，總結了目前國外的幾種解決方法。 第三，討論了最新的DNA計算在NP問題即點染色問題和邊染色問題中的應用．用DNA計算解染色問題，其主要思想是將著色問題分解成頂點獨立集問題和頂點劃分問題進行解決，該算法將點(邊)的DNA編碼分為兩部分，一部分存儲點(邊)和色位置的二維數(shù)據(jù)，另一部分存儲色號值．先將此NP問題在多項式時間內(nèi)歸約

9、到可滿足性問題．對初始試管T<,0>選用粘貼模型的操作，并引入Discard表示“舍棄”操作(將試管中的溶液倒掉)，以Lipton解決SAT問題的思想為依據(jù)，給出求解圖G的頂點k-著色問題的算法。然后在DNA計算的去除操作過程中采用批刪除操作，從而有效地解決了此染色問題．隨著社會和技術的發(fā)展，許多工程領域中的復雜巨系統(tǒng)不斷涌現(xiàn)，充滿著各種各樣的非線性問題，形形色色棘手的完全問題處處可見，而DNA計算機有望解決當今在電子計算機上許多無法解