Nadia Pisanti
email: pisanti@di.unipi.it

Maxime Crochemore
email: maxime.crochemore@univ-mlv.fr

Roberto Grossi
email: grossi@di.unipi.

Marie-France Sagot
email: sagot@inria.fr

A Comparative Study of Bases for Motif Inference *

Motif inference is at the heart of several time-demanding computational tasks, such as in molecular biology, data mining and identification of structured motifs in sequences, and in data compression, to name a few. In this scenario, a motif is a pattern that appears repeated at least a certain number of times (the quorum), to be of interest. The pattern can be approximated in that some of its characters can be left unspecified (the don't cares). Motif inference is not aimed at searching a given pattern but, rather, at discovering all the possible patterns that appear as motifs in the given input string. The combinatorial explosion of these patterns makes their discover an exponential-time computation. For this, the notion of basis has been recently introduced to succinctly represent all of them within reasonable time and space bounds. The goal of the paper is to shed light on the state of the art for this emerging field and to add further properties to what is currently known.

Introduction

Motivations and Applications

Pattern inference in the sense of finding regularities in various types of data is a very old activity which has generated much research in the past. The literature has been vast on the topic, the interested reader may consult for instance [START_REF] Duda | Pattern Classification[END_REF] for more details. Most approaches 1 have been based on the use of statistics to infer the desired information. Combinatorial methods have thus been rare. Pattern inference in textual data is a sub-topic that has been also much explored already. Among the more theoretical work in this area, there has been a large number of papers on identifying and characterizing periodicity and repeats in a string. One may consult for instance [START_REF] Lothaire | Combinatorics on Words[END_REF] or [START_REF] Lothaire | Algebraic Combinatorics on Words[END_REF]. Much of this theoretical work has been concerned however with exact repeats, unlike the more applied work discussed in [START_REF] Duda | Pattern Classification[END_REF].

In this paper, we address the problem of pattern inference in strings, with some clear applications in mind that require working with approximate regularities. We are therefore interested in finding approximate repeats in a text. We are concerned also with the combinatorial type of approaches for detecting such repeats.

The applications we have in mind can be varied. The main one which initially motivated the work is computational biology. In computational biology, approximate repeats may correspond to biologically functional units. Such units may represent, for instance, protein-DNA or protein-RNA binding sites, that is fragments of a molecule of DNA, RNA or protein that will come into interaction with another macromolecule in order for a function to happen. The molecular fragment may be seen as a word in a text (the whole molecule) that must be enough conserved through evolutionary time for the recognition of the two molecules by each other to take place. The conservation is in general not strict, hence the need to model it by introducing approximate repeats. Other applications, different from biology, present roughly the same characteristics. In document duplication and plagiarism for instance, common contents are detected in a set of documents divided into semantic units such as paragraphs or pages. It is possible to represent the distinct (stemmed or categorized) words in each unit by bit vectors as in the vector model used for information retrieval described in [START_REF] Baeza-Yates | Modern Information Retrieval[END_REF]. Paragraphs with similar contents are filtered for further processing since they share many common bits giving rise to approximate patterns in the concatenation of the bit vectors. In data mining systems [START_REF] Imielinski | A database perspective on knowledge discovery[END_REF] also, researchers have realized that discovering repetitions called "frequent itemsets" are at the heart of the problem of finding association rules. We can use for this purpose the same approach with bit vectors as above, each bit vector representing an itemset. The association rules can be based not only upon items appearing together often enough, but also upon their relation with the items that frequently do not appear (the latter corresponding to a sort of negative association rule). Motifs with don't cares are also useful in system security, where an intrusion is often indicated by a sequence of frequent operations appearing intermixed with others. Also in this case, we can break the log file of the operations into units and perform approximate pattern discovery. Finally, very recently, data compression has also started to use repeated approximate patterns of a special type [START_REF] Apostolico | Compression and the wheel of fortune[END_REF]. These are patterns with don't cares where a don't care is a symbol that matches anything.

All of the above examples are some of the best-known formulations that address the common issue of detecting approximate repeated patterns in several different contexts, thus revealing the algorithmic relevance of the problem.

Unfortunately, once approximate patterns are considered, the complexity of the algorithms for their discovery may easily become exponential due to the potentially exponential growth in the number of such patterns that may appear repeated in a string. Consider for instance the string A • • • ATA • • • A (same number of As on both sides of the letter T). It contains many repetitions of As intermixed with don't cares. In general, strings over a small alphabet, such as some "real-life" occurring ones like DNA sequences, will contain an ex-ponential number of repeats. A few heuristics try to alleviate this problem by reducing the number of interesting repeated patterns they identify to make feasible any further processing of them, but they often cannot guarantee sub-exponential bounds in the number of repeats in the worst case [START_REF] Parida | Pattern Discovery on Character Sets and Real-valued Data: Linear Bound on Irredundant Motifs and Efficient Polynomial Time Algorithm[END_REF].

About this paper

In this paper, we describe the algorithmic ideas behind pattern discovery while getting some insight into their combinatorial complexity. Although more general (and computationally demanding) notions of approximate patterns are possible [START_REF] Brazma | Approaches to the automatic discovery of patterns in biosequences[END_REF][START_REF] Sagot | A double combinatorial approach to discovering patterns in biological sequences[END_REF][START_REF] Sagot | Multiple comparison: a peptide matching approach[END_REF], the discovery and extraction of patterns with don't cares is flexible enough for several applications. These are therefore the types of patterns we shall consider in this paper.

Given a pattern x for a string s of length n, let us denote the set of starting positions of occurrences of x on s by L x ⊆ [0 . . n-1], and by |L x | is the number of occurrences of x. We define a pattern to be a motif when |L x | ≥ q, that is, the pattern appears at least q times in a string, where q is called the quorum the pattern must satisfy to be of any interest. We focus our attention on maximal motifs x, informally characterized as satisfying |L x | = |L y | for any other motif y more specific than x, that is, obtained from x by extending x, to the left or right, with don't cares and at least one alphabet letter and/or by replacing one or more of the don't cares in x with alphabet letters. In other words, x appears in y but x occurs in s more times than y does, which is considered informative for discovering the repetitions in s. For example,

x = M••T•E is maximal in COMMITTEE for q = 2 (and L x = {2, 3}) while z 1 = M••••E and z 2 = T•E are not maximal since
x is more specific than both of them, and has the same number of occurrences (L z 1 = L x and L z 2 = {5, 6}). Maximality is intuitively relevant since each maximal motif x indirectly represents all non-maximal motifs z that are less specific than it, namely, such that L z = L x + d, where L x + d denotes the set {i + d | i ∈ L x } of occurrences found exactly d positions apart from those in L x . Unfortunately, this property is not enough to significantly bound the number of maximal motifs. For example, A • • • ATA • • • A contains an exponential number of maximal motifs for q = 2 (see Section 2.1).

A further requirement on the maximal motifs relies on eliminating those whose occurrences can be derived from the occurrences of other motifs. The motifs selected form a basis for the maximal motifs, in that they can generate all the other maximal motifs by simple mechanical rules. They can thus be expressed mathematically in the algebraic sense of the term. This elegant introduction of a mathematical well-defined concept to the problem of motif discovery was, to the best of our knowledge, first introduced in the literature by Parida et al. [START_REF] Parida | Pattern Discovery on Character Sets and Real-valued Data: Linear Bound on Irredundant Motifs and Efficient Polynomial Time Algorithm[END_REF] for applications to molecular biology. It remains unclear what is the upper bound for the initial basis described in [START_REF] Parida | Pattern Discovery on Character Sets and Real-valued Data: Linear Bound on Irredundant Motifs and Efficient Polynomial Time Algorithm[END_REF] for a quorum of 2. This initial work inspired a number of others which introduced new definitions of bases of smaller sizes [13] [11] [14] [START_REF] Pisanti | A basis of tiling motifs for generating repeated patterns and its complexity for higher quorum[END_REF] [12] [START_REF] Apostolico | Compression and the wheel of fortune[END_REF]. The main motivation for this later work was computational biology except for [START_REF] Apostolico | Compression and the wheel of fortune[END_REF] where the area of application was for data compression. Pisanti et al., started exploring in [START_REF] Pisanti | Bases of motifs for generating repeated patterns with don't cares[END_REF][START_REF] Pisanti | A basis of tiling motifs for generating repeated patterns and its complexity for higher quorum[END_REF] the relation between Parida's initial basis and their own. The main purpose of the current paper is to explore further this comparison and extend it to the other related work in this scenario. The paper therefore makes an in-depth comparative exploration of the combinatorial properties of the various variants of bases for motifs and of the accompanying algorithms for identifying such bases. As a result, small differences in some basic definitions can defini-tively change the computational complexity of the corresponding bases, in terms of both time and space bounds. The paper also investigates new directions for possible extensions of the notion of a basis for some special situations (e.g. when the input is two strings).

The paper is organized as follows. Section 2 contains an overview of all definitions of a basis of motifs that have appeared in the literature, along with some of their common properties. Section 3 introduces the notions and other properties that are specific to some of the definitions. Section 4 shows lower and upper bounds on the size of the various bases for the special case of quorum q = 2. It also mentions a couple of results that have appeared in the literature concerning algorithms for computing bases. Section 5 contains some results that give for any quorum q a characterization of one of the defined bases, called the basis of tiling motifs, in terms of that for smaller quorum. Section 5 shows also that for increasing values of the quorum q, a lower bound on the size of all bases grows exponentially. Finally, Section 6 introduces two possible extensions of the notion of tiling motifs to the case of motifs common to two input strings, as well as efficient algorithms for computing them.

Bases of Motifs

This section contains some basic notions and terminology concerning motifs and lists all the definitions of a basis of motifs that have appeared in the literature. We detail the differences among the definitions that lead to different space and time bounds as we shall see in the rest of the paper. Examples are included in order to make the presentation clear.

The length of a string t is denoted by |t| and the letter at position i of t by t

[i]. Therefore, t = t[0]t[1] • • • t[|t| -1].
The input string is a word of length n over an alphabet Σ. The letters of Σ are called solid characters to distinguish them from an additional letter not in Σ called don't care and denoted by •. A don't care matches any other letter. The motifs in the input string correspond to the repetitions with don't cares that appear in the string.

Definition 1 (Pattern) A pattern is a string in Σ ∪ Σ(Σ ∪ {•}) * Σ, that is, a string on the alphabet Σ ∪ {•} that starts and ends with a solid character.

We also define a notion of partial order among elements of the set Σ ∪ {•} that we later extend to words.

Definition 2 (Specifity) The specificity relation denoted by is defined on Σ ∪ {•} as follows:

σ 1 σ 2 if and only if σ 1 = σ 2 or σ 1 = •, for σ 1 , σ 2 ∈ Σ ∪ {•}.
Strings are implicitly padded to the left and to the right with an infinite number of don't cares. In other words, for a string t, we consider that t[j] = • for any integer j such that j < 0 or j ≥ |t|. In this way the relation extends to strings as well: for any two strings u, v ∈ (Σ ∪ {•}) * , we have u v if and only if u[j] v[j] for any integer j. We refer to the condition u v saying that u is less specific than v. Definition 3 (Occurrence) Given two strings u, v ∈ (Σ ∪ {•}) * , we say that u occurs at position ℓ in v if and only if u[j] v[j + ℓ] for any integer j. Given a string s ∈ Σ * , with |s| = n, we define the motifs as special cases of patterns in s.

Definition 4 (Motif ) For a pattern x, the location list L x contains the positions of all the occurrences of x in s. Given a special parameter q ≥ 2, called quorum, we say that pattern x is a motif (according to s and q) if and only if |L x | ≥ q.

Example Let s = CACACATACATAC and q = 2. Pattern x 1 = CA•ACATAC is a motif with occurrence list L x 1 = {0, 4}, and pattern ACA•A is also a motif with occurrence list {1, 3}. On the other hand, the pattern T•CA is not a motif because it occurs only once.

Let us fix from now on the input string s ∈ Σ n . We are interested in finding all the motifs of s, that is, all patterns that appear at least q times in s. Unless differently specified, we assume that the quorum is q = 2. The problem of finding all the motifs is computationally difficult, since their number is possibly exponential in the worst case. We therefore define a few concepts that allow to reduce this quantity, leading to the various notions of bases.

Maximal Motifs

The first concept we discuss is the maximality of a motif, which is shared by all basis definitions. Intuitively, a motif x is maximal if no other motif y is more specific than it (i.e., y has a solid character at a position where x has a don't care, or it is longer) and simultaneously has the same occurrences as x, possibly shifted by some positions.

Given a set L of occurrences, we denote by L + d the set {i + d | i ∈ L}, where d is any given integer (it may be negative).

Definition 5 (Maximality) A motif x is maximal when, for any motif y and integer d such that L y = L x + d, we have that y occurs in x at position d ≥ 0.

Example (continued) Motif x 1 = CA•ACATAC of the previous example is maximal because if it is extended or if its don't care symbol is replaced by a solid character, then it loses at least one of its occurrences. On the contrary, motif CACA•A with list {0, 2} is not maximal since it occurs in x 2 = CACA•A•A•A which has the same occurrences. Indeed, x 2 is maximal and it is an extension of CACA•A.

Definition 5 is an equivalent formulation of the one given in [START_REF] Parida | Pattern Discovery on Character Sets and Real-valued Data: Linear Bound on Irredundant Motifs and Efficient Polynomial Time Algorithm[END_REF] and follows from the examples given there. It is known from [START_REF] Parida | Pattern Discovery on Character Sets and Real-valued Data: Linear Bound on Irredundant Motifs and Efficient Polynomial Time Algorithm[END_REF] that there can still be an exponential number of maximal motifs in a string. An example is given for quorum q = 2 with the string t k = A k TA k of length 2k + 1 which has a number of maximal motifs exponential in k. This can be shown by first noticing that any motif of t k can contain only A as a solid character because no motif containing T can occur twice. Secondly, let us consider, for all 1 ≤ i ≤ k -2, the set of motifs X i with all the motifs of length k containing exactly i don't cares. Each such motif occurs i + 2 times in the string, one for each distinct don't care matching the letter T, and two occurrences that match the first and the last k letters of t k . Moreover, all these motifs are maximal. In fact, any extension to the left or to the right would cause the loss of at least one among the two last occurrences mentioned above. Similarly, any replacement of a don't care with an A would cause the loss of one of the remaining i occurrences. Since we have that

|X i | = k-2 i , and since i ∈ [1, k -2], then there are k-2 i=1 k-2 i
= 2 k-2 such motifs. The fact that |t k | = Θ(k) leads to the exponential result.

Irredundant Motifs

The first notion of a basis of motifs with don't cares was given in [START_REF] Parida | Pattern Discovery on Character Sets and Real-valued Data: Linear Bound on Irredundant Motifs and Efficient Polynomial Time Algorithm[END_REF] and further explored in [START_REF] Parida | An output-sensitive flexible pattern discovery algorithm[END_REF]. It is based on the notion of irredundant motif which we formally introduce in this section.

Definition 6 (Irredundant motif ) A maximal motif x is irredundant if, for any maximal motifs y 1 , y 2 , . . . , y k such that L x = ∪ k i=1 L y i , motif x must be one of the y i 's. Vice versa, if all the y i 's are different from x, pattern x is said to be covered by motifs y i , y 2 , . . . , y k .

Example (continued) Consider again the string s = CACACATACATAC. Motif x 2 = CACA•A•A•A (which is maximal as we have shown in the previous example) is irredundant because its occurrence list L x 2 = {0, 2} cannot be built as the union of lists of maximal motifs different from x 2 itself. Likewise, motif x 4 = CA•AC with L x 4 = {0, 4, 8} is irredundant as well. It is maximal because an extension to the left/right would cause the loss of the leftmost/rightmost occurrence, and its don't care matches different solid characters in different occurrences. It is irredundant because occurrences at position 0 and 4 can be covered by x 2 , but no maximal motif can cover position 8. On the other hand, the motif

x 3 = CA•A with location list L x 3 = {0, 2, 4, 8} is maximal but it is redundant because L x 3 = L x 2 ∪ L x 4 .
In [START_REF] Parida | Pattern Discovery on Character Sets and Real-valued Data: Linear Bound on Irredundant Motifs and Efficient Polynomial Time Algorithm[END_REF], irredundant motifs are suggested as a generator for all repeated motifs in a string.

Definition 7 (B I ) Given a string s and a quorum q, the basis of irredundant motifs B I is the set of all irredundant motifs for s and q. The size of B I is the number of motifs it contains.

Example (continued) The basis of irredundant motifs B I for the string s of the previous example has size 7 and it contains the motifs x 0 = AC,

x 1 = CA•ACATAC, x 2 = CACA•A•A•A, x 4 = CA•AC, x 5 = ACA•A, x 6 = A•A, and x 7 = A•A•A.
The set B I is a generator for all maximal motifs in s. In [START_REF] Parida | Pattern Discovery on Character Sets and Real-valued Data: Linear Bound on Irredundant Motifs and Efficient Polynomial Time Algorithm[END_REF][START_REF] Parida | An output-sensitive flexible pattern discovery algorithm[END_REF], an algorithm is shown which generates all maximal motifs starting from the basis of irredundant motifs. The procedure is based on an iterative application of a generating operator ⊕ that we define as follows.

Definition 8 (⊕) Given σ 1 , σ 2 ∈ Σ∪{•} with σ 1 = σ 2 , we have σ 1 ⊕σ 2 = • and σ 1 ⊕σ 1 = σ 1 .
This operator is extended to two padded strings x, y ∈ Σ * with |x| = |y| in the obvious way:

u = x ⊕ y is such that u[i] = x[i] ⊕ y[i] for all integers i between 0 and |x| -1.
Example (continued) Let us consider again the input string s = CACACATACATAC. We showed that the motif

x 3 = CA•A is redundant because its occurrence list is the union of those of x 2 = CACA•A•A•A and x 4 = CA•AC. Indeed, we have that x 3 = CA•A = CACA•A•A•A⊕ CA•AC = x 2 ⊕ x 4 .
Notice that the ⊕ operator is such that, if u = x ⊕ y is not the empty word, then L u = L x ∪ L y . The ⊕ operator is also associative (and commutative) and therefore can be extended in an obvious way to three or more strings. Observe finally that Definition 8 is equivalent to the definition of ⊕ in [START_REF] Parida | An output-sensitive flexible pattern discovery algorithm[END_REF] which states that u = x ⊕ y if u is the most specific pattern such that u x, y.

Each redundant maximal motif x can be written as y 1 ⊕ y 2 ⊕ • • • ⊕ y p where the y i 's are irredundant motifs (it is enough to choose the y i 's that cover x according to the Definition 6, possibly iterating the process if these are redundant). Different sets of irredundant motifs y 1 , y 2 , . . . , y p can nevertheless lead to the same x. This makes inefficient the process of exhaustively generating all motifs from the subset of irredundant ones. For this reason, an output sensitive algorithm (in the sense of taking time proportional to the size of the output) is suggested in [START_REF] Parida | An output-sensitive flexible pattern discovery algorithm[END_REF]. The algorithm first builds maximal subsets P of B I , each containing motifs that start with the same letter and are such that none is less specific than another. It is shown in [START_REF] Parida | An output-sensitive flexible pattern discovery algorithm[END_REF] that it is not necessary to consider generations involving motifs belonging to different subsets P as the resulting maximal motifs may be obtained by generations involving motifs belonging to a same subset. The motifs in each subset are aligned on their first letter. For each column of the alignment, each letter appearing at least q times in the column leads to the generation of a new maximal motif.

Tiling Motifs

In this section, we describe the notion of a basis for motifs introduced in [START_REF] Pisanti | A basis for repeated motifs in pattern discovery and text mining[END_REF] and further explored in [START_REF] Pisanti | Bases of motifs for generating repeated patterns with don't cares[END_REF][START_REF] Pisanti | A basis of tiling motifs for generating repeated patterns and its complexity for higher quorum[END_REF]. Definition 9 (Tiling) A maximal motif x is a tiling motif if, for any choice of maximal motifs y 1 , y 2 , . . . , y k and integers

d 1 , d 2 , . . . , d k such that L x = ∪ k i=1 (L y i + d i )
, there exists at least one value of i such that y i = x. Otherwise, motif x is a tiled motif and motifs y i , y 2 , . . . , y k tile x.

Example (continued) Given s = CACACATACATAC, its motif x 5 = ACA•A with L x 5 = {1, 3, 7} is maximal, but it is tiled by x 1 and x 2 (where L x 1 = {0, 4} and L x 2 = {0, 2}) because its occurrence list can be obtained as (L x 1 + 3) ∪ (L x 2 + 1). Hence, the motif x 5 is not tiling. On the other hand, motif x 1 is tiling.

According to Definition 9, if x is tiled by y 1 , y 2 , . . . , y k for given integers d 1 , d 2 , . . . , d k , then k > 1. In fact, for k = 1, the equality L x = L y 1 + d 1 with x = y 1 would contradict the maximality of x or y 1 . Observe also that the y i 's in Definition 9 are not necessarily distinct.

Definition 10 (B T ) Given a string s and a quorum q, the basis of tiling motifs B T is the set of all tiling motifs for s and q. The size of B T is the number of these motifs.

Example (continued)

The basis B T of tiling motifs for the string s of the previous example has size 2 and it contains only the motifs x 1 = CA•ACATAC with L x 1 = {0, 4}, and

x 2 = CACA•A•A•A with L x 2 = {0, 2}.

Primitive Motifs

In [START_REF] Pelfrêne | Un algorithme d'indexation de motifs approchés[END_REF][START_REF] Pelfrêne | Extracting approximare patterns[END_REF], the concept of primitive motifs has been introduced as another possible notion of basis for repeated motifs with don't cares. Both in [START_REF] Pelfrêne | Un algorithme d'indexation de motifs approchés[END_REF] and in [START_REF] Pelfrêne | Extracting approximare patterns[END_REF], two different definitions have been proposed and claimed to be equivalent. The first definition is the following.

Definition 11 (Primitive) A maximal motif x is primitive if and only if there are no motifs y i (not necessarily maximal) with

y i = x for 1 ≤ i ≤ k, such that L x = ∪ k i=1 L y i .
In other words, the patterns that are candidate to cover x do not need to be maximal, but they have to occur at least q times. Hence, any right extension of x, or any motif obtained from x by replacing a don't care with a letter is a candidate for the set of y i 's of Definition 11, provided it has at least q occurrences. Although not explicitely stated in [START_REF] Pelfrêne | Un algorithme d'indexation de motifs approchés[END_REF][START_REF] Pelfrêne | Extracting approximare patterns[END_REF] (but clearly meant according to the examples that follow the definition of primitive motif in the paper1 ), it should be further required that the y i 's in Definition 11 do not occur in x, otherwise many motifs would be discarded because they are covered, for instance, by their prefixes occurring as many times as the motif itself (which is in contrast with the requirement of maximality).

The second definition given in [START_REF] Pelfrêne | Un algorithme d'indexation de motifs approchés[END_REF][START_REF] Pelfrêne | Extracting approximare patterns[END_REF] is claimed to be equivalent to the first one; rather, it is identical to the definition of tiling motifs (and produced independently). Definition 11 leads to a superset of the set of tiling motifs. Indeed, the fact of not allowing for shifts when trying to cover x (and thus to discard it), leads to keep more motifs than in the case of tiling motifs, as shown in the following example.

Example (continued) Let us consider again the input string s = CACACATACATAC with q = 2, and the motif x 0 = AC with L x 0 = {1, 3, 7, 11}. We have that x 0 is maximal because any extension to the right loses the rightmost occurrence, no one-letter extension to the left can be made with a solid character, and longer left extensions would lose the leftmost occurrence. Using the definition of tiling motifs, x 0 is discarded due to motifs

x 1 = CA•ACATAC and x 2 = CACA•A•A•A with, respectively, L x 1 = {0, 4} and L x 2 = {0, 2}, because L x 0 = (L x 1 + 7) ∪ (L x 2 + 1
). On the other hand, using Definition 11, no motif occurring at least twice can cover the occurrence at position 11 without a shift. Indeed, the only candidate different from x 0 itself is y = A, but the occurrence list of y is a superset of that of x 0 . Hence x 0 is primitive but not tiling in s. Notice also that x 0 is irredundant.

Observe that the set of motifs that are primitive (according to Definition 11) and not tiling contains at least all irredundant motifs x such that x occurs as a suffix of the input string. Indeed, in such cases, no motif different from x itself or occurring in it can cover the rightmost occurrence of x.

Definition 12 (B P ) Given a string s and a quorum q, the basis of primitive motifs B P is the set of all primitive motifs for s and q according to Definition 11. The size of B P is the number of motifs in B P .

Example (continued) The basis B P of the string s = CACACATACATAC has size 3 and contains the motifs x 0 = AC with L x 0 = {1, 3, 7, 11}, x 1 = CA•ACATAC with L x 1 = {0, 4}, and

x 2 = CACA•A•A•A with L x 2 = {0, 2}.
In the examples above we have shown an instance for which B T B P B I . In the Section 3 we will prove that these proper inclusions are valid in general.

Properties shared by all bases

In all definitions of a basis, a maximal motif x not in the basis is discarded by other motifs y 1 , . . . , y k distinct from x, each one occurring stricly less than |L x | times. As a consequence, if x is a maximal motif that occurs exactly q times, then there exist no set of maximal motifs distinct from x that can cover or tile it because they should be motifs with strictly less than q occurrences and this would contradict tha fact that they are maximal. All maximal motifs occurring exactly q times belong therefore to all bases.

When, instead, a motif x is covered or tiles by others, say y 1 , . . . , y k , then we must have by definition that L y i is a proper subset of L x for 1 ≤ i ≤ k if x is covered, and L y i is a proper subset of (L xd i ) if x is tiled. Observe that in both cases, we have that x occurs in each one of the y i 's; this happens at position 0 of each y i if x is redundant or non primitive, and at position d i if it is tiled. In fact, a motif x is only tiled or covered by motifs that are more specific than it, and thus x occurs in each one of them.

Finally, in all definitions of a basis, we have that if the quorum is set to q = 1, then the input string itself is a maximal motif and it is the only maximal motif occurring exactly q times. In the case of tiling motifs, this single motif coincides also with the basis.

As we mentioned in Section 2.2, it is shown in [START_REF] Parida | Pattern Discovery on Character Sets and Real-valued Data: Linear Bound on Irredundant Motifs and Efficient Polynomial Time Algorithm[END_REF][START_REF] Parida | An output-sensitive flexible pattern discovery algorithm[END_REF] that the set of irredundant motifs is enough to generate all maximal motifs. Basically, the reason is that the operation of eliminating a redundant motif can be easily reversed by means of the ⊕ operator. Indeed, the generating operator maps two or more patterns whose occurrences overlap into a pattern that is less specific than any of the initial patterns and whose occurrences is the union of all their occurrences.

It is intuitive to see that the ⊕ operator can be extended to allow a shift between the two input words in order to reverse also the operation of eliminating a tiled motif.

Definition 13 (⊕ h ) Given h and x, y ∈ (Σ∪•) * we define u = x⊕ h y by u[i] = x[i+h]⊕y[i]
for all integers i between 0 and |x|h.

In practice, this is the same as performing the operation ⊕ between x, and y shifted by h positions to the right.

Example (continued) Let us consider the usual input string and the motif x 0 which is tiled by x 1 and x 2 as

L x 0 = (L x 1 + 7) ∪ (L x 2 + 1). We have that x 1 ⊕ 6 x 2 = CA•ACATAC ⊕ 6 CACA•A•A•A = TAC ⊕ CACA•A•A•AAC = x 0 .
The shift h = 6 was chosen because 6 = 7 -1 where 7 and 1 are the respective shifts applied to L x 1 and to L x 2 in order to obtain L x 0 and thus to tile x 0 .

In [START_REF] Parida | An output-sensitive flexible pattern discovery algorithm[END_REF] an output sensitive algorithm is described which generates all maximal motifs starting from the basis of irredundant motifs (see Section 2.2). A similar approach applied to the basis of tiling motifs that replaces the ⊕ operator with its shifted version for all shifts would result in a method that generates all maximal motifs starting from such the basis. Making it also output sensitive is a less trivial extension because applying the ⊕ operator with different shifts to different pairs of tiling motifs may result in the same maximal (tiled) motif.

In either case however, we believe that actual applications based on the notion of a basis should not lead to a blind generation of all maximal motifs. Indeed, this would go against the motivation behind the whole idea of a basis of motifs. The generation of useful motifs should be driven by the specific application and should be applied on suitable subsets of the basis only. What is important is that, in theory, both bases are enough powerful to generate all motifs.

Differences among the bases

A remarkable difference between the bases is that the basis of tiling motifs B T is symmetric. That is, each tiling motif in the basis for the reverse string s is the reverse of a tiling motif in the basis of s. This follows directly from the definition of tiling motifs and from the fact that maximality is also a symmetric notion. Symmetry is a desirable property for a basis. It does not hold for the bases B I and B P of, respectively, irredundant and primitive motifs. Intuitively, the reason is that a motif x may be eliminated by other motifs only if the starting positions of such motifs coincide with those of x, while the ending position may differ. When the string and the motifs (maximal or not) are reversed, the former ending positions become starting positions and they might no longer coincide.

Example (continued) Let us consider again the string s = CACACATACATAC and the irredundant (but not tiling) motif x 6 = A•A for s. In the string s = CATACATACACAC we have that the motif x 6 = x 6 is not irredundant because it is eliminated, for example, by

A•AC = x 3 and A•A•A•ACAC = x 2 . Indeed, L f x 6 = {1, 3, 5, 7, 9} = {1, 5, 7, 9} ∪ {1, 3} = L f x 3 ∪ L f x 2 .
Notice that motif x 3 is also maximal in s as well as its reverse in s (the notion of maximality is symmetric), but x 3 is redundant in s while its reverse is irredundant in s. Similarly, motif x 0 = CA is not primitive in s, while x 0 is primitive in s as shown in Section 2.4. Indeed, in s we have that x 0 with L f x 0 = {0, 4, 8, 10} is covered, for example, by the two motifs CAC with L CAC = {8, 10} and CAT with L CAT = {0, 4}.

We now show some results concerning set inclusions among the three bases. Before that, we need the following definition. Definition 14 (Maximal Extension) Given a string s and a motif y, the maximal extension of y is the motif y obtained by, as much as possible, extending y and replacing its don't cares with letters, so long as no occurrence is lost.

Observe that for any y, the extension y is unique and that we always have that y is a maximal motif with that L y + d = L y for some d ≥ 0.

Example (continued)

In string s = CACACATACATAC, the maximal extension of the motif y = TAC (with L y = {6, 10}) is y = CA•ACATAC (with L y = {0, 4}).

We are now ready to prove the following results.

Lemma 1 For any input string s and for any quorum q, we have that B T ⊆ B P . Moreover, there exist instances for which B T B P .

Proof : In order to show that B T ⊆ B P , it is sufficient to show that for any x ∈ B P we have that x ∈ B T . Let x ∈ B P . This means that there exist k motifs y 1 , y 2 , . . . , y k with k > 1 and y i = x such that L x = ∪ k i=1 L y i . They are not necessarily maximal, hence let us consider y 1 , y 2 , . . . , y k that are, respectively, the maximal extensions of y 1 , y 2 , . . . , y k . The y i 's are maximal and none of them is equal to x because none of the y i 's occurred in x. Moreover, for each 1 ≤ i ≤ k we have that L y i + d i = L y i for some d i ≥ 0, and thus

L x = ∪ k i=1 L y i = ∪ k i=1 (L y i + d i )
, meaning that the y i 's tile x. This proves that x ∈ B T . Finally, the string s = CACACATACATAC of the previous examples is such that

B P \ B T = {x 0 } = ∅. ⊲⊳
The following result is proved in [START_REF] Pelfrêne | Extracting approximare patterns[END_REF].

Lemma 2 For any input string s and for any quorum q, we have that B P ⊆ B I . Moreover, there are instances for which B P B I .

Proof : As for the previous lemma, it is enough to show that for each x ∈ B I we have that x ∈ B P . To this purpose, it is sufficient to show that the y i 's that cover x according to Definition 6 are maximal motifs and thus, in particular, they are motifs that cover x according to Definition 11 as well.

Finally, in the string s of the proof of Lemma 1, we have B I \B P = {x 4 , x 5 , x 6 , x 7 } = ∅. ⊲⊳ Summing up, we proved the following general result.

Theorem 1 In general, B T ⊆ B P ⊆ B I ; there are strings for which B T B P B I .

The difference in the asymptotic sizes of the bases with respect to the length of the input string is an important issue that is addressed in Section 4 for q = 2 and in Section 5.2 for q > 2.

4 On the size of the bases if q = 2 and their construction

In this section we show that the different definitions for the bases lead to a hierarchy of space bounds, which enforces the condition B T B P B I stated in Theorem 1, for an input string of length n and quorum q = 2. We demonstrate in Section 4.1 that the size of B T is O(n). In Section 4.2, we show that the size of B P is between Ω(n) and O(n 2 ), while we show in Section 4.3 that the size of B I is Ω(n 2 ).

Tiling motifs

We define in this section a set of strings that are obtained by applying the ⊕ operation to the input string and all its possible shifts. We also give a characterization of tiling motifs in terms of these strings that leads to a linear upper bound for the number of tiling motifs.

Definition 15 (Merge) Let Merge

k = s ⊕ k s for 1 ≤ k ≤ |s| -1.
In other words, given a string s ∈ Σ * (recall that strings are padded to the left and right with an infinite number of don't cares), Merge k is the result of the application of the ⊕ operation to the string s with s itself shifted k positions to the right. We can observe that if q = 2 then each motif y occurs in at least one merge. In fact, it is enough to consider Merge |j-i| for i, j ∈ L y with i = j. More precisely, each pattern y occurs Ly 2 times in the merges, possibly having multiple occurrences in some of them. In fact, y has an occurrence in Merge |j-i| for each pair i, j ∈ L y with i = j. Moreover, in [START_REF] Pisanti | A basis for repeated motifs in pattern discovery and text mining[END_REF][START_REF] Pisanti | Bases of motifs for generating repeated patterns with don't cares[END_REF], the following lemmas are proved (and thus the proof is omitted here).

Lemma 3 Any Merge k of length at least one is a maximal motif.

Lemma 4 Each tiling motif of a string s with q = 2 is equal to Merge k for some integer k between 1 and n -1.

As a direct consequence of Lemmas 3 and 4, we have the following two results.

Theorem 2 Given a string s and q = 2,

B T ⊆ {Merge k | 1 ≤ k ≤ n -1}.
Corollary 1 (Linearity of B T ) The number of elements in B T of a string s of length n is at most n -1.

Example (continued) Among the merges listed in the previous example, we have that Merge 1 and Merge 2 coincide with, respectively, x 2 and x 1 , which are precisely the only tiling motifs of s. The other merges are all maximal but tiled.

In [START_REF] Pisanti | A basis of tiling motifs for generating repeated patterns and its complexity for higher quorum[END_REF], an O(n 2 log n log |Σ|) time complexity (and linear space) algorithm is given for the computation of the basis of tiling motifs. The algorithm is strongly based on the property of tiling motifs stated in Theorem 2. The algorithm is sketched as follows.

• The multiset M ′ of the n -1 merges is computed. For each Merge k , compute the occurrences list T k = {δ, δ + k} where s

[δ] = s[δ + k] is the first solid character of Merge k (done in O(n 2 ) time).
• The multiset M ′ is transformed into the set M by removing duplicates and possibly joining the lists T (takes O(n2 log |Σ|) time).

• The complete occurrence lists L of the merges are computed and the merges such that L = T are discarded 2 (done in O(n 2 log n log |Σ|) time).

• The remaining merges have a total number of occurrences that is linear in |s|, which allows to efficiently discard all remaining tiled motifs, if any (in O(n 2 ) time).

More details about the algorithm can be found in [START_REF] Pisanti | A basis for repeated motifs in pattern discovery and text mining[END_REF][START_REF] Pisanti | Bases of motifs for generating repeated patterns with don't cares[END_REF][START_REF] Pisanti | A basis of tiling motifs for generating repeated patterns and its complexity for higher quorum[END_REF].

Primitive motifs

The analog of Theorem 2 does not hold for B P as the following counter-example shows.

Example Let us consider the string s ′ = CACACATACACAC, quorum q = 2, and motif x ′ 0 = AC with L x ′ 0 = {1, 3, 7, 9, 11}. We have that x ′ 0 is maximal because a right extension would cause the loss of the rightmost occurrence, a left extension with a C would cause the loss of the occurrence at position 7, and any longer left extension would exclude the leftmost occurrence. Moreover, x ′ 0 is primitive because no motif different from x ′ 0 itself can cover the occurrence at position 11. The merges of s ′ are Merge The primitive motif x ′ 0 is not equal to any of the merges, although it is the suffix of several of them.

In order to understand the differences illustrated in the example, we give a characterization of the motifs in B P \ B T , which allows to obtain an upper bound on the size of such set, and hence on the size of B P for q = 2.

Lemma 5 (B

P \ B T ) ⊂ {x ′ | x ′ is a suffix of x ∈ B T }.
Proof : Let x ∈ (B P \ B T ). Since x is tiled, there must exist tiling motifs y 1 , y 2 , . . . , y k and integers d 1 , d 2 , . . . , d k such that L x = ∪ k i=1 (L y i + d i ) and y i = x for each 1 ≤ i ≤ k. Let us now consider, for each 1 ≤ i ≤ k, the pattern y ′ i that is the suffix of y i starting at position d i . The patterns y ′ 1 , y ′ 2 , . . . , y ′ k have the following properties:

• They start with a solid character. The reason for this is that the y i 's tile x with shifts d i 's. Their positions y i [d i ] thus coincide with the first letter of x which is the same in all occurrences. Since the y i 's are maximal, we have that y

i [d i ] = x[0] ∈ Σ.
• They occur at least q times because they are suffixes of motifs.

• We have that

L x = ∪ k i=1 L y ′ i because L y ′ i = L y i +d i .
In fact, we have that (L y i +d i ) ⊆ L y ′ i because y ′ i occurs at position d i of y i and thus that L x ⊆ ∪ k i=1 L y ′ i . Moreover, we have that x occurs in each y ′ i and thus that

∪ k i=1 L y ′ i ⊆ L x .
Hence, if y ′ 1 , y ′ 2 , . . . , y ′ k do not cover x (which is primitive), it must be because at least one of them is equal to x, which means that x is a suffix of the tiling motif y i . ⊲⊳

It is worth observing that the primitive motif x ′ 0 of the last example meets the characterization of Lemma 5 because it is a suffix of Merge 2 , Merge 4 , Merge 6 , Merge 8 which are tiling motifs for s ′ . We can now state the following result concerning the size of B P if q = 2.

Theorem 3

The number of elements in B P of a string s of length n with q = 2 is O(n 2 ).

Proof : This is a direct consequence of the fact that |B T | = O(n) and that |B P \ B T | = O(n 2 ) since there are at most O(n 2 ) suffixes of motifs in B T if q = 2.

⊲⊳

Observe that the quadratic upper bound of Theorem 3 may not be tight and thus the size of B P can still be linear if q = 2, although it is not a subset of the set of the merges.

Finally, an O(|Σ|n 2 log 2 n log log n) time complexity algorithm for the computation of the set of primitive motifs if q = 2 is described in [START_REF] Pelfrêne | Extracting approximare patterns[END_REF]. The idea of the algorithm is also to first compute a superset of the basis, and then to check for the primitive property. However, it is not clear for which one of the two definitions (primitive or tiling motifs) given in [START_REF] Pelfrêne | Extracting approximare patterns[END_REF] the algorithm is designed. Furthermore, the paper assumes that there is at most a linear number of primitive motifs for q = 2.

Irredundant motifs

In this section, we show a quadratic lower bound for the number of irredundant motifs. We can already observe that the set of irredundant motifs is not a subset of the merges, even though each irredundant motif necessarily occurs in at least one merge. Indeed, any irredundant motif x must occur in Merge k for k = ji with i, j ∈ L x and i < j.

= AC = Merge 10 , x 1 = CA•ACATAC = Merge 4 , x 2 = CACA•A•A•A = Merge 2 , x 4 = CA•AC = Merge 8 , x 5 = ACA•A = Merge 6 , x 6 = A•A which occurs in Merge 2 , Merge 4 , Merge 6 ,
and Merge 8 but is not equal to any of them, and finally

x 7 = A•A•A which occurs in (but is different from) Merge 2 .
Hence, the n -1 upper bound cannot hold for irredundant motifs. We now show that no linear upper bound holds either because there exists an infinite family of strings, introduced in [START_REF] Pisanti | Bases of motifs for generating repeated patterns with don't cares[END_REF], for which there are Ω(n 2 ) irredundant motifs in the basis for quorum q = 2, where n is the length of the input string. Such strings are denoted by s k . Each one of them (for any positive integer value of k) is an extension of t k = A k TA k , where A k denotes the letter A repeated k times. String t k has an exponential number of maximal motifs, including those having the form A{A, •} k-2 A with exactly two don't cares. The reason is that each such motif, let us call it x, occurs four times in t k : two occurrences of x match the first and the last k letters in t k while each distinct don't care in x matching the letter T in t k contributes to one of the two remaining occurrences. Extending x or replacing a don't care with a solid character reduces the number of these occurrences, so x is maximal. However, each motif x is covered in t k and hence it is redundant. String s k is obtained by prefixing t k with O(|t k |) symbols so that each motif x becomes irredundant in s k . Since there are Ω(k 2 ) of them, and n = |s k | = Θ(|t k |) = Θ(k), this leads to the quadratic lower bound for irredundant motifs.

In order to define the string s k on the alphabet Σ = {A, T, u, v, w, x, y, z, a 1 , a 2 , . . . , a k-2 }, we introduce a few notations. Let u denote the reversal of u, and let ev k , od k , u k , v k be the strings defined as follows:

if k is even : ev k = a 2 a 4 • • • a k-2 , if k is odd : ev k = a 2 a 4 • • • a k-3 , od k = a 1 a 3 • • • a k-3 , od k = a 1 a 3 • • • a k-2 , u k = ev k u ev k vw ev k , u k = ev k uv ev k wx ev k , v k = od k xy od k z od k , v k = od k y od k z od k .
The strings s k are then defined by s k = u k v k t k for k ≥ 5. For example, denoting letter a i with the number i, we have that s 7 = 24uv42wx24135y531z135AAAAAAATAAAAAAA.

Whatever the parity of k is, the string s k has size n = Θ(k). Moreover, in [START_REF] Pisanti | Bases of motifs for generating repeated patterns with don't cares[END_REF] the following result is proved.

Proposition 1 Each motif of the form A{A, •} k-2 A with exactly two don't cares is irredundant in s k .

By Proposition 1, the number of irredundant motifs in s k is at least k-2

2

= Ω(k 2 ), that is the number of choices of two positions in {A, •} k-2 . Since we observed that n = O(k), then we have that the basis of irredundant motifs for string s k contains Ω(n 2 ) irredundant motifs. All the details of the proof of this lower bound can be found in [START_REF] Pisanti | Bases of motifs for generating repeated patterns with don't cares[END_REF].

The construction of the basis for the irredundant motifs given in [START_REF] Apostolico | Incremental paradigms of motif discovery[END_REF] is incremental and requires O(n 3 ) time for an input string s of length n. Let B i denote the basis of irredundant motifs for the suffix

s i = s[i]s[i + 1] • • • s[n -1]
of the input string. The base step is B n-1 , which is simple to build. The inductive step computes B i having already computed B i+1 . The final outcome is then B 0 , which is the basis of irredundant motifs for s.

In order to illustrate the inductive step, we may figure out an n × n matrix M , whose rows and columns are numbered from 0 to n -1. Row i and column i are associated with symbol s[i], so that M [i, j] = s[i] ⊕ s[j]. Only the entries for which i < j are filled, so that M is an upper triangular matrix.

The diagonals of M restricted to its rows and columns numbered from i to n-1 contribute to the construction of B i . In particular, to obtain B i from B i+1 , two steps are run adding row i and column i to M :

• Find: Build B, which is the set of the motifs in B i+1 that occur also in position i, plus those occurring in i but not contained in B i+1 .

• Discard: Eliminate the redundant motifs in B ∪ B i+1 , thus obtaining B i .

Several properties are exhibited in [START_REF] Apostolico | Incremental paradigms of motif discovery[END_REF] to show that the two steps take each O(n 2 ) time, for a total of O(n 3 ) time. We refer the reader to that paper for more details.

We now prove a collection of properties that result in a characterization of the motifs in B q+1 in terms of those in B q .

The following result also holds for primitive ( [START_REF] Pelfrêne | Extracting approximare patterns[END_REF]) and irredundant motifs (the proof can be extended in a straightforward way).

Lemma 7 For all q ≥ 2, any motif x ∈ B > q belongs also to B q ′ for q < q ′ ≤ |L x |.

Proof : If x is in B > q , then it is maximal and, since it occurs at least q ′ times for q < q ′ ≤ |L x |, then x ∈ Max q ′ . Suppose by absurd, x were tiled for such quorum q ′ ≤ |L x |. Let y 1 , y 2 , . . . , y k be the maximal motifs which tile x, that is, such that L x = ∪ k i=1 (L y i + d i ) for integers d 1 , d 2 , . . . , d k . By Lemma 6, if y 1 , y 2 , . . . , y k ∈ Max q ′ , then y 1 , y 2 , . . . , y k ∈ Max for q < q ′ . This means that x would be tiled by motifs in Max q , and thus that x is not in B q , a contradiction.

⊲⊳

It is obvious that a motif x in B = q cannot belong to B q ′ for any q ′ > q because it does not satisfy the quorum. On the other hand, the reverse of Lemma 7 is not true: a motif x in B q ′ may not belong to B q for q < q ′ because there can be motifs in Max q -Max q ′ that tile it. Therefore, although the basis is always a subset of the set of maximal motifs, the inclusion relation proved in Lemma 6 for Max q is not inherited by B q . In fact, in general, the set B q is not a subset nor a superset of B q-1 . This holds for all the bases as shown by the following example.

Example Let us consider the string

s = ACAAATAAAAA. With quorum 2, basis B 2 con- tains A••AA•AA, A•A•A•AAA, AA••AAAA, and A•AAA•A. Basis B 3 includes A•••A•AA, A••AA•A, A•AAA.
We see that B 2 and B 3 do not even intersect. In fact, all motifs in B 2 occur exactly twice and thus cannot belong to Max 3 , and therefore to B 3 . On the other hand, all motifs in B 3 certainly belong to Max 3 and hence to Max 2 , but they are not tiling because they are tiled by motifs that belong to Max 2 \ Max 3 . For example, AA

••A with L AA••A = {3, 4, 7} is in B 3 , but it is not in B 2 because it is tiled by AA••AAAA (with L AA••AAAA = {3, 4}) and A••AA•AA (with L A••AA•AA = {1, 4}
) shifted by three positions. For the same string, the bases of primitive and irredundant motifs for q = 2 contain the tiling motifs plus some others (the primitives non tiling for q = 2 are AA, AAA, and A•AAA, and the irredundant non primitive are A•••AAA, A•AA, and AA••A). For both bases, the motifs that are also tiling must be discarded when q goes from 2 to 3 because they lose the quorum. Moreover, A••AA•A is primitive and irredundant (because it is tiling) when q = 3 but neither of them when q = 2.

We recall that

u = x ⊕ h y is such that u[i] = x[i + h] ⊕ h y[i]
for all integers i between 0 and |x|h, that is the operation applies to y and the i th suffix of x, which we also denote by x[i . . |x| -1]. The operation ⊕ can be naturally extended to more than two strings by placing a don't care at a position where at least two of the strings have different characters. Notice that such operation ⊕ is clearly associative (and commutative), while ⊕ h in general is not. For instance, we have that (

(ACDEG•H ⊕ 2 DAGMH) ⊕ 2 GM) = G is different from (ACDEG•H ⊕ 2 (DAGMH ⊕ 2 GM))
that results in the empty string. Therefore, when we apply the shifted ⊕ to more than two strings, we instead use a notation that applies the shift to the string (rather than to the operator) and we use the unshifted operator ⊕ notation. Hence, we use the more intuitive notation x[i . . |x| -1] ⊕ y[j . . |y| -1] ⊕ w to indicate that the operator ⊕ is applied to x, y, and w shifted in such a way that position i of x is aligned with position j of y and position 0 of w, although this can be written in a more compact way with an adequate choice of the shift applied to the operator. Lemma 8 Let y, z be two distinct elements of B q for q ≥ 2 padded to the left and to the right with an infinite number of don't cares. Let x = (y ⊕ i z) ∈ Σ ∪ Σ(Σ ∪ {•}) * Σ for i an integer between 0 and |y| -1. If x is not empty, then |L x | > q. Moreover, motif x belongs to Max q ′ for q < q ′ ≤ |L x |.

Proof : Clearly |L x | ≥ q. Suppose |L x | = q. Since L x = (L y + i) ∪ L z , then |L x | = q = |L y + i| = |L z |
and y and z would not be distinct, which is a contradiction. We now prove that x ∈ Max q ′ . Suppose again by absurd that x / ∈ Max q ′ for q < q ′ ≤ |L x |. There exists w ∈ Max q ′ with L w = L x + d such that w does not occur in x. Therefore, x occurs in w. Let j and k be the positions of the occurrences of x in y[i . . |y| -1] and z respectively. Let

y ′ = w[d . . |w| -1] ⊕ y[i + j . . |y| -1] and z ′ = w[d . . |w| -1] ⊕ z[k . . |z| -1]. We have that y[0] • • • y[i + j -1]y ′ and z[0] • • • z[k -1]z ′
are more specific than y and z respectively, contradicting the hypothesis that y, z ∈ B q . ⊲⊳ In other words, we have shown that a pair of motifs in y, z ∈ B q can generate a third motif x having more than q occurrences. Such a motif is not in B q because it is tiled by y and z, but it is a candidate to belong to the basis for quorum higher than q because it is maximal and it is possible that for a higher quorum, the set of maximal motifs no longer contains motifs that tile it. The next result investigates what happens to x in the case where

|L y |, |L z | ≥ q + 1.
Lemma 9 Let y, z be two distinct elements of B > q for q ≥ 2. Let x = y⊕ i z ∈ Σ∪Σ(Σ∪{•}) * Σ for i an integer between 0 and |y| -1 such that x is not empty. We have that x belongs to Max q+1 -B q+1 .

Proof : The fact that x ∈ Max q+1 is an immediate consequence of Lemma 7. Moreover, x ∈ B q+1 because it is tiled by y and z, which also belong to Max q+1 . ⊲⊳

A simple generalization of Lemma 9 suggets that a motif x generated by a pair of motifs y and z in B > q is a candidate for belonging to a basis only for a quorum stricly greater than min{|L y |, |L z |}.

Lemma 10 Let y 1 , . . . , y k (with k > 2) be three or more distinct elements of B q for q ≥ 2 padded to the left and to the right with an infinite number of don't cares. Let the string x be such that x = (y

1 [i 1 . . |y 1 | -1] ⊕ y 2 [i 2 . . |y 2 | -1] ⊕ • • • ⊕ y k ) ∈ Σ ∪ Σ(Σ ∪ {•}) * Σ belong to Max q+1 for i 1 , . . . , i k-1 integers such that 0 ≤ i j ≤ |y j | -1 and 1 ≤ j ≤ k. Then x does not belong to B q+1 .
Proof : We prove the results for the case of three strings, say y 1 , y 2 and y 3 , since the generalization to any number k > 2 of strings is straightforward. Let

