Distance-based Factor Graph Linearization and Sampled Max-sum Algorithm for Efficient 3D Potential Decoding of Macromolecules
Distance-based Factor Graph Linearization and Sampled Max-sum Algorithm for Efficient 3D Potential Decoding of Macromolecules
复制标题
DOI：
10.2197/ipsjtbio.4.34
复制
发表时间：
2011-09
影响因子：
--
通讯作者：
T. Shinozaki;Toshinao Iwaki;Shiqiao Du;M. Sekijima;S. Furui
中科院分区：
文献类型：
--
作者：
T. Shinozaki;Toshinao Iwaki;Shiqiao Du;M. Sekijima;S. Furui
分子的三维结构预测可以被建模为势能面上的最小能量搜索问题。基于这种形式化的流行的从头计算结构预测方法是以大都会方法为代表的蒙特卡罗方法。然而，对于较大的分子（如蛋白质），它们的预测性能会下降，因为搜索空间与原子数呈指数关系。为了更有效地搜索指数空间，我们提出了一种新的方法建模的潜在景观作为一个因素图。其核心思想是根据键合原子的最大距离对因子图进行切片，将其转化为线性结构图，并利用最大和搜索算法结合采样。它被称为切片链最大和，它的优点是搜索是有效的，因为图是线性的。使用具有50至300个氨基酸残基的多肽进行实验。它已被证明，所提出的方法是更有效的计算比大都会方法的大分子。
Three-dimensional structure prediction of a molecule can be modeled as a minimum energy search problem in a potential landscape. Popular ab initio structure prediction approaches based on this formalization are the Monte Carlo methods represented by the Metropolis method. However, their prediction performance degrades for larger molecules such as proteins since the search space is exponential to the number of atoms. In order to search the exponential space more efficiently, we propose a new method modeling the potential landscape as a factor graph. The key ideas are slicing the factor graph based on the maximum distance of bonded atoms to convert it to a linear structured graph, and the utilization of the max-sum search algorithm combined with samplings. It is referred to as Slice Chain Max-Sum and it has an advantage that the search is efficient because the graph is linear. Experiments are performed using polypeptides having 50 to 300 amino acid residues. It has been shown that the proposed method is computationally more efficient than the Metropolis method for large molecules.