DNA存儲(chǔ)中的編碼技術(shù)

畢 昆，顧萬(wàn)君，陸祖宏

(生物電子學(xué)國(guó)家重點(diǎn)實(shí)驗(yàn)室(東南大學(xué)，生物科學(xué)與醫(yī)學(xué)工程學(xué)院)，南京 210096)

全球數(shù)據(jù)信息總量將由2018年的30 ZB增長(zhǎng)至2025年的163 ZB, 該趨勢(shì)將很快超過(guò)現(xiàn)有硬盤等存儲(chǔ)介質(zhì)的承受能力。脫氧核糖核酸(Deoxyribonucleic Acid, DNA)數(shù)據(jù)存儲(chǔ)技術(shù)開辟了一種新的存儲(chǔ)模式, 其發(fā)展對(duì)于節(jié)省存儲(chǔ)能源及推進(jìn)大數(shù)據(jù)存儲(chǔ)發(fā)展有著重要作用。利用DNA分子進(jìn)行信息存取的想法早在60年代就已出現(xiàn)，由于DNA信息的讀寫較為困難，直到1988年才開始出現(xiàn)利用DNA保存少量信息的實(shí)驗(yàn)性工作，信息量極小，缺乏實(shí)際應(yīng)用。隨著二代測(cè)序技術(shù)的發(fā)展，出現(xiàn)了真正具有突破性進(jìn)展的DNA存儲(chǔ)工作。2012年，哈佛醫(yī)學(xué)院的Church團(tuán)隊(duì)通過(guò)在DNA中存儲(chǔ)650 KB的數(shù)據(jù)，第一次以體外存儲(chǔ)方式實(shí)現(xiàn)了較大數(shù)據(jù)的DNA存儲(chǔ)，實(shí)現(xiàn)了DNA存儲(chǔ)的實(shí)際應(yīng)用[1]。之后DNA數(shù)據(jù)存儲(chǔ)逐漸成為全球研究的熱點(diǎn)，包括哈佛大學(xué)、哥倫比亞大學(xué)、微軟研究院、華盛頓大學(xué)和劍橋大學(xué)等國(guó)內(nèi)外多家研究機(jī)構(gòu)均展開對(duì)DNA存儲(chǔ)的研究，并取得一定的進(jìn)展，但仍有許多難題需要攻克。

DNA是一種天然的信息存儲(chǔ)介質(zhì)，DNA具有存儲(chǔ)密度高、存儲(chǔ)時(shí)間長(zhǎng)、損耗率低等特點(diǎn)，在傳統(tǒng)存儲(chǔ)方式不能滿足信息增長(zhǎng)的需求時(shí)，DNA數(shù)據(jù)存儲(chǔ)技術(shù)逐漸成為生物信息領(lǐng)域的研究熱點(diǎn)。DNA存儲(chǔ)是將數(shù)據(jù)通過(guò)DNA編碼算法轉(zhuǎn)換為DNA分子鏈中不同堿基的序列信息并存儲(chǔ)于相應(yīng)的存儲(chǔ)載體，需要時(shí)通過(guò)特定的DNA解碼算法進(jìn)行讀取操作，重新生成原始數(shù)據(jù)。DNA存儲(chǔ)最明顯的優(yōu)勢(shì)是存儲(chǔ)量巨大，1 kg的DNA可以存儲(chǔ)全世界所有的信息，同時(shí)具有安全性高、存儲(chǔ)時(shí)間長(zhǎng)、保存穩(wěn)定等優(yōu)點(diǎn)。

DNA編碼是DNA存儲(chǔ)中的關(guān)鍵技術(shù), 它的目的是用盡可能少的堿基序列無(wú)錯(cuò)的存儲(chǔ)數(shù)據(jù)信息。DNA編碼的結(jié)果直接影響存儲(chǔ)性能的優(yōu)劣和數(shù)據(jù)讀寫的完整。整個(gè)DNA存儲(chǔ)編碼過(guò)程包括壓縮(盡可能少的占用空間)、糾錯(cuò)(無(wú)錯(cuò)存儲(chǔ))和轉(zhuǎn)換(數(shù)字信息轉(zhuǎn)為堿基序列)3部分組成。其中轉(zhuǎn)換為DNA存儲(chǔ)編碼的核心，壓縮、糾錯(cuò)早期研究中涉及較少[2]，但在近年的研究中已成為必須步驟[3-5]，有效的提高了存儲(chǔ)密度和準(zhǔn)確性。本文主要對(duì)DNA存儲(chǔ)中的編碼技術(shù)進(jìn)行綜述。

1 DNA存儲(chǔ)的發(fā)展

隨著信息技術(shù)的飛速發(fā)展，數(shù)據(jù)信息的含量呈指數(shù)級(jí)增長(zhǎng)，預(yù)計(jì)到2025年，全球數(shù)據(jù)信息總量將達(dá)到163 ZB, 約相當(dāng)于87.5億張2 TB常用硬盤，這一數(shù)據(jù)增長(zhǎng)趨勢(shì)將很快超過(guò)現(xiàn)有硬盤等存儲(chǔ)介質(zhì)的承受能力[2]。而且現(xiàn)階段使用的主要存儲(chǔ)方式包括磁帶、硬盤驅(qū)動(dòng)器、藍(lán)光存儲(chǔ)器和閃存等，都存在有效存儲(chǔ)時(shí)間短、數(shù)據(jù)易丟失缺損、能源消耗大、維護(hù)成本高以及污染環(huán)境等缺陷弊端[5-8]。因此尋求一種新的數(shù)據(jù)存儲(chǔ)介質(zhì)勢(shì)在必行，而DNA數(shù)據(jù)存儲(chǔ)技術(shù)開辟了一種新的存儲(chǔ)模式, 其發(fā)展對(duì)于節(jié)省存儲(chǔ)能源及推進(jìn)大數(shù)據(jù)存儲(chǔ)發(fā)展有著重要作用。

