基于极值de Bruijn子图实现最小标签数的DNA标记容量优化研究

《IEEE Transactions on Information Theory》：Achieving DNA Labeling Capacity with Minimum Labels through Extremal de Bruijn Subgraphs

本文研究DNA标记过程中如何用最少数量的标签达到最大信息容量（log2q）。通过构建路径唯一de Bruijn子图，作者建立了图论与DNA标记的等价关系，提出创新性构造方法并获得γ(q,d)的上下界。当标签长度趋近无穷时，证明仅需移除 negligible 边即可实现最大容量，为分子标记技术提供了理论依据。

　　

在分子生物学和生物技术领域，DNA标记技术通过荧光标记实现DNA分子的可视化、检测和研究，广泛应用于基因组学、微生物学和分子医学。荧光原位杂交（FISH）、CRISPR系统和甲基转移酶等方法虽已成熟，但如何用最少的标记模式区分几乎所有的DNA序列，实现最大信息容量，仍是亟待解决的难题。此前研究虽解决了标签长度为1或2的情况，但对更长标签的通用方案尚未突破。

本研究聚焦于DNA标记的信息理论极限，旨在确定达到最大标记容量所需的最小标签数。通过建立标记过程与de Bruijn图的路径唯一子图之间的等价关系，将问题转化为图论中的极值问题。研究人员提出两种路径唯一子图构造方法，推导出γ(q,d)的上下界，并借助通用命中集和去环集理论证明渐近最优性。

关键技术方法包括：1）构建路径唯一de Bruijn子图的组合设计；2）利用邻接矩阵幂次性质验证路径唯一性；3）通过包含-排除原理计算边集规模；4）结合Mykkeltveit V集分析渐近行为。研究基于理论推导和计算机搜索（混合整数规划、贪婪算法、模拟退火）验证构造最优性。

路径唯一子图的构造方法

通过限制边选择条件（如首符号不大于次符号、排除单调序列），Construction 1生成具有(q+1)/(2q)·q^d+1-binom(d+q-1,d+1)条边的路径唯一图。Construction 2针对d=2情况，通过顶点分块和颜色编码策略，实现更紧凑的边集规模（q³/3+3q²/2-23q/6+4）。

上界证明与渐近行为

基于邻接矩阵幂次特性及行走交集数η(q,d,k)，Theorem 5给出γ(q,d)≤q^d+1-(q^d+k-γ(q^d,1))/η(q,d,k)的上界。当d→∞时，通过连接通用命中集理论证明γ(q,d)/q^d+1→1，表明仅需移除渐近可忽略的边即可实现路径唯一性。

数值比较与最优性验证

通过计算机搜索（混合整数规划、贪婪算法、置换矩阵优化）验证小参数下的γ(q,d)值。当q=2,d=2时最优值为5；q=3,d=2时为15。图示结果表明Construction 2在d=2时优于Construction 1，且上界随q增大趋于5/8。

本研究首次建立了DNA标记容量优化与极值de Bruijn子图的完整理论框架，提出可实现的构造方法并证明渐近紧界。成果为分子标记技术的标签设计提供理论指导，尤其对长标签序列的优化具有显著应用价值。未来工作将聚焦于缩小有限参数的界差，并探索路径唯一图在生物信息学其他领域的应用潜力。