×

Effect of increasing the energy gap between the two lowest energy states on the mixing time of the Metropolis algorithm. (English) Zbl 1250.92009

Summary: In order to understand what makes natural proteins fold rapidly, Šali, Shakhnovich and Karplus had used the Metropolis algorithm to search for the minimum energy conformations of chains of beads in the lattice model of protein folding. Based on their computational experiments, they concluded that the Metropolis algorithm would find the minimum energy conformation of a chain of beads within an acceptable time scale if and only if there is a large gap between the energies of the minimum energy conformation and that of the second minimum. P. Clote [Lect. Notes Comput. Sci. 1644, 240–249 (1999; Zbl 1037.92016)] attempted to support this conclusion by a proof that the mixing time of the underlying Markov chain would decrease as the gap in energies of the minimum energy conformation and that of the second minimum increased. He was able to show that an upper bound on the mixing time does indeed decrease as the energy gap increases. We show that the mixing time itself, however, is a non-decreasing function of the value of the energy gap. Therefore, our result contradicts what Clote had attempted to prove.

MSC:

92C40 Biochemistry, molecular biology
92-08 Computational methods for problems pertaining to biology
60J20 Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.)
68W99 Algorithms in computer science

Citations:

Zbl 1037.92016
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Clote, Peter, Protein folding, the Levinthal paradox and rapidly mixing Markov chains, (Proceedings of 26th International Colloquium on Automata, Languages and Programming. Proceedings of 26th International Colloquium on Automata, Languages and Programming, LNCS, vol. 1644 (1999)), 240-249 · Zbl 1037.92016
[2] Levin, David A.; Peres, Yuval; Wilmer, Elizabeth L., Markov Chains and Mixing Times (2009), American Mathematical Society · Zbl 1160.60001
[3] Sasaki, Galen, The effect of the density of states on the Metropolis algorithm, Inform. Process. Lett., 37, 159-163 (1991) · Zbl 0713.68027
[4] Sinclair, Alistair, Algorithms for Random Generation and Counting: A Markov Chain Approach (1993), Birkhäuser: Birkhäuser Berlin · Zbl 0780.68096
[5] Swagato Sanyal, S. Raja, Somenath Biswas, Necessary and sufficient conditions of the Metropolis algorithm for optimization, in: Proceedings of the Tenth ACM GECCO 2010, 2010, pp. 1417-1424.; Swagato Sanyal, S. Raja, Somenath Biswas, Necessary and sufficient conditions of the Metropolis algorithm for optimization, in: Proceedings of the Tenth ACM GECCO 2010, 2010, pp. 1417-1424.
[6] Šali, Andrej; Shakhnovich, Eugene; Karplus, Martin, How does a protein fold?, Nature, 369, 249-252 (1994)
[7] Šali, Andrej; Shakhnovich, Eugene; Karplus, Martin, Kinetics of protein folding: A lattice model study of the requirement for folding to the native state, J. Mol. Biol., 235, 1614-1636 (1994)
[8] Skolnick, J.; Kolinski, A., Dynamic Monte Carlo simulation of a new lattice model of globular protein folding, structure and dynamics, J. Mol. Biol., 221, 499-531 (1991)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.