Fast and simple character classes and bounded gaps pattern matching, with application to protein searching.
The problem of fast searching of a pattern that contains Classes of characters and Bounded size Gaps (CBG) in a text has a wide range of applications, among which a very important one is protein pattern matching (for instance, one PROSITE protein site is associated with the CBG [RK]  x(2, where the brackets match any of the letters inside, and x(2, 3) a gap of length between 2 and 3). Currently, the only way to search a CBG in a text is to convert it into a full regular expression (RE). However, a RE is more sophisticated than a CBG, and searching it with a RE pattern matching algorithm complicates the search and makes it slow. This is the reason why we design in this article two new practical CBG matching algorithms that are much simpler and faster than all the RE search techniques. The first one looks exactly once at each text character. The second one does not need to consider all the text characters and hence it is usually faster than the first one, but in bad cases may have to read the same text character more than once. We then propose a criterion based on the form of the CBG to choose a-priori the fastest between both. We performed many practical experiments using the PROSITE database, and all them show that our algorithms are the fastest in virtually all cases.
Introduction
This paper deals with the problem of fast searching of patterns that contain Classes of characters
and Bounded size Gaps (CBG) in texts. This problem occurs in various elds, like information
retrieval, data mining and computational biology. We are particularly interested in the latter one.
In computational biology, this problem has many applications, among which the most important
is protein matching. These last few years, huge protein site pattern databases have been developed,
like PROSITE [7, 11]. These databases are collections of protein site descriptions. For each protein
site, the database contains diverse information, notably the pattern. This is an expression formed
with classes of characters and bounded size gaps on the amino acid alphabet (of size 20). This
pattern is used to search a possible occurrence of this protein in a longer one. For example, the
protein site number PS00007 has as its pattern the expression [RK] x(2;
where the brackets mean that the position can match any of the letters inside, and x(2; means
a gap of length between 2 and 3.
Dept. of Computer Science, University of Chile. Blanco Encalada 2120, Santiago, Chile.
gnavarro@dcc.uchile.cl. Work developed while the author was at postdoctoral stay at the Institut Gaspard Monge,
Univ. de Marne-la-Vallee, France, partially supported by Fundacion Andes and ECOS/Conicyt.
y Equipe genome, cellule et informatique, Universite de Versailles, 45 avenue des Etats-Unis, 78035 Versailles Cedex,
E-mail: raffinot@monge.univ-mlv.fr. The work was done while the author was at the Institut Gaspard-Monge,
Cite Descartes, Champs-sur-Marne, 77454 Marne-la-Vallee Cedex 2, France.
Currently, these patterns are considered as full regular expressions (REs) over a xed alphabet
, i.e generalized patterns composed of (i) basic characters of the alphabet (adding the empty
word " and also a special symbol x that can match all the letters of ), (ii) concatenation (denoted
closure (). This latter operation L  on a set of words L means
that we accept all the words made by a concatenation of words of L. For instance, our previous
pattern can be considered as the regular expression (RjK)  x  x  (xj")  (DjE)  x  x  (xj")  Y .
We note jREj the length of an RE, that is the number of symbols in it. The search is done with
the classical algorithms for RE searching, that are however quite complicated. The RE needs to be
converted into an automaton and then searched in the text. It can be converted into a deterministic
automaton (DFA) in worst case time O(2 jREj ), and then the search is linear in the size n of the
text, giving a total complexity of O(2 jREj + n). It can also be converted into a nondeterministic
automaton (NFA) in linear time O(jREj) and then searched in the text in O(n jREj) time, giving
a total of O(n  jREj) time. We give a review of these methods in Section 3. The majority of the
matching softwares use these techniques [13, 22].
None of the presented techniques are fully adequate for CBGs. First, the algorithms are intrin-
sequely complicated to understand and to implement. Second, all the techniques perform poorly
for a certain type of REs. The \di-cult" REs are in general those whose DFAs are very large, a
very common case when translating CBGs to REs. Third, especially with regard to the sizes of the
DFAs, the simplicity of CBGs is not translated into their corresponding REs. At the very least,
resorting to REs implies solving a simple problem by converting it into a more complicated one.
Indeed, the experimental time results when applied to our CBG expressions are far from reasonable
in regard of the simplicity of CBGs and compared to the search of expressions that just contain
classes of characters [18].
This is the motivation of this paper. We present two new simple algorithms to search CBGs in
a text, that are also experimentally much faster than all the previous ones. These algorithms make
plenty use of \bit-parallelism", that consists in using the intrinsic parallelism of the bit manipulations
inside computer words to perform many operations in parallel. Competitive algorithms have
been obtained using bit parallelism for exact string matching [2, 26], approximate string matching
[2, 26, 27, 3, 17], and REs matching [15, 25, 20]. Although these algorithms generally work well
only on patterns of moderate length, they are simpler, more
exible (e.g. they can easily handle
classes of characters), and have very low memory requirements.
We performed two dierent types of time experiments, comparing our algorithms against the
fastest known for RE searching algorithms. We use as CBGs the patterns of the PROSITE database.
We rst compared them as \pure pattern matching", i.e. searching the CBGs in a compilation of
6 megabytes of protein sequences (from the TIGR Microbial database). We then compared them
as \library matching", that is search a large set of PROSITE patterns in a protein sequence of 300
amino acids. Our algorithms are by far the fastest in both cases. Moreover, in the second case,
the search time improvements are dramatic, as our algorithms are about 100 times faster than the
best RE matching algorithms.
The two algorithms we present are patented by the french Centre National de la Recherche
Scientique (CNRS) 1 .
We use the following denitions throughout the paper.  is the alphabet, a word on  is a
nite sequence of characters of .   means the set of all the words build on . A word x 2   is
a factor (or substring) of p 2   if p can be written . A factor x of p is called a
su-x of p is a prex of p is
1 The patent number 00 11093 has been deposed by the CNRS the 08/30/00. For any information about it please
contact Sbastien CHIRIE (sebastien.chirie@st.fr), FIST, 135 Boulevard Saint Michel, 75005 Paris, FRANCE.
We note with brackets a subset of elements of : [ART ] means the subset fA; R; Tg (a single
letter can be expressed in this way too). We add the special symbol x to denote a subset that
corresponds to the whole alphabet. We also add a symbol x(a; b); a < b, for a bounded size gap of
minimal length a and maximal b. A CBG on  is formally a nite sequence of symbols that can
be (i) brackets, (ii) x and (iii) bounded size gaps x(a; b). We dene m as the total number of such
symbols in a CBG.
We use the notation for the text of n characters of  in which we are searching
the CBGs. A CBG matches T at position j if there is an alignment of t with the CBG,
considering that (i) a bracket matches with any text letter that appears inside brackets; (ii) an x
matches any text letter; and (iii) a bounded gap x(a; b) matches at minimum a and at maximum
b arbitrary characters of T . We denote by ' the minimum size of a possible alignment and L
the size of a maximum one. For example, [RK] x(2; matches the text
at position 11 by 3 dierent alignments (see Figure 1), l = 7 and
Y
Y
R 2Y

Figure

1: Three dierent alignments of the CBG [RK] x(2; over the text
AHLRKDEDATY at the same ending position.
Searching a CBG in a text consists in nding all the positions j of
T in which there is an alignment of the CBG with a su-x of
This paper is organized as follows. We begin in Section 2 by summarizing the two main bit-parallel
approaches that lead to fast e-cient matching algorithms for simple strings but also for
patterns that contain classes of characters. In Section 3, we explain in detail what are the approaches
to search full REs. We then present in Section 4 our new algorithm (which we call a
\forward algorithm"), that reads all the characters of the text exactly once. It is based on a new
automaton representation and simulation. We present in Section 5 another algorithm (which we
call a \backward algorithm" despite that it processes the text basically left to right), that allows
us to skip some characters of the text, being generally faster. However, it can not been used for all
types of CBGs, and it is sometimes slower than the forward one. Consequently, we give in the next
Section 6 a good experimental criterion that enables us to choose a-priori the fastest, depending on
the form of the CBG. Section 7 is devoted to the experimental results for both algorithms compared
to the fastest RE searching algorithms.
2 Bit-parallelism for simple pattern matching
In [2], a new approach to text searching was proposed. It is based on bit-parallelism [1]. This
technique consists in taking advantage of the intrinsic parallelism of the bit operations inside a
computer word. By using cleverly this fact, the number of operations that an algorithm performs
can be cut down by a factor of at most w, where w is the number of bits in the computer word.
Since in current architectures w is 32 or 64, the speedup is very signicative in practice.

Figure

2 shows a non-deterministic automaton that searches a pattern in a text. Classical
pattern matching algorithms, such as KMP [14], convert this automaton to deterministic form
and achieve O(n) worst case search time. The Shift-Or algorithm [2], on the other hand, uses
bit-parallelism to simulate the automaton in its non-deterministic form. It achieves O(mn=w)
worst-case time, i.e. an optimal speedup over a classical O(mn) simulation. For m  w, Shift-Or
is twice as fast as KMP because of better use of the computer registers. Moreover, it is easily
extended to handle classes of characters.
We use some notation to describe bit-parallel algorithms. We use exponentiation to denote bit
repetition, e.g. We denote as the bits of a mask of length ', which is stored
somewhere inside the computer word of length w. We use C-like syntax for operations on the bits
of computer words, i.e. \j" is the bitwise-or, \&" is the bitwise-and, \" complements all the
bits, and \<<" moves the bits to the left and enters zeros from the right, e.g. b ' b
We can also perform arithmetic operations on the bits, such as addition and
subtraction, which operate the bits as if they formed a number, for instance
We explain now the basic algorithm and then a later improvement over it.
b a a b b a a
Figure

2: A nondeterministic automaton to search the pattern in a text.
2.1 Forward scanning
We present now the Shift-And algorithm, which is an easier-to-explain (though a little less e-cient)
variant of Shift-Or. Given a pattern the
algorithm builds rst a table B which for each character stores a bit mask . The mask
in B[c] has the i-th bit set if and only if c. The state of the search is kept in a machine
word matches the end of the text read up to
now (another way to see it is to consider that d i tells whether the state numbered i in Figure 2 is
active). Therefore, we report a match whenever dm is set.
We set originally, and for each new text character t j , we update D using the formula
The formula is correct because the i-th bit is set if and only if the (i 1)-th bit was set for
the previous text character and the new text character matches the pattern at position i. In other
words, Again, it is
possible to relate this formula to the movement that occurs in the nondeterministic automaton for
each new text character: each state gets the value of the previous state, but this happens only if
the text character matches the corresponding arrow. Finally, the \j after the shift allows a
match to begin at the current text position (this operation is saved in the Shift-Or, where all the
bits are complemented). This corresponds to the self-loop at the initial state of the automaton.
The cost of this algorithm is O(n). For patterns longer than the computer word (i.e. m > w),
the algorithm uses dm=we computer words for the simulation (not all them are active all the time),
with a worst-case cost of O(mn=w) and still an average case cost of O(n).
2.2 Classes of characters and extended patterns
The Shift-Or algorithm is not only very simple, but it also has some further advantages. The most
immediate one is that it is very easy to extend to handle classes of characters, where each pattern
position may not only match a single character but a set of characters. If C i is the set of characters
that match the position i in the pattern, we set the i-th bit of B[c] for all c 2 C
is necessary to the algorithm. In [2] they show also how to allow a limited number k of mismatches
in the occurrences, at O(nm log(k)=w) cost.
This paradigm was later enhanced to support extended patterns [26], which allow wild cards,
regular expressions, approximate search with nonuniform costs, and combinations. Further development
of the bit-parallelism approach for approximate string matching lead to some of the fastest
algorithms for short patterns [3, 17]. In most cases, the key idea was to simulate a nondeterministic
nite automaton.
Bit-parallelism has became a general way to simulate simple nondeterministic automata instead
of converting them to deterministic. This is how we use it in this paper, for the new type of extended
patterns we are focusing on.
2.3 Backward scanning
The main disadvantage of Shift-Or is its inability to skip characters, which makes it slower than
the algorithms of the Boyer-Moore [5] or the BDM [10, 9] families. We describe in this section the
BNDM pattern matching algorithm [18]. This algorithm, a combination of Shift-Or and BDM, has
all the advantages of the bit-parallel forward scan algorithm, and in addition it is able to skip some
text characters.
BNDM is based on a su-x automaton. A su-x automaton on a pattern is an
automaton that recognizes all the su-xes of P . The nondeterministic version of this automaton
has a very regular structure and is shown in Figure 3. In the original algorithm BDM [10, 9], this
automaton is made deterministic. BNDM, instead, simulates the automaton using bit-parallelism.
Just as for Shift-And, we keep the state of the search using m bits of a computer word
b a a b b a a

Figure

3: A nondeterministic su-x automaton for the pattern lines represent
"-transitions (i.e. they occur without consuming any input).
A very important fact is that this automaton can not only be used to recognize the su-xes of
P , but also factors of P . Note that there is a path labeled by x from the initial state if and only
if x is a factor of P . That is, the nondeterministic automaton will not run out of active states as
long as it has read a factor of P .
The su-x automaton is used to design a simple pattern matching algorithm. This algorithm is
time in the worst case, but optimal on average (O(n log  m=m) time). Other more complex
variations such as TurboBDM [10] and MultiBDM [9, 21] achieve linear time in the worst case.
To search a pattern in a text the su-x automaton of P
(i.e the pattern read backwards) is built. A window of length m is slid along the
text, from left to right. The algorithm searches backward inside the window for a factor of the
pattern P using the su-x automaton, i.e. the su-x automaton of the reverse pattern is fed with
the characters in the text window read backward. This backward search ends in two possible forms:
1. We fail to recognize a factor, i.e we reach a window letter  that makes the automaton run
out of active states. This means that the su-x of the window we have read is not anymore a
factor of P . Figure 4 illustrates this case. We then shift the window to the right, its starting
position corresponding to the position following the letter  (we cannot miss an occurrence
because in that case the su-x automaton would have found a factor of it in the window).
New search
Window
Search for a factor with the DAWG
Fail to recognize a factor at .
New window
Secure shift

Figure

4: Basic search with the su-x automaton.
2. We reach the beginning of the window, therefore recognizing the pattern P since the length-m
window is a factor of P (indeed, it is equal to P ). We report the occurrence, and shift the
window by 1.
The bit-parallel simulation works as follows. Each time we position the window in the text we
initialize scan the window backward. For each new text character read in the window
we update D. If we run out of 1's in D then there cannot be a match and we suspend the scanning
and shift the window. If we can perform m iterations then we report the match.
We use a mask B which for each character c stores a bit mask. This mask sets the bits
corresponding to the positions where the reversed pattern has the character c (just as in the Shift-
And algorithm). The formula to update D is
BNDM is not only faster than Shift-Or and BDM (for 5  m  100 or so), but it can accommodate
all the extensions mentioned. Of particular interest to this work is that it can easily deal
with classes of characters by just altering the preprocessing, and it is by far the fastest algorithm
to search this type of patterns [18, 19].
Note that this type of search is called \backward" scanning because the text characters inside
the window are read backwards. However, the search progresses from left to right in the text as
the window is shifted.
3 Regular expression searching
The usual way of dealing with an expression with character classes and bounded gaps is actually
to search it as a full regular expression (RE) [13, 22]. A gap of the form x(a; b) is converted into a
letters x followed by b a subexpressions of the form (xj").
The traditional technique [23] to search an RE of length O(m) in a text of length n is to
convert the expression into a nondeterministic nite automaton (NFA) with O(m) nodes. Then,
it is possible to search the text using the automaton at O(mn) worst case time, or to convert the
NFA into a deterministic nite automaton (DFA) in worst case time O(2 m ) and then scan the text
in O(n) time.
Some techniques have been proposed to obtain a good tradeo between both extremes. In
1992, Myers [15] presented a four-russians approach which obtains O(mn= log n) worst-case time
and extra space. Other simulation techniques that aim at good tradeos based on combinations of
DFAs and bit-parallel simulation of NFAs are given in [26, 20].
There exist currently many dierent techniques to build an NFA from a regular expression R.
The most classical one is Thompson's construction [23], which builds an NFA with at most 2m
states (where m is counted as the number of letters and "'s in the RE). A second one is Glushkov's
construction, popularized by Berry and Sethi in [4]. The NFA resulting of this construction has
the advantage of having just m+ 1 states (where m is counted as the number of letters in the RE).
A lot of research on Gluskov's construction has been pursued, like [6], where it is shown that
the resulting NFA is quadratic in the number of edges in the worst case. In [12], a long time open
question about the minimal number of edges of an NFA (without -transition) with linear number
of states was answered, showing a construction with O(m) states and O(m(log m) 2 ) edges, as well
as a lower bound of O(m log m) edges. Hence, Glushkov construction is not space-optimal. Some
research has been done also to try to construct directly a DFA from a regular expression, without
constructing an NFA, such as [8].
We show in Figure 5 the Thompson and Gluskov automata for an example CBG a b c
e, which we translate into the regular expression a  b  c  x  (xj")  (xj")  d  e.
Both Thompson and Gluskov automata present some particular properties. Some algorithms
like [15, 26] make use of Thompson's automaton properties and some others, like [20], make use of
Gluskov's ones.
Finally, some work has been pursued in skipping characters when searching for an RE. A simple
heuristic that has very variable success is implemented in Gnu Grep, where they try to nd a plain
substring inside the RE, so as to use the search for that substring as a lter for the search of the
complete RE. In [24] they propose to reduce the search of a RE to a multipattern search for all
the possible strings of some length that can match the RE (using a multipattern Boyer-Moore like
algorithm). In [20] they propose the use of an automaton that recognizes reversed factors of strings
accepted by the RE (in fact a manipulation of the original automaton) using a BNDM-like scheme
to search those factors (see Section 2).
However, none of the presented techniques seems fully adequate for CBGs. First, the algorithms
are intrinsequely complicated to understand and to implement. Second, all the techniques perform
poorly for a certain type of REs. The \di-cult" REs are in general those whose DFAs are very
large, a very common case when translating CBGs to REs. Third, especially with regard to the
sizes of the DFAs, the simplicity of CBGs is not translated into their corresponding REs. For
example, the CBG \[RK] x(2; considered in the Introduction yields a
DFA which needs about 600 pointers to be represented.
At the very least, resorting to REs implies solving a simple problem by converting it into a more
x
e
e
e
x
e
e
e
d e14 15 1611785(a) Thompson construction
a b c x x x d e
d
(b) Gluskov construction

Figure

5: The two classical NFA constructions on our example a  b  c  x  (xj")  (xj")  d  e. We
recall that x matches the whole alphabet . The Gluskov automaton is " free, but both present
some di-culties to perform an e-cient bit-parallelism on them.
complicated one. Indeed, the experimental time results when applied to our CBG expressions are
far from reasonable in regard of the simplicity of CBGs, as seen in Section 7. As we show in that
section, CBGs can be searched much faster by designing specic algorithms for them. This is what
we do in the next sections.
4 A forward search algorithm for CBG patterns
We express the search problem of a pattern with classes of characters and gaps using a non-deterministic
automaton. Compared to the simple automaton of Section 2, this one permits the
existence of gaps between consecutive positions, so that each gap has a minimum and a maximum
length. The automaton we use does not correspond to any of those presented in Section 3, although
the functionality is the same.

Figure

6 shows an example for the pattern a b c x(1; e. Between the letters c and
d we have inserted three transitions that can be followed by any letter, which corresponds to the
maximum length of the gap. Two "-transitions leave the state where abc has been recognized and
skip one and two subsequent edges, respectively. This allows skipping one to three text characters
before nding the cd at the end of the pattern. The initial self-loop allows the match to begin at
any text position.
To build the NFA, we start with the initial state S 0 and read the pattern symbol by symbol (a
being a class of characters or a gap 2 ). We add new automaton edges and states for each
new symbol read. If after creating state S i the next pattern symbol is a class of characters C we
create a state S i+1 and add an edge labeled C from state S i to state S i+1 . On the other hand, if the
new pattern symbol is a gap of the form x(a; b), we create b states S labeled
2 Note that x and single letters can also be seen as classes of characters.
a b c x x x d e
e
e
Figure

Our non-deterministic automaton for the pattern a b c x(1;
linking state S j to S j+1 for Additionally, we create b a "-transitions from
state S i to states S . The last state created in the whole process is the nal state.
We are now interested in an e-cient simulation of the above automaton. Despite that this
is a particular case of a regular expression, its simplicity permits a more e-cient simulation. In
particular, a fast bit-parallel simulation is possible.
We represent each automaton state by a bit in a computer word. The initial state is not
represented because it is always active. As with the normal Shift-And, we shift all the bits to the
left and use a table of masks B indexed by the current text character. This accounts for all the
arrows that go from states S j to S j+1 .
The remaining problem is how to represent the "-transitions. For this sake, we chose 3 to
represent active states by 1 and inactive states by 0. We call \gap-initial" states those states S i
from where an "-transition leaves. For each gap-initial state S i corresponding to a gap x(a; b),
we dene its \gap-nal" state to be S i+b a+1 , i.e. the one following the last state reached by an
"-transition leaving S i . In the example of Figure 6, we have one gap-initial state (S 3 ) and one
gap-nal state (S 6 ).
We create a bit mask I which has 1 in the gap-initial states, and another mask F that has 1 in
the gap-nal states. Then, if we keep the state of the search in a bit mask D, then after performing
the normal Shift-And step, we simulate all the "-moves with the operation
The rationale is as follows. First, D & I isolates the active gap-initial states. Subtracting this
from F has two possible results for each gap-initial state S i . First, if it is active the result will have
1 in all the states from S i to S i+b a , successfully propagating the active state S i to the desired
target states. Second, if S i is inactive the result will have 1 only in S i+b a+1 . This undesired 1
is removed by operating the result with \&  F ". Once the propagation has been done, we or
the result with the already active states in D. Note that the propagations of dierent gaps do not
interfer with each other, since all the subtractions have local eect.
Let us consider again our example of Figure 6. The corresponding I and F masks are 00000100
and 00100000, respectively (recall that the bit masks are read right-to-left). Let us also consider that
we have read the text abc, and hence our D mask is 00000100. At this point the "-transitions should
take eect. Indeed, ((F (D &
where states S 3 , S 4 and S 5 have been activated. If, on the other hand, the
propagation formula yields ((00100000 00000000) & nothing changes.

Figure

7 shows the complete algorithm. For simplicity the code assumes that there cannot be
gaps at the beginning or at the end of the pattern (which are meaningless anyway). The value
(maximum length of a match) is obtained in O(m) time by a simple pass over the pattern P ,
summing up the maximum gap lengths and individual classes (recall that m is the number of
symbols in P ). The preprocessing takes O(Ljj) time, while the scanning needs O(n) time. If
3 It is possible to devise a formula for the opposite case, but unlike Shift-Or, it is not faster.
however, we need several machine words for the simulation, which thus takes O(ndL=we)
time.
Search (P 1:::m ,T 1:::n )
Preprocessing */
maximum length of a match
for c 2  do B[c] 0 L
I 0 L , F 0 L
if P j is of the form x(a; b) then /* a gap */
I I j (1 << (i 1))
else /* P j is a class of characters */
for
final state */
Scanning */
if report a match ending at

Figure

7: The forward scanning algorithm.
5 A backward search algorithm for CBG patterns
When the searched patterns contain just classes of characters, the backward bit-parallel approach
(see Section 2) leads to the fastest algorithm BNDM [18, 19]. The search is done by sliding over the
text (in forward direction) a window that has the size of the minimum possible alignment ('). We
read the window backwards trying to recognize a factor of the pattern. If we reach the beginning
of the window, then we found an alignment. Else, we shift the window to the beginning of the
longest factor found.
We extend now BNDM to deal with CBGs. To recognize all the reverse factors of a CBG, we
use quite the same automaton built in Section 4 on the reversed pattern, but without the initial
self-loop, and considering that all the states are active at the beginning. We create an initial state
I and "-transitions from I to each state of the automaton. Figure 8 shows the automaton for the
pattern a b c x(1; read by this automaton is a factor of the CBG as long
as there exists at least one active state.
a b c x x x d e
e
e
e
e
e
e
e
ee
e
I

Figure

8: The non-deterministic automaton built in the backward algorithm to recognize all the
reversed factors of the CBG a b c x(1;
The bit-parallel simulation of this automaton is quite the same as that of the forward automaton
(see Section 4). The only modications are (a) that we build iton P r , the reversed pattern; (b)
that the the bit mask D that registers the state of the search has to be initialized with
to perform the initial "-transitions; and (c) that we do not or D with 0 L 1 1 when we shift it, for
there is no more initial loop.
The backward CBG matching algorithm shifts a window of size ' along the text. Inside each
window, it traverses backward the text trying to recognize a factor of the CBG (this is why the
automaton that recognizes all the factors has to be built on the reverse pattern P r ).
If the backward search inside the window fails (i.e. there are no more active states in the
backward automaton) before reaching the beginning of the window, then the search window is
shifted to the beginning of the longest factor recognized, exactly like in the rst case of the classic
BNDM (see Section 2).
If the begining of the window is reached with the automaton still holding active states, then
some factor of length ' of the CBG is recognized in the window. Unlike the case of exact string
matching, where all the occurrences have the same length of the pattern, this does not automatically
imply that we have recognized the whole pattern. We need a way to verify a possible alignment
(that can be much longer than ') starting at the beginning of the window. So we read the characters
again from the beginning of the window with the forward automaton of Section 4, but without the
initial self-loop. This forward verication ends when (1) the automaton reaches its nal state, in
which case we found the pattern; (2) there are no more active states in the automaton, in which
case there is no pattern occurrence starting at the window. As there is no initial loop, the forward
verication surely nishes after reading at most L characters of the text. We then shift the search
window one character to the right and resume the search.

Figure

9 shows the complete algorithm. Some optimizations are not shown for clarity, for
example many tests can be avoided by breaking loops from inside, some variables can be reused,
etc.
The worst case complexity of the backward scanning algorithm is O(nL), which is quite bad in
theory. In particular, let us consider the maximum gap length G in the CBG. If G  ', then every
text window of length ' is a factor of the CBG, so we will surely traverse all the window during
the backward scan and always shift in 1, for a complexity of
n') at least. Consequently, the
backward approach we have presented must be restricted at least to CBGs in which G < '.
Backward search (P 1:::m ,T 1:::n )
maximum length of a match /* Preprocessing */
minimum length of a match
if P j is of the form x(a; b) then /* a gap */
I f I f j (1 << (i 1)) , I b I b j (1 << (L (i
do
else /* P j is a class of characters */
for do
final state for the forward scan*/
pos 0 /* Scanning */
while pos  n ' do
while D b 6= 0 L and j > 0
while D f 6= 0 L and pos
if
report a match beginning at pos
(D b << 1)

Figure

9: The backward scanning algorithm.
However, on the average, the backward algorithm is expected to be faster than the forward
one. The next section gives a good experimental criterion to know in which cases the backward
algorithm is faster than the forward one. The experimental search results (see Section 7) on the
database show that the backward algorithm is almost always the fastest.
6 Which algorithm to use ?
We have now two dierent algorithms, a forward and a backward one, so a natural question is
which one should be chosen for a particular problem. We seek for a simple criterion that enables
us to choose the best algorithm.
As noted at the end of the previous section, the backward algorithm cannot be e-ciently
applied if the length G of the maximum gap in the pattern exceeds ', the minimum length of a
string that matches the pattern. This is because the backward traversal in the window will never
nish before traversing the whole window (as any string of length '  G is a factor of a possible
pattern occurrence).
This can be carried on further. Each time we position a window in the text, we know that at
least G+ 1 characters in the window will be inspected before shifting. Moreover, the window will
not be shifted by more than ' G positions. Hence the total number of character inspections across
the search is at least (G which is larger than n (the number of characters inspected
by a forward scan) whenever ' < 2G + 1.
Hence, we dene (G 1)=' as a simple parameter governing most of the performance of the
backward scan algorithm, and predict that 0.5 is the point above which the backward scanning
is worse than forward scanning. Of course this measure is not perfect, as it disregards the eect
of other gaps, classes of characters and the cost of forward checking in the backward scan, but a
full analysis is extremely complicated and, as we see in the next section, this simple criterion gives
good results.
According to this criterion, we can design an optimized version of our backward scanning
algorithm. The idea is that we can choose the \best" prex of the pattern, i.e. the prex that
1)='. The backward scanning can be done using this prex, while the forward
verication of potential matches is done with the full pattern. This could be extended to selecting
the best factor of the pattern, but the code would be more complicated (as the verication phase
would have to scan in both directions, buering would be complicated, and, as we see in the next
section, the dierence is not so large.
7 Experimental results
We have tested our algorithms over an example of 1,168 PROSITE patterns [13, 11] and a 6
megabytes (Mb) text containing a concatenation of protein sequences taken from the TIGR Microbial
database. The set had originally 1,316 patterns from which we selected the 1,230 whose L
(maximum length of a match) does not exceed w, the number of bits in the computer word of our
machine. This leaves us with 93% of the patterns. From them, we excluded the 62 (5%) for which
G  ', which as explained cannot be reasonably searched with backward scanning. This leaves us
with the 1,168 patterns.
We have used an Intel Pentium III machine of 500 MHz running Linux. We show user times
averaged over 10 trials. Three dierent algorithms are tested: Fwd is the forward-scan algorithm
described in Section 4, Bwd is the backward-scan algorithm of Section 5 and Opt is the same Bwd
where we select for the backward searching the best prex of the pattern, according to the criterion
of the previous section.
A rst experiment aims at measuring the e-ciency of the algorithms with respect to the criterion
of the previous section. Figure 10 shows the results, where the patterns have been classied along
the x axis by their (G As predicted, 0.5 is the value from which Bwd starts to be
worse than Fwd except for a few exceptions (where the dierence is not so big anyway). It is also
clear that Opt avoids many of the worst cases of Bwd. Finally, the plot shows that the time of Fwd
is very stable. While the forward scan runs always at around 5 Mb/sec, the backward scan can be
as fast as 20 Mb/sec.
(G+1)/ell
secs/Mb
Bwd
(G+1)/ell
secs/Mb
Opt

Figure

10: Search times (in seconds per Mb) for all the patterns classied by their (G+ 1)=' value.
What

Figure

fails to show is that in fact most PROSITE patterns have a very low (G+ 1)='
value.

Figure

11 plots the number of patterns achieving a given search time, after removing a few
outliers (the 12 that took more than 0.4 seconds for Bwd). Fwd has a large peak because of its
stable time, while the backward scanning algorithms have a wider histogram whose main body is
well before the peak of Fwd. Indeed, 95.6% of the patterns are searched faster by Bwd than by
Fwd, and the percentage raises to 97.6% if we consider Opt. The plot also shows that there is little
statistical dierence between Bwd and Opt. Rather, Opt is useful to remove some very bad cases
of Bwd.
Our third experiment aims at comparing our search method against converting the pattern
to a regular expression and resorting to general regular expression searching. From the existing
algorithms to search for regular expressions we have selected the following.
Dfa: Builds a deterministic nite automaton and uses it to search the text.
Nfa: Builds a non-deterministic nite automaton and uses it to search the text, updating all the
states at each text position.
Myers: Is an intermediate between Dfa and Nfa [15], a non-deterministic automaton formed by a
few blocks (up to 4 in our experiments) where each block is a deterministic automaton over
a subset of the states. \(xj")" was expressed as \.?" in the syntax of this software.
Agrep: Is an existing software [26, 25] that implements another intermediate between Dfa and
Nfa, where most of the transitions are handled using bit-parallelism and the "-transitions
with a deterministic table. \(xj")" was expressed as \(.|"")" in the syntax of this software.
secs/Mb
frequency
Bwd
Opt

Figure

11: Histogram of search times for our dierent algorithms.
Grep: Is Gnu Grep with the option "-E" to make it accept regular expressions. This software
uses a heuristic that, in addition to (lazy) deterministic automaton searching, looks for long
enough literal pattern substrings and uses them as a fast lter for the search. The gaps
\x(a; b)" were converted to \.fa,bg" to permit specialized treatment by Grep.
BNDM: Uses the backward approach we have extended to CBGs, but adapted to general REs
instead [20]. It needs to build to deterministic automata, one for backward search and another
for forward verication
Multipattern: Reduces the problem to multipattern Boyer-Moore searching of all the strings of
length ' that match the RE [24]. We have used \agrep -f" as the multipattern search
algorithm.
To these, we have added our Fwd and Opt algorithms. Figure 12 shows the results. From the
forward scanning algorithms (i.e. Fwd, Dfa, Nfa and Myers, unable to skip text characters), the
fastest is our Fwd algorithm thanks to its simplicity. Agrep has about the same mean but much
more variance. Dfa suers from high preprocessing times and large generated automata. Nfa needs
to update many states one by one for each text character read. Myers suers from a combination
of both and shows two peaks that come from its specialized code to deal with small automata.
The backward scanning algorithms Opt and Grep (able to skip text characters) are faster than
the previous ones in almost all cases. Among them, Opt is faster on average and has less variance,
while the times of Grep extend over a range that surpasses the time of our Fwd algorithm for a
non-negligible portion of the patterns. This is because Grep cannot always nd a suitable ltering
substring and in that case it resorts to forward scanning. Note that BNDM and Multipattern have
been excluded from the plots due to their poor performance on this set of patterns.
Apart from the faster text scanning, our algorithms also benet from lower preprocessing times
when compared to the algorithms that resort to regular expression searching. This is barely noticeable
in our previous experiment, but it is important in a common scenario of the protein searching
problem: all the patterns from a set are searched inside a new short protein. In this case the
preprocessing time for all the patterns is much more important than the scanning time over the
(normally rather short) protein.
secs/Mb
frequency
Opt
Dfa
Nfa
Myers
Agrep
Grep

Figure

12: Histogram of search times for our best algorithms and for regular expression searching
algorithms.
We have simulated this scenario by selecting 100 random substrings of length 300 from our text
and running the previous algorithms on all the 1,168 patterns. Table 1 shows the time averaged
over the 100 substrings and accumulated over the 1,168 patterns. The dierence in favor of our new
algorithms is drastic. Note also that this problem is an interesting eld of research for multipattern
CBG search algorithms.
Algorithm Fwd Bwd Opt Dfa Nfa Myers Agrep Grep
Time

Table

1: Search time in seconds for all the 1,168 patterns over a random protein of length 300.
Conclusions
We have presented two new search algorithms for CBGs, i.e. expressions formed by a sequence
of classes of characters and bounded gaps. CBGs are of special interest to computational biology
applications. All the current approaches rely on converting the CBG into a regular expression
(RE), which is much more complex. Therefore the search cost is much higher than necessary for a
CBG.
Our algorithms are specically designed for CBGs and is based on BNDM, a combination of
bit-parallelism and backward searching with su-x automata. This combination has been recently
proved to be very eective for patterns formed by simple letters and classes of characters [18, 19].
We have extended BNDM to allow for limited gaps.
We have presented experiments showing that our new algorithms are much faster and more
predictable than all the other algorithms based on regular expression searching. In addition, we
have presented a criterion to select the best among the two that has experimentally shown to
be very reliable. This makes the algorithms of special interest for practical applications, such as
protein searching.
We plan to extend the present work by designing an algorithm able to skip characters and
that at the same time ensures a linear worst case time, and by extending the scope of the present
\optimized" algorithm so that it can select the best factor (not just the best prex) to search.
Other more challenging types of search are those allowing negative gaps and errors in the
matches (see, e.g. [16]). Our algorithms are especially easy to extend to permit errors and we are
pursuing in that direction.



--R

Text retrieval: Theory and practice.
A new approach to text searching.
Faster approximate string matching.
From regular expression to deterministic automata.
A fast string searching algorithm.

A generalized pro
From regular expression to DFA's using NFA's.
algorithms.
Speeding up two string-matching algorithms
The database
Juraj Hromkovi

Fast pattern matching in strings.

Approximate matching of network expressions with spacers.
A fast bit-vector algorithm for approximate pattern matching based on dynamic progamming

Fast and exible string matching by combining bit-parallelism and su-x automata
Fast regular expression matching.
On the multi backward dawg matching algorithm (MultiBDM).
Screening protein and nucleic acid sequences against libraries of patterns.
Regular expression search algorithm.
Taxonomies and toolkits of regular language algorithms.

Fast text searching allowing errors.

--TR
From regular expressions to deterministic automata
A Four Russians algorithm for regular expression pattern matching
A new approach to text searching
Fast text searching
Regular expressions into finite automata
Text algorithms
A fast bit-vector algorithm for approximate string matching based on dynamic programming
Programming Techniques: Regular expression search algorithm
Fast and flexible string matching by combining bit-parallelism and suffix automata
Text-Retrieval
Translating Regular Expressions into Small epsilon-Free Nondeterministic Finite Automata
Fast Regular Expression Search
A Bit-Parallel Approach to Suffix Automata

--CTR
Alberto Policriti , Nicola Vitacolonna , Michele Morgante , Andrea Zuccolo, Structured motifs search, Proceedings of the eighth annual international conference on Resaerch in computational molecular biology, p.133-139, March 27-31, 2004, San Diego, California, USA
Gonzalo Navarro , Mathieu Raffinot, Fast and flexible string matching by combining bit-parallelism and suffix automata, Journal of Experimental Algorithmics (JEA), 5, p.4-es, 2000
bit-parallelism;information retrieval;PROSITE;pattern matching;computational biology