Graph tree decomposition enabled biopolymer folding
MetadataShow full item record
Biopolymer tertiary structure prediction by computer programs plays a very important role in complementing the experimental determination method. There are two structure prediction approaches: template-based and ab initio predictions. Due to the nature of residue interactions in biopolymer tertiary structures, both prediction approaches are required to perform intensive computations. Previous research has discovered a small treewidth property for interaction topology graphs of biopolymer tertiary structures, rendering the opportunity to speed up the combinatorial computation needed by the predictions with graph tree decomposition based dynamic programming. In the current research, a heuristic strategy is developed to reduce the memory space usage for the dynamic programming. An application of this method to the template-based protein tertiary structure prediction is considered in detail. In addition, the method is extended as a step toward the ab initio prediction of biopolymer tertiary structures.