A Combinatorial Algorithm for Microbial Consortia Synthetic Design

Alice Julien Laferrière (Lyon)
Thursday, April 27, 2017 - 10:30
Room Aurigny
Talk abstract: 
Résumé en français plus bas. 
 
 
-------------------------------------------------------------------------------------
 
MULTIPUS (MULTIple species for the synthetic Production of Useful biochemical Substances) is a method to infer microbial communities and metabolic pathways to product specific target compounds from a set of defined substrates.
 
We use a weighted directed hypergraph and we merge several metabolic networks, including possible transports and exogenous reactions. The problem translates into the enumeration of Directed Steiner Hypertrees. 
 
We proposed to solve this enumeration problem using an dynamic programming algorithm or an answer-set programming (ASP) solver. Finally, we illustrated MULTIPUS with two case study, the production of antibiotics using a synthetic consortia and the artificial association of a methanogenic archae with Klebsiella pneumoniae.
 
 
-------------------------------------------------------------------------------------------------------------
Nous avons réfléchi à une méthode permettant d'inférer des voies métaboliques d’intérêt pour la production de composés chimiques au sein d'une communauté de micro-organismes.
 Dans cette méthode, nous représentons les réseaux métaboliques sous la forme d'hypergraphes dirigés et pondérés et permettons de prendre en compte  différentes souches ou espèces ainsi que des transports de composés ou encore l'insertion de réactions par ingénierie génétique.
 
Le problème correspond alors à un problème d'énumération d'hyper-arbres de Steiner dirigés. 
 
Nous avons proposé de résoudre cela soit avec un algorithme de programmation dynamique paramétré, soit par une approche de programmation par ensemble réponse (ASP). 
Ces deux approches sont implémentées dans  MULTIPUS (MULTIple species for the synthetic Production of Useful biochemical Substances). Enfin nous avons illustré l’intérêt de MULTIPUS dans deux cas d'applications, une communauté synthétique pour la production d'antibiotiques et un consortium artificiel.