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

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

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.