Maxime Crochemore
email: maxime.crochemore@kcl.ac.uk

Costas S Iliopoulos

M Sohel Rahman

Optimal Prefix and Suffix Queries on Texts

In this paper, we study a restricted version of the position restricted pattern matching problem introduced and studied Mäkinen and Navarro [Position-Restricted Substring Searching, LATIN 2006]. In the problem handled in this paper, we are interested in those occurrences of the pattern that lies in a suffix or in a prefix of the given text. We achieve optimal query time for our problem against a data structure which is an extension of the classic suffix tree data structure. The time and space complexity of the data structure is dominated by that of the suffix tree. Notably, the (best) algorithm by Mäkinen and Navarro, if applied to our problem, gives sub-optimal query time and the corresponding data structure also requires more time and space.

Introduction

The classical pattern matching problem is to find all the occurrences of a given pattern P = P [1..m] of length m in a text T = T [1..n] of length n, both being sequences of characters drawn from a finite character set Σ. This problem, along with its numerous variants, has been the focus of extensive research in the field of computer science. Due to the need of various practical applications, most recent works in pattern matching have considered 'inexact matching'. Many types of differences have been defined and studied in the literature, namely, errors (Hamming distance, LCS [START_REF] Cole | Dictionary matching and indexing with errors and don't cares[END_REF][START_REF] Hirschberg | Algorithms for the longest common subsequence problem[END_REF], edit distance [START_REF] Cole | Dictionary matching and indexing with errors and don't cares[END_REF][START_REF] Levenshtein | Binary codes capable of correcting, deletions, insertions and reversals[END_REF]), wild cards or don't cares [START_REF] Cole | Dictionary matching and indexing with errors and don't cares[END_REF][START_REF] Cole | Verifying candidate matches in sparse and wildcard matching[END_REF][START_REF] Fischer | String matching and other products[END_REF][START_REF] Pinter | Efficient string matching with dont care patterns[END_REF][START_REF] Rahman | Finding patterns with variable length gaps or don't cares[END_REF], rotations [START_REF] Amir | Twodimensional pattern matching with rotations[END_REF][START_REF] Amir | Faster two dimensional pattern matching with rotations[END_REF][START_REF] Fredriksson | Optimal exact and fast approximate two dimensional pattern matching allowing rotations[END_REF], scaling [START_REF] Amir | Real scaled matching[END_REF][START_REF] Amir | Efficient pattern matching with scaling[END_REF][START_REF] Amir | Faster two dimensional scaled matching[END_REF], permutations [START_REF] Butman | Scaled and permuted string matching[END_REF] among others.

The indexing problem for pattern matching is to preprocess a given text T [1..n] over an alphabet Σ as efficiently as possible to build a data structure to support the following form of online queries: Given a pattern P [1..m] over Σ find the occurrences of P in T . The indexing problem and its many variants have been central in pattern matching [START_REF] Gu | An efficient algorithm for dynamic text indexing[END_REF][START_REF] Ferragina | Fast incremental text editing[END_REF][START_REF] Amir | Text indexing and dictionary matching with one error[END_REF][START_REF] Chan | Compressed index for a dynamic collection of texts[END_REF][START_REF] Maaß | Text indexing with errors[END_REF][START_REF] Mäkinen | Dynamic entropy-compressed sequences and full-text indexes[END_REF][START_REF] Navarro | Indexing text with approximate q-grams[END_REF][START_REF] Rahman | Finding patterns with variable length gaps or don't cares[END_REF][START_REF] Rahman | Indexing factors with gaps[END_REF][START_REF] Cole | Dictionary matching and indexing with errors and don't cares[END_REF]. Recently, Mäkinen and Navarro, in [START_REF] Mäkinen | Position-restricted substring searching[END_REF], considered an interesting variant of indexed pattern matching, where only the occurrences of a given pattern starting in a particular area, are of interest. In particular, in this variant, the query provides an interval [ℓ..r], 1 ≤ ℓ ≤ r ≤ n along with the pattern P and the occurrences of P in T [ℓ..r] are sought for. These queries, as is pointed out in [START_REF] Mäkinen | Position-restricted substring searching[END_REF], are fundamental in many text search situations where one wants to search only a part of the text. The authors in [START_REF] Mäkinen | Position-restricted substring searching[END_REF] presented a number of algorithms depending on different trade-offs between the time and space complexities. The best query time they achieved was O(m+log log n+K) (K is the output size) against a data structure exhibiting O(n log 1+ǫ n) space and time complexity, where 0 ≤ ǫ ≤ 1.

In this paper, we study a restricted version of the problem handled in [START_REF] Mäkinen | Position-restricted substring searching[END_REF]. In particular, we are interested in those occurrences of the pattern that lies in a suffix or in a prefix of the given text. In other words, in our case, the query interval [ℓ..r] is of special form: either ℓ = 1, i.e. prefix search, or r = n, i.e. suffix search. This kind of queries seem to be interesting in many contexts as well. For example, many of the queries in real life are restricted up to the table of contents of a book or in the title and abstract of a scientific document. Another possible application for this problem can be found in Biological Sequence Assembly where the question is to build a kind of Shortest Super-string Common to a given set of sequences. In the greedy strategy for sequence assembly, this is usually done by finding markers close to the ends i.e. suffixes of the strings: these markers witness possible overlaps between a suffix of a sequence and a prefix of another sequence. Sequence having large overlaps are assembled in a longer sequence and so on.

In this paper, we present an efficient data structure to handle such online queries in the prefix or suffix of a given text in optimal time. Note that, the best query time achieved in [START_REF] Mäkinen | Position-restricted substring searching[END_REF] (for the more general problem) is not optimal due to the additional (mild) log log n term. As a result, if applied to our problem, their algorithm exhibits sub-optimal query time and the corresponding data structure also requires more time and space.

The rest of the paper is organized as follows. In Section 2, we present the preliminary concepts. The main result of this paper is presented in Section 3. We conclude briefly in Section 4.

Preliminaries

A text, also called a string, is a sequence of zero or more symbols from an alphabet

Σ. A text T of length n is denoted by T [1..n] = T 1 T 2 . . . T n , where T i ∈ Σ for 1 ≤ i ≤ n. The length of T is denoted by |T | = n. A string w is a factor or substring of T if T = uwv for u, v ∈ Σ * ; in this case, the string w occurs at position |u| + 1 in T . The factor w is denoted by T [|u| + 1..|u| + |w|]. A prefix (suffix ) of T is a factor T [x..y] such that x = 1 (y = n), 1 ≤ y ≤ n (1 ≤ x ≤ n).
We define ith prefix to be the prefix ending at position i i.e. T [1..i], 1 ≤ i ≤ n. On the other hand, ith suffix is the suffix starting at position i i.e.

T [i..n], 1 ≤ i ≤ n.
In traditional pattern matching problem, we want to find the occurrences of a given pattern P

[1..m] in a text T [1..n]. The pattern P is said to occur at position i ∈ [1..n] of T if and only if P = T [i..i + m -1]
. We use Occ P T to denote the set of occurrences of P in T .

The problem we handled in this paper can be defined formally as follows.

Problem "PMP/S" (Pattern Matching in a Prefix/Suffix). We are given a text T of length n. Preprocess T to answer the following form of queries. Query: Given a pattern P and a query interval [ℓ..r], with 1 ≤ ℓ ≤ r ≤ n, where either ℓ = 1 (prefix query) or r = n (suffix query), construct the set

Occ P T [ℓ..r] = {i | i ∈ Occ P T and i ∈ [ℓ..r]}.
It is easy to realize that Problem PMP/S is a special case of the problem handled in [START_REF] Mäkinen | Position-restricted substring searching[END_REF]. Apart from being interesting from pure combinatorial point if view, Problem PMP/S is motivated by practical applications as follows. In real life pattern matching applications, many of the queries are restricted to table of contents of a book or in the title and abstract of a scientific document. As a result, it is interesting to see whether the solution of [START_REF] Mäkinen | Position-restricted substring searching[END_REF] can be improved to optimal for this special case.

In traditional indexing problem one of the basic data structures used is the suffix tree data structure. In our indexing problem, we make use of this suffix tree data structure. A complete description of a suffix tree is beyond the scope of this paper, and can be found in [START_REF] Mccreight | A space-economical suffix tree construction algorithm[END_REF][START_REF] Ukkonen | On-line construction of suffix trees[END_REF] or in any textbook on stringology (e.g. [START_REF] Crochemore | Jewels of Stringology[END_REF][START_REF] Gusfield | Algorithms on Strings, Trees, and Sequences -Computer Science and Computational Biology[END_REF]). However, for the sake of completeness, we define the suffix tree data structure as follows. Given a string T of length n over an alphabet Σ, the suffix tree ST T of T is the compacted trie of all suffixes of T $, where $ / ∈ Σ. Each leaf in ST T represents a suffix T [i..n] of T and is labeled with the index i. We refer to the list (in left-to-right order) of indices of the leaves of the subtree rooted at node v as the leaf-list of v; it is denoted by LL(v). Each edge in ST T is labeled with a nonempty substring of T such that the path from the root to the leaf labeled with index i spells the suffix T [i..n]. For any node v, we let ℓ v denote the string obtained by concatenating the substrings labeling the edges on the path from the root to v in the order they appear. Several algorithms exist that can construct the suffix tree ST T in O(n log Σ) time5 [START_REF] Mccreight | A space-economical suffix tree construction algorithm[END_REF][START_REF] Ukkonen | On-line construction of suffix trees[END_REF]. Given the suffix tree ST T of a text T we define the "locus" µ P of a pattern P as the node in ST T such that ℓ µ P has the prefix P and |ℓ µ P | is the smallest of all such nodes. Note that the locus of P does not exist, if P is not a substring of T . Therefore, given P, finding µ P suffices to determine whether P occurs in T . Given a suffix tree of a text T , a pattern P, one can find its locus and hence the fact whether T has an occurrence of P in optimal O(|P|) time [START_REF] Mccreight | A space-economical suffix tree construction algorithm[END_REF][START_REF] Ukkonen | On-line construction of suffix trees[END_REF]. In addition to that, all such occurrences can be reported in constant time per occurrence.

Problem PMP/S

In this section, we handle Problem PMP/S. Our basic idea is to build an index data structure that would solve the problem in two steps. At first, it will (implicitly) give us the set Occ P T . Then, the index would 'select' some of the occurrences to provide us with our desired set Occ P T [ℓ..r],π , where either ℓ = 1 or r = n.

