Xavier Yvonne
email: yvonne@math.univ-lyon1.fr

An algorithm for computing the canonical bases of higher-level q-deformed Fock spaces

Keywords: Quantum groups, canonical bases, Fock spaces. 2

We derive a straightening-free algorithm that computes the canonical bases of any higher-level q-deformed Fock space.

Introduction

The higher-level q-deformed Fock spaces form an important family of integrable representations of the quantum group U q ( sl n ). The Fock representation F q [s l ] depends on a parameter s l = (s 1 , . . . , s l ) ∈ Z l called multi-charge. It was introduced in [JMMO] in order to compute the crystal graph of the integrable irreducible representation of U q ( sl n ) with highest weight

Λ s 1 + • • • + Λ s l .
The canonical basis of a Fock space is a lower global crystal basis in the sense of [START_REF] Kashiwara | Global crystal bases of quantum groups[END_REF] that enjoys nice properties. It was constructed for l = 1 in [START_REF] Leclerc | Canonical bases of q-deformed Fock spaces[END_REF][START_REF] Leclerc | Littlewood-Richardson coefficients and Kazhdan-Lusztig polynomials[END_REF] and for l ≥ 1 by Uglov [U]. This construction relies on 1. an embedding of U q ( sl n )-modules: F q [s l ] ֒→ Λ s which is a bijection if (and only if) l = 1. Here Λ s is the space of semi-infinite q-deformed wedge products of charge s = s 1 + • • • + s l (see [U]).

2. the definition of a -involution of Λ s compatible with the embedding above. The canonical basis is then the unique -invariant basis of F q [s l ] satisfying a certain congruence property modulo the Z[q]-lattice spanned by l-multi-partitions.

In [U], Uglov provides an algorithm for computing the canonical basis based on the straightening of non-ordered q-wedge products. Unfortunately, in particular when s 1 ≫ • • • ≫ s l , the number of q-wedge products (of 2 factors) to be straightened becomes too large for this algorithm being used for practical computations. The goal of this paper is to derive a faster algorithm, which does not require straightening q-wedge products. First, we compute a -invariant basis of Λ s . The vectors of this basis are obtained by letting act the generators of the quantum groups U q ( sl n ) and U p ( sl l ) (with p = -q -1 ) and a Heisenberg algebra H to the vacuum vector (see Thm. 3.11). Then, we compute the intersection of this basis with a given weight subspace V of F q [s l ] (see Prop. 3.16). We thus get the transition matrix T (q) between the standard basis and a -invariant 1 basis of V . We can then compute the matrix A(q) of the involution of V with respect to the standard basis by the formula A(q) = T (q) T (q -1 )

-1 . Note that we are forced here to invert a large matrix with Laurent polynomial entries. This is the time-consuming step of our algorithm. Note also that although A(q) is unitriangular by [U], this matrix T (q -1 ) is not. Once A(q) is known, the computation of the canonical basis is pure routine (see e.g. [START_REF] Leclerc | Symmetric functions and the Fock space, in Symmetric functions 2001: surveys of developments and perspectives[END_REF]Thm. 7.1]).

Our algorithm is a generalization of the algorithm of Leclerc and Thibon (see [L]) for l = 1. However, two difficulties arise when l > 1. First, we have to take into account the action of U p ( sl l ), which is trivial if l = 1. Secondly, the action of the Heisenberg algebra H is much more complicated for l > 1 and it particular it requires some new work to calculate its action on the vacuum vectors without using the straightening relations (see Section 3.3).

Using our algorithm, we were able to compute the canonical bases of large weight subspaces of different Fock spaces (see examples in Section 4). These calculations helped us to conjecture and prove a theorem giving a combinatorial expression of the derivative at q = 1 of the -involution (see [START_REF] Yvonne | A conjecture for q-decomposition matrices of cyclotomic v-Schur algebras[END_REF]Thm. 2.11]). The latter result supports in turn a new conjecture for computing the q-decomposition matrices of Dipper-James-Mathas' cyclotomic v-Schur algebras with parameters specialized at powers of a complex n-th root of unity ( [START_REF] Dipper | Cyclotomic q-Schur algebras[END_REF][START_REF] Yvonne | A conjecture for q-decomposition matrices of cyclotomic v-Schur algebras[END_REF]). In this context, our result is an analogue of the Jantzen sum formula for cyclotomic v-Schur algebras [JM].

Acknowledgments. I am grateful to Bernard Leclerc for the illuminating discussions I had with him. I thank him for his reading of the preliminary versions of this paper. I also thank the referee for his/her very quick replies.

Notation. Let N (resp. N * ) denote the set of nonnegative (resp. positive) integers, and for a, b ∈ R denote by [[a; b]

] the discrete interval [a; b] ∩ Z. For X ⊂ R, a ∈ R, N ∈ N * , put (1) X N (a) := {(x 1 , . . . , x N ) ∈ X N | x 1 + • • • + x N = a}.
Throughout this article, we fix 3 integers n, l ≥ 1 and s ∈ Z. Let Π denote the set of all integer partitions. If (W, S) is a Coxeter system, denote by ℓ : W → N the length function on W .

convenient to extend the index set of the fundamental weights by setting Λ i := Λ i mod n for all i ∈ Z. The space

n-1 i=0 Q Λ i ⊕ Q δ = n-1 i=0 Q α i ⊕ Q Λ 0 is equipped with a non-degenerate bilinear symmetric form (. , .) defined by (2) (α i , α j ) = a i,j , (Λ 0 , α i ) = δ i,0 , (Λ 0 , Λ 0 ) = 0 (0 ≤ i, j ≤ n -1),
where (a i,j ) 0≤i,j≤n-1 is the Cartan matrix of sl n . Let U q ( sl n ) be the q-deformed universal enveloping algebra of sl n (see e.g. [KMS, U]). This is an algebra over Q(q) with generators e i , f i , t ±1 i (0 ≤ i ≤ n -1) and ∂; the relations will be omitted. The subalgebra of U q ( sl n ) generated by e i , f i , t ±1 i (0 ≤ i ≤ n -1) will be denoted by

U ′ q ( sl n ). If M is a U q ( sl n )-
U q ( sl n )) is (4) W n = σ 0 , . . . , σ n-1 ∼ = S n ,
where σ i (0 ≤ i ≤ n -1) is the orthogonal reflection that fixes pointwise the hyperplane orthogonal to α i .

We also introduce the algebra U p ( sl l ) with

(5) p := -q -1 .

In order to distinguish the elements related to U q ( sl n ) from those related to U p ( sl l ), we put dots over the latter. For example, ėi , ḟi , ṫ±1 i (0 ≤ i ≤ l -1) and ∂ are the generators, αi (0 ≤ i ≤ l -1) are the simple roots, Ẇl = σ0 , . . . , σl-1 is the Weyl group of U p ( sl l ) and so on.

The space Λ

s Following [U], let (6) Λ s = Λ s [n, l]
be the space of (semi-infinite) q-wedge products of charge s (this space is denoted by Λ s+ ∞ 2 in [U]). This vector space has a natural basis formed by the ordered q-wedge products; this basis is called standard. A non-ordered q-wedge product can be expressed as a linear combination of ordered q-wedge products by using the straightening relations given in [START_REF] Uglov | Canonical bases of higher-level q-deformed Fock spaces and Kazhdan-Lusztig polynomials[END_REF]Prop. 3.16] (we do not need these relations in this article). Recall the notation Z l (s) and Z n (s) from (1). Following [U, §4.1] or [Y2, §2.2.1], we shall use in the sequel the following indexations of the standard basis:

(7) {|λ, s | λ ∈ Π} = {|λ l , s l | λ l ∈ Π l , s l ∈ Z l (s)} = {|λ n , s n • | λ n ∈ Π n , s n ∈ Z n (s)}.
Following [JMMO, FLOTW, U], the vector space Λ s can be made into an integrable representation of level l of the quantum algebra U q ( sl n ). The action of U q ( sl n ) can be described in a nice way in terms of addable/removable i-nodes of l-multi-partitions; see [START_REF] Uglov | Canonical bases of higher-level q-deformed Fock spaces and Kazhdan-Lusztig polynomials[END_REF]]. Note that these formulas do no involve the straightening of q-wedge products; they are therefore handy to use for computations. In a completely similar way, Λ s can be made into an integrable representation of level n of the quantum algebra U p ( sl l ). This action can be described using the indexation by n-multi-partitions; see [START_REF] Uglov | Canonical bases of higher-level q-deformed Fock spaces and Kazhdan-Lusztig polynomials[END_REF]]. The vectors of the standard basis of Λ s are weight vectors for the actions of U q ( sl n ) and U p ( sl l ). In order to recall the expression of the weights, let us introduce the following notation. For λ l ∈ Π l , s l ∈ Z l (s), 0 ≤ i ≤ n -1, denote by N i (λ l ; s l ; n) the number of nodes with residue i (modulo n) that are contained in the Young diagram of λ l (note that the definition of residues involves the multi-charge s l ). For s l = (s 1 , . . . , s l ) ∈ Z l , define

(8) ∆(s l , n) := 1 2 l b=1 s 2 b n -s b - (s b mod n) 2 n -(s b mod n) ,
where for 1

≤ b ≤ n, s b mod n denotes the integer in [[0; n -1]] that is congruent to s b modulo n. Proposition 2.1 ([U]
) With the notation above, we have

wt(|λ l , s l ) = -∆(s l , n)δ + Λ s 1 + • • • + Λ s l - n-1 i=0 N i (λ l ; s l ; n) α i , (9) ẇt(|λ l , s l ) = -∆(s l , n) + N 0 (λ l ; s l ; n) δ + (n -s 1 + s l ) Λ0 + l-1 i=1 (s i -s i+1 ) Λi , (10) ẇt(|λ n , s n • ) = -∆(s n , l) δ + Λs 1 + • • • + Λsn - l-1 i=0 N i (λ n ; s n ; l) αi , (11) wt(|λ n , s n • ) = -∆(s n , l) + N 0 (λ n ; s n ; l) δ + (l -s 1 + s n )Λ 0 + n-1 i=1 (s i -s i+1 ) Λ i . (12)
For m ∈ Z * , Uglov defined an endomorphism B m of Λ s (see [START_REF] Uglov | Canonical bases of higher-level q-deformed Fock spaces and Kazhdan-Lusztig polynomials[END_REF]Eq. (25) & Sect. 4.3] or [START_REF] Yvonne | Canonical bases of higher-level q-deformed Fock spaces[END_REF]Def. 2.2]). His definition is obtained by taking the limit r → ∞ in the action of the center of the Hecke algebra of S r on q-wedge products of r factors. However, by [U] the operators B m do not commute, but they span a Heisenberg algebra

(13) H = B m | m ∈ Z * .
Note that the q-wedge products involved in the definition of B m are in general not ordered. Therefore, the computation of the action of H often requires straightening many q-wedge products.

We now recall some results concerning the actions of U q ( sl n ), U p ( sl l ) and H on Λ s .

Proposition 2.2 ([U])

The actions of U ′ q ( sl n ), U ′ p ( sl l ) and H on Λ s pairwise commute. For L, N ∈ N * , introduce the finite set ( 14)

A L,N (s) := {(r 1 , . . . , r L ) ∈ Z L (s) | r 1 ≥ • • • ≥ r L , r 1 -r L ≤ N }.
Theorem 2.3 ([U], Thm. 4.8) We have

Λ s = r l ∈A l,n (s) U ′ q ( sl n ) ⊗ H ⊗ U ′ p ( sl l ).|∅ l , r l = rn∈A n,l (s) U ′ q ( sl n ) ⊗ H ⊗ U ′ p ( sl l ).|∅ n , r n • .
2.3 Higher-level q-deformed Fock spaces

Recall that p = -q -1 . For

