【摘要】：圖靈獎(jiǎng)得主Adleman首次提出DNA計(jì)算的概念。作為交叉學(xué)科的DNA計(jì)算具有強(qiáng)并行處理,高存儲(chǔ)、快運(yùn)算、低耗能等優(yōu)點(diǎn),因此引起各界學(xué)者的廣泛關(guān)注和研究。發(fā)展至今,DNA計(jì)算由理論到實(shí)驗(yàn),再到應(yīng)用,每一個(gè)階段都取得了很大的成果。DNA計(jì)算的粘貼模型具有多個(gè)優(yōu)點(diǎn),諸如反應(yīng)材料可重復(fù)使用,生物反應(yīng)過程中既無(wú)需生物酶作用也無(wú)需DNA鏈的延伸等,更重要的是,粘貼模型在解決圖論問題方面有巨大潛力和優(yōu)勢(shì),特別是針對(duì)復(fù)雜的NP完全問題。從已有文獻(xiàn)來(lái)看,利用DNA計(jì)算模型解決的問題都是無(wú)向圖相關(guān)的,而針對(duì)有向圖,目前尚缺乏有效的DNA計(jì)算方法。為此,本文選用粘貼模型,提出兩種新算法(k頂點(diǎn)導(dǎo)出子圖和k頂點(diǎn)關(guān)聯(lián)關(guān)系)且給出了賦權(quán)問題的改進(jìn)算法,這些在粘貼機(jī)上實(shí)現(xiàn)的子算法皆為DNA計(jì)算機(jī)提供了算法庫(kù),具體工作內(nèi)容如下:第一,針對(duì)有向圖k頂點(diǎn)導(dǎo)出子圖問題,本文提出了新算法——基于DNA粘貼模型的有向圖k頂點(diǎn)導(dǎo)出子圖算法。首先,粘貼模型提供的幾種基本操作,可作為新算法調(diào)用的基本函數(shù);其次,采用循環(huán)型程序結(jié)構(gòu),把上述基本函數(shù)按照一定的邏輯方式組織起來(lái)形成k頂點(diǎn)導(dǎo)出子圖的粘貼算法;最后,讀取生化反應(yīng)結(jié)果,即可獲得有向圖的k頂點(diǎn)導(dǎo)出子圖。通過仿真實(shí)驗(yàn)結(jié)果,證明了該DNA算法比經(jīng)典算法更加節(jié)省子圖生成時(shí)間。第二,針對(duì)有向圖k頂點(diǎn)關(guān)聯(lián)關(guān)系問題,本文提出了新算法——基于DNA粘貼模型的有向圖k頂點(diǎn)關(guān)聯(lián)關(guān)系算法。首先,把粘貼模型的基本標(biāo)準(zhǔn)生化操作作為可調(diào)用的基本函數(shù);其次,依據(jù)關(guān)聯(lián)關(guān)系的不同定義給出了4種相關(guān)聯(lián)的子算法,以判定單個(gè)頂點(diǎn)單條邊是否存在關(guān)聯(lián)關(guān)系;然后,將上述子算法和基本函數(shù)按照一定的邏輯方式組織起來(lái),即構(gòu)成有向圖k頂點(diǎn)關(guān)聯(lián)關(guān)系的粘貼算法;最后,運(yùn)行新算法,讀取生化反應(yīng)結(jié)果,便可獲得有向圖k頂點(diǎn)的關(guān)聯(lián)邊集。第三,針對(duì)之前的賦權(quán)算法功能單一,解決問題范圍較小的缺陷,本文給出了改進(jìn)算法——基于DNA粘貼模型的賦權(quán)問題的改進(jìn)算法。首先,把粘貼模型的標(biāo)準(zhǔn)生化元操作作為可調(diào)用的基本函數(shù);其次,把上述基本函數(shù)依照特定的邏輯模式組織起來(lái),以實(shí)現(xiàn)算法的不同功能;最后,運(yùn)行新算法,依需求讀取相應(yīng)的生化反應(yīng)結(jié)果,即可獲得賦權(quán)算法對(duì)應(yīng)功能的結(jié)果。
【學(xué)位授予單位】：鄭州大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2018
【分類號(hào)】：TP384
【圖文】：

DNA分子的平面結(jié)構(gòu)和立體結(jié)構(gòu)示意圖

有向圖G1

【相似文獻(xiàn)】

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

1 盧雪;陳蓉;杜鳳;唐卓;;一種利用活性炭提取中藥材DNA的方法[J];天然產(chǎn)物研究與開發(fā);年期

2 張志霞;高莉;劉倩倩;曹素娟;蘭利瓊;卿人韋;;適用于流式細(xì)胞術(shù)的三角褐指藻核DNA染色方法[J];應(yīng)用與環(huán)境生物學(xué)報(bào);年期

3 朱爽;陳閃沖;李奇威;黃曉瑩;章衛(wèi)民;吳光明;高曉霞;;基于DNA條形碼的三種沉香屬物種鑒定研究[J];中藥材;2018年05期

4 李萌;李翔;龐曉明;李穎岳;;珍稀樹種廟臺(tái)槭不同組織DNA高效提取方法分析[J];分子植物育種;年期

