Mireille Régnier
email: mireille.regnier@inria.fr

Zara Kirakosyan

Evgenia Furletova

Mikhail Roytberg
email: mroytberg@gmail.com

A Word Counting Graph

We study methods for counting occurrences of words from a given set H over an alphabet V in a given text. All words have the same length m. Our goal is the computation of the probability to find p occurrences of words from a set H in a random text of size n, assuming that the text is generated by a Bernoulli or Markov model. We have designed an algorithm solving the problem; the algorithm relies on traversals of a graph, whose set of vertices is associated with the overlaps of words from H. Edges define two oriented subgraphs that can be interpreted as equivalence relations on words of H. Let P(H) be the set of equivalence classes and S be the set of other vertices. The run time for the Bernoulli model is

O(np(|P(H)|+|S|)) time and the space complexity is O(pm|S|+|P(H)|).

In a Markov model of order K, additional space complexity is O(pm|V | K ) and additional time complexity is O(npm|V | K ). Our preprocessing uses a variant of Aho-Corasick automaton and achieves O(m|H|) time complexity. Our algorithm is implemented and provides a significant space improvement in practice. We compare its complexity to the additional improvement due to AhoCorasick minimization.

Introduction

Studies on word probabilities started as early as Eighties with the seed paper [START_REF] Guibas | String Overlaps, Pattern Matching and Nontransitive Games[END_REF]. A recent interest arose from applications to computational biology [GKM00,Lat04,GK97,PMG00,VM03]. Numerous statistical softwares have been designed recently [CFG + 05,TML + 02,BPL + 04] to extract "In Silico" exceptional words , i.e. words that are either overrepresented or underrepresented in genomes. An international competition was organized by M. Tompa [TLB + 05] to evaluate their capabilities and weaknesses. All softwares combine an algorithm to extract candidate motifs and a statistical criterium to evaluate overrepresented or underrepresented motifs. Sensitivity and selectivity of such criteria turn out to be crucial, as well as the speed and easiness of computation. A survey on motif searching can be found in [START_REF] Das | A survey of DNA motif finding algorithms[END_REF].

We address here the following problem, that is fundamental to assess significance. Given the alphabet V and a set H of words on alphabet V , all words in H have the same length m. Our aim is to compute the probability to find exactly p occurrences of a word from a set H in a text of size n. Below, t [p] n (H) denotes this probability. One assumes the text is randomly generated according to a Bernoulli or Markov model of order K. Naive solutions to this problem when p = 1 [START_REF] Chrysaphinou | The occurrence of sequence of patterns in repeated dependent experiments[END_REF] lead to a O(n|V| K |H| 2 ) time complexity. Recent states of the art of various improvements can be found in [START_REF] Szpankowski | Average Case Analysis of Algorithms on Sequences[END_REF][START_REF] Lothaire | Applied Combinatorics on Words[END_REF]. On the one hand, the language approach defined in [START_REF] Régnier | On Pattern Frequency Occurrences in a Markovian Sequence[END_REF] allows for an elimination of |V| K multiplicative factor in [START_REF] Régnier | A Unified Approach to Word Occurrences Probabilities[END_REF]. On the other hand, several approximations can be derived for t [1] n (H). They imply, at some stage, the computation of all possible overlaps of two words of H or a formal inversion of a |H| × |H| matrix of polynoms. Therefore, time complexity is O(|H| 2 ). A recent algorithm [START_REF] Hertzberg | Finding motifs in promoter regions[END_REF] allows for the computation of the generating function n≥0 t [1] n (H)z n in O(nm|H|) time and O(m|H|) space complexity. Interestingly, O(nm|H|) time complexity outperforms O(|H| 2 ) complexity for most practical values of n. Indeed, sets may be rather big [START_REF] Touzet | Efficient and accurate p-value computation for position weight matrices[END_REF], especially when they are defined through a Position Specific Scoring Matrix or PSSM [START_REF] Stormo | DNA binding sites: representation and discovery[END_REF]. Other algorithms simulate an automaton. This automaton is derived from a transition study [START_REF] Crochemore | Waiting time and complexity for matching patterns with automata[END_REF] or language equations in [START_REF] Nicodème | Motif statistics[END_REF]; it is embedded in a Markov chain, using sparse matrices in [START_REF] Fu | Distribution theory of runs and patterns and its applications. A finite Markov chain imbedding approach[END_REF][START_REF] Nuel | Effective p-value computations using finite markov chain imbedding (fmci): application to local score and to pattern statistics[END_REF]. Algorithm AhoPro [BCR + 07] addresses a more general problem. It computes the probability to find several occurrences (up to fixed bound p i for set H i ) in several sets H 1 , • • • , H q . It simulates an Aho One common feature of these approaches is their easy extension to the Markov model. The multiplicative factor |V | K in time complexity [START_REF] Chrysaphinou | The occurrence of sequence of patterns in repeated dependent experiments[END_REF] becomes an additive factor, except for [START_REF] Nicodème | Motif statistics[END_REF]. The main difference comes from the space complexity. As mentioned in [START_REF] Ribeca | Faster exact Markovian probability functions for motif occurrences: a DFA-only approach[END_REF], Markov chain embeddings may be costly, due to matrices sparsity. Although automaton implementations are less sparse, space complexity remains an actual drawback [BCR + 07].

One possible way to reduce space requirement is the classical minimization of the underlying automaton. This is realized, for p occurrences in a single set H, in [START_REF] Nuel | Pattern markov chains: optimal markov chain embedding through deterministic finite automata[END_REF], with an O(np|S||V |) time complexity. A recent publication [START_REF] Ribeca | Faster exact Markovian probability functions for motif occurrences: a DFA-only approach[END_REF] simulates the minimized automaton and implements a log n time complexity improvement, for a single set. In this paper, we propose an alternative modelling of word counting based on graphs that are related to overlaps of words of the set. We define a partition of set H into equivalence overlap classes that we represent in graphs and we show that the set of equivalence overlap classes, denoted P(H), is efficiently computed in a preprocessing step from a variant of classic Aho-Corasick tree, that can be built in O(m|H|) time. Let S denote the set of internal nodes, that are associated to proper overlaps. We also show that probabilities t

[p]

n (H) satisfy induction equations that only depend on these overlap classes. A simple algorithm follows, that relies on classical tree traversals with simple additional data structures that optimize memory management. As a whole, this algorithm improves on [NSF02,CS03,HZGD05,Nue06,BCR + 07] as it achieves a O(np(|P(H)|+|S|)) time computation and O(pm|S|) space complexity with a smaller set S. Here, S is the set of vertices of the overlap graph that are not in P(H). Finally, this algorithm can be extended to address the same features as AhoPro. This drastic space improvement on space and time complexity is discussed in 5. We also compare it with the alternative minimization approach [START_REF] Nuel | Pattern markov chains: optimal markov chain embedding through deterministic finite automata[END_REF]. Finally, we suggest on one example a possible combination with Aho-Corasick minimization.

Overlap Graphs

We will use terms word and text as synonyms; informally, a text is long, and a word is short. A pattern H of length m is a set

H = {H 1 , • • • , H q } of
words such that all words have the same length m.

