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

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

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

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