Laurent Bulteau
email: laurent.bulteau@univ-nantes.fr

Guillaume Fertin
email: guillaume.fertin@univ-nantes.fr

Irena Rusu
email: irena.rusu@univ-nantes.fr

Sorting by Transpositions is Difficult

In comparative genomics, a transposition is an operation that exchanges two consecutive sequences of genes in a genome. The transposition distance, that is, the minimum number of transpositions needed to transform a genome into another, can be considered as a relevant evolutionary distance. The problem of computing this distance when genomes are represented by permutations, called the SORTING BY TRANSPOSITIONS problem (SBT), has been introduced by Bafna and Pevzner [3] in 1995. It has naturally been the focus of a number of studies, but the computational complexity of this problem has remained undetermined for 15 years. In this paper, we answer this long-standing open question by proving that the SORTING BY TRANSPOSITIONS problem is NP-hard. As a corollary of our result, we also prove that the following problem from [9] is NP-hard: given a permutation π, is it possible to sort π using d b (π)/3 permutations, where d b (π) is the number of breakpoints of π?

Introduction

Along with reversals, transpositions are one of the most elementary large-scale operations that can affect a genome. A transposition consists in swapping two consecutive sequences of genes or, equivalently, in moving a sequence of genes from one place to another in the genome. The transposition distance between two genomes is the minimum number of such operations that are needed to transform one genome into the other. Computing this distance is a challenge in comparative genomics, since it gives a maximum parsimony evolution scenario between the two genomes.

The SORTING BY TRANSPOSITIONS problem is the problem of computing the transposition distance between genomes represented by permutations: see [START_REF] Fertin | Combinatorics of genome rearrangements[END_REF] for a detailed review on this problem and its variants. Since its introduction by Bafna and Pevzner [START_REF] Bafna | Sorting permutations by transpositions[END_REF][START_REF] Bafna | Sorting by transpositions[END_REF], the complexity class of this problem has never been established. Hence a number of studies [START_REF] Bafna | Sorting by transpositions[END_REF][START_REF] Christie | Genome Rearrangement Problems[END_REF][START_REF] Gu | Sorting permutations and its applications in genome analysis[END_REF][START_REF] Hartman | A simpler and faster 1.5-approximation algorithm for sorting by transpositions[END_REF][START_REF] Elias | A 1.375-approximation algorithm for sorting by transpositions[END_REF][START_REF] Benoît-Gagné | A new and faster method of sorting by transpositions[END_REF][START_REF] Feng | Faster algorithms for sorting by transpositions and sorting by block interchanges[END_REF] aim at designing approximation algorithms or heuristics, the best known fixed-ratio algorithm being a 1.375-approximation [START_REF] Elias | A 1.375-approximation algorithm for sorting by transpositions[END_REF]. Other works [START_REF] Guyer | Subsequence and run heuristics for sorting by transpositions[END_REF][START_REF] Christie | Genome Rearrangement Problems[END_REF][START_REF] Eriksson | Sorting a bridge hand[END_REF][START_REF] Labarre | New bounds and tractable instances for the transposition distance[END_REF][START_REF] Elias | A 1.375-approximation algorithm for sorting by transpositions[END_REF][START_REF] Benoît-Gagné | A new and faster method of sorting by transpositions[END_REF] aim at computing bounds on the transposition distance of a permutation. Studies have also been devoted to variants of this problem, by considering, for example, prefix transpositions [START_REF] Dias | Sorting by prefix transpositions[END_REF][START_REF] Labarre | Edit distances and factorisations of even permutations[END_REF][START_REF] Chitturi | Bounding prefix transposition distance for strings and permutations[END_REF] (in which one of the blocks has to be a prefix of the sequence), or distance between strings [START_REF] Christie | Sorting strings by reversals and by transpositions[END_REF][START_REF] Cormode | The string edit distance matching problem with moves[END_REF][START_REF] Shapira | Edit distance with move operations[END_REF][START_REF] Radcliffe | Reversals and transpositions over finite alphabets[END_REF][START_REF] Kolman | Reversal distance for strings with duplicates: Linear time approximation using hitting set[END_REF] (where multiple occurrences of each element are allowed in the sequences), possibly with weighted or prefix transpositions [START_REF] Qi | Combinatorial Algorithms of Genome Rearrangements in Bioinformatics[END_REF][START_REF] Bongartz | Algorithmic Aspects of Some Combinatorial Problems in Bioinformatics[END_REF][START_REF] Amir | Pattern matching with address errors: Rearrangement distances[END_REF][START_REF] Amir | Efficient computations of 1 and ∞ rearrangement distances[END_REF][START_REF] Chitturi | Bounding prefix transposition distance for strings and permutations[END_REF]. Note also that sorting a permutation by block-interchanges (i.e. exchanges of non-necessarily consecutive sequences) is a polynomial problem [START_REF] Christie | Sorting permutations by block-interchanges[END_REF].

In this paper, we address the long-standing issue of determining the complexity class of the SORTING BY TRANSPOSITIONS problem, by giving a polynomial-time reduction from SAT, thus proving the NP-hardness of this problem. Our reduction is based on the study of transpositions that remove three breakpoints. A corollary of our result is the NP-hardness of the following problem, introduced in [START_REF] Christie | Genome Rearrangement Problems[END_REF]: given a permutation π, is it possible to sort π using d b (π)/3 permutations, where d b (π) is the number of breakpoints of π?

Preliminaries

In this paper, n denotes a positive integer. Let a ; b = {x ∈ N | a ≤ x ≤ b}, and Id n be the identity permutation over 0 ; n . We consider only permutations of 0 ; n such that 0 and n are fixed-points. Given a word u 1 u 2 . . . u l , a subword is a subsequence u p1 u p2 . . . u p l , where 1 ≤ p 1 < p 2 < . . . < p l ≤ l. A factor is a subsequence of contiguous elements, i.e. a subword with p k+1 = p k + 1 for every k ∈ 1 ; l -1 .

Definition 1 (Transposition). Given three integers 0 < i < j < k ≤ n, the transposition τ i,j,k over 0 ; n is the following permutation:

τ i,j,k = 0 • • • i -1 i • • • k + i -j -1 k + i -j • • • k -1 k • • • n 0 • • • i -1 j • • • k -1 i • • • j -1 k • • • n
Let π be a permutation of 0 ; n . The transposition distance d t (π) from π to Id n is the minimum value k for which there exist

k transpositions τ 1 , τ 2 , . . . , τ k such that π • τ k • . . . • τ 2 • τ 1 = Id n .
The transposition τ i,j,k is the operation that, when it is composed with a permutation, exchanges factors with indices i, . . . , j -1 and j, . . . , k -1, see Figure 1a. The inverse function of τ i,j,k is also a transposition: τ -1 i,j,k = τ i,k+i-j,k . See Figure 1b for an example of the computation of the transposition distance.

We consider the following problem:

SORTING BY TRANSPOSITIONS PROBLEM [START_REF] Bafna | Sorting permutations by transpositions[END_REF] INPUT: A permutation π, an integer k. QUESTION: Is d t (π) ≤ k?

Computing the transposition distance has often been linked to studying the breakpoints of a permutation. A breakpoint of π is a pair (x -1, x), x ∈ 1 ; n , such that π(x) = π(x -1) + 1. A transposition can decrease the number of breakpoints of a permutation, d b (π), by at most 3. In this paper we in fact focus on the "simpler" problem of determining whether d t (π) = d b (π)/3 for a given permutation π.

3-Deletion and Transposition Operations

In this section, we introduce 3DT-instances, which are the cornerstone of our reduction from SAT to the SORTING BY TRANSPOSITIONS problem, since they are used as an intermediate between instances of the two problems.

Σ = {a 1 , b 1 , c 1 , a 2 , b 2 , c 2 }, hence ψ is a bijection (ψ(a 1 ) = 1, ψ(c 2 ) = 2, ψ(b 1 ) = 3, etc). I has an alphabet of size 3, Σ = {a 2 , b 2 , c 2 }, with ψ (b 2 ) = 2, ψ (c 2 ) = 4, ψ (a 2 ) = 6.
Definition 2 (3DT-instance). A 3DT-instance I = Σ, T, ψ of span n is composed of the following elements:

-Σ: an alphabet of at most n elements;

-T = {(a i , b i , c i ) | 1 ≤ i ≤ |T |}:
a set of (ordered) triples of elements of Σ, partitioning Σ (i.e. all elements are pairwise distinct, and

|T | i=1 {a i , b i , c i } = Σ); -ψ : Σ → 1 ; n , an injection.
The domain of I is the image of ψ, that is the set L = {ψ(σ) | σ ∈ Σ}. The word representation of I is the n-letter word u 1 u 2 . . . u n over Σ ∪ { } (where / ∈ Σ), such that for all i ∈ L, ψ(u i ) = i, and for i ∈ 1 ; n -L, u i = . For σ 1 , σ 2 ∈ Σ, we write

σ 1 ≺ σ 2 if ψ(σ 1 ) < ψ(σ 2 ), and σ 1 σ 2 if σ 1 ≺ σ 2 and x ∈ Σ, σ 1 ≺ x ≺ σ 2 .
Two examples of 3DT-instances are given in Figure 2. Note that such instances can be defined by their word representation and by their set of triples T . The empty 3DTinstance, in which Σ = ∅, can be written with a sequence of n dots, or with the empty word ε.

Using the triples in T , we can define a successor function over the domain L: Function succ I is a bijection, with no fixed-points, and such that succ I • succ I • succ I is the identity over L.

In the example of Figure 2,succ T is well-ordered if we have i < j < k. In such a case, we write τ [a, b, c, ψ] the transposition τ i,j,k .

An equivalent definition is that (a, b, c) ∈ T is well-ordered iff one of abc, bca, cab is a subword of the word representation of I. In the example of Figure 2,(a

1 , b 1 , c 1 ) is well-ordered in I: indeed, we have i = ψ(a 1 ), j = ψ(b 1 ) and k = ψ(c 1 ), so i < j < k. The triple (a 2 , b 2 , c 2 ) is also well-ordered in I (i = ψ (b 2 ) < j = ψ (c 2 ) < k = ψ (a 2 )), but not in I: i = ψ(c 2 ) < k = ψ(b 2 ) < j = ψ(a 2 ). In this example, we have τ [a 1 , b 1 , c 1 , ψ] = τ 1,3,5 and τ [a 2 , b 2 , c 2 , ψ ] = τ 2,4,6 .
Definition 5 (3DT-step). Let I = Σ, T, ψ be a 3DT-instance with (a, b, c) ∈ T a well-ordered triple. The 3DT-step of parameter (a, b, c) is the operation written

(a, b, c) -----→, transforming I into the 3DT-instance I = Σ , T , ψ such that, with τ = τ [a, b, c, ψ]: Σ = Σ -{a, b, c}; T = T -{(a, b, c)}; ψ : Σ → 1 ; n σ → τ -1 (ψ(σ))
.

If the word representation of I is W a X b Y c Z, then, after the 3DT-step I (a, b, c) -----→I , the word representation of I is W Y X Z. Note that a triple that is not well-ordered in I can become well-ordered in I , or vice-versa. In the example of Figure 2, I can be obtained from I via a 3DT-step:

