Cette thèse s'inscrit dans le cadre de la bioinformatique. Les outils mathématiques les plus utilisés dans ce travail relèvent de la théorie des graphes, des statistiques, de la théorie des ensembles et des mathématiques discrètes. Ces mathématiques ont permis de développer des modèles de systèmes biologiques ainsi que des algorithmes efficaces dans l'étude concrète de ces modèles. La nécessité d'analyses de jeux de données de très grande taille a rendu critique dans notre démarche cette notion d'efficacité des algorithmes. Il faut enfin remarquer que le champ biologique qui a servi de support à cette thèse nous a conduit à explorer un domaine particulier au sein de la théorie de la complexité, à savoir le développement et l'analyse des algorithmes d'énumération [etc...] / In the results presented in the present manuscripts, graph theory and combinatorial optimizationtecniques, have been used to model and solve biological problems. The manuscript is divided in twoparts, each one containing the mathematical and biological background of a given application and ouroriginal contributions to it.Part I groups a set of results designed for phylogenetics analysis, and in particular for reconstructingthe co-evolution of two groups of organisms (the so called co-phylogeny reconstruction problem).Although the addressed problem was treated in the available there was no method that solved suchproblem in a complete and efficient way. We thus developed and implemented a new one, calledEucalypt, with this purpose in mind. This not only provides a novel and usable software for cophylogenyreconstruction but also allows to investigate how the event-based model performs inpractice in terms of thenumber and quality of the solutions obtained. We compared our method to the available software. Bylooking at the results obtained, some interesting considerations about the advantages anddisadvantages of the commonly accepted mathematical model could be drawn. Finally, we introduceda new version of the problem where the host-switches are distance bounded: the k-bounded-All-MPRproblem. Eucalypt solves both problems in polynomial delay. These results have been accepted forpublication by the jounal Algorithms for Molecular Biology. The relative software is publicyavailable.Our studies show that the 'most parsimonious scenario' approach presents some limitationsthat cannot be ignored. To deal with these problems, we developed a second algorithm, called Coala,based on an approximate Bayesian computation approach for estimating the frequency of the events.The benefits of this method are twofold: it provides more confidence in the set of costs to be used in areconciliation, and it allows to estimate the frequency of the events in the cases where a reconciliationmethod cannot be applied. These results are currently under review by the jounal Systematic Biology.The relative software is publicy available.In Part 2 another set of studies is presented. Our original model for the contig scaffolding problem,and our algorithm MeDuSa, are presented and tested. Unlike traditional software, it does not rely eitheron paired-end information of sequencing reads or on a phylogenetic distance of the microorganismsused in the analysis. This drastically increases the usability of our software and, at the same time,reduces the computational time required for genome scaffolding. We show that the algorithmimplemented in MeDuSa, in most cases, is capable of producing less and longer scaffolds incomparison to commonly used scaffolders, while maintaining high accuracy and correctness of thepredicted joins. These results are currently under revision by the journal Bioinformatics.Finally, during the development of this method we encountered some pure theoretical open problemsand we decided to dedicate part of our job to their analysis. The last chapter is then dedicated to a setof problems, all related to the Implicit Hitting set enumeration problem. After some formal definitions,an original NP-completeness result is presented and the future directions of our work are described

