TY - GEN

T1 - A practical algorithm to find the best subsequence patterns

AU - Hirao, Masahiro

AU - Hoshino, Hiromasa

AU - Shinohara, Ayumi

AU - Takeda, Masayuki

AU - Arikawa, Setsuo

N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2000.

PY - 2000

Y1 - 2000

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84974712011&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84974712011&partnerID=8YFLogxK

U2 - 10.1007/3-540-44418-1_12

DO - 10.1007/3-540-44418-1_12

M3 - Conference contribution

AN - SCOPUS:84974712011

SN - 9783540413523

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 141

EP - 153

BT - Discovery Science - 3rd International Conference, DS 2000, Proceedings

A2 - Arikawa, Setsuo

A2 - Morishita, Shinichi

PB - Springer Verlag

T2 - 3rd International Conference on Discovery Science, DS 2000

Y2 - 4 December 2000 through 6 December 2000

ER -