[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
research-article

Similarity Search of Flexible 3D Molecules Combining Local and Global Shape Descriptors

Published: 01 September 2016 Publication History

Abstract

In this paper, a framework for shape-based similarity search of 3D molecular structures is presented. The proposed framework exploits simultaneously the discriminative capabilities of a global, a local, and a hybrid local-global shape feature to produce a geometric descriptor that achieves higher retrieval accuracy than each feature does separately. Global and hybrid features are extracted using pairwise computations of diffusion distances between the points of the molecular surface, while the local feature is based on accumulating pairwise relations among oriented surface points into local histograms. The local features are integrated into a global descriptor vector using the bag-of-features approach. Due to the intrinsic property of its constituting shape features to be invariant to articulations of the 3D objects, the framework is appropriate for similarity search of flexible 3D molecules, while at the same time it is also accurate in retrieving rigid 3D molecules. The proposed framework is evaluated in flexible and rigid shape matching of 3D protein structures as well as in shape-based virtual screening of large ligand databases with quite promising results.

References

[1]
A. Bender and R. C. Glen, "Molecular similarity: A key technique in molecular informatics," Organic Biomolecular Chem., vol. 2, no. 22, pp. 3204-3218, 2004.
[2]
V. Venkatraman, L. Sael, and D. Kihara, "Potential for protein surface shape analysis using spherical harmonics and 3D Zernike descriptors," Cell Biochem. Biophys., vol. 54, nos. 1-3, pp. 23-32, 2009.
[3]
D. Kihara and J. Skolnick, "The PDB is a covering set of small protein structures," J. Molecular Biol., vol. 334, pp. 793-802, 2003.
[4]
L. Holm and C. Sander, "Protein structure comparison by alignment of distance matrices," J. Molecular Biol., vol. 233, no. 1, pp. 123-138, 1993.
[5]
K. Mizuguchi and N. Gö, "Comparison of spatial arrangements of secondary structural elements in proteins," Protein Eng., vol. 8, no. 4, pp. 353-362, 1995.
[6]
M. R. Betancourt and J. Skolnick, "Local propensities and statistical potentials of backbone dihedral angles in proteins," J. Molecular Biol., vol. 342, no. 2, pp. 635-649, 2004.
[7]
K. Kinoshita and H. Nakamura, "Identification of protein biochemical functions by similarity search using the molecular surface database eF-site," Protein Sci., vol. 12, no. 8, pp. 1589-1595, 2003.
[8]
M. E. Bock, G. M. Cortelazzo, C. Ferrari, and C. Guerra, "Identifying similar surface patches on proteins using a spinimage surface representation," in Proc. 16th Annu. Symp. Combinatorial Pattern Matching, 2005, pp. 417-428.
[9]
M. Ankerst, G. Kastenmüller, H. P. Kriegel, and T. Seidl, "3D shape histograms for similarity search and classification in spatial databases," in Proc. 16th Int. Symp. Adv. Spatial Databases, 1999, pp. 207-226.
[10]
J. S. Yeh, D. Y. Chen, B. Y. Chen, and M. Ouhyoung, "A web-based three-dimensional protein retrieval system by matching visual similarity," Bioinf., vol. 21, no. 13, pp. 3056-3057, 2005.
[11]
P. J. Ballester and W. G. Richards, "Ultrafast shape recognition to search compound databases for similar molecular shapes," J. Comput. Chem., vol. 28, no. 10, pp. 1711-1723, 2007.
[12]
P. J. Ballester and W. G. Richards, "Ultrafast shape recognition for similarity search in molecular databases," Proc. Roy. Soc. A: Math., Phys. Eng. Sci., vol. 463, no. 2081, pp. 1307-1321, 2007.
[13]
M.-K. Hu, "Visual pattern recognition by moment invariants," IRE Trans. Inf. Theory, vol. 8, no. 2, pp. 179-187, 1962.
[14]
M. R. Teague, "Image analysis via the general theory of moments," J. Opt. Soc. Am, vol. 70, no. 8, pp. 920-930, 1980.
[15]
C.-H. Teh and R. T. Chin, "On image analysis by the methods of moments," IEEE Trans. Pattern Anal. Mach. Intell., vol. 10, no. 4, pp. 496-513, Jul. 1988.
[16]
P. Daras, D. Zarpalas, A. Axenopoulos, D. Tzovaras, and M. G. Strintzis, "Three-dimensional shape-structure comparison method for protein classification," IEEE/ACM Trans. Comput. Biol. Bioinf., vol. 3, no. 3, pp. 193-207, Jul. 2006.
[17]
W. Cai, J. Xu, X. Shao, V. Leroux, A. Beautrait, and B. Maigret, "SHEF: A vHTS geometrical filter using coefficients of spherical harmonic molecular surfaces," J. Molecular Model., vol. 14, no. 5, pp. 393-401, 2008.
[18]
R. J. Morris, R. J. Najmanovich, A. Kahraman, and J. M. Thornton, "Real spherical harmonic expansion coefficients as 3D shape descriptors for protein binding pocket and ligand comparisons," Bioinf., vol. 21, no. 10, pp. 2347-2355, 2005.
[19]
D. W. Ritchie and G. J. Kemp, "Fast computation, rotation, and comparison of low resolution spherical harmonic molecular surfaces," J. Comput. Chem., vol. 20, no. 4, pp. 383-395, 1999.
[20]
D. W. Ritchie and G. J. Kemp, "Protein docking using spherical polar Fourier correlations," Proteins: Struct., Function, Bioinf., vol. 39, no. 2, pp. 178-194, 2000.
[21]
L. Mak, S. Grandison, and R. J. Morris, "An extension of spherical harmonics to region-based rotationally invariant descriptors for molecular shape description and comparison," J. Molecular Graph. Model., vol. 26, no. 7, pp. 1035-1045, 2008.
[22]
L. Sael, B. Li, D. La, Y. Fang, K. Ramani, R. Rustamov, and D. Kihara, "Fast protein tertiary structure retrieval based on global surface shape similarity," Proteins: Struct., Function, Bioinf., vol. 72, no. 4, pp. 1259-1273, 2008.
[23]
V. Venkatraman, Y. Yang, L. Sael, and D. Kihara, "Protein-protein docking using region-based 3D Zernike descriptors," BMC Bioinf., vol. 10, no. 1, p. 407, 2009.
[24]
V. Venkatraman, P. R. Chakravarthy, and D. Kihara, "Application of 3D Zernike descriptors to shape-based ligand similarity searching," J. Cheminform, vol. 17, no. 1, p. 19, 2009.
[25]
Y. Fang, Y.-S. Liu, and K. Ramani, "Three dimensional shape comparison of flexible proteins using the local-diameter descriptor," BMC Struct. Biol., vol. 9, p. 29, 2009.
[26]
Y.-S. Liu, Y. Fang, and K. Ramani, "IDSS: Deformation invariant signatures for molecular shape comparison," BMC Bioinf., vol. 10, p. 157, 2009.
[27]
Y.-S. Liu, K. Ramani, and M. Liu, "Computing the inner distances of volumetric models for articulated shape description with a visibility graph," IEEE Trans. Pattern Anal. Mach. Intell., vol. 33, no. 12, pp. 2538-2544, Dec. 2011.
[28]
Y.-S. Liu, Q. Li, G.-Q. Zheng, K. Ramani, and W. Benjamin, "Using diffusion distances for flexible molecular shape comparison," BMC Bioinf., vol. 11, p. 480, 2010.
[29]
S. Yin, E. A. Proctor, A. A. Lugovskoy, and N. V. Dokholyan, "Fast screening of protein surfaces using geometric invariant fingerprints," Proc. Nat. Acad. Sci. USA, vol. 106, no. 39, pp. 16622-16626, Sep. 29, 2009.
[30]
P. Heider, A. Pierre-Pierre, R. Li, and C. Grimm, "Local shape descriptors, a survey and evaluation," in Proc. 4th Eurograph. Conf. 3D Object Retrieval, 2011, pp. 49-56.
[31]
Z. Lian, A. Godil, X. Sun, and H. Zhang, "Non-rigid 3D shape retrieval using multidimensional scaling and bag-of-features," in Proc. Int. Conf. Image Process., 2010, pp. 3181-3184.
[32]
D. Smeets, T. Fabry, J. Hermans, D. Vandermeulen, and P. Suetens, "Isometric deformation modeling for object recognition," in Proc. 13th Int. Conf. Comput. Anal. Images Patterns, 2009, pp.757- 765.
[33]
G. Lavoue, "Bag of words and local spectral descriptor for 3D partial shape retrieval," in Proc. Eurograph. Workshop 3D Object Retrieval, 2011, pp. 41-48.
[34]
R. Ohbuchi, K. Osada, T. Furuya, and T. Banno, "Salient local visual features for shape-based 3D model retrieval," in Proc. IEEE Int. Conf. Shape Modeling Appl., Jun. 4-6, 2008, pp. 93-102.
[35]
S. Kawamura, K. Usui, T. Furuya, and R. Ohbuchi, "Local goemetrical feature with spatial context for shape-based 3D model retrieval," in Proc. 5th Eurograph. Conf. 3D Object Retrieval, 2012, pp. 55-58.
[36]
P. Daras, A. Axenopoulos, and G. Litos, "Investigating the effects of multiple factors towards more accurate 3D object retrieval," IEEE Trans. Multimedia, vol. 14, no. 2, pp. 374-388, Apr. 2012.
[37]
E. Wahl, U. Hillenbrand, and G. Hirzinger, "Surflet-pair-relation histograms: A statistical 3D-shape representation for rapid classification," in Proc. IEEE 4th Int. Conf. 3D Digital Imaging Model., 2003, pp. 474-481.
[38]
N. Echols, D. Milburn, and M. Gerstein, "MolMovDB: Analysis and visualization of conformational change and structural flexibility," Nucleic Acids Res., vol. 31, pp. 478-482, 2003.
[39]
W. H. Press, S. A. Teukolsky, W. T. Vetterling, and B. P. Flannery, Numerical Recipes in C+: The Art of Scientific Computing, vol. 994. Cambridge, U.K.: Cambridge Univ. Press, 2009.
[40]
R. Osada, T. Funkhouser, B. Chazelle, and D. Dobkin, "Shape distributions," ACM Trans. Graphics, vol. 21, no. 4, pp. 807-832, 2002.
[41]
D. Zhou, O. Bousquet, T. N. Lal, J. Weston, and B. Schölkopf, "Learning with local and global consistency," in Proc. Adv. Neural Inf. Process. Syst., 2003, pp. 321-328.
[42]
B. Nadler, S. Lafon, R. R. Coifman, and I. G. Kevrekidis, "Diffusion maps, spectral clustering and eigenfunctions of fokker-planck operators," in Proc. Adv. Neural Inform. Processing Syst., 2005, vol. 18, pp. 955-962.
[43]
N. Huang, B. K. Shoichet, and J. J. Irwin, "Benchmarking sets for molecular docking," J. Med. Chem., vol. 49, pp. 6789-6801, 2006.
[44]
J. J. Irwin and B. K. Shoichet, "ZINC-a free database of commercially available compounds for virtual screening," J. Chem. Inf. Model, vol. 45, pp. 177-182, 2005.
[45]
O. S. Weislow, R. Kiser, D. L. Fine, J. Bader, R. H. Shoemaker, and M. R. Boyd, "New soluble-formazan assay for HIV-1 cytopathic effects: Application to highflux screening of synthetic and natural products for AIDS-antiviral activity," J. Nat. Cancer. Inst., vol. 81, pp. 577-586, 1989.
[46]
A. Bender and R. C. Glen, "A discussion of measures of enrichment in virtual screening: Comparing the information content of descriptors with increasing levels of sophistication," J. Chem. Inf. Model, vol. 45, pp. 1369-1375, 2005.
[47]
J. F. Truchon and C. I. Bayly, "Evaluating virtual screening methods: Good and bad metrics for the "early recognition" problem," J. Chem. Inf. Model, vol. 47, pp. 488-508, 2007.
[48]
M. Hattori, Y. Okuno, S. Goto, and M. Kanehisa, "Development of a chemical structure comparison method for integrated analysis of chemical and genomic information in the metabolic pathways," J. Am. Chem. Soc., vol. 125, pp. 11853-11865, 2003.
[49]
L. Holm and C. Sander, "The FSSP database: Fold classification based on structure-structure alignment of proteins," Nucleic Acids Res., vol. 24, pp. 206-210, 1996.
[50]
L. Holm and C. Sander, "Touring protein fold space with Dali/ FSSP," Nucleic Acids Res., vol. 26, pp. 316-319, 1998.
[51]
M. F. Sanner, A. J. Olson, and J.-C. Spehner, "Fast and robust computation of molecular surfaces," in Proc. 11th ACM Symp. Comput. Geometry, 1995, pp. 406-407.
[52]
R. Kolodny, D. Petrey, and B. Honig, "Protein structure comparison: Implications for the nature of 'fold space', and structure and function prediction," Curr. Opin. Struct. Biol., vol. 16, pp. 393-398, 2006.
[53]
I. N. Shindyalov and P. E. Bourne, "Protein structure alignment by incremental combinatorial extension (CE) of the optimal path," Protein Eng., vol. 11, pp. 739-747, 1998.
[54]
P. Daras and A. Axenopoulos, "A compact multi-view descriptor for 3D object retrieval," in Proc. IEEE 7th Int. Workshop Content-Based Multimedia Indexing, Chania, Greece, Jun. 2009, pp. 115-119.
[55]
S. C. Flores, L. J. Lu, J. Yang, N. Carriero, and M. B. Gerstein, "Hinge atlas: Relating protein sequence to sites of structural flexibility," BMC Bioinf., vol. 8, p. 167, 2007.
[56]
R. Gal, A. Shamir, and D. Cohen-Or, "Pose-oblivious shape signature," IEEE Trans. Visualization Comput. Graph., vol. 13, no. 2, pp. 261-271, Mar./Apr. 2007.
[57]
R. M. Rustamov, "Laplace-Beltrami eigenfunctions for deformation invariant shape representation," in Proc. 5th Eurograph. Symp. Geometry Process., 2007, pp. 225-233.
[58]
L. Nanni, J. Y. Shi, S. Brahnam, and A. Lumini, "Protein classification using texture descriptors extracted from the protein backbone image," J. Theoretical Biol., vol. 264, no. 3, pp. 1024-1032, 2010.
[59]
D.-Y. Chen, X.-P. Tian, Y.-T. Shen, and M. Ouhyoung, "On visual similarity based 3D model retrieval," Comput. Graph. Forum, vol. 22, no. 3, pp. 223-232, 2003.
[60]
T. Furuya and R. Ohbuchi, "Dense sampling and fast encoding for 3D model retrieval using bag-of-visual features," in Proc. ACM Int. Conf. Image Video Retrieval, 2009, p. 26, article 26.
[61]
Z. Lian, A. Godil, B. Bustos, M. Daoudi, J. Hermans, S. Kawamura, Y. Kurita, G. Lavoué, H. Van Nguyen, R. Ohbuchi, Y. Ohkita, Y. Ohishi, F. Porikli, M. Reuter, I. Sipiran, D. Smeets, P. Suetens, H. Tabia, and D. Vandermeulen, "A comparison of methods for nonrigid 3D shape retrieval," Pattern Recog., vol. 46, no. 1, pp. 449-461, Jan. 2013.
[62]
B. Li, A. Godil, M. Aono, X. Bai, T. Furuya, L. Li, R. López-Sastre, H. Johan, R. Ohbuchi, C. Redondo-Cabrera, A. Tatsuma, T. Yanagimachi, and S. Zhang, "SHREC'12 track: Generic 3D shape retrieval," in Proc. 5th Eurograph. Workshop 3D Object Retrieval, 2012, pp. 119-126.
[63]
Y. Ohkita, Y. Ohishi, T. Furuya, and R. Ohbuchi, "Non-rigid 3D model retrieval using set of local statistical features," in Proc. IEEE Int. Conf. Multimedia Expo Workshops, 2012, pp.593-598.
[64]
Y. Zhang and J. Skolnick, "TM-align: A protein structure alignment algorithm based on TM-score," Nucleic Acids Res., vol. 33, pp. 2302-2309, 2005.
[65]
Y. Ye and A. Godzik, "Flexible structure alignment by chaining aligned fragment pairs allowing twists," Bioinf., vol. 19, no. Suppl. 2, pp. II246-II255, 2003.
[66]
I. N. Shindyalov and P. E. Bourne, "Protein structure alignment by incremental combinatorial extension (CE) of the optimal path," Protein Eng., vol. 11, no. 9, pp. 739-747, 1998.
[67]
M. Shatsky, H. J. Wolfson, and R. Nussinov, "Flexible protein alignment and hinge detection," Proteins: Struct., Function, Genetics, vol. 48, pp. 242-256, 2002.
[68]
Z. Li, P. Natarajan, Y. Ye, T. Hrabe, and A. Godzik, "POSA: A user-driven, interactive multiple protein structure alignment server," Nucl. Acids Res., vol. 42, pp. W240-W245, 2014.
[69]
A. Mademlis, P. Daras, D. Tzovaras, and M. G. Strintzis, "3D object retrieval based on resulting fields," presented at the 29th Int. Conf. Workshop 3D Object Retrieval, Crete, Greece, Apr. 2008.
[70]
S. C. Flores and M. B. Gerstein, "FlexOracle: Predicting flexible hinges by identification of stable domains," BMC Bioinf., vol. 8, no. 1, p. 215, 2007.
[71]
Y. Y. Tseng, J. Dundas, and J. Liang, "Predicting protein function and binding profile via matching of local evolutionary and geometric surface patterns," J. Molecular Biol., vol. 387, no. 2, pp. 451-464, 2009.
[72]
T. A. Binkowski, L. Adamian, and J. Liang, "Inferring functional relationships of proteins from local sequence and spatial surface patterns," J. Molecular Biol., vol. 332, no. 2, pp. 505-526, 2003.
[73]
J. Konc and D. Jane¿i¿, "ProBiS-2012: Web server and web services for detection of structurally similar binding sites in proteins," Nucleic Acids Res., vol. 40, pp. W214-W221, 2012.
[74]
A. Sharma, A. Papanikolaou, and E. S. Manolakos, "Accelerating all-to-all protein structures comparison with TMalign using a NoC many-cores processor architecture," in Proc. IEEE 27th Int. Parallel Distrib. Process. Symp. Workshops PhD Forum, 2013, pp. 510-519.
[75]
B. Y. Chen and B. Honig, "VASP: A volumetric analysis of surface properties yields insights into protein-ligand binding specificity," PLoS Comput. Biol., vol. 6, no. 8, p. e1000881, 2010.
[76]
B. Y. Chen, "VASP-E: Specificity annotation with a volumetric analysis of electrostatic isopotentials," PLoS Comput. Biol., vol. 10, no. 8, p. e1003792, 2014.
[77]
S. R. Amin et al., "Prediction and experimental validation of enzyme substrate specificity in protein structures," Proc. Nat. Acad. Sci. USA, vol. 110, no. 45, pp. E4195-E4202, 2013.

Cited By

View all
  • (2022)Virtual Screening Based on Electrostatic Similarity and Flexible LigandsComputational Science and Its Applications – ICCSA 2022 Workshops10.1007/978-3-031-10562-3_10(127-139)Online publication date: 4-Jul-2022
  • (2022)Increasing the Accuracy of Optipharm’s Virtual Screening Predictions by Implementing Molecular FlexibilityBioinformatics and Biomedical Engineering10.1007/978-3-031-07802-6_20(234-245)Online publication date: 27-Jun-2022
  • (2021)3D non-rigid shape similarity measure based on Fréchet distance between spectral distance distribution curveMultimedia Tools and Applications10.1007/s11042-020-09420-580:1(615-640)Online publication date: 1-Jan-2021
  • Show More Cited By
  1. Similarity Search of Flexible 3D Molecules Combining Local and Global Shape Descriptors

      Recommendations

      Comments

      Please enable JavaScript to view thecomments powered by Disqus.

      Information & Contributors

      Information

      Published In

      cover image IEEE/ACM Transactions on Computational Biology and Bioinformatics
      IEEE/ACM Transactions on Computational Biology and Bioinformatics  Volume 13, Issue 5
      September 2016
      193 pages

      Publisher

      IEEE Computer Society Press

      Washington, DC, United States

      Publication History

      Published: 01 September 2016
      Published in TCBB Volume 13, Issue 5

      Qualifiers

      • Research-article

      Contributors

      Other Metrics

      Bibliometrics & Citations

      Bibliometrics

      Article Metrics

      • Downloads (Last 12 months)3
      • Downloads (Last 6 weeks)0
      Reflects downloads up to 11 Dec 2024

      Other Metrics

      Citations

      Cited By

      View all
      • (2022)Virtual Screening Based on Electrostatic Similarity and Flexible LigandsComputational Science and Its Applications – ICCSA 2022 Workshops10.1007/978-3-031-10562-3_10(127-139)Online publication date: 4-Jul-2022
      • (2022)Increasing the Accuracy of Optipharm’s Virtual Screening Predictions by Implementing Molecular FlexibilityBioinformatics and Biomedical Engineering10.1007/978-3-031-07802-6_20(234-245)Online publication date: 27-Jun-2022
      • (2021)3D non-rigid shape similarity measure based on Fréchet distance between spectral distance distribution curveMultimedia Tools and Applications10.1007/s11042-020-09420-580:1(615-640)Online publication date: 1-Jan-2021
      • (2021)Fitting PB1-p62 filaments model structure into its electron microscopy based on an improved genetic algorithmJournal of Combinatorial Optimization10.1007/s10878-019-00483-142:4(937-947)Online publication date: 1-Nov-2021
      • (2018)Protein shape retrievalProceedings of the 11th Eurographics Workshop on 3D Object Retrieval10.5555/3290638.3290648(53-61)Online publication date: 16-Apr-2018

      View Options

      Login options

      Full Access

      View options

      PDF

      View or Download as a PDF file.

      PDF

      eReader

      View online with eReader.

      eReader

      Media

      Figures

      Other

      Tables

      Share

      Share

      Share this Publication link

      Share on social media