Les pseudosuchiens représentent l'ensemble de la lignée des crocodiliens qui s'est différentiée de celle des dinosaures à partir du Trias inférieur (il y en a environ 250 Ma). A l'origine probablement endothermes et terrestres, les pseudosuchiens sont par la suite devenus ectothermes et certains d'entre eux sont retournés vers un mode de vie semi-aquatique lors de la transition Trias-Jurassique (200 Ma): les néosuchiens (formes encore représentées dans le nature actuelle) et les téléosauridés (disparus depuis le Crétacé). À l'image de certains taxons fossiles comme les " stégocéphales ", les pseudosuchiens présentent une ornementation composée de cupules et de sillons à la surface des os dermiques (toit crânien, mandibules et ostéodermes) qui a la particularité de se former par résorption osseuse au sein de ce groupe. L'étude d'os fossilisés et d'os sec par des techniques d'imagerie 3D combinées à des analyses phylogénétiques basées sur des caractères quantitatifs a montré que les formes amphibies présentent un développement accrue de l'ornementation. Par la suite, nos analyses histologiques à partir de prélèvements sur des crocodiliens vivants ont montré que ces cupules hébergent des bouquets vasculaires qui seraient possiblement impliqués dans les échanges de chaleurs en phase émergée et semi-émergée ainsi que dans le tampon, de l'acidité sanguine pendant les phases émergées (en apnée). Concernant les possible implications biomécaniques de l’ornementation, les analyses en éléments finis que nous avons effectuées à partir d’ostéodermes scannés en 3D ont montré que la présence d’ornementation n’avait pas d’influence ni sur la résistance mécanique des ostéodermes ni sur leur capacité à conduire la chaleur. Par conséquent, le rôle fonctionnel de l’ornementation serait strictement d’ordre physiologique en lien avec la mise en place d’un réseau sanguin péri-osseux qui faciliterait à la fois les transferts de chaleur entre l’organisme et l’environnement en phase d’exposition et le stockage du lactate dans les os dermiques en phase d’apnée. De plus, la mise en place de l’ornementation pourrait permettre le maintien de l’équilibre homéostatique phospho-calcique via la succession de résorption superficielle et de dépôt secondaires en périphérie des os dermiques suivant la trajectoire ontogénétique de chaque individu (phase de ponte, jeun prolongé...). / Pseudosuchia is the crocodylian lineage which split up with the dinosaurs since the Early- Triassic (around 250 million years ago). At first probably endothermic and terrestrial, pseudosuchians became secondarily ectothermic and some of them returned to a semi-aquatic lifestyle at the Triassic-Jurassic transition (200 Ma): the neosuchians (still present in current nature) and the teleosaurids (disappeared since the Cretaceous). Like some extinct vertebrate groups (« the stegocephalians »), the pseudosuchians possess a dermal bone ornamentation made of pits and grooves on the skull roof, the mandibles and the osteoderms but with the particularity to be excavated by resorption. The study of both fossil and dry bones combining 3D-data monitoring and quantitative data-based phylogenetic comparative analyses evidenced that the semi-aquatic forms possess a more excavated bone ornamentation. Further, histological analyses based on living animal sampling have revealed that the ornamentation pits always house a vessel proliferation which may be involved in heat exchanges during emerged and semi-emerged periods as well as acidosis buffering during submerged periods (apnea). Concerning the biomechanical and thermal implications, the finite element analyses performed on 3D-modeled osteoderms have proved that the bone ornamentation does not modify the osteoderm heat conduction nor their mechanical resistance. Consequently, we assess that the functional role of bone ornamentation shall mainly concern physiological implications through the set-up of a blood vessel network on the bone periphery (heat transfers, blood acidosis buffering; as hypothesized by previous authors). Secondarily, bone ornamentation may also be involved in phosphor-calcic homeostasis based on the succession of pit resorption and secondary superficial bone deposit in response to the specimens. life-long changes (eggshelling, diets.).

