Protein Structure Prediction as a Hard Optimization Problem: The Genetic Algorithm Approach

Using genetic programming to predict and optimize protein function

Protein engineers conventionally use tools such as Directed Evolution to find new proteins with better functionalities and traits. More recently, computational techniques and especially machine learning approaches have been recruited to assist Directed Evolution, showing promising results. In this article, we propose POET, a computational Genetic Programming tool based on evolutionary computation methods to enhance screening and mutagenesis in Directed Evolution and help protein engineers to find proteins that have better functionality. As a proof-of-concept, we use peptides that generate MRI contrast detected by the Chemical Exchange Saturation Transfer contrast mechanism. The evolutionary methods used in POET are described, and the performance of POET in different epochs of our experiments with Chemical Exchange Saturation Transfer contrast are studied. Our results indicate that a computational modeling tool like POET can help to find peptides with 400% better functionality than used before.

The Improvement of DV-Hop Model and Its Application in the Security Performance of Smart Campus

In the smart campus, sensors are the basic units in the whole the Internet of Things structure, which play the role of collecting information and transmitting it. How to transmits more information at a certain power level has attracted the attention of many researchers. In this paper, the DV-Hop algorithm is optimized by combining simulated annealing-interference particle swarm optimization algorithm to improve the node localization of wireless sensor networks and enhance the security performance of smart campus. To address the problem that particle swarm optimization easily falls into local optimum, a perturbation mechanism is introduced in the basic particle swarm optimization algorithm. Meanwhile, the acceptance probability P is introduced in the simulated annealing algorithm to determine whether a particle is accepted when it “flies” to a new position, which improves the probability of finding a global optimal solution. Comparing the average localization error and optimization rate of the DV-Hop algorithm, PSO-DV-Hop algorithm, and the optimized algorithm. The results show a greater advantage of the algorithm. This will greatly enhance the safety performance and efficiency of the smart campus.

Chaotic multiquenching annealing applied to the protein folding problem

The Chaotic Multiquenching Annealing algorithm (CMQA) is proposed. CMQA is a new algorithm, which is applied to protein folding problem (PFP). This algorithm is divided into three phases: (i) multiquenching phase (MQP), (ii) annealing phase (AP), and (iii) dynamical equilibrium phase (DEP). MQP enforces several stages of quick quenching processes that include chaotic functions. The chaotic functions can increase the exploration potential of solutions space of PFP. AP phase implements a simulated annealing algorithm (SA) with an exponential cooling function. MQP and AP are delimited by different ranges of temperatures; MQP is applied for a range of temperatures which goes from extremely high values to very high values; AP searches for solutions in a range of temperatures from high values to extremely low values. DEP phase finds the equilibrium in a dynamic way by applying least squares method. CMQA is tested with several instances of PFP.

Hill-Climbing search and diversification within an evolutionary approach to protein structure prediction

Proteins are complex structures made of amino acids having a fundamental role in the correct functioning of living cells. The structure of a protein is the result of the protein folding process. However, the general principles that govern the folding of natural proteins into a native structure are unknown. The problem of predicting a protein structure with minimum-energy starting from the unfolded amino acid sequence is a highly complex and important task in molecular and computational biology. Protein structure prediction has important applications in fields such as drug design and disease prediction. The protein structure prediction problem is NP-hard even in simplified lattice protein models. An evolutionary model based on hill-climbing genetic operators is proposed for protein structure prediction in the hydrophobic - polar (HP) model. Problem-specific search operators are implemented and applied using a steepest-ascent hill-climbing approach. Furthermore, the proposed model enforces an explicit diversification stage during the evolution in order to avoid local optimum. The main features of the resulting evolutionary algorithm - hill-climbing mechanism and diversification strategy - are evaluated in a set of numerical experiments for the protein structure prediction problem to assess their impact to the efficiency of the search process. Furthermore, the emerging consolidated model is compared to relevant algorithms from the literature for a set of difficult bidimensional instances from lattice protein models. The results obtained by the proposed algorithm are promising and competitive with those of related methods.

Ab initio protein fold prediction using evolutionary algorithms: influence of design and control parameters on performance

True ab initio prediction of protein 3D structure requires only the protein primary structure, a physicochemical free energy model, and a search method for identifying the free energy global minimum. Various characteristics of evolutionary algorithms (EAs) mean they are in principle well suited to the latter. Studies to date have been less than encouraging, however. This is because of the limited consideration given to EA design and control parameter issues. A comprehensive study of these issues was, therefore, undertaken for ab initio protein fold prediction using a full atomistic protein model. The performance and optimal control parameter settings of twelve EA designs where first established using a 15-residue polyalanine molecule-design aspects varied include the encoding alphabet, crossover operator, and replacement strategy. It can be concluded that real encoding and multipoint crossover are superior, while both generational and steady-state replacement strategies have merits. The scaling between the optimal control parameter settings and polyalanine size was also identified for both generational and steady-state designs based on real encoding and multipoint crossover. Application of the steady-state design to met-enkephalin indicated that these scalings are potentially transferable to real proteins. Comparison of the performance of the steady state design for met-enkephalin with other ab initio methods indicates that EAs can be competitive provided the correct design and control parameter values are used.

Evolutionary method for the assembly of rigid protein fragments

Genetic algorithms constitute a powerful optimization method that has already been used in the study of the protein folding problem. However, they often suffer from a lack of convergence in a reasonably short time for complex fitness functions. Here, we propose an evolutionary strategy that can reproducibly find structures close to the minimum of a potential function for a simplified protein model in an efficient way. The model reduces the number of degrees of freedom of the system by treating the protein structure as composed of rigid fragments. The search incorporates a double encoding procedure and a merging operation from subpopulations that evolve independently of one another, both contributing to the good performance of the full algorithm. We have tested it with protein structures of different degrees of complexity, and present our conclusions related to its possible application as an efficient tool for the analysis of folding potentials.