r 1 = y 1 [i 1 . . |y 1 | -1] ⊕ y 2 [i 2 . . |y 2 | -1] and r 2 = y 2 [i 2 . . |y 2 | -1] ⊕ y 3 . By Lemma 8, r 1 , r 2 ∈ Max q+1 and thus also |L r 1 |, |L r 2 | > q. Since x = y 1 [i 1 . . |y 1 | -1] ⊕ y 2 [i 2 . . |y 2 | -1] ⊕ y 3 ∈ Max q+1 and y 1 [i 1 . . |y 1 | -1] ⊕ y 2 [i 2 . . |y 2 | -1] ⊕ y 3 = r 1 [i 1 . . |r 1 | -1] ⊕ r 2 , with |L r 1 |, |L r 2 | ≥ q + 1
, maximal motifs r 1 and r 2 tile motif x. ⊲⊳

Summing up, as we state in the following proposition, Lemmas 8, 9 and 10 tell us that two motifs in B q can generate a motif in B q+1 only if one of the two has exactly q occurrences, and that more than two motifs in B q cannot generate a motif in B q+1 , even if they all have exactly q occurrences. Proposition 2 Let x belong to B q+1 . We have that, if x / ∈ B q then there exist y, z ∈ B q with either y ∈ B = q or (inclusive) z ∈ B = q , and an integer i between 0 and |y| -1 such that x = y ⊕ i z.