Given a word w, let |w| denote its length. Given two words w and t, one notes w ≺ t iff w is a proper prefix of t and w ⊂ t iff w is a proper suffix of t.

Definition 1. Given a pattern H over an alphabet V, a word w is a suffixprefix word for H iff exists H, F in H such as w ⊂ H and w ≺ F .

(1)

The set of suffixprefix words of a set H is called its overlap set and denoted OV (H).

In all examples, we use DNA alphabet V = {A, C, G, T }.

Example 1. Let H be the set

H = { H 1 = ACAT AT A, H 2 = AGACACA, H 3 = ATACACA, H 4 = ATAGATA , H 5 = CATTATA, H 6 = CTTTCAC, H 7 = CTTTCCA, H 8 = TACCACA} .
Overlap set is OV (H) = {AT A, ACA, T A, CA, A, AC, C, ǫ}. One has, for example, ACA ⊂ H 2 and ACA ≺ H 1 .

One observes that prefix relation and suffix relation define partial orders on OV (H) ∪ H. Clearly, the empty sequence ǫ is a prefix (respectively a suffix) of any suffixprefix and any word from H. Moreover, the set of prefixes (respectively suffixes) of a word H in H is totally ordered. Thus, it admits a maximal element in OV (H). Therefore, these relations naturally define equivalence relations between words in set H and, consequently, a partition of set H. Definition 2. Given a pattern H over an alphabet V, the left predecessor of a word H, noted lpred(H), is its longest prefix belonging to the overlap set OV (H). In other words, lpred(H) = max{w ≺ H, w ∈ OV (H)} .

(2)

Analogously, the right predecessor of H, noted rpred(H), is its longest suffix belonging to the overlap set OV (H). In other words,

rpred(H) = max{w ⊂ H, w ∈ OV (H)} . (3)
Two words H and F are said left (respectively right) equivalent iff they have the same left (respectively right) predecessor. For any pattern H, its left class is denoted H and its right class is denoted H. Two words H and F are said overlap equivalent if they are both left and right equivalent. The overlap class (i.e. the class of overlap equivalence) of a word H is denoted Ḣ. The set of all overlap classes is denoted P(H). One denotes lpred( Ḣ) (respectively rpred( Ḣ)) the common left (respectively right) predecessor of the patterns in Ḣ.

Example 2. In Example 1, H2 = H3 = H8 as ACA is their largest suffix in OV (H). There are four right classes CACA

= {H 2 , H 3 , H 8 }, CAT A = {H 1 , H 4 , H 5 }, CAC = {H 6 } and CCA = {H 7 }. H3 = H4 as AT A is their largest prefix in OV (H). There are six left classes CACA = {H 1 }, CAT A = {H 3 , H 4 }, CCA = {H 5 }, CT A = {H 8 }, CC = {H 6 , H 7 }, CA = {H 2 }.
There are eight overlap classes in P(H), that are the eight singletons of H. In other words, P(H) = H and the partition is trivial.

Definition 3. The left overlap graph is the oriented graph LOG H built on the set of vertices OV (H) ∪ P(H) with an edge from vertex s to vertex t iff:

s = lpred(t) = max{w ≺ t, w ∈ OV (H)} . (4)
The right overlap graph is the oriented graph ROG H built on the set of vertices OV (H) ∪ P(H) with an edge from vertex s to vertex t iff s = rpred(t) = max{w ⊂ t, w ∈ OV (H)} .

(5)

The overlap graph GOV H is the oriented graph LOG H ∪ ROG H .

As all words in an overlap class have the same predecessor in the prefix and suffix relations, this definition makes sense for vertices t that represent overlap classes. Moreover, one observes that all predecessors of a word are totally ordered and that the empty string is a minimal element for this order. Therefore, both left overlap graph and right overlap graphs are trees where the root is associated to the empty string ǫ that has no predecessor. The leaves are the elements of P(H). This definition implies the property below.

Property 1. Given a word H in H, or a class Ḣ in P(H), its ancestors in the left (respectively right) overlap graph are its prefixes (respectively suffixes) that belong to OV (H).

Example 3. In Example 1, ancestors of H 1 and H 6 in left overlap graph, depicted in Figure 1, distinct from the root are {ACA, AC, A} and {C} respectively. In the right overlap graph, depicted in Figure 2, their ancestors distinct from the root, are {AT A, T A, A} and {AC, C}. The paths associated to a node in LOG H (respectively ROG H ) are read from the top to the node (respectively, from the node to the top). [htb] Fig. 1. Left overlap graphs for Example 1. Round nodes are the elements of OV (H) and leaves are the elements of P(H). In that particular case, since P(H) = H, each leaf i is even simply the word Hi.

Remark 1. Let us call deep nodes are the predecessors of overlap classes. In automaton theory, deep nodes represent left and right quotients of the recognized language, e.g. H.

One observes that AC represents a right class and does not represent a left class. Nevertheless, the largest words in OV (H), e.g. ACA and AT A, represent a right class and a left class. Below, we define unions of overlap classes, as they appear in equations of words occurrences probabilities.

Definition 4. Given a set H over an alphabet V and a word w in OV (H), let Tw and Tw be the subtrees rooted in w in the left and right overlap graphs, respectively. One defines the subsets of P(H) :

Cw = Tw ∩ P(H) , (6) Cw = Tw ∩ P(H) . (7)
A set Cw is called a right union and a set Cw is called a left union.

Remark 2. Given a right union Cw and an overlap class Ḣ in P(H), the set Ḣ ∩ Cw is either empty, or equal to Ḣ when w is a suffix of any word in Ḣ. When w is a maximal suffixprefix, Cw and Cw are overlap classes.

It follows from these definitions that a right (respectively left) union contains the leaves of tree Tw (respectively Tw ). Therefore, Equations (8) and (9) follow immediately.

Cw = ∪ x∈ROGH,w⊆x Cx = ∪ w⊂H ( Ḣ) , (8) Cw = ∪ x∈LOGH,w x Cs = ∪ w≺H ( Ḣ) . (9) In Example 1, CA = CACA ∪ CAT A ∪ CCA = {H 1 , H 2 , H 3 , H 4 , H 5 , H 7 , H 8 } and CA = CACA ∪ CAT A ∪ CA = {H 1 , H 2 , H 3 , H 4 }. In Example 4, one has CACT A = Ġ2 ∪ Ġ7 .
Our bottom-up computations in 4.1 and 4.2 rely on these union properties.

Remark 3. The relation ∼ defined as x ∼ y iff xt ∈ H is equivalent to yt ∈ H is well-known in automata theory as right H-equivalence. There is a bijection between the states of the minimal automaton that recognizes H and classes of right equivalence.

Equations for words occurrences probabilities

The aim of this section is to establish our master Theorems 1 and 2 which state induction relations for word occurrence probabilities, in the Bernoulli and Markov model. They rely on a factorization lemma to achieve announced time and space complexities to be discussed in 5.1.

Basic Notations and Equations

One assumes the text T may be generated according to either one of the two models below.

(B) BERNOULLI MODEL: every symbol s of a finite alphabet V is created independently of the other symbols, with probability p s . (M) MARKOV MODEL: in a Markov model of order K, the probability of a symbol occurrence at some position in the text depends on the K previous symbols.

