des de reconstruction de super-arbres en phylogénomique Application à l’Arbre de la Vie Encadrants : V.Berry, O.Gascuel & E.J.P. Douzery Lieu LIRMM & ISEM, Montpellier. Mots-clefs : phylogénies, super-arbres, algorithmique, implémentation, application sur données réelles Description du sujet : Les relations de parentés entre espèces vivantes sont le plus souvent décrites par un arbre d'évolution, aussi appelée phylogénie. Les méthodes de super-arbres assemblent des phylogénies sur des ensembles d’espèces différents en un arbre référençant l’ensemble des espèces présentes au départ. Cet arbre, appelé super-arbre, est construit de façon à représenter le plus fidèlement possible les relations de parenté entre espèces telles qu'indiquées par les arbres sources. L’intérêt principal de ce type de méthodes est de pouvoir combiner des données provenant d’études différentes (moléculaires, morphologiques, géographiques, etc). Ces méthodes trouvent une application particulièrement importante en phylogénomique pour la construction d'Arbres de la Vie que l'on cherche à construire depuis plusieurs phylogénies, chacune centrée sur un domaine du Vivant. La thèse s'effectuera suivant plusieurs axes : - Plusieurs études ont proposé des propriétés théoriques simples que devraient respecter les méthodes de construction de super-arbres. Cependant, les méthodes existantes ne vérifient pas l'ensemble de ces propriétés. Un premier objectif de cette thèse sera de faire le lien entre les différentes propriétés proposées, et d'établir dans quelle mesure les différentes méthodes de super-arbres existantes vérifient ces propriétés ou peuvent être modifiées pour les vérifer. On pourra éventuellement proposer d'autres propriétés théoriques, qui devront être vérifiables en temps polynomial. - Un problème clef gênant la construction de super-arbres à grande echelle est le fait que certaines étiquettes des arbres sources sont situées à des niveaux taxonomiques différents (espèces, familles, etc) et que les relations d'ancestralité entre ces étiquettes ne sont pas explicitées dans les arbres sources. Par exemple, l’étiquette "mammifère" peut être une feuille dans une phyolgénie étudiant les relations entre les grandes familles d’animaux, tandis qu’elle sera associée à un nœud interne dans une phylogénie des vertébrés contenant plusieurs mammifères. L'exploitation automatique des banques d'arbres internationales comme TreeBASE ne peut se faire que si les informations d’ancestralité entre étiquettes sont connues. Le deuxième objectif de cette thèse consiste à mettre en place des stratégies pour collecter les informations d’ancestralité manquantes (par exemple à l'aide du Taxonomy Browser) et à concevoir des algorithmes de construction de super-arbres capables de prendre en compte ces informations d'ancestralité. Les recherches effectuées au cours de cette thèse seront appliquées à des problèmes biologiques pour lesquels l’équipe Phylogénie Moléculaire (de l'Institut des Sciences de l’Evolution de Montpellier) dispose de données et d’expertise . A moyen terme nous envisageons une application à échelle réduite, concernant l’élucidation de certaines parties de la phylogénie des mammifères, et une application à grande échelle, afin de proposer un premier assemblage automatique de l’Arbre de la Vie (de tels arbres sont pour l’instant construits à la main, cf le projet américain Tree of Life). Un tel Arbre de la Vie sera construit dans un premier temps sur la base des quelques dizaines d’arbres du projet Arbre de la Vie de l’ISEM). Dans un deuxième temps nous visons une exploitation automatique des milliers de phylogénies contenues dans TreeBASE, en réponse au challenge posé par M.Sanderson en 2004. Bibliographie des encadrants sur le thème des super-arbres : 2006. V.Berry, V. Ranwez, P.-H. Fabre & E.J.P. Douzery, "Votez veto pour l'Arbre de la Vie : la méthode BioBuild pour reconstruire des superarbres", Journées Ouvertes : Biologie, Informatique et Mathématiques (JOBIM). 2006. V.Berry and C.Semple, "Fast reconstruction of a phylogeny for compatible source trees", Systematic Biology.55 (2), 108-126. 2006. A.Criscuolo, V.Berry, E.Douzery, O.Gascuel, "SDM: a fast distance-based approach for (Super)tree building in phylogenomics", à paraître dans Systematic Biology. 2006. V.Ranwez, V.Berry, E.Douzery, Desirable properties to build the Tree of Life, soumis à ECCB (European Conference on Computational Biology). 2006. E. J. P. Douzery, F. Delsuc & H. Philippe. Les datations moléculaires à l'heure de la génomique. Médecine Sciences. 22 (4) 374-380. 2006. Poux C., Chevret P., Huchon D., de Jong W. W. & Douzery E. J. P., Arrival and diversification of caviomorph rodents and platyrrhine primates in South America. Systematic Biology 55 (2) : 228-244. 2005. Criscuolo A., Berry V., Douzery E. J. P. & Gascuel O., SDM : une méthode de distance rapide pour les études de phylogénomique. 231-243 in "Journées Ouvertes Biologie Informatique Mathématiques", Perrière G., Guénoche A. & Geourjon C. éds. Journées Ouvertes : Biologie, Informatique et Mathématiques (JOBIM). 2005. Steiner C., Tilak-Jean M., Douzery E. J. P. & Catzeflis F., 2005. New DNA data from a Transthyretin nuclear intron suggest an Oligocene to Miocene diversification of living South America opossums (Marsupialia: Didelphidae), Molecular Phylogenetics and Evolution 35 : 363-379. 2004. V.Berry and F.Nicolas, "Maximum agreement supertrees", 15th ann. Combinatorial Pattern Matching Symposium (CPM). 2004. Douzery E. J. P., Snell E. A., Bapteste E., Delsuc F. & Philippe H. The timing of eukaryotic evolution: Does a relaxed molecular clock reconcile proteins and fossils? Proceedings of the National Academy of Sciences of the USA 101 (43) : 15386-15391. 2003. Delsuc F., Mauffrey J.-F. & Douzery E. J. P.. Une nouvelle classification des mammifères. Pour La Science 303 : 62-66. Compétences du candidat idéal : - titulaire d'un Master de Recherche en Bioinformatique (ou en Informatique mais ayant suivi un module de bioinformatique). - un goût prononcé pour l'algorithmique et les mathématiques discrètes (graphes, combinatoire, etc) - un intérêt pour les applications réelles, allié à des capacités en programmation. - un double cursus, même partiel, en informatique et biologie sera un plus indéniable. Contacts : N'hésitez pas à nous contacter pour de plus amples renseignements sur cette bourse de thèse : Vincent Berry : vberry@lirmm.fr, (+33) 04 67 41 85 48. Equipe Méthodes et Algorithmes pour la Bioinformatique, LIRMM, CNRS-Université Montpellier II rue Ada, 34392 Montpellier cedex 5. Emmanuel Douzery : douzery@isem.univ-montp2.fr, (+33) 04 67 14 48 63 Equipe Phylogénie Moléculaire ISEM,Université Montpellier II. Place E. Bataillon, 34095 Montpellier.)