The idea we employ is as follows. We first construct a suffix tree ST T . According to the definition of suffix tree, each leaf in ST T is labeled by the starting location of its suffix. We do some preprocessing on ST T as follows. We maintain a linked list of all leaves in a left-to-right order. In other words, we realize the list LL(R) in the form of a linked list, where R is the root of the suffix tree. In addition to that, we set pointers v.lef t and v.right from each tree node v to its leftmost leaf v ℓ and rightmost leaf v r (considering the subtree rooted at v) in the linked list. It is easy to realize that, with these set of pointers at our disposal, we can indicate the set of occurrences of a pattern P by the two leaves µ P ℓ and µ P r because all the leaves between and including µ P ℓ and µ P r in LL(R) correspond to the occurrences of P in T . In what follows, we define the term ℓ T and r T such that LL(R)[ℓ T ] = µ P ℓ and LL(R)[r T ] = µ P r , where R is the root of ST T . Now recall that our data structure has to be able to somehow "select" and report only those occurrences that lies in the query interval. To solve this we use a solution to the following much studied problem.

Problem "RMIN/MAX" (Range Minima/Maxima Query Problem). We are given an array A[1..n] of numbers. We need to preprocess A to answer the following form of queries: Problem RMIN/MAX has received much attention in the literature and the best solution can build a data structure in O(n) time and space and can answer subsequent queries in O(1) time per query [START_REF] Gabow | Scaling and related techniques for geometry problems[END_REF][START_REF] Bender | The lca problem revisited[END_REF]. Now, to complete the construction of the data structure we simply preprocess the array data structure LL(R) for both range minima and range maxima queries. Algorithm 1 formally states the steps to build our data structure. In the rest of this paper, we refer to this data structure as IDS PMP/S.

Query: Given an interval I = [i s ..i e ], 1 ≤ i s ≤ i e ≤ n,

Algorithm 1 Algorithm to build IDS PMP/S

1: Build a suffix tree STT of T . Let the root of STT is R. 2: Label each leaf of STT by the starting location of its suffix. 3: Construct a linked list L realizing LL(R). Each element in L is the label of the corresponding leaf in LL(R). 4: for each node v in STT do 5:

Store v.lef t = i and v.right = j such that L[i] and L[j] corresponds to, respectively, (leftmost leaf) v ℓ and (rightmost leaf) vr of v. 6: end for 7: Preprocess L for both Range Minima and Range Maxima Queries.

Analysis

Let us analyze the the running time of Algorithm 1. Step 1 builds the traditional suffix tree requiring O(n log Σ) time. Note that, for bounded alphabet the time required is reduced to O(n). Step 2 can be done easily while building the suffix tree.

Step 3 and Step 4 can be done together in O(n) by traversing ST T using a breadth first or in order traversal. Finally, the preprocessing for range minima and range maxima queries require O(n) time and space [START_REF] Gabow | Scaling and related techniques for geometry problems[END_REF][START_REF] Bender | The lca problem revisited[END_REF]. So IDS PMP/S can be constructed in O(n) and O(n log Σ) time and space, respectively for bounded and general alphabet.

Algorithm 2 Algorithm for Query Processing

1: Find µ P in STT . 2: Set i = µ P .lef t, j = µ P .right. 3: Occ P T [ℓ..r] = ǫ 4: if ℓ = 1{This is a prefix query} then 5:
F indP ref ixOccurrence(L, r, i, j){See Algorithm 3} 6: else 7:

if r = 1{This is a suffix query} then 8:

F indSuf f ixOccurrence(L, ℓ, i, j){See Algorithm 4} 9:

end if 10: end if Algorithm 3 Procedure F indP ref ixOccurrence(L, r, i, j) F indP ref ixOccurrence(L, r, k + 1, j) 6: end if Algorithm 4 Procedure F indSuf f ixOccurrence(L, ℓ, i, j)

1: k = RangeM inimaQuery(L, i, j) 2: if L[k] <
1: k = RangeM aximaQuery(L, i, j) 2: if L[k] > ℓ then 3: Set Occ P T [ℓ..r] = Occ P T [ℓ..r] S L[k] 4:
F indSuf f ixOccurrence(L, ℓ, i, k -1) 5:

F indSuf f ixOccurrence(L, ℓ, k + 1, j) 6: end if

Query processing

Now we discuss the query processing. Suppose we are given a query pattern P along with a query interval [ℓ..r]. We first find the locus µ P in ST T . Let i = µ P .lef t and j = µ P .right. This means, we get the set Occ P T in the form of L[i..j] spending O(m) time. Now, suppose we are performing a prefix query, i.e. ℓ = 1. So we want to compute the set Occ P T [1..r] . It is easy to see that

Occ P T [1..r] = {L[k] | i ≤ k ≤ j, L[k] ≤ r}.
To compute Occ P T [1.

.r] , we apply a divide and conquer approach as follows. We perform a Range Minima Query on L on the interval [i..j]. Suppose the query returns the index k.

If L[k] ≤ r then L[k] ∈ Occ P T [1.
.r] and then we perform the range minima query on the intervals [i..k -1] and [k + 1..j] and continue as before. If any of the queries returns k such that L[k] > r we stop. It is easy to verify that this would give us the set Occ P T [1..r] . Note that, in this way, for each found entry in Occ P T [1.

.r] , we have at most 2 intervals to perform range minima queries further. So, in total the time spent is O(|Occ P T [1..r] |). On the other hand, for a suffix query, i.e. when r = n, we want to compute:

Occ P T [ℓ..n] = {L[k] | i ≤ k ≤ j, L[k] ≥ ℓ}.
So, in this case, in the above procedure, we just need to perform a Range Maxima

Conclusion

In this paper, we have studied Problem PMP/S, a restricted version of the position restricted pattern matching problem (Problem PRPM) introduced and studied in [START_REF] Mäkinen | Position-restricted substring searching[END_REF]. In Problem PRPM, the query provides an interval [ℓ..r], 1 ≤ ℓ ≤ r ≤ n along with the pattern P and the occurrences of P in T [ℓ..r] are sought for. In Problem PMP/S, on the other hand, we are interested in those occurrences of the pattern that lies in a suffix or in a prefix of the given text. In other words, in our case, the query interval [ℓ..r] is of special form: either ℓ = 1, i.e. prefix search, or r = n, i.e. suffix search. We have presented an efficient data structure, IDS PMP/S, which is an extension of the classic suffix tree data structure. The time and space complexity of IDS PMP/S is dominated by that of the suffix tree and hence is O(n) for bounded alphabet and O(n log Σ) for the general case. The query time we achieve is O(m + |Occ P T [ℓ..r] |) time per query, which is optimal. Notably, the (best) algorithm in [START_REF] Mäkinen | Position-restricted substring searching[END_REF], if applied to Problem PMP/S, gives suboptimal query time and the corresponding data structure also requires more time and space. One final remark is that, we can use the suffix array instead of suffix tree as well with some standard modifications in the corresponding algorithms to solve Problem PMP/S.

  the goal is to find the index k (or the value A[k] itself ) with minimum (maximum, in the case of Range Maxima Query) value A[k] for k ∈ I.

r then 3 :

 3 Set Occ P T [ℓ..r] = Occ P T [ℓ..r] S L[k] 4: F indP ref ixOccurrence(L, r, i, k -1) 5:

  (instead of Minima) Query and instead of checking whether L[k] ≤ r, we need to check whether L[k] ≥ ℓ. The query steps are formally stated in Algorithm 2, 3 and 4. In light of the above discussion, it is straightforward to see that the total query time is O(m + |Occ P T [ℓ..r] |). The result of this paper is formally presented in the form of following theorem. Theorem 1. For Problem PMP/S, we can construct the IDS PMP/S data structure in O(n) time and space for bounded alphabet and O(n log Σ) time for general alphabet. We can then answer the relevant queries in optimal O(m + |Occ P T [ℓ..r] |) time per query.

For bounded alphabet the running time remains linear, i.e. O(n).


Marie-Pierre Béal

Dominique Perrin

Completing codes in a sofic shift

Keywords: automata and formal languages, codes, complete codes, sofic shifts, symbolic dynamics, variable length codes

We define a code in a sofic shift as a set of blocks of symbols of the shift such that any block of the shift has at most one decomposition into code words. It is maximal if it is not strictly included in another one. Such a code is complete in the sofic shift if any block of the shift occurs within some concatenation of code words. We prove that a maximal code in an irreducible sofic shift is complete in this shift. We give an explicit construction of a regular completion of a regular code in a sofic shift. This extends the well known result of Ehrenfeucht and Rozenberg to the case of codes in sofic systems. We also give a combinatorial proof of a result concerning the polynomial of a code in a sofic shift.

Introduction

The classical notion of unique decipherability is defined on unconstrained words over a finite alphabet. It can be generalized to words satisfying some constraints. This generalization of the theory of (variable length) codes extends previous works of Reutenauer [START_REF] Ch | Ensembles libres de chemins dans un graphe[END_REF], Restivo [START_REF] Restivo | Codes and local constraints[END_REF] and Ashley et al. [START_REF] Ashley | Surjective extensions of slidingblock codes[END_REF].

The main result of this paper is an extension of a classical result of Schützenberger [START_REF] Schützenberger | Une théorie algébrique du codage[END_REF] (see also [START_REF] Berstel | Theory of codes[END_REF]) relating the notions of completeness and maximality of codes. It is an extended version of the paper presented at the conference STACS'06 [START_REF] Béal | Complete codes in a sofic shift[END_REF]. It is also the second part of a series of three contributions to the study of codes in sofic shifts [START_REF] Béal | Codes and sofic constraints[END_REF], [START_REF] Béal | Complete codes in a sofic shift[END_REF], and [START_REF] Béal | Codes, unambiguous automata and sofic systems[END_REF].

Let S be a sofic shift, i.e. the set of bi-infinite sequences of symbols labelling paths in a finite automaton. The set of factors of S, denoted by Fact(S), is the set of finite sequences of consecutive symbols (also called blocks) appearing in the elements of S. We call S-code a set of elements of Fact(S) such that any element of Fact(S) has at most one decomposition in code words. A set of words X is S-complete if any element of Fact(S) occurs within some concatenation of elements of X. An S-code is maximal if it is maximal for inclusion.

We prove that, for any irreducible sofic shift S, any maximal S-code is Scomplete. Moreover, we give an effective embedding of a regular S-code into an S-complete one. This extends the well known theorem of Ehrenfeucht and Rozenberg [START_REF] Ehrenfeucht | Each regular code is included in a maximal regular code[END_REF] to codes in a sofic shift.

