彭 源， 石曉龍

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

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

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

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

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

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

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

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

1.1 編碼

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

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

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

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

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

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

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

函數(shù)f1,…,f7的形式為fj=fj(x1,…,xj,z),其中,j=1,…,7,f是由logistic映射產(chǎn)生的一個(gè)函數(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是通過離散化具有混合和擴(kuò)散的非線性logistic映射.

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

(2)離散化標(biāo)準(zhǔn)化后的logistic映射.

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

1.2 篩選

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

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

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

2 實(shí)驗(yàn)結(jié)果及分析

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

表1 不同存儲(chǔ)技術(shù)對(duì)比實(shí)驗(yàn)結(jié)果Table 1 Performance of different storage plans

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

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

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

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

3 結(jié) 論

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