Les génomes peuvent être vus de manière simplifiée comme des suites de gènes, objets codants pour la production de protéines. De la même manière que les caractères physiques des êtres vivants évoluent au cours du temps, les caractères physiques des génomes évoluent également. Il s'agit alors de comprendre cette évolution à travers l'organisation des gènes sur le génome. Le problème peut être abordé sous un angle dynamique où l'on retrace les événements ayant permis les modifications, ou sous un angle statique en observant la localisation et le regroupement des gènes. D'autres part, les gènes nécessitent pour s'exprimer - se transformer en protéine - d'être d'abord transcrits en ARN. Le mécanisme de contrôle de la transcription fait appel, entre autres, à des protéines qui viennent se fixer en amont du gène, sur l'ADN, en reconnaissant de courts motifs. Une tâche récurrente, précédant toute autre analyse, est de trouver les occurrences de ces motifs qui ont la particularité d'être courts et particulièrement dégénérés. Nous retraçons le travail réalisé autour de ces deux problématiques biologiques : l'évolution de la structure des génomes et la localisation des motifs de fixation. Les méthodes mises en œuvre relèvent de l'algorithmique discrète sur les permutations pour la première partie et sur les mots pour la seconde.

Nous présentons un ensemble de résultats concernant deux types de problèmes biologiques: (1) la comparaison de structures de molécules d'ARN et (2) le calcul de distances intergénomiques en présence de gènes dupliqués. Dans ce manuscrit, nous déterminons la complexité algorithmique de certains problèmes liés soit à la comparaison de structures de molécules d'ARN (distance d'édition, problème APS, recherche de motifs de 2-intervalles, design d'ARN), soit aux réarrangements génomiques (distances de breakpoints et d'intervalles conservés). \\ L'approche adoptée pour l'ensemble de ces problèmes a été de déterminer, si possible, des algorithmes exacts et rapides répondants aux problèmes posés. Pour tout problème pour lequel cela ne semblait pas possible, nous avons essayé de prouver qu'il ne peut être résolu de fa\ccon rapide. Pour ce faire, nous démontrons que le problème en question est algorithmiquement difficile. Enfin, le cas échéant, nous poursuivons l'étude de ce problème en proposant, essentiellement, trois types de résultats: (1) Approximation, (2) Complexité paramétrée, (3) Heuristique. Nous utilisons, dans ce manuscrit, des notions d'optimisation combinatoire, de mathématique, de théorie des graphes et d'algorithmique.

Comme tous les ciliés, P. tetraurelia réarrange son génome à chaque génération sexuelle pendant le développement de son macronoyau somatique ¿ partir du micronoyau germinal. Les réarrangements incluent l’excision précise de courtes séquences dérivant de transposons et appelés IES (Internal Eliminated Sequences) dont la majorité sont intragéniques. L’excision d’une fraction d’entre elles dépend de petits ARN maternels (appelés scnARN) qui sont produits à partir de tout le génome germinal pendant la méiose. Ce mécanisme pose un problème lors d’une conjugaison entre deux souches présentant des polymorphismes d’insertion : une cellule sera théoriquement incapable d’exciser une IES portée par l’allèle paternel reçu si cette IES est absente de l’allèle maternel ou si la séquence est trop divergente. Mes résultats montrent cependant que les allèles paternels divergents sont correctement excisés en utilisant les scnARN produit par la cellule paternelle. Dans le cas d’un polymorphisme absence/présence, l’IES que j’ai étudié est excisée chez 70 % des hétérozygotes F1, également via les scnARN paternels. Nous avons exploré deux hypothèses pour expliquer comment ils pouvaient agir. Il pourrait s’agir d’une programmation précoce des noyaux gamétiques ou alors d’un échange cytoplasmique des scnARN. Finalement, j’ai montré qu’un défaut de scnARN maternels n’est pas une cause possible de dysgénésie hybride. Cependant, 30 % des hétérozygotes F1 présentent une rétention variable de l’IES étudié via un mécanisme inconnu. Si cela est généralisable à toutes les IES homozygotes, alors ce mécanisme aurait un effet délétère sérieux sur les F1 et pourrait contribuer à l’isolement reproductif. / Like all ciliates, P. tetraurelia entirely rearranges its genome during development of the somatic macronucleus from the germline micronucleus, in each sexual generation. Rearrangements include the precise excision of IESs (Internal Eliminated Sequences), single-copy intervening sequences likely derived from transposon insertions. At least for a fraction of IESs, correct excision, which is required to reconstitute functional genes in the macronucleus, is thought to depend on their recognition by Piwi-bound small RNAs (called scnRNAs) produced from the maternal germline genome during meiosis. This raises a problem during conjugation between strains presenting insertion polymorphisms: a cell will be theoretically unable to excise an IES from the incoming (paternal) allele if that IES is absent from the maternal allele, or if its sequence is too divergent. Our results, however, indicate that divergent paternal alleles are correctly rearranged, using scnRNAs produced by the paternal cell. In the case of an absence/presence polymorphism, the IES we studied is excised in 70% of heterozygotes, also using paternal scnRNAs. We explored two hypotheses to explain how they can act. It could be either an early programming of the gametic nuclei or through cytoplasmic exchange of scnRNAs. My results seem to favor the latter. Overall, I showed that the lack of maternal scnRNAs is not a possible cause of hybrid dysgenesis. However, 30% of heterozygous F1 display a variable retention of the IES through an unknown mechanism. If this is true for all hemizygous IESs then it will have a strong deleterious effect on hybrid F1s and may contribute to reproductive isolation.

Durant leur évolution, les génomes accumulent des mutations pouvant affecter d’un nucléotide à plusieurs gènes. Les modifications au niveau du nombre et de l’organisation des gènes dans les génomes sont dues à des mutations globales, telles que les duplications, les pertes et les réarrangements. En comparant les ordres de gènes des génomes, il est possible d’inférer les événements évolutifs les plus fréquents, le contenu en gènes des espèces ancestrales ainsi que les histoires évolutives ayant menées aux ordres observés. Dans cette thèse, nous nous intéressons au développement de nouvelles méthodes algorithmiques, par approche d’alignement, afin d’analyser ces différents aspects de l’évolution des génomes. Nous nous intéressons à la comparaison de deux ou d’un ensemble de génomes reliés par une phylogénie, en tenant compte des mutations globales. Pour commencer, nous étudions la complexité théorique de plusieurs variantes du problème de l’alignement de deux ordres de gènes par duplications et pertes, ainsi que de l’approximabilité de ces problèmes. Nous rappelons ensuite les algorithmes exacts, en temps exponentiel, existants, et développons des heuristiques efficaces. Nous proposons, dans un premier temps, DLAlign, une heuristique quadratique pour le problème d’alignement de deux ordres de gènes par duplications et pertes. Ensuite, nous présentons, OrthoAlign, une extension de DLAlign, qui considère, en plus des duplications et pertes, les réarrangements et les substitutions. Nous abordons également le problème de l’alignement phylogénétique de génomes. Pour commencer, l’heuristique OrthoAlign est adaptée afin de permettre l’inférence de génomes ancestraux au noeuds internes d’un arbre phylogénétique. Nous proposons enfin, MultiOrthoAlign, une heuristique plus robuste, basée sur la médiane, pour l’inférence de génomes ancestraux et d’histoires évolutives d’un ensemble de génomes représentés aux feuilles d’un arbre phylogénétique. / During the evolution process, genomes accumulate mutations that may affect the genome at different levels, ranging from one base to the overall gene content. Global mutations affecting gene content and organization are mainly duplications, losses and rearrangements. By comparing gene orders, it is possible to infer the most frequent events, the gene content in the ancestral genomes and the evolutionary histories of the observed gene orders. In this thesis, we are interested in developing new algorithmic methods based on an alignment approach for comparing two or a set of genomes represented as gene orders and related through a phylogenetic tree, based on global mutations. We study the theoretical complexity and the approximability of different variants of the two gene orders alignment problem by duplications and losses. Then, we present the existing exact exponential time algorithms, and develop efficient heuristics for these problems. First, we developed DLAlign, a quadratic time heuristic for the two gene orders alignment problem by duplications and losses. Then, we developed OrthoAlign, a generalization of DLAlign, accounting for most genome-wide evolutionary events such as duplications, losses, rearrangements and substitutions. We also study the phylogenetic alignment problem. First, we adapt our heuristic OrthoAlign in order to infer ancestral genomes at the internal nodes of a given phylogenetic tree. Finally, we developed MultiOrthoAlign, a more robust heuristic, based on the median problem, for the inference of ancestral genomes and evolutionary histories of extent genomes labeling leaves of a phylogenetic tree.

No description available.

Les champignons mycorhiziens à arbuscules (CMA) sont des organismes microscopiques du sol qui jouent un rôle crucial dans les écosystèmes naturels et que l’on retrouve dans tous les habitats de la planète. Ils vivent en relation symbiotique avec la vaste majorité des plantes terrestres. Ils sont des biotrophes obligatoires, c'est-à-dire qu'ils ne peuvent croître qu'en présence d'une plante hôte. Cette symbiose permet entre autres à la plante d'acquérir des nutriments supplémentaires, en particulier du phosphore et du nitrate. Malgré le fait que cette symbiose apporte des services importants aux écosystèmes, la richesse des espèces, la structure des communautés, ainsi que la diversité fonctionnelle des CMA sont mal connues et l'approfondissement des connaissances dans ces domaines dépend d’outils de diagnostic moléculaire. Cependant, la présence de polymorphisme nucléaire intra-isolat combiné à un manque de données génomiques dans différents groupes phylogénétique de ces champignons complique le développement de marqueurs moléculaires et la détermination de l'affiliation évolutive à hauts niveaux de résolution (c.a.d. entre espèces génétiquement similaires et/ou isolats de la même espèce). . Pour ces raisons, il semble une bonne alternative d’utiliser un système génétique différent en ciblant le génome mitochondrial, qui a été démontré homogène au sein d'un même isolat de CMA. Cependant, étant donné le mode de vie particulier de ces organismes, une meilleure compréhension des processus évolutifs mitochondriaux est nécessaire afin de valoriser l'utilisation de tels marqueurs dans des études de diversité et en génétique des populations. En ce sens, mon projet de doctorat consistait à investiguerétudier: i) les vecteurs de divergences inter-isolats et -espèces génétiquement rapprochéesphylogénétiquement apparentées, ii) la plasticité des génomes mitochondriaux, iii) l'héritabilité mitochondriale et les mécanismes potentiels de ségrégation, ainsi que iv) la diversité mitochondriale intra-isolat in situ. À l'aide de la génomique mitochondriale comparative, en utilisant le séquençage nouvelle génération, on a démontré la présence de variation génétique substantielle inter-isolats et -espèces, engendrées par l'invasion d'éléments mobiles dans les génomes mitochondriaux des CMA, donnant lieu à une évolution moléculaire rapide des régions intergéniques. Cette variation permettait de développer des marqueurs spécifiques à des isolats de la même espèce. Ensuite, à l'aide d'une approche analytique par réseaux de gènes sur des éléments mobiles, on a été en mesure de démontrer des évènements de recombinaisons homologues entre des haplotypes mitochondriaux distincts, menant à des réarrangements génomiques. Cela a permis d'ouvrir les perspectives sur la dynamique mitochondriale et l'hétéroplasmie dans un même isolatsuggère une coexistence de différents haplotypes mitochondriaux dans les populations naturelles et que les cultures monosporales pourraient induirent une sous-estimation de la diversité allélique mitochondriale. Cette apparente contradiction avec l'homogénéité mitochondriale intra-isolat généralement observée, a amené à investiguer étudier les échanges génétiques à l'aide de croisements d'isolats génétiquement distincts. Malgré l'observation de quelques spores filles hétéroplasmiques, l'homoplasmie était le statut par défaut dans toutes les cultures monosporales, avec un biais en faveur de l'un des haplotypes parentaux. Ces résultats suggèrent que la ségrégation opère durant la formation de la spore et/ou le développement de la coloniedu mycélium. De plus, ils supportent la présence d'une machinerie protéique de ségrégation mitochondriale chez les CMAAMF, où l'ensemble des gènes impliqués dans ce mécanisme ont été retrouvé et sont orthologues aux autres champignons. Finalement, on est revenue aux sources avecon a étudié le polymorphisme mitochondrial intra-isolat à l'aide d'une approche conventionnelle de PCR en utilisant une Taq polymérase de haute fidélité, suivie de clonage et de séquençage Sanger, sur deux isolats de R. irregularis. Cela a permis l'observation d'hétéroplasmie in situ, ainsi que la co-expression de variantes de variantes de protéines'ARNm dans une souche in vitro. Les résultats suggèrent que d'autres études basées sur le séquençage nouvelle génération aurait potentiellement ignorée cette variation, offrant ainsi plusieurs nouveaux arguments permettant de considérer les CMA comme des organismes possédant une population de génomes mitochondriaux et nucléaires distincts. / The association between arbuscular mycorrhizal fungi (AMF) and plant roots is one of the most widespread symbioses involving plants, and thus has an important role in terrestrial ecosystems. In exchange for carbohydrates, AMF improve plant fitness by enhancing mineral nutrient uptake, especially in particular phosphate and nitrate. Although this symbiosisDespite the fact that these symbioses contribute provides to important services toin ecosystems, the species richness, community structure and functional diversity of AMF is not well understood due to a lack of reliable molecular tools. The intra-isolate genetic polymorphism of nuclear DNA observed in AMF, combined with a lack of genomic data in a broad range of phylogenetic groups, has made it difficult to develop molecular markers and to determine evolutionary relatedness at high levels of resolution (i.e. between genetically-similar species and/or isolates). For these reasons, it seems a good alternative to use a different genetic system by targeting the mitochondrial genome, which have been shown to be homogeneous within AMF isolates. However, given the peculiar lifestyle of these organisms, a better understanding of the mitochondrial evolutionary processes and dynamics were is necessary in order to validate the usefulness of such markers in diversity and population genetics studies. In that regard, the objectives of my PhD project were to investigate: i) the divergence between closely related species and isolates, ii) mitochondrial genomes plasticity, iii) mitochondrial heritability and potential segregation mechanisms and iv) in situ mitochondrial intra-isolate allelic diversity. With Using comparative mitochondrial genomics using and next generation sequencing (NGS) sequencing, we found substantial sequence variation in intergenic regions caused by the invasion of mobile genetic elements. This variation gives risecontributes to rapid mitochondrial genome evolution among closely related isolates and species, which makes it possible to design reliable intra- and inter-specific markers. Also, an extensive gene similarity network-based approach allowed us to provide strong evidence of inter-haplotype recombination in AMF, leading to a reshuffled mitochondrial genome. These findings suggest the coexistence of distinct mtDNA haplotypes in natural populations and raise questions as to whether AMF single spore cultivations artificially underestimates mitochondrial genetic diversity in natural population.. This apparent contradiction with the intra-isolate mtDNA homogeneity usually observed in these fungi, led to the investigation of mitochondrial heritability in the spore progeny resulting from crossed-cultures. Although an heteroplasmic state was observed in some daughter spores, we found that homoplasmy was the dominant state in all monosporal cultures, with an apparent bias towards one of the parental haplotypes. These results strongly support the presence of a putative mitochondrial segregation proteic machinery in AMF, whose complete set of genes were orthologous with those found in other fungi. Our findings suggest that segregation takes place either during spore formation or colony mycelium development. Finally, we performed a conventional PCR based approach with a high fidelity Taq polymerase, followed by downstream cloning and Sanger sequencing using the model organism Rhizophagus irregularis. We found in situ heteroplasmy along with substantial intra-isolate allelic variation within the mtDNA that persists in the transcriptome. Our study also suggest that genetic variation in Glomeromycota is higher than meets the eye and might be critically underestimated in most NGS based-AMF studies both in nuclei and mitochondria.