I (a1, b1, c1) --------→I . Moreover, I (a2, b2, c2) --------→ε. Definition 6 (3DT-collapsibility). A 3DT-instance I = Σ, T, ψ is 3DT-collapsible if there exists a sequence of 3DT-instances I k , I k-1 , . . . , I 0 such that I k = I, I 0 = ε, and ∀i ∈ 1 ; k , ∃(a, b, c) ∈ T, I i (a, b, c) -----→Ii-1.
In Figure 2, I and I are 3DT-collapsible, since we have

I (a1, b1, c1) --------→I (a2, b2, c2) --------→ε.

3DT-collapsibility is NP-Hard to Decide

In this section, we define, for any boolean formula φ, a corresponding 3DT-instance I φ . We also prove that I φ is 3DT-collapsible iff φ is satisfiable (see Theorem 1).

Block Structure

The construction of the 3DT-instance I φ uses a decomposition into blocks, defined below. Some triples will be included in a block, in order to define its behavior, while others will be shared between two blocks, in order to pass information. The former are unconstrained, so that we can design blocks with the behavior we need (for example, blocks mimicking usual boolean functions), while the latter need to follow several rules, so that the blocks can easily be arranged together.

Definition 7 (l-block-decomposition). An l-block-decomposition B of a 3DT-instance I of span n is an l-tuple (s 1 , . . . , s l ) such that s 1 = 0, for all h ∈ 1 ; l -1 , s h < s h+1 and s l < n. We write t h = s h+1 for h ∈ 1 ; l -1 , and t l = n. Let I = Σ, T, ψ and u 1 u 2 . . . u n be the word representation of I. For h ∈ 1 ; l , the subword u s h +1 u s h +2 . . . u t h where every occurrence of is deleted is called the block B h . For σ ∈ Σ, we write block

I,B (σ) = h if ψ(σ) ∈ s h + 1 ; t h (equivalently, if σ appears in the word B h ). A triple (a, b, c) ∈ T is said to be internal if block I,B (a) = block I,B (b) = block I,B (c), external otherwise.
Given a 3DT-step I (a, b, c) -----→I , the arrow notation can be extended to an l-blockdecomposition B of I, provided at least one of the following equalities is satisfied: In this case, with τ = τ [a, b, c, ψ], the l-tuple B = (τ -1 (s 1 ), . . . , τ -1 (s l )) is an lblock-decomposition of I , and we write (I, B) (a, b, c) -----→(I , B ).

Definition 8 (Variable). A variable A of a 3DT-instance I = Σ, T, ψ is a pair of triples A = [(a, b, c), (x, y, z)] of T . It is valid in an l-block-decomposition B if (i) ∃h 0 ∈ 1 ; l such that block I,B (b) = block I,B (x) = block I,B (y) = h 0 (ii) ∃h 1 ∈ 1 ; l , h 1 = h 0 , such that block I,B (a) = block I,B (c) = block I,B (z) = h 1 (iii) if x ≺ y, then we have x b y (iv) a ≺ z ≺ c
For such a valid variable A, the block B h0 containing {b, x, y} is called the source of A, and the block B h1 containing {a, c, z} is called the target of A. For h ∈ 1 ; l , the variables of which B h is the source (resp. the target) are called the output (resp. the input) of B h . The 3DT-step I (x, y, z)

------→I is called the activation of A (it requires that (x, y, z) is well-ordered).

Note that, for any valid variable A = [(a, b, c), (x, y, z)] in (I, B), we have, according to condition (i), block I,B (x) = block I,B (y), thus its activation can be written (I, B) The graph obtained from a block B by following exhaustively the possible arcs as defined above (always assuming this block is in a valid context) is called the behavior graph of B. Figure 3 illustrates the activation of a valid variable A.

(x, y, z) ------→(I , B ).

Basic Blocks

We now define four basic blocks: copy, and, or, and var. They are studied independently in this section, before being assembled in Section 3.3. Each of these blocks is defined by -----→ , impacting only the target block of A. Dot symbols ( ) are omitted. We denote by R, S, T, U, V, W some factors of the source and target blocks of A: the consequence of activating A is to allow U and V to be swapped in the target of A.

• • • • • • • • • source º R x b y S º º R S º º R S º • • • • • • • • • target º T a U z V c W º º T a U b V c W º º T V U W º • • • • • • • • • A A (a, b, c) (x, y, z) (a, b, c)
a word and a set of triples. We distinguish internal triples, for which all three elements appear in a single block, from external triples, which are part of an input/output variable, and for which only one or two elements appear in the block. Note that each external triple is part of an input (resp. output) variable, which itself must be an output (resp. input) of block, the other block containing the remaining elements of the triple.

We then compute the behavior graph of each of these blocks (it is given here for the block copy, see Figure 4, and in the full version for the other blocks): in each case, we assume that the block is in a valid context, and follow exhaustively the 3DT-steps that can be applied to it. It must be kept in mind that for any variable, it is the state of the source block which determines whether it can be activated, whereas the activation itself affects mostly the target block. It can be verified that each output (resp. input) variable of these blocks satisfy the constraints (i) and (iii) (resp. (ii) and (iv)) of Definition 8.

The block copy This block aims at duplicating a variable: any of the two output variables can only be activated after the input variable has been activated. See Figure 4 The block and This block aims at simulating a conjunction: the output variable can only be activated after both input variables have been activated. Input variables: (d, e, f )

