Document Open Access Logo

pClay: A Precise Parallel Algorithm for Comparing Molecular Surfaces

Authors Georgi D. Georgiev, Kevin F. Dodd, Brian Y. Chen

PDF
Thumbnail PDF

File

LIPIcs.WABI.2019.6.pdf
  • Filesize: 5.17 MB
  • 13 pages

Document Identifiers

Author Details

Georgi D. Georgiev
  • Department of Computer Science and Engineering, Lehigh University, Bethlehem, PA, USA
Kevin F. Dodd
  • Department of Computer Science and Engineering, Lehigh University, Bethlehem, PA, USA
Brian Y. Chen
  • Department of Computer Science and Engineering, Lehigh University, Bethlehem, PA, USA

Cite AsGet BibTex

Georgi D. Georgiev, Kevin F. Dodd, and Brian Y. Chen. pClay: A Precise Parallel Algorithm for Comparing Molecular Surfaces. In 19th International Workshop on Algorithms in Bioinformatics (WABI 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 143, pp. 6:1-6:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.WABI.2019.6

Abstract

Comparing binding sites as geometric solids can reveal conserved features of protein structure that bind similar molecular fragments and varying features that select different partners. Due to the subtlety of these features, algorithmic efficiency and geometric precision are essential for comparison accuracy. For these reasons, this paper presents pClay, the first structure comparison algorithm to employ fine-grained parallelism to enhance both throughput and efficiency. We evaluated the parallel performance of pClay on both multicore workstation CPUs and a 61-core Xeon Phi, observing scaleable speedup in many thread configurations. Parallelism unlocked levels of precision that were not practical with existing methods. This precision has important applications, which we demonstrate: A statistical model of steric variations in binding cavities, trained with data at the level of precision typical of existing work, can overlook 46% of authentic steric influences on specificity (p <= .02). The same model, trained with more precise data from pClay, overlooked 0% using the same standard of statistical significance. These results demonstrate how enhanced efficiency and precision can advance the detection of binding mechanisms that influence specificity.

Subject Classification

ACM Subject Classification
  • Applied computing → Molecular structural biology
  • Computing methodologies → Volumetric models
  • Computing methodologies → Parallel algorithms
Keywords
  • Specificity Annotation
  • Structure Comparison
  • Cavity Analysis

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. F Aurenhammer. Power diagrams: properties, algorithms and applications. SIAM Journal on Computing, 16(1):78-96, 1987. Google Scholar
  2. CL Bajaj, V Pascucci, A Shamir, RJ Holt, and AN Netravali. Dynamic maintenance and visualization of molecular surfaces. Discrete Applied Mathematics, 127(1):23-51, 2003. Google Scholar
  3. J Bernal. REGTET: A program for computing regular tetrahedralizations. In International Conference on Computational Science, pages 629-632. Springer, 2001. Google Scholar
  4. M Brylinski and J Skolnick. A threading-based method (FINDSITE) for ligand-binding site prediction and functional annotation. P Natl Acad Sci USA, 105(1):129-134, 2008. Google Scholar
  5. BY Chen. VASP-E: Specificity annotation with a volumetric analysis of electrostatic isopotentials. PLoS computational biology, 10(8):e1003792, 2014. Google Scholar
  6. BY Chen and S Bandyopadhyay. VASP-S: A volumetric analysis and statistical model for predicting steric influences on protein-ligand binding specificity. In IEEE Int Conf Bioinformatics Biomed 2011, pages 22-29. IEEE, 2011. Google Scholar
  7. BY Chen, VY Fofanov, DH Bryant, BD Dodson, DM Kristensen, AM Lisewski, M Kimmel, O Lichtarge, and LE Kavraki. The MASH pipeline for protein function prediction and an algorithm for the geometric refinement of 3D motifs. J Comput Biol, 14(6):791-816, 2007. Google Scholar
  8. BY Chen and B Honig. VASP: a volumetric analysis of surface properties yields insights into protein-ligand binding specificity. PLoS computational biology, 6(8):e1000881, 2010. Google Scholar
  9. ML Connolly. Analytical molecular surface calculation. Journal of applied crystallography, 16(5):548-558, 1983. Google Scholar
  10. Herbert Edelsbrunner and Ernst P Mücke. Three-dimensional alpha shapes. ACM Transactions on Graphics (TOG), 13(1):43-72, 1994. Google Scholar
  11. L Ellingson and J Zhang. Protein surface matching by combining local and global geometric information. PloS one, 7(7):e40540, 2012. Google Scholar
  12. F Ferre, G Ausiello, A Zanzoni, and M Helmer-Citterich. Functional annotation by identification of local surface similarities: a novel tool for structural genomics. BMC Bioinf, 6(1):194, 2005. Google Scholar
  13. M Fischer, QC Zhang, F Dey, BY Chen, B Honig, and D Petrey. MarkUs: a server to navigate sequence-structure-function space. Nucleic acids research, 39(suppl_2):W357-W361, 2011. Google Scholar
  14. BG Godshall and BY Chen. Improving accuracy in binding site comparison with homology modeling. In IEEE Int Conf Bioinformatics Biomed 2012, pages 662-669. IEEE, 2012. Google Scholar
  15. L He, F Vandin, G Pandurangan, and C Bailey-Kellogg. Ballast: a ball-based algorithm for structural motifs. Journal of Computational Biology, 20(2):137-151, 2013. Google Scholar
  16. C-L Hung and Y-L Lin. Implementation of a parallel protein structure alignment service on cloud. International journal of genomics, 2013, 2013. Google Scholar
  17. T Ju, F Losasso, S Schaefer, and J Warren. Dual contouring of hermite data. In ACM transactions on graphics (TOG), volume 21 (3), pages 339-346. ACM, 2002. Google Scholar
  18. F Kaiser, A Eisold, and D Labudde. A novel algorithm for enhanced structural motif matching in proteins. Journal of Computational Biology, 22(7):698-713, 2015. Google Scholar
  19. K Kinoshita, Y Murakami, and H Nakamura. eF-seek: prediction of the functional sites of proteins by searching for similar electrostatic potential and molecular surface shape. Nucleic acids research, 35(suppl_2):W398-W402, 2007. Google Scholar
  20. J Konc, M Depolli, R Trobec, K Rozman, and D Janežič. Parallel-ProBiS: Fast parallel algorithm for local structural comparison of protein structures and binding sites. Journal of computational chemistry, 33(27):2199-2203, 2012. Google Scholar
  21. B Lee and FM Richards. The interpretation of protein structures: estimation of static accessibility. Journal of molecular biology, 55(3):379-IN4, 1971. Google Scholar
  22. Y Liu, K Shah, F Yang, L Witucki, and KM Shokat. A molecular gate which controls unnatural ATP analogue recognition by the tyrosine kinase v-Src. Bioorg Med Chem, 6(8):1219-1226, 1998. Google Scholar
  23. WE Lorensen and HE Cline. Marching Cubes: A High Resolution 3D Surface Construction Algorithm. In ACM siggraph computer graphics, volume 21 (4), pages 163-169. ACM, 1987. Google Scholar
  24. Thomas Madej, Christopher J Lanczycki, Dachuan Zhang, Paul A Thiessen, RC Geer, A Marchler-Bauer, and SH Bryant. MMDB and VAST+: tracking structural similarities between macromolecular complexes. Nucleic acids research, 42(D1):D297-D303, 2013. Google Scholar
  25. WA Martin and RJ Fateman. The MACSYMA system. In Proceedings of the second ACM symposium on Symbolic and algebraic manipulation, pages 59-75. ACM, 1971. Google Scholar
  26. NL Max and ED Getzoff. Spherical harmonic molecular surfaces. IEEE Computer Graphics and Applications, 8(4):42-50, 1988. Google Scholar
  27. EC Meng, BJ Polacco, and PC Babbitt. 3D Motifs. In From Protein Structure to Function with Bioinformatics, pages 187-216. Springer, 2009. Google Scholar
  28. RJ Morris, RJ Najmanovich, A Kahraman, and JM Thornton. Real spherical harmonic expansion coefficients as 3D shape descriptors for protein binding pocket and ligand comparisons. Bioinformatics, 21(10):2347-2355, 2005. Google Scholar
  29. BE Nolan, E Levenson, and BY Chen. Influential Mutations in the SMAD4 Trimer Complex Can Be Detected from Disruptions of Electrostatic Complementarity. Journal of Computational Biology, 24(1):68-78, 2017. Google Scholar
  30. D Petrey and B Honig. GRASP2: visualization, surface properties, and electrostatics of macromolecular structures and sequences. Methods in enzymology, 374:492-509, 2003. Google Scholar
  31. MF Sanner, AJ Olson, and J-C Spehner. Reduced surface: an efficient way to compute molecular surfaces. Biopolymers, 38(3):305-320, 1996. Google Scholar
  32. W Tian, C Chen, and J Liang. CASTp 3.0: Computed Atlas of Surface Topography of Proteins and Beyond. Biophysical Journal, 114(3):50a, 2018. Google Scholar
  33. J Venkateswaran, B Song, T Kahveci, and C Jermaine. TRIAL: A Tool for Finding Distant Structural Similarities. IEEE/ACM Trans Comput Biol Bioinform, 8(3):819-831, 2011. Google Scholar
  34. Y Zhou, X-P Li, BY Chen, and NE Tumer. Ricin uses arginine 235 as an anchor residue to bind to P-proteins of the ribosomal stalk. Scientific reports, 7:42912, 2017. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact