The evolution of biological species depends on changes in genes. Among these changes are the gradual accumulation of DNA mutations, insertions and deletions, duplication of genes, movements of genes within and between chromosomes, gene losses and gene transfer. As two populations of the same species evolve independently, they will eventually become reproductively isolated and become two distinct species. The evolutionary history of a set of related species through the repeated occurrence of this speciation process can be represented as a tree-like structure, called a phylogenetic tree or a species tree. Since duplicated genes in a single species also independently accumulate point mutations, insertions and deletions, they drift apart in composition in the same way as genes in two related species. The divergence of all the genes descended from a single gene in an ancestral species can also be represented as a tree, a gene tree that takes into account both speciation and duplication events. In order to reconstruct the evolutionary history from the study of extant species, we use sets of similar genes, with relatively high degree of DNA similarity and usually with some functional resemblance, that appear to have been derived from a common ancestor. The degree of similarity among different instances of the “same gene” in different species can be used to explore their evolutionary history via the reconstruction of gene family histories, namely gene trees. Orthology refers specifically to the relationship between two genes that arose by a speciation event, recent or remote, rather than duplication. Comparing orthologous genes is essential to the correct reconstruction of species trees, so that detecting and identifying orthologous genes is an important problem, and a longstanding challenge, in comparative and evolutionary genomics as well as phylogenetics. A variety of orthology detection methods have been devised in recent years. Although many of these methods are dependent on generating gene and/or species trees, it has been shown that orthology can be estimated at acceptable levels of accuracy without having to infer gene trees and/or reconciling gene trees with species trees. Therefore, there is good reason to look at the connection of trees and orthology from a different angle: How much information about the gene tree, the species tree, and their reconciliation is already contained in the orthology relation among genes? Intriguingly, a solution to the first part of this question has already been given by Boecker and Dress [Boecker and Dress, 1998] in a different context. In particular, they completely characterized certain maps which they called symbolic ultrametrics. Semple and Steel [Semple and Steel, 2003] then presented an algorithm that can be used to reconstruct a phylogenetic tree from any given symbolic ultrametric. In this thesis we investigate a new characterization of orthology relations, based on symbolic ultramterics for recovering the gene tree. According to Fitch’s definition [Fitch, 2000], two genes are (co-)orthologous if their last common ancestor in the gene tree represents a speciation event. On the other hand, when their last common ancestor is a duplication event, the genes are paralogs. The orthology relation on a set of genes is therefore determined by the gene tree and an “event labeling” that identifies each interior vertex of that tree as either a duplication or a speciation event. In the context of analyzing orthology data, the problem of reconciling event-labeled gene trees with a species tree appears as a variant of the reconciliation problem where genes trees have no labels in their internal vertices. When reconciling a gene tree with a species tree, it can be assumed that the species tree is correct or, in the case of a unknown species tree, it can be inferred. Therefore it is crucial to know for a given gene tree whether there even exists a species tree. In this thesis we characterize event-labelled gene trees for which a species tree exists and species trees to which event-labelled gene trees can be mapped. Reconciliation methods are not always the best options for detecting orthology. A fundamental problem is that, aside from multicellular eukaryotes, evolution does not seem to have conformed to the descent-with-modification model that gives rise to tree-like phylogenies. Examples include many cases of prokaryotes and viruses whose evolution involved horizontal gene transfer. To treat the problem of distinguishing orthology and paralogy within a more general framework, graph-based methods have been proposed to detect and differentiate among evolutionary relationships of genes in those organisms. In this work we introduce a measure of orthology that can be used to test graph-based methods and reconciliation methods that detect orthology. Using these results a new algorithm BOTTOM-UP to determine whether a map from the set of vertices of a tree to a set of events is a symbolic ultrametric or not is devised. Additioanlly, a simulation environment designed to generate large gene families with complex duplication histories on which reconstruction algorithms can be tested and software tools can be benchmarked is presented.

