利用位模式树对代谢网络中的极射线进行部分枚举

《Frontiers in Bioinformatics》：Partial enumeration of extreme rays in metabolic networks using bit pattern trees

　　

代谢网络的极射线分析虽然非常强大，但目前仅限于较小的代谢网络。已有一些生成部分极射线集的方法，但所谓的双描述方法（double-description method）的计算效率尚未被充分利用。先前的研究强调了在其迭代中进行采样的可能性，从而能够实现基于双描述方法的部分枚举。然而，这些方法严重缺乏作为合适替代方案的计算效率。在本工作中，高效的位模式树（bit pattern tree）被用于采样框架内，以显著提升其输出和速度。结合近期对规范基方法（Canonical Basis Approach, CBA）的修订，研究人员所提出的方法在报告的基准条件下，甚至在全枚举研究中都优于其他测试方法，仅需一半的计算时间。此外，过滤器设置允许在保持高效率的同时降低内存需求。然而，候选组合爆炸的一些问题仍然存在，并得到了进一步研究。因此，本研究提出了一种新颖的、基于双描述的部分极射线枚举替代方案。内存效率的进一步改进将使这一有前景的方法能够将强大的基于极射线的分析扩展到基因组规模代谢网络。

论文解读：基于位模式树的部分极射线枚举方法在代谢网络分析中的应用

代谢网络的计算分析是系统生物学中理解生物体代谢能力、预测行为的重要手段。通常，代谢网络由反应集和代谢物集定义，并通过化学计量矩阵在拟稳态假设下构成通量锥。由于反应数量远大于代谢物数量，线性系统欠定，使得通量分布的求解面临困难。极射线（extreme rays）分析通过枚举如基本通量模式（Elementary Flux Modes, EFMs）或极端途径（Extreme Pathways, EPs）等生成元，能够将整个可行解空间表示为这些极射线的组合，从而在不需要单一通量分布的情况下全面刻画细胞代谢状态。然而，极射线的数量随网络规模急剧增长，导致基于双描述方法（double-description method）的全枚举在基因组规模网络上面临严重的内存和时间瓶颈。已有的采样方法虽然可以在双描述迭代中产生部分极射线，但计算效率低下。因此，研究者试图结合高效的树形搜索技术和新近发展的元素性测试，以构建一种高效的部分枚举方法。

该研究提出了一种融合位模式树（bit pattern tree）的采样型规范基方法（Canonical Basis Approach, CBA）。所谓位模式树，是一种针对二进制反应参与向量的树结构，其节点根据某一位上的零/非零状态进行分裂，从而在遍历中快速排除不可能产生基本候选的节点组合。该方法的创新之处在于，将原来用于全枚举的基于树的双遍历候选缩减策略，引入到采样型CBA框架中，并结合Mores等人于2025年提出的正定元素性测试（positive-definite elementarity test），以实现更快的候选评估。同时，通过设置过滤参数K来控制遍历过程中保留的节点对数量，从而平衡计算时间与内存占用。研究中使用了两个已广泛研究的代谢网络作为测试案例：e_coli_core（包含72个代谢物和95个反应）和基因组规模的iJR904网络。所有计算均在配备Intel Core i7-7700处理器和16 GB内存的桌面计算机上完成，并启用了8个线程进行并行处理。两个网络均使用efmtool包中的压缩函数进行了相同的网络压缩。

在结果部分，研究者首先针对e_coli_core网络研究了不同过滤设置K下的性能。该网络的全部EPs总数为100,273个，被用作全枚举的停止标准。与未使用树缩减步骤的CBA和NSA方法相比，加入树遍历的CBA显著提高了生成速度。在同样的计算时间内，树型CBA产生的EPs数量比原始CBA高出一个数量级。与广泛使用的efmtool相比，树型CBA生成全部EPs所需的计算时间仅为efmtool的一半，尽管efmtool本身已采用了秩更新等优化措施。研究还发现，低K值会导致生成结果偏向于较短的II型和III型EPs，这些途径多数为内部循环，可能不包含从底物到产物的完整连接，在应用中价值有限。随着K值增大，生成的EPs数量增加，随机性影响减小。在基因组规模网络iJR904的测试中，由于内存限制，K值最大只能设为10⁶，当K值更高时内存使用超过16 GB。该网络的EP生成表现出很大的随机性，特别是当生成的EPs中II型和III型占比较高时。如果仅关注>80%为I型EPs的运行，则随着K值的增加，EP输出显示出明显的增长趋势。另一个发现是，在算法迭代过程中，表格的行数演化与中尺度网络不同：中尺度网络的行数在后期持续增长，直到过滤作用使其趋于平稳；而基因组尺度网络的行数在较早期达到峰值，之后急剧下降，特别是在最后几次迭代中，行数可能减少约100倍。这表明基因尺度网络的复杂性高度集中在早期迭代，过滤效果无法在后期维持候选集的规模，从而导致最终的EP输出有限，且经常以较短的II型和III型EPs为主。

讨论部分指出，中尺度网络中，树型CBA的内存占用为2.48 GB，远低于efmtool的4.57 GB，这是因为树型CBA以稀疏矩阵存储表格，且树遍历仅需存储二进制的并模式（union patterns），而efmtool的秩更新法需要保存多个子矩阵，导致更高内存消耗。在基因组尺度网络中，候选组合爆炸问题仍然存在，并且由于后期候选集崩塌，过滤参数K对最终EP数量的控制不如中尺度网络那样直接。为了应对这一挑战，研究者提出可以考虑采用通量模块（flux modules）或将网络按照需求分割为子网络，以降低早期复杂度，并使得过滤设置能够更有效地发挥作用。结论部分总结道，本文提出的树型CBA方法通过引入候选缩减步骤，显著提升了计算效率，使CBA能够利用更快的正定元素性测试，并在中尺度网络基准测试中实现了超过30倍的加速。尽管在全枚举条件下，其速度比efmtool快一倍，但在基因组尺度网络中仍受限于内存和随机性。未来的内存效率改进和针对候选崩塌的解决方案，有望使该方法适用于全基因组规模的极射线分析。