Chez les eucaryotes, la voie de protéolyse Ub/ protéasome 26S est responsable de la dégradation sélective de la plupart des protéines intracellulaires. Cette dégradation par le protéasome 26S est initiée par une polyubiquitination de la protéine réalisée grâce à l’action d’une cascade enzymatique impliquant 3 types d'enzymes nommées « ubiquitin-activating enzyme » (E1), « ubiquitin-conjugating enzyme » (E2) et « ubiquitin-protein ligase » (E3). Il existe différentes classes d’ubiquitines ligases (E3), parmi lesquelles la plus connue est le complexe SCF (Skp1-Cullin-F-box). La protéine SKP1 fixe à la fois la Culline et la F-box qui va reconnaitre spécifiquement la protéine cible. Contrairement aux protistes, les champignons et certains vertébrés qui possèdent un unique gène SKP1 fonctionnel, de nombreux animaux et espèces de plantes présentent plusieurs SKP1 homologues. Vingt et un et trente deux gènes SKP1 ont été décrits respectivement chez Arabidopsis thaliana et Oryza sativa. En dépit de l’importance du complexe SCF, chez le riz, peu de travaux décrivent les interactions entre les dizaines de protéines « SKP1-like » et les centaines de protéines F-box. Dans un premier temps, nous avons collecté et analysé les séquences de 288 gènes « SKP1-like » appartenant à 17 espèces, dont la mousse Physcomitrella patens, cinq monocotylédones et 11 eudicotylédones. Les analyses structurales et phylogénétiques de ces gènes indiquent qu’ils peuvent être divisés en différentes sous-familles. Nos analyses ont montré qu’OSK1 et OSK20 chez le riz constituent une classe de gènes SKP1 à intron unique conservé. Dans un deuxième temps, nous avons étudié le profil d’expression des gènes « SKP1-like » chez le riz. Notre investigation sur le nombre d’EST a montré que les gènes OSK1 et OSK20 sont les plus largement représentés dans les bases de données EST publiques. La méta-analyse de l’expression des gènes « SKP1-like » chez le riz, indique que les gènes OSK présentent des profils d'expression hétérogènes selon les tissus et les conditions physiologiques. Les résultats des intearctions protéine-protéine en double hybride ont révélé que les protéines OSK présentent différentes capacités d’interactions avec les protéines F-box. Cependant, OSK1 et OSK20 semblent interagir avec la plupart des protéines F-box testées. Les études de localisation subcellulaire ont indiqué que OSK1 et OSK20 sont des protéines nucléaires et cytosoliques. En se basant sur les divers résultats obtenus dans ce travail, nous pouvons suggérer que chez le riz, les gènes OSK1 et OSK20 sont fonctionnellement équivalents aux gènes ASK1 et ASK2 chez Arabidopsis thaliana. Nous pouvons également proposer les équivalents de ces gènes chez les autres espèces végétales dont le génome a été séquencé. / In eukaryotes, the ubiquitin Ub/26S proteasome pathway is responsible for the selective degradation of most intracellular proteins. This cellular process is initiated by protein polyubiquitination mediated by a three-step cascade involving: an ubiquitin-activating enzyme (E1), an ubiquitin-conjugating enzyme (E2) and an ubiquitin-protein ligase (E3). The E3 ubiquitin ligases contain several classes, among which the best-known are Skp1-Cullin-F-box (SCF) complexes. The SKP1 protein binds both Cullin and F-box which recognizes specifically the target proteins. Whereas protists, fungi and some vertebrates have a single functional SKP1 gene, many animal and plant species possess multiple SKP1 homologues. Twenty one and thirty-two SKP1-related genes have been described respectively in the Arabidopsis and Oryza sativa genome. Despite the importance of the SCF complex, there have been a few reports of systematic surveys of interactions between the dozens of SKP1-like proteins and the hundreds of F-box proteins in rice. In a first step, we retrieved and analyzed 288 SKP1-like genes belonging to 17 species including the moss Physcomitrella patens, five monocots and 11 eudicots. Structural and phylogenetic analysis of rice OSK genes and other plant SKP1-like genes have indicated that the different members of the plant SKP1 can be split into different subfamily. Our analyses indicated that OSK1 and OSK20 belong to a class of SKP1 genes that contain one intron at a conserved position. In a second step, we studied expression profiles of the rice Skp1-like genes. Our EST survey indicated that OSK1 and OSK20 are the most widely represented genes in public EST databases. Meta-analysis of the expression of rice SKP1-like genes indicated that OSK genes exhibit an expression profile that was heterogeneous in terms of tissues, conditions and overall intensity. Yeast two-hybrid results revealed that OSK proteins display a differing ability to interact with F-box proteins. However, OSK1 and OSK20 seemed to interact with most F-box proteins tested. Subcellular localization studies indicated that OSK1 and OSK20 are nuclear and cytosolic proteins. Based on the results obtained in this study, we can suggest that rice OSK1 and OSK20 are likely to have similar functions as do the Arabidopsis ASK1 and ASK2 genes. Similarly, we suggest a list of functional equivalent in the other sequenced plant genomes.

