Cardinality optimization in constraint-based modelling: application to human metabolism.

Area of Science:

• Computational Biology
• Optimization
• Systems Biology

Background:

• Cardinality optimization problems are crucial in constraint-based modeling for tasks like consistency testing and sparse solution computation.
• Existing methods for these computationally complex problems often lack exact and globally optimal solutions within polynomial time.

Purpose of the Study:

• To reformulate cardinality optimization problems in constraint-based modeling into a difference of convex functions.
• To develop and test novel algorithms for approximately solving these reformulated problems.

Main Methods:

• Approximating the zero-norm with nonconvex continuous functions to transform cardinality optimization problems.
• Employing a sequence of convex programs to iteratively solve the reformulated problems.
• Applying the algorithms to biochemical networks, including human metabolic reconstructions.

Main Results:

• Novel algorithms were implemented and numerically tested, demonstrating efficiency and practical utility.
• The developed algorithms match or outperform existing related approaches for cardinality optimization in constraint-based modeling.
• Successful application to extract models for thermodynamic flux balance analysis from human metabolic reconstructions.

Conclusions:

• The proposed approach provides an effective method for solving challenging cardinality optimization problems in constraint-based modeling.
• The algorithms offer a practical and efficient solution for analyzing biochemical networks and extracting relevant models.
• Open-source implementations are available for reproducibility and integration into existing modeling workflows.