Combinatorial Optimization in Computational Protein Design

Citation

Gordon, David Benjamin (2000) Combinatorial Optimization in Computational Protein Design. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/fzxm-d394. https://resolver.caltech.edu/CaltechTHESIS:07312025-172124033

Abstract

The central objective of computational protein design is to develop computational techniques for selecting amino acid sequences that fold into proteins with desired structures and functions. The work described here is directed toward addressing issues that arise in the development of computational methods for the design of solvent-exposed portions of beta-sheets. However, it is also demonstrated that the results of these investigations extend beyond specific secondary structures and in fact provide a means to address a broad spectrum of design problems. Computational issues arise from the fact that when constructing a representation of protein sequence space for analysis, significant concessions must be made with respect to the physical model and the search criteria in order to ensure that the calculation remains tractable. One of the limiting factors driving these concessions is the sheer number of combinations of amino acid identities and configurations that must be evaluated. We have therefore pursued the development and refinement of high-performance combinatorial search algorithms in order to better enable improvement of computational methods. The consequent algorithmic work consists of enhancement strategies based on combining optimization methods and instilling within them heuristics that manifest specialized knowledge of protein design problems. The results are significant performance enhancements for the well-established Dead-End Elimination algorithm, as well as two new algorithmic approaches, dubbed Branch and Terminate and Hybrid Rotamer Optimization.

Thesis Files