Discovering Most Classificatory Patterns for
Very Expressive Pattern Classes
Masayuki Takeda1,2 , Shunsuke Inenaga1,2, Hideo Bannai3 ,Ayumi Shinohara1,2, and Setsuo Arikawa1
1

Department of Informatics, Kyushu University 33, Fukuoka 812-8581, Japan
2
PRESTO, Japan Science and Technology Corporation (JST){takeda, s-ine, ayumi, arikawa}@i.kyushu-u.ac.jp3
Human Genome Center, University of Tokyo, Tokyo 108-8639, Japanbannai@ims.u-tokyo.ac.jp

Abstract. The classiﬁcatory power of a pattern is measured by how
well it separates two given sets of strings. This paper gives practicalalgorithms to ﬁnd the fixed/variable-length-don’t-care pattern (FVLDC
pattern) and approximate FVLDC pattern which are most classiﬁcatory
for two given string sets. We also present algorithms to discover the best
window-accumulated FVLDC pattern and window-accumulated approximate FVLDC pattern. All of our new algorithms run in practical amountof time by means of suitable pruning heuristics and fast pattern matching
techniques.

1

Introduction

String pattern discovery centers in the recent trend of knowledge discovery fromcomputational datasets, since such data are usually stored as strings. Especially,
the optimization problem of ﬁnding a pattern that most frequently appears inthe set of positive examples and least frequently in the set of negative examples,is of great importance. To obtain useful knowledge from given datasets, we beganwith the possibly most basic and simple pattern class, the substring pattern class(as known to be the work of BONSAI [8]), for which the problem can be solved inlinear time [3]. In many applications, however, it is necessary to consider a more
ﬂexible and expressive pattern class, for example in the ﬁeld of bioinformatics,
since biological functions are retained between sequences even if they are slightly
diﬀerent. In fact, the function may be dependent on two regions which are somedistance apart in the sequence, but are close in the three dimensional structurethat the sequence assumes. To this end, we considered the subsequence patternclass [3], and then the variable-length-don’t-care pattern class (VLDC patternclass) [5]. An example of a VLDC pattern is a  abb with a, b ∈ Σ, where thevariable length don’t care symbol  matches any string. The VLDC pattern classis a generalization of the substring and subsequence pattern classes.
In this paper, we further consider mismatches on constant segments of VLDC
patters. Firstly, we consider replacing a character with a ﬁxed length don’t caresymbol ◦ that matches any single character. It yields a pattern such as a 

a ◦ b for the running example. Such a pattern is called a ﬁxed/variable-lengthdon’t-care pattern (FVLDC pattern), and its class is named the FVLDC patternclass. Pursuing a pattern class of more expressive power, we secondly apply theapproximate matching measure to constant segments of FVLDC patterns. An
approximate FVLDC pattern is a pair q, k where q is an FVLDC pattern andk is a threshold for the number of mismatches in the constant segments of q.
The approximate FVLDC pattern class no doubt has a great expressive
power, but in the meantime, it includes quite many patterns without a classiﬁcatory power in the sense of being too general and matching even most negative
examples. Typically, an approximate FVLDC pattern could match almost alllong texts over a small alphabet. The same problem happens to the subsequence
pattern class for the ﬁrst place, but its window-accumulated version called theepisode pattern class has overcome this diﬃculty [4]. This paper considers thewindow-accumulated FVLDC pattern class as well as the window-accumulated
approximate FVLDC pattern class. We address that not only do they possess aremarkable expressive power, but also include many patterns with a very goodclassiﬁcatory power.
The main result of this paper consists in new practical algorithms to ﬁnd
a best pattern that separates two given string datasets, for all of the FVLDC
pattern class, approximate FVLDC pattern class, window-accumulated FVLDC
pattern class, and window-accumulated approximate FVLDC pattern class. Eachalgorithm runs in reasonable amount of time, due to the beneﬁt of suitable pruning heuristics and pattern matching techniques. Interested readers are guided
into reading our previous work [3–5] for the overall idea of our project, andtechnical report [9] for more detail of this work.