The evolution of biological species depends on changes in genes. Among these changes are the gradual accumulation of DNA mutations, insertions and deletions, duplication of genes, movements of genes within and between chromosomes, gene losses and gene transfer. As two populations of the same species evolve independently, they will eventually become reproductively isolated and become two distinct species. The evolutionary history of a set of related species through the repeated occurrence of this speciation process can be represented as a tree-like structure, called a phylogenetic tree or a species tree. Since duplicated genes in a single species also independently accumulate point mutations, insertions and deletions, they drift apart in composition in the same way as genes in two related species. The divergence of all the genes descended from a single gene in an ancestral species can also be represented as a tree, a gene tree that takes into account both speciation and duplication events. In order to reconstruct the evolutionary history from the study of extant species, we use sets of similar genes, with relatively high degree of DNA similarity and usually with some functional resemblance, that appear to have been derived from a common ancestor. The degree of similarity among different instances of the “same gene” in different species can be used to explore their evolutionary history via the reconstruction of gene family histories, namely gene trees. Orthology refers specifically to the relationship between two genes that arose by a speciation event, recent or remote, rather than duplication. Comparing orthologous genes is essential to the correct reconstruction of species trees, so that detecting and identifying orthologous genes is an important problem, and a longstanding challenge, in comparative and evolutionary genomics as well as phylogenetics. A variety of orthology detection methods have been devised in recent years. Although many of these methods are dependent on generating gene and/or species trees, it has been shown that orthology can be estimated at acceptable levels of accuracy without having to infer gene trees and/or reconciling gene trees with species trees. Therefore, there is good reason to look at the connection of trees and orthology from a different angle: How much information about the gene tree, the species tree, and their reconciliation is already contained in the orthology relation among genes? Intriguingly, a solution to the first part of this question has already been given by Boecker and Dress [Boecker and Dress, 1998] in a different context. In particular, they completely characterized certain maps which they called symbolic ultrametrics. Semple and Steel [Semple and Steel, 2003] then presented an algorithm that can be used to reconstruct a phylogenetic tree from any given symbolic ultrametric. In this thesis we investigate a new characterization of orthology relations, based on symbolic ultramterics for recovering the gene tree. According to Fitch’s definition [Fitch, 2000], two genes are (co-)orthologous if their last common ancestor in the gene tree represents a speciation event. On the other hand, when their last common ancestor is a duplication event, the genes are paralogs. The orthology relation on a set of genes is therefore determined by the gene tree and an “event labeling” that identifies each interior vertex of that tree as either a duplication or a speciation event. In the context of analyzing orthology data, the problem of reconciling event-labeled gene trees with a species tree appears as a variant of the reconciliation problem where genes trees have no labels in their internal vertices. When reconciling a gene tree with a species tree, it can be assumed that the species tree is correct or, in the case of a unknown species tree, it can be inferred. Therefore it is crucial to know for a given gene tree whether there even exists a species tree. In this thesis we characterize event-labelled gene trees for which a species tree exists and species trees to which event-labelled gene trees can be mapped. Reconciliation methods are not always the best options for detecting orthology. A fundamental problem is that, aside from multicellular eukaryotes, evolution does not seem to have conformed to the descent-with-modification model that gives rise to tree-like phylogenies. Examples include many cases of prokaryotes and viruses whose evolution involved horizontal gene transfer. To treat the problem of distinguishing orthology and paralogy within a more general framework, graph-based methods have been proposed to detect and differentiate among evolutionary relationships of genes in those organisms. In this work we introduce a measure of orthology that can be used to test graph-based methods and reconciliation methods that detect orthology. Using these results a new algorithm BOTTOM-UP to determine whether a map from the set of vertices of a tree to a set of events is a symbolic ultrametric or not is devised. Additioanlly, a simulation environment designed to generate large gene families with complex duplication histories on which reconstruction algorithms can be tested and software tools can be benchmarked is presented.

