William E. Hart and Sorin Istrail
Sandia National Laboratories MS 1110, Albuquerque, NM 87185-1110
We present performance-guaranteed approximation algorithms for the protein folding problem in the hydrophobic-hydrophilic model, Dill (1985). To our knowledge, our algorithms are the first approximation algorithms in the literature with guaranteed performance for this model, Dill (1994). The hydrophobic-hydrophilic model abstracts the dominant force of protein folding: the hydrophobic interaction. The protein is modeled as a chain of amino acids of length n that are of two types: H (hydrophobic, i.e., nonpolar) and P (hydrophilic, i.e., polar). Although this model is a simplification of more complex protein folding models, the protein folding structure prediction problem is notoriously difficult for this model. Our algorithms have linear (3n) or quadratic time and achieve a three-dimensional protein conformation that has a guaranteed free energy no worse than 8 of optimal. This result answers the open problem of Ngo, Marks and Karplus (1994) about the possible existence of an efficient approximation algorithm with guaranteed performance for protein structure prediction in any well-studied model of protein folding. By achieving speed and near-optimality simultaneously, our algorithms rigorously capture salient features of the recently proposed framework of protein folding by Sali, Shakhnovich and Karplus (1994). Equally important, the final conformations of our algorithms have significant secondary structure (anti-parallel sheets, beta sheets, compact hydrophobic core). Furthermore, hypothetical folding pathways can be described for our algorithms that fit within the framework of diffusion-collision protein folding proposed by Karplus and Weaver (1979). Computational limitations of algorithms that compute the optimal conformation have restricted their applicability to short sequences (length less than or equal to 90). Because our algorithms trade computational accuracy for speed, they can construct near-optimal conformations in linear time for sequences of any size.
 K. A. Dill, Biochemistry, 24:1501, 1985
 K. A. Dill, Personal Communication, 1994
 J. T. Ngo, J. Marks, M. Karplus, Computational complexity, protein structure prediction, and the Levinthal paradox in The Protein Folding Problem, ch. 14, pp. 435-508, Birkhauser, 1994
 A. Sali, E. Shakhnovich, M. Karplus, Nature, 369:248-251, 1994
 M. Karplus, D. L. Weaver, Biopolymers 18:1421, 1979
This work was supported by the U.S. Department of Energy and was performed at Sandia National Laboratories for the U.S. Department of Energy under contract DE-AC04-94AL85000.
Return to Table of Contents