A new approach to the problem of docking two molecules: The ellipsoid algorithm

Abstract A recently developed method of constrained optimization, known as the ellipsoid algorithm, is explored as a tool for determining sterically acceptable interactions between two molecules. These interactions are described by constraints on intermolecular distances. Upper distance bounds between specific pairs of atoms, one in the ligand and one in the enzyme, were used in two different types of docking problems. In the first type, knowledge of a small set of well‐defined upper distance constraints was assumed, e.g., specific information about hydrogen bonds or experimentally determined atom–atom distances. The second approach assumes only knowledge of the location of the binding site of one of the molecules, but nothing about how the second, typically small, molecule is packed into this site. In this case, a set of upper distance bounds was used one at a time to explore systematically all possible ways of packing the ligand into the site. In all applications, van der Waals repulsions were used to define a lower distance bound for each atom pair. To specify the relative orientation of the two molecules, a new set of variables had to be introduced. They enable us to represent the set of all possible rotations in a vector space as required by the ellipsoid algorithm. Consequently, in contrast to the usual Euler angles, they assure additivity, so that the result of multiple changes of the variables is not sensitive to the order in which they are performed. In addition to the six degrees of freedom involved in docking rigid objects, conformational flexibility can be explicitly included in the individual molecules. Applications discussed include the docking of two macromolecules and the formation of an enzyme–inhibitor complex. For each constraint set tested, ten randomly chosen starting structures were optimized. The time for each of the runs was between 3 min and 1.3 h on a VAX 750 or a Microvax II; in larger problems, the time is spent primarily in van der Waals checking. The advantages of the ellipsoid algorithm compared to other methods are its robustness with respect to local minima, and the relatively small amounts of computer time and memory that it needs. A final discussion compares this method to some other docking methods, including distance geometry and the matching of molecular surfaces.