Optimal assignment kernels for attributed molecular graphs

ABSTRACT

We propose a new kernel function for attributed molecular graphs, which is based on the idea of computing an optimal assignment from the atoms of one molecule to those of another one, including information on neighborhood, membership to a certain structural element and other characteristics for each atom. As a byproduct this leads to a new class of kernel functions. We demonstrate how the necessary computations can be carried out efficiently. Compared to marginalized graph kernels our method in some cases leads to a significant reduction of the prediction error. Further improvement can be gained, if expert knowledge is combined with our method. We also investigate a reduced graph representation of molecules by collapsing certain structural elements, like e.g. rings, into a single node of the molecular graph.

REFERENCES

• 1: Francis R. Bach , Michael I. Jordan, Kernel independent component analysis, The Journal of Machine Learning Research, 3, p.1-48, 3/1/2003 [doi>10.1162/153244303768966085]
• 2: Böhm, M., & Klebe, G. (2002). Development of New Hydrogen Bond Descriptors and Their Application to Comparative Molecular Field Analyses. J. Med. Chem., 45, 1585--1597.
• 3: Bonchev, D., & Rouvray, D. H. (Eds.). (1990). Chemical Graph Theory: Introduction and Fundamentals, vol. 1 of Mathematical Chemistry Series. London, UK: Gordon and Breach Science Publishers.
• 4: Chen, X., Rusinko, A., Tropsha, A., & Young, S. S. (1999). Automated Pharmacophore Identification for Large Chemical Data Sets. J. Chem. Inf. Comput. Sci., 39, 887--896.
• 5: Feher, M., Sourial, E., & Schmidt, J. (2000). A simple model for the prediction of blood-brain partitioning. Int. J. Pharmaceut., 201, 239--247.
• 6: Figueras, J. (1996). Ring Perception Using Breadth-First Search. J. Chem. Inf. Comput. Sci., 36, 986--991.
• 7: Gasteiger, J., & Marsili, M. (1978). A New Model for Calculating Atomic Charges in Molecules. Tetrahedron Lett., 34, 3181--3184.
• 8: Gärtner, T., Flach, P., & Wrobel, S. (2003). On graph kernels: Hardness results and efficient alternatives. Proc. 16th Ann. Conf. Comp. Learning Theory and 7th Ann. Workshop on Kernel Machines.
• 9: Helma, C., King, R., & Kramer, S. (2001). The predictive toxicology challenge 2000--2001. Bioinformatics, 17, 107--108.
• 10: Kashima, H., Tsuda, K., & Inokuchi, A. (2003). Marginalized kernels between labeled graphs. Proc. 20th Int. Conf. on Machine Learning.
• 11: Kubinyi, H. (2003). Drug research: myths, hype and reality. Nature Reviews: Drug Discovery, 2, 665--668.
• 12: Gert R. G. Lanckriet , Nello Cristianini , Peter Bartlett , Laurent El Ghaoui , Michael I. Jordan, Learning the Kernel Matrix with Semidefinite Programming, The Journal of Machine Learning Research, 5, p.27-72, 12/1/2004
• 13: Martin, Y. C. (1998). Pharmacophore mapping. Des. Bioact. Mol., 121--148.
• 14: Kurt Mehlhorn , Stefan Näher, LEDA: a platform for combinatorial and geometric computing, Cambridge University Press, New York, NY, 1999
• 15: Oprea, T. I., Zamora, I., & Ungell, A.-L. (2002). Pharmacokinetically based mapping device for chemical space navigation. J. Comb. Chem., 4. 258--266.
• 16: Stefan Kramer , Luc De Raedt, Feature Construction with Version Spaces for Biochemical Applications, Proceedings of the Eighteenth International Conference on Machine Learning, p.258-265, June 28-July 01, 2001
• 17: Schölkopf, B., & Smola, A. J. (2002). Learning with kernels. Cambridge, MA: MIT Press.
• 18: Todeschini, R., & Consonni, V. (Eds.). (2000). Handbook of Molecular Descriptors Weinheim: Wiley-VCH.
• 19: van de Waterbeemd, H., &- Gifford, E. (2003). ADMET In Silico Modelling: Towards Prediction Paradise? Nature Reviews: Drug Discovery, 2, 192--204.
• 20: Takashi Washio , Hiroshi Motoda, State of the art of graph-based data mining, ACM SIGKDD Explorations Newsletter, v.5 n.1, July 2003 [doi>10.1145/959242.959249]
• 21: Wegner, J., Fröhlich, H., & Zell, A. (2003). Feature selection for Descriptor based Classification Models: Part II - Human Intestinal Absorption (HIA). J. Chem. Inf. Comput. Sci., 44, 931--939.
• 22: Yoshida, F., & Topliss, J. (2000). QSAR model for drug human oral bioavailability. J. Med. Chem., 43, 2575--2585.