Our definition of S-codes generalizes the notion introduced by Restivo [2] and Ashley et al. [START_REF] Ashley | Surjective extensions of slidingblock codes[END_REF]. In the first place, they consider subshifts of finite type instead of the more general notion of sofic shifts. Although shifts of finite type can also be described by a finite automaton, there is a real gap between the two classes, because representations of shifts of finite type have nice strong properties of synchronization that do not apply to sofic shifts in general. These properties are used to complete the codes. Secondly, they consider codes such that all concatenations of code words are in Fact(S), a condition that we do not impose. Our definition here is also slightly more general than the one used in our previous paper [START_REF] Béal | Codes and sofic constraints[END_REF]. In fact, we only require the unique factorization for the words of Fact(S) and not for all products of code words. We think that this definition is more natural. The results of [START_REF] Béal | Codes and sofic constraints[END_REF] all extend straightforwardly to this new class.

In the last section, we give a combinatorial proof of the main result of our previous paper [START_REF] Béal | Codes and sofic constraints[END_REF] concerning the polynomial of a finite code. The proof is simpler and relates our result to the ones due to Williams [START_REF] Williams | Lattice invariants for sofic shifts[END_REF] and Nasu [START_REF] Nasu | An invariant for bounded-to-one factor maps between transitive sofic subshifts, Ergodic Theory Dynam[END_REF].

The paper is organized as follows. We first recall some basic definitions from the area of symbolic dynamics and from the theory of codes. We introduce the notions of S-code, maximal S-code, and S-complete code when S denotes a sofic shift. In Section 3, we prove that any maximal S-code is S-complete. A combinatorial proof of the result of [START_REF] Béal | Codes and sofic constraints[END_REF] is given in the last section.

Codes and Sofic Shifts

Sofic Shifts

Let A be a finite alphabet. We denote by A * the set of finite words, by A + the set of nonempty finite words, and by A Z the set of bi-infinite words on A. A subshift is a closed subset S of A Z which is invariant by the shift transformation σ (i.e. σ(S) = S) defined by σ((a i ) i∈Z ) = (a i+1 ) i∈Z .

A finite automaton is a finite multigraph labeled on a finite alphabet A. It is denoted A = (Q, E), where Q is a finite set of states, and E a finite set of edges labeled by A. All states of such automata can be considered as both initial and final states.

A sofic shift is the set of labels of all bi-infinite paths in a finite automaton. We then say that the automaton presents or accepts the sofic shift. A sofic shift is irreducible if there is a finite automaton with a strongly connected graph. In this case the automaton also is said to be irreducible. An automaton A = (Q, E) is deterministic if, for any state p ∈ Q and any word u, there is at most one path labeled by u and going out of p. When it exists, the target state of this path is denoted by p • u. An automaton is unambiguous if there is at most one path labeled by u going from a state p to a state q for any given triple p, u, q.

Irreducible sofic shifts have a unique (up to isomorphisms of automata) minimal deterministic automaton, that is a deterministic automaton having the fewest states among all deterministic automata presenting the shift. This automaton is called the Fischer cover of the shift (see [12, p. 98]). A subshift of finite type is defined as the set of bi-infinite words on a finite alphabet avoiding a finite set of finite words. It is a sofic shift. The full shift on the finite alphabet A is the set of all bi-infinite sequences on A, i.e. the set A Z .

The (topological) entropy of a sofic shift S is defined as

h(S) = lim n→∞ 1 n log 2 s n ,
where s n is the number of words of length n of Fact(S). The Fischer cover of a transitive sofic shift of null entropy is made of one cycle.

Example 1. Let S be the irreducible sofic subshift on A = {a, b} defined by the automaton on the left of Figure 1. This automaton is the Fischer cover of S. This shift is the so-called even system since its bi-infinite sequences are those having an even number of b's between two a's. It is not a shift of finite type.

Let T be the irreducible shift on A = {a, b} defined by the forbidden block bb. It is a shift of finite type. Its Fischer cover is given on the right of Figure 1. This shift is the so-called golden mean system. Let S be a subshift on the alphabet A. We denote by Fact(S) the set of finite factors (or blocks) of elements of S. Each element of Fact(S) is the label of a finite path in the Fischer cover of S.

Let A be a finite automaton. A word w is said to be a synchronizing word of A if w is the label of at least one path in A and any path labelled w ends in the same state depending only on w. If p denotes this state, one says that w synchronizes to p. For instance the words a, bab are synchronizing words of the Fischer cover of the even system. In the golden mean shift, which is a shift of finite type, each word of length 1, i.e. a or b, is a synchronizing word. For any Fischer cover of a shift of finite type S, there is a positive integer k such that any word of length k in Fact(S) is synchronizing.

Let L be a language of finite words. A word w is a synchronizing word of L if and only if whenever u, v are words such that uw and wv belong to L, one has uwv belongs to L. Note that if w is a synchronizing word of an automaton A recognizing a sofic shift S, it is a synchronizing word of the language Fact(S).

It is known that the Fischer cover of an irreducible sofic shift S has a synchronizing word (see for instance [START_REF] Lind | An Introduction to Symbolic Dynamics and Coding[END_REF]Proposition 3.3.16]). If w is one of them, for any words u, v such that uwv ∈ Fact(S), uwv is also a synchronizing word.

Codes

Let S be a sofic shift. A set of finite words X ⊂ Fact(S) on an alphabet A is an S-code if and only if whenever w = x 1 x 2 . . . x n = y 1 y 2 . . . y m , where x i , y j ∈ X, n, m are positive integers, and w ∈ Fact(S), one has n = m and x i = y i for 1 ≤ i ≤ n. Thus the classical definition of a code (also called a uniquely decipherable code) corresponds to the case where S is the full shift. Note that any code is an S-code but the converse is false as shown in the following example.

Example 2. The set {a, ab, ba} is not a code since the block aba has two factorizations into codewords a • ba = ab • a. However it is not difficult to see that it is an S-code in the even system. Indeed, any word with two factorizations contains the block aba.

Let S be a sofic shift. A set X on the alphabet A is said to be complete in S, or S-complete, if X is an S-code and any word in Fact(S) is a factor of a word in X * . For instance the code X = {a, bb} is complete in the even system.

An S-code X is maximal if it is not strictly included in another S-code.

The following example of an S-complete code which is not maximal is given in [START_REF] Ch | Ensembles libres de chemins dans un graphe[END_REF]: Consider the shift of finite type S defined on the alphabet A = {a, b} and avoiding the blocks aa and bb. The S-code X = {ab} is S-complete but not maximal since X is strictly included in the S-code Y = {ab, ba}.

There is a connection between complete S-codes and a concept which has been studied in symbolic dynamics. This explains why the results proved in Section 4 are related with the results of Williams [START_REF] Williams | Lattice invariants for sofic shifts[END_REF] and Nasu [START_REF] Nasu | An invariant for bounded-to-one factor maps between transitive sofic subshifts, Ergodic Theory Dynam[END_REF]. Let X be a complete S-code. Let A = (Q, E) be the Fischer cover of S. We build an automaton B computed from X and A as follows. The set of states of B is the union of the set of states Q of A and an additional set of dummy states. For each path in A labeled by a word in X going from a state p to a state q, we build a path in B from p to q with dummy states in-between. Let T be the subshift of finite type made of the bi-infinite paths of the graph of B. The labelling of the paths in the automaton B defines a block map φ from T to S. The set X is an S-code if and only if φ is finite-to-one. It is S-complete if and only if φ is onto. Thus statements on complete S-codes can be reformulated as statements on finite-to-one factor maps between irreducible sofic shifts.

Completion of an S-Code

The following result generalizes the theorem of Ehrenfeucht and Rozenberg [START_REF] Ehrenfeucht | Each regular code is included in a maximal regular code[END_REF]. The proof uses the same type of construction as the original one, also used in the case of the extension to subshifts of finite type obtained in [START_REF] Ashley | Surjective extensions of slidingblock codes[END_REF]. It requires however, as we shall see, a careful adaptation to extend to sofic shifts.

Theorem 1. Let S be an irreducible sofic shift. If X is an S-code, there is an S-code Y such that X ⊆ Y and Y is S-complete. If X is moreover regular, Y can be chosen regular.

A nonempty word w of A * is called unbordered if no proper nonempty left factor of w is a right factor of w. In other words, w is unbordered if and only if w ∈ uA + ∩ A + u implies u = ε, where ε denotes the empty word.

Lemma 2 below provides the construction of an unbordered word in the set of factors of an irreducible sofic shift. It replaces the construction used in [START_REF] Berstel | Theory of codes[END_REF]Proposition 3.6] for the case of the full shift.

Lemma 2. Let S be an irreducible sofic shift which has a positive entropy. Let z be a word in Fact(S). Then there is a word y in Fact(S) such that z is a factor of y and y is unbordered.

Proof. Let A be a deterministic automaton presenting S.

Without loss of generality, one can assume that z is the label of a path from p to p in A. Let C be the set of labels of first-return paths in A from p to p. Since the automaton A is deterministic, the set C is a code in the full shift. Set

z = c 1 c 2 • • • c r with c i ∈ C.
Since S has a positive entropy, there exists a word c = c 1 in C. The words c and z cannot be powers of the same word. Indeed, suppose that c = t n and z = t m with t ∈ A * and n, m positive integers.

If n ≤ m, then t m-n ∈ C * . Since C is a code, this forces c = c 1 , a contradiction. Otherwise, t n-m ∈ C * and thus c = t n-m t m is not in C. Let w = u m z m with m ≥ 2. Since w ∈ C * , we have w ∈ Fact(S)
. By [13, Theorem 9.2.4 pp. 166], w is a primitive word. Let y be the Lyndon word conjugate to w. It belongs to Fact(S) since any conjugate of a word in C * is in Fact(S). By a well known result (see [13, Proposition 5.1.2 p. 65]), a Lyndon word is unbordered. Thus y is an unbordered in Fact(S). It is trivial that z is a factor of y since m ≥ 2.

We are now ready to prove Theorem 1.

Proof of Theorem 1. Let S be an irreducible sofic shift. We denote by A the Fischer cover of S. Let X be an S-code.

Let us suppose that X is not S-complete. Consequently there is a word z in Fact(S) which is not in Fact(X * ).

We first assume that S has a null entropy. This means that the Fischer cover A is made of a unique cycle. One can assume that there is a state p such that p has no outgoing path in A labeled in X. Otherwise X is already S-complete. Since A is irreducible, one can assume without loss of generality that z is the label of a path in A going from a state p to itself, and that z is moreover a synchronizing word of A. We set Y = X ∪ {z}. Let us show that Y is an S-code. Assume the contrary and consider a relation

