An Efficient Polynomial Space and Polynomial
Delay Algorithm for Enumeration of Maximal
Motifs in a Sequence
Hiroki Arimura1? and Takeaki Uno2
1

Hokkaido University, Kita 14-jo, Nishi 9-chome, Sapporo 060-0814, JAPANarim@ist.hokudai.ac.jp
2
National Institute of Informatics, Tokyo 101–8430, JAPAN
uno@nii.jp

Abstract. In this paper, we consider the problem of enumerating all
maximal motifs in an input string for the class of repeated motifs withwild cards. A maximal motif is such a representative motif that is notproperly contained in any larger motifs with the same location lists. Although the enumeration problem for maximal motifs with wild cards has
been studied in (Parida et al., CPM’01), (Pisanti et al.,MFCS’03) and(Pelfrene et al., CPM’03), its output-polynomial time computability has
been still open. The main result of this paper is a polynomial space polynomial delay algorithm for the maximal motif enumeration problem forthe repeated motifs with wild cards. This algorithm enumerates all maximal motifs in an input string of length n in O(n3 ) time per motif with
O(n) space, in particular O(n3 ) delay. The key of the algorithm is depthfirst search on a tree-shaped search route over all maximal motifs basedon a technique called prefix-preserving closure extension. We also show
an exponential lower bound and a succinctness result on the number ofmaximal motifs, which indicate the limit of a straightforward approach.
The results of the computational experiments show that our algorithm
can be applicable to huge string data such as genome data in practice,and does not take large additional computational cost compared to usual
frequent motif mining algorithms.

1

Introduction

Pattern discovery is to find all patterns within a class of combinatorial patterns
that appear in an input data satisfying a specified constraint, and is a central
task in computational biology, temporal sequence analysis, sequence and text
mining [3]. We consider the pattern discovery problem for the class of patterns
with wild cards, which are strings consisting of constant symbols (called solid
letters) drawn from an alphabet and variables ’◦’ (called wildcards) that matches
any symbol [9, 13]. For instance, B ◦ AB and B ◦ AB ◦ ◦B are examples of patterns.
?

This work is done during the first author’s visit in LIRIS, University Claude-Bernard
Lyon 1, France.

00
10
20
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1

ABBCABRABRABCABABRABBC
[]*
[B]*
[AB]*
[BC]*
[ABRAB]*[BoAB]*[ABoAB]*[BoABoAB]*[BoooooB]*[BoABoooooB]*

21
9
7
3
3
5
4
3
4
3

10 maximal motifs

[]*
21
[B]*
9
[AB]*
7
[A]
7
[BC]*
3
[C]
3
[ABRAB]* 3
[R]
3
[RA]
3
[RAB]
3

input string s[RoB] 3[BR]
3[ABR] 3
[ABRA] 3[ABRoB] 3[ABoA] 4[AoR] 3
[AoRA] 3[AoRAB] 3[AoRoB] 3

quorum θ = 3[AooA]
4[BRA]
3[BRAB]
3[BRoB]
3[BoAB]* 5[BooB]
5[ABoAB]* 4[ABooB] 4[AooAB] 4[AoooB] 4[BoA]
5[BoABoA] 3[BoAooA] 3[BooBoA] 3[BooooA] 3[BoABoAB]*3[BoABooB] 3[BoAooAB] 3[BoAoooB] 3[BooBoAB] 3[BooBooB]
3[BooooAB]
3[ABoooooB]
3[BoooooB]*
4[BoABoooooB]* 3[AooooooB]
3[BoAooooooB] 3[BooBoooooB] 3[BooooooooB] 3

49 motifs (frequent motifs)

Fig. 1. Examples of maximal motifs (left) and motifs (right) for an input string s anda quorum θ, where * indicates a maximal motif and the number associated to eachmotif indicates its frequency. These 10 maximal motifs are representatives containing
the whole information on the occurrences of all motifs in s.

A pattern p is said to appear at the jth position of a string s if any ith letter ofp matches to (j + i − 1)th letter of s, i.e., they are the same, or the ith letter is◦. Given a positive integer θ called quorum and for an input string s, a frequent
motif (or motif , for short) in s is a pattern that appears at least θ times in s.
Frequent motif discovery has a drawback that a huge number of motifs areoften generated from an input string without conveying any useful information.
To overcome this problem, we focus on discovery of maximal motifs [9, 12, 13].
The semantics of a pattern x is given by the location list L(x) consisting of
the positions in an input string s at which the pattern occurs. A motif is said
to be maximal if it is not properly contained by other motifs with the equivalent location lists allowing position shift. For example, we show in Figure 1
all maximal motifs and all motifs on input sting s = ABBCABRABRABCABABRABBC
for quorum θ = 3. Then, the pattern x1 = R ◦ B is a motif having location
list L(x1 ) = {6, 9, 17} in s but not a maximal one since there is another motif
x2 = ABRAB which contains x1 and whose location list L(x2 ) = {4, 7, 15} is obtained from the location list L(x1 ) by shifting leftward with two. In this example,
we can also observe that there are only 10 maximal motifs among 50 motifs. In
general, the number of maximal motifs can be exponentially smaller than thenumber of motifs, while the former can be exponential in the input size.
In this paper, we study the problem of enumerating all maximal motifs in
an input string of length n. In particular, from a practical viewpoint, we areinterested in those algorithms that have small space and delay complexities independent from the output size in addition to polynomial amortized time per
maximal motif. Although an output-polynomial time algorithm for this problem is known[?], its time complexity is square of the output size, and the spacecomplexity is not polynomial in the input size. The computability for maximal
motifs discovery with polynomial space and delay has been still open.
We first show an exponential lower bound and a succinctness result on
the number of maximal motifs, which show the limit of straightforward approaches. Next, by examining the previous approaches [9, 13, 12], we present
a simple output-polynomial time algorithm for maximal motif enumeration bybreadth-first search, which possibly requires exponential space and delay. Then,
we present an efficient algorithm that enumerates all maximal motifs in an input
string of length n with O(n3 ) time per motif with O(n) space and O(n3 ) delay.
A key of the algorithm is depth-first search on a tree-shaped search route for all
maximal motifs build by prefix-preserving closure extension, which enable us toenumerate all maximal motifs without storing discovered motifs which are used
for detecting duplications and maximality tests. To the best of our knowledge,
this is the first result on a polynomial space polynomial delay algorithm for
maximal pattern discovery for sequences.
The organization of this paper is as follows. In Section 2, we give definitions
and basic results. Section 3 gives lower bounds on the number of maximal motifs.
Section 2.2 prepares tools for studying maximal motifs and Section 4 reviews
the previous results. In Section 5, we present our algorithm MaxMotif thatenumerates all maximal motifs. Section 6 shows the result of computational
experiments. In Section 7, we conclude this paper.

