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 http://resolver.caltech.edu/CaltechAUTHORS:20110620-160433649
Full text not available from this repository.
Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20110620-160433649
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).
|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).|
|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|
|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.|
|Deposited By:||Marie Ary|
|Deposited On:||26 Sep 2011 22:53|
|Last Modified:||26 Sep 2011 22:53|
Repository Staff Only: item control page