2

Preliminaries

Let N be the set of non-negative integers. Let Σ be a ﬁnite alphabet. An elementof Σ ∗ is called a string. The length of a string w is the number of characters in
w and denoted by |w|. The empty string is denoted by ε, that is, |ε| = 0. Strings
x, y, and z are said to be a preﬁx, substring, and suﬃx of string w = xyz,
respectively. The substring of a string w that begins at position i and ends at
position j is denoted by w[i : j] for 1 ≤ i ≤ j ≤ |w|. For convenience, letw[i : j] = ε for j < i. The reversal of a string w is denoted by wR . For a set
S ⊆ Σ ∗ of strings, the number of strings in S is denoted by |S| and the total
length of strings in S is denoted by S.
Let  be a special symbol called the variable length don’t care matching any
string in Σ ∗ . A string over Σ ∪ {} is a variable-length-don’t-care pattern (VLDC
pattern in short). For example, aabba is a VLDC pattern with a, b ∈ Σ. We
say a VLDC pattern q matches a string w if w can be obtained by replacing ’s
in q with some strings. In the running example, the VLDC pattern aabba
matches string abababbbaa with the ’s replaced by ab, b, b and a, respectively.
The size of p, denoted by size(p), is the length of p excluding all ’s. Thus,size(p) = 5 and |p| = 9 for p = a  ab  ba. We remark that size(p) is theminimum length of the strings p matches.
A pattern class over Σ is a pair (Π, L) consisting of a set Π of descriptions
over some ﬁnite alphabet, called patterns, and a function L that maps a patternπ ∈ Π to its language L(π) ⊆ Σ ∗ . A pattern π ∈ Π is said to match a stringw ∈ Σ ∗ if w belongs to the language L(π).
∗∗
Let good be a function from Π × 2Σ × 2Σ to the real numbers. The problem
we consider is: Given two sets S, T ⊆ Σ ∗ of strings, ﬁnd a pattern π ∈ Π thatmaximizes the score good (π, S, T ). Intuitively, the score good(π, S, T ) expresses
the “goodness” of π in the sense of distinguishing S from T . The deﬁnition ofgood varies with applications. For example, the χ2 values, entropy information
gain, and Gini index are often used. Essentially, these statistical measures aredeﬁned by the number of strings that satisfy the rule speciﬁed by π. Any of theabove-mentioned measures can be expressed by the following form:
good(π, S, T ) = f (xπ , yπ , |S|, |T |),where xπ = |S ∩ L(π)| and yπ = |T ∩ L(π)|.
When S and T are ﬁxed, xmax = |S| and ymax = |T | are regarded as constants.
On this assumption, we abbreviate the notation of the function to f (x, y). In thesequel, we assume that f is conic [3–5] and can be evaluated in constant time.
Let F (x, y) = max{f (x, y), f (x, 0), f (0, y), f (0, 0)}. The following lemma derives
from the conicality of function f , on which our pruning heuristics are based.
Lemma 1 ([3]). For any (x, y), (x , y  ) ∈ [0, xmax ] × [0, ymax ], if x ≤ x andy ≤ y  , then f (x, y) ≤ F (x , y  ).

3

Allowing Mismatches by Don’t Cares