2

Preliminaries

2.1

Maximal Motifs

We briefly introduce basic definitions and results on maximal pattern enumeration according to [13, 12]. For definitions not found here, see text books on stringalgorithms, e.g., [6, 8]. Given an alphabet ∆, a string of length n ≥ 0 is a consecutive sequence of letters s = a[0] · · · a[n − 1] ∈ ∆∗ , where a[i] ∈ ∆, 0 ≤ i ≤ n − 1.
For every 0 ≤ i ≤ j ≤ n−1, s[i..j] denotes the substring ai ai+1 · · · aj . ∆∗ denotes
the set of all possibly empty strings over ∆, and ε denotes the empty string. If
s = uvw for some u, v, w ∈ ∆∗ , then we say that u is a prefix and w is a suffix
of s. For a set S ⊆ ∆∗ of strings, we denote by |S| the cardinality of S and by
P||S|| = s∈S |s| the total length of S.
Let Σ be an alphabet of solid characters (or constant letters). Let ◦ 6∈ Σ bea distinguished letter not belonging to Σ, called the wild card (or don’t care).
A wild card ◦ matches any solid character c ∈ Σ and also matches ◦ itself. An
input string is a string s = s[1] · · · s[n] ∈ Σ ∗ consisting of solid characters oflength n ≥ 0.
Definition 1 (pattern [9, 13, 12]). A pattern over Σ is a string x in Σ ∪ (Σ·(Σ ∪ {◦})∗ ·Σ) that starts and ends with a solid character, or an empty string ε.

We denote the class of patterns by P = {ε} ∪ Σ ∪ (Σ ·(Σ ∪ {◦})∗ ·Σ). For
example, ABC and B ◦ C are patterns, but ◦BC and ◦ ◦ B◦ are not. Note that ε is apattern in our definition. We define a binary relation ¹ over letters and patterns,
called the specificity relation.3 For letters a, b ∈ Σ ∪ {◦}, we define a ¹ b if eithera = b or a = ◦ holds. For patterns x and y, We say that x occurs at position
p in y if there exists some index 0 ≤ p ≤ |y| − |x| such that for every index
0 ≤ i ≤ |x| − 1, x[i] ¹ y[p + i] holds. Then, we also say that p is an occurrenceof x in y, and that x matches the substring y[p..p + |x| − 1].
Example 1. Pattern x = B ◦ D occurs in pattern y = AB ◦ DA at position 1, and x
occurs three times in string s = EABCDABEDBCDE at positions 2, 6 and 9.
We extend the binary relation ¹ from letters to patterns as follows. Let x
and y be patterns in P. If x occurs at some position p in y, then we define x ¹ yand say that either x is contained by y or y is more specific to x. For any patternx, we define ε ¹ x. If x ¹ y but y 6¹ x, then we define x ≺ y and say that either
x is properly contained by y or y is properly more specific to x. We can see that
if x ¹ y and y ¹ x hold, then x and y are identical each other. Furthermore, ¹
is a partial order over P.
Definition 2 (location list [9, 13, 12]). For an input string s ∈ Σ ∗ of lengthn ≥ 0, the location list of pattern x is the set L(x) ⊆ {0, . . . , n − 1} of all the
positions in s at which x occurs. The frequency of x on s is |L(x)|.
Example 2. The location list of pattern x = B ◦ D in the input string s =EA BCD A BED BCD E is L(x) = {2, 6, 9}.
A quorum (or minimum frequency threshold ) is any positive number θ ≥ 1.
Definition 3 (motif [9, 13, 12]). Let θ ≥ 1 be a quorum. We say that pattern
x is a θ-motif (or motif, for short) in s if |L(x)| ≥ θ holds.
Let L be any location list and d be any integer. Then, we define the shift of
L with displacement d by L + d = { ` + d | ` ∈ L }. We write L − x to represent
the set L + y with y = −x.
Lemma 1 ([9, 12, 13]). Let θ ≥ 1 and x, y ∈ P be any motifs. If x ¹ y thenL(x) ⊇ L(y) + d for some integer d ≥ 0.
The converse of this lemma does not hold for motifs in general.
Example 3. Let s = EABCDABEDABCDE over Σ = {A, B, C, D, E} be an input string.
Consider motifs x = AB ◦ D with location list L(x) = {1, 5, 8}, y = B ◦ D with
L(y) = {2, 6, 9}, and z = D with L(z) = {4, 8, 11}. We can see that z ≺ y ≺ xholds and x, y, z are equivalent each other. For instance, L(z) = L(x) + d withthe displacement d = 3. Then, x is maximal in s, but y and z are not.
3

The binary relation ¹ is also called the generalization relation or the subsumption
relation in artificial intelligence and data mining.

Definition 4 (maximal motif [9]). Let θ ≥ 1 be a quorum. A motif x is
maximal in s if for any motif y that properly contains x, there is no integer dsuch that L(y) = L(x) + d.
In other words, θ-motif x is maximal in s iff there exists no θ-motif in sproperly containing x that is equivalent to x under shift-invariance. Let θ be aquorum. We denote by F and M the sets of all (frequent) motifs and all maximal
motifs, respectively. Clearly, M ⊆ F ⊆ P for any s and θ. A maximal motif yis a successor of maximal motif x (within M) if x ≺ y and there is no maximal
motif z such that x ≺ z ≺ y.
Now, we state our problem as follows.
Definition 5. The maximal motif enumeration problem is, given an input strings of length n and a quorum θ ≥ 1, to enumerate all maximal motifs in s without
repetition.
2.2

Merge and Closure

In this subsection, we define merge and closure operations which are originallyintroduced in [2, 3, 12, 13].
An infinite string is a function from integers to symbols in Σ ∪ {◦}. For a
finite string x ∈ (Σ ∪ {◦})∗ , the infinite or expanded version of x is an infinite
string bxc defined by bxc[i] = x[i] for 0 ≤ i ≤ |x| − 1 and bxc[i] = ◦ otherwise.
For an infinite string x, its finite string version (or trimmed version), denotedby dxe, is the longest substring of x that starts and ends with a solid characterin Σ, i.e., dxe ∈ P, if it exists and ε otherwise. By definition, if x is a patternthen dbxce = x for every finite x, but it is not the case for general string suchas x = ◦ B ◦ C ◦.
Let d be a displacement. For an infinite string x, the infinite string (x + d) is
defined by (x + d)[i] = x[i − d] for every i. For a finite string x, (x + d) = bxc + d.
Then, (x + d) is called the shift of x by d.
Example 4. Given a finite string s = EABCDABED, its infinite version is bsc =· · · ◦ ◦ ↓ EABCDABED ◦ ◦ · · ·, where ↓ indicates the origin i = 0. Then, (bsc − 2) =· · · ◦ ◦ EA ↓ BCDABED ◦ ◦ · · ·, and its finite version is d(bsc − 2)e = ↓ EABCDABED = s.
Merge of infinite and finite strings. Next, we define the merge operator ⊕.
For letters a, b ∈ Σ, we define a⊕a = a and a⊕◦ = ◦⊕a = a⊕b = ◦ if a 6= b. For
infinite strings α, β, the merge of α and β, denoted by α ⊕ β, is the infinite stringsuch that (α⊕β)[i] = α[i]⊕β[i] for every integer i. For finite strings x, y ∈ P, themerge of x and y, denoted by x ⊕ y, is the finite string x ⊕ y = d bxc ⊕ byc e ∈ P.
Note that the operator ⊕ is associative and commutative.

