Discovering Best Variable-Length-Don’t-Care
Patterns
Shunsuke Inenaga1 , Hideo Bannai3 , Ayumi Shinohara1,2 ,Masayuki Takeda1,2, and Setsuo Arikawa1
1

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

Abstract. A variable-length-don’t-care pattern (VLDC pattern) is an element of set Π = (Σ ∪ {})∗ , where Σ is an alphabet and  is a wildcard
matching any string in Σ ∗ . Given two sets of strings, we consider the
problem of ﬁnding the VLDC pattern that is the most common to one,and the least common to the other. We present a practical algorithm
to ﬁnd such best VLDC patterns exactly, powerfully sped up by pruning heuristics. We introduce two versions of our algorithm: one employsa pattern matching machine (PMM) whereas the other does an index
structure called the Wildcard Directed Acyclic Word Graph (WDAWG).
In addition, we consider a more generalized problem of ﬁnding the bestpair q, k, where k is the window size that speciﬁes the length of an occurrence of the VLDC pattern q matching a string w. We present threealgorithms solving this problem with pruning heuristics, using the dynamic programming (DP), PMMs and WDAWGs, respectively. Although
the two problems are NP-hard, we experimentally show that our algorithms run remarkably fast.

1

Introduction

A vast amount of data is available today, and discovering useful rules from thosedata is quite important. Very commonly, information is stored and manipulated
as strings. In the context of strings, rules are patterns. Given two sets of strings,
often referred to as positive examples and negative examples, it is desired to ﬁnd
the pattern that is the most common to the former and the least common to thelatter. This is a critical task in Discovery Science as well as in Machine Learning.
A string y is said to be a substring of a string w if there exist strings x, z ∈ Σ ∗such that w = xyz. Substring patterns are possibly the most basic patterns to
be used for the separation of two sets S, T of strings. Hirao et al. [8] statedthat such best substrings can be found in linear time by constructing the suﬃx
tree for S ∪ T [12, 21, 7]. They also considered subsequence patterns as rules
for separation. A subsequence pattern p is said to match a string w if p canbe obtained by removing zero or more characters from w [2]. Against the fact

that ﬁnding the best subsequence patterns to separate given two sets of strings
is NP-hard, they proposed an algorithm to solve the problem with practicallyreasonable performance. More recently, an eﬃcient algorithm to discover thebest episode patterns was proposed in [9]. An episode pattern p, k, where p isa string and k is an integer, is said to match a string w if p is a subsequence ofa substring u of w with |u| ≤ k [14, 6, 20]. The problem to ﬁnd the best episodepatterns is also known to be NP-hard.
In this paper, we focus on a pattern containing a wildcard that matches any
string. The wildcard is called a variable length don’t care and is denoted by .
A variable-length-don’t-care pattern (VLDC pattern) is an element of Π = (Σ ∪{ })∗ , and is also sometimes called a regular pattern as in [19]. When a, b ∈ Σ,ab bb ba is an example of a VLDC pattern and, for instance, matches string
abbbbaaaba with the ﬁrst and second ’s replaced by b and aaa, respectively. The
language L(q) of a pattern q ∈ Π is the set of strings obtained by replacing ’s
in q with arbitrary strings. Namely, L(ab bb ba) = {abubbvba | u, v ∈ Σ ∗ }. The
class of this language corresponds to a class of the pattern languages proposedby Angluin [1]. VLDC patterns are generalization of substring patterns andsubsequence patterns. For instance, consider a pattern string abc ∈ Σ ∗ . The
substring matching problem corresponding to the pattern is given by the VLDC
pattern abc . Also, the VLDC pattern a b c leads to the subsequence patternmatching problem.
This paper is devoted to introducing a practical algorithm to discover thebest VLDC pattern to distinguish two given sets S, T of strings. To speed up
the algorithm, ﬁrstly we restrict the search space by means of pruning heuristics
inspired by Morishita and Sese [16]. Secondly, we accelerate the matching phaseof the algorithm in two ways, as follows: In [11], we introduced an index structure
called the Wildcard Directed Acyclic Word Graph (WDAWG). The WDAWG fora text string w recognizes all possible VLDC patterns matching w, and thus
enables us to examine whether a given VLDC pattern q matches w in O(|q|)
time. More recently, a space-economical version of its construction algorithm
was presented in [10]. We use WDAWGs for quick matching of VLDC patterns.
Another approach is to preprocess a given VLDC pattern q, building a DFA
accepting L(q). We use it as a pattern matching machine (PMM) which runs
over a text string w and determines whether or not q matches w in O(|w|) time.
We furthermore propose a generalization of the VLDC pattern matchingproblem. That is, we introduce an integer k called the window size which speciﬁes
the length of an occurrence of a VLDC pattern that matches w ∈ Σ ∗ . The
introduction of k leads to the generalization of the episode patterns as well.
Specifying the length of an occurrence of a VLDC pattern is of great signiﬁcanceespecially when classifying long strings over a small alphabet, since a short VLDC
pattern surely matches most long strings. Therefore, for example, when two setsof biological sequences are given to be separated, this approach is adequate andpromising. Pruning heuristic to speed up our algorithm ﬁnding the best pairq, k is also presented. We propose three approaches eﬀective in computing thebest pair, using the dynamic programming, PMMs, and WDAWGs, respectively.

