Speaker:   Philippe Dague
  Laboratoire de Recherche en Informatique
  Université Paris-Sud

Title:   Characterizing and computing metabolic pathways under biological constraints: revisiting the concept of elementary flux mode

Metabolic pathway analysis is a key method to study metabolism, and thus critical for improving our understanding of the functioning of living systems and its application in agriculture, livestock farming, agri-food industry, energy production and health. The study of such metabolic pathways at steady state relies on elementary flux modes (EFMs) whose set of involved enzymatic reactions is minimal. EFMs represent irreducible functional building blocks as any steady state metabolic pathway can be built as a convex sum of EFMs. EFMs can also be interpreted in a dual network as minimal cut sets, i.e., minimal metabolic intervention strategies. Using the stoichiometry of the reactions and the irreversibility of some reactions, EFMs are traditionally computed as the extremal rays of a cone by efficient implementations of the Fourier–Motzkin double description method. Nevertheless, the most efficient tools cannot handle genome-scale networks with millions of EFMs, and most of the computed EFMs are not feasible because important biological constraints are not taken into account. Aiming to reduce the total number of EFMs and to minimize the number of unfeasible EFMs, we introduce three types of additional constraints: thermodynamic, kinetic, and transcriptional regulatory Boolean constraints. We present the state-of-the art approaches to handle these constraints within the double description framework and the mixed integer linear optimization formulation. We investigate the concept of EFMs under Boolean constraints and alternative approached based on propositional logic including satisfiability and satisfiability modulo theories (SAT/SMT). Preliminary results dealing with the characterization of the solution space are given.