x 1 x 2 • • • x n = y 1 y 2 • • • y m , with x 1 x 2 • • • x n ∈ Fact(S), x i ,
y j ∈ Y , and x n = y m . The set X being an Scode, at least one of the words x i , y j must be z. Hence, for instance

x 1 x 2 • • • x n = x 1 x 2 • • • x r zx r+1 . . . x n . The word zx r+1 • • • x n is
the label of a path in A going through the state p after reading the label z. Since p has no outgoing path in A labeled in X, it follows that

x r+1 • • • x n = z n-r . Hence there is a positive integer k such that x 1 x 2 • • • x n = x 1 x 2 • • • x r z k with x 1 , x 2 , . . . , x r = z. Since z is not a factor of X * , there is also a positive integer l such that y 1 y 2 • • • y m = y 1 y 2 • • • y t z l with y 1 , y 2 , • • • , y t = z. The above relation becomes x 1 x 2 • • • x r z k = y 1 y 2 • • • y t z l , which contradicts the hypothesis that x n = y m since z / ∈ Fact(X * ). It is trivial that Y is S-complete.
We may now assume that S has a positive entropy. Without loss of generality, by extending z on the right, one can moreover assume that z is a synchronizing word of A. By Lemma 2, we construct a word y ∈ Fact(S) which is unbordered and has z as factor. This latter point implies that y is a synchronizing word of A, and hence a synchronizing word of Fact(S).

If L is a language of finite words, we denote by u -1 L (resp. Lu -1 ) the set of words z such that uz ∈ L (resp. zu ∈ L).

We define the sets U and Y by

U = y -1 Fact(S)y -1 -X * -A * yA * , (1)
Y = X ∪ y(U y) * . (2)
The rest of the proof consists in verifying the following three properties.

• The set Y is a subset of Fact(S).

• The set Y is an S-code.

• The set Y is S-complete.

Let us show that Y is a subset of Fact(S). For any word u ∈ U , yuy ∈ F act(S). Since y is a synchronizing word of Fact(S), for any two words w, w ′ with wy, yw ′ ∈ Fact(S), wyw ′ ∈ Fact(S). It follows that for any two words u, u ′ ∈ U , yuyu ′ y belongs to Fact(S). By recurrence, y(U y) * ⊆ Fact(S), and thus Y ⊆ Fact(S). Now we show that Y is an S-code. Assume the contrary and consider a relation

y 1 y 2 . . . y n = y ′ 1 y ′ 2 . . . y ′ m , with y 1 , . . . , y ′ m ∈ Y , y 1 y 2 . . . y n ∈ Fact(S) and y 1 = y ′ 1 .
The set X being a code, one of these words must be in Y -X. Assume that one of y 1 , . . . , y n is in Y -X, and let k be the smallest index such that y k ∈ y(U y) * . From y / ∈ Fact(X * ) it also follows that y k / ∈ Fact(X * ). Consequently at least one of y ′ 1 , . . . , y ′ m is in y(U y) * . Let l be the smallest index such that y ′ l ∈ y(U y) * . Then

y 1 . . . y k-1 y, y ′ 1 y ′ 2 . . . y ′ l-1 y ∈ X * y.
Since y / ∈ Fact(X * ) and y is unbordered, X * y is a prefix code. It follows that y

1 . . . y k-1 = y ′ 1 y ′ 2 . . . y ′ l-1 .
The set X being a code and

y 1 = y ′ 1 , k = l = 1. Set y 1 = yu 1 y . . . yu q y, y ′ 1 = yu ′ 1 y . . . yu ′ r y, with u 1 , . . . u q , u ′ 1 , . . . u ′ r ∈ U . Assume |u 1 | > |u ′ 1 |. The word u ′ 1 y is a prefix of u 1 y. Since y is unbordered and u 1 / ∈ A * yA * , we get u ′ 1 = u 1 .
Let us assume that r ≥ q (the opposite case is similar). By recurrence, we get that

u 1 = u ′ 1 , . . . , u q = u ′ q . Let t = u ′ q+1 y • • • u ′ r y. We have y 2 • • • y n = ty ′ 2 • • • y ′ m .
The word y is a factor of t and thus occurs also in y 2 . . . y n . This shows that at least one of y 2 , . . . , y n , say y i is in y(U y) * . Suppose i is chosen minimal. Then

y 2 • • • y i-1 ∈ X * . Since y is unbordered and U ∩ A * yA * = ∅, u ′ q+1 = y 2 • • • y i-1 . Thus u ′
q+1 ∈ X * , in contradiction with the hypothesis u ′ q+1 ∈ U . This shows that Y is an S-code.

Finally, let us show that Y is S-complete. Let us assume that the word y is the label of a path from p to q in A. Let t ∈ Fact(S). By extending t on the right and on the left, one may assume, without loss of generality, that t is a label of a path from q to p in A. It follows that yty also is in Fact(S). Hence t ∈ y -1 Fact(S)y -1 . Set

t = v 1 yv 2 y • • • yv n-1 yv n ,
with v 1 , . . . , v n ∈ A * -A * yA * . Each yv i y is factor of t for 2 ≤ i ≤ n -1. Hence v i ∈ y -1 Fact(S)y -1 for 2 ≤ i ≤ n -1. Since yty ∈ Fact(S), v 1 and v n also belong to y -1 Fact(S)y -1 . Set

V = y -1 Fact(S)y -1 -A * yA * . Thus v i ∈ V for 1 ≤ i ≤ n and U = V -X * . Let v i1 , v i2 , . . . , v i k be the v i 's which are in X * . Then yty = (yv 1 y • • • yv i1-1 y)v i1 (yv i1+1 y • • • yv i2-1 y)v i2 × • • • × v i k (yv i k +1 y • • • yv iv y).
Each parenthesized word is in y(U y) * . Thus the whole word is in Y * .

It is clear from Equations ( 1) and ( 2) that Y is regular when X is regular.

Remark 1. When X is a regular S-code, the S-complete code Y of Theorem 1 can be computed in an effective way from Equations ( 1) and ( 2). More precisely, we consider a sofic shift S defined by its Fisher cover. This gives a non-deterministic automaton recognizing Fact(S). The S-code X is given by a deterministic automaton. Equations ( 1) and ( 2) allow to build a finite automaton recognizing Y .

Remark 2. Note that our proof shows that, if S is an irreducible sofic shift with a positive entropy, and X is a code, then X can be completed into a code Y (i.e a code for the full shift) which is S-complete. We do not know whether this property also holds for irreducible shifts of entropy zero. In [START_REF] Restivo | Codes with constraints[END_REF][START_REF] Restivo | Codes and local constraints[END_REF] (see also [START_REF] Ashley | Surjective extensions of slidingblock codes[END_REF]), it is proved that if S is an irreducible shift of finite type and X a code with X * ⊆ Fact(S) which is not S-complete, X can be embedded into an S-complete set which is moreover a code (i.e. a code for the full shift). The proof of our theorem allows us to recover this result. Indeed, when X * ⊆ Fact(S), our construction builds an S-code Y which is a code. Moreover, the S-complete code Y that we have built satisfies also Y * ⊆ Fact(S), when X * ⊆ Fact(S). This is due to the strong synchronization properties of the Fischer cover of an irreducible shift of finite type.

Example 3. We consider the even system S of Example 1 on the alphabet A = {a, b}. Let X = {a, ba}. The set X is an S-code but it is not S-complete since for instance z = bb does not belong to Fact(X * ). The regular completion of X is obtained following the proof of Theorem 1. We replace z by bba in order to get a synchronizing word. The proof of Lemma 2 says that the word y = aaabbabb is an unbordered word of Fact(S). Note that a smaller y can be chosen. For instance y = bba also is an allowable unbordered word of Fact(S). We then define U and Y as in Equations ( 1) and ( 2) and get z = bba (synchronizing),

y = bba (unbordered), U = a * (bb) + , Y = a + ba + bba(a * (bb) + bba) * .
The set Y is a regular S-complete code.

We derive the following corollary which generalizes to codes in irreducible sofic shifts the fact that any maximal code is complete [5, Theorem 5.1].

Corollary 3. Let S be an irreducible sofic shift. Any maximal S-code is Scomplete.

Polynomial of a Code

In the rest of this paper, S is an irreducible sofic shift recognized by its Fischer cover A = (Q, E). Let µ A (or µ) be the morphism from A * into N Q×Q defined as follows. For each word u, the matrix µ(u) is defined by

µ(u) pq = 1 if p • u = q 0 otherwise.
The matrix α A (u) (or α(u)) is defined by α(u) = µ(u)u. Thus the matrix α(u) is obtained from µ(u) by replacing its coefficients 1 by the word u. The coefficients of α(u) are either 0 or u. In this way α is a morphism from A * into the monoid of matrices with elements in the set of subsets of A * . The morphism α is extended to subsets of A * by linearity. For a finite set X, we denote by p X the polynomial in commuting variables:

p X = det(I -α(X)).
The following result is proved in [START_REF] Béal | Codes and sofic constraints[END_REF]. It is a generalization of a result of C. Reutenauer [START_REF] Ch | Ensembles libres de chemins dans un graphe[END_REF] who has proved it under more restrictive assumptions.

Theorem 4. Let S be an irreducible sofic shift and let X be a finite complete S-code. The polynomial p A divides p X .

Example 4. For the even shift and the set X = {aa, ab, ba, bb}, we have

α(A) = a b b 0 and α(X) = aa + bb ab ba bb ,
and

p A = 1 -a -bb, p X = 1 -aa -2bb + b 4 = (1 + a -bb)(1 -a -bb).
We present here two combinatorial proofs of this result, which come as an alternative to the analytic proof presented in [START_REF] Béal | Codes and sofic constraints[END_REF]. Both proofs rely on the reduction of automata with multiplicities.

The first proof goes along the same line as the proof of a result of S. Williams presented in Kitchen's book [15, p. 156], giving a necessary condition to the existence of a finite-to-one factor map between irreducible sofic shifts.

We first build as in Section 2 an automaton B computed from X and A as follows. The set of states of B contains the set of states Q of A. For each path in A labeled by a word in X going from state p to state q, we build a path in B from p to q with dummy states in-between as shown in Example 5. The automaton B is finite when X is finite. It is unambiguous if and only if the set X is an S-code. It presents the sofic shift S if and only if the set X is S-complete.

Example 5. Consider the code X = {aa, ab, ba, bb} in the even system S. The automaton B is represented in the right part of Figure 2. Thus, since X is a complete S-code, B is unambiguous and presents S. Without loss of generality, one can assume that B is irreducible. Otherwise, it is possible to keep only a strongly connected component of B presenting S. By definition,

