Résumé |
Elementary flux modes EFMS are commonly accepted tools for meta-bolic network
analysis under steady state conditions. They can be defined as the smallest
sub-networks enabling the metabolic system to operate in steady state with all
irreversible reactions proceeding in the appropriate direction. However, when
networks are complex, the number of EFMSquickly leads to a
combinatorial explosion, preventing from drawing even simple conclusions from
their analysis. Since the concept of EFMSanalysis was introduced
in 1994, there has been an important and ongoing effort to develop more
efficient algorithms. However, these methods share a
common bottleneck: they enumerate all the efms which make the computation
impossible when the metabolic network is large and only few works try to search
only efms with specific properties. As we will show in this paper, enumerating
all the efms is not necessary in many cases and it is possible to
directly query the network instead with an appropriate tool. For ensuring
a good query time, we will rely on a state of the art SAT solver, working on a
propositional encoding of EFMS, and enriched with a simple SMT-like solver
ensuring efms consistency with stoichiometric constraints. We illustrate our
new framework by providing experimental evidences of almost immediate answer
times on a non trivial metabolic network. |