DNA是一種天然的信息存儲(chǔ)介質(zhì)，保證生物體內(nèi)海量遺傳信息安全的存儲(chǔ)和一代代穩(wěn)定的復(fù)制遺傳，作為已知最密集、穩(wěn)定的數(shù)據(jù)存儲(chǔ)介質(zhì)之一，DNA具有存儲(chǔ)密度高、存儲(chǔ)時(shí)間長(zhǎng)、能量消耗低、并行存取性好，損耗率低和兼容性強(qiáng)等特點(diǎn)[9]。1 g的DNA可存儲(chǔ)455 EB信息, 4 g DNA即可存儲(chǔ)全球一年產(chǎn)生的信息量，而1 kg的DNA可以存儲(chǔ)人類所有的信息[10]。DNA單位體積的存儲(chǔ)密度是硬盤和存儲(chǔ)器的106倍, 是閃存的103倍，DNA存儲(chǔ)時(shí)長(zhǎng)至少為硬盤、閃存的10倍。同時(shí), 它還可以通過(guò)聚合酶鏈反應(yīng)較容易地實(shí)現(xiàn)擴(kuò)增以獲取所需數(shù)量的拷貝副本。DNA作為最穩(wěn)定的儲(chǔ)存設(shè)備之一, 對(duì)于外部環(huán)境, 如高溫、震蕩等具有極強(qiáng)的抗干擾能力。即使經(jīng)歷數(shù)千年自然環(huán)境的考驗(yàn)，DNA信息依舊能夠被有效地讀取[8-9]。研究表明在-5 ℃的條件下，DNA每6.8×106年只降解1 bp[11]。由于DNA可隱匿在任何生物體當(dāng)中，肉眼難以察覺，其又具有超高的安全性能。表1列舉了DNA和傳統(tǒng)數(shù)據(jù)存儲(chǔ)介質(zhì)各種性能的比較。所有傳統(tǒng)的數(shù)據(jù)存儲(chǔ)媒體(DVD、軟盤、CD、磁帶等)在幾年內(nèi)就會(huì)開始失去完整性。相比之下，DNA作為數(shù)據(jù)存儲(chǔ)介質(zhì)的壽命要長(zhǎng)得多，而且很容易通過(guò)聚合酶鏈反應(yīng)技術(shù)(PCR，一種可對(duì)特定DNA片段進(jìn)行放大擴(kuò)增的生物技術(shù))放大，從而獲得所需的拷貝數(shù)。因此，有研究者認(rèn)為一旦未來(lái)發(fā)生全球?yàn)?zāi)難，DNA將能夠作為一本 “啟示錄”記載所有人類的文明[12]。此外，DNA存儲(chǔ)與現(xiàn)有的計(jì)算機(jī)存儲(chǔ)有共同之處：①類似的編解碼方式對(duì)存儲(chǔ)信息進(jìn)行寫入和讀取；②存儲(chǔ)的信息是可定位、識(shí)別和還原的；③為了確保信息的正確性和存儲(chǔ)效率，均可引入壓縮碼、糾錯(cuò)碼等不同的數(shù)學(xué)算法?；谝陨咸攸c(diǎn)，DNA數(shù)據(jù)存儲(chǔ)技術(shù)應(yīng)運(yùn)而生。

表1 傳統(tǒng)存儲(chǔ)設(shè)備與DNA存儲(chǔ)的性能參數(shù)Table 1 Performance parameters of traditional storage device and DNA storage

DNA數(shù)據(jù)存儲(chǔ)技術(shù)作為下一代存儲(chǔ)技術(shù)的熱門，尤其是作為生物和信息等學(xué)科深度交叉發(fā)展的新技術(shù)，仍然有許多難題需要攻克。當(dāng)前階段首先要解決的就是高存儲(chǔ)成本，存儲(chǔ)1 MB的數(shù)據(jù)大約需要2 000-3 000美元，遠(yuǎn)遠(yuǎn)高于目前的硬盤存儲(chǔ)成本，很難進(jìn)入實(shí)際應(yīng)用階段；其次是DNA存儲(chǔ)中的DNA序列合成和測(cè)序耗時(shí)太長(zhǎng)，由此導(dǎo)致數(shù)據(jù)讀取和寫入需要至少以小時(shí)為單位，讀寫效率遠(yuǎn)低于現(xiàn)有硅基存儲(chǔ)設(shè)備。除了上述兩個(gè)核心難題外，仍有其他多個(gè)難題需要解決，DNA存儲(chǔ)的錯(cuò)誤率較高、冗余較大，主要是DNA合成、存儲(chǔ)、測(cè)序技術(shù)的限制；現(xiàn)有DNA存儲(chǔ)編解碼算法來(lái)自計(jì)算機(jī)領(lǐng)域的簡(jiǎn)單改變和應(yīng)用，與DNA存儲(chǔ)所需的生化技術(shù)不完全適應(yīng)，存在不穩(wěn)定性和高錯(cuò)誤率；DNA數(shù)據(jù)實(shí)現(xiàn)隨機(jī)讀取較為困難，為了讀取某一部分?jǐn)?shù)據(jù)，需要將整個(gè)DNA庫(kù)中的序列測(cè)序解嗎；將大數(shù)據(jù)轉(zhuǎn)換為DNA堿基序列需要消耗大量計(jì)算資源等。

DNA存儲(chǔ)技術(shù)優(yōu)勢(shì)明顯，需要解決的難題也較多，但DNA數(shù)據(jù)存儲(chǔ)技術(shù)是生物、信息等多學(xué)科交叉發(fā)展的成果，各個(gè)研究團(tuán)隊(duì)乃至科技巨頭紛紛進(jìn)入這一領(lǐng)域[13]，最近5年DNA存儲(chǔ)發(fā)展逐漸被眾多的研究者和企業(yè)關(guān)注。2012年，哈佛醫(yī)學(xué)院的Church團(tuán)隊(duì)通過(guò)在DNA中存儲(chǔ)650 KB的數(shù)據(jù)，第一次以體外存儲(chǔ)方式實(shí)現(xiàn)了較大數(shù)據(jù)的DNA存儲(chǔ)，成為DNA信息存儲(chǔ)領(lǐng)域的一個(gè)里程碑[2]，2017年該團(tuán)隊(duì)又將更大的視頻文件存入大腸桿菌的DNA中，完成了體內(nèi)存儲(chǔ)的DNA信息存儲(chǔ)[14]；2013年歐洲生物信息研究所的Nick Goldman及其團(tuán)隊(duì)在DNA中采用三進(jìn)制編碼方式實(shí)現(xiàn)了20 MB數(shù)據(jù)可行、高容量的存儲(chǔ)，并申請(qǐng)了相關(guān)專利，這使DNA數(shù)據(jù)存儲(chǔ)又邁出了一大步，逐步開始向應(yīng)用階段邁進(jìn)[15-16]；2016年，微軟研究院和華盛頓大學(xué)聯(lián)合將200 MB數(shù)據(jù)存入DNA[17]，同時(shí)微軟計(jì)劃于2020年在數(shù)據(jù)中心建立基于DNA的數(shù)據(jù)存儲(chǔ)系統(tǒng)；2017年紐約哥倫比亞大學(xué)將噴泉碼引入DNA存儲(chǔ)，這種方法可將2.15億千兆的數(shù)據(jù)存入到僅1 g的DNA中[3]，此后多項(xiàng)DNA存儲(chǔ)研究均在此基礎(chǔ)上展開[18-19]；同年Shipman等人成功利用CRISPR Cas系統(tǒng)在DNA中存儲(chǔ)信息，并將像素值編碼到一個(gè)活細(xì)菌種群的基因組中[14]，2019年，以色列理工學(xué)院的研究團(tuán)隊(duì)在噴泉碼的基礎(chǔ)上利用復(fù)合的DNA堿基“字母”進(jìn)行編碼，從而減少合成循環(huán)數(shù)，降低合成成本，使得DNA存儲(chǔ)技術(shù)的發(fā)展有了新突破[18]。同年，Erlich等通過(guò)噴泉碼編碼后，3D打印出一只存有遺傳信息的斯坦福兔子，并實(shí)現(xiàn)了DNA藍(lán)圖的穩(wěn)定復(fù)制和遺傳[19]。DNA信息存儲(chǔ)領(lǐng)域目前已得到了各行各業(yè)的廣泛關(guān)注。

2 DNA存儲(chǔ)框架

DNA是通過(guò)A(腺嘌呤)、T(胸腺嘧啶)、C(胞嘧啶)、G(鳥嘌呤)4種脫氧核糖核苷酸連接形成的長(zhǎng)鏈分子。A與T，C與G之間兩兩配對(duì)能夠形成穩(wěn)定的雙鏈結(jié)構(gòu)，無(wú)論是單鏈DNA還是雙鏈DNA均可用于以二進(jìn)制代碼的形式存儲(chǔ)信息。圖1為DNA單鏈和雙鏈的結(jié)構(gòu)模型，其中單鏈一般用于體外合成，而雙鏈用于體內(nèi)合成。

圖1 DNA模型Fig.1 DNA model

DNA作為存儲(chǔ)設(shè)備對(duì)信息進(jìn)行保存及讀取的整體流程如圖2所示，主要框架包括3部分：編碼寫入,數(shù)據(jù)存放及解碼讀取部分。首先通過(guò)計(jì)算機(jī)算法將二進(jìn)制數(shù)據(jù)映射成堿基序列，然后合成特定序列的DNA完成編碼的寫入；隨后以溶液或干粉的形式對(duì)DNA進(jìn)行保存，外部封裝的形式多種多樣，常見的為瓶裝，也可以像斯坦福兔子[19]，3D打印為任意形狀；最后利用PCR擴(kuò)增來(lái)實(shí)現(xiàn)數(shù)據(jù)拷貝，并通過(guò)測(cè)序儀器測(cè)得目標(biāo)DNA的所有堿基序列，進(jìn)而再通過(guò)解碼轉(zhuǎn)換成二進(jìn)制數(shù)據(jù)完成數(shù)據(jù)的讀取。

受限于現(xiàn)有的DNA合成技術(shù)，編碼寫入的堿基序列會(huì)分割為長(zhǎng)度相同的短序列，一般單條序列長(zhǎng)度不超過(guò)200 bp。每一條需要合成的序列里包括引物、數(shù)據(jù)、地址位、糾錯(cuò)碼等，其中地址位用于各條序列的快速定位、拼接和查找。引物是專門設(shè)計(jì)，合成前添加到序列兩端，用于提取所需的DNA序列。糾錯(cuò)碼包括序列內(nèi)糾錯(cuò)碼和序列間糾錯(cuò)碼，如圖3所示，序列內(nèi)糾錯(cuò)碼用于糾正單條序列內(nèi)的錯(cuò)誤，序列間糾錯(cuò)碼用于糾正整條序列缺失等錯(cuò)誤。

圖2 DNA存儲(chǔ)流程圖Fig.2 flow chart of DNA storage

圖3 DNA存儲(chǔ)序列示意圖Fig.3 Schematic diagram of DNA sequences

DNA編碼是通過(guò)一定的算法和映射關(guān)系，將需要存儲(chǔ)的信息以碼流的形式轉(zhuǎn)變成DNA堿基序列的排列組合，從而實(shí)現(xiàn)文件信息與DNA之間的關(guān)系轉(zhuǎn)換。不同的DNA模型適用于不同類型信息的存儲(chǔ)，雖然模型之間存在差別，但DNA信息編碼寫入的流程大致都是一致的，主要包括數(shù)據(jù)壓縮-引入糾錯(cuò)-轉(zhuǎn)換為堿基序列的過(guò)程，整體的流程如圖4所示。

DNA解碼是由存儲(chǔ)的DNA序列中獲取數(shù)字信息的過(guò)程，是編碼的逆過(guò)程。整個(gè)DNA解碼的讀取過(guò)程如圖5所示。解碼前通過(guò)PCR擴(kuò)增得到多個(gè)DNA拷貝，從而不會(huì)對(duì)原始存儲(chǔ)造成影響。再對(duì)拷貝進(jìn)行DNA測(cè)序，獲取DNA序列的堿基排列方式。獲取堿基序列后對(duì)序列糾錯(cuò)、去冗余、解碼，讀取原始數(shù)據(jù)。

圖4 DNA編碼流程Fig.4 Encoding process in DNA storage

圖5 DNA解碼流程Fig.5 Decoding process in DNA storage

3 DNA存儲(chǔ)編碼技術(shù)

3.1 轉(zhuǎn)換

