Using binding profiles to predict binding sites of target RNAs

Prediction of RNA-RNA interaction is a key to elucidating possible functions of small non-coding RNAs, and a number of computational methods have been proposed to analyze interacting RNA secondary structures. In this article, we focus on predicting binding sites of target RNAs that are expected to interact with regulatory antisense RNAs in a general form of interaction. For this purpose, we propose bistaRNA, a novel method for predicting multiple binding sites of target RNAs. bistaRNA employs binding profiles that represent scores for hybridized structures, leading to reducing the computational cost for interaction prediction. bistaRNA considers an ensemble of equilibrium interacting structures and seeks to maximize expected accuracy using dynamic programming. Experimental results on real interaction data validate good accuracy and fast computation time of bistaRNA as compared with several competitive methods. Moreover, we aim to find new targets given specific antisense RNAs, which provides interesting insights into antisense RNA regulation. bistaRNA is implemented in C++. The program and Supplementary Material are available at http://rna.naist.jp/program/bistarna/.     

Analysis of a 3'-translation enhancer in a tombusvirus: a dynamic model for RNA-RNA interactions of mRNA termini

Tomato bushy stunt virus is a (+)-strand RNA virus that is neither 5'-capped nor 3'-polyadenylated. Translation of viral proteins is instead mediated by an RNA element, the 3'-cap-independent translational enhancer (3'CITE), which is located in its 3' untranslated region (UTR). The 3'CITE is proposed to recruit the translational machinery to the viral message, while a long-distance RNA-RNA interaction between the 3'CITE and 5' UTR is thought to deliver the 43S ribosomal subunit to the 5' end of the viral mRNA. Here we provide the first evidence that the 5' UTR and 3'CITE interact physically. Mutational analysis showed that formation of this RNA-RNA interaction in vitro correlates well with efficient translation in vivo, thus supporting its functional relevance. Other analyses of the 3'CITE confirmed an overall Y-shaped RNA secondary structure and demonstrated the importance of numerous minor structural features for efficient translation of viral mRNAs. Functional studies on the role of the 5' UTR revealed that despite the absence of a cap structure, 43S subunits load at the very 5' end and scan in a 3' direction. These results indicate that the 5'-3' RNA-RNA interaction is likely disrupted by scanning ribosomal subunits and suggest a dynamic model for the interaction of mRNA termini during active translation.     

Control of ColE1 plasmid replication by antisense RNA

One of the two major classes of regulatory strategies that control plasmid copy number involves recognition via base pairing between two plasmid-encoded complementary RNAs. The detailed analysis of this control circuitry has revealed some features of regulatory mechanisms based on RNA-RNA interaction that distinguish them from those based on protein-nucleic acid interaction. These features provide a framework with which to understand other regulatory mechanisms based on RNA-RNA interaction, and will aid in the design of efficient artificial antisense RNA systems.     

Predicting RNA secondary structures with arbitrary pseudoknots by maximizing the number of stacking pairs.

The paper investigates the computational problem of predicting RNA secondary structures. The general belief is that allowing pseudoknots makes the problem hard. Existing polynomial-time algorithms are heuristic algorithms with no performance guarantee and can handle only limited types of pseudoknots. In this paper, we initiate the study of predicting RNA secondary structures with a maximum number of stacking pairs while allowing arbitrary pseudoknots. We obtain two approximation algorithms with worst-case approximation ratios of 1/2 and 1/3 for planar and general secondary structures, respectively. For an RNA sequence of n bases, the approximation algorithm for planar secondary structures runs in O(n(3)) time while that for the general case runs in linear time. Furthermore, we prove that allowing pseudoknots makes it NP-hard to maximize the number of stacking pairs in a planar secondary structure. This result is in contrast with the recent NP-hard results on psuedoknots which are based on optimizing some general and complicated energy functions.     

Multifaceted regulation of translational readthrough by RNA replication elements in a tombusvirus

