Dataset Information

Comparison and improvement of algorithms for computing minimal cut sets.

ABSTRACT:

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.

SUBMITTER: Jungreuthmayer C

PROVIDER: S-EPMC3882775 | biostudies-literature | 2013 Nov

REPOSITORIES: biostudies-literature

ACCESS DATA

Publications

Comparison and improvement of algorithms for computing minimal cut sets.

Jungreuthmayer Christian C Nair Govind G Klamt Steffen S Zanghellini Jürgen J

BMC bioinformatics 20131106

<h4>Background</h4>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.<h4>Results</h4>Here we show that by a small extension to the integ ...[more]

PMID: 24191903

Similar Datasets

Project description:BackgroundThe 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 MCS2 approach. In contrast to the Farkas-lemma-based dual system used in earlier studies, the MCS2 approach 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.ResultsIn 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 MCS2 approach (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.ConclusionsOur 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.

Project description:BackgroundActiGraph accelerometers are a widely used tool to objectively measure physical activity (PA) behavior in young children and several validated cut-point sets exist to estimate time spent in different PA intensities (sedentary time, light PA, moderate-to-vigorous PA). Applying different cut-point sets leads to large and meaningful differences in results. So far, only cut-point sets validated for the vertical axis have been compared and only the influence on time spent in moderate-to-vigorous PA has been analyzed.MethodsA range of validated cut-point sets with their respective epoch length was applied to analyze cross-sectional data of the Swiss Preschoolers' Health Study (SPLASHY): 1) Vertical axis in combination with an epoch length of 15 s (VA-15), 2) Vertical axis in combination with an epoch length of 60 s (VA-60) and 3) Vector magnitude in combination with an epoch length of 60 s (VM-60). PA was measured for eight consecutive days using ActiGraph accelerometers (wGT3X-BT). Three days were required to be included in the analysis (minimum two weekdays and one weekend-day with at least ten hours recording per day).ResultsFour hundred forty-five preschoolers (mean age 3.9 ± 0.5 years; 46% girls) had valid accelerometer measurements. A longer epoch (VA-60 vs VA-15) resulted in 2% less sedentary time (ST), 18% more light PA (LPA) and 51% less moderate-to-vigorous PA (MVPA); using the vector magnitude compared to the vertical axis (VM-60 vs VA-60) resulted in 34% less ST, 27% more LPA and 63% more MVPA (all p ≤ 0.001). Comparing all three sets of cut-points, ST ranged from 4.0 to 6.2 h, LPA from 5.1 to 7.6 h and MVPA from 0.8 to 1.6 h.ConclusionsEstimated time spent in different PA intensities was strongly influenced by the choice of cut-point sets. Both, axis selection and epoch length need to be considered when comparing different studies especially when they relate PA behavior to health. The differences in the prevalence of children fulfilling PA guidelines highlight the relevance of these findings.Trial registrationCurrent Controlled Trials ISRCTN41045021 (date of registration: 21.03.2014).

Dataset Information

Comparison and improvement of algorithms for computing minimal cut sets.

Background

Results

Conclusions

Publications

Comparison and improvement of algorithms for computing minimal cut sets.

Similar Datasets

OmicsDI is part of the ELIXIR infrastructure

Tweets