5 張仲豪;楊程;童珊珊;鄧家彬;高剛;張利;楊瑞武;;雪膽屬植物DNA條形碼的鑒定分析[J];分子植物育種;年期

6 郝雅賓;張愛菊;劉金殿;顧志敏;;環(huán)境DNA技術(shù)在魚類資源研究中的應(yīng)用[J];生物技術(shù)通報(bào);年期

7 梅瑜;邱道壽;肖深根;彭淼;陳棟;;篩選金線蓮種質(zhì)資源的通用DNA條形碼序列及鑒定其混偽品[J];分子植物育種;年期

8 荊禮;蘇航;睢博文;張鶴;潘黛安;齊濱;;DNA條形碼分子鑒定在動(dòng)物藥中的研究進(jìn)展[J];中國(guó)中藥雜志;年期

9 李文送;;DNA甲基化及其生物學(xué)功能[J];生物學(xué)教學(xué);2014年09期

10 劉慶華;茹慧香;;“DNA是主要的遺傳物質(zhì)”教學(xué)設(shè)計(jì)[J];中學(xué)生物教學(xué);2016年07期

相關(guān)會(huì)議論文 前10條

1 劉冰;王旭;趙夢(mèng)真;晁潔;樊春海;;基于DNA折紙術(shù)的納米金棒精密修飾[A];中國(guó)化學(xué)會(huì)第30屆學(xué)術(shù)年會(huì)摘要集-第二十八分會(huì)：化學(xué)生物學(xué)[C];2016年

2 劉冬生;李闖;程恩雋;邢永政;金娟;;DNA超分子水凝膠及其應(yīng)用[A];中國(guó)化學(xué)會(huì)第30屆學(xué)術(shù)年會(huì)摘要集-第二十四分會(huì)：超分子組裝與軟物質(zhì)材料[C];2016年

3 Kaiying Cheng;Hong Xu;Xuanyi Chen;Liangyan Wang;Bing Tian;Ye Zhao;Yuejin Hua;;Structural basis for DNA 5′-end resection by RecJ[A];第五屆中國(guó)結(jié)構(gòu)生物學(xué)學(xué)術(shù)討論會(huì)摘要集[C];2016年

4 陳南迪;覃詩(shī)雅;羊小海;王青;翦立新;王柯敏;;“傳感-治療”的DNA納米裝置在協(xié)同殺傷循環(huán)腫瘤細(xì)胞的應(yīng)用[A];中國(guó)化學(xué)會(huì)第30屆學(xué)術(shù)年會(huì)摘要集-第三十八分會(huì)：納米生物效應(yīng)與納米藥物化學(xué)[C];2016年

5 劉曄華;陳錦艷;江雁;張堅(jiān)磊;穆紅;;磁珠法提取金黃色葡萄球菌基因組DNA的評(píng)價(jià)[A];第七屆中國(guó)臨床微生物學(xué)大會(huì)暨微生物學(xué)與免疫學(xué)論壇論文匯編[C];2016年

6 譚磊;孫悅;周湘;劉偉;;多頭蚴核糖體DNA及線粒體DNA多態(tài)性研究[A];中國(guó)畜牧獸醫(yī)學(xué)會(huì)獸醫(yī)寄生蟲學(xué)分會(huì)第十三次學(xué)術(shù)研討會(huì)論文集[C];2015年

7 葉俏;沈潔;嚴(yán)婷婷;王宙政;;原發(fā)性干燥綜合征患者血漿循環(huán)DNA與疾病活動(dòng)相關(guān)性研究[A];2015年浙江省風(fēng)濕病學(xué)學(xué)術(shù)年會(huì)論文匯編[C];2015年

8 周嘉嘉;FriederikeSchmid;;計(jì)算模擬研究DNA和聚電解質(zhì)的結(jié)合[A];2015年全國(guó)高分子學(xué)術(shù)論文報(bào)告會(huì)論文摘要集——主題E 高分子理論計(jì)算模擬[C];2015年

9 Yuan Zhang;Yanlong Chen;Gaigai Xu;Chen Lan;Shaige Xia;Wenjie Zhao;Shusheng Zhang;;Endogenous DNA adducts method establishment and Human Biomonitoring[A];河南省化學(xué)會(huì)2016年學(xué)術(shù)年會(huì)論文摘要集[C];2016年

10 孫覓;辛麗斐;劉宏;;基于濃差電池原理高靈敏檢測(cè)DNA的傳感器[A];中國(guó)化學(xué)會(huì)第30屆學(xué)術(shù)年會(huì)摘要集-第四分會(huì)：生物分析和生物傳感[C];2016年

相關(guān)重要報(bào)紙文章 前10條

1 本報(bào)記者 辛明;鄧亞軍：災(zāi)難現(xiàn)場(chǎng)的DNA斗士[N];中國(guó)青年報(bào);2011年

2 本報(bào)記者 歐陽(yáng)曉紅　韓宋輝;“可怕”的友邦DNA 267億港元凈利從何而來(lái)[N];經(jīng)濟(jì)觀察報(bào);2015年