Translational readthrough of stop codons by ribosomes is a recoding event used by a variety of viruses, including plus-strand RNA tombusviruses. Translation of the viral RNA-dependent RNA polymerase (RdRp) in tombusviruses is mediated using this strategy and we have investigated this process using a variety of in vitro and in vivo approaches. Our results indicate that readthrough generating the RdRp requires a novel long-range RNA-RNA interaction, spanning a distance of ～3.5 kb, which occurs between a large RNA stem-loop located 3'-proximal to the stop codon and an RNA replication structure termed RIV at the 3'-end of the viral genome. Interestingly, this long-distance RNA-RNA interaction is modulated by mutually-exclusive RNA structures in RIV that represent a type of RNA switch. Moreover, a different long-range RNA-RNA interaction that was previously shown to be necessary for viral RNA replicase assembly was also required for efficient readthrough production of the RdRp. Accordingly, multiple replication-associated RNA elements are involved in modulating the readthrough event in tombusviruses and we propose an integrated mechanistic model to describe how this regulatory network could be advantageous by (i) providing a quality control system for culling truncated viral genomes at an early stage in the replication process, (ii) mediating cis-preferential replication of viral genomes, and (iii) coordinating translational readthrough of the RdRp with viral genome replication. Based on comparative sequence analysis and experimental data, basic elements of this regulatory model extend to other members of Tombusviridae, as well as to viruses outside of this family.     

A method for rapid similarity analysis of RNA secondary structures

Background  

Owing to the rapid expansion of RNA structure databases in recent years, efficient methods for structure comparison are in demand for function prediction and evolutionary analysis. Usually, the similarity of RNA secondary structures is evaluated based on tree models and dynamic programming algorithms. We present here a new method for the similarity analysis of RNA secondary structures.     

Determinants of apical loop-internal loop RNA-RNA interactions involving the HCV IRES

Domain II of the hepatitis C virus internal ribosome entry site is a major RNA structure involved in the viral mRNA translation. It comprises four different structural domains. We performed in vitro selection against the apical loop of the domain II and we identified RNA aptamers folding as an imperfect hairpin with an internal loop of interacting with the apical loop of the domain II. This RNA-RNA interaction creates apical loop-internal loop complex. The aptamer binds the target with an apparent K(d) of 35nM. In this study, the main structural elements of the target and the aptamer involved in the formation of the complex are characterized by mutation, deletion, and RNase probing analysis. We demonstrate that a complementary loop flanked by G,C rich upper and lower stems are crucial for such RNA-RNA interactions.     

Parsing nucleic acid pseudoknotted secondary structure: algorithm and applications.

Accurate prediction of pseudoknotted nucleic acid secondary structure is an important computational challenge. Prediction algorithms based on dynamic programming aim to find a structure with minimum free energy according to some thermodynamic ("sum of loop energies") model that is implicit in the recurrences of the algorithm. However, a clear definition of what exactly are the loops in pseudoknotted structures, and their associated energies, has been lacking. In this work, we present a complete classification of loops in pseudoknotted nucleic secondary structures, and describe the Rivas and Eddy and other energy models as sum-of-loops energy models. We give a linear time algorithm for parsing a pseudoknotted secondary structure into its component loops. We give two applications of our parsing algorithm. The first is a linear time algorithm to calculate the free energy of a pseudoknotted secondary structure. This is useful for heuristic prediction algorithms, which are widely used since (pseudoknotted) RNA secondary structure prediction is NP-hard. The second application is a linear time algorithm to test the generality of the dynamic programming algorithm of Akutsu for secondary structure prediction.Together with previous work, we use this algorithm to compare the generality of state-of-the-art algorithms on real biological structures.     

The role of the basic N-terminal region of protein L18 in 5S RNA-23S RNA complex formation.

Of the three proteins, L5, L18 and L25, which bind to 5S RNA, the former two effect the interaction of 5S RNA with 23S RNA. We have used trypsin as a probe to investigate the roles of the proteins in this RNA-RNA assembly, with the following results: (1) In complexes with 5S RNA, the highly basic N-terminal region of L18 is accessible to trypsin. This accessibility is unaffected by L25. However, its presence is essential for stimulating L5 binding. (2) In 5S RNA-protein-23S RNA complexes proteins L5 and L18 are both strongly resistant to proteolysis. (3) No 5S RNA-23S RNA complex formation occurs in the presence of L5 and the C-terminal L18 fragment. Two possible models for the mechanism of RNA-RNA assembly are proposed.     

RNA sequences and structures required for the recruitment and activity of the dengue virus polymerase

