Iterated local search with partition crossover for computational protein design

Area of Science:

• Computational biology
• Protein engineering
• Bioinformatics

Background:

• Computational protein design (CPD) aims to identify amino acid sequences that fold into specific protein structures.
• The energy landscape of CPD is rugged, necessitating optimization methods that can escape local minima.
• Existing methods like Rosetta fixbb and basic Iterated Local Search (ILS) have limitations in exploring the solution space.

Purpose of the Study:

• To analyze the performance and search dynamics of a novel CPD algorithm, PILS.
• To evaluate PILS's ability to find low-energy sequences and escape local minima.
• To compare PILS against established CPD algorithms.

Main Methods:

• Development of PILS, an Iterated Local Search (ILS) algorithm enhanced with a partition crossover operator.
• Exploitation of residue interaction graphs for efficient solution mixing and exploration of new basins.
• Benchmarking PILS on 30 proteins of diverse topology and size.

Main Results:

• PILS consistently identifies lower energy solutions compared to Rosetta fixbb and a classic ILS.
• The sequences generated by PILS are generally closer to native protein structures.
• PILS demonstrates efficient escape from local minima through solution perturbation and effective exploration of the sequence space.

Conclusions:

• PILS offers a significant improvement over existing methods for structure-based computational protein design.
• The enhanced ILS approach with partition crossover effectively navigates the rugged CPD energy landscape.
• PILS shows promise for designing novel proteins with desired structures and properties.