Mining molecular fragments: finding relevant substructures of molecules

By Christian Borgelt, Michael R. Berthold. IEEE International Conference on Data Mining. Proceedings, 2002

511 citations recorded by the source corpus.

We present an algorithm to find fragments in a set of molecules that help to discriminate between different classes of for instance, activity in a drug discovery context. Instead of carrying out a brute-force search, our method generates fragments by embedding them in all appropriate molecules in parallel and prunes the search tree based on a local order of the atoms and bonds, which results in substantially faster search by eliminating the need for frequent, computationally expensive reembeddings and by suppressing redundant search. We prove the usefulness of our algorithm by demonstrating the discovery of activity-related groups of chemical compounds in the well-known National Cancer Institute's HIV-screening dataset.

Subfields: Computational Theory and Mathematics, Information Systems, Molecular Biology

View Paper: https://www.semanticscholar.org/paper/dfb5cfd0498838b7a83684c3e32d39b591feffa0

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Information Systems

In Molecular Biology

Citations in the corpus

Cyclic pattern kernels for predictive graph mining (2004, background): “It has been used frequently in the empirical evaluation of graph mining approaches (see, e.g., [4, 8, 9, 20]).”
Frequent substructure-based approaches for classifying chemical compounds (2003, methodology): “[40], the FSG algorithm developed by members of our group [47], [50], the chemical substructure discovery algorithm developed by Borgelt and Berthold [19], the gSpan algorithm developed by Yan and Han [82], the FFSM by Huan et al.”
Finding Frequent Patterns in a Large Sparse Graph* (2004, methodology): “In recent years, a number of efficient and scalable algorithms have been developed to find patterns in the graph-transaction setting (Borgelt and Berthold, 2002; Yan and Han, 2002; Inokuchi et al., 2003; Hong et al., 2003; Yan and Han, 2003; Huan et al., 2003; Kuramochi and Karypis, 2004a).”
Bridging semantics and syntax with graph algorithms - state-of-the-art of extracting biomedical relations (2017, background): “Shared resources for biomedical relation extraction Utility category Data sources Terminology/Ontology/Knowledge Base GO [161], UMLS [58], MeSH [162], Wordnet [118], Verbnet [163], Biothesaurus [122], PDB [101], Uniprot [121], SIDER [164], DrugBank [165], HIVDB [166], RegaDB [167], Entrez Gene [153]”
A survey of frequent subgraph mining algorithms (2012, methodology): “However, W¨orlein et al. (2005) presented a detailed comparison of four DFS-based miners: MoFa, gSpan, FFSM, and GASTON, with respect to their performance on various chemical data sets.”
Frequent pattern mining: current status and future directions (2007, methodology): “Pattern-growth-based graph pattern mining algorithms include gSpan by Yan and Han (2002), MoFa by Borgelt and Berthold (2002), FFSM by Huan et al. (2003), SPIN by Huan et al. (2004), and Gaston by Nijssen and Kok (2004).”
Large scale mining and retrieval of visual data in a multimodal context (2008, methodology): “, 2003], FSG (Frequent SubGraph Discovery) [Kuramochi and Karypis, 2001], gSpan (graph-based Substructure pattern mining) [Yan and Han, 2002], CloseGraph [Yan and Han, 2003], and MoSS/MoFa [Borgelt and Berthold, 2002].”
An efficient algorithm for discovering frequent subgraphs (2004, background): “Index Terms—Data mining, scientific data sets, frequent pattern discovery, chemical compound data sets.”
Graph indexing: a frequent structure-based approach (2004, background): “Yan and Han [21] and Borgelt and Berthold [2] apply the pattern-growth approach to directly generate frequent subgraphs.”