Evolutionary and energy-domain Monte Carlo algorithms and their applications

Stanford University, Stanford CA

Investigators

Abstract

Abstract for DMS - 0505732 PI: Professor Wing Hung Wong INSTITUTION: STANFORD UNIVERSITY TITLE: Evolution and Energy Domain Monte Carlo algorithms and their applications This project will develop two new algorithms for Monte Carlo simulation and applied them to several problems in science and technology. The first method, called Evolutionary Monte Carlo, was introduced by the PI's laboratory under prior NSF support. It has been applied with excellent results in challenging problems such as the HP model in protein folding and Cp-based model selection. Here, it is proposed that Evolutionary MC be developed for the computational inference of network structure for directed acylic graphical models (DAG). The second method, called equi-energy sampling, is in an early stage of development by the PI and his collaborators. The idea is to generate samples from the equi-energy rings each of them having the energy lying within a restricted interval of values. An energy-temperature duality is exploited to allow the estimation of a Boltzmann average (i.e. averages corresponding to a fixed temperature) from estimates of the micro-canonical averages (i.e. averages within equi-energy rings). In addition to giving estimates of Boltzmann averages, this approach also provide estimates for the "density of states" function and the partition function. Thus equi-energy sampling can provide information for all thermodynamic quantities in a single run, and for this reason it should be a very attractive algorithm in physical applications such as protein folding. Recent development of Markov Chain Monte Carlo methods has allowed the application of statistical modeling and inference to more and more application areas. For many important applications such as DNA motif sampling, protein folding, and statistical inference of causal network structures, Monte Carlo computation has become an indispensable tool. The work proposed in this project will result in significant improvement of the performance Monte Carlo algorithms in problems with complex energy landscapes, and therefore will make it feasible to apply this method to a wider spectrum of problems.