現(xiàn)有的數(shù)據(jù)均可以二進(jìn)制形式存儲(chǔ)在計(jì)算機(jī)硬盤等硅存儲(chǔ)介質(zhì)內(nèi)，因此將信息存儲(chǔ)至DNA中實(shí)質(zhì)上就是將二進(jìn)制數(shù)據(jù)編碼為堿基序列存入DNA。堿基序列是由A, T, C和G 4種堿基組成, 根據(jù)DNA的組成及結(jié)構(gòu), 基本的DNA存儲(chǔ)編碼模型有3種:二進(jìn)制模型[2]、三進(jìn)制模型[16]和四進(jìn)制模型[3]。在此基礎(chǔ)上，還有混合模型(如二、四進(jìn)制組合在一起等)[20]、含簡(jiǎn)并堿基的模型[18]等。

3.1.1 二進(jìn)制模型

二進(jìn)制模型是DNA存儲(chǔ)中最簡(jiǎn)單的模型，根據(jù)二進(jìn)制0、1和四種堿基A、T、C、G之間的可能映射關(guān)系，將任意兩種堿基定義為0，另兩個(gè)則為1，共有6種可能的組合形式。早期的DNA存儲(chǔ)研究采用這種轉(zhuǎn)換模型進(jìn)行數(shù)據(jù)編碼。Church[2]在2012年按A或G等于0, C或T等于1，使用二進(jìn)制模型將0.65 MB的數(shù)據(jù)編碼成長(zhǎng)度為單條長(zhǎng)度159 nt的8.8 MB的DNA序列。鑒于大量的數(shù)字?jǐn)?shù)據(jù)成功地存儲(chǔ)在DNA中，這被認(rèn)為是一項(xiàng)里程碑式的研究，同時(shí)也證明了基于DNA的數(shù)據(jù)存儲(chǔ)在應(yīng)對(duì)信息爆炸挑戰(zhàn)方面的潛力。

這種二進(jìn)制模型相對(duì)簡(jiǎn)單, 具有較高的堿基變換靈活性，能夠較好地控制GC含量、均聚物數(shù)量等條件, 降低DNA合成難度，減少合成和測(cè)序錯(cuò)誤。但就編碼效率而言, 該編碼方案通過(guò)將每個(gè)二進(jìn)制碼轉(zhuǎn)換成1堿基，犧牲了信息密度，相同長(zhǎng)度的堿基序列二進(jìn)制模型能存儲(chǔ)的信息量較少, 編碼效率不高。在后續(xù)的研究中，已經(jīng)很少采用二進(jìn)制模型，研究者通過(guò)開發(fā)和引入新的編碼方式，在保證可靠性的前提下，進(jìn)一步提升存儲(chǔ)密度。

3.1.2 三進(jìn)制模型

三進(jìn)制編碼模型是將數(shù)據(jù)轉(zhuǎn)換為三進(jìn)制，以0、1、2的形式表示，接著按對(duì)應(yīng)關(guān)系轉(zhuǎn)換為相應(yīng)堿基，如圖6所示。這種對(duì)應(yīng)關(guān)系下，下一位堿基的確定依賴于前一位堿基，而堿基與數(shù)據(jù)之間沒有明確的對(duì)應(yīng)映射關(guān)系。三進(jìn)制模型由Goldman[16]團(tuán)隊(duì)在2013年提出，并在國(guó)內(nèi)外均申請(qǐng)了相關(guān)專利[15, 21]。

三進(jìn)制模型相較于二進(jìn)制模型，提高了存儲(chǔ)密度，也能夠控制GC含量、均聚物數(shù)量等條件，降低后期合成難度。但三進(jìn)制模型也沒有充分利用DNA的存儲(chǔ)能力，除了Goldman團(tuán)隊(duì)外，其他研究較少采用三進(jìn)制模型。

圖6 三進(jìn)制轉(zhuǎn)換模型Fig.6 Ternary transformation model

3.1.3 四進(jìn)制模型

將堿基A, T, C, G看作0, 1, 2, 3，則DNA序列可視為天然的四進(jìn)制編碼模型。對(duì)于任意二進(jìn)制數(shù)據(jù), 將按兩位二進(jìn)制數(shù)一組就可以編碼為堿基序列。例如將二進(jìn)制數(shù)據(jù)00, 01, 10, 11編碼為A, T, C, G，即可一一對(duì)應(yīng)進(jìn)行數(shù)據(jù)編碼。這種映射關(guān)系并不唯一, 共有24種組合方案, 理論上這24種方案彼此是等價(jià)的，但考慮到實(shí)際編碼時(shí)GC含量等條件，存在部分更優(yōu)化組合方案。

四進(jìn)制模型相對(duì)于其他兩種模型存儲(chǔ)能力最強(qiáng)，理論存儲(chǔ)極限為2 bit/nt，達(dá)到了堿基序列存儲(chǔ)效率的極限。在目前以提高存儲(chǔ)密度為導(dǎo)向的研究中，四進(jìn)制模型是應(yīng)用最廣泛的DNA存儲(chǔ)轉(zhuǎn)換模型[3, 9, 18, 22]。但需要指出的是，這種模型易出現(xiàn)GC含量過(guò)高、均聚物較多等影響后續(xù)的DNA合成和測(cè)序的情況。為了克服這些情況，研究者引入糾錯(cuò)碼等冗余數(shù)據(jù)進(jìn)行數(shù)據(jù)質(zhì)量控制，實(shí)際存儲(chǔ)效率都低于理論值。

3.1.4 混合模型

二進(jìn)制模型能夠較好地控制GC含量、均聚物數(shù)量等條件, 降低DNA合成難度，減少合成和測(cè)序錯(cuò)誤；而四進(jìn)制模型理論存儲(chǔ)極限為2 bit/nt，達(dá)到了堿基序列存儲(chǔ)效率的極限。綜合兩者的優(yōu)點(diǎn)，有研究者[20]提出了混合模型，在四進(jìn)制模型的基礎(chǔ)上加入二進(jìn)制模型，在保證存儲(chǔ)效率的同時(shí)，控制合成條件，降低合成難度。如圖7所示，前三組二進(jìn)制數(shù)采用四進(jìn)制模型，最后一組二進(jìn)制數(shù)采用二進(jìn)制模型，8 bit的數(shù)據(jù)存入5個(gè)堿基之中。類似的研究還有將5 bit的數(shù)據(jù)存入3個(gè)堿基之中[23]。

