title: A new framework for computational protein design through cost function network optimization.
abstract: BACKGROUND
  The main challenge for structure-based computational protein design (CPD) remains the combinatorial nature of the search space. Even in its simplest fixed-backbone formulation, CPD encompasses a computationally difficult NP-hard problem that prevents the exact exploration of complex systems defining large sequence-conformation spaces.
  
  
  RESULTS
  We present here a CPD framework, based on cost function network (CFN) solving, a recent exact combinatorial optimization technique, to efficiently handle highly complex combinatorial spaces encountered in various protein design problems. We show that the CFN-based approach is able to solve optimality a variety of complex designs that could often not be solved using a usual CPD-dedicated tool or state-of-the-art exact operations research tools. Beyond the identification of the optimal solution, the global minimum-energy conformation, the CFN-based method is also able to quickly enumerate large ensembles of suboptimal solutions of interest to rationally build experimental enzyme mutant libraries.
  
  
  BACKGROUND
  The combined pipeline used to generate energetic models (based on a patched version of the open source solver Osprey 2.0), the conversion to CFN models (based on Perl scripts) and CFN solving (based on the open source solver toulbar2) are all available at http://genoweb.toulouse.inra.fr/~tschiex/CPD
authors.affiliation: Université de Toulouse, 135 Avenue de Rangueil, Toulouse, France.
authors.forename: Seydou
authors.initials: S
authors.lastname: Traoré
authors.forename: David
authors.initials: D
authors.lastname: Allouche
authors.forename: Isabelle
authors.initials: I
authors.lastname: André
authors.forename: Simon
authors.initials: S
authors.lastname: de Givry
authors.forename: George
authors.initials: G
authors.lastname: Katsirelos
authors.forename: Thomas
authors.initials: T
authors.lastname: Schiex
authors.forename: Sophie
authors.initials: S
authors.lastname: Barbe
mesh_terms: D000465:Algorithms; D008958:Models, Molecular; D011487:Protein Conformation; D015202:Protein Engineering / Q000379:methods*; D011506:Proteins / Q000737:chemistry; D020539:Sequence Analysis, Protein; D012984:Software
chemical_list: D011506:Proteins