Chang Dou、Yijie Yang、Fei Zhu、Bingzhi Li和Yuping Duan等作者来自天津大学应用数学中心和合成生物学前沿科学中心，于2024年7月13日在《Briefings in Bioinformatics》期刊发表了题为《Explorer: Efficient DNA Coding by De Bruijn Graph Toward Arbitrary Local and Global Biochemical Constraints》的研究论文。该研究提出了一种基于德布鲁因图（De Bruijn graph）的高效DNA编码算法Explorer，并配套开发了基于Transformer架构的快速解码算法Codeformer，旨在解决DNA数据存储领域面临的生化约束复杂性和编码效率问题。
学术背景
随着数字数据的爆炸式增长，传统存储介质在容量和持久性上逐渐显现瓶颈。DNA分子因其稳定性、高存储密度（每克DNA可存储4.2×10²¹比特数据）和低能耗特性，成为新兴的数据存储载体。然而，DNA存储需满足合成与测序过程中的生化约束条件，例如GC含量平衡（GC content balance）、同聚物长度限制（homopolymer length, HL）以及避免特定有害序列（undesired motifs, UM）。现有编码算法（如DNA Fountain、Yin-Yang Code）在处理复杂约束时存在效率不足或时间复杂度高的问题。因此，本研究的目标是开发一种兼顾高效性与灵活性的编码方法，以支持任意局部和全局生化约束的DNA序列生成。
研究流程与方法
算法设计：Explorer编码框架
- 德布鲁因图建模：将长度为n的DNA子序列映射为德布鲁因图的顶点，通过约束顶点属性实现局部生化条件（如GC含量、同聚物长度）的全局满足。具体而言，算法输入二进制信息，转换为十进制后，在德布鲁因图中动态选择满足约束的相邻顶点，逐步构建DNA序列（图1b-d）。
- 约束处理机制：算法支持多种约束组合（GC、HL、UM），通过滑动窗口验证局部子序列的合规性。例如，GC含量约束要求子序列中G/C比例处于预设区间（公式1），而同聚物长度限制通过顶点筛选避免连续重复碱基。
- 创新性：Explorer通过图结构避免了传统筛选方法的高计算复杂度，其空间复杂度稳定，不随观察长度（observation length, ）指数增长（图6b）。
深度学习解码：Codeformer
- 模型架构：基于Transformer的Seq2Seq模型，将DNA序列分词为k-mer片段后，通过自注意力层（self-attention layer）和前馈神经网络映射为二进制序列（公式5）。训练数据包含30万对二进制-DNA序列，测试集独立5万对。
- 效率优化：采用束搜索（beam search）策略平衡解码速度与准确性，当束宽为5时，解码效率较传统算法提升10倍（图9a）。结合里德-所罗门码（Reed-Solomon code）后，解码准确率超过99%（图10）。
实验验证
- 编码性能测试：对比Fountain、Hedges等算法，Explorer在8类约束下均保持高编码效率（图5a），且码率（code rate）显著优于同类方法（图5b）。引入人工碱基（如S/PZ）的扩展版本Explorer-8进一步提升了信息密度。
- 错误校正：在200碱基的DNA序列中，Explorer对0.5%编辑错误（如插入、缺失）的校正准确率达96.5%；通过多拷贝测序（≥3次读取）可有效恢复原始数据（图8）。
主要结果
- 编码效率与稳定性：Explorer在观察长度10-20的范围内，编码效率高于Spider-web和Yin-Yang（图6a），且内存占用线性增长，具备可扩展性（图7）。
- 解码速度突破：Codeformer的并行计算能力使其解码速度达传统算法的10倍，结合RS码后兼顾高效与高精度（图10）。
- 多约束兼容性：算法可同时处理GC平衡（40%-60%）、同聚物限制（≤3）和有害序列规避（如酶切位点），为复杂生物操作（如细胞信息存储）提供支持。
结论与价值
该研究的科学价值在于：
1. 方法学创新：Explorer首次将德布鲁因图应用于DNA编码，解决了复杂约束下算法效率与稳定性的矛盾；Codeformer为DNA存储领域首次引入深度学习解码框架。
2. 应用潜力：高码率与低能耗特性推动DNA存储工业化；灵活约束处理能力适配合成生物学（如基因电路设计）的需求。
3. 跨学科意义：融合图论、深度学习与分子生物学，为生物计算（biological computation）提供新范式。
研究亮点
- 高效编码：Explorer在严格约束下码率提升≥10%，且内存占用仅为Spider-web的1/100（图6b）。
- 快速解码：Codeformer的Transformer架构实现端到端解码，速度优势显著。
- 扩展性：支持人工碱基（八进制编码），信息密度超越自然碱基限制。
局限与展望
当前算法需改进固定长度编码和错误校正机制。未来可开发可解释性图神经网络（如XGNN）以增强模型透明度，或结合CRISPR技术实现活细胞数据存储。
（注：术语如“德布鲁因图”（De Bruijn graph）、“k-mer”等首次出现时保留英文原词。）