Figure 1. Voronoi/Delaunay tessellation in 2D space
An objective definition of nearest neighbors in three-dimensional space can be obtained by applying the methods of statistical geometry. The statistical geometry approach for studying structure of disordered systems was introduced by Bernal (Bernal 1959). He suggested characterization of structural disorder using statistical analysis of irregular polyhedra obtained by a specific tessellation in the three-dimensional space. The method, including the design and implementation of practical algorithms, was further developed by Finney for the case of Voronoi tessellation (Finney 1970, 1977). Voronoi tessellation partitions the space into convex polytopes called Voronoi polyhedra. For a molecular system the Voronoi polyhedron is the region of space around an atom, such that each point of this region is closer to the atom than to any other atom of the system. A group of four atoms whose Voronoi polyhedra meet at a common vertex forms another basic topological object called a Delaunay simplex. The procedure for constructing Voronoi polyhedra and Delaunay simplices in two dimensions is illustrated in Figure 1. The topological difference between these objects is that the Voronoi polyhedron represents the environment of individual atoms whereas the Delaunay simplex represents the ensemble of neighboring atoms. Although the Voronoi polyhedra and the Delaunay simplices are completely determined by each other, there exists a significant difference. Whereas the Voronoi polyhedra may differ topologically (i.e., they may have different numbers of faces and edges), the Delaunay simplices are always topologically equivalent (i.e., in three-dimensional space they are always tetrahedra). Delaunay tessellation has been used for structural analysis of various disordered systems. In most such cases it has served as a valuable tool for structure description ( Voloshin et al. 1988, Vaisman et al. 1994). In this paper we report for the first time the use of Delaunay tessellation to define objectively the nearest neighbor residues in 3D protein structures. The most significant feature of Delaunay tessellation, as compared with other methods of nearest neighbor identification, is that the number of nearest neighbors in three dimensions is always four, which represents a fundamental topological property of 3D space. Statistical analysis of the amino acid composition of Delaunay simplices provides information about spatial propensities of all quadruplets of amino acid residues to be clustered together in folded protein structures. The empirical four-body contact potentials derived from this analysis may significantly improve the results of protein structure prediction.
Figure 1. Voronoi/Delaunay tessellation in 2D space
(Voronoi tessellation - dashed line,
Delaunay tessellation - solid line).
