Stochastic protein folding simulation in the three-dimensional HP-model

Abstract

We present results from three-dimensional protein folding simulations in the HP-model on ten benchmark problems. The simulations are executed by a simulated annealing-based algorithm with a time-dependent cooling schedule. The neighbourhood relation is determined by the pull-move set. The results provide experimental evidence that the maximum depth D of local minima of the underlying energy landscape can be upper bounded by $D<n^{2/3}$. The local search procedure employs the stopping criterion ${(m/\delta )}^{D/\gamma }$, where m is an estimation of the average number of neighbouring conformations, $\gamma$ relates to the mean of non-zero differences of the objective function for neighbouring conformations, and $1-\delta$ is the confidence that a minimum conformation has been found. The bound complies with the results obtained for the ten benchmark problems.

Introduction

Anfinsen’s thermodynamic hypothesis motivates the attempt to predict protein folding by solving certain optimization problems (Anfinsen, 1973). However, there are two main difficulties with this approach: the precise definition of the energy function that has to be minimised, and the extremely difficult optimization problems arising from energy functions commonly used in folding simulations Neumaier, 1997, Greenberg et al., 2004. To overcome at least some of these difficulties, various lattice models and simplified energy functions have been introduced. One of the most popular lattice models of protein folding is the hydrophobic–hydrophilic (HP) model Dill et al., 1995, Aichholzer et al., 2003, Greenberg et al., 2004, Leite et al., 2004, Schiemann et al., 2005. In the HP-model, proteins are modelled as chains whose vertices are marked either as H (hydrophobic) or P (hydrophilic); the resulting chain is embedded into some lattice; H nodes are considered to attract each other while P nodes are neutral. An optimal embedding is one that maximizes the number of H–H contacts. The rationale for this objective is that hydrophobic interactions contribute a significant portion of the total energy function Greenberg et al., 2004, Brylinski et al., 2006. Unlike more sophisticated models of protein folding, the main goal of the HP-model is to explore broad qualitative questions about protein folding such as whether the dominant interactions are local or global with respect to the chain (Greenberg et al., 2004). A major goal of our research on stochastic protein folding simulations in the HP-model is to investigate whether optimum conformations computed within this model (and some refinements of this model) can serve as appropriate starting conformations for folding simulations of real protein sequences and realistic energy functions.

In the present paper we focus on complexity aspects of protein folding simulations. For a variety of lattice models, protein folding simulation has been proven to be $\text{NP}$-complete Paterson and Przytycka, 1996, Berger and Leighton, 1998, Nayak et al., 1999, which a priori implies an upper time bound $\exp (n)$ for deterministic folding simulations of sequences of length n (unless $\text{P}=\text{NP}$, which is generally considered to be unlikely). To the best of our knowledge, Clote (1999) was the first to present a rigorous complexity analysis of protein folding simulations to optimum conformations. The underlying model is Monte Carlo simulations, and the aim is to provide a theoretical underpinning for an earlier work by Sali et al. (1994) where the authors conjecture that the folding time is inverse proportional to the energy gap between the ground state and the lowest energy of a misfolded state. By using the notion of rapidly mixing Markov chains (Sinclair, 1993), Clote (1999) prove an upper bound for the mean first passage time through the ground state that decreases if the energy gap increases. The upper bound does not explicitly relate protein sequence parameters to the first passage time. For protein sequences of length n, Fu and Wang (2004) proved an $\exp (O(n^{1-1/d}\cdot \ln n))$ deterministic algorithm for d-dimensional protein folding simulation to optimum conformations in the HP-model. Linear time algorithms for constant-factor approximations of optimum conformations are reported by Hart and Istrail (1997) and Heun (2003); however, protein folding is one of the problems where indeed the knowledge of optimum solutions is essential.

