基于糾錯碼編碼理論的ＤＮＡ編碼研究
2008-12-31 00:00:00王子成肖建華強小利
計算機應用研究 2008年11期
(華中科技大學 控制科學與工程系 圖像信息處理與智能控制教育部重點實驗室， 武漢 430074)
摘要：作為一種新的計算模式，DNA計算有著強大的計算能力，編碼問題在DNA計算中占據重要的位置，有效的編碼設計能夠提高DNA計算的可靠性?；诩m錯碼編碼理論，提出了一種新的DNA編碼方法，該方法可以找出具有一定長度且滿足漢明距離約束的DNA編碼序列。最后，給出了該算法的仿真，結果表明了該算法的有效性。
關鍵詞：DNA計算; DNA編碼; 糾錯碼
中圖分類號：TP3015文獻標志碼：A
文章編號：1001-3695(2008)11-3262-02
DNA word coding based on error correct code
WANG Zi-cheng， XIAO Jian-hua， QIANG Xiao-li
(Key Laboratory of Image Processing Intelligent Control， Dept. of Control Science Engineering， Huazhong University of Science Technology， Wuhan 430074， China )
Abstract:As a new computational paradigm， DNA computing has the powerful computational capacity. Encoding DNA sequence plays an important role in successful DNA computation， and good DNA sequences may significantly improve the reliability of DNA computing. Based on the error-correct coding theory， this paper proposed a method to design DNA encoding sequences which satisfied given length and Hamming distance constraint. The simulated results show the effectiveness of presented algorithm.
Key words：DNA computing; DNA coding; error-correcting coding
0引言
1994年，Adleman[1]首次提出了DNA計算模式，將DNA計算用于解決七個頂點有向圖的Halmilton路徑問題，利用DNA計算模型解決NP完全問題引起了學術界的廣泛關注。1995年，Lipton[2]通過構造一個接觸網絡，將3-SAT問題映射為接觸網絡G的起點和終點的所有Halmilton路，解決了小規模的3-SAT問題。2001年，以色列科學家Benenson[3]研制出由DNA分子和生物酶構成的生物二狀態有窮自動機，該機器是一種可編程的、可用于解決組合優化問題的有窮自動機。國內學者[4，5]提出了基于表面的 DNA算法用于求解圖的最大團問題和圖的著色問題。2002年，Adleman研究小組采用一種新的方法解決了20個變量的3-SAT問題[6]，該方法是迄今為止采用DNA計算所能夠解決的最復雜的NP問題。
DNA計算過程分為三個階段：a)編碼階段。利用堿基互補配對的特點以及生化反應的特性進行編碼，保證生化反應按實驗方案順利進行。b)計算階段，即生化反應階段。通過生化操作，如PCR擴增，酶的連接、剪切等操作，以輸入的DNA序列為原料進行反應，將反應生成的某種能夠提取的DNA序列作為輸出。c)檢測階段。解的檢測采用PCR擴增、凝膠電泳等生物操作技術，對生化反應所生成的DNA序列進行復制、擴增、篩選、分離，最終提取問題的解所對應的DNA序列，排除非解，從而得到問題的解。DNA計算中，編碼問題是一個十分重要而且非常困難的問題。編碼的目的是讓每個信息被編碼后在生化反應中能夠被惟一地識別，避免生化反應中出現假陽性和假陰性情況，以保證DNA計算能夠可靠地進行。DNA計算中編碼的約束條件包括組合約束條件和熱力學約束條件。組合約束條件是個很復雜的問題，近年來，國際上有很多學者對DNA編碼算法進行了研究。例如簡單隨機生成算法思想簡單、容易實現、產生的序列隨機性強，但同時也容易造成長時間遲滯的現象。2003年Feldkamp等人[7]提出基于這種惟一子串約束的最小長度子串的評價方法，這種惟一子鏈的算法在序列庫搜索時會迅速收斂。采用該方法可以迅速排除不符合條件的解。2003年，Tulpan等人[8]提出了隨機局部搜索(stochastic local search，SLS）算法。上述問題都歸結為解決組合優化問題。本文采用糾錯碼編碼原理，提出一種基于RS糾錯碼的DNA編碼方法。
1糾錯碼編碼
糾錯碼是指對信息進行編碼并將信息通過信道傳輸時，在傳輸過程中發生錯誤后能在信道的接收端發現錯誤并能夠進行自行糾正的編碼。只用于發現錯誤的編碼通常稱之為檢錯碼。在進行信息傳輸時，為了提高編碼信息的抗干擾能力，從而保證編碼信息具有較強的檢錯或糾錯能力，需對原始信息編碼字增加多余的碼元，以擴大編碼字之間的差別，即增加編碼字之間的漢明距離，要把原碼字按某種規則轉換成具有一定剩余度的編碼字，同時令每個編碼字的編碼之間保留某種關系。關系的建立稱為編碼。編碼字到達接收端后，可以根據編碼規則是否滿足以判定有無錯誤。當不能滿足時，為進行信息傳輸，能夠按照某種規則確定錯誤發生的位置并予以糾正。本文利用線性糾錯碼的一些性質，找出了一組滿足一定漢明距離以及附加約束條件的DNA編碼，首先給出有關定義如下。
定義1兩個DNA序列之間，對應位取值不同的個數稱為它們之間的漢明距離。
定義2 [9][n，k，d]線性分組碼是GF(q)上的n維線性空間Vn中的k維子空間Vn，k。其中：n是碼長；k是信息組碼長；d是線性分組碼之間的最小漢明距離。
定義3[10]給定任一有限域GF(q)及其擴域GF(q′)。其中：q是素數或是素數的冪；m為某一正整數。若碼元取自GF(q)上的循環碼，它的生成多項式g(x)的根集合R中含有以下δ-1個連續根R{am0，am0+1，…，am0+δ-2}時，則由生成的循環碼稱為q進制BCH碼。
定義4[9]GF(q)(q≠2)上，碼長N=q-1的本原BCH碼稱為RS碼。
2基于糾錯碼編碼理論的DNA編碼
根據糾錯碼原理，采用糾錯碼編碼，首先構造一個糾錯碼生成矩陣或者生成多項式，由這些生成多項式可以生成滿足一定漢明距離的糾錯碼，實際上這樣的糾錯碼在構成一個線性子空間；然后將二進制編碼轉換成四進制編碼，再將四進制編碼轉換成含有A、C、G、T的DNA序列。算法1是產生給定長度為n，漢明距離為d的DNA編碼序列的集合。
算法1
a）根據DNA序列長度n和漢明距離d，構造一個糾錯碼生成矩陣或者生成多項式;
b）將k位信息位所構成的所有可能的k個維向量與生成矩陣相乘得到二進制的編碼集合;
c)將二進制編碼轉換成四進制編碼;
d)將G代替0、A代替1、C代替2、T代替3，得到DNA序列。
算法2是在滿足給定約束條件下的流程。
算法2
a)輸入相關參數，DNA序列的長度n，漢明距離d，利用算法1產生滿足漢明約束條件的DNA序列的集合，令此集合為S，設集合M=，集合中編碼DNA序列的初始序數i=1。
b)將集合S中的第i個序列記為r，計算r的GC含量。
c)如果r的GC含量滿足要求，則轉到d)；否則，轉到h)。
d)如果r有回文結構， 轉到h)；否則，轉到e)。
e)如果r中含有不需要的特殊結構(如AAAA子序列)，轉到h)；否則，轉到f)。
f)計算r的Tm值， 如果Tm不滿足要求， 轉到h)；否則，轉到g)。
g)將r添加到集合M。
h)令i=i+1，如果i＞｜S｜， 結束，集合M中為所求的DNA序列；否則，轉到b)。
RS碼是一種特殊的BCH碼。本文研究了基于RS糾錯碼編碼技術的DNA編碼，即在編碼過程中采用了可以生成RS糾錯碼的生成矩陣或者生成多項式。采用RS糾錯碼進行編碼的優點是：
a)糾錯碼理論比較成熟，便于找到生成矩陣或者生成多項式。
b)運算時間復雜度比較低，找到生成矩陣或者生成多項式后，計算編碼運算量小，只需要用一個低維空間的向量與生成矩陣相乘。
基于RS糾錯碼編碼技術的DNA編碼算法步驟見引理1和算法3、4。由引理1生成最小距離為δ，q進制RS碼；算法3生成最小距離為d， 長為(m+1)/2」(2m-1)(m≥2)的四進制RS碼；算法4生成滿足一定漢明距離d，長為(m+1)/2」(2m-1)(m≥2)的DNA序列。
引理1設α是GF(q)(q=2m，m≥2)上的本原域元素，長為N=q-1，距離為d的RS碼的生成多項式為g(x)=(x-αm0)(x-αm0+1）…(x-αm0+δ-2)，通常取 m0=1。此時g(x)=(x-α)(x-α2)…(x-αδ-1)生成一個[q-1，q-δ]進制RS碼。
算法3
a)利用引理1生成最小漢明距離為d，碼長為q-1=2m-1（m≥2）的q進制RS碼。
b)用二進制符號代替q進制中的每一個符號。此時q=2m進制的[q-1，q-δ]RS碼轉換成了[m(q-1)，mK，d]二進制分組碼。
c)[m(q-1)，mK，d]二進制分組碼變成四進制碼，其長度為(m+1)/2」(2m-1)(m≥2)。
算法4
a)利用算法3生成最小距離為d，長為(m+1)/2」(2m-1)(m≥2)的四進制編碼。
b)用A代替0、C代替1、G代替2、T代替3，便得到相應DNA編碼字序列的集合。
3實例
本文采用上述算法，構造了長度為7，漢明距離為3的編碼字序列。編碼字序列中GC含量大于50%，沒有回文現象，且編碼字序列中不出現子串為AAA的DNA編碼字序列。
a)構造一個[14，5，6]碼的生成矩陣：
G=10001011000101
01001100100110001001100100110001111000111100000001111111
b)由此生成矩陣得到糾錯碼集合，如表1所示。
c)將二進制編碼轉換成DNA序列，如表2所示。
d)去掉不滿足約束條件的DNA編碼序列(GC含量大于50%，沒有回文序列，且沒有子串AAA)后得到DNA編碼序列，如表3所示。可以檢驗，表3中所有的DNA編碼滿足長度為7，GC含量小于50%，沒有出現回文序列，且編碼DNA序列沒有出現子串AAA， 并且任意兩條碼之間的漢明距離不小于3。
4結束語
本文基于糾錯碼編碼理論，設計了用于編碼DNA序列的算法，利用該算法生成了滿足一定約束條件的DNA編碼序列。所生成的這種編碼能夠很好地應用于DNA計算，提高了DNA計算的可靠性，所設計的DNA編碼序列適用于對漢明距離要求高，并且對DNA編碼序列需求數量不大的情況。通過對編碼結果進行分析，基于RS糾錯碼的編碼方法能到很快找到滿足漢明距離約束的編碼序列集合，這組編碼字集合中排除了特定的DNA編碼序列，時間復雜度為O（n)，并具有編碼效率高的優點。
參考文獻：
［1］ADLEMAN L. Molecular computation of solutions to combinatorial problems[J].Science，1994，266(5187)：1021-1024.
[2]LIPTON R J. DNA solution of hard computation problems[J].Science， 1995，268(4)：542-545.
[3]BENESON Y. Programmable and autonomous computing machine made of biomolecules[J]. Nature，2001，414(22)：430-434.
[4]PAN Lin-qiang， XU Jin， LIU Ya-chun. A surface-based DNA algorithm for the maximal clique problem[J].Chinese Journal of Electronics，2002，11(2):469-471.
[5]PAN Lin-qiang， XU Jin， LIU Ya-chun. A surface-based DNA algorithm for the minimal vertex problem[J]. Progress in Natural Science， 2003，13(1):81-84.
[6]BRAICH R S， CHELYAPOV N，JOHNSON C，et al. Solution of a 20-variable 3-SAT problem on a DNA computer[J].Science，2002，296(5567)：499-502.
[7]FELDKAMP U，RAUHE H，BANZHAF W. Software tools for DNA sequence design[J].Genetic Programming and Evolvable Machines，2003，4(2):153-170.
[8]TULPAN D， HOOS H， CONDON A. Stochastic local search algorithms for DNA word design[C]//Proc ofthe 8th DNA-based Computers. 2002：229-241.
[9]王新梅， 肖國鎮. 糾錯碼原理與方法（修訂版）[M].西安：西安電子科技大學出版社， 2001.
[10]LIU Qing-hua. DNA computation on surfaces[J].Nature，2000，403(6766)：175-179.
[11]FRUTOS A G， LIU Qing-hua， THIEL A J，et al. Demonstration of a word design strategy for DNA computing on surface[J]. Nucleic Acids Research，1997，25(23): 4748-4757.