p A = det(I -α A (A)) and p X = det(I -α A (X)). Furthermore, det(I -α A (X)) = det(I -α B (A)). Indeed, det(I -α B (A)) = (-1) k P c1 • • • P c k ,
where the sum is on the sets of independent cycles c 1 , . . . , c k of the automaton B.

Consider the transformation of B contracting each path p

a1 -→ d 1 a2 -→ d 2 • • • an --→ q, where d i are dummy states into p a1•••an ----→ q.
gives an automaton whose edges are labelled by words of X and whose adjacency matrix is α A (X). Since it does not change the labels of cycles, we obtain the formula.

Hence, Theorem 4 is a consequence of the following result.

Proposition 5. Let S be an irreducible sofic shift and let A be its Fischer cover. If B is an unambiguous and irreducible automaton presenting S, det(I

-α A (A)) divides det(I -α B (A)).
Proof. The degree of a word u in an automaton is defined as the number of paths labeled by u. The degree of an automaton is the minimal non-null value of the degrees of words. Any unambiguous irreducible automaton of degree k has the following property: for any word u of degree k and any word w such that uwu has a non-null degree, uwu has degree k. We first assume that the Fischer cover A of S is codeterministic (or left resolving): for any state p ∈ Q and any word u, there is at most one path labeled by u and ending at p. In this case the degree of A is d = 1. Indeed, since A is a Fischer cover, it has a synchronizing word. Since A is codeterministic, each synchronizing word has degree 1.

Let v (resp. w) be a word which has a non-null and minimal degree k (resp. d = 1) in B (resp. in A). Since B is irreducible, there are words z, z ′ such that vzwz ′ v has a non-null degree. Hence vzwz ′ v has degree k in B and degree d = 1 in A. We set u = vzwz ′ v.

An N-automaton with a set of states Q is a triple I, µ, T , where I and T are two vectors -respectively initial row vector and final column vector -with entries in N, and where µ is a morphism from A * into N Q×Q . It is equivalently defined by the triple I, α(A), T . Two N-automata I, µ, T and J, µ ′ , F are equivalent if and only if, for any word w ∈ A * , Iµ(w)T = Jµ ′ (w)F .

Let 1 A be the row-vector with all coefficients equal to 1 of size the number of states of A, and 1 t A its transpose. It follows from the definition of the word u that the two N-automata

C = k1 A µ A (u), µ A , µ A (u)1 t A ,
and

D = d1 B µ B (u), µ B , µ B (u)1 t B , are equivalent.
The standard Schützenberger reductions of the N-automata C and D over the field R are similar. The reduction of each N-automaton is obtained through a left reduction followed by a right reduction (see for instance [START_REF] Berstel | Rational series and their languages[END_REF] or [START_REF] Sakarovitch | Éléments de théorie des automates[END_REF]).

Since u has degree 1 in A, the initial row (resp. final column) vector of C has a unique non-null coefficient. Consequently, since A is deterministic (resp. codeterministic) and irreducible, the automaton C is left (resp. right) reduced. Hence C is already reduced.

Finally, it is not difficult to see that the transition matrix of D is similar to a matrix having a principal subblock equal to the transition matrix of its left (or right) reduced form. It follows that det(Iα A (A)) divides det(Iα B (A)).

The extension of the proof to sofic shifts that may not have a codeterministic Fischer cover can be obtained with a specialization argument as follows. In the general case, we number the labels of edges of the automaton A so that all edges have distinct labels (see the left part of Figure 3). We get a codeterministic Fischer cover A ′ presenting a new shift S ′ . We denote by A ′ the new alphabet. We define X ′ as the set of words u ∈ A ′ * labels of paths in A ′ , such that the word obtained from u by removing the numbers is in X. We build an automaton B ′ such that for each path in A ′ labeled by a word in X ′ going from state p to state q, we build a path in B ′ from p to q with dummy states in-between (see the right part of Figure 3). Since A ′ is codeterministic, we have det(Iα A ′ (A ′ )) divides det(Iα B ′ (A ′ )). As a consequence, det(Iα A (A)) divides det(Iα B (A)). can be now reduced on the left side. We get that G is similar to H. The upper left block matrix of size 2 of G is similar to α A (A). As a consequence, det(Iα

A (A)) = 1 -a -bb divides det(I -H) which divides det(I -F ) = det(I -α B (A)) = (1 -a -bb)(1 + a -bb).
A variant of the above combinatorial proof uses an argument due to Nasu [START_REF] Nasu | An invariant for bounded-to-one factor maps between transitive sofic subshifts, Ergodic Theory Dynam[END_REF].

We denote by M (resp. M ′ ) the matrix M = a∈A µ A (a) and (resp. M ′ = a∈A µ B (a)). It is known from the Perron-Frobenius theory that M and M ′ have the same positive spectral radius λ, the logarithm of λ being the topological entropy of the sofic shift S [START_REF] Lind | An Introduction to Symbolic Dynamics and Coding[END_REF]. Let U , V (resp. U ′ , V ′ ) be two real positive left and right eigenvectors of M (resp. of M ′ ) for the eigenvalue λ. One can choose these vectors such that U V = U ′ V ′ = 1. With these settings, the two R-automata C = U, µ A , V and D = U ′ , µ B , V ′ are equivalent.

The proof of this equivalence relies on the following arguments. One first divides µ A and µ B by λ to reduce to the case λ = 1.

For any word x ∈ A * and any R-automaton S = I, µ, T , we denote by π S (x) the real coefficient Iµ(x)T . We say that π S is recognized by S. The functions π C and π D define two rational probability measures on A * [START_REF] Hansel | Rational probability measures[END_REF]. By definition, this means that they are recognized by an R-automaton and satisfy the coherence condition: for any x ∈ A * , for any k ≥ 0, These measures π S for S equal to C or D satisfy the following two additional properties.

• The left invariance property: for any x ∈ A * , for any k ≥ 0, Moreover, since the automata A and B are unambiguous, one can show that there are positive real numbers ρ, ρ ′ such that for any x ∈ A * , π C (x) ≤ ρ π D (x) and π D (x) ≤ ρ ′ π C (x). Indeed, for any word x, we have µ A (x) = 0 if and only if µ B (x) = 0. Hence π C (x) = 0 if and only if π D (x) = 0. Moreover, since A is unambiguous, for any word x such that µ A (x) = 0, we have min i,j

U i V j ≤ U µ A (x)V ≤ ( i U i ) max i (V i ).
Hence, for any word x such that µ A (x) = 0, there are positive real numbers

k 1 , k 2 , k ′ 1 , k ′ 2 with k 1 ≤ U µ A (x)V ≤ k 2 , k ′ 1 ≤ U ′ µ B (x)V ′ ≤ k ′ 2 .
As a consequence, there are positive real numbers ρ, ρ ′ such that for any x ∈ A * , π C (x) ≤ ρ π D (x) and π D (x) ≤ ρ ′ π C (x). We deduce the equivalence of C and D from these inequalities as follows. Let x be a word such that µ A (x) = 0. Let us assume that π C (x) > π D (x). We have A reduction of these automata is used to finish this proof as in the previous proof.

π C (x)π C (x) = lim

Figure 1 :

 1 Figure1: The Fischer covers of the even system S on the left, and of the golden mean system T on the right.

Figure 2 :

 2 Figure 2: The automaton A (on the left), and the automaton B computed from A and X = {aa, ab, ba, bb} (on the right).

Figure 3 :Example 6 . 5 .

 365 Figure 3: The automaton A ′ (on the left), and the automaton B ′ computed from A ′ and X ′ = {aa, ab 1 , b 2 a, b 1 b 2 , b 2 , b 1 } (on the right).

  w∈A k π S (xw) = π S (x).Let us prove that π C satisfies this condition (the proof for π D is similar). For any x ∈ A * , for any k ≥ 0, µ = µ A ,w∈A k π C (xw) = U w∈A k µ(x)µ(w)V, = U µ(x) w∈A k µ(w)V, = U µ(x)M k V = U µ(x)V = π C (x).

M

  w∈A k π S (wx) = π S (x).• An ergodic property: for any x, y ∈ A * , π S (xwy) = π S (x)π S (y).The left invariance is proved as the coherence condition. Let us now show the ergodic property. For any x, y∈ A * , µ = µ A , i )µ(y)V, = U µ(x)(V U )µ(y)V, = π A (C)π C (y).The third equality above uses the fact that (lim n→∞1 n n-1 i=0 M i ) = V U since M is an irreducible stochastic matrix.

  π D (xwx), = ρ π D (x)π D (x).By induction, we get(π C (x)) n ≤ ρ(π D (x)) n .Or equivalently,π C (x) π D (x) n ≤ ρ,which contradicts the hypothesis. Hence π C (x) ≤ π D (x). We obtain similarly π D (x) ≤ π C (x) and thus C and D are equivalent.

Acknowledgments The authors would like to thank the anonymous reviewers for improving the presentation.


Guillaume Blin
email: gblin@univ-mlv.fr

David Faye
email: dfaye@igm.univ-mlv.fr

Jens Stoye
email: stoye@techfak.uni-bielefeld.de

Finding Nested Common Intervals Efficiently

In this paper, we study the problem of efficiently finding gene clusters formalized by nested common intervals between two genomes represented either as permutations or as sequences. Considering permutations, we give several algorithms whose running time depends on the size of the actual output rather than the output in the worst case. Indeed, we first provide a straightforward cubic time algorithm for finding all nested common intervals. We reduce this complexity by providing a quadratic time algorithm computing an irredundant output. We then show, by providing a third algorithm, that finding only the maximal nested common intervals can be done in linear time. Finally, we prove that finding approximate nested common intervals is fixed parameter tractable. Considering sequences, we provide solutions (modifications of previously defined algorithms and a new algorithm) for different variants of the problem, depending on the treatment one wants to apply to duplicated genes. This includes a polynomial-time algorithm for a variant implying a matching of the genes in the cluster, a setting that for other problems often leads to hardness.

Introduction and related work

Computational comparative genomics is an active field of bioinformatics. One of the problems arising in this domain consists in comparing two or more species by seeking for gene clusters between their genomes. A gene cluster refers to a set of genes appearing, in spatial proximity along the chromosome, in at least two genomes. Genomes evolved from a common ancestor tend to share some gene clusters. Therefore, they may be used for reconstructing recent evolutionary history and inferring putative functional assignments for genes.

The genome evolution process, including -among others -fundamental evolutionary events such as gene duplication and loss [START_REF] Ohno | Evolution by gene duplication[END_REF], has given rise to various genome models and cluster definitions. Indeed, genomes may be either represented as permutations (allowing one-to-one correspondence between genes of different genomes) or sequenceswhere the same letter (i.e. gene) may occur more than once (a more realistic model but with higher complexity). In both those models, there may exist, or not, genes not shared between two genomes (often called gaps).

