Les Wolbachia sont des α-Protéobactéries endocellulaires transmises maternellement et qui manipulent la reproduction des Arthropodes pour augmenter leur transmission. Chez le moustique Culex pipiens, Wolbachia induit l'incompatibilité cytoplasmique (IC) qui se traduit par une forte mortalité embryonnaire lors de croisements entre individus infectés par des souches incompatibles de Wolbachia. Ce moustique se caractérise par une forte diversité génétique de ses Wolbachia (nommées wPip) et par des patrons d'IC complexes. Nous avons examiné les mécanismes qui façonnent la dynamique de cette association symbiotique aux niveaux génomique, phénotypique et populationnel. Nous avons montré que les souches wPip ont une origine génétique commune récente et qu'elles s'organisent en groupes génétiques présentant une structuration géographique. Nous avons mis en évidence des évènements de recombinaison entre souches wPip qui pourraient jouer un rôle majeur dans la diversité génétique des Wolbachia et dans l'évolution rapide des patrons d'IC. En croisant des lignées de moustiques d'origines géographiques diverses et infectées par des souches de différents groupes génétiques, nous avons montré que les IC (i) évoluent très rapidement chez Cx. pipiens; (ii) sont contrôlées par plusieurs déterminants génétiques, et (iii) qu'il y a une relation entre les patrons d'IC et les groupes génétiques des Wolbachia. Dans les populations naturelles, il apparaît que les IC sont contre sélectionnées au sein d'une population mais qu'une zone de contact entre populations infectées par des souches incompatibles peut se maintenir de façon stable. / Wolbachia are maternally inherited endocellular α-Proteobacteria that manipulate the reproduction of Arthropods to promote their own transmission. In the mosquito Culex pipiens, Wolbachia induce cytoplasmic incompatibility (CI) which results in high embryonic mortality in crosses between mosquitoes infected with incompatible Wolbachia strains. This mosquito is characterized by high genetic diversity of its Wolbachia (referred as wPip strains) and by complex CI patterns. We examined mechanisms that shape the dynamics of this symbiotic association at genomic, phenotypic and field population levels to understand how it evolves. We showed that wPip strains have a unique and recent evolutionary origin and that their diversity clusters into distinct genetic groups with a geographic structure. We revealed the existence of extensive recombinations among wPip strains, which could influence their adaptive dynamics by creating new wPip strains and thus allow the rapid emergence of new CI patterns. The analysis of crossing relationships between mosquito lines from different geographic origins and infected with wPip strains belonging to different genetic groups showed that CIs (i) evolve rapidly in Cx. pipiens; (ii) are controlled by several genetic factors, and (iii) there is a significant relationship between CI patterns and genetic divergence of wPip strains. In field populations, it appears that CIs are selected against within a population but a contact zone between populations infected by incompatible Wolbachia strains can be stably maintained.

