Finding best patterns practically

Ayumi Shinohara, Masayuki Takeda, Setsuo Arikawa, Masahiro Hirao, Hiromasa Hoshino, Shunsuke Inenaga

Research output: Chapter in Book/Report/Conference proceedingChapter

11 Citations (Scopus)


Finding a pattern which separates two sets is a critical task in discovery. Given two sets of strings, consider the problem to find a subsequence that is common to one set but never appears in the other set. The problem is known to be NP-complete. Episode pattern is a generalized concept of subsequence pattern where the length of substring containing the subsequence is bounded. We generalize these problems to optimization problems, and give practical algorithms to solve them exactly. Our algorithms utilize some pruning heuristics based on the combinatorial properties of strings, and efficient data structures which recognize subsequence and episode patterns.

Original languageEnglish
Title of host publicationProgress in Discovery Science
PublisherSpringer Verlag
Number of pages11
ISBN (Print)3540433384, 9783540433385
Publication statusPublished - 2002

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Finding best patterns practically'. Together they form a unique fingerprint.

Cite this