Proof : If x ∈ B q+1 , then it must be that x ∈ Max q+1 and thus x ∈ Max q . Therefore, s ∈ Max q \ B q , and thus there exists y 1 , . . , y k ∈ Max q that tile x. For Lemma 10, it must be k = 2. Finally, Lemma 9 tells us that y 1 or y 2 belong to B = q , which is the thesis. ⊲⊳

A consequence of the results introduced in this section is that there are necessary and sufficient conditions on motifs in B q that allow an incremental generation of the bases for higher quorum. This is actually what was done in [START_REF] Pelfrêne | Extracting approximare patterns[END_REF] where such an incremental algorithm generating a basis with quorum q from a basis with quorum q -1 and from Max q-1 is suggested. Nevertheless, this algorithm has an exponential time complexity. This follows immediately from the results shown in the next section.

An exponential lower bound for all bases

We show (Section 5.2.1) that no polynomial-time algorithm generating bases explicitly can exist for any arbitrary value of q in the worst case, for all the bases considered in this paper. The size of these bases can be proven to depend exponentially on q ≥ 2, that is, we give a lower bound of

n-1 2 -1 q-1 = Ω( 1 2 q
n-1 q-1 ) for the size of any basis. In practice, this size has an exponential growth for increasing values of q up to O(log n), but larger values of q are theoretically possible in the worst case. Fixing q = (n -1)/4 + 1 in our lower bound, we get a size of Ω(2 (n-1)/4 ) motifs in the bases. On the average, q = O(log |Σ| n) using the fact that the expected number of simultaneous comparisons needed to find the first solid character of a merge is O(|Σ| q-1 ), which must be less than n.

