Enumeration and Cartesian Product Decomposition of Alternate Optimal Fluxes in Cellular Metabolism
提出一个框架，用于寻找和分析细胞代谢线性规划模型的所有最优解，包括生成替代最优通量的方法以及将最优解矩阵分解为独立子集的算法，并应用于致病菌代谢重建分析。
We introduce a framework for finding and analyzing all optimal solutions to a linear-programming-based model for cellular metabolism. The implementation of a pivoting-based method for generating alternate optimal reaction fluxes is described. We present a novel strongly polynomial algorithm to decompose a matrix of alternate optimal solutions of an optimization problem into independent subsets of variables and their respective alternate solutions. The matrix can be reconstructed as a Cartesian product of these subsets of alternate solutions. We demonstrate that our strategy for enumeration is more efficient than other methods, and that our Cartesian product matrix decomposition can quickly recover independent substructures. The framework is applied to analyze the metabolic reconstruction of a disease-causing organism, revealing metabolic pathways that are independently regulated. Data and the online supplement are available at https://doi.org/10.1287/ijoc.2016.0724 .