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]
| Identifer | oai:union.ndltd.org:theses.fr/2018LYSE1019 |
| Date | 16 February 2018 |
| Creators | Gastaldello, Mattia |
| Contributors | Lyon, Università degli studi La Sapienza (Rome), Sagot, Marie-France, Calamoneri, Tiziana |
| Source Sets | Dépôt national des thèses électroniques françaises |
| Language | English |
| Detected Language | French |
| Type | Electronic Thesis or Dissertation, Text |
Page generated in 0.002 seconds