Associated Team SIMBIOSI 

The Associated Teams programme of the INRIA is intended to promote and develop the international collaborations of the INRIA with high-level research teams throughout the world, in line with the international strategy of the institute. As one of international scientific policy tools of the INRIA, the Associate Teams programme provides valuable incentive to upgrade relationships with targeted institutions, and promotes the presence of the institute in the scientific environment of other countries. The Associated Team SIMBIOSI is funded starting from Jan. 1st 2009. It has a three partners, the Dipartimento di Informatica e Sistemistica, Università di Roma "La Sapienza"; the Free University and CWI, Amsterdam; and the BAMBOO team at the INRIA. The groups are headed, respectively, by Alberto Marchetti-Spaccamela, Leen Stougie and Marie-France Sagot.

SIMBIOSI's main purpose

The huge variety in the types of close and long-term relations observed between different species, the so-called symbiotic relations that involve a symbiont and its host, 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 project is to combinatorially explore those landscapes at the molecular level, that is at the level of the genome 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.

The symbiosis issue is vast and complex. The SIMBIOSI Associate Team will focus first 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. In a third part of the project, we therefore address 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.

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 evolution and co-evolution scenarii inferred.