DNA計算在圖論中的應(yīng)用.pdf

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

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

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

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

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