La duplication est un des évènements évolutifs les plus importants, car elle peut mener à la création de nouvelles fonctions géniques. Durant leur évolution, les génomes sont aussi affectés par des inversions, des translocations (incluant des fusions et fissions de chromosomes), des transpositions et des délétions. L'étude de l'évolution des génomes est importante, notamment pour mieux comprendre les mécanismes biologiques impliqués, les types d'évènements qui sont les plus fréquents et quels étaient les contenus en gènes des espèces ancestrales. Afin d'analyser ces différents aspects de l'évolution des génomes, des algorithmes efficaces doivent être créés pour inférer des génomes ancestraux, des histoires évolutives, des relations d'homologies et pour calculer les distances entre les génomes. Dans cette thèse, quatre projets reliés à l'étude et à l'analyse de l'évolution des génomes sont présentés : 1) Nous proposons deux algorithmes pour résoudre des problèmes reliés à la duplication de génome entier : un qui généralise le problème du genome halving aux pertes de gènes et un qui permet de calculer la double distance avec pertes. 2) Nous présentons une nouvelle méthode pour l'inférence d'histoires évolutives de groupes de gènes orthologues répétés en tandem. 3) Nous proposons une nouvelle approche basée sur la théorie des graphes pour inférer des gènes in-paralogues qui considère simultanément l'information provenant de différentes espèces afin de faire de meilleures prédictions. 4) Nous présentons une étude de l'histoire évolutive des gènes d'ARN de transfert chez 50 souches de Bacillus. / Gene duplication is one of the most important types of events affecting genomes during their evolution because it can create novel gene function. During the evolution process, genomes are also affected by inversions, translocations (including chromosome fusions and fissions), transpositions and deletions. Studying the evolution of genomes is important to get a better understanding of the biological mechanisms involved, which types of events are more frequent than others and what was the gene content in the ancestral species just to name a few. In order to analyze these different aspects of genome evolution, efficient algorithms need to be developed to infer ancestral genomes, evolutionary histories, homology relationships between genes and to compute distances between genomes. In this thesis, four different projects related to the study and analysis of genome evolution are presented: 1) We developed two algorithms to solve problems related to whole genome duplication: one that generalizes the genome halving problem to gene losses, and one that allows to compute the double distance with losses. 2) We developed a new method to infer evolutionary histories of orthologous tandemly arrayed gene clusters. 3) We proposed a new graph-theoretic approach to infer inparalogs that simultaneously considers the information given by multiple species in order to make better inferences of inparalogous gene pairs. 4) We studied the evolutionary history of the tRNA genes of 50 Bacillus strains.

