Cássio F Dantas
email: cassio.fraga-dantas@inria.fr

Jérémy E Cohen
email: jeremy.cohen@umons.ac.be

Rémi Gribonval

Learning fast dictionaries for sparse representations using low-rank tensor decompositions

Keywords: Kronecker product, tensor data, dictionary learning

A new dictionary learning model is introduced where the dictionary matrix is constrained as a sum of R Kronecker products of K terms. It offers a more compact representation and requires fewer training data than the general dictionary learning model, while generalizing Tucker dictionary learning. The proposed Higher Order Sum of Kroneckers model can be computed by merging dictionary learning approaches with the tensor Canonic Polyadic Decomposition. Experiments on image denoising illustrate the advantages of the proposed approach.

Introduction

Multi-dimensional data arise in a large variety of applications such as telecommunications, biomedical sciences, image and video processing to name a few [START_REF] Kolda | Tensor decompositions and applications[END_REF].

Explicitly accounting for this tensorial structure of the data can be more advantageous than relying on its vectorized version and losing the original neighboring relations, besides providing more efficient and economic representation and subsequent processing. The Kronecker product structure arises naturally when dealing with multi-dimensional (tensorial) data, since it manages to recover the underlying tensorial nature of vectorized data samples. Indeed, when applied to a vectorized tensor, each composing factor of a Kronecker-structured linear operator acts independently on each mode of the data. Conveniently, such operators are more compact to store and can be applied much more efficiently than their unstructured counterpart.

Nevertheless, relatively little attention has been paid to exploiting this type of structure on representation learning methods such as dictionary learning algorithms, which aim at obtaining a set of explanatory variables (the dictionary) capable of sparsely approximating an input dataset. Conventional methods impose no particular structure to the dictionary matrix learned from the vectorized input samples, therefore completely disregarding a potential multi-dimensional characteristic of the data.

In this paper, we provide a novel method to induce a generalized version of the Kronecker structure on the dictionary (namely, a sum of Kronecker products). To this end, we draw a parallel between the problem of approximating an arbitrary linear operator by a Kronecker-structured one and the low-rank tensor approximation problem.

The learned dictionary is constrained to the following structure:

D = R r=1 D r 1 ⊗ • • • ⊗ D r K = R r=1 K k=1 D r k ;
which we refer to as a rank-R K-Kronecker-structured matrix (or simply (R, K)-KS and even K-KS when R = 1). In [START_REF] Tsiligkaridis | Covariance estimation in high dimensions via kronecker product expansions[END_REF] R is referred to as the separation rank.

As we will see in Section 1.1, this structure may lead to significant memory and computational savings when compared to an unstructured matrix. At the same time, because we allow sums of several Kronecker terms, we make the structure more flexible thus increasing its approximation capabilities with respect to the conventional Tucker dictionary model [START_REF] Caiafa | Multidimensional compressed sensing and their applications[END_REF].

Motivations

The quest for Kronecker-structured linear operators has various motivations besides the suitability to multi-dimensional signals: 1) reduced computational complexity; 2) diminished memory requirements and 3) smaller sample complexity on learning applications. The complexity savings on matrix-vector multiplications are explained as follows. For an

(n × m) K-KS matrix D = D K ⊗ • • • ⊗ D 1 with factors D k ∈ R n k ×m k , n = K k=1
n k and m = K k=1 m k , the matrix-vector product Dx can be rewritten as

y = (D K ⊗ • • • ⊗ D 1 )x → Y = X × 1 D 1 × 2 • • • × K D K (1)
where Y ∈ R ×mK are the tensorized versions of y ∈ R n1...nK and x ∈ R m1...mK respectively [START_REF] Kolda | Tensor decompositions and applications[END_REF] and × k denotes the mode-k tensor matrix product. In other words, it comes down to multiplying each factor by the corresponding mode on the tensorized version X of the vector x.

Since the composing factors D k are much smaller than D, the total complexity for computing (1) can be significantly smaller than the usual O(nm). In particular, when the factors are all square (i.e. n k = m k ∀k) the total number of operations is given by ( 2 operations for an unstructured matrix of the same size. For a sum of R Kronecker products, the mentioned complexity is simply multiplied by R.

K k=1 n k )( K k=1 n k ) [16] compared to ( K k=1 n k )
In addition, the total storage cost for the structured operator is proportional to (

K k=1 n k m k ) instead of ( K k=1 n k m k ).
Similarly, recent studies [START_REF] Shakeri | Sample complexity bounds for dictionary learning of tensor data[END_REF] on the minimax risk for the dictionary identifiability problem showed that the necessary number of samples for reliable reconstruction, up to a given mean squared error, of a KS dictionary within its local neighborhood scales with (m

K k=1 n k m k ) compared to (m K k=1 n k m k )
for unstructured dictionaries of the same size [START_REF] Jung | On the minimax risk of dictionary learning[END_REF].

Related Work

The Kronecker structure was introduced in the Dictionary Learning domain by [START_REF] Hawe | Separable dictionary learning[END_REF][START_REF] Roemer | Tensor-based algorithms for learning multidimensional separable dictionaries[END_REF] both addressing only 2-dimensional data (i.e. 2-KS dictionaries). The model was extended to the 3rd-order (3-KS dictionaries) [START_REF] Peng | Decomposable nonlocal tensor dictionary learning for multispectral image denoising[END_REF][START_REF] Zubair | Tensor dictionary learning with sparse tucker decomposition[END_REF] and even for an arbitrary tensor order [START_REF] Caiafa | Multidimensional compressed sensing and their applications[END_REF][START_REF] Ghassemi | STARK: Structured Dictionary Learning Through Rank-one Tensor Recovery[END_REF] based on the Tucker decomposition, a model coined as Tucker Dictionary Learning. However, none of these works include a sum of Kronecker terms. Even though the formulation in [START_REF] Ghassemi | STARK: Structured Dictionary Learning Through Rank-one Tensor Recovery[END_REF] would allow it, they restrict their analysis to the rank-one (R = 1) case.

The sum of Kronecker products model was initially explored in the covariance estimation community [START_REF] Bijma | The spatiotemporal meg covariance matrix modeled as a sum of kronecker products[END_REF][START_REF] Tsiligkaridis | Covariance estimation in high dimensions via kronecker product expansions[END_REF] and was recently used in [START_REF] Dantas | Learning dictionaries as a sum of kronecker products[END_REF] as an extension of the existing Kronecker-structured dictionaries. But once again, these works addressed only the 2nd-order case (K = 2). We now extend [START_REF] Dantas | Learning dictionaries as a sum of kronecker products[END_REF] for an arbitrary tensor order, thus allowing for both R ≥ 1 and K ≥ 2. An advantage of our approach w.r.t [START_REF] Dantas | Learning dictionaries as a sum of kronecker products[END_REF] and [START_REF] Ghassemi | STARK: Structured Dictionary Learning Through Rank-one Tensor Recovery[END_REF] is that here we can choose the desired number of summing terms beforehand without needing to empirically adjust a regularization parameter.

Finally, similarly to what is introduced in this manuscript, Bastelier et. al. have recently discussed factorizations strategies for (R,K)-KS matrices, but with the goal of preserving the data structure and thus resorting to orthogonality constraints [START_REF] Batselier | A constructive arbitrary-degree kronecker product decomposition of tensors[END_REF].

Notation

Throughout this document, we denote ⊗ the Kronecker Product and • the outer product. Matrices (resp. tensors) are represented by bold uppercase (resp. underscored) letters and the (i, j)th entry of a matrix D is denoted d(i, j). The vectorization operation, denoted vec(•), consists in stacking the columns of a matrix and unvec(•) stands for the converse operation.

A Dictionary Learning Algorithm for Tensorial Data

(R,K)-KS dictionary learning model

Given a training data set in a tensor format Y, a naive approach to learn a dictionary from Y is to rearrange its entries into a matrix and apply a workhorse two-way dictionary learning algorithm. However, such a matricization of Y erases mode-wise information, such as the 2D structure of images or color information.

In [START_REF] Dantas | Learning dictionaries as a sum of kronecker products[END_REF], we have derived a dictionary learning algorithm for dictionaries as sums of 2-Kronecker products, which account for the two-way structure of the original training data. We now wish to extend this approach to tensors Y of any order. For this, we constrain the learned dictionary to be (R, K)-Kronecker-structured.

The dictionary learning model may be computed by solving the following minimization problem:

min D∈C R K , X 1 2 Y -DX 2 F + g(X) (2)
where C R K denotes the set of all (R, K)-KS matrices of size (n × m) and the training data, arranged as the columns of the matrix Y ∈ R n×N , is to be approximated as the product between the dictionary D ∈ R n×m and the sparse representation matrix X ∈ R m×N . The sparsity of the columns of X is enforced by the penalty function g (classical examples are the ℓ 0 and ℓ 1 norms). We also impose the columns of the dictionary to have unit ℓ 2 -norm.

Provided that the rank can be set to arbitrarily large values, any linear operator D may actually be written as a (R,K)-KS matrix [START_REF] Tsiligkaridis | Covariance estimation in high dimensions via kronecker product expansions[END_REF]. On the other hand, a K-KS matrix has a very specific structure that may not be appropriate for learning a good dictionary in a generic scenario. Therefore, for small rank values, the proposed approach may be understood as a trade-off between precision and complexity, storage and robustness to small training sets.

Dictionary Learning Algorithm

Following the literature, we employ a sub-optimal alternating minimization strategy to tackle problem [START_REF] Batselier | A constructive arbitrary-degree kronecker product decomposition of tensors[END_REF]. Since the problem is not jointly convex, there are no optimality guarantees for this classical approach. At each step, respectively dictionary update and sparse coding, we optimize with respect to one variable, resp. D and X, while fixing the other. The procedure is repeated N it times.

The sparse coding step can be performed by any existing sparse regression algorithm. In our experiments we use the OMP [START_REF] Pati | Orthogonal matching pursuit: recursive function approximation with applications to wavelet decomposition[END_REF] algorithm.

The difficulty in computing (2) lies in the (R,K)-KS structure imposed on D. In fact, in Sections 3 and 4, we show that this constraint is equivalent to imposing a Canonical Polyadic Decomposition model on a rearranged tensor R K (D) obtained from dictionary D. Therefore, for the dictionary update step, we propose a projected gradient algorithm, where the projection onto the set of C R K (set of matrices written as a sum of R K-Kronecker products) is approximated by the CPD algorithm applied to the rearranged tensor R K (D) as shown in Algorithm 1. The projection step is detailed in Section 4.

Algorithm 1 D = DictionaryUpdate(Y, X, R, n, m) 1: Initialize D0, t = 0 2: while Dt+1 -Dt F > tol do 3: Dt+1 = Dt -γt(DtX-Y)X T ⊲ Gradient step 4: Dt+1 = HO-SuKroApprox(Dt+1, R, n, m) ⊲ Projection into C R K 5: Normalize columns of D
The step-size γ t is determined with a backtracking line search. For acceleration purposes, the CPD can be initialized with the results of the previous iteration. Finally, note that the column normalization (line 5) can break the imposed structure. This is not a real concern, since the normalization coefficients can be stored separately, implying only m additional products in a matrix-vector operation. Put differently, it is equivalent to storing a dictionary in the form DΣ where Σ is a diagonal matrix containing the inverse norm of each column of D.

3 Rearrangement: transforming a K-Kroneckerstructured matrix into a low-rank tensor of order K This section introduces a rearrangement from a matrix to a multidimensional array that links the inference of the Kronecker structure for matrices to the low-rank approximation problem for multidimensional arrays i.e. higher-order tensors.

The second order case

Consider a matrix D ∈ R n1n2×m1m2 such that D = D 1 ⊗ D 2 , where D 1 ∈ R n1×m1 and D 2 ∈ R n2×m2 .
Then one can define an operator R 2 : R n1n2×m1m2 → R n2m2×n1m1 which rearranges the elements of D in such way that the output D π = R 2 (D) is a rank-1 matrix [START_REF] Van Loan | Approximation with kronecker products[END_REF] given by

D π = R 2 (D) = vec(D 2 ) vec(D 1 ) T = vec(D 2 ) • vec(D 1 ) (3)
It consists in vectorizing the jth-block in D to form the jth-column of R(D), running through the blocks column-wise. This process is illustrated in Figure 1.

Generalizing to higher order

Now, suppose a K-KS matrix D ∈ R n1n2...nK ×m1m2...mK given by

D = D 1 ⊗ • • • ⊗ D K = K k=1 D k (4)
with

D k ∈ R n k ×m k for k ∈ {1, . . . , K}.
We can generalize the rearrangement operator R 2 (for 2-KS matrices) to an operator R K : R n1n2...nK ×m1m2...mK → R nK mK ו••×n1m1 (for K-KS matrices) in a recursive manner. For this, let's suppose R K-1 known, such that

D = K k=2 D k ⇒ D π = R K-1 (D) = vec(D K ) • • • • • vec(D 2 ), (5)
which outputs a (K -1)th-order rank-1 tensor for an input (K -1)-KS matrix, and try to define R K from it. Note that we can rewrite

D = D 1 ⊗ (D 2 ⊗ • • • ⊗ D K ) which means that D is composed of n 1 by m 1 blocks given by d 1 (i, j) (D 2 ⊗ • • • ⊗ D K ) in
which we can directly apply R K-1 . If we again run through all these blocks columnwise applying R K-1 and stacking the resulting (K-1)th-order tensors along dimension K, we will obtain a (K)-order rank-1 tensor given by:

D π = R K (D) = (vec(D K ) • • • • • vec(D 2 )) • vec(D 1 )
Therefore, we can define a recursive algorithm to calculate R K which has R 2 defined in Section 3.1 as a base case. Actually, we can go even further and decompose R 2 recursively in the exact same way, in which case the base case R 1 becomes a simple vectorization operation.The described procedure is illustrated in Figure 2 for the particular case of K = 3. Just like in Section 3.1, note that for an input (R, K)-KS matrix, the rearrangement outputs a sum of R rank-1 tensors with factors vec(D i ) sorted in the reverse lexicographic order:

D π = R r=1 vec(D r K ) • • • • • vec(D r 1 ).

Inverse rearrangement

The inverse rearrangement R -1 K consists simply in switching the input and output indexes of the previous operator so to yield D = R -1 K (D π ). In practical terms, the resulting recursive algorithm consists in progressively reconstructing the blocks of D from their vectorized versions in D π . The base case is now a matricization (unvec) operation.

From SVD to CPD

Let D ∈ R n×m and consider the following constrained approximation problem:

min D∈C R K D -D 2 F (6)
With the help of the rearrangement operators defined in Section 3, the task of approximating any given matrix D comes down to low-rank approximation of the Kth-order rearranged tensor

D π = R K (D).
When the targeted structure is a (sum of) 2-Kronecker product(s), i.e. K = 2, we are interested in the low-rank approximation of D π = R 2 (D) which is still a matrix (2nd-order tensor). This is easily achieved -and also optimally, from Eckart-Young theorem -via the SVD.

The task gets harder if we want to generalize to a (sum of) K-Kronecker product(s), since a low-rank approximation of an order-K tensor D π = R K (D) is required. In this work, we propose to use the a Canonical Polyadic Decomposition (CPD) [START_REF] Kolda | Tensor decompositions and applications[END_REF] to approximate the tensor D π with a sum of R rank-one tensors.

{ dr k } r={1,...,R} k={1,...,K} = CPD(D π , R) such that Dπ = R r=1 dr K • • • • • dr 1 (7)
We can see that each composing Dr k can be obtained from the corresponding vector dr k through a simple matricization operation: Dr k = unvec( dr k ). The resulting approximation is thus a (R, K)-KS matrix with factors Dr

Experiments

To evaluate the proposed dictionary learning algorithm, we have performed some color image denoising experiments following the set-up introduced in [START_REF] Elad | Image denoising via sparse and redundant representations over learned dictionaries[END_REF]. The test images, 512×512×3 color images, are corrupted by a white Gaussian noise with different standard deviations σ. In these experiments we thus have K = 3. The dictionary is trained from a set of vectorized (6×6×3)-pixel patches extracted uniformly from the noisy image itself and then used to reconstruct all overlapping patches with a one-pixel step. The denoised image is obtained by averaging the pixel values of the overlapping patches. The simulation parameters are as follows: sample dimension (n) is 108 (with n 1 ×n 2 ×n 3 = 6×6×3), number of atoms (m) is 864 with m 1 ×m 2 ×m 3 = 12×12×6), number of training samples (N ) is 4×10 4 , convergence tolerance (tol) is D F ×10 -4 and number of iterations (N it ) is 20.

The sparse coding step is performed by the OMP algorithm. The PSNR of the reconstructed images are evaluated as follows: PSNR = 2552 N px / Npx i=1 (y i -ŷi ) 2 where 255 is the maximum pixel value, N px is the total number of pixels on the input image, y i and ŷi are respectively the i-th pixel value on the input and reconstructed image. The results are averaged over five noise realizations.

Figure 3 shows the denoised image PSNR (in dB) as a function of the number of Kronecker summing terms in the dictionary (i.e. the rank R of the rearranged tensor). We compare our results to an unstructured dictionary with the same size learned by the K-SVD [START_REF] Aharon | K-SVD: An algorithm for designing overcomplete dictionaries for sparse representation[END_REF] algorithm and to the 3D-ODCT analytic dictionary, which is actually a 3-Kronecker dictionary as well (although not trained from the data). 3D-ODCT is also used for initializing the proposed HO-SuKro Compared to the fixed 3D-ODCT dictionary, our algorithm achieves considerably better denoising results, even for one single separable term (R = 1) which is the exact same structure as the 3D-ODCT. It remains slightly inferior to a K-SVD dictionary in most cases, but with the advantage of the reduced application complexity due to the Kronecker structure (see Table 1). The chosen structure proved well suited to this kind of application, since its introduction compromised very little the performance. Actually, it even enhanced the denoising capabilities in higher noise scenarios, which we attribute to an overfitting prevention due to the structure constraint. The addition of separable terms tends to improve the performance until a certain point after which it saturates -or even deteriorates at higher noise, indicating the onset of overfitting.

Table 1 shows the theoretical complexity savings provided by the Kronecker structure for matrix vector operations as well as its storage cost compared to an unstructured dictionary. The gains are around one and two orders of magnitude in this case. Obviously, for the complexity gains to be observed in practice, the matrix-vector multiplications should be performed according to equation (1). In Figure 4 we evaluate the robustness of the learning algorithm to a reduction on the training set size. It shows the ∆PSNR, defined as the difference with respect to the PSNR obtained by ODCT. Note that the Kronecker-structured dictionaries become more competitive as the size of the training set decreases, to the point of consistently outperforming K-SVD for small enough training sets. This result goes in line with the theoretical results in [START_REF] Shakeri | Sample complexity bounds for dictionary learning of tensor data[END_REF] suggesting a smaller sample complexity for KS dictionaries.

Conclusion

To improve on storage, robustness to sample size and computational complexity, a new dictionary learning model was introduced where the dictionary is constrained as a sum of R Kronecker products of K terms. Such a constraint arises naturally when the original data are contained in a Kth-order tensor, such as a collection of color images. We have drawn a parallel between this sum of Kroneckers constraint and the tensor Canonical Polyadic Decomposition, the latter being used as a projection algorithm for imposing the structure constraint. Encouraging results are shown on color image denoising, and future works will focus on properly exploiting the Kronecker structure to accelerate the training phase of the dictionary, which is currently quite time consuming (about one order of magnitude slower than the K-SVD, as a comparison). Nevertheless, it remains interesting for cases where the dictionary is to be repeatedly applied afterwards.

Fig. 1 :

 1 Fig. 1: Rearrangement operation

Fig. 2 :

 2 Fig. 2: Rearrangement operation RK for K = 3.

1 : 4 :

 14 k . The proposed procedure to obtain D and its factors Dr k is summarized in Algorithm 2, which we call HO-SuKro (Higher Order Sum of Kroneckers) Approximation algorithm. It is parametrized by the targeted rank R and two vectors n = [n 1 , . . . , n K ] and m = [m 1 , . . . , m K ] with (n k × m k ) being the dimensions of the k-th factor Dr k (∀r ∈ {1, . . . , R}), such that n = K k=1 n k and m = K k=1 m k . Algorithm 2 D , { Dr k } r={1,...,R} k={1,...,K} = HO-SuKroApprox(D, R, n, m) RK (D) = Rearrange(D, n, m) ⊲ Rearranging input matrix 2: { dr k } r={1,...,R} k={1,...,K} = CPD(RK (D), R) ⊲ CPD on rearranged tensor 3: { Dr k } r={1,...,R} k={1,...,K} = unvec( dr k ) ⊲ Recovering factors Dr k return D = R r=1 Dr 1 ⊗ • • • ⊗ Dr K , { Dr k } r={1,...,R} k={1,...,K}

Fig. 3 :

 3 Fig. 3: PSNR vs. Number of separable terms (R) for the mandrill image.

Fig. 4 :

 4 Fig. 4: PSNR vs. Number of training samples for the mandrill image.

  n1×

  m1×

  1 .

			input PSNR =22.11dB				input PSNR =14.15dB				input PSNR =10.63dB				input PSNR =8.13dB
							22
																			18.15
		26.8					21.8						19.5
																			18.1
													19.4
	PSNR	26.6					21.6						19.3						18.05
		26.2 26.4			KSVD 3D-ODCT HO-SuKro	21.4 21.2				KSVD 3D-ODCT HO-SuKro	19.1 19.2				KSVD 3D-ODCT HO-SuKro	18 17.95				KSVD 3D-ODCT HO-SuKro
							21
		0	1	2	3	4	5	0	1	2	3	4	5	0	1	2	3	4	5	0	1	2	3	4	5
			Nb. Separable Terms				Nb. Separable Terms				Nb. Separable Terms				Nb. Separable Terms

