An Improved PERM Method for Protein Folding Problem of HP Model

Predicting the structure of a protein from its amino acid sequence is one of the central problems in computational biology. PERM (prunedenrichment Rosenbluth method) is an efficient algorithm for the protein folding problem based on HP lattice model. However, the PERM algorithm is not succinct and is not easily understood. Based on introducing the algorithm idea of PERM and the key factors affecting the efficiency of PERM, a new version of PERM with two improvements is proposed: one is that it redefines the weight and the predicted value in PERM, and the other is that it unifies the calculation of weight when choosing possible branches. The proposed formulae are more succinct and uniform and the algorithm idea is much clearer in the improved PERM. The computational result shows that the improved PERM can find the known lowest energy states for all the test instances. The improved PERM is generally several to hundreds times faster than PERM, and it is far more efficient than Monte Carlo. It is noteworthy that with the improved PERM, lower energy (-35) can be found than the previously best result (-34) in literature for one test instance with length equal to 46.