In a Markov model of order K, let P w (H) denote the probability to find H right of a given word w of length K. A Bernoulli model is viewed as a Markov model where K is 0. Given a word H, one denotes P(H) its probability in the Bernoulli model. Given a set of words F , one denotes P(F ) = H∈F P(H) and P w (F ) = H∈F P w (H) its probability in the Bernoulli and the Markov models, respectively.

Definition 5. Let H = {H 1 , H 2 , . . . , H q } be a given set of words with the same length m over an alphabet V.

One denotes t

[p] n (H) (respectively f [p]
n (H)) the probability to find exactly (respectively at least) p occurrences of H words in a text of size n.

One denotes r [p]

n (H) the probability to find word H in text T, with its end at position n, under the condition that exactly (p -1) other patterns from H appeared among positions 1,

• • • , n -1.
For a subset F of H , one denotes r

[p]
n (F ) the probability to find a word of F ending at position n in text T with exactly (p -1) F -words before it, i.e. r

[p] n (F ) = H∈F r [p] n (H).
Property 2. For any integers n and p, one has

t [p] n (H) = f [p] n (H) -f [p+1] n (H) , f [p] n (H) = n k=0 r [p] k (H)
Therefore, the computation of t

[i]
n follows from the computation of (r

[i]
n (H)) where H ranges over H. Definition 6. Given a word t and a prefix w of t, one denotes Φ w (t) the suffix of t that satisfies t = wΦ w (t). One denotes φ w (t) the probability of Φ w (t) in the Bernoulli model. By convention, φ w (t) = 0 if w is not a prefix of t.

Given a set F of words with a left common ancestor w, one defines

φ w (F ) = F∈F φ w (F) . (10)
Example 5. For word

H 1 from set H in Example 1, one has Φ ACA (H 1 ) = T AT A; then, in the Bernoulli model, φ ACA (H 1 ) = p 2 T p 2 A .
Proposition 1 below rewrites, using unions in overlap graphs defined above, a classical equation for words in H derived for p = 1 in [Szp01, [START_REF] Lothaire | Applied Combinatorics on Words[END_REF][START_REF] Hertzberg | Finding motifs in promoter regions[END_REF] for the Bernoulli model. This rewriting will incorporate classes of overlap equivalence in Theorems 1 and allows for a further generalization to Markov models in 2. These two theorems allow for an implementation based on overlap graphs with announced complexities.

Proposition 1. Assume a Bernoulli model. Let H be a given set of words and p be an integer. The probabilities (r

[1]
n (H)) n≥m where H ranges in H satisfy the induction relation:

r [1] n (H) = 1 - n-m k=1 r [1] k (H) P(H) - w∈LOGH\{ǫ},w≺H r [1] n-m+|w| ( Cw )φ w (H) . (11)
For any integer i satisfying 2 ≤ i ≤ p, the probabilities (r

[i]
n (H)) n≥m where H ranges in H satisfy the induction relations:

r [i] n (H) = n-m k=1 r [i-1] k (H) -r [i] k (H) P(H) (12) + w∈LOGH\{ǫ},w≺H r [i-1] n-m+|w| ( Cw ) -r [i] n-m+|w| ( Cw ) φ w (H) ,
with initial conditions:

r [i] 1 (H) = • • • = r [i] m-1 (H) = 0 , 1 ≤ i ≤ p , r [1] m (H) = P (H) , r [i] m (H) = 0 , 2 ≤ i ≤ p . Proof.
We propose a proof of this Proposition in the Bernoulli model, when p = 1, that extends to p occurrences, p ≥ 1. This Proposition is extended to overlap classes and to Markov model in Theorems 1 and 2. We study events that lead to a first occurrence and establish their probabilities. A word H is the first occurrence of H in text T at position n iff (i) word H occurs, ending at position n;

(ii) no H word occurred up to position n -m; (iii) no H word occurred in positions n -m + 1, • • • , n -1. The probability of (ii) is 1 -n-m k=1 r [1] k (H). Term (1 -n-m k=1 r [1]
k (H))P (H) is the probability of the simultaneous occurrence of (i) and (ii), as these events are independent in the Bernoulli model. One must substract the probability of the complementary event of (iii), conditioned by (i) and (ii). Complementary event of (iii) conditioned by (ii) is the union of (m -1) disjoint events, (E l ) 1≤l≤m-1 , where each event E l represents a first occurrence of a H-word ending at position nm + l. Each event E l contains (i). Now, event E l conditioned by (i) occurs iff a word F of H occurs at position nm + l when H ends at position n. This is satisfied iff exists w, with |w| = l and l = 0, that is a prefix of H and a suffix of F. Equivalently, w is a left ancestor of H different from the root and F belongs to Cw .

This reasoning steadily extends. To find an i-th occurrence ending at position n, (i -1) occurrences, are needed before nm; an i-th occurrence is forbidden before position n-m (condition (ii)), and between n-m+1 and n-1 (condition (iii)).

Example 6. Equation for word H 1 ∈ H is:

r [1] n (H 1 ) = [1 - n-7 k=1 r [1] k (H))]P (H 1 ) -r [1] n-6 ( CA )P (CAT AT A) - -r [1] n-5 ( CAC )P (AT AT A) -r [1] n-4 ( CACA )P (T AT A) .
As each word has no more than m ancestors, the recursive equations ( 11) and ( 12) provide an easy way to compute (r

[p]
n (H)) H∈H in O(npm|H|) time complexity. This complexity is achieved in [START_REF] Hertzberg | Finding motifs in promoter regions[END_REF] with a matrix and in [BCR + 07] with an Aho-Corasick-like automaton. In [START_REF] Nuel | Pattern markov chains: optimal markov chain embedding through deterministic finite automata[END_REF], the automaton is minimized, which yields a complexity O(np|V ||S|), where the size of the automaton is smaller. Overlap graphs provide an alternative improvement.

Overlap Graph Traversal

Our time complexity improvement, i.e. O(np(|P(H)| + |S|)), where S = OV (H), relies on a factorization property introduced below that reduces the computation to two graph traversals in Lemmas 1, 2 and 3. Space complexity issues will be discussed in Section 4 below.

Graph traversal Equations ( 11) and ( 12) are the same for all words H in H, up to the coefficients P(H) and φ w (H). Lemma 1 establishes that the computation of the second term in (11) or(12) for each word H or left class H only requires one parameter (ψ

[p]
n (t)) defined for its left predecessor t in LOG H and that this parameter can be computed in a traversal of the graph. Definition 7. In the Bernoulli model, one defines {(ψ

[i] n (w)) w∈OV (H)\{ǫ} } 1≤i≤p by the p top-down inductions ψ [i] n (w) = r [i] n-m+|w| ( Cw ), if lpred(w) = ǫ ψ [i] n (w) = ψ [i] n (lpred(w)) • φ lpred(w) (w) + r [i] n-m+|w| ( Cw ), otherwise . (13)
Lemma 1 establishes that ψ

[i]
n (w) represents the information on the past that is shared by all descendants of w.

Lemma 1. For any word H in H, and any left ancestor w of H such that w = ǫ, one has:

