Dirk V Arnold

Nikolaus Hansen
email: nikolaus.hansen@lri.fr

A (1+1)-CMA-ES for Constrained Optimisation

Keywords: I.2.8 [Problem Solving, Control Methods, and Search], I.2.6 [Learning]: Parameter Learning, G.1.6 [Optimization]: Constrained Optimization Stochastic optimisation, constraint handling, variable metric algorithm, evolution strategy

This paper introduces a novel constraint handling approach for covariance matrix adaptation evolution strategies (CMA-ES). The key idea is to approximate the directions of the local normal vectors of the constraint boundaries by accumulating steps that violate the respective constraints, and to then reduce variances of the mutation distribution in those directions. The resulting strategy is able to approach the boundary of the feasible region without being impeded in its ability to search in directions tangential to the boundaries. The approach is implemented in the (1 + 1)-CMA-ES and evaluated numerically on several test problems. The results compare very favourably with data for other constraint handling approaches applied to unimodal test problems that can be found in the literature.

INTRODUCTION

Numerous constraint handling approaches have been proposed for use in evolutionary algorithms (EAs). A list of references 1 to constraint handling techniques used with EAs compiled by Coello Coello at the time of this writing contains more than one thousand entries. Among the most com-monly employed approaches are algorithms that rely on immediate resampling of infeasible candidate solutions, penalty functions, or multiobjective techniques. A recent survey [START_REF] Mezura-Montes | Constraint-handling in nature-inspired numerical optimization: Past, present, and future[END_REF] provides a comprehensive overview.

Despite their strong performance in black box optimisation benchmarking exercises focusing on unconstrained realvalued problems [START_REF] Hansen | Comparing results of 31 algorithms from the black-box optimization benchmarking BBOB-2009[END_REF], little research has been done on constraint handling techniques for covariance matrix adaptation evolution strategies (CMA-ES). The objective of this paper is to develop a simple and robust constraint handling approach for use in CMA-ES, and to incorporate it in the (1 + 1)-CMA-ES. We consider the problem of minimising f (x) subject to inequality constraints gj(x) ≤ 0 for j = 1, . . . , m. Function f : R n → R is referred to as the objective function; functions gj : R n → R are the constraint functions. In contrast to many existing constraint handling approaches, we do not make the assumption that it is possible to obtain meaningful objective function values for infeasible candidate solutions. Moreover, our strategy does not make use of constraint function values other than for the purpose of determining feasibility of a candidate solution. That is, even though the constraint functions yield real values, our algorithm only makes use of the binary information whether a constraint is violated or not. As a result, our approach enjoys invariance properties that algorithms that rely on quantifying the degree of constraint violation do not. See Hansen et al. [START_REF] Hansen | Impacts of invariance in search: When CMA-ES and PSO face ill-conditioned and non-separable problems[END_REF] for a discussion of the importance of invariance properties in black box optimisation.

The key idea underlying our algorithm is to approximate the directions of the normal vectors of the constraint boundaries in the vicinity of the current candidate solution by accumulating steps that violate the respective constraints. Subsequently reducing variances of the distribution of offspring candidate solutions in those directions enables the strategy to closely approach the boundary of the feasible region without inhibiting its ability to search in orthogonal directions.

The remainder of this paper is organised as follows. Section 2 discusses constraint handling techniques used in connection with evolution strategies and then summarises the main ideas underlying the (1+1)-CMA-ES for unconstrained optimisation. Section 3 introduces the novel constraint handling approach that is the subject of this paper and describes its incorporation in the (1 + 1)-CMA-ES. Section 4 experimentally evaluates the algorithm on several test functions and compares its performance with that of other EAs for constrained optimisation. Section 5 concludes with a discussion of the results and directions for future research.

BACKGROUND

This section first reviews constraint handling techniques proposed in connection with evolution strategies. It then provides a brief review of the (1 + 1)-CMA-ES, which forms the basis of the approach introduced in Section 3.

Related Work

Two of the simplest constraint handling techniques used in connection with evolution strategies are discussed by Oyman et al. [START_REF] Oyman | An alternative constraint handling method for evolution strategies[END_REF]. One approach resamples infeasible candidate solutions until a feasible one has been generated. The other approach prefers feasible candidate solutions over infeasible ones, and it prefers those candidate solutions with smaller overall degrees of constraint violation in comparisons among infeasible candidate solutions. Neither approach requires computing objective function values for infeasible candidate solutions. In the case of the (1+1)-ES, which adapts its step size based on observed success probabilities, the difference between the two approaches is highly significant. Fig. 1(a) illustrates a linear problem with a linear constraint. We refer to the angle between the normal vector of the constraint boundary and the gradient vector of the objective function as the constraint angle. If the parental candidate solution is in close proximity to the constraint plane, then small constraint angles result in a small probability of generating successful offspring. The approach that resamples infeasible candidate solutions does not consider those in the calculation of the success probability and thus does not reduce the step size in response to infeasible candidate solutions. In situations where there are multiple constraints active at the same time, this may result in generating very large numbers of infeasible candidate solutions before a feasible one is found. The approach that ranks feasible candidate solutions higher than infeasible ones does consider infeasible candidate solutions in its calculation of the success probability and systematically reduces the step size, resulting in convergence to a non-stationary point of the objective. This issue was first pointed out by Schwefel [START_REF] Schwefel | Evolution and Optimum Seeking[END_REF] and has since been studied analytically by Arnold and Brauer [START_REF] Arnold | On the behaviour of the (1 + 1)-ES for a simple constrained problem[END_REF]. Fig. 1(b) illustrates that small constraint angles may arise in connection with nonlinear constrained optimisation problems.

Runarsson and Yao [START_REF] Runarsson | Stochastic ranking for constrained evolutionary optimization[END_REF] propose stochastic ranking as an approach for weighting differences in objective function values and constraint violations against each other. The approach requires the ability to obtain objective function values for infeasible candidate solutions.

Kramer et al. [START_REF] Kramer | A new mutation operator for evolution strategies for constrained problems[END_REF] propose the use of biased mutations for solving constrained optimisation problems. They do not evaluate their approach in an evolution strategy that is invariant with regard to rotations of the coordinate system.

Kramer and Schwefel [START_REF] Kramer | On three new approaches to handle constraints within evolution strategies[END_REF] propose and experimentally evaluate several constraint handling techniques for evolution strategies, ranging from adaptively lowering a lower bound on the global step size of the strategy to an algorithm evolving populations of feasible and infeasible candidate solutions in tandem and one that involves a nested strategy that adapts rotation angles of the mutation ellipsoid. All of those have in common that no objective function values are computed for infeasible candidate solutions.

Kramer et al. [START_REF] Kramer | Surrogate constraint functions for CMA evolution strategies[END_REF] are the first to propose a constraint handling approach specifically for CMA-ES. Similar to our approach, they learn a model of the constraint function and use that model to adapt the covariance matrix that governs the distribution of offspring candidate solutions. However, both the nature of the model for the constraint functions and the covariance matrix update differ. Our model is simpler and obtained on the fly, without the need for additional constraint function evaluations. The covariance matrix update in [START_REF] Kramer | Surrogate constraint functions for CMA evolution strategies[END_REF] aims to rotate the covariance matrix, whereas ours acts to reduce variances in directions where constraint violations have been observed.

Collange et al. [START_REF] Collange | Multidisciplinary optimisation in the design of future space launchers[END_REF] introduce a constraint handling approach for CMA-ES that strives to ensure that within some given number of iterations the population contains at least one feasible candidate solution. Their approach relies on constraint function values and a user defined constraint value threshold. No results from an evaluation of the approach on test functions are provided.

(1+1)-CMA-ES

The (1 + 1)-CMA-ES introduced by Igel et al. [START_REF] Igel | A computational efficient covariance matrix update and a (1+1)-CMA for evolution strategies[END_REF] is a variant of the (1 + 1)-ES that adapts the entire covariance matrix of its offspring distribution in addition to its global step size. As the covariance matrix C is positive definite, Cholesky decomposition yields n×n matrix A such that C = AA T , and offspring candidate solutions y are generated as

y = x + σAz (1)
where x is the parental candidate solution, z ∈ R n has standard normally distributed components, and σ is the global step size of the strategy. The strategy maintains an exponentially fading record s ∈ R n of successful steps that is referred to as the search path. Upon generating a successful offspring candidate solution it performs covariance matrix update

C ← (1 -c + cov )C + c + cov ss T (2)
where c + cov ∈ (0, 1) is a constant. Rather than working with the covariance matrix and performing a Cholesky decomposition in every iteration of the algorithm, Igel et al. [START_REF] Igel | A computational efficient covariance matrix update and a (1+1)-CMA for evolution strategies[END_REF] show that equivalently, matrix A can be updated according to

A ← p 1 -c + covA + p 1 -c + cov w 2 0 @ s 1 + c + cov w 2 1 -c + cov -1 1 A sw T (3)
where w = A -1 s. Suttorp et al. [START_REF] Suttorp | Efficient covariance matrix update for variable metric evolution strategies[END_REF] provide an analogous update of the inverse of A that removes the need for matrix inversion and makes it possible to implement the update with Θ(n 2 ) cost per iteration.

A variant of the (1 + 1)-CMA-ES proposed by Arnold and Hansen [START_REF] Arnold | Active covariance matrix adaptation for the (1 + 1)-CMA-ES[END_REF] incorporates the active covariance matrix update due to Jastrebski and Arnold [START_REF] Jastrebski | Improving evolution strategies through active covariance matrix adaptation[END_REF] into the strategy. The key observation is that in situations where there are isolated large eigenvalues of the Hessian matrix of the objective function, many iterations are required before the update in Eq. ( 2) yields appropriate step sizes in the directions of the corresponding eigenvectors. Rather than letting variances in those directions decay through repeated multiplication with (1 -c + cov ) < 1, in situations where the offspring candidate solution is especially unsuccessful (in the sense that it is inferior to its kth order ancestor for some k > 1), the strategy performs covariance matrix update

