String Pattern Regression Algorithm for Pattern Discovery

1

A String Pattern Regression Algorithm and Its
Application to Pattern Discovery in Long Introns
Hideo Bannai1

Shunsuke Inenaga2

Ayumi Shinohara2,3

bannai@ims.u-tokyo.ac.jp

s-ine@i.kyushu-u.ac.jp

ayumi@i.kyushu-u.ac.jp

12
3

Masayuki Takeda2,3Satoru Miyano1

takeda@i.kyushu-u.ac.jp

miyano@ims.u-tokyo.ac.jp

Human Genome Center, Institute of Medical Science, University of Tokyo, 4-6-1
Shirokane-dai, Minato-ku, Tokyo 108-8639, Japan
Department of Informatics, Kyushu University 33, Fukuoka 812-8581, Japan
PRESTO, Japan Science and Technology Corporation (JST)Abstract
We present a new approach to pattern discovery called string pattern regression, where we are
given a data set that consists of a string attribute and an objective numerical attribute. The problem
is to find the best string pattern that divides the data set in such a way that the distribution of
the numerical attribute values of the set for which the pattern matches the string attribute, is mostdistinct, with respect to some appropriate measure, from the distribution of the numerical attributevalues of the set for which the pattern does not match the string attribute. By solving this problem,
we are able to discover, at the same time, a subset of the data whose objective numerical attributes
are significantly different from rest of the data, as well as the splitting rule in the form of a string
pattern that is conserved in the subset. Although the problem can be solved in linear time for thesubstring pattern class, the problem is NP-hard in the general case (i.e. more complex patterns),
and we present an exact but efficient branch-and-bound algorithm which is applicable to various
pattern classes. We apply our algorithm to intron sequences of human, mouse, fly, and zebrafish,and show the practicality of our approach and algorithm. We also discuss possible extensions of
our algorithm, as well as promising applications, such as microarray gene expression data.

Keywords: pattern discovery, string pattern matching, regression, long introns

1

Introduction

Pattern discovery from the current wealth of biological sequences is one of the most important problems
in the field of bioinformatics. The aim is to find patterns which are conserved across different biologicalsequences, since such patterns might indicate that the sequences share the same or similar functions.
Computational analyses which provide such candidates can be very helpful, since they can guide thebiologists in the task of identifying and experimentally confirming the actual sequence in play.
In a broad perspective, traditional settings in pattern discovery can be classified into two cases [3].
The first is when we are given a single set of sequences, or a positive data set and we would like to findpatterns which are conserved in the sequences, generally preferring longer patterns which appear in
most of the sequences in the set. Solving such a problem ranges from a plethora of multiple alignment
methods, and numerous other methods such as Gibbs sampling [10] or MEME [1]. Another situation
is when we have more information at hand, and are given a second set of sequences as an explicit
negative data set that is known not to have characteristics of (or known to have different characteristicsfrom) the first set, and the problem is to find a pattern which match most of the sequences in one set,
while not matching those of the other set [8, 13, 14].

2

Bannai et al.

In this paper, we consider a new situation where we are given a single set of sequences, but this time,
we are presented with more information in the form of a numerical value expressing some objective
measure of interest, paired with each sequence. We formalize the situation and define the string
pattern regression problem for a general pattern class. The numerical values in our situation gives us
quantitative information concerning the sequences, and our intention is to find the best pattern whichis conserved in a subset of the sequences for which the distribution of numerical values of the subset
is most different from the distribution of the numerical values of the rest. Making use of both thestring attribute and numerical attribute, we are able to discover, at the same time, a subset of thedata whose objective numerical attributes are significantly different from rest of the data, as well as
the splitting rule in the form of a string pattern that is conserved in the subset. Although the problem
can be solved in linear time for the substring pattern class, the problem is NP-hard in the generalcase, and we will present an efficient branch-and-bound algorithm which solves the problem exactly.
We can apply our algorithm with various pattern classes, such as subsequence patterns, approximate
patterns, VLDC patterns [8], and many others.
Compared with the previous situations, the string pattern regression problem can be viewed as a
generalization of the situation where we have both a positive and negative sequence set, since we could
set the numerical attributes to 1 for the positive set, and −1 for the negative set, which would thenrepresent an equivalent problem. A natural advantage of our new situation is that more general values
can be assigned to each sequence. Also, the data set does not need to be divided a priori into positive
and negative data sets, for example, according to some threshold for the numerical attributes, which
we would have to do in the previous situation. Another way to view the problem is in the context ofregression, where it can be seen as trying to predict the numerical value from a binary value (whether
a pattern matches or not), and the aim is to find the pattern which best predicts the numerical value.
In Section 2, we will define the problem of string pattern regression for a general pattern class.
In Section 3, we will present the branch-and-bound algorithm which solves the problem exactly, andgive examples of pattern classes to which our algorithm can be applied. To show that our methods
are useful in practice, in Section 4, we describe computational experiments of applying our algorithm
to the acceptor site sequences of introns, paired with the logarithm of the (whole) intron length. The
results strengthen our recent observation that there is a correlation between the intron length and its
base composition in some species [2] (U over C, and A over G for longer introns), and especially theimportance of U’s in the polypyrimidine tract near the acceptor site for longer introns. We discusspossible extensions to our algorithm, as well as promising applications of our approach, in Section 5.

2

Preliminaries

2.1

Notation

Let N be the set of non-negative integers, and R the set of real numbers. Let Σ be a finite set ofcharacters called the alphabet. An element of Σ∗ is called a string. The length of a string w is denotedby l(w). The empty string is denoted by ε, that is, l(ε) = 0. Strings x, y, and z are said to be aprefix, substring, and suffix of string w = xyz, respectively. For a set T ⊆ Σ∗ of strings, the number ofstrings in T is denoted by |T | and the total length of strings in T is denoted by l(T ). Let 2Σ denotethe power set of Σ, which is the set of all subsets of Σ.
A pattern class is a pair C = (Π, m), where Π is a set called the pattern set and m : Σ∗ ×Π → {−1, 1}
is the pattern matching function. An element p ∈ Π is called a pattern. For a pattern p ∈ Π and stringt ∈ Σ∗ , we say p of class C matches t if m(t, p) = 1, and p of class C does not match t, otherwise.
For example, the substring pattern class is defined with the pattern set Σ∗ and the pattern matching
function strstr given by:(
1 p is a substring of t
strstr(t, p) =−1 otherwiseString Pattern Regression Algorithm for Pattern Discovery

3

Other examples of pattern classes will be given in Section 3.2. For a pattern p, we denote by LC (p)the set of strings in Σ∗ which p of class C matches. We will write p ¹C p0 if LC (p) ⊇ LC (p0 ).

2.2

Problem Definition

Here, we define the problem of string pattern regression. We assume a set of data having two attributes:
a string attribute and an objective numerical attribute. Let D ⊂ Σ∗ × R denote this data set. Fora pattern p ∈ Π, the data set D can be split into two sets: Dp , which represents the subset of D for
which the pattern p matches the string attribute, and Dp̄ , where p does not match the string attribute.
The aim of our approach is to find the pattern for which the distributions of the objective numeric
attribute of Dp is “best distinguished” from that of Dp̄ .
There can be many measures for the goodness of such splits, but we will define the problem asfollows:
Definition 1 (String pattern regression) Given a data set D ⊂ Σ∗ × R and a pattern class C =(Π, m), the string pattern regression problem is to find p ∈ Π such that the mean squared error defined
below is minimized:P

M SE(D, p) =(s,r)∈Dp (µ(Dp ) − r)2+P2(s,r)∈Dp̄ (µ(Dp̄ ) − r)|D|,

where Dp = {(s, r) | (s, r) ∈ D and s ∈ LC (p)} is the subset of D for which p matches the stringP
attribute, Dp̄ = D−Dp , and µ(D0 ) = (s,r)∈D0 r/|D0 | represents the average of the objective numericalattribute values of the data in D0 ⊆ D.
Minimizing the mean squared error can be achieved by maximizing the interclass variance (ICV ) [12],defined by:
ICV (D, p) = |Dp |(µ(D) − µ(Dp ))2 + |Dp̄ |(µ(D) − µ(Dp̄ ))2(1)

This measure is more convenient for our calculations, and will be used for the remaining of the paper.
For the substring pattern class, the problem can be solved in linear time, in the summed lengthof all the string attributes, by a clever use of suffix trees for strings, extending the algorithm of [7]to incorporate the numerical attributes. However, the problem is NP-hard in general, for example,
for more complex pattern classes such as subsequence patterns. This paper will focus on giving
an efficient but exact branch-and-bound algorithm for solving this problem in a general case, applicable to various pattern classes, such as subsequence patterns, approximate patterns (with substitution/insertion/deletion), patterns with don’t care characters, patterns with classes of alphabets, VLDC
patterns, etc.

3

Branch-and-Bound Algorithm

In this section, we present a branch-and-bound algorithm for solving the string pattern regression
problem. In principle, the algorithm proceeds by enumerating all of the patterns in Π. The idea
behind our branch-and-bound heuristics is as follows: at a given point in the algorithm, when we havecalculated the subset of the data for which the pattern p matches, we can calculate the upperboundof the interclass variance for any pattern p0 such that p ¹C p0 . If the upper bound is less than thecurrent maximum value, we can stop considering such patterns and therefore prune the search space.
Since the overall strategy for the enumeration of patterns is essentially the same as [8, 14], we will only
briefly describe this procedure. However, the calculation of the upperbound is somewhat different,
which we will describe in detail.

4

Bannai et al.



   !   

y

+

1000
800
600
400

0

200

x

0

0

100
20

-

50
40
x

0

60

y

-50

80

(a)

(b)

Figure 1: (a) The interclass variance ICV as a function of x and y for |D| = 100. (b) The region
depicting the possible values of x, y for any subset of a given data set D. The shaded region depicts
a smaller region, after 2 elements are removed from D. An upper bound for the ICV of any point
inside of the shaded region can be obtained by calculating the maximum ICV for the vertices of theconvex hull enclosing the shaded region.

3.1

Upperbound Calculation

We can normalize the numeric values so that their average will be 0, that is, µ(D) = 0. Under this
P
−yp
y
,
conversion, let xp = |Dp | and yp = (s,r)∈Dp r for a pattern p. Since µ(Dp ) = xpp and µ(Dp̄ ) = |D|−xp
the interclass variance can be written as:(

ICV (D, p) = f|D| (xp , yp ) =

yp2

³

0
1
1
xp + |D|−xp´

if xp = 0 or xp = |D|otherwiseP

For any subset D0 ⊆ D, we can define the pair (xD0 , yD0 ) = (|D0 |, (s,r)∈D0 r) and we call it the stamp
point of D0 . If D0 = Dp for some pattern p, we also call it the stamp point of pattern p.
Figure 1(a) shows the function f100 (x, y). Figure 1(b) shows the region of possible values for (x, y),for some subset of the data. For any set Dp , let H(Dp ) denote the convex hull enclosing the region of
the possible stamp points for all D0 ⊆ Dp . Although the number of stamp points inside H(Dp ) canbe exponential in |Dp |, H(Dp ) can be obtained by first sorting the data set according to the objective
numerical attribute, and then summing the values in order (i.e. given x = k, the maximum (minimum)
possible value for y is obtained by using the k largest (smallest) elements).
From the convexity of f [12], the following property holds:
Lemma 1 For any 0 ≤ x ≤ c and y1 ≤ y ≤ y2 , we have fc (x, y) ≤ max(fc (x, y1 ), fc (x, y2 )).
This gives us the following lemma.
Lemma 2 For a given data set Dp ⊆ D, the stamp point (x, y) for any D0 ⊆ Dp lies inside of, oris a vertex of H(Dp ). The maximum value for f|D| (x, y) for points in H(Dp ) is given by a vertex ofH(Dp ).
Since if p ¹C p0 , then LC (p) ⊇ LC (p0 ),String Pattern Regression Algorithm for Pattern Discovery

5

Lemma 3 Given a pattern p of class C and data set D, for any p0 such that p ¹C p0 , the stamp point(x0p , yp0 ) of p0 lies inside of, or is a vertex of H(Dp ).
For our problem, since we must use a string pattern to divide the data set, we do not know
immediately whether there exists a pattern whose stamp point is a given pair (x, y). Nevertheless, we
can use the maximum value of the ICV for the vertices in H(Dp ) as an upperbound for any point
inside H(Dp ). From the above lemmas, we are able to calculate the upperbound of any p0 which
satisfies p ¹C p0 by calculating the maximum value of f for the vertices of H(Dp ). The calculation
takes O(|D| log |D|) time for the initial sorting of the data set, and O(|Dp |) for each p.

3.2

Pattern Classes and Pattern Enumeration

We briefly describe several pattern classes and enumeration methods to which our branch-and-boundalgorithm can be applied.
substring pattern: C = (Σ∗ , strstr). Defined in Section 2.
subsequence pattern: C = (Σ∗ , subseq). subseq(t, p) = 1 if p can be obtained by removing any
number of characters from t.
pattern with don’t care characters: C = ({Σ ∪ {.}}∗ , dcstrstr). ‘.’ is the don’t care character.
dcstrstr(t, p) = 1 if a substring of t can be obtained by substituting each don’t care characterwith a character in Σ.
VLDC pattern: C = ({Σ ∪ {?}}∗ , vldc). ? is the variable length don’t care symbol, or a wild cardthat can represent 0 or more characters. vldc(t, p) = 1 if t can be obtained from p by substituting
each of the ?’s in p with an element of Σ∗ .
pattern with classes of alphabets: C = ({2Σ }∗ , cstrstr). A pattern p = p1 · · · pm is essentially asequence of subsets of the alphabet Σ. cstrstr(t, p) = 1 if there exists a substring ti . . . ti+m−1
of t such that ti+k−1 ∈ pk for 1 ≤ k ≤ m.
Patterns in the above pattern classes consist only of strings of a pattern alphabet, and can be enumerated simply by first starting from the empty string as a seed pattern, and then concatenating a
new character of the pattern alphabet, for all members of the alphabet. The new patterns are thenconsidered as new seed patterns, and the process is repeated (of course we should be careful not tocreate useless patterns such as ‘? ? ?’).
Adding a new character c to a pattern p results in the decrease in the number of strings forwhich the pattern matches, and it is easy to see that p ¹C p0 for any pattern p0 which is obtained byelongating a seed pattern p.
approximate pattern: C = (Σ∗ × N, astrstr). For p = hs, ni, astrstr(t, p) = 1 if t contains asubstring such that the edit distance (with insertion, deletion, substitution operations) from s
is within n.
episode pattern: C = (Σ∗ ×N, esubseq). For p = hs, ni, esubseq(t, p) = 1 if there exists a substring t0
of t where |t0 | ≤ n, for which subseq(t0 , p) = 1. Notice that hs, ∞i is the same as the subsequence
pattern s. Moreover, hs, |s|i is the same as the substring pattern.
VLDC pattern within a window: C = ({Σ ∪ {?}}∗ × N, evldc). For p = hs, ni, evldc(t, p) = 1 if
there exists a substitution for the ?’s in s with Σ∗ that yields t, and for the substitution, thelength between the corresponding positions, in t, for the first and last non-star characters of s,is less than n. Notice that hs, ∞i is the same as the VLDC pattern s.

6Bannai et al.

Patterns in the above pattern classes have two elements. The enumeration for the first element
can be done in the same way as the patterns described previously. Given the first element s, we cancalculate the best second element in the following way. For each text ti , we are able to calculate theminimum value kti for which the pattern hs, kti i matches the text for a given first element of the above
classes [8, 14]. If we sort the data set according to the kti ’s, we can calculate in one pass, all possible
scores, just by calculating the scores for each threshold, therefore obtaining the integer value giving
the best score [8, 14]. For a pattern p = hs, ni and any pattern p0 = hs0 , n0 i such that s0 is a descendantof s and n ≥ n0 , we have p ¹C p0 . We can use hs, nmax i to calculate the upperbound for p0 where
nmax can be ∞, or a predefined parameter to limit the space of possible patterns.

4

Computational Experiments

The algorithm was implemented in the Objective Caml language [16]. All experiments were conducted
on a dual Xeon 2.2 GHz desktop computer with 1GB of main memory running Debian Linux. We
have currently implemented all of the pattern classes mentioned in the previous section, except for
patterns with classes of alphabets. The enumeration of patterns was done in a guided depth firstsearch, where all characters of the alphabet are added to the seed, and the pattern which gives thebest upperbound is then used as the next seed.

4.1

Patterns from Intron Sequences

Introns are non-coding regions of a eucaryotic gene which are transcribed to RNA, but are subsequently
spliced out, to form the mature mRNA. There have been observations that a significant fraction of
mutations in human genes that cause diseases affect the pre-mRNA splicing [4, 9], and elucidating themechanism of pre-mRNA splicing is an important problem. Although the mechanism of splicing has
been studied extensively, and canonical splicing signals are known (e.g.: the GU-AG rule and branchsites with an adjacent polypyrimidine tract (PPT)), computational prediction of the splice sites fora given pre-mRNA sequence is still difficult due to many pseudo-signals which are detected. Splicesite predictions for short introns seem to be fairly accurate [11], but a deeper understanding of long
introns - which can even be longer than 100,000 bases - seems to be necessary.
In an attempt to find differences between short and long introns, we have recently observed that
there is a preference for U over C, and A over G in longer introns of human and mouse, especiallynear the acceptor site of the intron [2]. In this paper, we run our algorithm, on the data set createdas described below, to see if we could find string patterns which are characteristic of long (or short)introns. Intron sequences of several species were taken from the Ensembl database [6] (human release
4.28, mouse release 4.1, fly release 4.3, and zebrafish release 4.06.). The intron sequences of genes with
only one known transcript, obey the GU-AG rule, whose lengths are greater than or equal to 20, anddo not contain characters other than ’A’, ’C’, ’G’, or ’U’ (e.g. ’N’), were collected. This resulted in aset of 1063, 5929, 44833, 114669 introns for zebrafish, fly, mouse, and human, respectively. For each
intron, we use the pair of: 20 bases of the intron adjacent to its acceptor site (including the AG), andthe logarithm of the length of the entire intron.
We use the “VLDC pattern within a window” (defined in the previous section) as the patternclass, and a guided depth first enumeration of patterns. Figure 2 shows the histograms, for humanand mouse, of log intron lengths for the sets of introns which the best VLDC pattern discovered by
our algorithm matches or does not match the intron acceptor site sequence. The discovered patterns
h?U?U?U?U?U?U?A?, 18i, and h?U?U?U?U?U?U?, 15i which match the longer introns, interestingly
consists of many U’s, consistent with our previous observation concerning base content. We can seethat although the distributions of the log intron length for the matching and non-matching set issimilar for shorter introns (e.g. ∼256 for human), there is a clear difference for the longer introns.
The pattern discovered for zebrafish was h?U?U?UU?UUGCAG?,15i. This pattern shows that U is

String Pattern Regression Algorithm for Pattern Discovery

2500

Mouse
U U U U U U U

,15>
total
match
no match

0

1000

500

F requency

total
match
no match

3000

<

1500

A ,18>

0

F requency

< U U

Human
U U U U U

7

4

6

8
10
12
14
Log2 intron length

(a)

16

18

4

6

8
10
12
Log2 intron length

14

(b)

Figure 2: Splitting the log intron lengths with the best VLDC pattern within a window. The histograms of long intron lengths of 1) all introns, 2) introns which the pattern matches, and 3) introns
which the pattern does not match, are overlayed. (a) The human introns are split with the pattern
h?U?U?U?U?U?U?A?, 18i. (b) The mouse introns are split with the pattern h?U?U?U?U?U?U?, 15i.
an important element in longer introns for zebrafish as well, which was not evident when just looking
at the base frequencies. The pattern discovered for fly was h?A?A?A?U?,18i, which is more abundantin shorter introns this time, is yet to be interpreted. When using substring patterns, the patterns
discovered were UUU for human and mouse, UUGCAG for zebrafish, and AA (matching the shorter
introns) for fly.
The discovered patterns are interesting since there has been a report that the strength of a PPT(a region near the acceptor site of an intron, abundant in pyrimidines (C or U)), depends greatly on
the amount of U’s (the more the stronger) [5]. Assuming this is true for most PPT’s, this implies that
acceptor sites of longer introns tend to be stronger. This may imply that, it is harder for long introns
to be recognized after all, and they require a stronger acceptor site to be spliced correctly.

4.2

Performance

The execution time was about 47 hours and 42 hours respectively, using “VLDC pattern within awindow” for human and mouse. This may not seem very fast, but we should consider the fact thatthe calculation with this pattern class would not have been feasible without the pruning of the search
space.
Table 1 shows the comparison of execution times for the zebrafish introns, with and without thebranch-and-bound search, while varying the maximum length of the pattern searched for (the lengthof a VLDC pattern is defined as the number of non-wild card characters). The run time for theexhaustive search is exponential as expected while the run time for the branch-and-bound algorithm
seems to converge, even showing a slight decrease when not specifying a maximum length. This isprobably because a longer but higher scoring pattern was found at an earlier stage of the search, which
resulted in the pruning of a larger portion of the search space.

5

Discussion

We defined a new approach to string pattern discovery and presented an efficient branch-and-boundalgorithm for solving the problem exactly. We conducted computational experiments on intron sequences, and showed the practicality of our approach and methods.

8Bannai et al.

Table 1: Execution times (in seconds) for branch-and-bound and exhaustive algorithms on zebrafish
introns
max len
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
∞

exhaustive
0.02
0.12
0.69
3.57
16.10
64.52
237.56896.473136.8512230.58
43925.63
N/A
N/A
N/A
N/A
N/A

b&b
0.02
0.13
0.76
3.83
16.52
61.09
183.45418.11
761.351086.911345.591454.61
1483.77
1617.471685.52
1511.27

best pattern
hC?,1ih?C?G,8i
h?G?C?G,9i
h?G?C?AG?,9ih?UUG?C?G,7ih?UUG?C?G,7ih?UUG?C?G,7ih?UUG?C?G,7ih?UUG?C?G,7i
h?U?U?UU?UUGCAG?,15i
h?U?U?UU?UUGCAG?,15i
h?U?U?UU?UUGCAG?,15i
h?U?U?UU?UUGCAG?,15i
h?U?U?UU?UUGCAG?,15i
h?U?U?UU?UUGCAG?,15i
h?U?U?UU?UUGCAG?,15i

ICV
8.35
55.96
77.80
86.55
111.77111.77111.77111.77111.77115.09115.09115.09115.09115.09115.09115.09

Our problem definition can be easily extended for finding patterns from strings associated withn numerical attributes. However, subtleties arise in the process of calculating the upper bound ofa given pattern, where finding the maximum and minimum sizes of the sum vector (i.e. |~y |2 in|~y |2 (1/x + 1/(|D| − x))) does not seem to be straightforward. Still, the problem can be efficiently
solved for the substring pattern class, again in linear time, since pruning of the search space is notnecessary in this case. The score function used in this paper is the interclass variance (1), but anyother function f which satisfies Lemma 1 could be used in place. Our algorithm can also be easily
modified to find the k highest scoring patterns.
Another promising application of our approach is for microarray gene expression data, to discover
putative regulatory elements contained in the upstream regions of the genes. Preliminary experiments
have been conducted with the publicly available cell cycle data of [15], using the pair of upstream
sequence of the gene, and the expression level for that gene, as data. Our algorithm was able tocapture several known motifs, for example, the well known MCB element ACGCGT, related to cell
cycle.

Acknowledgements
This research was supported in part by Grant-in-Aid for Encouragement of Young Scientists, andGrant-in-Aid for Scientific Research on Priority Areas “Genome Information Science” from the Ministry of Education, Culture, Sports, Science and Technology of Japan.

References[1] Bailey, T. L. and Elkan, C., Fitting a mixture model by expectation maximization to discovermotifs in biopolymers. Proc. Second International Conference on Intelligent Systems for Molecular
Biology, 28–36, AAAI Press, 1994.
[2] Bannai, H., Tamada, Y., Ott, S., Nakai, K., and Miyano, S., Long introns tend to have stronger
splice acceptor sites. submitted

String Pattern Regression Algorithm for Pattern Discovery

9[3] Brazma, A., Jonassen, I., Eidhammer, I., and Gilbert, D., Approaches to automatic discovery ofpatterns in biosequences. Journal of Computational Biology, 5(2):279–305, 1998.
[4] Cartegni, L., Chew, S. L., and Krainer, A. R., Listening to silence and understanding nonsense:
exonic mutations that affect splicing, Nat. Rev. Genet., 3(4):285–298, 2002.
[5] Coolidge, C. J., Seely, R. J., and Patton, J. G., Functional analysis of the polypyrimidine tract
in pre-mRNA splicing, Nucleic Acids Res., 25(4):888–896, 1997.
[6] Hubbard, T., Barker, D., Birney, E., Cameron, G., Chen, Y., Clark, L., Cox, T., Cuff, J., Curwen,
V., Down, T., Durbin, R., Eyras, E., Gilbert, J., Hammond, M., Huminiecki, L., Kasprzyk, A.,
Lehvaslaiho, H., Lijnzaad, P., Melsopp, C., Mongin, E., Pettett, R., Pocock, M., Potter, S., Rust,A., Schmidt, E., Searle, S., Slater, G., Smith, J., Spooner, W., Stabenau, A., Stalker, J., Stupka,
E., Ureta-Vidal, A., Vastrik, I., and Clamp, M., The Ensembl genome database project, Nucleic
Acids Res., 30(1):38–41, 2002.
[7] Hui, L., Color set size problem with applications to string matching, Proc. Third Anual Symposium on Combinatorial Pattern Matching, LNCS 644:230–243, 1992.
[8] Inenaga, S., Bannai, H., Shinohara, A., Takeda, M., and Arikawa, S., Discovering best variablelength-don’t-care patterns, Proc. 5th International Conference on Discovery Science, 2002, inpress.
[9] Krawczak, M., Reiss, J., and Cooper, D. N., The mutational spectrum of single base-pair substitutions in mRNA splice junctions of human genes: causes and consequences, Hum. Genet.,
90(1–2):41–54, 1992.
[10] Lawrence, C. E., Altschul, S. F., Boguski, M. S., Liu, J. S., Neuwald, A. F., and Wootton, J. C.,
Detecting subtle sequence signals: a Gibbs sampling strategy for multiple alignment, Science,
262(5131):208–214, 1993.
[11] Lim, L. P. and Burge, C. B., A computational analysis of sequence features involved in recognitionof short introns, Proc. Natl. Acad. Sci., 98(20):11193–11198, 2001.
[12] Morimoto, Y., Ishii, H., and Morishita, S., Efficient construction of regression trees with range
and region splitting, Machine Learning, 45:235–259, 2001.
[13] Shimozono, S., Shinohara, A., Shinohara, T., Miyano, S., Kuhara, S., and Arikawa, S., Knowledge
acquisition from amino acid sequences by machine learning system BONSAI, Transactions ofInformation Processing Society of Japan, 35(10):2009–2018, 1994.
[14] Shinohara, A., Takeda, M., Arikawa, S., Hirao, M., Hoshino, H., and Inenaga, S., Finding best
patterns practically, Progress in Discovery Science, LNAI 2281:307–317, 2002.
[15] Spellman, P. T., Sherlock, G., Zhang, M. Q., Iyer, V. R., Anders, K., Eisen, M. B., Brown, P. O.,
Botstein, D., and Futcher, B., Comprehensive identification of cell cycle-regulated genes of theyeast saccharomyces cerevisiae by microarray hybridization, Mol. Biol. Cell, 9:3273–3297, 1998.
[16] Objective Caml - http://caml.inria.fr/ocaml/.