This proposal considers the problem of computational folding and detection of noncoding RNA genes in DNA sequences. RNA genes are among the most important biological features in DNA, but at the same time they are very challenging to detect experimentally or computationally. There is a significant body of work in algorithms and tools for folding and detecting RNA genes. Their practical application is limited, however, because of high computational demands. At the same time, recent advances in DNA sequencing, such as the completion of the entire human, mouse, and rat genomes, suggest that sequence comparison is a promising direction. Unfortunately, comparison-based algorithms are considerably more time-consuming. The goal of this research is to develop a framework, and a collection of individual algorithms and tools, for efficient folding and detection of noncoding RNA genes. New algorithms that are significantly more efficient than existing ones will be developed by exploring the structural properties of RNA genes and excluding a large set of "unlikely structures" from the search space of possible configurations. The added efficiency will allow development of more accurate algorithms, practical application at a whole-genome scale on the human genome, and development of algorithms based upon sequence comparison. This research will help educate students at the undergraduate and graduate levels. Undergraduate students through the CURIS undergraduate research program at the Computer Science department will be part of the project, located at the Clark Center, which is part of the BioX initiative whose goal is to foster cooperation across disciplines such as biology and computer science, and to educate a new generation of students that will be "bilingual" in computational and biological sciences. Software will be disseminated.