We declare that this work generalizes and outperforms the ones accomplishedin [8, 9], since it is capable of discovering more advanced and useful patterns. In
fact, we show some experimental results that convince us of the accuracy of ouralgorithms as well as their fast performances. Moreover, we are now installing
our algorithms into the core of the decision tree generator in BONSAI [17], apowerful machine discovery system.
We here only give basic ideas for our pruning heuristics, that are rather
straightforward extensions of those developed in our previous work [8, 9]. Interested readers are invited to refer to our survey report [18].

2Finding the Best Patterns to Separate Sets of Strings

2.1

Notation

Let N be the set of integers. Let Σ be a ﬁnite alphabet. An element of Σ ∗ iscalled a string. The length of a string w is denoted by |w|. The empty string isdenoted 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, let w[i : j] = ε for j < i. The reversal of a string w is denoted
by wR , that is, wR = w[n]w[n − 1] . . . w[1] where n = |w|.
For a set S ⊆ Σ ∗ of strings, the number of strings in S is denoted by |S| andthe total length of strings in S is denoted by S .
Let Π = (Σ ∪ { })∗ , where is a variable length don’t care matching any
string in Σ ∗ . An element q ∈ Π is a variable-length-don’t-care pattern (VLDC
pattern). For example, a ab ba 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 a ab bamatches string abababbbaa with the ’s replaced by ab, b, b and a, respectively.
For any q ∈ Π, |q| denotes the sum of numbers of characters and ’s in q.
2.2

Finding the Best VLDC Patterns

We write as q
elements in Π.

u if u can be obtained by replacing ’s in q with arbitrary

Definition 1. For a VLDC pattern q ∈ Π, we deﬁne L(q) by
L(q) = {w ∈ Σ ∗ | qw}.

According to the above deﬁnition, we have the following lemma.
Lemma 1. For any q, u ∈ Π, if qu, then L(q) ⊇ L(u).
∗∗Let good be a function from Σ ∗ × 2Σ × 2Σ to the set of real numbers. In
what follows, we formulate the problem to solve.

