摘要：DNA計算是計算機科學和分子生物學相互結(jié)合，相互滲透而產(chǎn)生的新計算模式，在解決一些復(fù)雜的問題上，尤其是NP—完全問題上具有一定的優(yōu)勢，提供了新的解決途徑。首先介紹DNA計算的基本原理，其次詳細介紹傳遞閉包問題的DNA算法 ，對圖中頂點用DNA片段進行編碼，將這些DNA片段放入溶液中進行生化反應(yīng)，通過基本的生物操作及生物酶完成解的產(chǎn)生，并最終篩選出傳遞閉包問題的所有解。最后介紹DNA計算的研究和一些尚待解決的問題。
　　關(guān)鍵詞：DNA計算 ；傳遞閉包； NP完全問題
　　中圖分類號：TP30 文獻標識碼：A 文章編號：1009-3044（2012）28-6771-02
　　1 概述
　　計算機技術(shù)被認為是20世紀三大科學革命之一，電子計算機為人類社會的發(fā)展起到了巨大的促進作用。然而，隨著科學技術(shù)的不斷發(fā)展，出現(xiàn)了許多新領(lǐng)域中的復(fù)雜難解問題，這些問題用普通的電子計算機很難解決，其原因就是電子計算機的運算速度慢和存儲空間小。因此，以DNA計算模型為背景而產(chǎn)生的所謂新一代計算機，即DNA計算機應(yīng)運而生。DNA計算在近幾年來倍受科學界的關(guān)注，尤其是在解決NP—完全問題上提供了新的方法。
　　自從Adleman 博士于1994年開創(chuàng)性地用DNA計算實現(xiàn)了7個頂點的有向圖的哈密頓問題以來，國際上對DNA計算引起了巨大的轟動。離散數(shù)學是數(shù)學的一個分支，在離散數(shù)學應(yīng)用的領(lǐng)域中，主要集中在對傳遞閉包問題，圖著色問題和主范式問題的求解上。自從Watson和Crick在1953年發(fā)現(xiàn)了DNA之后，人們發(fā)現(xiàn)和發(fā)展了許多操作DNA的方法，這些發(fā)現(xiàn)和發(fā)展不僅使我們能夠利用DNA作為信息載體，而且使我們能夠通過分子生物技術(shù)對DNA進行可空操作以實現(xiàn)某些算法。
　　2 DNA計算的基本原理
　　DNA計算的基本思想是：利用DNA特殊的雙螺旋結(jié)構(gòu)和堿基互補配對規(guī)律進行信息編碼，把要運算的對象映射成DNA分子鍵，在生物酶的作用下，生成各種數(shù)據(jù)池（data pool），然后按照一定的規(guī)則將原始問題的數(shù)據(jù)運算高度并行地映射成DNA分子鍵的可控的生化過程。最后，利用分子生物技術(shù)如聚合鏈反應(yīng)PCR，超聲波降解，親和層析，克隆，誘變，分子純化，電池，磁珠分離等，檢測所需要的運算結(jié)果。DNA計算的核心問題是將經(jīng)過編碼的DNA鏈作為輸入，在試管內(nèi)或其他載體上經(jīng)過一定時間完成控制的生物化學反應(yīng)，以此來完成運算，使得從反應(yīng)后的產(chǎn)物中能夠得到全部的解空間。
　　DNA計算的本質(zhì)就是利用大量不同的核酸分子雜交，產(chǎn)生類似于某種數(shù)學過程的一種組合的結(jié)果，并根據(jù)限定條件對其進行篩選。對DNA序可進行的操作是用生物酶來完成的。
　　3 傳遞閉包的DNA算法
　　3.1 傳遞閉包問題
　　文中我們考慮的圖是有向簡單圖。形式上，傳遞閉包求解的問題是這樣的：給定有向圖G=（V，E），設(shè)R是定義在非空集合A上的一個二元關(guān)系，R的傳遞閉包是A上的關(guān)系t（R），使得t（R）滿足以下條件：（1）[tR]具有傳遞性 （2）[R?tR]（3）對A上任何包含R的傳遞關(guān)系R，恒有[R?tR]。由定義可知，實際上就是找這樣的[tR]，向集合R中添加最少的元素（序偶）并使得R具有傳遞性的集合[tR]。
　　下面討論求解傳遞閉包問題的DNA算法。根據(jù)傳遞閉包的定義，我們可以將傳遞閉包的算法簡單概括如下：
　　3.2 DNA算法的生物實現(xiàn)
　　如圖1所示，
　　在非空集合[A=V1，V2，V3，V4]上定義了一個二元關(guān)系R，并且[R=V1，V2，V1，V3，V2，V3，V3，V4]。那么求解關(guān)系R的傳遞閉包[tR]的生物實現(xiàn)如下：
　　步驟 1 假定我們可獲得長20個核苷酸的隨機單鏈DNA序列， [V]代表DNA串[V]的逆補。先將圖中各個頂點[Vi]用一個任意的20個堿基單鏈DNA片段來代替，[Vij]弧分別用[Vi]頂點的后10個堿基的互補堿基和[Vj]頂點的前10個堿基的互補堿基構(gòu)成的DNA片段來代替。在適當?shù)臏囟认拢琜Waston-Crick]補很容易產(chǎn)生，所以可用[Vi]及[Vi]方便的構(gòu)成了路徑[Vki]和[Vij]的連接。通過連接酶反應(yīng)，我們將獲得許多隨機路徑。
　　假定所選代表頂點1，3，4的序列如下：
　　可通過以上序列構(gòu)造邊[V13]和[V34]，得[V13=CATATAGGCTCGATAAGCTC]
　　以此類推，可得到圖中隨機路徑編碼的DNA分子，即初始數(shù)據(jù)池。
　　4 結(jié)束語
　　傳遞閉包問題是離散數(shù)學中的一個重要內(nèi)容，因此，學者們都在尋求其解法。傳統(tǒng)的算法有[Warshall]算法，平方法，列標號法
　　等。這些方法在解決傳遞閉包問題時都有缺陷和不足，比如計算量大，運算速度慢，結(jié)果不夠精確等，而用DNA方法來解決此類問題就比較方便和簡單。當然，DNA計算在數(shù)學應(yīng)用領(lǐng)域中還存在一些尚待解決的問題，比如編碼問題等。
　　由于DNA分子計算尚處于胚胎發(fā)育時期，在一定程度上還不夠完善。盡管如此，目前國際上對DNA分子的前景信心十足，對于目前存在的種種不足，人們正在努力完善。
　　參考文獻：
　　[1] Adleman L M.Molecular Computation of Solutions to Combinatorial problem[J]Science，1994：266a（11）：1021-1023.
　　[2] Xu Jin，ZHANG Lei.DNA Computer Principle，Advances and Difficulties（II）[J].ChinesenJournal of Computers
　　[3] Lipton R J.DNA Solution of Computation Problem[J].Science，1995.
　　[4] Sakamoto K，Gouzu H，Komiya Ketal.Molecular computation by DNA hairpin formation[J].Scinence，2000.
　　[5] 殷志祥，張家秀.圖論中的DNA計算模型[J].系統(tǒng)工程與電子技術(shù)，2007（7）.
　　[6] 殷志祥.圖與組合優(yōu)化中的DNA計算[M].北京：科學技術(shù)出版社，2004.
　　[7] 張鴻雁.基于DNA計算的聚類算法研究[D].濟南：山東師范大學，2011.
　　[8] 朱越.基于DNA的連續(xù)優(yōu)化算法[J].計算機工程與應(yīng)用，2011，47（22）：48-52.
　　[9] 殷脂，葉春明，溫蜜.最小自由能約束的DNA編碼設(shè)計研究[J].計算機工程與應(yīng)用，2010，46（12）：25-27.
　　[10] 張凱，耿修堂，肖建華，等.DNA計算中核酸序列設(shè)計方法比較研究[J].計算機學報，2008，31（12）：2150-215