Combinatorial optimization methods to complete and analyse a metabolic network

Biological compartments have a important role with respect to the struc- turation of metabolic map and to the control of metabolic transformations within a cell. Such compartments highlight the role of speci?c compounds, namely those transported from a compartment to another, which can be view as metabolite crossroads. We will call them "intermediary metabo- lites". The goal of this talk will be to study the impact of such intermediary metabolite when one is reconstructing a metabolic map from genome scale data. More precisely, genome annotation allow to identify a set of metabolic reactions which are active in a given species. Although, very often, these reactions are not su?cient to explain the production of compounds which are experimentally characterized. In this case, we need to propose reac- tions to be added to the metabolic map in order to explain the production of the targeted metabolic compounds. Such gap-?lling algorithms rarely take into account the existence of internal crossroads in the metabolic map. To that goal, we will model the role of intermediary metabolites in terms of combinatorial constraints. Then we will study the role of intermediary metabolites on a gap?lling method based on ASP (answer set programming) technologies. The method will be illustrated on large-scale yeast data