Evolutionary and energy-domain Monte Carlo algorithms and their applications

DMS-0505732PI：Wong Hung Wong教授研究：斯坦福大学：进化和能域蒙特卡罗算法及其应用本项目将开发两种用于蒙特卡罗模拟的新算法，并将它们应用于几个科学和技术问题。第一种方法被称为进化蒙特卡罗，由PI的实验室在之前NSF的支持下引入。它已在蛋白质折叠中的HP模型和基于CP的模型选择等挑战性问题中得到了很好的应用。本文提出了一种用于有向无环图模型(DAG)网络结构计算推理的进化MC。第二种方法称为等能量抽样，由PI和他的合作者开发的早期阶段。这个想法是从等能量环中产生样本，每个环的能量都在一个有限的值区间内。能量-温度二元性被用来允许从微观正则平均值(即等能环内的平均值)的估计中估计玻尔兹曼平均值(即，对应于固定温度的平均值)。除了给出玻尔兹曼平均的估计值外，该方法还给出了“态密度”函数和配分函数的估计值。因此，等能量采样可以在一次运行中提供所有热力学变量的信息，因此它在蛋白质折叠等物理应用中应该是一个非常有吸引力的算法。近年来，马尔可夫链蒙特卡罗方法的发展使得统计建模和推理应用于越来越多的应用领域。对于DNA基序采样、蛋白质折叠、因果网络结构的统计推断等许多重要应用，蒙特卡罗计算已经成为不可或缺的工具。本项目提出的工作将显著提高蒙特卡罗算法在具有复杂能量场景的问题中的性能，从而使该方法应用于更广泛的问题是可行的。

Abstract for DMS - 0505732PI: Professor Wing Hung WongINSTITUTION: STANFORD UNIVERSITYTITLE: Evolution and Energy Domain Monte Carlo algorithms and their applicationsThis 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.