C ← (1 + c - cov )C -c - cov (Az)(Az) T (4)
where c - cov ∈ (0, 1) is a constant. Arnold and Hansen [START_REF] Arnold | Active covariance matrix adaptation for the (1 + 1)-CMA-ES[END_REF] show that the update can equivalently be accomplished by updating matrix A according to

A ← p 1 + c - covA + p 1 + c - cov z 2 0 @ s 1 - c - cov z 2 1 + c - cov -1 1 A Azz T (5)
and they also provide an update of the inverse of A that allows performing updates with Θ(n 2 ) cost per iteration.

ALGORITHM

The key idea underlying our constraint handling approach is to reduce variances of the distribution of offspring candidate solutions in the directions of the normal vectors of constraint boundaries in the vicinity of the current parental candidate solution. For that purpose, for each of the m constraints we maintain an exponentially fading record vj , j = 1, . . . , m, of steps that have violated the constraint. Those vectors are initialised to be zero and, in those iterations where the jth constraint is violated, updated according to

vj ← (1 -cc)vj + ccAz . (6)
We refer to the vj as constraint vectors. Accumulation acts as a low-pass filter and ensures that components of Az that are tangential to the local constraint boundary average out in the mean. Parameter cc ∈ (0, 1) determines how quickly the information present in the constraint vectors fades.

(a) (c) (b)
In those iterations where the offspring candidate solution is infeasible, the Cholesky factor of the covariance matrix is updated according to

A ← A - β P m j=1 1 g j (y)>0 m X j=1 1 g j (y)>0 vj w T j w T j wj (7)
where wj = A -1 vj and 1 g j (y)>0 equals one if gj(y) > 0 and zero otherwise. The update is akin to that in Eq. ( 5) with the constraint vectors vj replacing Az. Parameter β in Eq. ( 7) controls the size of the updates similar to the way that c - cov does in Eq. ( 5). However, while the update in Eq. ( 5) is of rank one, that in Eq. ( 7) is a multiple-rank update if multiple constraints are violated. In contrast to the update in Eq. ( 5), there is no multiplication of matrix A with a scalar greater than one in order to increase variances in directions other than those implicit in the constraint vectors. Also in contrast to the active covariance matrix update described in Section 2.2, we do not have an update of the inverse of matrix A that would allow performing a step with cost quadratic in n. Instead, the computational cost of the update is in O(n 3 + mn 2 ). Fig. 2 illustrates the effect of reducing the variance of the distribution of offspring candidate solutions in the direction of the normal vector of the constraint plane for a linear problem. Fig. 2(a) shows a parental candidate solution in the vicinity of the constraint boundary. The dashed circle indicates a contour line of the offspring density. Fig. 2(b) depicts the same situation with the variance of the offspring distribution reduced in the direction of the normal vector of the constraint plane as a result of the transformation implicit in matrix A. Fig. 2(c) considers the same situation as in (b), but uses a coordinate system transformed by A -1 . See Hansen [START_REF] Hansen | Adaptive encoding: How to render search coordinate system invariant[END_REF] for a discussion of coordinate transformations and adaptive encodings. Notice that the change in offspring distribution results in an increase in the constraint angle in the transformed space in Fig. 2(c) compared to Fig. 2(a). If capable of learning an appropriate coordinate transformation, the algorithm will be able to avoid the pitfalls associated with small constraint angles discussed in Section 2.1.

1. Generate offspring candidate solution y according to Eq. (1).

2. For j = 1, . . . , m, determine whether gj (y) > 0 and update vj according to Eq. ( 6) if it is.

3. If y is infeasible, then compute wj = A -1 vj for all j = 1, . . . , m and update the transformation matrix A according to Eq. ( 7). The iteration is complete.

4. Otherwise, evaluate f (y), update the success probability estimate according to

Psucc ← (1 -cP )Psucc + cP 1 f (y)≤f (x)
and update the global step size according to

σ ← σ exp " 1 d Psucc -Ptarget 1 -Ptarget « .
5. If f (y) ≤ f (x), then replace x with y, update the search path according to

s ← (1 -c)s + p c(2 -c)Az
and update matrix A according to Eq. ( 3). The iteration is complete.

6. Otherwise, if f (y) is inferior to its fifth order ancestor, update matrix A according to Eq. ( 5). Incorporating the idea of constraint handling through active covariance matrix adaptation in the (1 + 1)-CMA-ES yields an algorithm the state of which is described by parental candidate solution x along with its objective function value f (x) and those of its five most recent ancestors, global step size σ, success probability estimate Psucc, transformation matrix A, search path s, and constraint vectors vj for j = 1, . . . , m. Each iteration of the algorithm updates those quantities as described in Fig. 3. For β = 0, the algorithm is identical to the (1 + 1)-CMA-ES as described in [START_REF] Arnold | Active covariance matrix adaptation for the (1 + 1)-CMA-ES[END_REF], with constraints handled using the simple resampling scheme described by Oyman et al. [START_REF] Oyman | An alternative constraint handling method for evolution strategies[END_REF]. All parameter settings are summarised in Table 1. Values for parameters cc and β have been obtained by optimising the performance of the strategy applied to linearly constrained sphere functions and then reducing β by a factor of about six in order to achieve robust performance on other test problems. All other parameter settings are identical to those given in [START_REF] Arnold | Active covariance matrix adaptation for the (1 + 1)-CMA-ES[END_REF].

EXPERIMENTAL EVALUATION

This section experimentally evaluates the performance of the algorithm proposed in Section 3 using several constrained test problems. Section 4.1 considers constrained sphere functions that serve to examine basic scaling properties. Section 4.2 considers several test problems frequently used to evaluate the performance of algorithms for constrained optimisation, and it compares results observed for the (1 + 1)-CMA-ES with constraint handling through active covariance matrix adaptation with published work.

Table 1: Parameter settings.

d = 1 + n 2 c = 2 n + 2 cP = 1 12 Ptarget = 2 11 c + cov = 2 n 2 + 6 c - cov = min " 0.4 n 1.6 + 1 , 1 2 z 2 -1 « cc = 1 n + 2 β = 0.1 n + 2

Constrained Sphere Functions

Consider the problem of minimising function

f (x) = n X i=1 x 2 i subject to constraints xi ≥ 1 for i = 1, . . . , m ≤ n.
The optimal solution has components xi = 1 i≤m and objective function value m. Fig. 4 shows the number of objective and constraint function evaluations required to locate a solution with an objective function value that differs from the optimal one by no more than 10 -8 plotted against the dimension of the search space. In the counting of constraint function evaluations it is assumed that one function call yields information for all constraints. The upper graph shows results for m = 1, the lower one for m = n/2. Two variants of the (1 + 1)-CMA-ES are considered: one that employs constraint handling through active covariance matrix adaptation as described in Section 3, and one that relies on the simple resampling approach described by Oyman et al. [START_REF] Oyman | An alternative constraint handling method for evolution strategies[END_REF] (which is recovered from the former for β = 0). In every run the initial candidate solution is sampled uniformly from the feasible subregion of [-100, 100] n . The global step size σ and Cholesky factor A are initialised to 0.1 and the n × n identity matrix, respectively. Runs are terminated when either the optimal solution has been found to within the desired accuracy, or when 10 6 iterations have failed to locate it. We have conducted 99 runs of either strategy in each case and ordered the runs by the number of objective function evaluations and constraint function calls. The bars in the figure indicate the 10th, 50th, and 90th smallest values observed. The thin dotted lines have slopes corresponding to linear and quadratic growth, respectively.

In the case of a single constraint, the strategy variant that employs active covariance matrix adaptation for constraint handling locates the optimal solution to within the desired accuracy in every run and for every value of n considered. Both the number of objective function evaluations and the number of of constraint function calls appear to grow linearly with the dimension n. The number of objective function evaluations is less than twice that required on unconstrained sphere functions of the same dimension. The strategy variant that simply resamples infeasible candidate solutions locates the optimal solution to within the desired accuracy in every run up to n = 40. However, it requires more function evaluations, with the gap between the two variants widening as n increases. For n = 100, the resampling approach regularly fails to reach the termination condition within 10 6 iterations. In the case of m = n/2 constraints, the strategy variant that employs active covariance matrix adaptation for constraint handling again locates the optimal solution to within the desired accuracy in every run and for every value of n considered. The growth of the number of objective function evaluations again appears linear in n, with overall numbers very similar to those observed for m = 1 . The growth of the number of constraint function calls appears to be quadratic in the dimension of the problem. Results for the strategy variant that resamples infeasible candidate solutions are incomplete as for n ≥ 10 the strategy regularly fails to locate the optimal solution to within the desired accuracy.

Other Test Functions

In order to perform a comparison of our algorithm with published results, we have evaluated its performance on several test functions that are commonly used to evaluate EAs for constrained optimisation. Specifically, we have considered the test functions collected by Michalewicz and Schoenauer [START_REF] Michalewicz | Evolutionary algorithms for constrained parameter optimization problems[END_REF] as well as those employed by Kramer and Schwefel [START_REF] Kramer | On three new approaches to handle constraints within evolution strategies[END_REF]. However, a comparison is difficult for several reasons:

• Many test problems have multiple local minima. The (1 + 1)-ES is a poor global optimiser and not use-fully applied to multimodal problems. We have restricted ourselves to test functions g06, g07, g09, and g10 from the test suite in [START_REF] Michalewicz | Evolutionary algorithms for constrained parameter optimization problems[END_REF] as all others are multimodal. When comparing our results with those found in the literature, it is important to keep in mind that other EAs may sacrifice speed of convergence for improved global search performance, and that our choice of test functions is biased in favour of fast local optimisers. We expect that this caveat will be addressed as we incorporate the approach of handling constraints through active covariance matrix adaptation in the (µ/µ, λ)-CMA-ES.

• Many algorithms for which results are reported in the literature compute objective function values for infeasible candidate solutions. While this is possible for commonly used artificial test problems, relying on the ability to obtain meaningful objective function values for infeasible candidate solutions limits the applicability of the algorithms for some practical problems. Presumably, being able to compute objective function values for infeasible candidate solutions can simplify the task of locating near optimal solutions. At the same time, those algorithms that evaluate infeasible candidate solutions incur computational costs that those that evaluate only feasible candidate solutions do not.

