Chamaeleo： DNA存储碱基编解码算法的可拓展集成与系统评估平台

doi:10.12211/2096-8280.2020-083

合成生物学 ›› 2021, Vol. 2 ›› Issue (3): 412-427.DOI: 10.12211/2096-8280.2020-083

Chamaeleo： DNA存储碱基编解码算法的可拓展集成与系统评估平台

平质¹^,²^,³, 张颢龄¹^,²^,³, 陈世宏⁴^,⁵, 倪鸣¹^,³, 徐讯¹^,²^,³, 朱砂⁶^,⁷, 沈玥¹^,²^,³^,⁵

^1.深圳华大生命科学研究院，广东深圳 518083
^2.深圳市合成生物学创新研究院，中国科学院深圳先进技术研究院，广东深圳 518055
^3.广东省高通量基因组测序与合成编辑应用重点实验室，深圳华大生命科学研究院，广东深圳 518120
^4.广东省）华大基因合成基因组学院士工作站，深圳华大基因科技有限公司，广东深圳 518120
^5.深圳国家基因库，广东深圳 518120
^6.英国牛津大学大数据研究所，牛津 OX3 7LF
^7.英国TAICHI AI Ltd. ，伦敦 N1 7GU

收稿日期:2020-12-01 修回日期:2020-12-31 出版日期:2021-06-30 发布日期:2021-07-13
通讯作者: 朱砂,沈玥
作者简介:平质（1987—），男，博士，助理研究员。研究方向为合成生物学、DNA存储、生物信息分析算法。 E-mail：pingzhi@genomics.cn
张颢龄（1996—），男，助理研究员。研究方向为合成生物学、计算机科学、神经网络。 E-mail：zhanghaoling@genomics.com
朱砂（1985—），男，博士，罗氏（英国）资深统计分析师。研究方向为生物遗传模型相关的概率论。长期从事计算机统计方法研究和程序开发。E-mail：sha.joe.zhu@gmail.com
沈玥（1986—），女，博士，研究员。研究方向为合成生物学、合成基因组学、DNA合成技术与工具开发。E-mail：shenyue@genomics.cn
基金资助:
国家重点研发计划(2020YFA0712100);广东省高通量基因组测序与合成编辑应用重点实验室项目(2017B030301011);广东省华大基因合成基因组学院士工作站项目(2017B090904014)

Chamaeleo： an integrated evaluation platform for DNA storage

Zhi PING¹^,²^,³, Haoling ZHANG¹^,²^,³, Shihong CHEN⁴^,⁵, Ming NI¹^,³, Xun XU¹^,²^,³, Sha ZHU⁶^,⁷, Yue SHEN¹^,²^,³^,⁵

^1.BGI-Shenzhen，Shenzhen 518083，Guangdong，China
^2.Shenzhen Institute of Synthetic Biology，Shenzhen Institutes of Advanced Technology，Chinese Academy of Sciences，Shenzhen 518055，Guangdong，China
^3.Guangdong Provincial Key Laboratory of Genome Read and Write，BGI-Shenzhen，Shenzhen 518120，Guangdong，China
^4.Guangdong Provincial Academician Workstation of BGI Synthetic Genomics，BGI-Shenzhen，Shenzhen 518120，Guangdong，China
^5.China National GeneBank，BGI-Shenzhen，Shenzhen 518120，Guangdong，China
^6.Big Data Institute，University of Oxford，Oxford，OX3 7LF，United Kingdom
^7.TAICHI AI Ltd. ，London，N1 7GU，United Kingdom

Received:2020-12-01 Revised:2020-12-31 Online:2021-06-30 Published:2021-07-13
Contact: Sha ZHU, Yue SHEN

摘要/Abstract

摘要：