混合模型基本都是以四進(jìn)制模型為主，在保證存儲(chǔ)效率的前提下，引入二進(jìn)制模型降低合成難度，也可視為四進(jìn)制模型的一個(gè)變種。在單一的四進(jìn)制模型合成困難的缺點(diǎn)沒有完全克服前，混合模型可以降低對(duì)糾錯(cuò)碼等冗余數(shù)據(jù)的需求量，從降低冗余的角度提高存儲(chǔ)密度。這種模型可以根據(jù)實(shí)際數(shù)據(jù)的情況靈活組合，在存儲(chǔ)密度和合成難度之間取得較好的平衡，是一種較為常用的模型。

圖7 混合模型示意圖Fig.7 Schematic diagram of mixture model

3.1.5 含簡(jiǎn)并堿基的模型

最新研究[18]首次在編碼階段引入簡(jiǎn)并堿基，這種復(fù)合DNA字母表是由四種DNA核苷酸按預(yù)定比例混合而成的序列中位置的表示(見圖8)。利用現(xiàn)有的DNA存儲(chǔ)技術(shù)中涉及多個(gè)相同分子的并行合成和排序所導(dǎo)致的信息冗余，用更少的合成周期來(lái)編碼數(shù)據(jù)，每單位數(shù)據(jù)使用的合成周期減少了20%。模擬編碼表明，合成周期可能減少達(dá)75%。

3.2 壓縮

壓縮的目的在于盡可能地減少數(shù)據(jù)冗余，用盡可能少的空間存儲(chǔ)盡可能多的數(shù)據(jù)，最大化的利用DNA存儲(chǔ)序列。DNA存儲(chǔ)利用目前已有的信息領(lǐng)域的編碼方法進(jìn)行數(shù)據(jù)壓縮，主要有霍夫曼編碼[15]和噴泉嗎[3]，此外還有LZMA[24]等編碼方法。其中，霍夫曼編碼是DNA存儲(chǔ)領(lǐng)域最常見的編碼方法，而噴泉碼則是可能的未來(lái)主流編碼方法。

圖8 含簡(jiǎn)并堿基模型示意圖(來(lái)自Anavy等的工作[18])Fig.8 Schematic diagram of model with degenerate bases (from work of aNavy et al[18])

3.2.1 霍夫曼編碼

霍夫曼編碼是一種由David Huffman在20世紀(jì)50年代開發(fā)的，基于最小冗余編碼的無(wú)損數(shù)據(jù)壓縮算法，廣泛應(yīng)用于數(shù)據(jù)文件壓縮。2013年，Goldman[16]首次在DNA存儲(chǔ)中采用了霍夫曼編碼，有效地將編碼潛力提高到1.58 bit/nt。二進(jìn)制數(shù)據(jù)首先由值霍夫曼編碼壓縮，然后通過(guò)三進(jìn)制模型轉(zhuǎn)換為DNA序列，將每8 bit的數(shù)據(jù)存儲(chǔ)進(jìn)5到6個(gè)堿基之中。通過(guò)霍夫曼編碼和三進(jìn)制模型，可以壓縮原始數(shù)據(jù)25%～37.5%，并避免了均聚物的產(chǎn)生?；舴蚵幋a適用于多類數(shù)據(jù)，并能取得較好的壓縮效果。

然而，在處理某些二進(jìn)制數(shù)據(jù)時(shí)，霍夫曼編碼可以控制，但不能完全避免均聚物的產(chǎn)生，也不能防止異常的GC分布。此外，霍夫曼編碼對(duì)部分?jǐn)?shù)據(jù)的壓縮效果不佳。

3.2.2 噴泉碼

噴泉碼是通信系統(tǒng)中廣泛使用的一種信息編碼方法，以其魯棒性和高效率而著稱。噴泉碼又稱無(wú)速率擦除碼，其存儲(chǔ)的數(shù)據(jù)分為k個(gè)段，即資源包，可以從這些資源包派生出無(wú)限數(shù)量的編碼包。當(dāng)它返回n (n > k)個(gè)編碼包時(shí)，原始資源數(shù)據(jù)將完全恢復(fù)。在實(shí)際應(yīng)用中，只要n比k稍大一點(diǎn)，就可以獲得更好的編碼效率和信息通信的魯棒性。

在2017年，Erilich和Zielinski[3]在首次在DNA存儲(chǔ)中使用了噴泉碼，采用四進(jìn)制轉(zhuǎn)換模型，00,01,10,11分別映射到A, C, G, T。將原始的二進(jìn)制信息分割成若干小塊，這些塊是根據(jù)預(yù)先設(shè)計(jì)的偽隨機(jī)序列選擇的。然后，通過(guò)按位添加所選的帶有隨機(jī)種子的塊，并根據(jù)四進(jìn)制模型映射關(guān)系創(chuàng)建新的數(shù)據(jù)塊(見圖9)。最后進(jìn)行篩選防止單核苷酸重復(fù)和GC含量異常。該編碼方案中的引物是相關(guān)的，具有網(wǎng)格狀的拓?fù)浣Y(jié)構(gòu)，實(shí)現(xiàn)極低但必要的冗余。該研究將編碼潛力的理論極限提高到前所未有的高值1.98 bit/nt，并顯著降低了源文件無(wú)錯(cuò)誤恢復(fù)所需的冗余。此外，隨機(jī)選擇和有效性驗(yàn)證機(jī)制確保了長(zhǎng)單核苷酸均聚物不會(huì)出現(xiàn)在編碼序列中。

然而，在這種編碼方案中，編碼和解碼的復(fù)雜度與數(shù)據(jù)大小并不是線性相關(guān)的。因此，解碼可能很復(fù)雜，并且可能需要更多的資源和更長(zhǎng)的計(jì)算時(shí)間。有研究[25]認(rèn)為，盡管Erilich的文章表示丟失總包數(shù)4%不會(huì)影響原始文件的恢復(fù)，但就DNA噴泉碼的特征而言，丟失更多的包數(shù)可能會(huì)導(dǎo)致恢復(fù)完全失敗。如果最終目標(biāo)是永久存儲(chǔ)數(shù)據(jù)，則必須增加冗余的數(shù)量以確保信息的完整性。

圖9 噴泉碼編碼示意圖Fig.9 Schematic diagram of fountain code

