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探测的空间原子相互作用，目标是计算与实验数据和生物物理约束一致的结构。这两个问题是蛋白质结构研究中许多其他重要应用的基础。