title: Guaranteed Discrete Energy Optimization on Large Protein Design Problems.
abstract: In Computational Protein Design (CPD), assuming a rigid backbone and amino-acid rotamer library, the problem of finding a sequence with an optimal conformation is NP-hard. In this paper, using Dunbrack's rotamer library and Talaris2014 decomposable energy function, we use an exact deterministic method combining branch and bound, arc consistency, and tree-decomposition to provenly identify the global minimum energy sequence-conformation on full-redesign problems, defining search spaces of size up to 10(234). This is achieved on a single core of a standard computing server, requiring a maximum of 66GB RAM. A variant of the algorithm is able to exhaustively enumerate all sequence-conformations within an energy threshold of the optimum. These proven optimal solutions are then used to evaluate the frequencies and amplitudes, in energy and sequence, at which an existing CPD-dedicated simulated annealing implementation may miss the optimum on these full redesign problems. The probability of finding an optimum drops close to 0 very quickly. In the worst case, despite 1,000 repeats, the annealing algorithm remained more than 1 Rosetta unit away from the optimum, leading to design sequences that could differ from the optimal sequence by more than 30% of their amino acids.
authors.affiliation: INRA MIAT, UR 875 , Castanet-Tolosan, 31326 Cedex, France.
authors.forename: David
authors.initials: D
authors.lastname: Simoncini
authors.affiliation: INRA MIAT, UR 875 , Castanet-Tolosan, 31326 Cedex, France.
authors.forename: David
authors.initials: D
authors.lastname: Allouche
authors.affiliation: INRA MIAT, UR 875 , Castanet-Tolosan, 31326 Cedex, France.
authors.forename: Simon
authors.initials: S
authors.lastname: de Givry
authors.affiliation: INRA MIAT, UR 875 , Castanet-Tolosan, 31326 Cedex, France.
authors.forename: Céline
authors.initials: C
authors.lastname: Delmas
authors.affiliation: Université de Toulouse; INSA, UPS, INP; LISBP , 135 Avenue de Rangueil , F-31077 Toulouse, France.|CNRS, UMR5504 , F-31400 Toulouse, France.|INRA, UMR792 Ingénierie des Systèmes Biologiques et des Procédés , F-31400 Toulouse, France.
authors.forename: Sophie
authors.initials: S
authors.lastname: Barbe
authors.affiliation: INRA MIAT, UR 875 , Castanet-Tolosan, 31326 Cedex, France.
authors.forename: Thomas
authors.initials: T
authors.lastname: Schiex
mesh_terms: D000465:Algorithms; D019295:Computational Biology; D011506:Proteins / Q000737:chemistry* / Q000378:metabolism; D013816:Thermodynamics
chemical_list: D011506:Proteins