Study On Protein Folding Problem Based On The Hysteretic Optimization And Extremal Optimization

The problem of the protein's conformational space is a very important subject in computational biology. This thesis studies on the problem about how fold the amino acids'sequences to its native state, which is called protein folding problem. A popular lattice model (HP model), is exploited in this thesis as the basic model of protein folding problem. For 2D and 3D HP model, hysteretic optimization (HO) algorithm and extremal optimization (EO) algorithm are used respectively to study the protein folding problem.Firstly, hysteretic optimization algorithm (HO) is applied for the first time in this thesis to the study of 2D-HP model of protein folding problems. The hysteretic optimization (HO) is an algorithm based on physics and was originally proposed by G. Zarand et al for spin glass model in 2002. The initiative of HO solution is that it uses the AC-demagnetization process to achieve the purpose for system optimization. Specifically, the objective function is optimized step by step by introducing an external field into the model and alternately switching its direction and it finally approaches to the optimal solution. The initiator of HO, G. Zarand, once exploited it to solve a travelling salesman problem (TSP) with 100 cities and discussed its efficiency. In this study, we successfully apply HO to protein folding problem with 2D-HP model and the simulation results show that HO is efficient and easy to get the optimal conformation when the protein's amino acids sequence's length is less than 85.Then, the extremal optimization (EO) algorithm is extended and successfully exploited in this thesis to study the 3D-HP model of the protein folding problem. In the framework of 3D-HP model, it is much complicated to get the optimal solution of the protein folding problem. In recent years, with the successful application in the 2D-HP model of the protein folding problem, many algorithms such as genetic algorithm, Monte Carlo algorithm, etc. have been trying to solve the protein folding problem with 3D- HP model. The extremal optimization (EO) algorithm is a fast convergent algorithm, good for local searching and easy to design and implement. When applying EO to 2D protein folding problem, it shows a good result for short sequences. Based on the reported results, EO is applied in this thesis to more complex 3D protein folding problem by changing the space position of the molecule whose local fitness is poor, thereby adjusting the amino acids'space arrangement state and finally folding to a proper structure with the least energy.The conclusion and the future work are discussed in the end of the paper.