Stage de fin de master à l'université de Tübingen (encadrement : Daniel Huson)

(in English)

Sujets abordés

Optimisation de la représentation des splitsgraphs (ou split graphs, ou split networks).

Pour représenter l'évolution des espèces, ou des gènes, le modèle classique est l'arbre phylogénétique. Mais il s'avère insuffisant pour représenter les transferts horizontaux de gènes, les recombinaisons ou les hybridations. Dans ce cas, on est amené à utiliser des réseaux phylogénétiques.

Le logiciel SplitsTree permet de représenter plusieurs de ces réseaux, dont un cas particulier très utile : les "splitsgraphs". Ces graphes représentent les conflits phylogénétiques, en faisant apparaître des boîtes aux endroits où l'évolution est incertaine. On peut obtenir un splitsgraph en effectuant un bootstrap sur un arbre phylogénétique, mais aussi en prenant le consensus de plusieurs arbres, éventuellement ayant un nombre de taxons différents.

Mon objectif lors de cette première partie du stage était l'amélioration du dessin de ces splitsgraphs dans SplitsTree, en faisant augmenter l'aire de ces boîtes qui représentent les conflits phylogénétiques. Ce travail a été fait en commun avec Daniel Huson.


Optimisation de la représentation de réseaux réticulés.

Quand on ajoute des réticulations à un abre phylogénétique, par exemple causées par des recombinaisons, il est possible que les arêtes nouvellement ajoutées en intersectent d'autres de l'arbre de départ. Changer l'ordre des taxons pourrait réduire le nombre de ces intersections. Mon travail avec Tobias Klöpper a consisté à trouver une heuristique pour minimiser le nombre total d'intersections. Celle que nous proposons est fondée sur le concept de graphe dual, avec une distance qui reflète le nombre d'intersections, et un processus d'image miroir pour réduire cette distance dans un algorithme de récuit simulé.


Bilan du stage :


Diaporama des résultats     Quelques résultats     Photos de Tuebingen

On ouvre les boîtes
10 boucles de l'algorithme d'ouverture des boîtes.

Retour à l'accueil