A VLDC pattern requires that all of its constant segments occur within a stringin the speciﬁed order with variable-length gaps. To obtain a more expressive
pattern class, we ﬁrst introduce the don’t care symbol ◦ that matches any single
character of Σ. We have two purposes: One is to allow mismatches in the constantsegments of a VLDC pattern. The other is to realize a variety of gap symbols.
An s-times repetition of ◦ works as a ﬁxed-length don’t care that matches any
string of length s over Σ. Also, a VLDC  followed by an s-times repetition of◦ expresses a lower-bounded-length gap symbol that matches any string of length
at least s. A string in Π = (Σ ∪ {, ◦})∗ is called a ﬁxed/variable-length don’tcare pattern (an FVLDC pattern), and (Π, L) is the FVLDC pattern class. The
length and the size of an FVLDC pattern are deﬁned similarly to those of a
VLDC pattern, regarding ◦ as a character of Σ.
Definition 1 (Finding best FVLDC pattern according to f ).
Input: Two sets S, T ⊆ Σ ∗ of strings.
Output: An FVLDC pattern p ∈ Π that maximizes the score f (xp , yp ), where
xp = |S ∩ L(p)| and yp = |T ∩ L(p)|.

Note that any FVLDC pattern p of size greater than  matches no strings in
S ∪ T , and thus we have xp = 0 and yp = 0. The possible maximum length of
p is 2size(p) + 1 since we ignore the patterns with two or more consecutive ’s,and therefore we can restrict by 2 + 1 the length of the patterns to be examinedagainst S and T .
Lemma 2 (Search space for best FVLDC pattern). The best FVLDC
pattern for S and T can be found in Π () = {p ∈ Π | |p| ≤ 2 + 1}, where  isthe maximum length of the strings in S ∪ T .
We can prune the search space according to the following lemma.
Lemma 3 (Pruning lemma for FVLDC pattern). Let p be any FVLDC
pattern in Π. Then, f (xpq , ypq ) ≤ F (xp , yp ) for every FVLDC pattern q ∈ Π.
The following is a sub-problem of Deﬁnition 1, which should be solved quickly.
Definition 2 (Counting matched FVLDC patterns).
Input: A set S ⊆ Σ ∗ of strings and an FVLDC pattern p ∈ Π.
Output: The cardinality of the set S ∩ L(p).
The minimum DFA that accepts L(p) for an FVLDC pattern p has an exponential number of states. However, there is a nondeterministic ﬁnite automaton(NFA) with only m + 1 states that accepts the same language. As a practicalsolution, we adopt the bit-parallel simulation to this NFA. We use (m + 1)-bit
integers to simulate in constant time the state transitions in parallel for eachcharacter of the input strings. When m + 1 is not greater than the computer
word length, say 32 or 64, the algorithm runs in O(S) time after O(|p||Σ|)-time
preprocessing for p.

4

Finding Best Approximate FVLDC Patterns

Let (Π, L) be the FVLDC pattern class, and let δ : Σ ∗ × Σ ∗ → N ∪ {∞}be the well-known Hamming distance measure [2]. A pattern p ∈ Π is said toapproximately match a string w within a distance k if there is a string w ∈ L(p)such that δ(w, w ) ≤ k. For any p, k ∈ Π × N , letLδ (p, k) = {w ∈ Σ ∗ | ∃w ∈ L(p) such that δ(w, w ) ≤ k}.
Then, the pair (Π × N , Lδ ) is a new pattern class derived from (Π, L) with δ.
Let us call the elements of Π × N the approximate FVLDC patterns. For a ﬁxedk ∈ N , an ordered pair p, k with p ∈ Π is called a k-approximate FVLDC
pattern.
Definition 3 (Finding best approximate FVLDC pattern according tof ).
Input: Two sets S, T ⊆ Σ ∗ of strings, and a non-negative integer kmax .
Output: An approximate FVLDC pattern π = q, k ∈ Π × [0, kmax ] that maximizes the score f (xπ , yπ ), where xπ = |S ∩ Lδ (π)| and yπ = |T ∩ Lδ (π)|.

