Hamilton圖的DNA算法及應(yīng)用.pdf

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

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

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

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

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

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

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

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

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