Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published September 15, 1999 | public
Journal Article

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


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.

Additional details

August 22, 2023
October 23, 2023