Les gènes, qui servent à encoder les fonctions biologiques des êtres vivants, forment l'unité moléculaire de base de l'hérédité. Afin d'expliquer la diversité des espèces que l'on peut observer aujourd'hui, il est essentiel de comprendre comment les gènes évoluent. Pour ce faire, on doit recréer le passé en inférant leur phylogénie, c'est-à-dire un arbre de gènes qui représente les liens de parenté des régions codantes des vivants. Les méthodes classiques d'inférence phylogénétique ont été élaborées principalement pour construire des arbres d'espèces et ne se basent que sur les séquences d'ADN. Les gènes sont toutefois riches en information, et on commence à peine à voir apparaître des méthodes de reconstruction qui utilisent leurs propriétés spécifiques. Notamment, l'histoire d'une famille de gènes en terme de duplications et de pertes, obtenue par la réconciliation d'un arbre de gènes avec un arbre d'espèces, peut nous permettre de détecter des faiblesses au sein d'un arbre et de l'améliorer. Dans cette thèse, la réconciliation est appliquée à la construction et la correction d'arbres de gènes sous trois angles différents: 1) Nous abordons la problématique de résoudre un arbre de gènes non-binaire. En particulier, nous présentons un algorithme en temps linéaire qui résout une polytomie en se basant sur la réconciliation. 2) Nous proposons une nouvelle approche de correction d'arbres de gènes par les relations d'orthologie et paralogie. Des algorithmes en temps polynomial sont présentés pour les problèmes suivants: corriger un arbre de gènes afin qu'il contienne un ensemble d'orthologues donné, et valider un ensemble de relations partielles d'orthologie et paralogie. 3) Nous montrons comment la réconciliation peut servir à "combiner'' plusieurs arbres de gènes. Plus précisément, nous étudions le problème de choisir un superarbre de gènes selon son coût de réconciliation. / Genes encode the biological functions of all living organisms and are the basic molecular units of heredity. In order to explain the diversity of species that can be observed today, it is essential to understand how genes evolve. To do this, the past has to be recreated by inferring their phylogeny, i.e. a gene tree depicting the parental relationships between the coding regions of living beings. Traditional phylogenetic inference methods have been developed primarily to construct species trees and are solely based on DNA sequences. Genes, however, are rich in information and only a few known reconstruction methods make usage of their specific properties. In particular, the history of a gene family in terms of duplications and losses, obtained by the reconciliation of a gene tree with a tree species, may allow us to detect weaknesses in a tree and improve it. In this thesis, reconciliation is applied to the construction and correction of gene trees from three different angles: 1) We address the problem of resolving a non-binary gene tree. In particular, we present a linear time algorithm that solves a polytomy based on reconciliation. 2) We propose a new gene tree correction approach based on orthology and paralogy relations. Polynomial-time algorithms are presented for the following problems: modify a gene tree so that it contains a given set of orthologous genes, and validate a set of partial orthology and paralogy relations. 3) We show how reconciliation can be used to "combine'' multiple gene trees. Specifically, we study the problem of choosing a gene supertree based on its reconciliation cost.

