Gordon, D. Benjamin and Mayo, Stephen L. (1999) Branch-and-terminate: a combinatorial optimization algorithm for protein design. Structure, 7 (9). pp. 1089-1098. ISSN 0969-2126. http://resolver.caltech.edu/CaltechAUTHORS:20110620-160432352
Full text is not posted in this repository. Consult Related URLs below.
Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20110620-160432352
Background: Several deterministic and stochastic combinatorial optimization algorithms have been applied to computational protein design and homology modeling. As structural targets increase in size, however, it has become necessary to find more powerful methods to address the increased combinatorial complexity. Results: We present a new deterministic combinatorial search algorithm called ‘Branch-and-Terminate’ (B&T), which is derived from the Branch-and-Bound search method. The B&T approach is based on the construction of an efficient but very restrictive bounding expression, which is used for the search of a combinatorial tree representing the protein system. The bounding expression is used both to determine the optimal organization of the tree and to perform a highly effective pruning procedure named ‘termination’. For some calculations, the B&T method rivals the current deterministic standard, dead-end elimination (DEE), sometimes finding the solution up to 21 times faster. A more significant feature of the B&T algorithm is that it can provide an efficient way to complete the optimization of problems that have been partially reduced by a DEE algorithm. Conclusions: The B&T algorithm is an effective optimization algorithm when used alone. Moreover, it can increase the problem size limit of amino acid sidechain placement calculations, such as protein design, by completing DEE optimizations that reach a point at which the DEE criteria become inefficient. Together the two algorithms make it possible to find solutions to problems that are intractable by either algorithm alone.
|Additional Information:||© 1999 Elsevier Science Ltd. Received 8 February 1999; revised 14 May 1999; Accepted 18 May 1999. Available online 20 January 2000. We wish to thank AG Street for invaluable feedback throughout the process of developing the algorithm. We also wish to thank EM Reingold, R Manohar, and N Pierce for helpful discussions. This work was supported by the Howard Hughes Medical Institute (SLM), training grant GM 07616C-19 from the National Institutes of Health (DBG), the Rita Allen Foundation, and the David and Lucile Packard Foundation.|
|Subject Keywords:||Protein Engineering; Models: Molecular; Algorithms; Proteins; Molecular Structure; Branch-and-Bound; dead-end elimination; global energy minimum; protein design; rotamers|
|Official Citation:||D Benjamin Gordon, Stephen L Mayo, Branch-and-Terminate: a combinatorial optimization algorithm for protein design, Structure, Volume 7, Issue 9, 15 September 1999, Pages 1089-1098, ISSN 0969-2126, 10.1016/S0969-2126(99)80176-2.|
|Usage Policy:||No commercial reproduction, distribution, display or performance rights in this work are provided.|
|Deposited By:||Marie Ary|
|Deposited On:||27 Sep 2011 20:39|
|Last Modified:||27 Sep 2011 20:39|
Repository Staff Only: item control page