DNA計(jì)算編碼研究及其算法實(shí)現(xiàn).pdf

1、隨著生物技術(shù)的發(fā)展，DNA計(jì)算隨之產(chǎn)生。由于DNA計(jì)算機(jī)所具有的巨大并行性、海量存儲(chǔ)以及低能耗等優(yōu)點(diǎn)，因此將有望在某些領(lǐng)域彌補(bǔ)現(xiàn)有電子計(jì)算機(jī)的不足。本文的研究主要包括二方面的內(nèi)容：DNA計(jì)算中的編碼問(wèn)題和DNA計(jì)算實(shí)例模型研究。 編碼問(wèn)題是DNA計(jì)算的關(guān)鍵問(wèn)題，也是DNA計(jì)算中的重點(diǎn)和難點(diǎn)，目前還沒(méi)有一種通用的方法可以系統(tǒng)地解決編碼問(wèn)題。本文主要工作是在Braich等提出的DNA編碼約束條件的基礎(chǔ)上做進(jìn)一步研究，提出了一種新的

2、構(gòu)造性編碼方法——基于線性碼的DNA計(jì)算編碼算法，突破了以往的搜索式算法，該算法能快速、高效地產(chǎn)生所需的編碼，結(jié)果編碼的數(shù)量和質(zhì)量均有保障，從而解決了三字母表的DNA計(jì)算編碼問(wèn)題。 為了在已知編碼數(shù)量情況下，尋找到性能最優(yōu)地編碼參數(shù)，如碼長(zhǎng)l、最大相同子序列的長(zhǎng)度s、最小海明距離dh和GC含量等，需要對(duì)編碼的計(jì)數(shù)問(wèn)題進(jìn)行研究。目前對(duì)編碼的計(jì)數(shù)研究?jī)H局限于單個(gè)約束條件下的編碼計(jì)數(shù)，對(duì)于同時(shí)滿(mǎn)足多個(gè)約束條件的編碼計(jì)數(shù)問(wèn)題國(guó)內(nèi)外均未

3、見(jiàn)報(bào)道。本文提出了一個(gè)新的概念——約束強(qiáng)度，解決了多約束的編碼計(jì)數(shù)問(wèn)題，能有效地估算出多約束條件下的編碼數(shù)量。 在研究過(guò)程中還發(fā)現(xiàn)，搜索空間的優(yōu)化是尋找監(jiān)督矩陣的關(guān)鍵，而且滿(mǎn)足條件的監(jiān)督矩陣在搜索空間中的分布基本上是相對(duì)均勻的，監(jiān)督矩陣決定碼重分布。研究結(jié)果表明，三字母表的編碼參數(shù)一般為l=10-14、s=4-6、dh=5-6、GC含量約為1/3，可滿(mǎn)足編碼數(shù)量小于180的各種情況。 最后設(shè)計(jì)了一個(gè)編碼的應(yīng)用模型，用