III: Small: Algorithms and Computations for RNA Structure Prediction

该项目涉及开发RNA结构预测的有效算法和程序，使用已建立的RNA结构和动力学模型以及新兴的新模型。计算RNA结构预测是一个经典的研究领域，始于三十多年前，但它仍然是一个至关重要的开放领域。这个项目的动机是基于最近的三个发展。首先，在过去的十年中，人们对RNA的各种生物学作用和特性的理解有了巨大的增长。其次，最近在实验确定新的RNA结构和动力学方面取得了进展，但仍然有限。最后，也是本项目最核心的，最近在解决RNA结构预测经典问题的时间和空间效率方面取得了理论和实践上的进展。这也指出了一个事实，即计算机科学界开发的其他强大的算法技术尚未被充分利用（或在某些情况下应用）来解决RNA结构预测问题。这为改进计算RNA结构预测提供了一个明确而引人注目的机会，即通过提高计算方法的效率（在时间和空间上），并通过将新的生物学和结构见解纳入计算模型和问题的制定中。该项目将通过进一步开发和利用已知的、强大的算法技术来提高各种RNA结构预测问题的算法效率，这些算法技术以前没有被引入或完全用于解决RNA结构问题。该项目还将提供这些想法作为计算机程序的实现，并在经验上验证理论。该项目还将阐明新的计算问题和RNA结构和动力学模型，由新的和新兴的生物学和结构结果驱动。

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.