Direction des Relations Internationales (DRI)
Programme
INRIA "Equipes Associées"
(Demande de prolongation)
EQUIPE ASSOCIEE 
SIMBIOSI 
sélection 
2009 
Équipe INRIA: BAMBOO  Organisme étranger partenaire : Free Amsterdam University  Organisme étranger partenaire : University of Rome "La Sapienza" 
Unité de recherche INRIA : RhôneAlpes Grenoble Thème INRIA : BIO A 
Pays : The Netherlands  Pays : Italy 
Coordinateur
français 
Coordinateur
étranger 
Coordinateur
étranger 

Nom, prénom  Sagot MarieFrance  Stougie Leen  MarchettiSpaccamela Alberto 
Grade/statut  DR2  Full professor  Full professor 
Organisme d'appartenance (précisez le département et/ou le laboratoire)  INRIA RhôneAlpes 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, NL1090 GB, Amsterdam, The Netherlands  Via Ariosto 25, 00185 Roma, Italy 
URL  http://www.inrialpes.fr/helix/people/sagot/  http://db.cwi.nl/personen/publiek/zoek_show.php4?persnr=1126  http://www.dis.uniroma1.it/~alberto/ 
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 
Courriel  MarieFrance.Sagot@inria.fr  lstougie@feweb.vu.nl  alberto@dis.uniroma1.it 
Titre de la thématique de collaboration (en
français et en anglais) : 
Descriptif : The scientific objectives of the proposal center around a mathematical and algorithmic investigation of close and longterm relations observed between different biological species, the socalled 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 proteinprotein 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 coevolutionary scenarii inferred. 
Changements majeurs
survenus concernant l'Equipe Associée (modifications des
objectifs scientifiques, des chercheurs impliqués) 
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 cophylogeny in BAMBOO is ongoing 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 MarchettiSpaccamela. The travellers to Amsterdam included Vicente Acuña (PhD), Vincent Lacroix (then postdoc) and MarieFrance Sagot, plus Ludovic Cottret (exPhD student of MarieFrance 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 AlbertoMarchettiSpaccamela. 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 MarieFrance 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 MarieFrance 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:
Production
Papers in common
[1] (submitted) V. Acuña, A. MarchettiSpaccamela, 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. MarchettiSpaccamela, 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. MarchettiSpaccamela, L. Stougie, H. Charles, M.F. Sagot. Precursor sets of two coresident 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 level2 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 173185, 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.
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 INRIA  16121 
Total  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  
Total  14834 
(*) Ajouter ou supprimer des lignes au tableau cidessus
de façon à faire figurer tous les organismes ayant contribué au financement
de l'équipe associée
Total des financements externes dépensés 
14834 
Total des financements EA et externes dépensés 
32610 
1. Chercheurs Seniors
Nom 
statut (1) 
provenance  destination 
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 
2. Juniors
Nom 
statut (1) 
provenance 
destination  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 
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, 20092012 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.
Symbionthost cocladogenesis and coevolution
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 phylogenyrelated 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 cocladogenesis and coevolution can be divided into two main types of problems, only one of which is based on phylogeny. This is briefly described below.Cocladogenesis
Cocladogenesis implies two main steps: phylogenetic reconstruction of two trees, one for the hosts and one for the symbionts, followed by socalled 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.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 nonpartner members will also be organised again in 2010 with extra funds that will be also solicited to other institutions.
1. ESTIMATION DES DÉPENSES EN MISSIONS INRIA VERS LE PARTENAIRE  Nombre de personnes

Coût estimé

Chercheurs confirmés  2  2 x 2 (trips) x 750 
Postdoctorants 
2  2 x 2 (trips) x 750 
Doctorants  2  2 x 4 (trips) x 750 
Stagiaires 

Autre (précisez) : Workshop 
5000  
Total

6  12000+5000 
2. ESTIMATION DES DÉPENSES EN INVITATIONS DES PARTENAIRES  Nombre de personnes

Coût estimé

Chercheurs confirmés  3  5 x 2 (trips) x 750 
Postdoctorants 
2  3 x 2 (trips) x 750 
Doctorants  
Stagiaires 

Autre (précisez) : Workshop 
5000  
Total

5  12000+5000 
2. Cofinancement
Cette coopération bénéficietelle 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.
3. Demande budgétaire
Indiquez, dans le tableau cidessous, 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).
Commentaires

Montant

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.) 
20000 
Remarques ou observations :