Logic and linear programming for seed identification in metabolic networksA genome-scale metabolic network (GSMN) describes the metabolic reactions of a species. It can be built from genomic information based on functional annotations of genes [1]. By combining environmental response data and mathematical modeling, GSMNs can be employed to predict the behavior of the organism in a particularenvironment. Widely-used models rely on solving linear programming problems, such as Flux Balance Analysis (FBA), but discrete dynamical models were also shown to provide pertinent predictions. The former models are tied to steady state assumption, whereas the latter model consider transient dynamics from an initial state,using notions of network expansion and scope [2].We are interested here in the reverse problem : the identification of environemental nutrients, that we refer to as seeds, necessary to produce essential metabolites. Those precursor compounds can for example be needed in the environment to ensure the growth of a bacterial species, represented by a biomass reaction. This problembelongs to the field of reverse ecology, presented in [3] as an important analysis to understand the link between a system and its environment [4]. Applications include the design of culture media for uncultivated species through the prediction of optimal environmental compositions.The identification of seeds has been adressed by various methods over the years following either the steady state or transient dynamics assymptions. In this work, we aim at unifying both perspectives and provide a new hybrid resolution method for identifying necessary nutrient to both permit to light up the reaction network andmaintain a steady growth of the cells. We use Answer Setp Programming (ASP), a logic programming paradigm, to define the minimal or subset minimal set of seeds needed that could be selected starting from the initial state. Since FBA is a gold standard standard for controlling the activation of the biomass reaction, we use it ascontrol and or directly use it in our seed inference. We compared two approaches: using solely the discrete approach of the scope or combine it with linear programming (LP) through a constraint propagator (LP-ASP). In the first approach, the set of seeds are the tested with FBA to check the biomass reaction activation. In thehybrid one, the FBA is used on the second setps of the seeds identification directly to eliminate the solutions that do not activate the biomass reaction.It appeared that only a few solutions of the first method were sufficient to ensure the FBA constraint. With our hybrid resolution for the detections of seeds, the FBA constraint is guaranteed. Moreover, we demonstrated the scalability of our hybrid implementations on a set of 100 GSMN from the BIGG databases, comprisingmetabolic networks up to thousands of reactions. Applications of this work are numerous, including facilitating the search for seeds from metabolic networksobtained from microbiotas in which the high proportion of non-cultivated species impedes the understanding of species’s roles and interactions.References:[ 1] C. Francke, R. J. Siezen, and B. Teusink, Reconstructing the metabolic network of a bacterium from its genome, Trends in Microbiology, vol. 13, no.11. pp. 550–558, Nov. 2005. doi: 10.1016/j.tim.2005.09.001[2] T. Handorf, O. Ebenhöh, R. Heinrich, Expanding Metabolic Networks: Scopes of Compounds, Robustness, and Evolution, Journal of MolecularEvolution, vol. 61, no. 4. pp. 498–512, Jan. 2005. doi: 10.1007/s00239-005-0027-1[3] Levy, R., Borenstein, E.: Reverse Ecology: From Systems to Environments and Back. pp. 329–345. Springer, New York, NY (2012).https://doi.org/10.1007/978-1- 4614-3567-9_15, http://link.springer.com/10.1007/978-1-4614-3567-9{_}15[4] i, Y.F., Costello, J.C., Holloway, A.K., Hahn, M.W.: Reverse ecology and the power of population genomics. Evolution; international journal of organicevolution 62(12), 2984–94 (dec 2008). https://doi.org/10.1111/j.1558-5646.2008.00486.x, http://www. ncbi.nlm.nih.gov/pubmed/18752601< Réduire