基于DNA計算的NP問題研究.pdf

1、DNA計算是一種模擬生物分子DNA的結構并借助分子生物技術進行計算的新方法，DNA計算主要分為兩步：第一步是生成問題的所有可能解，第二步是解的檢測。它作為一門新興的交叉學科正逐漸發(fā)展起來，在解決大規(guī)模并行計算問題上，特別是在解決NP-完全問題上有其不可估量的優(yōu)勢。 1994年，Adleman利用DNA計算解決了圖論中的哈密頓路徑問題，并成功地進行了實驗。其目標是產生以DNA計算模型為背景、具有海量的存儲遺傳密碼以及極快運行速度的

2、新一代計算機。DNA計算的基本思想是：利用DNA特殊的雙螺旋結構和堿基互補配對規(guī)律進行信息編碼，把要運算的對象映射成DNA分子鏈，在生物酶的作用下，生成各種數據池（data pool），然后按照特定的規(guī)則將原始問題的數據運算高度并行地映射成DNA分子鏈的可控的生化過程。最后，利用分子生物技術如聚合鏈反應PCR、超聲波降解、親和層析、克隆、誘變、分子純化、電泳、磁珠分離等，檢測所需要的運算結果。DNA計算的核心問題是將經過編碼后的DNA鏈

3、作為輸入，在試管內或其它載體上經過一定時間完成可以控制的生物化學反應，并以此來完成運算，使得從反應后的產物中能得到全部的解空間。在DNA計算系統(tǒng)中，DNA分子中的密碼作為存儲的數據，當DNA分子間在某種酶的作用下瞬間完成某種生物化學反應時，可以從一種基因代碼變?yōu)榱硪环N基因代碼。DNA計算實際也就是通過對DNA雙螺旋進行豐富的精確可控的化學反應，包括標記、擴增或者破壞原有鏈來完成各種不同的運算過程。 本文從DNA計算所使用的DNA