Definition 6 (merge of location list [3, 12]). For a location list L = {d1 , . . . , d|L| }of a string s, the merge of L = {d1 , . . . , d|L| } ⊆ {0, . . . , n − 1} is the pattern
L
L ∈ P defined byM
L = d(bsc + d1 ) ⊕ · · · ⊕ (bsc + d|L| )e.
We can see the following properties hold.
Property 1. Let L, L0 be any location lists.
L
L 0
1. If L ⊇ L0 then
L¹
L.
L
L
2.
L = (L + d) for any integer d.
Property 2. Let θ be a quorum and L be any location list such that |L| ≥ θ.
LThen,
L is a maximal motif.
Property 3. For any string xy ∈ Σ(Σ ∪ {◦})∗ , L(xy) = L(x) ∩ (L(y) + |x|).
Property 4. Let x and y be two strings in Σ(Σ∪{◦})∗ such that x[i] = ◦, y[i] = c,and x[j] = y[j] for j 6= i. Then, we have L(y) = L(x) ∩ {d|x[d + i] = c}.
Definition 7 (closure operation [12, 13] 4 ). Given a pattern x and an inputLstring s, the motif Clo(x) =L(x) is called the closure of x on s.
The above definition is a generalization of the closure operation [11, 16] fromsets to motifs, and is introduced by [12, 13].
We can see the following lemma claiming the computability of the closure.
Lemma 2. The closure Clo(x) of a pattern x is unique and computable inO(mn) time from x and L(x), where n = |s| and m = |L(x)| ≤ n.
Proof. The character of the jth position of Clo(x) is bxc[d1 ]⊕, · · · , bxc[dm ] whereL(x) = {d1 , . . . , dm }. It can be computed in O(m) time. Since the character ofthe jth position of Clo(x) is ’◦’ for any j < 0 and j > n, we can compute Clo(x)in O(mn) time. We can also observe that Clo(x) is unique.
utLemma 3 (properties of closure). Let x, y be any patterns occurring in s.
1. x ¹ Clo(x).
2. Clo(x) = Clo(Clo(x)).
3. If x ¹ y then Clo(x) ¹ Clo(y).
4. Clo(x) is the unique maximal element w.r.t ¹ in the equivalence class ofpatterns [x] = { y | L(x) = L(y) + d for some integer d } containing x.
4

The set-counterpart of the closure has been known in data mining and formal concept
analysis [11, 16]. The closure Clo(x) for motifs was introduced in [12] and called the
maximal extension in [13].

Theorem 1 (characterization of maximal motifs [12]). Let θ be a quorum
and x be a motif in an input string s. Then, the following (i)–(iii) are equivalent:(i) x is a maximal motif.
L(ii) x =L and |L| ≥ θ for some L ⊆ {0, . . . , |s| − 1}.
(iii) x = Clo(x).
The next lemma says that the converse of Lemma 1 holds as follows for
maximal motifs.
Lemma 4 ([12]). Let θ ≥ 1 be a quorum and x, y ∈ M be maximal motifs.
Then,
1. x ¹ y iff L(x) ⊇ L(y) + d for some integer d, and
2. if x = y iff L(x) = L(y) + d for some integer d.
Proof. The only-if direction of the statement 1 is obvious from Lemma 1. Now,
we show its if direction. Let x, y ∈ M be maximal motifs. Suppose that L(x) ⊇L
L(y) + d holds for some d. From Property 1 for the merge operator , if L(x) ⊇L
L
L(y) thenL(x) ¹
L(y) holds. On the other hand, the characterization of
L
Theorem 1 says that x = Clo(x) =L(x) for every maximal motif x. Therefore,
it follows that x ¹ y, and thus the result is proved. Then, the statement of 2
immediately follows from the above statement 1.
ut
In other words, ordered sets (M, ¹) and (Lθ , ⊇) are isomorphic, where Lθ ={ L(x) | x ∈ F } is the class of the location lists for all (possibly non-maximal)
motifs in s.
Example 5. Let s = ABBCABRABRABCABABRABBC be an input string. Let x =B◦◦◦◦A be a pattern with location list L(x) = {2, 5, 8}. First, we compute thealignment of infinite strings S = {(bsc − 2), (bsc − 5), (bsc − 8)} as follows:◦◦◦◦◦◦AB↓BCABRABRABCABABRABBC = s − 2◦◦◦ABBCA↓BRABRABCABABRABBC◦◦◦ = s − 5
ABBCABRA↓BRABCABABRABBC◦◦◦◦◦◦ = s − 8where the underlines indicate the common letters. Then, we compute the mergeL
S = (bsc − 2) ⊕ (bsc − 5) ⊕ (bsc − 8) of the infinite strings in S as follows:◦◦◦◦◦◦◦◦↓B◦AB◦AB◦◦◦◦◦◦◦◦◦◦◦◦◦ =L

S

Finally, we get the closure Clo(x) = B◦AB◦AB by taking its finite version.

2.3

Enumeration algorithms

