Stage 1 : réalisation d’un logiciel de reconstruction phylogénique par maximum de parcimonie

Les méthodes de reconstruction phylogénétique cherchent à reconstruire l’histoire évolutive des espèces à partir de séquences biologiques. Le principe général de ce type de méthode est de définir un critère que l’on peut estimer pour un arbre et de rechercher l’arbre le meilleur au sens de ce critère.

Le maximum de parcimonie est l’un des plus anciens critères. Il s’est ensuite vu supplanté par le maximum de vraisemblance. De nombreuses heuristiques pour optimiser la vraisemblance ont été développées. De nouvelles applications du maximum de parcimonie rendent ce critère à nouveau pertinent.

L’objectif de ce stage est de réaliser un logiciel utilisant le critère de maximum de parcimonie qui tire partie des heuristiques développées dans le cadre du maximum de vraisemblance. Ce logiciel devra pouvoir être utilisé au sein de notre laboratoire et pouvoir être diffusé sur Internet. Ce qui implique une validation importante du logiciel notamment au travers de tests unitaires automatiques. L’implémentation se fera en C++ en s’appuyant sur une librairie développée à l’UM2 (bio++ : http://kimura.univ-montp2.fr/BioPP/).

Remarque : C++, algorithmique.

Stage 2 : réalisation d’un logiciel de manipulation d’arbres étiquetés.

L’objectif de ce stage est de développer un outil permettant de faire des opérations simples sur des arbres étiquetés. Il faudra par exemple implémenter des méthodes pour le calcul de distances entre 2 arbres, d’arbres consensus, de ré-enracinement et de filtrage des feuilles. Ce logiciel devra pouvoir être utilisé au sein de notre laboratoire et pouvoir être diffusé sur Internet. Ce qui implique une validation importante du logiciel notamment au travers de tests unitaires automatiques.

Remarque : C++, algorithmique, graphes.

Stage 3 : inférence de phylogénies à partir de plusieurs gènes.

Les méthodes de reconstruction phylogénétique cherchent à reconstruire l’histoire évolutive des espèces à partir de séquences biologiques. Le principe général de ce type de méthodes est de définir un critère que l’on peut estimer pour un arbre et de rechercher l’arbre le meilleur au sens de ce critère. De plus en plus d’études phylogénétiques s’appuient non plus sur un seul gène mais sur un ensemble de gènes. Une approche largement utilisée dans le cadre d’analyses multigènes consiste à concaténer l’ensemble de ces données en un seul jeu de séquences alignées et à utiliser une méthode conçue à l’origine pour traiter un seul gène. L’objectif de ce stage et d’essayer de prendre en compte le fait que les données sont issues de plusieurs gènes afin d’améliorer l’heuristique d’optimisation. L’implémentation se fera en C++ en s’appuyant sur une librairie développée à l’UM2 (bio++ : http://kimura.univ-montp2.fr/BioPP/).

Remarque : C++, algorithmique.