三元DNA Golay碼的構造*

馮 賓,白姍姍

(安徽理工大學理學院,安徽淮南232007)

三元DNA Golay碼的構造*

馮 賓1,白姍姍2

(安徽理工大學理學院,安徽淮南232007)

Golay碼是一類比較好的線性碼,并且是僅有的兩類達到Hamming界的完全碼中的一類。而DNA編碼是近幾年糾錯碼界研究的熱點,且比傳統(tǒng)糾錯碼具有更新更好的一些性質。它是DNA計算中的重點和難點問題,且是核心問題,所以合理的DNA編碼可以提高實驗的穩(wěn)定性和正確性,從而確保DNA計算的成功率。所以,用傳統(tǒng)糾錯碼構造DNA糾錯碼是一項有意義的工作。本文給出了利用三元Golay碼G12和G11構造三元DNA Golay碼D12和D11的方法,并給出了這兩種三元DNA Golay碼的性質。

線性碼 Golay碼 DNA Golay碼

0 引 言

近年來[1],不少學者發(fā)展了很多MP(Matching Pursuits)算法的改進算法,均具有一定的實際意義。其中,遺傳算法(GA,Genetic Algorithm)模擬了達爾文的遺傳選擇和自然淘汰的生物進化過程的計算模型,是一種通過模擬自然進化過程搜索最優(yōu)解的方法。類似遺傳算法的理念,DNA計算是生物學、數(shù)學和計算機的交叉性研究領域。由于DNA計算是以組成生命的遺傳物質DNA分子進行編碼并處理信息的,因此編碼問題隨著DNA計算的研究引起研究人員的注意。對DNA編碼的研究在最近幾年已有了很大的進展:20世紀90年代,DNA碼字間相似度的編碼方法,DNA編碼的定義以及對DNA雜交錯誤的防錯編碼策略的分析分別由Baum和Garzon提出;21世紀初,DNA碼字間相似度的計算方法和形式評價準則,模板編碼方法,單模板編碼方法,三字母表的編碼策略,隨機搜索優(yōu)碼方法分別由Feldkamp,Frutos,Arita,Braich,Tulpan提出,并得到了質量較好的DNA碼;Feldkamp等人給出了另一種定義序列間相似度的方法,用來衡量兩個編碼間的相似度,并給出了一個基于前綴樹的編碼構造算法,即最大相同子串。在此基礎上,又開發(fā)出了根據(jù)各種要求生成編碼的軟件包。Braich等人提出了可以降低DNA分子生產二級結構的三字母表編碼策略。在這方面,數(shù)學家也做了一些研究工作并發(fā)現(xiàn):最大相同子串的約束性非常強,其編碼數(shù)量隨編碼長度的增加變化不大。Suyama等人提出了正交編碼數(shù)的概念,此外,Adleman和Winfree的研究小組也有針對具體問題而進行的編碼方法研究。應該說,編碼問題的研究,不僅對DNA計算,而且在生物芯片的設計及其它方面也有廣闊的應用。

另外,王淑棟[2]等人在2009年提出:利用二元Golay碼G24=[24,12,8]和G23=[23,12,7]構造二元DNA Golay碼D24和D23的設計思路,并定義了DNA碼字重量和Watson Crick Hamming距離。本文借助此結論的原理,對二元DNA Golay碼的構造進行了推廣:利用三元Golay碼G12=[12,6,6]和G11=[11,6,5]構造三元DNA Golay碼D12和D11,并給出了它們的幾個特殊性質。

1 基本概念

1.1 DNA計算中的編碼問題

雜交反應[3]是DNA計算中最核心的反應,并且它的可靠性依賴于DNA分子間的特異性雜交。從而,DNA計算的效率和最終輸出結果的可靠性依賴于雜交反應的效率和精度。研究表明,DNA分子間的雜交反應在完全互補配對和不完全互補配對的情況下都有可能出現(xiàn)錯誤。研究人員把這兩種錯誤雜交分別稱為假陰性和假陽性,由于種種因素的影響,完全互補的DNA分子沒有雜交成功,此種錯誤被稱為假陰性;在合適的條件下,不完全互補的DNA分子也有可能雜交形成雙鏈分子,此種錯誤稱為假陽性。導致假陰性發(fā)生的主要原因是反應條件以及生化操作的失誤;而導致假陽性發(fā)生的主要原因是雜交的兩個DNA分子在很大程度上是互補的。編碼研究的主要目的就是為了能夠最大限度地對實際生化反應過程中的DNA序列進行唯一且準確的識別,使得計算過程能夠盡量按照模型的方向進行。從而,為了達到DNA計算能夠順利且可靠地進行下去的目的,我們必須想辦法,盡可能地降低錯誤雜交發(fā)生的概率。

