Optfill: A Novel Optimization-Based Tool to Automate the Gapfilling of Genome-Scale Metabolic Models

Computational modeling of metabolism is now an indispensable tool to drive the processes of understanding, discovering, and redesigning of biological systems. By defining the metabolic space, genome-scale metabolic (GSM) models can assess allowable cellular phenotypes and explore metabolic potential under specific environmental and/or genetic conditions. GSM model curation processes typically involve gleaning information on gene annotations and reactions from major public databases; however, incomplete gene annotations and system knowledge leaves gaps in any GSM reconstruction. Gapfill (and numerous similar tools) automates addressing of these gaps, applying Mixed Integer Linear Programming (MILP) and utilizes functionalities from related organisms or changing the direction of existing reactions to fill gaps on a per-gap basis. This is done without consideration of thermodynamically infeasible cycle (TIC) avoidance. Hence, Gapfill makes redundant changes and increases the number of TICs in GSM models, which ultimately require further manual scrutiny. To address the limitations of current automated gapfilling procedures, introduced here is an improved method, namely OptFill, which performs automated gapfilling. OptFill applies two MILP problems in series, which addresses the fixes needed on a per-GSM model basis. The first optimization problem (single-level MILP) seeks to identify all TICs which could be created by adding new functionalities to the GSM model. The second optimization problem (multi-level MILP) seeks to maximize the number of gap metabolites fixed subject to minimizing the number of new functionalities added. Included in the second problem is an integer cut based on the results of the first problem, which prevents any solution containing TICs from being viable solutions. OptFill has thus far been successfully applied to metabolic models of a generic test system, Saccharomyces cerevisiae (baker’s yeast), Exophiala dermatitidis. Thus, OptFill provides a distinct advantage over the traditional Gapfill approach in the extent of automation and needed manual curation.