HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Journal articles

Computational protein design as an optimization problem

Abstract : Proteins are chains of simple molecules called amino acids. The three-dimensional shape of a protein and its amino acid composition define its biological function. Over millions of years, living organisms have evolved a large catalog of proteins. By exploring the space of possible amino acid sequences, protein engineering aims at similarly designing tailored proteins with specific desirable properties. In Computational Protein Design (CPD), the challenge of identifying a protein that performs a given task is defined as the combinatorial optimization of a complex energy function over amino acid sequences. In this paper, we introduce the CPD problem and some of the main approaches that have been used by structural biologists to solve it, with an emphasis on the exact method embodied in the dead-end elimination/A⁎elimination/A⁎ algorithm (DEE/A⁎)(DEE/A⁎). The CPD problem is a specific form of binary Cost Function Network (CFN, aka Weighted CSP). We show how DEE algorithms can be incorporated and suitably modified to be maintained during search, at reasonable computational cost. We then evaluate the efficiency of CFN algorithms as implemented in our solver toulbar2, on a set of real CPD instances built in collaboration with structural biologists. The CPD problem can be easily reduced to 0/1 Linear Programming, 0/1 Quadratic Programming, 0/1 Quadratic Optimization, Weighted Partial MaxSAT and Graphical Model optimization problems. We compare toulbar2 with these different approaches using a variety of solvers. We observe tremendous differences in the difficulty that each approach has on these instances. Overall, the CFN approach shows the best efficiency on these problems, improving by several orders of magnitude against the exact DEE/A⁎DEE/A⁎ approach. The introduction of dead-end elimination before or during search allows to further improve these results.
Document type :
Journal articles
Complete list of metadata

Contributor : Archive Ouverte Prodinra Connect in order to contact the contributor
Submitted on : Thursday, February 4, 2016 - 11:17:48 PM
Last modification on : Monday, April 4, 2022 - 3:24:23 PM

Links full text



David Allouche, Isabelle André, Sophie Barbe, Jessica Davies, Simon de Givry, et al.. Computational protein design as an optimization problem. Artificial Intelligence, Elsevier, 2014, 212, pp.59-79. ⟨10.1016/j.artint.2014.03.005⟩. ⟨hal-01268554⟩



Record views