DNA存儲中的糾錯方法綜述

昝鄉(xiāng)鎮(zhèn), 姚翔宇, 許 鵬, 陳智華, 謝 戀, 劉文斌*

(廣州大學(xué) a.計算科技研究院; b. 黃埔研究院, 廣東 廣州 510006)

隨著分布式、云計算和物聯(lián)網(wǎng)技術(shù)的發(fā)展，人類每天產(chǎn)生的數(shù)據(jù)總量呈現(xiàn)出指數(shù)增長的趨勢.據(jù)國際數(shù)據(jù)公司(IDC)預(yù)測，2025年，全球數(shù)據(jù)信息總量將達到175 ZB[1].傳統(tǒng)的磁、光、電等存儲技術(shù)已無法滿足未來呈指數(shù)增長趨勢的數(shù)據(jù)存儲需求[2-3].與此同時，作為生命信息存儲介質(zhì)的DNA分子在存儲容量、穩(wěn)定及能耗方面有著巨大的優(yōu)勢[4-5].據(jù)估計，DNA分子的存儲密度可達到～107GB/mm3，比傳統(tǒng)存儲介質(zhì)提高了6個數(shù)量級.正是基于上述原因，DNA分子有望成為解決海量大數(shù)據(jù)存儲困境的一種極具潛力的存儲介質(zhì)[6-7].

20世紀(jì)60年代，Wiener[8]和Neiman[9]提出了用DNA分子存儲數(shù)據(jù)的想法，標(biāo)志著DNA存儲研究的正式開始.隨著合成和測序技術(shù)的成熟與推廣，2012年，哈佛醫(yī)學(xué)院的Church等[10]第一次在體外實現(xiàn)了0.65 MB數(shù)據(jù)的DNA存儲.此后的每一年，《Nature》 《Science》等權(quán)威期刊都有相關(guān)研究成果的報道[10-14].歐美發(fā)達國家已經(jīng)將DNA存儲列入國家發(fā)展戰(zhàn)略.2020年11月，微軟公司與西部數(shù)據(jù)公司、Twist生物科技公司以及Illumina公司結(jié)成聯(lián)盟，用于推進DNA數(shù)據(jù)存儲領(lǐng)域的發(fā)展.美國半導(dǎo)體產(chǎn)業(yè)協(xié)會(SIA)發(fā)布的《半導(dǎo)體10年計劃》也將DNA數(shù)據(jù)存儲列為未來海量數(shù)據(jù)存儲的重要選項.我國兩會公布的《中華人民共和國國民經(jīng)濟和社會發(fā)展第十四個五年規(guī)劃和2035年遠景目標(biāo)綱要》也明確指出，要加快布局DNA存儲等前沿技術(shù).

然而，DNA存儲過程會不可避免地引入一些錯誤，這些錯誤對DNA數(shù)據(jù)的準(zhǔn)確恢復(fù)提出了嚴(yán)峻的挑戰(zhàn).因此，DNA存儲研究必須要解決的一個關(guān)鍵問題是如何在DNA數(shù)據(jù)恢復(fù)的過程中發(fā)現(xiàn)錯誤并糾正錯誤.本文主要介紹了DNA存儲過程中錯誤的類型及其分布復(fù)雜性，DNA存儲糾錯技術(shù)的主要進展，并對其發(fā)展趨勢進行了展望.

1 DNA存儲信道復(fù)雜性

DNA存儲過程主要包括4個步驟：將計算機數(shù)據(jù)編碼成DNA序列,合成DNA序列，PCR擴增與存儲，測序并恢復(fù)存儲數(shù)據(jù).DNA存儲主要涉及3種生物技術(shù)：DNA序列合成技術(shù)、PCR擴增技術(shù)以及測序技術(shù).DNA存儲過程可以理解為一個信道模型，該信道模型主要由上述3種技術(shù)引起一些錯誤.這些錯誤可以分成兩類：序列內(nèi)錯誤和序列間錯誤.

序列內(nèi)錯誤主要是指DNA分子序列存在堿基的插入、刪除和替換等錯誤[15-17].DNA分子在合成時可能會發(fā)生堿基的替換、插入和刪除等錯誤；PCR擴增階段，可能發(fā)生替換錯誤；DNA分子在測序讀取階段，可能會發(fā)生堿基的替換、插入和刪除等錯誤.研究表明，使用二代測序技術(shù)，每個堿基發(fā)生錯誤的概率為1%～2%[17]， 而使用三代測序技術(shù)每個堿基發(fā)生錯誤的概率為10%～15%[18-19].此外，插入或刪除錯誤會導(dǎo)致DNA序列的長度與標(biāo)準(zhǔn)序列長度發(fā)生偏差.實驗表明，使用三代測序技術(shù)大約88%的reads長度不正確[20].

序列間錯誤主要是指DNA分子的缺失，以及DNA分子拷貝數(shù)分布不均勻[21].DNA編碼序列在合成階段，由于合成的不均勻性，DNA分子會被合成幾百甚至幾千個拷貝；DNA分子在PCR擴增階段也會發(fā)生拷貝數(shù)不均勻的現(xiàn)象，甚至有些序列會直接丟失[22-23]；在測序階段，各個序列拷貝分布的不均勻性，將會導(dǎo)致測序數(shù)據(jù)中各序列對應(yīng)的讀長(reads)也存在不均勻性，甚至?xí)G失某些序列的讀長.

可以看出，DNA存儲過程中每個階段都會發(fā)生DNA分子序列內(nèi)的錯誤以及序列間的錯誤，這些錯誤相互疊加，增加了DNA存儲解碼過程的復(fù)雜性(圖1).

圖1 DNA存儲信道的復(fù)雜性Fig.1 The complexity of DNA storage channel

有兩個原因直接導(dǎo)致了DNA存儲信道的復(fù)雜性：一個是技術(shù)原因，即技術(shù)水平存在缺陷；另一個是生物序列本身的一些約束沒有遵循.生物序列約束主要包括GC含量、均聚物長度以及回文結(jié)構(gòu).DNA序列中GC分布不均勻、GC含量過低或者過高會導(dǎo)致DNA序列PCR擴增分布不均勻；長度大于4的均聚物的出現(xiàn)會導(dǎo)致DNA序列在合成或測序時發(fā)生堿基錯誤；DNA序列存在的回文子序列會導(dǎo)致該序列在PCR擴增時出現(xiàn)發(fā)夾等二級結(jié)構(gòu)，進而影響PCR擴增的效率[24-25].

2 DNA存儲糾錯技術(shù)

目前,DNA存儲糾錯主要聚焦于兩個方面，即設(shè)計遵循生物序列約束的編碼策略以及魯棒的糾錯算法.

2.1 遵循生物序列約束的編碼策略

編碼DNA序列時遵循生物序列約束，有助于減少DNA存儲過程中產(chǎn)生的錯誤，并提高解碼效率[26].文獻[27]建議編碼DNA序列時遵循如下約束[27]：

(1)GC均勻分布且GC含量值介于40%～60%；

(2)均聚物的長度小于4；

(3)DNA序列不存在回文結(jié)構(gòu).

在設(shè)計遵循生物序列約束的策略方面，人們普遍采用隨機化的策略.

Church等[10]使用二進制編碼策略(即0用A或G表示，1用C或G表示)來控制GC含量，避免均聚物及回文序列的出現(xiàn).該二進制模型比較簡單，雖然能較好地滿足生物序列約束，但是該方法編碼效率不高.為了提高編碼效率并遵循序列約束，Goldman等[28]及Bornholt等[29]開發(fā)了一種三進制的編碼策略，即將數(shù)據(jù)轉(zhuǎn)換為三進制數(shù)字0、1、2的表示形式，然后根據(jù)編碼表將三進制數(shù)字轉(zhuǎn)變成DNA堿基，見表1.Goldman等[28]設(shè)計的編碼表，每個數(shù)字有多個對應(yīng)的DNA堿基，當(dāng)前數(shù)字對應(yīng)的DNA堿基依賴于前一位數(shù)字確定的DNA堿基.然而，使用二進制和三進制模型編碼DNA序列的研究比較少，目前的研究領(lǐng)域普遍采用四進制編碼DNA序列，即兩個二進制位對應(yīng)一個堿基.

表1 三進制編碼表

四進制編碼策略容易出現(xiàn)GC含量過高及均聚物較多的問題.為了解決這些問題，目前主流的方法是先將二進制數(shù)據(jù)與一個符合要求的隨機二進制序列做異或運算，形成一個二進制的結(jié)果序列，然后再對此二進制結(jié)果序列進行四進制編碼[20, 30].

DNA噴泉碼方法[26-27,31-32].通過隨機選擇二進制分組數(shù)據(jù)進行異或形成復(fù)合序列(液滴)，然后將復(fù)合序列按四進制編碼策略轉(zhuǎn)換成DNA序列.如果DNA序列符合生物序列約束，則留下等待后續(xù)合成，否則直接舍棄并繼續(xù)下一個復(fù)合序列(液滴)的生成.DNA噴泉碼充分利用了噴泉碼的無速率特性，省去了約束映射的冗余性.Wang等[33]采用混合的編碼策略，即隨機排列DNA序列里的堿基與可變長度映射策略相結(jié)合的方法，來滿足GC含量及均聚物的約束.其中，可變長度映射策略的構(gòu)建方法如下：①根據(jù)可變映射規(guī)則將不符合生物序列約束的二進制數(shù)據(jù)分組轉(zhuǎn)換為codeword序列，例如，二進制序列‘1100-00-00-1101-01-111100-0’轉(zhuǎn)換為‘01-1-1-02-2-001-1’；②將codeword序列每個數(shù)字與其前一個數(shù)字相加并對4求余,進而得到codeword序列對應(yīng)的四進制序列，即‘01-1-1-02-2-001-1’轉(zhuǎn)換為‘01-2-3-31-3-330-1’；③將四進制序列中的0映射為A堿基，1映射為T堿基，2映射為C堿基，3映射為G堿基，由此得到符合生物序列約束的DNA序列,即‘01-2-3-31-3-330-1’編碼成DNA序列‘AT-C-G-GT-G-GGA-T’.需要說明的是，上述步驟中可變映射規(guī)則的構(gòu)建是通過構(gòu)建一個包含3個狀態(tài)、4個數(shù)字(代表DNA的4個堿基),且連續(xù)出現(xiàn)的0不能超過2的狀態(tài)轉(zhuǎn)換圖FSTD(4,0,2),進而進行Huffman編碼得到的，見圖2.

圖2 可變長度的映射規(guī)則Fig.2 Variable-length constrained mapping rule

Zhang Yi團隊[13]、Yazdi等[34]及Xue 等[35]采用一種將用戶二進制數(shù)據(jù)與滿足0、1均衡的給定二進制序列(調(diào)制碼序列)進行調(diào)制的思想，來滿足GC均衡及均聚物的約束.具體方法為將待編碼二進制序列與調(diào)制碼序列逐列對齊，然后將每列按照調(diào)制規(guī)則轉(zhuǎn)換成一個DNA堿基，進而得到該二進制序列調(diào)制后的DNA序列(表2).

表2 調(diào)制規(guī)則

需要指出，上述所有方法除Church等[10]的方法外，均不能完全解決編碼序列存在二級結(jié)構(gòu)的問題.

2.2 DNA序列數(shù)據(jù)糾錯技術(shù)

2.2.1 序列丟失糾錯

目前,研究人員主要通過在編碼階段增加冗余序列來解決DNA存儲中序列的丟失問題.3種代表性的異或方法如圖3所示.

圖3 3種代表性的異或方法Fig.3 Three typical XOR methods

根據(jù)添加冗余序列方式的不同，DNA序列丟失的解決方法可以分為兩類.第一類主要是通過“序列異或”的思想產(chǎn)生冗余序列或復(fù)合序列.Bornholt等[29]采用連續(xù)兩個二進制序列進行異或產(chǎn)生第三個冗余序列的方法來解決丟失(圖3a).采用這種方法，任意一個序列丟失，可以通過該序列相關(guān)聯(lián)的其他兩個序列異或得出.然而，該種方法序列冗余度比較大.