Moreover, when modeling genomes for gene order analysis, one may consider either two or multiple genomes, seeking for exact or approximate occurrences, finding all or just nonextensible (i.e. maximal ) occurrences.

There are numerous ways of mathematical formalizations of gene clusters. Among others, one can mention common substrings (which require a full conservation), common intervals [START_REF] Uno | Fast algorithms to enumerate all common intervals of two permutations[END_REF][START_REF] Schmidt | Quadratic time algorithms for finding common intervals in two and more sequences[END_REF][START_REF] Didier | Character sets of strings[END_REF]Bergeron et al., 2008a) (genes must occur consecutively, regardless of their order), conserved intervals [START_REF] Bergeron | On the similarity of sets of permutations and its applications to genome comparison[END_REF][START_REF] Angibaud | On the approximability of comparing genomes with duplicates[END_REF] (common intervals, framed by the same two genes), gene teams [START_REF] Bergeron | The algorithmic of gene teams[END_REF][START_REF] He | Identifying conserved gene clusters in the presence of homology families[END_REF][START_REF] Zhang | Gene team tree: A hierarchical representation of gene teams for all gap lengths[END_REF] (genes in a cluster must not be interrupted by long stretches of genes not belonging to the cluster), and approximate common intervals [START_REF] Rahmann | Integer linear programs for discovering approximate gene clusters[END_REF][START_REF] Böcker | Computation of median gene clusters[END_REF] (common intervals that may contain few genes from outside the cluster). For more details, please refer to (Bergeron et al., 2008b).

In this article, we focus on another model -namely the nested common intervals -which was mentioned in [START_REF] Hoberman | The incompatible desiderata of gene cluster properties[END_REF]. In this model, an additional constraintnamely the nestedness -(observed in real data [START_REF] Kurzik-Dumke | Identification of a novel Drosophila melanogaster gene, angel, a member of a nested gene cluster at locus 59F4,5[END_REF]) is added to the cluster definition. [START_REF] Hoberman | The incompatible desiderata of gene cluster properties[END_REF] argued that, depending on the dataset, if the nestedness assumption is not excluding clusters from the data, then it can strengthen the significance of detected clusters since it reduces the probability of observing them by chance.

As far as we know, [START_REF] Hoberman | The incompatible desiderata of gene cluster properties[END_REF] was the only attempt to take into account the nestedness assumption in a gene cluster model (namely gene teams) and yields to a quadratic-time greedy bottom-up algorithm. In the following, we will give some efficient algorithms to find all nested common intervals, for different definitions of such intervals, between two genomes.

After providing basic definitions (Section 2), we will provide in Section 3 complexity results for the problems of computing irredundant and maximal nested common intervals in output-optimal time. In Section 4, we will provide algorithms to handle genomes represented as sequences considering three different variants of the problem. Finally, in Section 5, we will consider a natural extension of the problem, namely allowing gaps in the definition of nested common intervals.

Definitions and previous works

Let π 1 and π 2 be our genomes, represented as permutations over N := {1, . . . , n}. For any i ≤ j, π[i, j] will refer to the sequence of elements (π[i],

π[i + 1], . . . , π[j]). Let CS(π[i, j]) := {π[k] | k ∈ [i, j]} denote the character set of the interval [i, j] of π. A subset C ⊆ N is called a common interval of π 1 and π 2 if and only if there exist 1 ≤ i 1 < j 1 ≤ n and 1 ≤ i 2 < j 2 ≤ n such that C = CS(π 1 [i 1 , j 1 ]) = CS(π 2 [i 2 , j 2 ]
). Note that this definition purposely excludes common intervals of size one since they would not be considered in the more general nested common interval definition. The intervals [i 1 , j 1 ] and [i 2 , j 2 ] are called the locations of C in π 1 and π 2 , respectively. Note also that in case of multiple gene copies (i.e. considering sequences instead of permutations), these definitions will be slightly different, as detailed in the beginning of Section 4.

Given two common intervals

C and C of π 1 and π 2 , C contains C if and only if C ⊆ C.
This implies that the location of C in π 1 (resp. π 2 ) is included in the location of C in π 1 (resp. π 2 ).

Definition 1 A common interval C is called a nested common interval of π 1 and π 2 if either |C| = 2, or if |C| > 2 and it contains a nested common interval of size |C| -1.
Note that this recursive definition implies that for any nested common interval C there exists a series of nested common intervals such that

C 2 ⊆ C 3 ⊆ • • • ⊆ C with |C i | = i. Definition 2 A nested common interval of size is maximal if it is not contained in a nested common interval of size + 1.
A maximal nested common interval can however still be contained in a larger nested common interval. For example, considering π 1 := (3, 1, 2, 4, 5, 6) and π 2 := (1, 2, 3, 4, 5, 6), the maximal nested common interval [4,6] in π 1 is contained in [1,6].

The general Nested Common Intervals problem may be defined as follows: Given two genomes, find all their nested common intervals. One can then consider genomes either as permutations or sequences and might also be interested in finding only the maximal nested common intervals and/or allowing gaps. In the two following sections, we will give efficient algorithms for both permutations and sequences without considering gaps. We will, then, provide FPT solutions consisting of an extension of previously defined algorithms for finding maximal nested common intervals considering gaps in both permutations and sequences (except for the last variant that we leave as an open problem).

In (Bergeron et al., 2008a), a theoretical framework was introduced for computing common intervals based on a linear space basis. Of importance here is the technique proposed in order to generate the PQ-tree [START_REF] Booth | Testing for the consecutive ones property, interval graphs and graph planarity using P Q-tree algorithms[END_REF][START_REF] Landau | Gene proximity analysis across whole genomes via PQ trees[END_REF] corresponding to a linear space basis for computing all the common intervals of K permutations. Generating this basis can be done in O(n) time for two permutations of size n. Then one can, by a browsing of the tree, generate all the common intervals in O(n + z) time where z is the size of the output. One can adapt this algorithm in order to find nested common intervals in O(n + z) time.

In this work, we do not follow that approach, but instead provide algorithms for a more direct detection of the nested common intervals.

Nested common intervals on permutations

As described in [START_REF] Uno | Fast algorithms to enumerate all common intervals of two permutations[END_REF][START_REF] Schmidt | Quadratic time algorithms for finding common intervals in two and more sequences[END_REF][START_REF] Didier | Character sets of strings[END_REF], when considering permutations, both common substrings and common intervals can be found in optimal, essentially linear time. As we will show, not surprisingly, finding nested common intervals on permutations can also be done efficiently.

Finding all nested common intervals

First, one has to notice that the number of nested common intervals can be quadratic in n (e.g. when π 1 = π 2 ). However, in many practical cases the number of nested common intervals may be much smaller, such that one can still achieve lower time complexity by developing methods whose running time depends on the size of the actual output and not of the output in the worst case.

In the following, we will w.l.o.g. assume that π 1 is the identity permutation and rename π 2 by π for ease of notation. A naive bottom-up algorithm, inspired from the one given in [START_REF] Hoberman | The incompatible desiderata of gene cluster properties[END_REF] and straightforwardly following the definition of nested common intervals, can be defined as in Algorithm 1.

Algorithm 1 uses a bottom-up approach; namely it tries to compute any nested common interval from smaller ones by an extension procedure. More precisely, starting from a nested common interval of size one, the algorithm tries to extend this last interval both to the left and to the right by iteratively trying to add the left (resp. right) neighbor if it still induces a common interval (i.e. l--, l++, r--, r++).

Clearly such an algorithm requires O(n + z) time to report all nested common intervals where z is the size of the output. However, the output may be highly redundant as several Algorithm 1 Find all nested common intervals 1: for i ← 1, . . . , n do 2:

l ← i, r ← i 3: repeat 4: l ← l, r ← r 5: if π[l -1] = min(CS(π[l , r ])) -1 or π[r + 1] = max(CS(π[l , r ])) + 1 then 6: while π[l -1] = min(CS(π[l, r ])) -1 do l--done 7: while π[r + 1] = max(CS(π[l , r])) + 1 do r++ done 8: else 9: while π[l -1] = max(CS(π[l, r ])) + 1 do l--done 10: while π[r + 1] = min(CS(π[l , r])) -1 do r++ done 11: end if 12: report all intervals [l , r ] with l ≤ l ≤ l and r ≤ r ≤ r except [l , r ] 13:
until l = l and r = r 14: end for intervals will be identified more than once. The worst case is when one considers π = (1, 2, . . . , n). More precisely, in this case some of the O(n 2 ) nested common intervals will be reported up to n times, giving a total worst-case runtime of O(n 3 ).

Therefore, one may be interested in computing an irredundant output. The main improvement we propose consists in a simple preprocessing step that will speed up our algorithm for nested common intervals. Let us define a run of two permutations π 1 and π 2 as a pair of intervals

([i 1 , j 1 ], [i 2 , j 2 ]) such that π 1 [i 1 , j 1 ] = π 2 [i 2 , j 2 ] or π 1 [i 1 , j 1 ] = ← ----- π 2 [i 2 , j 2 ]
where ←x := (x k , x k-1 , . . . , x 1 ) denotes the reverse of sequence x = (x 1 , x 2 , . . . , x k ). A run is maximal if it cannot be extended to the left or right. Since a run can also be of size one, two permutations can always be decomposed into their maximal runs with respect to each other.

For example, in the following the maximal runs are underlined: , 2, 3, 4, 5, 6, 7, 8, 9) and π 2 = (4, 3, 2, 1, 5, 9, 6, 7, 8).

