Hetunandan Kamisetty, Eric P. Xing and Chris J. Langmead, "Free
Energy Estimates of All-atom Protein Structures using
Generalized Belief Propagation." Proceedings of the Eleventh Annual
International Conference on Research in Computational
Molecular Biology (RECOMB 2007), pp:366-380 [pdf].
An earlier version appeared as CMU-CS-06-160.
We present a technique for approximating
the free energy of protein structures using Generalized Belief
Propagation (GBP). The accuracy and utility of these estimates are
then demonstrated in two different application domains. First, we
show that the entropy component of our free energy estimates can
be useful in distinguishing native protein structures from decoys.
Second, we show that our estimates of the changes in free energy of protein
structures upon mutation have a linear correlation of upto 0.70 with
laboratory measurements.
GBP is also efficient, taking a few minutes to run on a typical sized protein,
further suggesting that GBP may be an attractive alternative to
more costly molecular dynamic simulations for some tasks.
Hetunandan Kamisetty, Chris Bailey-Kellogg and Gopal Pandurangan, "An efficient randomized algorithm for contact-based
NMR backbone resonance assignment," Bioinformatics 2006, 22(2):172-180 [abstract, html, pdf, preprint(color)].
This paper develops, analyzes and applies a novel algorithm for the identification of polytopes representing consistent patterns of
edges in a corrupted NOESY graph. We employ an NMR-specific random graph
model in proving that our algorithm gives optimal performance in expected polynomial time,
even when the input graph is significantly corrupted. We confirm this analysis in simulation studies with graphs
corrupted by up to 500% noise. Finally, we demonstrate the practical application of the algorithm on several experimental ß-sheet
datasets. Our approach is able to eliminate a large majority of noise edges and to uncover large consistent sets of interactions.