DNA計算及其應(yīng)用.docx

ID:57277812

大小:13.48 KB

頁數(shù):2頁

時間:2020-08-08

DNA計算及其應(yīng)用.docx_第1頁
DNA計算及其應(yīng)用.docx_第2頁
資源描述:

《DNA計算及其應(yīng)用.docx》由會員上傳分享,免費在線閱讀,更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、DNA計算及其應(yīng)用自動化14117王張鑫1994年,Adleman發(fā)表得論文《用分子計算解決組合問題》中,敘述了他如何用DNA分子的生物學(xué)反應(yīng)來模擬一個著名的N.P問題—有向哈密頓路徑(柵P)的求解過程,并獲得了結(jié)果。因此Adlem開創(chuàng)了一門新的計算方法:DNA計算。DNA計算機的基本運算是通過生物化學(xué)反應(yīng)來實現(xiàn)的,其存儲介質(zhì)是生物分子。脫氧核糖核酸(DNA)是一切細胞生物的遺傳信息的載體,其基本結(jié)構(gòu)單元是脫氧核苷酸。而脫氧核苷酸又由堿基、戊糖和磷酸三部分組成。組成脫氧核苷的酸堿基有四種,分別是腺嘌呤

2、A、胸腺嘧啶T、胞嘧啶C和鳥嘌呤G,每個脫氧核苷酸都只含有這四種堿基中的一種,人們通常用堿基名來指代整個脫氧核苷酸,堿基的特定化學(xué)結(jié)構(gòu)使得A只能和T配對,G只能和C配對。因此,從計算機科學(xué)的角度看,DNA分子鏈可以看作是字母表{A,C,G,T)上的有限多重集合。研究表明DNA分子與現(xiàn)行計算機相比具有以下優(yōu)勢:(1)生物化學(xué)反應(yīng)是并行反應(yīng),這使得DNA計算機本身就具有極高的并行計算能力。(2)由于生物化學(xué)反應(yīng)一般會釋放出能量,因此Ⅸ蛆計算機與常規(guī)電子計算機相比,是極其節(jié)能的。(3)DNA分子的信息存儲密

3、度很高。一個晶體管僅有一字節(jié),而一克DNA包含1021個DNA堿基,相當(dāng)于108萬億字節(jié)。因此,世界上現(xiàn)在存儲的所有數(shù)據(jù)用DNA來存儲,可能只需幾克DNA。由于DNA計算顯示了高速并行計算、極少耗能、極大存儲量的優(yōu)勢及其解決超大規(guī)模計算的可能性和潛在力,從而引起了計算機科學(xué),數(shù)學(xué)科學(xué)和工程及生物分子學(xué)等諸多領(lǐng)域的學(xué)者們的極大興趣。從計算機科學(xué)的角度看,DNA鏈可以看作是字母表A,C,G,T上的有限多重集合。DNA計算實質(zhì)上是對此集合作以下幾種運算:(1)提取:設(shè)T是字母表∑上的多重集,S∈∑,產(chǎn)生+(

4、T,S)與-(T,S)。+(T,S)里分子都包含連續(xù)的S,而-(T,S)里的分子則不包含連續(xù)的S。(2)分離:設(shè)T是字母表∑上的多重集,S∈T,按S的長度將T分離成T1……(3)合并:給定T-與T2,產(chǎn)生u(T。,T2,),這里u(T。,T2)=T。uT2。(4)檢測:給定T,如果T里有至少一個分子,返回“是”,否則返回“不”;(5)擴增:給定T,產(chǎn)生丁’(丁)與丁”(r),這里丁=丁’(丁)=丁"(丁);(6)附加:設(shè)T是字母表∑上的多重集,S∈∑,使T中所有的串后都加上S。DNA計算在密碼學(xué)方面的

