An efficient algorithm for three-dimensional β-complex and β-shape via a quasi-triangulation

ABSTRACT

The concept of a β-shape has been recently proposed by extending the concept of the well-known α-shape. Since the β-shape takes full consideration of the Euclidean geometry of spherical particles, it is better suited than the (weighted) α-shape for applications using spatial queries on the system of variable sized spheres based on the Euclidean distance metric. In this paper, we present an efficient and elegant algorithm which computers a β-shape from a quasi-triangulation in O(log m + k) time in the worst case, where the quasi-triangulation has m simplicies and the boundary of β-shape consists of k simplicies. We believe that the β-shape and β-complex for a set of variable sized spheres (such as the atoms in a protein) will be very useful in the near future since the precise and efficient analysis of molecular structure can be conveniently facilitated by using these structures.

REFERENCES

• 1: Cho, Y., Kim, D., and Kim, D.-S. 2005. Topology representation for the Voronoi diagram of 3D spheres. International Journal of CAD/CAM 5, 1, 59--68.
• 2: Connolly, M. L. 1983. Analytical molecular surface calculation. Journal of Applied Crystallography 16, 548--558.
• 3: Connolly, M. L. 1983. Solvent-accessible surfaces of proteins and nucleic acids. Science 221, 709--713.
• 4: Herbert Edelsbrunner , Ernst P. Mücke, Three-dimensional alpha shapes, ACM Transactions on Graphics (TOG), v.13 n.1, p.43-72, Jan. 1994 [doi>10.1145/174462.156635]
• 5: Herbert Edelsbrunner , Michael Facello , Jie Liang, On the definition and the construction of pockets in macromolecules, Discrete Applied Mathematics, v.88 n.1-3, p.83-102, Nov. 9, 1998 [doi>10.1016/S0166-218X(98)00067-5]
• 6: Heifets, A., and Eisenstein, M. 2003. Effect of local shape modifications of molecular surfaces on rigid-body protein-protein docking. Protein Engineering 16, 3, 179--185.
• 7: Kim, D., and Kim, D.-S. 2006. Region-expansion for the Voronoi diagram of 3D spheres. Computer-Aided Design 38, 5 (May), 417--430.
• 8: Deok-Soo Kim , Donguk Kim , Kokichi Sugihara, Voronoi diagram of a circle set from Voronoi diagram of a point set: geometry, Computer Aided Geometric Design, v.18 n.6, p.563-585, July 2001 [doi>10.1016/S0167-8396(01)00051-6]
• 9: Kim, D.-S., Cho, Y., and Kim, D. 2004. Edge-tracing algorithm for Euclidean Voronoi diagram of 3D spheres. In Proceedings of the 16th Canadian Conference on Computational Geometry, 176--179.
• 10: Kim, D.-S., Cho, Y., and Kim, D. 2005. Euclidean Voronoi diagram of 3D balls and its computation via tracing edges. Computer-Aided Design 37, 13, 1412--1424.
• 11: Kim, D.-S., Cho, Y., Kim, D., Kim, S., Bhak, J., and Lee, S.-H. 2005. Euclidean Voronoi diagrams of 3D spheres and applications to protein structure analysis. Japan Journal of Industrial and Applied Mathematics 22, 2 (June), 251--265.
• 12: Kim, D.-S., Cho, C.-H., Kim, D., and Cho, Y. 2006. Recognition of docking sites on a protein using β-shape based on Voronoi diagram of atoms. Computer-Aided Design 38, 5 (May), 431--443.
• 13: Kim, D.-S., Kim, D., Cho, Y., and Sugihara, K. 2006. Quasi-triangulation and interworld data struction in three dimensions. Computer-Aided Design 38, 7, 808--819.
• 14: Kim, D.-S., Seo, J., Kim, D., Ryu, J., and Cho, C.-H. 2006. Three-dimensional beta shapes. Computer-Aided Design 38, 11, 1179--1191.
• 15: Lee, B., and Richards, F. M. 1971. The interpretation of protein structures: Estimation of static accessibility. Journal of Molecular Biology 55, 379--400.
• 16: Liang, J., Edelsbrunner, H., and Woodward, C. 1998. Anatomy of protein pockets and cavities: Measurement of binding site geometry and implications for ligand design. Protein Science 7, 1884--1897.
• 17: Atsuyuki Okabe , Barry Boots , Kokichi Sugihara, Spatial tessellations: concepts and applications of Voronoi diagrams, John Wiley & Sons, Inc., New York, NY, 1992
• 18: Peters, K. P., Fauck, J., and Frömmel, C. 1996. The automatic search for ligand binding sites in protein of known three dimensional structure using only geometric criteria. Journal of Molecular Biology 256, 201--213.
• 19: Ryu, J., Park, R., and Kim, D.-S. 2007. Molecular surfaces on proteins via beta shapes. Computer-Aided Design (in press).
• 20: Shoichet, B., and Kunts, I. 1991. Protein docking and complementarity. Journal of Molecular Biology 221, 327--346.
• 21: Will, H.-M. 1999. Computation of Additively Weighted Voronoi Cells for Applications in Molecular Biology. PhD thesis, Swiss Federal Institute of Technology, Zurich.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations

  J. Computer Applications
  J.2 PHYSICAL SCIENCES AND ENGINEERING

Keywords:
α-complex, α-shape, β-complex, β-shape, Voronoi diagram of spheres, complex, quasi-triangulation