No description available.

Die Atyidae sind eine artenreiche Familie weit verbreiteter Süßwassergarnelen, zu der sowohl landumschlossene als auch amphidrome Arten gehören. Ein großer Teil der Atyidae ist im Indopazifik verbreitet, einer Region, die für ihre geologisch komplexe Geschichte bekannt ist. Die Evolution der Atyidae in Kombination mit der Taxonomie, die bis ins frühe 19. Jahrhundert zurückreicht, führt zu einem hohen Maß an taxonomischer Unsicherheit. Das zeigt sich darin, dass über 70 % der Artenvielfalt in einer Gattung – aus insgesamt 54 der gesamten Familie – enthalten sind. Diese Gattung, Caridina, ist nicht monophyletisch. Eine vollständige Überarbeitung fehlt jedoch noch aus mehreren Gründen; darunter unvollständige Kenntnisse über entsprechende Verwandtschaftsverhältnisse, das Abwägen zwischen der Arbeit mit Museumsexemplaren und dem Sammeln im weiten Verbreitungsgebiet der Familie sowie die Plastizität ihrer Morphologie. Ich führe eine Meta-Analyse der Biogeographie der Landmassen innerhalb der Grenzen des Indischen Ozeans durch. Die bei mehreren Taxa festgestellten Tendenzen belegen, dass die physische Verbindung zwischen den Landmassen für die Ausbreitung weniger wichtig war als der durch ökologische Bedingungen ausgeübte Druck. Dann vergleichen wir Extraktionsmethoden, abwägend zwischen DNA-Ausbeute und -Integrität sowie Probenkonservierung. Wir zeigen, dass die Maximierung der DNA-Ausbeute durch Ganzkörperlyse jedoch möglich ist, ohne die Merkmale im Exoskelett zu beschädigen. Abschließend verwenden wir einen Exon-Capture-Ansatz, um eine zeitkalibrierte Phylogenie der artenreichsten Gruppe innerhalb der Atyidae, d. h. Caridina und ihrer Verwandten, zu erstellen. Wir erläutern Details über die Evolution lebensgeschichtlicher Merkmale sowie der Biogeographie und zeigen, dass die Geschichte der Familie eng mit dem Indopazifik verbunden ist und schaffen einen robusten phylogenomischen Rahmen, der zukünftige Bemühungen zur Überarbeitung der Familie erleichtern wird. / The Atyidae is a speciose family of widely distributed freshwater shrimps that includes landlocked and amphidromous species. A large portion of the atyid diversity is distributed in the Indo-Pacific, a region known for its geologically complex history. Its evolution combined with a vast distribution range and a taxonomy that dates back to the early nineteenth century amounts to a high degree of taxonomic uncertainty, which is illustrated by the fact that over 70% of its diversity is contained within one genus out of the 54 in the family. This genus, Caridina, is not monophyletic, but a full revision is still lacking for several reasons, including incomplete knowledge about its relationships, the compromise between working with museum specimens and collecting new specimens along its wide distribution, and the plasticity of its morphology. My coauthors and I conduct a meta-analysis of the historical biogeography of the landmasses within the boundaries of the Indian Ocean. Trends shown by multiple taxa demonstrate that physical connectivity between said landmasses is less important to dispersal than the pressure exerted by ecological conditions. Then, we compare extraction methods in terms of the trade-off between DNA yield and integrity and specimen preservation. We show that, whereas traditional extraction methods are still useful to obtain viable DNA from museum samples a few decades old, maximising the DNA yield through whole-body lysis is possible without damaging characters in the exoskeleton. Finally, we proceed to use an exon-capture approach to produce a time-calibrated phylogeny of the most diverse group in Atyidae, i.e., Caridina and their kin. We reveal details about the evolution of life history traits as well as biogeography, showing that the history of the family is intimately linked to the Indo-Pacific and constructing a robust phylogenetic framework that will facilitate future endeavours to revise the family.