下面給出DNA計算中編碼問題的定義:

在字母集合{A,G,C,T}上,長度為n的DNA分子一共有4n個,它們組成的集合記為S。取k為正整數(shù),令ζ是評價編碼性質的準則(Hamming距離、最小相同子序列數(shù)目、移位距離等),則所有滿足公式ζ(si,sj)≥k(其中si和sj是S中的兩個編碼)的DNA分子構成集合C,C是S的子集。

取矩陣G=(gij)m×n(gij=0,1,2,3),A= (a1,a2,…,am)∈{0,1,2,3}m,對A的編碼過程W= A×G,其中A為信息元,W稱為碼元,G為線性碼的生成矩陣。對于信息元A可以取4m個行向量,因此生成4m組碼元,即4m個長度為n的線性碼。當G為生成矩陣的標準形式時,生成的線性碼為系統(tǒng)碼,系統(tǒng)碼是線性碼中最重要的一類碼。

1.2 DNA計算編碼的約束條件

有很多因素(化學自由能變化、生物酶、解鏈溫度、DNA分子的生物特異性等)都會影響DNA的計算,序列編碼的約束條件就是由這些因素所決定的。在前人研究成果的基礎上,對影響DNA計算的這些因素進行綜合考慮,給出了DNA計算的線性編碼約束條件。

用來編碼信息元的序列稱為字序列(word sequences),表示為xi;與之互補的序列稱為探針序列(probe sequences),表示為x′i。DNA分子中堿基A與堿基T互補配對,堿基G和堿基C互補配對。連接字序列與字序列所組成的序列叫做庫序列(Library sequences),表示為Ln=〈xi,xj,…,xk〉,由庫序列構成的集合{Ln}與待計算問題的全體基本解空間相對應。

約束DNA計算編碼的條件:DNA計算的編碼是在字母表∑={A,T,C}上進行的。

在三字母表{A,T,C}上進行編碼,編碼序列中就沒有了堿基G,從而探針序列中就沒有了堿基C。這樣以來,庫序列與庫序列之間、探針序列與探針序列之間就不會完全匹配;探針序列要正確匹配,只能選擇和庫序列進行匹配;并且各編碼序列自身與自身之間很難形成“發(fā)夾結構1”,同時編碼序列與其他編碼序列之間形成“發(fā)夾結構2”的可能性也大大地減小了。采用這種編碼方法也使編碼序列的生物特異性得到明顯提高,但它也是有缺點的,由于可用字母由4個變到3個,使得可用編碼的數(shù)量急劇減少,可用編碼的數(shù)量從4l個下降到了3l個(l表示字序列的長度),字序列長度為15時,整整下降了兩個數(shù)量級。然而針對現(xiàn)在DNA計算的規(guī)模,利用三字母表編碼仍然是非常有效的。

1.3 線性編碼方法

目前,DNA計算中的重點和難點仍然是編碼問題。實踐已證明:利用有效的編碼設計,能夠提高DNA計算過程中的可靠性。最小Hamming距離是DNA計算編碼的重要參數(shù),它決定了編碼序列DNA分子的生物特異性,與DNA分子在雜交反應中自由能變化直接相關,是計算可靠性的重要因素。用線性碼構造滿足Hamming距離的DNA編碼是一種非常有效的方法,關鍵在于構造相應的監(jiān)督矩陣。

在DNA編碼中,用數(shù)字“0,1,2,3”來表示字母“A,T,C,G”時,就可以用四進制數(shù)序列表示DNA編碼序列,這時DNA編碼的最小Hamming距離就可用線性系統(tǒng)碼來構造。在線性碼運算中,所有的運算均是指模運算,用剩余類的代表元表示運算結果。對于四進制的線性碼,我們采用模4運算。當DNA序列用三字母表{A,T,C}進行編碼時,我們用數(shù)字“0,1,2”表示“A,T,C”,這時DNA編碼序列就變成三進制數(shù)序列,對于三進制的線性碼采用模3運算。

2 三元DNA Golay碼的構造方法

2.1 三元Golay碼的定義

線性碼[4]是糾錯碼當中的一部分(因為線性碼不僅是Fq的子集合,而且要求是Fq的線性子空間),并且多數(shù)性能良好的糾錯碼都是線性碼。Golay碼就是一類較好的線性碼,即完全線性碼(參數(shù)為[n,k,d]的q元碼叫作完全碼,是指它達到Hamming界)。

1949年,Golay發(fā)現(xiàn)了兩個完全線性碼。一個參數(shù)為[n,k,2l+1]的q元完全碼要滿足,但是滿足這個等式的n,k,d(=2l+1)和q(為素數(shù)冪)是很少的。Golay首先求出滿足這個等式的三組參數(shù)為(q,n,k,d)=(2,23,12,7), (2,90,78,5)和(3,11,6,5),并且他證明了參數(shù)為[90,78,5]的二元線性碼是不存在的。然后通過精細的組合學考慮,構作出了二元線性碼[23,12,7]和三元線性碼[11,6,5]。下面給出兩種三元Golay碼的生成方法:

(1)以矩陣

為生成陣的三元線性碼G12是參數(shù)為[n,k,d]= [12,6,6]的自對偶碼。(其中F2上6階方陣P的構作方式是:左上角的元素為0,第1行和第1列中的其他元素均為1,剩下的5階方陣P1的第1行為(01221),而其余諸行依次為第1行向右循環(huán)移位。)

(2)將G12中所有碼字去掉末位,得到的收縮碼G11是[n,k,d]=[11,6,5]的三元線性碼,并且是完全碼。

2.2 三元DNA Golay碼的構造

堿基“A,T,C”用數(shù)字“0,1,2”來表示,這樣三進制數(shù)序列就可以用來表示編碼序列。類似二元DNA Golay碼的構造方法,給出三元DNA Golay碼的構造過程:

構造映射f:G12→D12如下:在G12中任取三進制碼字x=x1x2…x12,如果xi=j,則記f(xi)∈∑j(j=0, 1,2;i=1,2,…,12)。這時x對應的三元DNA Golay碼字就是f(x),稱三元Golay碼G12在映射f下得到DNA Golay碼D12。用同樣方法能夠構造出三元DNA Golay碼D11。

對于G12(G11)中的一個三進制碼字x,它唯一的與DNA Golay碼f(x)相對應;并且對于一個DNA Golay碼字f(x)∈D12(D11),其對應的三元Golay碼字也是唯一的,因此f是一個一一映射。即每一個三元DNA Golay碼字都唯一的與一個三元Golay碼字相對應,更好地滿足了DNA計算編碼中對生物特異性的要求。并且利用三字母表{A,T,C}進行編碼時,在編碼序列中不含有堿基G,探針序列中不含有堿基C,這樣庫序列和庫序列、探針序列和探針序列之間就不可以進行完全的匹配,探針序列只可以和庫序列進行正確的匹配,比較重要的一點是:各編碼序列自身與自身之間很難形成“發(fā)夾結構”。從而,三元DNA Golay碼優(yōu)于二元DNA Golay碼。

例:取信息元A中的一些碼字a1=(020112), a2=(201210),a3=(111021),a4=(010212),則它們對應的Golay碼分別為:

從而g1,g2,g3,g4∈G12且為系統(tǒng)碼,分別唯一的對應DNA Golay碼字:

去掉碼字的最末位,得到:

它們對應的DNA Golay碼字分別為:

其對應表格如下:

信息元Golay碼DNA Golay碼收縮Golay碼收縮DNA Golay碼(020112)(020112000012)(ACATTCAAAATC)(02011200001)(ACATTCAAAAT) (201210)(201210100100)(CATCTATAATAA)(20121010010)(CATCTATAATA) (111021)(111021212200)(TTTACTCTCCAA)(11102121220)(TTTACTCTCCA) (010212)(010212020100)(ATACTCACATAA)(01021202010)(ATACTCACATA)

顯然,三元DNA Golay碼與三元Golay碼是一一對應的。

2.3 三元DNA Golay碼的性質

為了進一步討論DNA Golay碼的性質,我們定義DNA Golay碼字間的加法、減法和乘法運算如下:

定義在f的逆映射f-1下,對D12(D11)中的任意碼字x,y與G12(G11)中的碼字x′,y′唯一對應。定義x+y=f(x′+y′),x-y=f(x′-y′),x*y=f(x′×y′),其中x′+y′,x′-y′和x′×y′分別是三元域上的加法、減法和乘法運算。

三元DNA Golay碼的性質與二元DNA Golay碼的性質相類似,表示如下:

引理2.1 三元Golay碼G12和G11都是線性碼,且參數(shù)分別為[12,6,6]和[11,6,5]。

性質1 DNA Golay碼D12和D11是線性碼。

證明：在映射f-1下,任意的x,y∈D12,存在唯一的x′,y′∈G12與之對應。由引理2.1知,G12是線性碼,則有x′+y′∈G12,αx′∈G12(α∈{1,2,3})成立。從而x+y=f(x′+y′)∈D12,αx=f(αx′)∈D12,由線性碼的定義知D12是線性碼。同理可證D11也是線性碼。證畢。

引理2.2Golay碼G11是完備碼。

性質2DNA Golay碼D11是完備碼。

證明：由引理2.2知,Golay碼G11是完備碼。因為Golay碼G11中的碼字在映射f下一一對應于DNA Golay碼D11中的碼字,因此兩者是等價的,并且DNA Golay碼D11的規(guī)模等于Golay碼G11的規(guī)模,從而DNA Golay碼D11也是完備碼。

3 結 語

本文在前人研究的基礎上,首次利用三元Golay碼構造出了三元DNA Golay碼,這種碼比傳統(tǒng)糾錯碼多了新性質,并且在DNA計算中具有很好的潛在實用性;同時,對DNA計算編碼的構造方法也做了新的嘗試和有益的補充。但是,如何將這些DNA Golay碼應用到實際的DNA計算當中,還是有待解決的。所以,我們需要繼續(xù)對這些問題做深入的研究和探討。

近幾年來,在編碼理論學者的共同努力下,DNA計算編碼的構造有了很大的突破,一些新的DNA編碼相繼被構造出來。對于編碼理論學者來說,利用更加簡便快捷的方法構造出更多性能良好的DNA編碼是未來研究的重點。

[1] 高麗貞.結合遺傳算法的匹配追蹤算法的性能分析[J].通信技術,2013(08):153-155.

GAO Lizhen.Matching Pursuit Algorithm of Genetic Algorithm Combining with Analysis of the Performance[J]. Communications Technology,2013(08):153-155.

[2] 王淑棟,宋濤,李二艷.DNA Golay碼的設計與分析[J].電子學報,2009(07):1542-1545.

WANG Shudong,SONG Tao,LI Eryan.The Design and Analysis of DNA Golay Codes[A].Beijing:Acta Electronic Sinica,2009(07):1542-1545.

[3] 朱翔歐,劉文斌.DNA計算中的編碼問題[M].北京:清華大學出版社.2012:21-24.

ZHU Xiangou,LIU Wenbin.Coding Problems in DNA Computing[M].Tsing hua university press.2012:21-24.

[4] 馮克勤.糾錯碼的代數(shù)理論[M].陳朝暉.第一版.北京:清華大學出版社.2005:22-29.

FENG Keqin.Algebraic Theory of Error-Correcting Codes [M].CHEN Zhaohui.The first edition.Beijing:Tsing hua university press.2005:22-29.

FENG Bin(1986-),female,graduate student,mainly working at theory and application of error-correcting codes.

白姍姍(1989—),女,碩士研究生,主要研究方向為糾錯碼理論及應用。

BAI Shan-shan(1989-),female,graduate student,mainly working at theory and application of error-correcting codes.

Construction of Ternary DNA Golay Codes

FENG Bin1,BAI Shan-shan2
(College of Science,Anhui University of Science&Technology,Huainan Anhui 232007,China)

Golay code is a fairly good linear code and one of the only two perfect codes reaching the Hamming periphery.In recent years,DNA encoding,as a research hotspot of error-correction code,enjoys some updated and better properties than traditional encoding,and is also the key problem in DNA computing,thus reasonable DNA coding could improve the reliability and stability of experiment and ensure the successful rate of DNA computation.Obviously,the construction of DNA codes by using traditional codes is of significant importance.How to construct ternary DNA Golay codes D12and D11by using ternary Golay codes G12and G11is described and the properties of these two ternary DNA Golay codes are also given in this paper.

linear codes;Golay code;DNA Golay code

10.3969/j.issn.1002-0802.2014.10.004

TP18

A

1002-0802(2014)10-1125-05

馮 賓(1986—),女,碩士研究生,主要研究方向為糾錯碼理論及應用;

2014-06-17;

2014-08-21 Received date：2014-06-17;Revised date：2014-08-21