We here have to ﬁnd the best combination of a pattern q and an error level k.
Lemma 4 (Search space for best approximate FVLDC pattern). The
best approximate FVLDC pattern for S, T ⊆ Σ ∗ and kmax can be found in Π () ×[0, kmax ], where Π () is the same as in Lemma 2.
We have two pruning techniques for the problem of Deﬁnition 3. The ﬁrst
one is as follows.
Definition 4 (Computing best error level according to f ).
Input: Two sets S, T ⊆ Σ ∗ of strings, an FVLDC pattern q ∈ Π, and a nonnegative integer kmax .
Output: An integer k ∈ [0, kmax ] that maximizes the score f (xπ , yπ ) for π =q, k, where xπ = |S ∩ Lδ (π)| and yπ = |T ∩ Lδ (π)|.
For an FVLDC pattern q ∈ Π and string u ∈ Σ ∗ , we deﬁne the distance
between q and u by Distδ (q, u) = min{δ(w, u) | w ∈ L(q)}. If there is no such w,
let Dist(q, u) = ∞. For q ∈ Π and S ⊆ Σ ∗ , let ∆(q, S) = {Distδ (q, u) | u ∈ S}.
Then, the best error level of a pattern q ∈ Π for given S, T ⊆ Σ ∗ can be foundin the set ∆(q, S ∪ T ) ∩ [0, kmax ].
Lemma 5. For an FVLDC pattern q ∈ Π and string w ∈ Σ ∗ , Distδ (q, w) can
be computed in O(|q||w|) time.
Proof. Directly from the results of Myers and Miller [6], in which regular expressions are treated instead of FVLDC patterns.
Lemma 6 (Pruning lemma 1 for approximate FVLDC pattern). Let p
be any FVLDC pattern in Π and π = p, kmax . Then, f (xτ , yτ ) ≤ F (xπ , yπ ) for
every approximate FVLDC pattern τ = pq, k such that q ∈ Π and k ∈ [0, kmax ].
The second approach for pruning the search space is quite simple. We repeatedly execute a procedure that ﬁnds the best k-approximate FVLDC pattern
p, k for S and T , in increasing order of k = 0, 1, . . . , kmax . It is possible to prune
the search space Π () × {k} by:Lemma 7 (Pruning lemma 2 for approximate FVLDC pattern). Letk ∈ [0, kmax ], p be any FVLDC pattern in Π, and π = p, k. Then, f (xτ , yτ ) ≤F (xπ , yπ ) for every k-approximate FVLDC pattern τ = pq, k with q ∈ Π.
The following is a sub-problem of Deﬁnition 3, which should be solved quickly.
Definition 5 (Counting matched approximate FVLDC patterns).
Input: A set S ⊆ Σ ∗ of strings and an approximate FVLDC pattern p, k.
Output: The cardinality of the set S ∩ Lδ (p, k).
We developed an eﬃcient algorithm to solve the above sub-problem. Although
we omit the detail due to lack of space, it performs the diagonal-wise bit-parallel
simulation (see [7]) of an NFA that recognizes the language Lδ (p, k) of an
approximate FVLDC pattern p, k. The NFA being simulated has (m+1)(k +1)

states (m = size(p)), but (m − k + 1)(k + 1)-bits are enough. If the (m − k +1)(k+1)-bit representation ﬁts in a single computer word, it runs in linear time inS after O(|q||Σ|)-time preprocessing of p, k. The algorithm was inspired by
the work of Baeza-Yates and Navarro [1], which aims an approximate substring
pattern matching where the Levenshtein distance is used as a distance measure δ,
not the Hamming distance. Although their algorithm could be easily extended tothe approximate FVLDC pattern matching if the Levenshtein distance measure
was used, a new development is actually necessary to cope with the Hamming
distance.

5

Extension to Window-Accumulated Patterns

For any pattern class Π, L, we introduce a window whose size (width) limits
the length of a pattern occurrence within a string. A pattern p ∈ Π is said tooccur in a string w within a window of size h if w has a substring of length at
most h the pattern p matches. For any pair p, h in Π × N , letL̂(p, h) = {w ∈ Σ ∗ | p occurs in w within a window of size h},and let L̂(p, ∞) = L(p) for convenience. The pair (Π × N , L̂) is a new patternclass derived from (Π, L). We call the elements of Π ×N the window-accumulated
patterns for (Π, L).
Definition 6 (Finding the best window-accumulated pattern in (Π, L)
according to f ).
Input: Two sets S, T ⊆ Σ ∗ of strings.
Output: A window-accumulated pattern π = q, h ∈ Π × N that maximizes thescore f (xπ , yπ ), where xπ = |S ∩ L̂(π)| and yπ = |T ∩ L̂(π)|.
We stress h is not given beforehand, and hence we have to ﬁnd the best combination of a pattern q and window width h. The search space is thus Π × N , notΠ.
The following is a sub-problem of Deﬁnition 6, which should be solved quickly.
Definition 7 (Computing best window size for (Π, L) according to f ).
Input: Two sets S, T ⊆ Σ ∗ of strings and a pattern q ∈ Π.
Output: An integer h ∈ N that maximizes the score f (xq,h , yq,h ), wherexq,h = |S ∩ L̂(q, h)| and yq,h = |T ∩ L̂(q, h)|.
For a pattern q ∈ Π and for a string u ∈ Σ ∗ , we deﬁne the minimum window
size θ of q for u by θq,u = min{h ∈ N | u ∈ L̂(q, h)}. If there is no such value,let θq,u = ∞. For any q ∈ Π and any S ⊆ Σ ∗ , let Θ(q, S) = {θq,u | u ∈ S}. The
best window size of q ∈ Π for S, T ⊆ Σ ∗ can be found in Θ(q, S ∪ T ).
Lemma 8 (Search space for best window-accumulated pattern). The
best window-accumulated pattern in (Π, L) for S and T can be found in {q, h |q ∈ Π and h ∈ Θ(q, S ∪ T )}.
We emphasize that the above discussion holds for the window-accumulated
version of any pattern class (Π, L). However, the complexity of computing theminimum window size depends on (Π, L).

5.1

Window-Accumulated FVLDC Patterns

This section is devoted to ﬁnding the best window-accumulated FVLDC patternfrom two given sets S, T of strings.
Lemma 9 (Search space for best window-accumulated FVLDC pattern). The best window-accumulated FVLDC pattern for S and T can be foundin {q, h | q ∈ Π () and h ∈ Θ(q, S∪T )}, where Π () is the same as in Lemma 2.
Lemma 10 (Pruning lemma for window-accumulated FVLDC pattern).
Let p be an FVLDC pattern and π = p, ∞. Then, f (xτ , yτ ) ≤ F (xπ , yπ ) for
every window-accumulated FVLDC pattern τ = pq, h such that q ∈ Π andh ∈ N.
Lemma 11. The minimum window size θq,w of an FVLDC pattern q for astring w ∈ Σ ∗ can be computed in O(|q||w|) time.
Proof. By a standard dynamic programming approach.

The dynamic programming method is, however, relatively slow in practice.
An alternative way to solve the problem is to build from a given FVLDC pattern
q two NFAs accepting L(q) and L(q R ), which we call the forward and backward
NFAs, respectively. An occurrence of a pattern q that starts at position i andends at position j of a string w, denoted by (i, j), is said to be minimal if noproper substring of w[i : j] contains an occurrence of q. Let (i1 , j1 ), · · · , (ir , jr ) be
the sequence of the minimal occurrences of q in w satisfying i1 < · · · < ir . We run
the forward NFA over w starting at the ﬁrst character to determine the value j1 .
When j1 is found, we use the backward NFA going backward starting at the j1 -th
character in order to determine the value i1 . After i1 is determined, we again use
the forward NFA going forward starting at the (i1 + 1)-th character for ﬁnding
the value j2 . Continuing in this fashion, we can determine all of the minimal
occurrences of q in w. The minimal window size is obtained as the minimum
among the widths of the minimal occurrences. We simulate the two NFAs over agiven string basing on the bit-parallelism mentioned in Section 3 when size(q)+1
does not exceed the computer word length. Although the running time of thismethod is O(r|w|) = O(|w|2 ) in the worst case, it shows a good performancecompared with the above-mentioned dynamic programming based method, since
the number r of minimal occurrences of q is not so large in reality.
5.2

Window-Accumulated Approximate FVLDC Patterns

The search space for the best window-accumulated approximate FVLDC patternis Π × [0, kmax ] × N . A reasonable approach would be to compute the best
pattern in Π × {k} × N for each k = 0, 1, . . . , kmax , and then choose the best one
among them. We have only to consider ﬁnding the best window-accumulated
k-approximate FVLDC pattern for a ﬁxed k.

Lemma 12 (Search space for best window-accumulated k-approximate
FVLDC pattern). Let k be a ﬁxed non-negative integer. The best windowaccumulated k-approximate FVLDC pattern for S, T can be found in {q, k, h |q ∈ Π () and h ∈ Θ(q, k, S ∪ T )}, where Π () is the same as in Lemma 2.
Lemma 13 (Pruning lemma for window-accumulated k-approximate
FVLDC pattern). Let k be a ﬁxed non-negative integer. Let p be an FVLDC
pattern, and let π = p, k, ∞. Then, f (xτ , yτ ) ≤ F (xπ , yπ ) for every windowaccumulated k-approximate FVLDC pattern τ = pq, k, h such that q ∈ Π andh ∈ N.
Lemma 14. Let k be a ﬁxed non-negative integer. The minimum window size
θq,w of a k-approximate FVLDC pattern q, k for a string w ∈ Σ ∗ can be computed in O(k|q||w|) time.
Proof. A straightforward extension of the dynamic programming method forLemma 11.

In practice, we again adopt the two NFAs based approach. It is possible tosimulate the NFA for an approximate FVLDC pattern q, k over a string w
using (m − k + 1)(k + 1)-bit integers in linear time, where m = size(q). The
running time is therefore O(r|w|) if (m − k + 1)(k + 1) does not exceed thecomputer word length.

References
1. R. Baeza-Yates and G. Navarro. Faster approximate string matching. Algorithmica,
23(2):127–158, 1999.
2. D. Gusﬁeld. Algorithms on Strings, Trees, and Sequences. Cambridge University
Press, New York, 1997.
3. M. Hirao, H. Hoshino, A. Shinohara, M. Takeda, and S. Arikawa. A practicalalgorithm to ﬁnd the best subsequence patterns. In Proc. Discovery Science 2000,
volume 1967 of LNAI, pages 141–154. Springer-Verlag, 2000.
4. M. Hirao, S. Inenaga, A. Shinohara, M. Takeda, and S. Arikawa. A practical algorithm to ﬁnd the best episode patterns. In Proc. Discovery Science 2001, volume2226 of LNAI, pages 435–440. Springer-Verlag, 2001.
5. S. Inenaga, H. Bannai, A. Shinohara, M. Takeda, and S. Arikawa. Discovering best
variable-length-don’t-care patterns. In Proc. Discovery Science 2002, volume 2534
of LNCS, pages 86–97. Springer-Verlag, 2002.
6. E. W. Myers and W. Miller. Approximate matching of regular expressions. Bulletinof Mathematical Biology, 51(1):5–37, 1989.
7. G. Navarro and M. Raﬃnot. Flexible pattern matching in strings: Practical on-line
search algorithms for texts and biological sequences. Cambridge University Press,
Cambridge, 2002.
8. S. Shimozono, A. Shinohara, T. Shinohara, S. Miyano, S. Kuhara, and S. Arikawa.
Knowledge acquisition from amino acid sequences by machine learning system BONSAI. Trans. of Information Processing Society of Japan, 35(10):2009–2018, 1994.
9. M. Takeda, S. Inenaga, H. Bannai, A. Shinohara, and S. Arikawa. Discovering
most classiﬁcatory patterns for very expressive pattern classes. Technical Report
DOI-TR-CS-219, Department of Informatics, Kyushu University, 2003.