FAST PROTEIN-FOLDING IN THE HYDROPHOBIC-HYDROPHILIC MODEL WITHIN 3 8 OF OPTIMAL/

We present performance-guaranteed approximation algorithms for the pro tein folding problem in the hydrophobic-hydrophilic model (Dill, 1985) . Our algorithms are the first approximation algorithms in the literat ure with guaranteed performance for this model (Dill, 1994). The hydro phobic-hydrophilic model abstracts the dominant force of protein foldi ng: 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., n onpolar) and P (hydrophilic, i.e., polar). Although this model is a si mplification of more complex protein folding models, the protein foldi ng structure prediction problem is notoriously difficult for this mode l. Our algorithms have linear (3n) or quadratic time and achieve a thr ee-dimensional protein conformation that has a guaranteed free energy no worse than three-eighths of optimal. This result answers the open p roblem of Ngo et al. (1994) about the possible existence of an efficie nt approximation algorithm with guaranteed performance for protein str ucture prediction in any well-studied model of protein folding. By ach ieving speed and near-optimality simultaneously, our algorithms rigoro usly capture salient features of the recently proposed framework of pr otein folding by Sali et al. (1994). Equally important, the final conf ormations 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 propo sed by Karplus and Weaver (1979). Computational limitations of algorit hms that compute the optimal conformation have restricted their applic ability to short sequences (length less than or equal to 90). Because our algorithms trade computational accuracy for speed, they can constr uct near-optimal conformations in linear time for sequences of any siz e.