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

这项研究涉及对蛋白质三维结构研究中出现的基本问题进行有效算法的设计和分析。图论问题是这些研究的基础，因为蛋白质结构自然地(并且充分地)由具有单个氨基酸残基的顶点和紧密对之间的边的图来表示。然而，图论形式主义导致了计算困难的优化问题，实验数据中的大量噪声使优化问题进一步复杂化。在核磁共振波谱和其他蛋白质结构研究的特殊挑战的推动下，该项目解决了两个重要的算法问题：识别两个图之间的对应关系，其中一个图是另一个图的严重损坏版本，以及确定图的顶点的三维坐标，给定其边的近似、噪声距离测量。第一个算法问题是图匹配的一种形式，该项目专注于开发高效的搜索算法来发现对应关系，使用随机图模型来严格分析算法并研究具有噪声鲁棒性的阈值现象。在分析核磁共振数据的应用中，一个图形表示蛋白质，另一个表示数据，这是一组嘈杂的、模棱两可的原子相互作用；目标是将核磁共振识别的相互作用与蛋白质中的特定原子相互作用相匹配。第二个算法问题是稀疏几何图形的欧几里德嵌入问题，研究内容包括开发算法使稀疏几何图形服从低秩距矩阵重构方法，推广重构方法以利用底层几何结构并解释混杂的噪声结构。在核磁共振设置中，该图表示核磁共振探测的贯穿空间的原子相互作用，目标是计算与实验数据和生物物理约束一致的结构。这两个问题都是蛋白质结构研究中许多其他重要应用的基础。

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.