FINDING THE GLOBAL MINIMUM - A FUZZY END ELIMINATION IMPLEMENTATION

The 'fuzzy end elimination theorem' (FEE) is a mathematically proven t heorem that identifies rotameric states in proteins which are incompat ible,vith the global minimum energy conformation, While implementing t he FEE we noticed two different aspects that directly affected the fin al results at convergence. First, the identification of a single dead- ending rotameric state can trigger a 'domino effect' that initiates th e identification of additional rotameric states which become dead-endi ng, A recursive check for dead-ending rotameric states is therefore ne cessary every time a dead-ending rotameric state is identified. It is shown that, if the recursive check is omitted, it is possible to miss the identification of some dead-ending rotameric states causing a prem ature termination of the elimination process. Second, we examined the effects of removing dead-ending rotameric states from further consider ations at different moments of time. Two different methods of rotameri c state removal were examined for an order dependence. In one case, ea ch rotamer found to be incompatible with the global minimum energy con formation was removed immediately following its identification, In the other, dead-ending rotamers were marked for deletion but retained dur ing the search, so that they influenced the evaluation of other rotame ric states. When the search was completed, all marked rotamers were re moved simultaneously. In addition, to expand further the usefulness of the FEE, a novel method is presented that allows for further reductio n in the remaining set of conformations at the FEE convergence. In thi s method, called a tree-based search, each dead-ending pair of rotamer s which does not lead to the direct removal of either rotameric state is used to reduce significantly the number of remaining conformations. In the future this method can also be expanded to triplet and quadrup let sets of rotameric states. We tested our implementation of the FEE by exhaustively searching ten protein segments and found that the FEE identified the global minimum every time. For each segment, the global minimum was exhaustively searched in two different environments: (i) the segments were extracted from the protein and exhaustively searched in the absence of the surrounding residues; (ii) the segments were ex haustively searched in the presence of the remaining residues fixed at crystal structure conformations. We also evaluated the performance of the method for accurately predicting side chain conformations. We exa mined the influence of factors such as type and accuracy of backbone t emplate used, and the restrictions imposed by the choice of potential function, parameterization and rotamer database. Conclusions are drawn on these results and future prospects are given.