Christo Kurisummoottil Thomas
email: christokt@vt.edu

Dirk Slock
email: dirk.slock@eurecom.fr

ALTERNATING CONSTRAINED MINIMIZATION BASED APPROXIMATE MESSAGE PASSING

Generalized Approximate Message Passing (GAMP) allows for Bayesian inference in linear models with non-identically independently distributed (n.i.i.d.) priors and n.i.i.d. measurements of the linear mixture outputs. It represents an efficient technique for approximate inference, which becomes accurate when both rows and columns of the measurement matrix can be treated as sets of independent vectors and both dimensions become large. It has been shown that the fixed points of GAMP correspond to the extrema of a large system limit of the Bethe Free Energy (LSL-BFE), which represents a meaningful approximation optimization criterion regardless of whether the measurement matrix exhibits the independence properties. However, the convergence of (G)AMP can be notoriously problematic for certain measurement matrices, and the only sure fixes so far are damping (by a difficult-to-determine amount) or perform a double ADMM. In this paper, we revisit the GAMP algorithm (as e.g. for sparse Bayesian learning (SBL)) by more rigorously applying an alternating constrained minimization strategy to an appropriately reparameterized LSL BFE. This guarantees convergence, at least to a local optimum. We furthermore introduce a natural extension of the BFE to integrate the estimation of (the SBL) hyperparameters via Variational Bayes, leading to Variational AMBGAMP or VAM-BGAMP.

INTRODUCTION

In the Gaussian noise case, a sparse signal vector x can be recovered using the signal model: y = A x + v, where y is the observed data, A is the known measurement or sensing matrix of dimension M × N , typically with M < N . In the sparse model, x contains only K nonzero entries, with K < M < N . Sparse Bayesian Learning (SBL) is a Bayesian inference algorithm proposed by [START_REF] Tipping | Sparse Bayesian Learning and the Relevance Vector Machine[END_REF] and [START_REF] Wipf | Sparse Bayesian Learning for Basis Selection[END_REF]. SBL is based on a hierarchical prior on the sparse coefficients x, inducing sparsity by choosing priors for the hyperparameters that make most coefficients tend towards zero. In [START_REF] Giri | Type I and type II bayesian methods for sparse signal recovery using scale mixtures[END_REF], the authors provide an overview of various sparse signal recovery algorithms, including Basis Pursuit, LASSO, and SBL. They demonstrate the superior recovery performance of SBL compared to conventional methods. However, the Linear Minimum Mean Squared Error (LMMSE) estimation step in SBL at each iteration involves matrix inversion, which makes it computationally complex, even for moderately large datasets. This complexity motivates the use of approximate inference methods. Belief Propagation (BP)-based Sparse Bayesian Learning (SBL) algorithms, as discussed in [START_REF] Tan | Computationally Efficient Sparse Bayesian Learning via Belief Propagation[END_REF], offer improved computational efficiency. For a more detailed overview of various approximate inference methods for SBL, refer to [START_REF] Thomas | Low Complexity Static and Dynamic Sparse Bayesian Learning Combining BP, VB and EP Message Passing[END_REF]. While BP has demonstrated empirical success [START_REF] Murphy | Loopy belief propagation for approximate inference: an empirical study[END_REF], more rigorous work is needed to characterize its convergence behavior in loopy networks. Several studies have investigated the convergence analysis of Gaussian BP (GaBP) and can be found in [START_REF] Du | Convergence Analysis of Distributed Inference with Vector-Valued Gaussian Belief Propagation[END_REF][START_REF] Du | Convergence Analysis of the Information Matrix in Gaussian Belief Propagation[END_REF][START_REF] Su | Convergence Analysis of the Variance in Gaussian Belief Propagation[END_REF][START_REF] Cseke | Properties of Bethe Free Energies and Message Passing in Gaussian Models[END_REF]. [START_REF] Malioutov | Walk-Sums and Belief Propagation in Gaussian Graphical Models[END_REF] provides a convergence condition for GaBP, which requires the underlying distribution to be walk-summable. Their convergence analysis is based on the Gaussian Markov random field (GMRF) de-composition, which expresses the underlying distribution in terms of pairwise connections between variables. The Approximate Message Passing (AMP) algorithm has been introduced to reduce the complexity of GaBP further, from 2M N to M + N messages. Generalized AMP (GAMP) allows non-Gaussian priors and more general measurement processes. But convergence of (G)AMP can be problematic for some matrices A. Many variations have been introduced to help (G)AMP converge, such as 1) adding the Alternating Direction Method of Multipliers (ADMM), 2) exploiting part of the singular value decomposition of the measurement matrix in Vector AMP (VAMP) (but which does not allow to handle n.i.i.d. priors conveniently), 3) sequential updating in Swept AMP (SwAMP), which can work in most cases, 4) by introducing damping, but with typically difficult to determine damping requirements. The AMP algorithm and its variations have many potential applications in (machine learning-aided) wireless communications systems:

• multi-user detection [START_REF] Liu | Sparse Signal Processing for Grant-Free Massive Connectivity[END_REF],

• channel estimation [START_REF] Thomas | Variational Bayesian Learning for Channel Estimation and Transceiver Determination[END_REF],

• joint detection and channel estimation [START_REF] Ngo | Multi-user detection based on expectation propagation for the non-coherent simo multiple access channel[END_REF],

• compressive sensing [START_REF] Thomas | Low Complexity Static and Dynamic Sparse Bayesian Learning Combining BP, VB and EP Message Passing[END_REF],

• reduced complexity Linear Minimum Mean Squared Error (LMMSE) receiver or transmitter computation [START_REF] Thomas | Variational Bayesian Learning for Channel Estimation and Transceiver Determination[END_REF].

Contributions of this paper

• We propose the AMBGAMP version of GAMP that guarantees convergence by utilizing an alternating constrained minimization strategy applied to an augmented Lagrangian of the constrained Large System Limit (LSL) of the Bethe Free Energy (BFE), inspired by but different from [START_REF] Rangan | Fixed Points of Generalized Approximate Message Passing with Arbitrary Matrices[END_REF], [START_REF] Rangan | Inference for Generalized Linear Models via Alternating Directions and Bethe Free Energy Minimization[END_REF]. The algorithm differs from [START_REF] Slock | Convergent Approximate Message Passing by Alternating Constrained Minimization of Bethe Free Energy[END_REF], [START_REF] Slock | Convergent Approximate Message Passing[END_REF] and involves a gradient update with line search, fixed-point iterations, and an ADMM-style Lagrange multiplier update. • The Kullback-Leibler divergences (KLDs) appearing in the LSL-BFE actually are exactly of the form required for applying Variational Bayesian (VB) posterior updates, not only for the main primal variables x and z but also for hyperparameters involved in their priors. We consider here the precisions (inverse variances) in Gaussian priors as hyperparameters, for the case of SBL. The resulting algorithm that involves optimization of the posteriors for x and the auxiliary variables (including the hyperparameters) is called variational AMBGAMP-SBL (VAMBGAMP-SBL).

) is γ = [γ1, • • • , γM ] T .
In SBL, we introduce a Gaussian prior with unknown precisions, denoted as αi, collected in the vector

α = [α1, • • • αN ] T . Hence, we write px i ,α i (xi, αi) = p x i |α i (xi|αi)pα i (αi) = N (xi; 0, α -1 i )G(αi; a, b) (2
) where the Gamma distribution for αi, G(αi; a, b) =

α a-1 i e -bα i b α i Γ(α i )
, with known a, b. Note that the case of an uninformative prior corresponds to a = 1, b = 0. Each γi is also assumed to have a Gamma prior distribution, pγ k (γ k ) = G(γ k ; c, d), where also c, d are known. In Bayesian estimation, we are interested in the posterior, which is given by

p x,z|y (x, z, α, γ|y) = e - N i=1 f (x i ,α i )- M k=1 f (z k ,γ k ) Z(y) 1 {z=Ax} , (3)
where we define the negative log-likelihoods as

fx i ,α i (xi, αi) = -ln px i ,α i (xi, αi) , fz k ,γ k (z k , γ k ) = -ln p y k ,γ k |z k (y k , γ k |z k ),
where we omit the dependence of fz k ,γ k (z k , γ k ) on y. The problem in Bayesian estimation is the computation of the normalization constant Z(y) and of the posterior means and variances. Belief propagation is a message passing technique that allows to compute the posterior marginals. However, due to loops in the factor graph, loopy belief propagation may have convergence issues and is furthermore still relatively complex. GAMP is an approximate belief propagation technique which is motivated by asymptotic considerations in which the rows and columns of the measurement matrix A are considered as random and independent. In which case GAMP can actually produce the correct posterior marginals. In any case, GAMP computes a separable approximate posterior of the form

qx,α,z,γ (x, α, z, γ) = qx(x) qα(α) qz(z)qγ (γ) = N i=1 qx i (xi)qα i (αi) M k=1 qz k (z k )qγ k (γ k ), (4)
in which the dependence on y has been omitted. The GAMP algorithm [START_REF] Rangan | Generalized Approximate Message Passing for Estimation with Random Linear Mixing[END_REF], [START_REF] Rangan | Fixed Points of Generalized Approximate Message Passing with Arbitrary Matrices[END_REF] appears in the table as Algorithm 1. We only consider here Sum-Product GAMP (for MMSE estimation, as opposed to Max-Sum GAMP for MAP estimation). We emphasize that, apart from the hyperparameter updates, the algorithms specified in the tables in this paper, hold for arbitrary Generalized Linear Models. Only the indicated hyperparameter updates are specific for SBL. Algorithm 1 reflects the standard Expectation Maximization (EM) approach for hyperparameter estimation.

PROPOSED VAMBGAMP-SBL

The abbreviation AMB stands for ACM-LSL-BFE, which denotes Alternating Constrained Minimization of the LSL of the BFE. AM-BGAMP employs most of the same updates as GAMP, but GAMP does not rigorously perform alternating minimization (block coordinate descent), particularly in the presence of constraints. Previous work [START_REF] Krzakala | Variational Free Energies for Compressed Sensing[END_REF] has demonstrated that any fixed point of the GAMP algorithm is a critical point of the following constrained minimization of a LSL of the BFE (see also [START_REF] Rangan | Fixed Points of Generalized Approximate Message Passing with Arbitrary Matrices[END_REF] and references therein), here extended to include the hyperparameters: min qx,qz ,τp,qα,qγ JLSL-BF E (qx, qz, τp, qα, qγ )

s.t. E(z|qz) = A E(x|qx) τp = S var(x|qx), (5)
Algorithm 1 EM-GAMP-SBL Require: y, A, S = A.A, fx,α(x, α), fz,γ (z, γ)

1: Initialize: t = 0, x t , τ t

x , s t-1 = 0, α t-1 , γ t-1 2: repeat 3:

[Output node update] 4:

τ t p = S τ t x 5: p t = A x t -s t-1 .τ t p 6: z t = E(z|p t , τ t p , γ t-1 )
7:

τ t z = var(z|p t , τ t p , γ t-1 )
8: 11:

s t = ( z t -p t )./
τ t r = 1./(S T τ t s )
12:

r t = x t + τ t r .A T s t
13:

x t+1 = E(x|r t , τ t r , α t-1 )
14:

τ t+1 x = var(x|r t , τ t r , α t-1 )
15:

[Hyperparameters update] 16:

α t i = 2a+1 E(x 2 i )+2b
, ∀i.

17:

γ t k = 2c+1 E(|y k -z k | 2 )+2d ,
L = D(qxqα||e -fx,α )+D(qzqγ ||e -fz,γ )+HG(qz, τp) +s T (E(z|qz) -A E(x|qx)) -1 2 τ T s (τp -S var(x|qx)) + 1 2 E(x|qx) -u 2 τr + 1 2 E(z|qz) -A u 2 τp , (7)
where s, τs are Lagrange multipliers, and τr = 1./(S T τs) is just a short-hand notation for a quantity that depends on τs. We also use the notations: u 2 τ = i u 2 i /τi, element-wise multiplication as in s.τ , element-wise division as in 1./τ and 1 is a vector of ones. In [START_REF] Slock | Convergent Approximate Message Passing by Alternating Constrained Minimization of Bethe Free Energy[END_REF], [START_REF] Slock | Convergent Approximate Message Passing[END_REF], a careful updating schedule was considered with partial optimization steps on subsets of primal and dual variables. However, that approach is not guaranteed to converge in general. Here we continue to consider an alternating optimization approach in which the schedule is less critical and some of the optimizations are reduced to gradient updates. The resulting algorithm can be considered an extended and generalized version of the ADMM algorithm (extended: there are more than two primal variable groups, generalized: the quadratic augmentation term does not exactly correspond to the linear (mean) constraint). We propose the following updating order

{u} → {qz} → {s} → {τp, τs} → {qx} → {qα, qγ } . ( 8
)
In other words, at iteration t we have the following sequence

{u t } = arg min u L(q t-1 x , q t z , τ t-1 p , u, s t-1 , τ t-1 s , τ t s , q t-1 α , q t-1 γ ) ( 9
)
{q t z } = arg min qz L(q t-1 x , qz, τ t-1 p , u t , s t-1 , τ t-1 s , τ t s , q t-1 α , q t-1 γ )( 10
)
{s t } = arg max s L(q t-1 x , q t z , τ t-1 p , u t , s, τ t-1 s , τ t s , q t-1 α , q t-1 γ ) ( 11
)
{τ t p , τ t s }= arg min τp max τs L(q t-1 x , q t z , τp, u t , s t , τs, τ t s , q t-1 α , q t-1 γ ) (12)

{q t x } = arg min qx L(qx, q t z , τ t p , u t , s t , τ t s , τ t s , q t-1 α , q t-1 γ ) (13)
{q t α , q t γ } = arg min qα,qγ L(q t x , q t z , τ t p , u t , s t , τ t s , qα, qγ ).

The result appears in the Algorithm 2 table.

Update of u

To update u, we use a gradient descent method with line search to optimize the step-size. From ( 7), ( 9), we get the relvant cost function

L(q t-1 x , q t-1 z , τ t-1 p , u, s t-1 , τ t-1 s , q t-1 α , q t-1 γ ) = 1 2 x t-1 -u 2 τ t-1 r + 1 2 z t-1 -A u 2 τ t-1 p + const. (15)
where const. denotes constants w.r.t. u. The minimizing update can be obtained as u t = u t-1 -η t g t (16) with gradient g t = g t (u t-1 ) where g t (u) = ∇uL(q t-1

x , q t-1 z , τ t-1 p , u,

s t-1 , τ t-1 s , q t-1 α , q t-1 γ ) = -A T (( z t-1 -Au)./τ t-1 p ) -( x t-1 -u)./τ t-1 r = g t (0) + H t u, H t = D(1./τ t-1 r ) + A T D(1./τ t-1 p )A (17)
where D(1./τ ) denotes a diagonal matrix with diagonal elements 1./τ . The step-size η t gets optimized for maximum descent :

∂L(q t-1 x , q t-1 z , τ t-1 p , u t , s t-1 , τ t-1 s , q t-1 α , q t-1 γ ) ∂η t = 0 ⇒ η t = g t 2 /g t T H t g t . (18)

Update of {qz}

The relevant terms in the augmented Lagrangian are

L(q t-1 x , qz, τ t-1 p , u t , s t-1 , τ t-1 s , q t-1 α , q t-1 γ ) = D(qzqγ ||e -fz,γ ) + 1 2 var(z|qz)./τ t-1 p +s t-1 T E(z|qz) + 1 2 E(z|qz) -A u t 2 τ t-1 p + const. = D(qzqγ ||e -fz,γ ) + 1 2 E(z T z|qz)./τ t-1 p -(E(z|qz)) T ((A u t )./τ t-1 p -s t-1 ) + const. = D(qzqγ ||e -fz,γ ) + 1 2 E( z -p t 2 τ t-1 p |qz) + const. (19
) where const. denotes constants w.r.t. z and p t = A u t -s t-1 .τ t-1 p . The Lagrangian in [START_REF] Slock | Convergent Approximate Message Passing[END_REF] is separable. We get per component

min qz k D(qz k qγ k ||g t z k /Z t z k ) ⇒ q t z k = gt z k /Z t z k with gt z k = e E q t-1 γ k ln g t z k , Z t z k = gt z k dz k , -ln gt z k = E q t-1 γ k fz k ,γ k (z k , γ k ) + 1 2τ t-1 p k [(z k -p t k ) 2 -(p t k ) 2 ] (20)
where the KLD optimization is as in standard Variational Bayes (VB), and p t k = p t k (s t-1 k ). Note that the partition function Z t z k acts as cumulant generating function:

- ∂ ln Z t z k ∂s k = E(z k |q t z k ) = E(z k |p t k , τ t-1 p k , γ t-1 k ) = z t k ∂ 2 ln Z t z k ∂s 2 k = var(z k |p t k , τ t-1 p k , γ t-1 k ) = τ t z k - ∂ 3 ln Z t z k ∂s 3 k = E((z k -E z k ) 3 |q t z k ). (21)
In the Gaussian prior case, we get a Gaussian posterior q t z k with

1./τ t z = 1./τ t-1 p +γ t-1 , z t = τ t z .(y.γ t-1 +p t ./τ t-1 p ) . ( 22
)

Update of {s} (ADMM style)

Although the quadratic augmentation terms in the Lagrangian do not correspond exactly to a weighted quadratic version of the linear mean constraint, due to the introduction of the auxiliary variable u which streamlines the derivation of the updates of qx and qz, nevertheless an ADMM style update of the mean constraint Lagrange multiplier s is possible. Indeed, the terms in [START_REF] Slock | Convergent Approximate Message Passing[END_REF] that contains s or z are

z T (( 1 2 z -p t )./τ t-1 p ) = z T (s t-1 + ( 1 2 z -Au t )./τ t-1 p ) (23)
Taking the gradient w.r.t. z (as part of the optimization over qz) leads to the RHS of

s t = s t-1 + ( z t -Au t )./τ t-1 p . (24)
Hence, if we use this update for s, then [START_REF] Javanmard | State Evolution for General Approximate Message Passing Algorithms, with Applications to Spatial Coupling[END_REF] reduces to z T s t , as if the quadratic augmentation terms have disappeared! This if the main characteristic of the Lagrange multiplier update in ADMM, which corresponds to a gradient ascent with a particular choice of (diagonal) step-size.

Update of {τp, τs}

In [START_REF] Slock | Convergent Approximate Message Passing by Alternating Constrained Minimization of Bethe Free Energy[END_REF], [START_REF] Slock | Convergent Approximate Message Passing[END_REF], the carefully chosen updating schedule made the quadratic augmentation terms inactive when {τp, τs}. Here these terms only become inactive at convergence. Nevertheless, these terms only play an active role for the means and not for the variances. Hence we shall ignore them here. Hence, the terms of interest in ( 7) for ( 12) are

L(q t-1 x , q t z , τp, u t , s t , τs, q t-1 α , q t-1 γ ) = HG(q t z , τp) -1 2 τ T s (τp -S τ t-1 x ) + const. = const.+ 1 2 M k=1 τ t z k τp k + ln(2π τp k ) - 1 2 M k=1 τs k (τp k -S k,: τ t-1 x ) (25
= 0 ⇒ τ t s k = 1 τ t-1 p k (1 - τ t z k τ t-1 p k ). (26)
∂L ∂τs k = 0 ⇒ τ t p k = S k,: τ t-1 x (27)
which we run as a fixed-point sub-algorithm. To guarantee nonnegativity, the update of τs should come first.

Update of qx

For the update of qx, consider the relevant terms in the augmented Lagrangian (and remember that τ t r = 1./(S T τ t s ) or 1./τ t r = S T τ t s ) L(qx, q t z , τ t p , u t , s t , τ t s , q t-1 α , q t-1 γ ) = D(qxqα||e -fx,α ) -s t T A E(x|qx)

+ 1 2 τ t T s S var(x|qx) + 1 2 E(x|qx) -u t 2 τ t r + const. = D(qxqα||e -fx,α ) + 1 2 (1./τ t r ) T E(x.x|qx) -s t T A E(x|qx) -(u t ./τ t r )) T E(x|qx) + const. = D(qxqα||e -fx,α ) + 1 2 (1./τ t r ) T E(x.x|qx) -(u t + τ t r .A T s t ) T (E(x|qx)./τ t r ) + const. = D(qxqα||e -fx,α ) + 1 2 E( x -r t 2 τ t r |qx) + const. (28
) where const. denotes constants w.r.t. x, and r t = u t + τ t r .A T s t . This cost function is again separable. We get per component a VB update

min qx i D(qx i q t-1 α i ||g t x i /Z t x i ) ⇒ q t x i = gt x i /Z t x i with gt x i = e E q t-1 α i ln g t x i , Z t x i = gt x i dxi , -ln gt x i = E q t-1 α i (fx i ,α i (xi, αi)) + 1 2τ t r i [(xi -r t i ) 2 -(r t i ) 2 ] . (29)
The partition function Z t x i acts as cumulant generating function:

τ t r i ∂ ln Z t x i ∂ri = E(xi|q t x i ) = E(xi|r t i , τ t r i , α t-1 i ) = x t i (τ t r i ) 2 ∂ 2 ln Z t x i ∂r 2 i = var(xi|r t i , τ t r i , α t-1 i ) = τ t x i . (30)
Simplifications occur again in the Gaussian scenario.

Algorithm 2 VAMBGAMP(-SBL)

Require: y, A, S = A.A, fx,α(x, α), fz,γ (z, γ)

1: Initialize: t = 0, x 0 , τ 0

x , u 0 , τ 0 p , s 0 = 0, γ 0 , α 0 2: repeat (t=1,2,. . . ) 3:

[Output node update] 4:

u t = u t-1 -η t g t , with g t , η t from ( 17), [START_REF] Slock | Convergent Approximate Message Passing by Alternating Constrained Minimization of Bethe Free Energy[END_REF] 5: 10:

p t = A u t -s t-1 .τ t-
τ t s = (1 -τ t z ./τ t-1 p
)./τ t-1 p 11:

τ t p = S τ t-1
x 12:

τ t r = 1./(S T τ t s )
13:

[Input node update] 14:

r t = u t + τ t r .A T s t
15:

x t = E(x|r t , τ t r , α t-1 ), Gaussian case:

x t = r t ./(1 + α t-1 .τ t r )
16:

τ t x =var(x|r t , τ t r , α t-1 ), Gaussian case: 1./τ t x = 1./τ t r + α t-1

17:

[Hyperparameters update] 18:

α t i = 2a+1 Eq x i (x 2 i )+2b
, ∀i

19:

γ t k = 2c+1 Eq z k (|y k -z k | 2 )+2d , ∀k 20: until Convergence

Update of Hyperparameter α

The relevant part of the augmented Lagrangian simply leads to a KLD term q t α = arg min qα D(q t x qα||e -fx,α ) + const.

which gets minimized alternatingly as in VB [START_REF] Thomas | SAVE -space alternating variational estimation for sparse Bayesian learning[END_REF] ln q t α i = (

1 2 + a -1) ln αi -( 1 2 E q t x i (x 2 i ) + b) αi + const. ( 32
)
This means that the posterior of αi is a Gamma distribution: q t α i = G(αi; a, b t ), with a = a + 1/2 and b t = E q t x i (x 2 i )/2 + b, with mean a b t or hence:

α t i = 2a + 1 E q t x i (x 2 i ) + 2b . (33)

Update of Hyperparameter γ

The relevant part of the augmented Lagrangian is again a KLD term:

q t γ = arg min qγ (γ) D(q t z qγ ||e -fz,γ ) + const. ( 34
)
which gets minimized alternatingly as in VB [START_REF] Thomas | SAVE -space alternating variational estimation for sparse Bayesian learning[END_REF] ln q t γ k = ( 1 2 +c-1) ln γi-(

E q t z k (|y k -z k | 2 ) 2 +d)γi+const. ( 35
)
which means again that the posterior of γ k is a Gamma distribution

q t γ k = G(γ k ; c, d t ), with c = c+1/2 and d t = E q t γ k (|y k -z k | 2 )/2+
d, and with mean c d t or:

γ t k = 2c + 1 E q t z k (|y k -z k | 2 ) + 2d . (36)
For the case in which all noise variances are assumed to be equal, the update of γ0 = γ k , ∀k can be shown to be [START_REF] Thomas | SAVE -space alternating variational estimation for sparse Bayesian learning[END_REF]:

γ t 0 = 2c + M E q t z ( y -z 2 ) + 2d . ( 37
)

VAMBGAMP-SBL LARGE SYSTEM ANALYSIS

In GAMP, as opposed to AMP, we may not have (simple) analytical updates for means and variances. As a result, the take on large system analysis (LSA) for GAMP is from a different angle. If both the rows or the columns of A are now modeled as independent, then given that also the priors on x and z are independent (factorized), the true posteriors for x and z will become factorized and will equal the approximate posteriors qx(x), qz(z). So multiplication with A or A T acts like scrambling in CDMA communications, that renders the individual outputs independent. Furthermore, the marginal posteriors are the product of the respective prior and extrinsic distributions that correspond to information coming through A or A T , the random nature Fig. 2. NMSE curves for low rank A, with M = 150, N = 250. of which will lead to Gaussian extrinsic distributions by the central limit theorem. In other words, in the LSA, in which the dimensions of x and z (the two dimensions of A) tend to infinity at a constant ratio, the approximate posteriors handled in GAMP become asymptotically exact. As a result, the variance information propagated by GAMP corresponds asymptotically to the exact MSE of the (MMSE) estimates propagated by GAMP. The existing GAMP steady-state analysis results are valid, assuming that the algorithm has converged to such a steady state. Such steady-state analysis appears in [START_REF] Rangan | Generalized Approximate Message Passing for Estimation with Random Linear Mixing[END_REF] (particularly in the extended arxiv version), or in [START_REF] Javanmard | State Evolution for General Approximate Message Passing Algorithms, with Applications to Spatial Coupling[END_REF]. In the Gaussian case of SBL, MMSE estimation becomes LMMSE, for which we have investigated LSA in [START_REF] Thomas | Posterior Variance Predictions in Sparse Bayesian Learning under Approximate Inference Techniques[END_REF] using large random matrix theory. It can be checked that the LSA of the general GAMP case above reduces to these same results in the Gaussian case.

SIMULATION RESULTS

The figures show Normalized MSE τx (2 top curves) and normalized MSE difference between x estimated by AMBAMP and LMMSE (2 bottom curves) with variance profile σ 2

x i = 0.93 i-1 , i = 1, . . . , N , for M = 150, N = 250. Fig. 1 is for i.i.d. Gaussian A whereas Fig. 2 is for low rank A in which the smallest half of the singular values in an i.i.d. A are set to zero. These simulations show that the VAMBGAMP-SBL algorithm continues to work in an unrealistically severe scenario, in which AMP diverges.

CONCLUDING REMARKS

We propose a convergent version of GAMP, VAMBGAMP, which applies alternating minimization to an augmented Lagrangian of a large system limit of the Bethe free Energy (BFE). One quadratic subproblem is minimized by a gradient descent with line search to maintain AMP style complexity. Some variance parameter updates are replaced by fixed-point updates. And an ADMM style update is used for the Lagrange multiplier associated to the mean constraint. Additionally, we have observed that the KLDs appearing in the BFE naturally lead to variational Bayesian inference for the hyperparameters.

Fig. 1 .

 1 Fig. 1. NMSE curves for i.i.d. A, with M = 150, N = 250. GAMP has similar performance as VAMBGAMP-SBL, hence omitted.

  x i |α i (xi|αi) pα i (αi) and n.i.i.d. measurements p y,γ|z (y, γ|z) = M k=1 p y k |z k (y k |z k , γ k ) pγ k (γ k ). The measurement noise precision vector (inverse variance hyperparameter

		2. SYSTEM MODEL
	The data model considered in (EM-GAMP-)SBL is essentially a linear
	mixing model represented by
	z = A x , px,α(x, α) , p y,γ|z (y, γ|z)	(1)
	with (possibly non) identically independently distributed (n.i.i.d.)
	prior px,α(x, α) =	N i=1 p
			• We also indicate that asymptotically, under an i.i.d. element
			model for A, the variance computations in AMBGAMP are
			exact. This allows to analyze the steady-state MSE as a func-
			tion of system dimensions and prior pdfs p(x), p(y|z) for x
			and z. In particular in the Gaussian case, this allows to analyze
			the performance for SBL.
			• Gaussian simulation results validate the convergence to the
			LMMSE solution for different measurement matrices, includ-
			ing i.i.d. and low-rank cases.

  ∀k. is the KLD and HG(qz, τp) is a sum of a KLD and an entropy of Gaussians with identical means but different variances. The LSL BFE optimization problem (6) can be reformulated with the following augmented Lagrangian min

	18: until Convergence
	where the LSL BFE is given by
	JLBF 2	M k=1	var(z k |qz k ) τp k	+ln(2πτp k )
	and where D(q||p)=Eq(ln( q p ))			(6)

E (qx, qz, τp, qα, qγ ) = D(qxqα||e -fx,α )+D(qzqγ ||e -fz,γ ) +HG(qz, τp), with HG(qz, τp) = 1 qx,qz ,qα,qγ ,τp,u max s,τs L(qx, qz, τp, u, s, τs, qα, qγ ) with

  ) where const. denotes constants w.r.t. {τp, τs}. Deriving w.r.t. {τp, τs} yields the feasibility conditions ∂L ∂τp k

  Gaussian case: z t = τ t z .(y. γ t-1 +p t ./τ t-1

			1
			p
	6:	z t = E(z|p t , τ t-1 p , γ t-1 ), p	)
	7:	τ t z = var(z|p t , τ t-1 p	, γ t-1 ), Gaussian case: 1./τ t z = 1./τ t-1 p	+ γ t-1
	8:	s t = s t-1 + (z t -Au t )./τ t-1 p
	9:	[Variance matching]

Acknowledgements EURECOM's research is partially supported by its industrial members: ORANGE, BMW, SAP, iABG, Norton Life-Lock, and by the French ANR project CellFree6G.


E Vautor
email: e.vautor@sophia.afssa.fr

G Abadie

J-M Guibert

N Chevalier

M Pépin

Nasal carriage of Staphylococcus aureus in dairy sheep

Abstract:

The purpose of this study was to assess the prevalence of Staphylococus aureus nasal carriage of dairy sheep in farms producing cheeses manufactured with raw ewe's milk.

Moreover, we investigated the genetic diversity of the 136 isolates recovered from the anterior nares of the ewes, from the ambient air of the milking parlor and from cheeses. The isolates were typed using pulsed-field gel electrophoresis (PFGE) of DNA SmaI digests.

The average nasal carriage in the flock was 29% of the nares of the ewes contaminated by Staphylococcus aureus. The genotyping results showed that strains with dominant pattern (named OV) and a genetically related isolates (named OV') by a majority (69.8%) are recovered from nasal carriage in dairy sheep in this area of France. has resulted in excellent control of this major mastitis pathogen in many cow herds. Milking time hygiene measures that decreased cow to cow transfer were largely responsible for decreasing new S. aureus intramammary infections. The most common transmission pathway consist of transfer from an infected mammary gland to an uninfected gland via fomites, such as milking equipment, common udder cloths, or the milker's hands. However, milking time hygiene alone was insufficient in controlling the disease. The addition of dry-cow therapy, and especially, culling the chronically infected were needed to achieve low level of S. aureus intrammmary infections. If there is little doubt that the primary and most important reservoir of S. aureus is the infected mammary gland, what about the others sources such the nares beside other sources as teat skin, udder skin, lips, eyes, vagina, rectum, sacral region, etc. It would suggest that total eradication of S. aureus in a flock is currently impossible [START_REF] Roberson | Ecology of Staphylococcus aureus isolated from various sites on dairy farms[END_REF][START_REF] Roberson | Sources of intramammary infections from Staphylococcus aureus in dairy heifers at first parturition[END_REF]. In Human disease, S. aureus nasal carriage has been extensively studied in patients and healthy individuals. Cross-sectional surveys of S. aureus nasal carriage have designated individuals as either carriers or noncarriers [START_REF] Kluytmans | Nasal carriage of Staphylococcus aureus: epidemiology, underlying mechanisms, and associated risks[END_REF]. Some authors have used the pulsed-field gel electrophoresis to genotype S. aureus colonising human nasal carriers [START_REF] Hu | Typing of Staphylococcus aureus colonising human nasal carriers by pulsedfield gel electrophoresis[END_REF]. Less information is available about dairy sheep, even though it is likely that the ecology of S. aureus in a dairy sheep farm is probably the same than in a bovine or goat dairy farm [START_REF] Vautor | Genotyping of Staphylococcus aureus isolated from various sites on farms with dairy sheep using pulsed-field gel electrophoresis[END_REF]. In this study, we focus on one of a probable S. aureus reservoir of contamination of the udder represented by the nares of the ewes producing the milk for the manufacturing of the ewe's farm cheeses. We used the pulsed-field gel electrophoresis (PFGE) to investigate the genetic diversity of the nares' S. aureus isolates and to understand genetic relatedness between isolates recovered from different farms.

Between May 2003 and February 2004, in the south-east of France, ten farms (named A to J) were enrolled in the study. The farms were located at a distance of 15-200 km from each other and had no epidemiological links between them. The flock size varied from 30 to 230 ewes of French milking sheep breeds. General husbandry methods applied in these flocks were different, particularly regarding feeding, housing, or the presence of other animals on the farm, etc. Farms A-G had a mechanical milking procedure and farms H-J had a hand milking procedure. The average number of milking ewes sampled in each flock was 37. Thus, a total of 368 ewes were sampled: 227 in farms A to G and 141 in farms H, I, J. Ewes included in the study were sampled only once. Both the left and right anterior nares were swabbed by rubbing the dry cotton-wool swab inside of each nostril while applying an even pressure and rotating the swab. Within 2-5 hours the swabs were transported at 4°C and streaked directly on Baird-Parker rabbit plasma fibrinogen agar (BPRPFA) medium (BioMérieux, Marcy-l'Etoile, France), incubated for 12-48 h at 37°C. Ambient air was sampled by using three plates (90mm in diameter) with BPRPFA medium exposed to the environment of the milking room for 15 min and incubated for 12-48 h at 37°C. These plates were exposed, for all the farm, at 51 cm from above the ground of the milking room (at the udder level). Samples of cheese were plated on BPRPFA medium and incubated for 24-48 h as described by De Buyser (De Buyser et al., 1998). Confirmation of the identity of some isolates was performed, after demonstration of catalase positivity, by using the API STAPH system and Slidex®Stap Plus-Kit (BioMérieux, Marcy-l'Etoile, France). For the ewes' nares, only one colony was chosen for further analysis. Such procedures have been done, assuming that all morphologically similar colonies on a plate are formed by the same strain. For the air and cheese, up to five colonies were taken into account.

A macrorestriction analysis of the chromosomal DNA of the cultures was performed with the restriction enzyme SmaI and subsequent pulsed-field gel electrophoresis. This genotyping system was chosen due to its high discriminatory power and excellent reproducibility [START_REF] Tenover | Comparison of traditional and molecular methods of typing isolates of Staphylococcus aureus[END_REF][START_REF] Olive | Principles and applications of methods for DNA-based typing of microbial organisms[END_REF]. A contour clamped homogeneous electrophoresis technique (CHEF) on the GenePath system (BIO-RAD Laboratories, California, USA) was used according to the instruction manual of the GenePath Group 1 reagent kit (BIO-RAD).

Briefly, isolates of S. aureus were transferred to a BHI broth and incubated overnight at 37°C in a shaking incubator. Bacterial cells were washed and resuspended in the cell suspension buffer (provided with the kit). The suspension was mixed with an equal volume of 1% chromosomal-grade agarose to make plugs. Bacterial cells were lysed in the resuspension buffer containing lysozyme (25 mg/ml) and lysostaphin (2 mg/ml) after an incubation for 1 h at 37°C. Then, 500 l of proteinase K buffer and 20 l of proteinase K (600 U/ml) were added and the plugs were incubated for 16-20 h at 50°C. The restriction enzyme SmaI (5 U/l) and its buffer were added and incubated for 16-20 h at 25°C. Digests of DNA were separated during 20 h by PFGE using 1% gel at the following conditions: 14°C, 120° field angle, 6 V/cm, 5-35 s pulse times. On each gel, two control plugs with the reference strain of S. aureus (strain CIP 57.10, Institut Pasteur, Paris, France) were included. Gels were stained with ethidium bromide (1 mg/ml) and photographed under UV light.

Isolates of S. aureus were placed in groups of identical or related strains by comparing, using visual examination, the banding patterns produced. The scheme used by Tenover [START_REF] Tenover | Interpreting chromosomal DNA restriction patterns produced by pulsed-field gel electrophoresis: criteria for bacterial strain typing[END_REF] was employed to differentiate between indistinguishable (zero band differences), closely related (1-3 band differences), possibly related (4-6 band differences) and unrelated or different (> 6 band differences) strains.

Among a total of 368 ewes' nares, 29% were positive for S. aureus.

The detailed results of the bacteriological examination for each farm is given in table 1. It is of interest to know the frequency of isolation, expressed as a percentage (number of positive S. aureus samples divided by total number of samples), because nasal carriage in dairy sheep may represent a major source of S. aureus for the contamination of milk's product, beside infected mammary gland. Although is could not be a direct contamination of the cheese it could serve as an important reservoir in the farm which could explain, despite strong hygienic procedures, the persistence of udder contamination. [START_REF] Zecconi | Epidemiologic study of intramammary infections with Staphylococcus aureus during a control program in nine commercial dairy herds[END_REF]. To our knowledge, no studies have been carried out in sheep dairy farms to assess the percentage of ewes' nasal carrier. In the general human population the authors agree in a mean carriage of 37.2% (13873 people) with variations according to population type (health care workers, patients hospitalised, drugs addicts, etc) and factors that may influence the rate of S. aureus nasal carriage (nasal abnormalities, age, hormonal status in women, ecology of nasal flora, viral infections of the upper respiratory tract, etc). In this general human population, the rate of S. aureus nasal carriage range from 19 to 55.1% [START_REF] Kluytmans | Nasal carriage of Staphylococcus aureus: epidemiology, underlying mechanisms, and associated risks[END_REF]. Longitudinal studies, however, indicated that carriage patterns differ between individuals, and that 10 to 35% of individuals carry S. aureus persistently, 20 to 75% carry S. aureus intermittently, and 5 to 70% are persistently free of S. aureus (noncarriers) [START_REF] Hu | Typing of Staphylococcus aureus colonising human nasal carriers by pulsedfield gel electrophoresis[END_REF][START_REF] Eriksen | Carriage of Staphylococcus aureus among 104 healthy persons during a 19month period[END_REF]. The variation in reported rates results, at least partly, from differences in study populations, sampling and culture techniques, and criteria for the definition of persistent or intermittent carriage. To our knowledge, no studies have been carried out in dairy sheep, so the mean rate (29%) found in our field survey couldn't been compared with other authors works. To identify for each ewe the carriage patterns (persistent, intermittent, and noncarriage), as determined by some authors for human being [START_REF] Vandenbergh | Follow-up of Staphylococcus aureus nasal carriage after 8 years: redefining the persistent carrier state[END_REF], we should have obtained nasal ewe swab specimen during a 12-week follow-up period. Persistent nasal carriage is a unique characteristic of a fraction of the population, and the attribute "persistent" should be confined to those ewes for whom serial swab specimen cultures consistently yield S. aureus. The carrier state of each ewe could change over time. In human patients, the mean number of colony forming unit (CFU) of S. aureus that can be isolated from the anterior nares is higher in persistent carriers than in intermittent carriers, resulting in more extensive dispersal of staphylococci in the environment [START_REF] White | Relation between quantitative nasal cultures and dissemination of staphylococci[END_REF]. In this field study, we found some ewes (11 ewes, data not shown) with high number of CFU (more than 100 CFU/23.7 mm 2 ): these ewes are, perhaps, cases of persistent carriers. The others ewes (mean contamination with standard deviation 6.6+/-0.5 CFU/23.7 mm 2 ) are intermittent carriers, probably contaminated by strains from ambient air. But, although the contamination rate of the ambient air had not been found high (only 5 farms/10 sampled were positive with S. aureus, at the height of 51cm from the floor), it is likely that the air in the milking room represents a S. aureus constant contamination for the nostrils of the ewe. That stresses a possible role of air as a vehicle for spread of S. aureus. To assess the contamination of ambient air, sampling should be performed at a height under 51 cm from the floor [START_REF] Vautor | Genotyping of Staphylococcus aureus isolated from various sites on farms with dairy sheep using pulsed-field gel electrophoresis[END_REF] or by means of a Surface Air System pump [START_REF] Albenzio | Immune response, udder health and productive traits of machine milked and suckling ewes[END_REF]. sheep dairy farm. So, if the infected mammary gland is not the only source/reservoir of S. aureus, control measures should continue even in herds with low to non-existent levels of S. aureus intramammary infections.

  Key-words: Staphylococcus aureus; Pulsed-Field Gel Electrophoresis (PFGE); Ewe's nares; Genoptyping; Epidemiology Understanding the epidemiology and the ecology of Staphylococcus aureus (S. aureus) [reservoirs, transmission pathways, and risk factors]

Acknowledgements

The authors gratefully acknowledge the ten farmers for their collaboration.

The S. aureus PFGE typing results were presented in table 2 and 3. Some S. aureus PFGE patterns are illustrated in figure 1. PFGE is considered to be among the most reliable and reproductible wholegenome typing procedure [START_REF] Tenover | Comparison of traditional and molecular methods of typing isolates of Staphylococcus aureus[END_REF][START_REF] Olive | Principles and applications of methods for DNA-based typing of microbial organisms[END_REF].

Twenty one different patterns were found among isolates of S. aureus (table 3). One major pulsotype (named OV) was identified in 25 strains found in five farms: A, C, E, I and J. Four patterns were closely or possibly related to OV (same genetic lineage classified as related patterns), according to Tenover's criteria [START_REF] Tenover | Interpreting chromosomal DNA restriction patterns produced by pulsed-field gel electrophoresis: criteria for bacterial strain typing[END_REF], and were named OV'. The OV' patterns were found in farms B, D, E and G-J.

The OV patterns were only absent in farm F. A previous study in these 10 dairy sheep farms, between October 2001 and April 2002 [START_REF] Vautor | Genotyping of Staphylococcus aureus isolated from various sites on farms with dairy sheep using pulsed-field gel electrophoresis[END_REF], showed that a single clone of S. aureus is widely distributed both in infected mammary glands and in cheese produced from raw milk.

In the present study, it is noteworthy when the S. aureus strains are recovered from the cheeses (farms B, D, F, G,…..), they are always isolated from the nares of ewes in the flock (except for farm I). That suggests that this organism, specially when this is the dominant S. aureus strain (OV or OV'), readily or intermittently colonizes nares and after contaminates the udder milk and subsequently the cheese.

Our actual finding bring to the fore that ewe nasal carriage may represent a reservoir for S. aureus to contaminate other sites on the


Eric Vautor
email: e.vautor@afssa.fr

Joshua Cockfield

Caroline Le Marechal

Yves Le Loir

Marlène Chevalier

D Ashley Robinson

Richard Thiery

Jodi Lindsay

Eric Vautor 1

Difference in virulence between Staphylococcus aureus isolates causing gangrenous mastitis versus subclinical mastitis in a dairy

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

INTRODUCTION

Staphylococci are the main aetiological agents of small ruminant intramammary infections (IMI), and S. aureus is the most frequent isolate from clinical IMI cases and coagulasenegative species are the most frequent in subclinical IMI. The annual incidence of clinical IMI in dairy sheep is generally lower than 5%, but in a small percentage of herds the incidence may exceed 30-50% of the animals, causing mortality (gangrenous mastitis) or culling of up to 70% of the herd [START_REF] Bergonier | Mastitis of dairy small ruminants[END_REF]. In addition subclinical or hidden S. aureus IMI cases occur in 3 to 37% of dairy sheep, and are important for economic, hygienic (dairy products consumers) and legal reasons in Europe (EU Directives 46/92 and 71/94 defining the bacteriological quality of milk) [START_REF] Bergonier | Mastitis of dairy small ruminants[END_REF]. In ewe flocks on farms with small-scale production of raw milk cheese, culling for S. aureus subclinical IMI is not the general rule but when a gangrenous case occurs, the death of the ewe due to the infection is common, even with emergency antibiotic therapy. If an animal survives the acute disease, the affected gland becomes necrotic and gradually separates from the surrounding tissue; in this case, healing can take many months [START_REF] Bor | Non-clinical intramammary infection in lactating ewes and its association with clinical mastitis[END_REF][START_REF] Winter | Mastitis in ewes[END_REF]. Why some cases should remain subclinical while others become gangrenous is not known. Bacterial features, which can be identified by genetic content, could be responsible [START_REF] Bor | Non-clinical intramammary infection in lactating ewes and its association with clinical mastitis[END_REF], or alternatively, ewe factors might be important.

There has been some conflicting data about whether some S. aureus strains are more virulent than others. A large study of 161 human nasal carriages of S. aureus in healthy people versus isolates that caused invasive disease failed to identify genetic markers associated with infection [START_REF] Lindsay | Microarrays reveal that each of the ten dominant lineages of Staphylococcus aureus has a unique combination of surface-associated and regulatory genes[END_REF]. In contrast, some human clones of Methicillin-resistant Staphylococcus aureus (MRSA), such as the USA300 and TW isolates, clearly cause unique types of infection [START_REF] Edgeworth | An outbreak of methicillin-resistant Staphylococcus aureus (MRSA)-ST 239 associated with a high rate of bacteremia[END_REF][START_REF] Tenover | Characterization of a strain of community-associated methicillinresistant Staphylococcus aureus widely disseminated in the United States[END_REF]. In rabbits, differences in virulence between S. aureus strains have clearly been demonstrated in experimental infection studies as well as in the field [START_REF] Meulemans | High and low virulence Staphylococcus aureus strains in a rabbit skin infection model[END_REF][START_REF] Vancraeynest | Genotypic and phenotypic screening of high and low virulence Staphylococcus aureus isolates from rabbits for biofilm formation and MSCRAMMs[END_REF].

In bovine intramammary infection, the virulence of S. aureus differs among strains according to previous studies but no specific virulence factor or combination of factors has been strongly associated with the severity of mastitis [START_REF] Haveri | Bacterial genotype affects the manifestation and percistence of bovine Staphylococcus aureus intrammmary infection[END_REF].

Because most previous studies have focussed on well known virulence factors (e.g. exoenzymes, toxins, adhesions) to try to explain the difference of S. aureus virulence between subclinical and acute cases of mastitis, the aim of this study was to explore if other genetic features could be found (e.g. genes evolved in cellular processes, cell-wall synthesis, transport, intermediary metabolism) that might contribute to virulence differences. This study was made possible because genetically similar S. aureus isolates caused either subclinical mastitis or gangrenous mastitis within the same flock. Here we used microarray technologies for the first time to probe the genomes of two isolates. These strains were then compared to additional isolates over a 21 month period using a variety of typing techniques to investigate the evolution of S. aureus in this flock.

MATERIALS AND METHODS

Clinical examination and sample collection

The field study was carried out over a twenty-one month period in a dairy sheep farm with small-scale production of raw milk cheese located in the southeast of France. The sheep were a crossbreed of the Lacaune breed and the "Rouge du Péone" breed. Three visits were made.

The first was in January 2002 to sample eighty ewes for S. aureus subclinical mastitis. The second was in November 2002 to sample a primipare ewe with S. aureus gangrenous mastitis. This ewe died within 24 h in spite of systemic and intramammary therapies. The last visit to the farm was made one year later in October 2003 to look for the gangrenous S. aureus strain in the flock after one dry period for the ewes (absence of milk production during five months). The isolates were recovered from the anterior nares of the ewes and the air of the milking room. The shepherd stopped the exploitation of the farm at the end of 2003.

Bacterial examination of milk samples was performed by streaking 0.1 mL of milk on Baird-Parker rabbit plasma fibrinogen agar (BPRPFA) medium (AES, Combourg, France). Moreover, in order to increase the sensitivity of the isolation, 1 mL of milk was incubated for 24 h at 37 °C in 9 mL of Chapman selective broth (AES) prior to streaking 0.1 mL on BPRPFA medium. Ambient air was sampled by using three plates with BPRPFA medium exposed to the environment of milking room for 15 min and incubated for 24-48 h at 37 °C.

For the ewes' nares, a swab was rubbed inside each nostril and streaked directly on BPRPFA medium plates [START_REF] Vautor | Genotyping of Staphylococcus aureus isolated from various sites on farms with dairy sheep using pulsed-field gel electrophoresis[END_REF][START_REF] Vautor | Nasal carriage of Staphylococcus aureus in dairy sheep[END_REF]. One randomly chosen coagulase-positive isolate per plate was confirmed as S. aureus by PCR performed on the 23S rDNA gene [START_REF] Straub | A 23S rDNA-targeted polymerase chain reactionbased system for detection of Staphylococcus aureus in meat starter cultures and dairy products[END_REF]. On the first visit (January 2002), 6 out of 80 ewes were found to have subclinical intramammary infection with S. aureus in their milk directly or after growth in selective broth. The six isolates were named O33, O46, O47, O54, O63 and O64. The second visit (November 2002) was for the isolation in pure culture of the S. aureus responsible of the death of the ewe with a gangrenous mastitis. This isolate was named O11. The last visit (October 2003) was to look for the S. aureus strain O11 in the nares of the ewes and in the air of the milking parlor. Eight out of 71 ewes were positive with S. aureus in their nares. These isolates were named O193-O200. The ambient air of the milking room during milking time was sampled and one isolate on the plate with BPRPFA was randomly selected and named O192.

Genomic comparison of the subclinical (O46) and gangrenous (O11) S. aureus isolates by DNA microarray studies

In the following methods, the isolate O46 (subclinical) was randomly chosen between the 6 isolates responsible of the subclinical mastitis in January 2002. This isolate O46 was genetically compared with O11 (gangrenous) with the DNA microarrays.

A one colour dye DNA microarray was constructed with 188 oligonucleotide probes of 65mer, mainly designed from the putative virulence genes of S. aureus Mu50. Chromosomal DNA extraction, microarray design, hybridisation and data analysis methods have been described in detail by Vautor et al. [START_REF] Vautor | Genetic differences among Staphylococcus aureus isolates from dairy ruminant species: a single-dye DNA microaaray approach[END_REF]. The results can be found in the supplemental material. In addition, the two strains were compared using the well-validated, two-colour S. aureus seven strain whole genome microarray that has been described previously [START_REF] Witney | Design Validation, and Application of a Seven-Strain Staphylococcus aureus PCR Product Microarray for Comparative Genomics[END_REF] and contains 3 623 PCR products representing every predicted open reading frame in the first seven genome sequencing projects: MRSA252, N315, Mu50, COL, 8325, MW2, MSSA476.

Each strain was co-hybridised with DNA from the reference strain MRSA252, and data were analysed using GeneSpring 7.2. The array design is available in BµG@Sbase (Accession No.

A-BUGS-17 1 ) and also ArrayExpress (Accession No. A-BUGS-17). Fully annotated microarray data have been deposited in BµG@Sbase (accession number E-BUGS-762 ) and in ArrayExpress (accession number E-BUGS-76).

Microarray profiles of the strains were compared to a database of previously characterised human and animal isolates, and clustered using 723 core-variable genes to identify lineages [START_REF] Lindsay | Microarrays reveal that each of the ten dominant lineages of Staphylococcus aureus has a unique combination of surface-associated and regulatory genes[END_REF][START_REF] Sung | Staphylococcus aureus host specificity: comparative genomics of human versus animal isolates by multi-strain microarray[END_REF]. The genes which were found "present" in one strain and not in the other using the DNA microarray where confirmed by PCR. Moreover, all the sixteen isolates were tested by PCR for the genes found different between O11 and O46 with the DNA microarrays. The PCR was performed using primers designed with the software Primer3 [START_REF] Rozen | Primer3 on the WWW for general users and for biologist programmers[END_REF] except for fnbB for which the primers designed by Kuhn et al. were used [START_REF] Kuhn | Evidence for clonal evolution among highly polymorphic genes in methicillin-resistant Staphylococcus aureus[END_REF]. Primers are listed in Table I.

Typing milk, air and nasal carriage S. aureus isolates from the flock

Sixteen S. aureus isolates from mastitis milk, air and nares were compared with different discriminating typing techniques. DNA was extracted with the DNeasy®Tissue kit (Qiagen, Courtaboeuf, France) according to the manufacturer's recommendations.

Pulsed-field-gel-electrophoresis (PFGE) of the chromosomal DNA was performed with the restriction enzyme SmaI and subsequent analysis as described by Vautor et al. [START_REF] Vautor | Nasal carriage of Staphylococcus aureus in dairy sheep[END_REF].

Randomly Amplified Polymorphic DNA (RAPD) typing was performed three times for each isolates [START_REF] Rodriguez-Calleja | Molecular and phenotypic typing of Staphylococcus aureus isolates from rabbit meat[END_REF]. The RAPD pattern with at least one band of difference was considered as one type and named (R, R1, R2 or R3).

For spa typing, the polymorphic X region of the protein A gene (spa) was amplified using the primers spa-1113f (5' TAA AGA CGA TCC TTC GGT GAG C 3') and spa-1514r (5' CAG CAG TAG TGC CGT TTG CTT 3') and sequenced 3 . Applying the recently developed algorithm BURP (Based Upon Repeat Patterns), spa types (spa-t) were clustered into different groups with calculated cost between members of a group less than or equal to five.

BURP spa clonal complexes (spa-CC) were automatically assigned by Ridom Staph Type software using the code system described on the Ridom SpaServer website.

Multiple-locus variable-number (MLVA) tandem repeats analysis for sdrD, sdrC, fnb, clfA, clfB, and SAV1078 genes was performed according to Gilbert et al. [START_REF] Gilbert | Differentiation of bovine Staphylococcus aureus isolates by use of polymorphic tandem repeat typing[END_REF] and for coa according to Callon et al. [START_REF] Callon | Application of variable number of tandem repeat analysis to determine the origin of S. aureus contamination from milk to cheese in goat cheese farms[END_REF]. The MLVA profiles for the S. aureus strains were determined by the combination of types of allele found for each gene analysed.

A genotyping method was also used, based on single nucleotide polymorphisms of exotoxin genes (ssl) [START_REF] Aguiar-Alves | New Staphylococcus aureus genotyping method based on exotoxin (set) genes[END_REF]. The sequences of PCR-amplified internal fragments of three different ssl genes (ssl2, ssl4, ssl9) were compared. These genes encode S. aureus superantigen-like proteins (ssl), belong to a family of exotoxins called staphylococcal exotoxins. For coherence with the literature, these genes, originally named set2, set5 and set7 by Aguiar-Alves et al. [START_REF] Aguiar-Alves | New Staphylococcus aureus genotyping method based on exotoxin (set) genes[END_REF], have been renamed ssl4 (432 bp), ssl9 (467bp) and ssl2 (496bp), respectively [START_REF] Lina | Standard nomenclature for the superantigens expressed by Staphylococcus[END_REF].

Sequences were compared for single-nucleotide polymorphisms (SNP) using the BioEdit Software 4 . Finally, a multiplex PCR assay was used for the detection of prophages in the genomes of lysogenic S. aureus strains. These PCR results allow the prophages to be classified into serogroups A, B, Fa, Fb, L or D [START_REF] Pantucek | Identification of bacteriophage types and their carriage in Staphylococcus aureus[END_REF].

S. aureus surface protein typing (sas typing) was implemented using the method described by Robinson and Enright [START_REF] Robinson | Evolutionary models of emergence of methicillinresistant Staphylococcus aureus[END_REF]. Briefly, gene fragments from seven putative or proven surface protein-encoding loci (sasA, sasB, sasD, sasE, sasF, sasH, sasI) were PCR-amplified and sequenced. Unique nucleotide sequences defined sas alleles, and unique series of alleles defined sas sequence types.

RESULTS

Genomic comparison of the subclinical (O46) and gangrenous (O11) S. aureus isolates by DNA microarray studies

Genomic differences between the two strains O11 and O46 are summarized in Table II along with PCR screening results for the other strains. The core genes (except SAR0940), the core variable genes (except sdrD, fnbB, splE), and the mobile genetic elements (plasmids, staphylococcal cassette chromosome, transposons, S. aureus pathogenicity islands, but excepting some bacteriophage genes) hybridize with similar intensity to the genomic DNA of both strains. PCR confirmed the genetic difference between the strains listed in Table II, including the presence of SAS0897, SAR1558, SAR2100, SACOL0343 in strain O46 but not in O11; these genes are typical of S. aureus lysogenic bacteriophage (hydrolase, lipoprotein, repressor, helicase dnaB). There were different weak comparative signals in the DNA array for MW0387 (exotoxin), SAR2036 (CHIPS) and SACOL0886 (enterotoxin K) but these targets were not confirmed by PCR.

The two strains O11 and O46 clustered with isolates of the CC130 lineage from cows (data not shown). The two strains had in common 3,615 identical predicted open reading frames as designed from the first seven genome sequencing project, including redundant open reading frames (ORF) printed from multiples strains on the arrays. Moreover, both strains O11 and O46 had no evidence of free plasmids (data not shown).

Typing S. aureus isolates from milk, air and nasal carriage in the flock

The PFGE results comparing the sixteen S. aureus isolates recovered over twenty one months are illustrated in Figure 1. Four patterns with more than one band difference were identified and named OV, OV', OV'' and OV'''. The strain O46 (OV) and the strain O11 (OV') had a PFGE pattern within three-band difference of each other. The strain O11 and the strains O193, O194, O195 and O196 had an identical PFGE pattern (OV').

Two spa types were found: t3568 with the repeats 04-39-17 and t524 with the repeats 04-17.

These two spa types, by clustering with BURP (Based Upon Repeat Patterns), belonged to the spa-CC 1773. The other genes found by DNA microarray results in O46 or in O11 (Table II), distinguishing these two isolates, were used to track by PCR the gangrenous strains in the ewes' nares.

The multiple locus variable-number tandem repeats (MLVA) showed six types named A-F.

With the MLVA, the patterns between O11 and O46 were found different for the genes sdrD, fnb, clfA and clfB (data not shown).

The RAPD typing technique showed four types named R-R3. Between the strain O11 (R1) and the strain O46 (R) three bands of difference were found. The strain O11 had the same RAPD pattern than O193, O194, O195 and O196.

For the ssl SNP typing, only ssl9 showed a difference, which was detected by the nucleotide replacement of T for G. The detection of prophages by the multiplex PCR showed that the isolates present on the farm over twenty one months had prophages of serotypes A, B and Fb.

The gangrenous isolate O11 was missing prophage B compared to the subclinical mastitis isolate O46.

The last typing technique used was the highly variable sas genes, which was done only for the strains found identical with all the previous typing techniques (i.e. O11, O193-O196) and O46. The strain O46 had sas type I (sasA26, sasB28, sasD20, sasE26, sasF33, sasH36, sasI29), whereas the strains O11 and O193-O196 had sas type II (sasA34, sasB27, sasD19, sasE26, sasF33, sasH36, sasI28). The sasA and sasB alleles differed at two and one nucleotide sites, respectively, whereas the sasD and sasI alleles differed by insertion-deletion events.

In summary, with all the techniques used to discriminate the S. aureus isolates, the gangrenous isolate O11 was found identical to the isolates O193, O194, O195, O196 recovered in the nares of the ewes during the last visit. It was also very closely related to O192, O199 and O200 isolated in the last visit, varying only in bacteriophage profiles. No isolate in the first visit was identical to O11. In contrast, the subclinical mastitis isolate O46 was found to be indistinguishable from subclinical mastitis isolates O33, O54 (recovered during the first visit) and was not found in ewes' nares (the last visit). Some variations in MLVA and ssl5 SNP were seen in the remaining isolates from the first and final visits, although they looked closely related to all of the isolates.

DISCUSSION

In ewe mastitis it is suspected that S. aureus strains have different virulence potential5 [START_REF] Amorena | Infection of rabbit mammary glands with ovine mastitis bacterial strains[END_REF], but the genetic features associated with the different outcomes were unknown. This is the first comprehensive genomic comparison of an ovine S. aureus strain responsible for subclinical mastitis versus a related strain responsible for a case of acute gangrenous mastitis. We found genomic differences between these genetically closely related strains but we did not find differences in genes evolved in cellular processes, cell-wall synthesis, transport, or intermediary metabolism.

As defined by Lindsay et al. by microarray [START_REF] Lindsay | Microarrays reveal that each of the ten dominant lineages of Staphylococcus aureus has a unique combination of surface-associated and regulatory genes[END_REF], the two strains O11 and O46 were closely related and clustered into the same lineages as two bovine isolates of MLST Clonal Complex 130 [START_REF] Sung | Staphylococcus aureus host specificity: comparative genomics of human versus animal isolates by multi-strain microarray[END_REF]. The PFGE and the spa typing results confirmed that the two isolates were genetically closely related (Fig. 1 and Tab. II) [START_REF] Tenover | Characterization of a strain of community-associated methicillinresistant Staphylococcus aureus widely disseminated in the United States[END_REF][START_REF] Vautor | Genetic differences among Staphylococcus aureus isolates from dairy ruminant species: a single-dye DNA microaaray approach[END_REF] although there are allelic variants between the strains as detected by MLVA, sslSNP and sas genes. The microarray results found that the gangrenous strain O11 was positive for the sdrD gene, which belongs to the Microbial Surface Components Recognizing Adhesive Matrix Molecules (MSCRAMM) family. The human protein that SdrD binds to is not known, but a study on human strains [START_REF] Sabat | Distribution of the serine-aspartate repeat protein-encoding sdr genes among nasal-carriage and invasive Staphylococcus aureus strains[END_REF] showed that the strains carrying sdrD and sdrE had an increased association with bone infection. In fact, O46 had a variant copy of the sdrD gene as determined by the MLVA (data not shown). One limitation of the microarray studies was that these microarrays were designed using only genes from seven human S. aureus strains [START_REF] Sung | Staphylococcus aureus host specificity: comparative genomics of human versus animal isolates by multi-strain microarray[END_REF] so we were unable to detect animal S. aureus-specific genes potentially present in O11 and O46. Moreover these microarrays do not provide information about the position of genes in the chromosome.

Serine protease-like E (splE) is one of several highly homologous spl genes found on the S. aureus genomic island beta (GI), and is predicted to be a substrate-specific serine proteases [START_REF] Popowicz | Functional and structural characterization of Spl proteases from Staphylococcus aureus[END_REF]. splE was only found in the gangrenous strain O11. The product of this splE gene might participate in the difference in disease manifestation between O11 and O46, as some Spl proteases possess restricted substrate specificity similar to that of the V8 protease and epidermolytic toxins [START_REF] Popowicz | Functional and structural characterization of Spl proteases from Staphylococcus aureus[END_REF].

Fibrinogen binding protein B (fnbB) was missing in the gangrenous O11 compared to O46. fnbB also belongs to the MSCRAMM family, and can bind to host proteins fibrinogen, fibronectin and elastin, and also play a role in biofilm production [START_REF] O'neill | A novel Staphylococcus aureus biofilm phenotype mediated by the fibronectinbinding proteins, FnBPA and FnBPB[END_REF]. In rabbit flocks with S. aureus infections (e.g. pododermatis, subcutaneous abscesses and mastitis), there are "low virulence" strains where the infection remains limited to a small number of animal, and "high virulence" strains which spread throughout the rabbitry [START_REF] Meulemans | High and low virulence Staphylococcus aureus strains in a rabbit skin infection model[END_REF][START_REF] Vancraeynest | Genotypic and phenotypic screening of high and low virulence Staphylococcus aureus isolates from rabbits for biofilm formation and MSCRAMMs[END_REF]. Vancraeynest et al. [START_REF] Vancraeynest | Genotypic and phenotypic screening of high and low virulence Staphylococcus aureus isolates from rabbits for biofilm formation and MSCRAMMs[END_REF] showed that fnbB was less common in high virulence isolates, and is associated with reduced spread of infection. It is interesting to notice that the O11 gangrenous strain did not have the fnbB compared to O46. Sung et al. [START_REF] Sung | Staphylococcus aureus host specificity: comparative genomics of human versus animal isolates by multi-strain microarray[END_REF] have also shown that animal strains of S. aureus generally encode variant types of fnbB compared to human S. aureus strains.

A major genomic difference between the O11 and O46 isolates was the missing prophage B in the gangrenous isolate. Because only a few genes on the microarray correlated with this phage, we presume it is relatively unrelated to those in the sequenced genomes.

Bacteriophages are among the most abundant inhabitants of the biosphere, considering that an environmental sample contains nearly 10-fold more phage particles than prokaryotes [START_REF] Brussow | Phage genomics: small is beautiful[END_REF]. All sequenced strains of S. aureus carry between one and four bacteriophage in their genomes [START_REF] Lindsay | aureus evolution: lineages and mobile genetic elements (MGE)[END_REF]. The contribution of these prophages to pathogenesis is probably multifactorial. Many prophage carry putative virulence genes on them. For example, S. aureus phages of the phi3 family carrying immune evasion genes (coding for staphylokinase [START_REF] Goerke | Increased frequency of genomic alterations in Staphylococcus aureus during chronic infection is in part due to phage mobilization[END_REF], enterotoxins [START_REF] Iandolo | Comparative analysis of the genomes of the temperate bacteriophages phi 11 phi 12 and phi 13 of Staphylococcus aureus 8325[END_REF], chemotaxis inhibitory protein CHIPS [START_REF] De Haas | Chemotaxis inhibitory protein of Staphylococcus aureus, a bacterial antiinflammatory agent[END_REF], antiphagocytic protein SCIN [START_REF] Rooijakkers | Immun invasion by a staphylococcal complement inhibitor that acts on C3 convertases[END_REF]), yet integrate specifically into the beta-haemolysin gene, potentially offsetting the virulence afforded by carriage of the immune evasion genes. However, these phage are widely distributed in human isolates, but less common in animal isolates [START_REF] Lindsay | Microarrays reveal that each of the ten dominant lineages of Staphylococcus aureus has a unique combination of surface-associated and regulatory genes[END_REF][START_REF] Tenover | Characterization of a strain of community-associated methicillinresistant Staphylococcus aureus widely disseminated in the United States[END_REF], and not found in the ewe isolates of this study. The integration site of the prophage B is currently unknown as are the rest of the genes on this putative phage. Bacteriophages are also involved in the horizontal transfer of virulence genes between isolates, perhaps allowing for adaptation to new environmental conditions [START_REF] Wagner | Bacteriophage control of bacterial virulence[END_REF], and there is evidence that bacteriophage move during the course of human infections [START_REF] Goerke | Regulatory and genomic plasticity of Staphylococcus aureus during persistent colonization and infection[END_REF][START_REF] Moore | Genetic variation among hospital isolates of methicillinsensitive Staphylococcus aureus: evidence for horizontal transfer of virulence genes[END_REF]. A case of phage conversion of exfoliative toxin A in S. aureus isolated from cows with mastitis was documented [START_REF] Endo | Phage conversion of exfoliative toxin A in Staphylococcus aureus isolated from cows with mastitis[END_REF]. The exfoliative toxin is the causative agent of staphylococcal scalded-skin syndrome in young children. The study suggested the possibility of horizontal transmission of eta gene by temperate bacteriophages among bovine isolates of S. aureus [START_REF] Endo | Phage conversion of exfoliative toxin A in Staphylococcus aureus isolated from cows with mastitis[END_REF]. Under stressful conditions such as the use of antibiotics or UV light, prophage can be induced and cause lysis and death of bacterial populations, potentially decreasing pathogenic potential of a phage carrying strain. More recent data has suggested that phage could encode small RNA molecules that control gene regulation in S. aureus, and affecting virulence potential [START_REF] Pichon | Small RNA genes expressed from Staphylococcus aureus genomic and pathogenicity islands with specific expression among pathogenic strains[END_REF]. Therefore the role of bacteriophage in S. aureus pathogenesis is complex, and some phage may actually be a burden to the bacteria and reduce pathogenic potential.

The DNA array technologies used in this study were constructed from human S. aureus strains so it is possible there are differences between O11 and O46 that are not detected by these microarrays. However, recent studies suggest that animal isolates may only have a limited number of unique genes [START_REF] Herron-Olson | Molecular correlates of host specialization in Staphylococcus aureus[END_REF][START_REF] Sung | Staphylococcus aureus host specificity: comparative genomics of human versus animal isolates by multi-strain microarray[END_REF] so one future direction for this study will be to implement massively parallel sequencing. The various typing methods used showed that the isolates O11 and O46 were genetically closely related. The major differences were in the presence/absence of alleles for sdrD, splE, fnbB, clfA-B and the presence of prophage genes (SAS0897, SAR1558, SAR0940, SAR2100, SACOL0343). Furthermore, the sas typing between O11 and O46 (variations in sasA, sasB, sasD, and sasI) indicates minor variation in additional putative surface products, beside sdrD, fnbB and clfA-B, not revealed by the DNA microarray technologies. All surface expressed proteins may play a role in binding to specific host proteins and/or in immune recognition.

The sequence-based typing methods, spa and sas typing, were the easiest methods for comparing and could be used for short-term epidemiologic studies as well as long-term epidemiologic or phylogenic studies. The difference in the spa repeat between O11 and O46 shows that O11 had a deletion of only one repeat (r39) compared with O46, indicating that they are closely related and they belong to the spa Clonal Complex 1773 (Ridom SpaServer website) [START_REF] Vautor | Genetic differences among Staphylococcus aureus isolates from dairy ruminant species: a single-dye DNA microaaray approach[END_REF]. The sixteen strains belong to the same spa clonal complex 1773 underscoring that the S. aureus presence in this flock is probably to link to a common ancestor. The MLVA typing provided the greatest level of discrimination of the isolates because 6 MLVA different patterns were found, which confirms its utility in epidemiological study in a given herd [START_REF] Gilbert | Differentiation of bovine Staphylococcus aureus isolates by use of polymorphic tandem repeat typing[END_REF]. PFGE as a band-based, rather than sequence-based, typing method gave subtle differences between the isolates (Fig. 1) so was not easy to compare in all cases. The S aureus exotoxinlike protein genes (ssl) did not exhibit significant allelic variability. Variation between individual isolates indicated that individual genes or the bacteriophage were capable of changes in a relatively stable background, suggesting local evolution of S. aureus from a common ancestor over an unknown period of time.

Altogether, with all the typing techniques used in this study (PFGE, MLVA, SNPssl, RAPD, spa typing, sas typing and by PCR for all the genes found different between O11 and O46) the strain O11 was found in the nares of four ewes (O193, O194, O195, O196) eleven months after the gangrenous mastitis case. The ewes's nares are an ecological niche for S. aureus and are important in the epidemiology of mastitis in dairy sheep farms [START_REF] Vautor | Nasal carriage of Staphylococcus aureus in dairy sheep[END_REF]. So with this study we suggest that this body site could serve for transmission of potentially mastitis gangrenous strains in dairy sheep flock. The subclinical mastitis genotype was common in the flock, until a gangrenous genotype emerged and caused a gangrenous disease. Subsequently, the gangrenous genotype was found in the nares of ewes in the flock. But, we could not assert that the mastitis gangrenous case was a primary case with a new emerged virulent strain or if it appear after the nasal carriage had participated to the dissemination of the gangrenous strains in the flock. Maybe S. aureus in this flock has evolved to become more virulent. Evolution of S. aureus is driven by survival of the fittest in different environments, which include host interaction, antibiotic use, and environmental reservoirs, conditions which may fluctuate over time [START_REF] Lindsay | aureus evolution: lineages and mobile genetic elements (MGE)[END_REF].

Although we cannot dismiss the role of host susceptibility in the clinical events in this flock, this study could support the hypothesis that different strains of S. aureus may have different virulence potential in ewe mastitis. Surprisingly, absence of a prophage and particular combinations of putative surface products occurred in the isolate with enhanced virulence. It The absence/presence of the genes, sdrD, splE, SAS0897, SAR0940, SAR1558, SAR2100 and SACOL0343 were evaluated with primers designed in this study.

a [START_REF] Kuhn | Evidence for clonal evolution among highly polymorphic genes in methicillin-resistant Staphylococcus aureus[END_REF]; b [START_REF] Rodriguez-Calleja | Molecular and phenotypic typing of Staphylococcus aureus isolates from rabbit meat[END_REF]: at least one band of difference for each RAPD types; c [START_REF] Vautor | Genotyping of Staphylococcus aureus isolated from various sites on farms with dairy sheep using pulsed-field gel electrophoresis[END_REF] the PFGE profiles were named, OV, OV', OV'', OV'''; d [START_REF] Callon | Application of variable number of tandem repeat analysis to determine the origin of S. aureus contamination from milk to cheese in goat cheese farms[END_REF][START_REF] Gilbert | Differentiation of bovine Staphylococcus aureus isolates by use of polymorphic tandem repeat typing[END_REF]: the letters correspond to a unique pattern made by the combination of the variable number-number tandem repeats of each gene; e [START_REF] Pantucek | Identification of bacteriophage types and their carriage in Staphylococcus aureus[END_REF]: bacteriophages serogroups.

+ positive with PCR, -negative with PCR; sub.: isolates recovered in a S. aureus subclinical mastitis case (January 2002); O192-O200 are the isolates recovered in the last visit to look for the gangrenous strain O11 in the ewes'nares and in the air of the milking room (October 2003). f [START_REF] Aguiar-Alves | New Staphylococcus aureus genotyping method based on exotoxin (set) genes[END_REF]: Single Nucleotide Polymorphism (SNP). The same exotoxin sequence type had an identical numerical number, N.D.: not done; g [START_REF] Robinson | Evolutionary models of emergence of methicillinresistant Staphylococcus aureus[END_REF]: unique sequences defined alleles and unique series of alleles defined a sequence type (named I or II).

Figure 1 .

 1 Figure 1. Representative example of S. aureus PFGE pattern of DNA digested by SmaI. Lane

Table I .

 I Primers used in the study to confirm the microarray data.

Table II .

 II Typing study of sixteen S. aureus isolates in a dairy sheep flock over 21 months.

	501	Figure 1.
	502
	503	R	1	2	3	4	5	6	7	8	9	10 11	12 13	R
														674 kb
														476 kb
														376 kb
														269 kb
														212 kb
														157 kb
														139 kb
														115 kb
														90 kb
														< 80 kb
	504
		Supplementary data-DNA array oligonucleotide 65-mer (Excel document)

Table I .

 I

	Table II.
			O54, O33 (sub.)	O47 (sub.)	O63 (sub.)	O64 (sub.)	O46 (sub.)	O11 (gangrenous)	O193, O194, O195, O196 (nares)	O197 (nares)	O198 (nares)	O200 (nares) O192 (air) O199 (nares)
	SdrD		-	Gene		-		-	Primers used in this study (5'-3') or author's --+ +	-	-	+	+	+
	FnbB a		+			+		+	+			+		references -	-	+	+	-	-	-
	SplE	SdrD (Mu50 NC_002758) --	-	-		AACGATTGTACCAGCCCAAG -+ +	-	-	+	+	+
	SAS0897 SAR1558		+ +			+ +		+ +	+ +			+ TTTGCAGTCGCAATTGTTTC --+ --	+ +	+ +	+ -	--	+ -
	SAR0940		+			+		+	+			+		-	-	+	+	+	-	+
	SAR2100		+	FnbB		+		+	+			+	Khun et al. [16] -	-	+	+	-	-	-
	SACOL0343		SplE (SAR1902) + +		+	+		CAGCCAAAGCCGAACATAAT + --	+	+	+	+	-
	Spa types		3568	3568		3568	3568			3568	524	524	3568	3568	524	524	524
	Spa Clonal										TATGTGCGCCAATTTCCATA
	Complex RAPD types b		SAS0897 1773 1773 R R2		1773 R	1773 GAGAACTTGCTGAAGCTATTGGA 1773 1773 1773 R R R1 R1	1773 R3	1773 R2	1773 R1	1773 R1	1773 R1
	PFGE types c		OV	OV		OV	OV	CCCTCCTTATCAAAATGAGCA OV OV' OV'	OV'''	OV	OV''	OV'	OV'
	MLVA types SAV 1078) d (coa, sdrD, sdrC, fnb, clfA, clfB,	SAR1558 B	F		E	D	CAAACCAAAAACGCAACAAG CAGGCGAAACGACATACTCA B A A	C	B	A	A	A
	Prophages e		SAR0940 A, B, Fb A, B, Fb	A, B, Fb	A, B, Fb	TTTGCGGACACTGTAGGATG A, B, Fb A, Fb A, Fb	A, B, Fb	A, B, Fb	A, B, Fb	A, Fb	A, Fb
	Ssl9 SNP f		1			2		2	2		ATTACCCGCTCTCTCACCAA 1 2 2	2	2	2	2	2
	Ssl4 SNP		1	SAR2100 N.D.		N.D.	N.D.		GCTGATGTTTTCGAGGTTGG 1 1 1	N.D.	1	N.D.	1	1
	Ssl2 SNP Sas types g		1 N.D.	N.D. N.D.		N.D. N.D.	N.D. N.D.	1 TACACCAGCAGAGACGCAAC 1 1 I II II	N.D. N.D.	1 N.D.	N.D. N.D.	1 N.D.	1 N.D.
			SACOL0343					CAAGCAATGAGGCATTCAGA
											GTCCGATAGCATTGGTCGTT

http://bugs.sgul.ac.uk/A-BUGS-17

http://bugs.sgul.ac.uk/E-BUGS-76

http://www.spa.ridom.de

http://bioedit.software.informer.com/

Bergonier D., personal communication.

ACKNOWLEDGEMENTS

We acknowledge G. Rossi for excellent technical assistance. We acknowledge H. Meugnier (INSERM U851, Centre National de Référence des Staphylocoques, Lyon, France) for the spa typing and clustering. We also acknowledge BµG@S (the Bacterial Microarray Group at St George's, University of London) for supply of the microarray and advice and The Wellcome Trust for funding BG@S under its Functional Genomics Resources Initiative. The support of the Réseau National Génopole TM and the CNRS (Centre National de la Recherche Scientifique) are greatly appreciated and we thank Dr P. Barbry. Caroline Le Marechal was recipient of a Ph.D. fellowship from Institut National de la Recherche Agronomique (INRA) and Agence Française de Sécurité Sanitaire des Aliments (AFSSA). Part of this work was supported by INRA-AFSSA transversality project (IMISa project).