s l ∈ Z l (s), s n ∈ Z n (s), let (15) F q [s l ] = λ l ∈Π l Q(q)|λ l , s l , F p [s n ] • = λn∈Π n Q(q)|λ n , s n •
denote the higher-level (q-deformed) Fock spaces [U]. By [U], the subspace F q [s l ] ⊂ Λ s is stable under the actions of U q ( sl n ) and H (but not under the action of U p ( sl l )) and the subspace F p [s n ] • ⊂ Λ s is stable under the actions of U p ( sl l ) and H.

For N , L ∈ N * , define a bijective map

(16) θ L,N : Q L (s) → Q L (N ), (s 1 , . . . , s L ) → (N -s 1 + s L , s 1 -s 2 , . . . , s L-1 -s L ).
The next result shows that the Fock spaces are sums of certain weight subspaces of Λ s . The proof follows easily from Proposition 2.1.

Proposition 2.4 ([U]) (i) Let s n ∈ Z n (s)
. Let (a 0 , . . . , a n-1 ) := θ n,l (s n ) and w := n-1 i=0 a i Λ i . Then we have

F p [s n ] • = d∈Z Λ s w + dδ . (ii) Let s l ∈ Z l (s). Let (a 0 , . . . , a l-1 ) := θ l,n (s l ) and ẇ := l-1 i=0 a i Λi . Then we have F q [s l ] = d∈Z Λ s ẇ + d δ .
We now compare some weight subspaces of the Fock spaces. The proof again follows from Proposition 2.1.

Proposition 2.5 Let s l ∈ Z l (s) and w be a weight of F q [s l ]. Then there exists a unique pair

(s n , ẇ) such that s n ∈ Z n (s), ẇ is a weight of F p [s n ] • and F q [s l ] w = F p [s n ] • ẇ . More precisely, write w = dδ + n-1 i=0 a i Λ i (with a 0 , . . . , a n-1 , d ∈ Z), s l = (s 1 , . . . , s l ) and put s 0 := n + s l . Then we have s n = θ -1 n,l (a 0 , . . . , a n-1 ) and ẇ = d δ + l-1 i=0 (s i -s i+1 ) Λi .
Example 2.6 Take n = 3, l = 2, s l = (1, 0) and w = -2Λ 0 + Λ 1 + 3Λ 2 -2δ. Then by ( 9), we have wt (1, 1), ( 1) , s l = w, so w is a weight of F q [s l ]. By Proposition 2.5, we have

F q [s l ] w = F p [s n ] • ẇ with s n = (2, 1, -2
) and ẇ = 2 Λ0 + Λ1 -2 δ. Moreover, using ( 9) and ( 11), we see that for all |λ l ,

s l = |λ n , s n • ∈ F q [s l ] w = F p [s n ] • ẇ , we have N 0 (λ l ; s l ; n) = 2, N 1 (λ l ; s l ; n) = 1, N 2 (λ l ; s l ; n) = 0 and N 0 (λ n ; s n ; l) = N 1 (λ n ; s n ; l) = 0 (this shows a posteriori that dim(F q [s l ] w ) = 1). ⋄

Action of the Weyl groups W n and Ẇl

The Weyl group W n acts on the weight lattice n-1 i=0 ZΛ i ⊕ Zδ by

(17) σ i .δ = δ and σ i .Λ j = Λ j if j = i, Λ i-1 + Λ i+1 -Λ i -δ i,0 δ if j = i (0 ≤ i, j ≤ n -1).
Moreover, it is easy to see that W n acts faithfully on Z n (s) by ( 18)

σ 0 .(s 1 , . . . , s n ) = (s n + l, s 2 , . . . , s n-1 , s 1 -l), σ i .(s 1 , . . . , s n ) = (s 1 , . . . , s i+1 , s i , . . . , s n ) (1 ≤ i ≤ n -1),
and the set A n,l (s) defined by ( 14) is a fundamental domain for this action. In a similar way, one can define two actions of the Weyl group Ẇl of U p ( sl l ), one on the weight lattice l-1 i=0 Z Λi ⊕ Z δ and one on Z l (s).

The lower crystal basis (L[s

l ], B[s l ]) of F q [s l ] at q = 0
Let s l ∈ Z l (s). Following [START_REF] Kashiwara | Global crystal bases of quantum groups[END_REF], let A ⊂ Q(q) be the ring of rational functions which are regular at q = 0, L[s l ] := λ l ∈Π l A |λ l , s l and for 0 ≤ i ≤ n -1, let ẽi = ẽi low and fi = fi low denote Kashiwara's operators acting on

L[s l ]. Put (19) B[s l ] := {|λ l , s l mod qL[s l ] | λ l ∈ Π l }.
In the sequel, if s l ∈ Z l (s) is fixed, we shall write more briefly λ l for the element in B[s l ] indexed by the corresponding multi-partition. By [JMMO], [FLOTW], [U], the pair (L[s l ], B[s l ]) is a lower crystal basis of F q [s l ] at q = 0 in the sense of [START_REF] Kashiwara | Global crystal bases of quantum groups[END_REF], and the crystal graph B[s l ] contains the arrow λ l i -→ µ l if and only if the multi-partition µ l is obtained from λ l by adding a good i-node in the sense of [START_REF] Uglov | Canonical bases of higher-level q-deformed Fock spaces and Kazhdan-Lusztig polynomials[END_REF]Thm. 2.4].

We now recall the definition of the involution σ i of B[s l ] (we sometimes view σ i as a bijection of Π l ). First, let us introduce a piece of notation that will be used in the sequel.

Notation 2.7 For s l ∈ Z l (s) and w ∈ P(F q [s l ]), put (20) Π l (s l ; w) := {λ l ∈ Π l |λ l , s l ∈ Λ s w },
and define similarly Π n (s n ; ẇ) for

s n ∈ Z n (s) and ẇ ∈ Ṗ(F p [s n ] • ). ⋄ Definition 2.8 Fix s l ∈ Z l (s). Let λ l ∈ B[s l ] ∼ = Π l and i ∈ [[0; n -1]]. Let C be the i- chain in B[s l ] containing λ l . Let σ i (λ l ) ∈ B[s l ] ∼ = Π l be the unique element in C such that wt(σ i (λ l )) = σ i .(wt(λ l ))
. In other words, σ i (λ l ) is obtained from λ l via a central symmetry in the middle of C. This defines an involution σ i of B[s l ]. This map induces, for w ∈ P(F q [s l ]), a bijection ( 21)

σ i : Π l (s l ; w) ∼ -→ Π l (s l ; σ i .w).
⋄ By [START_REF] Kashiwara | The crystal base and Littelmann's refined Demazure character formula[END_REF], the definition of σ 0 , . . . , σ n-1 as bijections of B[s l ] gives actually rise to an action of the Weyl group W n on B[s l ], but we do not need this fact in the sequel. The next proposition gives a simple expression for σ i (λ l ) when λ l is located at the head of an

i-chain in B[s l ]. Proposition 2.9 Let s l ∈ Z l (s), w ∈ P(F q [s l ]) and i ∈ [[0; n -1]] be such that w + α i is not a weight of F q [s l ]. Let λ l ∈ Π l (
s l ; w) and µ l := σ i (λ l ). Then (i) µ l is the multi-partition obtained by adding to λ l all its addable i-nodes, and there are

k i = (w, α i ) of them. (ii) We have |µ l , s l = f (k i ) i
.|λ l , s l and |λ l , s l = e

(k i ) i .|µ l , s l . Proof. See [Y2, Prop. 3.5].

Uglov's canonical bases of the Fock spaces

Following [U], the space Λ s can be endowed with an involution . Instead of recalling the definition of this involution, we give its main properties. They turn out to characterize it completely; see Remark 3.12.

Proposition 2.10 ([U]

) There exists an involution of Λ s such that:

(i) is a Q-linear map of Λ s such that for all u ∈ Λ s , k ∈ Z, we have q k u = q -k u.
(ii) (Unitriangularity property.) For all λ ∈ Π, we have

|λ, s ∈ |λ, s + µ⊳λ Z[q, q -1 ] |µ, s ,
where ⊳ stands for the dominance ordering on partitions.

(iii) For all λ ∈ Π, we have wt(|λ, s ) = wt(|λ, s ) and ẇt(|λ, s ) = ẇt(|λ, s ).

(iv) For all

0 ≤ i ≤ n -1, 0 ≤ j ≤ l -1, m < 0, v ∈ Λ s , we have f i .v = f i .v, ḟj .v = ḟj .v and B m .v = B m .v.
By [U], this involution can be computed by straightening non-ordered q-wedge products. However, the number of q-wedge products of 2 factors to be straightened is in general too large for practical computations. We shall derive in Section 3 another more efficient algorithm that does not require straightening q-wedge products.

By Propositions 2.10 (iii) and 2.4, the higher-level Fock spaces are stable under the involution . The involution induced on these spaces will still be denoted by . Let

s l ∈ Z l (s). For µ l ∈ Π l , write (22) |µ l , s l = λ l ∈Π l a λ l ,µ l ; s l (q) |λ l , s l
with a λ l ,µ l ; s l (q) ∈ Z[q, q -1 ], and let (23) A s l (q) := a λ l ,µ l ; s l (q) λ l ,µ l ∈Π l denote the matrix of the involution of F q [s l ] with respect to the standard basis. Since the weight subspaces of F q [s l ] are stable under the involution , (9) implies that a λ l ,µ l ; s l (q) is zero unless

|λ l | = |µ l |, where |λ l | (resp. |µ l |
) denotes the number of boxes contained in the Young diagram of λ l (resp. µ l ). By Proposition 2.10 (ii), the matrix A s l (q) is unitriangular.

As a consequence, one can define, by a classical argument, canonical bases as follows.

Theorem 2.11 ([U]) Let s l ∈ Z l (s). Then there exists a unique basis

{G + (λ l , s l ) | λ l ∈ Π l } resp. {G -(λ l , s l ) | λ l ∈ Π l } of F q [s l ] such that: (i) G + (λ l , s l ) = G + (λ l , s l ) (resp. G -(λ l , s l ) = G -(λ l , s l ) ), (ii) G + (λ l , s l ) ≡ |λ l , s l mod qL + [s l ] (resp. G -(λ l , s l ) ≡ |λ l , s l mod q -1 L -[s l ] ), where L ǫ [s l ] := λ l ∈Π l Z[q ǫ ] |λ l , s l (ǫ = ±1). For ǫ = ±1, define entries ∆ ǫ λ l ,µ l ; s l (q) ∈ Z[q, q -1 ] (λ l , µ l ∈ Π l ) by (24) G ǫ (µ l , s l ) = λ l ∈Π l ∆ ǫ λ l ,µ l ; s l (q) |λ l , s l ,
and denote by

(25) ∆ ǫ s l (q) := ∆ ǫ λ l ,µ l ; s l (q) λ l ,µ l ∈Π l (ǫ = ±1)
the transition matrices between the standard and the canonical bases of F q [s l ].

We shall give some (parts of the) canonical bases of different Fock spaces in Section 4. By [U], the entries of ∆ + s l (q) (resp. ∆ - s l (q)) are Kazhdan-Lusztig polynomials of parabolic submodules of affine Hecke algebras of type A, so by [KT], these polynomials are in N[q] (resp. N[p]). Moreover, both canonical bases of F q [s l ] are dual to each other with respect to a certain bilinear form, which gives an inversion formula for Kazhdan-Lusztig polynomials; see [START_REF] Uglov | Canonical bases of higher-level q-deformed Fock spaces and Kazhdan-Lusztig polynomials[END_REF]Thm. 5.15]. By [U], the basis

{G + (λ l , s l ) | λ l ∈ Π l } is a lower global crystal basis (in the sense of [Kas1]) of the integrable U q ( sl n )-module F q [s l ].
3 Computation of the canonical bases of F q [s l ] 3.1 A -invariant basis B of Λ s Notation 3.1 In this section, we use the following notation.

* In this article, we always identify the multi-partition λ l = (λ (1) , . . . , λ (l)

) ∈ Π l with its Young diagram {(i, j, b) ∈ N * × N * × [[1; l]] | 1 ≤ j ≤ λ (b) i } . Let (i(γ), j(γ), b(γ)) denote the coordinates of the node γ ∈ λ l . Let (26) ∂λ l := {(i, j, b) ∈ λ l | j = λ (b)
i } denote the border of λ l , that is the vertical strip made of the rightmost nodes of λ l . * For s l ∈ Z l (s), let

(27) M q [s l ] := U q ( sl n ).|∅ l , s l .
Let Π l (s l )

• = Π l (s l , n)

• denote the set of l-multi-partitions indexing the crystal graph of the U q ( sl n )-module M q [s l ]. For s l ∈ Z l (s) and w ∈ P(F q [s l ]), put (28) Π l (s l ; w) • = Π l (s l , n; w)

• := Π l (s l ; w) ∩ Π l (s l ) • . * Let (29) X l,n := {(v 1 , . . . , v l ) ∈ Z l | n -1 ≥ v 1 ≥ • • • ≥ v l ≥ 0}. Note that the U ′ q ( sl n )-module M q [s l ] s l = (s 1 , . . . , s l ) ∈ Z l (s) is isomorphic to M q [v l ] for a unique multi-charge v l = (v 1 , . . . , v l ) ∈ X l,n ; more precisely, this v l is related to s l by Λ v 1 + • • • + Λ v l = Λ s 1 + • • • + Λ s l . ⋄ 3.1.1 A basis of M q [s l ] (s l ∈ Z l (s))
In [J1], Jacon gave a monomial basis of M q [v l ] with v l ∈ X l,n . Using this basis, he derived in [J2] an algorithm for computing the canonical bases of M q [v l ]. We recall here his result and give a basis of the same type for M q [s l ] with s l ∈ Z l (s).

Let v l ∈ X l,n , λ l ∈ Π l and 0 ≤ k ≤ n -1. Let X k be the set of all removable k-nodes γ in λ l such that for every (k -1)-node β in ∂λ l , we have j(γ) > j(β). Here in the definition of i-nodes (i = k or k -1), the residues are taken with respect to the multi-charge v l .

Example 3.2 Take n = 4, l = 2, v l = (3, 1) and λ l = ((4, 2), (4, 1)). Then we have

X 0 = {(1, 4, 2)}, X 1 = ∅, X 2 = {(1, 4, 1)} and X 3 = ∅.

⋄

Jacon proved the following result.

Proposition 3.3 ([J1], Lemmas 4.2 & 4.3) Let v l ∈ X l,n and λ l = (λ (1) , . . . , λ (l) ) ∈ Π l (v l ) • , λ l = ∅ l . Let j max := max{λ (b) 1 | 1 ≤ b ≤ l} denote the largest part of λ l and for 0 ≤ k ≤ n-1, let X k be the set defined above. Then there exists k ∈ [[0; n -1]] such that X k ∩ {γ ∈ λ l | j(γ) = j max }
is nonempty. Moreover, the multi-partition obtained from λ l by removing all the nodes in X k (for k as above) is in Π l (v l )

• .

Thanks to this proposition, one can define recursively a Jacon element

F (λ l ) ∈ U q ( sl n ). Definition 3.4 Let v l ∈ X l,n and λ l ∈ Π l (v l ) • . If λ l is the empty multi-partition, let F (λ l ) := 1 ∈ U q ( sl n ). Otherwise, let k ∈ [[0; n-1]
] be the minimal integer given by Proposition 3.3 and let X k be corresponding set of removable k-nodes. Then

µ l := λ l \ X k is in Π l (v l )
• , so by induction, we can define (30)

F (λ l ) := f (♯X k ) k F (µ l ).
Note that F (λ l ) is a product of divided powers of the f k 's. ⋄ Example 3.5 Take n = 4, l = 2, v l = (3, 1) ∈ X l,n and λ l = ((4, 2), (4, 1)). One can check, e.g. by computing the crystal graph of M q [v l ], that λ l ∈ Π l (v l )

• . We have

F (λ l ) = f (1) 0 f (1) 2 f (1) 1 f (2) 3 f (2) 0 f (2) 2 f (1) 1 f (1)
3 .

⋄

Jacon proved the following result.

Theorem 3.6 ([J1], Prop. 4.6) Let v l ∈ X l,n and λ l ∈ Π l (v l ) • . Then F (λ l ).|∅ l , v l ∈ |λ l , v l + µ l ∈Π l a(µ l )>a(λ l ) Z[q, q -1 ] |µ l , v l ,
where a : Π l → Z denotes Lusztig's a-value [START_REF] Broué | Familles de caractères des algèbres de Hecke cyclotomiques[END_REF][START_REF] Jacon | On the parametrization of the simple modules for Ariki-Koike algebras at roots of unity[END_REF].

We do not use this a-value in the sequel, but only the unitriangularity property of this theorem, which implies the following.

Corollary 3.7 Let s l = (s 1 , . . . , s l ) ∈ Z l (s), and v l = (v 1 , . . . , v l ) be the unique element in X l,n such that

Λ v 1 + • • • + Λ v l = Λ s 1 + • • • + Λ s l . For λ l ∈ Π l (v l )
• , let F (λ l ) be the Jacon element associated to λ l and v l . Then

{F (λ l ).|∅ l , s l | λ l ∈ Π l (v l ) • } is a basis of M q [s l ]. Proof. Fix a weight w of M q [v l ]. Let B w := {F (λ l ).|∅ l , v l | λ l ∈ Π l (v l ; w)
• }. By Theorem 3.6, the transition matrix between the standard basis of M q [v l ] w and B w is unitriangular with respect to a certain ordering given by the a-value, which shows that B w is a basis of M q [v l ] w . This proves the corollary if s l = v l . Now, by definition of v l , there ex-

ists an isomorphism M q [v l ] ∼ -→ M q [s l ] of U ′ q ( sl n )-modules that maps u.|∅ l , v l on u.|∅ l , s l (u ∈ U ′ q ( sl n ))
. The result follows.

A basis of

H.|∅ l , s l (s l ∈ Z l (s))
Recall that the operators B m , m > 0 (resp. m < 0) pairwise commute. For any partition λ = (λ 1 , . . . , λ r ), put

B λ := B λ 1 • • • B λr ∈ End(Λ s ) (31)
(by convention, B ∅ is the identity operator), and define in a similar way B -λ .

Proposition 3.8 Let s l ∈ Z l (s). Then {B -λ .|∅ l , s l | λ ∈ Π} is a basis of H.|∅ l , s l .

Proof. Let Sym denote the Q(q)-vector space of symmetric functions and let {p λ | λ ∈ Π} be the basis formed by the power sums [Mac]. Let us recall the action of H on Sym. For k < 0 let b k denote the multiplication in Sym by p (-k) . For k > 0 and

f = f (p (1) , p (2) , . . .) ∈ Sym, put b k (f ) := γ k ∂f ∂p (k) , where γ k ∈ Z(H) ∼ = Q(q) is the scalar such that [B k , B -k ] = γ k .
One easily checks that there exists a homomorphism of algebras H → End(Sym) that maps B k on b k (k ∈ Z * ). This makes Sym into a simple H-module. Note that the vector v := |∅ l , s l ∈ F q [s l ] is a singular vector for the action of H, that is, v = 0 and B k .v = 0 for all k > 0. By a classical result (see e.g. [Kac, Lemma 9.13 a)]), the linear map: Sym → H.v, p λ → B -λ .v (λ ∈ Π), is an isomorphism of H-modules. Since {p λ | λ ∈ Π} is a basis of Sym, the result follows.

A -invariant basis B of Λ s

We need a lemma on bimodules, whose proof is left to the reader. Lemma 3.9 Let A be Q(q)-algebra with unity, and U := U ′ q ( sl n ) or U ′ p ( sl l ). Let V be an (A ⊗ U )-module such that the actions of A ∼ = (A ⊗ 1) and U ∼ = (1 ⊗ U ) commute. Assume that V is an integrable U -module and there exists a highest weight vector (for the action of U ), denoted by v 0 , such that V

= (A ⊗ U ).v 0 = A.U.v 0 . Let A • ⊂ A and U • ⊂ U be subsets 3.2 Computation of B ∩ F q [s l ] v (s l ∈ Z l (s), v ∈ P(F q [s l ]))
Let s l ∈ Z l (s) and v be a weight of F q [s l ]. Let B be the -invariant basis of Λ s given by Theorem 3.11. The goal of this section is to compute the list of vectors of B that lie in F q [s l ] v . Since the weights of the operators F (λ l ), B -µ and Ḟ (λ n ) from Theorem 3.11 are known, it is enough to determine whether the sum of these weights and the weight of |∅ l , r l is equal to v. This raises no theoretical problem but requires, in view of practical computations, to introduce some cumbersome notation.

Define a partial ordering on

P := n-1 i=0 ZΛ i ⊕ Zδ by writing w ′ ≤ w ′′ (w ′ , w ′′ ∈ P ) if w ′′ -w ′ ∈ n-1 i=0 Nα i .
Definition 3.13 We say that the weight w ∈ P is admissible (with respect to

F q [s l ] v ) if: (i) w is a weight of F q [s l ] such that v ≤ w. (ii) Let (r n , ẇ) ∈ Z n (s) × Ṗ(Λ s ) be the unique pair such that F q [s l ] w = F p [r n ] • ẇ (see Proposition 2.5).
We then require r n to be in A n,l (s). ⋄ Notation 3.14 Let w be an admissible weight with respect to F q [s l ] v . Then by Definition 3.13, there exist N 0 , . . .

, N n-1 ∈ N such that w -v = n-1 i=0 N i α i . Let N (w) := min i N i . The pair (r n , ẇ) ∈ A n,l (s) × Ṗ(Λ s ) such that F q [s l ] w = F p [r n ] • ẇ will be denoted by r n (w), ẇ(w) . Let r l (w) ∈ A l,n (s) be such that |∅ l , r l (w) = |∅ n , r n (w) • .
Recall the notation X l,n and X n,l from (29). Then there exists a unique v l (w) ∈ X l,n (resp.

v n (w) ∈ X n,l ) such that U ′ q ( sl n ).|∅ l , v l (w) is isomorphic to U ′ q ( sl n ).|∅ l , r l (w) (resp. U ′ p ( sl l ).|∅ n , v n (w) • is isomorphic to U ′ p ( sl l ).|∅ n , r n (w) • ). ⋄ Example 3.15 Take n = 3, l = 2, s l = (3, 6) and v = 2Λ 0 -4δ = wt(|∅ l , s l )-(α 0 +α 1 +α 2 ).
The following array gives the list of the admissible weights w with respect to F q [s l ] v and the corresponding N (w), ẇ(w), r n (w), v n (w), r l (w) and v l (w).

w N (w) ẇ(w) rn(w) vn(w) r l (w) v l (w) 2Λ0 -3δ 1 3 Λ1 -3 α1 (3, 3, 3) (1, 1, 1) (6, 3) (0, 0) (2Λ0 -3δ) -α0 0 2 Λ0 + Λ1 -( α0 + 3 α1) (4, 3, 2) (1, 0, 0) (5, 4) (2, 1) (2Λ0 -3δ) -(α0 + α1 + α2) 0 3 Λ1 -( α0 + 4 α1) (3, 3, 3) (1, 1, 1) (6, 3) (0, 0) ⋄ Proposition 3.16 Let s l ∈ Z l (s) and v be a weight of F q [s l ].
Let B be the -invariant basis of Λ s given by Theorem 3.11. Put B := B ∩ F q [s l ] v . Then with Notation 3.14, we have

B = w admissible F (λ l ) Ḟ (λ n )B -µ .|∅ l , r l (w) µ ∈ Π, |µ| ≤ N (w), λ n ∈ Π n (v n (w), l) • , ẇt Ḟ (λ n ).|∅ n , r n (w) • = ẇ(w), λ l ∈ Π l (v l (w), n) • , wt F (λ l ).|∅ l , r l (w) = w ′ (w, µ) ,
where we put w ′ (w, µ) := vw + |µ|δ + wt(|∅ l , r l (w) ).

Proof.

* Proof of inclusion ⊃. Let x := F (λ l ) Ḟ (λ n )B -µ .|∅ l , r l (w) with w admissible and λ l , µ and λ n as in the right hand-side of the statement of this proposition. We must show that x ∈ F q [s l ] v . Put y := Ḟ (λ n ).|∅ n , r n (w) • . Since wt F (λ l ).|∅ l , r l (w) = w ′ (w, µ) and the operator B -µ has weight -|µ|δ, we have

wt(x) = wt F (λ l ).|∅ l , r l (w) + wt(y) -wt |∅ n , r n (w) • -|µ|δ = w ′ (w, µ) + wt(y) -wt |∅ l , r l (w) -|µ|δ = v -w + wt(y).
By assumption, we have ẇt(y) = ẇ(w), whence y

∈ F p [r n (w)] • ẇ(w) = F q [s l ] w .
This implies wt(y) = w and wt(x) = v. Moreover, since the actions of U ′ q ( sl n ), U ′ p ( sl l ) and H pairwise commute, we have

x = F (λ l )B -µ .y ∈ U ′ p ( sl l ).H (F q [s l ] w ) ⊂ F q [s l ]. * Proof of inclusion ⊂. Let x ∈ B. With notation from Theorem 3.11, let r n ∈ A n,l (s), r l ∈ A l,n (s), λ l ∈ Π l (v l , n) • , µ ∈ Π and λ n ∈ Π n (v n , l) • be such that x = F (λ l )B -µ Ḟ (λ n ).|∅ n , r n • = F (λ l ) Ḟ (λ n )B -µ .|∅ l , r l .
Since x = 0, the vector y

:= Ḟ (λ n ).|∅ n , r n • = Ḟ (λ n ).|∅ l ,
r l is nonzero, so it is a weight vector of the U q ( sl n )-module Λ s . Let us now show that w := wt(y) is an admissible weight. Let t l ∈ Z l (s) be such that y ∈ F q [t l ]. Then we have

x = F (λ l )B -µ .y ∈ F q [t l ] w -|µ|δ -n-1
i=0 n i α i , where for 0 ≤ i ≤ n -1 we put n i := N i (λ l ; v l ; n). Moreover, since x ∈ F q [s l ] v and the spaces F q [a l ], a l ∈ Z l (s) are in direct sum, we must have t l = s l and

( * ) : v = w -|µ|δ - n-1 i=0 n i α i = w - n-1 i=0 (n i + |µ|) α i .
In particular, we have y ∈ F q [s l ] w and v ≤ w. By Proposition 2.5, there exists a unique pair (s n , ẇ)

∈ Z n (s) × Ṗ(Λ s ) such that F p [s n ] • ẇ = F q [s l ] w . We thus have y = Ḟ (λ n ).|∅ n , r n • ∈ F p [r n ] • ∩ F q [s l ] w = F p [r n ] • ∩ F p [s n ] • ẇ ⊂ F p [r n ] • ∩ F p [s n ] • . Since the F p [a n ] • , a n ∈ Z n (s) are in direct sum, we must have s n = r n ∈ A n,l (s)
. As a consequence, w is an admissible weight. One easily checks that ẇ = ẇ(w),

r n = r n (w), v n = v n (w), r l = r l (w) and v l = v l (w). By ( * ) we have w -v = n-1 i=0 N i α i with N i := n i + |µ| (0 ≤ i ≤ n -1). Since the n i 's are nonnegative integers, we must have |µ| = N i -n i ≤ N i for all 0 ≤ i ≤ n -1, whence |µ| ≤ min i (N i ) = N (w). Since y ∈ F q [s l ] w = F p [r n (w)] • ẇ(w) , we have ẇt Ḟ (λ n ).|∅ n , r n (w) • = ẇ(w). Finally, we have v = wt(x) = wt F (λ l ).|∅ l , r l (w) + wt(y) -wt |∅ n , r n (w) • -|µ|δ
and wt(y) = w, which implies wt F (λ l ).|∅ l , r l (w) = w ′ (w, µ).

Let us now explain how we can apply Proposition 3.16. Let w be an admissible weight with respect to F q [s l ] v . We compute the list of the multi-partitions λ n ∈ Π n (v n (w), l)

• such that ẇt Ḟ (λ n ).|∅ n , r n (w) • = ẇ(w) as follows. The proof of Proposition 3.16 shows that y

:= Ḟ (λ n ).|∅ n , r n (w) • ∈ F p [r n (w)] • ẇ(w) and y = 0, so ẇ(w) is a weight of F p [r n (w)] • . By (11), there exist N 0 , . . . , N l-1 ∈ N such that (32) ẇ(w) = ẇt(|∅ n , r n (w) • ) - l-1 i=0 N i αi .
Moreover, by definition of the Jacon elements and ( 11), the weight of

Ḟ (λ n ).|∅ n , r n (w) • with λ n ∈ Π n (v n (w), l) • is equal to ẇt(|∅ n , r n (w) • ) - l-1 i=0 N i (λ n ; v n (w); l) αi .
As a consequence, the multi-partitions λ n we are looking for are the vertices of the crystal graph of U p ( sl l ).|∅ n , v n (w) • that have exactly N i i-nodes for all 0 ≤ i ≤ l -1. In a similar way, we compute the list of the multi-partitions

λ l ∈ Π l (v l (w), n) • satisfying the condition wt F (λ l ).|∅ l , r l (w) = w ′ (w, µ) (µ ∈ Π, |µ| ≤ N (w)).
We now give an example for Proposition 3.16.

Example 3.17

Take n = 3, l = 2, s l = (3, 6) and v = 2Λ 0 -4δ = wt(|∅ l , s l )-(α 0 +α 1 +α 2 ).
We compute the basis B of F q [s l ] v given by Proposition 3.16. By Example 3.15, the admissible weights are 2Λ 0 -3δ, (2Λ 0 -3δ)α 0 and (2Λ 0 -3δ) -(α 0 + α 1 + α 2 ). * Contribution of w := 2Λ 0 -3δ. Example 3.15 gives ẇ(w) = ẇt(|∅ n , r n (w) • ) -3 α1 , v n (w) = (1, 1, 1), r l (w) = (6, 3) and v l (w) = (0, 0). By computing the first 4 layers of the crystal graph of U p ( sl l ).|∅ n , v n (w) • , we see that the only multi-partition λ n in Π n (v n (w), l)

• such that ẇt Ḟ (λ n ).|∅ n , r n (w) • = ẇ(w) is λ n := (1), ( 1), (1) . The corresponding Jacon element is Ḟ (λ n ) = ḟ (3) 1 . Moreover, since N (w) = 1, the only contributing partitions µ are µ = ∅ and µ = (1). Take µ = ∅. With notation from Proposition 3.16, we have

w ′ (w, µ) = wt(|∅ l , r l (w) ) -(α 0 + α 1 + α 2 ),
so we compute the first 3 layers of the crystal graph of U q ( sl n ).|∅ l , r l (w) . Doing this, we see that the only multi-partitions λ l ∈ Π l (v l (w), n)

• satisfying the condition wt F (λ l ).|∅ l , r l (w) = w ′ (w, µ) are ∅, (3) and ∅, (2, 1) . The corresponding Jacon elements are f 2 f 1 f 0 and f 1 f 2 f 0 . We therefore get 2 vectors of B, namely (6,3) .

v 1 := ḟ (3) 1 f 2 f 1 f 0 .|∅ l , (6, 3) and v 2 := ḟ (3) 1 f 1 f 2 f 0 .|∅ l ,
Taking w = 2Λ 0 -3δ, µ = (1) gives another vector of B: (6,3) .

v 3 := ḟ (3) 1 B -1 .|∅ l ,
* Contribution of the other admissible weights. In the same way, we get 3 other vectors of B: (5,4) and v 6 := ḟ (3) 1 ḟ0 ḟ1 .|∅ l , (6, 3) .

v 4 := ḟ (3) 1 ḟ0 f 2 f 1 .|∅ l , (5, 4) , v 5 := ḟ (3) 1 ḟ0 f 1 f 2 .|∅ l ,
By Proposition 3.16, we therefore have (5,4) , ḟ (3) 1 ḟ0 ḟ1 .|∅ l , (6, 3) .

B = {v 1 , . . . , v 6 } = ḟ (3) 1 f 2 f 1 f 0 .|∅ l , (6, 3) , ḟ (3) 1 f 1 f 2 f 0 .|∅ l , (6, 3) , ḟ (3) 1 B -1 .|∅ l , (6, 3) , ḟ (3) 1 ḟ0 f 2 f 1 .|∅ l , (5, 4) , ḟ (3) 1 ḟ0 f 1 f 2 .|∅ l ,

⋄

3.3 Action of the Heisenberg algebra H on the vectors |∅ l , s l (s l ∈ Z l (s))

In this section, we explain how to compute the action of H on the vectors |∅ l , s l (s l ∈ Z l (s)) without using the straightening relations. Using the action of U ′ p ( sl l ), we can restrict ourselves to the case where s l = (s 1 , . . . , s l ) is dominant, that is s 1 ≫ • • • ≫ s l (see Definition 3.21). By a theorem of Uglov (see Theorem 3.22), this case can in turn be reduced to the level-one case. When l = 1, Leclerc and Thibon [START_REF] Leclerc | Littlewood-Richardson coefficients and Kazhdan-Lusztig polynomials[END_REF] have given a combinatorial formula for the action of H, which avoids the straightening of q-wedge products in this case.

The case l = 1

We now recall the result of Leclerc and Thibon mentioned above. To this aim, we introduce the horizontal ribbon strips. Definition 3.18 ([LT2], §4.1) Let θ be a skew diagram. Denote by θ↓ the horizontal strip made of the bottom nodes of the columns of θ. We say that θ is a horizontal N -ribbon strip of weight k if it can be tiled by k ribbons of length N whose origins lie in θ↓. One can check that if such a tiling exists, it is unique. In this case, the spin of θ, denoted by spin(θ), is the sum of the heights of the ribbons in the tiling of θ. ⋄

Still following [START_REF] Leclerc | Littlewood-Richardson coefficients and Kazhdan-Lusztig polynomials[END_REF], we define operators of Λ s as follows. Let λ, µ ∈ Π and

N , m ∈ N * . If λ ⊂ µ and µ \ λ is a horizontal N -ribbon strip of weight m, put L (N ) λ,µ,m (q) := (-q) -spin(θ) . Otherwise, put L (N ) λ,µ,m (q) := 0. Now define U k , V k ∈ End(Λ s ) (k ∈ N * ) by (33) U k .|ν, s = µ∈Π L (n) µ,ν,k (q) |µ, s and V k .|ν, s = λ∈Π L (n) ν,λ,k (q) |λ, s (ν ∈ Π).
Before stating the result of Leclerc and Thibon, let us give some extra notation. Let λ ∈ Π.

Recall the notation B λ and B -λ from (31), and define in a similar way U λ , V λ ∈ End(Λ s ).

Let {h λ | λ ∈ Π} denote the set of complete symmetric functions and {p λ | λ ∈ Π} denote the set of power sums [Mac]. Either set is a basis of the space of symmetric functions. Let (α λ,µ ) λ,µ∈Π denote the transition matrix between both bases, namely the matrix defined by ( 34)

p µ = λ∈Π α λ,µ h λ (µ ∈ Π).
The entries α λ,µ can be computed recursively, e.g. using Newton formula (see [START_REF] Macdonald | Symmetric functions and Hall polynomials[END_REF](2.11)]):

(35) p (k) = kh (k) - k-1 i=1 p (i) h (k-i) (k ∈ N * ).
Theorem 3.19 ([LT2], Thm. 6.4) Assume that l = 1. Then with the notation above, we have

B k =        λ∈Π α λ,(k) U λ if k > 0, λ∈Π α λ,(|k|) V λ if k < 0.
Example 3.20 Take l = 1, n = 2, k = -2 and s ∈ Z. By Theorem 3.19 and ( 35), we have

B -2 = 2V 2 -V 2 1 . One computes V1.|∅, s = |(2), s -q -1 |(1, 1), s , V1.|(2), s = |(4), s + |(2, 2), s -q -1 |(2, 1, 1), s , V1.|(1, 1), s = |(3, 1), s -q -1 |(2, 2), s -q -1 |(1, 1, 1, 1), s , V 2 1 .|∅, s = |(4), s -q -1 |(3, 1), s + (1 + q -2 )|(2, 2), s -q -1 |(2, 1, 1), s + q -2 |(1, 1, 1, 1), s , V2.|∅, s = |(4), s -q -1 |(3, 1), s + q -2 |(2, 2), s , whence B -2 .|∅, s = |(4), s -q -1 |(3, 1), s + (-1 + q -2 )|(2, 2), s + q -1 |(2, 1, 1), s -q -2 |(1, 1, 1, 1), s ,
as one can check using the straightening relations. ⋄

The dominant case

We shall now see that by a result of [U] (see Theorem 3.22), it is possible to compute the action of B m (m ∈ Z * ) on certain vectors of the standard basis of Λ s by reducing to the case l = 1. In this case, we can apply subsequently Theorem 3.19 and therefore avoid using the straightening relations. Before stating Theorem 3.22, let us introduce the following definition and notation.

Definition 3.21 ([U]

) Let M ∈ N * , λ l ∈ Π l and s l = (s 1 , . . . , s l ) ∈ Z l . We say that the pair (λ l , s l ) is M -dominant if for all 1 ≤ i ≤ l -1, we have

s i -s i+1 ≥ M + |λ l |. ⋄ Recall that Λ s [n, 1
] denotes the space of q-wedge products of charge s in which we take l = 1. If x is an operator of Λ s [n, 1] that acts on the standard basis by (36) x.|λ, s

= µ∈Π x (s) λ,µ |µ, s λ ∈ Π, x (s) λ,µ ∈ Q(q) , define for b ∈ [[1; l]] an operator x[b] of Λ s [n, l] by (37) x[b].|λ l , s l = µ∈Π x (s b ) λ (b) ,µ (λ (1) , . . . , λ (b-1) , µ, λ (b+1) , . . . , λ (l) ), s l (λ l = (λ (1) , . . . , λ (l) ) ∈ Π l , s l = (s 1 , . . . , s l ) ∈ Z l (
B -2 .|∅ l , s l = B -2 [1].|∅ l , s l + q 2 B -2 [2].|∅ l , s l = |((4), ∅), s l -q -1 |((3, 1), ∅), s l + (-1 + q -2 )|((2, 2), ∅), s l +q -1 |((2, 1, 1), ∅), s l -q -2 |((1, 1, 1, 1), ∅), s l +q 2 |(∅, (4)), s l -q|(∅, (3, 1)), s l + (-q 2 + 1)|(∅, (2, 2)), s l +q|(∅, (2, 1, 1)), s l -|(∅, (1, 1, 1, 1)), s l ,
as one can check using the straightening relations. ⋄ of σ as follows. Since r > 0, we have s l / ∈ A l,n (s), so by ( 14) there exists i r ∈ [[0; l -1]] such that s ir < s ir+1 (here we put, as usual, s 0 := n + s l ). Let τ := σir σ. By [START_REF] Deodhar | On some geometric aspects of Bruhat orderings II[END_REF]Lemma 2.1 (iii)], we have ℓ( τ ) < ℓ( σ). By induction we get a reduced expression τ = σi r-1

• • • σi 1 of τ , so σ = σir • • • σi 1 is a reduced expression of σ. Now let r n ∈ A n,l (s) be such that |∅ n , r n • = |∅ l , r l . By Lemma 3.25, we have |∅ l , s l = | σir . . . σi 1 (∅ n ), r n • . Let k j := | σi j . . . σi 1 (∅ n )| -| σi j-1 . . . σi 1 (∅ n )| (1 ≤ j ≤ r).
By Proposition 2.9, we have

|∅ l , r l = |∅ n , r n • = ė(k 1 ) i 1 • • • ė(kr) ir .| σir . . . σi 1 (∅ n ), r n • = ė(k 1 ) i 1 • • • ė(kr) ir .|∅ l , s l ,
and the proof of the other equality is similar.

Example 3.27 Take s = 0, n = 2, l = 3, λ = (1) and s l = (1, -1, 0). We apply the method derived in this section for computing B -λ .|∅ l , s l . Note that s l is not n|λ|-dominant, so we cannot directly apply Theorem 3.22. The computation is done in four steps.

1. Following the proof of Lemma 3.24, put t l := (3, 1, -4). Then t l is n|λ|-dominant and Ẇl -conjugated to s l .

2. As in the proof of Proposition 3.26, we compute u ∈ U ′ p ( sl l ) such that |∅ l , s l = u.|∅ l , t l . The element in A l,n (s) that is Ẇl -conjugated to s l is r l := (1, 0, -1). The following array shows the computation of a reduced expression of σ, where σ ∈ Ẇl is the element of minimal length such that s l = σ.r l . Each line contains a multi-charge a l = (a 1 , . . . , a l ) and an integer i ∈ [[0; l -1]] such that a i < a i+1 (if it exists). The multi-charge on the next line is σi .a l .

(3, 1, -4) i = 0 (-2, 1, 1) i = 1 (1, -2, 1) i = 2 (1, 1, -2) i = 0 (0, 1, -1) i = 1 (1, 0, -1)

We get s l = σir • • • σi 1 .r l with r = 5 and (i r , . . . , i 1 ) = (0, 1, 2, 0, 1). The element r n ∈ A n,l (s) such that |∅ l , r l = |∅ n , r n • is r n := (1, -1). We compute recursively the n-multi-partitions λ (j)

n := σi j • • • σi 1 (∅ n ) (0 ≤ j ≤ r) from λ (0)
n = ∅ n . The proof of Proposition 3.26 shows that for 1 ≤ j ≤ r, k j is the number of addable i j -nodes of λ (j-1) n and λ (j) n is obtained from λ (j-1) n by adding these nodes. The computation of the integers k j (1 ≤ j ≤ r) is displayed in the following array.

Examples

In this section, we give some transition matrices of the canonical bases of some weight subspaces of higher-level Fock spaces. We first give, for k ∈ Z, the matrices ∆ k (q) = ∆ + λ l ,µ l ; s (k) l (q) λ l , µ l ∈Π l (s (k) l ; w (k) )

for n = l = 2, s ) -(2α 0 + 2α 1 ). These matrices should be read by columns, for example we have G + (3, 1), ∅ , (-2, 2) = (3, 1), ∅ , (-2, 2) + q (2, 2), ∅ , (-2, 2) + q 2 (2, 1, 1), ∅ , (-2, 2) .

Let N k denote the number of nonzero entries in ∆ k (q). Mark by a * the rows indexed by the multi-partitions in Π l (s (k) l , n)

• . As a consequence, the corresponding columns give the expression (in the standard basis) of the vectors of the lower global crystal basis of the irreducible U q ( sl n )-module M q [s (k) l ]. Using Uglov's algorithm, we were able to compute the matrices ∆ k (q) only for |k| ≤ 1, because otherwise the number of factors of the q-wedge products to be straightened was too large. With our algorithm we computed the matrices ∆ k (q) for |k| 20. The matrix ∆ 0 (q) was already published in [U]. Note that for a given k ≥ 1, the matrices ∆ k (q) and ∆ -k (q) are equal up to a permutation of the rows and the columns; if k ≥ 2, this is a special case of [START_REF] Yvonne | Canonical bases of higher-level q-deformed Fock spaces[END_REF]Prop. 5.5]. Moreover, note that for all k ≥ 1 (case of the dominant multi-charges), the matrices ∆ k (q) are equal (up to a permutation of the rows and the columns). This property was observed and proved (for k ≥ 6) in [START_REF] Yvonne | Canonical bases of higher-level q-deformed Fock spaces[END_REF]Thm 5.2]. This result supports in turn a conjecture for computing the q-decomposition matrices of some cyclotomic v-Schur algebras (see Section 1 and [Y1]). In this conjecture, the assumption of dominance is necessary. Indeed, note that in our example we have N k = N 0 for k = 0, which shows that ∆ k (1) (k = 0) cannot be obtained from ∆ 0 (1) by a mere permutation of rows and columns.

  module, denote by P(M ) the set of weights of M and let M w denote the subspace of M of weight w. Let (3) wt(x) := w denote the weight of x ∈ M w . The Weyl group of sl n (or

  s)) ; in other words, x[b] acts as x on the b-th component and trivially on the other components. Theorem 3.22 ([U], Prop 5.3) Let m ∈ Z * . Assume that (λ l , s l ) is n m-dominant, where m := max(0, -m). Then we have B m .|λ l , s l = l b=1 q (b-1)|m| B m [b].|λ l , s l . Example 3.23 Take n = 2, l = 2, m = -2, λ l = ∅ l and s l = (2, -2). By Theorem 3.22 and Example 3.20, we have

  , -2k) and w (k) = wt(|∅ l , s (k) l

Higher-level q-deformed Fock spacesIn this section, we recall briefly the definition of the higher-level Fock spaces and their canonical bases. These objects were introduced by[U], to which we refer the reader for more details. We follow here the notation from[Y2].

  1 . . . . . . . . . . . . . . . q 1 . . . . . . . . . . . . . . 0 q 1 . . . . . . .

Recall Notation 3.1 and the definition of the Jacon elements in U ′ q ( sl n ). In a similar way, define a Jacon element Ḟ (λ n ) ∈ U ′ p ( sl l ) for λ n ∈ Π l (v n , l)

• , v n ∈ X n,l .

Lemma 3.10 Keep the notation above. Let r l ∈ A l,n (s). By [U], there exists a unique r n ∈ A n,l (s) such that |∅ n , r n • = |∅ l , r l . Let v l be the unique multi-charge in X l,n such that U ′ q ( sl n ).|∅ l , v l ∼ = U ′ q ( sl n ).|∅ l , r l and let v n be the unique multi-charge in X n,l such that

is a basis of the vector space

Proof.

All the equalities come from the fact that the actions of U ′ q ( sl n ), U ′ p ( sl l ) and H pairwise commute. By Corollary 3.7 and Proposition 3.8,

r l , and

We now conclude with Lemma 3.9.

We are now ready to state the following:

Theorem 3.11 With notation of Lemma 3.10, the set

Proof. The fact that B is a basis of Λ s comes from Lemma 3.10 and Theorem 2.3. Let r l ∈ Z l (s). By (9), the subspace of F q [r l ] of weight wt(|∅ l , r l ) is one-dimensional. Therefore, by Proposition 2.10 (ii), the vector |∅ l , r l is -invariant. Proposition 2.10 (iv) then implies that every vector in B is -invariant.

Remark 3.12 The proof that B is a basis of Λ s does not use the involution . Since every vector in B is fixed by the involution , this determines this involution completely. ⋄

Let λ = (λ 1 , . . . , λ r ) ∈ Π and s l ∈ Z l (s). Recall that we put

We derive here a method for computing B -λ .|∅ l , s l without using the straightening relations. We proceed in four steps. The first two steps use some results that we prove in this section.

1. We find t l ∈ Ẇl .s l such that t l is n|λ|-dominant; see Lemma 3.24.

2. We find u ∈ U ′ p ( sl l ) (more precisely, u is a monomial in the Chevalley generators of

. Finally, we compute the action of u on B -λ .|∅ l , t l by using the indexation of the standard basis of Λ s by n-multi-partitions.

We now state and prove Lemma 3.24 and Proposition 3.26. We give an example of application at the end of this section.

Lemma 3.24 Let s l ∈ Z l (s) and M ∈ N * . Then there exists an nM -dominant multi-charge t l that is Ẇl -conjugated to s l .

Proof. Let λ := ((l -1)M, (l -2)M, . . . , M, -l(l -1)M/2) ∈ Z l and τ ∈ End(Q l ) be the translation by nλ. Since λ ∈ Z l (0), we have τ ∈ Ẇl . We can choose σ ∈ S l ⊂ Ẇl such that a l = (a 1 , . . . , a l ) := σ.s l satisfies a 1 ≥ a 2 ≥ . . . ≥ a l . Then t l := τ σ.s l is nM -dominant and Ẇl -conjugated to s l .

Recall the definition of σ

Then for all 1 ≤ j ≤ r, ẇt |λ

• , and we have

Proof.

We proceed by induction on r. If r = 0, the equality |λ

n , r n • and i := i r . By induction, we have u = |∅ l , t l . We must show that x = y and ẇ + αi is not a weight of F p [r n ] • . We claim that x and y lie in F p [r n ] • σi . ẇ . The claim for y follows by the definition of

• . Now we show easily that ẇt(x) = σi . ẇt(u) = ẇt(y), whence the claim for x. Put ẇ∅ := ẇt |∅ n , r n

• . By (11), the weight subspace

As a consequence, x and y are vectors of the standard basis of a one-dimensional subspace of Λ s , whence x = y.

Let us now show that ẇ + αi is not a weight of By (10), we have ( ẇt(x), αi ) = s is i+1 , where we put s 0 := s l + n if i = 0. We thus have φiεi = s is i+1 . Since ℓ( σ) = ℓ( τ ) + 1, a classical result about Coxeter groups (see e.g. [START_REF] Deodhar | On some geometric aspects of Bruhat orderings II[END_REF]Lemma 2.1 (iii)]) shows that s i+1 > s i (even if i = 0). As a consequence, εi > φi ≥ 0, therefore ẇt(x) + αi and σ-1 .( ẇt(x) + αi ) = ẇ∅ + σ-1 . αi are weights of F p [r n ] • . By (11), we have σ-1 . αi ∈ l-1 j=0 N αj and ẇ∅σ-1 . αi is not a weight of

The following result is a refinement of [START_REF] Uglov | Canonical bases of higher-level q-deformed Fock spaces and Kazhdan-Lusztig polynomials[END_REF]Cor. 4.9]. Proposition 3.26 Let r l ∈ A l,n (s) and s l = (s 1 , . . . , s l ) ∈ Ẇl .r l . Then there exist integers

