The Study On Applying Parallel Ant Colony Optimization To Protein Structure Prediction

The tertiary structure of protein is of significance for biology and medicine. How-ever, it is expensive and time-consuming to obtain protein structure with biochemicalmethods. Therefore predicting protein three-dimensional structure with computationalmethods has become critical in computational biology. How to e?ectively search inthe vast conformational space is one of the major challenges of this problem. In thisthesis, we propose to apply parallel ant colony optimization technique to the problemof protein structure prediction.For predicting protein structure based on two-dimensional HP model, we designa single ant colony algorithm - ACOHP, and the corresponding parallel version withshared pheromone matrix - PACOHP. For a test set of 11 instances, PACOHP obtains8 optimal solutions. The experiment results inspire us to apply the same strategyto the realistic and complex problem which tries to predict three-dimensional proteinbackbone.For the backbone prediction of protein, we design and implement pacBackbone,which employs parallel ant colonies with sharing pheromone matrix. Such paral-lel strategy enables to fuse the di?erent types of energy functions. In addition, wepresent local optimization technique to refine the ?exible loop regions, and a cross-conformation operation to generate more high-quality candidate conformations withlittle cost. Finally we tune the proper clustering algorithm to discriminate the confor-mation close enough to the nature conformation from the decoys.We evaluate pacBackbone with all 13 de novo prediction targets from the latestCASP8, and compare the accuracy with the published results of the competitions inCASP8. Among the results from pacBackbone, two structures are the best, and 7structures are top 10. The experimental results show that pacBackbone, consisted ofparallel ant colonies with sharing pheromone matrix, is a novel approach for proteinstructure prediction.