DNA計算在圖論中的應用.pdf

1、DNA計算是一種模擬生物分子DNA的結(jié)構(gòu)并借助于分子生物技術(shù)進行計算的新方法。它開創(chuàng)了以化學反應作為計算工具的先例，具有廣闊的應用前景。 1994年，Adleman首次在Science公布了DNA計算的理論，利用DNA計算解決了圖論中的哈密頓路徑問題，并成功地進行了實驗。Adleman的DNA計算完全是一種新的概念。它突破了傳統(tǒng)計算機體系結(jié)構(gòu)的束縛。DNA計算的基本思想是：利用DNA特殊的雙螺旋結(jié)構(gòu)和堿基互補配對規(guī)律進行信息編碼

2、，把要運算的對象映射成DNA分子鏈，在生物酶的作用下，生成各種數(shù)據(jù)池(datap001)，然后按照特定的規(guī)則將原始問題的數(shù)據(jù)運算高度并行地映射成DNA分子鏈的可控的生化過程。最后，利用分子生物技術(shù)如聚合鏈反應PCR、超聲波降解、親和層析、克隆、誘變、分子純化、電泳、磁珠分離等，檢測所需要的運算結(jié)果。DNA計算的核心問題是將經(jīng)過編碼后的DNA鏈作為輸入，在試管內(nèi)或其它載體上經(jīng)過一定時間完成可以控制的生物化學反應，并以此來完成運算，使得從反

3、應后的產(chǎn)物中能得到全部的解空間。 本文主要討論了三類圖論中問題的DNA計算模型，具體如下： 最小支撐樹問題的DNA算法：最小支撐樹問題是圖論中一個重要的、應用性很強的問題。求一個給定圖的最小支撐樹，常見的方法是Kruskal避圈法和破圈法。但這兩種方法都需要判斷圖的圈，這是非常繁瑣的。在這一章中，我們利用最小支撐樹的基本定義及DNA編碼，借助生物的基本操作電泳、探針分離及測序，給出了最小支撐樹的DNA算法。通過該算法，最

4、多只需，z一1步就可以找到圖的最小支撐樹(n為圖的定點數(shù))。 圖的頂點著色問題的DNA算法：利用DNA粘貼模型的巨大并行性，從圖頂點著色問題的本質(zhì)出發(fā)，先把圖的頂點著色問題分解成頂點獨立集問題和頂點劃分問題并給出這兩個問題的DNA粘貼算法，然后調(diào)用這兩個算法以解決圖的頂點著色問題。實例證明DNA粘貼算法在理論上可以實現(xiàn)的。 無向賦權(quán)圖哈密頓路徑問題的DNA算法：我們通過鏈中G、C含量的不同來表示不同的權(quán)值，對于權(quán)值較高的

5、邊使其具有高的GC含量否則具有較低的GC含量；因為GC配對是形成三共價鍵其解鏈溫度(Tm)大于AT形成的二個共價鍵的結(jié)合，我們就很容易的能夠根據(jù)它們解鏈溫度的不同來提取出權(quán)值低的路徑。我們采用粘貼短鏈隨機生成所有路徑，提取解時采用加熱變性與PCR反應同時進行的方式，首先變性的個體具有較低的權(quán)值優(yōu)先得到擴增，這樣的特點很好的解決了權(quán)值表示及分離的問題。權(quán)值的表示方法對于其他相關(guān)問題也很有借鑒意義。針對GC堿基對進行配對時形成的三共價鍵能量