Approximate Inference and Protein-Folding

Side-chain prediction is an important subtask in the protein-folding problem. We show that finding a minimal energy side-chain con(cid:173) figuration is equivalent to performing inference in an undirected graphical model. The graphical model is relatively sparse yet has many cycles. We used this equivalence to assess the performance of approximate inference algorithms in a real-world setting. In cases where exact inference was possible, max-product BP al(cid:173) ways found the global minimum of the energy (except in few cases where it failed to converge), while other approximation algorithms of similar complexity did not.