傳遞閉包問題的DNA計(jì)算

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