La proposition en bref

---

II. BILAN 2009

Changements majeurs survenus concernant l'Equipe Associée (modifications des objectifs scientifiques, des chercheurs impliqués) New members: Vincent Lacroix (before postdoc, now Associate Professor BAMBOO), Paulo Milreu (PhD student BAMBOO), Cecília Klein (Brazilian Master, apprenticeship at BAMBOO for one year). Members who left: Paulo Fonseca (now with a position at INESC-ID, IST Portugal), Ludovic Cottret (now postdoc at INRA Toulouse), Leonor Palmeira (now postdoc at Liège), Emmanuel Prestat (now postdoc at l'École Centrale de Lyon). New scientific refocusing: On two of the three topics indicated when the proposal was submitted, namely "Symbiont biochemical network evolution" and "Symbiont-host co-cladogenesis and co-evolution", with a special emphasis on the first for the year 2010 again.

 

Rapport scientifique de l'année 2009

Description de l'activité scientifique de l'équipe associée et des résultats obtenus : publications, communications, organisation de colloques, formation, soutenances de thèse, valorisation économique, sociale, industrielle, enregistrement de logiciels, dépôt de brevets ... (1 à 2 pages)

A web page has been created for the Associated Team at this address.

The planned work for 2009 can be found at this address and on the web page of the Associated Team. The work done in collaboration until October 2009 has concentrated on the analysis of metabolic networks. Work on phylogeny at Amsterdam and on co-phylogeny in BAMBOO is on-going but will start being discussed among all the teams at the meeting in early 2010 (tentatively planned for January in either Lyon or Rome).

Meetings/Workshop that happened in or are planned for 2009

Three meetings took already place in 2009, while one more is planned before the end of the year. The three meetings that took already place happened in Lyon for the first one, Jan. 19 to 22, in Amsterdam for the second, May 3 to 6, and in Lyon again, Sept. 29 to Oct. 3. The travellers to the first Lyon meeting were Leen Stougie and Alberto Marchetti-Spaccamela. The travellers to Amsterdam included Vicente Acuña (PhD), Vincent Lacroix (then postdoc) and Marie-France Sagot, plus Ludovic Cottret (ex-PhD student of Marie-France Sagot) and Fabien Jourdan (postdoc supervisor of Ludovic Cottret at the INRA Toulouse and BAMBOO external member). The visitors to the second Lyon meeting included Leen Stougie and his postdoc, Steven Kelk, as well as Alberto-Marchetti-Spaccamela. Two additional guests were Pierluigi Crescenzi from the Univ. of Florence, Italy and Etienne Birmelé from the Statistique et Génome group at the Univ. of Evry. Etienne is member of the ANR NeMo of which BAMBOO is also partner. Besides Vincent Lacroix and Marie-France Sagot, the PhD students and postdocs from BAMBOO involved in the meeting were Vicente Acuña, Paulo Milreu and Augusto Vellozo.

A workshop is planned for Oct 26 to 30, at the Lorentz Center in Leiden, the Netherlands. The meeting, called Metabolic Pathways Analysis 2009, was organised mostly by the Dutch members of the Associated Team, Leen Stougie, Frank Bruggeman and Brett Olivier, with help also from an external researcher, Stefan Schuster and from Marie-France Sagot. The Dutch members thus submitted a proposal to the Lorentz Center early in 2009. Its acceptance meant that financial support could be offered to between 30 and 40 participants (covering fully for lodging and conference dinner; the participants are expected to cover only for their flight or train tickets), the trip of the French and Italian members of the Associated Team being covered by SIMBIOSI. The meeting will have some 45 participants (current list available here), of which approximately a quarter are PhD students and postdocs (6 from the Associated Team), and more than half are international experts on the mathematical modelling and analysis of metabolic networks. One of the main objectives of the meeting is to build an European project on the theoretical and applied study of metabolism. Discussion on this project will happen mostly in the last afternoon.

A meeting is already tentatively planned for Jan. 2010, either in Lyon again or in Rome.

Common work related to the Associated Team in 2009

Common work has focused on four main issues:

