Model Search in Highly Dimensional Constrained Graphical Models with Application to Protein Backbone Nuclear Magnetic Resonance Assignment

• Activity Number: 370
• Type: Contributed
• Date/Time: Wednesday, August 10, 2005 : 8:30 AM to 10:20 AM
• Sponsor: Section on Statistical Computing
• Author(s): Olga Vitek*+
• Companies: Purdue University
• Keywords: graphical models ; model search ; structural genomics ; adaptive sampling

Abstract

Constrained graphical models arise in applications where knowledge of subject matter imposes satisfiability restrictions on edges in the graph. Learning the structure of such models in Bayesian framework presents significant challenges. First, generating an admissible instance of a graph is computationally expensive. Second, the posterior landscape of the graphs is jagged, as even a small difference in edges can result in a sharp change in the graph's weight. Performance of existing methods such as MCMC is limited in these problems because they require highly tuned and dataset-specific proposal distributions. This talk describes an efficient approach to searching large spaces of constrained graphs. Instead of examining one candidate graph at a time, we recursively partition the graph space into small subspaces. The resulting tree structure is explored using a sampling procedure where the importance of branches is learned adaptively on the basis of previously visited graphs. We illustrate the approach on a problem from structural genomics, which consists of learning the assignment of protein backbone Nuclear Magnetic Resonances (NMR).