OpenProblems < BioGeometry

BioGeometry
BioGeometry.OpenProblemsr1.1 - 22 Feb 2005 - 10:33 - Main.guesttopic end
-- Main.AndrewLeaverFay - 21 Feb 2005


---++++ Rotamer Energy Calculation
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. -- Main.JackSnoeyink - 22 Feb 2005
to top
End of topic
Skip to action links | Back to top
You are here: BioGeometry > OpenProblems

to top