Structure-based querying of proteins using wavelets

ABSTRACT

The ability to retrieve molecules based on structural similarity has use in many applications, from disease diagnosis and treatment to drug discovery and design. In this paper, we present a method to represent protein molecules that allows for the fast, flexible and efficient retrieval of similar structures, based on either global or local attributes. We begin by computing the pair-wise distance between amino acids, transforming each 3D structure into a 2D distance matrix. We normalize this matrix to a specific size and apply a 2D wavelet decomposition to generate a set of approximation coefficients, which serves as our global feature vector. This transformation reduces the overall dimensionality of the data while still preserving spatial features and correlations. We test our method by running queries on three different protein data sets that have been used previously in the literature, basing our comparisons on labels taken from the SCOP database. We find that our method significantly outperforms existing approaches, in terms of retrieval accuracy, memory utilization and execution time. Specifically, using a k-d tree and running a 10-nearest-neighbor search on a dataset of 33,000 proteins against itself, we see an average accuracy of 89% at the SCOP SuperFamily level and a total query time that is up to 350 times faster than previously published techniques. In addition to processing queries based on global similarity, we also propose innovative extensions to effectively match proteins based solely on shared local substructures, allowing for a more flexible query interface.

REFERENCES

• 1: David W. Aha , Dennis Kibler , Marc K. Albert, Instance-Based Learning Algorithms, Machine Learning, v.6 n.1, p.37-66, Jan. 1991 [doi>10.1023/A:1022689900470]
• 2: S. F. Altschul, W. Gish, W. Miller, E. W. Myers, and D. J. Lipman. Basic local alignment search tool. J. of Mo. Biol., 215:403--410, 1990.
• 3: S. F. Altschul, T. L. Madden, A. A. Schaffer, J. Zhang, Z. Anang, W. Miller, and D. J. Lipman. Gapped BLAST and PSI-BLAST: A new generation of protein database search programs. Nucleic Acids Research, 25:3389--3402, 1997.
• 4: Zeyar Aung , Kian-Lee Tan, Rapid 3D protein structure database searching using information retrieval techniques, Bioinformatics, v.20 n.7, p.1045-1052, May 2004 [doi>10.1093/bioinformatics/bth036]
• 5: Jon Louis Bentley, Multidimensional binary search trees used for associative searching, Communications of the ACM, v.18 n.9, p.509-517, Sept. 1975 [doi>10.1145/361002.361007]
• 6: A. Bhattacharya, T. Can, T. Kahveci, A. Singh, and Y. Wang. ProGreSS: Simultaneous searching of protein databases by sequence and structure. In Pacific Symposium on Biocomputing, volume 9, pages 264--275. World Scientific Press, 2004.
• 7: Orhan Çamoglu , Tamer Kahveci , Ambuj K. Singh, Towards Index-based Similarity Search for Protein Structure Databases, Proceedings of the IEEE Computer Society Conference on Bioinformatics, p.148, August 11-14, 2003
• 8: Feng Gao , Mohammed J. Zaki, PSIST: Indexing Protein Structures Using Suffix Trees, Proceedings of the 2005 IEEE Computational Systems Bioinformatics Conference (CSB'05), p.212-222, August 08-11, 2005 [doi>10.1109/CSB.2005.46]
• 9: S. M. Larson, C. D. Snow, M. Shirts, and V. S. Pande. Foldingυhome and genomeυhome: Using distributed computing to tackle previously intractable problems in computational biology. In R. Grant, editor, Computational Genomics. Horizon Press, 2002.
• 10: S. Mallat. A Wavelet Tour of Signal Processing. Academic, New York, 2nd edition, 1999.
• 11: Keith Marsolo , Srinivasan Parthasarathy, Alternate Representation of Distance Matrices for Characterization of Protein Structure, Proceedings of the Fifth IEEE International Conference on Data Mining, p.298-305, November 27-30, 2005 [doi>10.1109/ICDM.2005.19]
• 12: S. Mehta, S. Barr, A. Choy, H. Yang, S. Parthasarathy, R. Machiraju, and J. Wilkins. Dynamic classification of anomalous structures in molecular dynamics simulation data. In Proceedings of the SIAM Conference on Data Mining, 2005.
• 13: A. G. Murzin, S. E. Brenner, T. Hubbard, and C. Chothia. Scop: a structural classification of proteins database for the investigation of sequences and structures. J. Mol. Biol, 247:536--540, 1995.
• 14: Loren K. Platzman , John J. Bartholdi, III, Spacefilling curves and the planar travelling salesman problem, Journal of the ACM (JACM), v.36 n.4, p.719-737, Oct. 1989 [doi>10.1145/76359.76361]
• 15: Sandeep Tata , Jignesh M. Patel, PiQA: an algebra for querying protein data sets, Proceedings of the 15th international conference on Scientific and statistical database management, p.141-150, July 09-11, 2003, Cambridge, MA [doi>10.1109/SSDM.2003.1214975]

INDEX TERMS

Primary Classification:
  E. Data
  E.2 DATA STORAGE REPRESENTATIONS
      Subjects: Object representation

Additional Classification:
  J. Computer Applications
  J.3 LIFE AND MEDICAL SCIENCES
      Subjects: Biology and genetics

General Terms:
Algorithms

Keywords:
indexing, protein structure similarity, wavelets