MOTIVATION: Minimal cut sets (MCSs) for metabolic networks are sets of reactions which, if they are removed from the network, prevent a target reaction from carrying flux. To compute MCSs different methods exist, which may fail to find sufficiently many MCSs for larger genome-scale networks. RESULTS: Here we introduce irreversible minimal cut sets (iMCSs). These are MCSs that consist of irreversible reactions only. The advantage of iMCSs is that they can be computed by projecting the flux cone of the metabolic network on the set of irreversible reactions, which usually leads to a smaller cone. Using oriented matroid theory, we show how the projected cone can be computed efficiently and how this can be applied to find iMCSs even in large genome-scale networks. AVAILABILITY AND IMPLEMENTATION: Software is freely available at https://sourceforge.net/projects/irreversibleminimalcutsets/. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

BACKGROUND: Constraint-based analysis has become a widely used method to study metabolic networks. While some of the associated algorithms can be applied to genome-scale network reconstructions with several thousands of reactions, others are limited to small or medium-sized models. In 2015, Erdrich et al. introduced a method called NetworkReducer, which reduces large metabolic networks to smaller subnetworks, while preserving a set of biological requirements that can be specified by the user. Already in 2001, Burgard et al. developed a mixed-integer linear programming (MILP) approach for computing minimal reaction sets under a given growth requirement. RESULTS: Here we present an MILP approach for computing minimum subnetworks with the given properties. The minimality (with respect to the number of active reactions) is not guaranteed by NetworkReducer, while the method by Burgard et al. does not allow specifying the different biological requirements. Our procedure is about 5-10 times faster than NetworkReducer and can enumerate all minimum subnetworks in case there exist several ones. This allows identifying common reactions that are present in all subnetworks, and reactions appearing in alternative pathways. CONCLUSIONS: Applying complex analysis methods to genome-scale metabolic networks is often not possible in practice. Thus it may become necessary to reduce the size of the network while keeping important functionalities. We propose a MILP solution to this problem. Compared to previous work, our approach is more efficient and allows computing not only one, but even all minimum subnetworks satisfying the required properties.