Small regulatory RNAs are highly abundant noncoding RNAs (ncRNA) found in bacterial genomes. These small regulatory ncRNAs (sRNAs) can regulate the synthesis of proteins by mediating mRNA transcription, translation and stability. Furthermore, they also control the activity of specific proteins by binding to them. In this study, we present a general computational approach for identifying the distinct structure of sRNAs in the Escherichia coli (E. coli) genome by a quantitative measure, Ediffthat is the energy difference between the optimal structure folded from a sequence segment and its corresponding optimal restrained structure where all base pairings formed in the original optimal structure are excluded. Our results indicate that most of the known small ncRNAs in E. coli K12 have very high normalized Ediffscores with high statistical significance. These sRNAs have distinct well-ordered structures that are both thermodynamically stable and uniquely folded.

Recent advances in RNA studies show that the well-ordered, structured RNAs perform a broad functions in various biological mechanisms. Included among these functions are regulations of gene expression at multiple levels by diversified ribozymes and various RNA regulatory elements. The discovered microRNAs (miRNAs) with a distinct stem-loops are a new class of RNA regulatory elements. The prediction of those well-ordered folding sequences (WFS) associated with the RNA regulatory elements in genomic sequences is very helpful for our understandings of RNA-based gene regulations. We present here a new computational method in searching for the conserved WFS in genomes. In the method, the WFS is assessed by a quantitative measure E diff that is defined as the difference of free energies between the computed optimal structure (OS) and its corresponding optimal restrained structure where all the previous base pairings in the OS are forbidden. From those WFS with high E diff scores, the conserved WFS is determined by computing the maximal similarity score (MSS) between the two compared structures. In practice, we first search for those distinct WFS with high statistical significance in genomic sequences and then seek for those conserved WFS with high MSS. The potential and implications of our discoveries in the genome of Caenorhabditis elegans are discussed.

MOTIVATION: Growing evidence demonstrates that local well-ordered structures are closely correlated with cis-acting elements in the post-transcriptional regulation of gene expression. The prediction of a well-ordered folding sequence (WFS) in genomic sequences is very helpful in the determination of local RNA elements with structure-dependent functions in mRNAs. RESULTS: In this study, the quality of local WFS is assessed by the energy difference (E(diff)) between the free energies of the global minimal structure folded in the segment and its corresponding optimal restrained structure (ORS). The ORS is an optimal structure under the condition in which none of the base-pairs in the global minimal structure is allowed to form. Those WFSs in HIV-1 mRNA, various ferritin mRNAs and genomic sequences containing let-7 RNA gene were searched by a novel method, ed_scan. Our results indicate that the detected WFSs are coincident with known Rev response element in HIV-1 mRNA, iron-responsive elements in ferritin mRNAs and small let-7 RNAs in Caenorhabditis elegans, Caenorhabditis briggsae and Drosophila melanogaster genomic sequences. Statistical significance of the WFS is addressed by a quantitative measure Zscr(e) that is a z-score of E(diff) and extensive random simulations. We suggest that WFSs with high statistical significance have structural roles involving their sequence information. AVAILABILITY: The source code of ed_scan is available via anonymous ftp as ftp://ftp.ncifcrf.gov/pub/users/shuyun/scan/ed_scan.tar.

The RNA pseudoknot has been proposed as a significant structural motif in a wide range of biological processes of RNAs. A pseudoknot involves intramolecular pairing of bases in a hairpin loop with bases outside the stem of the loop to form a second stem and loop region. In this study, we propose a method for searching and predicting pseudoknots that are likely to have functional meaning. In our procedure, the orthodox hairpin structure involved in the pseudoknot is required to be both statistically significant and relatively stable to the others in the sequence. The bases outside the stem of the hairpin loop in the predicted pseudoknot are not entangled with any formation of a highly stable secondary structure in the sequence. Also, the predicted pseudoknot is significantly more stable than those that can be formed from a large set of scrambled sequences under the assumption that the energy contribution from a pseudoknot is proportional to the size of second loop region and planar energy contribution from second stem region. A number of functional pseudoknots that have been reported before can be identified and predicted from their sequences by our method.