Dengue virus RNA-dependent RNA polymerase specifically binds to the viral genome by interacting with a promoter element known as stem-loop A (SLA). Although a great deal has been learned in recent years about the function of this promoter in dengue virus-infected cells, the molecular details that explain how the SLA interacts with the polymerase to promote viral RNA synthesis remain poorly understood. Using RNA binding and polymerase activity assays, we defined two elements of the SLA that are involved in polymerase interaction and RNA synthesis. Mutations at the top of the SLA resulted in RNAs that retained the ability to bind the polymerase but impaired promoter-dependent RNA synthesis. These results indicate that protein binding to the SLA is not sufficient to induce polymerase activity and that specific nucleotides of the SLA are necessary to render an active polymerase-promoter complex for RNA synthesis. We also report that protein binding to the viral RNA induces conformational changes downstream of the promoter element. Furthermore, we found that structured RNA elements at the 3' end of the template repress dengue virus polymerase activity in the context of a fully active SLA promoter. Using assays to evaluate initiation of RNA synthesis at the viral 3'-UTR, we found that the RNA-RNA interaction mediated by 5'-3'-hybridization was able to release the silencing effect of the 3'-stem-loop structure. We propose that the long range RNA-RNA interactions in the viral genome play multiple roles during RNA synthesis. Together, we provide new molecular details about the promoter-dependent dengue virus RNA polymerase activity.     

Dynamics of RNA-protein interactions in the HIV-1 Rev-RRE complex visualized by 6-thioguanosine-mediated photocrosslinking.

Expression of the structural proteins of human immunodeficiency virus type 1 (HIV-1) requires the direct interaction of multiple copies of the viral protein Rev with its target RNA, the Rev response element (RRE). RRE is a complex 351-nt RNA that is highly structured and located within the viral env gene. During initial Rev-RRE recognition, Rev binds with high affinity to a bubble structure located within the RRE RNA stem-loop II. We have used a site-specific photocrosslinking method based on 6-thioguanosine (6-thioG) photochemistry to probe the conformation of the high-affinity binding site of RRE RNA and its interactions with Rev protein under physiological conditions. A minimal duplex RNA containing the bubble region of RRE and 12 flanking base pairs was synthesized chemically. Two different RRE constructs with a single photoactive nucleoside (6-thio-dG or 6-thioG) at position 47 or 48 were synthesized. Upon UV irradiation, 6-thioG at both positions formed interstrand covalent crosslinks in RRE RNA. Mapping of crosslink sites by RNA sequencing revealed that 6-thioG at position 47 or 48 crosslinked to A73. In the presence of Rev, both RNA-RNA and RNA-protein crosslinks were observed, however, the RNA-RNA crosslink site was unchanged. Our results provide direct evidence that, during RNA-protein recognition, Rev is in close proximity to O6 of G47 and G48 in the major groove of RRE RNA. Our results also show that the bubble region of RRE RNA has a biologically relevant structure where G47 and G48 are in close proximity to A73 and this RNA structure is not changed significantly upon Rev binding. We propose that Rev protein recognizes and binds to specific structural elements of RRE RNA containing non-Watson-Crick base pairs and such structures could be a determinant for recognition by other RNA-binding proteins. Our site-specific crosslinking methods provide a general approach to capture dynamic states of biologically relevant RNA structures that are otherwise missed by NMR and X-ray crystallographic studies.     

Long-range RNA-RNA interactions circularize the dengue virus genome

Secondary and tertiary RNA structures present in viral RNA genomes play essential regulatory roles during translation, RNA replication, and assembly of new viral particles. In the case of flaviviruses, RNA-RNA interactions between the 5' and 3' ends of the genome have been proposed to be required for RNA replication. We found that two RNA elements present at the ends of the dengue virus genome interact in vitro with high affinity. Visualization of individual molecules by atomic force microscopy revealed that physical interaction between these RNA elements results in cyclization of the viral RNA. Using RNA binding assays, we found that the putative cyclization sequences, known as 5' and 3' CS, present in all mosquito-borne flaviviruses, were necessary but not sufficient for RNA-RNA interaction. Additional sequences present at the 5' and 3' untranslated regions of the viral RNA were also required for RNA-RNA complex formation. We named these sequences 5' and 3' UAR (upstream AUG region). In order to investigate the functional role of 5'-3' UAR complementarity, these sequences were mutated either separately, to destroy base pairing, or simultaneously, to restore complementarity in the context of full-length dengue virus RNA. Nonviable viruses were recovered after transfection of dengue virus RNA carrying mutations either at the 5' or 3' UAR, while the RNA containing the compensatory mutations was able to replicate. Since sequence complementarity between the ends of the genome is required for dengue virus viability, we propose that cyclization of the RNA is a required conformation for viral replication.     

