Practical Approach To Protein Structure Prediction

Protein structure prediction is one of the central problems in the field of computationalbiology and one of the most demanding tasks of protein engineering in post-genome era.Meanwhile, the protein structure prediction problem remains to be NP-Hard even for itsmost simplified model. Therefore, it is a challenging task to study the problem of proteinstructure prediction.For NP-Hard problems, we are forced to go on one of three ways. One is accurate algo-rithms that are employed to produce an optimal solution in an enumerative way. However,under the widely believed conjecture that P=NP, the exponential complexity of accuratealgorithms have limited themselves only to theoretical analysis or small size applications.As an alternative to solving NP-Hard problems to optimality, a stream of research has con-centrated on polynomial-time approximate algorithms with performance guarantee, i.e., anupper bound on the ratio between the approximate solution quality and the optimal one.The third way is to design practically efficient heuristic or meta-heuristic algorithmsfor solving NP-Hard problems. Heuristic algorithms seek for high quality solutions at areasonable computational time, and they can also be considered as intelligent techniquesthat are based upon human intuition, which often comes out as a result of analogies withphysical world, human experience or biological phenomena. Quasi-physical and quasi-human algorithm is one of the most effective methods for solving NP-Hard problems, whichis inspired by the wisdom from physical phenomenon and human experience. For proteinstructure prediction problem, the main focus of current research is to design highly efficientheuristic and meta-heuristic optimization algorithms.Two of the simplified models for protein structure prediction, called HP lattice modeland AB off-lattice model, respectively, are studied. For HP lattice model, PERM algorithmis not succinct and can not be naturally explained, while for AB off-lattice model, no appro-priate heuristic algorithms have been reported. Besides, for both models, the computational performance of the previously proposed algorithms in literature still needs to be improved.For HP lattice model, PERM (Pruned-Enrichment Rosenbluth Method) is recognizedto be the most efficient algorithm in literature for solving the protein structure predictionproblem based on this model. A personification explanation of PERM is proposed basedupon introducing PERM, which makes PERM algorithm naturally explained. A new versionof PERM, population control algorithm, with two main improvements is presented: one isthat it redefines the weight and the predicted value in PERM, and the other is that it is ableto unify the calculation of weight when choosing possible branches. Further personificationimprovement strategy is proposed, that is, predicted value of weight is redefined using thepersonification ideas. The further improved PERM algorithm not only considers the typesof amino acids (H or P), but also takes into account the position of the current amino acid inthe protein chain during the chain growth procedure.The merits of the two improved PERM algorithms can be generalized as the followingthree points: Firstly, the improved PERM is more efficient than the previous version nPER-Mis (new PERM importance sampling) and is generally several to hundreds times fasterthan nPERMis. Secondly, for a standard benchmark instance with length equal to 103, itcan find lower energy (-55) than that nPERMis can find (-54). Finally, for a standard bench-mark instance with length equal to 46, it can find lower energy (-35) than the previously bestresult (-34) in literature.For AB off-lattice model, an appropriate physical model—–spring model—–is pro-posed to simulate the original problem, based on which the original constraint optimizationproblem can be converted into an unconstraint one. Then a corresponding quasi-physical al-gorithm is provided to solve the protein structure prediction problem based on AB off-latticemodel, whose main ideas are based on the proposed physical model.The merits of the proposed quasi-physical algorithm and its computational results canbe concluded as the following three points: First of all, the proposed quasi-physical ideais perfectly appropriate for the original problem. Secondly, based on the initial solutionsgenerated on SC-HP lattice model, the quasi-physical algorithm can produce higher qualitysolutions than PERM+ method which utilizes PERM to generate initial solutions and sub- sequently a conjugate gradient method is employed to improve them. Finally, based on theinitial solutions generated by ELP (Energy Landscape Paving) algorithm, the quasi-physicalalgorithm is superior to a number of famous algorithms in literature for most of the standardbenchmark instances.Above results indicate that quasi-physical and quasi-human strategy is one of the mostefficient and effective approaches for solving protein structure prediction problem. Furtherresearch work will be focused on the high-efficient heuristic algorithms for more realisticprotein structure prediction models, so as to apply them to the practical protein engineeringin the near future. Meanwhile, following the path of quasi-physical quasi-human strategies,it is promising to design high-efficient heuristic algorithms for solving other NP-Hardproblems.