Orthology and paralogy distinguish whether a pair of genes originated by a speciation or a gene duplication event, whereas xenology refers to horizontal gene transfer. These concepts play a key role in phylogenomics and species tree inference is one of its prevalent tasks. Commonly, species tree inference is performed using sequence-based phylogenetic methods which heavily rely on the initial data sets to be solely composed of 1:1 orthologs. Such approaches are strongly restricted to a small set of genes that provide information about the species tree. In this work, it is shown that the restriction to 1:1 orthologs is not necessary to reconstruct a reliable hypothesis on the evolutionary history of species. Besides orthology, knowledge on all three major driving forces of gene evolution can be considered: speciation, gene duplication, and horizontal gene transfer. The corresponding concepts of orthology, paralogy, and xenology imply binary relations on pairs of genes. These relations, in turn, convey meaningful phylogenetic information and allow the inference of plausible phylogenetic species trees. To this end, it is shown that orthology, paralogy, and xenology have to fulfill certain mathematical properties. In particular, they have to be representable as a tree – the so-called gene tree. This work investigates the theoretical concepts of tree representable sets of binary relations to unfold the underlying mathematical structure. Various novel characterizations for those relations are given and the close connection between tree representable sets of binary relations and cographs, symbolic ultrametrics, and so-called unp 2-structures is revealed. Based on the novel characterizations, polynomial-time recognition algorithms for tree representable sets of relations are presented. In the case, a set of relations is tree representable, the corresponding tree representation can be found in polynomial time as well. Moreover, for the NP-complete problems of editing a given set of relations to its closest tree representable set, exact algorithms are developed by means of formulations as integer linear program. Finally, all algorithms have been implemented in the software ParaPhylo, a species tree inference method based on orthology and paralogy data. It is demonstrated on simulated data sets, as well as real-life data sets, that non-trivial phylogenies can indeed be reconstructed from tree-free orthology estimates alone.

Phenotypes and diseases may be related by seemingly dissimilar phenotypes in other species by means of the orthology of underlying genes. Such "orthologous phenotypes," or "phenologs," are examples of deep homology, and one member of the orthology relationship may be used to predict candidate genes for its counterpart. (There exists evidence of "paralogous phenotypes" as well, but validation is non-trivial.) In Chapter 2, I demonstrate the utility of including plant phenotypes in our database, and provide as an example the prediction of mammalian neural crest defects from an Arabidopsis thaliana phenotype, negative gravitropism defective. In the third chapter, I describe the incorporation of additional phenotypes into our database (including chicken, zebrafish, E. coli, and new C. elegans datasets). I present a method, developed in coordination with Martin Singh-Blom, for ranking predicted candidate genes by way of a k nearest neighbors naïve Bayes classifier drawing phenolog information from a variety of species. The fourth chapter relates to a computational method and application for identifying shared and overlapping pathways which contribute to phenotypes. I describe a method for rapidly querying a database of phenotype--gene associations for Boolean combinations of phenotypes which yields improved predictions. This method offers insight into the divergence of orthologous pathways in evolution. I demonstrate connections between breast cancer and zebrafish methylmercury response (through oxidative stress and apoptosis); human myopathy and plant red light response genes, minus those involved in water deprivation response (via autophagy); and holoprosencephaly and an array of zebrafish phenotypes. In the first appendix, I present the SciRuby Project, which I co-founded in order to bring scientific libraries to the Ruby programming language. I describe the motivation behind SciRuby and my role in its creation. Finally in Appendix B, I discuss the first beta release of NMatrix, a dense and sparse matrix library for the Ruby language, which I developed in part to facilitate and validate rapid phenolog searches. In this work, I describe the concept of phenologs as well as the development of the necessary computational tools for discovering phenotype orthology relationships, for predicting associated genes, and for statistically validating the discovered relationships and predicted associations. / text

Lacking experimental data, protein function is often predicted from evolutionary and protein structure theory. Under the 'domain grammar' hypothesis the function of a protein follows from the domains it encodes. Under the 'orthology conjecture', orthologs, related through species formation, are expected to be more functionally similar than paralogs, which are homologs in the same or different species descended from a gene duplication event. However, these assumptions have not thus far been systematically evaluated. To test the 'domain grammar' hypothesis, we built models for predicting function from the domain combinations present in a protein, and demonstrated that multi-domain combinations imply functions that the individual domains do not. We also developed a novel gene-tree based method for reconstructing the evolutionary histories of domain architectures, to search for cases of architectures that have arisen multiple times in parallel, and found this to be more common than previously reported. To test the 'orthology conjecture', we first benchmarked methods for homology inference under the obfuscating influence of low-complexity regions, in order to improve the InParanoid orthology inference algorithm. InParanoid was then used to test the relative conservation of functionally relevant properties between orthologs and paralogs at various evolutionary distances, including intron positions, domain architectures, and Gene Ontology functional annotations. We found an increased conservation of domain architectures in orthologs relative to paralogs, in support of the 'orthology conjecture' and the 'domain grammar' hypotheses acting in tandem. However, equivalent analysis of Gene Ontology functional conservation yielded spurious results, which may be an artifact of species-specific annotation biases in functional annotation databases. I discuss possible ways of circumventing this bias so the 'orthology conjecture' can be tested more conclusively. / At the time of the doctoral defense, the following paper was unpublished and had a status as follows: Paper 6: Epub ahead of print.

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.

No description available.