We have defined the almost-Delaunay tetrahedra as a mathematical framework for modeling the effect of uncertainty in the coordinates of protein atoms on structures used to express proximity relations on these atoms - Voronoi Diagrams and Delaunay Tessellations. As the theoretical basis for this work, we defined almost-Delaunay k-simplices, the (k+1)-tuples of points in arbitrary dimensional space that can be made Delaunay neighbors (satisfying the empty sphere property) when all the points are allowed to move by at most some constant distance threshold from their original locations.

Delaunay tessellations have many applications in the structural analysis of proteins. We have been particularly considering statistical potentials defined by Alex Tropsha and others, where the protein is simplified to one point per residue (e.g. the C-alpha atom or the side-chain centroid). We have analyzed the almost-Delaunay tetrahedra to demonstrate the relative stability of the Delaunay tessellation in proteins compared to other similarly packed data sets. The experiments indicate that Tropsha's SNAPP method for analysis of protein packing using a Delaunay-based four-body potential is nearly as effective at distinguishing proteins from decoys when AD tetrahedra, unweighted or weighted by their Delaunay probability, are substituted for Delaunay tetrahedra. We have also applied AD tetrahedra to detect and quantify structural motifs in proteins. For the C-alpha atoms of synthetic alpha-helices, the almost-Delaunay tetrahedra have characteristic threshold values that can be associated with patterns of vertices along the protein backbone. This led to a novel method to detect and individually enumerate alpha-helices purely from geometric criteria, robustly and accurate to within 5-10% of the number of helix residues determined by DSSP, a standard method for secondary structure assignment. Knowing the helical content, we are working on quantifying interactions such as inter-helix packing. We have also devised criteria based on almost-Delaunay tetrahedra to identify residues in beta-sheets and beta-turns, somewhat less accurately than alpha-helices. The work will extend to handle more complex motifs.