Substrate Affinity Versus Catalytic Efficiency: Ancestral Sequence Reconstruction of tRNA Nucleotidyltransferases Solves an Enzyme Puzzle.

In tRNA maturation, CCA-addition by tRNA nucleotidyltransferase is a unique and highly accurate reaction. While the mechanism of nucleotide selection and polymerization is well understood, it remains a mystery why bacterial and eukaryotic enzymes exhibit an unexpected and surprisingly low tRNA substrate affinity while they efficiently catalyze the CCA-addition. To get insights into the evolution of this high-fidelity RNA synthesis, the reconstruction and characterization of ancestral enzymes is a versatile tool. Here, we investigate a reconstructed candidate of a 2 billion years old CCA-adding enzyme from Gammaproteobacteria and compare it to the corresponding modern enzyme of Escherichia coli. We show that the ancestral candidate catalyzes an error-free CCA-addition, but has a much higher tRNA affinity compared with the extant enzyme. The consequence of this increased substrate binding is an enhanced reverse reaction, where the enzyme removes the CCA end from the mature tRNA. As a result, the ancestral candidate exhibits a lower catalytic efficiency in vitro as well as in vivo. Furthermore, the efficient tRNA interaction leads to a processive polymerization, while the extant enzyme catalyzes nucleotide addition in a distributive way. Thus, the modern enzymes increased their polymerization efficiency by lowering the binding affinity to tRNA, so that CCA synthesis is efficiently promoted due to a reduced reverse reaction. Hence, the puzzling and at a first glance contradicting and detrimental weak substrate interaction represents a distinct activity enhancement in the evolution of CCA-adding enzymes.

Evolution of DNA Methylation Across Ecdysozoa.

DNA methylation is a crucial, abundant mechanism of gene regulation in vertebrates. It is less prevalent in many other metazoan organisms and completely absent in some key model species, such as Drosophila melanogaster and Caenorhabditis elegans. We report here a comprehensive study of the presence and absence of DNA methyltransferases (DNMTs) in 138 Ecdysozoa, covering Arthropoda, Nematoda, Priapulida, Onychophora, and Tardigrada. Three of these phyla have not been investigated for the presence of DNA methylation before. We observe that the loss of individual DNMTs independently occurred multiple times across ecdysozoan phyla. We computationally predict the presence of DNA methylation based on CpG rates in coding sequences using an implementation of Gaussian Mixture Modeling, MethMod. Integrating both analysis we predict two previously unknown losses of DNA methylation in Ecdysozoa, one within Chelicerata (Mesostigmata) and one in Tardigrada. In the early-branching Ecdysozoa Priapulus caudatus, we predict the presence of a full set of DNMTs and the presence of DNA methylation. We are therefore showing a very diverse and independent evolution of DNA methylation in different ecdysozoan phyla spanning a phylogenetic range of more than 700 million years.

Unusual Occurrence of Two Bona-Fide CCA-Adding Enzymes in Dictyostelium discoideum.

Dictyostelium discoideum, the model organism for the evolutionary supergroup of Amoebozoa, is a social amoeba that, upon starvation, undergoes transition from a unicellular to a multicellular organism. In its genome, we identified two genes encoding for tRNA nucleotidyltransferases. Such pairs of tRNA nucleotidyltransferases usually represent collaborating partial activities catalyzing CC- and A-addition to the tRNA 3'-end, respectively. In D. discoideum, however, both enzymes exhibit identical activities, representing bona-fide CCA-adding enzymes. Detailed characterization of the corresponding activities revealed that both enzymes seem to be essential and are regulated inversely during different developmental stages of D. discoideum. Intriguingly, this is the first description of two functionally equivalent CCA-adding enzymes using the same set of tRNAs and showing a similar distribution within the cell. This situation seems to be a common feature in Dictyostelia, as other members of this phylum carry similar pairs of tRNA nucleotidyltransferase genes in their genome.

