Scaling behavior of stochastic minimization algorithms in a perfect funnel landscape

We determined scaling laws for the numerical effort to find the optimal configurations of a simple model potential energy surface (PES) with a perfect funnel structure that reflects key characteristics of the protein interactions. Generalized Monte Carlo methods [Monte Carlo minimization and stochastic tunneling (MCM, STUN)] avoid an enumerative search of the PES and thus provide a natural resolution of the Levinthal paradox. We find that the computational effort grows with approximately the eighth power of the system size for MCM and STUN, while a genetic algorithm was found to scale exponentially. The scaling behavior of a derived lattice model is also rationalized. [S1063-651X(99)01701-8].