【摘要】：DNA計算一直以來都是很熱門的一門學科,它利用分子生物技術(shù)解決計算機科學或數(shù)學中的問題,是計算機科學與生物化學之間的橋梁。在DNA的計算中,信息通過DNA分子間的相互作用進行傳遞,并且它的過程是通過一系列生化反應來完成的,由于生化反應中固有的大量并行性和DNA分子的高信息密度,使得DNA計算慢慢成為一個有吸引力的并且值得研究的領(lǐng)域。本文主要研究的是DNA計算在NP-完全問題中的應用。首先在緒論中介紹了 DNA計算的背景知識,基本的思想和意義。然后詳細闡述了 DNA折紙術(shù)在可滿足性問題中的應用,并列出了可滿足性問題的研究現(xiàn)狀�？蓾M足性問題是理論計算機與人工智能等領(lǐng)域共同關(guān)注的NP-完全問題之一,在NP-完全問題中占有很重要的地位。與以往提出的一些DNA自組裝方法相比,DNA折紙術(shù)可以看成是一種新的DNA自組裝方法。利用基于DNA折紙術(shù)求解可滿足性問題的計算模型,解決了一個含3個變量、3條子句的實例,以說明算法的可行性。該計算模型只需利用凝膠電泳尋找滿足問題的解,這是目前已知的最可靠的生物操作,提高了模型可行性,降低了生物操作的難度。目前,利用折紙術(shù)來求解NP-完全問題的成果相對較少,我們提出的方法是利用生物DNA分子解決NP-完全問題的一種新的嘗試。盡管SAT問題有很多豐碩成果,但基于SAT問題的重要性,新的方法總能引起讀者重視。隨著研究人員們更深入的研究以后,使得對于DNA折紙術(shù),其結(jié)構(gòu)的尺寸及其穩(wěn)定性有了初步的改進,它作為一個新興的DNA計算模型,在很多方面都起到了一定的推動作用,對DNA計算的發(fā)展提供了更大的幫助。根據(jù)列出的0-1整數(shù)規(guī)劃問題的研究現(xiàn)狀,提出巨磁電阻型DNA計算模型在0-1整數(shù)規(guī)劃問題中的應用。本文將問題的變量編碼成DNA鏈,在GMR型芯片表面固定DNA探針,然后將被生物素標記的待分析目標DNA鏈與探針進行充分雜交,通過芯片上的GMR傳感器對芯片上納米磁珠的檢測,以電信號方式輸出,得到問題的解,避免了熒光分析中的信號轉(zhuǎn)換而引起的失真。該模型具有較高靈敏度,信號檢測和分析較為簡單,對信號檢測設(shè)備要求較低。最后簡單的介紹了本文的主要研究結(jié)果,比較了提出的模型與其他DNA計算模型的優(yōu)點與不足,并交代了進一步的研究方向。圖[29]表[2]參考文獻[58]
【學位授予單位】：安徽理工大學
【學位級別】：碩士
【學位授予年份】：2019
【分類號】：Q523;O221.4
【圖文】：

解決了一個ＮＰ－完全問題（Ｈａｍｉｌｔｏｎ路問題），具有指定頂點ｖ，＿？和，的有向圖Ｇ逡逑被稱為具有Ｈａｍｉｌｔｏｎｉａｎ路，當且僅當存在一系列兼容的“單向”邊ｅ｜，ｅ２，．．．，ｅ？邋（即逡逑路徑），以ｖ，？開始，結(jié)束，并且每一個頂點完全進入一次（圖１）。逡逑圖１有向圖，當ｖ，？＝０，＝邐存在唯一的哈密頓路徑：逡逑０邋—＞邋１，１邋—＞邋２，２邋—＞邋３，３邋—＞邋４，４邋—＞邋５，５邋—＞邋６逡逑Ｆｉｇ．邋１邋Ｄｉｒｅｃｔｅｄ邋ｇｒａｐｈ，邋ｗｈｅｎ邋ｖｉｎ邋＝邋０，邋ｖｏｕｔ邋＝邋６邋，ｔｈｅｒｅ邋ｉｓ邋ａ邋ｕｎｉｑｕｅ邋Ｈａｍｉｌｔｏｎｉａｎ邋ｐａｔｈ逡逑０邋—＞邋１，１邋—＾邋２，２邋—＞邋３，３邋—＞邋４，４邋—＞邋５，５邋—＞邋６逡逑這是分子生物學工具被直接應用在ＮＰ－完全問題上，科學發(fā)展大大促進了分逡逑子生物技術(shù)以很快的速度發(fā)展。這一問題一經(jīng)提出引起了各界研究人員的重視和逡逑關(guān)注，尤其是數(shù)學，物理方面的科學家，ＤＮＡ計算由于其并行性和高可存儲性可逡逑以滿足各種研究的需要，因而成為熱門領(lǐng)域。它的應用性較強，被廣泛應用于實逡逑際問題。ＤＮＡ計算是通過利用分子生物學實驗室技術(shù)來操縱ＤＮＡ鏈來解決計算逡逑問題

更簡單方便操作，試管的形成方式與Ａｄｌｅｍａｎ形成所有路徑的試管相同，試管中逡逑的ＤＮＡ組對應于下面的簡單圖Ｇ？，圖Ｇ具有節(jié)點ａ１，ｘ１，；￡：ｉ，ａ２，ｘ２，ｘｊ，．．．，ｆｌ？＋１，邊逡逑緣從心到＼和；＾以及從心和＜到七＋１邋（圖２），這是對比其他方法以后，更適合逡逑用來解決ＮＰ－完全問題的方法，與我們的計算機相比較而言，這種ＤＮＡ計算模逡逑型具有更快的速度和更大的存儲容量。逡逑－１邋－逡逑

【參考文獻】

相關(guān)期刊論文 前7條

1 俞洋;蘇邵;晁潔;;基于“DNA折紙術(shù)”設(shè)計哈密頓路徑問題的解決方案[J];中國科學:化學;2015年11期

2 吳忠鈺;劉竟然;尹俊;張峰;;DNA折紙術(shù)的研究進展[J];基因組學與應用生物學;2014年03期

3 劉靜;殷志祥;;基于分子信標的DNA自組裝立體結(jié)構(gòu)[J];合肥工業(yè)大學學報(自然科學版);2014年04期

4 宋勃升;殷志祥;甄誠;華程;;DNA自組裝的可滿足性問題模型[J];小型微型計算機系統(tǒng);2011年09期

5 朱雅莉;李浪;鄒超君;;DNA計算機的研究現(xiàn)狀[J];電子設(shè)計工程;2011年06期

6 錢璐璐;汪穎;張釗;趙健;潘敦;張益;劉強;樊春海;胡鈞;賀林;;DNA納米結(jié)構(gòu)仿中國地圖[J];科學通報;2006年24期

7 周康;王延峰;劉文斌;許進;;基于閉環(huán)DNA的邊著色問題DNA算法[J];華中科技大學學報(自然科學版);2006年09期

本文編號：2718398