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ône-Alpes Grenoble Thème INRIA : BIO A |
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 |
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 | Marie-France.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 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. |
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 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:
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.
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 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 |
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, 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
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.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.
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 |
Post-doctorants |
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 |
Post-doctorants |
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é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.
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).
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 :