Depth Annotation of RNA Folds for Secondary Structure Motif Search

The biological activity of RNA depends on the way it folds into secondary structures. Presented here is a framework for exploratory motif searching in the space of RNA secondary structures. A collection of RNA sequences, suspected of having a particular biological activity, is fragmented into overlapping pieces of a uniform size. Each piece is folded and the details of the fold are used to annotate the primary structure. Distances between annotated structures are computed. The distance matrix for the structures is then projected into the Euclidean plane for visualization and detection of clusters. A motif is taken to be a cluster in the two dimensional space. An instance of the framework is implemented for testing on a data set containing examples of the Iron Response Element in the following manner. Folding is performed with the Mfold package. A depth-of-fold that records stems and loops onto the primary sequence is used to annotate the pieces of RNA. Dynamic programming is used to find distances between pieces of annotated primary sequence. An evolutionary algorithm is then used to find a one-to-one mapping of pieces of RNA to points in the plane that has acceptable distortion of the distances found with dynamic programming. This one-to-one mapping is a form of non-linear projection that optimizes for fidelity of projected distances to the distances derived from the Iron Response Element data set.