Proteins and other biological macromolecules undergo large conformational changes as part of their natural function. These changes are largely driven by energy functions involving pairwise interactions among the atoms. Most forces in nature are short range and defined by pairwise interactions, and thus efficient computer simulation of these processes need to maintain lists of pairs of atoms which are sufficiently close to have a significant energetic interaction. We are developing techniques based on the notion of graph spanners towards this goal. A spanner for a molecule is a lightweight, combinatorial structure that consists of a list of atom pairs providing a set of shortcuts in going from one part of the molecule to another. The spanner guarantees that the shortest path between any two atoms in the graph defined by the molecular bonds and these additional shortcuts is a close approximation to the Euclidean distance between the atoms. In particular, before two atoms can collide, there has to be a spanner shortcut between them.

We extend this approach to forces defined by the interaction of three or more atoms at a time. For example, the hydrophobic effect is modeled in terms of a weighted area or volume, which can be computed using inclusion-exclusion with terms for singletons, pairs, triplets and quadruplets. The alpha complex of the molecule identifies these terms, but there are others that give the same result. We identified the class of independent complexes to have the right inclusion-exclusion structure; these are similar to alpha complexes but relax the interior triangulation by only requiring the independence of all simplices. We use the ambiguity to our advantage since it implies that just because the Delaunay triangulation or the alpha complex changed due to a local motion does not necessarily imply that we have to change our independent complex. Using the lightweight spanner, we detect global changes in the complex, and we are now working on a complementary strategy that detects necessary local changes to maintain the independence of the complex.