Phylogenie

Bonjour,
J'ai un TP de Structures de données ( phylogenie ) en utilisant java sur eclipse, si quelqu'un peut m'aidé , je vous remercie d'avance;

Projet du module Structures de Donnees
Arbres et TDA
Application aux phylogenies

1 Motivation
Les arbres sont utilises de nombreuses facons en informatique et d'en d'autres do-
maines ou l'informatique intervient. Par exemple, pour modeliser l'evolution des especes,
on utilise des arbres dont les feuilles representent les especes actuelles, et les noeuds in-
ternes representent les especes ancestrales (cf gure).
Les arbres representant l'evolution des especes sont appeles phylogenies. Les phy-
logenies sont representables par des arbres comme nous les avons vu en cours avec
quelques proprietes supplementaires. Par exemple, les ar^etes ont une longueur. Suivant
les applications, la longueur d'une arete represente soit un temps d'evolution (la lon-
gueur est d'autant plus importante que les epoques a laquelle vivent les deux especes aux

extremites de l'arete sont eloignees dans le temps) ou des distances evolutives (l'ar^ete
est d'autant plus longue que ces especes ont des genomes dierents).
2 But du projet
Le but est de proposer ici un module pour manipuler les phylogenies dans des appli-
cations. On realisera pour cela un type de donnees abstrait Phylogenie (sans accent
pour le codage Java).
Pour cela on proposera a la fois une interface et une classe d'implementation basee
sur ls arbres cha^nes vus precedemment en TP.
3 Fonctionnalites
Quand on manipule des phylogenies, on est interesse par tout un tas de fonction-
nalites qui ne sont pas naturellement presentes dans le tda Arbre. Ce projet vise a en
implementer un petit nombre.
4 Realisation
4.1 Premiere phase
Pour cette premiere phase on se concentre sur les algorithmes de parcours d'arbres.
On utilisera pour tester une phylogenie dont la structure est progressivement creee par
le la methode main() par des appels au constructeur.
4.1.1 Creation de l'interface Phylogenie
Cette interface doit deja inclure dans son contrat certaines operations que nous allons
implementer ainsi que des operations denies pour le tda Arbre.
Comment vous y prendre pour denir cette interface et la positionner par rapport
au tda Arbre ?
Vous passerez ensuite a la pratique en mettant cette interface dans un package tda
qui comprendra aussi les interfaces et classes de Arbre.
Ajouter deja dans le contrat de Phylogenie la methode longueur() qui permet de
conna^re la longueur totale d'une phylogenie, c'est-a-dire la somme des longueurs de ses
ar^etes.
4.1.2 Creation d'une implementation
Pour creer des objets phylogenies en pratique nous allons mettre en place une
implementation basee sur des objets cha^nes les uns aux autres, comme nous l'avons
vu pour les tda Arbre et Liste
Mettez en place cette implementation, en n'oubliant pas d'ajouter un attribut per-
mettant de stocker la longueur des ar^etes quand elle est precisee.
Proposez un/des constructeurs permettant de mettre en place une phylogenie depuis
les attributs que vous avez denis.
2
Testez votre implementation en lui ajoutant une classe main(...) dans laquelle
vous ferez des appels au constructeur pour essayer de creer une phylogenie comportant
4 feuilles et 3 noeuds internes.
Demandez un achage de l'objet Phylogenie ainsi cree. Quel resultat obtenez-vous
a l'ecran ? pourquoi ?
(ne remediez pas ici a ce probleme, passez par la question suivante).
4.1.3 Achage en texte d'une phylogenie
Proposez une methode toString() permettant d'acher un objet de type Phylogenie
au format Newick (cf. ci-dessous). Testez ensuite cette methode sur une phylogenie
creee \en dur" dans votre methode main(...), comme celle creee pour repondre a la
question precedente.
Le format Newick est un format parenthese pour coder un arbre par une cha^ne de
caracteres. Par exemple, la phylogenie de la gure ci-dessus est representee par la chaine
suivante :
(((Canis :0.058216,((Homo :0.001967,Pan :0.001103) :0.008098,Macaca :0.009522) :0.039742)
:0.004001,(Mus :0.092989,Bos :0.205584) :0.02403) :0.105714,Monodelphi :0.105714) ;
Chaque couple de parentheses represente un noeud de l'arbre. Les chires representent
les longueurs d'ar^etes (donnees systematiquement apres le symbole deux-points). Une
longueur s'applique soit a l'ar^ete menant a une feuille, identiee par le nom de l'espece
qui lui correspond, soit a une ar^ete interne, identiee par un couple de parentheses.
4.2 Implementation de fonctions utilitaires
4.3 Calcul de la longueur d'une phylogenie
Implementez la methode longueur() dont il a ete question plus haut dans ce docu-
ment.
4.4 Ultrametricite d'une phylogenie
Une phylohgenie est ultrametrique si la distance de chaque feuille a la racine est
toujours la m^eme. Implementez une methode permettant de savoir si une phylogenie est
ultrametrique.
Pour cela, vous aurez inter^et a d'abord ecrire une methode renvoyant la liste des
feuilles, que vous passerez ensuite en revue une a une.
3
4.5 Re-enracinement d'une phylogenie
Implementez une fonction prenant au clavier un ensemble d'especes, puis re-enracinant
la phylogenie au dessus du noeud correspondant a ce groupe d'especes.
Par exemple si l'utilisateur choisi le groupe compose de Mus et Bos, sur la phylogenie
de la gure precedente, on obtient la phylogienie de la figure suivante :
5 Pour les plus courageux
Implementez un constructeur de phylogienie acceptant une String en parametre,
celle-ci contenant une chaine Newick. Le constructeur devra creer l'objet phylogenie qui
est codee dans la chaine Newick.
4