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 can be described using a library of rotamers, the determination of the global minimum energy conformation (GMEC) of a large collection of side chains, given fixed backbone coordinates, represents a challenging combinatorial problem with important applications in the field of homology modelling. Recently, we have developed a theoretical framework, called the dead-end elimination method, which allows us to identify efficiently rotamers that cannot be members of the GMEC. Such dead-ending rotamers can be iteratively removed from the system under study thereby tracking down the size of the combinatorial problem. Here we present new developments to the dead-end elimination method that allow us to handle larger proteins and more extensive rotamer libraries. These developments encompass (i) a procedure to determine weight factors in the generalized dead-end elimination theorem thereby enhancing the elimination of dead-ending rotamers and (ii) a novel strategy, mainly based on logical arguments derived from the logic pairs theorem, to use dead-ending rotamer pairs in the efficient elimination of single rotamers. These developments are illustrated for proteins of various sizes and the flow of the current method is discussed in detail. The effectiveness of dead-end elimination is increased by two orders of magnitude as compared with previous work. In addition, it now becomes feasible to use extremely detailed libraries. We also provide an appendix in which the validity of the generalized dead-end criterion is shown. Finally, perspectives for further applications which may now become within reach are discussed.