title: Fast search algorithms for computational protein design.
abstract: One of the main challenges in computational protein design (CPD) is the huge size of the protein sequence and conformational space that has to be computationally explored. Recently, we showed that state-of-the-art combinatorial optimization technologies based on Cost Function Network (CFN) processing allow speeding up provable rigid backbone protein design methods by several orders of magnitudes. Building up on this, we improved and injected CFN technology into the well-established CPD package Osprey to allow all Osprey CPD algorithms to benefit from associated speedups. Because Osprey fundamentally relies on the ability of A* to produce conformations in increasing order of energy, we defined new A* strategies combining CFN lower bounds, with new side-chain positioning-based branching scheme. Beyond the speedups obtained in the new A*-CFN combination, this novel branching scheme enables a much faster enumeration of suboptimal sequences, far beyond what is reachable without it. Together with the immediate and important speedups provided by CFN technology, these developments directly benefit to all the algorithms that previously relied on the DEE/ A* combination inside Osprey* and make it possible to solve larger CPD problems with provable algorithms.
authors.affiliation: Université De Toulouse, INSA, UPS, INP, LISBP, 135 Avenue de Rangueil, Toulouse, F-31077, France.|INRA, UMR792, Ingénierie des Systèmes Biologiques et des Procédés, Toulouse, F-31400, France.|CNRS, UMR5504, Toulouse, F-31400, France.
authors.forename: Seydou
authors.initials: S
authors.lastname: Traoré
authors.affiliation: Department of Biochemistry, Department of Computer Science, Department of Chemistry, Duke University, Durham, North Carolina.
authors.forename: Kyle E
authors.initials: KE
authors.lastname: Roberts
authors.affiliation: Unité de Mathématiques et Informatique Appliquées, Toulouse, UR 875, INRA, Castanet, Tolosan, F-31320, France.
authors.forename: David
authors.initials: D
authors.lastname: Allouche
authors.affiliation: Department of Biochemistry, Department of Computer Science, Department of Chemistry, Duke University, Durham, North Carolina.
authors.forename: Bruce R
authors.initials: BR
authors.lastname: Donald
authors.affiliation: Université De Toulouse, INSA, UPS, INP, LISBP, 135 Avenue de Rangueil, Toulouse, F-31077, France.|INRA, UMR792, Ingénierie des Systèmes Biologiques et des Procédés, Toulouse, F-31400, France.|CNRS, UMR5504, Toulouse, F-31400, France.
authors.forename: Isabelle
authors.initials: I
authors.lastname: André
authors.affiliation: Unité de Mathématiques et Informatique Appliquées, Toulouse, UR 875, INRA, Castanet, Tolosan, F-31320, France.
authors.forename: Thomas
authors.initials: T
authors.lastname: Schiex
authors.affiliation: Université De Toulouse, INSA, UPS, INP, LISBP, 135 Avenue de Rangueil, Toulouse, F-31077, France.|INRA, UMR792, Ingénierie des Systèmes Biologiques et des Procédés, Toulouse, F-31400, France.|CNRS, UMR5504, Toulouse, F-31400, France.
authors.forename: Sophie
authors.initials: S
authors.lastname: Barbe
mesh_terms: D000465:Algorithms; D000595:Amino Acid Sequence; D019295:Computational Biology; D015195:Drug Design; D011487:Protein Conformation; D011506:Proteins / Q000737:chemistry*
chemical_list: D011506:Proteins
keywords: computational protein design; computer-aided protein design; cost function networks; deterministic search methods; exact combinatorial optimization; global minimum energy conformation; near-optimal solutions; search heuristics
references.citation: PeerJ. 2013 Nov 12;1:e211
references.pmid: 24255821
references.citation: J Comput Chem. 2008 Jul 30;29(10):1527-42
references.pmid: 18293294
references.citation: Biochemistry. 2006 Dec 26;45(51):15495-504
references.pmid: 17176071
references.citation: Proteins. 2000 Aug 15;40(3):389-408
references.pmid: 10861930
references.citation: Protein Eng. 2002 Oct;15(10):779-82
references.pmid: 12468711
references.citation: Methods Enzymol. 2013;523:87-107
references.pmid: 23422427
references.citation: Chem Biol. 2012 Apr 20;19(4):449-55
references.pmid: 22520751
references.citation: Curr Opin Struct Biol. 2009 Aug;19(4):458-63
references.pmid: 19646858
references.citation: J Mol Biol. 2000 Aug 18;301(3):713-36
references.pmid: 10966779
references.citation: J Comput Biol. 2002;9(4):597-612
references.pmid: 12323095
references.citation: PLoS Comput Biol. 2012;8(4):e1002477
references.pmid: 22532795
references.citation: Pac Symp Biocomput. 2005;:16-27
references.pmid: 15759610
references.citation: Science. 2010 Jul 16;329(5989):309-13
references.pmid: 20647463
references.citation: Proteins. 1998 Nov 1;33(2):227-39
references.pmid: 9779790
references.citation: Biophys J. 1994 May;66(5):1335-40
references.pmid: 8061189
references.citation: J Comput Biol. 2005 Jul-Aug;12(6):740-61
references.pmid: 16108714
references.citation: Proc Natl Acad Sci U S A. 2009 Mar 10;106(10):3764-9
references.pmid: 19228942
references.citation: Nature. 1992 Apr 9;356(6369):539-42
references.pmid: 21488406
references.citation: Biotechnol Adv. 2015 Sep-Oct;33(5):605-13
references.pmid: 25560932
references.citation: Bioinformatics. 2005 Apr 1;21(7):1028-36
references.pmid: 15546935
references.citation: Proc Natl Acad Sci U S A. 2008 Aug 26;105(34):12242-7
references.pmid: 18708527
references.citation: Nature. 2014 Jun 5;510(7503):103-8
references.pmid: 24870237
references.citation: Chem Biol. 2007 Oct;14(10):1186-97
references.pmid: 17961830
references.citation: J Comput Chem. 2009 Sep;30(12):1923-45
references.pmid: 19123203
references.citation: J Comput Chem. 2003 Jan 30;24(2):232-43
references.pmid: 12497602
references.citation: Proteins. 2013 Jan;81(1):18-39
references.pmid: 22821798
references.citation: Proteins. 1999 May 1;35(2):133-52
references.pmid: 10223287
references.citation: J Mol Biol. 2000 Jun 9;299(3):789-803
references.pmid: 10835284
references.citation: Eur J Biochem. 1977 Nov 1;80(2):319-24
references.pmid: 923582
references.citation: Structure. 1999 Sep 15;7(9):1089-98
references.pmid: 10508778
references.citation: Bioinformatics. 2013 Sep 1;29(17):2129-36
references.pmid: 23842814
references.citation: Proc Natl Acad Sci U S A. 2000 Sep 12;97(19):10383-8
references.pmid: 10984534
references.citation: Proc Natl Acad Sci U S A. 2010 Aug 3;107(31):13707-12
references.pmid: 20643959
references.citation: PLoS Comput Biol. 2012 Jan;8(1):e1002335
references.pmid: 22279426