Table 1 :

 1 Complexity costs (for matrix-vector multiplications) and storage costs 2

		HO-SuKro Unstructured Ratio (Unstructured/HO-SuKro)
	Complexity (# operations) 12960 × R	186624	14.4/R
	Storage (# parameters)	162 × R	93312	576/R

The 1-D n×m overcomplete DCT dictionary, as defined in[START_REF] Rubinstein | Double sparsity: Learning sparse dictionaries for sparse signal approximation[END_REF], is a cropped version of the orthogonal m×m DCT matrix. The K-dimensional ODCT is the Kronecker product of K 1-D ODCT.

Complexity cost for HO-SuKro is trivially obtained considering eq. (1). Storage cost is the total number of elements in all factors: R( k n k m k ).

support by the F.R.S.-FNRS (incentive grant for scientific research n o F.4501. 16)


The Type VI secretion system (T6SS) is a versatile machine that delivers toxins into 2! either eukaryotic or bacterial cells. It thus represents a key player in bacterial 3! pathogenesis and inter-bacterial competition. Schematically, the T6SS can be viewed as 4! a contractile tail structure anchored to the cell envelope. The contraction of the tail 5! sheath propels the inner tube loaded with effectors towards the target cell. The 6! components of the contracted tail sheath are then recycled by the ClpV AAA + ATPase 7! for a new cycle of tail elongation. The T6SS is widespread in Gram-negative bacteria 8! and most of the genomes of these bacteria carry several copies of T6SS gene clusters, 9! which might be activated in different conditions. Here, we show that the ClpV ATPases 10! encoded within the two T6SS gene clusters of enteroaggregative Escherichia coli are not 11! interchangeable and specifically participate to the activity of their cognate T6SS. Using 12! bacterial two-hybrid, co-immunoprecipitation, in vitro microscale thermophoresis and 13! deletion studies, we further show that this specificity is dictated by interaction between 14! the ClpV N-terminal domains and the N-terminal helices of their cognate TssC proteins. 15! We finally present the crystal structure of the ClpV1 N-terminal domain, alone or in 16! complex with the TssC N-terminal helical peptide, highlighting the commonalities and 17! diversities in the recruitment of ClpV to contracted sheaths. 18! 19! ! 3! ! 4!

[42][43] .

2!

. Polymerase Chain Reactions (PCR) were performed using a 6! Biometra thermocycler using the Q5 high fidelity DNA polymerase (New England BioLabs).

7!

, were synthesized by Sigma 8! Aldrich. Enteroaggregative E. coli 17-2 chromosomal DNA was used as a template for all 9! PRCs. The amplified DNA fragments correspond to the full-length ClpV1 (EC042_4530, GI: 10! 284924251), ClpV2 (EC042_4577, GI: 284924293), TssC1 (EC042_4525, GI: 284924246) 11! and TssC2 (EC042_4562, GI: 284924279) proteins, as well as the N-terminal domains of 12! ClpV1 (residues 1-163) and ClpV2 (residues 1-147). Plasmids were engineered by restriction-13! free cloning 47 as previously described 35 . Briefly, genes of interest were amplified with 14! oligonucleotides introducing extensions annealing to the target vector. The double-stranded 15! product of the first PCR was then been used as oligonucleotides for a second PCR using the 16! target vector as template. Deletion of TssC1 and TssC2 N-terminal helices as well as point 17! mutations have been obtained by site-directed mutagenesis. All constructs have been verified 18! by restriction analysis and DNA sequencing (Eurofins, MWG).

19!

Bacterial two-hybrid assay. The adenylate cyclase-based bacterial two-hybrid technique 48 20! was used as previously published 49 . Briefly, compatible vectors producing proteins fused to 21! the isolated T18 and T25 catalytic domains of the Bordetella adenylate cyclase were 22! transformed into the reporter BTH101 strain and the plates were incubated at 30°C for 24 23! hours. Three independent colonies for each transformation were inoculated into 600 µL of LB 24! medium supplemented with ampicillin, kanamycin and IPTG (0.5 mM). After overnight 25! growth at 30°C, 10 µL of each culture were spotted onto LB plates supplemented with 26! ampicillin (100 µg/mL), kanamycin (50 µg/mL), IPTG (0.5 mM) and Bromo-Chloro-Indolyl-27! Galactopyrannoside (40 µg/mL) and incubated for 16 hours at 30 °C. The experiments were 28! done at least in triplicate and a representative result is shown.

29!

.

19!

Peptide synthesis, protein purification and characterization. E. coli BL21 (DE3) pLysS 20! cells carrying the pETG20A-ClpV1-Nt plasmid were grown at 37°C in TB medium (1.2% 21! peptone, 2.4% yeast extract, 72 mM K 2 HPO 4 , 17 mM KH 2 PO 4 , and 0.4% glycerol).

22!

Expression of clpV1-Nt was induced at A 600 = 0.6 with 0.5 mM IPTG for 18 hours at 25°C.

23!

Cells were then resuspended in lysis buffer (50 mM Tris-HCl pH 8.0, 300 mM NaCl, 1 mM 24! EDTA, 0.5 mg/mL lysozyme, 1mM phenylmethylsulfonyl fluoride), submitted to several 25! freeze-thawing cycles and sonicated after the addition of 20 µg/mL DNase and 20 mM 26! MgCl 2 . Pellet and soluble fraction were separated by centrifugation for 30 min at 16,000 × g.

27!

The soluble fraction containing ClpV1-Nt was loaded onto a 5-mL Ni 2+ affinity column 28! (HisTrap™ FF) using an ÄKTA Explorer apparatus (GE healthcare) and the immobilized 29! proteins were eluted in 50 mM Tris-HCl pH8.0, 300 mM NaCl supplemented with 250 mM 30! imidazole. The protein solution was desalted on a HiPrep 26/10 column (Sephadex TM G-25, 31! Amersham Biosciences), and ClpV1-Nt was obtained by cleavage using 2 mg of TEV 32! ! 7! protease for 18 hours at 4°C and collected in the flow-through of a 5-mL Nickel column. The 1! protein was concentrated using the centricon technology (Millipore, 10-kDa cut-off). After 2! concentration, the soluble ClpV1-Nt protein was passed through a Sephadex 200 26/60 3! column pre-equilibrated with 25 mM Tris-HCl pH7.5, 100 mM NaCl, 5% Glycerol. A similar 4! procedure was applied for the ClpV2-Nt domain but the protein was insoluble and could not 5! be purified. 6! Peptides corresponding to the α-helices from TssC1 and TssC2 (Fig. 3A) were synthesized by 7! Genscript (TssC1 (residues 23-35), KKW-DSVYASLFEKINL-KK; TssC2 (residues 15-29), 8! Douzi et al. Figure 2! Hcp1-T18! T18-ClpV1!

Introduction

1!

The Type VI secretion system (T6SS) is a multi-protein complex widely distributed in 2! Gram-negative bacteria with an over-representation in Proteobacteria and Bacteriodetes that 3! transports and delivers effector toxins into target cells [1][START_REF] Cascales | The type VI secretion toolkit[END_REF][3][4] . The activities and molecular targets 4! ATDDCLEEIINNTRA). Due to its hydrophobic nature, the TssC1 N-terminal peptide was 9! flanked by two lysines to improve its solubility and by an additional tryptophane to follow it 10! during purification.

11!

Microscale thermophoresis (MST) experiments. Microscale thermophoresis experiments 12!

were performed using a Monolith NT.115 apparatus (NanoTemper). ClpV1-Nt was labeled 13! with the blue-fluorescent dye NT-495-NHS (NanoTemper) and the buffer was exchanged for 14! the assay buffer (25 mM Tris-HCl pH 7.5, 200 mM NaCl, glycerol 5%, 0.05% Tween-20) 15! using a Nap5 column (GE Healthcare). Titrations were conducted with a constant 200 nM 16! fluorophore-labeled ClpV1-Nt against up to 500 µM TssC N-terminal peptides in hydrophilic-17! coated capillaries. Each data point was measured in triplicate. Single-site fitting was 18! performed using the NanoTemper data analysis software.

19!

Crystal structures determination. ClpV1-Nt was purified to homogeneity and the protein 20! crystallized spontaneously during gel filtration. ClpV1-Nt crystals belong to space group 21! P2 1 2 1 2 1 with cell dimensions a=40.9Å, b=58.7 Å, c=65.6 Å (Supplemental Table S2). A 22! complete data set was collected at the Soleil synchrotron (Saint-Aubin, France) at 2 Å. Data 23! were integrated with XDS 50 and reduced with XSXALE 50 (Supplemental Table S2). The 24! structure was solved by soaking crystals in a 0.5 M NaI and 0.5 M of CsI solution followed by 25! data collection at 1.77-Å wavelength, allowing remote SAD phasing. The cesium/iodine 26! positions were defined with SHELXC and SHELXD 51 and subsequently used for SAD 27! phasing using PHASER 52 . These phases were improved by solvent flattening and histogram 28! matching using the program PARROT 53 , resulting in interpretable maps from which the 29! BUCCANEER program 54 was able to build an initial model. The model was completed and 30! corrected manually with COOT 55 and refined with autoBUSTER 56 (Supplemental Table S2).

31! ! 8!

The ClpV1-Nt/ TssC1 peptide complex was obtained by mixing the purified ClpV1 N-1! terminal domain with the peptide at a 1:4 molecular ratio in 20 mM Tris-HCl pH8.0, 100 mM 2! NaCl, 5% Glycerol and concentrated using the centricon technology (Millipore, kDa cut-off 3! of 10) to 2 mg/mL. Crystals were obtained in one condition (0.2 M imidazole, malate pH 6.0, 4! 8% w/v PEG 4000) using the STURA screen (Molecular dimensions) and diffracted at 2.5-Å 5! resolution. The structure was solved by molecular replacement using the structure of ClpV1-6! Nt as starting model. The model was completed and corrected manually with COOT 55 and 7! refined with autoBUSTER 56 (Supplemental Table S2).

Results

14!

ClpV1 and ClpV2 are not interchangeable.

15!

The enteroaggregative E. coli Sci-1 and Sci-2 T6SS are both involved in bacterial 16! competition 29,40 . However, these two T6SS are active in different laboratory conditions 17! (minimal medium for the Sci-1 T6SS and modified Eagle medium for the Sci-2 T6SS; 57,58 .

18!

To test whether the two ClpV proteins, ClpV1 (EC042_4530, GI: 284924251) and ClpV2 19! (EC042_4577, GI: 284924293), respectively encoded by the sci-1 and sci-2 gene clusters are 20! interchangeable, we engineered ∆clpV1 and ∆clpV2 strains and complementation vectors 21! (pIBA-ClpV1 and pIBA-ClpV2). The different combinations were tested for their ability to 22! confer a growth advantage in Sci-1-or Sci-2-active conditions against E. coli K-12. Figure 1 23! shows that while clpV1 and clpV2 trans-expression restores the growth advantage of the 24! ∆clpV1 and ∆clpV2 mutant strains respectively, over-production of ClpV2 does not restore 25! ∆clpV1 defects, and vice versa. From this experiment, we concluded that the ClpV1 and 26! ClpV2 ATPase are not interchangeable and we hypothesized that this specificity could be 27! imputable to specific contacts with partners. 28!

29!

ClpV specificity is dictated by ClpV-TssC complex formation.

30! ! 9!

To identify ClpV1 partners, we performed a systematic bacterial two-hybrid analysis.

1!

ClpV1 was fused to the N-or C-terminus of the Bordetella pertussis Cya T25 domain and 2! these protein fusions were tested as baits against preys comprising fusion of the T18 domain 3! to the individual T6SS core components. Growth on reporter plates demonstrated that ClpV1 4! interacts with itself (Fig. 2A), in agreement with the ability of AAA + ATPases to assemble 5! hexameric structures 22,59 . However, ClpV1 does not interact with ClpV2 suggesting that these 6! two proteins cannot assemble hetero-hexamers (Fig. 2B). In addition, ClpV1 interacts with 7! TssC1 (EC042_4525, GI: 284924246), one of the sheath components (Fig. 2C). The ClpV1-8! TssC1 interaction was further confirmed by co-immunoprecipitation (Fig. 2D). The ClpV-9! TssC interaction has already been reported in V. cholerae and P. aeruginosa and involves 10! contacts between the N-terminal domain of ClpV and an N-terminal helix of TssC 22,[START_REF] However | values obtained in vitro might not represent the in vivo situation. In 16! vivo[END_REF]43 .

11!

Similarly, co-immunoprecipitation assays showed that ClpV1 the N-terminal domain of 12! ClpV1 (ClpV1-Nt, residues 1-163) is sufficient to mediate the interaction with TssC1, while a 13! deletion of the TssC1 N-terminal helix (deletion of residues 23-25, TssC1∆h) abolishes 14! ClpV1-TssC1 complex formation (Fig. 2D, left panel). Identical results were obtained for 15! ClpV2 and the Sci-2-encoded TssC2 protein (Fig. 2D, right panel). We then tested cross-16! interaction between the ClpV N-terminal domains and TssC proteins. TssC proteins from the two T6SSs was further confirmed by bacterial two-hybrid (Fig. 2E).

20!

From these results, we concluded that specificity determinants control ClpV-TssC complex 21! formation and we hypothesized that these specificity determinants should be located within 22! the TssC N-terminal helices. In support of this hypothesis, a sequence alignment of TssC1 and 23! TssC2 showed that the two proteins share high level of homologies except in the N-terminal 24! region that is, in average, less conserved (18% identity within the 55 N-terminal residues 25! compared to 38 % identity on full-length sequences, Supplemental Figure S1).

26!

To gain further insights onto the binding and specificity of ClpV1 towards the TssC 27! N-terminal helices, the ClpV1 N-terminal domain was purified. In addition, peptides 28! corresponding to TssC1 (residues 23-35) and TssC2 (residues 15-29) N-terminal helices (Fig.

29!

3A) were synthesized. Binding of the TssC peptides to ClpV1-Nt was assayed by microscale 30! thermophoresis that allows the quantification of molecular interactions in free solution states. 31! Fig. 3B shows that the TssC1 peptide binds to ClpV 1 -Nt with a K D of ~ 26 µM, a value that is 32! comparable to the affinity measured between V. cholerae ClpV and the VipB (TssC) N-33! ! 10! terminal peptide (K D ~ 39 µM) [START_REF] However | values obtained in vitro might not represent the in vivo situation. In 16! vivo[END_REF] . By contrast, no binding of TssC2 peptide to ClpV1-Nt was 1! observed (Fig. 3C).

2! 3!

Structures of the ClpV1 N-terminal domain alone and in complex with the TssC1 N-4! terminal peptide reveal a new mode of binding.

5!

To obtain molecular details on the ClpV1-TssC1 interaction, we crystallized the 6! ClpV1-Nt domain alone and in complex with the TssC1 N-terminal helix peptide. ClpV1-Nt 7! crystallized in the P2 1 2 1 2 1 space group and diffracted to 2.0-Å resolution (Supplemental Table 8! S2). ClpV1-Nt structure was solved using a CsI derivative and phasing was achieved with 9! remote SAD methods, using a 1.77-Å wavelength for data collection. The amino-acid chain 10! could be traced between residues 1 and 163. The structure comprises 10 α-helices (H0 to H9) 11! (Fig. 4), with overall dimensions of a flat disc of 50 × 46 × 28 Å. Interestingly, helix H0 is 12! oriented perpendicular to helix H1, delimiting a groove.

13!

Crystals of ClpV1-Nt in complex with the TssC1 peptide were obtained. The crystals 14! belong to space group P2 1 2 1 2 1 and diffracted to 2.5-Å resolution (Supplemental Table S2).

15!

The structure of the complex was determined by molecular replacement using the 16! uncomplexed structure (Fig. 5A-B). ClpV1-Nt is defined between residues 6 and 162 in the 17! electron density map and its structure shows that it is not subjected to significant variation 18! compared to the unbound ClpV1-Nt domain (root mean square deviation of 0.8 Å). The 19! TssC1 N-terminal peptide is well defined in the electron density map between the residue 20! Asp23 and Leu35. The peptide forms a ~ 2-turn α-helix between Ser24 and Phe30 21! (SVYASLF), while the rest of the peptide (EKINL) is elongated (Fig. 5A-B). PISA analysis 22!

shows that the interaction between ClpV1-Nt and the TssC1 peptide covers 622 Å 2 on the 23! peptide (38% of the total surface) and 520 Å 2 on the ClpV1 N-terminal domain (6.6% of the 24! total surface) (Fig. 5C, Supplemental Table S3). The TssC1 peptide accommodates in the 25! ClpV1-Nt groove delimited by helices H0 and H1, and the H4-H5 loop (Fig. 4A, Fig. 5A-E, 26! Supplemental Table S3). Most residues of the peptide are involved in the interaction, with the 27! exception of Ser24 and Ala27. The most significant interactions involve Tyr26, Leu29, 28! Phe30, Lys32, Ile33 and Asn34, the three last residues belonging to the elongated stretch (Fig.

29!

5D and 5E, Supplemental Table S3). The co-structure of ClpV1-Nt with the N-terminal tested their effects on ClpV1-TssC1 interaction and T6SS function. The Glu24-to-Lys 7! (ClpV1 EK mutant) and Arg87-to-Glu (ClpV1 RE mutant) substitutions (as well as the double 8! mutant variant, ClpV1 EKRE ) were introduced in ClpV1. These mutations did not interfere with 9! ClpV1 oligomerization (Fig. 6A). The Glu31-to-Lys and Lys32-to-Glu substitutions were 10! introduced in TssC1 (TssC1 EKKE mutant). Here again, these mutations did not prevent the 11! ability of TssC1 to oligomerize or to interact with TssB1 (Fig. 6A), two complexes previously 12! described in EAEC [START_REF] Zhang | Dissection of the TssB-TssC interface during type VI secretion sheath 2! complex formation[END_REF] . However, all these substitutions affected partly or totally ClpV1-TssC1 13! complex formation (Fig. 6A). While the ClpV1 RE mutation had only a mild effect on the 14! interaction, the ClpV1 EK and EKRE and the TssC1 EKKE mutations prevented formation of 15! the ClpV1-TssC1 complex. The ClpV1 and TssC1 variants were then tested for their ability to 16! support T6SS function. The two double mutants, ClpV1 EKRE and TssC1 EKKE , did not restore 17! the anti-bacterial activity of ∆clpV1 (Fig. 6B) and ∆tssC1 (Fig. 6C) EAEC cells, respectively.

18!

By contrast the ClpV1 RE and EK single substitutions caused a 9-and 310-fold decrease of 19! the function of the EAEC Sci-1 T6SS, respectively (Fig. 6B). 20!

21!

Discussion

22!

Bacterial genomes may encode several copies of Type VI secretion gene clusters.

23!

Although these gene clusters are usually subjected to different regulatory controls and 24! expressed in different conditions, distinct Type VI secretion machineries may co-exist in the 25! same bacterial cell 1,2 . There is therefore a need to control proper assembly of these machines 26! and to allow recruitment of cognate subunits. Indeed, previous studies have demonstrated that 27! specificity operates during machine assembly, more specifically for the interaction between 28! the inner tube Hcp subunit and its cognate TssB sheath protein in enteroaggregative E. coli [START_REF] Basler | Type 6 secretion dynamics within and between bacterial 22! cells[END_REF] .

29!

Here, we show that a second level of specificity exists, at the stage of sheath

T! IP! T! IP! T! IP! ClpV2 FL! TssC2Δh V ! T! IP! ClpV2 FL! TssC1 V ! !! 64! !! 36! !! 64! !! 50! !! 50! !! 64! ClpV ! !! 36! !! 50! * ! * ! !! 30! !! 16! !! 98! !! 36! !! 50! !! 64! B! T18-ClpV1! T18-ClpV2! T18-Pal! E! T18-ClpV1! T18-ClpV2! T18-Pal! Douzi et al.

8 ! 9 !

 89 Data deposition. The EAEC ClpV1-Nt and ClpV1-Nt/TssC1 peptide X-ray structures have 10! been deposited in the Protein Data Bank (PDB) under accession numbers 4HH5 and 4HH6,

  Fig. 2D (right lanes in 17! left and right panels) shows that each ClpV N-terminal domain interacts only with the TssC 18! encoded within the same gene cluster. The lack of cross-interaction between the ClpV and 19!

4 !

 4 therefore reveals a mode of binding distinct from previous co-structures (see 1Mutagenesis studies confirm the ClpV1-TssC1 interface shown in the co-crystal.To test the physiological relevance of the ClpV1-Nt/TssC1 peptide co-structure, we 5! engineered point mutations within the ClpV1 groove and the TssC1 N-terminal region, and 6!

Figure 1 .Figure 2 .Figure 3 .Figure 4 . 22 !Figure 5 .Figure 6 .Figure 7 . 23 !Figure 8 .Figure S1 .

 123422567238S1 Figure 1. ClpV1-ClpV2 interchangeability. (A) Sci-1-dependent antibacterial growth 2! inhibition. Prey cells (W3110 gfp + , kan R ) were mixed with the indicated attacker cells, spotted 3! onto sci-1-inducing medium (SIM) agar plates and incubated for 4 hours at 37°C. (B) Sci-2-4! dependent antibacterial growth inhibition. Prey cells (W3110 gfp + , kan R ) were mixed with the 5! indicated attacker cells, spotted onto Dulbecco's modified Eagle Medium (DMEM) agar 6! plates and incubated for 4 hours at 37°C. The image of a representative bacterial spot is 7! shown and the relative fluorescent levels (in arbitrary units, AU) are indicated in the upper 8! graph. The number of recovered E. coli prey cells is indicated in the lower graph (in log 10 of 9! colony-forming units (cfu)). The circles indicate values from three independent assays, and 10! the average is indicated by the bar. 11!

  ----------EEEE-------HHHHHHHHH------------HHHHH-----! !TssC2! MTVASTLGLNETQYATDDCLEEIINNTRAVRQDSEKTRFKLQINNFLAEVASGSL! ---HHHHH---------HHHHHHHHHH-------HHHHHHHHHHHHHHHHH----! --HHHHHHHHHHHHHHHH-------HHHHHHHHHHH----HHHHHHHH---HHHHHHHHHHHHH---------HHHHHHHHHHHHHHHH-------HHHHHHHHHH-------HHHHHHH---HHHHHH-HHHHHHH------

Table S1 . Strains, Plasmids and Oligonucleotides used in this study. 18! Table S2. Data collection and refinement statistics for the ClpV1-Nt and ClpV1- 19! Nt/TssC1 peptide crystals. 20!Table S3 . ClpV1-Nt / TssC1 contacts in the co-crystal structure.

 S1S3

	21!
	22!	!

Table S3 . Interaction between the ClpV1-N-terminal domain and the TssC1 peptide

 S3 . (A) Analysis of the interaction surface. (B) Residues of TssC1 peptide interacting with the ClpV1-N-terminal domain. (C) Residues of the ClpV1-N-terminal domain interacting with the TssC1 peptide. ASA : accessible surface area. BSA : buried surface area. Analysis performed with PISA. ! A

	Supplemental Peptide 1	ClpV-Nt
	Interface Å 2	622.5	38.4% 520.8	6.6%
	Total surface Å 2 1620.9	7912.5
	!
	B"
	Peptide 1 ASP 23	ASA Completeness a (%) BSA 70.21 24.4	96.1 (92.1)	99.6 (98.5)
	VAL 25	Multiplicity a 72.85 20.3
	TYR 26	REFINEMENT 133.51 113.0
	SER 28	Resolution a (Å) 59.69 19.7	43.8-2.0 (2.24-2.0)	36.0-2.5 (2.79-2.5)
	LEU 29 PHE 30	Nr of reflections a 118.81 113.0 130.83 62.7	(1.79-1.75) 10703( 2770)	5359 (1358)
	Atoms : protein, ions, water GLU 31 131.80 22.1	1275 / 1 /107	1297 / 27
	LYS 32	Nr test set reflections 142.15 101.2	512	516
	ILE 33	R work /R free 97.17	a (%) 75.5	0.186/0.205 (0.181/0.234) 0.244/0.263 (28.1/32.1)
	r.m.s.d.bonds (Å) / angles (°) ASN 34 114.88 57.5	0.008 / 1.04	0.008 / 1.36
	B-wilson / B-average (Å 2 ) LEU 35 230.48 12.6 Ramachandran: preferred/allowed (%) ! C"	28.35 / 29.6 97.5 / 2.5	57.6 / 55 91.6 / 6.0 / 2.4
	ClpV1-Nt	(%) ASA	BSA
	SER	8	31.16	10.5
	ALA	9	67.64	25.9
	LEU 12	57.58	52.7
	ARG 13	182.26	46.3
	LEU 15	10.34	10.3
	HIS 17	169.33	52.7
	ALA 20	41.75	38.7
	LEU 23	13.70	13.5
	GLU 24	109.71	68.4
	ALA 27	26.96	26.8
	SER 28	55.93	7.2
	GLN 31	32.77	2.5
	ILE 38	5.36	4.2
	ARG 87	215.54	77.3
	PRO 88	31.75	28.6
	GLN 89	64.68	27.6
	LEU 90	41.49	18.1

Acknowledgements 20! We thank the members of the Cascales and Cambillau research groups for insightful 21! discussions and the Soleil synchrotron (Saint-Aubin, France) for beamline allocation. This 22! work was supported by the Centre Nationale de la Recherche Scientifique (CNRS), the Aix-23! Douzi et al. Figure 7! B! A! Douzi et al. Figure 8!

Source Expression vectors pUA66-rrnb P rrnB ::gfpmut2 transcriptional fusion in pUA66 Zaslaver et al., 2006 pASK-IBA37 cloning vector, Ptet, Amp R IBA Technology pIBA37-ClpV1 FLAG sci1 clpV, C-terminal FLAG tag cloned into pASK-IBA37 This study pIBA37-ClpV1-Nt FLAG sci1 clpV N-terminal fragment (residues 1-162), C-terminal FLAG tag cloned into pASK-IBA37(+) This study pIBA37-ClpV1-E24K FLAG clpV1 Glu24-to-Lys substitution into pIBA37-ClpV1 FLAG This study pIBA37-ClpV1-R87E FLAG clpV1 Arg87-to-Glu substitution into pIBA37-ClpV1 FLAG This study pIBA37-ClpV1-E24K-R87E FLAG clpV1 Glu24-to-Lys and Arg87-to-Glu substitutions into pIBA37-ClpV1 FLAG This study pIBA37-ClpV2 FLAG sci2 clpV, C-terminal FLAG tag cloned into pASK-IBA37 This study pIBA37-ClpV2-Nt FLAG sci2 clpV N-terminal fragment (residues 1-147), C-terminal FLAG tag cloned into pASK-IBA37(+) This study pBAD33 cloning vector, pACYC184 origin, Para, araC Cm R Guzman et al., 1995 pBAD33-TssC1 VSV-G sci1 tssC, C-terminal VSV-G tag cloned into pBAD33 This study pBAD33-TssC1-E31K-K32E VSV-G tssC1 Glu31-to-Lys and Lys32-to-Glu substitutions into pBAD33-TssC1 VSV-G This study pBAD33-TssC1∆h VSV-G Deletion of amino-acids 23-35 of sci1 tssC into pBAD33-TssC1 VSV-G This study pBAD33-TssC2 VSV-G sci2 tssC, C-terminal VSV-G tag cloned into pBAD33 This study pBAD33-TssC2∆h VSV-G Deletion of amino-acids 2-15 of sci2 tssC into pBAD33-TssC2 VSV-G This study Bacterial Two-Hybrid vectors pT18-FLAG Bacterial Two Hybrid vector, ColE1 origin, Plac, T18 fragment of Bordetella pertussis CyaA, Amp R Battesti & Bouveret, 2008 pT18-Pal Soluble region of E. coli K-12 Pal cloned downstream T18 in pT18-FLAG Battesti & Bouveret, 2008 pClpV1-T18 sci1 clpV cloned upstream T18 into pT18-FLAG This study pT18-ClpV1 sci1 clpV cloned downstream T18 into pT18-FLAG This study pT18-ClpV1-E24K clpV1 Glu24-to-Lys substitution into pT18-ClpV1 This study pT18-ClpV1-R87E clpV1 Arg87-to-Glu substitution into pT18-ClpV1 This study pT18-ClpV1-E24K-R87E clpV1 Glu24-to-Lys and Arg87-to-Glu substitutions into pT18-ClpV1 This study pT18-ClpV2 sci2 clpV cloned downstream T18 into pT18-FLAG This study pT25-FLAG Bacterial Two Hybrid vector, p15A origin, Plac, T25 fragment of Bordetella pertussis CyaA, Kan R Battesti & Bouveret, 2008 pTolB-T25 E. coli K-12 tolB cloned upstream T25 in pT25-FLAG Battesti & Bouveret, 2008 pClpV1-T25 sci1 clpV cloned upstream T25 into pT25-FLAG This study pT25-ClpV1 sci1 clpV cloned downstream T25 into pT25-FLAG This study pTssC1-T25 sci1 tssC cloned upstream T25 into pT25-FLAG Zoued et al., 2013 pTssC1-E31K-K32E-T25 tssC1 Glu31-to-Lys and Lys32-to-Glu substitutions into pTssC1-T25 This study pTssC2-T25 sci2 tssC (EC042_4564) cloned upstream T25 into pT25-FLAG This study All others BACTH constructs have been described in Zoued et al., 2013.

Additional information

4!

Supplementary information accompanies this article (Figure S1, Tables S1-S3).

5!

Competing financial interests. The authors declare no competing financial interests. ! Supplemental Table S1


Xavier Chapeleau
email: xavier.chapeleau@univ-nantes.fr

Dominique Leduc

Pascal Casari

Yves Quinquempois

Josselin Lebon

Francisco Lopez

Cyril Lupi

Christian Boisrobert

Yves Quiquempois

Accurate index profile measurements for fiber bragg gratings and sensor application

Introduction

The determination of the index profiles of Fiber Bragg Gratings (FBGs) is more and more desired in order to improve their spectral and temporal performances in particular for high bite rate transmission systems. Some methods as tranverse diffraction technique, local heating technique or Optical Space Domain Reflectometry (OSDR) can be used but they are more suitable for highly reflective gratings. In general, their sensitivity is not sufficient to dectect index modulation amplitude below ¦ §¦ © . An alternative method is based on the association of the Optical Low-Coherence Reflectometry (OLCR) and an inverse scattering algorithm called layer-peeling [START_REF] Skaar | On the Synthesis of Fiber Bragg Gratings by Layer Peeling[END_REF]. The OLCR measures the complex reflection coefficient which is necessary for the layer-peeling to retrieve the index profile of FBGs. The aim of this paper is to demonstrate the efficiency of this method. The sensitivity of the index modulation amplitude and phase measurements are studied. An application of our method to the determination of axial strain distribution is also presented.

OLCR and layer-peeling

FBGs are a periodic refractive index modulation in the core of optical fibers, induced by UV exposure. This index perturbation "! $# is generally written as the following form :

% & '! (# §) 0 21 43 5 '! (# 46 7 28 3 9 '! (# A@ CB $D E GF IH P 5Q ! R6

F SH P ¡ Q RT VU Q P '! XW Y# a`P 5Q # cb $! dW fe (1)
where % 8 g3 is the index modulation amplitude and g1 43 is the mean index variation. P "! $# is the period of the grating. For uniform gratings

P '! (# h) P iQ

and for gratings with linear chirp P "! $# is expressed as P "! $# h) 0p %! 56 P qQ

.

The layer-peeling algorithm is based on the coupled mode theory. By knowning the complex reflexion coefficient, this algorithm gives the coupling coefficient r s "! $# which is expressed by the following relation :

r s '! (# §) t H F u wv P 9Q % 8 g3 "! $# 2x y 2 '! (# f "! $# h) F IH t 2u wv P 5Q T U Q 1 43 "! dW # cb $! dW X6 F SH P ¡ Q sT U Q P '! XW Y# a`P Q # qb X! XW (2)
where u wv is the unperturbed effective index of the fiber and t the fraction of the modal power contained in the fiber core. '! (# corresponds to the phase of the grating. The equation 2 shows that the index modulation amplitude and the phase of the grating can easily be determined. However, the layer-peeling algorithm can only be used if the complex reflexion coefficient of FBGs is measured accurately. The OLCR is admitted as a suitable method to do it. Severals papers [START_REF] Leduc | Accurate low-coherence interferometric relative group delay and reflectance measurements; characterization of a free space optics multiplexeur/demultiplexeur[END_REF][START_REF] Dyer | Low-coherence interferometric measurements of the dispersion of multiple fiber Bragg gatings[END_REF][START_REF] Giaccari | Local coupling-coefficient characterization in fiber Bragg gratings[END_REF] have demonstrated its efficiency. A description of our experimental set-up and the first results we obtained can be found in [START_REF] Chapeleau | Experimental synthesis of fiber Bragg gratings using optical low coherence reflectometry[END_REF].

Performance of the OLCR technique

As all inverse scattering algorithms, the layer-peeling is hindered due to the presence of noise in the complex reflexion coefficient measurements, especially for high reflexion coefficient. So, it can't determine correctly the index profile of FBGs having reflexion coefficient upper than 90 %. It's the highest limit we obtained so that the index profiles determined by the layer-peeling and the transverse diffraction technique (Krugg method [START_REF] Krug | Measurement of index modulation along an optical fiber Bragg grating[END_REF]) are in good agreement. The figure 1 shows the index modulation amplitudes obtained by both methods for a uniform FBG whose reflexion coefficient is equal to 90 %. We can notice that the index profiles exhibit some ripples. They are not an artefact of the layer-peeling algorithm since they appear also for the transverse diffraction measurement. They are due to internal reflexion in the phase mask. To evaluate the repetability of ten successives measurements, the maximum relative difference has been calculated. In the figure 1, we can see that these differences remain lower than 3 %, which demonstrates the high repetability of our measurements.

Index modulation

Maximum relative difference (%)

Figure 1: Index modulation amplitude. ) ¢¡ ¨% (10 measurements)

It's clear that the layer-peeling algorithm is most suitable for weak gratings. However, if the coupling strength becomes too small, the noise can hinder the index profile reconstruction. To illustrate this fact, the figure 2 shows the index profile of a grating whose reflexion coefficient is equal to only 1 %. In this case, the index modulation amplitude doesn't exceed F ¤£ ¦¥ ¦ G and we can see that the maximum relative difference is a little higher than in the previous case. Nevertheless, it remains lower than 4 %. It's important to emphasize that the index profile presented in this figure can't be detected by the diffration technique. This proves the high sensitivity of our method. To show more precisely the sensitivity, the index profile of a particular grating has been measured. Seven uniform, 500 § m long, gratings were written successively and the index modulation amplitude was divided approximately by two from one grating to the next. The measured index profile reveals well this step structure (cf. figure 3). The first step has a high index modulation amplitude close to ¦ §¦ © ¢

Maximum relative difference (%)

. The last step is very small since the index modulation amplitude is below F ¦ G¨ . This results demonstrate that the association of the layer- peeling and OLCR techniques is perfectly suitable for the measurement of index profile whose amplitude is as small as ¦ §¦ G2 .

Phase grating measurement

An other advantage of our technique is that the phase of the grating can be measured. For example, a H phaseshift grating has been studied. Theoretically, if we assume that the mean index 1 43 '! (# is constant along the grating, the phase grating can be modeled by :

¡ ¡ ¢ ¡ ¡ £ '! (# h) F SH t u wv P 9Q % 1 43 ! ¥¤ §¦ ! ¦ ! Q '! (# h) F SH t u wv P 9Q % 1 43 ! R6 H ¥¤ ! Q ¦ ! ¦ ©¨( 3)
where ! Q

is the position of the phase-shift in the grating.

The figure 4 shows the phase we obtained for this grating. This phase is linear with ! and in the middle of the grating, we can see the phase-shift which expands over 50 § m. Sometimes, it can be less long, this depends on the fabrication process. The figure in insert shows that the amplitude of the phase-shift is close to H as expected. Thus, this result demonstrates the efficiency of our method to measure the phase grating.

Axial strain distribution measurement

When FBGs are subjected to an axial force, both the grating period and the refractive index are modified. Indeed, the refractive index is changed due to the photoelastic effect :

% 1 43 ) ` ¢ u wv F ¡ s 6 ¡ # © ©# (4)
where "! ¡ are the strain-optic coefficients and the Poisson's ratio of the FBG. The grating period variation is related to the strain by the following relation :

P '! (# P Q ) # '! (# (5)
Taking into account these two effects, the phase of the grating modified by an axial strain becomes :

'! (# §)

F IH P Q ¡ ¦ `t 2u wv ¡ F ¢ ¡ ` ¢ 6 ¢ ¡ # ¤£ T U Q '! XW # cb X! XW (6)
So, the axial strain can be obtained simply by differentiating the phase.

In order to test this method, an uniform FBG, 4 mm long, has been embedded in a parallelepipedal sample of epoxy resin in which two holes have been drilled symmetrically beside the sensor (figure 5). This scheme permits to obtain a non-uniform strain along the grating.

Figure 6(a) shows the strains obtained from different tensile loads. Without applied force, the strain curve is a straight line despite some small ripples. For a force equal to 1200 N, the curve appears rounded as shows it the figure 6(b). This indicates that the strain is not uniform along the grating. The dissymetry of the measurement is only due to the fact that the two holes are not perfectly centered to the middle of the FBG.

Figure 5: Sketch of the embedded FBG A finite element model (FEM) has been used in order to predict the strain evolution along the grating. The figure 6(b) shows that the strain obtained by FEM follows exactly the same evolution as the ones measured with the FBG sensor. The excellent agreement between the two results demontrates the validity of our method for non uniform axial strain measurements.

Conclusion

The association of OLCR and layer-peeling is an efficient method for the index profile of FBGs characterization. Thanks to its high sensitivity, index modulation amplitude variations as small as ¦ 9¦ G can be detected.

Moreover, this method gives the phase of the grating, which permits to localize phase-shift or to measure the mean index variation in the case of uniform gratings. Such phase grating measurements can also be used in sensor applications. Indeed, we demonstrated that non-uniform axial strain distribution can be measured.

Figure 2 :

 2 Figure 2: Index modulation amplitude. ) ¦ % (10 measurements)

Figure 3 :

 3 Index modulation amplitude (10 measurements).

Figure 4 :

 4 Phase of the H phase-shift grating (10 measurements).

  Strain along the grating with and without applied traction force Comparison between strain measured and calculated by FEM

Figure 6 :

 6 Figure 6: Strain distribution measurement.


Farzan Kalantari

Edward Lank
email: lank@uwaterloo.ca

Yosra Rekik

Laurent Grisoni

Frédéric Giraud
email: frederic.giraud@univ-lille1.fr

Determining the Haptic Feedback Position for Optimizing the Targeting Performance on Ultrasonic Tactile Displays

Alongside questions of how to create haptic effects on displays via alternative hardware, recent work has explored rendering options with respect to haptic effects, i.e. when and where to provide haptic feedback. In particular, recent work by Zhang and Harrison for electrostatic haptic feedback noted that the optimal technique for haptic feedback during interaction is the Fill technique, where haptic effects are rendered at all times when a user's finger is within the bounds of the target. In this paper, we explore whether this result generalizes to an alternative haptic rendering technology that uses ultrasonic vibrations to create haptic sensations, a technique called the "Squeeze Film Effect". In contrast to prior work, our results indicate that positioning the haptic feedback as a discrete linear stimulus centred on the target provides an optimal trade-off between speed, accuracy, and user preference. We highlight the implications of this work to the generalizability of haptic feedback: Haptic feedback can improve time, errors, and user satisfaction during interaction, but only if the correct form of feedback is used for the specific haptic effect generated by the hardware.

I. INTRODUCTION

Modern devices such as smartphones, tablets, and ultra portable computers frequently leverage touch as a primary input modality. Touch is an attractive input modality because the dexterity and sensitivity of our fingers makes possible a wide range of fine-grained manipulations and subtle variations of force. While touchscreen devices originally sensed touch as a binary state -touching or not-touching -recently we see ever-finer capture of characteristics of touch. For example, Android devices sometimes examine touch contact area to provide an estimate of pressure and recent Apple touch sensors have incorporated force sensors to accurately capture force applied during input. On the other hand, while consumer devices have begun to use additional information for touch input, these devices still rarely provide fine-grained haptic output despite established research that demonstrates the need for haptic output, i.e. haptic feedback, to enhance efficiency and realism during common interaction tasks [START_REF] Buxton | Issues and Techniques in Touchsensitive Tablet Input[END_REF].

Researchers exploring fine-grained haptic output typically explore various forms of dynamic haptic feedback to enhance input on touchscreen devices. Within this space of dynamic haptic feedback, four main technologies are used. First, vibrotactile actuators such as solenoids, vibrotactile coils, and ERM motors can be utilized for tactile rendering on touchscreens [START_REF] Choi | Vibrotactile Display: Perception, Technology, and Applications[END_REF]. These actuators are used presently on smartwatches, mobile phones and tablets, but typically provide for a device, on-or-off sensation. Alongside vibrotactile actuation, two techniques, "electrostatic-vibration" [START_REF] Bau | TeslaTouch: Electrovibration for Touch Surfaces[END_REF], [4] and "electroadhesion" [START_REF] Shultz | Surface haptics via electroadhesion: Expanding electrovibration with Johnsen and Rahbek[END_REF] use electrostatic force generated, respectively, by applying a voltage to the screen surface or by applying DC excitation of the tactile display. Both of these techniques increase the friction between the finger and the interaction surface when activated, thus varying the perceived stickiness of the surface. Finally, a fourth type of haptic feedback uses ultrasonic vibrations to generate an air-gap between a user's finger and the display to reduce friction when activated, a phenomenon called the "squeeze film effect".

In 2015, Zhang and Harrison [START_REF] Zhang | Quantifying the Targeting Performance Benefit of Electrostatic Haptic Feedback on Touchscreens[END_REF] examined how different haptic rendering techniques (shown in Fig. 3) affect target acquisition times and error rates for one type of haptic effect, electrostatic haptic feedback. However, given the significant differences between haptic effects, it seems reasonable to assume that different types of haptic effects might have different optimal renderings.

In this paper, we study haptic rendering techniques for an alternative haptic effect, the squeeze film effect. We describe a study replicating the experimental design of Zhang and Harrison [START_REF] Zhang | Quantifying the Targeting Performance Benefit of Electrostatic Haptic Feedback on Touchscreens[END_REF]. We show that, for haptic feedback displays based on the squeeze film effect, the optimal rendering technique of Zhang and Harrison, haptic Fill, is not optimal for both time and error rate. We find instead that, balancing time and error, an alternative strategy called line centre, i.e., applying a haptic effect when the user's finger's contact point is at the centre of the target, best balances time and error rate.

II. RELATED WORK A. The Squeeze Film Effect

While explaining all dynamic tactile rendering techniques is beyond the scope of this note, our specific hardware system utilizes a specific tactile rendering technique called the "squeeze-film effect" (Figure 1). The squeeze-film effect is an over-pressure phenomenon while generates an ultrathin air film between two surfaces, similar to the way an air hockey table allows the puck to float with low friction. To create this air gap, an ultrasonic vibration of a few micrometers is applied to the surface. This pushes the surfaces slightly apart, allowing one surface to slide more easily across the other. In haptic rendering, the surfaces are the display screen which vibrates and the user's finger which is pushed slightly away from the surface by the vibration as described in [START_REF] Wiesendanger | Squeeze film air bearings using piezoelectric bending elements[END_REF]- [START_REF] Winfield | T-PaD: Tactile Pattern Display Through Variable Friction Reduction[END_REF]. An implication of squeeze film effect rendering is that, unlike electrostatic techniques which increase friction, squeeze film haptic rendering reduces friction when active.

B. Interaction Techniques with Tactile Feedback on Touchscreens

It has been shown in [START_REF] Casiez | Surfpad: Riding Towards Targets on a Squeeze Film Effect[END_REF], [START_REF] Levesque | Enhancing Physicality in Touch Interaction with Programmable Friction[END_REF] that haptic feedback based on friction reduction using the squeeze film effect is able to improve the performance of interaction techniques. Liu et al. [START_REF] Liu | Effect of Electrostatic Tactile Feedback on Accuracy and Efficiency of Pan Gestures on Touch Screens[END_REF] have recently investigated the effect of electrostatic vibration for evaluating the accuracy and efficiency of pan gestures on haptic touch screens. In literature we can also find several studies using haptic pens for improving the performances of different interaction techniques as explained in [START_REF] Forlines | Evaluating Tactile Feedback and Direct vs. Indirect Stylus Input in Pointing and Crossing Selection Tasks[END_REF], [START_REF] Poupyrev | Haptic Feedback for Pen Computing: Directions and Strategies[END_REF].

In recent work, Zhang and Harrison [START_REF] Zhang | Quantifying the Targeting Performance Benefit of Electrostatic Haptic Feedback on Touchscreens[END_REF] presented the first study on how best to use electrostatic vibration to enhance targeting. Specifically, they showed that, both from the perspective of time and errors, providing a tactile sensation across the entire target -electrostatic Fill -was the best strategy for designing dynamic haptic feedback as opposed to providing more localized haptic feedback (e.g. along one edge, in the centre, or in the background). In our research, we work with a dynamic haptic feedback system that leverages the squeeze film effect to provide dynamic haptic feedback. Furthermore, because the squeeze film effect works differently than electrostatic vibration -reducing rather than increasing friction -it was unclear to us whether, given the different sensations, electrostatic Fill would remain the optimal technique to enhance targeting. Therefore, in this paper we have applied the same comparative approach and procedure as in [START_REF] Zhang | Quantifying the Targeting Performance Benefit of Electrostatic Haptic Feedback on Touchscreens[END_REF] to determine the positioning of haptic feedback for improving the user's targeting performance on ultrasonic based touchscreens using the squeeze film effect.

III. EXPERIMENT

With the exception of our haptic display technology, to preserve experimental validity we use the same experimental design of Zhang and Harrison [START_REF] Zhang | Quantifying the Targeting Performance Benefit of Electrostatic Haptic Feedback on Touchscreens[END_REF]. We use an identical number of participants and an identical set of haptic feedback techniques while substituting squeeze film effect haptic output. For completeness, this section describes our apparatus, participants, and method. A. Apparatus

We used E-ViTa (Enhanced Visual-Tactile Actuator), a tactile feedback tablet based on ultrasonic vibrations to create the squeeze-film effect for haptic rendering [START_REF] Vezzoli | Texture Rendering Strategies with a High Fidelity -Capacitive Visual-Haptic Friction Control Device[END_REF]. A sine-wave grating with a spatial period of 1000 µm and an amplitude of 1.25 µm was applied to generate haptic feedback sensation to a user's fingertip. E-ViTa is developed on a Banana Pi, a single-board computer (Shenzhen LeMaker Technology Co. Ltd, China) with a 1 GHz ARM Cortex-A7, dual-core CPU and 1 GB of RAM working in parallel with STM32f4 microcontroller (STMicroelectronics, France). The communication between the microcontroller and the single board computer is provided via the Serial Peripheral Interface (SPI) bus at 10 kHz. This single-board computer is connected to a 12.5cm capacitive touchscreen (Banana-LCD 5"-TS, MAREL, China) for detecting the user's finger position on the display with a sampling frequency of 62 Hz.

Ten 14 × 6 × 0.5 mm piezoelectric cells actuate a 154 × 81 × 1.6 mm fixed glass plate, resonating at 60750 Hz with a half wavelength of 8 mm. A power electronic circuit converts a 12V DC voltage source into an AC voltage, controlled in amplitude and frequency and supplied to the piezoelectric cells. The microcontroller synthesizes a pulsewidth modulation (PWM) signal to drive a voltage inverter that actuates the piezoceramics. The detailed structure of the E-ViTa haptic display is illustrated in Figure 2.

B. Participants

Twenty healthy volunteers (9 females) from the age of 24 to 37 and the mean age of 29.4 participated in our experiment. All participants were right-handed. They were all naive to the aim of the study and had no previous experience with haptic feedback displays. Participants were wearing active noise-cancelling headphones (Panasonic RP-DJS200, Japan) during the experiment, while Gaussian white noise was played at a comfortable listening level in order to prevent potential interference from auditory cues. The experiment took on average approximately 40 minutes.

C. Experimental Design and Variables

The experiment was a 5 × 3 × 5 repeated measures within-subjects design. To determine significant main effects, repeated measures analysis of variance was applied for the following independent variables: feedback (No Feedback, Line Leading Edge, Line Background, Line Center and Fill), target width (SMALL: 30 pixels = 4.125mm, MEDIUM:

D. Procedure and Task

The experiment proceeded as follows. First, a brief description of our task as well as all the necessary instructions for interacting with our haptic feedback display were given to each participant. Participants were given about 10 minutes of training and familiarization before beginning the main task. We used a drag and drop task identical to past experiments contrasting haptic rendering techniques [START_REF] Zhang | Quantifying the Targeting Performance Benefit of Electrostatic Haptic Feedback on Touchscreens[END_REF]. As illustrated Fig. 4. An example setup of the trials in our experiment in Figure 4, for each trial, the participant was required to correctly select the blue rectangular virtual object. Then the selected object had to be dragged and successfully dropped on a specified target, a red virtual object (Figure 3). The black objects were considered distractors. The red target became green to confirm that the trial had been successfully completed and the participant proceeded to the next trial. The trials in which participants were not able to perform the task correctly were marked as errors. The trials were repeated for each of the five haptic feedback options (No Feedback, Line Leading, Line Background, Line Center, and Fill) with the different target widths and distances as noted in the section on Experimental Design.

IV. RESULTS

To understand the effect of different haptic rendering techniques, we analyze the effect of independent parameters on error rate, number of failed attemps, number of overshoots and trial time (our dependent measures). We also analyzed the subjective responses of participants vis a vis the five haptic feedback options. While our primary interest is in determining the effect that haptic feedback options have on these dependent measures, to further determine potential interaction effects between indepdent variables, all analyses were multi-way ANOVA. Tukey tests were used post-hoc when significant effects were found. In the following, we report the results for each of the dependent variables.

A. Error Rate

Targets that were not selected on first attempt were marked as errors. There were significant main effects of target width (F 2,28 =54.76, p< 0.0001) on error rate but there was also a significant effect of target width × distance (F 8,112 = 2.63, p = 0.01) and distance × feedback (F 16,224 = 2.28, p<0.005) interactions. Post-hoc tests revealed that for SMALL target width, performance deteriorated more significantly among decreasing distance (p< 0.05). Similarly, we found that for all distance conditions, performance deteriorated more significantly among decreasing target width (p< 0.05). Importantly, we found that for the Fill condition, error rate was significantly higher for LONGEST distance (mean 10.22 %, S.D 4.24%) than for SHORTEST distance (mean 23.11 %, S.D 7.77%) (p< 0.05).

The most compelling haptic feedback position, with respect to error rate was Line Background (mean 13.06%, S.D 2.51%) followed by Line Center (mean 14.57%, S.D 2.94%), Line Leading Edge (mean 17.06%, S.D 2.77%), Fill (mean 18.22%, S.D 2.90%) and No Feedback (mean 20.44%, S.D 3.16%) condition (see Figure 5). These results are in contrast to the findings of [START_REF] Zhang | Quantifying the Targeting Performance Benefit of Electrostatic Haptic Feedback on Touchscreens[END_REF] when using electro-static based haptic display in which the Fill condition was found to provide the best performance. However and similar to [START_REF] Zhang | Quantifying the Targeting Performance Benefit of Electrostatic Haptic Feedback on Touchscreens[END_REF], post-hoc tests showed no significant differences between different line haptic feedback types.

B. Number of Failed Attempts

We found that there was a significant main effect of target width (F 2,28 = 5.88, p< 0.001) on number of failed attempts. Post-hoc tests revealed that the number of failed attempts is significantly higher with SMALL target width than with MEDIUM or LARGE target widths (p< 0.05). We correlated these results with comments from participants who felt that selecting and dragging virtual objects with small size was difficult. The major reason for these difficulties (as explained in [START_REF] Kalantari | Finding the Minimum Perceivable Size of a Tactile Element on an Ultrasonic Based Haptic Tablet[END_REF]) is due to the limitation of the object size which can be accurately perceived by the user's finger on ultrasonic (squeeze-film effect) haptic displays.

C. Number of Overshoots

Number of overshoots were measured as the number of times when the participants enter and leave the target without selecting it. There was a significant main effect of target width (F 2,28 = 10.63, p< 0.05) on overshoots. Post-hoc tests revealed that the number of overshoots is significantly larger with SMALL target width than with MEDIUM or LARGE target widths (p< 0.05).

D. Trial Time

Trial time was measured from the first control area movement, to target successfully selected. There were significant main effects of target width (F 2,28 = 120.04, p< 0.0001) and distance (F 4,56 = 99.78, p< 0.0001) on trial time, but there was also a significant main effect of target width × distance (F 8,112 = 2.79, p < 0.001) interaction. Post-hoc tests revealed that the trial time increased more significantly for the SMALL target width among decreasing distance (p< 0.05). Similarly, the trial time increased more significantly for the shortest, short and the medium distance respectively among decreasing target width (p< 0.05). The best feedback position, with respect to trial time was Line Center followed by Line Background, Line Leading Edge and Fill which lowered the trial time by respectively 18.84%, 15.04%, 12.75% and 5.45% compared to No Feedback condition (see Figure 6). For error rate, these results are in contrast to the findings of [START_REF] Zhang | Quantifying the Targeting Performance Benefit of Electrostatic Haptic Feedback on Touchscreens[END_REF] in the case of electrostatic haptic displays in which the Fill condition has been found to provide the shortest trial time. We have also found a significant main effect of Line Center, Line Background and Line Leading Edge feedback conditions compared to No Feedback (p< 0.05) on trial time.

E. Qualitative Ranking

Participants were also asked to rank the five haptic feedback positions after completing the experiment. Line Center was the most preferred feedback with an average score of 4.2 (SD = 0.94), followed by Line Background with an average score of 3.8 (SD = 1.14), Line Leading Edge with an average score of 3 (SD = 0.96), and Fill feedback with an average score of 2.4 (SD = 0.73). The No Feedback condition received the lowest average score of 1.53 (SD = 1.40). These results present an interesting contrast with Zhang and Harrison [START_REF] Zhang | Quantifying the Targeting Performance Benefit of Electrostatic Haptic Feedback on Touchscreens[END_REF], where Fill was most preferred and Line Center and Line Background least preferred.

We correlate these results with the comments of participants who felt that the three line haptic feedback conditions had better performance, required less concentration, and were less frustrating for accomplishing the experimental task. In particular one participant noted that he or she was "comfortable with the line haptic feedback particularly in order to select and drag the small size of objects and ... to select the target". Another found advantages in precision, i.e. that "when the tactile feedback is a line, I think that I can select the target even if my eyes are closed... those tactile feedback conditions tell me that there is either a distractor or the target, so I just need to count to know whether I'm on the target or not!". In contrast, for the Fill condition, the participants felt that it was cumbersome and required more concentration and time. One participant noted that the "high amount of vibrations under my finger is not very pleasant and I'd prefer the other haptic feedback designs". Several participants also found a delay in notification for the Fill technique, with one claiming that he or she "preferred the [line-based forms] of haptic feedback [because they] warned me before arriving at the target", thus increasing accuracy. Finally one participant noted that he or she was "frustrated with [Fill] feedback... [because] it disturbs me and [requires] more concentration".

Despite the relative advantages of Line Centre/Background over the Fill condition, all participants found that haptic feedback of any form was an advantage. In the case of No Feedback, the participants declared that, "Without any haptic feedback [it] is definitely harder to select and drag the objects, specially for the small sizes... I need lots of concentration in order not to pass the target and finish each trial successfully" and that, "If I wanted to do the task with a high velocity of touching the object with no haptic feedback, it was kinda impossible to finish each trial without several attempts and repetitions! Therefore it became a bit boring after several attempts."

V. DISCUSSION

While all haptic feedback techniques clearly perform better than the No Feedback condition, analyzing our haptic feedback techniques using both qualitative ranking and quantitative effects, the main take-away from this work is that Line Center seems an optimal feedback technique balancing user preference (most preferred), speed (fastest selection time) and error rate (second lowest error rate) when using squeeze film effect haptic rendering techniques. Line Background and Line Leading Edge might also be possible rendering options for haptic effects. Finally, for squeeze file effects, Fill seems a poor choice both from the perspective of user preference (least preferred), time (slowest), and errors (highest).

As we noted before, for a competing haptic feedback technology, electrostatic vibration, Zhang and Harrison found that Fill was the best technique and that Line Center and Line Background were typically poor performers in time, error, and user preference when compared to Fill.

Alongside haptic rendering techniques, we note that our experiment results in a higher error rate than Zhang and Harrison [START_REF] Zhang | Quantifying the Targeting Performance Benefit of Electrostatic Haptic Feedback on Touchscreens[END_REF]. In their work, they obtained an error rate of approximately 8%, compared to our error rate of 16.67%. While it is possible that haptic rendering differences may result in higher or lower error rates, we believe that other potential confounds may explain this discrepancy. These include factors such as touchscreen performance (Zhang and Harrison used 3M Microtouch capacitive panels over a standard LCD screen whereas we used the E-Vita, a standalone portable device) and participants (Zhang and Harrison's participants were significantly younger than ours -adults average age 24 versus adults average age 29 in our experiments). This is particularly true because of the discrepancy in the No Feedback condition. If haptic effects were responsible for increased error rate, one would expect that the No Feedback conditions would remain similar.

While we were surprised by these results, it may be the case that post-hoc rationale exists for the contradictory effects. After all, the squeeze film effect serves to reduce friction when active, whereas electrostatic techniques then to increase friction when active. It may be the case that participants can effectively sense increase in friction, thus arguing for the advantage of background based feedback techniques. However, the overall advantage of Line Center are not fully explained by this rationale. We believe that the overall message of this work is simply that different haptic technologies produce different physical sensations for the end user. These differences in physical sensation limit the overall generalizability of rendering options between competing technologies. As new techniques are developed, additional work will be required to explore how best to perform haptic feedback such that speed and accuracy are maximized.

One additional data point that both Zhang and Harrison [START_REF] Zhang | Quantifying the Targeting Performance Benefit of Electrostatic Haptic Feedback on Touchscreens[END_REF] and our work presented here demonstrates is that effective haptic feedback continues to show advantages over no haptic feedback. Optimal haptic rendering techniques exhibit a 15 -25% improvement in both speed and error rate. However, poor haptic rendering choices significantly effect these performance improvements. For the Squeeze Film Effect (our technique), choosing Fill haptic feedback results in less than 10% improvement, and, for electrostatic vibration (Zhang and Harrison's technique), choosing Line Center haptic feedback results in almost no improvement in time or error. As a result, the argument for haptic feedback is nuanced: Haptic feedback appears to improve time, errors, and user satisfaction, but only if the correct form of feedback is used for the specific haptic feedback technology generated by the hardware.

VI. CONCLUSION

We conducted an experiment to determine the best tactile feedback position on ultrasonic (squeeze-film effect) haptic displays for targeting tasks. Our results demonstrate that the Line Center condition provides the best balance of improved speed, accuracy, and user satisfaction compared to other techniques. We also note that the contrast between these results and past research on haptic feedback techniques [START_REF] Zhang | Quantifying the Targeting Performance Benefit of Electrostatic Haptic Feedback on Touchscreens[END_REF] advocates for a need for caution when attempting to generalize results across different hardware configurations.

Fig. 1 .

 1 Fig. 1. The principle of squeeze film effect. Ultrasonic vibration creates an air gap which reduce the friction.

Fig. 2 .

 2 Fig.2. The structure of E-ViTa haptic feedback display[START_REF] Vezzoli | Texture Rendering Strategies with a High Fidelity -Capacitive Visual-Haptic Friction Control Device[END_REF]

Fig. 3 .

 3 Fig. 3. Four haptic feedback and No Feedback designs in our experiment (adapted from [6])

Fig. 5 .

 5 Fig. 5. Average error rate cross feedback conditions. Error bars are standard error across participants (95% CI).

Fig. 6 .

 6 Fig. 6. Average trial time cross feedback conditions. Error bars are standard error across participants (95% CI).

ACKNOWLEDGMENTS

The authors would like to thank Nicolas Bremard for his useful help in our study. This work is partially funded by European ERDF grants (IRCICA, CPER MAUVE) and ANR funding agency. Researcher support was also provided by the Invited Researcher Program of Région Hauts-de-France.

*This work is partially funded by European ERDF grants (IRCICA, CPER MAUVE) and ANR funding agency.


Jacqueline Argant

C Beaudouin

Y Deng-Amiot

Gourd des Aillères (Sauvain). Palynological study of the sequence 260-655 cm

Gourd des Aillères (Sauvain). Palynological study of the sequence 260-655 cm (J. Argant 1 , C. Beaudoin 2 , Y. Deng-Amiot 3 ) 1 Aix Marseille Université, LAMPEA, Maison Méditerranéenne des Sciences de l'Homme, 5 rue du château de l'horloge, BP 647, 13094, Aix-en-Provence, France 2 Pollen & Cores 3 Palynoscope, 34 rue Charles Darwin, 38230 Charvieu-Chavagneux

The palynological record obtained for the Late Glacial period and the beginning of the Holocene can be divided in 7 main zones with 5 subzones (Fig. 1).

LPAZ 1 (depth 656-583 cm, from about 15400 cal. BP to 14600 cal BP): Oldest Dryas, steppic herbs and pioneer shrubs; archaeological period: Palaeolithic. The occurrence of Quercus pollen as well as mesophilous trees, puts forward the question of the origin of this pollen, incompatible with the climatic conditions of this period. Several assumptions can be considered: regional input of pollen coming from lower altitudes; long way transport of pollen from southern countries; or as often observed, reworking of ancient sediments. This latter interpretation is probable, considering the presence of sand inside the clay deposits (cf. macro remains study, A-M. Dendievel) LPAZ 2 (depth 583-550 cm; from about 14600 to 14100 cal. BP): Bølling, increase of Juniperus and Betula; archaeological period: Palaeolithic.

The very rapid arrival of Juniperus is closely followed by Betula and the decline of Pinus. As for the herbs, pollen of Artemisia and of the other steppic plants is decreasing. The landscape remains open. Marsh and aquatic vegetation expands, including algae (Pediastrum). Between 560 and 570 cm (from 14400 to 14300 cal. BP) Pinus, Betula, Juniperus are rapidly decreasing, which indicates possibly the Intra Bølling Cold Phase detected at this time in the ice cores of Greenland [START_REF] Stuiver | The GISO2 δ 18 O climate record of the past 16500 years and the role of the sun, ocean and volcanoes[END_REF].

LPAZ 3 (depth 550-532 cm, from about 14100 to 13800 cal. BP): Dryas II (Older Dryas); archaeological period: Palaeolithic/Epipalaeolithic Juniperus and Betula clearly decrease while Pinus progression stops. Artemisia, Chenopodiaceae and particularly Apiaceae, Plantago and the Cyperaceae do increase. Wet prairies do develop close to the lake. All this clearly demonstrate a cooling corresponding to the Older Dryas.

LPAZ 4 (depth 532-467 cm; from about 13800 to 12800 cal. BP): Allerød; archaeological period: Epipaleolithic. This LPAZ is subdivided in three subzones. LPAZ 4a, depth 532 to 492 cm, age about 13800 to 13000 cal. BP: Pinus develops slowly and coexists with birch and juniper which remain stable up to depth 500 cm. Artemisia and other steppic plants decrease, while tall herbs expand (e.g. Apiaceae).

During the following LPAZ 4b and 4c there are no big changes among the herbs. Pinus takes the first place but its percentages remain low (often < 30%). Betula and Juniperus reduce significantly. During LPAZ 4b (depth 492 to 480 cm age about 13000 to 12900 cal. BP) we can observe two peaks in the curve of Pinus. One of these peaks could correspond to the Gerzensee oscillation (Intra Allerød Cold Phase).

LPAZ 5 (depth 467-347 cm, from about 12800 to 11800 cal. BP): Younger Dryas; archaeological period: Epipaleolithic.

Artemisia values increase slightly, as well as Apiaceae, and Plantago. Pediastrum values are strongly reduce pointing to changes in the lake (e.g. a reduced surface). All this suggests climatic conditions cooler than during the LPAZ 4, but without a clear impact on the vegetation environment.

LPAZ 6 (depth 347-290 cm; from about 11800 to 9960 cal. BP): Preboreal; archaeological period: Mesolithic.

This LPAZ is characterized by the clear increase in AP, particularly Pinus and Betula and by a continuous curve of Quercus, Corylus and then Ulmus. In the same time Artemisia, Poaceae and steppic plants decrease while Rumex and the Ranunculaceae expanded around the lake; hydrophytes and algae suggest a free water surface.

LPAZ 7 (depth 290-...analysis in progress): Boreal. This LPAZ is characterized by the classical rapid and strong expansion of Corylus, contemporaneous with the collapse of Pinus and the establishment of Quercus and Ulmus. A marsh, occupied by Cyperaceae and other hygrophilous plants, takes the place of the lake.

  Artemisia, Chenopodiaceae, Helianthemum, Thalictrum, Plantago, various Asteraceae and Cyperaceae. Some shrubs are also growing: Ephedra, Betula nana, Juniperus. Salix appears sporadically. Pinus is relatively abundant but doesn't exceed 30%. Some water plants and Botryococcus indicate a free water surface around which Cyperaceae developed. LPAZ 1b (depth 606-583 cm; from about 14900 to 14600 cal. BP): Pinus and Artemisia decrease significantly, while other herbs increase (Poaceae, Asteraceae, Plantago), Cyperaceae develop and Typha/Sparganium arises.

	Two subzones:
	LPAZ 1a (depth 656-606 cm; about from 15400 to 14900 cal. BP): Herbs are dominating with
	Poaceae,