The week's pick
Random Articles
Reseach Article
Walk-based Graph Kernel for Drug Discovery: A Review
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 94 - Number 16 |
| Year of Publication: 2014 |
| Authors: Preeja M. P., K P Soman |
10.5120/16440-5878
|
Preeja M. P., K P Soman . Walk-based Graph Kernel for Drug Discovery: A Review. International Journal of Computer Applications. 94, 16 ( May 2014), 1-7. DOI=10.5120/16440-5878
Abstract
The key motivation for the study of virtual screening is to reduce the time and cost requirement of the drug discovery process. Virtual screening is a computational method for finding an efficient drug molecule from pool of potential candidates. There are two different methods for virtual screening 1) structure based 2) ligand based. In the structure based method, 2D or 3D structure of a target molecule is used to screen the ligands which do not bind to the target molecule. Ligand based virtual screening is based on the fact that ligands similar to an active drug molecule might be active. The amount of information required is different in both the case. Structure based virtual screening is computationally intensive and complex while a few active ligand information is enough to start ligand based virtual screening. Based on the type of information, ligand based virtual screening can be performed in different ways. The machine learning approach using molecular graphs has been found to be very effective. Graph kernel is the similarity measure used to screen molecular graphs based on the structure. It is based on the fact that structurally similar molecules will have same property. In this review we have summarized the recent development in graph kernel for chemical molecule and elaborated upon the need of more accurate and efficient graph kernel with less computational complexity. The accuracy of different methods have been compared using standard dataset. The review shows the current state of art in the ongoing research in the design of efficient walk kernels.
References
- TingjunHou and XiaojieXu , Recent Development and Application of Virtual Screening in Drug Discovery: An Overview , Current Pharmaceutical Design, pp. 1011-1033, vol. 10, 2004
- VivekVyas ,Anurekha Jain, Avijeet Jain, Arun Gupta, Virtual Screening: A Fast Tool for Drug Design ,Sci Pharm. , pp. 333-360, vol. 76,pp. 0803-03, 2008.
- S. Kramer, E. Frank, and C. Helma, Fragment generation and support vector machines for inducing SARs , SAR QSAR Environ Res. , vol. 13, no. 05, pp. 509-523, July 2002.
- Helma, T. Cramer, S. Kramer, and L. De Raedt, Data mining and machine learning techniques for the identification of mutagenicity inducing substructures and structure activity relationships of noncongeneric compounds , J ChemInfComput Sci. , vol. 44, no. 04, pp. 1402-1411, 2004.
- Feng Luan, Ruisheng Zhang, Chunyan Zhao, Xiaojun Yao, Mancang Liu, Zhide Hu, and Botao Fan, Classification of the carcinogenicity of N-nitroso compounds based on support vector machines and linear discriminant analysis , Chem Res Toxicol. , vol. 18, no. 02, pp. 198-203, Feb 2005.
- S. Joshua Swamidass,J, Jonathan Chen, JocelyneBruand,Peter Phung, Liva Ralaivola and Pierre Baldi, Kernels for small molecules and the prediction of mutagenicity, toxicity and anti-cancer activity , Bioinformatics 2005, ISMB 2005 Proceedings, Vol 21, no 01, i359-i368. March 27, 2005.
- Pierre Mahé, Liva Ralaivola, Véronique Stoven and Jean-Philippe Vert, The Pharmacophore Kernel for Virtual Screening with Support Vector Machines , J. Chem. Inf. Model. , vol. 46 no. 05, pp 2003–2014, Aug 2006.
- L. Ralaivola, S. J. Swamidass,J. H. Saigo, and P. Baldi, Graph kernels for chemical informatics ,In Advances in Neural Information Processing Systems, vol. 19, no. 01 ,pp. 1093-1110 ,Sep 2005.
- C. -A. Azencott, A. Ksikes, S. J. Swamidass,J. H. Chen, L. Ralaivola, and P. Baldi, One- to four dimensional kernels for virtual screening and the prediction of physical, chemical, and biological properties , J ChemInf Model, vol. 47 no. 03 pp. 965-974, 2007.
- Gartner. T, Exponential and geometric kernels for graphs , NIPS-02 Workshop on Unreal Data: Principles of Modelling Nonvectorial Data, Whistler, British Columbia, December, 2002.
- J. Lafferty and G. Lebanon, Information diffusion kernels , In Neural Information Processing Systems, volume 15. MIT Press, 2002.
- H. Kashima and A. Inokuchi, Kernels for Graph Classification ,Proc. 1st ICDM Workshop on Active Mining (AM-2002), Maebashi, Japan, 2002.
- Koji Tsuda, Taishin Kin and Kiyoshi Asai, Marginalized kernels for biological sequences , Bioinformatics, Vol 1 pp. 1-8, 2002.
- T. Jaakkola and D. Haussler, Exploiting generative models in discriminative classifiers , In Advances in Neural Information Processing Systems,Vol 11, 1998.
- H. Kashima, K. Tsuda and A. Inokuchi, Marginalized Kernels between Labeled Graphs , Proceedings of the Twentieth International Conference on Machine Learning, pp. 321-328, AAAI Press, 2003.
- T. Gartner, P. Flach, and S. Wrobel, On graph kernels: hardness results and efficient alternatives ,Proceedings of the Sixteenth Annual Conference on Computational Learning Theory and the Seventh Annual Workshop on Kernel Machines, vol. 2777 of Lecture Notes in Computer Science, pp. 129-143, July 2003.
- H. Kashima, K. Tsuda, and A. Inokuchi, Kernels for graphs ,Kernel Methods in Computational Biology, pp. 155-170. MIT Press, 2004.
- P. Mahe, N. Ueda, T. Akutsu, J. L. Perret, and J. P. Vert, Graph kernels for molecular structure-activity relationship analysis with support vector machines , J ChemInf Model, vol. 44, no. 04, pp. 939-951, 2005.
- J. Ramon and T. Gartner, Expressivity versus effciency of graph kernels , Proceedings of the First International Workshop on Mining Graphs, Trees and Sequences, pp. 65-74, 2003.
- K. M. Borgwardt and H. P. Kriegel, Shortest-path kernels on graphs , Proc. 5th IEEE Int. Conf. on Data Mining, Houston, Texas, USA, pp. 74-81, 2005.
- P. Mahe and J. P. Vert, Graph kernels based on tree patterns for molecules , Technical Report ccsd-00095488, HAL, September 2006.
- S. V. N. Vishwanathan, Karsten M. Borgwardt, and Nicol N. Schraudolph, Fast Computation of Graph Kernels ,In Advances in Neural Information Processing Systems, vol. 19 , MIT Press, Cambridge MA, 2006.
- Computer-Aided Molecular Design,Vol 12, pp. 471 – 490, 1998.
- M. Collins and N. Duffy, Convolution kernel for naturallanguage, In Proc. of the 14th NIPS, Vancouver, British Columbia, Canada, 2001.
- S. V. N. Vishwanathan and Alexander J. Smola, Fast Kernels for String and Tree Matching , Kernel Methods in Computational Biology, MIT Press, Cambridge, MA, 2004.
- Shervashidze N. and and K. M. Borgwardt, Fast subtree kernels on graph , Proceedings of the 2009 Conference NIPS, BC, Canada,pp. 1660-1668, 2009.
- T. Gartner, J. W. Lloyd, and P. A. Flach, Kernels and distances forstructured data , Journal Machine Learning, Vol 57, no 03, pp. 205-232 September 2006.
- C. Z. Cai, W. L. Wang, L. Z. Sun, and Y. Z. Chen, Protein function classification viasupport vector machine approach ,Math. Biosci. , vol. 185, no. 02, pp. 111-122, 2003.
- H. Frohlich, J. K. Wegner, F. Sieker, and A. Zell, Optimal assignment kernelsfor attributed molecular graphs ,In Proceedings of the 22nd international conference on Machine learning, New York, NY, USA ,pp. 225-232, 2005.
- T. Horvath, T. Gartner, and S. Wrobel, Cyclic pattern kernels for predictive graph mining ,In Proceedingsof the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, New York, NY, USA, pp. 158-167, 2004.
- D. Haussler, Convolution Kernels on Discrete Structures, Technical Report UCSC-CRL-99-10,UC Santa Cruz, 1999.
- Matthias Rarely and J. Scott Dixon, Feature trees: A new molecular similarity measure basedon tree-matching, J.
Index Terms
Keywords