• Our algorithm requires a feasible candidate solution as starting point. Some test problems include recommended starting points, and we have used those. For those test problems where no starting point is given, we uniformly sample candidate solutions from the volume defined by the bound constraints until the first feasible candidate solution is encountered. Notice that no objective function evaluations are required for this process. The number of constraint function calls required to generate starting points is highly dependent on the choice of bound constraints and is not included in the figures given below. Algorithms that evaluate infeasible candidate solutions may have a bias in the first feasible candidate solutions that they encounter as the objective function landscape in the infeasible region may act as a funnel.

• Performance measures employed in different papers vary. Many authors only report objective function values after a number of objective function evaluations that far exceeds the computational budget required by our algorithm to locate near optimal solutions.

We have performed 99 runs of the (1 + 1)-CMA-ES with constraint handling through active covariance matrix adaptation on each of the eight test problems described in Appendix A. For test problems g06, g07, g09, g10, and HB, runs were terminated when a solution was obtained that, when rounded to the accuracy with which the optimal values are given in Appendix A, was identical to the optimal value. For the remaining problems, runs were terminated when optimal objective function values were attained to within a factor of 10 -8 . Table 2 lists the problems' dimensions n, the number mact of constraints active at the location of the optimal solution, and the 10th, 50th, and 90th smallest numbers of objective and constraint function evaluations in each case. All runs have located the respective optimal solutions to within the desired accuracy. We have conducted analogous experiments with the strategy that employs the simple resampling scheme and observed failure to converge to the optimal solutions in many cases for all test problems but g06 and TR2. In those cases where optimal solutions were attained, the number of constraint function calls was very significantly higher than for the strategy that employs active covariance matrix adaptation for constraint handling. While a comparison with published work is difficult for the reasons outlined above and the figures need to be interpreted with care, some results from the literature are as follows:

• Runarsson and Yao [START_REF] Runarsson | Stochastic ranking for constrained evolutionary optimization[END_REF] Keeping the caveats mentioned above in mind, these results suggest the (1 + 1)-CMA-ES with constraint handling through active covariance matrix adaptation as a relatively capable EA for solving unimodal constrained optimisation problems.

DISCUSSION AND FUTURE WORK

We have proposed a novel approach for handling constraints in covariance matrix adaptation evolution strategies. Our algorithm does not assume that meaningful objective function values can be obtained for infeasible candidate solutions. It does not make use of constraint function values other than for determining feasibility of candidate solutions and thus has desirable invariance properties. The key idea of the approach is to obtain approximations to the directions of normal vectors of constraint boundaries in the vicinity of the location of current candidate solutions by low-pass filtering steps that violate the respective constraints, and to then reduce variances of the offspring distribution in those directions. The scaling implicit in the transformation that is learned in the process has the effect of increasing local constraint angles. We have presented experimental evidence that if incorporated in the (1 + 1)-CMA-ES, the proposed constraint handling approach outperforms a simple resampling scheme. Further experiments on several unimodal test problems suggest that the approach may be significantly more efficient than other approaches for constrained evolutionary optimisation.

In future work we will conduct comparisons of the performance of the evolution strategy introduced here with further algorithms for constrained optimisation, such as mesh adaptive direct search algorithms and generating set search methods. Furthermore, we will incorporate the idea of constraint handling through active covariance matrix adaptation in the (µ/µ, λ)-CMA-ES and evaluate its potential for solving constrained multimodal optimisation problems.

Figure 1 :

 1 Figure 1: (a) Linear problem with a single linear constraint. The two-dimensional subspace spanned by the normal vector of the constraint plane and the gradient vector of the objective function is shown. The feasible region is shaded. (b) Two-dimensional quadratic problem with a linear constraint where the optimal solution lies on the boundary of the feasible region. Constraint angles decrease as the optimal solution is approached.

Figure 2 :

 2 Figure 2: Effect of reducing the variance of the offspring distribution in the direction of the normal vector of the constraint boundary. The parental candidate solution is marked by a dot. (a) The original distribution is indicated by the dashed circle. Dotted lines are contour lines of the objective function. (b) The variance of the distribution in the horizontal direction is reduced. (c) Situation from (b) shown with the variables transformed by A -1 .

Figure 3 :

 3 Figure 3: Single iteration of the (1 + 1)-CMA-ES with constraint handling through active covariance matrix adaptation.

Figure 4 :

 4 Figure 4: Comparison of the number of objective and constraint function evaluations required to optimise constrained sphere functions with m = 1 (top) and m = n/2 (bottom). The curves show results for the (1+1)-CMA-ES with and without constraint handling through active covariance matrix adaptation.

Table 2 :

 2 Function evaluations required to solve test problems.

	problem n mact	objective function 10th 50th 90th	constraint function 10th 50th 90th
	g06	2	2	272	308	364	827	1060	1223
	g07	10	6	1939 2211 2703 10435 11283 12704
	g09	7	2	1430 1674 2074	3626	4106	5075
	g10	8	6	2794 3976 5369 15621 18781 23088
	TR2	2	1	376	443	510	616	708	839
	2.40	5	5	1326 1990 3326	4551	6994 11114
	2.41	5	5	1483 2271 3581	5235	8108 12056
	HB	5	4	623	768 1150	2338	2912	3970

  These values exceed the median values reported in Table 2 by factors of 1,797.3, 40.0, 22.7, and 70.8 for objective function calls and by factors of 1,554.9, 110.1, 46.8, and 72.6 for constraint function calls. • Kramer et al. [12] employ a CMA-ES that learns constraint function models and rotates mutation distributions accordingly. They report figures of 3,249 and 11,216 objective function calls and 3,650 and 30,068 constraint function calls for problems TR2 and 2.40, respectively. These figures exceed the median numbers of objective function calls reported in Table 2 by factors of 7.3 and 5.6. The corresponding numbers of constraint function calls differ by factors of 5.2 and 4.3.

	and 99,866 and exceed the median values reported in
	Table 2 by factors of 34.1, 8.9, 12.4, and 5.3.
	• Kramer and Schwefel [13] apply evolution strategies
	with several constraint handling mechanisms to prob-
	lems TR2, 2.40, 2.41, and HB. The best figures they
	report for any of the evolution strategies are 796,201,
	79,566, 51,660, and 54,344 objective function calls and
	1,100,872, 770,334, 379,268, and 211,499 constraint
	function calls, respectively.
	use stochastic ranking in a
	relatively basic evolution strategy that evaluates in-
	feasible candidate solutions. They report the median
	number of function evaluations required to attain the
	best values encountered in each run. Those values are
	in some cases less accurate than those used as termi-
	nation conditions here. For test problems g06, g07,
	g09, and g10 they report figures of 108,000, 143,000,
	124,000, and 128,000 objective and as many constraint
	function calls, respectively. These values exceed the
	median values reported in Table 2 by factors of 350.6,
	64.7, 74.1, and 32.2 for objective function calls and
	by factors of 101.9, 12.7, 30.2, and 6.8 for constraint
	function calls.
	• In a paper that was ranked first in the 2006 IEEE Con-
	gress on Evolutionary Computation Special Session on
	Constrained Real-Parameter Optimization, Takahama
	and Sakai [21] report the number of function calls re-
	quired by ǫ constrained differential evolution with gra-
	dient-based mutation and feasible elites to obtain so-
	lutions within 10 -4 of optimal solutions for g06, g07,
	g09, and g10 to be 7,381, 74,303, 23,121, and 105,234
	in the mean, respectively. These values exceed the
	median values reported in Table 2 by factors of 24.0,
	33.6, 13.8, and 26.5 for objective function calls and by
	factors of 7.0, 6.6, 5.6, and 5.6 for constraint function
	calls.
	• Takahama and Sakai [22] report to have reached op-
	timal solutions for problems g06, g07, g09, and g10
	using ǫ constrained adaptive differential evolution af-
	ter 15,846, 38,402, 25,400, and 24,815 objective func-
	tion calls on average, respectively. These values exceed
	the median values reported in Table 2 by factors of
	51.4, 17.4, 15.2, and 6.2. The corresponding numbers
	of constraint function calls are 36,112, 99,896, 50,766,

ACKNOWLEDGEMENTS

This research was supported by the Natural Sciences and Engineering Research Council of Canada (NSERC) and the Canada Foundation for Innovation (CFI).

APPENDIX A. TEST PROBLEMS

Problem g07: (Hock and Schittkowski [START_REF] Hock | Test Examples for Nonlinear Programming Codes[END_REF]) Minimise

5 -2x6 -60 ≤ 0 and bound constraints -10 ≤ xi ≤ 10 for i = 1, . . . , 10. Six of the eight constraints other than the bound constraints are active at the optimum, which has an objective function value of 24.3062091.

Problem g09: (Hock and Schittkowski [START_REF] Hock | Test Examples for Nonlinear Programming Codes[END_REF]) Minimise

3 + 5x6 -11x7 ≤ 0 and bound constraints -10 ≤ xi ≤ 10 for i = 1, . . . , 7. Two of the constraints other than the bound constraints are active at the optimum, which has an objective function value of 680.630057.

Problem g10: (Hock and Schittkowski [START_REF] Hock | Test Examples for Nonlinear Programming Codes[END_REF]) Minimise Problem TR2: (Kramer and Schwefel [START_REF] Kramer | On three new approaches to handle constraints within evolution strategies[END_REF]) Minimise

The constraint is active at the optimum, which has an objective function value of 2. Point (50, 50) T serves as the starting point. Problem 2.40: (Schwefel [19]) Minimise


Ambre Nour Sayed

Ambre Jousselin

Brice Felden
email: bfelden@univ-rennes1.fr

A cis antisense RNA acts in

come

A cis-antisense RNA acts in trans in Staphylococcus aureus to control translation of a human cytolytic peptide.

INTRODUCTION

