A graph-theoretic algorithm for comparative modeling of protein structure
A graph-theoretic algorithm for comparative modeling of protein structure
复制标题
DOI：
10.1006/jmbi.1998.1689
复制
发表时间：
1998-05-29
影响因子：
5.6
通讯作者：
Moult, J
中科院分区：
文献类型：
--
作者：
Samudrala, R;Moult, J
蛋白质结构中相互作用的相互联系性质似乎是阻止建立准确比较模型的主要障碍。我们提出了一个用图论来处理这个问题的算法。氨基酸序列中残基的每一种可能构象都用图中节点的概念来表示。每个节点根据其侧链原子与局部主链原子之间的相互作用程度赋予权重。然后在彼此一致的残馀构象/节点对之间绘制边缘（即无冲突且满足几何约束）。根据两个节点的原子之间的相互作用对边缘进行加权。一旦构建了整个图，使用团查找算法找到所有完全连接节点（团）的最大集。考虑到各自的环境，具有最佳权值的团表示各种主链和侧链可能性的最佳组合。该算法用于比较建模场景，以上下文敏感的方式构建侧链、主链区域以及不同同源物之间的混合匹配。通过将该方法应用于事先不知道实验结构的情况来评估该方法的预测能力。(C) 1998学术出版社有限公司
The interconnected nature of interactions in protein structures appears to be the major hurdle in preventing the construction of accurate comparative models. We present an algorithm that uses graph theory to handle this problem. Each possible conformation of a residue in an amino acid sequence is represented using the notion of a node in a graph. Each node is given a weight based on the degree of the interaction between its sidechain atoms and the local main-chain atoms. Edges are then drawn between pairs of residue conformations/nodes that are consistent with each other (i.e. clash-free and satisfying geometrical constraints). The edges are weighted based on the interactions between the atoms of the two nodes. Once the entire graph is constructed, all the maximal sets of completely connected nodes (cliques) are found using a clique-finding algorithm. The cliques with the best weights represent the optimal combinations of the various main-chain and side-chain possibilities, taking the respective environments into account. The algorithm is used in a comparative modeling scenario to build side-chains, regions of main chain, and mix and match between different homologs in a context-sensitive manner. The predictive power of this method is assessed by applying it to cases where the experimental structure is not known in advance. (C) 1998 Academic Press Limited.