CRII: III: RUI: Effective Protein Characterization via Fast Exact Open Modification Searching

蛋白质构成了细胞的主要组成部分，蛋白质与蛋白质的相互作用提供了有关细胞功能的信息。通过质谱（MS）可以表征这些相互作用，这是一种将复杂的生物样品分解为更简单的离子并测量其单个质量的技术。计算机算法可用于解释MS实验的输出。串联质谱（MS/MS）的出现，也被称为鸟枪蛋白质组学，导致研究人员执行蛋白质组学实验的速度大幅提高，这反过来又使包含数百万已知光谱的大型数据库得以创建。这项研究将创建新的算法，通过将样本中的未知光谱与整个已知光谱库进行比较，能够快速识别生物样本中存在哪些蛋白质。最终，该项目将使人类更容易理解疾病的分子基础，并将实现个性化医疗和识别新药来解决目前无法治愈的疾病。该项目的目标是开发用于MS/MS实验结果中蛋白质表征的新方法，该方法将提供更高的光谱匹配效率，同时扩展到搜索最大的现有蛋白质数据库及其他数据库。鸟枪法蛋白质组学的关键计算部分是将MS/MS光谱与光谱数据库中的理论光谱或实际光谱进行匹配，以识别可能的肽（蛋白质部分）。本质上，给定光谱到欧几里德空间中的点的平移和所选择的邻近函数，搜索中的算法组件是最近邻搜索算法。由于光谱数据库的规模很大，传统上已经通过各种近似最近邻搜索方法以及向量空间和概率邻近度量的组合来解决该问题，这些方法通常不可扩展并导致错过光谱匹配。本项目旨在通过两种方式解决这些限制。首先，它将开发新的基于过滤的精确最近邻搜索方法的移位点积邻近度测量，最近已被证明优于替代方案，占光谱翻译后修饰，同时搜索匹配。所提出的基于过滤的方法修剪大部分的搜索空间，消除潜在的候选人，而不计算其接近的查询，根据其组成和接近度的理论属性。其次，该项目将开发有效的分解技术，用于拟议的基于修剪的搜索的固有不规则计算要求，使分布式方法能够搜索当今及以后最大的蛋白质组学数据库。该项目将导致开发的方法传播到大型计算基因组学社区，并将涉及代表性不足的本科生的研究教育。该奖项反映了NSF的法定使命，并已被认为是值得通过使用基金会的智力价值和更广泛的影响审查标准进行评估的支持。

Proteins form the major building blocks of cells, and protein-protein interactions provide information about cell functions. Characterizing these interactions is made possible through mass spectrometry (MS), a technique that breaks down complex biological samples into much simpler ions and measures their individual masses. Computer algorithms can then be used to interpret the output of MS experiments. The advent of tandem mass spectrometry (MS/MS), also known as shotgun proteomics, led to a huge increase in the speed with which researchers can execute proteomics experiments, which in turn has enabled the creation of massive databases containing millions of known spectra. This research will create novel algorithms that will be able to quickly identify which proteins exist in a biological sample by comparing unknown spectra from the sample against entire libraries of known spectra. Ultimately, this project will make it easier for humans to understand the molecular basis of disease and will enable personalized medicine and identifying new drugs to tackle currently incurable diseases. The goal of this project is to develop novel methods for protein characterization in MS/MS experiment results that will provide increased spectral match effectiveness while scaling to search the largest existing protein databases and beyond. The key computational component in shotgun proteomics is matching MS/MS spectra against theoretical spectra or actual spectra in spectral databases to identify possible peptides (protein sections). In essence, given a translation of the spectra to points in the Euclidean space and a chosen proximity function, the algorithmic component in the search is a nearest neighbor search algorithm. Due to the large size of spectral databases, the problem has been traditionally solved through a variety of approximate nearest neighbor search methods and a combination of vector space and probabilistic proximity measures which are often not scalable and lead to missed spectral matches. This project aims to address these limitations in two ways. First, it will develop novel filtering-based exact nearest neighbor search methods for the shifted dot-product proximity measure, which has been recently shown to outperform alternatives by accounting for spectral post translational modifications while searching for matches. The proposed filtering-based methods prune much of the search space by eliminating potential candidates without computing their proximity to the query, based on their composition and on theoretic properties of the proximity measure. Second, the project will develop effective decomposition techniques for the inherently irregular computation requirements of the proposed pruning-based search that will enable distributed methods to search the largest proteomics databases of today, and beyond. The project will result in the dissemination of the developed methods to the large computational genomics community and will involve research education of underrepresented undergraduate students.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.