Enhanced dead-end elimination in the search for the global minimum energy conformation of a collection of protein side chains

Although the conformational states of protein side chains canbe described using a library of rotamers, the determinationof the global minimum energy conformation (GMEC) of a largecollection of side chains, given fixed backbone coordinates,represents a challenging combinatorial problem with importantapplications in the field of homology modelling. Recently, wehave developed a theoretical framework, called the dead-endelimination method, which allows us to identify efficientlyrotamers that cannot be members of the GMEC. Such dead-endingrotamers can be iteratively removed from the system under studythereby tracking down the size of the combinatorial problem.Here we present new developments to the dead-end eliminationmethod that allow us to handle larger proteins and more extensiverotamer libraries. These developments encompass (i) a procedureto determine weight factors in the generalized dead-end eliminationtheorem thereby enhancing the elimination of dead-ending rotamersand (ii) a novel strategy, mainly based on logical argumentsderived from the logic pairs theorem, to use dead-ending rotamerpairs in the efficient elimination of single rotamers. Thesedevelopments are illustrated for proteins of various sizes andthe flow of the current method is discussed in detail. The effectivenessof dead-end elimination is increased by two orders of magnitudeas compared with previous work. In addition, it now becomesfeasible to use extremely detailed libraries. We also providean appendix in which the validity of the generalized dead-endcriterion is shown. Finally, perspectives for further applicationswhich may now become within reach are discussed.