0.3 Molecular shapes and surfaces  (Page 2/3)

Alpha-shapes

Part of the problem with defining the shape of a protein is that we start with nothing but a point set, and the "shape" of a set of discontinuous points is poorly defined. The problem is, what do we mean by shape? As you saw above, the shape of a molecule depends on what is being used to measure it. To handle this ambiguity, we will introduce a method of shape calculation based on a parameter, α, which will determine the radius of a spherical probe that will define the surface. The method defines a class of shapes, called α-shapes for any given point set. It allows fast, accurate, and efficient calculations of volume and surface area.

α-shapes are a generalization of the convex hull . Consider a point set S. Define an α-ball as a sphere of radius α. An α-ball is empty if it contains no points in S. For any α between zero and infinity, the α-hull of S is the complement of the union of all empty α-balls.

• For α of infinity, the α-shape is the convex hull of S.
• For α smaller than the 1/2 smallest distance between two points in S, the α-shape is S itself.
• For any α in between, one can think of the α-hull as the largest polygon (polyhedron) or set thereof whose vertices are in the point set and whose edges are of length less than 2α. The presence of an edge indicates that a probe of radius α cannot pass between the edge endpoints.

Computing the alpha-shape: delaunay triangulation

A triangulation of a three-dimensional point set S is any decomposition of S into non-intersecting tetrahedra (triangles for two-dimensional point sets). The Delaunay triangulation of S is the unique triangulation of S satisfying the additional requirement that no sphere circumscribing a tetrahedron in the triangulation contains any point in S. Although it is incidental to α-shapes, it is worth noting that the Delaunay triangulation maximizes the average of the smallest angle over all triangles. In other words, it favors relatively even-sided triangles over sharp and stretched ones.

• The points of S are sorted on one coordinate (x, y, or z). This step is not strictly necessary but makes the algorithm run faster than if the points were in arbitrary order.
• Each point is added in sorted order. Upon adding a point:
  • The point is connected to previously added points that are "visible" to it, that is, to points to which it can be connected by a line segment without passing through a face of a tetrahedron.
  • Any new tetrhedra formed are checked and flipped if necessary.
  • Any tetrahedra adjacent to flipped tetrahedra are checked and flipped. This continues until further flipping is unnecessary, which is guaranteed to occur