CAREER: Statistical methods and algorithms for the analysis of combinatorial mass spectrometry data

质谱学是一种重要的现代研究工具，它可以在几个尺度上分析样品的成分：核、小化学物质和生物分子。在生物研究中，质谱学被用于分析蛋白质(“蛋白质组学”)和代谢(“代谢组学”)数据，而在非研究领域，它被用于例如在机场例行安检中检测与炸弹有关的化学物质。这项研究解决了质谱仪数据处理中尚未满足的三个需求：第一个是生物样本中蛋白质的统计识别；这对于了解细胞的不同之处很重要，例如，皮肤细胞和血细胞的不同之处。第二个是确定样本中有哪些生物物种；这在诸如实现准确和自动化的疾病诊断等应用中至关重要。三是在样本中找到基本分子成分的“字母表”。这项研究通过开发新的算法和统计方法来解决这些目标，这些方法可以正确地分离复杂混合物的基本成分。从事这个项目的研究人员创建了数学工具，这些工具被实现为研究人员友好的软件工具，用于解决列出的问题。为了帮助科学和非科学受众更容易理解这些想法，研究人员将创建教学模块和播客节目来解释算法是如何工作的，以及开发了哪些数学技巧来分解问题的复杂性，使其能够得到有用的解决方案。组合相关性问题在质谱学中普遍存在。可以利用组合依赖中的对称性来构造特殊的动态规划算法：卷积树、快速数值最大卷积和其他方法，所有这些方法都是由研究人员发明和开发的。研究人员将使用并改进这些利用对称性的算法，以实现基于高级质谱学的蛋白质识别、物种分类和小分子分析。卷积树可以用来在准线性时间内解决这些问题，因此它们可以应用于非常大量的蛋白质、物种或小分子(或来自这些问题的大量光谱)。研究人员将构建这些算法的软件实现库，并允许开放源码许可，供不受限制的学术和工业使用。随着他们进一步开发这些组合方法，研究人员将创建一门组合学课程，以直观的方式向K-12学生教授这些概念，并制作播客节目，以便于理解的方式解释这些概念。这项研究的成果将在https://alg.cs.umt.edu/nsf-career.html上免费提供。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Mass spectrometry is a crucial modern research tool that allows analysis of the components of samples at several scales: nuclear, small chemicals and biological molecules. In biological research, mass spectrometry is used in the analysis of protein ("proteomics") and metabolic ("metabolomics") data, while in non-research areas it is deployed, for example, to detect bomb-associated chemicals in routine airport security screenings. This research addresses three unmet needs in the processing of the data from mass spectrometry machines: The first is statistical identification of proteins in a biological sample; this is important for understanding what makes cells different, e.g., what makes a skin cell different from a blood cell. The second is identification of which biological species are in a sample; this is crucial in applications such as, for example, enabling accurate and automated disease diagnostics. The third is finding the "alphabet" of basic molecular ingredients in a sample. This research addresses these aims by developing new algorithmic and statistical methods that can correctly separate the basic elements of a complex mixture. The researchers working on this project create mathematical tools that are implemented as researcher-friendly software tools for solving the listed problems. To help make the ideas more accessible to both scientific and non-scientific audiences, the researchers will create teaching modules and podcast episodes to explain how the algorithms work, and what math tricks were developed to break down the complexity of the problem so it is amenable to a useful solution.Problems with combinatorial dependencies are ubiquitous in mass spectrometry. Symmetries in combinatorial dependencies can be exploited to construct special dynamic programming algorithms: convolution trees, fast numeric max-convolution, and other approaches, all of which were invented and developed by the researchers. The researchers will use and improve these symmetry-exploiting algorithms to implement superior mass spectrometry-based protein identification, species classification, and small molecule analysis. Convolution trees can be used to solve these problems in quasilinear time, and so they can be applied to a very large number of proteins, species, or small molecules (or to a large number of spectra from any of these problems). The researchers will construct a library of software implementations of these algorithms with permissive open source licensing for unrestricted academic and industrial use. As they further develop these combinatorial methods, the researchers will create a combinatorics curriculum for intuitively teaching these concepts to K-12 students and create podcast episodes explaining these ideas in an accessible manner.The fruits of this research will be freely available at https://alg.cs.umt.edu/nsf-career.html .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.