The genome-wide search for non-coding RNAs requires efficient methods to compute and compare local secondary structures. Since the exact boundaries of such putative transcripts are typically unknown, arbitrary sequence windows have to be used in practice. Here we present a method for robustly computing the probabilities of local base pairs from long RNA sequences independent of the exact positions of the sequence window.

Unlike tRNAs and microRNAs, both classes of snoRNAs, which direct two distinct types of chemical modifications of uracil residues, have proved to be surprisingly difficult to find in genomic sequences. Most computational approaches so far have explicitly used the fact that snoRNAs predominantly target ribosomal RNAs and spliceosomal RNAs. The target is specified by a short stretch of sequence complementarity between the snoRNA and its target. This sequence complementarity to known targets crucially contributes to sensitivity and specificity of snoRNA gene finding algorithms. The discovery of ‘orphan’ snoRNAs, which either have no known target, or which target ordinary protein-coding mRNAs, however, begs the question whether this class of ‘housekeeping’ non-coding RNAs is much more widespread and might have a diverse set of regulatory functions. In order to approach this question, we present here a combination of RNA secondary structure prediction and machine learning that is designed to recognize the two major classes of snoRNAs, box C/D and box H/ACA snoRNAs, among ncRNA candidate sequences. The snoReport approach deliberately avoids any usage of target information. We find that the combination of the conserved sequence boxes and secondary structure constraints as a pre-filter with SVM classifiers based on a small set of structural descriptors are sufficient for a reliable identification of snoRNAs. Tests of snoReport on data from several recent experimental surveys show that the approach is feasible; the application to a dataset from a large-scale comparative genomics survey for ncRNAs suggests that there are likely hundreds of previously undescribed ‘orphan’ snoRNAs still hidden in the human genome.

Motivation: Many classes of functional RNA molecules are characterized by highly conserved secondary structures but little detectable sequence similarity. Reliable multiple alignments can therefore be constructed only when the shared structural features are taken into account. Since multiple alignments are used as input for many subsequent methods of data analysis, structure-based alignments are an indispensable necessity in RNA bioinformatics. Results: We present here a method to compute pairwise and progressive multiple alignments from the direct comparison of base pairing probability matrices. Instead of attempting to solve the folding and the alignment problem simultaneously as in the classical Sankoff's algorithm, we use McCaskill's approach to compute base pairing probability matrices which effectively incorporate the information on the energetics of each sequences. A novel, simplified variant of Sankoff's algorithms can then be employed to extract the maximum-weight common secondary structure and an associated alignment.

Many of the known microRNAs are encoded in polycistronic transcripts. Here, we reconstruct the evolutionary history of the mir17 microRNA clusters which consist of miR-17, miR-18, miR-19a, miR-19b, miR-20, miR-25, miR-92, miR-93, miR-106a, and miR-106b. The history of this cluster is governed by an initial phase of local (tandem) duplications, a series of duplications of entire clusters and subsequent loss of individual microRNAs from the resulting paralogous clusters. The complex history of the mir17 microRNA family appears to be closely linked to the early evolution of the vertebrate lineage.

MicroRNAs (miRNAs) form an abundant class of non‐coding RNA genes that have an important function in post‐transcriptional gene regulation and in particular modulate the expression of developmentally important transcription factors including Hox genes. Two families of microRNAs are genomically located in intergenic regions in the Hox clusters of vertebrates. Here we describe their evolution in detail. We show that the micro RNAs closely follow the patterns of protein evolution in the Hox clusters, which is characterized by cluster duplications followed by differential gene loss.

Replicator equations have been studied for three decades as a generic dynamical system modelling replication processes. Here we show how they arise naturally in models of self-replicating polymers and discuss some of their basic properties. We then concentrate on a minimal dynamic model of a protocell by coupling replicating polymers with a growing membrane.

The concept of a fitness landscape arose in theoretical biology, while that of effective fitness has its origin in evolutionary computation. Both have emerged as useful conceptual tools with which to understand the dynamics of evolutionary processes, especially in the presence of complex genotype-phenotype relations. In this contribution we attempt to provide a unified discussion of these two approaches, discussing both their advantages and disadvantages in the context of some simple models. We also discuss how fitness and effective fitness change under various transformations of the configuration space of the underlying genetic model, concentrating on coarse-graining transformations and on a particular coordinate transformation that provides an appropriate basis for illuminating the structure and consequences of recombination.

Template-dependent replication at the molecular level is the basis of reproduction in nature. A detailed understanding of the peculiarities of the chemical reaction kinetics associated with replication processes is therefore an indispensible prerequisite for any understanding of evolution at the molecular level. Networks of interacting self-replicating species can give rise to a wealth of different dynamical phenomena, from competitive exclusion to permanent coexistence, from global stability to multi-stability and chaotic dynamics. Nevertheless, there are some general principles that govern their overall behavior. We focus on the question to what extent the dynamics of replication can explain the accumulation of genetic information that eventually leads to the emergence of the first cell and hence the origin of life as we know it. A large class of ligation-based replication systems, which includes the experimentally available model systems for template directed self-replication, is of particular interest because its dynamics bridges the gap between the survival of a single fittest species to the global coexistence of everthing. In this intermediate regime the selection is weak enough to allow the coexistence of genetically unrelated replicators and strong enough to limit the accumulation of disfunctional mutants.

Networks are a common theme at all levels of molecular evolution: Networks of metastable states and their connecting saddle points determine structure and folding kinetics of biopolymers. Neutral networks in sequence space explain the evolvability of both nucleic acids and polypeptides by linking Darwinian selection with neutral drift. Interacting replicators, be they simple molecules or highly complex mammals, form intricate ecological networks that are crucial for their survival. Chemical reactions are collected in extensive metabolic networks by means of specific enzymes; both the enzymes and the chemical reaction network that they govern undergoes evolutionary changes. Networks of gene regulation, protein-protein interaction, and cell signaling form the physico-chemical basis for morphogenesis and development. The nervous systems of higher animals form another distinct level of network architecture. We are beginning to understand the structure and function of each of the individual levels in some detail. Yet, their interplay largely remains still in the dark.

RNA and protein molecules were found to be both templates for replication and specific catalysts for biochemical reactions. RNA molecules, although very difficult to obtain via plausible synthetic pathways under prebiotic conditions, are the only candidates for early replicons. Only they are obligatory templates for replication, which can conserve mutations and propagate them to forthcoming generations. RNA based catalysts, called ribozymes, act with high efficiency and specificity for all classes of reactions involved in the interconversion of RNA molecules such as cleavage and template assisted ligation. The idea of an RNA world was conceived for a plausible prebiotic scenario of RNA molecules operating upon each other and constituting thereby a functional molecular organization. A theoretical account on molecular replication making precise the conditions under which one observes parabolic, exponential or hyperbolic growth is presented. Exponential growth is observed in a protein assisted RNA world where plus-minus-(±)-duplex formation is avoided by the action of an RNA replicase. Error propagation to forthcoming generations is analyzed in absence of selective neutral mutants as well as for predefined degrees of neutrality. The concept of an error threshold for sufficiently precise replication and survival of populations derived from the theory of molecular quasispecies is discussed. Computer simulations are used to model the interplay between adaptive evolution and random drift. A model of evolution is proposed that allows for explicit handling of phenotypes.