Research On Tree Search Algorithm For Solving Protein Two-Dimensional Structure Prediction Problem

The protein structure prediction problem refers to predicting its high dimensional structures from the primary structure of the protein,and the structural information of the protein can give far more information about the functional mechanisms that the sequence can give.Therefore,this issue is one of the core issues pursued by life science and theoretical chemistry.Since the protein structure prediction problem has been proved to be an NP problem,people try to find an efficient heuristic algorithm which has considerable advantages in solving the NP problem to solve this problem.Heuristic algorithm is an algorithm proposed in relation to the optimization algorithm.By learning various phenomena in nature,it tries to achieve a good balance between the time of calculation and the precision of calculation.This algorithm is aimed at getting an acceptable calculation result for more complicated problems in a short time.In order to accurately predict protein structure,people usually simplify the protein structure into a specific mathematical model for calculation.This algorithm is based on one of the most widely used models-HP grid modelThe basis of this algorithm is the nPERMh2 algorithm,which optimizes the algorithm by adding anthropomorphic improvement strategy based on the traditional PERM algorithm.This kind of algorithm is a pruning algorithm.By considering the position of the current configuration in the historical configuration and the influence of arbitrary actions on the current configuration,a suitable pruning strategy is developed to improve the search efficiency of the algorithm.The algorithm which is further optimized based on the nPERMh1 algorithm is a tree search algorithm.The algorithm uses the calculation result of the nPERMh1 algorithm as the basis for branch selection in the tree search process.When the algorithm selects the branch for growth,it refers to the calculation result on the new branch formed by the nPERMh1 algorithm after each legal action on this branch is completed.The calculation result of the nPERMh1 algorithm can be used to determine which branch is better.This method can make it more targeted in the process of tree search,so that the optimal configuration can be found in a shorter time.