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.