在基于DNA的數(shù)據(jù)存儲(chǔ)和檢索中，最常見的錯(cuò)誤是由堿基突變引起的。為了解決這個(gè)問(wèn)題，大多數(shù)編碼方案都創(chuàng)建了高冗余度來(lái)進(jìn)行錯(cuò)誤糾正。然而，這些糾錯(cuò)算法需要復(fù)雜的譯碼過(guò)程和大量的計(jì)算資源。在這里，噴泉編碼方案的使用表明，它不必要使用錯(cuò)誤檢測(cè)/糾正算法，可以有效提高DNA編碼的性能。

3.2.3 其他算法

DNA存儲(chǔ)編碼中，也有研究采用其他壓縮編碼，但是相對(duì)較少，效果也一般。例如，Yim研究團(tuán)隊(duì)[24]于2012年對(duì)一張BMP圖片的二進(jìn)制碼流利用LZMA算法壓縮后存儲(chǔ)于DNA中，但該方法并不適用于高通量數(shù)據(jù), 且壓縮過(guò)程的耗時(shí)較長(zhǎng)。也有研究采用TAR和LZMA算法聯(lián)合進(jìn)行數(shù)據(jù)壓縮和DNA存儲(chǔ)[23]。

采用其他壓縮算法的DNA存儲(chǔ)研究較少，彼此之間相對(duì)孤立，也缺乏連貫性和驗(yàn)證。這些方法可能存在進(jìn)一步研究的空間，但目前尚無(wú)報(bào)道。

3.3 糾錯(cuò)

在DNA存儲(chǔ)信息的過(guò)程中, 無(wú)論是DNA編碼、合成、存儲(chǔ)，還是DNA測(cè)序、解碼, 均有可能出現(xiàn)錯(cuò)誤, 導(dǎo)致最終出現(xiàn)信息的損失。為了盡量保證信息的無(wú)錯(cuò)讀取, 在DNA存儲(chǔ)過(guò)程中引入相應(yīng)的糾錯(cuò)機(jī)制來(lái)提高存儲(chǔ)的準(zhǔn)確性。

糾錯(cuò)機(jī)制多種多樣，在合成、存儲(chǔ)和測(cè)序階段都有相應(yīng)的措施，例如可以通過(guò)提高測(cè)序深度來(lái)減少錯(cuò)誤率。但上述措施都意味著DNA存儲(chǔ)成本的上升，而在編碼階段引入糾錯(cuò)碼則是在控制成本的前提下保證準(zhǔn)確率的最有效方式。值得注意的是，糾錯(cuò)碼本身屬于冗余，糾錯(cuò)是通過(guò)引入冗余的方式提高準(zhǔn)確率，在冗余和準(zhǔn)確率之間取得平衡，是非常關(guān)鍵的一點(diǎn)。目前的DNA存儲(chǔ)中使用的糾錯(cuò)方式以RS碼為主[3, 18, 26]，少量文獻(xiàn)采用LDPC碼[24]、漢明碼[27]、前向糾錯(cuò)[22]、多倍冗余[16]、XOR計(jì)算[9]等糾錯(cuò)方式。

3.3.1 RS碼

RS碼是一種典型的線性循環(huán)碼, 即源文件編碼后向左或向右移動(dòng)后仍為有限組碼組中的一組, 它可對(duì)隨機(jī)錯(cuò)誤、突發(fā)錯(cuò)誤及二者的組合進(jìn)行糾錯(cuò)。Grass[26]在2015年年將基于有限域的RS代碼引入DNA存儲(chǔ)領(lǐng)域，特別強(qiáng)調(diào)錯(cuò)誤檢測(cè)和校正，將潛在的數(shù)據(jù)密度提高到1.78 bits/nt。該編碼方案以2字節(jié)(8×2位)的基本信息塊為基礎(chǔ)，引入一個(gè)有限域作為其元素。為了防止編碼過(guò)程中產(chǎn)生長(zhǎng)度大于3 nt的均聚物，三聯(lián)體的最后2個(gè)核苷酸是不同的，可以產(chǎn)生48個(gè)不同的三聯(lián)體。因?yàn)?7是比48小的最大質(zhì)數(shù)，所以用了GF(47)。然后將信息塊映射到GF(47)中的3部分元素，即，2562至473。該方案采用RS碼來(lái)檢測(cè)和糾正錯(cuò)誤。對(duì)GF轉(zhuǎn)碼生成的矩陣分別進(jìn)行水平方向和垂直方向的2輪RS編碼。在這項(xiàng)初步研究中，83 KB的文本數(shù)據(jù)被編碼。雖然數(shù)據(jù)量不是很大，但是引入了一種有效的糾錯(cuò)機(jī)制，大大提高了編碼和合成的效率。

RS碼能用較小的冗余恢復(fù)更多的數(shù)據(jù)信息, 此后的研究中大部分均采用RS碼作為糾錯(cuò)機(jī)制。但由于涉及有限域，其計(jì)算量較大，對(duì)大數(shù)據(jù)編碼的計(jì)算機(jī)硬件要求較高。

3.3.2 其他糾錯(cuò)機(jī)制

Goldman[16]在2013年的研究中采用四倍重疊冗余進(jìn)行糾錯(cuò)，保證存儲(chǔ)的準(zhǔn)確性，在DNA存儲(chǔ)領(lǐng)域引入糾錯(cuò)的概念。但這種糾錯(cuò)機(jī)制帶來(lái)了巨大的冗余，存儲(chǔ)密度只有0.33 bit/nt。2016年，Bornholt等人[9]利用異或(XOR)編碼原理改進(jìn)了Goldman的編碼方案，每2個(gè)原始序列，A和B，將由A?B產(chǎn)生一個(gè)冗余序列C。因此，任意2個(gè)序列(AB、AC或BC)，都可以很容易地恢復(fù)到第三個(gè)序列。這種編碼方案還根據(jù)特定數(shù)據(jù)鏈的重要程度提供了冗余的靈活性，即“可調(diào)冗余”。它將原始數(shù)據(jù)的冗余度從三倍降低到一半，存儲(chǔ)效率上升到0.88 bit/nt。