3 本報(bào)記者 陸成寬;DNA到底能不能預(yù)測(cè)外貌[N];科技日?qǐng)?bào);2018年

4 陸成寬;DNA到底能不能預(yù)測(cè)外貌[N];科學(xué)導(dǎo)報(bào);2018年

5 記者 劉霞;人體細(xì)胞內(nèi)存在全新DNA結(jié)構(gòu)[N];科技日?qǐng)?bào);2018年

6 強(qiáng)天林 王佳樂;DNA存儲(chǔ)技術(shù)：掌握信息控制權(quán)的利器[N];解放軍報(bào);2018年

7 柯文;人體細(xì)胞內(nèi)存在全新DNA結(jié)構(gòu)[N];江蘇科技報(bào);2018年

8 本報(bào)記者 秦珍子;是不是另一半，DNA說(shuō)了算？[N];中國(guó)青年報(bào);2014年

9 本報(bào)記者 梁國(guó)勝;“1000萬(wàn)”破解企業(yè)家身上的理想DNA[N];中國(guó)青年報(bào);2007年

10 記者 聶翠蓉;DNA開關(guān)能調(diào)控單個(gè)分子內(nèi)電流[N];科技日?qǐng)?bào);2017年

相關(guān)博士學(xué)位論文 前10條

1 王文娟;非天然核苷酸的組裝及其DNA鏈的結(jié)構(gòu)性能研究[D];山東師范大學(xué);2018年

2 石元元;豬繁殖與呼吸綜合征病毒通過DNA甲基化限制IRF3上調(diào)表達(dá)的機(jī)制及其在先天性抗病毒免疫中的作用[D];中國(guó)農(nóng)業(yè)科學(xué)院;2017年

3 滕翠娟;單分子技術(shù)研究Sso7d與DNA的相互作用[D];中國(guó)科學(xué)院大學(xué)(中國(guó)科學(xué)院物理研究所);2018年

4 付一本;DNA聚合酶Ⅰ和兩個(gè)kinesin耦合體系的動(dòng)力學(xué)研究[D];中國(guó)科學(xué)院大學(xué)(中國(guó)科學(xué)院物理研究所);2018年

5 王一舟;DNA及染色質(zhì)高級(jí)結(jié)構(gòu)的單分子研究[D];中國(guó)科學(xué)院大學(xué)(中國(guó)科學(xué)院物理研究所);2018年

6 孫月瑩;基于恒溫指數(shù)擴(kuò)增技術(shù)高靈敏度檢測(cè)mRNA及DNA甲基化[D];陜西師范大學(xué);2018年

7 田茜;黃單胞菌屬DNA條形碼篩選及其重要致病變種檢測(cè)技術(shù)研究[D];中國(guó)農(nóng)業(yè)科學(xué)院;2018年

8 范景榮;P450酶與底物及轉(zhuǎn)錄因子TcaR與DNA作用機(jī)制的分子動(dòng)力學(xué)模擬研究[D];吉林大學(xué);2018年

9 王倩倩;雙加氧酶Tet對(duì)DNA甲基化修飾的影響及相關(guān)調(diào)控機(jī)制研究[D];中國(guó)農(nóng)業(yè)大學(xué);2018年

10 鄭心如;DNA雙鏈斷裂修復(fù)調(diào)控蛋白篩選及調(diào)控機(jī)制研究[D];廈門大學(xué);2017年

相關(guān)碩士學(xué)位論文 前10條

1 張勁蕾;水相中DNA催化C-C鍵形成研究[D];陜西師范大學(xué);2018年

2 廖晶;DNA在牛奶加工貯藏過程中變化規(guī)律研究及其在摻假鑒別中的應(yīng)用[D];陜西師范大學(xué);2018年

3 董長(zhǎng)江;BTF與BACH1相互作用共同參與DNA損傷修復(fù)[D];上海師范大學(xué);2018年

4 何暮春;頭足類DNA甲基化水平及其動(dòng)態(tài)變化規(guī)律[D];浙江海洋大學(xué);2018年

5 任明;細(xì)胞內(nèi)尿嘧啶-DNA糖基化酶的超靈敏檢測(cè)研究[D];山東師范大學(xué);2018年

6 鄭悅;黃色粘球菌生物被膜中胞外DNA的整合機(jī)制與生物學(xué)功能[D];山東大學(xué);2018年

7 朱小靜;長(zhǎng)江河口大型底棲動(dòng)物及游泳動(dòng)物DNA條形碼研究[D];華東師范大學(xué);2018年

8 光天磊;單鏈端粒DNA的溶液行為研究[D];中國(guó)科學(xué)技術(shù)大學(xué);2018年

9 辜凌云;環(huán)境因素及幾何受限對(duì)DNA凝聚影響的模擬研究[D];貴州師范大學(xué);2018年

10 馬詩(shī)詩(shī);基于熒光標(biāo)記DNA與聚合物納米材料相互作用的神經(jīng)退行性疾病相關(guān)靶標(biāo)分析方法研究[D];華東師范大學(xué);2018年

本文編號(hào)：2742872