Cette thèse étudie d'un point de vue algorithmique diverses méthodes de consensus portant sur des collections d'objets étiquetés. Les problèmes étudiés impliquent des objets étiquetés sans répétition d'étiquettes ; ces objets peuvent être des arbres enracinés ou des séquences, avec des applications à la bioinformatique. Ainsi, les problèmes sur les arbres considérés dans cette thèse peuvent trouver des applications pour l'estimation de congruence entre phylogénies, pour la construction de superarbres, et pour l'identification de transferts horizontaux de gènes. Pour leur part, les problèmes sur les séquences considérés dans cette thèse ont des applications potentielles pour le calcul de distance génomique basé sur les ordres de gènes. De manière générale, ce travail met à profit les théories de la complexité paramétrique et de l'approximabilité pour obtenir des algorithmes et des résultats de difficulté pour les problèmes étudiés.
| Identifer | oai:union.ndltd.org:CCSD/oai:tel.archives-ouvertes.fr:tel-00401456 |
| Date | 09 December 2008 |
| Creators | Guillemot, Sylvain |
| Publisher | Université Montpellier II - Sciences et Techniques du Languedoc |
| Source Sets | CCSD theses-EN-ligne, France |
| Language | fra |
| Detected Language | French |
| Type | PhD thesis |
Page generated in 0.0023 seconds