In all living organisms, gene expression is modulated by proteins and small regulatory RNAs (sRNAs). sRNAs were identified in many bacteria and a few act by binding and modulating protein activity. The majority of sRNAs functions by pairing with target mRNAs, modifying mRNA transcription, stability or translation [START_REF] Waters | Regulatory RNAs in bacteria[END_REF] . These base pairing sRNAs fall into two categories, trans-and cis-encoded sRNAs. The trans sRNAs are encoded at genomic locations distant from the mRNAs they regulate and share only limited complementarities with their targets. The cis-encoded antisense RNAs (asRNAs) are transcribed from the DNA strand opposite another gene and have perfect complementarities with their target. Recently, a considerable amount of natural asRNAs has been detected in various organisms, including human cells [START_REF] He | The antisense transcriptomes of human cells[END_REF] .

In bacteria, antisense transcription was first demonstrated almost 50 years ago and was considered to be the exception to the rule. However, accumulating evidence from transcriptome studies suggests that extensive antisense transcription occurs in bacteria, producing many cis-sRNAs of various sizes [START_REF] Georg | cis-Antisense RNA, Another Level of Gene Regulation in Bacteria[END_REF] . In the human pathogen Helicobacter pylori, asRNAs were detected for 46% of all annotated open reading frames [START_REF] Sharma | The primary transcriptome of the major human pathogen Helicobacter pylori[END_REF] , indicating that bacterial transcriptomes are unexpectedly complex. The functional relevance of this massive antisense transcription, however, is poorly understood but these asRNAs are predicted to have significant, as yet largely unexplored, impacts on gene expression. Also, information on the molecular mechanisms of individual asRNAs is growing at a slow pace. In bacteria, mechanisms of asRNA action include alteration of target RNA stability, transcription interference or termination, as well as translation modulation [START_REF] Georg | cis-Antisense RNA, Another Level of Gene Regulation in Bacteria[END_REF] .

The Gram-positive bacterium Staphylococcus aureus (S. aureus) is a major human pathogen causing a wide spectrum of nosocomial and community-associated infections with high mortality. S. aureus generates a large number of virulence factors whose timing and expression levels are precisely tuned by regulatory proteins and sRNAs. S. aureus expresses at least 91 sRNAs [START_REF] Felden | The Staphylococcus aureus RNome and its commitment to virulence[END_REF] including asRNAs. Recent high-resolution transcriptome analysis detected a large proportion of these asRNAs among the inventoried S. aureus sRNAs [START_REF] Pichon | Small RNA genes expressed from Staphylococcus aureus genomic and pathogenicity islands with specific expression among pathogenic strains[END_REF][START_REF] Abu-Qatouseh | Identification of differentially expressed small non-proteincoding RNAs in Staphylococcus aureus displaying both the normal and the smallcolony variant phenotype[END_REF][START_REF] Geissmann | A search for small noncoding RNAs in Staphylococcus aureus reveals a conserved sequence motif for regulation[END_REF][START_REF] Bohn | Experimental discovery of small RNAs in Staphylococcus aureus reveals a riboregulator of central metabolism[END_REF] . In S. aureus, many asRNAs are expressed from Pathogenicity Islands (PIs) and mobile elements including plasmids and transposons. Since the SaPIs are the repository of toxins, adherence and invasion factors, superantigens and secretion systems, the location of sRNAs in the PIs suggests that they play important roles during S. aureus infections. In addition to all the Small pathogenicity island rnas [START_REF] Pichon | Small RNA genes expressed from Staphylococcus aureus genomic and pathogenicity islands with specific expression among pathogenic strains[END_REF] (RNAs expressed from the PIs), at least four asRNAs are also expressed from the PIs [START_REF] Felden | The Staphylococcus aureus RNome and its commitment to virulence[END_REF] . One of these asRNAs, Teg152, was detected in strain N315 by high throughput sequencing [START_REF] Beaume | Cartography of methicillin-resistant S. aureus transcripts: detection, orientation and temporal expression during growth phase and stress conditions[END_REF] and predicted, based on its overall genomic location, to be complementary with SprA1 3'-end. Because Teg152 acts as a functional asRNA against SprA1 as reported here, it was renamed SprA1 AS . Sequence comparison suggest that the 'SprA1/SprA1 AS ' pair forms a type I 'toxin-antitoxin' (TA) module [START_REF] Fozo | Abundance of type I toxin-antitoxin systems in bacteria: searches for new candidates and discovery of novel families[END_REF] . SprA1 was identified by computer searches combined with transcriptomic analysis and its expression verified by Northern blots [START_REF] Pichon | Small RNA genes expressed from Staphylococcus aureus genomic and pathogenicity islands with specific expression among pathogenic strains[END_REF] . The sprA gene is in 2-5 copies in the bacterial chromosome and in plasmids, depending on the strains. We set out to answer the question of the biological roles of the 'SprA1/SprA1 AS ' pair in S. aureus.

We provide evidence that a cis-encoded

RESULTS

Expression of SprA1 and SprA1 AS

Up to five copies of sprA are detected in the S. aureus strains [START_REF] Pichon | Small RNA genes expressed from Staphylococcus aureus genomic and pathogenicity islands with specific expression among pathogenic strains[END_REF] . In strain Newman, a human clinical isolate, only two copies, sprA1 and sprA2, are identified. Therefore, that strain is a simplified model for studying the multicopy sprA gene. In Newman, sprA1 is located in the νSαβ pathogenicity island [START_REF] Baba | Genome sequence of Staphylococcus aureus strain Newman and comparative analysis of staphylococcal genomes: polymorphism and evolution of two major pathogenicity islands[END_REF] , between a transposase and a hypothetical protein (Fig. 1a). We also detected an antisense RNA (asRNA) to SprA1, identified in strain N315 by highthroughput sequencing [START_REF] Beaume | Cartography of methicillin-resistant S. aureus transcripts: detection, orientation and temporal expression during growth phase and stress conditions[END_REF] . The sprA1 and sprA1 AS genes read in opposite directions with a predicted sequence overlap at their 3'-ends (Fig. 1a). A second copy, sprA2, is detected in the core genome at position '2560389-2560600', between a HP and a protein from the GtrA family (not shown). SprA1 and sprA2 share 74% nucleotide identity. Using a DNA probe specific of SprA1, we demonstrate that the RNA is expressed in Newman, as well as its asRNA, SprA1 AS , (Fig. 1b). To distinguish between the expression of the two copies of sprA, and to assess their functional implications independently one another, a 'sprA1-sprA1 AS ' deletion mutant (ΔsprA1-sprA1 AS ) was constructed in Newman by homologous recombination. SprA1-and SprA1 AS -specific DNA probes confirm the absence of expression of both SprA1 and SprA1 AS in the deletion strain (Fig. 1b, right panel). Quantification of the expression levels of SprA1 and of SprA2 indicate that SprA1 is expressed two-to three-fold more than SprA2 in the Newman strain (not shown). This report focuses on the functional investigation of the SprA1 and SprA1 AS RNAs.

Nucleotide overlap between SprA1 and SprA1 AS

Determining SprA1 and SprA1 AS 5' and 3' boundaries was required for subsequent functional and structural analysis. Since they are predicted to overlap, the extent of sequence overlay between the two RNAs was assessed experimentally in Newman. For SprA1, it was resolved using RACE (rapid amplification of cDNA ends), as described [START_REF] Antal | A small bacterial RNA regulates a putative ABC transporter[END_REF] , combined with direct size assessment using Northern blots on polyacrylamide gels (Fig. 1b, left panel). SprA1 5'-end maps at position G 1889597 in strain Newman (at G 1856485 in strain N315, data not shown), twelve nucleotides downstream from a -12 TATAAT -7 box that is the predicted promoter (Supplementary Fig. 1a,boxed). SprA1 3'-end forms an intrinsic terminator characterized by a stem loop (H6, Supplementary Fig. 1a) followed by an imperfect U-tract (UUGGUGU). In E. coli, about half of the Rho-independent terminators possess imperfect Utract [START_REF] Peters | Bacterial Transcription Terminators: The RNA 3'-End Chronicles[END_REF] .

SprA1 AS ends were very difficult to assess experimentally because its small size precludes from using RACE on circularized RNAs [START_REF] Redko | Mini-III, an unusual member of the RNase III family of enzymes, catalyses 23S ribosomal RNA maturation in B. subtilis[END_REF] . Therefore, SprA1 AS transcriptional start site was resolved by primer extension analysis on total RNAs from wild-type Newman cells containing a pCN35ΩsprA1 AS plasmid expressing SprA1 AS from its endogenous promoter, to bypass the obstacle of its small size. We verified that SprA1 AS expressed in vivo from the plasmid has a similar length that wild-type SprA1 AS . SprA1 AS 5'-end was assigned at position G 1889770 (Supplementary Fig. 2a). Therefore, SprA1 AS 5'-end is positioned ten nucleotides downstream from a -10 TATAAT -5 box that is its predicted promoter (Supplementary Fig. 1b, boxed). SprA1 AS 3'-end forms an intrinsic transcription terminator characterized by a stem loop (H2 AS , Supplementary Fig. 1b) followed by a near-perfect U-tract (UUUUUAUU, Supplementary Fig. 1b). SprA1 AS is a ∼60 nt-long asRNA. The experimental determination of the two RNA boundaries allowed producing them as synthetic transcripts.

Phylogenetic distribution of sprA1 and sprA1 AS genes

The phylogenetic distribution of sprA1 and sprA1 AS was studied in all sequenced bacterial genomes. The genes encoding SprA1 and SprA1 AS were identified in two orders of the bacilli class, the bacillales (staphylococcaceae, genus staphylococcus) and the lactobacillales (enterococcaceae, genus enterococcus). They were distinguished from sprA2 that is in the core genome by their locations within the PIs. Sequence alignments of SprA1 AS indicate sequence conservation in the non-overlapping region of the RNA pair, corresponding to ∼20 nucleotides at the 5'side of the RNA. Within all the aureus species in which the RNA pair was detected, there is conservation of the two genes at the nucleotide level, suggesting selective pressure (Supplementary Fig. 1, only four S. aureus sequences shown). Within the Staphylococcus genus, however, there are differences scattered through the RNA sequence.

