Nematodes in the genus Steinernema (Nematoda: Steinernematidae) and their associated bacteria Xenorhabdus spp. (Gamma-Proteobacteria) are an emergent model of terrestrial animal-microbe symbiosis. Although interest in this association initially arose out of their potential as biocontrol agents against insect pests (Tanada and Kaya, 1993), this mutualistic partnership is currently viewed more broadly under the umbrella of basic sciences to inform ecology, evolution, biochemistry, molecular, among other disciplines (Burnell and Stock, 2000; Forst and Clarke, 2002).Despite advances in the discovery and field application of this nematode-bacterium partnership, and the growing popularity of this model system, relatively little has been published to uncover the evolutionary facets of their association. This study adds to the body of knowledge regarding nematode-bacteria symbiosis by 1) producing novel, multi-gene phylogenies for Steinernema and Xenorhabdus; 2) proposing a possible scenario for historical association in the form of a cophylogenetic hypothesis; 3) describing a newly discovered Steinernema species from France.

Das Problem der Rekonstruktion einer gemeinsamen evolutionären Entwicklung zwischen Wirts- und Parasitenspezies ist in der Forschung weit diskutiert. Dabei wird der Komplexität einer solchen Berechnung besondere Bedeutung beigemessen. In dieser Arbeit wird ein algorithmischer Ansatz vorgestellt, welcher auf Basis dynamischer Programmierung eine Rekonstruktion zweier phylogenetischer Stammbäume und einer gegebenen Abbildung von Parasiten auf zugehörige Wirte erzeugt. Grundlage dieser Berechnung ist ein ereignis-basiertes Modell der Koevolution, bei dem jedem Ereignis ein Kostenwert zugeordnet ist. Gesucht wird nach Rekonstruktionen, welche die Gesamtkosten der aufgetretenen Ereignisse minimieren. Es wird eine Vorgehensweise vorgestellt, mit welcher sich die Kosten der Ereignisse automatisch berechnen lassen. Dazu wurde ein Gütemaß entwickelt, um verschiedene Rekonstruktionen bezüglich der bei ihrer Berechnung verwendeten Ereigniskostenverteilung bewerten zu können. Im Gegensatz zu bisherigen Arbeiten unterstützt der vorgestellte Ansatz zudem die Verwendung von Stammbäumen mit mehrfach verzweigenden Knoten. Die algorithmischen Überlegungen wurden in einem Javaprogramm namens DynamicTreeMap umgesetzt. / The problem of reconstructing the common evolutionary development between host- and parasite species has been strongly discussed in research. Hereby a special meaning has been attributed to the complexity of such a calculation. In this thesis an algorithmic approach based on dynamic programming will be introduced, that creates a reconstruction of two phylogenetic genealogical trees and a given mapping of parasites on appropriate hosts. The foundation of this calaculation is an event-driven model of coevolution where costs are assigned to each event. The algorithm searches for reconstructions, which minimize the total costs of all occurred events. A method will be introduced which calculates the event-costs automatically. Therefore a quality rate has been developed, to evaluate different reconstructions concerning the used event-costs. Unlike present approaches genealogical trees with multiple branching nodes can be considered. The described approach has been implemented in a java program named DynamicTreeMap.

Host-parasite associations are born by cospeciations or by host switches. Feather lice have traditionally been used as model parasites for studying these events and underlying ecological factors. By now tens of analyses have addressed comparisons of host and parasite phylogenies to study cospeciations and host switches in lice, however, these analyses are strongly biased towards the temperate zone. Tropical environment could provide new insight into the origin of host-parasite interactions, because it is ecologically unique. This work aims to supplement the knowledge of host-parasite associations in lice using coevolution analyses of two feather lice genera and their passerine hosts in tropical rainforest in Cameroon. It shows that lice in the tropics cospeciate rarely. To assess whether host switches are non-random and occur preferentially between hosts with specific traits, this work also analyses relations between parasite genetic distances and hosts' trait similarities. No effect of host morphology and spatial distribution was found. However, genetic distances of the lice strongly correlate with genetic distances of their hosts.

A subset of 199 Melissotarsus insularis and 130 Diaspididae specimens were analyzed to 1) determine the species status of M. insularis and 2) to explore the relative intimacy of the relationship between M. insularis and Diaspididae. An analysis of molecular variance and the observed lack of association between clades and distinct habitats on the M. insularis phylogeny suggested that while M. insularis exhibits isolation by distance, it does not apparently diversify by habitat. When cryptic COI pseudogenes were accounted for, the majority of the genetic diversity exhibited by M. insularis was limited to a divergence of 3% or less suggesting that M. insularis represents a single, albeit broadly distributed, species. A cophylogenetic reconstruction of the relationship between M. insularis and Diaspididae yielded 14 “cospeciation” events but was not significant unlike reconstructions of host-parasite relationships. Analyses of reduced datasets suggested that incomplete taxon sampling may significantly affect cophylogenetic reconstruction results. / National Science Foundation (grants No. DEB-0072713, DEB-0344731 to BLF and DEB-0842395 to BLF and MAS), a Natural Sciences and Engineering Research Council of Canada Discovery Grant to MAS and a Leaders Opportunity Fund grant from the Canada Foundation for Innovation to MAS

Lors de cette thèse, je me suis intéressée aux modèles et aux algorithmes pour étudier l'histoire évolutive commune des hôtes et des symbiotes. Le premier objectif était d'analyser la robustesse des méthodes de réconciliation des arbres phylogénétiques, qui sont très utilisées dans ce type d'étude. Celles-ci associent (ou lient) un arbre, d'habitude celui des symbiotes, à l'autre, en utilisant un modèle dit basé sur des évènements. Les évènements les plus utilisés sont la cospéciation, la duplication, le saut et la perte. Les phylogénies des hôtes et des symbiotes sont généralement considérés comme donnés, et sans aucune erreur. L'objectif était de comprendre les forces et les faiblesses du modèle parcimonieux utilisé et comprendre comment les résultats finaux peuvent être influencés en présence de petites perturbations ou d'erreurs dans les données en entrée. Ici deux cas sont considérés, le premier est le choix erroné d'une association entre les feuilles des hôtes et des symbiotes dans le cas où plusieurs existent, le deuxième est lié au mauvais choix de l'enracinement de l'arbre des symbiotes. Nos résultats montrent que le choix des associations entre feuilles et le choix de l'enracinement peuvent avoir un fort impact sur la variabilité de la réconciliation obtenue. Nous avons également remarqué que l'evènement appelé “saut” joue un rôle important dans l'étude de la robustesse, surtout pour le problème de l'enracinement. Le deuxième objectif de cette thèse était d'introduire certains evènements peu ou pas formellement considérés dans la littérature. L'un d'entre eux est la “propagation”, qui correspond à l'invasion de différents hôtes par un même symbiote. Dans ce cas, lorsque les propagations ne sont pas considérés, les réconciliations optimales sont obtenues en tenant compte seulement des coûts des évènements classiques (cospeciation, duplication, saut, perte). La nécessité de développer des méthodes statistiques pour assigner les coûts les plus appropriés est toujours d'actualité. Deux types de propagations sont introduites : verticaux et horizontaux. Le premier type correspond à ce qu'on pourrait appeler aussi un gel, à savoir que l'évolution du symbiote s'arrête et “gèle” alors que le symbiote continue d'être associé à un hôte et aux nouvelles espèces qui descendent de cet hôte. Le second comprend à la fois une invasion, du symbiote qui reste associé à l'hôte initial, mais qui en même temps s'associe (“envahit”) un autre hôte incomparable avec le premier, et un gel par rapport à l'évolution des deux l'hôtes, celui auquel il était associé au début et celui qu'il a envahi. Nos résultats montrent que l'introduction de ces evènements rend le modèle plus réaliste, mais aussi que désormais il est possible d'utiliser directement des jeux de données avec un symbiote qui est associé plusieurs hôtes au même temps, ce qui n'était pas faisable auparavant / In this Ph.D. work, we proposed models and algorithms to study the common evolutionary history of hosts and symbionts. The first goal was to analyse the robustness of the methods of phylogenetic tree reconciliations, which are a common way of performing such study. This involves mapping one tree, most often the symbiont’s, to the other using a so-called event-based model. The events considered in general are cospeciation, duplication, host switch, and loss. The host and the symbiont phylogenies are usually considered as given and without any errors. The objective here was to understand the strengths and weaknesses of the parsimonious model used in such mappings of one tree to another, and how the final results may be influenced when small errors are present, or are introduced in the input datasets. This may correspond either to a wrong choice of present-day symbiont-host associations in the case where multiple ones exist, or to small errors related to a wrong rooting of the symbiont tree. Our results show that the choice of leaf associations and of root placement may have a strong impact on the variability of the reconciliation output. We also noticed that the host switch event has an important role in particular for the rooting problem. The second goal of this Ph.D. was to introduce some events that are little or not formally considered in the literature. One of them is the spread, which corresponds to the invasion of different hosts by a same symbiont. In this case, as when spreads are not considered, the optimal reconciliations obtained will depend on the choice made for the costs of the events. The need to develop statistical methods to assign the most appropriate ones therefore remains of actuality. Two types of spread are introduced: vertical and horizontal. The first case corresponds to what could be called also a freeze in the sense that the evolution of the symbiont “freezes” while the symbiont continues to be associated with a host and with the new species that descend from this host. The second includes both an invasion, of the symbiont which remains with the initial host but at the same time gets associated with (“invades”) another one incomparable with the first, and a freeze, actually a double freeze as the evolution of the symbiont “freezes” in relation to the evolution of the host to which it was initially associated and in relation to the evolution of the second one it “invaded”. Our results show that the introduction of these events makes the model more realistic, but also that it is now possible to directly use datasets with a symbiont that is associated with more than one host at the same time, which was not feasible before