Direction des Relations Internationales (DRI)

Programme INRIA "Equipes Associées"
(Demande de prolongation)





Équipe INRIA: BAMBOO Organisme étranger partenaire : Free Amsterdam University Organisme étranger partenaire : University of Rome "La Sapienza"
Unité de recherche INRIA : Rhône-Alpes Grenoble
Pays : The Netherlands Pays : Italy
Coordinateur français
Coordinateur étranger
Coordinateur étranger
Nom, prénom Sagot Marie-France Stougie Leen Marchetti-Spaccamela Alberto
Grade/statut DR2 Full professor Full professor
Organisme d'appartenance
(précisez le département et/ou le laboratoire)
INRIA Rhône-Alpes Grenoble Free University Amsterdam and CWI, Amsterdam Dipartimento di Informatica e Sistemistica, Università di Roma "La Sapienza"
Adresse postale LBBE, Université Claude Bernard, 69622 - Villeurbanne cedex P.O. Box 94079, NL-1090 GB, Amsterdam, The Netherlands Via Ariosto 25, 00185 Roma, Italy
Téléphone +33 (0)4 72 44 82 38 +31 (0)20 5924045 +39 06 77274021
Télécopie +33 (0)4 72 43 13 88 +31 (0)20 5924199 +39 06 77274002

La proposition en bref

Titre de la thématique de collaboration (en français et en anglais) :
Exploration mathématique et algorithmique de la symbiose
Mathematical and algorithmic investigation of symbiosis

Descriptif :
The scientific objectives of the proposal center around a mathematical and algorithmic investigation of close and long-term relations observed between different biological species, the so-called symbiotic relations that involve a symbiont and its host.
The huge variety in such types of relations is mirrored by a huge variety of genomic and biochemical landscapes inside the symbiont world, and at the interface between symbionts and hosts. The purpose of this proposal is to combinatorially explore those landscapes at the molecular level, that is at the level of the genome (rearrangements) and of two of the main types of biochemical networks that may be reconstructed from the sequenced genomes of symbionts and hosts. Such networks are the metabolic and protein-protein interaction (PPI) networks. The final objective is to try to relate the contours of the landscapes to the modus operandi of the symbiotic relation, thereby offering a hope of better understanding the latter, in particular its evolution and environmental impact.
Graph (tree) combinatorics and algorithmics underlie each of these problems, as well as issues related to random graph enumeration under certain models to improve confidence in the evolutionary and co-evolutionary scenarii inferred.


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

(joindre la page du programme de travail initialement prévu fin 2008 pour l'année 2009
ou insérer un lien vers cette page)

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:

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.


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.

Rapport financier 2009

Avant de remplir les tableaux, consultez les règles au paragraphe "Financement" de la page d'accueil du programme.

