Samudrala R, Moult J
Center for Advanced Research in Biotechnology, University of Maryland Biotechnology Institute, Rockville 20850, USA.
J Mol Biol. 1998 May 29;279(1):287-302. doi: 10.1006/jmbi.1998.1689.
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 side-chain 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.
蛋白质结构中相互作用的内在联系似乎是阻碍构建精确比较模型的主要障碍。我们提出了一种利用图论来处理这个问题的算法。氨基酸序列中残基的每个可能构象都用图中节点的概念来表示。根据其侧链原子与局部主链原子之间的相互作用程度给每个节点赋予一个权重。然后在彼此一致（即无冲突且满足几何约束）的残基构象/节点对之间绘制边。边根据两个节点的原子之间的相互作用进行加权。一旦构建了整个图，就使用团查找算法找到所有完全连通节点的最大集（团）。权重最佳的团代表了各种主链和侧链可能性的最优组合，同时考虑了各自的环境。该算法用于比较建模场景，以上下文敏感的方式构建侧链、主链区域，并在不同同源物之间进行混合和匹配。通过将该方法应用于事先不知道实验结构的情况来评估其预测能力。
