Evènement pour le groupe Combinatoire Énumérative et Algébrique


Date 2009-10-23  10:45-11:45
TitreArbres de gènes et arbres d’espèces : problèmes de parcimonie 
RésuméUne famille de gènes est un ensemble de gènes, présents dans les génomes de plusieurs organismes, qui ont pour origine un unique ancêtre commun. Un arbre de gènes est un arbre phylogénétique décrivant les relations des gènes d'une même famille. Un tel arbre est le résultat d’événements d'évolution qui incluent la spéciation, la duplication de gène et la perte de gène. Dans le cadre des approches dites « phylogénomiques » qui visent à inférer l’histoire évolutive de plusieurs espèces à partir de leurs génomes complets (au contraire des approches phylogénétiques qui se concentrent sur une famille de gènes), l’approche consistant à rechercher, étant donné un ensemble d'arbres de gènes, un arbre d'espèces qui induit un nombre minimum de duplications est de plus en plus employée. Il s’agit d’un problème d’optimisation combinatoire simple à décrire, mais qui est, sans surprise, NP-complet. Dans cet exposé, je propose de : - faire un survol de ce problème ; - présenter des instances que l’on peut résoudre en temps polynomial (collaboration avec J-P Doyon et Nadia El-Mabrouk) ; - décrire un algorithme astucieux de calcul d’une 3-approximation pour le calcul de la première spéciation parcimonieuse, basée sur la minimisation de fonctions sous-modulaires (collaboration avec A. Ouangraoua). 
Lieu076 
OrateurCédric Chauve 
Emailcedric.chauve@sfu.ca 
UrlSFU 



Aucun document lié à cet événement.

Retour
Retour à l'index