A practical algorithm to find the best subsequence patterns

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

16 Citations (Scopus)


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. We generalize the problem to an optimization problem, and give a practical algorithm to solve it exactly. Our algorithm uses pruning heuristic and subsequence automata, and can find the best subsequence. We show some experiments, that convinced us the approach is quite promising.

Original languageEnglish
Title of host publicationDiscovery Science - 3rd International Conference, DS 2000, Proceedings
EditorsSetsuo Arikawa, Shinichi Morishita
PublisherSpringer Verlag
Number of pages13
ISBN (Print)9783540413523
Publication statusPublished - 2000
Event3rd International Conference on Discovery Science, DS 2000 - Kyoto, Japan
Duration: Dec 4 2000Dec 6 2000

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


Other3rd International Conference on Discovery Science, DS 2000

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'A practical algorithm to find the best subsequence patterns'. Together they form a unique fingerprint.

Cite this