• Network motifs: these can be defined in different ways depending on the type of network considered, whether interaction networks where node and edge/arc labels are often ignored but topology would be essential in absence of data error, or metabolic where node and edge/arc labels are important elements of the network but topology possibly less so although this is a debatable question. Complexity issues where discussed in the May meeting in Amsterdam but specially open is the question of a good random model, in particular for an hypergraph which is the most interesting way of representing metabolism. Random hypergraphs was one of the main topics discussed in the meeting of Sept. 29 to Oct. 3 in Lyon.
• Precursor sets: these are defined as minimal sets of metabolites that enable to produce a set of target metabolites. After a first publication in common that pre-dates the Associated Team, we continued working on the topic, trying to: 1. improve the algorithm, 2. use the algorithm to explore the metabolic dialog between hosts and their symbionts, 3. introduce stoichiometric information in the model. Stoichiometry roughly refers to the proportion of each metabolite that is input or output by a given reaction. Taking such information into account makes the problem of enumerating all minimal precursor sets considerably more complex.
• "Metabolic stories": given a metabolic network and a set of metabolites of interest, the problem here is to enumerate all the metabolic "stories" (paths) linking subsets of these metabolites. This problem comes from the fact that the data obtained in metabolomics studies (which corresponds to the "systematic study of the unique chemical fingerprints that specific cellular processes leave behind", that is, to the study of their small-molecule metabolite profiles) is very often partial as it is usually not possible to measure the concentration of every metabolite in a metabolic system. The metabolites that can be measured, although they represent partial information, may in practice be used to reconstruct or at least formulate hypotheses on which have been the metabolic pathways used in the system or organism of interest.
• Elementary modes: these intuitively correspond to the smallest subnetworks that can function in steady state where by steady state is meant a state in which all compounds internal to the subnetwork that are produced are also consumed. Elementary modes can be used to understand cellular objectives for an overall metabolic network. Furthermore, elementary mode analysis takes into account stoichiometry and thermodynamics when evaluating whether a particular metabolic route or network is feasible and likely for a set of proteins/enzymes.

A paper in common with all three partners has been submitted to BioSystems [1] that presents new complexity results relative to elementary modes. Two other papers [2,3] are in preparation on the precursor sets problem, one presenting a new, improved algorithm that should also help us to address the stoichiometry issue, as well as a new complexity result relative to the enumeration of all minimal sets. This work is a continuation of the work presented at WABI 2008 (Cottret et al.) and that was part of L. Cottret's PhD defended in Jan. 2009. The second paper presents a detailed application to the understanding of the metabolic dialog between a host and its symbiont(s). The models chosen concern (the host) and its primary and secondary endosymbionts (bacteria living inside the cells of the host). This is also part of L. Cottret's PhD. Work on motifs and "metabolic stories" is on-going and is done in close collaboration with Ludovic Cottret and his current postdoc supervisor, Fabien Jourdan, from the INRA Toulouse and external member of BAMBOO.

Production

Papers in common

[1] (submitted) V. Acuña, A. Marchetti-Spaccamela, M.-F. Sagot, L. Stougie. A note on the complexity of finding and enumerating elementary modes. submitted to BioSystems in August 2009.

[2] (in preparation) V. Acuña, P.V. Milreu, L. Cottret, A. Marchetti-Spaccamela, M.-F. Sagot, L. Stougie. Complexity analysis and efficient algorithm for enumerating all minimal metabolic precursor sets (tentative title). Submission planned before end 2009.

[3] (in preparation) L. Cottret, P.V. Milreu, V. Acuña, A. Marchetti-Spaccamela, L. Stougie, H. Charles, M.-F. Sagot. Precursor sets of two co-resident endocytobionts of the glassywinged sharpshooter (tentative title). Submission planned before end 2009.

Papers by partners on the topics of the collaboration

[4] L. van Iersel, J.C.M. Keijsper, S.M. Kelk, L. Stougie, F. Hagen, T. Boekhout. Constructing level-2 phylogenetic networks from triplets IEEE/ACM Transactions on Computational Biology and Bioinformatics, in press.

[5] Y.-P. Deniélou, F. Boyer, M.-F. Sagot, A. Viari. Multiple alignment of biological networks: A flexible approach. CPM'09, Lecture Notes in Computer Science volume 5542, pages 173-185, 2009.

PhD that involved the collaboration

[6] Ludovic Cottret, defended Jan 2009, Systemic analysis of the intracellular symbiosis: evolution and organisation of the metabolic network of endocytobionts.

Next planned PhD defense that involves the collaboration

[7] Vicente Acuña, defense planned for before March 2010.

Workshop organisation

[8] Metabolic Pathways Analysis 2009, Lorentz Center, Leiden, the Netherlands, Oct 26 to 30, 2009, around 45 participants.