Divergent Evolution of Eukaryotic CC- and A-Adding Enzymes.

Synthesis of the CCA end of essential tRNAs is performed either by CCA-adding enzymes or as a collaboration between enzymes restricted to CC- and A-incorporation. While the occurrence of such tRNA nucleotidyltransferases with partial activities seemed to be restricted to Bacteria, the first example of such split CCA-adding activities was reported in Schizosaccharomyces pombe. Here, we demonstrate that the choanoflagellate Salpingoeca rosetta also carries CC- and A-adding enzymes. However, these enzymes have distinct evolutionary origins. Furthermore, the restricted activity of the eukaryotic CC-adding enzymes has evolved in a different way compared to their bacterial counterparts. Yet, the molecular basis is very similar, as highly conserved positions within a catalytically important flexible loop region are missing in the CC-adding enzymes. For both the CC-adding enzymes from S. rosetta as well as S. pombe, introduction of the loop elements from closely related enzymes with full activity was able to restore CCA-addition, corroborating the significance of this loop in the evolution of bacterial as well as eukaryotic tRNA nucleotidyltransferases. Our data demonstrate that partial CC- and A-adding activities in Bacteria and Eukaryotes are based on the same mechanistic principles but, surprisingly, originate from different evolutionary events.

Toward a mechanistic explanation of phenotypic evolution: The need for a theory of theory integration.

Reconciling different underlying ontologies and explanatory contexts has been one of the main challenges and impediments for theory integration in biology. Here, we analyze the challenge of developing an inclusive and integrative theory of phenotypic evolution as an example for the broader challenge of developing a theory of theory integration within the life sciences and suggest a number of necessary formal steps toward the resolution of often incompatible (hidden) assumptions. Theory integration in biology requires a better formal understanding of the structure of biological theories The strategy for integrating theories crucially depends on the relationships of the underlying ontologies.

Expansion of gene clusters, circular orders, and the shortest Hamiltonian path problem.

Clusters of paralogous genes such as the famous HOX cluster of developmental transcription factors tend to evolve by stepwise duplication of its members, often involving unequal crossing over. Gene conversion and possibly other mechanisms of concerted evolution further obfuscate the phylogenetic relationships. As a consequence, it is very difficult or even impossible to disentangle the detailed history of gene duplications in gene clusters. In this contribution we show that the expansion of gene clusters by unequal crossing over as proposed by Walter Gehring leads to distinctive patterns of genetic distances, namely a subclass of circular split systems. Furthermore, when the gene cluster was left undisturbed by genome rearrangements, the shortest Hamiltonian paths with respect to genetic distances coincide with the genomic order. This observation can be used to detect ancient genomic rearrangements of gene clusters and to distinguish gene clusters whose evolution was dominated by unequal crossing over within genes from those that expanded through other mechanisms.

Ecological plant epigenetics: Evidence from model and non-model species, and the way forward.

Growing evidence shows that epigenetic mechanisms contribute to complex traits, with implications across many fields of biology. In plant ecology, recent studies have attempted to merge ecological experiments with epigenetic analyses to elucidate the contribution of epigenetics to plant phenotypes, stress responses, adaptation to habitat, and range distributions. While there has been some progress in revealing the role of epigenetics in ecological processes, studies with non-model species have so far been limited to describing broad patterns based on anonymous markers of DNA methylation. In contrast, studies with model species have benefited from powerful genomic resources, which contribute to a more mechanistic understanding but have limited ecological realism. Understanding the significance of epigenetics for plant ecology requires increased transfer of knowledge and methods from model species research to genomes of evolutionarily divergent species, and examination of responses to complex natural environments at a more mechanistic level. This requires transforming genomics tools specifically for studying non-model species, which is challenging given the large and often polyploid genomes of plants. Collaboration among molecular geneticists, ecologists and bioinformaticians promises to enhance our understanding of the mutual links between genome function and ecological processes.

