Les méthodes de super-arbres sont un outil pratique et fondamental en phylogénomique. De façon générale, ces méthodes amalgament un ensemble de phylogénies sources contenant des ensembles d’étiquettes partiellement différents en un arbre parent qui inclus l’ensemble des étiquettes. Cet arbre parent est construit de façon à représenter le plus fidèlement possible les relations de parenté entre étiquettes 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).

Un problème clef gênant la construction de super-arbres est le fait qu’une étiquette puisse être positionnée sur une feuille dans un arbre source, alors qu’elle correspond à un nœud interne dans un autre arbre source. 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. Très peu de méthodes de super-arbre ont été proposées qui permettent d’envisager la position d’étiquettes non seulement aux feuilles mais aussi aux nœuds internes des arbres (de tels arbres sont dits semi-étiquetés). Nous venons de participer à la mise au point d’une de ces méthodes, décidant de la compatibilité d’un ensembles d’arbres semi- étiquetés [1]. Toutefois, l’application automatique de cet algorithme (comme des autres méthodes de super-arbres) aux phylogénies stockées dans les banques d’arbres ne peut se faire que si les informations d’ancestralité entre étiquettes sont connues. Par exemple, si une phylogénie source contient l’étiquette "mammifère" et une autre contient "éléphant", il est nécessaire que l’algorithme sache que la première doit appara”tre au dessus de la seconde dans le super-arbre à construire. Malheureusement, une telle information n’est pas présente en général dans les phylogénies sources, et doit être collectée de façon extérieure, par exemple par extraction d’information depuis une taxonomie (classification) des organismes vivants (cf Taxonomy Browser).

La recherche effectuée dans ce stage s’orientera en fonction des axes suivants :

1. Etant donné une collection d’arbres sources semi-étiquetés, identifier les conditions qui font qu’un super-arbre respectant les relations d’ancestralités entre étiquettes peut être obtenu.
   
2. Identifier le type et la quantité d’information qu’il est nécessaire d’ajouter à une collection d’arbres sources (pas forcément semi-étiquetés) pour que la reconstruction du super-arbre puisse se faire correctement.
   
3. Mettre au point une stratégie pour collecter les informations d’ancestralité manquantes dans une collection d’arbres sources compatibles. Implémenter un algorithme collectant ces informations et effectuant la reconstruction du super-arbre en présence de ces informations.
   
4. Dans le cas d’arbres sources incompatibles, il est nécessaire de proposer une méthode qui reconstruise un super-arbre en respectant une plus grande partie possible des informations topologiques des arbres sources. Plusieurs pistes à explorer sont envisagées. Il s’agira de les explorer (écriture de l’algorithme, implémentation, expérimentation, comparaison).

Les recherches effectuées le stage seront appliquées à des problèmes biologiques pour lesquels nous disposons de données et d’expertise grâce à une collaborartion déjà en cours dans le cadre d’une ACI avec l’équipe Phylogénie Moléculaire d’Emmanuel Douzery, appartenant à l’ISEM (Institut des Sciences de l’Evolution de Montpellier). 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 de la base de données internationale TreeBASE, contenant plusieurs milliers d’arbres.

Bibliographie mentionnée :

[1] V.Berry and C.Semple, Fast reconstruction of a phylogeny for compatible source trees, Systematic Biology (in press).

Bibliographie complémentaire :

- Algorithme de compatibilité ancestrale (pdf)