We have developed a method for detecting more stable and significant folding regions relative to others in the sequence. The algorithm is based on the calculation of the lowest free energy of RNA secondary structures and Monte Carlo simulation. For any given RNA segment, the stability and statistical significance of RNA folding are assessed by two measures: the stability score and the significance score. The stability score measures the degree of thermodynamic stability of the segment between all possible biological segments in the RNA sequence. The significance score characterizes the specific arrangement of the nucleotides in the segment that could imply a structural role for the sequence information. Using these two measures, we are able to detect a series of distinct folding regions where highly stable and statistically significant secondary structures occur in human immunodeficiency virus (HIV) and simian immunodeficiency virus (SIV) sequences.

In our recent series of papers, we have used the structures of statistical significance from Monte Carlo simulations to improve the predictions of secondary structure of RNA and to analyze the possible role of locally significant structures in the life cycle of human immunodeficiency virus. Because of intensive computational requirements for Monte Carlo simulation, it becomes impractical even using a supercomputer to assess the significance of a structure with a window size greater than 200 along an RNA sequence of 1000 bases or more. In this paper, we have developed a new procedure that drastically reduces the time needed to assess the significance of structures. In fact, the efficiency of this new method allows us to assess structures on the VAX as well as the CRAY.

A method for assessing the preserved stem-loops of RNA secondary structures is presented. Frequently recurring helical stems in a set of secondary structures resulting from the simulated folding process of a given RNA are assessed and consensus structural motifs can then be selected to construct a secondary structure of the RNA. Alternatively, it can be applied to a series of 'optimal' and 'suboptimal' secondary structures computed using the dynamic program developed by Williams and Tinoco. To demonstrate the power and the usefulness of the program we give examples of this procedure.

We describe a program for the analysis of RNA secondary structure. There are two new features in this program. (i) To get vector speeds on a vector pipeline machine (such as Cray X-MP/24) we have vectorized the secondary structure dynamic algorithm. (ii) The statistical significance of a locally 'optimal' secondary structure is assessed by a Monte Carlo method. The results can be depicted graphically including profiles of the stability of local secondary structures and the distribution of the potentially significant secondary structures in the RNA molecules. Interesting regions where both the potentially significant secondary structures and 'open' structures (single-stranded coils) occur can be identified by the plots mentioned above. Furthermore, the speed of the vectorized code allows repeated Monte Carlo simulations with different overlapping window sizes. Thus, the optimal size of the significant secondary structure occurring in the interesting region can be assessed by repeating the Monte Carlo simulation. The power of the program is demonstrated in the analysis of local secondary structures of human T-cell lymphotrophic virus type III (HIV).

Current secondary structure prediction computations have a serious drawback. The calculated thermodynamically most stable structure often differs from that observed in solution or in crystal form. In this paper we suggest a way to partially over-come some of these limitations by simulating the RNA folding process and calculating the frequencies of occurrence of the various substructures obtained. The frequently recurring substructures are then selected to construct the secondary structure of the whole RNA. 142 tRNA molecules and an E. coli 16S rRNA molecule have been examined by this method. The percentage of successful prediction of the correct helices are significantly higher than those calculated previously. The secondary structures of intervening sequences (IVSs) excised from human alpha-like globin pre-mRNAs are also computed. Thus, in this method the secondary structures obtained are composed of the statistically more significant substructures. This has also been demonstrated by using randomly shuffled sequences. The secondary structures of each of the randomized sequences are computed and their mean and standard deviations are used in evaluating the significance of the substructures obtained in the folding of the biological sequence. Some potentially appealing structural features aligning adjacent exons for ligation have been found.