A Caltech Library Service

Branch-and-terminate: a combinatorial optimization algorithm for protein design

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. doi:10.1016/S0969-2126(99)80176-2.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


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.

Item Type:Article
Related URLs:
URLURL TypeDescription
Mayo, Stephen L.0000-0002-9785-5018
Contact Email
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.
Funding AgencyGrant Number
Howard Hughes Medical Institute (HHMI)UNSPECIFIED
NIHGM 07616C-19
Rita Allen FoundationUNSPECIFIED
David and Lucile Packard FoundationUNSPECIFIED
Subject Keywords:Protein Engineering; Models: Molecular; Algorithms; Proteins; Molecular Structure; Branch-and-Bound; dead-end elimination; global energy minimum; protein design; rotamers
Issue or Number:9
Record Number:CaltechAUTHORS:20110620-160432352
Persistent URL:
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.
ID Code:24115
Deposited By: Marie Ary
Deposited On:27 Sep 2011 20:39
Last Modified:09 Nov 2021 16:20

Repository Staff Only: item control page