A study of accessible motifs and RNA folding complexity.

mRNA molecules are folded in the cells and therefore many of their substrings may actually be inaccessible to protein and microRNA binding. The need to apply an accessibility criterion to the task of genome-wide mRNA motif discovery raises the challenge of overcoming the core O(n(3)) factor imposed by the time complexity of the currently best known algorithms for RNA secondary structure prediction. We speed up the dynamic programming algorithms that are standard for RNA folding prediction. Our new approach significantly reduces the computations without sacrificing the optimality of the results, yielding an expected time complexity of O(n(2) psi(n)), where psi(n) is shown to be constant on average under standard polymer folding models. A benchmark analysis confirms that in practice the runtime ratio between the previous approach and the new algorithm indeed grows linearly with increasing sequence size. The fast new RNA folding algorithm is utilized for genome-wide discovery of accessible cis-regulatory motifs in data sets of ribosomal densities and decay rates of S. cerevisiae genes and to the mining of exposed binding sites of tissue-specific microRNAs in A. thaliana.     

A binary Cy3 aptamer probe composed of folded modules

Aptamers are short single-stranded DNA or RNA sequences that are selected in vitro based on their high affinity to a target molecule. Dye-binding aptamers are promising tools for real-time detection of not only DNA or RNA sequences but also proteins of interest both in vitro and in vivo. In this study, we aimed to isolate an RNA aptamer to Cy3, a widely used, membrane-permeant, and nontoxic fluorescent cyanine dye. Extensive selection of affinity RNA molecules to Cy3 yielded a unique sequence aptamer named Cy3_apt. The selected Cy3_apt was 83 nucleotides long and successfully shortened to 49 nucleotides long with increased affinity to Cy3 by multiple base changes. The shortest Cy3_apt is composed of two separate hairpin modules that are required for the affinity to Cy3 as monitored by the surface plasmon resonance (SPR) assay. Also, the fluorescence of Cy3 increased on binding to Cy3_apt. The two modules of Cy3_apt, when detached from each other, functioned as a binary aptamer probe. We demonstrate that the binary Cy3_apt probe is applicable to the detection of target oligonucleotides or RNA-RNA interaction by tagging with target sequences. This binary probe consists of two folded modules, referred to as a folded binary probe.     

Conformational organization of the 3' untranslated region in the tomato bushy stunt virus genome

The 3' untranslated regions (UTRs) of positive-strand RNA viruses often form complex structures that facilitate various viral processes. We have examined the RNA conformation of the 352 nucleotide (nt) long 3' UTR of the Tomato bushy stunt virus (TBSV) genome with the goal of defining both local and global structures that are important for virus viability. Gel mobility analyses of a 3'-terminal 81 nt segment of the 3' UTR revealed that it is able to form a compact RNA domain (or closed conformation) that is stabilized by a previously proposed tertiary interaction. RNA-RNA gel shift assays were used to provide the first physical evidence for the formation of this tertiary interaction and revealed that it represents the dominant or "default" structure in the TBSV genome. Further analysis showed that the tertiary interaction involves five base pairs, each of which contributes differently to overall complex stability. Just upstream from the 3'-terminal domain, a long-distance RNA-RNA interaction involving 3' UTR sequences was found to be required for efficient viral RNA accumulation in vivo and to also contribute to the formation of the 3'-terminal domain in vitro. Collectively, these results provide a comprehensive overview of the conformational and functional organization of the 3' UTR of the TBSV genome.     

Locomotif: from graphical motif description to RNA motif search

MOTIVATION AND RESULTS: Motivated by the recent rise of interest in small regulatory RNAs, we present Locomotif--a new approach for locating RNA motifs that goes beyond the previous ones in three ways: (1) motif search is based on efficient dynamic programming algorithms, incorporating the established thermodynamic model of RNA secondary structure formation. (2) motifs are described graphically, using a Java-based editor, and search algorithms are derived from the graphics in a fully automatic way. The editor allows us to draw secondary structures, annotated with size and sequence information. They closely resemble the established, but informal way in which RNA motifs are communicated in the literature. Thus, the learning effort for Locomotif users is minimal. (3) Locomotif employs a client-server approach. Motifs are designed by the user locally. Search programs are generated and compiled on a bioinformatics server. They are made available both for execution on the server, and for download as C source code plus an appropriate makefile. AVAILABILITY: Locomotif is available at http://bibiserv.techfak.uni-bielefeld.de/locomotif.