Uncovering missing pieces: duplication and deletion history of arrestins in deuterostomes.

BACKGROUND: The cytosolic arrestin proteins mediate desensitization of activated G protein-coupled receptors (GPCRs) via competition with G proteins for the active phosphorylated receptors. Arrestins in active, including receptor-bound, conformation are also transducers of signaling. Therefore, this protein family is an attractive therapeutic target. The signaling outcome is believed to be a result of structural and sequence-dependent interactions of arrestins with GPCRs and other protein partners. Here we elucidated the detailed evolution of arrestins in deuterostomes. RESULTS: Identity and number of arrestin paralogs were determined searching deuterostome genomes and gene expression data. In contrast to standard gene prediction methods, our strategy first detects exons situated on different scaffolds and then solves the problem of assigning them to the correct gene. This increases both the completeness and the accuracy of the annotation in comparison to conventional database search strategies applied by the community. The employed strategy enabled us to map in detail the duplication- and deletion history of arrestin paralogs including tandem duplications, pseudogenizations and the formation of retrogenes. The two rounds of whole genome duplications in the vertebrate stem lineage gave rise to four arrestin paralogs. Surprisingly, visual arrestin ARR3 was lost in the mammalian clades Afrotheria and Xenarthra. Duplications in specific clades, on the other hand, must have given rise to new paralogs that show signatures of diversification in functional elements important for receptor binding and phosphate sensing. CONCLUSION: The current study traces the functional evolution of deuterostome arrestins in unprecedented detail. Based on a precise re-annotation of the exon-intron structure at nucleotide resolution, we infer the gain and loss of paralogs and patterns of conservation, co-variation and selection.

Design specifications for cellular regulation.

A critical feature of all cellular processes is the ability to control the rate of gene or protein expression and metabolic flux in changing environments through regulatory feedback. We review the many ways that regulation is represented through causal, logical, and dynamical components. Formalizing the nature of these components promotes effective comparison among distinct regulatory networks and provides a common framework for the potential design and control of regulatory systems in synthetic biology.

The paralog-to-contig assignment problem: high quality gene models from fragmented assemblies.

BACKGROUND: The accurate annotation of genes in newly sequenced genomes remains a challenge. Although sophisticated comparative pipelines are available, computationally derived gene models are often less than perfect. This is particularly true when multiple similar paralogs are present. The issue is aggravated further when genomes are assembled only at a preliminary draft level to contigs or short scaffolds. However, these genomes deliver valuable information for studying gene families. High accuracy models of protein coding genes are needed in particular for phylogenetics and for the analysis of gene family histories. RESULTS: We present a pipeline, ExonMatchSolver, that is designed to help the user to produce and curate high quality models of the protein-coding part of genes. The tool in particular tackles the problem of identifying those coding exon groups that belong to the same paralogous genes in a fragmented genome assembly. This paralog-to-contig assignment problem is shown to be NP-complete. It is phrased and solved as an Integer Linear Programming problem. CONCLUSIONS: The ExonMatchSolver-pipeline can be employed to build highly accurate models of protein coding genes even when spanning several genomic fragments. This sets the stage for a better understanding of the evolutionary history within particular gene families which possess a large number of paralogs and in which frequent gene duplication events occurred.

Algebraic Dynamic Programming over general data structures.

