Vendredi 9 juillet à 14h30

Amphithéâtre de l'INRIA Rhône Alpes 655 avenue de l'Europe 38330 Montbonnot Saint Martin

Reconstruction ab initio de voies métaboliques - Formalisation et approches combinatoires

Frédéric Boyer, projet Helix, INRIA Rhône-Alpes

Jury

Daniel Kahn, rapporteur

Jacques Nicolas, rapporteur

Christine Collet, examinatrice

François Fages, examinateur

Laurent Trilling, directeur de thèse

Alain Viari, directeur de thèse

Abstract

Reconstructing the metabolic pathways of an organism is a task of major importance and several approaches have already been proposed in order to help biologists in this task, but more exploratory approaches are needed.

The first part of this thesis emphasis on what we call ab initio metabolic pathway reconstruction. This consists in finding, inside the global network of chemical reactions occurring in a living organism, a subnetwork connecting at least two chemical compounds. Given a set of biochemical reactions together with their substrates and products, we consider the reactions as transfers of atoms between the chemical compounds and we look for sequences of reactions transferring a maximal (or preset) number of atoms between a source and a sink compound. We state this problem as the one of finding a composition of partial injections that maximises the image size. The theoretical complexity of this problem has been studied and a practical algorithm to solve it is presented.

The second part presents a formalization of a problem concerning graph comparison. The particular case treated in this thesis concerns the comparison of a network of reactions with the spatial organization of genes on the genome. This comparison permits to identify operon encoded metabolic pathways.

Résumé

La reconstruction des voies métaboliques d'un organisme est une tâche importante en biologie et plusieurs approches ont déjà été proposées pour assister ce travail, mais il y a un besoin pour des approches plus exploratoires.

La première partie de cette thèse s'intéresse à la reconstruction ab initio de voies métaboliques. Cela consiste à retrouver, au sein du réseau de l'ensemble des réactions chimiques décrites pour un organisme vivant, un sous-réseau connectant au moins deux composés. Nous proposons une nouvelle formulation de ce problème qui considère les réactions comme des transferts d'atomes entre composés chimiques. Une voie métabolique est ainsi associée à un transfert d'atomes entre deux composés. Le problème de la reconstruction est alors de rechercher la succession de réactions maximisant le nombre d'atomes transférés entre ces deux composés. Ce problème est exprimé comme la recherche d'une composition d'injections partielles dont la taille de l'image est maximale. La complexité de ce problème a été étudiée et un algorithme le résolvant est présenté.

La seconde partie présente la formalisation d'un problème de comparaison de graphes. Le cas particulier traité dans cette thèse concerne la comparaison d'un réseau de réactions avec l'organisation spatiale des gènes sur le génome. Cette comparaison permet l'identification de voies métaboliques codées en opérons dans les génomes bactériens.