2023年全國碩士研究生考試考研英語一試題真題(含答案詳解+作文范文)_第1頁
已閱讀1頁,還剩48頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領

文檔簡介

1、DNA計算是生物計算中最受關注的一種計算,目前的DNA計算領域始于1994年Adleman先生的著名實驗.本文探討了采用分子生物技術,通過DNA計算尋找Hamilton路從而判定Hamilton圖的一些算法及用DNA計算來解決染色問題. 第一,本文首先分析總結了Hamilton圖的充分條件問題、研究狀況.Hamilton圈問題是圖論最古老的研究課題之一,是至今未解決的世界難題.特別是尋找一般圖的Hamilton圖的充分條件問題是

2、NP問題. 其次,介紹了DNA計算的產生背景、研究狀況、生物學基礎、DNA計算解決Hamilton圈的基本原理和操作方法。DNA計算機起源于人們對并行計算的研究和追求,以傳統(tǒng)的圖靈機(Turing Machine)為原型的現(xiàn)代電子計算機很難從真正意義上實現(xiàn)并行算.于是人們將目光投向了其它領域,以求獲得完全不同的計算方式和計算理念.DNA算法解決計算問題的基本思想是:以DNA堿基序列作為信息編碼的載體,利用現(xiàn)代分子生物學技術,在試

3、管內控制酶的作用下進行DNA的序列反應,Watson-Crick互補序列反應作為實現(xiàn)運算的過程.以反應前的.DNA序列作為輸入的數(shù)據(jù),反應后的DNA序列作為運算的結果.DNA計算的操作方法一般有抽取、切割、溶解、退火、合成、雜交、擴增PCR、檢測、分離、電泳、磁珠分離、連接和合并等. 最后,指出DNA計算機的優(yōu)點、應用前景與存在的技術問題.DNA計算機的優(yōu)點是:運算速度快;低能耗;存儲容量高;可以真正實現(xiàn)并行工作.DNA計算機的

4、應用前景:1.解決某些NP完全問題2.數(shù)據(jù)加密解密3.智能控制4.生物化學、組合化學、醫(yī)學等5.Boolean電路和數(shù)據(jù)流邏輯運算.DNA計算機的存在的技術問題:DNA計算中誤差消除問題;快速操作技術問題;DNA計算系統(tǒng)的框架還未形成;DNA制作成本較高等. 第二,本文建立了解決簡單問題的簡單模型,從而推廣到解決復雜問題即NP完全問題.并探討了在推廣過程中產生的偽解問題及采取的相應的去除操作.先結合Adleman的實驗建立一個小

5、規(guī)模圖的DNA計算的簡單模型,用凝練的語言介紹DNA計算解Hamilton圖的思想方法、生物實驗操作步驟,然后再擴大規(guī)模研究NP問題(Hamilton圖的問題).并對問題的復雜性作了計算復雜性討論.介紹一種用基于可滿足解空間的DNA計算方法,來解決Hamilton回路問題,該方法可以簡化DNA計算過程,提高求解問題的規(guī)模.建立HPP問題的DNA計算模型的步驟包括:問題描述、算法設計、DNA計算的實現(xiàn)三部分.這種方法在原理上也同樣適用于比

6、較大的圖.這種方法的關鍵是大規(guī)模的并行計算和堿基互補原則.對于解決HPP問題,Adlemarl的解決方案基于如下非確定算法: 輸入:具有n個頂點的有向圖G,指定頂點v<,in>和v<,out>. 第一步:在G中隨機生成大量的各種各樣的路徑. 第二步:去掉所有不以頂點v<,in>為起點和不以頂點v<,out>為終點的路. 第三步:去掉所有沒有恰含n個頂點的路. 第四步:對于這n個頂點中的每一個頂點v

7、<'V>,去掉所有不包含頂點v的路. 輸出:如果存在路,輸出“是”,否則輸出“否”. 實質上,此算法是在執(zhí)行窮舉搜索,在Adleman的算法中,DNA串的巨大規(guī)模的并行計算處理了令人討厭的非確定性,Watson-Crick堿基互補原則用來確保構造出的邊的序列就是圖G中的路.DNA計算的優(yōu)勢是其具有強大的并行性.但是在解決組合優(yōu)化中的NP-完全問題時,傳統(tǒng)的DNA計算模型面對指數(shù)級增長的解空間卻顯得無能為力.據(jù)估計對于20

8、0個頂點的HPP問題,按照Adleman的方法,所需的DNA分子將超過地球的重量,為了解決“指數(shù)爆炸”問題,總結了目前國外的幾種解決方法。 第三,討論了最新的DNA計算在NP問題即點染色問題和邊染色問題中的應用.用DNA計算解染色問題,其主要思想是將著色問題分解成頂點獨立集問題和頂點劃分問題進行解決,該算法將點(邊)的DNA編碼分為兩部分,一部分存儲點(邊)和色位置的二維數(shù)據(jù),另一部分存儲色號值.先將此NP問題在多項式時間內歸約

9、到可滿足性問題.對初始試管T<,0>選用粘貼模型的操作,并引入Discard表示“舍棄”操作(將試管中的溶液倒掉),以Lipton解決SAT問題的思想為依據(jù),給出求解圖G的頂點k-著色問題的算法。然后在DNA計算的去除操作過程中采用批刪除操作,從而有效地解決了此染色問題.隨著社會和技術的發(fā)展,許多工程領域中的復雜巨系統(tǒng)不斷涌現(xiàn),充滿著各種各樣的非線性問題,形形色色棘手的完全問題處處可見,而DNA計算機有望解決當今在電子計算機上許多無法解

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
  • 4. 未經(jīng)權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
  • 5. 眾賞文庫僅提供信息存儲空間,僅對用戶上傳內容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
  • 6. 下載文件中如有侵權或不適當內容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論