此外，Blawat[22]采用“前向糾錯(cuò)”機(jī)制，預(yù)先指定兩個(gè)參考編碼表，將一個(gè)1字節(jié)(8位)的基本信息塊分配給一個(gè)5堿基DNA序列，并交換第三個(gè)和第四個(gè)堿基，并滿足條件：前3個(gè)堿基不相同，且最后兩個(gè)堿基不相同。22 Mb的數(shù)據(jù)被成功地編碼并存儲(chǔ)，且這些數(shù)據(jù)被無(wú)錯(cuò)誤地檢索，存儲(chǔ)密度達(dá)到0.92 bit/nt。然而，這種方法不能檢測(cè)和糾正單個(gè)突變的情況。

在DNA信息存儲(chǔ)中也有研究團(tuán)隊(duì)將LDPC碼[24]、漢明碼[27]用于糾錯(cuò)環(huán)節(jié), 以防止在DNA合成及測(cè)序中出現(xiàn)隨機(jī)錯(cuò)誤, 提高文件讀取的準(zhǔn)確性。然而，雖然簡(jiǎn)單的LDPC碼可以檢測(cè)錯(cuò)誤，但它不能糾正錯(cuò)誤。此外，冗余度的增加不可避免地降低了編碼效率。

4 DNA存儲(chǔ)編碼技術(shù)的發(fā)展方向

目前為止，DNA存儲(chǔ)編碼已經(jīng)形成壓縮+糾錯(cuò)+轉(zhuǎn)換的較為穩(wěn)定的模式，其中四進(jìn)制轉(zhuǎn)換模型成為主流，在此基礎(chǔ)上，改進(jìn)的混合模型[20]、含簡(jiǎn)并堿基模型[18]等進(jìn)一步得到發(fā)展。而噴泉碼有取代霍夫曼編碼成為DNA存儲(chǔ)領(lǐng)域最常見編碼方法的趨勢(shì)。DNA存儲(chǔ)中使用的糾錯(cuò)方式仍然以RS碼為主[3, 18, 26]，沒有新的突破，其他糾錯(cuò)方式研究者較少，如表2所示。

表2 DNA存儲(chǔ)主要方案的參數(shù)Table 2 Parameters of main DNA storage schemes

DNA存儲(chǔ)編碼技術(shù)未來(lái)發(fā)展方向是比較明確的，首先是編碼算法的進(jìn)一步深化，其次是將編碼技術(shù)擴(kuò)展到DNA存儲(chǔ)的合成、測(cè)序環(huán)節(jié)，在實(shí)現(xiàn)DNA存儲(chǔ)編碼的基礎(chǔ)上，進(jìn)一步對(duì)整個(gè)存儲(chǔ)流程進(jìn)行編碼算法優(yōu)化，提高存儲(chǔ)效率和準(zhǔn)確率，降低成本和合成周期。

4.1 編碼算法

4.1.1 壓縮編碼

目前的主要研究方向仍然是將現(xiàn)有信息領(lǐng)域的算法與DNA存儲(chǔ)相結(jié)合，尋找更適合DNA的編碼方法, 盡可能充分地利用DNA存儲(chǔ)空間, 引入較少的冗余?，F(xiàn)有的壓縮方法不對(duì)數(shù)據(jù)類型進(jìn)行區(qū)分，壓縮質(zhì)量參差不齊，DNA存儲(chǔ)的成本仍居高不下，尤其是存儲(chǔ)數(shù)據(jù)規(guī)模逐漸擴(kuò)大，需要針對(duì)不同類型的數(shù)據(jù)選擇不同的壓縮方法以盡可能的提高存儲(chǔ)效率，降低成本。

4.1.2 糾錯(cuò)編碼

RS碼是現(xiàn)階段效果最好的糾錯(cuò)編碼，被大部分研究所采用，但計(jì)算量較大。RS碼的高效性在小規(guī)模數(shù)據(jù)存儲(chǔ)中被證明，未來(lái)大數(shù)據(jù)存儲(chǔ)需要有效降低RS碼的計(jì)算量，同時(shí)尋找更合適、冗余更小的糾錯(cuò)編碼。

4.1.3 轉(zhuǎn)換模型

現(xiàn)有理論存儲(chǔ)效率最高的四進(jìn)制模型為2 bit/nt，但因?yàn)榈刂反a、糾錯(cuò)碼等冗余的引入，存儲(chǔ)效率無(wú)法達(dá)到理論值。未來(lái)需要考慮在四進(jìn)制模型的框架內(nèi)合理設(shè)置冗余，做到冗余與糾錯(cuò)之間的平衡。此外，簡(jiǎn)并堿基在編碼中的引入，雖然不是真正意義上的突破了2 bit/nt的限制，但在目前合成階段存在大量相同序列的前提下，引入的簡(jiǎn)并堿基越多，存儲(chǔ)效率越高，現(xiàn)階段達(dá)到了2.5 bit/nt，理論可達(dá)到10 bit/nt[18]。但這也對(duì)編碼和合成技術(shù)提出了較高的要求。

4.2 合成與測(cè)序編碼優(yōu)化算法

既往算法研究主要在滿足低均聚物和適當(dāng)?shù)腉C含量的基礎(chǔ)上展開，沒有更進(jìn)一步考慮更多的DNA特性和生化技術(shù)特點(diǎn)，缺乏對(duì)DNA存儲(chǔ)中合成與測(cè)序錯(cuò)誤的優(yōu)化算法，僅靠編碼階段的糾錯(cuò)機(jī)制被動(dòng)減少錯(cuò)誤率。究其原因，DNA存儲(chǔ)尚在初級(jí)研究階段，現(xiàn)階段研究者主要關(guān)注高密度數(shù)據(jù)存儲(chǔ)的實(shí)現(xiàn)，對(duì)合成與測(cè)序中的錯(cuò)誤通過(guò)增加冗余的簡(jiǎn)單處理方式進(jìn)行被動(dòng)控制和糾正，效果不穩(wěn)定，成本和周期也大幅上升。

DNA存儲(chǔ)載體一般為溶液或干粉，進(jìn)行信息提取時(shí)則必須為溶液形式，受合成技術(shù)與成本的影響，不同DNA存儲(chǔ)樣品的單位密度存在差異。密度高，包含的DNA序列多，信息存儲(chǔ)完整，但重復(fù)冗余較大，合成周期長(zhǎng)，成本高昂；密度低，DNA序列少，冗余小，成本和合成周期低，但信息可能丟失。既往研究發(fā)現(xiàn)，完全相同的數(shù)據(jù)和算法的重復(fù)性實(shí)驗(yàn)中，由于合成技術(shù)的可能差異，會(huì)導(dǎo)致密度發(fā)生變化，進(jìn)而影響編解碼參數(shù)設(shè)置，并導(dǎo)致信息冗余或者丟失。