We show a further property for the basis of tiling motifs in Section 5.2.2, giving an upper bound of n-1 q-1 on its size with a simple proof. Since we can find an algorithm taking time proportional to the square of that size, we can conclude that a polynomial-time algorithm for finding the basis of tiling motifs exists in the worst case if and only if the quorum q satisfies either q = O(1) or q = n -O(1) (the latter condition is hardly meaningful in practice).

A lower bound of

n-1 2 -1 q-1

on the bases

We show the existence of a family of strings for which there are at least

n-1 2 -1 q-1
tiling motifs for a quorum q. Since a tiling motif is also primitive and irredundant, this gives a lower bound for all bases. For q > 2, this gives a lower bound of Ω n-1

2 -1 q-1 = Ω( 1 2 q
n-1 q-1 ) for the the size of all bases.

The strings are this time of the form t k = A k TA k (k ≥ 5), without the left extension used in the bound of Section 4.3. The proof proceeds by exhibiting k-1 q-1 motifs that are maximal and have each exactly q occurrences, from whence it follows immediately that they are tiling.

Indeed, the observation we made in Section 2.5 holds for any q ≥ 2. Namely, all maximal motifs that occur exactly q times in a string are tiling. The following results are proved in [START_REF] Pisanti | Bases of motifs for generating repeated patterns with don't cares[END_REF]. Proposition 3 For 2 ≤ q ≤ k and 1 ≤ p ≤ kq + 1, any motif A p • {A, •} k-p-1 • A p with exactly q don't cares is tiling (and thus primitive and irredundant) in t k .