BACKGROUND: Dynamic programming algorithms provide exact solutions to many problems in computational biology, such as sequence alignment, RNA folding, hidden Markov models (HMMs), and scoring of phylogenetic trees. Structurally analogous algorithms compute optimal solutions, evaluate score distributions, and perform stochastic sampling. This is explained in the theory of Algebraic Dynamic Programming (ADP) by a strict separation of state space traversal (usually represented by a context free grammar), scoring (encoded as an algebra), and choice rule. A key ingredient in this theory is the use of yield parsers that operate on the ordered input data structure, usually strings or ordered trees. The computation of ensemble properties, such as a posteriori probabilities of HMMs or partition functions in RNA folding, requires the combination of two distinct, but intimately related algorithms, known as the inside and the outside recursion. Only the inside recursions are covered by the classical ADP theory. RESULTS: The ideas of ADP are generalized to a much wider scope of data structures by relaxing the concept of parsing. This allows us to formalize the conceptual complementarity of inside and outside variables in a natural way. We demonstrate that outside recursions are generically derivable from inside decomposition schemes. In addition to rephrasing the well-known algorithms for HMMs, pairwise sequence alignment, and RNA folding we show how the TSP and the shortest Hamiltonian path problem can be implemented efficiently in the extended ADP framework. As a showcase application we investigate the ancient evolution of HOX gene clusters in terms of shortest Hamiltonian paths. CONCLUSIONS: The generalized ADP framework presented here greatly facilitates the development and implementation of dynamic programming algorithms for a wide spectrum of applications.

The relativity of biological function.

Function is a central concept in biological theories and explanations. Yet discussions about function are often based on a narrow understanding of biological systems and processes, such as idealized molecular systems or simple evolutionary, i.e., selective, dynamics. Conflicting conceptions of function continue to be used in the scientific literature to support certain claims, for instance about the fraction of "functional DNA" in the human genome. Here we argue that all biologically meaningful interpretations of function are necessarily context dependent. This implies that they derive their meaning as well as their range of applicability only within a specific theoretical and measurement context. We use this framework to shed light on the current debate about functional DNA and argue that without considering explicitly the theoretical and measurement contexts all attempts to integrate biological theories are prone to fail.

Kiwi genome provides insights into evolution of a nocturnal lifestyle.

BACKGROUND: Kiwi, comprising five species from the genus Apteryx, are endangered, ground-dwelling bird species endemic to New Zealand. They are the smallest and only nocturnal representatives of the ratites. The timing of kiwi adaptation to a nocturnal niche and the genomic innovations, which shaped sensory systems and morphology to allow this adaptation, are not yet fully understood. RESULTS: We sequenced and assembled the brown kiwi genome to 150-fold coverage and annotated the genome using kiwi transcript data and non-redundant protein information from multiple bird species. We identified evolutionary sequence changes that underlie adaptation to nocturnality and estimated the onset time of these adaptations. Several opsin genes involved in color vision are inactivated in the kiwi. We date this inactivation to the Oligocene epoch, likely after the arrival of the ancestor of modern kiwi in New Zealand. Genome comparisons between kiwi and representatives of ratites, Galloanserae, and Neoaves, including nocturnal and song birds, show diversification of kiwi's odorant receptors repertoire, which may reflect an increased reliance on olfaction rather than sight during foraging. Further, there is an enrichment of genes influencing mitochondrial function and energy expenditure among genes that are rapidly evolving specifically on the kiwi branch, which may also be linked to its nocturnal lifestyle. CONCLUSIONS: The genomic changes in kiwi vision and olfaction are consistent with changes that are hypothesized to occur during adaptation to nocturnal lifestyle in mammals. The kiwi genome provides a valuable genomic resource for future genome-wide comparative analyses to other extinct and extant diurnal ratites.

The ancestor of modern Holozoa acquired the CCA-adding enzyme from Alphaproteobacteria by horizontal gene transfer.

Transfer RNAs (tRNAs) require the absolutely conserved sequence motif CCA at their 3'-ends, representing the site of aminoacylation. In the majority of organisms, this trinucleotide sequence is not encoded in the genome and thus has to be added post-transcriptionally by the CCA-adding enzyme, a specialized nucleotidyltransferase. In eukaryotic genomes this ubiquitous and highly conserved enzyme family is usually represented by a single gene copy. Analysis of published sequence data allows us to pin down the unusual evolution of eukaryotic CCA-adding enzymes. We show that the CCA-adding enzymes of animals originated from a horizontal gene transfer event in the stem lineage of Holozoa, i.e. Metazoa (animals) and their unicellular relatives, the Choanozoa. The tRNA nucleotidyltransferase, acquired from an α-proteobacterium, replaced the ancestral enzyme in Metazoa. However, in Choanoflagellata, the group of Choanozoa that is closest to Metazoa, both the ancestral and the horizontally transferred CCA-adding enzymes have survived. Furthermore, our data refute a mitochondrial origin of the animal tRNA nucleotidyltransferases.

Orthology detection combining clustering and synteny for very large datasets.

The elucidation of orthology relationships is an important step both in gene function prediction as well as towards understanding patterns of sequence evolution. Orthology assignments are usually derived directly from sequence similarities for large data because more exact approaches exhibit too high computational costs. Here we present PoFF, an extension for the standalone tool Proteinortho, which enhances orthology detection by combining clustering, sequence similarity, and synteny. In the course of this work, FFAdj-MCS, a heuristic that assesses pairwise gene order using adjacencies (a similarity measure related to the breakpoint distance) was adapted to support multiple linear chromosomes and extended to detect duplicated regions. PoFF largely reduces the number of false positives and enables more fine-grained predictions than purely similarity-based approaches. The extension maintains the low memory requirements and the efficient concurrency options of its basis Proteinortho, making the software applicable to very large datasets.

The CHR site: definition and genome-wide identification of a cell cycle transcriptional element.

The cell cycle genes homology region (CHR) has been identified as a DNA element with an important role in transcriptional regulation of late cell cycle genes. It has been shown that such genes are controlled by DREAM, MMB and FOXM1-MuvB and that these protein complexes can contact DNA via CHR sites. However, it has not been elucidated which sequence variations of the canonical CHR are functional and how frequent CHR-based regulation is utilized in mammalian genomes. Here, we define the spectrum of functional CHR elements. As the basis for a computational meta-analysis, we identify new CHR sequences and compile phylogenetic motif conservation as well as genome-wide protein-DNA binding and gene expression data. We identify CHR elements in most late cell cycle genes binding DREAM, MMB, or FOXM1-MuvB. In contrast, Myb- and forkhead-binding sites are underrepresented in both early and late cell cycle genes. Our findings support a general mechanism: sequential binding of DREAM, MMB and FOXM1-MuvB complexes to late cell cycle genes requires CHR elements. Taken together, we define the group of CHR-regulated genes in mammalian genomes and provide evidence that the CHR is the central promoter element in transcriptional regulation of late cell cycle genes by DREAM, MMB and FOXM1-MuvB.

Chromatin computation: epigenetic inheritance as a pattern reconstruction problem.

