课题基金 / 基金详情

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

AF:Small:Collaborative Research: Algorithmic Problems in Protein Structure Studies
AF:Small:协作研究:蛋白质结构研究中的算法问题
批准号:
0915916
负责人:
Gopal Pandurangan
金额:
$22.5万
依托单位:
依托单位国家:
美国
项目类别:
Standard Grant
财政年份:
2009
资助国家:
美国
项目状态:
已结题
起止时间:
2009-09-01 至 2010-05-31

项目摘要

项目成果

Gopal Pandurangan的其他基金

相似基金

相关文献

中文摘要
翻译
该研究涉及设计和分析在蛋白质三维结构研究中出现的基本问题的有效算法。图论问题是这些研究的基础,因为蛋白质结构自然地(而且充分地)用图来表示,图的顶点是单个氨基酸残基,边缘是紧密对之间的。然而,图论的形式化导致了难以计算的优化问题,实验数据中大量的噪声使问题进一步复杂化。受到核磁共振波谱学和其他蛋白质结构研究中的具体挑战的激励,该项目解决了两个重要的算法问题:识别一对图之间的对应关系,其中一个是另一个的严重损坏版本,并确定图的顶点的三维坐标,给出其边缘的近似噪声距离测量。第一个算法问题是图匹配的一种形式,该项目侧重于开发有效的搜索算法来发现对应关系,使用随机图模型严格分析算法并研究表征对噪声鲁棒性的阈值现象。在核磁共振数据分析的应用中,其中一个图表示蛋白质,另一个图表示数据,这是一组嘈杂的、模糊的原子相互作用;目标是将核磁共振识别的相互作用与蛋白质中特定的原子相互作用相匹配。第二个算法问题是稀疏几何图的欧几里得嵌入,该研究涉及到使稀疏几何图适用于低秩距离矩阵重构方法的算法开发,推广重构方法以利用底层几何结构并考虑混杂噪声结构。在核磁共振设置中,该图表示核磁共振探测通过空间原子相互作用,目标是计算与实验数据和生物物理约束一致的结构。这两个问题都是蛋白质结构研究中许多其他重要应用的基础。
英文摘要
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.
期刊论文(0)
专著(0)
科研奖励(0)
会议论文
Collaborative Research: AF: Medium: The Communication Cost of Distributed Computation
  • 批准号:
    2402837
  • 项目类别:
    Continuing Grant
  • 资助金额:
    $33.26万
  • 财政年份:
    2024
  • 负责人:
    Gopal Pandurangan
  • 依托单位:
CCF-BSF: AF:Small: Time-Message Tradeoffs in Distributed Algorithms
  • 批准号:
    1717075
  • 项目类别:
    Standard Grant
  • 资助金额:
    $46.26万
  • 财政年份:
    2017
  • 负责人:
    Gopal Pandurangan
  • 依托单位:
BIGDATA: Collaborative Research: F: Efficient Distributed Computation of Large-Scale Graph Problems in Epidemiology and Contagion Dynamics
  • 批准号:
    1633720
  • 项目类别:
    Standard Grant
  • 资助金额:
    $54.99万
  • 财政年份:
    2016
  • 负责人:
    Gopal Pandurangan
  • 依托单位:
BSF:2014424:Time-Message Tradeoffs in Distributed Algorithms
  • 批准号:
    1540512
  • 项目类别:
    Standard Grant
  • 资助金额:
    $5.0万
  • 财政年份:
    2015
  • 负责人:
    Gopal Pandurangan
  • 依托单位:
国内基金
海外基金
昼夜节律性small RNA在血斑形成时间推断中的法医学应用研究
  • 批准号:
  • 项目类别:
    省市级项目
  • 资助金额:
    --
  • 批准年份:
    2024
  • 负责人:
  • 依托单位:
tRNA-derived small RNA上调YBX1/CCL5通路参与硼替佐米诱导慢性疼痛的机制研究
  • 批准号:
  • 项目类别:
    省市级项目
  • 资助金额:
    10.0万元
  • 批准年份:
    2022
  • 负责人:
    张祥忠
  • 依托单位:
Small RNA调控I-F型CRISPR-Cas适应性免疫性的应答及分子机制
Small RNAs调控解淀粉芽胞杆菌FZB42生防功能的机制研究
  • 批准号:
    31972324
  • 项目类别:
    面上项目
  • 资助金额:
    58.0万元
  • 批准年份:
    2019
  • 负责人:
    高学文
  • 依托单位: