Molecular feature mining in HIV data

ABSTRACT

We present the application of Feature Mining techniques to the Developmental Therapeutics Program's AIDS antiviral screen database. The database consists of 43576 compounds, which were measured for their capability to protect human cells from HIV-1 infection. According to these measurements, the compounds were classified as either active, moderately active or inactive. The distribution of classes is extremely skewed: Only 1.3 % of the molecules is known to be active, and 2.7 % is known to be moderately active.Given this database, we were interested in molecular substructures (i.e., features) that are frequent in the active molecules, and infrequent in the inactives. In data mining terms, we focused on features with a minimum support in active compounds and a maximum support in inactive compounds. We analyzed the database using the levelwise version space algorithm that forms the basis of the inductive query and database system MOLFEA (Molecular Feature Miner). Within this framework, it is possible to declaratively specify the features of interest, such as the frequency of features on (possibly different) datasets as well as on the generality and syntax of them. Assuming that the detected substructures are causally related to biochemical mechanisms, it should be possible to facilitate the development of new pharmaceuticals with improved activities.

REFERENCES

• 1: Rakesh Agrawal , Tomasz Imieliński , Arun Swami, Mining association rules between sets of items in large databases, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.207-216, May 25-28, 1993, Washington, D.C., United States
• 2: Roberto J. Bayardo, Jr., Efficiently mining long patterns from databases, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.85-93, June 01-04, 1998, Seattle, Washington, United States
• 3: L. Dehaspe, H. Toivonen, R.D. King. Finding frequent substructures in chemical compounds, in: Proceedings of the Fourth International Conference on Knowledge Discovery and Data Mining (KDD-98), 30-36, AAAI press, 1998.
• 4: Luc Dehaspe , Hannu Toivonen, Discovery of frequent DATALOG patterns, Data Mining and Knowledge Discovery, v.3 n.1, p.7-36, March 1999 [doi>10.1023/A:1009863704807]
• 5: Luc De Raedt, A Logical Database Mining Query Language, Proceedings of the 10th International Conference on Inductive Logic Programming, p.78-92, July 24-27, 2000
• 6: L. De Raedt, S. Kramer. The levelwise version space algorithm and its application to molecular fragment finding, in: Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence (IJCAI-01), 2001.
• 7: Dimitrios Gunopulos , Heikki Mannila , Sanjeev Saluja, Discovering All Most Specific Sentences by Randomized Algorithms, Proceedings of the 6th International Conference on Database Theory, p.215-229, January 08-10, 1997
• 8: Jiawei Han , Laks V. S. Lakshmanan , Raymond T. Ng, Constraint-Based, Multidimensional Data Mining, Computer, v.32 n.8, p.46-50, August 1999 [doi>10.1109/2.781634]
• 9: Haym Hirsh, Generalizing Version Spaces, Machine Learning, v.17 n.1, p.5-46, Oct. 1994 [doi>10.1023/A:1022600917598]
• 10: Tomasz Imielinski , Heikki Mannila, A database perspective on knowledge discovery, Communications of the ACM, v.39 n.11, p.58-64, Nov. 1996 [doi>10.1145/240455.240472]
• 11: C.A. James, D. Weininger, J. Delany. Daylight theory manual - Daylight J. 71, Daylight Chemical Information Systems, 2000. http ://www. daylight, corn/
• 12: David D. Jensen , Paul R. Cohen, Multiple Comparisons in Induction Algorithms, Machine Learning, v.38 n.3, p.309-338, March 2000 [doi>10.1023/A:1007631014630]
• 13: 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
• 14: Heikki Mannila , Hannu Toivonen, Levelwise Search and Borders of Theories in KnowledgeDiscovery, Data Mining and Knowledge Discovery, v.1 n.3, p.241-258, 1997 [doi>10.1023/A:1009796218281]
• 15: Rosa Meo , Giuseppe Psaila , Stefano Ceri, An Extension to SQL for Mining Association Rules, Data Mining and Knowledge Discovery, v.2 n.2, p.195-224, June 1998 [doi>10.1023/A:1009774406717]
• 16: Chris Mellish, The description identification problem, Artificial Intelligence, v.52 n.2, p.151-167, Dec. 1991 [doi>10.1016/0004-3702(91)90040-Q]
• 17: T.M. Mitchell. Generalization as search, Artificial Intelligence, 18(2), 1982.
• 18: Akihiro Inokuchi , Takashi Washio , Hiroshi Motoda, An Apriori-Based Algorithm for Mining Frequent Substructures from Graph Data, Proceedings of the 4th European Conference on Principles of Data Mining and Knowledge Discovery, p.13-23, September 13-16, 2000
• 19: Ashwin Srinivasan , Ross D. King, Feature construction with Inductive Logic Programming: A Study of Quantitative Predictions of Biological Activity Aided by Structural Attributes, Data Mining and Knowledge Discovery, v.3 n.1, p.37-57, March 1999 [doi>10.1023/A:1009815821645]
• 20: Ashwin Srinivasan , Ross D. King , Douglas W. Bristol, An assessment of submissions made to the Predictive Toxicology Evaluation Challenge, Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, p.270-275, July 31-August 06, 1999
• 21: D. Weininger. SMILES 1. Introduction and encoding rules. Journal of Chemical Information and Computer Sciences, 28, 31, 1988.
• 22: D. Weininger, A. Weininger, J.L Weininger. SMILES II, algorithm for generation of unique SMILES notation. Journal of Chemical Information and Computer Sciences, 29, 97, 1989.
• 23: Weislow, O.S., R. Kiser, D.L. Fine, J.P. Bader, R.H. Shoemaker, M.K. Boyd. New soluble formazan assay for HIV-1 cytopathic effects: application to high flux screening of synthetic and natural products for AIDS antiviral activity. Journal of the National Cancer Institute, 81:577-586, 1989.

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Statistical databases

  J. Computer Applications
  J.3 LIFE AND MEDICAL SCIENCES
      Subjects: Medical information systems

General Terms:
Algorithms, Performance, Theory