Theorem 4 String t k has n-1 2 -1 q-1 = Ω( 1 2 q
n-1 q-1 ) tiling (and thus primitive and irredundant) motifs, where n = |t k | and k ≥ 2.

An upper bound of n-1

q-1 tiling motifs We now show that n-1 q-1 is an upper bound for the size of a basis of tiling motifs for a string s and quorum q ≥ 2. Let us denote as before such a basis by B. To prove the upper bound, we use again the notion of a merge except that it involves q strings. Let k denote now an array of q -1 positive values k 1 , . . . , k q-1 with 1 ≤ k i < k j ≤ n -1 for all 1 ≤ i < j ≤ q -1. A merge is the (non empty) pattern that results from applying the operator ⊕ to the string s and to s itself q -1 times, each time shifted by k i positions to the right for 1 ≤ i ≤ q -1.

Definition 19 (MMerge) Let s k denote the string such that its jth character is s k

[j] = s[j] ⊕ s[j + k 1 ] ⊕ • • • ⊕ s[j + k q-1
] for all integers j. MMerge k is the pattern obtained by removing all the leading and trailing don't cares in s k (that is, appearing before the leftmost solid character and after the rightmost solid character).

Lemmas 11-12 reported below extend Lemmas 3-4 to the case of q > 2 and their proofs are also simple extensions.

