彭 源， 石曉龍

(1.華中科技大學 人工智能與自動化學院， 湖北 武漢 430074; 2.廣州大學 計算科技研究院, 廣東 廣州 510006)

計算機科學技術(shù)在飛速發(fā)展的同時，信息量的增長速度也不容小覷.根據(jù)Stasista公司的統(tǒng)計，到2025年全球信息的總量將達到2018年的5倍.現(xiàn)在的存儲介質(zhì)如硬盤和硅制半導(dǎo)體的增長速度遠遠沒有達到信息量的增長速度[1-3]，因此，尋找下一代信息存儲介質(zhì)迫在眉睫.

脫氧核糖核酸(DNA)作為遺傳信息的載體，具有存儲密度大、并行性較高及低能耗等好處，是一種天然的數(shù)據(jù)存儲介質(zhì)[4].隨著第二代DNA測序技術(shù)的出現(xiàn)，結(jié)合人工合成技術(shù)，研究人員期望用DNA作為下一代數(shù)據(jù)存儲介質(zhì).

近年來DNA存儲技術(shù)逐漸成為研究人員關(guān)注的焦點[5].哈佛大學醫(yī)學院的Church團隊在2012年首次將650 kb的一本圖書存儲在DNA上[6]，實現(xiàn)了體外DNA的數(shù)據(jù)存儲，在國際尚屬首次，五年后利用大腸桿菌DNA存儲了一段視頻文件[7]， 實現(xiàn)了DNA數(shù)據(jù)的快速復(fù)制.同年，哥倫比亞大學和紐約基因組中心的研究人員發(fā)明了一種DNA噴泉系統(tǒng)，該系統(tǒng)在達到較高的香農(nóng)信息量的同時，還可以有較高的魯棒性[8].2018年，Organick等[9]提出一種編碼方法，該方法顯著減少了測序冗余，并實現(xiàn)了文件的隨機訪問.微軟計劃于2020年在數(shù)據(jù)中心建立基于DNA的數(shù)據(jù)存儲系統(tǒng).DNA存儲取得革命性進展的同時還存在難題需要攻克.

本文研究一種基于混沌分組編碼的DNA存儲技術(shù)，該方法具備一定的抗數(shù)據(jù)損壞的穩(wěn)健性，具有較高的數(shù)據(jù)存儲容量，并縮短編碼時間，提高存儲性能.

1 方法設(shè)計與原理

基于混沌分組碼的DNA存儲技術(shù)步驟如圖1所示，先將待存儲的文件壓縮為二進制文件，隨后對二進制文件進行編碼使其變?yōu)楹蠥TCG四種核苷酸的DNA序列.在序列兩端加入DNA擴增所需的引物片段和底物片段，隨后將這些堿基序列合成為DNA片段，這樣就完成了信息的存儲.在進行信息讀取時，為了獲得多段相同的DNA，對DNA庫進行聚合酶鏈反應(yīng)技術(shù)(PCR)進行擴增，再對DNA序列進行測序，然后解碼恢復(fù)所存儲的信息.

整個存儲技術(shù)中關(guān)鍵部分為DNA編碼部分，該部分主要分為編碼和篩選兩個環(huán)節(jié).

1.1 編碼

本文編碼部分分為兩個步驟，第一步將二進制文件進行LT編碼得到中間數(shù)據(jù)，然后將中間數(shù)據(jù)進行混沌分組編碼，進行混亂和擴散.因為DNA鏈的生化特性，不能含有較長的均聚物長度以及需要穩(wěn)定的GC含量.混沌分組編碼的混亂和擴散特性剛好可以降低均聚物長度，以及穩(wěn)定GC含量，這樣可以降低程序運行時間以及提升DNA存儲的正確性.

首先，將二進制文件預(yù)處理為一系列一定長度的非重疊段，然后，迭代計算三個步驟，即Luby變換、混亂擴散和篩選.Luby變換為噴泉碼奠定了基礎(chǔ).基本上，它通過使用魯棒孤波分布從文件中選擇隨機片段并將其異或變?yōu)樾聰?shù)據(jù)，這樣將二進制數(shù)據(jù)打包為任意數(shù)量的短消息(小滴).流程如圖2所示.小滴包含兩條信息：保存數(shù)據(jù)異或過程結(jié)果和固定長度的短種子.該種子對應(yīng)于液滴創(chuàng)建過程中變換的隨機數(shù)生成器的狀態(tài)，并允許解碼器算法推斷液滴中各段的身份.從理論上講只要液滴的累積大小略大于原始文件的大小，就可以使用高效算法，通過收集液滴的任何子集來逆向Luby變換.本算法在每次迭代中利用一輪計算來創(chuàng)建單個液滴.

圖2 Luby變換流程圖Fig.2 Flowchort of Luby transformation

下面利用混沌分組編碼來對單個液滴進行混亂擴散重排，使單個液滴轉(zhuǎn)化堿基序列的GC含量穩(wěn)定以及不含有較長的均聚物長度，滿足DNA的生化特性.利用logistic映射，本文提出一種基于Feistel結(jié)構(gòu)的混沌分組密碼.記Bi為長度8字節(jié)64位的小液滴，即Bi是一個長為8字節(jié)xi,0，xi,1，xi,2，xi,3，xi,4，xi,5，xi,6，xi,7的分組，Bi=xi,0xi,1xi,2xi,3xi,4xi,5xi,6xi,7.作用過程由k輪相同計算循環(huán)作用于同一個明文分組構(gòu)成，其變換為