1. Dépenses EA (effectuées sur les crédits de l'Equipe Associée)
Montant dépensé
Invitations des partenaires
Spent with second meeting: 3592
Planned with third meeting: approx. 2209
Planned with workshop: approx. 10320
Missions INRIA16121
approx. 15000 (the remaining will be taken from other funded projects of BAMBOO)

Justifiez en quelques lignes l'utilisation des crédits et en particulier une utilisation partielle du budget alloué.

2. Dépenses externes (effectuées sur des financements hors EA)
Montant dépensé
Nom de l'organisme 1 (*):Univ. Lyon 1
Invitations des partenaires Spent with first meeting: 1334
Missions INRIA vers le partenaire  
Nom de l'organisme 2 (*): Lorentz Center
Invitations des partenaires  
Missions INRIA vers le partenaire  
Invitations autres chercheurs 10000
Nom de l'organisme 3 (*): Netherlands Institute of Systems Biology (NISB)
Invitations des partenaires  
Missions INRIA vers le partenaire  
Invitations autres chercheurs 1000
Nom de l'organisme 4 (*): DIAMANT (Mathematics Cluster on Discrete Mathematics)
Invitations des partenaires  
Missions INRIA vers le partenaire  
Invitations autres chercheurs 2500

(*) Ajouter ou supprimer des lignes au tableau ci-dessus de façon à faire figurer tous les organismes ayant contribué au financement de l'équipe associée

Total des financements externes dépensés


Total des financements EA et externes dépensés



Bilan des échanges effectués en 2009

1. Chercheurs Seniors

statut (1)
objet (2)
durée (3)
Coût (si financement EA)
Coût (si financement externe)
L Stougie Prof Amsterdam Lyon Meeting 4 days   667
A Marchetti Prof Rome Lyon Meeting 4 days   667
MF Sagot DR Lyon Amsterdam Meeting 4 days 645  
L Stougie Prof Amsterdam Lyon Meeting 3 days 493  
A Marchetti Prof Rome Lyon Meeting 4 days 612  
P Crescenzi Prof Florence Lyon Meeting 4 days 664  
E Birmelé Ass. prof Paris Lyon Meeting 4 days 85  
MF Sagot DR Lyon Leiden Workshop 6 days 1225  
A Marchetti Prof Rome Leiden Workshop 6 days 621  
L Stougie Prof Amsterdam Leiden Workshop 6 days   284
F Bruggeman Prof Amsterdam Leiden Workshop 6 days 284  
F Jourdan CR INRA Toulouse Leiden Workshop 6 days 1655  

Total des durées
57 days
(1) DR / CR / professeur
(2) colloque, thèse, stage, visite....
précisez l'unité (mois, semaine..)

2. Juniors

statut (1)
objet (2)
durée (3)
Coût (si financement EA)
Coût (si financement externe)
V Lacroix Postdoc (at the time) Lyon Amsterdam Meeting 4 days 866  
V Acuña PhD Lyon Amsterdam Meeting 5 days 775  
L Cottret Postdoc Toulouse Amsterdam Meeting 5 days 1306  
S Kelk Postdoc Amsterdam Lyon Meeting 3 days 445  
V Lacroix Postdoc Lyon Leiden Workshop 4 days 815  
A Vellozo Postdoc Lyon Leiden Workshop 6 days 1225  
V Acuña PhD Lyon Leiden Workshop 6 days 1225  
P Milreu PhD Lyon Leiden Workshop 6 days 1225  
C Klein Master Lyon Leiden Workshop 6 days 1225  
L Cottret Postdoc Toulouse Leiden Workshop 6 days 1655  
B Olivier Postdoc Amsterdam Leiden Workshop 6 days   284
S Kelk Postdoc Amsterdam Leiden Workshop 6 days   284

Total des durées
63 days
(1) post-doc / doctorant / stagiaire
(2) colloque, thèse, stage, visite....
(3) précisez l'unité (mois, semaine..)


Programme de travail

Description du programme scientifique de travail
pour l'année 2010

Symbiont biochemical network evolution

Work on biochemical network in 2010 will focus on four main issues that were intensively discussed in the Lyon meeting of Nov 29 to Oct 3, 2009, plus one more general topic that will represent an important part of the PhD of Paulo Vieira (funded by an ANR Blanc project, MIRI, 2009-2012 whose sole partner is BAMBOO). The topics are described briefly below. Emphasis will for now continue on metabolic networks, which are also in a sense the richer and more complex from a mathematical and computational point of view.

Symbiont-host co-cladogenesis and co-evolution

This is a topic that has not yet been addressed by the partners of the Associated Team, although the Dutch and French has already done work on phylogeny or phylogeny-related issues. The year 2010 will therefore serve more for each team to get acquainted with what the others have been doing on phylogeny. The specific problem of co-cladogenesis and co-evolution can be divided into two main types of problems, only one of which is based on phylogeny. This is briefly described below.


Co-cladogenesis implies two main steps: phylogenetic reconstruction of two trees, one for the hosts and one for the symbionts, followed by so-called reconciliation of the two phylogenetic trees. The French part of the project has been exploring the existing literature on tree reconciliation that has been used in two contexts: the one of species and gene trees, and the one of host and parasite trees. The underlying assumptions are different although many aspects are common to the two problems. What is very different in the case that the French team wishes to address with their collaborating biologists is that the host and the parasite trees they have to deal with is at least one order of magnitude greater than the size of the trees that the existing methods can usually deal with (approx. 3000 species of hosts and more for the parasites).

Genetic architecture of Cytoplasmic Incompatibility

Cytoplasmic Incompatibility (CI) is the phenomenon whereby intracellular bacteria, when present in, for instance, a male insect, induces an infection that may ultimately lead to the death of the fertilized embryo unless the male's mate carries the very same symbiont that is also transmitted to the embryo. This protection confers a fertility benefit to infected females and promotes the spread of the infection. The molecular bases of CI have yet to be uncovered. However, theory suggests that it must involve a minimum of two components: a toxin, produced in males and somehow imprinted on the paternal chromosomes, and an antitoxin, produced in the eggs and that can rescue the embryos from the effect of the toxin. Given a matrix of observed CIs, which is a n by n matrix where n is the number of males that is equal to the number of their female mates and with 0 in a cell if the male carries a toxin but the female does not have the corresponding antitoxin, and 1 otherwise (neither toxin nor antitoxin are present, both are present, or only the female is infected by an antitoxin), the simplest version of the problem is to determine what is the minimum number of distinct pairs of toxins/antitoxins are required to explain the data. This simplest version is related to the problem of finding the minimum number of bicliques required to cover the edges of a bipartite graph. This work was proposed by and is done in collaboration with Sylvain Charlat from the LBBE.


Programme d'échanges avec budget prévisionnel

1. Echanges

As for 2009, all expenses will be for regular trips to Amsterdam, Rome or Lyon by the other partners of the Associated team, with an approximately equal mixture of junior and senior people. Each trip should be for approximately one week. A small workshop of one week open to non-partner members will also be organised again in 2010 with extra funds that will be also solicited to other institutions.

Nombre de personnes
Coût estimé
Chercheurs confirmés 2 2 x 2 (trips) x 750
2 2 x 2 (trips) x 750
Doctorants 2 2 x 4 (trips) x 750


Autre (précisez) : Workshop
6 12000+5000


Nombre de personnes
Coût estimé
Chercheurs confirmés 3 5 x 2 (trips) x 750
2 3 x 2 (trips) x 750


Autre (précisez) : Workshop
5 12000+5000

2. Cofinancement

Cette coopération bénéficie-t-elle déjà d'un soutien financier de la part de l'INRIA, de l'organisme étranger partenaire ou d'un organisme tiers (projet européen, NSF, ...) ?
Indiquez ces éléments et donnez les montants associés.

The collaboration benefits once again from funds obtained through the ANR Blanc, project Miri, accepted in 2008 and due to last from 2009 to 2012. Although not partners in the project (BAMBOO is the sole partner of Miri), some funds were sollicited to invite Alberto Marchetti-Spaccamela and Leen Stougie, as well as to pay for trips to visit their labs. The value asked per year for Alberto and Leen amounted to 2 times 3000 euros (out of a total of 52000 euros over 4 years for visits, conference participations and publication costs). The remaining 10000 euros for organising a workshop must be solicited to other organisms, as was the case for the year 2009.

3. Demande budgétaire

Indiquez, dans le tableau ci-dessous, le coût global estimé de la proposition et le budget demandé à la DRI dans le cadre de cette Equipe Associée.
(maximum 20 K€ pour une prolongation en 2e année et 10 K€ pour une 3e année).

A. Coût global de la proposition (total des tableaux 1 et 2 : invitations, missions, ...) 34000
B. Cofinancements utilisés (financements autres que Equipe Associée) 4000+10000

Financement "Équipe Associée" demandé (A.-B.)
(maximum 20 K€ pour une 2e année et 10 K€ pour une 3e année)


Remarques ou observations :




© INRIA - mise à jour le 08/07/2009