Utah State University is awarded a grant to develop a hierarchical method for predicting RNA secondary structures with pseudoknots. The proposed method mirrors the natural hierarchy of RNA folding by considering both secondary structures and tertiary interactions, and strives for the right balance in rigor and tractability by combining approximation and heuristics at both helix and base-pair resolutions. The proposed method is based on two novel ideas: 2-interval graph and 3D triangular lattice. 2-interval graph models the computational paradigm of all existing helix-resolution algorithms; 3D triangular lattice is a novel lattice that is superior to other lattices in terms of regularity, density, and parity; the move sets for the simulation-based heuristics are both efficient and biologically relevant. This project employs clean mathematical objects and intuitive computational techniques that are attractive to students, and will help foster the new bioinformatics specialization of the computer science Ph.D. program at Utah State University. The target of the project is not only a specialized software system for a very important bioinformatics problem but also a set of tools, libraries, and application programming interfaces that will benefit the bioinformatics community in general. The 3D triangular lattice and the associated interactive tools for visualization and manipulation are excellent pedagogic devices for teaching biological sciences and computational techniques at all educational levels.