Cette thèse réalise une étude ludo-politique du glitche vidéoludique (bogue, erreur logicielle, faille de design, échec du système, etc.). Elle problématise l’expérience du glitche comme un point d’inflexion entre deux postures d’engagement. Premièrement, une contrejouabilité paralogique désignant une attitude anarcho-communiste qui s’approprie le glitche comme artefact pour explorer, rediriger et (re)façonner la matérialité vidéoludique dans une optique subversive, critique et commune. Deuxièmement, une contre-jouabilité innovante consolidant un programme néolibéral qui exploite le glitche comme une marchandise pour renégocier, dominer et recoder le jeu dans le but de sécuriser un gain en capital. La méthodologie de l’archéologie des médias est mobilisée pour décortiquer les tenants et aboutissants de ces deux modes de contre-jouabilité. Une chasse aux glitches effectuée à travers les discours, l’imaginaire collectif, les arts d’avant-garde et différentes sphères techniques retrace les rapports de continuité entre l’objet d’étude et une matrice de concepts, de formes esthétiques, de méthodes créatives et d’articulations rhétoriques. Un cadre théorique pluridisciplinaire focalisé sur les sciences du jeu, l’étude des médias, les sciences de la communication, la théorie de l'art et les études de fans est employé pour discerner la place singulière qu’occupe la poésie bruyante du glitche vidéoludique à l’intérieur de son vaste réseau d’héritages transhistoriques et transmédiatiques. L’aménagement d’un espace théorique de réflexion nommé la Carte ludo-politique du glitche structure l’analyse des implications idéologiques d’un corpus de glitches issu de la culture du jeu de tir à la première personne comprise comme champ culturel frontalement tiraillée entre la paralogie anarcho-communiste et l’innovation néolibérale. Ce tiraillement est exploré à l’aide d’un second modèle nommé le Circuit de l'économie socio-technique du glitche. Cet outil assiste l’exposition d’un tissu économique de pertes et de profits croisés entre les glitcheurs et l’industrie. Deux tendances prédominantes sont étudiées. D’une part, une culture de la marchandise basée sur des logiques compétitives de détournement et d’hameçonnage où la valeur d’échange du glitche est exploitée pour optimiser un rendement économique. D’autre part, une économie du don découlant d’un esprit de coopération et de partage où la valeur d’usage du glitche est cultivée et abritée au service du bien commun et de la diversité des pratiques. La démystification de ces dynamiques révèle des rapports d’exploitation économique ii et d’assujettissement politique reliant le glitche 1) à la transformation matérielle des jeux vidéo, 2) à la force de travail des développeurs de jeux, 3) à la force de jouavail des glitcheurs et 4) à la philosophie socio-économique du néolibéralisme qui règne dans la culture et l’industrie vidéoludique. Les dimensions matérielles, laborieuses et économiques du glitche sont discutées en fonction de leurs effets de politisation ambivalents. Sur le plan de la contre-jouabilité innovante, la notion de glitches de l’Empire est théorisée comme vecteur d’une subjectivité politique conformée aux préceptes du néolibéralisme. Cette attitude s’harmonise avec la privatisation des moyens de production, la propriété privée et intellectuelle, le libre marché, la recherche du profit, la liberté entrepreneuriale de soi, la compétition marchande et la quantification du vivant. Sur le plan de la contre-jouabilité paralogique, le concept de glitches de la multitude est présenté comme cristallisant une sensibilité anarcho-communiste. Cette dernière encourage un éthos de désobéissance qui défend la liberté d’expression et d’association, l’autonomisation des individus et des communautés, la socialisation des moyens de production, la collectivisation des ressources, l’autogestion et de la démocratie/action directe au sein de groupes affinitaires ainsi que la préservation du commun. / This thesis conduct a ludo-political study of videogame glitches (bugs, software errors, design flaws, system failures, etc.). The glitch experience is analyzed as an inflection point between two modes of engagement. First, a paralogical counterplay related to an anarchocommunist ethos that appropriates glitches as artifacts to explore, redirect and (re)shape videogame materiality in a subversive, critical, and communal manner. Second, an innovative counterplay consolidating a neoliberal agenda that exploits glitches as commodities to renegotiate, dominate and recode the game to secure capital gains. Media archeology is mobilized as a methodology to dissect the ins and outs of these two modes of counterplay. An academic form of glitch hunting through discourse, collective imaginary, avant-garde arts and various technical fields has been carried out to retrace the continuity between the object of study and a shared matrix of concepts, aesthetic forms, creative techniques and rhetorical articulations. A multidisciplinary theoretical framework built from game studies, media studies, communication studies, art theory and fan studies is used to determine the unique place of videogame glitches’ noisy poetry within its vast network of transhistoric and transmedia heritages. The development of a theoretical model named the Glitch Ludo-Political Map frames the analysis of the ideological implications of a body of glitches from the first-person shooter gaming culture understood as a cultural field in tension between the anarcho-communist paralogy and neoliberal innovation. This polarization is explored using a second model called the Circuit of the Glitch Socio-Technical Economy. This tool is used to expose a complex interplay of economic losses and gains between glitchers and the industry. Two predominant trends are studied. On the one hand, a culture of commodity based on a hijacking and harnessing competitive logic where the exchange value of glitches is exploited to optimize economic incomes. On the other hand, a gift economy resulting from a spirit of cooperation, sharing, and gratuitousness in which the use value of glitches is harvested and harboured in the service of the common good and the diversity of practices. The investigation of these dynamics reveals relationships of economic exploitation and political subjugation that link glitches to 1) the material transformation of videogames, 2) the labour force of game developers, 3) the playbour iv force of glitchers, and 4) the neoliberal socio-economic philosophy that shapes gaming culture and industry. The material, labour, and economic dimensions of glitches are discussed according to their ambivalent political effects. In terms of innovative counterplay, the notion of glitches of Empire is theorized as a vector of a political subjectivity consistent with the precepts of neoliberalism. This attitude is aligned with the privatization of the means of production, private and intellectual property, free market, search for profit, entrepreneurial freedom of the self, aggressive competition and quantification of life itself. In terms of paralogical counterplay, the concept of glitches of multitude is presented as crystallizing an anarcho-communist political sensibility. This political stance catalyzes an ethos of disobedience fostering freedom of speech and association, empowerment of individuals and communities, socialization of the means of production, collectivization of wealth, self-management and direct democracy/action within affinity groups, and the protection of the common good.