Like many other combinatorially massive systems, the
protein folding problem is currently
(and may be for a very long time) a computationally intractable problem to solve. Given that each link in a protein chain has 3 or more degrees of freedom, each able to occupy a large number of states, the number of possible shapes a particular protein explodes exponentially.
Often, rather than resorting to determining the structure of each new encountered protein, a first guess at protein structure made computationally based on
homology modelling. That is, determining the structure of the protein by comparing it to a database of known proteins and finding the best match. Such methods have a decent success rate at matching the shape of the protein
backbone. Getting the
sidechains correctly is another issue. For a protein
n amino acids long, with an average of
r rotamer states (rotational orientations), there are still
rn states to explore.
In order to find a solution,
Monte Carlo algorithms are applied that make random changes to the protein and decide whether the change resulted in an improvement. Basically, if a change results in a better structure, it is kept. Otherwise, its rejected and something else is tried instead. See
simulated annealing for details on the application of this. However, if your goal is to find the
best solution ... the
global minimum energy conformation (GMEC), you need to have an efficient way to deal with the
rn conformations.
Dead End Elimination (DEE) is one algorithm used to eliminate searching of structures which are not going to lead to the minimum solution. In order to speed up the search, the sooner a rotamer is determined to be unproductive, the less states containing that rotamer need to be searched. The discovery that one rotamer is dead ending can then affect the dead-ending criteria for subsequent residues. This selection is applied until no more dead-ending rotamers are found and the conformational space is tractably searchable.
Speeding up this process has applications in protein
threading and protein design. Threading requires the rapid evaluation of how a sequence fills a number of possible scaffolds. The scaffold which has the lowest energy is the best guess for the protein structure. In design, the same scaffold is often filled with many different sequences. In order to determine which sequence is optimal, a quick evaluation of the lowest energy state must be determined. DEE assists in arriving at this energy.
For further information, see:
The dead-end elimination theorem and its use in protein side-chain positioning. J Desmet, M De Maeyer, B Hazes, I Lasters,
Nature, v356 April 9, 1992. p 539.