AMBIPACK - A SYSTEMATIC ALGORITHM FOR PACKING OF MACROMOLECULAR STRUCTURES WITH AMBIGUOUS DISTANCE CONSTRAINTS

The determination of structures of multimers presents interesting new challenges. The structure(s) of the individual monomers must be found and the transformations to produce the packing interfaces must be desc ribed. A substantial difficulty results from ambiguities in assigning intermolecular distance measurements (from nuclear magnetic resonance, for example) to particular intermolecular interfaces in the structure . Here we present a rapid and efficient method to solve the packing an d the assignment problems simultaneously given rigid monomer structure s and (potentially ambiguous) intermolecular distance measurements. A promising application of this algorithm is to couple it with a monomer searching protocol such that each monomer structure consistent with i ntramolecular constraints can be subsequently input to the current alg orithm to check whether it is consistent with (potentially ambiguous) intermolecular constraints. The algorithm AmbiPack, uses a hierarchica l division of the search space and the branch-and-bound algorithm to e liminate infeasible regions of the space, Local search methods are the n focused on the remaining space. The algorithm generally runs faster as more constraints are included because more regions of the search sp ace can be eliminated. This is not the case for other methods, for whi ch additional constraints increase the complexity of the search space. The algorithm presented is guaranteed to find all solutions to a pred etermined resolution. This resolution can be chosen arbitrarily to pro duce outputs at various level of detail. Illustrative applications are presented for the P22 tailspike protein (a trimer) and portions of be ta-amyloid (an ordered aggregate). Proteins 32:26-42, 1998. (C) 1998 W iley-Liss, Inc.