為了降低冗余，2017年，Erlich等[27]在噴泉碼思想的基礎(chǔ)上提出了DNA噴泉碼算法(圖3b).其方法為①隨機選擇多個二進制數(shù)據(jù)分組進行異或操作生成復(fù)合序列(也叫液滴)；②合成并存儲復(fù)合序列(液滴)；③PCR擴增并測序每個復(fù)合序列;④將已經(jīng)分解出的二進制分組依次異或包含該二進制分組的液滴，直至分解出所有二進制分組數(shù)據(jù).盡管該方法可以以很高的DNA邏輯存儲密度(1.57 bit/nt)復(fù)現(xiàn)數(shù)據(jù)，但是該方法編碼和解碼的復(fù)雜度與數(shù)據(jù)大小并不是線性相關(guān)，相比編碼解碼更復(fù)雜.Ping等[36]認(rèn)為盡管Erlich等宣稱DNA噴泉碼丟失4%的液滴(指DNA編碼合成的序列)不會影響源數(shù)據(jù)的恢復(fù)，但是丟失更多的數(shù)據(jù)將有可能導(dǎo)致整個源數(shù)據(jù)無法恢復(fù).因此，存儲永久性的數(shù)據(jù)就必須有足夠量的冗余.

考慮到DNA噴泉碼中潛在的解碼失敗和冗余地址(降低凈信息密度)可能會阻礙其在DNA擴展性存儲中的實際應(yīng)用，Wang等[33]提出了累積碼的概念，即在源文件二進制分組數(shù)據(jù)的基礎(chǔ)上，添加一定量的冗余校驗序列.冗余校驗序列生成的方法為(圖3c)：根據(jù)累積碼率，選擇一定量的二進制分組數(shù)據(jù)(注意：圖例中選擇二進制分組的數(shù)量為5*0.8=4)，將其與前一個冗余校驗序列一起進行異或運算.使用該方法，可以通過冗余校驗序列和丟失序列相關(guān)的其他二進制序列進行異或運算,即可恢復(fù)丟失的序列.

第二類通過使用糾錯碼(Error Correcting Codes, ECCs)來實現(xiàn)缺失序列的恢復(fù).該類方法主要是通過在一個數(shù)據(jù)塊內(nèi)添加一些冗余序列(又叫外碼)來實現(xiàn)，參見圖4.基本思想是通過將缺失序列的位信息轉(zhuǎn)變成替換錯誤，然后通過糾錯碼來實現(xiàn)糾正[20, 37-38].具體方法是①首先將數(shù)據(jù)塊內(nèi)的二進制數(shù)據(jù)分組按列排放，形成一個矩陣；②依次向矩陣每一行的左側(cè)(或右側(cè))使用糾錯碼添加r位冗余位信息.解碼時先將數(shù)據(jù)塊內(nèi)的二進制數(shù)據(jù)根據(jù)各自的Index值依次排列好，缺失序列用等長的隨機二進制數(shù)據(jù)替換，然后依次對矩陣的每行使用糾錯碼糾正缺失序列對應(yīng)的位信息，直至缺失序列完全恢復(fù)為止.考慮到目前DNA合成技術(shù)一次最多可以同時合成DNA鏈的數(shù)量為224=16 777 216，Meiser等[37]最先針對圖4框架中一個數(shù)據(jù)塊內(nèi)二進制分組數(shù)據(jù)的個數(shù)k、二進制分組數(shù)據(jù)的大小(包括分組數(shù)據(jù)數(shù)據(jù)塊內(nèi)的序號ID)、外碼的個數(shù)以及每個符號所占位數(shù)等參數(shù)的組合進行了研究，并給出了每種參數(shù)組合下每條編碼序列包含的堿基個數(shù).目前，該類方法使用的糾錯碼主要為Reed-Solomon碼(RS碼).

圖4 外碼和內(nèi)碼框架Fig.4 The framework of outer code and inner code

2.2.2 序列內(nèi)堿基錯誤糾錯

(1)基于多序列比對思想上的糾錯

