Protein tertiary structure prediction using a branch and bound algorithm.

We report a new method for predicting protein tertiary structure from sequence and secondary structure information. The predictions result from global optimization of a potential energy function, including van der Waals, hydrophobic, and excluded volume terms. The optimization algorithm, which is based on the alphaBB method developed by Floudas and coworkers (Costas and Floudas, J Chem Phys 1994;100:1247-1261), uses a reduced model of the protein and is implemented in both distance and dihedral angle space, enabling a side-by-side comparison of methodologies. For a set of eight small proteins, representing the three basic types--all alpha, all beta, and mixed alpha/beta--the algorithm locates low-energy native-like structures (less than 6A root mean square deviation from the native coordinates) starting from an unfolded state. Serial and parallel implementations of this methodology are discussed.

A branch and bound algorithm for protein structure refinement from sparse NMR data sets.

We describe new methods for predicting protein tertiary structures to low resolution given the specification of secondary structure and a limited set of long-range NMR distance constraints. The NMR data sets are derived from a realistic protocol involving completely deuterated 15N and 13C-labeled samples. A global optimization method, based upon a modification of the alphaBB (branch and bound) algorithm of Floudas and co-workers, is employed to minimize an objective function combining the NMR distance restraints with a residue-based protein folding potential containing hydrophobicity, excluded volume, and van der Waals interactions. To assess the efficacy of the new methodology, results are compared with benchmark calculations performed via the X-PLOR program of Brünger and co-workers using standard distance geometry/molecular dynamics (DGMD) calculations. Seven mixed alpha/beta proteins are examined, up to a size of 183 residues, which our methods are able to treat with a relatively modest computational effort, considering the size of the conformational space. In all cases, our new approach provides substantial improvement in root-mean-square deviation from the native structure over the DGMD results; in many cases, the DGMD results are qualitatively in error, whereas the new method uniformly produces high quality low-resolution structures. The DGMD structures, for example, are systematically non-compact, which probably results from the lack of a hydrophobic term in the X-PLOR energy function. These results are highly encouraging as to the possibility of developing computational/NMR protocols for accelerating structure determination in larger proteins, where data sets are often underconstrained.