目前的DNA存儲(chǔ)算法無(wú)法對(duì)這些基于DNA特性的問(wèn)題進(jìn)行調(diào)控優(yōu)化，而只能通過(guò)合成前添加冗余糾錯(cuò)的方式進(jìn)行被動(dòng)校正，糾錯(cuò)碼屬于冗余，糾錯(cuò)是通過(guò)引入冗余的方式提高準(zhǔn)確率，在冗余和準(zhǔn)確率之間取得平衡，是非常關(guān)鍵的一點(diǎn)，但現(xiàn)有的糾錯(cuò)機(jī)制無(wú)法做到這一點(diǎn)，再加上各種合成與測(cè)序技術(shù)的不同，相關(guān)研究重復(fù)性較差，使得錯(cuò)誤率的控制機(jī)制完全屬于經(jīng)驗(yàn)判斷，不穩(wěn)定性很高。

綜上所述，現(xiàn)有DNA存儲(chǔ)算法研究主要集中在輸入文件轉(zhuǎn)換為DNA序列的編碼部分，對(duì)于合成與測(cè)序階段的錯(cuò)誤缺乏客觀的識(shí)別、控制、優(yōu)化和評(píng)價(jià)的模型算法，單靠前期的糾錯(cuò)碼進(jìn)行錯(cuò)誤校正，只能被動(dòng)的等待結(jié)果輸出，對(duì)合成與測(cè)序過(guò)程無(wú)法進(jìn)行基于生物學(xué)特性的優(yōu)化評(píng)價(jià)，且目前的DNA合成和測(cè)序技術(shù)主要為生物學(xué)服務(wù)，對(duì)于數(shù)字信息編碼而成的DNA序列的效果并不穩(wěn)定，仍有待探索。通過(guò)算法優(yōu)化模型，提高合成和測(cè)序的成功率是必須解決的問(wèn)題。

4.3 DNA存儲(chǔ)的計(jì)算機(jī)適配系統(tǒng)

現(xiàn)階段DNA存儲(chǔ)算法主要來(lái)自計(jì)算機(jī)等領(lǐng)域的簡(jiǎn)單改編，研究重點(diǎn)均集中在編碼技術(shù)上，較少涉及之后的合成、存儲(chǔ)、測(cè)序和解碼等步驟，且相關(guān)研究是零散的，不成體系的，基本只包括了將輸入文件轉(zhuǎn)換為DNA合成序列這部分，甚至只關(guān)注其中的壓縮、轉(zhuǎn)換或糾錯(cuò)等某一步驟。究其原因，DNA存儲(chǔ)尚在初級(jí)研究階段，現(xiàn)階段研究者主要關(guān)注高密度數(shù)據(jù)存儲(chǔ)，而對(duì)解碼技術(shù)的要求較低，只需保證數(shù)據(jù)可以完整讀取即可。

由于缺乏完整的DNA存儲(chǔ)計(jì)算機(jī)適配系統(tǒng)，不同的研究采用的編解碼算法、合成、測(cè)序技術(shù)和存儲(chǔ)條件各不相同，相應(yīng)的軟件適配系統(tǒng)差異很大。DNA存儲(chǔ)的計(jì)算機(jī)適配系統(tǒng)應(yīng)考慮存儲(chǔ)效率、魯棒性、準(zhǔn)確率和成本等多方面因素，目前算法較多的只考慮存儲(chǔ)效率和準(zhǔn)確率，且不同的合成與測(cè)序技術(shù)對(duì)DNA存儲(chǔ)效果影響很大，缺乏一個(gè)全面的、具有一致性的軟件適配系統(tǒng)，導(dǎo)致研究的可重復(fù)性不高，難以重復(fù)實(shí)現(xiàn)。

針對(duì)上述問(wèn)題，在目前編碼研究基礎(chǔ)上，需要首先確定DNA存儲(chǔ)的完整流程，并實(shí)現(xiàn)模塊化，并延伸至DNA存儲(chǔ)流程的每一步，針對(duì)DNA存儲(chǔ)編碼、合成、測(cè)序、解碼等主要階段分別進(jìn)行算法設(shè)計(jì)和優(yōu)化，建立完整的DNA存儲(chǔ)算法適配系統(tǒng)，有效提高存儲(chǔ)效率和準(zhǔn)確率，降低合成周期和成本，增強(qiáng)研究的可重復(fù)性和實(shí)際應(yīng)用性。

5 總 結(jié)

DNA存儲(chǔ)編碼算法經(jīng)過(guò)近十年的發(fā)展，壓縮以霍夫曼編碼和噴泉碼為主，糾錯(cuò)主要為RS碼，轉(zhuǎn)換大多使用四進(jìn)制模型，整體編碼模式已經(jīng)形成，未來(lái)將逐步向大規(guī)模編碼存儲(chǔ)和商業(yè)化應(yīng)用發(fā)展。但現(xiàn)有的DNA存儲(chǔ)的編解碼算法主要來(lái)自計(jì)算機(jī)等領(lǐng)域的簡(jiǎn)單改編，缺乏對(duì)DNA分子特性的研究和匹配，適應(yīng)性和可靠性不高，基于現(xiàn)有算法編碼得到的DNA合成序列，直接用于DNA存儲(chǔ)合成較不穩(wěn)定，錯(cuò)誤率較高。未來(lái)需要考慮更多的DNA特性和生化技術(shù)特點(diǎn)，通過(guò)建立參數(shù)優(yōu)化模型對(duì)DNA合成序列實(shí)現(xiàn)優(yōu)化，在目前編碼研究基礎(chǔ)上，針對(duì)DNA存儲(chǔ)編碼、合成、測(cè)序、解碼、評(píng)價(jià)等主要階段分別進(jìn)行算法設(shè)計(jì)和優(yōu)化，建立完整的DNA存儲(chǔ)算法適配系統(tǒng)，為大規(guī)模的DNA存儲(chǔ)研究奠定基礎(chǔ)。