Max Planck Institute for Dynamics of Complex Technical Systems, Sandtorstrasse 1, 39106, Magdeburg, Germany.
Department of Chemical Engineering and Applied Chemistry, University of Toronto, 200 College Street, Toronto, ON, M5S 3E5, Canada.
BMC Bioinformatics. 2020 Nov 9;21(1):510. doi: 10.1186/s12859-020-03837-3.
The concept of minimal cut sets (MCS) has become an important mathematical framework for analyzing and (re)designing metabolic networks. However, the calculation of MCS in genome-scale metabolic models is a complex computational problem. The development of duality-based algorithms in the last years allowed the enumeration of thousands of MCS in genome-scale networks by solving mixed-integer linear problems (MILP). A recent advancement in this field was the introduction of the MCS approach. In contrast to the Farkas-lemma-based dual system used in earlier studies, the MCS approach employs a more condensed representation of the dual system based on the nullspace of the stoichiometric matrix, which, due to its reduced dimension, holds promise to further enhance MCS computations.
In this work, we introduce several new variants and modifications of duality-based MCS algorithms and benchmark their effects on the overall performance. As one major result, we generalize the original MCS approach (which was limited to blocking the operation of certain target reactions) to the most general case of MCS computations with arbitrary target and desired regions. Building upon these developments, we introduce a new MILP variant which allows maximal flexibility in the formulation of MCS problems and fully leverages the reduced size of the nullspace-based dual system. With a comprehensive set of benchmarks, we show that the MILP with the nullspace-based dual system outperforms the MILP with the Farkas-lemma-based dual system speeding up MCS computation with an averaged factor of approximately 2.5. We furthermore present several simplifications in the formulation of constraints, mainly related to binary variables, which further enhance the performance of MCS-related MILP. However, the benchmarks also reveal that some highly condensed formulations of constraints, especially on reversible reactions, may lead to worse behavior when compared to variants with a larger number of (more explicit) constraints and involved variables.
Our results further enhance the algorithmic toolbox for MCS calculations and are of general importance for theoretical developments as well as for practical applications of the MCS framework.
最小割集 (MCS) 的概念已成为分析和（重新）设计代谢网络的重要数学框架。然而，在基因组规模代谢模型中计算 MCS 是一个复杂的计算问题。近年来对偶算法的发展允许通过求解混合整数线性问题 (MILP) 枚举数千个基因组规模网络的 MCS。在该领域的最新进展是引入了 MCS 方法。与早期研究中使用的基于 Farkas 引理的对偶系统不同，MCS 方法采用基于代谢矩阵零空间的对偶系统的更简洁表示，由于其维度降低，有望进一步增强 MCS 计算。
在这项工作中，我们引入了几种基于对偶的 MCS 算法的新变体和修改，并对它们对整体性能的影响进行了基准测试。作为一个主要结果，我们将原始的 MCS 方法（仅限于阻止某些目标反应的操作）推广到具有任意目标和期望区域的最一般的 MCS 计算情况。在此基础上，我们引入了一种新的 MILP 变体，该变体在 MCS 问题的公式化中具有最大的灵活性，并充分利用基于零空间的对偶系统的减小尺寸。通过一组全面的基准测试，我们表明基于零空间的对偶系统的 MILP 优于基于 Farkas 引理的对偶系统的 MILP，平均加速约 2.5 倍。我们还提出了约束形式的一些简化，主要与二进制变量有关，这进一步提高了与 MILP 相关的 MCS 的性能。然而，基准测试还表明，一些高度简化的约束形式，特别是对于可逆反应，与具有更多（更显式）约束和相关变量的变体相比，可能会导致更差的行为。
我们的结果进一步增强了 MCS 计算的算法工具包，对理论发展以及 MCS 框架的实际应用都具有重要意义。