We introduce terminology for enumeration algorithms according to [7, 15]. An
enumeration algorithm for an enumeration problem Π is an algorithm A thatreceives an instance I and outputs all solutions S in the answer set S(I) intoa write-only output stream O without duplicates. Let N = ||I||, M = |S(I)|be the input and the output sizes on I, and TA be the total running time of A
for computing all solutions on I. Then, A is of output-polynomial (P-OUTPUT)
if TA is bounded by a polynomial q(N, M ). A is of polynomial enumeration
time (P-ENUM) if the amortized time for each solution x ∈ S is bounded bya polynomial p(N ) in N , i.e., TA = O(M · p(N )). A is of polynomial delay (PDELAY) if the delay, which is the maximum computation time between two
consecutive outputs, is bounded by a polynomial p(N ) in the input size N . A isof polynomial space (P-SPACE) if the maximum size of its working space, except
the size of output stream O, is bounded by a polynomial p(N ). By definition,
P-OUTPUT is the weakest and P-DELAY is the strongest among P-OUTPUT,
P-ENUM, and P-DELAY, that is, any P-DELAY algorithm is P-ENUM, andany P-ENUM algorithm is P-OUTPUT.
The class of tree-search algorithm is an important class of P-ENUM algorithms, which traverses a spanning tree T over S(I), and outputs each solution
at each node with work time P (N ). In general, if P (N ) is polynomial then atree-search algorithm A is a P-ENUM with linear total complexity M · P (N ),but not necessarily P-DELAY since the delay depends on the maximum depth of
the tree. The following lemma by Uno [15] gives a useful technique to translatea tree-search enumeration algorithm in P-ENUM into one in P-DELAY.
Lemma 5 (Uno [15]). Any tree-search algorithm for Π with polynomial work
time P (N ) per node can be transformed into a polynomial delay algorithm forΠ with delay O(P (N )).
Proof. For completeness, we sketch the proof of [15]. The modified algorithm A0
with the delay 3·P (N ) + O(1) visits all nodes of T in a depth-first order as theoriginal. At each node of depth d ≥ 0 with solution x, A0 outputs x in the first
visit (preorder) if d is even, and in the last visit (postorder) if d is odd. At theleaf node, the algorithm always outputs a solution, immediately. Then, we cansee that on at least one node among three consecutive visiting nodes, a solution
is output.
ut3

Lower bounds for the number of maximum motifs

We show the following lower bound of the number of maximal motifs in a given
sequence, which justifies output-sensitive algorithms for the maximal motif enumeration problem. The upper bound of |M| is obviously 2O(n) .

Theorem 2 (exponential lowerbound of maximal motifs). There is an
infinite series of input strings s0 , s1 , s2 , . . . , such that for every i = 0, 1, 2, . . .,the number |M| of maximal motifs in si is bounded below by 2Ω(n) , that is,exponential in n = |si |.
Proof. Let Σ = {#, 0, 1} and n ≥ 1 be any nonnegative integer. We define theinput string s = #t1 # · · · #tn # over Σ so that s has a family of exponentially many
motifs that have mutually distinct location lists. For every i = 1, . . . , n, the i-th
block ti = b1 · · · bn ∈ {0, 1}n is defined as follows: for every j = 1, . . . , n, bj is 1 if
i = j and 0 otherwise. These n blocks t1 , . . . , tn correspond to the boolean matrixof size n×n with 1’s on the diagonal. Next, we define a family X of patterns asfollows. For every bit string b = b1 . . . bn ∈ {0, 1}n of length n we define patternx(b) = #p1 . . . pn # in X as follows: for every i = 1, . . . , n, pi = ◦ if bi = 1, andpi = 0 if bi = 0. For example, if b = 0010 then x(b) = 00 ◦ 0. Then, we can showthat pattern x(b) matches the i-th block ti for every i = 1, . . . , n iff bi = 1. Let{d1 , . . . , dn } ⊆ {0, . . . , |s| − 1} be the set of the initial n positions of delimiters# in s. Then, the location lists of x(b) is L(x(b)) = { di | 1 ≤ i ≤ n, bi = 1 }.
Furthermore, if b 6= b0 then L(x(b)) 6= L(x(b0 )) for any b, b0 ∈ {0, 1}n . Therefore,
we know that all patterns in X have mutually distinct location lists, and thus
they are maximal in s provided they satisfy a quorum. Let θ = 21 n be a quorum.
Then, we can show thatthe number of maximum motifs within X is boundedPn ¡ ¢
ut
below by F = k=θ nk = 2Ω(n) . This completes the proof.
The following lemma shows that frequent closed itemset mining is a special case of maximal motif mining. A transaction database D is a collection oftransactions where a transaction is a subset of a given set E of items. D may
includes many identical transactions. For a subset x of E, an occurrence of x isa transaction including x. The set of occurrences of x is called the d enotationof x, and the frequency of x is the cardinality of its denotation. x is called aclosed itemset[11, 16] if x is properly included in another subset of E which has
the same denotation as x. See the details of the notion of closed itemsets and its
enumeration algorithm in [11, 16]
It is known that the closed itemset enumeration (with frequency at least 1)
is equivalent to the maximal bipartite clique enumeration in bipartite graphs[5]. Since counting maximal bipartite cliques in a bipartite graph is known to be#P-complete[17], we can see that counting maximal motifs is also #P-complete.
Lemma 6 (transformation from closed itemsets to maximal motifs).
For every transaction database r = {t1 , . . . , tm } consisting of m transactions
over n items of total size N = mn, there exists an input sequence s of lengthO(nm) such that the set Mrθ of θ-frequent closed itemsets in r is equivalent tothe set of Msθ+m of maximal motifs in s with quorum θ + m.

Proof. Let Σ = {#, 0, . . . , n + 1, 1̄, . . . , n̄}. We define s(t) for transaction t by
the string of length n such that ith letter is i if i ∈ t, and is ī otherwise.
Then, we define s = s(t1 )# · · · #s(tm )s({0, . . . , n + 1}) · · · s({0, . . . , n + 1}) wheres({0, . . . , n + 1}) = 0123 · · · n + 1 and it is repeated m times. Note that there
is no # between s({1, . . . , n})’s. We can see that any pattern x of frequency atmost m + 1 includes only letters in 0, . . . , n, ◦, and can not include two same
letters. Thus, such x is obtained from a substring of 0123 · · · n + 1 by replacingsome letters the substring by ◦. Since any such pattern matches 0123 · · · n + 1,
the frequency of such pattern is always no less than m. Moreover, we can seethat if such a pattern x does not begin with 0 or does not end with n + 1, it
never be a maximal motif.
For an itemset I, we define its corresponding pattern by the pattern obtained
from 0123 · · · n + 1 by replacing items not in I by ◦. Then, we can see that x
appears at the position of s(ti ) if and only if ti includes I. Thus, I is a closed
pattern if and only if it is a maximal motif, and the frequency of I is equal to
the frequency of the corresponding maximal motif minus m.
ut
From the following corollary obtained by the lemma, we know that the maximal motif enumeration problem is at least as hard as the closed itemset enumeration problem [5, 11, 16].
Corollary 1. Any algorithm for enumerating maximal motifs in s of size n intime T (n) per motif, space S(n), and delay D(n) can be transformed into analgorithm for enumerating closed itemsets with minimum support in O(T (N 2 ))time per itemset, space O(S(N 2 )), and delay O(D(N 2 )) on r of size N .
Theorem 3 (#P-completeness of maximal motifs). The problem of counting the number of maximal motifs in a given string is #P-complete.
The following theorem says that the number of motifs can be exponentiallylarger than the number of maximal motifs.
Theorem 4 (succinctness of maximal motifs). There is an infinite series
1of input strings s0 , s1 , s2 , . . . , such that for every i ≥ 0 with quorum θ = 2n+2
|si |,
1

the number F = |F| of motifs in si is exponential (more precisely 2Ω( 2n+2 |si |) ),while the number M = |M| of maximal motifs in si is no more quadratic in |si |.
Proof. Theorem 1 of Uno et al. [16] says that there is an infinite series of transaction databases such that the number F of frequent itemsets and the number
M of frequent closed itemsets in a transaction database of size mn are F = 2Ω(n)and M = O(m2 ), respectively. Combining Lemma 6 above and the constructionsof Theorem 1 of [16], where N = Θ(m2 ) for large m and n, we obtain the result.
utFrom Theorem 4, we know that a straightforward algorithm for enumerating
M based on the enumeration of motifs does not work efficiently. This is also
true for most real world datasets. Figure 1 shows an example, where there are
only 10 maximal motifs among 50 motifs in a string of length 21.

4Previous approaches for maximal motif enumeration

We give a brief review on possible approaches for output-sensitive computationof M and summarize the previous results.
4.1

Previous approaches

A most straightforward method of generating maximal motifs is to use frequent
pattern generation. We enumerate all motifs in an input string s, classify theminto equivalence classes according to their location lists, and find the maximal
motifs for each equivalence class. This method requires O(|F|) time and O(||F||)memory. Since O(|F|) can be exponentially larger than |M|, we cannot obtainany output-sensitive algorithm in time and memory in this way. The algorithmin [?] uses maximal motifs instead of solid characters to extend the pattern.
In the worst case it combines any pairs of maximal motifs, thus the time complexity is output polynomial but square of the output size. Moreover, the spacecomplexity is not polynomial in the input size, since we have to store maximal
motifs previously discovered in memory.
Another possible method is to use the basis for maximal motifs [10, 12, 13].
Parida et al [9] introduced the use of the basis for maximal motif enumeration.
A basis for M is a subset B ⊆ M of motifs such that M can be generated byfinite applications of an operation, e.g., ⊕, over M. Presently, the basis BI of
irredundant motifs [9], the basis BT of tiling motifs [13], and the basis BP ofprimitive motifs [12] have been proposed. A maximal motif x ∈ M is tiling if
for any set of maximal motifs y1 , . . . , yk ∈ M and any set of integers d1 , . . . , dk
Swith x ¹ yi , if L(x) = i (L(yi ) + di ) then x = yi for some i. Pisanti et al. [14]describe a simple algorithm for computing M from BT in O(|M|2 · n) total timeand O(||M||) space. However, the total time is not linear in |M|. Thus, it is of
P-OUTPUT but not of P-ENUM.
4.2

An improved algorithm for generating M from a basis BT

We can improve Pisanti et al.’s method for M adopting an idea used in [12] forgeneration of BT from s. The next lemma is essential for our algorithm.
Lemma 7. Any maximal motif x ∈ M satisfies either (i) x ∈ BT , or (ii) there
exist some y ∈ M and integer d such that x ≺ y and x = y ⊕ (s + d).

Algorithm MaxBasis( θ: quorum, s: input string, B: basis)
1 M0 := B; i := 02 while (∆ 6= ∅) do begin3∆ := ∅;
4for each y ∈ Mi and d ∈ {0, . . . , n − 1} do
Si
5
if y ⊕ (s + d) 6∈ ( k=0 Mk ∪ ∆) then ∆ = ∆ ∪ {y ⊕ (s + d)}; output y ⊕ (s + d);i+16M:= ∆; i := i + 1;
7 end
Fig. 2. An polynomial time enumeration algorithm for generating M from B basedon breadth-first search. This algorithm does not have polynomial space or polynomial
delay.

Figure 2 shows our algorithm MaxBasis that computes M from BT . In thealgorithm, the set Mi is the set of maximal motifs which can be generated from
B by applying the operation in line 5 i times. We use a trie to store Mi and ∆for O(|x|) membership of pattern x. Thus, we can implement MaxBasis to runin O(|M| · n2 ) total computation time.
Theorem 5 (generation of maxmal motifs from the basis). Given a quorum θ ≥ 1, an input string s of length n, and the basis BT of tiling motifs, thealgorithm MaxBasis in Figure 2 enumerates all maximal motifs of M from B
in O(n2 ) amortized time per maximal motif with O(||M||) space.
Since its space complexity and delay are O(||M||) and O(|M| · n2 ), respectively, MaxBasis is neither a polynomial space or polynomial delay even givena basis BT as input. Note that it is still open whether the basis BT (or BP )is output-polynomial time computable from s since the total running time ofPθ
the algorithms in [12] and [14] are only bounded by O(nθ i=1 |BTi |) or nO(θ) ,where BTi is the basis for quorum i ≥ 1. Hence, it seems difficult to obtain an
output-polynomial time algorithm for BT and thus M in this approach. 5

5

A polynomial space polynomial delay algorithm using
depth-first search

In this section, we present an efficient depth-first search algorithm MaxMotif
that, given a quorum θ ≥ 1 and an input string s of length n, enumerates all
5

Parida et al. [10] presented an output-polynomial time algorithm for the class offlexible motifs, and claimed that they also presented a similar algorithm for maximal
motifs with wild cards in [9]. Since these algorithms seem to depend on an unproved
conjecture in [9], however, we did not include them. At least, the algorithm in [10]requires the space and the delay proportional to the output size |M|. Thus, it is notpolynomial space and polynomial delay.

maximal motifs x in s in O(|L(x)| · n2 ) delay and O(n) space. In what follows,
we fix input string s of length n ≥ 1 and 1 ≤ θ ≤ n. Unlike MaxBasis in theprevious section, MaxMotif uses depth-first search over M to avoid the useof extra storage for keeping all discovered motifs. In the following sections, we
explain the details of the algorithm.
5.1

Building tree-shaped search route for maximal motifs

We first build a tree-shaped search route T = (V, P, ⊥) for traversing all maximal
motifs (Figure 3). The node set V = M consists in all maximal motifs in s, P
is the set of reverse edges defined later, and ⊥ = Clo(ε) is the root called theroot motif . If s contains at least two distinct solid letters then ⊥ = ε, otherwise⊥ = a for the only letter a in s.
Lemma 8. ⊥ = Clo(ε) is the unique shortest maximal motif in s.
Proof. Since L(⊥) = {0, . . . , n − 1} is the largest location list on s, it follows
from Lemma 4 that Clo(ε) ¹ x for any maximal motif x.
ut
Next, we define the set P of reverse edges from a child to its parent asfollows. Given a maximal motif x, the core index of x, denoted by core i(x), is
the smallest index 0 ≤ ` ≤ |x|−1 such that L(x) = L(y) for the prefix y = x[0..`],
if x 6= ⊥. For x = ⊥, core i(x) is defined by −1. Then, we assign the uniqueparent to each non-root maximal motif.
Definition 8 (parent of maximal motif ). For a maximal motif y such thaty 6= ⊥, the parent of y, denoted by P(y), is the pattern P(y) = Clo(dy[0..core i(y)−1]e). 6
Lemma 9. For every maximal motif y such that y 6= ⊥, P(y) always exists, isunique, and is a maximal motif. Furthermore, P(y) ≺ y holds.
Proof. Since y 6= ⊥, L(y) 6= L(⊥), thereby L(dy[0..` − 1]e) 6= L(y) holds forsome l ≥ 0. This assures that core i(y) − 1 ≥ −1 and P(y) is always defined.
From the definition, P(y) is unique, and clearly a maximal motif.
utTheorem 6. T = (V, P, ⊥) is a spanning tree for all maximal motifs in M.
Proof. From Lemma 9, all maximal motifs y but ⊥ have the unique parent P(y)such that P(y) ≺ y. Since the relation ¹ is acyclic on M, i.e., there is no infinite
decreasing chain of maximal motifs of M, the result follows.
ut
The remaining task is to show how to enumerate all children y of a given
parent motif x within polynomial memory space of the input size. This is notan easy task since we have only reverse edges. We discuss this issue in the next
subsection.
6

In the definition, y[0..core i(y)−1] ∈ Σ(Σ ∪{◦})∗ ∪{ε} may not be a proper pattern.
Thus, we use dy[0..core i(y) − 1]e instead of y[0..core i(y) − 1] to remove the trailing◦’s.

input string s

00
10
20
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1

quorum θ = 3

ABBCABRABRABCABABRABBC

spanning tree T = (M, P) for maximal motifs
εpattern lattice L = (M, ≤) for maximal motifs

21

<0,A>

AB

AB

7

<2,R>

ABRAB

3

ABoAB

4

BC

3

<3,A>
<0,B>

B

9

ε

21

<1,C>
<2,A>

BoAB
<5,A>
<9,B>

<6,B>

BoooooB

5
BoABoAB3

BoABoooooB

3

4

B

ABRAB

3

ABoAB

4

BC

3

BoAB

5

7

9
BoooooB

BoABoAB3

BoABoooooB

3

4

Fig. 3. The spanning tree T = (M, P) (left) and the pattern lattice L = (M, ¹)(right) for maximal motifs of M on quorum θ = 3 and input string s (top). Eachbox represents maximal motif x in M and the number right to the box indicates its
frequency |L(x)|. Each arrow indicates ordering, P or ¹, of a tree/lattice. (Section
5.1). An arrow in the tree T indicates the ppc-extension with seed hk, ci. The newly
introduced letter c is written in bold face. (Section 5.2). There are 10 maximal motifs
among 49 motifs in s.

5.2

Prefix-preserving closure extension

We introduce the prefix-preserving closure extension defined as follows. A substitution for motif x is a pair ξ = hk ← ci ∈ Z × Σ of integer k and solid letterc. If bxc[k] = ◦, ξ is compatible with x. The application of ξ to x, denoted byxξ = xhk ← ci, is the motif dye, where y is the infinite string such that for every
integer i, y[i] = c if i = k and y[i] = bxc[i] otherwise. For example, if x = BA ◦ B,
then xh−1 ← Ci = CBA ◦ B, xh2 ← Ci = BACB, and xh6 ← Ci = BA ◦ B ◦ ◦ C.
Definition 9 (ppc-extension). For any maximal motifs x and y, y is a prefixpreserving closure extension (or a ppc-extension) of x if the following (i)–(iii)hold:(i) y = Clo(xhk ← ci) for some substitution, called its seed, ξ = hk ← ci ∈ Z×Σcompatible with x, that is, y is obtained by first substituting c at index k andthen taking its closure,(ii) the index k satisfies k > core i(x), and(iii) x[0..k − 1] = y[0..k − 1], that is, the prefix of length k − 1 is preserved, wherex[0..k − 1] is obtained from x by padding trailing ◦’s if necessary.
Example 6. In Figure 3, we show an example of the spanning tree for M generated by the ppc-extension for an input string s = ABBCABRABRABCABABRABBC andquorum θ = 3. Then, we have maximal motif x = AB with location list L(x) ={0, 4, 7, 10, 13, 15, 18}. If we apply substitutions ξ1 = h2, Ri and ξ2 = h3, Ai tox, respectively, then we obtain the ppc-extension y = ABRAB = Clo(ABR) =Clo(x · ξ1 ) with {4, 7, 15}, and z = AB ◦ AB = Clo(AB ◦ A) = Clo(x · ξ2 ) with
{4, 7, 10, 15}.
Lemma 10. Let x be any maximal motif and y = Clo(xhk ← ci) be a ppcextension of x. Then, k is the core index of y.
Proof. Since k is larger than the core index of x, we have that L(dy[0..k − 1]e) =L(x). Thus, the core index of y is greater than k − 1. Since y = Clo(dy[0..k]e),
L(y) = L(dy[0..i]e) holds for any i ≥ k. Therefore, the core index of y is k.
The goal of this subsection is to prove the following theorem.
Theorem 7 (correctness of ppc-extension). For any maximal motifs x, ysuch that y 6= ⊥, (1) x = P(y) if and only if (2) y = Clo(xξ) is a prefixpreserving closure extension of x for some substitution ξ = hk ← ci ∈ Z × Σ
compatible with x. Furthermore, there exists exactly one ξ satisfying condition(2) for each y.
Proof. (1) to (2): Suppose x = P(y), and thus x = Clo(dy[0..` − 1]e) for thecore index ` of y. First, we show that x[0..` − 1] = y[0..` − 1] holds. Since x =Clo(dy[0..`−1]e), we have x[0..`−1] ¹ y[0..`−1]. Thus, if x[0..`−1] 6= y[0..`−1],a more specific motif y 0 = x[0..` − 1]y[`..|y| − 1] satisfies y ≺ y 0 but L(y) = L(y 0 )using Lemma 3. Next, if we take ξ = h` ← y[`]i, then the definition of core index
assures that y = Clo(xξ). Thus, ξ satisfies the condition of ppc-extension. This
proves this direction.
(2) to (1): Suppose that y = Clo(xhk ← ci). Then, it follows from Lemma 10
that k is the core index of y, thus P(y) = Clo(dy[0..k − 1]e). Since y is a ppc
extension, we have y[0..k − 1] = x[0..k − 1], and then Clo(dy[0..k − 1]e) =Clo(dx[0..k − 1]e). By condition (iii) of ppc-extension, we can show that choiceof ξ is unique.
ut
5.3

A polynomial space polynomial delay algorithm

Based on Theorem 7, we present in Figure 4 our algorithm MaxMotif thatenumerates all maximal motifs in a given input string by the depth-first searchover M applying the ppc-extension to each maximal motif.
Although a straightforward implementation of the procedure Expand in Figure 4 requires O(n4 ) time for each maximal motif, we can reduce the computation
time further.
Theorem 8. Given a quorum θ ≥ 1 and an input string s of length n, thealgorithm MaxMotif in Figure 4 enumerates all maximal motifs x of M in
O(L(x)n2 ) amortized time per motif with O(n) space and O(L(x)n2 ) delay.

Algorithm MaxMotif(θ: quorum, s: input string)
input: a quorum θ and an input string s;
output: all maximal motifs in M;
0 ⊥ = Clo(ε);//the root motif ⊥.
1 call Expand(⊥, {0, ..., n − 1}, −1, θ, s);//core i(⊥) = −1.
Procedure Expand(x, L(x), core i(x), θ, s)
input: maximal motif x, L(x), core i(x), quorum θ, and input string s;
output: all descendants of x in T ;2 if |L(x)| < θ then return;3 output x;
4 for each k, core i(x) + 1 ≤ |s| − 1 such that x[k] = ◦ do5
for each c ∈ Σ do begin
6
y = Clo(xhk ← ci);//ppt-extension.
7
if bxc[0..k − 1] = byc[0..k − 1] then8call Expand(y, L(y), k, θ, s);
9
end for
10 end forFig. 4. A polynomial space polynomial delay enumeration algorithm for M.