x∈OV (H)\{ǫ},x w r [i] n-m+|x| ( Cx )φ x (H) = ψ [i] n (w) • φ w (H) . ( 14
)
Any subset T of a left class H in H satisfies F∈T w∈OV (H)\{ǫ},w≺F r [i] n-m+|w| ( Cw )φ w (F) = ψ [i] n (t) • φ t (T ) , ( 15
)
where t is the common left predecessor.

Proof. Indeed, φ x (H) rewrites φ x (w)φ w (H). Therefore,

ψ [i]
n inductive definition allow to prove inductively, for any i in [1..p], that

w∈OV (H)\{ǫ},w≺H r [i] n-m+|w| ( Cw )φ w (H) = ψ [i] n (t) • φ t (H) , ( 16
)
where t is the left predecessor of H in LOG H . A summation over all words in a subset T of left class H and a factorization yields (15).

Second term in (11) or (12) may be computed once for any subset of words in a left class. Yet, probabilities computation for larger n implies to memorize separately right classes. Therefore, we split left classes with respect to right equivalence, which yields classes of P(H). A rewriting of Equation (8) leads to Lemma 2 below.

Lemma 2. Let w be a node in ROG H . For any integer i or n, probabilities r

[i] n ( Cw ) satisfy:

r [i] n ( Cw ) = x∈OV (H),w⊆x r [i] n ( Cx ) = Ḣ⊆ Cw r [i] n ( Ḣ) . ( 17
)
Corollary 1. The set {r

[i]
n ( Cw )} w∈OV (H) can be computed from {r Theorem 1. Let Ḣ be a class in P(H) and denote t the left predecessor of Ḣ. In the Bernoulli model, probabilities r

[i] n ( Ḣ) satisfy r [1] n ( Ḣ) = 1 - n-m k=1 r [1] k (H) P ( Ḣ) -ψ [1] n (t) • φ t ( Ḣ), (18)
and, for i ≥ 2,

r [i] n ( Ḣ) = n-m k=1 r [i-1] k (H) -r [i] k (H) P ( Ḣ) + ψ [i-1] n (t) -ψ [i] n (t) • φ t ( Ḣ), ( 19
)
with initial conditions

r [i] 1 (H) = • • • = r [i] m-1 (H) = 0 , 1 ≤ i ≤ p , r [1] m (H) = P (H) , r [i] m (H) = 0 , 2 ≤ i ≤ p .

Markov extension

Unlike the algorithms based on finite automata accepting the corresponding texts (see e.g. [NSF02,CS03,HZGD05,Nue08,BCR + 07,RR08]), our computation on the Markov model is a generalization of (11) that relies onto overlap graphs introduced above. An extension of the induction to the Markov model requires to extend the (ψ

[i]
n ) family for nodes w with a depth smaller than K. This is realized with a suitable partition of union Cw . We use the notations of Definition 6 and restrict the presentation to the case K ≤ m. Definition 8. Given a word w such that K ≤ |w|, one denotes suf K (w) its suffix of size K. Given a word α in V K , one denotes

H(α) = {H ∈ H; α = suf K (H)} .
Given a word t such that w is a prefix of t, one defines parameter φ w (t) by

φ w (t) = P sufK (w) (Φ w (t)) . ( 20
)
Remark 4. φ w (t) represents the probability to find Φ w (t) right after a w-occurrence.

In Example 1, φ ACA (H 1 ) = P CA (T )P AT (A)P T A (T )P AT (A) in the Markov model of order 2.

Definition 9. Given a set H and a Markov model of order K, with K ≤ m, one defines the right K-frontier of H, noted RF K (H), and the left K-frontier, noted LF K (H), by:

RF K (H) = {w ∈ OV (H); |rpred(w)| < K ≤ |w|} , (21)
LF K (H) = {w ∈ OV (H); |lpred(w)| < K ≤ |w|} . ( 22
)
The set of right K-leaves, noted RL K (H), and the set of left K-leaves, noted LL K (H), are defined as:

RL K (H) = { Ḣ ∈ P(H); |rpred( Ḣ)| < K} , (23)
LL K (H) = { Ḣ ∈ P(H); |lpred( Ḣ)| < K} . ( 24
)
Example 7. In Example 1, the right 3-frontier is {ACA, AT A} and the right 3-leaves are Ḣ6 and Ḣ7 .

The right K-frontier and the set of right K-leaves allow to define for every word w such that |w| < K, a natural partition of each union Cw defined by the successors of w in ROG H that belong to these two sets.

Definition 10. Given a word w in OV (H) \ {ǫ} such that |w| < K, one defines a subset S K (w) of V K as

S K (w) = t∈RFK (H)∪RLK(H),w⊂t {suf K (t)} . ( 25
)
Given a word w in RF K (H) ∪ RL K (H), one denotes For instance, it follows from Example 8 that CCA = CACA ∪ {H 7 }.

S K (w) = {suf K (w)} .
Definition 11. Given a word w in OV (H) \ {ǫ} satisfying |w| < K, one defines for each α in S K (w):

r [i] n,α (w) = {t∈RFK (H);w⊆rpred(t),α⊆t} r [i] n ( Ct ) + { Ḣ⊂RLK (H);w⊆rpred( Ḣ),α⊆ Ḣ} r [i] n ( Ḣ) .
(26) By convention, r

[i] n,α (w) = 0 if α ∈ V K \ S K (w).
Remark 6. It is guaranteed that at least one of the two sums contribute, and that w ⊂ α.

We now show how this knowledge on the past allows for the computation of Equations ( 11) and (12).

Definition 12. Given a word w in OV (H)\{ǫ} satisfying |w| < K, one denotes SP K (w) the subset of V K defined inductively as follows.

SP K (w) = S K (w) if lpred(w) = ǫ S K (w) ∪ {α ∈ V K ; S [α] (w) = ∅} otherwise , (27)
where n,α (w)) α∈SPK (w) .