近年来DNA存储因其数据存储密度与保存时间方面的优势而备受关注，有望在如光盘、硬盘等传统存储介质之外作为一种新型信息存储方式，满足海量数据存储及特殊应用领域数据加密存储的迫切需求。DNA存储流程中，二进制信息到DNA碱基序列的相互转换（即编解码）方法是实现数字信息技术与生物技术衔接的最核心步骤。尽管DNA存储编解码研究已有丰富进展，但与现有上下游衔接技术的兼容性，对不同存储文件的适配性、存储稳健性和数据安全性等尚缺少一个可量化比较与评估的系统。因此，本研究开发了一个DNA存储编解码方法的可扩展集成与评估平台Chamaeleo，以模块化集成方式对已开发的编解码方法进行系统性量化分析与评估，可针对不同类型文件进行编解码方法的择优方案输出。Chamaeleo以开源方式运行，以便于未来新编解码方法和评价指标的持续加载，促进该领域开放交流，推动规范化有序发展。

关键词: DNA存储, 二进制-碱基编解码方法, 评估体系, 兼容性, 存储稳健性

Abstract:

The emerging field of DNA based data storage has attracted considerable interests for the enormous potentials of DNA in high density and durability as a medium. Compare to traditional storage material such as magnetic, optical and electronic storage media, the use of DNA as storage media has been considered as a promising novel solution to meet the global demand for storing the skyrocketing amount of data worldwide. In addition, DNA storage adds an extra layer of protection for the stored information because the coding and decoding process of DNA based data storage relies on the combined implementation of DNA synthesis and sequencing technologies, which are not as commonly used as technologies in information communication area. Transcoding between binary digital data and quaternary DNA molecules is the most important step in the whole process of DNA-based data storage. Several coding methods have been developed using different programming languages in the past decades, however, it is difficult to compare the overall performance of these methods due to different software architectures and varying parameters. Thus, it brings challenges for researchers to further develop or for users to compare and choose the suitable methods as needed. In this study, we introduce an integrated evaluation platform "Chamaeleo" to address the issues as stated above. One of the key features of Chamaeleo is the integration of existing coding schemes and modulization of functions including data handling, transcoding, index operating and error-correcting as a user-friendly design. The other key feature is the function of evaluating a coding scheme in a qualitative and quantitative manner. A set of widely recognized and accepted indexes are chosen to evaluate the compatibility with DNA writing and reading technologies, the robustness regarding tolerance of introduced errors or data loss and the complexity of transcoding rules. Considering the rapid advancement in this field, Chamaeleo is designed as an open-source style for researchers to incorporate new coding schemes and evaluation indexes into the platform, thus encouraging the community to contribute together in the shaping of future DNA based data storage.

Key words: DNA digital storage, binary-nucleotide transcoding scheme, evaluation system, compatibility, storage robustness

中图分类号:

Q819

平质, 张颢龄, 陈世宏, 倪鸣, 徐讯, 朱砂, 沈玥. Chamaeleo： DNA存储碱基编解码算法的可拓展集成与系统评估平台[J]. 合成生物学, 2021, 2(3): 412-427.

Zhi PING, Haoling ZHANG, Shihong CHEN, Ming NI, Xun XU, Sha ZHU, Yue SHEN. Chamaeleo： an integrated evaluation platform for DNA storage[J]. Synthetic Biology Journal, 2021, 2(3): 412-427.

图/表 8

图1 Chamaeleo平台简介［（a）DNA存储的常规流程：该流程分为终端部分和生化部分，Chamaeleo针对DNA存储中的转码步骤进行设计，串联上下游DNA合成与测序；（b）Chamaeleo搭建的评价体系，从多维度对转码方案进行量化分析；（c）Chamaeleo的程序架构及模块间的相互关系。Chamaeleo开源软件平台可通过https：∥github.com/ntpz870817/Chamaeleo进行访问，或通过pypi： pip install Chamaeleo的方式在计算机终端进行安装和使用］

