Quasi-Physical Quasi-Human Algorithm For Protein Folding

Since the proteins'biological properties rest on their dimensional folding structures, the study of the proteins'structure is of great significance in theoretical structural biology. According to the research of Anfinsen et al, predicting the native structure of a protein from its amino acid sequence by using theoretical computing method is a feasible approach. The theoretical science community has introduced and examined several highly simplified models since the protein folding problem is too difficult to be approached with fully realistic potentials. Among the simplified models, HP model of Dill and AB model of Stillinger are the most popular ones and have been studied extensively. Even in these highly simplified models, it is not easy to predict the native state for the protein folding problem, which has been recognized to be NP-complete. As a NP hard problem, it means that there does not exist an algorithm that is complete, rigorous and efficient. Consequently, people hope to obtain a heuristic algorithm for solving NP hard problems that is not absolutely complete, but is of high speed, high reliability and high efficiency. Through the so-called quasi-physical and quasi-human strategy, we proposed some efficient and effective algorithms for solving the protein folding problems based on HP model and AB model, respectively.In order to reduce the search space, a pruning algorithm with random strategy was proposed to solve the two-dimensional protein folding problem based on HP model. In this algorithm, only the promising nodes are kept for further branching with certain probability, while those nodes not promising enough are pruned with certain probability. With this pruning algorithm, the search space is reduced and the corresponding search time is decreased accordingly.Based on pruning and enrichment strategy, PERM (pruned-enriched Rosenbluth method) is a kind of chain growth algorithm. By formulating some certain evaluation criteria, PERM enriches those promising branches and prunes those with poor quality so that the search space is reduced. Via analyzing PERM, the factors that essentially affect the efficiency of PERM were indicated, and then some further analyses from the personification explanation were made. PERM can be viewed as a population control strategy, by means of which, the quality of an individual is evaluated, and then a guideline on procreation of the individual can be obtained, thus realizing the aim of"go with the winners". With such a vivid background, a much more reasonable rule for evaluation was generated, and an improved version of PERM was proposed. Computational results indicate that the improved PERM performs efficiently with benchmarks of protein folding problem.Based on the quasi-physical idea, a new mathematical model including attraction potential and exclusion potential is constructed so that the three dimensional protein folding problem based on HP model is converted from a nonlinear constraint-satisfied problem to an unconstrained one. A heuristic algorithm based on local search strategy was proposed for solving the problem.A perfect physical model, that is, a mechanical system, is constructed for the three-dimensional AB mode-based protein folding problem. In this system, an amino acid monomer is regarded as a smooth elastic ball. Assume that the centers of any two successive balls along the chain are linked by springs with natural length to be 1. Therefore, apart from the energy contributions from Lennard-Jones, bond angles and torsion angles, the elastic potential energy of springs is also a part of the total potential of the configuration. The elastic energy of the springs acts as a penalty function of the degree of departure of a configuration from a legal one, and it is the key to relax the constraints. Accordingly, the protein folding is converted from a constraint optimization problem into an unconstrained one, which could be solved by the gradient method. A heuristic strategy was proposed to generate promising initial configurations.In the course of solution using the gradient method, it is often possible for the calculation to fall into the trap of local minimum. To jump out of the trap of local minimum and guide the search to the points with better prospects, we combined our quasi-physical algorithms with other methods with global-search ability, and then obtained a simulated annealing method and a Tabu search method, which are more efficient than the quasi-physical algorithm. It is noteworthy that based on the initial configurations obtained by ELP (energy landscape paving minimizer), most of our results for the benchmark instances are better than the best values previously reported in literature.The research in this dissertation indicates that by abstracting and formalizing the evolution rule of the motion of matter in the physical world and the humanity's social experience, we could design highly efficient algorithm for solving the protein folding problem. Through this working path, we are trying to seek for high-efficent algorithms for other model-based protein folding problem and other NP-complete problems in our future study.