EAGER: Breaking the Speed and Accuracy Barrier for Protein Property Prediction

蛋白质分子在细胞中折叠成的物理结构对于理解蛋白质在体内执行的功能至关重要。从组成蛋白质分子的氨基酸的基本序列预测这种折叠结构是分子生物学和生物信息学中的关键计算任务，并且由于其在生命科学和最终人类健康中的广泛影响，是计算机方法的密集研究的主题。该项目利用了研究人员最近在计算速度和算法准确性方面的突破，用于预测称为蛋白质二级结构的折叠结构的离散形式。该项目旨在进一步打破蛋白质二级结构预测的速度障碍，通过更快的方法进行数据库中称为最近邻搜索的基本算法步骤，并通过更准确的方法自动学习最近邻搜索中使用的邻近度来进一步打破准确性障碍。该项目将通过发布实现这些算法的开源软件工具、培养从事研究的博士生以及将这项研究融入大学水平的本科生和研究生生物信息学课程的教学中来影响国家基础设施，以实现更快、更准确的蛋白质二级结构预测和相关蛋白质性质预测任务的目标，该项目建立在完全不同的计算方法上，该方法放弃了所有当前最先进的方法所采用的昂贵的序列数据库同源性搜索，而是在距离度量下利用固定长度串上的最近邻搜索来估计残基结构概率，随后进行动态编程以计算全局最优、最大似然、物理有效的二级结构预测。为了进一步打破速度和准确性的障碍，该项目将开发新的更快的数据结构，用于距离度量下的字符串最近邻搜索的核心问题，以及距离度量学习的新的更准确公式，用于最近邻分类。最近邻搜索和距离度量学习的技术是通用的，这将在这些基本的计算问题上产生进展，超出了蛋白质性质预测的激励生物信息学应用。该奖项反映了NSF的法定使命，并被认为是值得通过使用基金会的智力价值和更广泛的影响审查标准进行评估的支持。

The physical structure that a protein molecule folds up into in the cell is critical to understanding the function that the protein performs in the body. Predicting this folded structure from the basic sequence of amino acids comprising the protein molecule is a key computational task in molecular biology and bioinformatics, and a subject of intense research into computer methods, due to its broad impact in the life sciences and ultimately human health. This project capitalizes on a recent breakthrough by the investigator in both the computational speed and accuracy of algorithms for predicting a discrete form of folded structure known as protein secondary structure. The project aims to further break the speed barrier for protein secondary structure prediction through faster methods for an essential algorithmic step called nearest neighbor search over a database, and to further break the accuracy barrier through more accurate methods for automatically learning the proximity measure used in nearest neighbor search. The project will impact national infrastructure through the release of open-source software tools implementing these algorithms, the training of doctoral students in research, and integrating this research into the teaching of university-level undergraduate and graduate bioinformatics courses.To achieve these goals for faster and more accurate protein secondary structure prediction and related protein property prediction tasks, the project builds on a radically-different computational approach that forgoes the costly sequence database homology searches employed by all current state-of-the-art methods, and instead leverages nearest neighbor search on fixed-length strings under a distance metric to estimate residue structure probabilities, followed by dynamic programming to compute a globally-optimal, maximum-likelihood, physically-valid, secondary structure prediction. To further break the speed and accuracy barrier, the project will develop new faster data structures for the core problem of nearest neighbor search on strings under a distance metric, and new more accurate formulations of distance metric learning for nearest-neighbor-like classification. The techniques for nearest neighbor search and distance metric learning are general, which would yield advances in these fundamental computational problems beyond the motivating bioinformatics applications of protein property prediction.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.