The importance of the HP-model is highlighted by the fact that the algorithmic complexity bound by Fu and Wang (2004) comes close to the (worst case) folding time approximation of $\exp (\lambda \cdot n^{2/3}\pm \chi \cdot n^{1/2}/2)$ ns by Finkelstein and Badretdinov (1997), where $\lambda$ and $\chi$ are constants close to unity. We note that both time bounds depend on the sequence length n only. In our paper, we try to link the time estimation to crucial parameters of the underlying energy landscape induced by a particular sequence. This is motivated by the ongoing attempts to improve folding time approximations for specific (subsets of) protein sequences. For example, Bakk et al. (2002) suggest folding time approximations of $O(n^2)$ and $\exp (O(\sqrt{n}))$ for some small globular proteins; Galzitskaya et al. (2003) stress the dependence of folding time on sequence length and analyse folding time estimations of type $\exp (O(n^p))$, $0<p\le 1$, for 54 proteins, where $41\le n\le 396$; a comprehensive experimental study of folding time as a function of temperature is presented by Zhu et al. (2004) for a single sequence (and its mutants); similar problems are discussed by Lee et al. (2003), Leite et al. (2004), Wang (2004), and Li et al. (2004), based on analytical approximations and numeric simulations. We note that the model used by Li et al. (2004) is close to the above-mentioned HP-model and the model employed by Clote (1999), including a combinatorial neighbourhood similar to the one we utilize in the present paper. The coefficient $\lambda$ in the folding time approximation by Finkelstein and Badretdinov (1997) has been further analysed by Ivankov et al. (2003).

We analyse a sequence-dependent time bound for protein folding simulations in the HP-model. The simulations utilize a stochastic local search procedure that is based on a specific type of simulated annealing. Simulated annealing-based search has been discussed and applied in the context of protein folding simulation for about twenty years Li and Scheraga, 1987, Wilson et al., 1988, Kawai et al., 1989 as an extension of Monte Carlo methods (Paine and Scheraga, 1985), shortly after the independent introduction of simulated annealing as a new optimization tool by Kirkpatrick et al. (1983) and Černy (1985). For on overview on early applications of simulated annealing to protein folding simulations, we refer the reader to Hansmann and Okamoto (1996). Apart from simulated annealing, search-based methods like genetic algorithms Unger and Moult, 1993, Rabow and Scheraga, 1996, Cooper et al., 2003 and tabu search (Pardalos et al., 1997) have been applied to protein folding simulation (see also Greenberg et al., 2004). More recent simulated annealing-related applications to protein folding simulation can be found in Eastman et al. (2001) and Klepeis et al. (2003).

In order to be able to relate the time bound of simulations to landscape parameters, we utilize the cooling schedule $T=T(k)=D/\log (k+2)$ in simulated annealing procedures, where D is the maximum value of the minimum escape height from local minima of the underlying conformation space, i.e. the transition probabilities are time-dependent. Under some natural assumptions about the conformation space, the probability distribution over the conformation space tends to the distribution over optimum solutions (Hajek, 1988). We note that Hajek’s result has been discussed before in the wider context of protein folding by Reidys and Stadler (2002) and Apaydin et al. (2003).

We focus on the three-dimensional rectangular lattice model, but extensions to other lattice models, e.g. as described by Backofen (2004), are actually depending upon the definition of a suitable neighbourhood relation only. We employ the pull-move set for the definition of the neighbourhood relation in the conformation space, which was independently introduced by Lesh et al. (2003) and Milostan et al. (2003) (see also Blazewicz et al., 2005). We further analyse experimentally the time complexity bound ${(m/\delta )}^{a\cdot D}$ for protein folding simulations as presented by Albrecht and Steinhöfel (2006) and Steinhöfel et al. (2007a), where a is a small constant and D the above-mentioned maximum escape height from local minima; the parameter $m=O(n)$ depends on the lattice structure and the pull-move set; the value $p=1-\delta$ indicates the confidence that a minimum energy conformation has been found after the number of search steps provided by the complexity bound.

In the present paper, the complexity bound is improved to ${(m/\delta )}^{D/\gamma }$, where $\gamma$ relates to the mean of non-zero differences between the values of the objective function for neighbouring conformations. Unfortunately, to calculate or approximate the parameter D by analytical methods is, in general, a difficult problem. Therefore, we try to provide experimental evidence for a worst case upper bound that depends on the sequence length n only. Based on Fu and Wang (2004) and Finkelstein and Badretdinov (1997), we conjecture $D<n^{2/3}$. The conjecture is verified on ten benchmark problems defined by Beutler and Dill (1996) (see also Blazewicz et al., 2005). For $m=n/2$, $1-\delta =0.5$ and $D=n^{2/3}/\kappa <n^{2/3}$ with $\kappa >1$, the upper bound complies with the results of our computational experiments and we were able to find ground states for all ten benchmark problems.

We note that the simulation experiments in the present paper are not optimized with respect to the run-time in order to have a strict comparison to the theoretical convergence bound (i.e. the impact of the parameter D). A preliminary version of the present paper has been presented at the International Conference on Bioinformatics Research and Development in March 2007 (Steinhöfel et al., 2007b).