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).

Deux types de méthodes de super-arbres existent : les méthodes d'optimisation, cherchant à résoudre les conflits entre arbres sources, et les méthodes de consensus, cherchant à ne pas prendre partie dans le cas de conflits. Peu de méthodes de consensus existent actuellement. La méthode pionnière dans ce domaine est la méthode de consensus strict pour les super-arbres, proposée par Gordon en 1986.

En l'état, cette méthode souffre de plusieurs défauts :

• elle n'accepte que deux arbres en entrée
• elle ne fonctionne que si les arbres sont compatibles lorsqu'ils sont restreints à leurs feuilles communes
• son extension naturelle à plus de deux arbres présuppose que tous les arbres sources ont en commun un ensemble

  de feuilles (ce qui n'est pas toujours le cas dans les données réelles).

Le but de ce stage est de proposer une extension de la méthode de consensus-strict pour les super-arbres de Gordon [86].

On adoptera une approche top-down, consistant à construire le super-arbre en partant de ces clades les plus grands. Pour ce faire on travaillera depuis l'ensemble des clades "couvrants" induits par les arbres sources. Un clade "couvrant" est un clade qui n'est inclus dans aucun autre clade induit par les arbres de départ. Suivant les intersections entre clades couvrants, on peut déduire les premiers clades de super-arbre. On trouve les clades suivants en remplaçant les clades couvrants utilisés par les clades qu'il couvraient directement dans les arbres de départ, et ainsi de suite.

Dans un premier temps, il s'agira de bien fixer le comportement de la méthode suivant le type d'arbres de départ (on travaillera sur des exemples simples à la main), puis on proposera un algorithme de complexité aussi faible que possible (si possible linéaire). Enfin, une implémentation sera proposée de façon à ce que la méthode soit utilisable par les biologistes.

Bibliographie mentionnée :

[1] Gordon, A.G., Consensus supertrees: the synthesis of rooted trees containing overlapping sets of labelled leaves,Journal of Classification, vol 3, pages 335--348, 1986