Langues : English français
Accueil > Manifestations > Thèses et HDR > Thèses > Laurent BULTEAU

Laurent BULTEAU

Directeur de thèse

Guillaume Fertin
Irena Rusu

Résumé

Dans cette thèse, nous explorons la complexité algorithmique de plusieurs problèmes issus de la génomique comparative, et nous apportons des solutions à certains de ces problèmes sous la forme d’algorithmes d’approximation ou paramétrés.

Le dénominateur commun aux problèmes soulevés est la mise en commun d’informations génomiques provenant de plusieurs espèces dans le but de tirer des conclusions pertinentes pour l’étude de ces espèces. Les problèmes de tri par transpositions et de tri par inversions préfixes permettent de retrouver l’histoire évolutive des deux espèces. Les problèmes de distance exemplaire et de plus petite partition commune ont pour but de comparer deux génomes dans les cas algorithmiquement difficiles où chaque gène apparaît avec plusieurs copies indistinguables dans le génome. Enfin, les problèmes d’extraction de bandes et de linéarisation visent à préciser ou corriger l’information génomique afin qu’elle soit plus pertinente pour des traitements ultérieurs.

Les résultats principaux que nous présentons sont la NP-difficulté des problèmes de tri (par transpositions et par inversions préfixes) dont la complexité est restée longtemps une question ouverte ; une étude complète de la complexité du calcul des distances exemplaires ; un algorithme paramétré pour le calcul de plus petite partition commune (avec un unique paramètre étant la taille de la partition) ; une étude à la fois large et approfondie des problèmes d’extraction de bandes et enfin une nouvelle structure de données permettant de résoudre plus efficacement le problème de linéarisation.

Mots-clés : Génomique comparative, Théorie de la complexité, Algorithmes paramétrés, Approximabilité.

Composition du jury

  • Rolf Niedermeier, Professeur, Technische Universität, Berlin (Examinateur)
  • Dieter Kratsch, Professeur, Université Paul Verlaine, Metz (Examinateur)
  • Christina Bazgan, Professeur, Université Paris Dauphine (Rapporteur)
  • Michel Habib, Professeur, Université Paris Diderot (Rapporteur)
  • Guillaume Fertin, Université de Nantes (Directeur de thèse)
  • Irena Rusu, Université de Nantes (Co-Directrice de thèse)

Dernière modification : mardi 14 janvier 2014