Mining Maximal Flexible Patterns in a Sequence

We consider the problem of enumerating all maximal flexible patterns in an input sequence database for the class of flexible patterns, where a

maximal

pattern

(also called a closed pattern) is the most specific pattern among the equivalence class of patterns having the same list of occurrences in the input. Since our notion of maximal patterns is based on position occurrences, it is weaker than the traditional notion of maximal patterns based on document occurrences. Based on the framework of reverse search, we present an efficient depth-first search algorithm

MaxFlex

for enumerating all maximal flexible patterns in a given sequence database without duplicates in

$O(||{\mathcal{T}}||\times|\Sigma|)$

time per pattern and

$O(||{\mathcal T}||)$

space, where

$||{\mathcal T}||$

is the size of the input sequence database

$\mathcal T$

and |

Σ

| is the size of the alphabet on which the sequences are defined. This means that the enumeration problem for maximal flexible patterns is shown to be solvable in polynomial delay and polynomial space.