前面已經(jīng)指出，每個DNA序列在DNA存儲信道中都會有多個拷貝.研究人員利用DNA序列的多拷貝性來糾正DNA序列內(nèi)的堿基錯誤，即替換、插入和刪除等錯誤.該算法實現(xiàn)糾錯不要求參與比對的讀長具有相同的長度.該算法的基本思想是，把屬于同一序列的多個拷貝聚類(或分組)到一起，然后使用多序列比對軟件(比如MUSCLE,MAFFT等[39-40])比對同一序列的多個拷貝，然后按照多數(shù)投票原則確定出一個一致性的序列，見圖5.該類方法可以糾正序列內(nèi)堿基的插入、缺失和替換等錯誤.

圖5 聚類和多數(shù)投票示例Fig.5 Schematic diagram of clustering and majority voting

Goldman等[28]采用4倍重疊冗余來解決序列的堿基錯誤問題，即每個序列產(chǎn)生3個重疊的冗余序列，各個冗余序列和前一序列有3/4的重疊.然而該方法的DNA邏輯存儲密度只有0.33 bit/nt，難以實際推廣.為了降低合成成本，李彥敏等[41]沒有使用重疊片段的編碼思想，而是通過在序列內(nèi)增加序列索引重復(fù)的方式提高后續(xù)聚類的精度，進而實現(xiàn)糾錯.但是,該方法只能適應(yīng)錯誤率較低的情形.

Yadiz等[34]糾正序列內(nèi)堿基錯誤的方法分成兩個階段，如圖6所示.第一階段，根據(jù)每個讀長(reads)的索引值(序列號)對reads進行分組，然后使用多序列比對軟件對每個分組包含的讀長進行比對，然后使用多數(shù)投票算法得到一致性序列(碼字)；第二階段，迭代使用BWA[42]比對算法以及均聚物查找算法，修正第一階段產(chǎn)生的一致性序列(碼字).需要說明的是，第一階段生成一致性序列的方式是通過逐個確定均聚物的方式而產(chǎn)生的.該方法完成糾錯需要較高的測序深度(200X).

圖6 序列比對及均聚物校正示意圖Fig.6 Sequence alignment and homopolymer correction

Organick等[20]、Antkowiak等[30]以及Jeong等[26]通過改進聚類算法，提高了產(chǎn)生一致性序列的準(zhǔn)確度. Organick等[20]、Antkowiak等[30]使用局部敏感哈希辦法聚類測序得到讀長(reads)，該種聚類方法相比以漢明距離為基礎(chǔ)的Jaccard相似性聚類方法，具有更快的時間性能.該方法的基本思想是，首先獲取各讀長在給定隨機數(shù)矩陣上的簽名，然后通過比較簽名的相似性完成讀長的聚類.Jeong等[26]首次將序列各堿基的Q-score值納入聚類算法考慮的因素.

(2)基于傳統(tǒng)通信糾錯碼上的糾錯

傳統(tǒng)通信糾錯碼可以糾正二進制數(shù)據(jù)分組上的錯誤，尤其擅長糾正替換錯誤，且具有完備的數(shù)學(xué)理論基礎(chǔ).由于DNA存儲信道和傳統(tǒng)通信信道相比，都是將計算機二進制數(shù)據(jù)經(jīng)過一系列變換最終再轉(zhuǎn)變成二進制數(shù)據(jù)，這就使得用傳統(tǒng)通信糾錯碼去糾正二進制分組數(shù)據(jù)里的錯誤成為可能.

