Discovery of RNA structural elements using evolutionary computation

Abstract

RNA molecules fold into characteristic secondary and tertiary structures that account for their diverse functional activities. Many of these RNA structures, or certain structural motifs within them, are thought to recur in multiple genes within a single organism or across the same gene in several organisms and provide a common regulatory mechanism. Search algorithms, such as RNAMotif, can be used to mine nucleotide sequence databases for these repeating motifs. RNAMotif allows users to capture essential features of known structures in detailed descriptors and can be used to identify, with high specificity, other similar motifs within the nucleotide database. However, when the descriptor constraints are relaxed to provide more flexibility, or when there is very little a priori information about hypothesized RNA structures, the number of motif 'hits' may become very large. Exhaustive methods to search for similar RNA structures over these large search spaces are likely to be computationally intractable. Here we describe a powerful new algorithm based on evolutionary computation to solve this problem. A series of experiments using ferritin IRE and SRP RNA stem-loop motifs were used to verify the method. We demonstrate that even when searching extremely large search spaces, of the order of 10(23) potential solutions, we could find the correct solution in a fraction of the time it would have taken for exhaustive comparisons.

Figure 1

A schematic of the initialization process. Hits from an RNAMotif file are placed randomly into bins, where the bin size (B) is determined by the user (here B = 5). For initialization, the randomly generated bins are considered ‘parent’ bins (P). Each P is then used to generate O offspring bins with variation (see text). After initialization, the P + O bins are considered as one evolving population.

Figure 2

Structures of the human ferritin IRE (A and B) and structure of human SRP domain IV (C) found in the literature (20,23).

Figure 3

RNAMotif descriptors used IRE experiments 1–4 (A–C) and SRP experiments 5–10 (D–H). Descriptors (A–C) include the possibility for one potential mispair at the base of the upper stem (not shown). Descriptor (C) has unpaired nucleotides on the 3′ side of the stem in opposition to the original bulge providing the possibility for internal loops in the final product.

Figure 4

Alignment of the S.pyogenes and S.aureus SRP RNA domain IV structures discovered, relative to the four closest organisms found in the SRPDB. The top line of the alignment provides information on proposed base pairing for the S.pyogenes structure. The symbols ( and ) are used to denote the 5′ and 3′ sides of the helix, respectively.