Actualités
  Période
semaine
ou mois
aucune période


  Thèmes:
Thèses
Colloques
Autres
Groupes
Tous les thèmes

   
  Liens:
Voir les thèses

Voir les colloques

Voir les autres événements

Voir la page des groupes

Accéder à l'intranet

Intitulé:   
Tri parfait par renversements : analyse de complexité en moyenne
du 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