A Caltech Library Service

Trading accuracy for speed: a quantitative comparison of search algorithms in protein sequence design

Voigt, Christopher A. and Gordon, D. Benjamin and Mayo, Stephen L. (2000) Trading accuracy for speed: a quantitative comparison of search algorithms in protein sequence design. Journal of Molecular Biology, 299 (3). pp. 789-803. ISSN 0022-2836. doi:10.1006/jmbi.2000.3758.

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

Use this Persistent URL to link to this item:


Finding the minimum energy amino acid side-chain conformation is a fundamental problem in both homology modeling and protein design. To address this issue, numerous computational algorithms have been proposed. However, there have been few quantitative comparisons between methods and there is very little general understanding of the types of problems that are appropriate for each algorithm. Here, we study four common search techniques: Monte Carlo (MC) and Monte Carlo plus quench (MCQ); genetic algorithms (GA); self-consistent mean field (SCMF); and dead-end elimination (DEE). Both SCMF and DEE are deterministic, and if DEE converges, it is guaranteed that its solution is the global minimum energy conformation (GMEC). This provides a means to compare the accuracy of SCMF and the stochastic methods. For the side-chain placement calculations, we find that DEE rapidly converges to the GMEC in all the test cases. The other algorithms converge on significantly incorrect solutions; the average fraction of incorrect rotamers for SCMF is 0.12, GA 0.09, and MCQ 0.05. For the protein design calculations, design positions are progressively added to the side-chain placement calculation until the time required for DEE diverges sharply. As the complexity of the problem increases, the accuracy of each method is determined so that the results can be extrapolated into the region where DEE is no longer tractable. We find that both SCMF and MCQ perform reasonably well on core calculations (fraction amino acids incorrect is SCMF 0.07, MCQ 0.04), but fail considerably on the boundary (SCMF 0.28, MCQ 0.32) and surface calculations (SCMF 0.37, MCQ 0.44).

Item Type:Article
Related URLs:
Mayo, Stephen L.0000-0002-9785-5018
Contact Email
Additional Information:© 2000 Academic Press. Received 27 September 1999; revised 27 January 2000; Accepted 23 February 2000. Available online 25 March 2002. Edited by J. Thornton. The work was partially supported by the Howard Hughes Medical Institute, NIH training grant GM 08346, the Helen G. and Arthur McCallum Foundation (DBG), and a National Science Foundation Graduate Fellowship (CAV).
Funding AgencyGrant Number
Howard Hughes Medical Institute (HHMI)UNSPECIFIED
NIH Training Grant FellowshipGM 08346
Helen G. and Arthur McCallum FoundationUNSPECIFIED
NSF Graduate FellowshipUNSPECIFIED
Subject Keywords:Stochastic Processes; Protein Engineering; Algorithms; Proteins; Combinatorial Chemistry Techniques; Probability, Databases: Factual; Sensitivity and Specificity; Monte Carlo Method; Protein Structure: Secondary; Thermodynamics; Temperature; Time Factors; protein design; combinatorial optimization
Issue or Number:3
Record Number:CaltechAUTHORS:20110620-160433649
Persistent URL:
Official Citation:Christopher A. Voigt, D.Benjamin Gordon, Stephen L. Mayo, Trading accuracy for speed: a quantitative comparison of search algorithms in protein sequence design, Journal of Molecular Biology, Volume 299, Issue 3, 9 June 2000, Pages 789-803, ISSN 0022-2836, 10.1006/jmbi.2000.3758.
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:24123
Deposited By: Marie Ary
Deposited On:26 Sep 2011 22:53
Last Modified:09 Nov 2021 16:20

Repository Staff Only: item control page