π 1 = (1
Given a decomposition of two permutations into their maximal runs with respect to each other, a breakpoint will refer to any pair of neighboring elements that belong to different runs. In the above example, π 1 (resp. π 2 ) contains three breakpoints (4, 5), (5, 6) and (8, 9) (resp. (1, 5), (5, 9) and (9, 6)). By definition, the number of breakpoints is one less than the number of runs. When considering one of π 1 and π 2 as being the identity permutation then a run may be defined as a single interval.

Algorithm 2, hereafter defined, computes irredundant output by making use of the two following simple observations. In fact, it tries to extend the actual nested common interval by more than one position at each step using the notion of run.

Lemma 1 All subintervals of length at least 2 in a run are nested common intervals.

Lemma 2 In the procedure of constructing incrementally a nested common interval by extension, when one reaches up to one end of a run such that the begin/end of this run can be included, then the whole run can be included and all subintervals ending/beginning in this run can be reported as nested common intervals.

Proof. By definition, the elements of a run [i, j] in π with respect to the identity permutation are consecutive integers strictly increasing or decreasing. Therefore, in an incremental construction by extension of a nested common interval nc that has a run [i, j] as its right (resp. left) neighbor, if one may extend nc by i (resp. j) then, by definition,

π[i] (resp. π[j])
is the minimal or maximal element among the elements of the extended interval. Thus, all the elements of the run [i, j] may be added one by one, each leading to a new nested common interval. 2

Consequently, by identifying the runs in a preprocessing step (which can be easily done in linear time), whenever during an extension a border of a run is included, the whole run is added at once and all sub-intervals are reported. The details are given in Algorithm 2 which employs a data structure end defined as follows: if i is the index of the first or last element of a run in π then end [i] is the index of the other end of that run; end[i] = 0 otherwise.

Algorithm 2 Find all nested common intervals, irredundant version 1: decompose π into maximal runs w.r.t. id and store them in a data structure end 2: for i ← 1, . . . , n -1 do

3: if end[i] > i then 4: l ← i, r ← end[i] 5:
report all intervals [l , r ] with l ≤ l < r ≤ r 6:

repeat 7: l ← l, r ← r 8: if π[l -1] = min(CS(π[l , r ])) -1 or π[r +1] = max(CS(π[l , r ])) + 1 then 9: if π[l -1] = min(CS(π[l, r ])) -1 then l ← end[l -1] end if 10: if π[r + 1] = max(CS(π[l , r])) + 1 then r ← end[r + 1] end if 11: else 12: if π[l -1] = max(CS(π[l, r ])) + 1 then l ← end[l -1] end if 13: if π[r + 1] = min(CS(π[l , r])) -1 then r ← end[r + 1] end if 14: end if 15:
report all intervals [l , r ] with l ≤ l ≤ l and r ≤ r ≤ r except [l , r ] 16:

until l = l and r = r Proof. In order to be possibly reported twice, an interval would have to cover (i.e. include both) two different runs. However, in order to yield the interval, the breakpoint(s) between these two runs would have to be passed through twice, which is not possible by Lemma 3.

2

Finding all maximal nested common intervals

As previously mentioned, one might also be interested in finding only the maximal nested common intervals in optimal time O(n+z) where z is the number of maximal nested common intervals of π 1 and π 2 , since there will be fewer. In fact, we will first prove that the number of maximal nested common intervals is in O(n) leading to an overall linear time algorithm.

Lemma 5 Every element of π is contained in at most three different maximal nested common intervals.

Proof. This follows immediately from the correctness of Lemma 3. Indeed, according to Lemma 3 each position can be reached from at most two directions. Thus, the only case where an element of π may be contained in exactly three different maximal nested common

intervals nc 1 = [i 1 , j 1 ], nc 2 = [i 2 , j 2 ] and nc 3 = [i 3 , j 3 ] is when i 1 ≤ i 2 ≤ i 3 ≤ j 1 ≤ j 2 ≤ j 3 .
For example, considering π 1 = (2, 1, 3, 4, 6, 5) and π 2 = (1, 2, 3, 4, 5, 6), the element 3 in π 1 is contained in (2, 1, 3, 4), (3, 4) and (3,4,6,5). 2

In order to get only the locations of maximal nested common intervals, one has to modify Algorithm 2 such that only the locations at the end of an extension are reported. To do so, one has simply to (1) remove from Algorithm 2 lines 5 and 15 and (2) report the unique interval [l, r] -which is by definition maximal -just after the end of the repeat ... until loop (currently line 16).

Clearly, the time complexity of this slightly modified version of Algorithm 2 is unchanged; that is O(n + z) where z is the size of the output. Lemma 5 implies that the number of maximal nested common intervals is in O(n), leading to an overall linear time.

Nested common intervals on sequences

In this section, we will give algorithms to handle genomes represented as sequences (i.e. genes may be duplicated). In the following, we will assume that our genomes, denoted by S 1 and S 2 , are defined over a bounded integer alphabet Σ = {1, . . . , σ} and have maximal length n. The precise definition of nestedness in sequences is subtle. Therefore, we propose three different variants of the problem, depending on the treatment one wants to apply when, during the extension of an interval, an element that is already inside the interval is met once again. The definitions and the differences are illustrated by the running example of two sequences S 1 = (3, 1, 2, 3, 4, 5, 6) andS 2 = (2,3,1,3,2,4,6,3,5), see also Figure 1.

First, one may just extend the interval "for free", only caring about the "innermost occurrence"; all other occurrences are considered as not contributing to the cluster content. This definition follows the same logic as earlier ones used for common intervals [START_REF] Schmidt | Quadratic time algorithms for finding common intervals in two and more sequences[END_REF][START_REF] Didier | Character sets of strings[END_REF] and for approximate common intervals [START_REF] Böcker | Computation of median gene clusters[END_REF].

In our example, starting from the left in S 1 with the characters 3 and 1 will immediately yield three different locations of the character set [3,4]). Adding the next character in S 1 , 2, will also allow to add the following 3 (at index 4) since a 3 already belonged to the cluster. Combined with the five possible intervals in S 2 that can be obtained by extending the three intervals containing {1, 3}, this yields ten cluster locations for ([1, 4], [1,4]), ([1, 4], [1,5]), ([1, 4], [2,5]), ([1, 4], [3,5]).

C 2 = {1, 3}: ([1, 2], [2, 3]), ([1, 2], [2, 4]) and ([1, 2],
C 3 = {1, 2, 3}: ([1, 3], [1, 3]), ([1, 3], [1, 4]), ([1, 3], [1, 5]), ([1, 3], [2, 5]), ([1, 3], [3, 5]), ([1, 4], [1, 3]),
A slight modification of our naive Algorithm 1 leads to an O(n 3 ) algorithm. Indeed, since the sequences may contain duplicates, one has to start the extension procedure with all possible pairs (S 1 [i], S 2 [j]) where 1 ≤ i ≤ |S 1 | and 1 ≤ j ≤ |S 2 |. Moreover, after each extension step all genes that are already members of the cluster have to be "freely" included.

This can be tested efficiently by storing the elements belonging to the current cluster in a bit vector c[1, . . . , σ].

The resulting Algorithm 3 -which clearly runs in O(n 3 ) time as each pair of index positions (i, j) is considered at most once and for each of them the extension cannot include more than n steps -only reports maximal gene clusters as previously done for permutations.

Second, one may forbid the inclusion of a second copy of a gene in a nested common interval. In our example, for C 2 = {1, 3} at indices 1 and 2 in S 1 this would give only the two locations ([1, 2], [2, 3]) and ([1, 2], [3,4]), and the extension by character 2 would be allowed in only one of the two possible directions, giving for C 3 = {1, 2, 3} the locations ([1, 3], [1,3]) and ([1, 3], [3,5]). Note, however, that if one starts with the intervals [2, 3] or [3,4] in S 1 , more locations can be obtained for C 3 = {1, 2, 3}. This problem variant can also be solved easily, by a quite similar algorithm which stops any extension when a gene already contained in the common interval is encountered.

Finally, one may be interested in finding a bijection (sometimes called matching in the computational comparative genomics literature) where, inside a nested common interval, each gene occurrence in S 1 must match a unique gene occurrence in S 2 from the same gene family. In our example, of the ten locations for C 3 = {1, 2, 3} listed above, only those six with the same cardinality of characters are eligible as nested common intervals of this type: ( [2,5]). Moreover, among the possible matchings, only those are allowed for which the necessary smaller intervals exist.

[1, 3], [1, 3]), ([1, 3], [3, 5]), ([1, 4], [1, 4]), ([1, 4],
For example, the pair of locations ([1, 4], [1,4]) as an extension of the locations ([1, 3], [1, 3]) implies that the 3 at index 4 in S 1 is matched with the 3 at index 4 in S 2 and not with the Algorithm 3 Find all maximal nested common intervals in two sequences

1: for i ← 1, . . . , |S 1 | do 2:
for each occurrence j of S 1 [i] in S 2 do 3:

for each k ← 1, . . . , σ do c[k] ← (k = S 1 [i]) done 4: l 1 ← i, r 1 ← i 5: l 2 ← j, r 2 ← j 6: repeat 7: while c[S 1 [l 1 -1]] = true do l 1 --done 8: while c[S 1 [r 1 + 1]] = true do r 1 ++ done 9: while c[S 2 [l 2 -1]] = true do l 2 --done 10: while c[S 2 [r 2 + 1]] = true do r 2 ++ done 11: l 1 ← l 1 , r 1 ← r 1 12: if S 1 [l 1 -1] = S 2 [l 2 -1] or S 1 [r 1 + 1] = S 2 [r 2 + 1] then 13: while S 1 [l 1 -1] = S 2 [l 2 -1] do 14: l 1 --, l 2 --, c[S 1 [l 1 ]] ← true 15: while c[S 1 [l 1 -1]] = true do l 1 --done 16: while c[S 2 [l 2 -1]] = true do l 2 --done 17:
end while 18:

while

S 1 [r 1 + 1] = S 2 [r 2 + 1] do 19: r 1 ++, r 2 ++, c[S 1 [r 1 ]] ← true 20: while c[S 1 [r 1 + 1]] = true do r 1 ++ done 21: while c[S 2 [r 2 + 1]] = true do r 2 ++ done 22:
end while while

S 1 [r 1 + 1] = S 2 [l 2 -1] do 30: r 1 ++, l 2 --, c[S 1 [r 1 ]] ← true 31: while c[S 1 [r 1 + 1]] = true do r 1 ++ done 32: while c[S 2 [l 2 -1]] = true do l 2 --done 33:
end while 34:

end if

35:

until l 1 = l 1 and r 1 = r 1 36:

report ([l 1 , r 1 ], [l 2 , r 2 ]) 37:
end for 38: end for one at index 2. Surprisingly, the nestedness constraint leads to a polynomial time algorithm whereas 3 1 2 3 4 5 6 ) 1 2 3 4 5 6 7 S 2 = (2 3 1 3 2 4 6 3 5 ) 1 2 3 4 5 6 7 8 (2,3,1,3,2,4,6,3,5).