S [α] (w) = {β ∈ SP K (lpred(w)); α = suf K (β • Φ lpred(w) (w))} . (28
ψ [p] n,α (w) = r [p] n-m+|w|,α (w) if lpred(w) = ǫ β∈S [α] (w) ψ [p] n,β (x)P β (Φ x (w)) + r [p] n-m+|w|,α (w) otherwise (29) If |w| ≥ K, one defines a single function ψ [p] n (w). ψ [p] n (w) = r [p] n-m+|w| ( Cw )+ β∈S [suf K (w)] (w) ψ [p] n,β (x)P β (Φ x (w)) if w ∈ LF K (H) ψ [p] n (x) • φ x (w) otherwise . ( 30
)
Example 10. Let us use (26), ( 29) and (30) in Example 1.

(i) Let w be A. As lpred(A) = ǫ, one applies the first equation in (29) for α ranging in S 3 (A). Right members are computed through (26) which yields ψ

[p] n,ACA (A) = r [p] n-6 (H 2 ) + r [p] n-6 (H 3 ) + r [p] n-6 (H 8 ), ψ [p] n,AT A (A) = r [p] n-6 (H 1 ) + r [p] n-6 (H 4 ) + r [p] n-6 (H 5 ) and ψ [p] n,CCA (A) = r [p] n-6 (H 7 ). (ii) One uses (29) to compute ψ [i] n,T AC (AC) and ψ [i]
n,CAC (AC). For instance,

ψ [i] n,CAC (AC) = ψ [i] n,ACA (A)•P ACA (C)+ψ [i] n,CCA (A)•P CCA (C)+r [i] n-5,CAC (AC) ,
where, using (26), r

[i] n-5,CAC (AC) = r [i] n-5 ( Ḣ6 ).
(iii) Word A is the left predecessor of AT A that belongs to the right 3-frontier.

Therefore, (30) yields

ψ [p] n (AT A) = ψ [p] n,ACA (A)P ACA (T A) + ψ [p] n,AT A (A)P AT A (T A) + ψ [p] n,CCA (A)P CCA (T A) + r [p] n-4 (H 1 ) + r [p] n-4 (H 4 ) + r [p]
n-4 (H 5 ) . Lemma 1 can now be rewritten into Lemma 3 below that steadily yields Theorem 2. Lemma 3. Any leaf class Ḣ in P(H) with left predecessor t satisfies w∈LOGH\{ǫ},w≺H

r [p] n-m+|w| ( Cw )φ w ( Ḣ) = ψ [p] n (t) • φ t ( Ḣ) if |t| ≥ K , (31)
= α∈V K ,t⊂α ψ [p] n,α (t) • φ t ( Ḣ) if |t| < K . ( 32
) Definition 14. Let f [p]
k (α) be the probability that a text of size k, k ≥ m, ending with suffix α in V K , contains at least p occurrences of words from H.

Lemma 4. The probabilities f

[p] k (α) satisfy the following induction

f [p] k (α) = β∈V K f [p] k-1 (β) • P β (α) + r [p] k (H(α)) , (33)
with the initial condition

f [p] m (α) = r [p]
m (H(α)) . Theorem 2. Let Ḣ be a class in P(H) and t be its left predecessor. In the Markov model, probabilities r

[i] n ( Ḣ(β)) are equal to α∈V K (f [i-1] n-m (α)-f [i] n-m (α))P α ( Ḣ(β))+ (ψ [i-1] n (t) -ψ [i] n (t)) • φ t ( Ḣ) if |t| ≥ K α∈V K (ψ [i-1] n,α (t) -ψ [i] n,α (t)) • φ t ( Ḣ) if Ḣ ⊂ LL K (H) (34) with initial conditions r [i] 1 (H) = • • • = r [i] m-1 (H) = 0 , 1 ≤ i ≤ p , r [1] m (H) = P (H) , r [i] m (H) = 0 , 2 ≤ i ≤ p ,

and convention ψ

Basic Algorithm

We describe a procedure to compute the probabilities of words occurrences in texts. Our input is a set of words H. Our output is the set of probabilities (r

[i]
n (H)) 1≤i≤p for a given position n. Overlap graph modelling provides a straighforward but efficient algorithm.

Overlap Graphs Construction

Our preprocessing step builds right and left overlap graphs and partition P(H).

It relies on a tree T H built with Aho-Corasick algorithm [START_REF] Aho | Efficient String Matching[END_REF]. A basic feature of Aho-Corasick is the on-line construction of so-called suffix links. Given a word s in V * , suf(s) denotes the largest suffix of s that is a proper prefix of some word from the set H. Below, we identify each node or leaf with the word defined by the path from the root. A suffix link is a link from a node s to node suf(s).

Right overlap graph

We start with the right overlap graph. According to Definition 1, a node in T H belongs to OV (H) iff there exists a sequence of suffix links from a leaf to this node. Therefore, a bottom-up traversal of T H according to the suffix links allows one to find out the nodes from OV (H) and to construct ROG H . See Figure 3.

Left overlap graph To link the nodes in OV (H) with the links for LOG H , one can use a depth-first traversal of T H . Partition Thanks to the order of AC tree, a depth-first traversal of LOG H , MaxSufPref, achieves a partition of H into P(H). As all words of a class are left equivalent, it is enough to identify below each deep node x all words that are right equivalent and number the designed classes. To achieve this linearly, one maintains in each internal node s the class number i(s) of the last visited leaf H in H satisfying suf(H) = s. One achieves an increasing numbering; let j denote the number of the last class created before the visit of leaves below x. When a leaf H is visited, an equivalent leaf has been previously visited iff i(suf(H)) > j. In this case, leaf H is addressed to class i(suf(H)). Otherwise, it is given the next available class number k and i(suf(H)) is updated to k. . Once these steps have been performed, tree T H is not needed any more and space can be released.

Markov model

Algorithm and basic data structures

Our algorithm computes inductions ( 19) and ( 34) in a depth-first traversal of LOG H . Bottom-up traversals of ROG H allow to manage memory: an extraction of suitable information is performed at the beginning of each cycle and an update is realized at the end of each cycle. For sake of clarity, we first describe the Bernoulli model.

Memory management One observes that results of previous computations that are used in (19) are

n-m k=1 (r n-m+|w| ( Cw )) 1≤i≤p . Therefore, one memorizes the p(m -|w|) values {r

[i-1] k (H) -r [i] k (H)) and (ψ [i] n (t)) that depend on (r [i] n-m+|w| ( Cw )) w∈LOGH\{ǫ} . 1. Values n-m k=1 r [i]
[i] n-m+|w| ( Cw ), • • • , r [i]
n-1 ( Cw )} 1≤i≤p in an array P robM ark of size p(m -|w|). 3. In each node w and in each leaf class Ḣ in LOG H \ {ǫ}, one memorizes probability φ x (w) or φ x ( Ḣ), where x is its father in LOG H .

Algorithm For any inductive step n, our algorithm executes:

1. In a bottom-up traversal of ROG H , including the root, P robM ainCalc extracts from P robM ark, for each internal node, the p values (r

[i]
n-m+|w| ( Cw )) 1≤i≤p . They are addressed in a field of each node. At the root, (r

[i] n (H)) are ex- tracted.
2. In a depth-first traversal of LOG H :

(a) when one visits an internal node, (ψ

[i]
n (w)) 1≤i≤p are computed according to (13);

(b) when a leaf class Ḣ is visited:

(i) compute r

[i] n ( Ḣ) using (19), for i in {1, • • • , p}; (ii) Add r [i]
n ( Ḣ) to a temporary variable, F irstT emp[i], in its predecessor in ROG H (a deep node). 3. In a bottom-up traversal of ROG H , update P robM ark for internal nodes, using F irstT emp according to (17). At the root ǫ, r

[i] n (C ǫ ) = r [i]
n (H) is added to SumP rob.

Markov model For memory management, it is now necessary to store values r

[i]
k (H(β)) for all words β in V K . Moreover, for a node w at depth smaller than K, one stores, for each i, non-zero values r

[i]
n,α (w). For a node w in the left K-frontier or above it, and for a leaf class Ḣ in the left K-leaves, one must memorize several values P β (Φ x (w)) or P β (Φ t ( Ḣ)) .

Procedures are slightly modified. In nodes above the right K-frontier, one extracts additional values, namely r

[i]
n,α (w), in step 1. In step 2, families (ψ

[i]
n (w)) computation relies on (29) and necessitates a preprocessing to memorize all φ x (w).

If a leaf class Ḣ is a left K-leaf, one computes r

