title: Sequential computation of elementary modes and minimal cut sets in genome-scale metabolic networks using alternate integer linear programming.
abstract: BACKGROUND
  Elementary (flux) modes (EMs) have served as a valuable tool for investigating structural and functional properties of metabolic networks. Identification of the full set of EMs in genome-scale networks remains challenging due to combinatorial explosion of EMs in complex networks. It is often, however, that only a small subset of relevant EMs needs to be known, for which optimization-based sequential computation is a useful alternative. Most of the currently available methods along this line are based on the iterative use of mixed integer linear programming (MILP), the effectiveness of which significantly deteriorates as the number of iterations builds up. To alleviate the computational burden associated with the MILP implementation, we here present a novel optimization algorithm termed alternate integer linear programming (AILP).
  
  
  RESULTS
  Our algorithm was designed to iteratively solve a pair of integer programming (IP) and linear programming (LP) to compute EMs in a sequential manner. In each step, the IP identifies a minimal subset of reactions, the deletion of which disables all previously identified EMs. Thus, a subsequent LP solution subject to this reaction deletion constraint becomes a distinct EM. In cases where no feasible LP solution is available, IP-derived reaction deletion sets represent minimal cut sets (MCSs). Despite the additional computation of MCSs, AILP achieved significant time reduction in computing EMs by orders of magnitude. The proposed AILP algorithm not only offers a computational advantage in the EM analysis of genome-scale networks, but also improves the understanding of the linkage between EMs and MCSs.
  
  
  METHODS
  The software is implemented in Matlab, and is provided as supplementary information .
  
  
  BACKGROUND
  hyunseob.song@pnnl.gov.
  
  
  BACKGROUND
  Supplementary data are available at Bioinformatics online.
authors.affiliation: Biological Sciences Division, Pacific Northwest National Laboratory, Richland, WA 99352, USA.
authors.forename: Hyun-Seob
authors.initials: HS
authors.lastname: Song
authors.affiliation: Department of Management, Bar-Ilan University, Ramat Gan 52900, Israel.
authors.forename: Noam
authors.initials: N
authors.lastname: Goldberg
authors.affiliation: Industrial Engineering and Operations Research, IIT Bombay, Powai, Mumbai 400076, India.
authors.forename: Ashutosh
authors.initials: A
authors.lastname: Mahajan
authors.affiliation: School of Chemical Engineering, Purdue University, West Lafayette, IN 47907, USA.
authors.forename: Doraiswami
authors.initials: D
authors.lastname: Ramkrishna
mesh_terms: D000465:Algorithms; D019295:Computational Biology / Q000379:methods*; D053858:Metabolic Networks and Pathways; D008954:Models, Biological; D011382:Programming, Linear; D012984:Software