5、應(yīng)用:由于DNA計算天生具備極大的并行計算能力與海量儲存密度這兩個常規(guī)電子計算機所不具備的強大優(yōu)勢,所以DNA計算一經(jīng)創(chuàng)立,就被嘗試用來攻擊密碼系統(tǒng)。1995年,Boneh提出了一種基于liptonDNA計算模型攻擊DES密碼系統(tǒng)的方法。Boneh采用的編碼方法如下:每一比特均用兩條獨一無二的30個堿基長的寡聚核苷酸鏈編碼,一條寡聚核苷酸鏈編碼該比特所在的位置,另一條寡聚核苷酸鏈編碼該比特的值。將每一次異或運算的結(jié)果添加在編碼密鑰的Ⅸ蛆分子的后面。S運算則通過提取、添加等操作將編碼該次運算結(jié)果的DNA

6、分子加在DNA分子的后面。Boneh的算法采用并行提取的方法,一次能同時并行進行32個提取操作,只需916步,該算法就有可能破譯DES。由于現(xiàn)在的大多數(shù)生物儀器,例如PCR儀,具有同時操作多種溶液的功能,因此這種方法在實際上是可行的。Adlem鋤的編碼方法如下,將一條長為11580聚體的單鏈DNA分子分成576個的單元,每個單元含20個堿基,前56個單元編碼密鑰,第57—120個單元編碼密文,剩余的單元用來存儲計算過程中的中間結(jié)果。其異或運算用并行分離、并行設(shè)置來實現(xiàn),S運算則用并行分離、并行設(shè)置、并

7、行組合來實現(xiàn)。DNA計算在自動機領(lǐng)域的應(yīng)用:從可行性的角度出發(fā),研究DNA計算能有效且可靠地求解問題更具有現(xiàn)實意義。正是基于這一點,利用DNA計算模擬有窮自動機成為DNA計算研究領(lǐng)域的一個重要內(nèi)容,因為有窮自動機是一種最簡單的理想計算機,用DNA計算來模擬有限自動機比較容易實現(xiàn)。1997年,Rose報導(dǎo)了用DNA計算快速、準(zhǔn)確地模擬有窮自動機的方法;1997年,Gao設(shè)計了用DNA計算模擬非確定性有窮自動機的方法。2001年,以色列科學(xué)家成功地進行了用DNA計算自動模擬有窮自動機的實驗。2003年,該

8、國科學(xué)家又成功地設(shè)計出不需外界提供能量就能自動運行的DNA自動機。2004年,他們還研究出能對基因的表達起調(diào)控作用的DNA自動機。國內(nèi)對DNA計算的研究剛剛起步不久,基本上都是針對大規(guī)模計算問題的研究。2003年,趙健設(shè)計出運行于磁珠表面的可自動運算的DNA自動機。從2004年開始,北京航空航天大學(xué)DNA研究小組致力于用DNA計算攻擊密碼的研究。我們已完成了攻擊對稱與非對稱密鑰系統(tǒng)的設(shè)計,并完成了其可行性論證。以上說明了DNA計算相關(guān)的理論研究、實驗研究

當(dāng)前文檔最多預(yù)覽五頁,下載文檔查看全文

此文檔下載收益歸作者所有

當(dāng)前文檔最多預(yù)覽五頁,下載文檔查看全文
溫馨提示:
1. 部分包含數(shù)學(xué)公式或PPT動畫的文件,查看預(yù)覽時可能會顯示錯亂或異常,文件下載后無此問題,請放心下載。
2. 本文檔由用戶上傳,版權(quán)歸屬用戶,天天文庫負責(zé)整理代發(fā)布。如果您對本文檔版權(quán)有爭議請及時聯(lián)系客服。
3. 下載前請仔細閱讀文檔內(nèi)容,確認(rèn)文檔內(nèi)容符合您的需求后進行下載,若出現(xiàn)內(nèi)容與標(biāo)題不符可向本站投訴處理。
4. 下載文檔時可能由于網(wǎng)絡(luò)波動等原因無法下載或下載錯誤,付費完成后未能成功下載的用戶請聯(lián)系客服處理。
关闭