[i]
n ( Ḣ) through (34) instead of (19). In step 3, the bottom-up traversal stops at the right K-frontier. n (w) computation or probability update is O(p|S|). In our current implementation, P robM ark is built for all internal nodes, which yields a O(mp|S|) space complexity. This already improves on recent algorithms [HZGD05,BCR + 07]. This upper bound can be improved. Indeed, given a node w at depth k, one needs only memorize (r

Complexity and experimental results

Complexity

Overlap graph complexity

[i]
n-l ( Cw )) when for 1 ≤ i ≤ p and 1 ≤ l ≤ mk. Therefore, space complexity is pD with

D = w∈S [m -|w|] . (35)
When a Markov model is used, additional space is needed. First, m values f Previous algorithms Exact computation of p occurrences probability depends on the text size n as a linear function O(n) or a logarithmic function O(log n). Let us mention that there also exist approximate computations that may be realized in constant time with some drawbacks on the space complexity or the tightness of the approximation. They are beyond the scope of this paper.

[i] k (α) use O(pm|V | K ) space. Then, for a node w, constraint w ⊂ α yields at most |V | K-|w| non-zero values r [i] n,α . Additional space is O(pK|V | K ).
We now discuss exact computation. All approaches, including automata or Markov Chain embedding [NSF02,CS03,FL03,Nue08], matrices [START_REF] Hertzberg | Finding motifs in promoter regions[END_REF] or languages [START_REF] Régnier | A Unified Approach to Word Occurrences Probabilities[END_REF] need to compute a set of linear equations of order m with constant coefficients. Therefore, theoretical complexity is known. Algorithms that are linear in n, such as RegExpCount, AhoPro or Spatt achieve a complexity p|S|n where |S| is the size of the structure used for the computation. Using the classical system reduction [START_REF] Régnier | A Unified Approach to Word Occurrences Probabilities[END_REF], it is theoretically possible to achieve a O(m p log n) algorithm, with a constant factor that depends of the data structure to be used. This optimization has been recently implemented in [START_REF] Ribeca | Faster exact Markovian probability functions for motif occurrences: a DFA-only approach[END_REF]. Nevertheless, one observes that the m p factor may represent a significant drawback. Therefore, counting algorithms are compared below on the basis of the two data structures used in the computation and the memorization.

[HZGD05] data structure is O(|H| log |H|). Markov Chain Embedding algorithms use very sparse matrices. Therefore, RegExpCount and AhoPro automata outperform them, and the minimization achieved in [START_REF] Nuel | Pattern markov chains: optimal markov chain embedding through deterministic finite automata[END_REF] is a further improvement. Overlap graph is an alternative approach. In both cases, there is no non-trivial upper bound for the ratio between |S| and the size of Aho-Corasick automata. Remark that one must take into account the alphabet size V in automata time complexity and a multiplicative factor m in overlap graph space complexity. When a minimization is very efficient, (pattern AN N N N N A), an overlap graph is less significantly reduced. Our last example suggests that building an overlap graph on a minimized automaton is an improvement and might be optimal. Indeed, for set G in Example 4, minimized Aho-Corasick automaton has 3 final states and 19 internal nodes. Overlap graph for this minimized automaton contains 4 classes and 4 internal nodes, associated to prefixes ǫ, C, CC = GG and CCCC. This difference is mainly due to backward links, that are necessary for a searching algorithm, but are unnecessary for counting algorithms, and therefore erased by overlap graphs.

Experiments

We have performed computer experiments to compare our approach and the approach using finite automaton representation of the corresponding set of text (e.g. [BCR + 07,Nue08]). We used a Intel Celeron 2.26 GHz with Windows XP. The complexity of automaton based methods can be described with the size |Σ| of minimal automaton accepting the set of texts containing the desired number of patterns. The proposed approach leads to other characteristics of the pattern:

(i) |S| is the number of overlaps; (ii) |P(H)| is the number of overlap classes, i.e. equivalence classes in the overlapbased partition of the given word set; (iii) D is the sum of differences m -|w| over all suffix-prefixes w defined in (35).

In our case, it was stated above in section 5.1) that the run-time is proportional to |S| + |P(H)| and the required space is proportional to D. 11) and ( 19)). We have generated 30 sets of 50k random words (k = 1, 2, • • • , 30) of length 8 and 12; the random words were generated in 4-letter alphabet {A, C, G, T } using Bernoulli model with equal probabilities of all letters. In the vast majority of cases, the number of overlap classes coincides with the initial number of words. We give the line only for the random patterns of length 8; the line for random patterns of length 12 coincides with it. Two lower lines corresponds to the patterns based on two position-specific scoring matrices (PSSM). Given a PSSM M, a threshold or cutoff s defines a set F (M, s), that consists of all the words in V m with a score greater than s. Different cutoffs were used to obtain patterns of different sizes. The PSSMs were created by Dan Pollard for Drosophila genes (http://www.danielpollard.com/matrices.html) and are given in Table 1. The PSSMs are referred to as PSSM-08 and PSSM-12; their lengths are 8 and 12, respectively. Cutoffs are chosen to ensure that the set sizes range from 1 to 1500. One can see that in case of non-random patterns usage of overlap classes may bring significant improvement. Tables 3, 4, 5 and 6 demonstrate results of experiments with the above four series of patterns. For each pattern we show its length and size, as well as above complexity measures related both to automaton-based and overlap-based approaches. Columns Time and Space represent time and space complexity of algorithms. For the automaton-based approach the run-time is proportional to The series of computer experiments allowed one to learn and compare the advantages of the approaches. For the overlap approach, the important characteristics of the pattern is number |S| of its suffix-prefixes; the characteristics is also important for various pattern matching methods. The experiments demonstrate that for random patterns the value |S| depend only of patterns size (i.e. number of words) but does not depend on pattern length (see Table 2 and Figure 4). The following Theorem justifies this observation.

Theorem 3. Let V be an alphabet and U (r; m) be a set of all sets (patterns) of r words with the same length m over an alphabet V ; all elements of U (r; m) are considered as having the same probability. Let further E(r, m) be the average number of suffix-prefixes (overlaps) of the patterns from U (r; m). Then

E(r, m) ≤ C • r (36)
where C does not depend on r and m.

The proof of the theorem is not given here due to lack of space and will be presented in a companion paper.

The above feature predetermines that the proposed approach exceeds the automaton one in case of random patterns (Figures 8 and9). For non-random patterns, the automaton approach due to general minimization procedure get benefits from the structure of pattern and in these cases the advantage of the overlap approach is not so clear; moreover, in some cases the automaton approach works better. It seems to be interesting to provide deeper investigation of the dependence of the methods behavior on the structure of patterns and to develop a new method combining the advantages of the approaches.

Conclusion

In this paper, we introduced a new concept of overlap graphs to count word occurrences and their probabilities. The concept led to a recursive equation that differs from the classical one based on the finite automaton accepting the proper set of texts. In case of many occurrences, our approach yields the same order of time and space complexity as the approach based on minimized automaton.

For random patterns, our approach has asymptotically better constants and this advantage is achieved for relatively small pattern length, e.g. for lengths around 10 (see Figures 8 and9). For non-random patterns, our approach gives results compatible with S-Patt [START_REF] Nuel | Pattern markov chains: optimal markov chain embedding through deterministic finite automata[END_REF]; the results depend on the structure of the pattern. Because of this, we here restricted ourselves with comparison of theoretical constants rather than run-times. The description of the algorithm in Sections 4 and 5 justifies this way of algorithms comparison. Remark that the constants well describe the space complexity of the algorithms. In the same time, our results are significantly better than the results of methods that do not implement the automaton minimization, e.g. [NSF02,CS03,HZGD05,Nue06,BCR + 07].

In the future, we plan to design a novel recursion equation combining advantages of overlap graphs and minimal automata. Other directions of improvement are extensions of the scheme allowing to count differently various patterns and implement probability distributions described with Hidden Markov Models.

  -Corasick like automaton. Its time and space complexity are O(n(|S| + |H|)|V| p i ) and O((|S| + |H|) × p i ), where |S| is the size of the automaton. A rough upper bound for this size is (m -1)|H|. This reduces to O(pn(|S| + |H|)) and O(p(|S| + |H|)) for p occurrences in a single set.

Example 4 .

 4 Let G be {ACN N N T A} where N stands for any symbol in alphabet V. Pattern G contains 4 3 = 64 words and its overlap set contains

Fig. 2 .

 2 Fig. 2. Right overlap graphs for Example 1.Subwords are read bottom-up

  )} x∈Dr by a bottom-up traversal of ROG H .

Example 8 .

 8 Let w be A in Example 1. Word t will range in {ACA, AT A, H 7 }. Therefore S 3 (A) = {ACA, AT A, CCA}. Let w be AC. Then word t ranges in {H 6 } and S 3 (AC) = {CAC}. Remark 5. With the notations above, one gets Cw = (∪ {t∈RFK (H);w⊆rpred(t)} Ct ) (∪ { Ḣ∈RLK(H);w⊆rpred( Ḣ)} ( Ḣ)) .

)

  Example 9. In Example 1, one has SP 3 (A) = S 3 (A) = {ACA, AT A, CCA}. Let w be AC. One has lpred(AC) = A, and α ranges over {CAC, T AC} when β ranges over SP 3 (A). Finally, S[CAC] (AC) = {ACA, CCA} and S [T AC] (AC) = {AT A} that are a partition of SP 3 (A). Finally, SP 3 (AC) = {CAC, T AC}.Definition 13. Let w be any word in OV (H) \ {ǫ}.If |w| < K, one defines a family (ψ[p]

Fig. 3 .

 3 Fig. 3. Aho-Corasick tree TH for set H in Example 1 used to build ROGH and LOGH in Figures 1 and 2. The nodes corresponding to OV (H) are marked with double circles. A leaf corresponding to the word Hi in H is labeled with the number i, 1 ≤ i ≤ 8. The dashed lines depicts suffix links needed to construct ROGH; the other Aho-Corasicks suffix links are omitted.

  Main preprocessing step is the computation of the right K-frontier and the right K-leaves, which is O(|V | K ). Aho-Corasick construction of the tree, including the suffix links, can be achieved in time and space O(m|H|) [CR02]. Subgraph extraction algorithms are classical graph traversals. They run with O(|T H |) time and space complexity and O(|T H |) is upper bounded by O(m|H|) [AC75]

k

  (H) where i ranges in {1 • • • p} are memorized in p global variables, e.g. an array SumP rob of p integers. 2. For each node w at depth |w| in LOG H \ {ǫ}, one needs, to perform computation at cycle n, values (r [i]

  Our algorithm achieves an overall O(np(|S|+ |P(H)|)) time complexity, where S = OV (H). Indeed, depth-first traversal at step 2 and bottom-up traversals at steps 1 and 3 yield a O(p|S|) time complexity. Computation of (19) is done for each overlap class in constant time. This yields an O(|P(H)|) time complexity in the Bernoulli model. Temporary memory for ψ [p]

  Finally, computation of (29) needs values P β (Φ x (w)). A node x needs at most |V | K-|x| values P β (Φ x (w)). Summing over at most |V | |x| nodes at level |x| yields an upper bound O(pK|V | K ). Therefore, overall additional space complexity is O(pm|V | K ). As each term is computed once at each inductive step, in O(1) time, additional time complexity is O(npm|V | K ).

First, we

  studied the dependence of the size |S| of overlap graph on the size and length of the pattern H. Data are given in Table 2 and depicted in Figure 4 Surprisingly, the average value of |S| for random patterns does not depend on the pattern length m while the size of the minimal automaton grows almost linearly with the growth of the pattern length (the number of words in the pattern being fixed). One can see that for reasonable pattern lengths (up to 24) and sizes (up to 1500 words) the value |S| (and even |S| + |P(H)|) is less than the number |Σ| of states of the corresponding minimized automaton. The independence of value |S| of the pattern length can be justified theoretically (see Theorem 3 in Section 6).

Fig. 4 .

 4 Fig. 4. Overlap graph size |S| and minimal automaton size |Σ|. Average values for random patterns of size 500. Blue diamond shapes represent |S| and purple squares represent |Σ|.

Figure 5

 5 Figure 5 demonstrates the impact of usage of overlap classes instead of individual words (cf. equations (11) and (19)). We have generated 30 sets of 50k random words (k = 1, 2, • • • , 30) of length 8 and 12; the random words were generated in 4-letter alphabet {A, C, G, T } using Bernoulli model with equal probabilities of all letters. In the vast majority of cases, the number of overlap classes coincides with the initial number of words. We give the line only for the random patterns of length 8; the line for random patterns of length 12 coincides with it. Two lower lines corresponds to the patterns based on two position-specific scoring matrices (PSSM). Given a PSSM M, a threshold or cutoff s defines a set F (M, s), that consists of all the words in V m with a score greater than s. Different cutoffs were used to obtain patterns of different sizes. The PSSMs were created by Dan Pollard for Drosophila genes (http://www.danielpollard.com/matrices.html) and are given in Table1. The PSSMs are referred to as PSSM-08 and PSSM-12; their lengths are 8 and 12, respectively. Cutoffs are chosen to ensure that the set sizes range from 1 to 1500. One can see that in case of non-random patterns usage of overlap classes may bring significant improvement.

Fig. 5 .

 5 Fig. 5. Number of overlap classes as a function of the number of words in the pattern. The data are given for three series of patterns: (1) random patterns of length 8; (2) patterns corresponding to two PSSMs with different cutoffs. The upper line (blue triangles) corresponds to random patterns.

Fig. 8 .

 8 Fig. 8. Time coefficients for the random patterns of lengths 8 and 12. The graphs for overlap coefficients of lengths 8 and 12 (the lowest lines) almost coincide

Table 2 .

 2 Average number of overlaps and size of minimized Aho-Corasick automaton for random patterns of different lengths (from 8 to 24) and sizes (from 100 to 1000 words). The number of overlaps does not depend on the pattern's length while the size of the automaton grows linearly with the length of the pattern

	100	200	500	1000
	m |Σ| |S| |Σ| |S| |Σ| |S| |Σ| |S|
	8 510 96 929 199 1960 515 3427 988
	12 906 98 1713 192 3976 518 7358 1006
	16 1302 107 2533 207 5956 503 11368 961
	20 1698 95 3307 190 7958 516 15415 987
	24 2105 92 4114 201 9983 512 19442 991

Table 3 .

 3 Characteristics of patterns related to PSSM-08 containing different numbers |H| of words. For the automaton approach, NAC is the size of Aho-Corasick automaton; Σ is the size of minimal automaton that represents the coefficient for space complexity; coefficient for time complexity T ime equals |Σ| × |V |. For the overlap approach we give the number of overlap classes, P(H); the number of overlaps S; time coefficient that is equal to |S| + |P(H)| and space coefficient Space from (35)

	Automaton approach Overlap approach
	|H| NAC |Σ|	Time	|P(H)| |S| Time Space
	48 243 57	228	14	6 20	18
	104 416 103	412	24	8 32	55
	160 512 108	432	74 14 88	90
	232 640 119	476	125 16 141 112
	296 736 119	476	144 16 160 138
	352 840 129	516	198 20 218 149
	400 928 131	524	213 21 234 153
	464 1016 133	532	237 21 258 241
	528 1120 145	580	304 23 327 273
	592 1224 148	592	312 23 335 301
	664 1469 207	828	446 44 490 344
	728 1533 205	820	488 44 532 381
	768 1589 201	804	496 45 541 382
	816 1725 234	936	563 50 613 383
	880 1861 246	984	611 50 661 384
	952 1973 219	876	638 51 689 385
	984 2005 214	856	662 51 713 386
	1184 2997 344	1376	754 58 812 392
	1240 3077 345	1380	762 58 820 409
	1328 3237 404	1616	792 60 852 430
	1584 4213 561	2244	1111 83 1194 450

Table 4 .

 4 Characteristics of patterns related to PSSM-12 containing different numbers of words.

	Automaton approach	Overlap approach
	|H| NAC |Σ|	Time	|P(H)| |S| Time Space
	50 299 284	1136	50	51 101 256
	100 549 512	2048	100 108 208 501
	150 783 729	2916	149 150 299 660
	200 1003 919	3676	200 208 408 868
	250 1198 1085	4340	250 243 493 985
	300 1410 1290	5160	300 301 601 1175
	350 1592 1448	5792	350 341 691 1319
	400 1814 1658	6632	400 417 817 1561
	450 1993 1808	7232	450 454 904 1648
	500 2156 1941	7764	500 488 988 1766
	550 2362 2161	8644	550 561 1111 1973
	600 2528 2276	9104	600 584 1184 2034
	650 2722 2469	9876	650 674 1324 2291
	700 2855 2564 10256	700 697 1397 2346
	750 3050 2738 10952	750 746 1496 2483
	800 3217 2914 11656	800 815 1615 2656
	850 3336 2955 11820	850 799 1649 2641
	900 3519 3130 12520	900 879 1779 2807
	950 3693 3303 13212	950 947 1897 3002
	1000 3823 3398 13592	1000 976 1976 3044
	1100 4156 3699 14796	1100 1059 2159 3262
	1200 4452 3970 15880	1200 1195 2395 3564
	1300 4750 4202 16808	1300 1231 2531 3693
	1400 5063 4502 18008	1400 1388 2788 4027
	1500 5356 4790 19160	1500 1509 3009 4284

Table 5 .

 5 Characteristics of random patterns of length 8 containing different numbers of words.

	Automaton approach	Overlap approach
	|H| NAC |Σ|	Time	|P(H)| |S| Time Space
	50 496 476	1904	50	51 101 256
	100 959 921	3684	99	95 194 501
	150 1367 1311	5244	150 153 303 660
	200 1801 1722	6888	199 200 399 868
	250 2224 2142	8568	250 265 515 985
	300 2613 2494	9976	300 288 588 1175
	350 3007 2888 11552	349 370 719 1319
	400 3396 3232 12928	400 395 795 1561
	450 3756 3579 14316	450 452 902 1648
	500 4170 3959 15836	500 489 989 1766
	550 4552 4335 17340	550 567 1117 1973
	600 4938 4694 18776	600 609 1209 2034
	650 5294 5013 20052	650 627 1277 2291
	700 5650 5339 21356	699 677 1376 2346
	750 5985 5686 22744	750 736 1486 2483
	800 6368 6022 24088	800 803 1603 2656
	850 6776 6431 25724	850 887 1737 2641
	900 7061 6675 26700	900 908 1808 2807
	950 7514 7194 28776	950 994 1944 3002
	1000 7854 7495 29980	1000 1021 2021 3044
	1100 8499 8019 32076	1099 1060 2159 3262

Table 6 .

 6 Characteristics of random patterns of length 12 containing different numbers of words.

Acknowledgments:

The authors are very grateful to anonymous referees whose remarks greatly helped to improve this paper.

E. Furletova and M. Roytberg were supported by grants 08-01-92496-NCNILa and 09-04-01053-from RFBR (Russia). M. Régnier and M. Roytberg were supported by Intas grant 05-1000008-8028 and Migec-Inria associate team.

C

G T 1 0.405 -1.424 0.301 -0.097 2 -0.944 0.122 -0.097 0.454 3 -0.622 -0.622 -3.989 1.067 4 1.041 -3.989 -1.156 -0.182 5 1.353 -3.989 -3.989 -2.380 6 -3.989 -1.792 -1.792 1.294 7 -3.989 -0.770 0.054 0.901 8 0.702 -3.989 0.665 -3.989 -A C G T 1 0.368 -2.197 -0.588 0.636 2 0.000 0.000 0.000 0.000 3 0. In Figures 6, 7, 8 and 9, one can see that in the vast majority of cases the coefficients for overlap approach are less than ones for the automaton approach. Time coefficients and space coefficients for PSSM-08 patterns are depicted in Figures 6 and7, respectively. The average ratios of time coefficients are 4.64 (for patterns of length less than 500); 2.12 (for patterns with lengths between 500 and 1000); 1.65 (for patterns of length between 1000 and 15004). The plot for PSSM-12 is similar (the plot is not shown, see Tables 3 and4 ). The advantage of overlap approach for space coefficients (in case of PSSM-08 patterns) is not so high compared to time coefficients, but still significant (see Figure 7). However for the PSSM-12 patterns, the space coefficients for the automaton approach are in average slightly better (the plot is not shown, see Tables 3 and4 ).

The data on random patterns (see Figures 8 and9) demonstrate that in this case the overlap-based approach works better. The lines depicting the behavior of the overlap approach for random patterns of different lengths almost coincide. This corresponds to the results given in Table 2 and Figure 4. In contrast, the automaton approach coefficients for the patterns of length 12 are significantly greater than ones for the patterns of length 8.

Discussion

The majority of the algorithms [NSF02,CS03,FL03,Nue06,BCR + 07,Nue08] computing probability to find the given number of occurrences of a pattern in a ran- In this paper we present another approach based on explicit usage of partition of the given word set according to the structure of its overlaps. Recursive equations, (11) used here and in [START_REF] Hertzberg | Finding motifs in promoter regions[END_REF], (12) and (19 ) employ subtraction of probabilities and therefore cannot be reduced to the automaton-based equations for any automaton.