University of Wisconsin Computer Sciences Header Map (repeated with 
textual links if page includes departmental footer) Useful Resources Research at UW-Madison CS Dept UW-Madison CS Undergraduate Program UW-Madison CS Graduate Program UW-Madison CS People Useful Information Current Seminars in the CS Department Search Our Site UW-Madison CS Computer Systems Laboratory UW-Madison Computer Sciences Department Home Page UW-Madison Home Page

A. Soni, C. Bingman & J. Shavlik (2010).
Guiding Belief Propagation using Domain Knowledge for Protein-Structure Determination. Proceedings of the ACM International Conference on Bioinformatics and Computational Biology (ACM-BCB), Niagara Falls, New York.
Slides (PPTX).

This publication is available in PDF.

The slides for this publication are available in Microsoft PowerPoint.


A major bottleneck in high-throughput protein crystallography is producing protein-structure models from an electron-density map. In previous work, we developed Acmi, a probabilistic framework for sampling all-atom protein-structure models. Acmi uses a fully connected, pairwise Markov random field to model the 3D location of each non-hydrogen atom in a protein. Since exact inference in this model is intractable, Acmi uses loopy belief propagation (BP) to calculate marginal probability distributions. In cases of approximation, BP's message-passing protocol becomes a crucial design decision. Previously, Acmi took a naive, round-robin protocol to sequentially process messages. Others have proposed informed methods for message scheduling by ranking messages based on the amount of new information they contain. These information-theoretic measures, however, fail in the highly connected, large output space domain of protein-structure inference. In this work, we develop a framework for using domain knowledge as a criterion for prioritizing messages in BP. Specifically, we show that using predictions of protein-disorder regions effectively guides BP in our task. Our results show that guiding BP using protein-disorder prediction improves the accuracy of marginal probability distributions and also produces more accurate, complete protein-structure models.

return Return to the publications of the Univ. of Wisconsin Machine Learning Research Group.

Computer Sciences Department
College of Letters and Science
University of Wisconsin - Madison


5355a Computer Sciences and Statistics ~ 1210 West Dayton Street, Madison, WI 53706 ~ voice: 608-262-1204 ~ fax: 608-262-9777