title: Deterministic Search Methods for Computational Protein Design.
abstract: One main challenge in Computational Protein Design (CPD) lies in the exploration of the amino-acid sequence space, while considering, to some extent, side chain flexibility. The exorbitant size of the search space urges for the development of efficient exact deterministic search methods enabling identification of low-energy sequence-conformation models, corresponding either to the global minimum energy conformation (GMEC) or an ensemble of guaranteed near-optimal solutions. In contrast to stochastic local search methods that are not guaranteed to find the GMEC, exact deterministic approaches always identify the GMEC and prove its optimality in finite but exponential worst-case time. After a brief overview on these two classes of methods, we discuss the grounds and merits of four deterministic methods that have been applied to solve CPD problems. These approaches are based either on the Dead-End-Elimination theorem combined with A* algorithm (DEE/A*), on Cost Function Networks algorithms (CFN), on Integer Linear Programming solvers (ILP) or on Markov Random Fields solvers (MRF). The way two of these methods (DEE/A* and CFN) can be used in practice to identify low-energy sequence-conformation models starting from a pairwise decomposed energy matrix is detailed in this review.
authors.affiliation: INSA, UPS, INP, Université de Toulouse, 135 Avenue de Rangueil, 31077, Toulouse, France.|Laboratoire d'Ingénierie Ingénierie des Systèmes Biologiques et des Procédés - INSA, INRA, UMR792, 31400, Toulouse, France.|CNRS, UMR5504, 31400, Toulouse, France.
authors.forename: Seydou
authors.initials: S
authors.lastname: Traoré
authors.affiliation: Unité de Mathématiques et Informatique de Toulouse, UR 875, INRA, 31320, Castanet Tolosan, France.
authors.forename: David
authors.initials: D
authors.lastname: Allouche
authors.affiliation: INSA, UPS, INP, Université de Toulouse, 135 Avenue de Rangueil, 31077, Toulouse, France.|Laboratoire d'Ingénierie Ingénierie des Systèmes Biologiques et des Procédés - INSA, INRA, UMR792, 31400, Toulouse, France.|CNRS, UMR5504, 31400, Toulouse, France.
authors.forename: Isabelle
authors.initials: I
authors.lastname: André
authors.affiliation: Unité de Mathématiques et Informatique de Toulouse, UR 875, INRA, 31320, Castanet Tolosan, France.
authors.forename: Thomas
authors.initials: T
authors.lastname: Schiex
authors.affiliation: INSA, UPS, INP, Université de Toulouse, 135 Avenue de Rangueil, 31077, Toulouse, France. sophie.barbe@insa-toulouse.fr.|Laboratoire d'Ingénierie Ingénierie des Systèmes Biologiques et des Procédés - INSA, INRA, UMR792, 31400, Toulouse, France. sophie.barbe@insa-toulouse.fr.|CNRS, UMR5504, 31400, Toulouse, France. sophie.barbe@insa-toulouse.fr.
authors.forename: Sophie
authors.initials: S
authors.lastname: Barbe
mesh_terms: D000465:Algorithms; D019295:Computational Biology / Q000379:methods*; D003198:Computer Simulation; D008958:Models, Molecular; D011487:Protein Conformation; D015202:Protein Engineering / Q000379:methods*; D011506:Proteins / Q000737:chemistry / Q000235:genetics / Q000378:metabolism; D012984:Software; D013329:Structure-Activity Relationship
chemical_list: D011506:Proteins
keywords: Cost function network; Dead-end-elimination; Exact combinatorial optimization; Global minimum energy conformation; Integer linear programming; Markov random field; Near-optimal solutions