Minimal cut sets (MCSs) have emerged as an important branch of constraint-based metabolic modeling, offering a versatile framework for analyzing and engineering metabolic networks. Over the past two decades, MCSs have evolved from a theoretical concept into a powerful tool for identifying tailored metabolic intervention strategies and studying robustness and failure modes of metabolic networks. Successful (experimental) applications range from designing highly efficient microbial cell factories to targeting cancer cell metabolism. This review highlights key conceptual and algorithmic advancements that have transformed MCSs into a flexible methodology applicable to metabolic models of any size. It also provides a comprehensive overview of their applications and concludes with a perspective on future research directions. The review aims to equip both newcomers and experts with the knowledge needed to effectively leverage MCSs for metabolic network analysis and design, therapeutic targeting, and beyond.

MOTIVATION: Flux balance analysis (FBA) is widely recognized as an important method for studying metabolic networks. When incorporating flux measurements of certain reactions into an FBA problem, it is possible that the underlying linear program may become infeasible, e.g. due to measurement or modeling inaccuracies. Furthermore, while the biomass reaction is of central importance in FBA models, its stoichiometry is often a rough estimate and a source of high uncertainty. RESULTS: In this work, we present a method that allows modifications to the biomass reaction stoichiometry as a means to (i) render the FBA problem feasible and (ii) improve the accuracy of the model by corrections in the biomass composition. Optionally, the adjustment of the biomass composition can be used in conjunction with a previously introduced approach for balancing inconsistent fluxes to obtain a feasible FBA system. We demonstrate the value of our approach by analyzing realistic flux measurements of E.coli. In particular, we find that the growth-associated maintenance (GAM) demand of ATP, which is typically integrated with the biomass reaction, is likely overestimated in recent genome-scale models, at least for certain growth conditions. In light of these findings, we discuss issues related to the determination and inclusion of GAM values in constraint-based models. Overall, our method can uncover potential errors and suggest adjustments in the assumed biomass composition in FBA models based on inconsistencies between the model and measured fluxes. AVAILABILITY AND IMPLEMENTATION: The developed method has been implemented in our software tool CNApy available from https://github.com/cnapy-org/CNApy.

