基于混沌分组编码的DNA存储技术研究

1、基于混沌分组编码的DNA存储技术研究摘 要：大数据时代下信息的增长使现有的存储系统不堪重负.DNA作为天然的存储介质，因其具有信息密度 大、稳定性高、不易丢失等特点，使越来越多的研究人员将目光聚焦其上.因此，在原有基础上提出一种新的 DNA存储技术，该技术采用喷泉码将压缩文件转化为中间文件，并引入RS纠错码保证信息传输的正确性，根 据DNA的生化特性,提出一种混沌分组编码使中间文件在生成DNA片段时具有稳定的GC含量以及较短的均 聚物长度.最后使用一张压缩图片验证本DNA存储技术的可行性.实验结果表明，本方案能有效降低编码尝试 次数，提高编码正确率，具备良好信息存储性能.关键词：DNA;信息存

2、储；混沌分组编码；喷泉码计算机科学技术在飞速发展的同时，信息量 的增长速度也不容小觑.根据Stasista公司的统 计，到2025年全球信息的总量将达到2018年的5 倍.现在的存储介质如硬盘和硅制半导体的增长 速度远远没有达到信息量的增长速度口-,因此， 寻找下一代信息存储介质迫在眉睫脱氧核糖核酸(DNA)作为遗传信息的载体， 具有存储密度大、并行性较高及低能耗等好处，是 一种天然的数据存储介质.随着第二代DNA测 序技术的出现，结合人工合成技术，研究人员期望 用DNA作为下一代数据存储介质.近年来DNA存储技术逐渐成为研究人员关 注的焦点.哈佛大学医学院的Church团队在 2012年首次

3、将650 kb的一本图书存储在DNA 上，实现了体外DNA的数据存储，在国际尚属 首次,五年后利用大肠杆菌DNA存储了一段视频 文件，实现了 DNA数据的快速复制.同年，哥伦 比亚大学和纽约基因组中心的研究人员发明了一 种DNA喷泉系统，该系统在达到较高的香农信息 量的同时，还可以有较高的鲁棒性囱.2018年,Or- ganick等提出一种编码方法，该方法显著减少 了测序冗余，并实现了文件的随机访问.微软计划 于2020年在数据中心建立基于DNA的数据存储 系统.DNA存储取得革命性进展的同时还存在难 题需要攻克.本文研究一种基于混沌分组编码的DNA存 储技术，该方法具备一定的抗数据损坏的稳健

4、性， 具有较高的数据存储容量，并缩短编码时间，提高 存储性能.1方法设计与原理基于混沌分组码的DNA存储技术步骤如图1 所示，先将待存储的文件压缩为二进制文件，随后 对二进制文件进行编码使其变为含有ATCG四种 核苷酸的DNA序列.在序列两端加入DNA扩增 所需的引物片段和底物片段，随后将这些碱基序 列合成为DNA片段,这样就完成了信息的存储. 在进行信息读取时，为了获得多段相同的DNA，对 DNA库进行聚合酶链反应技术(PCR)进行扩增， 再对DNA序列进行测序，然后解码恢复所存储的 信息.整个存储技术中关键部分为DNA编码部分, 该部分主要分为编码和筛选两个环节.1.1 编码本文编码部分分

5、为两个步骤，第一步将二进 制文件进行LT编码得到中间数据,然后将中间数 据进行混沌分组编码，进行混乱和扩散.因为DNA 链的生化特性，不能含有较长的均聚物长度以及需要稳定的GC含量.混沌分组编码的混乱和扩散 特性刚好可以降低均聚物长度，以及稳定GC含 量，这样可以降低程序运行时间以及提升DNA存 储的正确性.图1 DNA存储技术流程图Fig. 1 Flowchart of DNA storoge technology图2 Luby变换流程图Fig. 2 Flowchort of Luby transformation首先，将二进制文件预处理为一系列一定长 度的非重叠段，然后，迭代计算三个步骤，

6、即Luby 变换、混乱扩散和筛选.Luby变换为喷泉码奠定了 基础.基本上,它通过使用鲁棒孤波分布从文件中 选择随机片段并将其异或变为新数据，这样将二 进制数据打包为任意数量的短消息(小滴).流程 如图2所示.小滴包含两条信息：保存数据异或过 程结果和固定长度的短种子.该种子对应于液滴 创建过程中变换的随机数生成器的状态,并允许 解码器算法推断液滴中各段的身份.从理论上讲 只要液滴的累积大小略大于原始文件的大小，就 可以使用高效算法,通过收集液滴的任何子集来 逆向图2 Luby变换流程图Fig. 2 Flowchort of Luby transformation下面利用混沌分组编码来对单个液

