This dissertation focuses on the application of a new search algorithm, the difference map, to the problem of protein structure prediction.

First a short review of protein structure is given to explain the terms and concepts used in the following chapters. A brief description of the current structure determination techniques (x-ray diffraction, NMR) are given, but the bulk of this dissertation is focused on ab initio structure prediction. Using ab initio methods, the native fold of a protein is assumed to be the global minimum of a high dimensional energy function. The current methods for minimizing this energy function are reviewed. The next chapter introduces a new search algorithm, the difference map. The difference map has been applied to many fields and problems where an exhaustive search is not feasible. A brief description of its historical development is given. Following this is an explanation of how the algorithm efficiently searches a high dimensional search space. A program called the difference map explorer was created to explore the effects of various difference map parameters on the search dynamics of the algorithm.

The application of the difference map to the problem of protein energy minimization is demonstrated in chapter 3. In this chapter, the rate at which the difference map produces low energy protein conformations is compared with that of a Monte Carlo based search algorithm, parallel tempering. It is shown that the difference map finds low energy protein conformations at a significantly higher rate than parallel tempering. The final chapter describes in detail NENA, the software implementation of the difference map folding algorithm.