Abstract
Protein consists of amino acids, and an amino acid consists of atoms. Given a protein, understanding its functions is critical for various reasons for designing new drugs, treating diseases, and so on. Due to recent researches, it is now known that the structure of protein directly influences its functions. Hence, there have been strong research trends towards understanding the geometric structure of proteins. In this paper, we present a Euclidean Voronoi diagram of atoms constituting a protein and show how this computational tool can effectively and efficiently contribute to various important problems in biology. Some examples, among others, are the computations for molecular surface, solvent accessible surface, extraction of pockets, interaction interface, convex hull, etc.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Angelov, B., Sadoc, J.-F., Jullien, R., Soyer, A., Mornon, J.-P., Chomilier, J.: Nonatomic solvent-driven Voronoi tessellation of proteins: an open tool to analyze protein folds. Proteins: Structure, Function, and Genetics 49, 446–456 (2002)
Aurenhammer, F.: Power diagrams: properties, algorithms and applications. SIAM Journal of Computing 16, 78–96 (1987)
Bajaj, C.L., Lee, H.Y., Merkert, R., Pascucci, V.: NURBS based B-rep models for macromolecules and their properties. In: Proc. 4th Symposium on Solid Modeling and Applications, pp. 217–228 (1997)
Boissonnat, J.D., Karavelas, M.I.: On the combinatorial complexity of Euclidean Voronoi cells and convex hulls of d-dimensional spheres. In: Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 305–312 (2003)
Cheng, H.-L., Dey, T.K., Edelsbrunner, H., Sullivan, J.: Dynamic skin triangulation. Discrete & Computational Geometry 25, 525–568 (2001)
Kim, D.-S., Cho, C.-H., Cho, Y., Won, C.I., Kim, D.: Pocket recognition on a protein using Euclidean Voronoi diagram of atoms. In: Gervasi, O., Gavrilova, M.L., Kumar, V., Laganá, A., Lee, H.P., Mun, Y., Taniar, D., Tan, C.J.K. (eds.) ICCSA 2005. LNCS, vol. 3480, pp. 707–715. Springer, Heidelberg (2005)
Connolly, M.L.: Solvent-accessible surfaces of proteins and nucleic acids. Science 221, 709–713 (1983)
Edelsbrunner, H., Facello, M., Liang, J.: On the definition and the construction of pockets in macromolecules. Discrete Applied Mathematics 88, 83–102 (1998)
Farin, G.: Curves and Surfaces for Computer-Aided Geometric Design: A Practical Guide, 4th edn. Academic Press, San Diego (1996)
Gavrilova, M.: Proximity and Applications in General Metrics. Ph.D. thesis: The University of Calgary, Dept. of Computer Science, Calgary, AB, Canada (1998)
Gavrilova, M., Rokne, J.: Updating the topology of the dynamic Voronoi diagram for spheres in Euclidean d-dimensional space. Computer Aided Geometric Design 20, 231–242 (2003)
Gerstein, M., Tsai, J., Levitt, M.: The volume of atoms on the protein surface: calculated from simulation, using Voronoi polyhedra. Journal of Molecular Biology 249, 955–966 (1995)
Goede, A., Preissner, R., Frömmel, C.: Voronoi cell: new method for allocation of space among atoms: elimination of avoidable errors in calculation of atomic volume and density. Journal of Computational Chemistry 18, 1113–1123 (1997)
Kim, D.-S., Kim, D., Sugihara, K.: Voronoi diagram of a circle set from Voronoi diagram of a point set: I. Topology. Computer Aided Geometric Design 18, 541–562 (2001)
Kim, D.-S., Kim, D., Sugihara, K.: Voronoi diagram of a circle set from Voronoi diagram of a point set: II. Geometry. Computer Aided Geometric Design 18, 563–585 (2001)
Kim, D.-S., Cho, Y., Kim, D., Cho, C.-H.: Protein structure analysis using Euclidean Voronoi diagram of atoms. In: Proc. International Workshop on Biometric Technologies (BT 2004), Special Forum on Modeling and Simulation in Biometric Technology, pp. 125–129 (2004)
Kim, D.-S., Cho, Y., Kim, D.: Edge-tracing algorithm for Euclidean Voronoi diagram of 3D spheres. In: Proc. 16th Canadian Conference on Computational Geometry, pp. 176–179 (2004)
Kim, D.-S., Cho, Y., Kim, D., Kim, S., Bhak, J., Lee, S.-H.: Euclidean Voronoi diagram of 3D spheres and applications to protein structure analysis. In: Proc. International Symposium on Voronoi Diagrams in Science and Engineering, pp. 137–144 (2004)
Kunts, I.D.: Structure-based strategies for drug design and discovery. Science 257, 1078–1082 (1992)
Lee, B., Richards, F.M.: The interpretation of protein structures: estimation of static accessibility. Journal of Molecular Biology 55, 379–400 (1971)
Liang, J., Edelsbrunner, H., Woodward, C.: Anatomy of protein pockets and cavities: Measurement of binding site geometry and implications for ligand design. Protein Science 7, 1884–1897 (1998)
Lozano-Perez, T.: Spatial planning: a configuration space approach. IEEE Transactions on Computers 32, 108–120 (1983)
Montoro, J.C.G., Abascal, J.L.F.: The Voronoi polyhedra as tools for structure determination in simple disordered systems. The Journal of Physical Chemistry 97, 4211–4215 (1993)
Peters, K.P., Fauck, J., Frömmel, C.: The automatic search for ligand binding sites in protein of known three-dimensional strucutre using only geometric criteria. Journal of Molecular Biology 256, 201–213 (1996)
Richards, F.M.: The interpretation of protein structures: total volume, group volume distributions and packing density. Journal of Molecular Biology 82, 1–14 (1974)
Richards, F.M.: Areas, volumes, packing and protein structure. Annu. Rev. Biophys. Bioeng. 6, 151–176 (1977)
Rokne, J.: Appolonius’s 10th problem. In: Arvo, J. (ed.) Graphics Gems II, pp. 19–24. Academic Press, London (1991)
Ryu, J., Kim, D., Cho, Y., Park, R., Kim, D.-S.: Computing molecular surfaces of proteins. In: ICCSA 2005 conference (2005) (submitted)
Varshney, A., Brooks Jr., F.P., Wright, W.V.: Computing smooth molecular surfaces. IEEE Computer Graphics and Applications 14, 19–25 (1994)
Voloshin, V.P., Beaufils, S., Medvedev, N.N.: Void space analysis of the structure of liquids. Journal of Molecular Liquids 96-97, 101–112 (2002)
Watson, J.D., Crick, F.H.C.: A structure for deoxyribose nucleid acid. Nature 171, 737–738 (1953)
Will, H.-M.: Computation of Additively Weighted Voronoi Cells for Applications in Molecular Biology. Ph.D. thesis, ETH, Zurich (1999)
RCSB Protein Data Bank Homepage (2004), http://www.rcsb.org/pdb/
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kim, DS. et al. (2005). Visualization and Analysis of Protein Structures Using Euclidean Voronoi Diagram of Atoms. In: Gervasi, O., et al. Computational Science and Its Applications – ICCSA 2005. ICCSA 2005. Lecture Notes in Computer Science, vol 3482. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11424857_107
Download citation
DOI: https://doi.org/10.1007/11424857_107
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-25862-9
Online ISBN: 978-3-540-32045-6
eBook Packages: Computer ScienceComputer Science (R0)