Lemma 11 If MMerge k exists for quorum q, it must be a maximal motif.

Lemma 12 For each tiling motif x in the basis B with quorum q, there is at least one k for which MMerge k = x.

We now state the main property of tiling bases that follows from Lemma 11 and Lemma 12.

Theorem 5 Given a string s of length n and a quorum q ≥ 2, let M be the set of MMerge k , for any of the n-1 q-1 possible choices of k for which MMerge k exists. The basis B of tiling motifs for s satisfies B ⊆ M, and therefore the size of B is at most n-1 q-1 .

The tiling motifs in our basis appear in s for a total of q n-1 q-1 times at most. A variation of the algorithm given in [START_REF] Pisanti | A basis of tiling motifs for generating repeated patterns and its complexity for higher quorum[END_REF] gives a pseudo-polynomial time complexity of O q 2 n-1 q-1 2 for computing B q .

In [START_REF] Pelfrêne | Extracting approximare patterns[END_REF], the same upper bound is proved (independently from the proof of [START_REF] Pisanti | Bases of motifs for generating repeated patterns with don't cares[END_REF]). Namely, it is shown that there are at most C q-1 n-1 primitive motifs, but again here it is not clear whether the result refers to the definition of tiling motifs or of primitive ones. The same doubt applies to an algorithm that computes the basis of primitive motifs for quorum q from that with quorum q -1 in O(C q-1 n-1 |Σ| n log 2 n log log n) time. Adding the cost of computing the requested basis for q -1 (and thus for q -2 and so on until the quorum 2), this would also result in an algorithm computing a basis for any q having a cost that is quadratic in the possibly exponential size of the basis itself. Notice that Lemma 5 which characterizes the set B P \ B T is valid for any quorum q, and hence we have that in general the size of B P is in O(|B T | + n|B T |) = O(n|B T |) but, as it was the case for q = 2, this bound is not necessarily tight.

Combining the upper bound shown in this section with the lower bound of Section 5.2.1, we obtain that there exists a polynomial time algorithm for finding the basis if and only if either q = O(1) or q = n -O(1).

Two Bases for Common Motifs

In the literature, the problem of finding motifs that are common to more than one string instead of repeated within a unique input string is often considered. For instance, a motif common to two or more biological sequences can correspond to a binding site shared by the sequences. The problem has also other text mining applications that we mentioned in Section 1, such as detection of plagiarism and frequent itemsets. In this section, we define two notions of basis for the set of motifs common to two input strings.

Weak Basis

Let s ∈ Σ n and t ∈ Σ m be the two input strings (we assume w.l.o.g. that m ≥ n). As for the case of repeated motifs considered so far, common motifs are strings in the alphabet Σ ∪ {•} where Σ is the alphabet of the input strings and • is the don't care. Such strings start and end with a solid character. Differently from the problem addressed so far, there is no other quorum requirement for common motifs than that they should occur in both input strings. Assuming the definitions of pattern, specificity, and occurrence of Section 2, we extend the definitions concerning motifs to common motifs and their occurrences in the following way.

Definition 20 (Common motif ) A pattern x ∈ Σ ∪ Σ(Σ ∪ {•}) * Σ is a common motif for strings s ∈ Σ n and t ∈ Σ m if and only if there exist ℓ, ℓ ′ with 0 ≤ ℓ ≤ |s| -1 and 0 ≤ ℓ ′ ≤ |t| -1, such that x occurs in s at position ℓ and in t at position ℓ ′ . Definition 21 (Occurrence pair) A common motif x that occurs in s at position ℓ and in t at position ℓ ′ has an occurrence pair P x = (ℓ, ℓ ′ ). Given an occurrence pair P, we denote by P + i the set {(ℓ + i, ℓ ′ + i) | P = (ℓ, ℓ ′ )}.

The above definition associates to a motif just a pair of occurrences independently from the possibility that the same motif occurs also elsewhere in s or t. In this sense, the occurrence pair is a weak version of the complete occurrence list of a common motif, and for this reason we call the resulting basis (defined below) a weak basis.

Definition 22 (w-maximal common motifs) A common motif x is w-maximal (weak maximal) if and only if it has an occurrence pair P x such that, for each common motif y with an occurrence pair P y and integer d with P y = P x + d, we have that y occurs in x.

Observe that the notion of maximality of a common motif is related to one (or more) of its occurrence pairs that, unlike occurrence lists, are not unique.

Example Let s = ATGATC and t = ATCATG. The common motif ATC has only the occurrence pair (3, 0) for which it is w-maximal. The common motif AT has four occurrence pairs, namely (0, 0), (0, 3), [START_REF] Baeza-Yates | Modern Information Retrieval[END_REF][START_REF] Baeza-Yates | Modern Information Retrieval[END_REF], and (3, 0), for which it is not w-maximal. For example, for the occurrence pair (0, 3), there is the common motif ATG with the same occurrence pair and it does not occur in AT.

Since the occurrence list is here limited to a pair for all w-maximal motifs, there is no need to appeal to more restrictive properties such as the property of not being tiled by other w-maximal common motifs. Therefore, we suggest as a first notion of basis for the motifs common of s and t, the set of all w-maximal common motifs with the corresponding occurrence pairs. Such a basis, called a weak basis, has an interesting and surprisingly simple characterization which leads to an efficient algorithm for computing it. This is formalized in the following definitions and results.

Definition 23 (CMerge) Let us assume that t[i] = • for all i < 0 and i > |t| -1. For all possible shifts k such that -

(n -1) ≤ k ≤ m -1, let c k be the string such that c k [i] = s[i] ⊕ t[i + k] ∀ 0 ≤ i ≤ |s| -1.
We denote by CMerge k (common merge) the string obtained from c k by removing all don't cares to the left of the leftmost solid character and to the right of the rightmost solid character.

Example Given a string t, let us consider again s = ATGATC and t = ATCATG. We have that the non empty CMerges are CMerge -3 = ATC, CMerge 0 = AT•AT, and CMerge 3 = ATG.

The CMerges are analogous to the merges introduced in Section 4.1, except that they are no longer obtained by superposing a string s with all the shifts of itself, but rather by superposing the longest string t with all possible shifts of the other string s. Notice that any common motif c has one occurrence in CMerge (j-i) for each one of its occurrence pairs P c = (i, j).

Theorem 6

The weak basis coincides with the set of distinct non empty CMerges.

Proof : We first show that all non empty CMerges are w-maximal common motifs. Let c = CMerge k be non empty. It has an occurrence pair P c = (ℓ, ℓ + k). Let us assume that there exists another common motif y with an occurrence pair P y such that P y = P c + d for some integer d. As observed above, it must be that y occurs in CMerge k and thus in c.

We now show that all w-maximal common motifs are CMerges. Let x be a w-maximal common motif with the occurrence pair P x = (ℓ, ℓ ′ ). From the remark above, we have that x occurs in CMerge (ℓ ′ -ℓ) . Moreover, CMerge (ℓ ′ -ℓ) has the occurrence pair (ℓ, ℓ ′ ), which is equal to P x (and thus in particular it is a d-shift with d = 0), and by definition of w-maximality of x it must be that CMerge (ℓ ′ -ℓ) occurs in x, which implies that x = CMerge (ℓ ′ -ℓ) . ⊲⊳

As a consequence, the size of the weak basis is linearly bounded (there are at most as many motifs in the weak basis as distinct CMerges), and computing it is as easy as computing the set of distinct non empty CMerges, which can obviously be done in O(n(m + n)) time.

Strong Basis

The reason for the efficiency of the algorithm that computes the weak basis lies on the fact that there is no need to compute all the occurrences of the CMerges, as this is not required in the output nor is needed for a selection like in the case of tiling motifs. Nevertheless, a complete list of all the occurrences of a common motif may be required by certain applications. For this reason, we now define a new notion of occurrence list for common motifs, and hence a corresponding new notion of maximality and basis.

Definition 24 (Common motifs occurrence list) A common motif x has as occurrence list the pair of lists CL x = (L (x,s) , L (x,t) ) where L (x,s) (resp. L (x,t) ) is the list of all the occurrences of x in s (resp. t). Given an occurrence list CL = (L s , L t ), we denote by CL + i the pair of lists (L s + i, L t + i).

Observe that for a given common motif x, its occurrence list is unique, differently from the case of occurrence pairs. In fact, any common motif with occurrence list CL x = (L (x,s) , L (x,t) ) has an occurrence pair (i, j) for each i ∈ L (x,s) and j ∈ L (x,s) . As a direct consequence of this, we have that also for occurrence lists of common motifs, there is a relation with the CMerges. Namely, each common motif x with occurrence list CL x = (L (x,s) , L (x,t) ) occurs in CMerge (j-i) for each i ∈ L (x,s) and j ∈ L (x,s) . Based on this more complete version of occurrence set for common motifs, a new notion of maximality can be defined, as well as a notion of tiling motifs.

Definition 25 (Maximal common motifs) A common motif x is maximal if and only if for each common motif y and integer d such that CL y = CL x + d, we have that y occurs in x (and thus d ≥ 0). Definition 26 (Tiling common motifs) Given two occurrence lists of common motifs CL 1 = (L 1 , L ′ 1 ) and CL 2 = (L 2 , L ′ 2 ), let CL 1 ∪ CL 2 = ((L 1 ∪ L 2 ), (L ′ 1 ∪ L ′ 2 )). A maximal common motif x is a tiling common motif if and only if, for any maximal common motifs y 1 , y 2 , . . . , y k and integers d 1 , d 2 , . . . , d k such that L x = ∪ k i=1 (L y i + d i ), motif x is one y i . When, instead, all y i are different from x, pattern x is said to be a tiled common motif. We also say that the common motifs y i , y 2 , . . . , y k tile x.

Example Let us consider again the strings s = ATGATCATG and t = ATCATGATC and their maximal common motif ATG with occurrence list CL ATG = ({0, 6}, {3}). This motif is maximal but not tiling because it is tiled by the maximal common motifs ATCATG and ATGATC. In fact, the latter are both maximal because they are equal to CMerge -3 and CMerge 3 , respectively; moreover, since CL ATCATG = ({3}, {0}) and CL ATGATC = ({0}, {3}), we have that CL ATG = (CL ATCATG + 3) ∪ CL ATGATC .

The second notion of basis for common motifs that we suggest is that set of all tiling common motifs, and we call it strong basis. Similarly to the case of repeated motifs, the following results hold3 :

• For all k such that -(n -1) ≤ k ≤ m -1, CMerge k is a maximal common motif.

• Each maximal common motif is also w-maximal for a suitable occurrence pair.

• Each tiling common motif is a CMerge k for some k with -(n -1) ≤ k ≤ m -1.

Nevertheless, in general not all CMerges are tiling common motifs.

• The strong basis for common motifs contains O(n + m) motifs.

• The strong basis for common motifs is symmetric.

The strong basis can be computed by an algorithm similar to the one shown in [START_REF] Pisanti | A basis for repeated motifs in pattern discovery and text mining[END_REF] for repeated motifs. Indeed, we can prove that for each tiling common motif the list CL x coincides with the list CT x of the occurrence pairs that can be directly recovered from the CMerges that are equal to x. Furthermore, the sum of all these occurrences is linearly bounded. This allows an efficient detection of non tiling common motifs among the CMerges. In conclusion, we have that the strong basis can be computed in the following way.

  Example (continued) Let us consider again the string s = CACACATACATAC. The non empty merges are Merge 2 = CACA•A•A•A, Merge 4 = CA•ACATAC, Merge 6 = ACA•A, Merge 8 = CA•AC, and Merge 10 = AC.

2 =

 2 CACA•A•ACAC, Merge 4 = CA•ACA•AC, Merge 6 = ACACA, Merge 8 = CACAC, Merge 10 = CAC, and Merge 12 = C.

  Example (continued) In the string s = CACACATACATAC, the merges are Merge 2 = CACA•A•A•A, Merge 4 = CA•ACATAC, Merge 6 = ACA•A, Merge 8 = CA•AC, and Merge 10 = AC. The irredundant motifs are x 0

  First, the set of all the distinct CMerges can be computed in O(n(n + m)) time and there are O(n + m) of them. Second, finding all their occurrences and discarding those such that CT = CL takes O((n + m)m log m) = O(m 2 log m) time. Finally, discarding the remaining non tiling motifs can be performed in O((m + n) 2 ) time using two bit vectors of size n + m. The overall time complexity is thus in O(m 2 + (n + m)m log m + (m + n) 2 ) = O(m 2 log m).

In[START_REF] Pelfrêne | Extracting approximare patterns[END_REF], page 331, x = AAAA••AAAA is listed among the primitive motifs with q =

of AAAAAXAAAAA while, according to Definition 11, it is covered, for instance, by AAAA••AAA and AAAA••AA that occur at the same positions as x.

Correctness of this step is guaranteed by a result proved in[START_REF] Pisanti | A basis for repeated motifs in pattern discovery and text mining[END_REF] stating that for all tiling motifs the lists L and T must coincide.

We omit the proofs either because they are similar to those for repeated motifs or because they are trivial consequences of previous results.

Acknowledgments

We wish to thank Laxmi Parida for sending us a copy of reference [1].

* The work described in this paper is partially supported by the French program bioinformatique EPST 2002 "Algorithms for Work partially supported by the Italian MIUR project PRIN "ALINWEB: Algorithmics for Internet and the Web". Work partially supported by CNRS, NATO Science Programme grant PST.CLG.977017, and Wellcome Trust Foundation. di Pisa, Italy (it). Work partially supported by the Italian MIUR project PRIN "ALINWEB: Algorithmics for Internet and the Web". Work partially supported by CNRS-INRIA-INRA-INSERM action BioInformatique and Wellcome Trust Foundation.

Increasing the quorum

We now indicate some properties related to the computation of a basis for a string s when the quorum q is higher than 2. We start by observing some properties of maximal motifs related to the quorum. Definition 16 (Max q ) Given a string s, let Max q be the set of maximal motifs for a quorum q (with q ≥ 2).

We start by proving the following result.

Lemma 6 Given a string s, we have that Max q ′ ⊆ Max q for all 2 ≤ q < q ′ . Proof : Let x ∈ Max q ′ . Suppose x / ∈ Max q . This implies there exists y ∈ Max q with L y = L x + d and y does not occur in x. Therefore, x occurs in y (consequently, d ≤ 0). Motif y has thus the same number of occurrences as x (this number is at least q ′ ) and is more specific than it, which contradicts the hypothesis that x ∈ Max q ′ . ⊲⊳ Lemma 6 applied to increasing values of the quorum suggests that for each string s ∈ Σ n , there exists q 0 with 2 ≤ q o ≤ n such that, for q > q 0 , we have Max q = ∅, and thus also all the bases eventually collapse to the empty set when the quorum reaches the threshold q 0 . The value of q 0 is indeed the number of occurrences of the most frequent symbol appearing in the input string. In general, it can be as large as n, as is the case for s = A n where {A} = Max n = B T = B P = B I with q = n. Interesting values of q are those for which this is not yet the case and in the next section we investigate some properties of the basis of tiling motifs with quorum q > 2 with respect to the bases with smaller quorums.

Generating B q+1 from B q for tiling motifs

In this section, we show some properties of the basis of tiling motifs for growing values of the quorum. Related results have been independently observed also in [START_REF] Pelfrêne | Extracting approximare patterns[END_REF] for primitive motifs. In what follows, the results are proved for tiling motifs, thus in this section B will mean B T omitting the subscript T , which we replace with the value of the quorum q. When appropriate, we shall mention also whether the property holds for the other bases.

Definition 17 (B q ) Given a string s and quorum q, let B q ⊆ Max q be the set of tiling motifs with quorum q (with q ≥ 2).

We start by defining an useful notation.

be the set of motifs in B q that occur exactly q times. In a similar way, we denote by B > q = {x ∈ B q | |L x | > q} ⊆ B q the set of motifs in B q that occur strictly more than q times. Clearly B = q ∪ B > q = B q and B = q ∩ B > q = ∅.


Stephane Lohier
email: lohier@univ-mlv.fr

Gilles Roussel
email: roussel@univ-mlv.fr

Yacine Ghamri Doudane

Hierarchical and QoS-aware Routing in Multi-tier Wireless Multimedia Sensor Networks

The Wireless Multimedia Sensors Networks (WMSN) are a particular case of the Wireless Sensors Networks (WSN) as they present a lower density, a limited mobility, require more important resources and need especially QoS to transport the multimedia streams. In this paper, we propose, starting from a reference architecture of WMSN, a first approach to organize the routing in a hierarchical way while ensuring a certain level of QoS.

Introduction

The emergence and the development of the WMSN [START_REF] Akyildiz | A survey on wireless multimedia sensor networks[END_REF] are related to the availability of low-cost and low-consumption CMOS cameras. For this new kind of network the applications are numerous: monitoring of public or private places (concerts, borders, companies, houses…); detection, recognition and tracking of objects; automobile traffic management (speed control, car parking assistance…); industrial process control (visual inspection, automated actions…). In these particular sensors networks, the main concerns are not only the scalability and the energy but also the QoS needed for the multimedia streams: delay for the real time flows; bandwidth on the links related to the tolerable compression ratio; limited loss ratios. Besides, the routing problem on the WSN [START_REF] Akkaya | A survey of routing protocols in wireless sensor networks[END_REF] is different from that met on the MANET (many-to-one and not many-to-many); the type of routing (hierarchical or data-centric) and the QoS metrics are strongly related to the application (application aware). Moreover, for WMSN, we have to consider specific factors: low mobility, low density, heterogeneous sensors, specific nodes capabilities for the processing and the storage. Figure 1 described our proposal for a multi-tier architecture inspired by the work of I.F. Akyldiz [START_REF] Akyildiz | A survey on wireless multimedia sensor networks[END_REF]. In this heterogeneous and hierarchical architecture, each tier corresponds to a category of video sensors with increasing performances in term of camera resolution, processing, storage and transmission capabilities. For the first tier, the sensors can be CMUCam (weak resolution of 160x255) coupled with microcontrollers allowing a minimum processing and not very greedy transmissions like in ZigBee, Bluetooth or UWB standards. The second tier can be made up of webcam and microcontrollers with more processing, more storage and mixed transmissions like ZigBee and 802.11, for example. The last tier is connected to the sink (multimedia server) and includes high resolution cameras coupled with laptop. An implementation example of this type of architecture is presented in [START_REF] Kulkarni | The Case for Multi-tier Camera Sensor Networks[END_REF]. For each tier, our proposal is to organize the topology in clusters with Cluster Head (CH), possibly Cluster Routers (CR), allowing multi-hop routing, and Cluster Terminals (CT), only able to capture video information and to transmit it. In order to limit the interferences, the nearby clusters can use distinct transmission channels. The sensors of the various levels are not permanently mobile but can be moved. Moreover, the processing, essentially carried out in the CHs and towards the collector, includes specifics operations like data aggregation (images of different scenes in the same flow) and data suppression (redundant images of various sensors). For all these reasons (clustered architecture, many-to-one flows, heterogeneous capacities, processing into the CHs) we believe that a hierarchical routing is the most suited.

The following sections present a first approach for the QoS-aware hierarchical routing inside the clusters, whatever is the tier, and between the clusters of the various tier. The QoS routes setup is a first step of our proposition. Indeed, the organization of the network must remain evolutionary according to the periodic requests of nodes to join/leave a cluster and to the needs of the sink-application which will select, starting from descriptors, interesting flows (image of a particular zone with a selected resolution…). Thus, the objective here is not to guarantee a QoS constantly but to choose and receive pictures of a sufficient quality (soft QoS) by dynamically optimizing the links quality, the processing in the nodes and the choice of the sources.

Intra-cluster QoS Routing

The proposed QoS routing in each cluster is proactive and includes 6 stages for the cluster self-organization and the routes setup procedure (figure 2): 1. Each node self-determines its possible role (CH, CR or CT) in a cluster according to fixed or periodically re-evaluated criteria: sufficient storage and energy (comparison with specific thresholds for each role); for CH:

• transmission capacities (need for the corresponding interfaces);

• computation capacity for aggregation, suppression, compression…. 2. Each CH initiates a cluster (scan channels, select a channel, select a cluster id…).

CR and CT carry out a research for a cluster:

-CR/CT broadcast a message for discovery: Cluster_Discovery_Request (Scan Channels...);

response of the nearby CHs (and/or CR in case of multi-hop) with a Cluster_Discovery_Response (Cluster Description…). 4. Estimation of a cost for the concerned links (use of a function integrating the selected QoS metrics, see section 4) starting from the exchange of the Cluster_Discovery messages of stage 3. 5. CR and CT choose a CH (or a CR) according to the previous QoS estimate and join a cluster: -CR/CT send a message Cluster_Join_Request (Cluster id…); response of the selected CH (or CR) with a Cluster_Join_Response (Cluster id, Network addresses…). The associations of the CRs and the CTs are carried out in a recursive way: for the multi-hop routing, a CT out of the CH range has to wait for the association of a nearby CR to obtain an answer and to join in its turn a cluster. 6. The CR informs its CH (or its nearby CR which is closer to CH) of its router's role: -CR send a message Cluster_Router_Request (Cluster id…); -Response of CH (or CR) with a Cluster_Router_Response (Cluster id, Network address block…). In its response, the CH specifies the address block (or the subblock for the response of a CR) which can be used by the CR for its CT (or its lower level CR).

Fig. 2. Intra-cluster Routing Algorithm

After one or several exchange cycles, each CR or CT knows the address of its CH or its nearby CR (the one with the lower cost toward the CH); each CH has a routing table for all its nodes. The routing is hierarchical: all the data go towards CH.

According to the network dynamicity, the various stages are periodically re-launched.

Inter-tier QoS Routing

The routing between the CHs of the various tiers (figure 1) proceeds in 5 stages according to the same hierarchical and recursive principle:

1. The CH 1 (CH of first tier) broadcast to know the CH 2 .

2.

The CH 1 choose a CH 2 according to a cost estimated on the links (see section 4).

3.

The CH 2 broadcast in their turn on the corresponding interface to know the CH 3 .

4.

The CH 2 choose a CH 3 according to a cost estimated on the links. 5. The CH 3 broadcast to know the sink. In this last case, the cost is also computed to evaluate if, according to its position and its environment, the CH 3 can obtain a sufficient QoS on the link towards the sink.

After sufficient exchanges, each CH i knows the address of its CH i+1 or of the sink (transmitted with the broadcast response). Each node of each cluster can thus transmit towards the sink and conversely (the sink knows the CH 3 which knows the CH 2 …).

Estimation of the links cost

During the messages exchange of the discovery stage (between CT/CR and CR/CH or between CH i and CH i+1 ), the cost on each possible links is periodically estimated and compared (i) with a threshold to decide if the node is under the conditions (range, noise, contentions…) to obtain a sufficient QoS and (ii) with the costs on the other links to choose the most efficient CR/CH. The cost function on a link between two nodes i and j (j being the closest to the sink) can be expressed according to the chosen QoS metrics:

1 2 3 4 5 ( ) ( ) ( ) ( ) ( ) ij ij ji ij i j C c f delay c f SNR c f e c f energy c f energy = × + × + × + × + × -f (delay ij
) is a function of the delay for a data packet transmitted from i towards j; f (SNR ji ) is a function of the Signal/Noise Ratio measured from j towards i; f (e ij ) gives the error rate for the data packets transmitted from i towards j; f (energy i ) and f (energy j ) give respectively the remaining energy in i and j.

The choice of the coefficients c 1 to c 5 depends on the application and the type of traffic (the delay is more important than the loss rate for streaming…). Besides, for "real time" applications, it is necessary to control the end-to-end delay.

Rather than using higher level protocols like RTP and RTCP which involve overload we can evaluate this global delay at the routing level, starting from the delay on each link and the knowledge of the route towards the sink, both information being provided by our routing protocol. The loss rate on a path from a CT towards the sink can also be evaluated, starting from the successive loss rates and the knowledge of the route.

Conclusion

In this paper, we presented a first approach for QoS routing in the WMSN. Insofar as the nodes are very few, not very mobile, and heterogeneous in term of resources, a hierarchical routing passing by "Cluster Head" is the most suitable. To introduce QoS, we proposed a cost function, estimated on a hop and which can be extended on several hops or the complete route towards the sink. The continuation of this study will be directed to (i) the complete specifications and the tests of the routing algorithm and the cost function, in connection with the possible MAC layers (ZigBee, UWB, 80211) and (ii) the specification of the data exchanges and processing after the first stage of QoS routing.

Fig. 1 .

 1 Fig. 1. Multi-tier Architecture of WMSN