A 1 = [(a 1 , b 1 , c 1 ), (x 1 , y 1 , z 1 )] and A 2 = [(a 2 , b 2 , c 2 ), (x 2 , y 2 , z 2 )]. Output variable: A = [(
A 2 A 1 A 1 A 1 Fig. 4: Behavior graph of the block [A 1 , A 2 ] = copy(A).
The block or This block aims at simulating a disjunction: the output variable can be activated as soon as any of the two input variables is activated. Input variables:

A 1 = [(a 1 , b 1 , c 1 ), (x 1 , y 1 , z 1 )] and A 2 = [(a 2 , b 2 , c 2 ), (x 2 , y 2 , z 2 )]. Output variable: A = [(a, b, c), (x, y, z)].
Internal triples: (a , b , c ) and (d, e, f ). Definition:

A = or(A 1 , A 2 ) = a 1 b z 1 a 2 d y a x b f z 2 c 1 e c c 2
Property 4. In a block A = or(A 1 , A 2 ) in a valid context, the possible orders in which A, A 1 and A 2 can be activated are

(A 1 , A, A 2 ), (A 2 , A, A 1 ), (A 1 , A 2 , A) and (A 2 , A 1 , A).
The block var This block aims at simulating a boolean variable: in a first stage, only one of the two output variables can be activated. The other needs the activation of the input variable to be activated. Input variable: A = [(a, b, c), (x, y, z)].

Output variables:

A 1 = [(a 1 , b 1 , c 1 ), (x 1 , y 1 , z 1 )], A 2 = [(a 2 , b 2 , c 2 ), (x 2 , y 2 , z 2 )].
Internal triples: (d 1 , e 1 , f 1 ), (d 2 , e 2 , f 2 ) and (a , b , c ). Definition:

[A 1 , A 2 ] = var(A) = d 1 y 1 a d 2 y 2 e 1 a e 2 x 1 b 1 f 1 c z b c x 2 b 2 f 2 Property 5. In a block [A 1 , A 2 ] = var(A)
in a valid context, the possible orders in which A, A 1 and A 2 can be activated are

(A 1 , A, A 2 ), (A 2 , A, A 1 ), (A, A 1 , A 2 ) and (A, A 2 , A 1 ).
With such a block, if A is not activated first, one needs to make a choice between activating A 1 or A 2 . Once A is activated, however, all remaining output variables are activable.

Assembling the blocks copy, and, or, var.

Definition 10 (Assembling of basic blocks). An assembling of basic blocks (I, B) is composed of a 3DT-instance I and an l-block-decomposition B obtained by the following process. Create a set of variables A. Define I = Σ, T, ψ by its word representation, as a concatenation of l factors B 1 B 2 . . . B l and a set of triples T , where each

B h is one of the blocks [A 1 , A 2 ] = copy(A), A = and(A 1 , A 2 ), A = or(A 1 , A 2 ) or [A 1 , A 2 ] = var(A), with A 1 , A 2 , A ∈ A (such
that each X ∈ A appears in the input of exactly one block, and in the output of exactly one other block); and where T is the union of the set of internal triples needed in each block, and the set of external triples defined by the variables of A.

Lemma 1. Let I be a 3DT-instance with an l-block-decomposition B , such that (I , B ) is obtained from an assembling of basic blocks (I, B) after any number of 3DT-steps. Then (I , B ) is a valid context. Moreover, if the set of variables of (I , B ) is empty, then I is 3DT-collapsible.

The above lemma justifies the assumption that each block is in a valid context to derive Properties 2 to 5. An assembling of basic blocks is 3DT-collapsible iff there exists a total order, satisfying these properties, in which all its variables can be activated.

Construction of I φ

Let φ be a boolean formula, over the boolean variables x 1 , . . . , x m , given in conjunctive normal form:

φ = C 1 ∧ C 2 ∧ . . . ∧ C γ . Each clause C c (c ∈ 1 ; γ ) is
the disjunction of a number of literals, x i or ¬x i , i ∈ 1 ; m . We write q i (resp. qi ) for the number of occurrences of the literal x i (resp. ¬x i ) in φ, i ∈ 1 ; m . We also write k(C c ) for the number of literals appearing in the clause C c , c ∈ 1 ; γ . We can assume that γ ≥ 2, that for each c ∈ 1 ; γ , we have k(C c ) ≥ 2, and that for each i ∈ 1 ; m , q i ≥ 2 and qi ≥ 2 (otherwise, we can always add clauses of the form (x i ∨ ¬x i ) to φ, or duplicate the literals appearing in the clauses C c such that k(C c ) = 1). In order to distinguish variables of an l-block-decomposition from x 1 , . . . , x m , we always use the term boolean variable for the latter.

The 3DT-instance I φ is defined as an assembling of basic blocks: we first define a set of variables, then we list the blocks of which the word representation of I φ is the concatenation. It is necessary that each variable is part of the input (resp. the output) of exactly one block. Note that the relative order of the blocks is of no importance. We simply try, for readability reasons, to ensure that the source of a variable appears before its target, whenever possible. We say that a variable represents a term, i.e. a literal, clause or formula, if it can be activated only if this term is true (for some fixed assignment of the boolean variables), or if φ is satisfied by this assignment. We also say that a block defines a variable if it is its source block.

The construction of I φ is done as follows (see Figure 5 for an example): Create a set of variables:

-For each i ∈ 1 ; m , create q i + 1 variables representing x i : X i and X j i , j ∈ 1 ; q i , and qi + 1 variables representing ¬x i : Xi and Xj i , j ∈ 1 ; qi . -For each c ∈ 1 ; γ , create a variable Γ c representing the clause C c .

-Create m + 1 variables, A φ and A i φ , i ∈ 1 ; m , representing the formula φ.

Ú Ö ÓÔÝ X 1 X 1 1 X 2 1 ÓÔÝ X1 X1 1 X2 1 Ú Ö ÓÔÝ X 2 X 1 2 X 2 2 ÓÔÝ X2 X1 2 X2 2 Ú Ö ÓÔÝ X 3 X 1 3 X 2 3 ÓÔÝ X3 X1 3 X2 3 Ú Ö ÓÔÝ X 4 X 1 4 X 2 4 ÓÔÝ X4 X1 4 X2 4 ÓÖ ÓÖ V 2 1 ÓÖ ÓÖ ÓÖ V 2 3 ÓÖ ÓÖ V 2 4 ÓÖ ÓÖ ÓÖ V 2 6 Ò Γ 1 Γ 2 Ò W 2 Γ 3 Ò W 3 Γ 4 Ò W 4 Γ 5 Ò W 5 Γ 6 ÓÔÝ A φ ÓÔÝ Y 2 ÓÔÝ Y 3 A 1 φ A 2 φ A 3 φ A 4 φ Fig. 5: Schematic diagram of the blocks defining I φ for φ = (x 1 ∨ x 2 ∨ ¬x 3 ) ∧ (x 1 ∨ ¬x 2 ) ∧ (¬x 1 ∨ x 2 ∨ ¬x 4 ) ∧ (¬x 1 ∨ x 3 ∨ x 4 ) ∧ (x 3 ∨ ¬x 4 ) ∧ (¬x 2 ∨ ¬x 3 ∨ x 4 ).
For each variable, we draw an arc between its source and target block. Note that φ is satisfiable (e.g. with the assignment x 1 = x 3 = true and x 2 = x 4 = f alse). A set of variables that can be activated before A φ is in bold, they correspond to the terms being true in φ for the assignment x 1 = x 3 = true and x 2 = x 4 = f alse.

-We also use a number of intermediate variables, with names U j i , Ū j i , V p c , W c and Y i . Start with an empty 3DT-instance ε, and add blocks successively:

-For each i ∈ 1 ; m , add the following q i + qi -1 blocks defining the variables X i , X j i (j ∈ 1 ; q i ), and Xi , Xj i (j ∈ 1 ; qi ):

[X i , Xi ] = var(A i φ ); [X 1 i , U 2 i ]=copy(X i ); [X 2 i , U 3 i ]=copy(U 2 i ); . . . [X qi-2 i , U qi-1 i ]=copy(U qi-2 i ); [X qi-1 i , X qi i ]=copy(U qi-1 i ); [ X1 i , Ū 2 i ]=copy( Xi ); [ X2 i , Ū 3 i ]=copy( Ū 2 i ); . . . [ X qi-2 i , Ū qi-1 i ]=copy( Ū qi-2 i ); [ X qi-1 i , X qi i ]=copy( Ū qi-1 i
).

-

For each c ∈ 1 ; γ , let C c = λ 1 ∨ λ 2 ∨ . . . ∨ λ k , with k = k(C c ).
Let each λ p , p ∈ 1 ; k , be the j-th occurrence of a literal x i or ¬x i , for some i ∈ 1 ; m and j ∈ 1 ; q i (resp. j ∈ 1 ; qi ). We respectively write L p = X j i or L p = Xj i . Add the following k -1 blocks defining Γ c :

V 2 c = or(L 1 , L 2 ); V 3 c = or(V 2 c , L 3 ); . . . V k-1 c = or(V k-2 c , L k-1 ); Γ c = or(V k-1 c , L k ). -Since φ = C 1 ∧ C 2 ∧ . . . ∧ C l , add the following l -1 blocks: W 2 =and(Γ 1 , Γ 2 ); W 3 =and(W 2 , Γ 3 ); . . . W l-1 =and(W l-2 , Γ l-1 ); A φ =and(W l-1 , Γ l ).
-The m copies A 1 φ , . . . , A m φ of A φ are defined with the following m -1 blocks:

[A 1 φ , Y 2 ] = copy(A φ ); [A 2 φ , Y 3 ] = copy(Y 2 ); . . . [A m-2 φ , Y m-1 ] = copy(Y m-2 ); [A m-1 φ , A m φ ] = copy(Y m-1
). Theorem 1. Let φ be a boolean formula, and I φ the 3DT-instance defined above. The construction of I φ is polynomial in the size of φ, and φ is satisfiable iff I φ is 3DTcollapsible.

Sorting by Transpositions is NP-Hard

In order to transfer our result from 3DT-collapsibility to SORTING BY TRANSPOSI-TIONS, we need a notion of equivalence between 3DT-instances and permutations, which is introduced here. Definition 11. Let I = Σ, T, ψ be a 3DT-instance of span n with domain L, and π be a permutation of 0 ; n . We say that I and π are equivalent, and we write I ∼ π, if:

π(0) = 0, ∀v ∈ 1 ; n -L, π(v) = π(v -1) + 1, ∀v ∈ L, π(v) = π(succ -1 I (v) -1) + 1.
There is no guarantee that any 3DT-instance I has an equivalent permutation π (for example, no permutation is equivalent to I = a 1 a 2 b 1 b 2 c 1 c 2 ). However, coming back to our example in Figure 2, we have I ∼ π = (0 5 2 1 4 3 6), and I ∼ π = (0 1 4 5 2 3 6). More generally, with the following theorem, we show that such a permutation can always be found in the special case of assemblings of basic blocks, which is the case we are interested in. Theorem 2. Let I be a 3DT-instance of span n with B an l-block-decomposition such that (I, B) is an assembling of basic blocks. Then there exists a permutation π I , computable in polynomial time in n, such that I ∼ π I .

With an equivalence I ∼ π, each breakpoint of π can be associated to an element of Σ via ψ, and the triples of breakpoints that may be resolved by a single transposition correspond to the well-ordered triples of T . Moreover, applying such a transposition on π corresponds to operating a 3DT-step on I. These properties, which lead to the following theorem, can be seen on the previous example as summarized below: With the previous theorem, we now have all the necessary ingredients to prove the main result of this paper. Proof. The reduction from SAT is as follows: given any instance φ of SAT, create a 3DT-instance I φ , being an assembling of basic blocks, which is 3DT-collapsible iff φ is satisfiable (Theorem 1). Then create a permutation π I φ equivalent to I φ (Theorem 2). The above two steps can be achieved in polynomial time.

Finally, set k = d b (π I φ )/3 = n/3: φ is satisfiable iff d t (π I φ ) = k (Theorem 3).

Corollary 1. The following decision problem from [START_REF] Christie | Genome Rearrangement Problems[END_REF] is also NP-complete: given a permutation π of 0 ; n , is the equality d t (π) = d b (π)/3 satisfied?

Conclusion

In this paper we have proved that the SORTING BY TRANSPOSITIONS problem is NPhard, thus answering a long-standing question. However, a number of questions remain open. For instance, does this problem admit a polynomial-time approximation scheme?

We note that the reduction we have provided does not answer this question, since it is not a linear reduction. Indeed, by our reduction, if a formula φ is not satisfiable, it can be seen that we have d t (π I φ ) = d b (π I φ )/3 + 1. Also, do there exist some relevant parameters for which the problem is fixed parameter tractable? A parameter that comes to mind when dealing with the transposition distance is the size of the factors exchanged (e.g., the value max{ji, k -j} for a transposition τ i,j,k ). Does the problem become tractable if we bound this parameter? In fact, the answer to this question is no if we bound only the size of the smallest factor, min{ji, k -j}: in our reduction, this parameter is upper bounded by 6 for every transposition needed to sort π I φ , independently of the formula φ.

π=Fig. 1 :Fig. 2 :

 12 Fig. 1: (a) Representation of a transposition τ i,j,k for 0 < i < j < k ≤ n on a general permutation. (b) The transposition distance from π = (0 2 4 3 1 5) to Id 5 is 2: it is at most 2 since π • τ 1,3,5 • τ 1,2,4 = Id 5 , and it cannot be less than 2 since d t (π) ≥ d b (π)/3 = 5/3 > 1. I = a1 c2 b1 b2 c1 a2 with T = {(a1, b1, c1), (a2, b2, c2)} I = b2 c2 a2 with T = {(a2, b2, c2)} Fig. 2: Two examples of 3DT-instances of span 6. We write I = Σ, T, ψ and I = Σ , T , ψ . I has an alphabet of size 6, Σ = {a 1 , b 1 , c 1 , a 2 , b 2 , c 2 }, hence ψ is a bijection (ψ(a 1 ) = 1, ψ(c 2 ) = 2, ψ(b 1 ) = 3, etc). I has an alphabet of size 3, Σ = {a 2 , b 2 , c 2 }, with ψ (b 2 ) = 2, ψ (c 2 ) = 4, ψ (a 2 ) = 6.

Definition 3 .

 3 Let I = Σ, T, ψ be a 3DT-instance with domain L. We write succ I : L → L the function such that, for all (a, b, c) ∈ T , ψ(a) → ψ(b), ψ(b) → ψ(c), and ψ(c) → ψ(a).

Definition 4 .

 4 Let I = Σ, T, ψ be a 3DT-instance, and (a, b, c) be a triple of T . Write i = min{ψ(a), ψ(b), ψ(c)}, j = succ I (i), and k = succ I (j). The triple (a, b, c) ∈

  block I,B (a) = block I,B (b), block I,B (b) = block I,B (c) or block I,B (c) = block I,B (a).

Property 1 .

 1 Let (I, B) be a 3DT-instance with an l-block-decomposition, and A be a variable of I that is valid in B, A = [(a, b, c), (x, y, z)]. Then (x, y, z) is well-ordered iff x ≺ y; and (a, b, c) is not well-ordered. Definition 9 (Valid context). A 3DT-instance with an l-block-decomposition (I, B) is a valid context if the set of external triples of I can be partitioned into valid variables. Let B be a block in a valid context (I, B) (in which B = B h , for some h ∈ 1 ; l ), and (I, B) (d, e, f ) ------→(I , B ) be a 3DT-step such that, writing B = B h , we have B = B. Then, depending on the triple (d, e, f ), we are in one of the following three cases: -(d, e, f ) is an internal triple of B. We write: B B ′ (d, e, f ) -(d, e, f ) = y, z) for some output A = [(a, b, c), (x, y, z)] of B. We write: B B ′ A -(d, e, f ) = (x, y, z) for some input A = [(a, b, c), (x, y, z)] of B. We write:

Fig. 3 :

 3 Fig. 3: Activation of a valid variable A = [(a, b, c), (x, y, z)]. It can be followed by the 3DTstep (a, b, c)-----→ , impacting only the target block of A. Dot symbols ( ) are omitted. We denote by R, S, T, U, V, W some factors of the source and target blocks of A: the consequence of activating A is to allow U and V to be swapped in the target of A.

a y 1 e z d y 2 x 1 b 1 c x 2 b 2 f 2 .

 22 for the behavior graph of this block. Input variable: A = [(a, b, c), (x, y, z)]. Output variables: A 1 = [(a 1 , b 1 , c 1 ), (x 1 , y 1 , z 1 )] and A 2 = [(a 2 , b 2 , c 2 ), (x 2 , y 2 , z 2 )]. Internal triple: (d, e, f ). Definition: [A 1 , A 2 ] = copy(A) = Property In a block [A 1 , A 2 ] = copy(A) in a valid context, the possible orders in which A, A 1 and A 2 can be activated are (A, A 1 , A 2 ) and (A, A 2 , A 1 ).

a 1 e z 1 a 2 c 1 z 2 d y c 2 x b f Property 3 .

 3 a, b, c), (x, y, z)]. Internal triple: (d, e, f ). Definition: A = and(A 1 , A 2 ) = In a block A = and(A 1 , A 2 ) in a valid context, the possible orders in which A, A 1 and A 2 can be activated are (A 1 , A 2 , A) and (A 2 , A 1 , A).

º a y 1 e z d y 2 x 1 b 1 c x 2 b 2 f º º a y 1 e b d y 2 x 1 b 1 c x 2 b 2 f º º d y 2 x 1 b 1 y 1 e x 2 b 2 f º º x 2 b 2 y 2 x 1 b 1 y 1 º º d y 2 e x 2 b 2 f º º x 1 b 1 y 1 º º x 2 b 2 y 2

 2

Theorem 3 .

 3 Let I = Σ, T, ψ be a 3DT-instance of span n with domain L, and π be a permutation of 0 ; n , such thatI ∼ π. Then I is 3DT-collapsible iff d t (π) = |T | = d b (π)/3.

Theorem 4 .

 4 The SORTING BY TRANSPOSITIONS problem is NP-hard.


Sébastien Angibaud
email: sebastien.angibaud@univ-nantes.fr

Philippe Bordron
email: philippe.bordron@univ-nantes.fr

Damien Eveillard
email: damien.eveillard@univ-nantes.fr

Guillaume Fertin
email: guillaume.fertin@univ-nantes.fr

Irena Rusu
email: irena.rusu@univ-nantes.fr

Integration of omics data to investigate common intervals

Keywords: comparative genomics, integrative approach, operons prediction I

During the last decade, we witnessed the huge impact of the comparative genomics for understanding genomes (from the genome organization to their annotation). However, those genomic approaches quickly reach their limits when one looks at investigating the functional properties of genes in the wide genome context. Such limitation may be overcome thanks to recent high-throughput experimental progresses like those obtained via metabolic and co-expression studies, that produce so-called omics data. Therefore, integrating those data and state-of-the-art computational genomic comparison is a natural evolution. This paper achieves such an integration and proposes a heuristic algorithm IISCS that incorporates omics knowledge into the IILCS heuristic, already known as accurate to compare genomes. When applied on bacteria, one emphasize large functional units composed of several operons.

INTRODUCTION

During the last decade, comparative genomics provided several computational tools to understand genomes. In particular they give us the opportunity to investigate genome organization that leads us to annotate genes based of their relative location into conserved genomic areas during the evolution of two species. Finding those sets of conserved genes implies the use of a dedicated measure. Common intervals, as computed by the IILCS heuristic, is appropriated to compare bacterial circular genomes [START_REF] Angibaud | Comparing bacterial genomes by searching their common intervals[END_REF]. Indeed, a common interval, as illustrated in Figure 1(a), is defined as a set of genes that are located together inside both genomes, not necessarily in the same order and without taking gene orientations into account. Common intervals correspond to conserved areas (i.e. areas with the same genes content) inside which some rearrangements have occurred during the evolution of both species. However, investigating the functional meanings of a genomic comparison remains a difficult task (mainly due to the large number of conserved organizations with no function to rely on). In addition, when applied on the operon predictions at wide-genome information, one must notice that the use of intergenic distance only is not sufficient [START_REF] Chuang | Binary particle swarm optimization for operon prediction[END_REF], which leads to investigate techniques that combine omics data to improve the prediction accuracy.

Following a similar philosophy the use of omics data combination, we propose herein to extent the common interval computation with an estimation of their biological interests by using metabolic or microarray data. Our goal is thus dual. First, we aim at filtering the most relevant common intervals in a context other than genomic only. Second, we consider merging heterogeneous knowledge with a genomic information, which represents one of the key question in integrative genomics. Every step of the method will be illustrated by a concrete biological case, based on the comparison between two bacterial species: Escherichia coli and Vibrio cholerae.

As a preliminary step, the paper will start (Sec II) with a sketch of the common interval computation, which considers, in our process, only genes that are in both genomes. Thus, a gene that has been lost in one of the two genomes during the evolutionary process, or a gene that has been duplicated after the speciation (in-paralogous gene) is not taken into account in the computation process. This technique implies that common intervals can contain a gene that has appeared after the speciation. To illustrate such a common interval, Figure 1(b) gives an example where both genomes do not have the same gene content. As a natural refinement, we will then propose an heuristic for integrating the obtained common intervals with microbial omics data at disposal. As a major contribution, such an integration rises the accuracy of the common intervals which is emphasized by comparing and discussing (Sec. III) our results with known bacterial operons.

II. MATERIAL AND METHOD

A. Genomes investigated

Our biological benchmark is composed of two genomes of proteobacteria : Escherichia coli K12 MG1655 (one chromosome, NCBI id : NC_000913) and Vibrio cholerae 01 biovar eltor str. N16961 (two chromosomes, NCBI id: NC_002505 & NC_002506). In order to benefit from large knowledge on the genome of Escherichia coli, we compared E. coli with each of the two other chromosomes.

B. Computation of common intervals

The comparison between two given genomes, using the common interval measure is implemented in a software called Match&Watch [START_REF] Angibaud | Comparing bacterial genomes by searching their common intervals[END_REF]. This program is available on request. It provides a GUI that controls the processes described below, and an automatic graphical representation of common intervals.

Homologies detection: The first step of the method consists in computing gene homologies. We use for that the Inparanoid software [3] (step 1), which clusters ortholog and inparalog genes based on a Blastp. Then, we tag the homologous genes with a similar label according to the clusters (step 2). This step does not take into account separation of orthologs and inparalogs given by Inparanoid.

Matching choice: When genomes contain duplicates, we cannot directly compute the number of common intervals, because this measure is defined on permutations (i.e. with pairwise distinct genes). A natural solution consists in i) finding a one-to-one correspondence (i.e. a matching) between genes of the two genomes, ii) using this correspondence to relabel genes of both genomes, and iii) leaving aside the unmatched genes in order to obtain two fictitious genomes such that the first one is a permutation of the other. There exists two main models to compute such a matching : the exemplar model [START_REF] Sankoff | Genome rearrangement with gene families[END_REF] and the maximum matching model [START_REF] Tang | Phylogenetic reconstruction from generearrangement data with unequal gene content[END_REF]. The first one consists in keeping one occurrence for each gene label and the second one in keeping the maximum of occurrences (see Figure 2). Having chosen a model, in our study the maximum matching model, we select among all possible matchings, one that maximizes the number of common intervals, proposed in [START_REF] Angibaud | Comparing bacterial genomes by searching their common intervals[END_REF] (step 3).

Common intervals computation: Having chosen a matching of genes that disambiguates duplicates, we rename all genes according to the matching (step 4). We thus obtain two permutations, for which we can easily compute common intervals (step 5) that is the set of all common intervals Maximal common intervals selection: Let ϒ be the set of all common intervals. We remove from ϒ each interval that contains all the genes of one of the two genomes. Indeed the whole genome is a trivial common interval which is not informative considering comparative genomics. As we work on circular genomes, note that each common interval I in ϒ has a complementary interval I' in ϒ. We consider that the smaller between two complementary intervals is the more informative in a biological viewpoint, which means that we remove the larger from ϒ. We also remove from ϒ each common interval that contains only one gene and each common interval that is include in another interval of ϒ. Thus, the resulting set ϒ is the set of maximal common intervals.

C. Integrating omics data: using a matrix of interest.

The matching that maximizes the number of common intervals is performed by the algorithm named IILCS (Improved Iteration Longest Subsequence Substring) described in Figure 3, which is a heuristic but shows results close (98.9% in a 40 pairwise γ-protobacteria genomes comparison) to the maximum number of common intervals [START_REF] Angibaud | A pseudo-boolean general framework for computing rearrangement distances between genomes with duplicates[END_REF]. Because we propose to refine the common intervals based on omics information, one must change the IILCS heuristic. We propose here the IISCS heuristic (Improved Iteration Scoring Common Substring) described in Figure 4, as a solution. The difference between IILCS and IISCS lies in the addition of a matrix A as input and the modification of step 1 of the IILCS algorithm, which consists of taking the (a) (b) Figure 1. Illustration of a common interval between genomes G1 and G2. The set of genes {2, 3, 4} is a common interval since genes 2, 3 and 4 are consecutive in both genomes. (b) Illustration of a common interval between two genomes which do not have the same gene contents. The set of genes {2, 3, 5} is also a common interval since genes 2, 3 and 5 are consecutive in both genomes, when we consider only genes that are present in both genomes (genes 1, 2, 3, 5, 7, 8 and 9). Dashed genes (4, 6, 10, 11, 12) are left aside before common intervals computation since they are not present on both genomes. After intervals computation, these genes are then re-introduced into common intervals.

) Taking into account metabolic information

To take into account metabolic information in the computation of common intervals, we integrate here both genomic and metabolic information in order to generate a new matrix of interest A'. The relationship between a genome and its corresponding metabolic network is established by the "gene produces enzyme(s)" rule. Combination of this rule and knowledge at disposal conduces to define an integrated genomic metabolic network, denoted ς int . The network ς int is a directed graph, whose vertices are all the pairs (gene g, reaction r) such that the gene g produces an enzyme (identified herein by its EC number) that catalyzes the reaction r. An arc goes from vertex (g 1 ,r 1 ) to vertex (g 2 ,r 2 ) whenever a product of r 1 is a substrate of r 2 . Its weight w is defined as the genomic distance between g 1 and g 2 , that is the number of intermediate genes between g 1 and g 2 along the genome (plus 1 when g 1 ≠ g 2 ). If g 1 and g 2 are not on the same chromosome, their distance is set to infinity. If the chromosome is circular, the smallest genomic distance between the right-hand traversal and the left-hand traversal is chosen. For two given genes g 1 and g 2 and respectively any reactions x and y which are associated to g 1 and g 2 by the rule "gene produces enzyme(s)", the MAXimum Genomic Density Integrated Pathway from g 1 to g 2 (MAXGD-IP(g 1 ,g 2 ) for short) in is the path from a vertex (g 1 ,x) to a vertex (g 2 ,y) in ς int that maximizes its genomic density. The genomic density of a path in ς int is the ratio between the number of distinct genes that participate in the path and the length of the smallest interval of genes in the genome that contains all the genes of the path. The computation of MAXGD-IP(g 1 ,g 2 ) is approximated by computing in the 10 shortest loopless paths from the vertices (g 1 ,x) to the vertices (g 2 ,y), and taking the densest among them. A MAXGD-IP(g 1 ,g 2 ) where genes g 1 and g 2 are any genes in G 1 is called a MAXGD-IP.

Matrix generation: We define GIP={MAXGD-IP(g i ,g j )| ∀g i ,g j ∈ G 1 } the set of all MAXGD-IP in G 1 . The value A'[i,j] is defined as the maximum Jaccard score between the set of genes associated with the interval [g i ,g j ] and the set of genes of each MAXGD-IP in GIP. The score of an interval that cannot be associated to a MAXGD-IP is set to 0, which is the smallest possible value. At the opposite, the best possible score is 1, that can only be obtained by an interval whose set of genes is exactly the set of genes of a MAXGD-IP. Thus, the higher the score in A'[i,j] is, the most significant the interval [g i ,g j ] is, regarding to the metabolic information.

The set GIP is computed on E. coli K-12. The E. coli genome is the one from NCBI (id: NC_000913) and the metabolic network is from the KEGG pathways database (id: eco). It results that GIP is composed of 333714 MAXGD-IP.

2

) Taking into account the coexpression information

In order to achieve such a task, we generate a coexpression matrix by calculating the Pearson correlation of each couple of genes. Let g i (resp. g j ) be the gene at position i (resp. j) in the genome of reference G 1 . As the interval of genes [g i ,g j ] is composed of many distinct genes, we define the score of expression of the interval as the means over all coexpression scores for every couple of genes inside [g i ,g j ].

Matrix A'' is then defined as follows :

where n is the number of genes and cov(g x ,g y ) is the covariance between the expression of the genes g x and g y .

When the expression level of a given gene is not measured in the experiment, the gene is not taken into account in the score of expression of the interval. If none of the genes of an interval has an expression value, then the score of the interval is 0, which is the default score. The expression of a gene with itself is not taken into account in the score of expression of the interval. Hence, for a given interval composed of n genes with an expression value, there are at most Σ 1≤i<n i different covariance measures. genomes according to their score in the matrix A, up to a complete reversal. If there are several candidates, pick one at random 2. Match all the genes of S accordingly 3. Remove from genome G1 (resp. G2 ) the unmatched gene(s) for which there remains no unmatched genes of the same family in G2 (resp. G1 ) 4. Iterate the process until all possible genes have been matched (i.e., we have obtained a maximum matching) 5. Compute the number of common intervals that have been obtained in this solution Gene expression data for E. coli are from the Gene Expression Omnibus [START_REF] Edgar | Gene expression omnibus: NCBI gene expression and hybridization array data repository[END_REF]. The experiment used in this paper is GDS2580, but other data were used for replication (GDS2578, GDS2584, GDS2585, GDS2586, GDS2587, GDS2588, GDS2589, GDS2590, GDS2591).

D. Matching operons

To quantify the functional interest of our measure, we are interested by matching common intervals of genes with operons. We consider an operon as a transcription unit that contains at least two genes, and may include more than one promoter. We get those transcription units from Ecocyc [START_REF] Karp | The ecocyc database[END_REF] for E. coli.

A given interval of genes is a non operonic interval (NOI) when there exists no operon whose set of genes is a subset of the set of genes in the interval. On the contrary the interval is a partially operonic interval (POI) when there exists a collection of operons whose set of genes is a subset of the set of operonic genes in the interval, and the interval is a full operonic interval (FOI) when there exists a collection of operons whose set of genes is the set of operonic genes in the interval. Based of this measure, we will say that an interval of genes contains at least one operon when the interval is a POI or a FOI, and an interval contains no operon when the interval is a NOI.

May be common intervals have no more operonic meaning any other set of intervals of genes. In order to compare the maximal common intervals, obtained via the IILCS algorithm, with any other, we generated 100 random sets of intervals. Let IC M be the set of maximal common intervals n x be the number of maximal common intervals of length x and X the set of lengths of the different maximal common intervals. The set IC R of random intervals is obtained by taking randomly, in genome G 1 , n x intervals with the length x, ∀ x ∈ X. Thus, IC R contains the same number of intervals of the same length as IC M .

III. RESULTS/DISCUSSION

A. Operonic interest of the maximal common intervals

As an application, we applied the above protocol on E. coli and V. cholerae genomes. The computation of all common intervals give us 11504 common intervals. As shown in Figure 6, only 43% of all common intervals contain at least one operon (FOI + POI). Similarly, the IILCS algorithm shows 325 maximal common intervals in which 74% contain at least one operon. When compared with the 100 intervals randomly produced (of similar size with those produced by IILCS), the results are similar (48%) than those obtained considering all common intervals, which confirms the interest of maximal common intervals from a functional point of view. As a natural consequence, maximal common intervals are then good candidates for applying a IILCS refinement as described above in the IISCS algorithm.

B. IISCS algorithm application results

The IISCS algorithm application gives a similar number of common intervals (318 and 317 when applied respectively with metabolic and co-expression information). Despite this obvious similarity between the IILCS and IISCS results, the IISCS algorithm shows the great advantage to associate a score (either metabolic or co-expression like) to each common interval. It gives us the opportunity to select the most interesting intervals based on a given omics knowledge. After a parameter fitting process (data not shown), we consider a common interval as interesting when its score is above 0.6. In that case, 30 intervals reach the cut-off in a metabolic context, whereas 86 intervals are selected in a coexpression one.

As previously done for the IILCS maximal common intervals, we establish the operonic interest of the selected intervals. Figure 7 illustrates the corresponding results. The functional refinement of the common intervals is obvious using the IISCS algorithm (i.e. from 74% (FOI + POI) to respectively 90% and 89% of intervals with an operonic meaning in a metabolic and co-expression context). In proportion, we obtain less NOI in both omics contexts. Furthermore, note that when one compares both contexts, only 13 intervals are selected in either metabolic and coexpressed-like.

C. Operon prediction vs. functional insights

IISCS results sound accurate from a functional viewpoint when compared to the bacterial operons. Therefore, passing from the functional meaning of intervals to the computational prediction of operons is very tempting. Operon prediction methods are evaluated in function of two measures [START_REF] Salgado | Operons in escherichia coli: genomic analyses and predictions[END_REF]. The first, called sensitivity, relies on the rate of the number of accurately predicted within operon gene pairs on concrete within operon gene pairs. In other words, higher the sensitivity is, more the technique is efficient to recognize the gene composition of operons. The second, called specificity, relies on the rate of the number of accurately predicted transcription unit border gene pairs on concrete transcription unit border gene pairs. Higher the specificity is, more the method accurately delimits the operon borders. When applied on E. coli, the maximal common intervals show 45.47% sensitivity and 21.43% specificity. IISCS in a metabolic context emphasizes 30.26% sensitivity and 12.48% specificity. IISCS in a co-expression context shows 18.75% sensitivity and 15.39% specificity.

Thus, the IISCS heuristic is obviously a bad computational operon predictor. However, few common intervals (30) correspond to 50 operons in metabolic context, which implies that common intervals contain a more complex organization than just a unique operon per interval. As an example, IISCS provides an interval composed by four operons (fepDGC, fepB, entS, entCEBA-ybdB). It is important to notice herein that all these four operons are coregulated by common activators: Crp and Fur. fepDGC and fepB products compose a unique ABC transporter, which indicates the functional and essential relationship of these two operons, corroborating their common selection within an interval. Moreover, entS operon is divergent or antagonistic to fepDGC, which reinforces the intuition of common intervals composed by functional units instead of a unique operon. Note again, that such a complex structure may not be predicted using standard computational operon predictors.

IV. CONCLUSION

We proposed herein a technique that combines comparative genomics algorithms and omics data. As already pointed out in [START_REF] Chuang | Binary particle swarm optimization for operon prediction[END_REF], such an integration significantly improves the functional understanding of genomes comparison. As mentioned above, this integrated genomics approach is not appropriate to predict operons as other standard methods, but emphasizes functional units (themselves composed by operons more or less conserved among species) and their respective organizations in terms of gene rearrangements. Beyond the simple help to the genome annotation, this information is useful to discriminate functional units conserved from one species to another that might be further investigated using systems biology techniques and other modeling approaches.

  Figure 2. Example of genes matching under the exemplar and maximum matching models. (a) Here, only the gene family labelled 2 is duplicated in genomes. In the exemplar model, we keep only one occurrence of gene 2 in both genomes. (b) In the maximum matching model, we keep two occurrences of gene 2. Dashed genes correspond to genes that are left aside for common intervals computation, since they are not present in the matching.

Figure 3 .

 3 Figure 3. IILCS heuristicInput: Two genomes G 1 and G 2 Output: A set of common intervals between G 1 and G 2 1. Compute the Longest Common Substring S of the two genomes, up to a complete reversal. If there are several candidates, pick one at random 2. Match all the genes of S accordingly 3. Remove from genome G 1 (resp. G 2 ) the unmatched gene(s) for which there remains no unmatched genes of the same family in G 2 (resp. G 1 ) 4. Iterate the process until all possible genes have been matched (i.e., we have obtained a maximum matching) 5. Compute the number of common intervals that have been obtained in this solution

Figure 4 .

 4 Figure 4. IISCS heuristic Input: Two genomes G1 and G2 Input: A |G1 | × |G1 | matrix A Output: A set of common intervals between G1 and G2 1. Take the best Scoring Common Substring S of the twogenomes according to their score in the matrix A, up to a complete reversal. If there are several candidates, pick one at random 2. Match all the genes of S accordingly 3. Remove from genome G1 (resp. G2 ) the unmatched gene(s) for which there remains no unmatched genes of the same family in G2 (resp. G1 ) 4. Iterate the process until all possible genes have been matched (i.e., we have obtained a maximum matching) 5. Compute the number of common intervals that have been obtained in this solution

Figure 5 .

 5 Figure 5. The matrix A that allows to reproduce heuristic IILSC from IISCS. The value of each cell A[i,j] is the length of the interval that begins with the gene at the position i in the genome and ends with the gene at the position j.

Figure 6 .

 6 Figure 6. Proportion of common intervals that are (1) full operonic intervals, (2) non operonic intervals and (3) partially operonic intervals for all common intervals, maximal common intervals and random intervals.

Figure 7 .

 7 Figure 7. Full operonic intervals, partially operonic intervals and non operonic intervals proportion for each common intervals experiment : common intervals obtained by (a) the IILCS method, (b) the IISCS method in metabolic context with a genomic density cutoff of 0.6 and (c) the IISCS method in the GDS2580 experiment context with a cutoff of 0.6 in interval expression score.


Jeremy Kiszka
email: jeremy.kiszka@wanadoo.fr

Marc Oremus

Pierre Richard

Michael Poole

Vincent Ridoux

The use of stable isotope analyses from skin biopsy samples to assess trophic relationships of sympatric delphinids off Moorea (French Polynesia)

Keywords: delphinids, ecological niche, stable isotopes, carbon, nitrogen, biopsy samples, Moorea, French Polynesia, South Pacific

Defining trophic relationships among organisms of a community is critical in ecology. However, the access to data is sometimes difficult, particularly in remote environments. Ecological niche segregation among the most common delphinid species was investigated: the spinner dolphin (Stenella longirostris), the roughed-toothed dolphin (Steno bredanensis), the short-finned pilot whale (Globicephala macrorhynchus), and the melon-headed whale (Peponocephala electra).

Resource partitioning was explored by analysing δ 13 C (reflecting foraging habitats) and δ 15 N stable isotopes (reflecting trophic level) from skin biopsies collected around Moorea from July to October 2002 to 2004. Results revealed that spinner dolphins had the lowest trophic level. The three other species had similar δ 15 N signatures. The most significant result is the differentiation of S. longirostris from S. bredanensis and G. macrorhynchus but not from the P. electra. For the latter three species, some degrees of overlap were apparent. For S. longirostris, S. bredanensis and G. macrorhynchus, variation of δ 13 C and δ 15 N stable isotope was not significant between sexes. This study suggests that stable isotopes reveal some degree of segregation and overlap within this delphinid community. However, fine-scale segregation processes may be concealed by stable isotope analyses, meaning that traditional dietary analyses investigations are complementary in answering questions related to niche segregation.

Introduction

Sympatric species with similar ecological requirements can compete for resources and thus their coexistence requires some degree of habitat and resource segregation [START_REF] Pianka | Niche overlap and diffuse competition[END_REF]. Indeed, similar species that co-occur are thought to compete for resources unless they occupy different physical locations and/or feed on different prey. A shared resource in limited supply will bring about competition between members of the same species (intra-specific competition) or between individuals of different species (inter-specific competition) [START_REF] Roughgarden | Resource partitioning among competing species: a co-evolutionary approach[END_REF].

Oceanic delphinids belong to 35 species worldwide [START_REF] Jefferson | Marine mammals of the world. A comprehensive guide to their identification[END_REF]. Many of them, have similar morphological characteristics, feeding habits and habitat preferences. This phenomenon has been documented around tropical oceanic islands, where delphinid diversity and biomass is generally high and where closely-related species co-occur [START_REF] Gross | A preliminary study of habitat and resource partitioning among co-occurring tropical dolphins around Mayotte, southwest Indian Ocean[END_REF]. Around these islands, high cetacean diversity may be explained by the presence of a wide range of marine habitats in close proximity to one another [START_REF] Kiszka | Cetacean diversity around the Mozambique Channel island of Mayotte (Comoros archipelago)[END_REF]. In addition, oceanic islands appear to constitute areas of particular density of top predators due to an "island mass" effect. Similar to continental margins, insular slopes of islands potentially provide more abundant resources in the oligotrophic tropical marine environment (Guilmartin & Revelante, 1974). This situation of sympatry suggests that fine-scale mechanisms allow for the partitioning of habitats and/or resources. A study of the tropical delphinid community around the island of Mayotte, in the Comoros Archipelago (south-western Indian Ocean), has shown that the ecological niches of the delphinids occurring there do not overlap [START_REF] Gross | A preliminary study of habitat and resource partitioning among co-occurring tropical dolphins around Mayotte, southwest Indian Ocean[END_REF]. Indeed, these species capture prey at different depths of the water column, where prey communities are segregated according to species and size. In other areas, such as the Bahamas, the cetacean community shares habitat and resources but only during the season when prey abundance is sufficient to support its needs, while competitive exclusion exists for the rest of the year [START_REF] Macleod | Diversity, relative density and structure of the cetacean community in summer months east of Great Abaco, Bahamas[END_REF]. On the other hand, top predators may overlap in their feeding habits due to low productivity of tropical waters [START_REF] Cherel | Resource partitioning within a tropical seabird community: new information from stable isotopes[END_REF]. If these shared resources are limited quantitatively, inter-species competition can occur.

The dietary ecology of cetaceans and their trophic level can be determined using different methods. The most extensively used consist in analysing the stomach contents of dead animals.

However, the specimens required for performing such analyses are often unavailable. The use of naturally occurring nitrogen and carbon stable isotopes has provided alternative information from which to better understand top predator feeding ecology, including marine mammals [START_REF] Hobson | Determination of trophic relationships within a high Arctic marine food web using δ 13 C and δ 15 N analysis[END_REF][START_REF] Abend | Differences in ratios of stable isotopes of nitrogen in longfinned pilot whales (Globicephala melas) in the western and eastern North Atlantic[END_REF][START_REF] Das | Marine mammals from the southern North Sea: feeding ecology data from δ 13 C and δ 15 N measurements[END_REF][START_REF] Zhao | Trophic interactions of Antarctic seals as determined by stable isotope signatures[END_REF][START_REF] Gross | A preliminary study of habitat and resource partitioning among co-occurring tropical dolphins around Mayotte, southwest Indian Ocean[END_REF]. This approach is generally considered as complementary to stomach content studies as it integrates feeding habits on a longer-term basis. Various tissues, having varying temporal resolution (turnover rates), may be used in stable isotope analyses, including skin [START_REF] Gross | A preliminary study of habitat and resource partitioning among co-occurring tropical dolphins around Mayotte, southwest Indian Ocean[END_REF].