S 1 = (
for many other paradigms, considering matching and duplicates leads to hardness [START_REF] Blin | Comparing genomes with duplications: a computational complexity point of view[END_REF]. Unfortunately, we only know a very inefficient algorithm described hereafter.

The main idea is to, first, construct a directed acyclic graph G whose vertices correspond to pairs of intervals ([i 1 , j 1 ], [i 2 , j 2 ]), one from S 1 and one from S 2 , that contain the same multiset of characters. In G, an edge is drawn from a

vertex v = ([i 1 , j 1 ], [i 2 , j 2 ]) to a vertex v = ([i 1 , j 1 ], [i 2 , j 2 ]
) if and only if the corresponding interval pairs differ by one in length, i.e.

|(j 1 -i 1 ) -(j 1 -i 1 )| = 1, and the shorter one is contained in the longer one, i.e. ((i 1 = i 1 )

or (j 1 = j 1 )) and ((i 2 = i 2 ) or (j 2 = j 2 )). An illustration is given in Figure 1.

Since, for a given multiset of cardinality there are at most (n -+ 1) 2 vertices in the graph, the total number of vertices in G is bounded by O(n 3 ). Moreover, by definition, each vertex has an output degree of at most four, hence the number of edges is also bounded by O(n 3 ). Finally, G can clearly be constructed in polynomial time.

One can easily see that there is a correspondence between nested gene clusters and directed paths in G starting from vertices corresponding to multisets of size 2. Indeed, a path (ci 1 , ci 2 , . . . , ci k ) in this DAG, where ci 1 , ci 2 , . . . , ci k are common intervals, induces that ci 1 ⊆ ci 2 ⊆ . . . ⊆ ci k and for all j, 1 ≤ j < k, we have |ci j | + 1 = |ci j+1 |. Therefore, since any common interval of size 2 is a nested common interval, in any such path, if ci 1 is of size 2 then, by definition, any common interval of this path is a nested common interval.

Thus, the nested gene clusters can be reported in polynomial time. Indeed, building the DAG can be done in O(n 3 ) time. Then, one has to browse any path starting from a vertex corresponding to a common interval of size 2. Since there are at most n -1 such common intervals, and each vertex has an output degree of at most four, on the whole the number of such paths is bounded by (n -1) • 4(n -2); i.e. O(n 2 ).

5 Finding all maximal approximate nested common intervals

As a natural extension of the problem, we will consider allowing gaps in the definition of nested common intervals. Let us recall that an approximate common interval is a common interval that may contain an overall bounded number of genes not belonging to the cluster (called gaps). The natural extension of nested common intervals -approximate nested common intervals -may thus be defined as follows: an approximate common interval [i, j] is an approximate nested common interval if removing the gaps from [i, j] produces a nested common interval.

The general Approximate Nested Common Intervals problem may be defined as follows: Given two genomes, find all their approximate nested common intervals. As we will show, this last problem is fixed parameter tractable (FPT) in the number of allowed gaps in any approximate nested common interval.

Theorem 2 Given two genomes as permutations (resp. sequences), finding all their approximate nested common intervals can be done in O(n

• 3 k ) (resp. O(n 3 • 15 k ))
where k is the maximal number of allowed gaps.

We leave the problem of determining the complexity of the Approximate Nested

Common Intervals problem as an open problem.

Considering permutations

One can slightly modify Algorithm 2 in order to both, only report maximal occurrences and allowing a bounded number of gaps. In order to find all maximal approximate nested common intervals in two permutations, one has to call the expansion function defined in Algorithm 4 for all the starting positions of any maximal run (i.e. each position i,

1 ≤ i ≤ |π|, such that end[i] ≥ i): expansion(maxgap, i, end[i], min(π[i], π[end[i]]), max(π[i], π[end[i]])).
Indeed, since one may use a gap to extend any maximal run, one has to start from every maximal run, even from those of size one. Lines 4 to 21 of Algorithm 4 are similar to the code of Algorithm 2 and correspond to the maximal expansion from positions l and r considering min and max as the current minimum and maximum values. Indeed, since there may be some gaps in [l, r], computing the minimum and maximum values from the character set is not possible anymore. After this expansion process, we may report an approximate nested common interval if it contains at least two elements (i.e. min = max) and then try to extend it again by considering either the left neighbor (i.e. l -1) or the right one (i.e. r + 1) or both as gaps (lines 25 to 35). This last part leads to the exponential complexity of the algorithm.

The overall time complexity is in O(n • 3 k ) where k is the maximal number of allowed gaps. This is straightforward to see since when allowing gaps, Lemma 5 still holds for the extension procedure and in lines 25 to 35, one has to call expansion procedure for each combination of {(l -1, r), (l, r + 1), (l -1, r + 1)} untill nbgap becomes null. On the whole, in the worst case, the execution of the algorithm may needs 3 k calls to expansive (a call tree with nodes

Considering sequences

Considering sequences, one can similarly slightly modify Algorithm 3 in order to handle the first two variants. In order to find all maximal approximate nested common intervals in seq expansion(i, i, j, j, c).

As done in Algorithm 3, we use a bit vector c[1, . . . , σ] in order to store the elements belonging to the current cluster and test efficiently if an element has already been added to it.

Lines 4 to 34 are quite similar to the code of Algorithm 3 and correspond to the maximal expansion from positions l 1 , r 1 and l 2 , r 2 considering c as the character set of the intervals without including gaps. After this expansion process, we may report an approximate nested

  Algorithm 2 has an O(n 2 ) time complexity.Proof. It is easily seen that the time complexity remains in O(n + z) with z being the output size, except that this time the output is irredundant (i.e. each nested common interval is reported exactly once). Since the number of nested common intervals is at most quadratic, the complexity follows. 2 When applied to π := (1, 2, 3, 6, 4, 5) for example, one may check that Algorithm 2 willreport locations [1, 2], [1, 3], [2, 3] when i = 1, locations [5, 6], [4, 6], [1, 6], [2, 6],[3, 6] when i = 5, and nothing for the other values of i. Let us prove this interesting property of Algorithm 2.Lemma 3 In Algorithm 2, any breakpoint is considered at most once during the extension procedure described from lines 8 to 14.Proof. In the following, a breakpoint will be passed through from left (resp. from right) when considered during an extension procedure to the right (resp. left). Assume bp = (π[x], π[y]) is a breakpoint in π with respect to the identity permutation. Then y = x + 1 and there are only two possibilities for bp to be passed through twice: either (1) once from the left and once from the right, or (2) twice from the same side.Let us first consider the case where bp is passed through from both left and right. Therefore assume thatπ = (. . . , π[X], . . . , π[x], π[y], . . . , π[Y ], . . .)whereC 1 := CS(π[X, x]) and C 2 := CS(π[y, Y ]) are nested common intervals (otherwise bp would not be passed through more than once). Further assume w.l.o.g. that bp is passed in the extension of interval [X, x] (a similar proof handles the extension of [y, Y ]) whose maximum (or minimum) element is M := max(C 1 ) (resp. m := min(C 1 )). Then, in order for [X, x] to be extensible, either π[y] = M + 1 or π[y] = m -1. Let us assume that π[y] = M + 1 (the case where π[y] = m -1 can be shown similarly). We will show that bp cannot be passed through in the other direction, i.e. in an extension of [y, Y ]. Since π[y] = M + 1 and each of the two intervals [X, x] and [y, Y ] consists of consecutive integers, we have that all elements in C 1 are smaller than any element in C 2 . Thus, for an extension in the left direction across bp, the largest element of C 1 must be at its right end, i.e. π[x] = M . However, if this was the case, then bp = (π[x], π[y]) = (M, M + 1) would not be a breakpoint, a contradiction. Now let us consider the case where bp is passed through twice from the same side, starting with different runs. Therefore assume that π = (. . . , π[X ], . . . , π[X], . . . , π[x], π[y], . . .) where C 1 := CS(π[X, x]) and C 2 := CS(π[X , x]) are nested common intervals derived from different runs (i.e. reported from two different values of i), one in the interval [X, x] and the other in the interval [X , X -1]. Further assume w.l.o.g. that bp is passed through in the extension of [X, x] (a similar proof handles the extension of [X , x]) whose maximum (or minimum) element is M := max(C 1 ) (resp. m := min(C 1 )). Then, in order for [X, x] to be extensible, either π[y] = M + 1 or π[y] = m -1. Let us assume that π[y] = M + 1 (the case where π[y] = m -1 can be shown similarly). We will show that bp cannot be passed again in this direction, i.e. in an extension of [X , x]. Since π[y] = M +1 and, by construction, C 1 ⊂ C 2 , we have that all elements in CS(π[X , X -1]) are smaller than any element in C 1 . Moreover, since bp is a breakpoint, we have that π[x] = M and, more precisely, π[x] < M . Then, any extension of [X , X -1] would not be able to include M since at least one necessary intermediate element (namely π[x]) would not have been previously included. Thus, all cases are covered and the lemma is proved. 2 Irredundancy of the locations of nested common intervals returned by Algorithm 2 follows immediately. Lemma 4 In Algorithm 2, starting from two different runs (cf. line 4) cannot yield to reporting the same nested common interval twice.

  S 1 [l 1 -1] = S 2 [r 2 + 1] do 25: l 1 --, r 2 ++, c[S 1 [l 1 ]] ← true 26: while c[S 1 [l 1 -1]] = true do l 1 --done 27: while c[S 2 [r 2 + 1]] = true do r 2 ++ done

  two sequences, one has to call the seq expansion function defined in Algorithm 5 for each position i, 1 ≤ i ≤ |S 1 |, and for each occurrencej of S 1 [i] in S 2 such that for all k, 1 ≤ k ≤ σ, c[k] = S 1 [i]:

  common interval and then try to extend it again by considering (in lines 25 to 35) any combination of left neighbors (i.e. l 1 -1 and l 2 -1) and right ones (i.e. r 1 + 1 and r 2 + 1) as gaps.This last part leads to the exponential complexity of the algorithm. The overall time complexity is in O(n 3 • 15 k ) where k is the maximal number of allowed gaps. This is straightforward to see since the expansion can still be done in O(n 3 ) time, whereas one has to test6 ConclusionIn this article, we proposed a set of efficient algorithms considering the nestedness assumption in the common intervals model of gene clusters for genomes represented both as permutations and as sequences. Two main questions remain open: (1) finding a more efficient algorithm for the last variant of nested common intervals on sequences and (2) determining the complexity of the Approximate Nested Common Intervals problem.

Acknowledgments

The authors wish to thank Ferdinando Cicalese, Martin Milanič and Mathieu Raffinot for helpful suggestions on the complexity of finding nested common intervals on sequences and on PQ-tree aspects.

Algorithm 4 Expansion function

1: expansion(nbgap, l, r, min, max){ 2: //try to extend the approximate nested common interval [l, r] with at most nbgap 3: //considering that min and max are resp. the minimum and maximum elements of [l, r] 4: repeat

end if 35: end if 36: } of degree 3 and depth nbgap ; i.e. k).

end while 16:

end while 21: