Metabolomics and Analytics Center, Leiden Academic Centre for Drug Research, Leiden University, Wassenaarseweg 76, Leiden 2333 CC, The Netherlands.
Luxembourg Centre for Systems Biomedicine, University of Luxembourg, 6 avenue du Swing, Belvaux L-4362, Luxembourg.
Bioinformatics. 2023 Sep 2;39(9). doi: 10.1093/bioinformatics/btad450.
Several applications in constraint-based modelling can be mathematically formulated as cardinality optimization problems involving the minimization or maximization of the number of nonzeros in a vector. These problems include testing for stoichiometric consistency, testing for flux consistency, testing for thermodynamic flux consistency, computing sparse solutions to flux balance analysis problems and computing the minimum number of constraints to relax to render an infeasible flux balance analysis problem feasible. Such cardinality optimization problems are computationally complex, with no known polynomial time algorithms capable of returning an exact and globally optimal solution.
By approximating the zero-norm with nonconvex continuous functions, we reformulate a set of cardinality optimization problems in constraint-based modelling into a difference of convex functions. We implemented and numerically tested novel algorithms that approximately solve the reformulated problems using a sequence of convex programs. We applied these algorithms to various biochemical networks and demonstrate that our algorithms match or outperform existing related approaches. In particular, we illustrate the efficiency and practical utility of our algorithms for cardinality optimization problems that arise when extracting a model ready for thermodynamic flux balance analysis given a human metabolic reconstruction.
Open source scripts to reproduce the results are here https://github.com/opencobra/COBRA.papers/2023_cardOpt with general purpose functions integrated within the COnstraint-Based Reconstruction and Analysis toolbox: https://github.com/opencobra/cobratoolbox.
约束建模中的几个应用可以用涉及向量中非零数最小化或最大化的基数优化问题在数学上进行公式化。这些问题包括测试化学计量一致性、测试通量一致性、测试热力学通量一致性、计算通量平衡分析问题的稀疏解以及计算放松约束的最小数量以使不可行的通量平衡分析问题可行。这种基数优化问题计算复杂，没有已知的多项式时间算法能够返回精确的全局最优解。
通过用非凸连续函数逼近零范数，我们将约束建模中的一组基数优化问题重新表述为凸函数的差。我们实现并数值测试了使用一系列凸规划来近似求解重新表述问题的新算法。我们将这些算法应用于各种生化网络，并证明我们的算法与现有相关方法相匹配或优于它们。特别是，我们说明了我们的算法对于从给定人类代谢重建提取准备进行热力学通量平衡分析的模型时出现的基数优化问题的效率和实际效用。
在这里可以重现结果的开源脚本：https://github.com/opencobra/COBRA.papers/2023_cardOpt，其中包含了集成在基于约束的重建和分析工具箱中的通用函数：https://github.com/opencobra/cobratoolbox。
Zotero 插件