Finding patterns in three-dimensional graphs: Algorithms and applications to scientific data mining

Xiong Wang, Jason T.L. Wang, Dennis Shasha, Bruce A. Shapiro, Isidore Rigoutsos, Kaizhong Zhang

Research output: Contribution to journalArticle

Abstract

This paper presents a method for finding patterns in 3D graphs. Each node in a graph is an undecomposable or atomic unit and has a label. Edges are links between the atomic units. Patterns are rigid substructures that may occur in a graph after allowing for an arbitrary number of whole-structure rotations and translations as well as a small number (specified by the user) of edit operations in the patterns or in the graph. (When a pattern appears in a graph only after the graph has been modified, we call that appearance "approximate occurrence"). The edit operations include relabeling a node, deleting a node and inserting a node. The proposed method is based on the geometric hashing technique, which hashes node-triplets of the graphs into a 3D table and compresses the labeltriplets in the table. To demonstrate the utility of our algorithms, we discuss two applications of them in scientific data mining. First, we apply the method to locating frequently occurring motifs in two families of proteins pertaining to RNA-directed DNA Polymerase and Thymidylate Synthase and use the motifs to classify the proteins. Then, we apply the method to clustering chemical compounds pertaining to aromatic, bicyclicalkanes, and photosynthesis. Experimental results indicate the good performance of our algorithms and high recall and precision rates for both classification and clustering.

Original languageEnglish (US)
Pages (from-to)731-749
Number of pages19
JournalIEEE Transactions on Knowledge and Data Engineering
Volume14
Issue number4
DOIs
StatePublished - Jul 1 2002

Keywords

  • Biochemistry
  • Classification and clustering
  • Data mining
  • Geometric hashing
  • KDD
  • Medicine
  • Structural pattern discovery

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'Finding patterns in three-dimensional graphs: Algorithms and applications to scientific data mining'. Together they form a unique fingerprint.

  • Cite this