Proof. By Theorem 6 and Theorem 7, we see that the algorithm MaxMotifvisits all maximal motifs on the spanning tree T starting from the root ⊥. Since
T is a tree and any maximal motif appears in T , the algorithm enumerates M
without duplicates.
Let W (x) be the work that Expand spends for each maximal motif x except
the recursive call. For each y = xhk ← ci, computing the closure Clo(y) at line 6
takes O(|L(y)| · n) time. Thus, W (x) = O(|Σ| · |L(x)| · n2 ) time and this gives
the delay per maximal motif.
To improve the computation from line 5 to line 9, we compute L(y) for all
y = xhk ← ci at once, by using the technique called Occurrence Deliver 7 .
Suppose that we have an empty bucket for each letter c ∈ Σ. Then, for eachposition d ∈ L(x), we insert d to the bucket of the letter s[d + k]. After thisoperation, the content of the bucket of c is L(xhk ← ci). Now we can see that foreach k line 5 to line 9 takes O(|L(x)|n) time. This does not increase the spacecomplexity of O(n).
By applying the technique by Uno [15] that transforms any tree-search enumeration algorithm with work time W (x) at each node into a W (x) delay algorithm, we finally obtain an algorithm with delay O(|L(x)| · n2 ).
ut
In summary, the time complexity of the algorithm is O(n3 ), the space complexity is O(n), and the delay is O(n3 ).
7

Occurrence deliver is introduced for closed itemsets enumeration in Uno et al. [16]1000000
100000Motif
MaxMotif
quorum

1000
100
10

00
0

00

00

+0
7
1E

25
60

64
00

0

16
00

0

40
00

1
10
00

time per 10000 patterns (sec)

10000lengthFig. 5. Computation time with the increase of string length

Corollary 2. The maximal motif enumeration problem is solvable in polynomial
space and polynomial delay in the input size n = |s|.
ut6Computational experiments

In this section, we show the results of computational experiments of our MaxMotif algorithm. The aims of the experiments are to see,
1. the computation time for the real world data,
2. the increase of the computation time against the increase of the length of
the input string,
3. the increase of the computation time against the decrease of quorum, and
4. what kind of patterns we get.
We compared these with frequent motif mining. The algorithm for frequent
motif mining is a usual depth-first backtracking type one, with occurrence deliver, so the main body of the implementations of both algorithms are the same.
We coded the algorithms with C language with standard library functions.
The computer has CPU of Intel Pentium M 1.2GHz and 256MB memory, the OS
was cygwin, a Linux emulator on Windows, and the compiler was gcc. We chose
Y chromosome of the human genome8 as a test instance, and some text files
additionally. Y chromosome has repeated structures in it, thus it is a good instance for frequent pattern mining. By the experiments, we evaluated the changeof computation time with the change of the input string length and the quorum.
First, we see the change of the computation time by the increase of the input
string length. We made strings for the experiments by taking the first k letters of
Y chromosome for several k’s. For each string, we gave a quorum so that nearly
10,000 frequent patterns appear. The results are shown in Figure 5. The X axis
8

We took the genome data at ftp://ftp.ncbi.nih.gov/genomes/H sapiens/100000
10000

Motif
MaxMotif
quorum

100
10

+0
7
1E

00

00

00
0
25
60

64
00

0

16
00

0

40
00

1
10
00

time per 10000 patterns (sec)1000lengthFig. 6. Computation time with the increase of string length without any consecutive
six ◦’sis the length of the input strings, and Y axis is the computation time for 10,000
patterns. Both axes are drawn in log scales. We also draw lines for the quorum.
We can see that the computation time is not so long for genome sequence of
10 million length, if we want to find not so many patterns. Perhaps MaxMotifworks for practical huge genome sequences. Both the number of patterns andthe computation time are quite similar, between MaxMotif and frequent motif
mining. This shows that the computational costs for generating ppc extensions,which is mainly for checking the equalities of prefixes, are not large. Thus, we
can see that we need no additional computational cost to find only maximal
patterns. The lines of the computation time and quorum is close to parallel.
This means that the computation time depends deeply on quorum but not somuch on the length of input string, when we discover thousands of patterns.
In the output, we saw many unnatural patterns, such as A ◦ · · · ◦ T ◦ · · · ◦ A.
They are maximal motifs, but seem to be unnecessary in practice. To avoid such
patterns, we restricted consecutive ◦’s. Here we restrict six consecutive ◦’s inthis experiments. The results are shown in Figure 6. The computation time perpattern does not increase, but the quorum to get 10,000 patterns is decreased.
This implies that we avoided many such unnecessary patterns, and find more
infrequent but necessary patterns.
Next, we see the result by the change of quorum. The test instance was asubstring of 4,000 letters taken from Y chromosome, and we execute the algorithm for several quorums from 320 to 4. The results are shown in Figure 7.
Figure 8 shows the results when we forbid any consecutive three ◦’s.
As we can see, there is no difference on the number of patterns, between
frequent motifs and frequent maximal motifs when the quorum is large. However, when the quorum is small, the difference is quite huge. Especially, whenthe quorum was smaller then eight, frequent motif mining algorithm did notterminate in three hours. This implies that maximal motif is a good model formining many sequence patterns with a small frequency.

