Patent ID: 7765071

Claim:
A computer-implemented method for characterizing protein structures, the method comprising the steps of: accessing a database having a molecular structure of a protein, the molecular structure being represented as a set of spheres wherein said database is stored in a memory; retrieving the molecular structure of the protein from the database; and mathematically computing a Euclidean Voronoi diagram representing atoms of the protein from the set of spheres using a region-expansion algorithm, wherein the step of mathematically computing a Euclidean Voronoi diagram representing atoms of the protein from the set of spheres comprises the steps of: (a) retrieving a set of spheres; (b) computing initial Voronoi diagram for the centers of said set of spheres; (c) expanding spheres in said set one by one; (d) adjusting said initial Voronoi diagram based on the expanded spheres wherein while one of said spheres expands, corresponding region expands in such a way that a topology among vertices, edges, faces, and regions for said adjusted Voronoi diagram is consistently maintained; and (e) computing a complete Euclidean Voronoi diagram for the protein by repeating the steps (c)˜(d), said step of mathematically computing a Euclidean Voronoi diagram is performed by a processor.