Proof. Let σ ∈ Ẇl be the element of minimal length such that s l = (s 1 , . . . , s l ) = σ.r l . We argue by induction on the length r of σ. If r = 0, we have s l = r l and there is nothing to prove. Assume now that r > 0. We compute a reduced expression

((2, 2, 1, 1), (1, 1)) 0 5 5 ((3, 2, 2, 1, 1), (2, 1, 1)) By Proposition 3.26, we therefore have

In the same way we get

3. By Theorem 3.22, we have

)), t l -q|(∅, ∅, (1, 1)), t l .

4. We only have to apply u to get

as one can check using the straightening relations. ⋄

End of the algorithm

Let s l ∈ Z l (s) and w be a weight of F q [s l ]. By Sections 3.2 and 3.3, we get a basis B of F q [s l ] w that is -invariant. Let T (q) denote the transition matrix between the standard basis of F q [s l ] w and the basis B, and let A(q) denote the matrix of the involution of F q [s l ] w with respect to the standard basis. Since the basis B is -invariant, we have the following:

Lemma 3.28 With the notation above, we have A(q) = T (q) T (q -1 ) -1 .

Thus this lemma gives an algorithm for computing the involution of F q [s l ] w . Once this is known, the computation of the canonical bases can be performed in a classical way by solving unitriangular systems (see e.g. [START_REF] Leclerc | Symmetric functions and the Fock space, in Symmetric functions 2001: surveys of developments and perspectives[END_REF]Proof of Thm. 7.1]

0 q 2q 2 q 3 q 2 q q q 1 . . . . . . q 2 q q 2 q 3 q 4 q 3 + q q 2 0 q 2 q 1 . . . . . q 2 0 0 0 0 q 0 0 0 0 0 1 . . . . q 3 q 2 0 0 0 q 2 0 0 0 0 q q 1 . . . 0 q 3 q 2 0 0 0 0 0 0 q q 2 0 q 1 . . q 3 q 4 q 3 q 2 0 q 2 q 0 q q 2 q 3 q q 2 q 1 . q 4 0 0 q 3 0 q 3 q 2 q 2 q 2 q 0

q q q 3 q 2 q 0 q 1 . . . . . q 2 0 q 3 0 q 2 q 4 q 3 + q q 2 0 q 2 q 1 . . . . q 3 0 0 0 0 0 q 2 0 q 0 0 q 1 . . . 0 q 3 0 q 2 q 2 0 0 0 0 0 q 0 0 1 . . q 3 q 4 q 2 q 3 q 3 0 q 2 q q q q 2 0 0 q 1 . q 4 0 q 3 0 0 0 q 3 q 2 q 2 q 2 q q 2 q 0 q 1 . . . . . . q q 2 q 1 . . . . . . . . . . . . q 2 q 3 q 2 q 1 . . . . . . . . . . . q 0 0 0 q 1 . . . . . . . . . . q 2 0 0 q q 2 q 1 . . . . . . . . . q 2 0 0 q 0 0 0 1 . . . . . . . . q 2 0 0 q q 2 q 0 0 1 . . . . . . . q 3 0 q 2q 2 q 3 q 2 q q q 1 . . . . . . q 2 q q 2 q 3 q 4 q 3 + q q 2 0 q 2 q 1 . . . . . q 2 0 0 0 0 q 0 0 0 0 0 1 . . . . q 3 q 2 0 0 0 q 2 0 0 0 0 q q 1 . . . 0 q 3 q 2 0 0 0 0 0 0 q q 2 0 q 1 . . q 3 q 4 q 3 q 2 0 q 2 q 0 q q 2 q 3 q q 2 q 1 . q 4 0 0 q 3 0 q 3 q 2 q 2 q 2 q 0 q 2 0 0 q 1 (2, 2), ∅ (2, 1, 1), ∅ * (2, 1), (1)

(2), (2) (2), (1, 1) (1, 1, 1, 1), ∅ (1, 1), (2) (1, 1), (1, 1) (1), (2, 1) ∅, (4) ∅, (3, 1) ∅, (2, 2) ∅, (2, 1, 1) ∅, (1, 1, 1, 1)

,

We now give the matrix ∆(q) = ∆ + λ l ,µ l ; s l (q) λ l , µ l ∈Π l (s l ; w) for n = l = 2, s l = (0, 0) and w = wt(|∅ l , s l ) -(7α 0 + 4α 1 ). It would be very hard to compute it using Uglov's algorithm. Indeed, the partitions λ such that |λ, 0 ∈ F q [s l ] w all satisfy |λ| = 25, so applying Uglov's algorithm requires the straightening of q-wedge products with at least 25 factors. Moreover, since dim(F q [s l ] w ) = 28, the matrix ∆(q) here is too large to be displayed on a single page. We thus write it as

, where ∆ (1,1) (q), ∆ (2,1) (q) and ∆ (2,2) (q) are (14 × 14)-matrices.

q q 2 q 3 q 2 q 0 q 2 q 0 1 . . . q 3 q 2 q 3 0 q q 2 q 0 q 2 q q 1 . . 0 0 q 2 q 0 0 0 0 0 0 0 0 1 . 0 0 q 3 q 2 q 0 0 q q 2 q 0 0 q 1      q 2 0 q 2 q 3 + q q 2 q 0 q 2 0 0 0 0 q 2 q q 3 0 q 3 q 2 0 q 2 q 0 0 0 0 0 0 0 q 3 q 2 q 3 q 4 + q 2 q 3 + q q 2 0 q 3 q 2 q q 0 q 3 q 2 q 4 q 3 q 4 q 3 2q 2 q 3 q 2 q 2 q 3 q 2 q 2 q 0 q 0 0 q 2 q 3 q 2 q 0 0 0 q 2 0 0 q 4 q 3 0 0 q 3 0 0 q 2 q 0 0 0 0 0 0 0 q 2 0 q 4 q 3 q 2 q 3 + q q 2 0 0 0 0 0 0 0 q 3 0 0 q 4 q 3 q 2 0 q 3 0 0 0 0 0 q 2 q 4 0 0 0 0 q 3 q 2 0 0 0 0 0 0 0 0 0 q 3 q 4 q 3 q 2 0 q 3 q 2 q 3 q 0 q 5 q 4 q 3 q 2 0 q 4 q 3 q 2 0 0 0 0 q 0 0 0 q 4 q 3 q 4 q 5 q 4 + q 2 2q 3 q 2 q 4 q 3 q 2 2q 2 q 0 q 3 0 0 q 5 0 q 3 q 4 q 3 0 q 4 q 3 + q q 3 q 2 0 0 q 5 q 4 0 0 q 3 q 4 q 3 0 0 0 q 3 q 2 0 0   q q 0 q 2 q 1 . . . . . . . q 3 q 2 q 2 q 0 0 q 1 . . . . . . 0 q 0 0 0 q q 2 q 1 . . . . . q 3 0 q 2 0 q 0 0 0 0 1 . . . . q 3 q 2 q 2 0 0 0 q 0 0 0 1 . . . q 4 q 3 q 3 + q q 2 q 2 q q 2 q 0 q q 1 . . 0 0 q 2 0 q 3 q 2 0 0 0 q 2 0 q 1 . 0 q 2 q 2 q 0 q 2 q 3 q 2 q 0 q 2 q 0 1


Nicolas Briot
email: briot@lirmm.fr

Annie Chateau
email: chateau@lirmm.fr

Remi Coletta
email: coletta@lirmm.fr

Simon De Givry

Philippe Leleux

Thomas Schiex

Rémi Coletta

An integer linear programming approach for genome scaffolding

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

This paper presents an application of the constraint programming paradigm to a crucial problem in bioinformatics, namely the genome scaffolding problem. The genome scaffolding problem consists in determining a suitable order of the incompletely assembled genome parts, called contigs, provided by common assembly techniques to infer a genomic sequence from Next Generation Sequencing (NGS) data.

The initial formulation as a path-merging problem was proved NP-complete [START_REF] Huson | The greedy path-merging algorithm for contig scaffolding[END_REF]. A similar result was recently proven when the problem is simplified and modeled as an optimization problem in a particular graph called the scaffold graph [START_REF] Chateau | Complexity and Polynomial-Time Approximation Algorithms around the Scaffolding Problem[END_REF]. Although this problem has already been studied through a variety of computational techniques (see 3), the constraint programming approach together with this model is fully original. The main advantage of this approach is its flexibility, enabling the modeling of various aspects of the problem, by progressive extension towards several directions. Indeed, we may have to adapt to various forms of genomic sequences or data sources, and deal with complex issues like repeated contigs. In this paper, we set the first steps of an efficient tool that aims at performing scaffolding even on large genomes in a reasonable time on a usual computer. This approach is presented here as a proof of concept of the application of constraint programming to the scaffolding problem.

First, we describe the biological context and mathematical formalization of the problem in Section 2. We present the state of the art in Section 3. In Section 4, we detail the model and algorithms. In Section 5, we describe the chosen experimental settings, as well as the datasets. Finally, we examine the results in Section 6.

Genome scaffolding

When the genome of a new species is sequenced, the provided data consist in a huge amount (up to several billion for the longest genomes) of short sequences in which there is a variable fraction of so-called paired-end reads. Sequencing technologies [START_REF] Adams | DNA sequencing technologies[END_REF] may vary and produce several kind of paired-end reads, but the principle remains the same. A pair of reads is defined by the sequenced extremities of a given genomic fragment (see Figure 1). Pairs can be oriented outwards or inwards, depending on the technology, but the orientation and the rough fragment length are consistent within a given dataset. In the remaining of this paper, without loss of generality, we assume that all paired-end reads are innies (inward orientation). Notice that, since the genome is oriented by the physical structure of the DNA molecule, reads are also oriented.

Given the reads dataset, the assembly step builds the big puzzle using overlaps between the reads (for a review of usual methods, see [START_REF] Salzberg | GAGE: A critical evaluation of genome assemblies and assembly algorithms[END_REF]). However, due to local lack of coverage (some areas of the genome being harder to sequence than others) and repetitions, the puzzle cannot be completely solved and the assembly produces a set of sequences of various lengths, the contigs (see Figure 2). Once the contigs are produced, the next step is to order them and determine their orientation, to produce larger parts of the genome called scaffolds (see Figure 3). We also need to estimate the relative positions of the contigs inside the scaffolds (estimation of gap sizes between successive contigs). Usually, this is determined by the estimated fragment size between both reads in a pair, and the position of the reads on the contigs : the pairing information. The scaffolding problem is defined as follows: given a set of contigs C = {C 0 , . . . , C n-1 }, and a set of paired-end reads, we want to infer an order on the contigs, and the orientation of the contigs, that is the most consistent with the pairs. We assume that the reads have already been properly mapped to the contigs and we focus on pairs whose elements are mapped on distinct contigs. Given a fixed orientation of the contigs, there are four ways, called stories, in which a pair can map on two distinct contigs, depending on the reads orientations relatively to the contigs orientations (see Figure 4).

C1 C2 C1 C2 C1 C2 C1 C2 A B C D
Fig. 4. The four possible ways of linking two contigs for inward paired-end reads. In story A (resp. B), contigs C1 (resp. C2) precedes contig C2 (resp. C1) with their original orientations. In story C (resp. D), contig C1 (resp. C2), with its alternative orientation, precedes contig C2 (resp. C1) with its original orientation. Several pairs could tell the same stories (see Figure 5). In this case, we assume that we can bundle them and attribute a weight to the obtained story equal to the number of stories that have been bundled. The bundling process is similar to the one presented in [START_REF] Huson | The greedy path-merging algorithm for contig scaffolding[END_REF]. The data of the contigs and the weighted stories is called the scaffold graph. We denote by m the number of distinct stories, meaning the number of weighted edges in the scaffold graph. Since contigs are oriented sequences, they are represented by a pair of extremities linked by an intra-contig edge. The contig numbered k is represented by two vertices, namely 2k and 2k + 1. The example in Figure 5 has six vertices (k = 3) and three edges (0, 5), (1, 2), [START_REF] Adams | DNA sequencing technologies[END_REF][START_REF] Salzberg | GAGE: A critical evaluation of genome assemblies and assembly algorithms[END_REF] with weights 1, 3, 3 respectively (m = 3) and three intra-contig edges (0, 1), (2, 3), [START_REF] Salzberg | GAGE: A critical evaluation of genome assemblies and assembly algorithms[END_REF][START_REF] Dayarian | SOPRA: Scaffolding algorithm for paired reads via statistical optimization[END_REF].

The genomes can be composed of several chromosomes, linear or circular. We want to adopt a general model that allows to handle those different cases. In what follows, we model the problem such that a solution produces a subgraph of the scaffold graph, which has only linear or circular (paths or cycles) connected components, and maximizes the weight of the chosen stories (i.e. weighted edges of the scaffold graph).

In Figure 6 we can see a scaffold graph of size 30 (subgraph of the scaffold graph for the bacterial sequence of a Wolbachia endosymbiont), and the solution which is produced by the optimization process. Notice that, although the original sequence consists in one circular chromosome, there are several linear components, and a very small circular one. The linear components are good candidates to be parts of the circular chromosome, but the small cycle should not appear. In fact, it could be an artifact due to repeats in the sequence. Indeed, the corresponding contig appears several times in the complete genome. expectation-maximization process. They obtain results which are intermediary between SSPACE and Opera. In SCARPA [START_REF] Donmez | SCARPA: scaffolding reads with practical algorithms[END_REF], the two problems of orienting and ordering the contigs are separated, as in SOPRA. The orientation of the contigs is an FPT (Fixed Parameter Tractable) problem. Then, pre-oriented contigs are ordered using a heuristic, and the removal of articulation vertices is used to limit the size of the connected components. Misassembled contigs are detected and removed. The authors qualify their method as moderately slow, but using not so much memory.

In all these approaches, repeats are not handled, or in the best case, they are detected and removed.

Model and algorithms

Integer Linear Programming Model

We present here a simple integer linear programming (ILP) model of the problem. Since the weights on the inter-contig edges are integers, this model seems quite natural. The set of variables is just the set of stories, denoted by V = {x 1 , . . . , x m }. The domain of these variables is D = {0, 1}, where 0 means that the story is not chosen, and 1 that it is chosen.

The set of constraints C expresses the constraint on the maximal degree of the chosen subgraph, i.e. a set of paths and cycles. For each contig extremity, we impose that at most one outgoing story is chosen. We do not constrain the solution to be connected, because we want to avoid choosing an artificial path including stories of too low weight.

Finally, we maximize the objective function corresponding to the weight of the chosen subgraph:

m j=1 w j x j ,
where w j is the weight of the story x j .

In Figure 7, we present a scaffold graph for n = 7 contigs (14 vertices). The ILP model leads to the following set of constraints:

x 1 ≤ 1 x 8 ≤ 1 x 2 ≤ 1 x 8 + x 9 ≤ 1 x 3 ≤ 1 x 4 + x 7 ≤ 1 x 3 + x 4 + x 5 ≤ 1 x 9 + x 10 ≤ 1 x 1 + x 6 ≤ 1 x 10 ≤ 1 x 6 + x 7 ≤ 1 x 2 + x 5 ≤ 1 (1)
and the following objective function to maximize:

32x 1 + 2x 2 + 2x 3 + 28x 4 + 52x 5 + 20x 6 + 80x 7 +6x 8 + 34x 9 + 4x 10 . (2)
An optimal solution for this problem has an objective value of 198, selecting edges x 1 , x 5 , x 7 , x 9 (assigned to 1). The resulting scaffolding contains three scaffolds with contig orderings (C 1 ), (C 6 , C 2 , C 0 ), and (C 5 , C 4 , C 3 ). This model can be implemented using several types of solvers:

-Pseudo-boolean SAT solvers, e.g., SAT4J [START_REF] Berre | The Sat4j library, release 2.2[END_REF] ; -SAT solvers with cardinality constraint encoding [START_REF] Abío | A New Look at BDDs for Pseudo-Boolean Constraints[END_REF], possibly improved by [START_REF] Abío | A Parametric Approach for Smaller and Better Encodings of Cardinality Constraints[END_REF] ; -Max-SAT solvers using unary soft clauses encoding the objective function and hard clauses encoding cardinality (connectivity) constraints as in SAT ; -Integer Linear Programming (ILP) solvers such as the state-of-the-art branchand-bound solver IBM ILOG cplex.

Cycles removing

In our model, since we only use local constraints on the degree of each vertex, we allow solution with cycles. Except for a Hamiltonian cycle, which may correspond to a circular genome, we don't want those cycles. We also make the assumption that these cycles are generated by repeats in the genome. If two contigs a and b form a tandem repeat in the genome, meaning that they appear several times in the genome consecutively in that order, for instance ababab, then the stories "a is followed by b" and "b is followed by a" have biased weights compared to stories which are not duplicated. Thus, the cycle aba may be chosen instead of the sequence ab included in a longer sequence. Our cycle removing step is then also a potential repeats removing step. More work is needed to fully investigate the relation between the cycles that appear in our optimization process and repeats. In this paper, we focus on solving time, in order to be able to tackle large instances.

Several encoding have been proposed to enforce the no-subcycle constraint in CSP, but such a constraint is less easy to express in an ILP context. Thus we decided to address it by a SAT Modulo Theory inspired scheme: we solve the ILP problem with a solver and integrate this resolution in an incremental process, where cycles that may have been produced by the solver are forbidden in the next iteration.

Experiments

We present in this section the chosen dataset to explore the efficiency and accuracy of our method. We describe the experimental results in a more complete way than just comparing NG50 scores and computation times. We recall that the NG50 measures the scaffold length such that using longer or equal length scaffolds produces 50% of the bases of the reference genome. The results show that the NG50 is not enough to assess the quality of a scaffolder, and we give other metrics such as corrected NG50 (NGA50) and misassemblies statistics. In what follows, we refer to our method as scaftools.

Dataset

We performed the experiments on the following dataset, composed of four bacterial genomes and two eukaryotic genomes:

-Staphylococcus Aureus (alias staphylo), NC 010079 (Staphylococcus aureus subsp. aureus USA300 TCH1516, complete genome) -Escherichia Coli (alias ecoli), U00096.2 (Escherichia coli K-12 MG1655, complete genome) -Yersinia Pestis CO92 strain (alias ypco92), NC 003143.1 (Yersinia pestis CO92 chromosome) -Wolbachia endosymbiont (alias wolbachia), NC 010981.1 (Wolbachia endosymbiont of Culex quinquefasciatus Pel chromosome, complete genome) -Homo Sapiens chromosome Y (alias chrY), human g1k v37 GRCh37.

-Arabidopsis Thaliana (alias arabido), accession TAIR10.

The read datasets have several origins:

-Real sequencing dataset for:

• Staphylococcus Aureus, short jump library7 (from the GAGE dataset [START_REF] Salzberg | GAGE: A critical evaluation of genome assemblies and assembly algorithms[END_REF])

• Escherichia Coli, Illumina reads library SRR001665

• Arabidopsis Thaliana, Illumina reads library SRR616966 -Simulated datasets for:

• Wolbachia, simulated with toyseq, a specific tool developed for the Variathon experiment8 [14]. This dataset presents a minor variant frequency of 20%. • Yersinia Pestis and the human chromosome Y, simulated with wgsim, a classical read simulator9 [START_REF] Li | The sequence alignment/map format and SAMtools[END_REF].

For the read assembly step required to produce the contigs, it has been performed using two different tools (both being de Bruijn graph based):

-Staphylococcus Aureus, Escherichia Coli, and Arabidopsis Thaliana were assembled with velvet [16] -Wolbachia, Yersinia Pestis and the human chromosome Y were assembled with minia [START_REF] Chikhi | Space-efficient and exact de Bruijn graph representation based on a Bloom filter[END_REF] The mapping of the reads on the contigs was performed using bowtie [START_REF] Langmead | Ultrafast and memory-efficient alignment of short DNA sequences to the human genome[END_REF] for Escherichia Coli and Arabidopsis Thaliana, and bwa [START_REF] Li | Fast and accurate long-read alignment with Burrows-Wheeler transform[END_REF] for the other datasets. Notice that, according to [START_REF] Hunt | A comprehensive evaluation of assembly scaffolding tools[END_REF], these mapping tools are among the best ones from the point of view of building scaffolds.

