Quelques problèmes de graphes en phylogénie
Institution:
Paris 7Disciplines:
Directors:
Abstract EN:
A phylogenetic model, which describes the evolutionary history of the ancestors of a species set, is a graph where each vertex of degree 1 is labelled by a species. This PhD dissertation explores 3 graph problems related to the reconstruction of the evolution of an existent species set. The used models are phylogenetic trees and phylogenetic networks which are generalizations of trees. The first problem comes from the perfect phylogeny, i. E. Reconstructing phylogenetic trees from a set of characters. We conjecture that there exists a function f(r) such that a set of r-states characters is compatible iff every f(r) characters are compatible. An approach is using the notion of chordal sandwich graph. We propose an example showing that f(4) > 4 which improves the bound of Fitch-Meacham when r=4, and an operation compatible with the notion of chordal sandwich graph. The second problem consists of reconstructing a level-k network from a dense triplet set. We prove that this problem is polynomial for a fixed value of k by bounding the number of possible decompositions of a network. Finally, we generalize the problem of k-leaf powers of trees to networks. The input gives the information about the distance between each two species compared with a threshold k, and we must reconstruct networks which respect these distances. A similar result with the tree model is found for recognizing 3-leaf network powers. For 4-leaf powers, by imposing a restriction on the cycles of networks, we have a polynomial algorithm.
Abstract FR:
Un modèle phylogénétique, qui décrit l'histoire de l'évolution des ancêtres d'un ensemble d'espèces, est un graphe dans lequel chaque sommet de degré 1 est étiqueté par une espèce. Cette thèse explore 3 problèmes de graphes liés à la reconstruction de l'évolution d'un ensemble d'espèces existantes. Les modèles utilisés sont les arbres phylogénétiques et les réseaux phylogénétiques qui sont des généralisations des arbres. Le premier problème vient de la phylogénie parfaite, i. E. Reconstruire arbre phylogénétiques depuis un ensemble de caractères. On conjecture qu'il existe une fonction f(r) telle qu'un ensemble de r-états caractères est compatible ssi chaque f(r) caractères sont compatibles. Une approche est d'utiliser la notion de graphe sandwich triangulé. On propose un exemple qui montre que f(4) > 4, qui donc améliore la borne de Fitch-Meacham quand r=4, et une opération compatible avec la notion de graphe sandwich triangulé. Le deuxième problème consiste à reconstruire un réseau de niveau k depuis un ensemble dense de triplets. On montre que ce problème est polynomial avec un k fixé en bornant le nombre de décompositions possibles d'un réseau. Finalement, nous généralisons le problème de k-leaf power d'arbres aux réseaux. L'entrée donne l'information sur la distance entre chaque 2 espèces par rapport d'un seuil k, et il s'agit de reconstruire les réseaux qui respectent ces distances. Un résultat similaire avec le modèle d'arbre est trouvé pour reconnaître les 3-leaf power de réseaux. Pour 4-leaf power, en imposant une restriction sur les cycles des réseaux, nous obtenons un algorithme polynomial.