This question is partially addressed in
RotamerTrie --
JackSnoeyink - 02 Apr 2005
Rotamer Energy Calculation
--
AndrewLeaverFay - 21 Feb 2005
Problem: minimize the number of additions and table-look-ups in calculating the pair interaction energy for two sets of rotamers on two neighboring atoms. The energy function between two pairs of rotamers is the sum of the pair interaction energies between atoms; the interactions that need to be calculated can be described graphically. Think of the complete bipartite graph K_m_n (subscript?) where m is the number of atoms in rotamer 1 and n is the number of atoms in rotamer 2. The edges in this graph represent the interactions that must be computed. Each edge is the interaction between a pair of atoms. The interaction energy for the rotamer pair (rotamers 1 and 2) is the sum of the interaction energies given by each edge in the graph.
Let there be
r rotamers on residue
A, and
a atoms on each rotamer. There are
r*a atoms total for residue
A. These
r*a atoms will interact with the
r*a atoms on another residue, residue
B. Again, the edges in a complete bipartite graph describe the interactions that must be computed - this time the graph is K_r*a,_r*a. Now lets say that for residue
A many rotamers share the same atom. By saying that two atoms are "the same atom," I mean that the atoms' type (aliphatic-carbon, arromatic-carbon, hydroxyl-hydrogen, etc.) are identical for both atoms in their corresponding rotamers, and their locations (xyz in 3-space) are identical for both atoms in their corresponding rotamers. In this case, we may merge the vertices in the bipartite graph that correspond to these two identical atoms into a single vertex - the number of edges in the resulting bipartite graph decreases, thus making the problem smaller. I must perform table lookups for each edge in the resulting graph - store the atom-pair interaction energies, and then add them to the respective rotamers.
The first step in minimizing the energy computation is to merge all identical atoms together. If I drop the number of atoms (so all remaining are unique) by half, I reduce the number of table-look-ups by a factor of four. This is because the number of table-look-ups is quadratic in the number of atoms.
The problem does not stop here.
I now store a table of unique-atom pair interactions. I must add the atom-pair-interaction energies for each rotamer pair. But many rotamer pairs share multiple atoms. Consider two pairs of leucine rotamers. One pair belongs to residue
A, one pair belongs to residue
B. Let's say that the dihedral geometry of the pairs is identical - and that the dihedral geometry within a single pair differs only at the distal Chi-2 dihedral. The dihedral angles might look like: rotamer 1 for residue
A: (180, 60), rotamer 2 for residue
A: (180, 180). Rotamer 1 for residue
B: (180, 60), rotamer 2 for residue
B: (180, 180). There are four interactions which must be scored. A1 vs B1, A1 vs B2, A2 vs B1, A2 vs B2. The most efficient way to add the atom-pair-interaction energies is to store one value that describes the pair interaction between the two leucines for only the atoms (CA, CB, HB1, HB2, CG1) for the two residues since these atoms appear in exactly the same position in all four rotamer pairs. Only after this inital calculation should the four variant rotamer interactions be separated.
The answer seems obvious if only a pair of rotamer pairs is to be computed. The real problem is to optimize this calculation if there are many rotamer pair interactions.
What is the most efficient way to divide the calculations?
Most shared atoms are because the rotamer grows from the Calpha, and this structure can be used to share memory and computation. Once the computation is done in preprocessing 'the result is stored in an
r*r table, and the
a*a factor is gone. --
JackSnoeyink - 22 Feb 2005