×

Almost-Delaunay simplices: Robust neighbor relations for imprecise 3D points using CGAL. (English) Zbl 1114.65308

Summary: This paper describes a new computational geometry technique, almost-Delaunay simplices, that was implemented for 3D points using CGAL. Almost-Delaunay simplices capture possible sets of Delaunay neighbors in the presence of a bounded perturbation, and give a framework for nearest neighbor analysis in imprecise point sets such as protein structures. The use of CGAL helps us tune our implementation so that it is reasonably fast and also performs robust computation for all inputs, and also lets us distribute our technique to potential users in a portable, reusable and extensible form. The implementation, available on http://www.cs.unc.edu/debug/software is faster and more memory efficient than our prototype MATLAB implementation, and enables us to scale our neighbor analysis to large sets of protein structures, each with 100-3000 residues.

MSC:

65D18 Numerical aspects of computer graphics, image analysis, and computational geometry
65Y15 Packaged methods for numerical algorithms
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Delaunay, B., Sur la sphère vide. A la memoire de Georges Voronoi, Izv. Akad. Nauk SSSR, Otdelenie Matematicheskih i Estestvennyh Nauk, 7, 793-800 (1934) · JFM 60.0946.06
[2] Branden, C.; Tooze, J., Introduction to Protein Structure (1999), Garland Publishing Inc.: Garland Publishing Inc. New York
[3] Liang, J.; Edelsbrunner, H.; Fu, P.; Sudhakar, P.; Subramaniam, S., Analytical shape computing of macromolecules II: Identification and computation of inaccessible cavities inside proteins, Proteins, 33, 18-29 (1998)
[4] 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)
[5] Carter, C. W.; LeFebvre, B. C.; Cammer, S.; Tropsha, A.; Edgell, M. H., Four-body potentials reveal protein-specific correlations to stability changes caused by hydrophobic core mutations, J. Molecular Biol., 311, 4, 625-638 (2001)
[6] Singh, R.; Tropsha, A.; Vaisman, I., Delaunay tessellation of proteins, J. Comput. Biol., 3, 213-222 (1996)
[7] Krishnamoorthy, B.; Tropsha, A., Development of a four-body statistical pseudo-potential to discriminate native from non-native protein conformations, Bioinformatics, 19, 1540-1548 (2003)
[8] Wako, H.; Yamato, T., Novel method to detect a motif of local structures in different protein conformations, Protein Engineering, 11, 981-990 (1998)
[9] D. Bandyopadhyay, J. Snoeyink, Almost-Delaunay simplices: Nearest neighbor relations for imprecise points, in: ACM-SIAM Symposium on Discrete Algorithms, 2004, pp. 403-412; D. Bandyopadhyay, J. Snoeyink, Almost-Delaunay simplices: Nearest neighbor relations for imprecise points, in: ACM-SIAM Symposium on Discrete Algorithms, 2004, pp. 403-412 · Zbl 1317.68244
[10] Barber, C. B.; Dobkin, D. P.; Huhdanpaa, H., The QuickHull algorithm for convex hulls, ACM Trans. Math. Softw., 22, 4, 469-483 (1996) · Zbl 0884.65145
[11] Hert, S.; Hoffmann, M.; Kettner, L.; Pion, S.; Seel, M., An adaptable and extensible geometry kernel, (Proc. Workshop on Algorithm Engineering. Proc. Workshop on Algorithm Engineering, Lecture Notes in Comput. Sci., vol. 2141 (2001), Springer-Verlag), 79-90 · Zbl 1002.68624
[12] Josuttis, N. M., The C++ Standard Library: A Tutorial and Reference (1999), Addison Wesley
[13] Vandevoorde, D.; Josuttis, N. M., C++ Templates: The Complete Guide (2002), Addison Wesley
[14] Meyers, S., Effective STL: 50 Specific Ways to Improve the Use of the Standard Template Library, Professional Computing Series (2001), Addison Wesley
[15] Austen, M. H., Generic Programming and The STL: Using and Extending the C++ Standard Template Library, Professional Computing Series (1999), Addison Wesley
[16] Alexandrescu, A., Modern C++ Design: Generic Programming and Design Patterns Applied, AW C++ in Depth Series (2001), Addison Wesley
[17] Brönnimann, H.; Kettner, L.; Schirra, S.; Veltkamp, R., Applications of the generic programming paradigm in the design of CGAL, (Jazayeri, M.; Loos, R.; Musser, D., Generic Programming—Proceedings of a Dagstuhl Seminar. Generic Programming—Proceedings of a Dagstuhl Seminar, Lecture Notes in Comput. Sci., vol. 1766 (2000), Springer), 206-217
[18] Fabri, A.; Giezeman, G.-J.; Kettner, L.; Schirra, S.; Schönherr, S., The CGAL kernel: A basis for geometric computation, (Lin, M. C.; Manocha, D., Proc. 1st ACM Workshop on Appl. Comput. Geom.. Proc. 1st ACM Workshop on Appl. Comput. Geom., Lecture Notes in Comput. Sci., vol. 1148 (1996), Springer-Verlag), 191-202
[19] Boissonnat, J.-D.; Devillers, O.; Pion, S.; Teillaud, M.; Yvinec, M., Triangulations in CGAL, Comput. Geom. Theory Appl., 22, 5-19 (2002) · Zbl 1016.68138
[20] K.Q. Brown, Geometric transforms for fast geometric algorithms, PhD thesis, Carnegie-Mellon University, Pittsburgh, PA, 1980; K.Q. Brown, Geometric transforms for fast geometric algorithms, PhD thesis, Carnegie-Mellon University, Pittsburgh, PA, 1980
[21] Trolltech AS, Q public license v1.0, 1999; Trolltech AS, Q public license v1.0, 1999
[22] J. Huan, W. Wang, D. Bandyopadhyay, J. Snoeyink, J. Prins, A. Tropsha, Mining protein family specific residue packing patterns from protein structure graphs, in: Eighth Annual International Conference on Research in Computational Molecular Biology (RECOMB), 2004, pp. 308-315; J. Huan, W. Wang, D. Bandyopadhyay, J. Snoeyink, J. Prins, A. Tropsha, Mining protein family specific residue packing patterns from protein structure graphs, in: Eighth Annual International Conference on Research in Computational Molecular Biology (RECOMB), 2004, pp. 308-315
[23] Brönnimann, H.; Burnikel, C.; Pion, S., Interval arithmetic yields efficient dynamic filters for computational geometry, (SCG ’98: Proceedings of the Fourteenth Annual Symposium on Computational Geometry (1998), ACM Press: ACM Press New York), 165-174
[24] O. Devillers, S. Pion, Efficient exact geometric predicates for Delaunay triangulations, in: 5th Workshop on Algorithm Engineering and Experiments (ALENEX 03), Baltimore, MD, 2003; O. Devillers, S. Pion, Efficient exact geometric predicates for Delaunay triangulations, in: 5th Workshop on Algorithm Engineering and Experiments (ALENEX 03), Baltimore, MD, 2003
[25] Shewchuk, J. R., Robust adaptive floating-point geometric predicates, (SCG ’96: Proceedings of the Twelfth Annual Symposium on Computational Geometry (1996), ACM Press: ACM Press New York), 141-150
[26] Moult, J.; Fidelis, K.; Zemla, A.; Hubbard, T., Critical assessment of methods of protein structure prediction (CASP)-round V, Proteins, 53, 6, 334-339 (2003), Suppl
[27] D. Bandyopadhyay, A geometric framework for robust nearest neighbor analysis of protein structure and function, PhD thesis, University of North Carolina, Chapel Hill, NC, 2005; D. Bandyopadhyay, A geometric framework for robust nearest neighbor analysis of protein structure and function, PhD thesis, University of North Carolina, Chapel Hill, NC, 2005
[28] Huan, J.; Bandyopadhyay, D.; Wang, W.; Snoeyink, J.; Prins, J.; Tropsha, A., Comparing graph representations of protein structure for mining family-specific residue-based packing motifs, J. Comput. Biol., 12, 6, 657-671 (2005)
[29] Bandyopadhyay, D.; Huan, J.; Liu, J.; Prins, J.; Snoeyink, J.; Wang, W.; Tropsha, A., Structure-based function inference using protein family-specific fingerprints, Protein Science, 15, 6, 1537-1543 (2006)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.