目前，糾正DNA序列內(nèi)堿基替換錯誤的方法，主要采用通信領(lǐng)域里性能較好的糾錯碼來實現(xiàn)檢錯和糾錯的目的.這些糾錯碼包括Reed-Solomon碼(RS碼)[37, 43-44]、BCH碼[45-46]、Raptor Code碼[47]、漢明碼[12, 48]、LDPC碼[44, 49-50],等等，其中，主流的是使用RS碼(圖4中的內(nèi)碼是指RS糾錯碼).使用這些糾錯碼的方法是①針對二進制分組數(shù)據(jù)，使用上述糾錯碼對應(yīng)的生成矩陣產(chǎn)生冗余位信息；②將冗余位信息融入到二進制分組形成待編碼二進制序列；③將待編碼二進制序列按照四進制編碼策略轉(zhuǎn)換成DNA序列；④在將測序得到的DNA序列轉(zhuǎn)換為二進制序列后，使用糾錯碼的一致性校驗矩陣進行矩陣運算，從而檢錯和糾錯.然而，上述糾錯碼糾錯的能力越強，即糾錯的數(shù)量越多，冗余度就越高.例如，BCH(255，47)碼可以糾正替換錯誤率達16%的錯誤，但是冗余度達到82%.

Xue等[35]在Levenshtein碼的基礎(chǔ)上，開發(fā)了一個既能實現(xiàn)GC平衡，又能解決堿基插入/缺失/替換錯誤的編碼方法.該方法構(gòu)建levenshtein碼的方法為(圖7)①將每一個長度為(2n-3「log2n?-2)的二進制分組數(shù)據(jù)拆分成長度為n和長度為(n-3「log2?n-2)的兩個子串；②從最后一位開始，將長度為n的二進制分組數(shù)據(jù)子串逐位取反直至該子串含1的數(shù)量為n/2，標(biāo)記為奇串；③將奇串的統(tǒng)計信息、校驗信息以及長度為(n-3「log2n?-2)的二進制分組數(shù)據(jù)子串合并，構(gòu)成偶串；④將奇串和偶串調(diào)制成DNA序列.解碼時，當(dāng)有一位插入/缺失/替換錯誤發(fā)生時，奇串和偶串的對應(yīng)信息會出現(xiàn)沖突，此時根據(jù)奇串的長度與標(biāo)準(zhǔn)長度的差值以及當(dāng)前解碼出的二進制字符串的S值和H值，可以準(zhǔn)確地推算出發(fā)生堿基錯誤的位置并給予糾正.然而，該方法一個碼字只能解決一位插入/刪除/替換錯誤，且碼字較長.

圖7 Levenshtein碼的構(gòu)建Fig.7 Construction of Levenshtein code

(3)基于算法角度實現(xiàn)糾錯

糾正DNA序列內(nèi)錯誤的難點是糾正序列里的插入和刪除等錯誤，因為很難分辨出DNA序列內(nèi)具體哪些堿基發(fā)生了這些錯誤.因此，糾正錯誤的關(guān)鍵在于準(zhǔn)確地識別出發(fā)生插入/刪除錯誤的位置.目前，研究人員大都通過設(shè)計一套有一定規(guī)律的編碼策略來編碼DNA序列.該編碼策略對插入/刪除非常敏感且不需要額外的堿基進行存儲.

Blawat等[46]設(shè)計了一套編碼表，即每個字節(jié)對應(yīng)兩個DNA編碼(圖8a)，然后將所有字節(jié)的DNA編碼分成兩類，編碼DNA序列時，交替使用各字節(jié)的第一類編碼和第二類編碼.當(dāng)插入/缺失錯誤發(fā)生時，第一類DNA編碼和第二類DNA編碼交替出現(xiàn)的規(guī)律將會打破，由此可以定位發(fā)生插入/刪除的編碼位置(圖8b).然而該算法只能檢測插入/缺失錯誤，不能糾錯.

圖8 Blawat設(shè)計的編碼表及可檢測插入/缺失錯誤的示例Fig.8 The code table by Blawat and an illustration of insertion/deletion detecting

Press等[51]設(shè)計了一個名為HEDGES的算法，同時結(jié)合RS碼，用于糾正DNA序列內(nèi)的插入/刪除/替換錯誤(圖9).其方法：①將源文件二進制數(shù)據(jù)劃分成等長度的二進制信息，然后對每個二進制信息添加索引(即序列ID),形成一系列待編碼二進制序列；②將待編碼二進制序列的每個二進制位數(shù)值、位置下標(biāo)索引、序列index以及該位前面連續(xù)幾個位信息進行hash操作最終變成一個DNA堿基，由此得到一個待編碼二進制序列對應(yīng)的DNA序列.當(dāng)插入/刪除/替換錯誤發(fā)生時，上述編碼規(guī)律將會打破，通過查找樹結(jié)構(gòu)可以判斷該二進制位是否發(fā)生錯誤及發(fā)生什么錯誤，并最終將出錯二進制位信息予以糾正.實驗結(jié)果表明，該方法能夠處理約1.2%的增刪錯誤.然而該方法的編碼率不高，糾正3%的錯誤，編碼率將降低到0.6以下.

圖9 HEDGES編碼與解碼Fig.9 Schematic diagram of HEDGES encoding and decoding

天津大學(xué)的Song 等[52]在De Bruijn圖的基礎(chǔ)上，構(gòu)建了同一序列多個拷貝的De Bruijn圖，然后通過基于貪心的搜索策略，搜索原序列對應(yīng)的最可能路徑.該算法與第一類算法相比，不需要聚類，因此具有更快的時間性能(圖10).該方法可以解決序列內(nèi)的插入、刪除、替換等錯誤.但是，該方法De Bruijn圖的構(gòu)建過度依賴于序列索引(即序列ID).如果屬于同一序列的每個拷貝index都出現(xiàn)錯誤，該方法將不能構(gòu)建De Bruijn圖.

圖10 de Bruijn 圖算法框架Fig.10 The framework of de Bruijn graph

Sharma等[53]通過定義堿基異或規(guī)則(表3)實現(xiàn)了糾正堿基替換錯誤的目的.其方法是①將每一個DNA編碼序列從左到右4個堿基為一組切分該編碼序列；②依次將每個切分第一字符拼接起來形成第一個編碼序列，同時將每個切分后續(xù)3個字符拼接起來形成第二個編碼序列；③依次將每個切分第一個字符與該切分后續(xù)3個字符做異或操作，將所有切分異或操作結(jié)果依次拼接起來，形成第三個編碼序列；④解碼時，根據(jù)得到的屬于同一序列的3個片段，兩兩異或推導(dǎo)出3個原編碼序列，根據(jù)一致性最終確定原編碼序列.然而，該方法的冗余度比較高，冗余度為75%.

表3 堿基異或表

3 DNA糾錯技術(shù)展望

DNA數(shù)據(jù)存儲是一種新興的非易失性存儲技術(shù)，具有前所未有的密度、耐用性和復(fù)制效率.盡管DNA存儲與傳統(tǒng)存儲技術(shù)相比，具有較明顯的優(yōu)勢，但是現(xiàn)階段DNA存儲距離真正的大規(guī)模應(yīng)用還有很長的距離.未來DNA存儲要做到真正大規(guī)模的應(yīng)用，使用成本較低、通量較大，但同時錯誤率較高的DNA合成技術(shù)及DNA測序技術(shù)再所難免.因此，未來DNA存儲糾錯技術(shù)可能呈現(xiàn)出以下兩個變化.

(1)編碼DNA序列時嚴(yán)格遵循生物序列約束.在滿足GC平衡及無均聚物的同時，尤其要避免DNA二級結(jié)構(gòu)的形成.因此，未來的糾錯算法可能包括DNA二級結(jié)構(gòu)子序列的查找算法以及DNA二級結(jié)構(gòu)的替換算法，從源頭上嚴(yán)格保證DNA編碼序列滿足生物序列約束，盡可能減少后續(xù)DNA存儲過程中的錯誤.

(2)未來的DNA存儲糾錯算法應(yīng)能適應(yīng)錯誤率更高的環(huán)境，同時具有良好的時間性能.目前的DNA存儲糾錯算法能夠適應(yīng)的堿基錯誤率最高為15%左右(使用三代測序).隨著人們對DNA存儲成本的要求越來越低及對存儲通量的要求越來越高，未來DNA存儲糾錯算法可能要適應(yīng)錯誤率高達20%以上的環(huán)境.針對高噪聲環(huán)境，設(shè)計魯棒的糾錯算法，同時滿足處理海量DNA數(shù)據(jù)時間性能上的要求，是未來DNA存儲糾錯算法的方向.