6

10

20

motif
MaxMotif#Motifs#MaxMotifs

80

32
0

time(sec) & #discovered motifs

100000000
10000000
1000000
100000
10000
1000
100
10
1
0.1
0.01

quorumFig. 7. The number of patterns and computation time with the decrease of quorum

6

10

20

motif
MaxMotif#Motifs#MaxMotifs

80

32
0

time(sec) & #discovered motifs

1000000000
100000000
10000000
1000000
100000
10000
1000
100
10
1
0.1
0.01

quorumFig. 8. The number of patterns and computation time with the decrease of quorum
with forbidding any consecutive three ◦’s

Finally, we report the results of an execution for text data; We examined thesource code of MaxMotif itself. The source code contains about 15000 letters,
and we ignored any “new line” characters. The computation was done in two
seconds, and we got about 20,000 maximal motifs. However, there were many
patterns such as “*****************◦◦*”. Such patterns match the comment
line, such as/***********************************************//***** main routine ****************************//***********************************************/
One can see that many combinations of consecutive ’*’ and ◦ make maximal
motifs for this string, and such patterns are almost part of the output. Even if
we forbid some consecutive ◦’s, still they remain in the output. To avoid such
patterns, we introduced “removing overlapping occurrences”. For a pattern x, if
two positions d and d0 in L(x) satisfy that d < d0 < d + |x|, that is, overlapping,we consider that d0 is redundant, and remove it from L(x) when we take theclosure. Then, we could avoid almost all such redundant patterns efficiently.
As a conclusion, we could see that maximal motifs can be a good model inpractice, and we can solve the problem in short time even if the input string is
so huge. However, we did not see any result when the size of alphabet is large; inour experiments, it was 4 for genome sequences, and at most 100 for text data.
It is a remaining task in this research.

7

Conclusion

In this paper, we presented a polynomial space polynomial delay algorithm forenumerating all maximal motifs in an input string for the class of motifs withwild cards. By the use of depth-first search based on the prefix-preserving extension, the algorithm enumerates all maximal motifs without explicitly storing andchecking the maximal motifs enumerated so far. This drastically improves thespace and the delay complexities compared with the previous algorithms withbreadth-first search. The experimental results show the efficiency of our algorithm in practice, even if the input string is so huge, such as genome sequencesof over 10 million length.
In the context of data mining, maximal motifs for sets of this type are called
closed itemsets, and since the end of 90’s, related enumeration problems havebeen extensively studied for various classes of combinatorial objects, such as
sets, sequences, trees, and graphs [3, 5, 11, 12, 16, 18]. On the other hand, however, most of them are heuristic algorithms based on branch-and-bound, andthere are only a few results on output-polynomial time enumeration for theseclasses [3, 5, 16]. Hence, the result of this paper will be a first step towards efficient enumeration of maximal patterns for complex combinatorial objects suchas sequences, trees, and graphs [3].
Pattern discovery for classes of unions of patterns is one of the difficult
problems in machine learning. Since the class of maximal motifs is a class ofunions generated from tiling motifs [13], it will be a future problem to extend
the proposed enumeration method to pattern discovery for unions of sequence
patterns, e.g. [4]. Implementation of the proposed algorithm with practical improvement and evaluation of the algorithm on the real world datasets, e.g., biological datasets, are also interesting future problems.

References
1. A. Apostolico, M. Comin 2, L. Parida, Conservative Extraction of OverRepresented Extensible Motifs,” ISMB (Supplement of Bioinformatics) 21, 9-18,
2005.
2. A. Apostolico and L. Parida, Compression and the wheel of fortune, In Proc. the2003 Data Compression Conference (DCC’03), IEEE, 2003.

3. H. Arimura, T. Uno, An output-polynomial time algorithm for mining frequent
closed attribute trees, In Proc. ILP’05, LNAI 3625, 1–19, August 2005.
4. H. Arimura, T. Shinohara, S. Otsuki, Finding minimal generalizations for unionsof pattern languages and its application to inductive inference from positive data,
In STACS’94, LNCS 775, Springer-Verlag, 649–660, 1994.
5. E. Boros V. Gurvich, L. Khachiyan, K. Makino, The complexity of generating
maximal frequent and minimal infrequent sets, In Proc. STACS ’02, LNCS, 133141, 2002.
6. M. Crochemore and W. Rytter, Jewels of Stringology, World Scientific, 2002.
7. L. A. Goldberg, Polynomial space polynomial delay algorithms for listing familiesof graphs, In Proc. the 25th STOC, ACM, 218–225, 1993.
8. D. Gusfield, Algorithms on strings, trees, and sequences, Cambridge, 1997.
9. L. Parida, I. Rigoutsos, A. Floratos, D. Platt, and Y. Gao, Pattern discovery
on character sets and real-valued data: linear bound on irredundant motifs andeffcient polynomial time algorithm, In Proc. the 11th SIAM Symposium on Discrete
Algorithms (SODA’00), 297–308, 2000.
10. L. Parida, I. Rigoutsos, D. E. Platt, An Output-Sensitive Flexible Pattern Discovery Algorithm. In Proc. CPM’01, LNCS 2089, 131–142, 2001.
11. N. Pasquier, Y. Bastide, R. Taouil, L. Lakhal, Discovering Frequent Closed Itemsets for Association Rules, In Proc. ICDT’99, 398–416, 1999.
12. J. Pelfrêne, S. Abdeddaim, and J. Alexandre, Extending Approximate Patterns,
In Proc. CPM’03, LNCS 2676, 328–347, 2003.
13. N. Pisanti, M. Crochemore, R. Grossi, and M.-F. Sagot, A basis of tiling motifs for generating repeated patterns and its complexity for higher quorum, In
Proc. MFCS’03, LNCS 2747, 622–631, 2003.
14. N. Pisanti, M. Crochemore, R. Grossi, and M.-F. Sagot, A comparative study ofbases for motif inference, In String Algorithmics, KCL publications, 2004.
15. T. Uno, Two general methods to reduce delay and change of enumeration algorithms, NII Technical Report, NII-2003-004E, April 2003.
16. T. Uno, T. Asai, Y. Uchida, H. Arimura, An efficient algorithm for enumeratingclosed patterns in transaction databases, In Proc. DS’04, LNAI 3245, 16-30, 2004.
17. L. G. Valiant, The complexity of computing the permanent, Theoretical Computer
Science 8, 189-201, 1979.
18. X. Yan, J. Han, CloseGraph: mining closed frequent graph patterns, In
Proc. SIGKDD’03, 2003.