*Result*: Seed Inference in Interacting Microbial Communities Using Combinatorial Optimization ; Inférence des graines (seeds) dans les communautés microbiennes en interaction à l'aide de l'optimisation combinatoire

*International audience ; The behaviour of microorganisms and microbial communities can be abstracted by models combining a description of their metabolic capabilities as metabolic networks, and suitable computational or mathematical paradigms that further integrate simulation conditions. A major component of the latter is the composition of the environment or growth medium that can be referred to as seeds. Predicting the seeds from the metabolic network and an expected behaviour is an inverse problem that can be addressed with linear programming or logic paradigms such as Answer Set Programming (ASP). Here, we formalise seed prediction for microbial communities, taking into account that their members may interact positively through metabolite transfers, which may reduce the need for external seed metabolites. We address the problem with ASP and add a hybrid component ensuring the satisfiability of linear constraints. We explore the subset-minimality solving heuristic of the Clingo solver and develop two heuristics supporting priority of seeds over transfers. We present a proof of concept of seed inference in small-scale communities, and assess the scalability of the three heuristics at genome-scale. Overall, our work introduces a hybrid logic-linear model for seed inference in interacting microbial communities, and new heuristics for the exploration of the solution space with subset minimality optimisations. ; Le comportement des micro-organismes et des communautés microbiennes peut être résumé à l'aide de modèles combinant une description de leurs capacités métaboliques sous forme de réseaux métaboliques et des paradigmes computationnels ou mathématiques appropriés qui intègrent en outre les conditions de simulation. L'un des principaux éléments de ces derniers est la composition de l'environnement ou du milieu de culture, que l'on peut qualifier de « graines ». La prédiction des graines à partir du réseau métabolique et d'un comportement attendu est un problème inverse qui peut être résolu à l'aide de la ...*