xi，n+1=xi-1，n⊕fn-1[xi-1,1,…,xi-1,n-1,zi-1,n-1,z].

其中，i表示當前是循環(huán)次數(shù)i=1,…,k.n=1,…,8,f0=z,z是密鑰，為簡化計算,密鑰取相同值，其流程如圖3所示.

圖3 混沌分組編碼流程圖Fig.3 Flowchart of chaotic block coding

函數(shù)f1,…,f7的形式為fj=fj(x1,…,xj,z),其中,j=1,…,7,f是由logistic映射產(chǎn)生的一個函數(shù).函數(shù)的輸出xk,0xk,1xk,2xk,3xk,4xk,5xk,6xk,7是下一輪函數(shù)的輸入.所以，k輪的輸出xk,0xk,1xk,2xk,3xk,4xk,5xk,6xk,7長度為8字節(jié)64位的密文分組，長度與明文分組相同.本文的函數(shù)fj=g(x1⊕x2⊕…⊕xj⊕z),其中,g是通過離散化具有混合和擴散的非線性logistic映射.

(1)改變logistic映射的系數(shù)，使其輸入輸出值在0到256之間.

(2)離散化標準化后的logistic映射.

DNA存儲技術(shù)中的信息在生成DNA鏈，以及DNA鏈復(fù)制，和DNA測序等眾多過程中，堿基極易發(fā)生替換、丟失等問題，這樣在DNA信息解碼時，因為某個堿基的錯誤而導(dǎo)致信息解碼錯誤，進而數(shù)據(jù)恢復(fù)出錯.為了保證DNA存儲數(shù)據(jù)的正確性，加入糾錯碼尤為重要.RS(Reed-Solomon)糾錯碼因為其性能優(yōu)良，被廣泛應(yīng)用于DNA存儲技術(shù)中，確保信息存儲的正確性.

1.2 篩選

與計算機和手機等基于信息論信道通信過程不同的是，DNA存儲技術(shù)過程中生成的DNA序列需要滿足一定的生化特性.在雙鏈DNA中，如果其中胞嘧啶C，鳥嘌呤G的含量越高，決定雙鏈DNA穩(wěn)定性的氫鍵越多.DNA越穩(wěn)定則測序時需要的條件越高.因此，為了降低DNA測序的條件，需要將DNA序列中的胞嘧啶C和鳥嘌呤G控制在一定范圍.研究發(fā)現(xiàn)均聚物長度也是引起DNA合成，及測序錯誤的一個重要原因.所以為了確保DNA合成和測序時的準確性，除了引入RS糾錯碼外還需對候選堿基序列進行胞嘧啶C，鳥嘌呤G含量和均聚物長度過濾.

本文選取DNA堿基序列中GC含量在45%～55%之間，以及最長均聚物長度不超過3的序列進行DNA存儲.流程如圖4所示.對不滿足條件的堿基序列去除重新計算，滿足條件的堿基序列保留生成DNA序列.

圖4 篩選流程Fig.4 Screening plan process

2 實驗結(jié)果及分析

實驗過程：本文對一張12 KB的圖片進行壓縮后得到的10 KB壓縮文件作為本文DNA存儲技術(shù)的輸入，后經(jīng)編碼、篩選后生成堿基序列實現(xiàn)DNA儲存.為了全方位評價本算法的優(yōu)越性，加入了近年來主流的DNA[4-10]存儲方案進行對比實驗.對比結(jié)果如表1所示.

表1 不同存儲技術(shù)對比實驗結(jié)果Table 1 Performance of different storage plans

從表1可以看出，本文提出的方法具有1.57位/nt的信息密度，并且DNA存儲的信息中冗余信息占比較低，并可以將信息還原，可以看出本方案的各項評價指標皆優(yōu)于其他方案，與DNA噴泉方案相同，故更詳細地對比這兩種方案.

本文在DNA噴泉碼的基礎(chǔ)上對生成的中間文件進行混沌編碼，使其GC含量穩(wěn)定并使均聚物長度降低.為了對比的效果更加明顯，本文固定信息冗余量為0.1.統(tǒng)計編碼堿基序列需要嘗試的次數(shù)，在設(shè)定最長均聚物長度不超過3的條件下對比結(jié)果如圖5(a)所示，可以看出，本算法具有一定的混亂和擴散特性，編碼嘗試的次數(shù)降低了20%.圖5(b)表示均聚物長度不超過4的編碼嘗試次數(shù)，可以看出編碼嘗試的次數(shù)主要與最長均聚物長度有關(guān).本文提出的DNA存儲技術(shù)方案可以有效降低編碼所需嘗試次數(shù)，增加編碼成功率.

圖5 DNA噴泉與本文編碼次數(shù)Fig.5 DNA fountain and the coding times of this artide

與DNA噴泉碼相比，本文提出的方案在相同條件下可以降低編碼嘗試的次數(shù)，提升編碼成功率，并具有相同的信息密度.

3 結(jié) 論

本文提出一種基于混沌分組編碼的DNA存儲技術(shù)，在DNA噴泉碼的基礎(chǔ)上將混沌分組編碼對原文的混亂與擴散性應(yīng)用于中間文件中，克服生成的DNA序列中GC含量差別較大以及均聚物長度過長的問題.實驗使用壓縮的圖片驗證提出方案的編碼效率及編碼成功率，同時與DNA噴泉系統(tǒng)進行對比.實驗結(jié)果說明，所提方案在不影響DNA恢復(fù)準確率的情況下，編碼嘗試次數(shù)減少，提升了編碼成功率.