Turnover rate for this tissue has been estimated for the beluga whale (Delphinapterus leucas;[START_REF] St Aubin | Seasonal epidermal molt in beluga, Delphinapterus leucas[END_REF] and the common bottlenose dolphin (Tursiops truncatus; [START_REF] Hicks | Epidermal growth in the bottlenose dolphin, Tursiops truncatus[END_REF].

The estimated time required for cell migration, from the basal lamina to the outermost surface, is at least two months. The carbon and nitrogen isotope ratios ( 13 C/ 12 C and 15 N/ 14 N, expressed hereafter as δ 13 C and δ 15 N) of a consumer reflect those of its diet, with a slight retention of the heavier isotope and excretion of the lighter one [START_REF] Das | Marine mammals from the southern North Sea: feeding ecology data from δ 13 C and δ 15 N measurements[END_REF]. As a consequence, tissues will be enriched with heavy isotopes at every trophic level (1‰ for δ 13 C and 3‰ for δ 15 N). The minor stepwise trophic enrichment of the carbon-isotope ratio limits its use in assessing trophic levels but enhances its use in tracking carbon sources through a food chain. The carbon isotope ratio of secondary and tertiary consumers should thus reflect the source of carbon at the base of their food chain [START_REF] Kelly | Stable isotopes of carbon and nitrogen in the study of avian and mammalian trophic ecology[END_REF].

Moorea, a volcanic tropical island in French Polynesia (South Pacific), is characterized by the presence of many species of cetaceans, including several resident odontocetes, mostly delphinids [START_REF] Poole | A sighting and stranding network in French Polynesia[END_REF][START_REF] Poole | Aspects of the behavioral ecology of spinner dolphins (Stenella longirostris) in the nearshore waters of Mo'orea, French Polynesia[END_REF][START_REF] Oremus | Isolation and interchange among insular spinner dolphin communities in the South Pacific revealed by individual identification and genetic diversity[END_REF]. At least thirteen species of dolphins may coexist around the island. Of these, the most common are the spinner dolphin (Stenella longirostris), the rough-toothed dolphin (Steno bredanensis), the short-finned pilot whale (Globicephala macrorhynchus) and the melon-headed whale (Peponocephala electra) [START_REF] Gannier | Distribution of cetaceans off the Society Islands (French Polynesia) as obtained from dedicated surveys[END_REF]. The present study aimed to investigate ecological niche partitioning in the dolphin community of Moorea, especially for the spinner dolphin, the rough-toothed dolphin, the shortfinned pilot whale and the melon-headed whale. We concentrated on these four species as they can be found within the same proximity around the island, in closely-related habitats within a small area and at all seasons [START_REF] Poole | A sighting and stranding network in French Polynesia[END_REF]. We hypothesised that these four species have different feeding niches that could be reflected in diverging stable isotope signatures. We also investigated some potential segregation processes that may occur intra-specifically, especially between sexes. Resource partitioning between sexes has been documented for a number of species, including mammals such as the giraffe (Giraffa camelopardalis) and several primate species [START_REF] Beier | Sex differences in quality of white-tailed deer diets[END_REF][START_REF] Young | Sex differences in giraffe feeding ecology: energetic and social constraints[END_REF]. Sexual segregation in foraging habitats has also been documented for some marine mammals, such as the grey seal (Halichoerus grypus) [START_REF] Breed | Sexual segregation of seasonal foraging habitat in a non-migratory marine mammal[END_REF]. Females may use higher quality food, especially during gestation and lactation; therefore, it is often assumed that the energetic costs are greater for females than they are for males [START_REF] Key | Sex differences in energy expenditure in non-human primates[END_REF]. This could result in diverging stable isotope signatures if females develop sex-specific foraging strategies to fulfil their elevated energy requirements. On the other hand, in dimorphic species, such as long-finned pilot whales (Globicephala melas), males seem to have higher energetic needs (due to their larger size and weight) and potentially higher diving capabilities, and consequently use larger and deeper-living prey than females [START_REF] Desportes | Preliminary results on the diet of long-finned pilot whales off the Faroe Islands[END_REF]. As a consequence, males may have a higher trophic level than females.

In order to answer the question of niche segregation among the four most common dolphin species around Moorea Island, and intra-specifically between sexes, we analysed δ 13 C and δ 15 N stable isotopes from skin biopsies collected from 2002 to 2004.

Material and methods

Study area

Moorea (17°30'S, 149°50'W) is a high volcanic island of the Society Archipelago (134 km²), French Polynesia, located in the central South Pacific (Figure 1). The island is almost entirely surrounded by a barrier reef which delimits a lagoon system connected to the open ocean by twelve passes varying in width and depth. Depth drops to more than 1000m just 2 to 3 km outside the barrier reef. All species are usually observed outside the barrier reef, except the spinner dolphin (Stenella longirostris) which commonly enters the lagoon through passes during daytime [START_REF] Poole | Aspects of the behavioral ecology of spinner dolphins (Stenella longirostris) in the nearshore waters of Mo'orea, French Polynesia[END_REF] and feed in the open ocean only at night [START_REF] Norris | The Hawaiian Spinner Dolphin[END_REF].

Sample collection

Samples were collected from 2002 to 2004, during small-boat-based surveys (2002, n = 107; 2003, n = 32, 2004, n = 63), in sea conditions not exceeding Beaufort 3. Most of the observation effort concentrated in austral winter (July -October). Efforts were made to survey the entire coastline. However, the targeted species during these surveys were the spinner dolphin and the humpback whale (Megaptera novaeangliae), and efforts were primarily concentrated in nearshore waters (i.e., within 500 m from the barrier reef or within the lagoon), where these species are preferentially distributed during daytime [START_REF] Poole | Aspects of the behavioral ecology of spinner dolphins (Stenella longirostris) in the nearshore waters of Mo'orea, French Polynesia[END_REF][START_REF] Poole | Occurrence of humpback whales (Megaptera novaeangliae) in French Polynesia in 1988[END_REF]. Therefore, it must be noted that search efforts were not optimal for encounters of more oceanic species. During each encounter with dolphins, geographical position was recorded, group size was estimated by visual counts, and photographs were taken using a digital camera equipped with a 70-300 mm lens. Skin samples for genetic analyses were collected from adult dolphins using a small stainless-steel biopsy dart fired from a modified veterinary capture rifle equipped with a variable pressure valve [START_REF] Krützen | A biopsy system for small cetaceans: darting success and wound healing in Tursiops spp[END_REF]. Behavioural responses to biopsy attempts were recorded and reported in [START_REF] Oremus | Genetic and demographic investigation of population structure and social system in four delphinid species[END_REF]. Level of short-term responses was low for all species and similar to that reported elsewhere (e.g. [START_REF] Krützen | A biopsy system for small cetaceans: darting success and wound healing in Tursiops spp[END_REF]. All samples were preserved in 70% ethanol and stored at -20°C for subsequent analysis.

Stable isotope analyses

Blubber and skin were separated for each biopsy. Stable isotope analyses were only performed on the skin. The ethanol was evaporated at 45°C over 48 h and the samples were ground and freeze-dried [START_REF] Hobson | Preservation of blood and tissue samples for stable-carbon and stable-nitrogen isotope analysis[END_REF]. The preservative used (ethanol) was the most suitable that could be used due to logistical constraints. Ethanol storage may have variable and organism-dependent effects on stable isotope signatures, generally higher on δ13C values than on δ15N values [START_REF] Kaehler | Effect of storage and preservation on the δ 13 C and δ 15 N signatures of selected marine organisms[END_REF]. It does not affect stable isotope signatures in freshwater zooplankton and benthic macroinvertebrates [START_REF] Syväranta | Evaluating the utility of stable isotope analyses in archived freshwater sample materials[END_REF], bird eggs, blood and muscle [START_REF] Hobson | Preservation of blood and tissue samples for stable-carbon and stable-nitrogen isotope analysis[END_REF][START_REF] Gloutney | Field preservation techniques for the analysis of stablecarbon and nitrogen isotopes in eggs[END_REF]. The increase in δ13C values is generally considered to be due to the extraction of some lipids but because lipids are depleted in δ13C, they have anyway to be extracted to avoid a bias in the isotopic signature of δ13C [START_REF] De Niro | Influence of diet on the distribution of carbon isotopes in animals[END_REF][START_REF] Tieszen | Fractionation and turnover of stable carbon isotopes in animal tissues: implications for δ 13 C analysis of diet[END_REF], that likely cancels any potential effect of storage in ethanol. Lipid extraction was done by shaking (1 h at room temperature) in cyclohexane (C6H12), and subsequent centrifugation prior to analysis. After drying, small sub-samples (0.35 to 0.45 mg + 0.001 mg) were prepared for analysis. Stable isotope measurements were performed with a continuous-flow isotope-ratio mass spectrometer (Delta V Advantage, Thermo Scientific, Germany) coupled to an elemental analyser (Flash EA1112 Thermo Scientific, Italy). Results are expressed in δ notation relative to PeeDee Belemnite and atmospheric N 2 for δ 13 C and δ 15 N, respectively, according to the equation

1000 1 tan ×       - = dard s sample R R X δ
where X is 13 C or 15 N and R is the isotope ratio 13 C/ 12 C or 15 N/ 14 N, respectively. Replicate measurements of internal laboratory standards (acetanilide) indicated that measurement errors were <0.1‰ for δ 13 C and δ 15 N. Percent C and N elemental composition of tissues were obtained using the elemental analyzer and used to calculate the sample C:N ratio, indicating good lipid removal efficiency when <4.

Species identification and molecular sexing

Species sampled for this study were identified visually and confirmed using photographic and genetic evidences. Mitochondrial DNA control region were sequenced for all samples, as reported in [START_REF] Oremus | Isolation and interchange among insular spinner dolphin communities in the South Pacific revealed by individual identification and genetic diversity[END_REF], and sequences were submitted to the program DNAsurveillance v. 3.01 [START_REF] Ross | DNA Surveillance: Web-based molecular identification of whales, dolphins and porpoises[END_REF] to determine species identity. Sex was identified by coamplification of the male-specific sry gene and ZFX positive control gene [START_REF] Gilson | Deer gender determination by polymerase chain reaction: validation study and application to tissues, bloodstains, and hair forensic samples from California[END_REF].

Data analysis

Differences of stable isotopes signatures of δ 15 N and δ 13 C among species were tested using non-parametric Kruskal-Wallis tests. Pairwise tests to compare δ 13 C and δ 15 N values between species were performed using Mann-Whitney-U tests. Variability of δ 13 C and δ 15 N signatures among sexes was also tested using U tests. For all statistical analyses, a significance level of α=0.05 was used.

Results

Sampling

We collected skin samples from 91 delphinids: spinner dolphin (N = 40; 29 males and 11 females), rough-toothed dolphin (N = 35; 23 males and 12 females), short-finned pilot whale (N = 12; 6 males and 5 females) and melon-headed whale (N = 4; not sexed). All samples were collected during the same season, i.e. austral winter (July to October). All sampled individuals were considered to be adults based on their size.

Resource partitioning

The distribution of δ 15 N and δ 13 C values is given in Figure 2. Overall, overlap among species is present, and intra-specific variability appears high. However, significant statistical differences were found among the four species for δ 15 N (H = 24; df = 3; P < 0.001) and δ 13 C values (H = 37; df = 3; P < 0.001). Even with the melon-headed whale removed from the analysis, differences remained significant (for δ 15 N: H = 12.3; df = 2; P = 0.001 and δ 13 C: H = 13; df = 2; P = 0.002). Short-finned pilot whales had the highest δ 15 N and δ 13 C signatures, spinner dolphins had the lowest δ 15 N values (Figure 2), and melon-headed whales had the lowest δ 13 C signatures.

Rough-toothed dolphins had an intermediate position between spinner dolphins and short-finned pilot whales. At a finer scale, when looking at differences in δ 13 C and δ 15 N signatures between species, some degrees of overlap and differentiation can be observed (Table 1). In δ 13 C, differences were not significant between the spinner dolphin and the melon-headed whale nor between the rough-toothed dolphin and the short-finned pilot whale. For other pairwise comparisons of δ 13 C values, statistically significant differences were found. For δ 15 N, overlap was statistically significant between the melon-headed whale, the rough-toothed dolphin and the short-finned pilot whale. The spinner dolphin could not be differentiated from the melon-headed whale but differed significantly from the rough-toothed dolphin and short-finned pilot whale.

Differences between sexes

We tested differences in stable isotope signatures between males and females, both for δ 15 N and a δ 13 C, in all species except the melon-headed whale; in the latter case, sample size was too small and sex data unavailable. Box plots (Figure 4) show stable isotope median values, 50, 75 percentiles and outliers of the three species. Male spinner dolphins and rough-toothed dolphins seem to have a lower trophic position than females. In addition, both species seem to feed on less 13 C-enriched preys (Figure 4). An opposite situation was found for short-finned pilot whales, with males having higher mean δ 15 N and δ 13 C signatures. For the short-finned pilot whale, males seem to have a wider range of δ 13 C signatures (Figure 4). Conversely, females had a wider range of δ 15 N values. However, none of the differences were statistically significant (spinner dolphins: δ 15 N: U = 59; P = 0.236; δ 13 C: U = 33; P = 0.203, rough-toothed dolphin: δ 15 N: U = 51; P = 0.266; δ 13 C: U = 57; P = 0.409 and short-finned pilot whales: δ 15 N: U = 50; P = 0.193; δ 13 C: U = 13; P = 0.074).

Discussion

General comments

Stable isotope approaches are powerful analytical tools to link the foraging ecology of top predators with habitat, diving behaviour and diet [START_REF] Das | Marine mammals from the southern North Sea: feeding ecology data from δ 13 C and δ 15 N measurements[END_REF][START_REF] Zhao | Trophic interactions of Antarctic seals as determined by stable isotope signatures[END_REF]. This has been shown for a number of taxa, including seabirds [START_REF] Cherel | Resource partitioning within a tropical seabird community: new information from stable isotopes[END_REF]), sharks (Comi et al., 2005), pinnipeds [START_REF] Zhao | Trophic interactions of Antarctic seals as determined by stable isotope signatures[END_REF] and cetaceans such as tropical delphinids [START_REF] Gross | A preliminary study of habitat and resource partitioning among co-occurring tropical dolphins around Mayotte, southwest Indian Ocean[END_REF]. These results were the first describing the isotopic niches of sympatric delphinids in French Polynesia; they can be used in the future to examine seasonal, year-to-year or long term variation in delphinid trophic ecology in the region. Lack of significance in some comparisons may partly result from insufficient sample size. Analytical resolution was <0.1‰ as shown by replicate measurements of internal laboratory standards, and delipidation was successfully carried out on all samples since C:N ratios were always <4. Carbon sources and reference levels of nitrogen were not investigated in this work; hence isotopic data can only be interpreted in terms of relative values among the four species studied.

Isotopic niche segregation

Very few other studies have attempted to address issues regarding ecological segregation in delphinid assemblages by analysing isotopic signature in skin biopsies [START_REF] Gross | A preliminary study of habitat and resource partitioning among co-occurring tropical dolphins around Mayotte, southwest Indian Ocean[END_REF], but more work has been done on communities of other marine top predators including sharks, large teleost fishes, seabirds and marine mammals [START_REF] Hobson | Determination of trophic relationships within a high Arctic marine food web using δ 13 C and δ 15 N analysis[END_REF][START_REF] Abend | Differences in ratios of stable isotopes of nitrogen in longfinned pilot whales (Globicephala melas) in the western and eastern North Atlantic[END_REF][START_REF] Das | Marine mammals from the southern North Sea: feeding ecology data from δ 13 C and δ 15 N measurements[END_REF][START_REF] Zhao | Trophic interactions of Antarctic seals as determined by stable isotope signatures[END_REF][START_REF] Domi | Feeding ecology of five commercial shark species of the Celtic Sea through stable isotope and trace metal analysis[END_REF][START_REF] Ménard | Isotopic evidence of distinct feeding ecologies and movement patterns in two migratory predators (yellowfin tuna and swordfish) in the western Indian Ocean[END_REF][START_REF] Cherel | Resource partitioning within a tropical seabird community: new information from stable isotopes[END_REF][START_REF] Jaeger | Etude isotopique des variations saisonnière et à long terme de l'écologie alimentaire des oiseaux marins de l'océan Austral[END_REF]. In top predator communities, significant habitat partitioning has been found in polar communities, such as in pinnipeds from the Antarctic [START_REF] Zhao | Trophic interactions of Antarctic seals as determined by stable isotope signatures[END_REF]. Conversely, in tropical sympatric seabirds, significant overlap of feeding niches has been found at the community level [START_REF] Cherel | Resource partitioning within a tropical seabird community: new information from stable isotopes[END_REF]. This may be laid to the low productivity of tropical oligotrophic waters, leading top predators to share the same feeding resources. However, significant differences in isotopic niches were found in delphinids from the tropical island of Mayotte, in the south-western Indian Ocean [START_REF] Gross | A preliminary study of habitat and resource partitioning among co-occurring tropical dolphins around Mayotte, southwest Indian Ocean[END_REF]. In the Southern Hemisphere, clearly structured latitudinal carbon isoscapes have been found from the Antarctic to the subtropical zones [START_REF] Jaeger | Etude isotopique des variations saisonnière et à long terme de l'écologie alimentaire des oiseaux marins de l'océan Austral[END_REF]. This structured shape of latitudinal isoscapes may not exist in tropical waters, mainly due to the oligotrophic nature of these waters. However, around oceanic islands such as Mayotte, clear differences of δ 13 C and δ 15 N values were observed between the three delphinid genera investigated, which could be interpreted by the structured nature of marine habitats (high carbon gradients from coastal to oceanic surface waters; Kiszka et al., unpublished data) around the island, from lagonal to oceanic waters. In addition, diving predators such as small cetaceans use resources at varying depth, where carbon gradients are significant (from the surface to bottom, where organic matter accumulates and provides carbon sources). In conclusion, investigating trophic relationships of predators living in a structured system (such as around an oceanic island) and feeding at varying depth may result in diverging isotopic niches, while in surface feeders like seabirds, feeding in the homogenous oceanic system may result in low to no difference in isotopic niches.

In our study, overall analyses show some degrees of niche partitioning among the four species investigated, the most significant result being the differentiation in trophic level revealed by δ 15 N values among spinner dolphin, rough-toothed dolphin and short-finned pilot whale, but not between spinner and melon-headed whale. In terms of foraging habitats, δ 13 C values were significantly different between all species except two pairs of species that could not be discriminated: spinner dolphin/melon-headed whale and rough-toothed dolphin/short-finned pilot whale. No significant intra-specific difference was found between sexes. Finally, it must be kept in mind that differences in isotopic signatures are informative, whereas similarities do not necessarily imply that species share a similar trophic niche; indeed different foraging strategies may result in similar isotopic signatures. If stable isotope signatures and preys of two predators are effectively similar, other segregation processes may occur, such as differential spatial and temporal use of habitat and resources. Published studies from other areas in the Pacific suggest that the community of delphinids around Moorea is likely to feed on pelagic and oceanic prey.

The spinner dolphin had the lowest trophic level and, with the melon-headed whale, the lowest δ 13 C values. The spinner dolphin feeds primarily on mesopelagic fishes and squids at night [START_REF] Norris | The Hawaiian Spinner Dolphin[END_REF][START_REF] Dolar | Comparative feeding ecology of spinner dolphins (Stenella longirostris) and Fraser's dolphins (Lagenodelphis hosei) in the Sulu Sea[END_REF]. Vertical distribution of the prey items summarized from published literature indicate that spinner dolphins forage in the upper 200 meters and probably occasionally as deep as 400 meters [START_REF] Dolar | Comparative feeding ecology of spinner dolphins (Stenella longirostris) and Fraser's dolphins (Lagenodelphis hosei) in the Sulu Sea[END_REF]. Melon-headed whales are oceanic predators, mostly feeding on mesopelagic fishes and cephalopods throughout their range [START_REF] Brownell | Behavior of melon-headed whales, Peponocephala electra, near oceanic islands[END_REF]. When considering the vertical distribution of these prey groups, melonheaded whales probably forage in the upper 700 meters [START_REF] Young | Vertical distribution and photosensitive vesicles of pelagic cephalopods from Hawaiian waters[END_REF]. Like spinner dolphins, melon-headed whales seem to feed at night during vertical migrations of their preys, while they rest and socialize during daytime near oceanic islands [START_REF] Brownell | Behavior of melon-headed whales, Peponocephala electra, near oceanic islands[END_REF]. Therefore, the two species may share some similar features of habitat and resource use, although at Moorea, melonheaded whales do not use inshore and nearshore waters like spinner dolphins do. This possible overlap was confirmed in this study, as stable isotope signatures were not significantly distinguishable. Note that this absence of significant difference could be due to small sample size for melon-headed whales. However, around the island of Mayotte (with similar habitats to those around Moorea) in the south-western Indian Ocean, stable isotope analyses on skin samples revealed significant differences in δ 13 C and δ 15 N values with similar sample size than in our study [START_REF] Gross | A preliminary study of habitat and resource partitioning among co-occurring tropical dolphins around Mayotte, southwest Indian Ocean[END_REF]. Melon-headed whales were characterised by significantly higher δ 13 C and δ 15 N values [START_REF] Gross | A preliminary study of habitat and resource partitioning among co-occurring tropical dolphins around Mayotte, southwest Indian Ocean[END_REF]. In our study, δ 13 C signatures were very similar between spinner dolphins and melon-headed whales, suggesting they prey on species with similar δ 13 C signatures or even similar prey. This could suggest that their prey are not limited quantitatively, allowing the two species to feed on similar resources without deleterious competition for one or the other.

However, despite no statistical evidences, some differences in the δ 15 N values suggest that melon-headed whale has a higher trophic level, and may probably feed on prey of higher trophic position (probably larger prey). The feeding ecology of the rough-toothed dolphin is poorly known, but it is known to feed on cephalopods (Aguiar dos [START_REF] Aguiar Dos Santos | Cephalopods in the diet of marine mammals stranded or incidentally caught along southeastern and southern Brazil (21 -34°S)[END_REF], deep water fishes [START_REF] Miyazaki | Rough-toothed dolphin Steno bredanensis[END_REF] and occasionally on coastal prey (Shallenberger, 1981).

Foraging on flying fishes and other surface fish has been regularly observed off Moorea (Oremus & Poole, personal observations). In the eastern tropical Pacific, rough-toothed dolphins regularly feed on dolphin fish (Coryphaena hippurus; [START_REF] Pitman | Rough-toothed dolphins (Steno bredanensis) as predators of Mahimahi (Coryphaena hippurus)[END_REF]. Short-finned pilot whales are deep-water cephalopod predators (Hernandez-Garcia & Martin, 1994). Recent evidence suggests that short-finned pilot whales can dive to depths reaching 1,000 meters on occasion [START_REF] Aguilar Soto | Cheetahs of the deep sea: deep foraging sprints in short-finned pilot whales off Tenerife (Canary Islands)[END_REF]. Based on the available literature, making comparisons of the diet of the rough-toothed dolphin and the short-finned pilot whale appears highly hazardous, given the limited existing information. However, the latter seem to feed deeper in the water column. In our results, the rough-toothed dolphin and the short-finned pilot whale were not statistically different in their stable isotope signatures. However, S. brenadensis had lower δ 13 C and δ 15 N signatures than those in short-finned pilot whales. The later may feed on more carbonenriched prey. As there is a bottom-surface gradient of δ 13 C, with higher carbon values from the sea bottom than at the surface [START_REF] Hobson | Tracing origins and migration of wildlife using stable isotopes: a review[END_REF], higher δ 13 C values observed in short-finned pilot whales could be due to their preference for prey occurring deeper in the water column, in closer proximity to bottom organic matter sources. This is consistent with published literature describing general ecology, prey preferences and diving behaviour of short-finned pilot whales [START_REF] Aguilar Soto | Cheetahs of the deep sea: deep foraging sprints in short-finned pilot whales off Tenerife (Canary Islands)[END_REF]Hernandez-Garcia & Martin, 1994). The lower δ 15 N values observed in the rough-toothed dolphin may be attributed to its preference for preys of a lower trophic position than those consumed by pilot whales.

Overall, when looking at biometrical data of predators from our study [START_REF] Jefferson | Marine mammals of the world. A comprehensive guide to their identification[END_REF], we observe that there is a correlation between trophic position and body size. Larger predators have a higher trophic level in this delphinid community, which is consistent with many other species communities.

Difference in feeding ecology between genders has been documented in delphinids [START_REF] Desportes | Preliminary results on the diet of long-finned pilot whales off the Faroe Islands[END_REF]. From our dataset, we did not observed statistically significant gender-specific variations of stable isotope signatures. However, mean values of carbon and nitrogen isotope values were higher for female spinner and rough-toothed dolphins. On the contrary, carbon and nitrogen isotope values were higher in male short-finned pilot whales. In other words, the feeding niches of delphinids from Moorea may not differ according to sex.

However, some segregation processes may be not detected through the use of stable isotopes, and traditional dietary analyses may answer this question. Detailed studies of diving behaviour may also contribute to assessing gender-specific variation in feeding strategies. However, at least for short-finned pilot whales, our sample size was small, which could conceal potential differences related to sex. Indeed, it is known that males in sexually dimorphic species such as long-finned pilot whales feed on larger prey, and potentially have a higher trophic level [START_REF] Desportes | Preliminary results on the diet of long-finned pilot whales off the Faroe Islands[END_REF]. Nevertheless, no detailed studies of the diet of short-finned pilot whales have been published, and such gender-specific variation may not occur in this species.

Overall, this study

Conclusions

When conventional dietary studies cannot be undertaken, such as around Moorea where dead animals from strandings and bycatch are unavailable, the use of stable isotopes can be recommended to assess trophic relationships in a community of cetacean predators, especially delphinids. The delphinids around Moorea seem to have different feeding niches, although statistical analyses do not always show significant differences among species. To complement the interpretation of these first results, documenting accurate data on local carbon sources and reference levels of nitrogen by analysing the isotopic content of particulate organic material that constitute the basis of the local food webs and/or of a range of putative prey taxa from coastal to oceanic habitats, would help in characterizing the three-dimensional isoscape [START_REF] Jaeger | Etude isotopique des variations saisonnière et à long terme de l'écologie alimentaire des oiseaux marins de l'océan Austral[END_REF] in which this assemblage of sympatric dolphins dwells. Additionally, any information on the diet, diving behaviour, activity budget and micro-scale spatial distribution of the four dolphin species constituting this community would considerably improve the potential for interpreting stable isotope data.

Table 1 :

 1 Pairwise Mann-Whitney U test p values for each pairs of delphinid species in carbon and nitrogen. Values in bold are significant, meaning that the two species do not overlap in their isotopic signatures. Stenella longirostris: spinner dolphin; Peponocephala electra: melon-headed whale; Steno bredanensis: rough-toothed dolphin; Globicephala macrorhynchus: short-finned pilot whale.

Figure 1 :

 1 Figure 1: Location of the study area.

Figure 2 :

 2 Figure 2: Stable isotope distribution (δ 13 C and δ 15 N in ‰) in delphinid skin tissues from Moorea.

Figure 3 :

 3 Figure 3: Stable isotopes (δ 13 C and δ 15 N in ‰) in delphinid skin tissues from Moorea. Graphs

Figure 4 :

 4 Figure 4: Stable isotope (δ 13 C and δ 15 N in ‰) median values, 50, 75 percentiles and outliers of

δ 13 C

	δ 13 C	Peponocephala electra Stenella longirostris Globicephala macrorhynchus	Steno bredanensis δ 15 N
	Stenella longirostris	0.394	0.0001	0.0001
	Steno bredanensis	0.005	0.131
	Globicephala macrorhynchus	0.006
	δ 15 N
	Stenella longirostris	0.09	0.00001	0.00004
	Steno bredanensis	0.235	0.06
	Globicephala macrorhynchus	0.07
	♂	♀	♂	♀
		Steno bredanensis
	♂	♀	♂	♀
		Globicephala macrorhynchus
	♂	♀	♂	♀
		27

Acknowledgements

The authors thank Gael Guillou for carrying out the mass spectrometer analyses. Florence Caurant, Aurore Aubail and Hélène Peltier (University of La Rochelle, LIENSs) provided helpful comments on the early version of the manuscript and technical support. We also thank Jeff Seminoff and Bill Perrin (NOAA) for their critical comments on the early version of the manuscript.