Abstract

Recent discoveries highlight RNA's biological significance, far beyond its traditional role in protein production. RNA also has the same synthetic potential as DNA in applications such as nanotechnology and biomolecular computing. Naturally single-stranded, an RNA sequence self-bonds. These nucleotide pairings, or secondary structure, largely determine the molecule's overall shape and functionality. Algorithmic questions regarding RNA secondary structures include design, analysis, and prediction. These are important problems at the rapidly developing intersection of the biological, mathematical, and computational sciences.
Solutions to the RNA design question are sequences which fold to a specified secondary structure. This inverts the typical computational problem of predicting a set of base pairs from a nucleotide sequence. We give a constructive method which reduces a special case of the design problem to a coding theory question. In this context, we analyze the potential configurations of simple RNA sequences through their graphical representation as weighted plane trees. We give results regarding strings encoding plane trees, bounds on loop energies, and the combinatorial relationship among different configurations. We also discuss the broader implications of our work in understanding this complex biological problem.

Dr. Christine Heitsch is a postdoctoral fellow at the University of Wisconsin -- Madison, funded by the National Library of Medicine training grant, "Computation and Informatics in Biology and Medicine." An interdisciplinary researcher, she is affiliated with both the UW Madison Department of Chemistry and the Mathematics Department. Previously, Dr. Heitsch had been a postdoc in the theory group of the Department of Computer Science at the University of British Columbia. She received her Ph.D. in Mathematics from the University of California at Berkeley, writing a dissertation under the direction of John Rhodes. Her current research interests focus on problems at the juncture of discrete mathematics, theoretical computer science, and computational biology.