Table 1 provides additional information on the genomes, reads and contigs. Table 2 presents information about the scaffold graphs used as input for scaftools. In series of four figures for the number of stories and total stories weight, the first one represents the figure without any filtering, and the other ones when the stories of weight less than 3, 6 and 10 are respectively filtered. Despite the fact that this filtering may seem drastic concerning the number of stories, it does not change the total weight so much, indicating that the data contain a lot of low supported stories.

Evaluation

We choose to evaluate our method on several criteria. Since one of our goals is to offer a very efficient and quick tool, a major criterion is the computation time. scaftools was run on a usual laptop (Intel i3-2348M with 2 cores at 2.3 GHz and 5.6 GB of RAM), and memory consumption was never a problem. The other scaffolding tools were run on servers of the Genotoul cluster (48 cores AMD Operon 6176 at 2.3 GHz with 128 GB of RAM).

The other criteria concern the quality of the produced scaffolds and are offered by the QUAST tool 10 [21]. QUAST is originally targeted at assessing assembly quality, but can also be applied for scaffold evaluation. It performs local alignment and rearrangement analysis on the produced scaffolds.

The filling of the gaps for the scaftools method was arbitrary set to 50bp, since it does not yet estimate the size of gaps. Preliminary experiments have shown that this length has not a strong influence on the quality of the results.

The scaffolding of the genomes were performed with respectively:

-SSPACE [7] -SOPRA [5] -OPERA [6]
scaftools scaftools + filtering out the stories of weight < 3 scaftools + filtering out the stories of weight < 6 scaftools + filtering out the stories of weight < 10

Results

In this section, we present the results obtained on the different datasets.

Computation time

The computation times presented on Table 4 show that scaftools is faster than the other methods. The rare exceptions are due to the output writing time, for large genomes, as shown on Table 4, which presents the detailed computation time for each step of the scaftools process. Table 6 shows that the cycle breaking process presents few iterations, even for large genomes. Thus, the iterative strategy is not expensive and we do not have to fear long collapsing time. Concerning the RAM requirements, memory usage was never a problem during the experiments on a usual laptop. We recall the memory requirements of the other scaffolders on Table 7.

Quality of the scaffolding

QUAST provides a variety of measures to estimate the quality of a set of sequences (usually contigs, here scaffolds) relatively to a reference genome. Table 8 presents some of these measures and Figure 8 shows a visualization of the Opera and Scaftools scaffolds for the staphylo dataset. The NGA50 is the NG50 where the lengths of aligned blocks are counted instead of scaffold lengths. i.e., if a scaffold has a misassembly with respect to the reference, the scaffold is broken into smaller pieces. Opera and scaftools show larger statistics because they are more aggregative, but it does not mean that this aggregation is always better.

Results on other genomes are similar, detailed results can be found at http: //www.lirmm.fr/ ~chateau/scaftools/v_0_1/results/.

As could be expected, the blunt scaftools method without filtering leads to more errors than the classical methods, but this is improved by filtering the low supported stories. Notice that the results are then comparable to those provided by other scaffolders. 8. QUAST scaffolding analysis for the staphylo dataset. We display here 7 different statistics for the assemblies. #scaffolds: the number of scaffolds in the assembly. Assembly length: total length of the assembled scaffolds in base pairs. NG50: scaffold length such that using longer or equal length scaffolds produces half (50%) of the bases of the reference genome. NGA50: NG50 where the lengths of aligned blocks are counted instead of scaffold lengths, i.e. if a scaffold has some misassemblies with respect to the reference, the scaffold is broken into smaller pieces. # misassemblies: number of positions in the assembled scaffolds where (1) two contigs should be adjacent but are separated by over 1kbp or overlap on more than 1 kbp: relocation or (2) two contigs appear on different strands: inversion or (3) they appear on different chromosomes: translocation. Notice that, for all scaffolders and genomes included, most misassemblies were relocations. # local misassemblies: number of relocations where two contigs should be adjacent but are separated by over 1kbp or overlap on more than 1 kbp. # predicted genes (unique): number of unique genes in the assembly identified by GeneMark.hmm.

We developed and analyzed an efficient method for scaffolding, which defines a proof of concept with encouraging results when compared to other methods. There are still a a variety of possible improvements that need to be explored in future work. For instance, we aim at integrating the distances between contigs in the scaffolding process. This information can be extracted from the mapping results, based on the mean insert size. This may lead to an improvement of the quality of the stories, since we will be able to put aside pairs of reads showing inconsistent distance information. We also could improve the model by accounting for possible multiplicities of the contigs (repeats), either by inferring those multiplicities using the mapping profile, or by deeply investigating the connexion between artefactual small cycles and repeated contigs. There are multiple ways to integrate this information in our model and it is still unclear which approach is the most favorable. Finally, the computation time can still be further improved, by exploiting, for example, incremental resolution of the ILP problems instead of iterated solving 11 .

Fig. 1 .

 1 Fig. 1. A fragment and its corresponding sequenced paired-end reads. Orientation can be outwards (left) or inwards (right).

Fig. 2 .

 2 Fig.2. Contigs (below) are built using the overlaps between reads (above).

Fig. 3 .

 3 Fig. 3. Contigs (segments) are oriented and ordered into scaffolds (boxes) along the genome (above).

Fig. 5 .

 5 Fig. 5. Three contigs and their linking pairs of reads.

Fig. 6 .

 6 Fig. 6. Left: a (partial) scaffold graph. Contigs edges are not weighted, stories edges are weighted. Right: the solution of the corresponding scaffolding problem.

Fig. 7 .

 7 Fig. 7. A scaffold graph for k = 7 contigs.

Fig. 8 .

 8 Fig. 8. Visualization of the S. Aureus assembly with Opera (left) and Scaftools 10 (right) respectively on y-axis versus the reference genome on x-axis. Each horizontal dotted line separates two different scaffolds.

Table 1 .

 1 Genome Ref. genome size Read length Number of pairs Insert size Number of contigs Statistics on the datasets.

	staphylo	2903081 bp	102	833596	3500	301
	ecoli	4639675 bp	36	20816448	200	866
	ypco92	4653728 bp	70	2000000	500	4983
	wolbachia	1482455 bp	100	703838	300	280
	chrY	59373566 bp	71	16600000	500	24560
	arabido 119667750 bp	100	49703592	500	172616
	Genome Number of vertices	Number of stories		Total stories weight
	staphylo	602	4464/1442/716/489	72729/68875/66213/64602
	ecoli	1732	7276/3177/2239/1829	303161/298351/294808/291911
	ypco92	2656	2137/1521/1323/1197	69340/68592/67823/66918
	wolbachia	560	756/243/179/119	12234/5013/4412/3851
	chrY	49120	52169/31831/26940/23357 1268481/1242982/1224513/1198088
	arabido	345232	146368/80146/57717/42478 1901142/1819557/1733228/1622083

Table 2 .

 2 The scaffold graphs.

Table 3 .

 3 Computation time comparison.

			Server			Laptop
	Dataset	Opera	SSPACE	SOPRA	Scaftools Scaftools 3 Scaftools 6 Scaftools 10
	S. Aureus	33s	16s	1min40s	1s	<1s	<1s		<1s
	E. Coli	3h28min16s 16min4s	39min48s		<1s	7s		8s
	Y. Pestis	39s	44s	6min26s	6s	6s	4s		3s
	Wolbachia	13s	7s	3s	<1s	<1s	<1s		<1s
	Chr. Y	4min27	3min45s	10min54s	7min36s	NA	6min52s	6min4s
	A. Thaliana 22h11min13s 3h25min42s 31h3min24s 8h13min43s 5h24min25s 6h3min9s 4h22min57s
	Dataset		Detailed computation time				Total
	Phase	cplex1 CR 1 cplex2 CR 2			output		Total
	S. Aureus 0.12s 0.0037s 0.14s 0.0029s			0.1016s 0.3682s
	E. Coli	0.48s 0.0610s 0.08s 0.0037s			0.1375s 0.7622s
	Y. Pestis 0.10s 0.17s 0.11s 0.17s			52s		52.55s
	Wolbachia 0.06s 0.0042s 0.08s 0.0037s			0.1374s 0.2853s
	Chr. Y	2.69s 42.06s 4.94s 42.80s cplex3 CR 3 cplex4 CR 4	193s	285.49s
	A. Thaliana 3.85s 619.44s 5.00s 596.299s 5.03 608.655s 5.28 602.322 2878.51s 5324.386s

Table 4 .

 4 Detailed computation times for scaftools. CR means "Cycle Removal". The output time does not include the generation of the fasta file.

Table 5 .

 5 Time to generate the scaffold graph from the SAM file.

	Dataset Graph generation time (s) SAM file size (Mo)
	S. Aureus	5.052	272.1
	E. Coli	140.580	4734
	Y. Pestis	13.140	632.4
	Wolbachia	4.720	261.8
	Chr. Y	97.984	4360
	A. Thaliana	304.980	15463.1
	Dataset Number of iterations Number of cycles
	S.	2	3
	E. Coli	2	3
	Y. Pestis	2	1
	Wolbachia	2	6
	Chr. Y	2	3
	A. Thaliana	4	60 -7 -2

Table 6 .

 6 Number of iterations and cycles

	Dataset	Opera SSPACE Sopra
	S. Aureus 336M	496M 1.150G
	E. Coli 10.745G 1.453G 16.878G
	Y. Pestis	345M	462M	685M
	Wolbachia 251M	448M	230M
	Chr. Y	262M	512M 1.718G
	A. Thaliana 15.167G 9.355G 25.169G

Table 7 .

 7 Memory usage for Opera, SSPACE, and Sopra.

Previous work on scaffoldingContig scaffolding is an NP-complete problem, whose solutions can be approximated by a greedy approach. The first greedy approach in[START_REF] Huson | The greedy path-merging algorithm for contig scaffolding[END_REF] is dedicated to genomic fragments (BAC 5 ) combined with mate-pairs, which differ from the paired-end reads essentially by their larger insert-size 6 , and their lower covering depth, so the size of the data and the organization of the graph may differ from actual NGS data coupled with paired-end reads data. In SOPRA[START_REF] Dayarian | SOPRA: Scaffolding algorithm for paired reads via statistical optimization[END_REF], the authors introduce a removal procedure for problematic contigs, together with a simulated annealing technique, to perform the scaffolding. Time performances are not really detailed. In OPERA[START_REF] Gao | Opera: Reconstructing Optimal Genomic Scaffolds with High-Throughput Paired-End Sequences[END_REF], a graph contraction procedure approach is used to limit the size of the input, allowing the use of an exact dynamic programming approach. It is shown that the exact method gives better scaffold quality than existing heuristics. In SSPACE[START_REF] Boetzer | Scaffolding pre-assembled contigs using SSPACE[END_REF], they use a nearly greedy approach, by combining iteratively the longest contigs. In GRASS[START_REF] Gritsenko | GRASS: a generic algorithm for scaffolding next-generation sequencing assemblies[END_REF], a genetic algorithm is provided, using mixed integer programming (MIP) as in[START_REF] Salmela | Fast scaffolding with small independent mixed integer programs[END_REF] and an[START_REF] Dayarian | SOPRA: Scaffolding algorithm for paired reads via statistical optimization[END_REF] Bacterial Artificial Chromosome[START_REF] Gao | Opera: Reconstructing Optimal Genomic Scaffolds with High-Throughput Paired-End Sequences[END_REF] The insert size is the size, in base pairs, between the two fragments constituting a pair of reads

http://gage.cbcb.umd.edu/

http://bioinf.dimi.uniud.it/variathon

https://github.com/lh3/wgsim

bioinf.spbau.ru/quast

Acknowledgements

This work was partially funded by the Institut de Biologie Computationnelle. Thanks to Laurent Lemarchand, for his"last minute' interesting discussion on CPLEX. We also thank in Toulouse Christophe Klopp for introducing the scaffolding problem to us and Matthias Zytnicki for his help on collecting the datasets.