Definition 2 (Finding the best VLDC pattern according to good ).
Input: Two sets S, T ⊆ Σ ∗ of strings.
Output: A VLDC pattern q ∈ Π that maximizes the score of good (q, S, T ).
Intuitively, the score of good(q, S, T ) expresses the “goodness” of q in the senseof distinguishing S from T . The deﬁnition of good varies with applications. For
examples, the χ2 values, entropy information gain, and gini index can be used.
Essentially, these statistical measures are deﬁned by the numbers of strings thatsatisfy the rule speciﬁed by q. Any of the above-mentioned measures can be
expressed by the following form:
good (q, S, T ) = f (xq , yq , |S|, |T |), where
xq = |S ∩ L(q)|,yq = |T ∩ L(q)|.
When S and T are ﬁxed, |S| and |T | are regarded as constants. On this assumption, we abbreviate the notation of the function to f (x, y) in the sequel.
We say that a function f from [0, xmax ] × [0, ymax ] to real numbers is conic if– for any 0 ≤ y ≤ ymax , there exists an x1 such that• f (x, y) ≥ f (x , y) for any 0 ≤ x < x ≤ x1 , and• f (x, y) ≤ f (x , y) for any x1 ≤ x < x ≤ xmax .
– for any 0 ≤ x ≤ xmax , there exists a y1 such that• f (x, y) ≥ f (x, y  ) for any 0 ≤ y < y  ≤ y1 , and• f (x, y) ≤ f (x, y  ) for any y1 ≤ y < y  ≤ ymax .
In the sequel, we assume that f is conic and can be evaluated in constant time.
The optimization problem to be tackled follows.
Definition 3 (Finding the best VLDC pattern according to f ).
Input: Two sets S, T ⊆ Σ ∗ of strings.
Output: A VLDC pattern q ∈ Π that maximizes the score of f (xq , yq ), where
xq = |S ∩ L(q)| and yq = |T ∩ L(q)|.
The problem is known to be NP-hard [15], and thus we essentially have exponentially many candidates. Therefor, we reduce the number of candidates by using
the pruning heuristic inspired by Morishita and Sese [16].
The following lemma derives from the conicality of function f .
Lemma 2 ([8]). For any 0 ≤ x < x ≤ xmax and 0 ≤ y < y  ≤ ymax , we havef (x, y) ≤ max{f (x , y  ), f (x , 0), f (0, y  ), f (0, 0)}.
By Lemma 1 and Lemma 2, we have the next lemma, basing on which we
can perform the pruning heuristic to speed up our algorithm.
Lemma 3. For any two VLDC patterns q, u ∈ Π, if q
max{f (xq , yq ), f (xq , 0), f (0, yq ), f (0, 0)}.

u, then f (xu , yu ) ≤2.3

Finding the Best VLDC Patterns within a Window

We here consider a natural extension of the problem mentioned previously. We
introduce an integer k called the window size. Let q ∈ Π and q[i], q[j] be theﬁrst and last characters in q that are not , respectively, where 1 ≤ i ≤ j ≤ |q|.
If q matches w ∈ Σ ∗ , let w[i ], w[j  ] be characters to which q[i] and q[j] cancorrespond, respectively, where 1 ≤ i ≤ j  ≤ |w|. (Note that we might havemore than one combination of i and j  .) If there exists a pair i , j  satisfyingj  − i < k, we say that q occurs w within a window of size k. Then the pairq, k is said to match the string w.
Definition 4. For a pair q, k with q ∈ Π and k ∈ N , we deﬁne L (q, k) byL (q, k) = {w ∈ Σ ∗ | q, k matches w}.
According to the above deﬁnition, we have the following lemma.
Lemma 4. For any q, k and p, j with q, p ∈ Π and k, j ∈ N , if q
j ≥ k, then L (q, k) ⊇ L (p, j).

p and

The problem to be tackled is formalized as follows.
Definition 5 (Finding the best VLDC pattern and window size according to f ).
Input: Two sets S, T ⊆ Σ ∗ of strings.
Output: A pair q, k with q ∈ Π and k ∈ N that maximizes the score off (xq,k , yq,k ), where xq,k = |S ∩ L (q, k)| and yq,k = |T ∩ L (q, k)|.
We stress that the value of k is not given beforehand, i.e., we compute not only q
but also k with which the score of function f is maximum. Therefore, the search
space of this problem is Π × N , while that of the problem in Deﬁnition 3 is Π.
We remark that this problem is also NP-hard.
By Lemma 4 and Lemma 2, we achieve the following lemma that plays a keyrole for the heuristic to prune the search tree.
Lemma 5. For any q, k and p, j with q, u ∈ Π and k, j ∈ N , if q u andj ≥ k, f (xp,j , yp,j ) ≤ max{f (xq,k , yq,k ), f (xq,k , 0), f (0, yq,k ), f (0, 0)}.

3

Eﬃcient Match of VLDC Patterns

Definition 6 (Counting the matched VLDC patterns).
Input: A set S ⊆ Σ ∗ of strings.
Query: A VLDC pattern q ∈ Π.
Answer: The cardinality of set S ∩ L(q).
This is a sub-problem of the one given in Deﬁnition 3. It must be answered as
fast as possible, since we are given quite many VLDC patterns as queries. Here,
we utilize two practical methods which allows us to answer the problem quickly.

a
b

a

b

a

b

b
a

b
b
a

a
b

a
a
b

b

Fig. 1. WDAWG(w) where w = abbab.

3.1

Using a DFA for a VLDC pattern

Our ﬁrst idea is to use a deterministic ﬁnite-state automaton (DFA) for a pattern.
Given a VLDC pattern q ∈ Π, we construct a DFA that accepts L(q) and use
it as a pattern matching machine (PMM) which runs over text strings in S. For
any q ∈ Π, a DFA can be constructed in O(|q|) time.
Lemma 6. Let S ⊆ Σ ∗ and q ∈ Π. Then |S ∩ L(q)| can be computed in O(|q|)
preprocessing time and in O( S ) running time.
3.2

Using Wildcard Directed Acyclic Word Graphs

The second approach is to use an index structure for a text string w ∈ S thatrecognizes all VLDC patterns matching w.
The Directed Acyclic Word Graph (DAWG) is a classical, textbook index
structure [5], invented by Blumer et al. in [3]. The DAWG of a string w ∈ Σ ∗ isdenoted by DAWG(w), and is known to be the smallest deterministic automatonthat recognizes all suﬃxes of w [4]. By means of DAWG(w), we can examine
whether or not a given pattern p ∈ Σ ∗ is a substring of w in O(|p|) time.
Recently, we introduced Minimum All-Suﬃxes Directed Acyclic Word Graphs(MASDAWGs) [11]. The MASDAWG of a string w ∈ Σ ∗ , which is denoted by
MASDAWG(w), is the minimization of the collection of the DAWGs for all
suﬃxes of w. More precisely, MASDAWG(w) is the smallest automaton with|w| + 1 initial nodes, in which the directed acyclic graph induced by all reachable
nodes from the k-th initial node conforms with the DAWG of the k-th suﬃx ofw.
Several important applications of MASDAWGs were given in [11], one ofwhich corresponds to a signiﬁcantly time-eﬃcient solution to the VLDC pattern matching problem. Namely, a variant of MASDAWG(w), called Wildcard
DAWG (WDAWG) of w and denoted by WDAWG(w), was introduced in [11].
WDAWG(w) is the smallest automaton that accepts all VLDC patterns matching w. WDAWG(w) with w = abbab is displayed in Fig. 1.

Theorem 1. When |Σ| ≥ 2, the number of nodes of WDAWG(w) for a string
w is Θ(|w|2 ). It is Θ(|w|) for a unary alphabet.
Theorem 2. For any string w ∈ Σ ∗ , WDAWG(w) can be constructed in time
linear in its size.
For all strings in S ⊆ Σ ∗ , we construct WDAWGs. Then we obtain thefollowing lemma that is a counterpart of Lemma 6.
Lemma 7. Let S ⊆ Σ ∗ and q ∈ Π. Let N = w∈S |w|2 . Then |S ∩ L(q)| canbe computed in O(N ) preprocessing time and in O(|q|·|S|) running time.
In spite of the quadratic space requirement of WDAWGs, it is meaningful toconstruct them because of the following reasons. Assume that, for a string w in
S, a VLDC pattern q has been recognized by WDAWG(w). We then memorize
the node at which q was accepted. It allows us a rapid search of any VLDC
pattern qr with r ∈ Π, since we only need to move |r| transitions from thememorized node. Therefore, WDAWGs are signiﬁcantly useful especially in oursituation. Moreover, WDAWGs are also helpful for pruning the search tree. Onceknowing that a VLDC pattern q does not match any string in S by using the
WDAWGs, we need not consider any u ∈ Π such that q u.

4

How to Compute the Best Window Size

Definition 7 (Computing the best window size according to f ).
Input: Two sets S, T ⊆ Σ ∗ of strings and a VLDC pattern q ∈ Π.
Output: An integer k ∈ N that maximizes the score of f (xq,k , yq,k ), wherexq,k = |S ∩ L (q, k)| and yq,k = |T ∩ L (q, k)|.
This is a sub-problem of the one in Deﬁnition 5, where a VLDC pattern is given
beforehand.
Let be the length of the longest string in S ∪ T . A short consideration
reveals that, as candidates for k, we only have to consider the values from |q|
up to , which results in a rather straightforward solution. In addition to that,
we give a more eﬃcient computation method, whose basic principle originatesin [9].
For a string u ∈ Σ ∗ and a VLDC pattern q ∈ Π, we deﬁne the thresholdvalue θ of q for u by
θu,q = min{k ∈ N | u ∈ L (q, k)}.
/ L (q, k) for any k < θ
If there is no such value, let θu,q = ∞. Note that u ∈and u ∈ L (q, k) for any k ≥ θ. The set of threshold values for q ∈ Π withrespect to S ⊆ Σ ∗ is deﬁned as ΘS,q = {θu,q | u ∈ S}.
A key observation is that the best window size for given S, T ⊆ Σ ∗ and a
VLDC pattern q ∈ Π can be found in set ΘS,q ∪ ΘT,q without loss of generality.
Thus we can restrict the search space for the best window size to ΘS,q ∪ ΘT,q .
It is therefore important to quickly solve the following sub-problem.

Definition 8 (Computing the minimum window size).
Input: A string w ∈ Σ ∗ and a VLDC pattern q ∈ Π.
Output: The threshold value θw,q .
We here show our three approaches to eﬃciently solve the above sub-problem.
The ﬁrst is to adopt the standard dynamic programming method. For a stringw ∈ Σ ∗ with |w| = n and a pattern q ∈ Π with |q| = m, let dij be the lengthof the shortest suﬃx of w[1 : j] that q[1 : i] matches, where 0 ≤ i ≤ m and
0 ≤ j ≤ n. We can compute all dij ’s in O(mn) time, basing on the following
recurrences: d00 = 0,d0j = 0 if q[1] =for j ≥ 1,
∞ otherwise
for i ≥ 1, anddi0 = di−1,0 if q[1] =∞otherwise
min{di−1,j−1 +1, di,j−1 +1, di−1,j } if q[i] =dij = di−1,j−1 +1
if q[i] = w[j] for i ≥ 1 and j ≥ 1.
∞otherwise
min1≤j≤n {dmj } if q[m] =Then θw,q =otherwise.
dmn
Remark that if the row dmj (1 ≤ j ≤ n) is memorized, it will save the computation time for any pattern qr with r ∈ Π.
The second approach is to preprocess a given VLDC pattern q ∈ Π. We
construct a DFA accepting L(q) and another DFA for L(q R ), and utilize them as
PMMs running over a given string w ∈ Σ ∗ . If q[1] = (q[m] = , respectively),
we have only to compute the shortest preﬁx (suﬃx, respectively) of w that q
matches and return its length. We now consider the case q[1] = q[m] = .
Firstly, we run the DFA for L(q) over w. Suppose that q is recognized between
positions i and j in w, where 1 ≤ i < j ≤ |w| and j − i > |q|. A delicate pointis that it is unsure whether w[i : j] corresponds to the shortest occurrence ofq ending at position j. How can we ﬁnd the shortest one? It can be found byrunning the DFA for L(q R ) backward, over w from position j. Assume that q R isrecognized at position k, where i ≤ k < j − |q|. Then w[k : j] corresponds to theshortest occurrence of q ending at position j. After that, we resume the runningof the DFA of L(q) from position k + 1, and continue the above procedure until
encountering position |w|. The pair of positions of the shortest distance gives thethreshold value θw,q . This method is feasible in O(m) preprocessing time and inO(mn) running time, where m = |q| and n = |w|.
The third approach is to preprocess a text string w ∈ Σ ∗ , i.e., we construct
WDAWG(w) and WDAWG(wR ). For any w ∈ Σ ∗ , each and every node of
WDAWG(w) can be associated with a position in w [11]. Thus we can perform
a procedure similar to the second approach above, which enables us to ﬁnd thethreshold value θw,q . This approach takes us O(n) preprocessing time and O(mn)running time, where m = |q| and n = |w|.
As a result, we obtain the following:Lemma 8. Let w ∈ Σ ∗ and q ∈ Π with |w| = n and |q| = m. The thresholdvalue θw,q can be computed in O(mn) running time.

5

Computational Experiments

The algorithms were implemented in the Objective Caml Language. All calculations were performed on a Desktop PC with dual Xeon 2.2GHz CPU (though
our algorithms only utilize single CPU) with 1GB of main memory running Debian Linux. In all the experiments, the entropy information gain is used as thescore for which the search is conducted.
5.1

Artificial Data

We ﬁrst tested our algorithms on an artiﬁcial dataset. The datasets were createdas follows: The alphabet was set to Σ = {a, b, c, d}. We then randomly generate
strings over Σ of length l. We created 3 types of datasets: 1) a completely random
set, 2) a set where a randomly chosen VLDC pattern ccd a ddad is embeddedin the positive examples, and 3) a set where a pair of a VLDC pattern and awindow size  ccd a ddad , 19 is embedded in the positive examples. In 2)
and 3), a randomly generated string is used as a positive example if the patternmatches it, and used as a negative example otherwise, until both positive andnegative set sizes are n. Examples for which the set size exceeds n are discarded.
Fig. 2 shows the execution times for diﬀerent l and n, for the completely
random dataset. We can see that the execution time grows linearly in n and l as
expected, although the eﬀect of pruning seems to take over for VLDC patterns
in the left graph, when the length of each sequence is long. Searching for VLDC
patterns and window sizes using dynamic programming with row memoization,
does not perform very well.
Fig. 3 shows the execution times for diﬀerent maximum lengths of VLDC
patterns to look for, for the 3 datasets (The length of a VLDC pattern is deﬁned
as the length of the pattern representation, excluding any ’s on the ends). We
can see that the execution time grows exponentially as we increase the maximum
pattern length searched for, until the pruning takes eﬀect. The lower left graphin Fig. 3 shows the eﬀect of performance of an exhaustive search, run on thecompletely random dataset, compared to searches with the branch and boundpruning for the diﬀerent datasets. The pruning is more eﬀective when it is more
likely to have a good solution.
5.2

Real Data

To show the usefulness of VLDC patterns and windows, we also tested ouralgorithms on actual protein sequences. We use the data available at http://www.cbs.dtu.dk/services/TargetP/, which consists of protein sequences
which are known to contain protein sorting signals, that is, (in many cases)a short amino acid sequence segment which holds the information which enables

Execution time for 100 positive/100 negative completely random data (maxlen = 8)350

Execution time for completely random data of length 100 (maxlen = 8)350

Substring
VLDC: PMM
VLDC: WDAWG
VLDC: WDAWG-sm
VLDC in Window: PMM
VLDC in Window: DP-rm

300

300

250

Time (secs)

Time (secs)

250

200

150

200

150

100

100

50

50

0

Substring
VLDC: PMM
VLDC: WDAWG
VLDC: WDAWG-sm
VLDC in Window: PMM
VLDC in Window: DP-rm

50

100

150

200
250
300
350
Length of each string in positive/negative set

400

450

500

0

50

100

150

200
250
300
350
# of strings in each positive/negative set

400

450

500

Fig. 2. Execution time (in seconds) for artiﬁcial data for: diﬀerent lengths of the examples (left) diﬀerent number of examples in each positive/negative set (right). The
maximum length of patterns to be searched for is set to 8. WDAWG-sm is matching
using the WDAWG with state memoization. DP-rm is matching using the dynamic
programming table with row memoization. Only one point is shown for DP-rm in theleft graph, since a greater size caused memory swapping, and the computation was not
likely to end in a reasonable amount of time.

the protein to be carried to speciﬁed compartments inside the cell. The dataset
for plant proteins consisted of: 269 sequences with signal peptide (SP), 368 sequences with mitocondrial targeting peptide (mTP), 141 sequences with chloroplast transit peptide (cTP), and 162 “Other” sequences. The average length of
the sequences was around 419, and the alphabet is the set of 20 amino acids.
Using the signal peptides as positive examples, and all others as negative
examples, we searched for the best pair p, k with maximum length of 10
using PMMs. To limit the alphabet size, we classify the amino acids into 3classes {0, 1, 2}, according to the hydropathy index [13]. The most hydrophobic amino acids {A, M, C, F, L, V, I} (hydropathy ≥ 0.0) are converted to 0,{P,Y,W,S,T,G} (−3.0 ≤ hydropathy < 0.0 ) to 1, and {R, K, D, E, N, Q, H}(hydropathy < −3.0 ) to 2. We obtained the pair 0 00 00000 , 26, which occurs in 213/269 = 79.2% of the sequences with SP, and 26/671 = 3.9% of theother sequences. The calculation took exactly 50 minutes. This pattern can beinterpreted as capturing the well known hydrophobic h-region of SP [22]. Also,
the VLDC pattern suggests that the match occurs in the ﬁrst 26 amino acidresidues of the protein, which is natural since SP, mTP, cTP are known to be Nterminal sorting signals, that is, they are known to appear near the head of theprotein sequence. A best substring search quickly ﬁnds the pattern 00000001
in 36 seconds, but only gives us a classiﬁer that matches 152/269 = 56.51% of
the SP sequences, and 41/671 = 6.11% of the others.
For another example, we use the mTP set as positive examples, and the
SP and Other sets as negative examples. This time, we convert the alphabet
according to the net charge of the amino acid. Amino acids {D, E} (negative
charge) are converted to 0, {K, R} (positive charge) to 1, and the rest {A, L, N,
M, F, C, P, Q, S, T, G, W, H, Y, I, V} to 2. The calculation took about 21 minutes
and we obtain the pair 2 1 1 2221 , 28 which occurs in 334/368 = 90.76% ofExecution time for completely random 100 positive/100 negative data of length 100
100

80

60

40

20

0

1

2

40

3

4

5

6

7

8

9

10

11

0

12

1

2

3

4

5

6

7

8

9

10

Maximum pattern length

Maximum pattern length

Execution time for 100 positive/100 negative data of length 100 with VLDC in Window

Effect of branch-and-bound for 100 positive/100 negative of length 100
100

Substring
VLDC: PMM
VLDC: WDAWG
VLDC: WDAWG-sm
VLDC in Window: PMM
VLDC in Window: DP-rm

80

11

12

11

12

VLDC: PMM with Branch and bound - Embedded VLDCVLDC: PMM with Branch and bound - Embedded VLDC in Window
VLDC: PMM with Branch and bound - Random
VLDC: PMM Exhaustive search

80

60Time (secs)

Time (secs)

60

20

100

40

20

0

Substring
VLDC: PMM
VLDC: WDAWG
VLDC: WDAWG-sm
VLDC in Window: PMM
VLDC in Window: DP-rm

80

Time (secs)

Time (secs)

Execution time for 100 positive/100 negative data of length 100 with embedded VLDC in Window
100

Substring
VLDC: PMM
VLDC: WDAWG
VLDC: WDAWG-sm
VLDC in Window: PMM
VLDC in Window: DP-rm

60

40

20

1

2

3

4

5

6

7

Maximum pattern length

8

9

10

11

12

0

1

2

3

4

5

6

7

8

9

10

Maximum pattern length

Fig. 3. Execution time (in seconds) for artiﬁcial data for diﬀerent maximum lengthsof patterns to be searched for with: completely random data (upper left), VLDC andwindow size embedded data (upper right), VLDC embedded data (lower left). The
lower right graph shows the eﬀect of pruning of the search space for the diﬀerent data
sets, compared to exhaustive search on the completely random dataset.

the mTP sequences and (73/431 = 16.94%) of the SP and Other sequences. Thispattern can also be regarded as capturing existing knowledge about mTPs [23]:They are fairly abundant in K or R, but do not contain much D or E. The patternalso suggests a periodic appearance of K or R, which is a characteristic of anamphiphilic α-helix that mTPs are reported to have. A best substring searchﬁnds pattern 212221 in 20 seconds, which gives us a classiﬁer that matches
318/368 = 86.41% of sequences with mTP and 255/431 = 59.16% of the othersequences.

References
1. D. Angluin. Finding patterns common to a set of strings. J. Comput. Sys. Sci.,
21:46–62, 1980.
2. R. A. Baeza-Yates. Searching subsequences (note). Theoretical Computer Science,78(2):363–376, Jan. 1991.
3. A. Blumer, J. Blumer, D. Haussler, A. Ehrenfeucht, M. T. Chen, and J. Seiferas.
The smallest automaton recognizing the subwords of a text. Theoretical Computer
Science, 40:31–55, 1985.
4. M. Crochemore. Transducers and repetitions. Theoretical Computer Science,
45:63–86, 1986.

5. M. Crochemore and W. Rytter. Text Algorithms. Oxford University Press, New
York, 1994.
6. G. Das, R. Fleischer, L. Gasieniec, D. Gunopulos, and J. Kärkkäinen. Episodematching. In Proc. 8th Annual Symposium on Combinatorial Pattern Matching (CPM’97), volume 1264 of Lecture Notes in Computer Science, pages 12–27.
Springer-Verlag, 1997.
7. D. Gusﬁeld. Algorithms on Strings, Trees, and Sequences. Cambridge University
Press, New York, 1997.
8. M. Hirao, H. Hoshino, A. Shinohara, M. Takeda, and S. Arikawa. A practicalalgorithm to ﬁnd the best subsequence patterns. In Proc. The Third International Conference on Discovery Science, volume 1967 of Lecture Notes in Artificial
Intelligence, pages 141–154. Springer-Verlag, 2000.
9. M. Hirao, S. Inenaga, A. Shinohara, M. Takeda, and S. Arikawa. A practicalalgorithm to ﬁnd the best episode patterns. In Proc. The Fourth International
Conference on Discovery Science, volume 2226 of Lecture Notes in Artificial Intelligence, pages 435–440. Springer-Verlag, 2001.
10. S. Inenaga, A. Shinohara, M. Takeda, H. Bannai, and S. Arikawa. Space-economical
construction of index structures for all suﬃxes of a string. In Proc. 27th International Symposium on Mathematical Foundations of Computer Science (MFCS’02),
Lecture Notes in Computer Science. Springer-Verlag, 2002. To appear.
11. S. Inenaga, M. Takeda, A. Shinohara, H. Hoshino, and S. Arikawa. The minimum
dawg for all suﬃxes of a string and its applications. In Proc. 13th Annual Symposium on Combinatorial Pattern Matching (CPM’02), volume 2373 of Lecture Notes
in Computer Science, pages 153–167. Springer-Verlag, 2002.
12. S. R. Kosaraju. Fast pattern matching in trees. In Proc. 30th IEEE Symp. on
Foundations of Computer Science, pages 178–183, 1989.
13. J. Kyte and R. Doolittle. A simple method for displaying the hydropathic characterof a protein. J. Mol. Biol., 157:105–132, 1982.
14. H. Mannila, H. Toivonen, and A. I. Verkamo. Discovering frequent episode insequences. In Proc. 1st International Conference on Knowledge Discovery andData Mining, pages 210–215. AAAI Press, 1995.
15. S. Miyano, A. Shinohara, and T. Shinohara. Polynomial-time learning of elementary formal systems. New Generation Computing, 18:217–242, 2000.
16. S. Morishita and J. Sese. Traversing itemset lattices with statistical metric pruning.
In Proc. of the 19th ACM SIGACT-SIGMOD-SIGART Symposium on Principles
of Database Systems, pages 226–236. ACM Press, 2000.
17. S. Shimozono, A. Shinohara, T. Shinohara, S. Miyano, S. Kuhara, and S. Arikawa.
Knowledge acquisition from amino acid sequences by machine learning system
BONSAI. Transactions of Information Processing Society of Japan, 35(10):2009–2018, 1994.
18. A. Shinohara, M. Takeda, S. Arikawa, M. Hirao, H. Hoshino, and S. Inenaga.
Finding best patterns practically. In Progress in Discovery Science, volume 2281
of Lecture Notes in Artificial Intelligence, pages 307–317. Springer-Verlag, 2002.
19. T. Shinohara. Polynomial-time inference of pattern languages and its applications.
In Proc. 7th IBM Symp. Math. Found. Comp. Sci., pages 191–209, 1982.
20. Z. Tronı́ček. Episode matching. In Proc. 12th Annual Symposium on Combinatorial
Pattern Matching (CPM’01), volume 2089 of Lecture Notes in Computer Science,
pages 143–146. Springer-Verlag, 2001.
21. E. Ukkonen. On-line construction of suﬃx trees. Algorithmica, 14(3):249–260,
1995.

22. G. von Heijne. The signal peptide. J. Membr. Biol., 115:195–201, 1990.
23. G. von Heijne, J. Steppuhn, and R. G. Herrmann. Domain structure of mitochondrial and chloroplast targeting peptides. Eur. J. Biochem., 180:535–545, 1989.