Fig. 1 Brief introduction of Chamaeleo[(a) General procedure of DNA storage includes in-silico transcoding and experimental DNA synthesis and sequencing. Chamaeleo focuses on in-silico transcoding part and connect the related technologies. (b) The evaluation system created by Chamaeleo quantitatively analyzes coding schemes from multiple aspects. (c) Software architecture and relations between modules and classes. The source code is available at https://github.com/ntpz870817/Chamaeleo, which can be also installed by the command of pip.exe, ＂pip install chamaeleo＂]

图2 DNA序列结构设计与已收录编码方法的净信息密度评估［（a）输出DNA序列设计，纠错码为可选项，其中，Hamming和RS码在结构上的分布略有不同；（b）测试文件通过不同转码算法获得的净信息密度，其中Goldman转码算法使用的报道中生成的哈夫曼树［4］，DNA Fountain转码算法使用伪随机数生成器中默认度分布参数（δ = 0.05， c_dist = 0.1）以及默认的7%的冗余［6］，Yin-Yang 转码算法则选择相关研究中采用的第888号规则［7］］

Fig. 2 Structure of output DNA sequences and their net information densities[(a) Basic design of output DNA sequences with/without optional error-correction codes (Hamming code and RS code). (b) Distribution of net information density using different coding schemes. The setting of parameters is identical to that of original report: For Goldman's coding scheme, the Huffman tree used in the evaluation process is set as the same in Goldman, et al[4]. For DNA Fountain scheme, the degree distribution tuning parameter (δ = 0.05 and c_dist = 0.1) and redundancy (7%) used in the evaluation process is set as the same in Erlich, et al[6]. For Yin-Yang coding scheme, rule No. 888 was used as reported in Ping, et al[7]]

图3 转码方案的兼容性评估［在无纠错码情况下，不同转码算法从10个测试文件中编码所得DNA序列的GC含量分布（a）和最大单碱基重复长度分布的统计（b）］

Fig. 3 Compatibility evaluation of coding schemes[Distribution of GC content (a) and maximum homopolymer length (b) of DNA sequences from transcoding of 10 test-files by different coding schemes. For Base coding in (b), the maximum homopolymer length is 42 and not shown in this panel for a clarity purpose]

图4 转码方案的稳健性评估［（a）在测试文件转码获得的DNA序列文库中引入1%的随机序列丢失，对比解码后文件与源文件，获得该情况下文件的恢复率。右侧图为98.94%～99.02%区间放大。（b）在测试文件转码获得的DNA序列文库中引入3%的随机碱基错误（插入、删除、替换各1%），对比解码后文件与源文件，获得该情况下文件的恢复率。右侧图为97%～98.4%区间放大］

Fig. 4 Robustness evaluation of coding schemes[Distribution of file retrieval rate under condition of (a) 1% random sequence loss and (b) 3% of nucleotide error (1% for insertion/deletion/substitution, respectively). Figures on the right is the zoom in part for a closer view]

图5 使用图论对不同转码算法进行可视化［实心红点表示起点或虚拟起点（即Goldman转码及Yin-Yang转码中为编码第一位碱基所用的虚拟位）。在每一轮编码过程中，已知当前的碱基（节点）和输入的二进制（箭头），跳转至下一个节点并输出其所指代的碱基，最后将下一个节点作为当前节点。在对应的每一轮解码过程中，已知当前节点（碱基）和下一节点（碱基），获得两个节点之间的箭头，并输出箭头指代的二进制信息，最后将下一节点作为当前节点］

Fig. 5 Visualization of different coding schemes using Graph-theory-based presentation[Red dot represents starting point or virtual starting point (for Goldman & Yin-Yang coding schemes). During each step of encoding, with known previous base (node) and input bit value (arrow), the current base would be obtained from graph. During each step of decoding, with known previous and current nodes (base), the bit value (arrow) would be obtained from graph]

表S1 使用代码调用流程完成转码过程实例

Tab.S1 Example commands to invoke transcoding process

# 加载对应的包

from Chamaeleo.methods.fixed import Church

from Chamaeleo.methods.ecc import ReedSolomon

from Chamaeleo.utils.pipelines import TranscodePipeline

# 创建Church转码方法（Church），并设定实时展示日志（进程）。

coding_scheme = Church（need_logs=True）

# 创建纠错算法：RS码（error_correction），并设定实时展示日志（进程）。

error_correction = ReedSolomon（check_size=3， need_logs=True）

# 将具体的转码算法和纠错码装载到转码任务流程中，并设定实时展示日志（进程）。

pipeline = TranscodePipeline（coding_scheme=coding_scheme， error_correction=error_correction， need_logs=True）

# 设置转码方向（direction）为硅向碳存储（t_c），设置电子文件的路径（input_path）为s.txt、DNA文件的路径（output_path）为t.dna，设置待编码的每条比特序列的长度为120，设置是否需要增加索引（index）为True。

pipeline.transcode（direction="t_c"， input_path="s.txt"， output_path="t.dna"， segment_length=120， index=True）

# 设置转码方向（direction）为碳向硅存储（t_s），设置DNA文件的路径（input_path）为t.dna、电子文件的路径（output_path）为t.txt，设置是否需要增加索引（index）为True。

pipeline.transcode（direction="t_s"， input_path="t.dna"， output_path="t.txt"， index=True）

# 输出有用的评估指标信息，输出方式（type）为在控制台输出字符串（string）。

pipeline.output_records（type="string"）

图S1 10个典型测试文件的文件大小和字节频率［每个分布中的4条横线从下到上表示1%～4%的出现比例。部分比特在文件中的出现概率超过4%，最高可达42.67%（BMP代表文件中的比特“00101110”）］

Fig. S1 Sizes and byte-frequency distributions of 10 typical test files[The 4 lines in each distribution indicates 1% to 4% from bottom to top. The probabilities of occurrence of few specific bytes exceed 4%, which are labeled with digits. The highest probability of occurrence is 42.67% ("00101110" in BMP file)]

图S2 不同转码算法编码和解码速度的比较（测试环境：Windows 7系统；i7 CPU处理器；12GB内存；Python版本，3.7.3；IDE，PyCham 2019.1）(Test environment: Windows 7 environment including an i7 CPU and 12 GB of RAM using Python 3.7.3 in the IDE PyCharm 2019.1)

Fig. S2 Encoding and decoding speed of different transcoding algorithms

参考文献 37

1	PING Z, MA D Z, HUANG X L, et al. Carbon-based archiving: current progress and future prospects of DNA-based data storage [J]. Gigascience, 2019, 8(6): gizo75.
2	DONG Y M, SUN F J, PING Z, et al. DNA storage: research landscape and future prospects [J]. National Science Review, 2020, 7(6): 1092-1107.
3	CHURCH G M, GAO Y, KOSURI S, Next-generation digital information storage in DNA [J]. Science, 2012, 337(6102): 1628.
4	GOLDMAN N, BERTONE P, CHEN S, et al. Towards practical, high-capacity, low-maintenance information storage in synthesized DNA [J]. Nature, 2013, 494(7435): 77-80.
5	GRASS R N, HECKEL R, PUDDU M, et al. Robust chemical preservation of digital information on DNA in silica with error-correcting codes [J]. Angewandte Chemie International Edition, 2015, 54(8): 2552-2555.
6	ERLICH Y, ZIELINSKI D. DNA Fountain enables a robust and efficient storage architecture [J]. Science, 2017, 355(6328): 950-954.
7	PING Z, CHEN S, HUANG X, et al. Towards practical and robust DNA-based data archiving by codec system named 'Yin-Yang' [EB/OL]. [2021-05-26]. .
8	HAO M, QIAO H, GAO Y, et al. A mixed culture of bacterial cells enables an economic DNA storage on a large scale [J]. Communications Biology, 2020, 3(1): 416.
9	PRESS W H, HAWKINS J A, JONES S K, et al. HEDGES error-correcting code for DNA storage corrects indels and allows sequence constraints [J]. Proceedings of the National Academy of Sciences of the United States of America, 2020, 117(31): 18489.
10	WANG Y X, NOOR-A-RAHIM M, GUNAWAN E, et al. Construction of bio-constrained code for DNA data storage [J]. IEEE Communications Letters, 2019, 23(6): 963-966.
11	NGUYEN T T, CAI K, IMMINK K A S, et al. Constrained coding with error control for DNA-based data storage [C]//2020 IEEE International Symposium on Information Theory (ISIT). 2020.
12	BLAWAT M, GAEDKE K, HUETTER I, et al. Forward error correction for DNA data storage [J]. Procedia Computer Science, 2016, 80: 1011-1022.
13	FOWLER M. Refactoring: improving the design of existing code [M]. Boston: Addison-Wesley Professional, 2018.
14	COX B J. Object-oriented programming: an evolutionary approach [M]. Boston: Addison-Wesley, 1986.
15	KOCH J, GANTENBEIN S, MASANIA K, et al. A DNA-of-things storage architecture to create materials with embedded memory [J]. Nature Biotechnology, 2020, 38(1): 39-43.
16	TANENBAUM A S BOS H. Modern operating systems [M]. London: Pearson, 2015.
17	SAYOOD K. Introduction to data compression [M]. Burlington: Morgan Kaufmann, 2017.
18	FENG L, FOH C H, JIANFEI C, et al. LT codes decoding: design and analysis [C]//2009 IEEE International Symposium on Information Theory. 2009.
19	YAZDI S H T, GABRYS R, MILENKOVIC O. Portable and error-free DNA-based data storage [J]. Scientific Reports, 2017, 7(1): 1-6.
20	ORGANICK L, CHEN Y J, ANG S D, et al. Probing the physical limits of reliable DNA data retrieval [J]. Nature Communications, 2020, 11(1): 1-7.
21	HECKEL R, MIKUTIS G, GRASS R N. A characterization of the DNA data storage channel [J]. Scientific Reports, 2019, 9(1): 9663.
22	MACKAY D J MAC KAY D J. Information theory, inference and learning algorithms [M]. Cambridge: Cambridge University Press, 2003.
23	KOSURI S, CHURCH G M. Large-scale de novo DNA synthesis: technologies and applications [J]. Nature Methods, 2014, 11(5): 499-507.
24	KULSKI J K. Next generation sequencing-advances, applications and challenges[M]. London: Intech Open, 2016: 3-60.
25	CHEN Y J, TAKAHASHI C N, ORGANICK L, et al. Quantifying molecular bias in DNA data storage [J]. Nature Communications, 2020, 11(1). DOI:http://doi.org/10.1038/s41467-020-16958-3.
26	MOON T K. Error correction coding: mathematical methods and algorithms [M]. Hoboken: John Wiley & Sons, 2005.
27	STINSON D R, PATERSON M. Cryptography: theory and practice[M]. Boca Raton: CRC Press, 2018.
28	PASCHKE J, BURKERT J, FEHRIBACH R. Computing and estimating the number of n-ary Huffman sequences of a specified length [J]. Discrete Mathematics, 2011, 311(1): 1-7.
29	KOSHY T. Catalan numbers with applications [M]. Oxford: Oxford University Press, 2008.
30	AVAL J C. Multivariate fuss-catalan numbers [J]. Discrete Mathematics, 2008, 308(20): 4660-4669.
31	WEST D B. Introduction to graph theory [M]. Hoboken: Prentice Hall, 1996.
32	COMPEAU P E, PEVZNER P A, TESLER G. How to apply de Bruijn graphs to genome assembly [J]. Nature Biotechnology, 2011, 29(11): 987-991.
33	BOUCHET A. Greedy algorithm and symmetric matroids [J]. Mathematical Programming, 1987, 38(2): 147-159.
34	MILO R, SHEN-ORR S, ITZKOVITZ S, et al. Network motifs: simple building blocks of complex networks [J]. Science, 2002, 298(5594): 824-827.
35	BORNHOLT J, LOPEZ R, CARMEAN D M, et al. A DNA-based archival storage system [C]//Proceedings of the Twenty-First International Conference on Architectural Support for Programming Languages and Operating Systems. 2016.
36	CAFFERTY B J, TEN A S, FINK M J, et al. Storage of information using small organic molecules [J]. ACS Central Science, 2019, 5(5): 911-916.
37	KENNEDY E, ARCADIA C E, GEISER J, et al. Encoding information in synthetic metabolomes [J]. PLoS One, 2019, 14(7): e0217364.

[1]	马孟丹, 刘宇辰. 合成生物学在疾病信息记录与实时监测中的应用潜力[J]. 合成生物学, 2023, 4(2): 301-317.
[2]	杨洋, 樊春海. 基于人工染色体的DNA信息存储前沿进展[J]. 合成生物学, 2021, 2(3): 305-308.
[3]	黄小罗, 戴俊彪. 人工DNA合成技术：DNA数据存储的基石[J]. 合成生物学, 2021, 2(3): 335-353.

Chamaeleo： DNA存储碱基编解码算法的可拓展集成与系统评估平台

Chamaeleo： an integrated evaluation platform for DNA storage

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

图/表 8

参考文献 37

相关文章 3

编辑推荐

Metrics

本文评价