SprA1 and SprA1 AS expression profiles during growth

SprA1 and SprA1 AS expression levels were monitored by northern blots during growth of S. aureus strain Newman (Fig. 1c andd). Their expression levels were quantified relative to tmRNA, a ubiquitous eubacterial sRNA expressed at constant levels during growth. SprA1 is constitutively expressed, detected early and present at all phases. SprA1 AS is also expressed early and reproducibly exhibits a peak of expression at mid-exponential phase and is also expressed later. Similar expression patterns for the two RNAs are also observed in SH1000 and N315 S. aureus strains (data not shown). The in vivo concentrations of SprA1 and SprA1 AS in wild-type Newman strain was determined by including a range of each of the purified synthetic RNAs in the Northern blots, for quantitative estimations (Fig. 1e). At all times during growth, SprA1 AS is in large excess relative to SprA1, from a 35-to a ∼90 fold molar excess (Fig. 1e).

In vivo detection and binding of the 'SprA1-SprA1 AS ' duplex Since the two RNA genes are partially overlapping, we tested experimentally if the two RNAs, SprA1 and SprA1 AS are interacting in vivo. For that purpose, a streptomycin-binding aptamer [START_REF] Windbichler | Isolation of specific RNA-binding proteins using the streptomycin-binding RNA aptamer[END_REF] was fused at the 5'-end of the sprA1 gene and cloned into a 'pCN35ΩSTsprA1-SprA1 AS ' plasmid expressing 5'ST-SprA1 (STSprA1) and SprA1 AS from their endogenous promoters. The ΔsprA1-ΔsprA1 AS Newman strain was complemented with the 'pCN35Ω STsprA1-sprA1 AS ' plasmid and Northern blots demonstrated that STSprA1 is expressed in the complemented strain at both mid-exponential (OD=3) and early stationary (OD=11) growth phases (Fig. 2a, STSprA1 is expressed to higher levels than wt SprA1 in vivo because of the plasmid copy number). As controls, the expression of SprA1 in wt cells, but not in the deletion strain, was monitored and the size difference between STSprA1 and wt SprA1 corresponds to the 46 nt-long ST. Total RNAs extracted from Newman 'ΔsprA1-ΔsprA1 AS -pCN35Ω STsprA1-sprA1 AS ' cells were loaded on a streptomycin affinity matrix. As shown by PAGE (Supplementary Fig. 2b), the flow through (FT) contains the non specific RNAs (tRNAs and ribosomal RNAs), the last two washes cause some loss of STSprA1 from the column and, interestingly, the elution performed with 100 μM streptomycin contains STSprA1 and SprA1 AS (Supplementary Fig. 2b), indicating that SprA1 AS is in complex with immobilized STSprA1. As a negative control, total RNAs were extracted from Newman 'WT-pCN35ΩsprA1 AS ' cells and loaded onto the affinity matrix. Northern blots demonstrate that in the absence of STSprA1 in vivo, SprA1 AS cannot bind the column by itself and is only detected in the FT, together with a non specific sRNA, tmRNA (Fig. 2b). However, with the 'ΔsprA1-ΔsprA1 AS -pCN35Ω STsprA1-sprA1 AS ' cells, Northern blots demonstrate that the eluted fraction contains both SprA1 AS and STSprA1, but not tmRNA (Fig. 2b). Altogether, these experiments indicate that SprA1 forms a complex with SprA1 AS in vivo and that its 5'ST does not hamper recognition.

Duplex formation between SprA1 and SprA1 AS was analyzed by gel retardation assays. A 'SprA1-SprA1 AS ' duplex was detected at a 1:0.3 molar ratio and all SprA1 was in complex with sprA1 AS at a 1:1 molar ratio (Fig. 2c). Complex formation between labeled SprA1 and SprA1 AS was also analyzed and nearly all labeled SprA1 was in complex at a 1:1 molar ratio (Fig. 2d). In the two experiments, the binding is specific since a 1,000-fold molar excess of total tRNAs do not displace SprA1 AS or SprA1 from preformed 'SprA1 AS -SprA1' complexes, whereas a twenty-fold excess of unlabeled SprA1 AS or SprA1 RNAs does. SprA1 AS binds SprA1 with an apparent Kd of 15nM ±5 (Fig. 2c andd), a value that was mandatory for complex formation between the two RNAs subsequently analyzed by structural probes in solution.

Structural interaction between SprA1 and SprA1 AS

We analyzed conformations of free SprA1 and SprA1 AS (Supplementary Fig. 3), as well as the SprA1-SprA1 AS duplexes (Supplementary Figs. 4 and5) by structural probes (lead, RNAse V1 and nuclease S1). The data are summarized onto SprA1 and SprA1 AS models.

SprA1 AS has two folded stems (H1 AS and H2 AS ) separated by an 8 nt-long junction (H1-H2 AS ). Sequence alignments provide strong phylogenetic support for stem H1 AS , but much less for H2 AS (Supplementary Figs. 1b and5b). In SprA1, the presence of V 1 cuts with no S 1 or lead cuts supports the existence of six stems, H1 to H6. Probing data support the existence of two loops, L1 and L6, capping respectively H1 and H6 (Supplementary Fig. 3b andc).

Internal bulges within H1 and H6 are supported by nuclease S 1 and lead cleavages. A 5 nt junction separates H1 from the first pseudoknot, PK1 (H2-L2-H3-L3), followed by PK2 (H4-Running Title: a cis antisense RNA operates in trans in S. aureus 10 L4 H5-L5). SprA1 is a compact RNA made of two tandem pseudoknots flanked by two stable helices, the second acting as a transcription terminator. Sequence alignments provide strong phylogenetic support for stem H1-H6 but not for H3 (Supplementary Figs. 1a and5a).

The structural changes induced by duplex formation between the two RNAs were examined. Upon SprA1 binding, the most striking reactivity changes involve the singlestranded H1/H2 AS junction that is cleaved by RNase V1 and protected from lead cuts, suggesting that it becomes double stranded upon duplex formation (Fig. 3, Supplementary Figs. 4 and5c). An overall destabilization of the RNA is highlighted by the disappearance of V1 cuts in H1 AS and H2 AS as well as by the fading of S1 and lead cuts in L1 AS and L2 AS .

Conversely, in the presence of SprA1 AS , all the reactivity changes in SprA1 are centred between lower portion of H1 and PK1, indicating that it turns double-stranded, as it becomes protected from lead and S1 cuts (Fig. 3 and Supplementary Fig. 4a). Interestingly, there are no structural changes at the cis-overlapping region between the two RNAs. Altogether, the probing data collected on the 'SprA1-SprA1 AS ' duplex support an interaction between the two RNAs as presented on Figure 3. Comparing sequences from genomes and plasmids provides phylogenetic support of the interaction (covariations in Fig. 3b).

SprA1 and SprA1 AS interact by non-overlapping domains

Between SprA1 and SprA1 AS , there is an intuitive binding site that involves a 35-nt overlap at their 3'-ends (Fig. 3c andd, yellow). Experimental evidences support a different, unexpected, binding site that involves pairings between nucleotides located at their 5'-domains (Fig. 3, red). To assess the contribution of those binding sites in duplex formation, SprA1 and SprA1 AS were cleaved in two halves to retain a single binding domain on each RNA variant ('5'-SprA1', '3'-SprA1', '5'-SprA1 AS ' and '3'-SprA1 AS ', Supplementary Fig. 6). Duplex formation between each of these shorter RNAs was analysed by gel retardation assays (Fig. 4 and Supplementary Fig. 2d). A specific '5'SprA1-SprA1 AS ' duplex is detected (Fig. 4a) with a K d similar to that observed with wild-type SprA1 (Fig. 2c andd), whereas the 3'SprA1 construct is unable to bind SprA1 AS , even at a 20 fold molar excess (Fig. 4b), indicating that SprA1 5'-domain, including H1-L1 and PK1, is necessary and sufficient to interact with SprA1 AS . Also, a specific '5'SprA1 AS -5'SprA1' duplex is detected (Supplementary Fig. 2d), with a weaker affinity than that between the two native RNAs (Fig. 2, c andd), probably because of two conformations for PK1 from 5'SprA1 (Supplementary Fig. 2d, two bands in the control lane) including an open and closed pseudoknotted structures. In addition, a specific '5'SprA1 AS -SprA1' duplex is detected (Fig. 4c) but its apparent K d is much higher than that between the two native RNAs, probably because of the reduced stability of 5'sprA1 AS lacking the H2 AS terminal helix, and also because of the reduced accessibility of the folded PK1 in full-length SprA1. Reciprocally, the 3'SprA1 AS construct is unable to bind SprA1, even at a 200 fold molar excess (Fig. 4d). Overall, the non-overlapping 5'-domains of each RNA are necessary and sufficient for duplex formation, whereas the complementary 35 nucleotides at SprA1 and SprA1 AS 3'-ends are dispensable for duplex formation.

Translation initiates onto SprA1 producing a peptide repressed by SprA1 AS 5' non overlapping domain

In all the sprA1 genomic sequences, an internal ORF was identified (Supplementary Fig. 1a, green), predicted to encode a 30-33 amino acid-long peptide, starting at a 51 GUG 53 or 54 AUG 56 initiation codons and ending at a 144 UAG 146 stop codon. Moreover, an internally conserved ' 37 AGGAGG 42 ' Shine-Dalgarno (SD) sequence was identified 8 to 11 nucleotides upstream the predicted start codons (Fig. 5a). To test whether or not ribosomes can form translation initiation complexes onto SprA1, toeprint assays were performed on ternary initiation complexes including purified 70S ribosomes from S. aureus, initiator tRNA fMet and SprA1. In the presence of the purified S. aureus ribosomes, toeprints are detected onto SprA1 at C65-C69 within L2 from pseudoknot PK1, 14 to 18 nucleotides downstream from the predicted initiation codons (Fig. 5b). The presence of multiple toeprints suggests that ribosome loading onto SprA1 takes place at several positions; probably because of two available initiation codons and also since there is a compact pseudoknot structure at the loading site that needs opening by the ribosomes. Within SprA1, the predicted SD sequence was mutated into 37 UCCUCC 42 and, to maintain the conformation of helix H1, 5 CCUAUCU 11 was also mutated into 5 GGAAGGA 11 (Fig. 5a). Ribosomes are unable to load onto this SprA1 variant named 'SD-mutated sprA1' (Fig. 5b, right panel), demonstrating that the 37 AGGAGG 42 sequence is required for translation initiation. Since the interaction between SprA1 AS and SprA1 (Fig. 3) coincides with the region covered by the ribosomes during translation initiation, SprA1 AS should prevent ribosome loading onto SprA1. Indeed, in the presence of SprA1 AS , SprA1 toeprints disappear (Fig. 5b), indicating that the asRNA prevents ribosome loading onto SprA1. Interestingly, a strong stop is detected at U61 within SprA1 structure likely because RNA duplex formation induces a conformational change (Fig. 3).

