Combinatorial Approaches for the Consensus of Trees and Sequences
| Autor: | Guillemot, Sylvain |
|---|---|
| Přispěvatelé: | Peridier, Martine |
| Jazyk: | francouzština |
| Rok vydání: | 2008 |
| Předmět: |
computational complexity
parameterized algorithms Méthodes de consensus complexité calculatoire [INFO] Computer Science [cs] algorithmes d'approximation algorithmes paramétrés Consensus methods complexité paramétrique algorithmics approximation algorithms algorithmique bioinformatique bioinformatics parameterized complexity |
| Popis: | This thesis studies from an algorithmic point of view various consensus methods on collections of labeled objects. The problems under study involve labeled objects without repetition of labels ; these objects may be rooted trees or sequences, with applications to bioinformatics. For instance, the problems on trees considered in this thesis may find applications to the estimation of congruence between phylogenies, the construction of supertrees, and the identification of horizontal gene transfers. For their part, the problems on sequences considered in this thesis have potential applications for the computation of genomic distances based on gene orders. Overall, this work relies on the theories of parameterized complexity and approximability to obtain algorithms and hardness results for the problems studied. 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|