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]

Dans les génomes bactériens, les fréquents transferts horizontaux de gènes (HGT) introduisent des innovations génomiques qui peuvent entraîner la diversification des populations bactériennes. À l'inverse, la recombinaison homologue (RH) au sein des populations homogénéise leurs génotypes, et ainsi renforce leur cohésion. Ces processus d'échange génétique, et la fréquence à laquelle ils interviennent au sein et entre les populations, doivent avoir un grand impact sur la cladogénèse bactérienne. Au-delà de la configuration des échanges qui se sont réellement produits entre les bactéries, les traces de RH et de HGT que nous observons dans leurs génomes reflètent les événements qui ont été fixés tout au long de leur histoire. Ce processus de fixation peut être biaisé en ce qui concerne la nature des gènes ou allèles qui ont été introduits. La sélection naturelle peut notamment conduire à la fixation des gènes transférés qui apportent de nouvelles adaptations écologiques. En outre, des biais mécaniques dans le processus de recombinaison lui-même peuvent conduire à la fixation d'allèles non-adaptatifs. Nous avons cherché à caractériser certains de ces processus adaptatifs et non-adaptatifs qui façonnent les génomes bactériens. À cette fin, plusieurs aspects de l'évolution des génomes, comme les variations de leurs répertoires de gènes, de leur architecture et de leur composition en nucléotides ont été examinés à la lumière de leur histoire de transfert et de recombinaison / In bacterial genomes, the frequent horizontal gene transfers (HGT) introduce genomic novelties that can promote the diversification of bacterial populations. In opposition, homologous recombination (HR) within populations homogenizes their genotypes, enforcing their cohesion. These processes of genetic exchange, and their patterns of occurrence among and within lineages, must have a great impact on bacterial cladogenesis. Beyond the pattern of exchanges actually occurring between bacteria, the traces of HR and HGT we observe in their genomes reflect what events were fixed throughout their history. This fixation process can be biased regarding the nature of genes or alleles that were introduced. Notably, natural selection can drive the fixation of transferred genes that bring new ecological adaptations. In addition, some mechanical biases in the recombination process itself may lead to the fixation of non-adaptive alleles. We aimed to characterize such adaptive and non-adaptive processes that are shaping bacterial genomes. To this end, several aspects of genome evolution, such as variations of their gene repertoires, of their architecture and of their nucleotide composition were examined in the light of their history of transfer and recombination