Combinatorial Pattern Discovery for Scientific Data: Some Preliminary Results

Jason Tsong Li Wang, Gung Wei Chirn, Thomas G. Marr, Bruce Shapiro, Dennis Shasha, Kaizhong Zhang

Research output: Contribution to journalArticlepeer-review


Suppose you are given a set of natural entities 1994 that possess some important common externally observable properties. You also have a structural description of the entities (e.g., sequence, topological, or geometrical data) and a distance metric. Combinatorial pattern discovery is the activity of finding patterns in the structural data that might explain these common properties based on the metric. This paper presents an example of combinatorial pattern discovery: the discovery of patterns in protein databases. The structural representation we consider are strings and the distance metric is string edit distance permitting variable length don't cares. Our techniques incorporate string matching algorithms and novel heuristics for discovery and optimization, most of which generalize to other combinatorial structures. Experimental results of applying the techniques to both generated data and functionally related protein families obtained from the Cold Spring Harbor Laboratory show the effectiveness of the proposed techniques. When we apply the discovered patterns to perform protein classification, they give information that is complementary to the best protein classifier available today.

Original languageEnglish (US)
Pages (from-to)115-125
Number of pages11
JournalACM SIGMOD Record
Issue number2
StatePublished - May 24 1994

ASJC Scopus subject areas

  • Software
  • Information Systems


Dive into the research topics of 'Combinatorial Pattern Discovery for Scientific Data: Some Preliminary Results'. Together they form a unique fingerprint.

Cite this