Evènement pour le groupe BioInformatique et Visualisation


Date 2011-09-29  11:00-12:30
TitreTri parfait par renversements : analyse de complexité en moyenne 
RésuméLe problème du tri parfait par renversements est motivé par l'étude des réarrangements de génomes. Il s'agit de trier une permutation signée vers la permutation identité (ou son miroir), par une séquence de renversements qui ne cassent aucun intervalle commun. Dans les travaux de Bérard et al. (2007), un algorithme résolvant le problème du tri parfait par renversements d'une permutation signée est proposé, qui repose de manière cruciale sur les arbres des intervalles forts associés aux permutations. Les propriétés combinatoires de cette famille d'arbres sont essentielles à l'analyse de l'algorithme. Dans l'exposé, je présenterai l'algorithme de Bérard et al., et montrerai comment une étude combinatoire de ces arbres permet de démontrer que la complexité moyenne de l'algorithme est polynomiale. Plus précisément, je montrerai aussi que cet algorithme de tri est de complexité polynomiale avec probabilité 1, asymptotiquement en la taille des permutations en entrée. Nous nous intéresserons ensuite à la classe des permutations séparables, pour laquelle la combinatoire analytique permet d'obtenir des résultats précis sur certains paramètres des scénarios calculés par l'algorithme : longueur moyenne d'un renversement et nombre moyen de renversements. Enfin, nous discuterons de la pertinence des résultats en moyenne obtenus pour la distribution uniforme, et des ouvertures possibles vers des distributions non-uniformes. Il s'agit de travaux en commun avec Cédric Chauve, Marni Mishna et Dominique Rossin, puis avec Marni Mishna et Cyril Nicaud. 
Lieu178 (LaBRI) 
OrateurMathilde Bouvel 
EmailMathimathilde.bouvel@labri.fr 
UrlLaBRI 



Aucun document lié à cet événement.

Retour
Retour à l'index