In vitro translation assays were performed to provide direct experimental evidence that SprA1 can express a polypeptide predicted to contain 31 amino acids (Supplementary Fig. 7).

In the presence of wild-type SprA1, a 2 to 5 KDa polypeptide is detected (Fig. 5c), in agreement with its ~3.45 KDa theoretical molecular weight. Remarkably, when SprA1 AS is added in the reaction (2-fold molar excess compared to SprA1), SprA1 translation is blocked.

We conclude that SprA1 AS down regulates SprA1 translation by direct pairing interactions at and around the SprA1 translation initiation signals (Fig. 3). A ten-fold molar excess of either 5'SprA1 AS or 3'SprA1 AS was added in the translation assays of SprA1 (5'SprA1 AS has a weaker binding affinity for SprA1 than wt SprA1 AS has (Figs. 2c, 2d, and4c). Whereas 5'SprA1 AS reduces significantly SprA1 translation, 3'SprA1 AS does not (Fig. 5c), providing Running Title: a cis antisense RNA operates in trans in S. aureus 13 direct evidence that SprA1 AS prevents SprA1 translation by its 5'-domain, but not by its 3'domain. As a negative control, the 'SD-mutated SprA1' cannot be translated in vitro (Fig. 5c), in agreement with the toeprint data, as it fails to recruit the S. aureus ribosomes (Fig. 5b, right panel). Altogether, these experiments indicate that SprA1 AS binds SprA1 at its 5' nonoverlapping sequence to block internal translation of SprA1. To assay if SprA1 AS also regulates SprA1 transcription and/or stability, in addition to its translational control, SprA1 AS was over expressed in vivo and the expression levels of SprA1 were monitored by northern blots during bacterial growth. Increasing the expression levels of SprA1 AS does not significantly affect SprA1 levels in vivo, ruling out a direct regulation at the RNA level (Fig. 5d).

SprA1-encoded peptide expression is down regulated in trans by cis-SprA1 AS in vivo

With regard to the data presented above, the sprA1 and sprA1 AS genes were linked physically.

Decoupling genetically the location and expression of the two overlapping RNAs was required to demonstrate in vivo that a cis-sRNA operates in trans. The SprA1 peptide has very low immunogenicity (not shown), and its over expression in vivo inhibits S. aureus growth (data not shown). A reporter peptide construct was designed by combining the 5'sequence of SprA1 including 20 amino acids at N-ter from its internal coding sequence, merged to a 22 amino acid 3XFlag, for detection. SprA1 peptide truncation of its 11 amino acids at C-ter was required to lower its toxicity in vivo. Also, the transcription terminator sequence of SprA1 that overlaps with sprA1 AS was replaced by another unrelated terminator sequence (blaZ). A low-copy (∼20 copies per bacterium) vector was used (pCN34) and the pCN34ΩsprA1tag was transformed into Newman ΔsprA1-ΔsprA1 AS . Immunoblots using anti-FLAG antibodies demonstrate that the SprA1 fusion peptide is expressed in vivo (Fig. 6a). To monitor the impact of SprA1 AS on the SprA1-encoded fusion peptide in vivo, strain ΔsprA1-ΔsprA1 AS pCN34ΩsprA1tag was transformed with either pCN35 or pCN35ΩsprA1 AS . In the strain containing the two RNAs in trans, each expressed from a different plasmid, SprA1 peptide levels are drastically reduced (Fig. 6a), demonstrating the down regulation of the expression of the SprA1 peptide by SprA1 AS in vivo. Northern blots validate the presence of the SprA1-flagged and SprA1 AS RNAs in the 'ΔsprA1-ΔsprA1 AS ' double deletion strain containing the two plasmids whereas, as expected, there is only the SprA1-flagged RNA in the ΔsprA1-ΔsprA1 AS pCN34ΩsprA1tag strain transformed with the empty pCN35 plasmid (Fig. 6b). We conclude that SprA1 AS prevent sprA1-encoded peptide expression in trans in vivo and that its 3'-overlapping region with SprA1 is dispensable for the regulation.

The SprA1-encoded peptide is cytolytic for human cells

Sequence alignments of the SprA1-encoded peptide indicate α-helicity and amphipathy (Supplementary Fig. 7), which are typical features of pore-forming peptides [START_REF] Mellor | Properties of ion channels formed by Staphylococcus aureus delta-toxin[END_REF] . The lytic activity of the SprA1 peptide was demonstrated by adding increasing concentrations of the chemically synthesized peptide on human erythrocytes (Fig. 7a). The SprA1 peptide lyses human erythrocytes at a 1µM concentration and above, but is less active towards sheep erythrocytes (Fig. 7b), suggesting a narrow hemolytic range. Some microbial hemolysins display antibacterial activity [START_REF] Verdon | deltahemolysin, an update on a membrane-interacting peptide[END_REF] . The SprA1 peptide has also antimicrobial activity against Gram negative and positive bacteria (not shown). The bactericidal activity of the SprA1 peptide against S. aureus cells gives a rationale as to why SprA1 AS is continuously expressed during bacterial growth, preventing SprA1 translation and toxicity against S. aureus cells.

DISCUSSION

Many asRNAs were recently inventoried in bacteria and eukaryotes but information on the molecular mechanisms underlying their functions is, for the most part, unknown. By definition, cis-asRNAs regulate the genes encoded on the respective opposite strands [START_REF] Thomason | Bacterial antisense RNAs: how many are there, and what are they doing?[END_REF] . It is commonly accepted that cis-asRNA functions are linked to their sequence overlap with genes transcribed from the opposite DNA chain. We report a case of an asRNA that acts as a trans regulator in S. aureus. It demonstrates that asRNAs can interact in trans with complementary target genes and possibly also with other genes at remote genetic loci. Base complementarities between overlapping RNAs do not necessary imply that they are the functional unit of the pair. Because cis-RNAs can work in trans, the distinction between cisand trans-RNAs should be revised. Our findings also suggest that the mechanisms of gene regulations of the identified asRNAs should be re-evaluated, as some could operate in trans on targets. It may be advantageous for trans sRNAs to be located in cis on the chromosome because, during genomic rearrangements, they will move with their target genes. In many bacteria, trans-acting sRNAs require the Hfq RNA chaperone protein for pairings with target RNAs [START_REF] Chao | The role of Hfq in bacterial pathogens[END_REF] . In vivo, SprA1 steady-state levels are unaffected by the presence or absence of Hfq (Supplementary Fig. 2c), suggesting that the protein is dispensable for the interaction between SprA1 AS and SprA1. The cis-overlap between SprA1 and SprA1 AS 3'-ends operates as a bi-directional transcription terminator, presumably for genome compaction and tightness. Their 5' non-overlapping domains, however, interact in trans to repress SprA1-encoded cytolytic peptide synthesis (Fig. 7c).

SprA1 has a compact secondary structure made of RNA pseudoknots flanked by stable stem-loops, hindering internal translation initiation signals from the ribosomes. Despite such structural lock, the S. aureus ribosomes can load onto SprA1 in vitro to produce a 31 amino acid peptide. SprA1 AS is therefore required to block internal translation onto SprA1, inducing a conformation rearrangement by pairing interactions. These observations are consistent with a continuous and tight repression of peptide synthesis that is detrimental for S. aureus growth (data not shown). The SprA1 peptide is probably only expressed under restricted, currently unknown, physiological conditions by specific environmental clue(s) reducing SprA1 AS levels. The peak of SprA1 AS expression at mid-exponential phase suggests that translation repression of SprA1 is optimized during the exponential phase, probably to insure that the lytic peptide is not produced when the S. aureus cells are actively spreading. Alternatively, SprA1 AS could have other functions; it might act in trans on other RNAs. Indeed, in Listeria monocytogenes, riboswitches that are cis-RNA elements can also function in trans, therefore acting as regulatory RNAs [START_REF] Loh | A trans-acting riboswitch controls expression of the virulence regulator PrfA in Listeria monocytogenes[END_REF] . SprA1 could have other functions, possibly at the RNA level, in addition to expressing a peptide. Dual functions, at the transcription and translation levels, were recently reported for a cytolysin (phenol-soluble modulin, PSM) regulating virulence in S. aureus [START_REF] Kaito | Transcription and translation products of the cytolysin gene psm-mec on the mobile genetic element SCCmec regulate Staphylococcus aureus virulence[END_REF] .

The SprA1 peptide is a novel virulence factor that lyses erythrocytes and probably other eukaryotic cell types and organelles, possibly also involved in erasing competing bacteria. Its function is consistent with its genomic location within a PI-containing virulence gene. In order to exert its cytotoxicity, the SprA1 peptide should be released from the bacteria.

Another S. aureus cytolytic peptide, the δ-hemolysin [START_REF] Janzon | Identification and nucleotide sequence of the delta-lysin gene, hld, adjacent to the accessory gene regulator (agr) of Staphylococcus aureus[END_REF] , is internally encoded within a sRNA, RNAIII. δ-hemolysins are α-helical and amphipatic PSMs, as the SprA1 peptide (Supplementary Fig. 7), and active against a wide range of cells and organelles. δ-hemolysin enables the phagosomal escape of staphylococci in human cells [START_REF] Giese | Expression of delta-toxin by Staphylococcus aureus mediates escape from phago-endosomes of human epithelial and endothelial cells in the presence of beta-toxin[END_REF] . Therefore, the SprA1 peptide could also be involved in evading the human phago-endosomes, the acidic pH could lower SprA1 AS levels, leading to SprA1 peptide expression.

Based on sequence comparisons, SprA1 and SprA1 AS were proposed to form a type I TA module resembling those of the LDR/Fts family [START_REF] Fozo | Abundance of type I toxin-antitoxin systems in bacteria: searches for new candidates and discovery of novel families[END_REF] . Type-I TA modules kill cells usually by forming pores [START_REF] Fozo | Abundance of type I toxin-antitoxin systems in bacteria: searches for new candidates and discovery of novel families[END_REF] , some are involved in the general stress response [START_REF] Wang | Identification of novel cytolytic peptides as key virulence determinants for community-associated MRSA[END_REF] or in specific functions including controlling production of multidrug tolerant cells [START_REF] Dorr | Ciprofloxacin causes persister formation by inducing the TisB toxin in Escherichia coli[END_REF] . Here, the toxin is internally encoded by a sRNA and not by an mRNA, and protein synthesis is prevented by the sRNA antitoxin in trans. Bacterial Type-I TA systems are usually found in multiple copies and there is up to five copies of sprA in some S. aureus strains [START_REF] Pichon | Small RNA genes expressed from Staphylococcus aureus genomic and pathogenicity islands with specific expression among pathogenic strains[END_REF] , but the systematic expression of an associated asRNA with each copy is unknown. However, one difference between the TA systems and 'SprA1-SprA1 AS ' is that in vivo, SprA1 levels are unaffected by increasing SprA1 AS expression. The SprA1-encoded peptide shares physico-chemical properties with S. aureus PSMs that are small, amphipathic and α-helical peptides with significant cytolytic activity against human neutrophils and erythrocytes [START_REF] Otto | Basis of virulence in community-associated methicillin-resistant Staphylococcus aureus[END_REF] . α-type PSMs also cause chemotaxis and cytokines release. Therefore, similar biological activities are anticipated for the SprA1 peptide. PSMs are regulated by the accessory gene regulator A through its direct interaction with the PSM promoter [START_REF] Queck | RNAIII-independent target gene control by the agr quorum-sensing system: insight into the evolution of virulence regulation in Staphylococcus aureus[END_REF] . In contrast, SprA1 translation is down-regulated by an asRNA, as for the TA systems.

In conclusion, cis antisense RNAs can officiate in trans, implying mechanistic reevaluations of the identified antisense RNA-mediated target gene regulations in eubacteria, archeas and eukaryotes. Also, a novel virulence factor expressed by S. aureus is reported and its expression is locked in vivo by an inhibitory sRNA pair. The next challenges are to understand when this novel cytolysin is expressed and what its biological functions are during staphylococcal infections. between the RNAs were inferred from these data. For 'SprA1 AS -5'SprA1', the Kd is 16 ± 5nM. For 'SprA1-5'SprA1 AS ', the Kd is 300 ± 50nM. There is no duplex formation between SprA1 and 3'SprA1 AS or between 3'SprA1 and SprA1 AS . The black diamonds indicate the molar ratios used to perform the competition assays with a 2000-fold molar excess of polyU RNAs or with a 20-fold molar excess of indicated unlabeled RNA. Asterisks point to the 32 Pradiolabeled RNAs. See also Supplementary Fig. 6.

METHODS

Strains and plasmids

Strains and plasmids are listed in Table S1. S. aureus strains were grown at 37°C in brain heart infusion broth. When necessary, chloramphenicol and erythromycin were added at 10 µg mL -1 , and kanamycin was added at 200 µg mL -1 .

Genetic manipulations

Primers used for all the constructions are listed in Table S2. In pCN35ΩsprA1 AS , SprA1 AS sequence with 113 nts upstream and 26 nts downstream was amplified from Newman genomic DNA as a 215-bp fragment, with flanking PstI/EcoRI sites. The fragment is inserted in pCN35. In pCN35ΩSTsprA1/sprA1 AS , the sprA1/sprA1 AS locus was amplified from Newman genomic DNA (with 48 upstream and 45 nt downstream) with streptotag [START_REF] Windbichler | Isolation of specific RNA-binding proteins using the streptomycin-binding RNA aptamer[END_REF] (46b aptamer with affinity to streptomycin) incorporated between sprA1 and its promoter. For the truncated-flagged SprA1 construct, sprA1 gene sequence, from positions -171 to +110, was amplified from Newman genomic as a 368-bp fragment flanked by PstI and EcoRI restriction sites in frame with the first 20 amino acids encoded within SprA1, the reverse primer contains 3XFlag (66-bp, 20 amino acids) followed by two UAG termination codons. The PCR fragment was inserted into pCN48 [START_REF] Charpentier | Novel cassette-based shuttle vector system for gram-positive bacteria[END_REF] and then digested by PstI/NarI. The resulting 684bp fragment (truncated sprA1 ending by 3XFlag followed by the blaZ transcription terminator) was inserted into pCN34 [START_REF] Charpentier | Novel cassette-based shuttle vector system for gram-positive bacteria[END_REF] . The resulting amino acid sequence of the SprA1 fusion peptide is 'MLIFVHIIAPVISGCAIAFDYKDHDGDYKDHDIDYKDDDDK'. The construction of the deletion mutant S. aureus strain Newman ΔSprA1/SprA1 AS was done as described [START_REF] Chabelskaya | A Staphylococcus aureus small RNA is required for bacterial virulence and regulates the expression of an immune-evasion molecule[END_REF] . Briefly, chromosomal gene disruption of sprA1/sprA1 AS locus was constructed by deletion of targeted locus and insertion of erythromycin resistance gene by using the temperature-sensitive vector pBT2 [START_REF] Bruckner | Gene replacement in Staphylococcus carnosus and Staphylococcus xylosus[END_REF] .

In vitro transcription and RNA labeling

All the RNAs used in this report were transcribed from PCR-amplified templates using Newman genomic DNA. Forward primers contain a T7 promoter sequence (Table S2). PCR generated DNA was used as template for transcription using the 'Ambion T7Megascript' kit.

For synthesis of short RNAs (SprA1 AS , 5'SprA1 AS, 3'SprA1 AS ), template was produced by annealing the primers listed in Table S2. RNAs were gel purified, eluted passively and ethanol precipitated. 5' and 3' end labeling of the RNAs were performed as described [START_REF] Antal | A small bacterial RNA regulates a putative ABC transporter[END_REF] .

Primer extension, RACE mapping

For SprA1 AS 5' end mapping, RNA extracts from Newman pCN35ΩsprA1 AS were used.

Primer extension carried out as described [START_REF] Antal | A small bacterial RNA regulates a putative ABC transporter[END_REF] using Superscript III reverse transcriptase. 5'-RACE of SprA1 were carried out as described [START_REF] Antal | A small bacterial RNA regulates a putative ABC transporter[END_REF] . Primers for end determination are listed in Table S2.

RNA Extraction and Northern Blots

Isolated colonies were suspended in 5 ml of BHI and incubated at 37°C overnight. Culture was diluted 1:100 then incubated at 37°C with agitation and stopped at various phases of growth. RNA extraction was performed as described [START_REF] Cheung | A method to isolate RNA from grampositive bacteria and mycobacteria[END_REF] . The DNA probes used to detect sRNA are listed in Table S2. Total RNA was separated on denaturing PAGE and transferred onto a Zeta probe GT membrane (Bio-Rad). Specific 32 P-labeled probes were hybridized with

  RNA functions in trans. During S. aureus growth, SprA1 AS and SprA1 are constitutively and concomitantly expressed and the asRNA forms a complex with SprA1 in vivo to prevent internal translation of the SprA1-encoded open reading frame (ORF) by occluding its translation initiation signals by pairing interactions. Whereas the 60 nt-long SprA1 AS is made of two stem-loops, the 208 nt-long SprA1 contains two RNA pseudoknots including an internal ORF. Polypeptide translation is naturally disfavoured by the SprA1 secondary structure in which its Shine-Dalgarno (SD) sequence is sequestered within a 5' stem-loop. The SprA1 peptide lyses human cells, and upon SprA1 AS binding, an internal RNA pseudoknot of SprA1 unfolds and forms a helix with SprA1 AS . Structural evidences supported by mutational analysis of the RNAs indicate that the functional domain of SprA1 AS is outside its 3'-complementary sequence with SprA1. Functional domains of antisense RNAs can be located outside from their target gene complementary sequences, rendering arduous mechanistic elucidations of asRNA-based gene regulation in all kingdoms of life.

Figure 1

 1 Figure 1 Genomic location, lengths, boundaries, and expression of sprA1 and sprA1 AS . (a) Location of sprA1/sprA1 AS in Pathogenicity Island SaPIn3 of S. aureus strain Newman genome. (b) Right panels: Northern blots detection of SprA1 and SprA1 AS in a wild-type Newman strain (lane 1) and in an isogenic sprA1/sprA1 AS double deletion strain (lane 2). Left panels: Lengths evaluation of SprA1 and SprA1 AS adjoining synthetic labeled RNAs of known lengths combined to 5'-end determinations by RACE mapping. The nucleotide numberings of SprA1 and SprA1 AS ends refer to positions in S. aureus Newman genomic sequence 12 . (c-d) SprA1 and SprA1 AS expression profiles during S. aureus growth. The expression levels of SprA1 and SprA1 AS during a 10-hour growth of S. aureus Newman strain detected by Northern blots. As loading controls, the blots were also probed for tmRNA. The growth curves of the Newman strain is presented, with the quantification of SprA1 (black triangles) and SprA1 AS (grey diamonds) levels relative to the amount of tmRNA from the same RNA extraction. AU =arbitrary units. (e) Determination of the in vivo concentrations of SprA1 and SprA1 AS in a wild-type S. aureus Newman strain during growth detected by Northern blots. The quantification of SprA1 and SprA1 AS in vivo levels (left panels) were performed relative to increasing amounts of synthetic, gel purified SprA1 and SprA1 AS RNAs (the two right panels). In vivo, the ratios between the SprA1 and SprA1 AS RNAs are 1/35, 1/92, 1/63 and 1/50, respectively at A 600nm of 4, 7, 10 and 12.

Figure 2

 2 Figure 2 Detection of the interaction between SprA1 and SprA1 AS in vivo and assessing their binding constants. (a) Northern blot analysis of SprA1 (wild-type or tagged with a ST) expression at mid-exponential (OD 600nm = 3) and stationary (OD 600nm = 11) phases in Newman wild-type (lane 3), isogenic Newman ΔsprA1/sprA1 AS deletion mutant (lane 2) and Newman ΔsprA1-ΔsprA1 AS pCN35Ω STsprA1/sprA1 AS strain (lane 1). (b) Northern blot

Figure 3

 3 Figure 3 Experimental and phylogenetic evidence for the pairings between SprA1 AS and SprA1. (a) Proposed pairings between SprA1 and SprA1 AS . SD and GUG/AUG start codons are in red, the SprA1 AS and SprA1 interacting domains are boxed in red. Blue minus signs indicate the disappearance of the cleavages triggered by the structural probes in the RNA duplex. Triangles are the V1 cuts, arrows capped by circles are the S1 cuts and uncapped arrows are the lead cleavages. The intensity of the cleavages is proportional to the darkness of the symbols. The blue S1 cut appears when the duplex forms. (b) Phylogenetic support for the proposed interaction between SprA1 and SprA1 AS when comparing the sequences of the two RNAs located in genomes and plasmids. Covariations are shown in grey, SD and start codons are boxed. (c,d) Experimentally supported structure of SprA1 and SprA1 AS emphasizing the 3'-overlapping sequence (yellow) as well as the experimentally and phylogenetically supported interaction region (red box). Covariations are shown in grey. The other symbols are similar to panel (a). Structural changes detected upon complex formation are indicated in blue. The domains of the RNAs are indicated (SprA1: H1-H6, H1-H2

Figure 4

 4 Figure 4 SprA1 and SprA1 AS interact by their 5' non-overlapping domains. Complex formation between labeled SprA1 AS with increasing amounts of unlabeled 5'SprA1 (a) or 3'SprA1 (b) and between labeled SprA1 with increasing amounts of unlabeled 5'SprA1 AS (c) or 3'SprA1 AS (d), detected by native gel retardation assays. The apparent binding constants

Figure 5

 5 Figure 5 SprA1 recruits the S. aureus ribosomes, is translated in vitro and SprA1 AS hinders SprA1 translation by its 5' non-overlapping domain. (a) SprA1 structure indicating the ribosome toeprints (oval), the reverse transcriptase (RT) pause in the presence of sprA1 AS (black arrowhead) and the mutated nucleotides in the 'SD-mutated SprA1' construct (rectangles, twelve mutated nucleotides to maintain H1 while modifying the SD sequence). The predicted initiation and termination codons are framed and the nucleotide sequence overlapping with sprA1 AS is in grey. (b) S. aureus ribosome toeprints onto SprA1(WT SprA1), and the disappearance of the toeprints onto the 'SD-mutated SprA1'. In the presence of SprA1 AS at a 2:1 molar ratio, there are no toeprints, indicating that the asRNA impairs ribosome loading onto SprA1. The toeprints are indicated with a black bar and the RT pause onto SprA1, in the presence of SprA1 AS , is indicated by an arrowhead. 'T', 'A', 'G'

Figure 6

 6 Figure 6 SprA1 AS cis RNA acts in trans to down-regulate SprA1-encoded peptide expression in vivo. (a) Detection of the ∼5kDa SprA1-encoded flagged peptide at early (OD 600nm =1) and mid-exponential (OD 600nm =5) phases of growth in strains Newman 'ΔsprA1-ΔsprA1 AS pCN34ΩsprA1tag pCN35' (lanes 1 and 3) and in isogenic Newman 'ΔsprA1-ΔsprA1 AS pCN34ΩsprA1tag pCN35ΩsprA1 AS ' strain (lanes 2 and 4) by immunoblots using anti-FLAG antibodies. (b) Northern blot analysis monitoring SprA1-FLAG RNA (upper panel) and SprA1 AS RNA (lower panel) expression levels at identical phases of growth. 5S rRNAs are the internal loading controls.

Figure 7

 7 Figure 7 The SprA1-encoded peptide is lytic for human cells. (a) Hemolytic activity of synthetic SprA1-encoded peptide compared to a non-hemolytic peptide used as a negative control. Controls: the minus sign indicates that PBS was added to the RBCs, the plus sign indicates hypotonic solution was added to RBCs. RBC sedimentation indicates the absence of hemolysis, whereas a red supernatant implies hemolysis. (b) Differential hemolytic activity of the synthetic SprA1 peptide between human and sheep RBCs. The peptide induces a strong hemolysis on the human RBCs but a weak hemolysis on the sheep RBCs. (c) Proposed model for the down-regulation of SprA1 sRNA internal translation in trans by the cis-

ACKNOWLEDGMENTS

We are thankful to Drs S. Chabelskaya and M. Hallier for critical reading of the manuscript and comments. This study was supported by grant 'ANR-09-MIEN-030-01' from the 'Agence Nationale pour la Recherche' to B.F. and funds from the Inserm, Brittany region (Ph.D grant for N.S.) and from the French Department of Research and Education.

ExpressHyb solution (Clontech) for 90 min, washed, exposed and scanned with a PhosphorImager (Molecular Dynamics).

Streptomycin-streptotag purification

RNA extracts of Newman ΔsprA1/sprA1 AS pCN35ΩSTsprA1/sprA1 AS are used for affinity purification. Streptomycin sepharose preparation and the affinity purification are performed as described [START_REF] Windbichler | Isolation of specific RNA-binding proteins using the streptomycin-binding RNA aptamer[END_REF] . Eluted RNAs are ethanol-precipitated.

Gel-mobility assays, structural probing and Toeprints

Gel-mobility assays were performed as described [START_REF] Antal | A small bacterial RNA regulates a putative ABC transporter[END_REF] . RNAs mix were incubated in binding buffer (80 mM K-HEPES pH 7.5, 4 mM MgCl 2 , 330 mM KCl) before native gel separation.

Structural assays were performed as described [START_REF] Antal | A small bacterial RNA regulates a putative ABC transporter[END_REF] . Structural analysis of duplexes between SprA1 and SprA1 AS are prepared by incubating 0.5 pmol of labeled RNA with 1 pmol of unlabeled RNA in binding buffer 20 min at 30°C. Digestions with the various ribonucleases were performed for 15 min 30°C in the presence of 1 μg of total tRNA from yeast (V1 at 5.10 -5 units; S1 at 5 units, lead acetate at 0.75 mM). The toeprints were done as described [START_REF] Chabelskaya | A Staphylococcus aureus small RNA is required for bacterial virulence and regulates the expression of an immune-evasion molecule[END_REF] with modifications. S. aureus purified 70S were used and reverse transcription was performed using labeled primer 'sprA1Toep' (Table S2).

Protein extractions, western blots and in vitro translation assays.

For proteins extractions during growth, the pellets were re-suspended in lysis buffer (50mM Tris-Cl pH7.5, 3mM MgCl 2 , 0.1 mg mL -1 lysostaphin and 0.2U µL -1 of Benzonase) incubated 15 minutes at 37°C then transferred into ice. Bradford assays were performed on the samples and equal amounts of total proteins were used for the Western Blots. The samples were separated on a 16% Tricine-SDS-PAGE [START_REF] Schagger | Tricine-SDS-PAGE[END_REF] , transferred on Hybond™-P PVDF membrane (Amersham) and revealed using the Amersham™ ECL™ Plus detection Kit. In vitro translation using [ 35 S]-methionine was performed using E. coli S30 extract system for linear templates (Promega) following the manufacturer's instruction. For the assays in the presence Running Title: a cis antisense RNA operates in trans in S. aureus 29 of SprA1 AS or other RNAs, the RNA mix was incubated in binding buffer 20min at 30°C. 30 pmol of purified WT SprA1 or SD-mutated SprA1 were used in the presence or absence of 60 pmol of SprA1 AS or 300 pmol of either 5'SprA1 AS or 3'SprA1 AS . Samples were separated on a 16% Tricine-SDS-PAGE [START_REF] Schagger | Tricine-SDS-PAGE[END_REF] . The gel was fixed, exposed and visualized with PhosphorImager.

Hemolytic assays

For the titration of hemolytic activity of SprA1 peptide, 100µL of serial ½ dilutions of PBS containing peptides were pipetted in a V Bottom 96 Well Plate (Sigma). 100µL of PBS containing 3% (v/v) RBC are added to each well and incubated 1 hour at room temperature.

For hemolysis comparison between human or sheep RBC, RBC were washed and diluted to 3% (v/v) in PBS. Human or sheep RBCs are incubated at 37°C with either 5µL of 50% (v/v) isopropanol (negative control) or with 5µL of 50% (v/v) isopropanol containing 3nmol of the chemically synthesized SprA1-encoded peptide.

Ribonucleotides, oligodesoxynucleotides and proteins

SprA1 peptide was synthesized by PROTEOGENIX (Oberhausbergen, France). Superscript III reverse transcriptases, lysostaphin, Benzonase were purchased from Invitrogen.

Restriction enzymes were from New England Biolabs (Berverly, MA). [γ 32 P]ATP, [α 32 P]pCp (3000 mCi mmol -1 ) and [ 35 S] methionine at (1150Ci mmol -1 at 10mCi mL -1 ) were from Perkin-Elmer (Courtaboeuf, France).

AUTHOR CONTRIBUTIONS

N.S. and B.F. designed experiments, prepared samples, analyzed the data and wrote the manuscript. A.J. constructed the sRNA double mutant, the Hfq experiment and participated in discussions and manuscript writing.

COMPET ING FINANCIAL INTERESTS

The authors declare no competing financial interests.