Contraction Graphs: A Unified Representation and Analysis of RNA Secondary Structure
Chris Ding, Xiaofeng He, and Stephen R. Holbrook
Lawrence Berkeley National Laboratory

The secondary structure of RNA is critical in defining its shape and function and can be predicted directly from sequence. RNA secondary structures are conventionally described by tree graphs or dual graphs. Tree graphs describe common RNA secondary structures, while dual graphs can represent more complicated structural motifs such as RNA pseudoknots. A graph representation allows structure searching, structure enumeration, and new motif discovery for RNA to be conveniently carried out. We propose a unified graph representation of RNA secondary structure using graphs generated by a novel multi-level contraction graph process. Initially, a particular RNA is represented as a directed graph, proceeding from 5' to 3' end, where nodes represent nucleotides and directed edges represent covalent links along the RNA backbone. In the first stage, we contract base-paired nucleotides into a single node, describing a double helix or stem in RNA structure. At the second stage, we contract consecutive paired residues along the double helix and single stranded regions in internal, junction and hairpin loops. At the third stage, tree graphs are obtained by further contracting adjacent loop residues into a single node, or, dual graph are obtained by further contracting double helical stems into a node. In this manner, pseudoknots come about naturally. This new graph representation has a number of advantages over traditional tree and dual graphs. Depending on the detail required in a particular problem, there are several levels in the contraction graph for a RNA structure, instead of just one level of detail in tree and dual graphs. Using a directed graph, the contraction process preserves flow conservation. The 5' and 3' ends are now easily recognized as the nodes where flow conservation is broken; in tree and dual graphs, they are simply ignored. Besides clarity of graph construction and mathematical consistency, the contraction graph can also incorporate more information than the tree and dual graphs. For example, we can create "stacking" contracted graphs to indicate certain nucleotides are stacking on top of each other, "co-axial" contraction graphs to indicate certain nucleotides are part of an extended coaxial helix, or "tertiary" contraction graphs to indicate tertiary interactions.

Identifying microRNAs in Plant Genomes
Christopher Maher, Marja Timmermans, Lincoln Stein, and Doreen Ware
Cold Spring Harbor

The ability to control gene expression during development in plants could be used for improving crop yields, resistance to disease, and environmental adaptability. It has been suggested that microRNAs, or miRNAs, control developmental processes such as meristem cell identity, organ polarity, and developmental timing by interfering with the expression of mRNAs. MicroRNAs are 20-22 nucleotide sequences that arise from processing of larger precursor sequences transcribed from non-protein-coding genes by a ribonuclease III-like nuclease known as DICER- LIKE (dcl1). Our preliminary analysis focuses on the miR166 family since it has been shown to mediate repression of rolled-leaf1 (rdl1) in maize. Based on maize sequences derived from degenerate primers, we computationally identified miR166b, miR166c, miR166d, and four more closely related putative maize precursors. Patscan, a pattern-matching program that allows RNA basepairing and mismatches, was used to identify functional elements in the putative hairpins. Each hairpin was further supported by their stable secondary structures determined with Mfold. Since many noncoding RNAs display sequence conservation amongst eukaryotic genomes, we expect the miR166 precursors to be conserved in multiple plant genomes. Through sequence alignment we demonstrate that the hairpin tends to be conserved between rice and maize whereas only the mature miRNA is conserved between arabidopsis and maize or rice. By expanding the precursor sequences and then aligning them together we have identified recently duplicated precursors, which is supported by their physical location near syntenic blocks between chromosomes. We intend on expanding our analysis of the miR166 family into other microRNA families across multiple plant genomes.

Return to Poster Abstract Index
Return to Top

Fine-Grain Matrix Graph Representation for Predicting Mutations Leading to Conformational Rearrangements in Small RNAs
Assaf Avihoo, Nir Dromi, and Danny Barash
Computer Science Department, Ben-Gurion University

Previously, it was shown that predicting selective mutations leading to topological transitions in the secondary structure of RNAs can be achieved by a coarse-grain Laplacian matrix tree-graph representation using its second eigenvalue. The coarse-grain tree graph representation, initiated by Shapiro, is capable of predicting mutations leading to conformational rearrangements in RNAs of about 50 nt and higher. However, for small RNAs, such representations at the level of stems, bulges, and loops become ineffective. Recently, there is an interest in investigating secondary structure rearrangements in small RNAs following their structural probing by comparative imino proton NMR spectroscopy. For computational predictions of mutations leading to the structure rearrangements of small RNAs, it is necessary to use a fine-grain graph representation as initiated by Waterman at the level of nucleotides. Each nucleotide becomes a node in the graph and its equivalent Laplacian matrix is of the size NxN for a sequence of N nucleotides. Conformational rearrangements caused by mutations can be studied using measures to assess the differences between Laplacian matrices of fine-grain graph representations. The second eigenvalue of the Laplacian matrix can be used to filter mutations that led to a structure similar to the wildtype. Image analysis techniques, by moving a sliding window over Laplacian matrices, can facilitate in differentiating between local rearrangements and global rearrangements.

Return to Poster Abstract Index
Return to Top