TER 2004-2005

Méthode de consensus majoritaire pour l'assemblage d'arbres dont les feuilles sont étiquetées.

Encadrant : Vincent Berry, UM2-LIRMM.

Mot clefs : algorithmique, arbres, complexité d'un algorithme, graphes.

Résumé :

On dispose d'arbres dont les feuilles ont chacune une étiquette. Ces arbres n'ont pas forcément la même structure (certains sont équilibrés, d'autres non, etc). On veut obtenir un arbre "consensus" de ces arbres, c'est à dire une sorte d'arbre résumé, représentant tous les points sur lesquels la majorité des arbres de départ sont d'accord.

Quand tous les arbres de départ ont le même ensemble d'étiquettes, il existe une méthode bien établie (nommée AM). Le sujet de ce projet porte sur le cas où les arbres de départ ont des ensembles d'étiquettes différents (les arbres ont toutefois quelques étiquettes en commun). Ce cas n'a pas encore été étudié semble-t-il

Etapes proposées dans la réalisation du projet :

1. On se familiarisera avec les programmes (ligne de commande) implémentant la méthode AM ou proche de cette approche. Par ex : Phylip, PAUP, Clann.

2. Puis on proposera une extension naturelle de la méthode AM, en utilisant par exemple une modélisation sous forme de graphe.

3. On pourra ensuite explorer une variante permettant de produire un arbre résultat ne contenant pas forcément toutes les étiquettes des arbres de départ.

Domaine d'application :

de telles méthodes peuvent être appliquées dans de nombreux domaines (bioinformatique, description d'images, langues naturelles, bases de données, etc). Si nous en avons le temps, et suivant la motivation des étudiants, nous regarderons de plus près leur application en bioinformatique pour la construction de phylogénies, sortes d'arbres généalogiques expliquant la façon dont les espèces vivantes actuelles découlent d'ancêtres communs (espèces éteintes). Notamment, on pourra considérer la construction d' "arbres de la Vie".

Type du projet :

ce projet porte avant tout sur l'étude et l'écriture d'algorithmes d'assemblage d'arbres, puis éventuellement sur la programmation des méthodes proposées et leur comparaison sur la base de données simulées ou réelles. Si les étudiants sont extrêmement motivés et productifs, on pourra aller jusqu'à la mise en ligne du ou des programmes (technos web CGI/scripting) sur un serveur déjà opérationnel au LIRMM afin de permettre à d'autres scientifiques de traiter leurs collections d'arbres à distance.

Pré-requis :

Il est conseillé aux étudiants choisissant ce sujet de suivre les modules d'algorithmique, le module sur les graphes, et éventuellement un module de programmation et de calculabilité. Bien-sûr, malgré une application potentielle à la biologie, aucune connaissance biologique n'est requise pour ce projet.

Bibliographie :

prévoir la lecture de 2,3 articles, dont :

J. Creevey, CLANN, article paru dans la revue Bioinformatics (en anglais)

V.Berry Super-arbre d'accord maximum, rapport de recherche (en français)