7、滴进行混 乱扩散重排,使单个液滴转化碱基序列的GC含量 稳定以及不含有较长的均聚物长度，满足DNA的 生化特性利用logistic映射，本文提出一种基于 Feistel结构的混沌分组密码.记&为长度8字节 64位的小液滴，即&是一个长为8字节1展，1， 13,2，13,3，13,4，13,5，13,6，13,7 的分组，&3 = 13，% 13,1 13,2 13,3 1,4 13,5 13,6 13,7 -作用过程由U轮相同计算循环作用 于同一个明文分组构成，其变换为13,+ + 1 = 13-1, + f+ -1 13-1,1，13-1,+ -1，W3-1, + - 1 ,zB 其中，3表

8、示当前是循环次数3 =1,U. + = 1，-, 8 ,f%= 是密钥，为简化计算，密钥取相同值，其 流程如图3所示.图3混沌分组编码流程图Fig. 3 Flowchart of chaotic block coding函数f1，77 的形式为 fj =fj( 11, ,1；,w), 其中,= 1,7，/是由logistic映射产生的一个函数.函数的输出 1U,% 1U,1 1U,2 1U,3 1U,4 1U,5 1U,6 1U,7 是下一 轮函数的输入.所以，U轮的输出1气% 1u,1 1U,2 1U,3 1U,4 1U,5 1U,6 1U,7长度为8字节64位的密文分组，长度与明文分组相同

9、.本文的函数片=H( 1112 1W),其中，H是通过离散化具有混合和扩散的 非线性logistic映射.H( 1)1( 256 - H( 1)1 256642551 = 256(1)改变logistic映射的系数，使其输入输出 值在0到256之间.(2)离散化标准化后的logistic映射.DNA存储技术中的信息在生成DNA链，以及 DNA链复制，和DNA测序等众多过程中，碱基极 易发生替换、丢失等问题，这样在DNA信息解码 时，因为某个碱基的错误而导致信息解码错误，进 而数据恢复出错.为了保证DNA存储数据的正确 性，加入纠错码尤为重要.RS( Reed-Solomon)纠错 码因为其性能

10、优良,被广泛应用于DNA存储技术 中，确保信息存储的正确性.1.2筛选与计算机和手机等基于信息论信道通信过程 不同的是,DNA存储技术过程中生成的DNA序列 需要满足一定的生化特性.在双链DNA中，如果 其中胞嘧啶C,鸟瞟吟G的含量越高，决定双链 DNA稳定性的氢键越多.DNA越稳定则测序时需 要的条件越高.因此，为了降低DNA测序的条件, 需要将DNA序列中的胞嘧啶C和鸟瞟吟G控制 在一定范围.研究发现均聚物长度也是引起DNA 合成，及测序错误的一个重要原因.所以为了确保 DNA合成和测序时的准确性，除了引入RS纠错 码外还需对候选碱基序列进行胞嘧啶C,鸟瞟吟G 含量和均聚物长度过滤.图4筛

11、选流程Fig. 4 Screening plan process本文选取DNA碱基序列中GC含量在45% - 55%之间，以及最长均聚物长度不超过3的序列 进行DNA存储.流程如图4所示.对不满足条件 的碱基序列去除重新计算，图4筛选流程Fig. 4 Screening plan process表1不同存储技术对比实验结果Table 1 Performance of different storage plans方案文献4文献6文献8文献10本文信息量0. 880. 831.570. 331.57冗余44.3017. 0020.7179.1117. 00纠错无无RS重复RS还原不行不行可以不行

12、可以从表1可以看出，本文提出的方法具有1.57 位/nt的信息密度,并且DNA存储的信息中冗余 信息占比较低,并可以将信息还原,可以看出本方 案的各项评价指标皆优于其他方案，与DNA喷泉 方案相同，故更详细地对比这两种方案.18 000(a)均聚物长度不超过33 0002 0004 5004 0002 500 DNA喷泉混沌(b)均聚物长度不超过4本文在DNA喷泉码的基础上对生成的中间 文件进行混沌编码，使其GC含量稳定并使均聚物 长度降低为了对比的效果更加明显，本文固定信 息冗余量为0.1.统计编码碱基序列需要尝试的次 数，在设定最长均聚物长度不超过3的条件下对 比结果如图5( a)所示，可

13、以看出，本算法具有一 定的混乱和扩散特性，编码尝试的次数降低了 20%.图5( b)表示均聚物长度不超过4的编码尝 试次数18 000(a)均聚物长度不超过33 0002 0004 5004 0002 500 DNA喷泉混沌(b)均聚物长度不超过4图5 DNA喷泉与本文编码次数2实验结果及分析实验过程:本文对一张12 KB的图片进行压 缩后得到的10 KB压缩文件作为本文DNA存储 技术的输入，后经编码、筛选后生成碱基序列实现 DNA储存.为了全方位评价本算法的优越性，加入 了近年来主流的dna4-10存储方案进行对比实 验.对比结果如表1所示.Fig. 5 DNA fountain and the coding times of this artide与DNA喷泉码相比，本文提出的方案在相同 条件下可以降低编码尝试的次数,提升编