This project concerns the development of efficient algorithms and programs for RNA structure prediction, using both established models of RNA structure and dynamics, and emerging new models. Computational RNA structure prediction is a classic area of research, starting more than thirty years ago, and yet it is still a vital and open area. The motivation for this project is based on three fairly recent developments. First, in the last decade, there has been a huge growth in understanding of the varied biological roles and properties of RNA. Second, there has been recent, yet still limited, progress on experimentally determining new RNA structures and dynamics. Finally, and most central to this project, there have been recent theoretical and practical advances in the time and space-efficiency of solutions to classic problems of RNA structure prediction. This also points to the fact that additional powerful algorithmic techniques developed in the computer science community have not been fully exploited (or in some cases ever applied) to problems of RNA structure prediction. This provides a clear and compelling opportunity to improve computational RNA structure prediction, i.e., through improvement in the efficiency (in time and space) of computational methods, and by incorporating new biological and structural insights into the formulation of computational models and problems.

This project will improve the efficiency of algorithms for a variety of RNA structure prediction problems through the further development and exploitation of known, powerful algorithmic techniques that have not been previously introduced or fully exploited in addressing RNA structure problems. The project will also provide implementations of these ideas as computer programs and empirically validate the theory. The project will also articulate new computational problems and models for RNA structure and dynamics, driven by new and emerging biological and structural results.

National Science Foundation (NSF)
Division of Information and Intelligent Systems (IIS)
Standard Grant (Standard)
Application #
Program Officer
Sylvia Spengler
Project Start
Project End
Budget Start
Budget End
Support Year
Fiscal Year
Total Cost
Indirect Cost
University of California Davis
United States
Zip Code