Advanced pruning strategies to speed up mining closed molecular fragments

In years, several algorithms for mining frequent subgraphs in graph databases have been proposed, with a major application area being the discovery of frequent substructures of biomolecules. Unfortunately, most of these algorithms still struggle with fairly long execution times if larger substructur...

Full description

Saved in:
Bibliographic Details
Main Authors: Borgelt, C., Meinl, T., Berthold, M.R.
Format: Conference Proceeding
Language:English
Subjects:
Applied sciences
Biochemistry
Computer science
Computer science
control theory
systems
Control theory. Systems
Data mining
Drugs
Ear
Exact sciences and technology
Human immunodeficiency virus
Hydrogen
Information science
Protection
Tree graphs
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In years, several algorithms for mining frequent subgraphs in graph databases have been proposed, with a major application area being the discovery of frequent substructures of biomolecules. Unfortunately, most of these algorithms still struggle with fairly long execution times if larger substructures or molecular fragments are desired. We describe two advanced pruning strategies - equivalent sibling pruning and perfect extension pruning - that can be used to speed up the MoFa algorithm (introduced in C. Borgelt and M.R. Berthold, (2002)) in the search for closed molecular fragments, as we demonstrate with experiments on the NCI's HIV database.
ISSN:1062-922X
2577-1655
DOI:10.1109/ICSMC.2004.1401251