Quasi-human Approach To Chain Geometry Structure

Protein is formed by the linear arrangement of amino acid residues, it folded to 3-dimensional structure through the interaction between residues. The function of protein depends on its three-dimensional structure. The goal of protein structure prediction is to directly predict its three-dimensional structure through the protein chain. It is an important task of protein engineering.HP lattice model of protein structure prediction is a simplified and important model. it has been proven NP-hard. For NP-hard problems, Exact and accurate algorithm must have exponential complexity (unless P=NP). For larger problem instances, the time of its running is often difficult to accept. Approximate algorithm cannot guarantee the optimal solution obtained, but the time required can be greatly reduced, it can find a satisfactory approximate optimal solution in within an acceptable time, is good substitute of the exact and accurate algorithm.Heuristic optimization algorithm is the most important approximation algorithm currently. Heuristic optimization algorithm use human knowledge about the physical and biological to design the algorithm, it has been an unprecedented development in recent decades. A lot of different types of algorithms are generated. These are more realistic approach for large-scale complex problem currently. Quasi-physical and Quasi-human algorithm use physical knowledge and experience of human society to design the algorithm, it is important extend and complement of the heuristic optimization algorithm, can further improve the efficiency of the algorithm.Through study of the geometry structure of protein conformation within HP lattice model, we have got energy formula according to the geometric structure of the conformation and upper bound estimation. In the study of the growth process of the proteins, this energy formula has further refined, it finally used to the design of algorithms. Through comparing the growth process of the protein conformation and the process of games on the Go, the two concepts of "real benefits" and "external potential" of the Go were borrow up to the protein conformation. The real benefits and external potential guide the growth of protein conformation. Through the analysis of the impact of the current pattern to later, the estimation formula of external potential was constructed. This formula is used to construct the algorithm finally.Monte Carlo method is an important method to study protein structure prediction, PERM is an important improvement to the sequential importance sampling in Monte Carlo methods. PERM is current one of the most efficient algorithms to solve HP lattice model. Usually the weight of the sequential importance sampling is only with the current conformation, the impact of the geometry structure does not take into account for the future. We made the external potential as a factor of the weight, reconstructed the weight formula, combined with the branch control ideal of PERM, and proposed a quasi-human random growth algorithm. By analyzing the evolution of the energy equation in the conformation growth process, and the impact of various components of the energy formula to energy, we constructed a new weight of the sequential importance sampling, and proposed a heuristic optimization algorithm.With the important examples internationally recognized, we tested the quasi-human random growth algorithm and the heuristic structure optimization algorithm in two-dimensional case, and compared it with international importance algorithm. The results show that, the formula developed by the paper may improve the algorithm.Currently the most successful structure prediction is homology modeling method, its make the structure of similar protein as the "template", to get the structure of unresolved homologous proteins. Determine the similarity of the protein chain is the basis of homology modeling method, the amino acid fragment match of the protein chain is the basis of determine the similarity of the protein chain. BM algorithm is one of the most efficient algorithms of string matching. For their application to bioinformatics, we proposed two improved algorithm of BM algorithm:CBM algorithm and BMX algorithm, they can further improve the efficiency of BM algorithm.