| 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://www.win.tue.nl/~leen/ (web page at Eindhoven Technical University where L. Stougie will be until Nov. 2008) | http://www.dis.uniroma1.it/~alberto/ |
| Téléphone | +33 (0)4 72 44 82 38 | +31 20 5924045 | +39 06 77274021 |
| Télécopie | +33 (0)4 72 43 13 88 | +39 06 77274002 | |
| Courriel | Marie-France.Sagot@inria.fr | stougie@cwi.nl | alberto@dis.uniroma1.it |
La proposition en bref
|
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. |
Présentation
détaillée de l'Équipe Associée
1. Objectifs scientifiques de la proposition
The symbiosis issue is vast and complex. The project will focus on two questions concerning the evolution of symbionts, one at the genome level, namely the studies of rearrangements, and one at the biochemical network level and interface between genome and network. The evolution of symbionts may be largely dependent on the evolution of their hosts. We therefore address also the question of the evolution of the intimate relations themselves by studying the co-cladogenesis (co-speciation) of hosts and symbionts, and more generally their co-evolution, that is the mutual evolutionary influence they exert on each other.
On the methodological front, symbionts and the computational problems they raise have been the specific object of study of very few papers. A subgroup of the proteobacteria phylum, the gamma-proteobacteria (which includes Escherichia coli), has thus been used as illustration for a gene order and phylogenetic reconstruction [1], while phylogenetic co-evolution of host-parasites has been more extensively studied from a statistical and algorithmic point of view (see [2] and [3] for surveys) but remains frought with problems [4] and is able to address only simplified models because of the underlying combinatorics of the question. The group of the late Reinhardt Heinrich (Humboldt University, Berlin) has been the most prolific in developing methods for comparing the metabolic capabilities of different species of bacteria [5] and relating this to the bacteria's environment [6] but the group has developed computationally naive approaches that in particular have avoided to explicitely address such hard problems as the presence of numerous cycles in metabolic networks. The relation with evolutionary processes has also been little explored by the authors. Finally, we know of no current systematic algorithmic method specifically made for comparatively analysing the PPI networks of symbionts and hosts. A recent analysis of Buchnera aphidicola as compared to Escherichia coli [7] was performed using a method that is generic and questionable [8] because it is based on a definition of modules that is purely structural, uses a hard to justify modularity function and is not guaranteed to be optimal.
The present collaborative project is exploratory. We know there is great variety in the gene order and genome dynamics of different symbionts, a puzzling relationship between these and other features of a genome, a great variety in the characteristics of the symbionts biochemical networks that probably bear a complicated relation with both the genomes and the different environments (hosts) in which the species live, and a complex co-evolutionary history. The objective is to develop combinatorial methods that extensively investigate the variety of the landscapes observed given formally established models for genome and network evolution, compare them to one another and to what could be expected in the absence of environmental constraints and evolutionary forces.
The proposal is divided into three main parts described below.
Symbiont genome evolution and dynamics
The aim is to explore gene order dynamics by inferring gene rearrangement scenarii between different species of symbionts and by attempting to relate this to: 1. other features in the symbionts genome as well as to their environment and relation with the host, 2. random scenarii under certain models for randomness.
Gene order dynamics is mathematically modelled as distances between permutations of sets or multisets of gene identifiers under one or a set of operations that include principally reversal of a sequence of gene identifiers, but also displacement, deletion and duplication.
Numerous algorithms for computing a rearrangement scenario between different gene orders exist. As far as we know, only three, including one from some of the participants in this project [9,10], explore all possible optimal scenarii, and this only for the reversal permutation distance. There can be thousands or even millions of such scenarii which would seem to make them useless for any biological interpretation. There appears, however, to be structure in this huge set that has been very little explored yet, mainly because of the high complexity of the problem. How much biological information there is in this structure has, to the best of our knowledge, never been analysed.
Symbiont biochemical network evolution
Evolution is in general studied by comparative approaches. In the case of networks, many criteria could be used, from full network alignment - but this leads to hard computational problems - to the comparison of general network properties that ignore altogether topology and identify the networks to be compared with bags of proteins or of enzymes and metabolites (see [11] for metabolism), or with various structural indices such as clustering coefficient, betweeness centrality, average path length, diameter, concentration of subgraphs etc. (as examples, see [12,13,14]). Other measures have been used such as scope of compounds or its inverse problem [5,6]. Comparing flux distributions and regulation could represent a biologically richer approach in the case of metabolic networks but poses already the still largely unsolved problem of efficiently computing and then manipulating all possible or all optimal fluxes. The question of which method is best for comparing two networks is open, in particular when the purpose is to understand evolution and to elucidate the relation between genotype (genetic constitution of an individual, including here the constituents of its biochemical networks) and phenotype (describing any observed characteristic of an organism).
As concerns the evolution of symbiont networks more precisely, we know of very little work that has this as its specific object of study, although different analyses have been made on the evolution of metabolic networks in general [15,16,17] including ones that attempt to relate this to changes in the genomic landscape [18]. The most notable exception of a symbiotic study in the case of metabolism comes from the Hurst group [19]. This however makes use of a metabolic flux analysis model for Escherichia coli to predict the gene content of two organisms, in the case Buchnera aphidicola and Wigglesworthia glossinidia. The method is based on a greedy procedure which consists in removing a randomly chosen enzyme from the Escherichia coli network and calculating the impact of this deletion on the production of the biomass components that each of the two other symbiotic bacteria is known to output in normal conditions. Nothing guarantees that the order in which the enzymes are removed does not bias the outcome, and thus its biological interpretation. Furthermore, metabolic flux analysis models require precise knowledge of the nutrients that are available to the symbiont, an information that is in general not known, notably for symbionts living inside their hosts. The combinatorial scope of the investigation is also somewhat limited as other more readily available characteristics of a network could be used that would enable to apply the comparison to more species.
Whether we consider metabolic or PPI networks, we are dealing with node- and sometimes edge-labelled graphs (or bipartite graphs or hypergraphs in the case of metabolism) so topology only is not a fine enough measure when one of the main objectives is to study evolution. The information sustained by the labels, that bear a relation with the genomic text is also important. Whether the relation is independent or, inversely, dependent on its context, that is on the genes that are near along the genome or in the cellular space, is another open issue.
Symbiont-host co-cladogenesis and co-evolution
Co-cladogenesis (cladogenesis refers to the evolutionary process whereby one species splits into two or more species) and in general co-evolution of symbiont and host will be examined at the sequence level and, more speculatively, at the network level.
Sequence level
Among the questions that will be addressed concerning co-cladogenesis examined at the sequence level are: how often are symbionts horizontally transferred among branches of the host phylogenetic tree, how long do symbionts persist inside a given host following its invasion, and finally, what processes underlie this dynamic gain/loss equilibrium?
Current methods for answering to these questions are based on a phylogenetic approach where an evolutionary tree is built for symbiont and host separately and then compared to determine whether the two are identical (the two have indeed evolved together) or not. In the latter case, various events could have happened: the host has speciated (i.e. given risen to two new species) but not the symbiont (this is the "miss the boat" scenario), the symbiont has speciated but not the host or the symbiont has duplicated and one of the two went to infect another host (this is the "host-switching" scenario), the symbiont has gone extinct, or both host and symbiont have speciated. Other events may further complicate the co-evolutionary history: a host may live with various symbionts ("multi-infection"), symbionts may exchange genetic material further scrambling the evolutionary signal in either sense, etc. The latter events are, so far as we know, never taken into account in all existingcombinatorial or statistical methods.
Because of possible mistakes at various levels, for instance failure to detect the presence of a symbiont or mistake in the phylogenetic reconstruction, a difference between the two trees may also not mean a different host-symbiont evolution and although some methods consider this possibility, random models for co-evolution scenarii may be improved. Here again, combinatorial approaches may serve as important guides.
Network level
Rough as the measures for comparing two networks mentioned in the previous section may be for now, some could provide another looking-glass into the co-evolution of symbionts and hosts. This is a far more open issue of this project as fewer data are available to get at an accurate enough picture of the evolution of the interface between symbiont and host networks. The topic is however fully open and any new result in this area would thus be interesting.
References
[1] Blin G, Chauve C, Fertin G.
Genes order and phylogenetic reconstruction: application to
gamma-Proteobacteria.
Comparative Genomics (RCG 2005), Lecture Notes in Bioinformatics,
vol. 3678, pages
11-20, Springer-Verlag, 2005.
[2] Charleston MA, Perkins SL.
Traversing the tangle: algorithms and applications for cophylogenetic
studies. J Biomed Inform, 39:62-71, 2006.
[3]
Stevens J.
Computational aspects of host-parasite phylogenies.
Brief Bioinform, 5:339-349, 2004.
[4]
de Vienne DM, Giraud T, Shykoff JA.
When can host shifts produce congruent host and parasite phylogenies?
A simulation approach. J Evol Biol, 20:1428-1438, 2007.
[5] Handorf T, Ebenhõh O, Heinrich R.
Expanding metabolic networks: scopes of compounds, robustness,
and evolution.
J Mol Evol, 61(4):498-512, 2005.
[6]
Handorf T, Christian N, Ebenhõh O, Kahn D.
An environmental perspective on metabolism.
J Theor Biol, ahead of print, 2008.
[7]
Tamames J, Moya A, Valencia A.
Modular organization in the reductive evolution of protein-protein interaction networks.
Genome Biol, 8(5):R94, 2007.
[8]
Guimerà R, Nunes Amaral LA.
Functional cartography of complex metabolic networks.
Nature, 433(7028):895-900, 2005.
[9]
Braga MDV, Sagot M-F, Scornavacca C and
Tannier E. The solution space of sorting by reversals. in International
Symposium on Bioinformatics Research and Applications (ISBRA). Lecture
Notes in Bioinformatics (LNBI), vol. 4463, pages 293-304, 2007.
[10]
Braga MDV, Sagot M-F, Scornavacca C and
Tannier E. Exploring The Solution Space of Sorting by Reversals With
Experiments and an Application to Evolution, IEEE/ACM Transactions
on Computational Biology and Bioinformatics, 5:348-356, 2008.
[11] Clemente JC, Satou K, Valiente G.
Reconstruction of phylogenetic relationships from metabolic pathways
based on the enzyme hierarchy and the gene ontology,
Genome Inform,16:45-55,2005.
[12] Parter M, Kashtan N, Alon U.
Environmental variability and modularity of bacterial metabolic
networks.
BMC Evol Biol, 7:169, 2007.
[13]
Wang Z, Zhu XG, Chen Y, Li Y, Hou J, Li Y, Liu L.
Exploring photosynthesis evolution by comparative analysis of metabolic
networks between chloroplasts and photosynthetic bacteria,
BMC Genomics, 7:100, 2006.
[14]
Zhu D, Qin ZS.
Structural comparison of metabolic networks in selected single
cell organisms. BMC Bioinformatics, 6:8, 2005.
[15]
Parter M, Kashtan N, Alon U.
Environmental variability and modularity of bacterial metabolic
networks.
BMC Evol Biol, 7:169, 2007.
[16]
Wang Z, Zhu XG, Chen Y, Li Y, Hou J, Li Y, Liu L.
Exploring photosynthesis evolution by comparative analysis of metabolic
networks between chloroplasts and photosynthetic bacteria,
BMC Genomics, 7:100, 2006.
[17]
Zhu D, Qin ZS.
Structural comparison of metabolic networks in selected single
cell organisms. BMC Bioinformatics, 6:8, 2005.
[18]
Mahadevan R, Lovley DR.
The degree of redundancy in metabolic genes is linked to mode of metabolism.
Biophys J, 94(4):1216-1220, 2008.
[19]
Pál C, Papp B, Lercher MJ, Csermely P, Oliver SG, Hurst LD.
Chance and necessity in the evolution of minimal metabolic networks.
Nature. 440(7084):667-670, 2006.
2. Présentation
des partenaires
Brief history of the collaboration
The collaboration between the INRIA team and the other two partner teams started with a meeting at the 4th Workshop on Algorithms in Bioinformatics - WABI 2004, in Bergen, Norway where Marie-France Sagot was an invited speaker and Alberto Marchetti-Spaccamela an attendee. The following year, the two met again at the same conference, together this time with Leen Stougie with whom Alberto has maintained a more than 25-years working collaboration.
The two were interested in the work of the, now former, PhD student of Marie-France, Vincent Lacroix, was presenting on motifs in metabolic networks. A collaboration then started, initially on the enumeration of elementary modes in metabolic networks, that is of minimal-sized sub-networks capable to function in steady state, that then extended into another problem, namely of enumerating all minimal sets of precursors for a given set of target chemical compounds. The collaboration got off well from the start and has been extremely fruitful, with two papers already in common [15,16], regular visits (2 to Amsterdam with a 3rd already planned for Nov. 2008, 2 to Rome, and some 3-4 to Lyon with again a new one already planned for Jan. 2009), and informal exchange of PhD students (Vincent Lacroix, Vicente Acuña, Ludovic Cottret, Flavio Chierichetti) and one Master student (Paulo Milreu, Federal University of Mato Grosso do Sul, Brazil; visit to France funded by the HELIX-USP Associated Team ArcoIris and a STIC AmSud project involving BAMBOO, two teams in Brazil and one in Chile).
Both Alberto and Leen were also indicated in two ANR projects as outside, non-funded collaborators. The ANRs concern one ANR Blanc project (Miri, 2009-2012) and another ANR-BBSRC (MetNet4SysBio, 2008-2010) which involve, resp. the French coordinator and her project-team alone (ANR Blanc), and the French cooordinator and funded partners that could not, by the rules of the ANR and ANR-BBSRC, be the two partners proposed for this Associated Team project. It is hoped Paulo Milreu will be able to come back to France to do his PhD in co-supervision between Marie-France Sagot and Leen Stougie.
The collaboration with Alberto Marchetti-Spaccamela and Leen Stougie has been extremely important for the BAMBOO team by enabling it to establish a close relationship with computer science and mathematical groups that are both very strong and have an extensive network of other collaborative research contacts. Because of its localisation inside a mainly biological lab, the team had felt somewhat scientifically cut off from its coordinator's and main group members' original academic background. In turn, the collaboration with an interdisciplinary team inside a biological lab has brought to the Dutch and Italian teams a whole set of new interesting algorithmic and combinatorial problems. The extension of the collaboration to other permanent investigators and students in the groups of each of the coordinators can only help to make this collaboration even more fruitful.
Although this does not stricto sensu concern science, it is worth observing that this collaboration has also been immensely agreeable. It certainly helps explain why it has been scientifically productive despite the fact that the topic around which the collaboration started (metabolic networks) was entirely new to the Dutch and Italian teams, that the latter was not at all at the time involved with bioinformatics while the first is being funded on a bioinformatics project only from this year on, and that all money for travelling among the teams was taken from other projects.
References for the on-going collaboration
[20]
Acuña V, Chierichetti F, Lacroix V, Marchetti-Spaccamela
A, Sagot M-F, and Stougie L. Modes and cuts in metabolic networks:
Complexity and algorithms. accepted in BioSystems, 2008.
[21]
Cottret L, Milreu P. V., Acuña V,
Marchetti-Spaccamela
A, Martinez F V, Sagot M-F and
Stougie L. Enumerating precusor sets of metabolites in a metabolic
network. WABI'08, Lecture
Notes in Computer Science/Lecture Notes in BioInformatics, volume 5251,
pages 233-244, 2008.
INRIA BAMBOO team
Researchers from the INRIA BAMBOO team belong to the INRIA, to the University Claude Bernard (Lyon 1), and to the INSA-Lyon. The team has a background mainly in the design and analysis of algorithms as well as in combinatorics and statistics for biology, and in bioinformatics. It is strongly interdisciplinary, gathering together people from computer science, mathematics and biology (both theoretical and experimental).
Team members
Marie-France Sagot, INRIA, responsible, CV is found
below, Computational biology/Algorithmics/Combinatorics, Director of
Research
Hubert Charles, BF2I Lab
at INSA Lyon and BAMBOO,
Biology/Bioinformatics, Associate professor
Christian Gautier, University Claude Bernard and BAMBOO,
Statistics/Computational biology, Full professor
Yvan Rahbé, BF2I Lab
at INSA Lyon and BAMBOO,
Biology/Bioinformatics, Director of Research
Vincent
Miele, CNRS and BAMBOO,
Statistics/Computational biology, Research Engineer
Franck Picard, CNRS and BAMBOO,
Statistics/Computational biology, Research Associate
Eric
Tannier, INRIA and BAMBOO,
Computational biology/Algorithmics, Research Associate
Alain
Viari, INRIA Rhône-Alpes Grenoble, Computational biology, Director of Research
Paulo Fonseca, University Claude Bernard and BAMBOO, PostDoc
Vincent Lacroix, University Claude Bernard and BAMBOO,
PostDoc
Igor Nor, CNRS, University Claude Bernard and BAMBOO,
PostDoc
Leonor Palmeira, University Claude Bernard and BAMBOO,
PostDoc
Amélie Véron, CNRS and BAMBOO,
PostDoc
Augusto
Vellozo, INSA-Lyon, University Claude Bernard and BAMBOO,
PostDoc
Vicente Acuña, University Claude Bernard and
BAMBOO, PhD student
Ludovic Cottret, University Claude Bernard and BAMBOO,
PhD student
Yves-Pol
Deniélou, University Joseph Fourier and BAMBOO,
PhD student
Emmanuel Prestat, University Claude Bernard and BAMBOO,
PhD student
Patrícia
Simões, University Claude Bernard and BAMBOO,
PhD student
Possibly two Brazilian PhD students
who have applied or will apply for a scholarship to come to France, one as a "sandwich" and the other
as full PhD
CV of Marie-France Sagot
Marie-France Sagot was born on April 21st, 1956, in São Paulo,
Brazil; she obtained a Bachelor of Science degree in Computer Science
in December 1991 at the University of São Paulo,
Brazil, a PhD in Theoretical Computer Science in July 1996 at
the University of Marne-la-Vallée, France and the Habilitation
à Diriger les Recherches (HDR) in July 2000 from the same University. She was appointed
Associate Researcher at the Pasteur Institute in Paris from 1997 to
2001, then Associate Researcher from 2001 to 2003 at the INRIA
in Lyon, in the HELIX project-team. In 2003, she was promoted to
Director of Research at the INRIA.
She has co-authored about 60 papers in journals, international
conferences or as
book chapters. Her current research interests concern the design and
analysis of algorithms notably for biology.
She has co-founded
one national and one international Conference (resp. JOBIM and the
European Conference on Computational Biology - ECCB) and (co-)chaired
national and international Conferences and Workshops (JOBIM 2000 - Montpellier;
JOBIM 2004 - Montreal, Canada; ECCB 2003 - Paris; CompBioNets 2004 -
Recife, Brazil; CompBioNets 2005 - Lyon; BSB 2007 - Rio de
Janeiro, Brazil; ISMB-ECCB 2009 - Stockholm). She has served,
resp. serves, in the Steering Committee of JOBIM and ECCB. She is Associate Editor
in Lecture Notes in BioInformatics, Journal of Discrete Algorithms,
BMC Bioinformatics, BMC Algorithms for Molecular Biology and IEEE/ACM
Transactions on Computational Biology and Bioinformatics of which she
will become the Editor-in-Chief starting in January 2009.
She is or
has been the PI, for her team or general, of several national and international grants (Welcome
Trust, Royal Society UK, Brazilian and Portuguese projects, ARCs
INRIA, ACIs, ANRs of which two as sole funded team).
She founded and
directed from 2004 to 2007 the first PhD Program on Computational Biology
in Portugal, is a Visiting Researcher Fellow at King's College, London
(since 2002) and at the INESC-ID, Instituto Superior Técnico,
Lisbon (since 2004).
She has
served as committee member in the Comité national de la
recherche scientifique CID 44 (2004-2008), has served in various
researchers selection committees for the INRIA and is currently serving
in the 01 (Maths) section of the CoNRS.
Free University and CWI team
The majority of the CWI/VU Amsterdam team is mathematician or computer scientist. Steven Kelk, Gunnar Klau and Leen Stougie have been working for several years in the field of computational biology. In a few years time they have acquired a reputation for solving complicated mathematical optimization problems resulting from modelling biological problems. Rene Sitters, who has mainly worked on optimization problems related to logistics and telecommunication, will join the team on January 1, 2008.
Frank Bruggeman and Leen Stougie, with the assistance of Wilfred Röling, obtained a Dutch grant for studying "microbial ecosystems and multiple environment stoichiometric analyses", having significant overlap with the subject of our present research proposal. Brett Olivier and Steven Kelk are the PostDocs on the project and Jerien Klaver the PhD-student. The project starts on November 1, 2008. Within the Dutch project there is money for travelling and for receiving guests, some of which can be supplementary to the present project proposal. More PhD-students are expected to join.
Team members
Leen Stougie, Free University and CWI Amsterdam, responsible, CV is found below, Mathematician/Operations Researcher, Full Professor
Gunnar Klau, CWI Amsterdam, Mathematician/ Operations Researcher, Tenure track
Steven Kelk, CWI Amsterdam, Computer Scientist, PostDoc
Frank Bruggeman, Free University and CWI Amsterdam, Systems Biologist, PostDoc
Wilfred Röling, Free University Amsterdam, Micro-ecological biologist, Assistant Professor
Rene Sitters, Free University Amsterdam, Mathematician, Assistant Professor
Jerien Klaver, Free University Amsterdam, PhD-student
CV of Leen Stougie
Leen Stougie was born on July 20, 1956, in
Oud-Beijerland, The Netherlands. He will hold a full
professorship at the Department of Economics and Business
Administration of the Free University in Amsterdam
from November 1, 2008 on, being currently an associate professor at
theDepartment of Mathematics and Computer Science of the
Technical University Eindhoven. Next to that he will continue holding a
researcher position at the CWI in Amsterdam,
since 2008. Before this he worked full-time at CWI, and at the
University of Amsterdam. He held several visiting
professorships, among others at UC Berkeley, La Sapienza
University of Rome, and Technical University of Berlin.
He obtained a PhD-degree in May 1985 at Faculty
of Economics at the Erasmus University Rotterdam on a thesis titled
"Design and Analysis of Algorithms for Stochastic Integer
Programming" under the supervision of Jan Karel Lenstra and
Alexander Rinnooy Kan. 8 PhD-students graduated under his supervision.
In 2006 he was awarded the Howard W.
Kuhn Award, during the INFORMS meeting, Pittsburgh,
Pennsylvania, USA. His research interests are mathematics on the
interface of operations research, combinatorial optimization and probability
theory. A common theme in his research is optimization under uncertainty:
stochastic programming and on-line optimization. But he has recently made
contributions to graph optimization problems related to telecommunication
networks. Since 2004 he is involved in projects on computational biology:
metabolic network analysis and the construction of phylogenetic
networks.
He (co-)authored over 50 papers in journals, reviewed conference proceedings
and books (list here).
He was in 2001 Coordinator of NWO-Special Year on Mathematical Biology, in
2001
and 2003 Organizer of the Winterschool on Mathematics
and Biology at Wageningen in The Netherlands, and is
since 2005 until 2009 Project leader of the BSIK/BRICKS-project AFM2, and from
2005
until 2009 Site leader of the European FET-project ARRIVAL.
La Sapienza University Team
Researchers from Sapienza belong to the Algorithm Engineering group at the Department of Computer and Systems Sciences of Sapienza, University of Rome that has a strong background in the design and analysis of algorithms for network applications, combinatorial optimisation, massive data sets, and in the analysis of the structure of large and complex networks.
The group's strong theoretical background is complemented by extensive experimental activities in the analysis of very large complex networks.
Team members
Alberto
Marchetti-Spaccamela, University of Rome La Sapienza, responsible, CV is
found below, Design and analysis of algorithms/Combinatorial optimisation, Full Professor
Giorgio Ausiello, University of Rome La Sapienza, Design and analysis of algorithms/Combinatorial optimisation, Full professor
Stefano Leonardi, University of Rome La Sapienza, Design and analysis of algorithms/Combinatorial optimisation, Full professor
Luca Becchetti,
University of Rome La Sapienza, Design and analysis of
algorithms/Combinatorial optimisation, Research Associate
Vincenzo Bonifaci, University of Rome La Sapienza, Design and analysis of algorithms/Combinatorial optimisation, PostDoc
Two PhD students
CV of Alberto Marchetti-Spaccamela
Alberto Marchetti-Spaccamela was born on September 10th, 1954, in La Spezia, Italy; he graduated in Electrical Engineering cum laude in October 1977 at the University of Rome.
During 1982-1983 he was visiting scholar at University of California
at Berkeley. In 1987 he has been appointed Full Professor at the
University of L'Aquila and since 1991 he is at Sapienza University of
Rome.
Alberto Marchetti-Spaccamela has (co)-authored about 100 papers in
journals and international conferences. His current research interests
concern the design and the analysis of algorithms, and their
applications to computer networks, bioinformatics and high
performance computing.
He has co-authored a book on "Approximation Algorithms" (Springer
Verlag 1999) and four textbooks for University classes (in
Italian). He has chaired International Conferences and Workshops (WG
96, ICALP 97, WSDAAL 97, ICTCS 91, OLA 99, WAE 01, Hot TiNA 08) and
will chair in 2009 track C of ICALP on "Foundations of networked
computation"; he has been guest editor for special issues of
Theoretical Computer Science, ACM Computing Surveys, Discrete Applied
Mathematics, J. of Discrete Algorithmss; he has co-edited three volumes
published by Springer Verlag and has served in the program committee
of more than forty international conferences and workshops (e.g. 2007:
MFCS - Prague, ICTCS - Rome; 2008: WG - Leicester, ALGOSENSORS -
Reykjavik, WINE - Hong Kong, AAIM - Shanghai, TGC - Nice). He has
served in the steering committee of ESA and is currently member of the
WG steering committee.
He is and has been PI for Sapienza of several European grants (current
projects: AEOLUS, FRONTS, PANORAMA, Graal) and is in the advisory
board of PERADA.
He is a member of the National Committee for the International
Olympiads in Informatics and he is current president of the Italian
Chapter of the European Association for Theoretical Computer Science
(EATCS).
3. Impact
The three teams in this collaboration are both complementary and similar. They are complementary in the sense that both the Italian and Dutch teams are specialised in mathematical modelling and the design and analysis of optimization and approximation algorithms while the French team is fully interdisciplinary, with a spectrum of scientific knowledge that is larger (including also statistics, biology, string algorithmics) but in most cases less expert. The teams are similar in that all three teams are composed mainly of computer scientists and mathematicians with furthermore a background more deeply rooted in discrete mathematics (algorithmics, graph theory, enumerative combinatorics). There is therefore already a common language which greatly facilitates communication and establishes strong common goals although the spectrum of scientific interests are more varied among the teams. The French team has a clear interest in having some impact also on biology, which is increasingly the goal of the Dutch team too, particularly now that it is extended to more people, and houses a project similar to the one of the proposal. This can only enhance the focus and add to the critical mass of the proposed project. The biological part of the team will most likely be involved mainly through seminar days to be organised once or twice per year at one of the three sites. The Italian team remains interested essentially in the algorithmic and combinatorial questions raised by biology of which they are however getting an increasingly sophisticated grasp.
The expected impact of this collaboration is therefore to 1. enrich all three teams with new expert computational and mathematical knowledge and problems, 2. pull together the bioinformatics forces of the French and Dutch teams, 3. enable a strong flow of Master, PhD and PostDoc students among all three teams, and finally 4. prepare the way for more narrow scientific and possibly institutional projects and administrative links between all three partners.
Indeed, the teams would like to be able to find some stronger administrative framework for their work together. The ideal would be to be able to establish an international INRIA team involving at least the coordinators and the main investigators of the non French teams.