| Over the past decade, the field of machine learning has seen a large increase in the study of probabilistic graphical models due to their ability to provide a compact representation of complex, multidimensional problems. Recently, the complexity posed in many applications has stressed the ability of algorithms to reason in graphical models. New techniques for inference are essential to meet the demands of these problems in an efficient and accurate manner.;One such area of application is the task of determining protein structures --- a core problem to the biology community. The imaging technique X-ray crystallography is central to many recent structural-genomic initiatives at is the most popular method for determining structures. In creating a high-throughput crystallography pipeline, however, the final step of constructing a protein model from an electron-density map remains a major bottleneck in need of computational methods.;In this thesis, I develop new inference techniques for the use of probabilistic graphical models for the automated determination of protein structures in electron-density maps. The first, guided belief propagation using domain knowledge, prioritizes messages in the popular belief propagation algorithm for approximate inference. Second, I develop Probabilistic Ensembles in ACMI (PEA) to leverage multiple executions of approximate inference to produce more accurate estimations of each variable's probability distribution. Lastly, I present work on the use of particle filtering for the purpose of providing physically feasible, all-atom protein structures.;I demonstrate that my new methods not only improve the accuracy of the probabilistic model in terms of log-likelihood values, but also produce protein structures with higher completeness and correctness. Across a set of poor-quality density maps, my work outperforms all related work in the field by improving the state-of-the-art technique, ACMI.;I also describe my contributions on the subtask of three-dimensional shape matching in electron-density maps by utilizing spherical-harmonic decompositions to quickly align two 3D objects over rotations. I show that this technique is more efficient and accurate than previous work at detecting small protein fragments as well as homologous protein structures. |