Dans cette thèse, nous abordons deux problèmes de théorie des graphes liés à deux problèmes biologiques de symbiose (deux organismes vivent en symbiose s'ils ont une interaction étroite et à long terme). Le premier problème est lié au phénomène de l'Incompatibilité cytoplasmique (IC) induit par certaines bactéries parasites chez leurs hôtes. L'IC se traduit par l'impossibilité de donner naissance à une progéniture saine lorsqu'un mâle infecté s'accouple avec une femelle non infectée. En termes de graphe ce problème peut s'interpréter comme la recherche d'une couverture minimum par des "sous-graphes des chaînes" d'un graphe biparti. Un graphe des chaînes est un graphe biparti dont les noeuds peuvent être ordonnés selon leur voisinage.En terme biologique, la taille minimale représente le nombre de facteurs génétiques impliqués dans le phénomène de l'IC. Dans la première moitié de la thèse, nous abordons trois problèmes connexes à ce modèle de la théorie des graphes. Le premier est l'énumération de tous les graphes des chaînes maximaux arêtes induits d'un graphe biparti G, pour lequel nous fournissons un algorithme en delai polynomial avec un retard de O(n^2m) où n est le nombre de noeuds et m le nombre d'arêtes de G. Dans la même section, nous montrons que (n/2)! et 2^(\sqrt{m}\log m) bornent le nombre de sous-graphes de chaînes maximales de G et nous les utilisons pour établir la complexité "input-sensitive" de notre algorithme. Le deuxième problème que nous traitons est de trouver le nombre minimum de graphes des chaînes nécessaires pour couvrir tous les bords d'un graphe biparti.Pour résoudre ce problème NP-hard, en combinant notre algorithme avec la technique d'inclusion-exclusion, nous fournissons un algorithme exponentiel exact en O^*((2+c)^m), pour chaque c > 0 (par O^* on entend la notation O standard mais en omettant les facteurs polynomiaux). Le troisième problème est l'énumération de toutes les couvertures minimales par des sous-graphes des chaînes. Nous montrons qu'il est possible d'énumérer toutes les couvertures minimales de G en temps O([(M + 1) |S|] ^ [\ log ((M + 1) |S|)]) où S est le nombre de couvertures minimales de G et M le nombre maximum des sous-graphes des chaînes dans une couverture minimale. Nous présentons ensuite la relation entre le second problème et le calcul de la dimension intervallaire d'un poset biparti. Nous donnons une interprétation de nos résultats dans le contexte de la dimension d'ordre / In this thesis, we address two graph theoretical problems connected to two different biological problems both related to symbiosis (two organisms live in symbiosis if they have a close and long term interaction). The first problem is related to the size of a minimum cover by "chain subgraphs" of a bipartite graph. A chain graph is a bipartite graph whose nodes can be ordered by neighbourhood inclusion. In biological terms, the size of a minimum cover by chain subgraphs represents the number of genetic factors involved in the phenomenon of Cytoplasmic Incompatibility (CI) induced by some parasitic bacteria in their insect hosts. CI results in the impossibility to give birth to an healthy offspring when an infected male mates with an uninfected female. In the first half of the thesis we address three related problems. One is the enumeration of all the maximal edge induced chain subgraphs of a bipartite graph G, for which we provide a polynomial delay algorithm with a delay of O(n^2m) where n is the number of nodes and m the number of edges of G. Furthermore, we show that (n/2)! and 2^(\sqrt{m} \log m) bound the number of maximal chain subgraphs of G and use them to establish the input-sensitive complexity of the algorithm. The second problem we treat is finding the minimum number of chain subgraphs needed to cover all the edges of a bipartite graph. To solve this NP-hard problem, we provide an exact exponential algorithm which runs in time O^*((2+c)^m), for every c>0, by a procedure which uses our algorithm and an inclusion-exclusion technique (by O^* we denote standard big O notation but omitting polynomial factors). Notice that, since a cover by chain subgraphs is a family of subsets of edges, the existence of an algorithm whose complexity is close to 2^m is not obvious. Indeed, the basic search space would have size 2^(2^m), which corresponds to all families of subsets of edges of a graph on $m$ edges. The third problem is the enumeration of all minimal covers by chain sugbgraphs. We show that it is possible to enumerate all such minimal covers of G in time O([(M+1)|S|]^[\log((M+1)|S|)]) where S is the number of minimal covers of G and M the maximum number of chain graphs in a minimal cover. We then present the relation between the second problem and the computation of the interval order dimension of a bipartite poset. We give an interpretation of our results in the context of poset and interval poset dimension... [etc]

Die intrazellulären Parasiten der Bakteriengattung Wolbachia sind weit verbreitet im Phylum der Arthropoden. In vielen Wirten lösen sie eine Paarungsinkompatibilität zwischen nicht infizierten Weibchen und infizierten Männchen aus. Die mögliche Rolle dieser zytoplasmatischen Inkompatibilität in Artbildungsprozessen der Wirtsorganismen wird seit langer Zeit diskutiert. In dieser Arbeit analysieren wir häufig angeführte Kritikpunkte einer solchen Rolle mit Hilfe von mathematischen Modellen, in denen Infektionsdynamik von Wolbachia und Populationsgenetik der Wirte kombiniert werden. Die einzelnen Teile befassen sich mit dem Folgenden: (i) Wir untersuchen die Stabilität von Infektionsmustern in Wirts-Metapopulationen, indem wir kritische Migrationsraten herleiten. (ii) Zur Abschätzung des Einflusses der zytoplasmatischen Inkompatibilität auf den Genfluss zwischen Populationen berechnen wir effektive Migrationsraten. (iii) Wir bestimmen die Bedingungen, die die Verstärkung von Reproduktionsbarrieren durch die Evolution von weiblichen Paarungspräferenzen begünstigen. Schließlich (iv) wenden wir unsere Modelle auf einen realen Artbildungsprozess zweier Drosophila-Arten in Nordamerika an, diskutieren auftretende Probleme und unterbreiten Vorschläge für weiterführende Forschung. Zusammenfassend implizieren unsere Ergebnisse, dass Wolbachien häufig mit der Entstehung neuer Wirtsarten verknüpft sein können, allerdings in den meisten Fällen nur, indem sie als einer von mehreren Faktoren zur reproduktiven Isolation beitragen. Eine Verstärkung sexueller Isolation wird nur unter speziellen Bedingungen bewirkt. / The intracellular bacterial parasites of the genus Wolbachia are widespread among arthropod species. In many hosts, they induce a reproductive incompatibility between uninfected females and infected males. The potential role of this cytoplasmic incompatibility in speciation processes of the bacteria''s hosts has long been debated. In this thesis, we analyze common criticisms of such a role by means of mathematical models, combining Wolbachia infection dynamics and host population genetics. In particular, we are concerned with the following: (i) In order to measure the stability of infection patterns within host metapopulations, we derive critical migration rates. (ii) We evaluate the impact of cytoplasmic incompatibility on gene flow between populations by calculating effective migration rates. (iii) We determine the conditions that favor the evolution of female mating preferences through reinforcement. Finally, (iv) we apply our models to a particular real-world speciation process of two sibling Drosophila species in North America, discuss emerging problems, and suggest future directions of research. In summary, our results implicate that Wolbachia might be a frequent factor in host speciation, but usually only by contributing to overall reproductive isolation among other factors. Reinforcement of premating isolation is selected for only under stringent conditions.