Iterated local search with partition crossover for computational protein design
- 6 July 2021
- Vol. 89 (11), 1522-1529
- https://doi.org/10.1002/prot.26174
Abstract
Structure-based computational protein design (CPD) refers to the problem of finding a sequence of amino acids which folds into a specific desired protein structure, and possibly fulfills some targeted biochemical properties. Recent studies point out the particularly rugged CPD energy landscape, suggesting that local search optimization methods should be designed and tuned to easily escape local minima attraction basins. In this article, we analyze the performance and search dynamics of an iterated local search (ILS) algorithm enhanced with partition crossover. Our algorithm, PILS, quickly finds local minima and escapes their basins of attraction by solution perturbation. Additionally, the partition crossover operator exploits the structure of the residue interaction graph in order to efficiently mix solutions and find new unexplored basins. Our results on a benchmark of 30 proteins of various topology and size show that PILS consistently finds lower energy solutions compared to Rosetta fixbb and a classic ILS, and that the corresponding sequences are mostly closer to the native.Keywords
This publication has 21 references indexed in Scilit:
- Multi-language evaluation of exact solvers in graphical model discrete optimizationConstraints, 2016
- Fast search algorithms for computational protein designJournal of Computational Chemistry, 2016
- Guaranteed Discrete Energy Optimization on Large Protein Design ProblemsJournal of Chemical Theory and Computation, 2015
- Partition Crossover for Pseudo-Boolean OptimizationPublished by Association for Computing Machinery (ACM) ,2015
- Computational protein design as an optimization problemArtificial Intelligence, 2014
- A Smoothed Backbone-Dependent Rotamer Library for Proteins Derived from Adaptive Kernel Density Estimates and RegressionsStructure, 2011
- Rosetta3Methods in Enzymology, 2010
- Iterated Local Search: Framework and ApplicationsPublished by Springer Science and Business Media LLC ,2010
- An object‐oriented library for computational protein designJournal of Computational Chemistry, 2007
- Protein Design is NP-hard"Protein Engineering, Design and Selection", 2002