Linkage and Problem Structures.- Linkage Structure and Genetic Evolutionary Algorithms.- Fragment as a Small Evidence of the Building Blocks Existence.- Structure Learning and Optimisation in a Markov Network Based Estimation of Distribution Algorithm.- DEUM - A Fully Multivariate EDA Based on Markov Networks.- Model Building and Exploiting.- Pairwise Interactions Induced Probabilistic Model Building.- ClusterMI: Building Probabilistic Models Using Hierarchical Clustering and Mutual Information.- Estimation of Distribution Algorithm Based on Copula Theory.- Analyzing the k Most Probable Solutions in EDAs Based on Bayesian Networks.- Applications.- Protein Structure Prediction Based on HP Model Using an Improved Hybrid EDA.- Sensible Initialization of a Computational Evolution System Using Expert Knowledge for Epistasis Analysis in Human Genetics.- Estimating Optimal Stopping Rules in the Multiple Best Choice Problem with Minimal Summarized Rank via the Cross-Entropy Method.
"Protein Structure Prediction Based on HP Model Using an Improved Hybrid EDA (p. 193-194)
Benhui Chen and Jinglu Hu
Abstract. Protein structure prediction (PSP) is one of the most important problems in computational biology. This chapter introduces a novel hybrid Estimation of Distribution Algorithm (EDA) to solve the PSP problem on HP model. Firstly, a composite fitness function containing the information of folding structure core (H-Core) is introduced to replace the traditional fitness function of HP model. The new fitness function is expected to select better individuals for probabilistic model of EDA. Secondly, local search with guided operators is utilized to refine found solutions for improving efficiency of EDA. Thirdly, an improved backtracking-based repairing method is introduced to repair invalid individuals sampled by the probabilistic model of EDA. It can significantly reduce the number of backtracking searching operation and the computational cost for long sequence protein. Experimental results demonstrate that the new method outperforms the basic EDAs method. At the same time, it is very competitive with other existing algorithms for the PSP problem on lattice HP models.
1 Introduction
Protein structure prediction (PSP) is one of the most important problems in computational biology. A protein is a chain of amino acids (also called as residues) that folds into a specific native tertiary structure under certain physiological conditions. Understanding protein structures is vital to determining the function of a protein and its interaction with DNA, RNA and enzyme. The information about its conformation can provide essential information for drug design and protein engineering.
While there are over a million known protein sequences, only a limited number of protein structures are experimentally determined. Hence, prediction of protein structures from protein sequences using computer programs is an important step to unveil proteins’ three dimensional conformation and functions. Because of the complexity of the PSP problem, simplified models like Dill’s HPlattice [17] model have become the major tools for investigating general properties of protein folding. In HP model, 20-letter alphabet of residues is simplified to a two-letter alphabet, namely H (hydrophobic) and P (polar).
Experiments on small protein suggest that the native state of a protein corresponds to a free energy minimum. This hypothesis is widely accepted, and forms the basis for computational prediction of a protein’s conformation from its residue sequence. The problem of finding such a minimum energy configuration has been proved to be NP-complete for the bi-dimensional (2-D) [8] and tri-dimensional (3-D) lattices [4]. Therefore, a deterministic approaches is always not practical for this problem."
