Computational protein design as an optimization problem

Autor: George Katsirelos, Barry O'Sullivan, David Allouche, Thomas Schiex, Sophie Barbe, Simon de Givry, Steve Prestwich, Jessica Davies, Isabelle André, Seydou Traoré
Přispěvatelé: Unité de Biométrie et Intelligence Artificielle (UBIA), Institut National de la Recherche Agronomique (INRA), Laboratoire d'Ingénierie des Systèmes Biologiques et des Procédés (LISBP), Institut National de la Recherche Agronomique (INRA)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS), Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées, Insight Centre for Data Analytics, University College Cork (UCC), ANR, Unité de Biométrie et Intelligence Artificielle (ancêtre de MIAT) (UBIA), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS), Université de Toulouse (UT), Centre National de la Recherche Scientifique (CNRS)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National de la Recherche Agronomique (INRA), University College Cork
Jazyk: angličtina
Rok vydání: 2014
Předmět:
Zdroj: Artificial Intelligence
Artificial Intelligence, Elsevier, 2014, 212, pp.59-79. ⟨10.1016/j.artint.2014.03.005⟩
Artificial Intelligence, 2014, 212, pp.59-79. ⟨10.1016/j.artint.2014.03.005⟩
ISSN: 0004-3702
DOI: 10.1016/j.artint.2014.03.005⟩
Popis: 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.
Databáze: OpenAIRE
Externí odkaz: