AF:Small:Collaborative Research: Algorithmic Problems in Protein Structure Studies

AF:Small:协作研究：蛋白质结构研究中的算法问题

• 批准号: 0915388
• 负责人: Christopher Bailey-Kellogg
• 金额: $ 22.5万
• 依托单位: Dartmouth College
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2009
• 资助国家: 美国
• 起止时间: 2009-09-01 至 2012-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0915388&HistoricalAwards=false
• 关键词: AF; Small; Collaborative; Research; Algorithmic

The research involves the design and analysis of efficient algorithms for fundamental problems that arise in studies of the three-dimensional structures of proteins. Graph-theoretic problems underlie these studies, since protein structures are naturally (and sufficiently) represented by graphs that have vertices for the individual amino acid residues and edges between close pairs. However, graph-theoretic formalisms lead to computationally hard optimization problems, further complicated by extensive amounts of noise in experimental data. Motivated by specific challenges in nuclear magnetic resonance spectroscopy and other protein structure studies, the project addresses two significant algorithmic problems: identifying correspondences between a pair of graphs where one is a significantly corrupted version of the other, and determining three-dimensional coordinates for the vertices of a graph, given approximate, noisy distance measurements for its edges. The first algorithmic problem is a form of graph matching, and the project focuses on developing efficient search algorithms to uncover correspondences, with random graph models to rigorously analyze the algorithms and study threshold phenomena characterizing robustness to noise. In an application to analysis of NMR data, one of the graphs represents the protein and the other the data, a noisy, ambiguous set of atomic interactions; the goal is to match the NMR-identified interactions with specific atomic interactions in the protein. The second algorithmic problem is Euclidean embedding for sparse geometric graphs, and the research involves development of algorithms to render such graphs amenable to low rank distance matrix reconstruction methods, generalizing the reconstruction methods to exploit the underlying geometric structure and account for the confounding noise structure. In the NMR setting, the graph represents NMR-probed through-space atomic interactions, and the goal is to compute structures consistent with the experimental data and biophysical constraints. Both problems are fundamental to numerous other significant applications in protein structure studies.

该研究涉及对蛋白质三维结构研究中出现的基本问题的有效算法的设计和分析。这些研究是基于这些研究的基础的图理论问题，因为蛋白质结构是自然（并且充分）的图表，这些图具有为单个氨基酸残基和近距离对之间的边缘的顶点的图。然而，图理论形式主义导致了计算上的硬性优化问题，从而使实验数据中的噪声大量噪声更加复杂。该项目以核磁共振光谱和其他蛋白质结构研究的特定挑战的启发，解决了两个重要的算法问题：确定一对图之间的对应关系，其中一个图是对方的显着损坏版本，并确定图形的三维坐标的图表，均具有近似，差不多的距离测量值。第一个算法问题是图形匹配的一种形式，该项目着重于开发有效的搜索算法以发现对应关系，随机图模型可严格分析算法并研究阈值现象，表征了对噪声的鲁棒性。在对NMR数据分析的应用中，其中一个图表示蛋白质，另一个图表是一组嘈杂的，模棱两可的原子相互作用。目的是将NMR识别的相互作用与蛋白质中的特定原子相互作用匹配。第二个算法问题是欧几里得嵌入稀疏的几何图，研究涉及开发算法以使这些图形呈现为低等级距离矩阵重建方法，从而推广重建方法以利用基础几何结构并计算混杂的噪声结构。在NMR设置中，该图代表通过空间原子相互作用进行的NMR探测，目标是计算与实验数据和生物物理约束一致的结构。这两个问题都是蛋白质结构研究中许多其他重要应用的基础。