Belief Propagation Algorithms: From Matching to Cancer Genomics
We review belief propagation algorithms inspired by the study of phase transitions in combinatorial optimization problems. In particular, we present rigorous results on convergence of such algorithms for matching and associated bargaining problems. We also present a belief propagation algorithm for the prize-collecting Steiner tree problem, for which rigorous convergence results are not yet known. Finally, we show how this algorithm can be used to discover associations in cancer genomics, and to suggest drug therapies for cancer.
Jennifer Chayes, Microsoft Research, US