Computational Genomics Using Graph Theory

With exciting new discoveries concerning RNA's regulatory cellular roles in gene expression, structural and functional problems associated with DNA's venerable cousin have come to the forefront. RNA folding, for example, is analogous to the well-known protein folding problem, and seeks to link RNA's primary sequence with secondary and tertiary structures. As a single-stranded polynucleotide, RNA's secondary structures are defined by a network of hydrogen bonds, which lead to a variety of stems, loops, junctions, bulges, and other motifs. Supersecondary pseudoknot structures can also occur and, together, lead to RNA's complex tertiary interactions stabilized by salt and solvent ions in the natural cellular milieu. Besides folding, challenges in RNA research include identifying locations and functions of RNA genes, discovering RNA's structural repertoire (folding motifs), designing novel RNAs, and developing new antiviral and antibiotic compounds composed of, or targeting, RNAs. In this talk, I will describe some of these new biological findings concerning RNA and present an approach using graph theory (network theory) to represent RNA secondary structures. Because the RNA motif space using graphs is vastly smaller than RNA's sequence space, many problems related to analyzing and discovering new RNAs can be simplified and studied systematically. Some preliminary applications to designing novel RNAs will also be described.\newline\newline Related Reading\newline H. H. Gan, S. Pasquali, and T. Schlick, ``A Survey of Existing RNAs using Graph Theory with Implications to RNA Analysis and Design,'' Nuc. Acids Res. 31: 2926--2943 (2003). J. Zorn, H. H. Gan, N. Shiffeldrim, and T. Schlick, ``Structural Motifs in Ribosomal RNAs: Implications for RNA Design and Genomics,'' Biopolymers 73: 340--347 (2004). H. H. Gan, D. Fera, J. Zorn, M. Tang, N. Shiffeldrim, U. Laserson, N. Kim, and T. Schlick,``RAG: RNA-As-Graphs Database -- Concepts, Analysis, and Features,'' Bioinformatics 20: 1285--1291 (2004). U. Laserson, H. H. Gan, and T. Schlick, ``Searching for 2D RNA Geometries in Bacterial Genomes,'' Proceedings of the ACM Symposium on Computational Geometry, June 9--11, New York, pp. 373--377 (2004). (http://socg.poly.edu/home.htm). N. Kim, N. Shiffeldrim, H. H. Gan, and T. Schlick, ``Novel Candidates of RNA Topologies,'' J. Mol. Biol. 341: 1129--1144 (2004). Schlick, ``RAG: RNA-As-Graphs Web Resource,'' BMC Bioinformatics 5: 88--97 (2004) (http://www.biomedcentral.com/1471-2105/5/88). S. Pasquali, H. H. Gan, and T. Schlick, ``Modular RNA Architecture Revealed by Computational Analysis of Existing Pseudoknots and Ribosomal RNAs,'' Nucl. Acids Res., Submitted (2004). T. Schlick, Molecular Modeling: An Interdisciplinary Guide, Springer-Verlag, New York, 2002.