Les Truffes sont des champignons ascomycètes ectomycorhiziens appartenant à la famille des Tuberaceae et plus précisément au genre Tuber. On dénombre à ce jour plus d’une trentaine d’espèces de Tuber en Europe. Lors de ce travail de thèse, nous nous sommes plus précisément focalisés sur le modèle Tuber aestivum-uncinatum. Cette truffe communément appelée « Truffe de Bourgogne » présente un intérêt à la fois gastronomique et culturel.La première partie de ce travail de thèse a porté sur la clarification du statut taxonomique de la truffe de Bourgogne (Tuber uncinatum). Pour cela, nous avons utilisé une approche multi-marqueurs combinant des marqueurs génétiques couramment utilisés à l’échelle interspécifique. Nos analyses ont montré que les deux taxons Tuber aestivum (la truffe d’été) et Tuber uncinatum sont conspécifiques. Durant la deuxième partie, nous nous sommes intéressés à la diversité génétique de Tuber aestivum. Pour cela, nous avons tout d’abord développé des marqueurs microsatellites spécifiques par une approche de « direct shotgun pyrosequencing ». Cette méthode a permis le développement de 15 marqueurs microsatellites polymorphes. Nous les avons ensuite utilisés pour génotyper des individus provenant de différentes localisations en Europe. Nous avons pu identifier quatre sous populations différenciées qui ne correspondent pas, pour la majorité, à une répartition géographique. Cependant, un des clusters se différencie des autres à la fois par sa situation géographique (sud de la France) et ses caractéristiques génétiques (présence d’allèles rares). Ces résultats préliminaires pourraient indiquer l’existence d’un écotype particulier attaché à une écologie méridionale, Tuber aestivum sensu stricto.Nous nous sommes ensuite intéressés, dans la troisième partie de ce travail de thèse à la diversité aromatique de Tuber aestivum à l’échelle locale. Les résultats obtenus permettent de mettre en évidence l’existence d’une différenciation modérée entre les individus issus d’une truffière naturelle et les individus issus d’une truffière plantée. D’une saison de récolte à l’autre, une stabilité génotypique a été observée. Au niveau aromatique, seuls les composés C8 semblent être liés aux génotypes.Dans la dernière partie, nous nous sommes intéressés à l’analyse de données de récolte sur plus de trente ans au sein d’une truffière plantée de noisetiers inoculés initialement par Tuber melanosporum. Grâce à des analyses statistiques simples, nous avons pu noter les fluctuations tant en quantité qu’en poids des truffes récoltées suivant les saisons et les arbres truffiers. Il apparait que le remplacement de Tuber melanosporum par Tuber aestivum s’est fait de manière très rapide (trois ans). La disparition de Tuber melanosporum peut probablement être expliquée par la fermeture de la canopée des noisetiers, Tuber melanosporum n’appréciant pas un ombrage excessif / Truffles are ectomycorrhizal Ascomycota fungi belonging to the Tuberaceae family and more specifically to the Tuber genus. More than thirty Tuber species are currently described in Europe. In this thesis, we specifically focused on the Tuber aestivum-uncinatum model. This truffle is commonly called "Burgundy Truffle" and has a gastronomic and cultural interest.The first part of this thesis focused on the taxonomic status of the Burgundy truffle (Tuber uncinatum). For this, we used a multi-marker approach combining several genetic markers commonly used at the interspecific scale. Our analyses showed that the two taxa, Tuber aestivum (summer truffle) and Tuber uncinatum are conspecific.In the second part, we addressed the genetic diversity of Tuber aestivum. To do this, we firstly developed specific microsatellite markers by "direct shotgun pyrosequencing". This method has allowed the development of 15 polymorphic microsatellite markers. Then, we used those markers to genotype individuals from different European locations. We have identified four differentiated subpopulations that not correspond, for the majority, to a geographical distribution. However, one cluster differs from the others by its location (south of France) and its genetic characteristics (presence of rare alleles). These preliminary results may indicate the existence of a particular ecotype attached to a southern ecology: Tuber aestivum sensu stricto.We were then interested, in the third part of this thesis, to the aromatic diversity of Tuber aestivum at a local scale. Our results highlight the existence of a moderate differentiation between individuals from a natural truffle orchard and individuals from planted orchard. From one season to another, genotypic stability was observed. Only C8 volatile organic compounds seem to be related to the genotypes.In the last part, we analyzed harvesting data, over more than thirty years, from an hazelnut truffle orchard initially inoculated by Tuber melanosporum. Through simple statistical analyzes, we noted changes in both quantity and weight of truffles harvested according to the seasons and hazelnut trees. It appears that Tuber aestivum rapidly replaced Tuber melanosporum (in three years). The disappearance of Tuber melanosporum can probably be explained by the canopy closure; Tuber melanosporum not appreciating excessive shading.