Distancebased Graph Linearization and Sampled Maxsum Algorithm for Efficient 3D Potential Decoding of Macromolecules
Search this article
Abstract
Threedimensional 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 maxsum search algorithm combined with samplings. It is referred to as Slice Chain MaxSum 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.Threedimensional 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 maxsum search algorithm combined with samplings. It is referred to as Slice Chain MaxSum 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.
Journal

 研究報告バイオ情報学（BIO）

研究報告バイオ情報学（BIO） 2011 (5), 18, 20110906
 Tweet
Details

 CRID
 1571698601990259072

 NII Article ID
 110008605709

 NII Book ID
 AA12055912

 Text Lang
 en

 Data Source

 CiNii Articles