Discovery of Pyrobaculum small RNA families with atypical pseudouridine guide RNA features.

In the Eukarya and Archaea, small RNA-guided pseudouridine modification is believed to be an essential step in ribosomal RNA maturation. While readily modeled and identified by computational methods in eukaryotic species, these guide RNAs have not been found in most archaeal genomes. Using high-throughput transcriptome sequencing and comparative genomics, we have identified ten novel small RNA families that appear to function as H/ACA pseudouridylation guide sRNAs, yet surprisingly lack several expected canonical features. The new RNA genes are transcribed and highly conserved across at least six species in the archaeal hyperthermophilic genus Pyrobaculum. The sRNAs exhibit a single hairpin structure interrupted by a conserved kink-turn motif, yet only two of ten families contain the complete canonical structure found in all other H/ACA sRNAs. Half of the sRNAs lack the conserved 3'-terminal ACA sequence, and many contain only a single 3' guide region rather than the canonical 5' and 3' bipartite guides. The predicted sRNA structures contain guide sequences that exhibit strong complementarity to ribosomal RNA or transfer RNA. Most of the predicted targets of pseudouridine modification are structurally equivalent to those known in other species. One sRNA appears capable of guiding pseudouridine modification at positions U54 and U55 in most or all Pyrobaculum tRNAs. We experimentally tested seven predicted pseudouridine modifications in ribosomal RNA, and all but one was confirmed. The structural insights provided by this new set of Pyrobaculum sRNAs will augment existing models and may facilitate the identification and characterization of new guide sRNAs in other archaeal species.

Beyond Mfold: recent advances in RNA bioinformatics.

Computational analysis of RNA secondary structure is a classical field of biosequence analysis, which has recently gained momentum due to the manyfold regulatory functions of RNA that have become apparent. We present five recent computational approaches that address the problems of synoptic folding space analysis, pseudoknot prediction, structure alignment, comparative structure prediction, and miRNA target prediction. All these programs are in current use and are available via the Bielefeld Bioinformatics Server at .

Pure multiple RNA secondary structure alignments: a progressive profile approach.

In functional, noncoding RNA, structure is often essential to function. While the full 3D structure is very difficult to determine, the 2D structure of an RNA molecule gives good clues to its 3D structure, and for molecules of moderate length, it can be predicted with good reliability. Structure comparison is, in analogy to sequence comparison, the essential technique to infer related function. We provide a method for computing multiple alignments of RNA secondary structures under the tree alignment model, which is suitable to cluster RNA molecules purely on the structural level, i.e., sequence similarity is not required. We give a systematic generalization of the profile alignment method from strings to trees and forests. We introduce a tree profile representation of RNA secondary structure alignments which allows reasonable scoring in structure comparison. Besides the technical aspects, an RNA profile is a useful data structure to represent multiple structures of RNA sequences. Moreover, we propose a visualization of RNA consensus structures that is enriched by the full sequence information.

Local similarity in RNA secondary structures.

We present a systematic treatment of alignment distance and local similarity algorithms on trees and forests. We build upon the tree alignment algorithm for ordered trees given by Jiang et. al (1995) and extend it to calculate local forest alignments, which is essential for finding local similar regions in RNA secondary structures. The time complexity of our algorithm is O(|F(1)| |F(2) deg(F(1)) deg(F(2)) (deg(F(1)) + deg(F(2))) where |F(i)| is the number of nodes in forest F(i) and deg (F(i)) is the degree of F(i). We provide carefully engineered dynamic programming implementations using dense, two-dimensional tables which considerably reduces the space requirement. We suggest a new representation of RNA secondary structures as forests that allow reasonable scoring of edit operations on RNA secondary structures. The comparison of RNA secondary structures is facilitated by a new visualization technique for RNA secondary structure alignments. Finally, we show how potential regulatory motifs can be discovered solely by their structural preservation, and independent of their sequence conservation and position.

Fast and effective prediction of microRNA/target duplexes.

MicroRNAs (miRNAs) are short RNAs that post-transcriptionally regulate the expression of target genes by binding to the target mRNAs. Although a large number of animal miRNAs has been defined, only a few targets are known. In contrast to plant miRNAs, which usually bind nearly perfectly to their targets, animal miRNAs bind less tightly, with a few nucleotides being unbound, thus producing more complex secondary structures of miRNA/target duplexes. Here, we present a program, RNA-hybrid, that predicts multiple potential binding sites of miRNAs in large target RNAs. In general, the program finds the energetically most favorable hybridization sites of a small RNA in a large RNA. Intramolecular hybridizations, that is, base pairings between target nucleotides or between miRNA nucleotides are not allowed. For large targets, the time complexity of the algorithm is linear in the target length, allowing many long targets to be searched in a short time. Statistical significance of predicted targets is assessed with an extreme value statistics of length normalized minimum free energies, a Poisson approximation of multiple binding sites, and the calculation of effective numbers of orthologous targets in comparative studies of multiple organisms. We applied our method to the prediction of Drosophila miRNA targets in 3'UTRs and coding sequence. RNAhybrid, with its accompanying programs RNAcalibrate and RNAeffective, is available for download and as a Web tool on the Bielefeld Bioinformatics Server (http://bibiserv.techfak.uni-bielefeld.de/rnahybrid/).