Hydrogen atoms, with their single electron, cannot be resolved in x-ray diffraction experiments. Thus, their positions are not included in the PDB, but must be inferred for proper analysis of protein packing and for understanding of structural energetics. The software REDUCE written by Michael Word, now at GlaxoSmithKlein, tries to place hydrogens on the PDB structure to maximize the volume of electron orbital overlap for hydrogen bond partners and minimize overlap where hydrogen bonding is not possible. Additionally, histidine rings and the ends of asparagines and glutamine side chains must be allowed to flip, as crystal structures are most often unable to distinguish between carbon and nitrogen, or nitrogen and oxygen. Since these three amino acids can participate in hydrogen bonding, their orientation must also be optimized.

In the original software, the configuration of interacting groups of ambiguous elements was selected by brute-force enumeration of all possible states after discretizing placement of certain hydrogen atoms, e.g. hydroxyl hydrogens. Because sphere overlap is localized, the interaction graph of ambiguous elements is sparse. We developed and implemented a dynamic programming solution that reduces the computational complexity from exponential to linear in all observed cases. This insight, along with an additional efficiency in scoring sphere overlap, has allowed us to compute the optimal configuration in less than two minutes for one file that would previously have required six and a half years.