SUMMARY: Various constraint-based optimization approaches have been developed for the computational analysis and design of metabolic networks. Herein, we present StrainDesign, a comprehensive Python package that builds upon the COBRApy toolbox and integrates the most popular metabolic design algorithms, including nested strain optimization methods such as OptKnock, RobustKnock and OptCouple as well as the more general minimal cut sets approach. The optimization approaches are embedded in individual modules, which can also be combined for setting up more elaborate strain design problems. Advanced features, such as the efficient integration of GPR rules and the possibility to consider gene and reaction additions or regulatory interventions, have been generalized and are available for all modules. The package uses state-of-the-art preprocessing methods, supports multiple solvers and provides a number of enhanced tools for analyzing computed intervention strategies including 2D and 3D plots of user-selected metabolic fluxes or yields. Furthermore, a user-friendly interface for the StrainDesign package has been implemented in the GUI-based metabolic modeling software CNApy. StrainDesign provides thus a unique and rich framework for computational strain design in Python, uniting many algorithmic developments in the field and allowing modular extension in the future. AVAILABILITY AND IMPLEMENTATION: The StrainDesign package can be retrieved from PyPi, Anaconda and GitHub (https://github.com/klamt-lab/straindesign) and is also part of the latest CNApy package.

SUMMARY: Constraint-based reconstruction and analysis (COBRA) is a widely used modeling framework for analyzing and designing metabolic networks. Here, we present CNApy, an open-source cross-platform desktop application written in Python, which offers a state-of-the-art graphical front-end for the intuitive analysis of metabolic networks with COBRA methods. While the basic look-and-feel of CNApy is similar to the user interface of the MATLAB toolbox CellNetAnalyzer, it provides various enhanced features by using components of the powerful Qt library. CNApy supports a number of standard and advanced COBRA techniques and further functionalities can be easily embedded in its GUI facilitating modular extension in the future. AVAILABILITY AND IMPLEMENTATION: CNApy can be installed via conda and its source code is freely available at https://github.com/cnapy-org/CNApy under the Apache 2 license.

Microbial communities have become a major research focus due to their importance for biogeochemical cycles, biomedicine and biotechnological applications. While some biotechnological applications, such as anaerobic digestion, make use of naturally arising microbial communities, the rational design of microbial consortia for bio-based production processes has recently gained much interest. One class of synthetic microbial consortia is based on specifically designed strains of one species. A common design principle for these consortia is based on division of labor, where the entire production pathway is divided between the different strains to reduce the metabolic burden caused by product synthesis. We first show that classical division of labor does not automatically reduce the metabolic burden when metabolic flux per biomass is analyzed. We then present ASTHERISC (Algorithmic Search of THERmodynamic advantages in Single-species Communities), a new computational approach for designing multi-strain communities of a single-species with the aim to divide a production pathway between different strains such that the thermodynamic driving force for product synthesis is maximized. ASTHERISC exploits the fact that compartmentalization of segments of a product pathway in different strains can circumvent thermodynamic bottlenecks arising when operation of one reaction requires a metabolite with high and operation of another reaction the same metabolite with low concentration. We implemented the ASTHERISC algorithm in a dedicated program package and applied it on E. coli core and genome-scale models with different settings, for example, regarding number of strains or demanded product yield. These calculations showed that, for each scenario, many target metabolites (products) exist where a multi-strain community can provide a thermodynamic advantage compared to a single strain solution. In some cases, a production with sufficiently high yield is thermodynamically only feasible with a community. In summary, the developed ASTHERISC approach provides a promising new principle for designing microbial communities for the bio-based production of chemicals.

BACKGROUND: In order to improve the accuracy of constraint-based metabolic models, several approaches have been developed which intend to integrate additional biological information. Two of these methods, MOMENT and GECKO, incorporate enzymatic (kcat) parameters and enzyme mass constraints to further constrain the space of feasible metabolic flux distributions. While both methods have been proven to deliver useful extensions of metabolic models, they may considerably increase size and complexity of the models and there is currently no tool available to fully automate generation and calibration of such enzyme-constrained models from given stoichiometric models. RESULTS: In this work we present three major developments. We first conceived short MOMENT (sMOMENT), a simplified version of the MOMENT approach, which yields the same predictions as MOMENT but requires significantly fewer variables and enables direct inclusion of the relevant enzyme constraints in the standard representation of a constraint-based model. When measurements of enzyme concentrations are available, these can be included as well leading in the extreme case, where all enzyme concentrations are known, to a model representation that is analogous to the GECKO approach. Second, we developed the AutoPACMEN toolbox which allows an almost fully automated creation of sMOMENT-enhanced stoichiometric metabolic models. In particular, this includes the automatic read-out and processing of relevant enzymatic data from different databases and the reconfiguration of the stoichiometric model with embedded enzymatic constraints. Additionally, tools have been developed to adjust (kcat and enzyme pool) parameters of sMOMENT models based on given flux data. We finally applied the new sMOMENT approach and the AutoPACMEN toolbox to generate an enzyme-constrained version of the E. coli genome-scale model iJO1366 and analyze its key properties and differences with the standard model. In particular, we show that the enzyme constraints improve flux predictions (e.g., explaining overflow metabolism and other metabolic switches) and demonstrate, for the first time, that these constraints can markedly change the spectrum of metabolic engineering strategies for different target products. CONCLUSIONS: The methodological and tool developments presented herein pave the way for a simplified and routine construction and analysis of enzyme-constrained metabolic models.

Abstract Background 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 MCS2approach. In contrast to the Farkas-lemma-based dual system used in earlier studies, the MCS2approach 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. Results 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 MCS2approach (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. Conclusions 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.

The concept of minimal cut sets (MCS) provides a flexible framework for analyzing properties of metabolic networks and for computing metabolic intervention strategies. In particular, it has been used to support the targeted design of microbial strains for bio-based production processes. Herein we present a number of major extensions that generalize the existing MCS approach and broaden its scope for applications in metabolic engineering. We first introduce a modified approach to integrate gene-protein-reaction associations (GPR) in the metabolic network structure for the computation of gene-based intervention strategies. In particular, we present a set of novel compression rules for GPR associations, which effectively speedup the computation of gene-based MCS by a factor of up to one order of magnitude. These rules are not specific for MCS and as well applicable to other computational strain design methods. Second, we enhance the MCS framework by allowing the definition of multiple target (undesired) and multiple protected (desired) regions. This enables precise tailoring of the metabolic solution space of the designed strain with unlimited flexibility. Together with further generalizations such as individual cost factors for each intervention, direct combinations of reaction/gene deletions and additions as well as the possibility to search for substrate co-feeding strategies, the scope of the MCS framework could be broadly extended. We demonstrate the applicability and performance benefits of the described developments by computing (gene-based) Escherichia coli strain designs for the bio-based production of 2,3-butanediol, a chemical, that has recently received much attention in the field of metabolic engineering. With our extended framework, we could identify promising strain designs that were formerly unpredictable, including those based on substrate co-feeding.

MOTIVATION: The computer-aided design of metabolic intervention strategies has become a key component of an integrated metabolic engineering approach and a broad range of methods and algorithms has been developed for this task. Many of these algorithms enforce coupling of growth with product synthesis and may return thousands of possible intervention strategies from which the most suitable strategy must then be selected. RESULTS: This work focuses on how to evaluate and rank, in a meaningful way, a given pool of computed metabolic engineering strategies for growth-coupled product synthesis. Apart from straightforward criteria, such as a preferably small number of necessary interventions, a reasonable growth rate and a high product yield, we present several new criteria useful to pick the most suitable intervention strategy. Among others, we investigate the robustness of the intervention strategies by searching for metabolites that may disrupt growth coupling when accumulated or secreted and by checking whether the interventions interrupt pathways at their origin (preferable) or at downstream steps. We also assess thermodynamic properties of the pathway(s) favored by the intervention strategy. Furthermore, strategies that have a significant overlap with alternative solutions are ranked higher because they provide flexibility in implementation. We also introduce the notion of equivalence classes for grouping intervention strategies with identical solution spaces. Our ranking procedure involves in total ten criteria and we demonstrate its applicability by assessing knockout-based intervention strategies computed in a genome-scale model of E.coli for the growth-coupled synthesis of l-methionine and of the heterologous product 1,4-butanediol. AVAILABILITY AND IMPLEMENTATION: The MATLAB scripts that were used to characterize and rank the example intervention strategies are available at http://www2.mpi-magdeburg.mpg.de/projects/cna/etcdownloads.html. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

Constraint-based modeling (CBM) is increasingly used to analyze the metabolism of complex microbial communities involved in ecology, biomedicine, and various biotechnological processes. While CBM is an established framework for studying the metabolism of single species with linear stoichiometric models, CBM of communities with balanced growth is more complicated, not only due to the larger size of the multi-species metabolic network but also because of the bilinear nature of the resulting community models. Moreover, the solution space of these community models often contains biologically unrealistic solutions, which, even with model linearization and under application of certain objective functions, cannot easily be excluded. Here we present RedCom, a new approach to build reduced community models in which the metabolisms of the participating organisms are represented by net conversions computed from the respective single-species networks. By discarding (single-species) net conversions that violate a minimality criterion in the exchange fluxes, it is ensured that unrealistic solutions in the community model are excluded where a species altruistically synthesizes large amounts of byproducts (instead of biomass) to fulfill the requirements of other species. We employed the RedCom approach for modeling communities of up to nine organisms involved in typical degradation steps of anaerobic digestion in biogas plants. Compared to full (bilinear and linearized) community models, we found that the reduced community models obtained with RedCom are not only much smaller but allow, also in the largest model with nine species, extensive calculations required to fully characterize the solution space and to reveal key properties of communities with maximum methane yield and production rates. Furthermore, the predictive power of the reduced community models is significantly larger because they predict much smaller ranges of feasible community compositions and exchange fluxes still being consistent with measurements obtained from enrichment cultures. For an enrichment culture for growth on ethanol, we also used metaproteomic data to further constrain the solution space of the community models. Both model and proteomic data indicated a dominance of acetoclastic methanogens (Methanosarcinales) and Desulfovibrionales being the least abundant group in this microbial community.

Modern methods for the inference of cellular networks from experimental data often express nondeterminism by proposing an ensemble of candidate models with similar properties. To further discriminate among these model candidates, new experiments need to be carried out. Theoretically, the number of possible experiments is exponential in the number of possible perturbations. In praxis, experiments are expensive and usually there exist several constraints limiting which experiments can be performed. Limiting factors may exist on the combinations of perturbations that are technically possible, which components can be measured, and limitations on the number of affordable experiments. Further, not all experiments are equally well suited to discriminate model candidates. Therefore, the goal of optimal experiment design is to determine those experiments that discriminate most of the candidates while minimizing the costs. We present an approach for experiment planning with interaction graph models and sign consistency methods. This new approach can be used in combination with methods for network inference and consistency checking. The proposed method determines experiments which are most suitable to deliver results that reduce the number of candidate models. We applied our method to study the Erythropoietin signal transduction in human kidney cells HEK293. We first used simulated experiment data from an ODE model to demonstrate in silico that our experimental design results in the inference of the gold standard model. Finally, we used the approach to plan in vivo experiments that enabled us to discriminate model candidates for the Erythropoietin signal transduction in this cell line.

Constraint-based modeling techniques have become a standard tool for the in silico analysis of metabolic networks. To further improve their accuracy, recent methodological developments focused on integration of thermodynamic information in metabolic models to assess the feasibility of flux distributions by thermodynamic driving forces. Here we present OptMDFpathway, a method that extends the recently proposed framework of Max-min Driving Force (MDF) for thermodynamic pathway analysis. Given a metabolic network model, OptMDFpathway identifies both the optimal MDF for a desired phenotypic behavior as well as the respective pathway itself that supports the optimal driving force. OptMDFpathway is formulated as a mixed-integer linear program and is applicable to genome-scale metabolic networks. As an important theoretical result, we also show that there exists always at least one elementary mode in the network that reaches the maximal MDF. We employed our new approach to systematically identify all substrate-product combinations in Escherichia coli where product synthesis allows for concomitant net CO2 assimilation via thermodynamically feasible pathways. Although biomass synthesis cannot be coupled to net CO2 fixation in E. coli we found that as many as 145 of the 949 cytosolic carbon metabolites contained in the genome-scale model iJO1366 enable net CO2 incorporation along thermodynamically feasible pathways with glycerol as substrate and 34 with glucose. The most promising products in terms of carbon assimilation yield and thermodynamic driving forces are orotate, aspartate and the C4-metabolites of the tricarboxylic acid cycle. We also identified thermodynamic bottlenecks frequently limiting the maximal driving force of the CO2-fixing pathways. Our results indicate that heterotrophic organisms like E. coli hold a possibly underestimated potential for CO2 assimilation which may complement existing biotechnological approaches for capturing CO2. Furthermore, we envision that the developed OptMDFpathway approach can be used for many other applications within the framework of constrained-based modeling and for rational design of metabolic networks.

Elementary flux modes (EFMs) emerged as a formal concept to describe metabolic pathways and have become an established tool for constraint-based modeling and metabolic network analysis. EFMs are characteristic (support-minimal) vectors of the flux cone that contains all feasible steady-state flux vectors of a given metabolic network. EFMs account for (homogeneous) linear constraints arising from reaction irreversibilities and the assumption of steady state; however, other (inhomogeneous) linear constraints, such as minimal and maximal reaction rates frequently used by other constraint-based techniques (such as flux balance analysis [FBA]), cannot be directly integrated. These additional constraints further restrict the space of feasible flux vectors and turn the flux cone into a general flux polyhedron in which the concept of EFMs is not directly applicable anymore. For this reason, there has been a conceptual gap between EFM-based (pathway) analysis methods and linear optimization (FBA) techniques, as they operate on different geometric objects. One approach to overcome these limitations was proposed ten years ago and is based on the concept of elementary flux vectors (EFVs). Only recently has the community started to recognize the potential of EFVs for metabolic network analysis. In fact, EFVs exactly represent the conceptual development required to generalize the idea of EFMs from flux cones to flux polyhedra. This work aims to present a concise theoretical and practical introduction to EFVs that is accessible to a broad audience. We highlight the close relationship between EFMs and EFVs and demonstrate that almost all applications of EFMs (in flux cones) are possible for EFVs (in flux polyhedra) as well. In fact, certain properties can only be studied with EFVs. Thus, we conclude that EFVs provide a powerful and unifying framework for constraint-based modeling of metabolic networks.

MOTIVATION: Robustness, the ability of biological networks to uphold their functionality in spite of perturbations, is a key characteristic of all living systems. Although several theoretical approaches have been developed to formalize robustness, it still eludes an exact quantification. Here, we present a rigorous and quantitative approach for the structural robustness of metabolic networks by measuring their ability to tolerate random reaction (or gene) knockouts. RESULTS: In analogy to reliability theory, based on an explicit consideration of all possible knockout sets, we exactly quantify the probability of failure for a given network function (e.g. growth). This measure can be computed if the network's minimal cut sets (MSCs) are known. We show that even in genome-scale metabolic networks the probability of (network) failure can be reliably estimated from MSCs with lowest cardinalities. We demonstrate the applicability of our theory by analyzing the structural robustness of multiple Enterobacteriaceae and Blattibacteriaceae and show a dramatically low structural robustness for the latter. We find that structural robustness develops from the ability to proliferate in multiple growth environments consistent with experimentally found knowledge. CONCLUSION: The probability of (network) failure provides thus a reliable and easily computable measure of structural robustness and redundancy in (genome-scale) metabolic networks. AVAILABILITY AND IMPLEMENTATION: Source code is available under the GNU General Public License at https://github.com/mpgerstl/networkRobustnessToolbox CONTACT: [email protected] SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

BACKGROUND: The inference of gene regulatory networks (GRNs) from transcriptional expression profiles is challenging, predominantly due to its underdetermined nature. One important consequence of underdetermination is the existence of many possible solutions to this inference. Our previously proposed ensemble inference algorithm TRaCE addressed this issue by inferring an ensemble of network directed graphs (digraphs) using differential gene expressions from gene knock-out (KO) experiments. However, TRaCE could not deal with the mode of the transcriptional regulations (activation or repression), an important feature of GRNs. RESULTS: In this work, we developed a new algorithm called TRaCE+ for the inference of an ensemble of signed GRN digraphs from transcriptional expression data of gene KO experiments. The sign of the edges indicates whether the regulation is an activation (positive) or a repression (negative). TRaCE+ generates the upper and lower bounds of the ensemble, which define uncertain regulatory interactions that could not be verified by the data. As demonstrated in the case studies using Escherichia coli GRN and 100-gene gold-standard GRNs from DREAM 4 network inference challenge, by accounting for regulatory signs, TRaCE+ could extract more information from the KO data than TRaCE, leading to fewer uncertain edges. Importantly, iterating TRaCE+ with an optimal design of gene KOs could resolve the underdetermined issue of GRN inference in much fewer KO experiments than using TRaCE. CONCLUSIONS: TRaCE+ expands the applications of ensemble GRN inference strategy by accounting for the mode of the gene regulatory interactions. In comparison to TRaCE, TRaCE+ enables a better utilization of gene KO data, thereby reducing the cost of tackling underdetermined GRN inference. TRaCE+ subroutines for MATLAB are freely available at the following website: http://www.cabsel.ethz.ch/tools/trace.html .

MOTIVATION: Stoichiometric and constraint-based methods of computational strain design have become an important tool for rational metabolic engineering. One of those relies on the concept of constrained minimal cut sets (cMCSs). However, as most other techniques, cMCSs may consider only reaction (or gene) knockouts to achieve a desired phenotype. RESULTS: We generalize the cMCSs approach to constrained regulatory MCSs (cRegMCSs), where up/downregulation of reaction rates can be combined along with reaction deletions. We show that flux up/downregulations can virtually be treated as cuts allowing their direct integration into the algorithmic framework of cMCSs. Because of vastly enlarged search spaces in genome-scale networks, we developed strategies to (optionally) preselect suitable candidates for flux regulation and novel algorithmic techniques to further enhance efficiency and speed of cMCSs calculation. We illustrate the cRegMCSs approach by a simple example network and apply it then by identifying strain designs for ethanol production in a genome-scale metabolic model of Escherichia coli. The results clearly show that cRegMCSs combining reaction deletions and flux regulations provide a much larger number of suitable strain designs, many of which are significantly smaller relative to cMCSs involving only knockouts. Furthermore, with cRegMCSs, one may also enable the fine tuning of desired behaviours in a narrower range. The new cRegMCSs approach may thus accelerate the implementation of model-based strain designs for the bio-based production of fuels and chemicals. AVAILABILITY AND IMPLEMENTATION: MATLAB code and the examples can be downloaded at http://www.mpi-magdeburg.mpg.de/projects/cna/etcdownloads.html. CONTACT: [email protected] or [email protected] SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

BACKGROUND: A rapidly growing amount of knowledge about signaling and gene regulatory networks is available in databases such as KEGG, Reactome, or RegulonDB. There is an increasing need to relate this knowledge to high-throughput data in order to (in)validate network topologies or to decide which interactions are present or inactive in a given cell type under a particular environmental condition. Interaction graphs provide a suitable representation of cellular networks with information flows and methods based on sign consistency approaches have been shown to be valuable tools to (i) predict qualitative responses, (ii) to test the consistency of network topologies and experimental data, and (iii) to apply repair operations to the network model suggesting missing or wrong interactions. RESULTS: We present a framework to unify different notions of sign consistency and propose a refined method for data discretization that considers uncertainties in experimental profiles. We furthermore introduce a new constraint to filter undesired model behaviors induced by positive feedback loops. Finally, we generalize the way predictions can be made by the sign consistency approach. In particular, we distinguish strong predictions (e.g. increase of a node level) and weak predictions (e.g., node level increases or remains unchanged) enlarging the overall predictive power of the approach. We then demonstrate the applicability of our framework by confronting a large-scale gene regulatory network model of Escherichia coli with high-throughput transcriptomic measurements. CONCLUSION: Overall, our work enhances the flexibility and power of the sign consistency approach for the prediction of the behavior of signaling and gene regulatory networks and, more generally, for the validation and inference of these networks.

Signaling pathways are characterized by crosstalk, feedback and feedforward mechanisms giving rise to highly complex and cell-context specific signaling networks. Dissecting the underlying relations is crucial to predict the impact of targeted perturbations. However, a major challenge in identifying cell-context specific signaling networks is the enormous number of potentially possible interactions. Here, we report a novel hybrid mathematical modeling strategy to systematically unravel hepatocyte growth factor (HGF) stimulated phosphoinositide-3-kinase (PI3K) and mitogen activated protein kinase (MAPK) signaling, which critically contribute to liver regeneration. By combining time-resolved quantitative experimental data generated in primary mouse hepatocytes with interaction graph and ordinary differential equation modeling, we identify and experimentally validate a network structure that represents the experimental data best and indicates specific crosstalk mechanisms. Whereas the identified network is robust against single perturbations, combinatorial inhibition strategies are predicted that result in strong reduction of Akt and ERK activation. Thus, by capitalizing on the advantages of the two modeling approaches, we reduce the high combinatorial complexity and identify cell-context specific signaling networks.

One ultimate goal of metabolic network modeling is the rational redesign of biochemical networks to optimize the production of certain compounds by cellular systems. Although several constraint-based optimization techniques have been developed for this purpose, methods for systematic enumeration of intervention strategies in genome-scale metabolic networks are still lacking. In principle, Minimal Cut Sets (MCSs; inclusion-minimal combinations of reaction or gene deletions that lead to the fulfilment of a given intervention goal) provide an exhaustive enumeration approach. However, their disadvantage is the combinatorial explosion in larger networks and the requirement to compute first the elementary modes (EMs) which itself is impractical in genome-scale networks. We present MCSEnumerator, a new method for effective enumeration of the smallest MCSs (with fewest interventions) in genome-scale metabolic network models. For this we combine two approaches, namely (i) the mapping of MCSs to EMs in a dual network, and (ii) a modified algorithm by which shortest EMs can be effectively determined in large networks. In this way, we can identify the smallest MCSs by calculating the shortest EMs in the dual network. Realistic application examples demonstrate that our algorithm is able to list thousands of the most efficient intervention strategies in genome-scale networks for various intervention problems. For instance, for the first time we could enumerate all synthetic lethals in E.coli with combinations of up to 5 reactions. We also applied the new algorithm exemplarily to compute strain designs for growth-coupled synthesis of different products (ethanol, fumarate, serine) by E.coli. We found numerous new engineering strategies partially requiring less knockouts and guaranteeing higher product yields (even without the assumption of optimal growth) than reported previously. The strength of the presented approach is that smallest intervention strategies can be quickly calculated and screened with neither network size nor the number of required interventions posing major challenges.

MOTIVATION: Systems Genetics approaches, in particular those relying on genetical genomics data, put forward a new paradigm of large-scale genome and network analysis. These methods use naturally occurring multi-factorial perturbations (e.g. polymorphisms) in properly controlled and screened genetic crosses to elucidate causal relationships in biological networks. However, although genetical genomics data contain rich information, a clear dissection of causes and effects as required for reconstructing gene regulatory networks is not easily possible. RESULTS: We present a framework for reconstructing gene regulatory networks from genetical genomics data where genotype and phenotype correlation measures are used to derive an initial graph which is subsequently reduced by pruning strategies to minimize false positive predictions. Applied to realistic simulated genetic data from a recent DREAM challenge, we demonstrate that our approach is simple yet effective and outperforms more complex methods (including the best performer) with respect to (i) reconstruction quality (especially for small sample sizes) and (ii) applicability to large data sets due to relatively low computational costs. We also present reconstruction results from real genetical genomics data of yeast. AVAILABILITY: A MATLAB implementation (script) of the reconstruction framework is available at www.mpi-magdeburg.mpg.de/projects/cna/etcdownloads.html CONTACT: [email protected].

BACKGROUND: Constrained minimal cut sets (cMCSs) have recently been introduced as a framework to enumerate minimal genetic intervention strategies for targeted optimization of metabolic networks. Two different algorithmic schemes (adapted Berge algorithm and binary integer programming) have been proposed to compute cMCSs from elementary modes. However, in their original formulation both algorithms are not fully comparable. RESULTS: Here we show that by a small extension to the integer program both methods become equivalent. Furthermore, based on well-known preprocessing procedures for integer programming we present efficient preprocessing steps which can be used for both algorithms. We then benchmark the numerical performance of the algorithms in several realistic medium-scale metabolic models. The benchmark calculations reveal (i) that these preprocessing steps can lead to an enormous speed-up under both algorithms, and (ii) that the adapted Berge algorithm outperforms the binary integer approach. CONCLUSIONS: Generally, both of our new implementations are by at least one order of magnitude faster than other currently available implementations.

Cross-referencing experimental data with our current knowledge of signaling network topologies is one central goal of mathematical modeling of cellular signal transduction networks. We present a new methodology for data-driven interrogation and training of signaling networks. While most published methods for signaling network inference operate on Bayesian, Boolean, or ODE models, our approach uses integer linear programming (ILP) on interaction graphs to encode constraints on the qualitative behavior of the nodes. These constraints are posed by the network topology and their formulation as ILP allows us to predict the possible qualitative changes (up, down, no effect) of the activation levels of the nodes for a given stimulus. We provide four basic operations to detect and remove inconsistencies between measurements and predicted behavior: (i) find a topology-consistent explanation for responses of signaling nodes measured in a stimulus-response experiment (if none exists, find the closest explanation); (ii) determine a minimal set of nodes that need to be corrected to make an inconsistent scenario consistent; (iii) determine the optimal subgraph of the given network topology which can best reflect measurements from a set of experimental scenarios; (iv) find possibly missing edges that would improve the consistency of the graph with respect to a set of experimental scenarios the most. We demonstrate the applicability of the proposed approach by interrogating a manually curated interaction graph model of EGFR/ErbB signaling against a library of high-throughput phosphoproteomic data measured in primary hepatocytes. Our methods detect interactions that are likely to be inactive in hepatocytes and provide suggestions for new interactions that, if included, would significantly improve the goodness of fit. Our framework is highly flexible and the underlying model requires only easily accessible biological knowledge. All related algorithms were implemented in a freely available toolbox SigNetTrainer making it an appealing approach for various applications.

MOTIVATION: Elementary modes (EMs) and minimal cut sets (MCSs) provide important techniques for metabolic network modeling. Whereas EMs describe minimal subnetworks that can function in steady state, MCSs are sets of reactions whose removal will disable certain network functions. Effective algorithms were developed for EM computation while calculation of MCSs is typically addressed by indirect methods requiring the computation of EMs as initial step. RESULTS: In this contribution, we provide a method that determines MCSs directly without calculating the EMs. We introduce a duality framework for metabolic networks where the enumeration of MCSs in the original network is reduced to identifying the EMs in a dual network. As a further extension, we propose a generalization of MCSs in metabolic networks by allowing the combination of inhomogeneous constraints on reaction rates. This framework provides a promising tool to open the concept of EMs and MCSs to a wider class of applications. CONTACT: [email protected]; [email protected] SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

MOTIVATION: Distinguishing direct from indirect influences is a central issue in reverse engineering of biological networks because it facilitates detection and removal of false positive edges. Transitive reduction is one approach for eliminating edges reflecting indirect effects but its use in reconstructing cyclic interaction graphs with true redundant structures is problematic. RESULTS: We present TRANSWESD, an elaborated variant of TRANSitive reduction for WEighted Signed Digraphs that overcomes conceptual problems of existing versions. Major changes and improvements concern: (i) new statistical approaches for generating high-quality perturbation graphs from systematic perturbation experiments; (ii) the use of edge weights (association strengths) for recognizing true redundant structures; (iii) causal interpretation of cycles; (iv) relaxed definition of transitive reduction; and (v) approximation algorithms for large networks. Using standardized benchmark tests, we demonstrate that our method outperforms existing variants of transitive reduction and is, despite its conceptual simplicity, highly competitive with other reverse engineering methods.

BACKGROUND: Interaction graphs (signed directed graphs) provide an important qualitative modeling approach for Systems Biology. They enable the analysis of causal relationships in cellular networks and can even be useful for predicting qualitative aspects of systems dynamics. Fundamental issues in the analysis of interaction graphs are the enumeration of paths and cycles (feedback loops) and the calculation of shortest positive/negative paths. These computational problems have been discussed only to a minor extent in the context of Systems Biology and in particular the shortest signed paths problem requires algorithmic developments. RESULTS: We first review algorithms for the enumeration of paths and cycles and show that these algorithms are superior to a recently proposed enumeration approach based on elementary-modes computation. The main part of this work deals with the computation of shortest positive/negative paths, an NP-complete problem for which only very few algorithms are described in the literature. We propose extensions and several new algorithm variants for computing either exact results or approximations. Benchmarks with various concrete biological networks show that exact results can sometimes be obtained in networks with several hundred nodes. A class of even larger graphs can still be treated exactly by a new algorithm combining exhaustive and simple search strategies. For graphs, where the computation of exact solutions becomes time-consuming or infeasible, we devised an approximative algorithm with polynomial complexity. Strikingly, in realistic networks (where a comparison with exact results was possible) this algorithm delivered results that are very close or equal to the exact values. This phenomenon can probably be attributed to the particular topology of cellular signaling and regulatory networks which contain a relatively low number of negative feedback loops. CONCLUSION: The calculation of shortest positive/negative paths and cycles in interaction graphs is an important method for network analysis in Systems Biology. This contribution draws the attention of the community to this important computational problem and provides a number of new algorithms, partially specifically tailored for biological interaction graphs. All algorithms have been implemented in the CellNetAnalyzer framework which can be downloaded for academic use at http://www.mpi-magdeburg.mpg.de/projects/cna/cna.html.

3,41Max Planck Institute for Dynamics of Complex Technical Systems, Magdeburg, Germany, 2Institute for Mathematical Optimization, Faculty of Mathematics, Otto-von-Guericke University Magdeburg, Magdeburg, Germany, 3Institute for Bioinformatics and Systems Biology, Helmholtz Zentrum Mu¨nchen—German Research Center forEnvironmental Health, Neuherberg, Germany, 4Max Planck Institute for Dynamics and Self-Organization, Go¨ttingen, Germany

The epidermal growth factor receptor (EGFR) signaling pathway is probably the best-studied receptor system in mammalian cells, and it also has become a popular example for employing mathematical modeling to cellular signaling networks. Dynamic models have the highest explanatory and predictive potential; however, the lack of kinetic information restricts current models of EGFR signaling to smaller sub-networks. This work aims to provide a large-scale qualitative model that comprises the main and also the side routes of EGFR/ErbB signaling and that still enables one to derive important functional properties and predictions. Using a recently introduced logical modeling framework, we first examined general topological properties and the qualitative stimulus-response behavior of the network. With species equivalence classes, we introduce a new technique for logical networks that reveals sets of nodes strongly coupled in their behavior. We also analyzed a model variant which explicitly accounts for uncertainties regarding the logical combination of signals in the model. The predictive power of this model is still high, indicating highly redundant sub-structures in the network. Finally, one key advance of this work is the introduction of new techniques for assessing high-throughput data with logical models (and their underlying interaction graph). By employing these techniques for phospho-proteomic data from primary hepatocytes and the HepG2 cell line, we demonstrate that our approach enables one to uncover inconsistencies between experimental results and our current qualitative knowledge and to generate new hypotheses and conclusions. Our results strongly suggest that the Rac/Cdc42 induced p38 and JNK cascades are independent of PI3K in both primary hepatocytes and HepG2. Furthermore, we detected that the activation of JNK in response to neuregulin follows a PI3K-dependent signaling pathway.

Cellular decisions are determined by complex molecular interaction networks. Large-scale signaling networks are currently being reconstructed, but the kinetic parameters and quantitative data that would allow for dynamic modeling are still scarce. Therefore, computational studies based upon the structure of these networks are of great interest. Here, a methodology relying on a logical formalism is applied to the functional analysis of the complex signaling network governing the activation of T cells via the T cell receptor, the CD4/CD8 co-receptors, and the accessory signaling receptor CD28. Our large-scale Boolean model, which comprises 94 nodes and 123 interactions and is based upon well-established qualitative knowledge from primary T cells, reveals important structural features (e.g., feedback loops and network-wide dependencies) and recapitulates the global behavior of this network for an array of published data on T cell activation in wild-type and knock-out conditions. More importantly, the model predicted unexpected signaling events after antibody-mediated perturbation of CD28 and after genetic knockout of the kinase Fyn that were subsequently experimentally validated. Finally, we show that the logical model reveals key elements and potential failure modes in network functioning and provides candidates for missing links. In summary, our large-scale logical model for T cell activation proved to be a promising in silico tool, and it inspires immunologists to ask new questions. We think that it holds valuable potential in foreseeing the effects of drugs and network modifications.

BACKGROUND: Structural analysis of cellular interaction networks contributes to a deeper understanding of network-wide interdependencies, causal relationships, and basic functional capabilities. While the structural analysis of metabolic networks is a well-established field, similar methodologies have been scarcely developed and applied to signaling and regulatory networks. RESULTS: We propose formalisms and methods, relying on adapted and partially newly introduced approaches, which facilitate a structural analysis of signaling and regulatory networks with focus on functional aspects. We use two different formalisms to represent and analyze interaction networks: interaction graphs and (logical) interaction hypergraphs. We show that, in interaction graphs, the determination of feedback cycles and of all the signaling paths between any pair of species is equivalent to the computation of elementary modes known from metabolic networks. Knowledge on the set of signaling paths and feedback loops facilitates the computation of intervention strategies and the classification of compounds into activators, inhibitors, ambivalent factors, and non-affecting factors with respect to a certain species. In some cases, qualitative effects induced by perturbations can be unambiguously predicted from the network scheme. Interaction graphs however, are not able to capture AND relationships which do frequently occur in interaction networks. The consequent logical concatenation of all the arcs pointing into a species leads to Boolean networks. For a Boolean representation of cellular interaction networks we propose a formalism based on logical (or signed) interaction hypergraphs, which facilitates in particular a logical steady state analysis (LSSA). LSSA enables studies on the logical processing of signals and the identification of optimal intervention points (targets) in cellular networks. LSSA also reveals network regions whose parametrization and initial states are crucial for the dynamic behavior. We have implemented these methods in our software tool CellNetAnalyzer (successor of FluxAnalyzer) and illustrate their applicability using a logical model of T-Cell receptor signaling providing non-intuitive results regarding feedback loops, essential elements, and (logical) signal processing upon different stimuli. CONCLUSION: The methods and formalisms we propose herein are another step towards the comprehensive functional analysis of cellular interaction networks. Their potential, shown on a realistic T-cell signaling model, makes them a promising tool.

BACKGROUND: The analysis of biochemical networks using a logical (Boolean) description is an important approach in Systems Biology. Recently, new methods have been proposed to analyze large signaling and regulatory networks using this formalism. Even though there is a large number of tools to set up models describing biological networks using a biochemical (kinetic) formalism, however, they do not support logical models. RESULTS: Herein we present a flexible framework for setting up large logical models in a visual manner with the software tool ProMoT. An easily extendible library, ProMoT's inherent modularity and object-oriented concept as well as adaptive visualization techniques provide a versatile environment. Both the graphical and the textual description of the logical model can be exported to different formats. CONCLUSION: New features of ProMoT facilitate an efficient set-up of large Boolean models of biochemical interaction networks. The modeling environment is flexible; it can easily be adapted to specific requirements, and new extensions can be introduced. ProMoT is freely available from http://www.mpi-magdeburg.mpg.de/projects/promot/.

MOTIVATION: Structural studies of metabolic networks yield deeper insight into topology, functionality and capabilities of the metabolisms of different organisms. Here, we address the analysis of potential failure modes in metabolic networks whose occurrence will render the network structurally incapable of performing certain functions. Such studies will help to identify crucial parts in the network structure and to find suitable targets for repressing undesired metabolic functions. RESULTS: We introduce the concept of minimal cut sets for biochemical networks. A minimal cut set (MCS) is a minimal (irreducible) set of reactions in the network whose inactivation will definitely lead to a failure in certain network functions. We present an algorithm which enables the computation of the MCSs in a given network related to user-defined objective reactions. This algorithm operates on elementary modes. A number of potential applications are outlined, including network verifications, phenotype predictions, assessing structural robustness and fragility, metabolic flux analysis and target identification in drug discovery. Applications are illustrated by the MCSs in the central metabolism of Escherichia coli for growth on different substrates. AVAILABILITY: Computation and analysis of MCSs is an additional feature of the FluxAnalyzer (freely available for academic users upon request, special contracts for industrial companies; see web page below). SUPPLEMENTARY INFORMATION: http://www.mpi-magdeburg.mpg.de/projects/fluxanalyzer

BACKGROUND: Metabolic pathway analysis has been recognized as a central approach to the structural analysis of metabolic networks. The concept of elementary (flux) modes provides a rigorous formalism to describe and assess pathways and has proven to be valuable for many applications. However, computing elementary modes is a hard computational task. In recent years we assisted in a multiplication of algorithms dedicated to it. We require a summarizing point of view and a continued improvement of the current methods. RESULTS: We show that computing the set of elementary modes is equivalent to computing the set of extreme rays of a convex cone. This standard mathematical representation provides a unified framework that encompasses the most prominent algorithmic methods that compute elementary modes and allows a clear comparison between them. Taking lessons from this benchmark, we here introduce a new method, the binary approach, which computes the elementary modes as binary patterns of participating reactions from which the respective stoichiometric coefficients can be computed in a post-processing step. We implemented the binary approach in FluxAnalyzer 5.1, a software that is free for academics. The binary approach decreases the memory demand up to 96% without loss of speed giving the most efficient method available for computing elementary modes to date. CONCLUSIONS: The equivalence between elementary modes and extreme ray computations offers opportunities for employing tools from polyhedral computation for metabolic pathway analysis. The new binary approach introduced herein was derived from this general theoretical framework and facilitates the computation of elementary modes in considerably larger networks.

MOTIVATION: The analysis of structure, pathways and flux distributions in metabolic networks has become an important approach for understanding the functionality of metabolic systems. The need of a user-friendly platform for stoichiometric modeling of metabolic networks in silico is evident. RESULTS: The FluxAnalyzer is a package for MATLAB and facilitates integrated pathway and flux analysis for metabolic networks within a graphical user interface. Arbitrary metabolic network models can be composed by instances of four types of network elements. The abstract network model is linked with network graphics leading to interactive flux maps which allow for user input and display of calculation results within a network visualization. Therein, a large and powerful collection of tools and algorithms can be applied interactively including metabolic flux analysis, flux optimization, detection of topological features and pathway analysis by elementary flux modes or extreme pathways. The FluxAnalyzer has been applied and tested for complex networks with more than 500,000 elementary modes. Some aspects of the combinatorial complexity of pathway analysis in metabolic networks are discussed. AVAILABILITY: Upon request from the corresponding author. Free for academic users (license agreement). Special contracts are available for industrial corporations. SUPPLEMENTARY INFORMATION: http://www.mpi-magdeburg.mpg.de/projects/fluxanalyzer.