Studies Of Protein Prediction Using Lattice Model Based On Combined Backtracking And MC Method

Ab-initio approach to predict 3D protein structure can reveal the mechnism for protein folding.But it is a NP hard problem.Therefore,in order to improve search efficiency,the coarse-grained model,such as lattice model,is adopted.In lattice model,there are two types of algorithms: the first one is the chain growth model,represented by back tracking algorithm,the second one is the non-chain growth model,represented by the Monte Carlo algorithm.Monte Carlo algorithm is simple,less memory,but slow convergence,especially for long chain.Back tracking method,while dealing with complex and larger problems,has a greater time complexity.Therefore,how to combine the two types of algorithms,reduce search space,improve search efficiency,and have important significance for the prediction of protein structure.This research shows optimization approaches to protein folding.The protein folding problem is to predict the compact three dimensional structure of a protein based on its amino acid sequence.This research focuses on ab-initio mathematical models to find provably optimal solutions to the 3D HP-lattice protein folding model.Three algorithms are compared including Monte Carlo algorithms,replica exchange Monte Carlo algorithm,back tracking algorithm.Based on this,a hybrid algorithm was built,composed by Monte Carlo algorithm and back tracking algorithm,to predict protein structure.First,Monte Carlo algorithms and replica exchange Monte Carlo algorithm were compared.The results show that replica exchange Monte Carlo algorithm is more effective than Monte Carlo algorithm,and the final conformation energy is lower.The reason is that the protein conformation space with a complex probability density distribution.Monte Carlo algorithm,compared to replica exchange Monte Carlo algorithm,is more likely to fall into the "local minimum".Second,back tracking algorithm was improved in order to reduce the time complexity.We used the summation of the hydrophobic amino acid distance as a parameter to describe free energy.The conformations of each branch were rated according to the summation and continue to grow along the lowest energy branch until the entire amino acids were arranged in lattice.Third,the performance of back tracking algorithm is compared to that of Monte Carlo method.The results for the short sequence show that the searching efficiency of back tracking algorithm is better than that of Monte Carlo program under the condition of conformation energy given.But without the time constraint,the energy of the conformations predicted by back tracking algorithm is highter than that of the conformations predicted by Monte Carlo algorithm.For long chain,the performance of back tracking algorithm is superior to that of Monte Carlo algorithm both in speed and conformational energy.The reason is that as the amino acid chain increases,the conformational spatial probability density distribution will be more complex,therefore Monte Carlo algorithm as well as replica exchange Monte Carlo algorithm are easier to enter local minimum.Finally,back tracking algorithm was combined with Monte Carlo algorithm.The results for the short-chain amino acid sequence show that the hybrid algorithm make up for the shortcomings of the two original methods.The energy of the conformation is the same as that of replica exchange Monte Carlo algorithm,but the speed is better than that of replica exchange Monte Carlo algorithm.The results of long chain prediction show that the performance of the hybrid algorithm are better than those of replica exchange Monte Carlo algorithm,both at search speed and the energy of the conformation.It can be seen that the hybrid algorithm,combined back tracking algorithm and Monte Carlo algorithm,have both higher search efficiency and lower energy conformation.It's performance is superior to Monte carlo algorithm and replica exchange Monte Carlo algorithm and back tracking algorithm.