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
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.