Eukaryotic histones carry a diverse set of specific chemical modifications that accumulate over the life-time of a cell and have a crucial impact on the cell state in general and the transcriptional program in particular. Replication constitutes a dramatic disruption of the chromatin states that effectively amounts to partial erasure of stored information. To preserve its epigenetic state the cell reconstructs (at least part of) the histone modifications by means of processes that are still very poorly understood. A plausible hypothesis is that the different combinations of reader and writer domains in histone-modifying enzymes implement local rewriting rules that are capable of "recomputing" the desired parental modification patterns on the basis of the partial information contained in that half of the nucleosomes that predate replication. To test whether such a mechanism is theoretically feasible, we have developed a flexible stochastic simulation system (available at http://www.bioinf.uni-leipzig.de/Software/StoChDyn) for studying the dynamics of histone modification states. The implementation is based on Gillespie's approach, i.e., it models the master equation of a detailed chemical model. It is efficient enough to use an evolutionary algorithm to find patterns across multiple cell divisions with high accuracy. We found that it is easy to evolve a system of enzymes that can maintain a particular chromatin state roughly stable, even without explicit boundary elements separating differentially modified chromatin domains. However, the success of this task depends on several previously unanticipated factors, such as the length of the initial state, the specific pattern that should be maintained, the time between replications, and chemical parameters such as enzymatic binding and dissociation rates. All these factors also influence the accumulation of errors in the wake of cell divisions.

Transcriptional regulation by histone modifications: towards a theory of chromatin re-organization during stem cell differentiation.

Chromatin-related mechanisms, as e.g. histone modifications, are known to be involved in regulatory switches within the transcriptome. Only recently, mathematical models of these mechanisms have been established. So far they have not been applied to genome-wide data. We here introduce a mathematical model of transcriptional regulation by histone modifications and apply it to data of trimethylation of histone 3 at lysine 4 (H3K4me3) and 27 (H3K27me3) in mouse pluripotent and lineage-committed cells. The model describes binding of protein complexes to chromatin which are capable of reading and writing histone marks. Molecular interactions of the complexes with DNA and modified histones create a regulatory switch of transcriptional activity. The regulatory states of the switch depend on the activity of histone (de-) methylases, the strength of complex-DNA-binding and the number of nucleosomes capable of cooperatively contributing to complex-binding. Our model explains experimentally measured length distributions of modified chromatin regions. It suggests (i) that high CpG-density facilitates recruitment of the modifying complexes in embryonic stem cells and (ii) that re-organization of extended chromatin regions during lineage specification into neuronal progenitor cells requires targeted de-modification. Our approach represents a basic step towards multi-scale models of transcriptional control during development and lineage specification.

A global genome segmentation method for exploration of epigenetic patterns.

Current genome-wide ChIP-seq experiments on different epigenetic marks aim at unraveling the interplay between their regulation mechanisms. Published evaluation tools, however, allow testing for predefined hypotheses only. Here, we present a novel method for annotation-independent exploration of epigenetic data and their inter-correlation with other genome-wide features. Our method is based on a combinatorial genome segmentation solely using information on combinations of epigenetic marks. It does not require prior knowledge about the data (e.g. gene positions), but allows integrating the data in a straightforward manner. Thereby, it combines compression, clustering and visualization of the data in a single tool. Our method provides intuitive maps of epigenetic patterns across multiple levels of organization, e.g. of the co-occurrence of different epigenetic marks in different cell types. Thus, it facilitates the formulation of new hypotheses on the principles of epigenetic regulation. We apply our method to histone modification data on trimethylation of histone H3 at lysine 4, 9 and 27 in multi-potent and lineage-primed mouse cells, analyzing their combinatorial modification pattern as well as differentiation-related changes of single modifications. We demonstrate that our method is capable of reproducing recent findings of gene centered approaches, e.g. correlations between CpG-density and the analyzed histone modifications. Moreover, combining the clustered epigenetic data with information on the expression status of associated genes we classify differences in epigenetic status of e.g. house-keeping genes versus differentiation-related genes. Visualizing the distribution of modification states on the chromosomes, we discover strong patterns for chromosome X. For example, exclusively H3K9me3 marked segments are enriched, while poised and active states are rare. Hence, our method also provides new insights into chromosome-specific epigenetic patterns, opening up new questions how "epigenetic computation" is distributed over the genome in space and time.

Modeling the dynamic epigenome: from histone modifications towards self-organizing chromatin.

Epigenetic mechanisms play an important role in regulating and stabilizing functional states of living cells. However, in spite of an increasing amount of experimental data, models of transcriptional regulation by epigenetic processes, in particular by histone modifications, are rather rare. In this article, we focus on epigenetic modes of transcriptional regulation based on histone modifications and their potential dynamical interplay with DNA methylation and higher-order chromatin structure. The main purpose of this article is to review recent formal modeling approaches to the dynamics and propagation of histone modifications and to relate them to available experimental data. We evaluate their assumptions with respect to recruitment of relevant modifiers, establishment and processing of modifications, and compare the emerging stability properties and memory effects. Theoretical predictions that await experimental validation are highlighted and potential extensions of these models towards multiscale models of self-organizing chromatin are discussed.