ConfMatch: automating electron-density map interpretation by matching conformations

Building a protein model from the initial three-dimensional electron-density distribution (density map) is an important task in X-ray crystallography. This problem is computationally challenging because proteins are extremely flexible. The algorithm ConfMatch is a global real-space fitting procedure in torsion-angle space. It solves this `map-interpretation' problem by matching a detailed conformation of the molecule to the density map (conformational matching). This `best-match' structure is defined as one which maximizes the sum of the density at atom positions. ConfMatch is a practical systematic algorithm based on a branch-and-bound search. The most important idea of ConfMatch is an efficient method for computing accurate bounds. ConfMatch relaxes the conformational matching problem, a problem which can only be solved in exponential time, into one which can be solved in polynomial time. The solution to the relaxed problem is a guaranteed upper bound for the conformational matching problem. In most empirical cases, these bounds are accurate enough to prune the search space dramatically, enabling ConfMatch to solve structures with more than 100 free dihedral angles. Experiments have shown that ConfMatch may be able to automate the interpretation of density maps of small proteins.