I Morfin

E Buhler

F Cousin

I Grillo

F Boué

Rodlike Complexes of a Polyelectrolyte (Hyaluronan) and a Protein (Lysozyme) observed by SANS. Second revision (improvement of English) + SI DESCRIPTION INCLUDED, and with Scheme 2 reviewed

We study by Small Angle Neutron Scattering (SANS) the structure of Hyaluronan -Lysozyme 2 complexes. Hyaluronan (HA) is a polysaccharide of 9 nm intrinsic persistence length that bears one negative charge per disaccharide monomer (M mol = 401.3 g/mol); two molecular weights, M w = 6000 and 500 000 Da were used. The pH was adjusted at 4.7 and 7.4 so that lysozyme has a global charge of +10 and + 8 respectively. The lysozyme concentration was varied from 3 to 40 g/L, at constant HA concentration (10 g/L). At low protein concentration, samples are monophasic and SANS experiments reveal only fluctuations of concentration although, at high protein concentration, clusters are observed by SANS in the dense phase of the diphasic samples. In between, close to the onset of the phase separation, a distinct original scattering is observed. It is characteristic of a rod-like shape, which could characterize "single" complexes involving one or a few polymer chains. For the large molecular weight (500 000) the rodlike rigid domains extend to much larger length scale than the persistence length of the HA chain alone in solution and the range of the SANS investigation. They can be described as a necklace of proteins attached along a backbone of diameter one or a few HA chains. For the short chains (M w ~ 6000), the rod length of the complexes is close to the chain contour length (~ 15 nm).

I. Introduction

Hyaluronan (HA) is a linear semi-rigid polyelectrolyte with the repeating disaccharide structure poly((1→3)-β-D-GlcNAc-(1→4)-β-D-GlcA), with global formula C 14 H 20 NO 11 Na, for the Sodium salt form (see extended formula of the disaccharide unit in Scheme 1), molar mass 401.3 g/mol and length b segm close to 1 nm. HA is found in large quantities in animals and human body, where it is mainly produced by fibroblasts and other specialized connective tissues cells. It is a common component of synovial fluid and extracellular matrix and one of its assumed functions in the body is

joint lubrication.

Hyaluronan and hyaluronan-protein complexes. In joints as well in other situations, HA seems to have complex roles and its associations and interactions with proteins or other biomolecules are known to participate in many biological mechanisms that can even be opposite depending on the molecular mass. 1 Large masses are involved in ovulation, embryogenesis, regeneration, while small masses are inflammatory 2 , and very short ones are involved in the mobility of cancerous cells and stimulate neo-vascularization of tumors. In pharmacology, HA is widely used in dermatology, ophthalmology, and rheumatology 3 . In this last domain, different formulations of hyaluronic acid are used for arthritic patients, while proof of their efficiency remains to be established 4 .

Among the group of glycoaminoglycans (GAGs), HA is the only one that is not covalently associated with a core protein. Being charged, like DNA, HA has specific interactions with proteins (HAbp, HA bonding proteins, like CD44 which is important in cancer for example). In addition, HA has a repetitive primary structure that allows also nonspecific binding with proteins, via electrostatic interactions identical along the chain 5 , contrary to DNA. The charge density of the HA depends on pH of the solution since the dissociation coefficient of the carboxyl groups is pHdependent; such complexes depend therefore on pH (as well as on ionic strength). Detailed analysis and theory has been given by Cleland 6 . The first HA-protein complex structures have been studied by biologists for medical applications, using biological indirect investigation techniques. Only few recent works have investigated HA-protein complexes from a soft matter point of view [5][6][7] . For interaction of HA with BSA, identification by Integrated Computer Modeling and Light Scattering Studies of an Electrostatic Binding Site has been reported recently 7 . First, the dependence on salt concentration has been studied by Moss 5 , while the effect of pH is reported by Malay et al. 8 More recently, the effect of charge ratio has been considered by Lenormand 9 . Bovine serum albumin (BSA) was used as a model to study the HA-protein electrostatic complexes at pH=4 using zetametry and Uronic Assay. At low ionic strength, there is formation of (i) neutral insoluble complexes at the phase separation and (ii) small positively-charged or large negatively-charged 4 soluble complexes whether BSA or HA is in excess. Moreover, hyaluronidase, which catalyses HA hydrolysis, was also shown to form various types of complex with HA at low ionic strength, and to be in competition with BSA. These studies indicate that electrostatic parameters are important. On the reverse, some studies are missing: the effect of H-bonding, largely present between HA chains in pure HA aqueous solutions 10 , or the effect of molecular weight, observed in biological situations, have not been investigated. But also, none of these works gives information on the internal structure of complexes.

Parameters involved in the electrostatic complexes: Let us first review rapidly the experimental and theoretical works done on polyelectrolytes-proteins complexes or polyelectrolytes-polyelectrolytes complexes during the last few decades in order to detail all relevant parameters for complexation. Soft matter scientists were first interested on synthetic polyelectrolyte-protein complexes for fundamental research or technology. Using essentially techniques leading to general information (turbidimetry, rheology, spectrometry, light scattering or microscopy), studies focused on the solubility of the complexes and established phase diagrams, as reviewed by Tribet 11 and Cooper [START_REF] Cooper | [END_REF] . Natural polymer-protein complexes studies, taking into account many parameters like pH, ionic strength, and concentrations, have been also recently reviewed by Turgeon et al 13 . Electrostatic interactions have a dominant role in these systems. Charge densities, as shown experimentally, drive all signatures of complexation to their utmost for charge ratio introduced in solution ([-]/[+] intro ) equal to 1, which corresponds to neutralization of the complexes 14,15 (where the charge ratio [-]/[+] intro corresponds to the ratio between the negative and the positive charges carried respectively by the polymer and the protein). Surface charge densities are heterogeneous when proteins are involved instead of homogeneously charged spheres, so that patches of opposite charges enable electrostatic complexation with polyelectrolyte of the same global charge: this has been observed for polyanions at pH higher than the pI of the protein 16,17 .

Another key factor is the gain of entropy, observed by calorimetry 18,14,19 , and attributed to the 5 release of the counterions initially condensed on the chains or on the spheres. This has been shown recently for large globular complexes by direct structural measurement (scattering) of the counterion location 20 . However, complex coacervation could be enthalpy driven for less charged systems [21][22][23] . About ionic strength effect, while some experimental studies show that the Debye length κ -1 is the determining scale [START_REF] Cooper | [END_REF] , in accordance with simulations, another experiment has shown recently that a decrease of κ -1 (i.e. an increase of electrostatic screening), can increase the size of protein/ polyelectrolyte globules when they are present in the complexes 24 . The asymmetry of electrostatics around strongly patched proteins can also be important 26 .

Nevertheless, interactions other than electrostatics have to be considered, especially in natural polymer or proteins: hydrogen bonding, e.g. for PolyEthyleneOxyde (PEO) -or polysaccharidebased backbones, and hydrophobic interactions if the backbone of the polyelectrolyte is partially hydrophobic, e.g. due to alkyl chains [START_REF] Tribet | Surfactant science Series « physical chemistry of polyelectrolytes[END_REF]27 . In the latter case, interactions with hydrophobic patches on the protein can contribute to the formation of a complex 14,28 . Another effect of interactions can lead to changes in structure of one of the component: this has been observed for sodium polystyrene sulfonate, PSSNa, which unfolds lysozyme and napin protein, but not with another polyelectrolyte 29 .

An important parameter, which is relevant to this study, is the rigidity of the polymer chain (characterized by its persistence length L p ). All numerical studies underline the importance of the polyelectrolyte stiffness: complexation is abated when the polyelectrolyte is less flexible 30,31 . These main trends have been checked experimentally by Kayitmazer et al. who compare the binding of chitosan and PDADMAC, two polyelectrolytes with equal charge density but different persistence lengths, to oppositely charges micelles, dendrimers and proteins 32 . However the authors point out that the relevant parameter for binding is not necessarily the intrinsic persistence length of the chain L p , but the flexibility of the chain on the colloid length scale 32 .

6

In parallel, computer simulations also studied the role of electrostatic interactions in mixtures of charged strings with charged spheres and their interplay with parameters such as chain stiffness, at first in simulations involving only one protein and one polyelectrolyte chain 30,31 , and more recently on systems dealing with several proteins in the presence of an oppositely charged polyelectrolyte 33,34 . In ref [34], the heterogeneous charge density of proteins in the presence of weak polyelectrolyte has also been taken into account, whereby different chain lengths and ionic strengths were employed:

-large polyelectrolyte-protein clusters are simulated for the strongest electrostatic interactions, at least at stoichiometric charge ratio (with polyelectrolyte in excess, re-dissolution occurs, with proteins still attached to polyelectrolyte).

-clusters are smaller with shorter chains, and for increased ionic strength.

-complexation is reduced for more rigid chains.

Analytical theory has also been used. Reference [35] considers asymmetric mixtures of large macroions -sphere or chain, with smaller ionic species (called Z ions) of opposite charge, which can also be a short chain or a small sphere or ion. The different types of complexes are determined by the electrostatic screening and by the ratio [-]/[+] intro of total charges of Polycation and Polyanion in the solution. When this ratio [-]/[+] intro ~ 1, the authors 35 predict a condensation, that is the formation of "condensates" containing many large components (the macroions) -and therefore also many small Z-ions -with a spherical dense shape (which could be also called a globular shape). This regime of total condensation is sandwiched (for [-]/[+] intro < 1 or >1) by a regime of mixed complexation, where the condensates coexist with smaller complexes which could contain only one large macroions (and several small Z-ions) and could then be called "single complexes". In the case of small spherical Z-ions plus long macroions chains (flexible or semiflexible), these single complexes are of the bead-on-a-string type, also called by authors "artificial chromatin". Even further from the point [-]/[+] intro ~ 1, only small complexes are present.

Experiments on internal structures of complexes:

We wish to recall here some of the works where the internal structure, i.e. at distances larger than the protein size and lower than the cluster size, as well as the composition of complexes, has been described accurately using Small Angle Scattering techniques. This is the case of the work performed on polystyrene sulfonate-lysozyme complex systems using Small Angle Neutron Scattering (SANS) 15,24,29 , for which the systematic use of contrast matching enabled the investigation of the internal structures of the different compounds separately inside the complexes. [-]/[+] intro was established as a key parameter among several different general types of structures. For all other parameters fixed, as [-]/[+] intro varies, both species are quasi-totally associated in one of the following structures: (i) a gel where polymer chains are crosslinked by the proteins when polymer is in excess 29 or (ii) clusters with a well defined spherical shape, rather dense, which we called "globules": inside the two species are in close contact when proteins are in excess 29,15 . The globules are organized in fractal bunches as confirmed in real space by Electronic Microscopy 15 . SANS was also used recently on complexes of lysozyme and pectin, which being a natural polysaccharide could not be deuterated, but being semirigid (L p ~ 8 nm) allowed to check the effect of chain stiffness 36 : globules are also present here, and seem to be less dense (e.g. twice less dense) for such less flexible pectin chains. In spite of the complexity of pectin structure, electrostatic interactions, through the linear charge density, appear as the main parameter in the formation of large dense globules: hydrophobicity has a minor role. SANS (combined with SALS) has also been used to study coacervates of BSA with chitosan 37 (L p ~ 60 nm), which are largely solvated (84% of water), while they are denser (~ 75% of water) with the same protein and a more flexible polyelectrolyte, PDAMAC (L p ~ 2.5 nm) 38 , which points out again a role of polyelectrolyte chain stiffness. More recently, SANS was used for βlactoglobulin/pectin coacervates, and showed two kinds of microstructures, either protein molecules dispersed in the coacervate network, or protein domains enclosed in the interpenetrated pectin chains 39 . Networks of polymer-rich zones were also found for agar-gelatin complex coacervates, but with a correlation length around 1.2 nm only 40 .

The goal of the present work is the investigation of HA-lysozyme complexes for different HA molecular weights, pHs, ionic strengths of the solution, as a function of the charge ratio between the polymer and the protein. The choice of the HA polymer first comes from its primordial role in biological process as mentioned above but also because it is an excellent model of semi-rigid polyelectrolyte. Indeed, in spite of its natural origin, HA is a perfect linear homopolymer with a well defined intrinsic persistence length, i.e. in absence of electrostatic repulsion, of L p0 ~ 80 nm. This is well documented since HA has been studied as single specie in aqueous solution for some time 41 . We took particular advantage of direct studies of conformation using also neutron (combined with light) scattering, in pure solution 42 as well as in a mixture with another polyion, sodium polystyrene sulfonate (PSSNa) 43 . The choice of the lysozyme as protein is twofold as well:

we have a precise knowledge of the local structure of complexes of lysozyme with other polyelectrolytes, either flexible in case of PSSNa-lysozyme system 15,29 (where the flexible polyion conformation was measured even inside the complexes 25 ), or rigid in pectin-lysozyme system 36 , both studied by SANS. In addition, lysozyme is, like HA, present in the extracellular medium of the cartilage, whereas the roles of this protein, or the protein-HA complexes, have not yet been precisely established. This system has therefore also a biological interest. Moreover, extensions to mixtures of HA with other proteins are foreseen.

II. Materials and methods.

II.1. Components of the complexes and mixing procedure.

Two very different molecular weights of sodium hyaluronan were used: HA1, of small mass (Mn = 4700, M w = 6200, Soliance, Pomacle, France), and HA2, of large mass (M w > 500000, Sigma-Aldrich, ref. H9390). Knowing the segment mass (401.3 g/mol) and its length (b segm = 1 nm) the contour lengths are respectively L c = 15 nm and 1250 nm. It was mixed with hen egg white 9 lysozyme (HEWL, Sigma Aldrich, ref. 62970), well known as globular, enveloped inside an ellipsoid of size 4.5 x 3 x 3 nm 3 . Complexes were prepared at two different pHs in order to change [-]/[+] intro keeping the same concentration of the compounds. First pH = 4.7, used before 15,29 , was chosen because it is easily reached in acetic acid/sodium acetate buffer (0.05M/0.05M), and it is a good compromise for both the charge of lysozyme and HA, which remains still high. The ionic strength of this buffer 1 is I buffer = 0.1 M. Buffer 2 was prepared at pH = 7.4, in order to go towards pH conditions in tissues rich in HA (Extra Cellular Matrix, ECM). We used the following Phosphate Buffer Solution ("PBS") contents: to 10 mM of Na 2 HPO 4 where added 1.76 mM of KH 2 PO 4 and 2.7 mM of KCl. Following this composition and the literature 44 , the ionic strength I buffer is around 30 mM. To be closer to physiological conditions of ECM, to the mixture of such composition we added 137 mM of NaCl, leading to buffer 3, where total ionic strength I buffer is 170 mM. Samples made with this buffer are called "with salt".

All samples for SANS have been prepared the same way. Solutions of HA at 20 g/L (0.5 ml) and lysozyme at 40 g/L (or 80 g/L for few samples) were first prepared in the corresponding buffer 1, 2 or 3, made with D 2 O. Complexes were formed by adding various volumes of lysozyme and buffer solutions to HA solutions in order to have a final HA concentration equal to 10 g/L. Mixing is first done with a vortex. Temporary precipitation takes place instantaneously as lysozyme is added in all samples. After slow magnet stirring of the samples for at least 24 hours, they reach a stable state that is maintained a few weeks. Such protocol has been chosen as the best after that several others were investigated. SANS measurements are performed a few days after the mixture preparation, when solutions do not present any evolution with time, and before degradation of HA or lysozyme.

In any cases, mixing the samples for a longer time does not change the result. The other ways of mixing investigated before this one seems to show the same results after 24 or more hours. We performed SANS measurements just after that the visual aspect became stable,i.e. after 3 days and compared them to measurements after one week: they give the same SANS profiles. Visual observation of the samples a couple of weeks after the SANS measurements neither reveals any 10 modification. We therefore assumed that samples are stable or at least have a time evolution longer than 2 weeks.

We define the charge ratio [-]/[+] intro as the ratio between negative charges of hyaluronan at this pH, and the global charge of lysozyme at the same pH. Here [-]/[+] intro will decrease while lysozyme is added at constant concentration of HA, 10 g/L. At both pHs, HA is quasi-completely or completely dissociated 9 , and the number of charges is around 1 charge each monomer unit (which comprises 2 oses, see Scheme 1). For C HA = 10 g/L solutions, this gives 10/401= 0.025 negative charge per liter (and therefore an additional ionic strength due to sodium counterions of 12.5 mM).

At pH = 4.7, lysozyme (molar mass 14298) carries 10 charges per molecules, hence a positive charge molarity ((10/14298) * C Lyso moles/L of charges). The counterions, assumed monovalent, bring an additional ionic strength of 0.33 mM per g/L (e.g. 1 mM at 3.32 g/L and 13.3 mM at 40 g/L). At pH = 7.4, lysozyme has still a global charge positive but 20% smaller ((8/14298)* C Lyso ).

Table 1 and Table 2 list the sample concentrations, and [-]/[+]

intro for the two pHs for the large molecular weight HA2. Table 3 gives the characteristics of the different mixtures for the small molecular weight polymer, HA1, which was only studied at pH 7.4.

At the concentration 10 g/L, HA is in semidilute regime for the large mass 500 000: assuming a fully stretched chain of length L c , the radius of gyration R g = L c /√12 = 360 nm and the overlap concentration is very small, C* = M/(4π R g 3 /3) = 4.25 10 -3 g/L. Conversely, solutions of small mass HA1 are below c* (M = 5000, L c = 15 nm, C* = 25 g/L).

II.2. SANS measurements.

SANS measurements were performed on PACE spectrometer (Orphée reactor, LLB, CEA, Saclay, France) and on D11 and D22 spectrometer (ILL, Grenoble, France). Table 4 summarizes the different configurations (wavelengths λ, sample-detector distances, collimations...) leading to 11 the following q range 3.5 10 -3 < q (Å -1 ) < 3.5 10 -1 , where the wave vector, q, is defined as q = 4 π/λ sin(θ/2), θ being the scattering angle. Each time, detector efficiency was accounted by dividing by the scattering of water (H 2 O), an almost pure incoherent scatterer, which was also used as absolute intensity standard. All data are therefore in cm -1 .

We give below in Table 5 the scattering length density of the different species. First, for HA, ρ HA is calculated assuming complete dissociation of the sodium ion. This dissociation into water has a negative contribution of a few Å 3 per ion (-6.6 cm 3 /mole of ion, i.e. for a solution at 1 Mol/L, a relative variation of -7.10 -3 ) distributed over all the solvent volume, as explained in former papers 45 .

In terms of contrast this is equivalent, keeping the solvent density constant, to a relative increase of the volume of the HA unit V molecular by + 7.10 -3 , giving a quantity of the order of + 5 Å 3 , which is minute. Second, more important, is the effect of exchange of labile protons with the deuterons of the solvent. They are 5 per repetition unit, so that in a H 2 O/D 2 O mixture with a volume fraction of

D 2 O x D2O, ρ HA becomes ρ HA (x D20 ) = 2.3 + x D20 (5(b D -b H ))/V molecular (see Table 5 for 100% D 2 O).
We see also from Table 5 that the matching point of scattering of the two species HA or lysozyme in a proper H 2 O/D 2 O mixture would result in relatively small contrast for the other. We thus did not attempt matching experiments.

III. Results

III. 1 Macroscopic aspects.

The macroscopic visual aspect of the different samples is summarized in Scheme 2. In all cases without salt, below a particular [-]/[+] intro that can be slightly different for a sample to another, a phase separation is observed, between a supernatant solution (clear or turbid liquid), and a lower, thus denser, turbid one at the bottom of the cell. This lower phase looks like a gel for the larger polymer mass, and like a precipitate for the smaller one (in this case it that can be re-suspended by agitation for the time of measurement).

[Scheme 2] Scheme 2 must not be considered as a phase diagram. We will not discuss in details the reason of the slight [-]/[+] intro difference for a same event between the two pHs (which are not at the same ionic strength). The goal of the paper is not to investigate in detail the effect of pH or of the ionic strength, but rather to overview the general behavior of HA-lysozyme mixtures when [-]/[+] intro is varied. We will then see in the following whether the similarity between samples observed macroscopically is also found for scattering results.

III. 2. Scattering from single species.

Hyaluronan scattering: Figure 1 shows the scattering of the pure HA2 solution having the largest molecular weight, HA2. This rather weak signal was measured here only for reference. At large q, it displays a q -1 variation, within the error in background subtraction. When q decreases, the scattering crosses over, around 5. 10 -2 Å -1 , from a q -1 to a q -2 variation which is characteristic of a flexible chain at a scale larger than the persistence length 46 . Such cross-over value agrees with the value of the persistence length L p which has been determined in various conditions of polymer and salt concentrations directly on the form factor using SANS for HA 42 . An intrinsic value L p0 > 8 nm at least was found (a smaller value of 4 nm was given formerly using less direct methods 41 ), and due to electrostatic repulsion it can increase for weak ionic strength I as predicted by the Odijk-Skolnick-Fixman model (L pe = L p -L p0 ~ I -1 ) 47,48 . Here the total ionic strength is I ~ 50 mM, making L pe a few Angströms, which brings L p close to L p0 . The most important for the following is probably that the HA signal is always rather weak, compared to the signal measured for all samples except at large and low q for the complexes with C Lyso = 3.32 g/L. The low q upturn is due to the well known presence of some HA aggregates; its influence is discussed below. SANS measurements of pure solutions of HA1 (lowest molecular weight), not shown here, show also a usual behavior.

[Figure 1]

Lysozyme scattering: In the same Figure 1, the top curve is the scattering from a pure lysozyme solution, at 20 g/L in buffer at pH = 7.4 (I = 0.01 M):

-at large q, above 0.2 Å -1 , it varies like q -4 (Porod scattering associated to the sharp interface between the compact globular protein and the surrounding medium).

-between 0.2 Å -1 and 0.01 Å -1 , the curve flattens: this corresponds to the Guinier regime q. R gLyso < 1, (R gLyso radius of gyration of the protein); it must tend to a constant proportional to the mass and concentration of the protein.

-however, in the lowest q points, an upturn appears. Part of the increase of the zero-q limit could be associated with dimerisation -j-merisation of lysozyme 49 , but the main effect is likely due to larger protein aggregates 50 . Neglecting this slight upturn, the signal can be extrapolated to a zero q limit of 0.28 cm -1 , in agreement with contrast, volume, and density of lysozyme given in Table 5 NOTE 1 . It can also be fitted to the form factor of a polydisperse sphere of radius R = 1.55 nm as shown on Figure 1 with a slightly lower zero q limit, 0.23 cm -1 . We consider this difference negligible for our goal. The goal is to use this spectrum to compare with the HA signal. Assuming the signal as proportional to concentration at lower concentration, we extrapolate the signal at 3.32 g/L from the signal at 20 g/L, by dividing it by the concentration ratio 20/3.32, as also shown in Figure 1. This corresponds to the lowest lysozyme concentration used for the complexes. We see that even at this concentration, the protein scattering is larger than the HA signal in almost all q regions except at q < 0.014 Å -1 , and also close to the largest q values. At larger C Lyso the scattering of the protein is larger than the one of the HA for all q values. This remark prompts us to consider the HA signal to be a negligible contribution for lysozyme concentrations larger than 3.32 g/L. We 14 will discuss the latter case in detail below. -at low protein fractions (high [-]/[+] intro ), where an upturn that can not be attributed to the scattering of pure lysozyme and HA solutions is observed at low q, -at intermediate ones, where the scattering is characterized by a well defined q -1 region at intermediate q,

III

-at large protein fractions (low [-]/[+] intro ) where the previous q -1 power law disappears.

In the following, some of the scattering curves of these two figures will be selected and redrawn in complementary figures in order to discuss the structures at the different lengths scales and for the different charge ratio regimes.

III. 3. 2. Detailed SANS analysis.

III.3.2.1 Low protein fractions.

We give details here on the first type of profile, at high [-]/[+] intro , taking Figure 4 for illustration (pH 7.4). Here we present the scattering of a lysozyme corresponding to a 3.32 g/L solution.

Compared with this scattering are three samples (shown already in Figure 3) having the three lowest protein contents (3.32 g/L and 6.64 g/L and 8g/L of lysozyme, [-]/[+] intro = 13.4, 6.7 and 5.5). The third one (5.5) being diphasic, only the liquid fraction has been observed.

[Figure 4]

At large q, above 0.2 Å -1 , the scattering varies as a q -4 law, characteristic of sharp interfaces.

Figure 4 shows that it is possible to superimpose the data to the lysozyme alone at 3.32g/L by multiplying them by a given factor, F. For monophasic mixtures with 3.32g/L and 6.64g/L of lysozyme, F corresponds to 1 and ½, respectively: the high q signal corresponds to the lysozyme form factor. This also demonstrates that the proteins keep their native shape (no unfolding) and are still surrounded by solvent (their interface with solvent is still visible). The intensity of the signal is also the sign that the sample is monophasic. On the contrary, for the mixture containing originally 8g/L of lysozyme, the factor is ½ instead of 1/2.4, (from the ratio of the nominal lysozyme concentrations: 8/3.32) because the sample is diphasic: the missing lysozyme is indeed in the dense phase, which has sedimented at the bottom of the cell. This remark is true for all scattering curves 16 of diphasic samples shown in this work.

At intermediate and small q values, the sample scattering flattens with q decreasing, (as was observed on the pure lysozyme scattering (see III.2); this corresponds to a Guinier regime) but this flattening is followed at even lower q by an upturn for the three concentrations between 3.32 g/L and 8 g/L, as gathered on Figure 4 for pH 7.4. The 3 data for pH 4.7 also show this upturn in (the lowest concentration) is plotted and compared with the same spectrum after subtraction of the HA contribution. In the latter the upturn stays well defined with a slope close to -2.1 +/-0.02, indicating that a low q scattering identical to the one of the pure HA solution is not the major contribution to the low q scattering of the complexes.

III.3.2.2 Intermediate protein content and charge ratio (between monophasic and fully

diphasic systems): rod scattering. phase has a small volume located at the bottom of the cell). In this charge ratio range, the scattering keeps overlapping the form factor of the lysozyme at large q, as seen in insert of Figure 5, while a new type of variation with q, never seen before in protein-polyelectrolyte complexes at our knowledge, appears at lower q: a straight line corresponding to a q -1 power law. Such q -1 regime spreads over a large range of q, reaching the smallest q available in our experiments (3.10 -3 Å -1 ) for a particular charge ratio ([-]/[+] intro = 3.6, C Lyso = 10 g/L, pH = 4.7) as seen in Figure 5. The presence in solution of rigid domains that extend to larger length scale than the persistence length of the HA alone in solution may explain such power law. When varying the lysozyme concentration, the full curve is shifted by the same factor at all q. In other words, both the part of the curve showing the q -1 regime, and the part at large q corresponding to the lysozyme form factor, are multiplied by the same factor: this suggests strongly that the scattering is dominated by the lysozyme, and that all the proteins are belonging to the complexes.

[Figure 5]

III.3.2.3 Diphasic systems and globular objects.

A further increase of the lysozyme concentration leads to diphasic samples with an increasing quantity of dense phase. The SANS q -1 variation observed previously disappears at the two q range boundaries:

-at the low q, an upturn grows progressively and extends up to q ~1 10 -2 Å -1 . At pH 4.7, the upturn is first seen -this is moderate for this sample little-for [-]/[+] intro = 2.4 (C Lyso = 15 g/L), where a tiny volume of dense phase is seen, corresponding to the onset of phase separation. The upturn becomes clearly visible for [-]/[+] intro = 2.2 (C Lyso = 20 g/L) just above the onset. For higher protein contents (27 and 40 g/L), the volume of the dense phase increases and the upturn also increases; for 40 g/L it reaches a q -4 law (Porod scattering). This second Porod law at low q is the signature of large compact objects, which can contain both lysozyme and HA. This q -4 variation extends towards the lowest q values (as can be checked using a q 4 I(q) representation in Figure S.I.2 of Supporting Information): this means that the average global size of these objects is larger than 60 nm. We will call these objects "clusters" in the following.

-at the large q, around q max ~ 0.2 Å -1 , for the highest protein contents (27 and 40 g/L), the scattering of the dense phases is dominating since they occupy most of the volume. It has not the same shape than pure lysozyme at large q: a "shoulder" is observed in the scattering. It thus appears when the cluster scattering and the phase separation are sufficiently important. It could be the signature of proteins in close contact inside clusters, at a distance D = 2 π / q max ~ 3.1 nm. This distance D is close to (2. R lyso ), where R lyso is the average lysozyme radius. A correlation peak has been observed formerly in different systems, in particular for lysozyme mixed with PSS or pectin at the same q abscissa 13,34 .

[Figure 6] At pH 7.4 in Figure 3 a similar behavior than in Figure 2 is observed: an upturn as soon as C Lyso = 8 g/L, and a shoulder as soon as C Lyso =10 g/L. But, moreover, we can compare in Figure 6, the scattering measured completely separately for the two phases, liquid supernatant (two lower curves) and dense phase (two upper curves), for C Lyso = 10 and 40 g/L. The behaviors are different. For C Lyso =10 g/L, at smaller q, the signal of supernatant is close to the monophasic solution at 6.6 g/L (also shown on Figure 6), while the dense phase shows aggregation and a protein-to-protein shoulder. This indicates that the supernatant phase in equilibrium with the dense phase is close in structure to the monophasic samples. On the contrary, for C Lyso = 40 g/L, the signal of supernatant is the one of single lysozyme, while the dense phase shows even more pronounced aggregation and protein-to-protein shoulder (while the q -1 rod signal is still present). In the latter case, the supernatant signal suggests therefore that phase separation is completed: all complexes have precipitated into the dense phase, while the supernatant keeps the lysozyme in excess.

III.4 Large molecular weight HA2-lysozyme complexes with salt (physiological conditions of extracellular matrix).

The effect of salt (in PBS buffer) has been investigated for complexes made with high molecular weight HA (HA2). 137 mM of NaCl have been added to the initial buffer solution (final value I buffer = 170 mM) before mixing in the same proportions of HA2 and lysozyme than some of the samples without salt. In presence of salt, whatever the quantity of lysozyme added, samples never show a macroscopic phase separation. Nevertheless, for the largest lysozyme amounts (40 g/L), they are turbid and look like paste.

[Figure 7]

Figure 7 compares the scattering curves from samples with and without salt (pH 7.4). The behaviors are different at the two protein concentrations:

-for [-]/[+] intro giving monophasic samples in low salt conditions, the SANS profiles are not clearly modified by addition of salt.

-for [-]/[+] intro giving diphasic samples in low salt conditions, both the shoulder at large q, attributed to protein-to-protein stacking and the low q upturn disappear when adding salt.

Thus the formation of clusters is prevented by salt, probably due to electrostatic screening, while the single complexes observed in monophasic samples are not salt sensitive, at least at the scales observed by SANS.

III.5 Small molecular weight HA1-lysozyme complexes: short rods.

Figure 8 shows the scattering of the different samples listed in Table 3 (buffer pH is 7.4, I buffer = 30 mM and total ionic strength varies between 44 mM and 55 mM depending on lysozyme content).

The highest concentrations give diphasic samples, but the dense phase is composed of small solid objects visible by eyes which can be put in suspension by shaking the samples. For the lowest [-]/[+] intro , (C Lyso = 40 g/l), the scattering has been measured for the liquid supernatant only, as well as on the whole sample, after shaking the sample a few seconds just before recording the data: the two scatterings are essentially very close (Figure 8). The scattering at C Lyso = 27 g/L scale is also very close. At large q, a q -4 power law is observed, followed at intermediate q by a q -1 slope. Comparison with scattering from HA2 is enlightening:

-in the q -1 range, the intensity almost overlaps with the one for the large mass (HA2) at same pH 20 20 and same concentration, or shows proportionality to concentration NOTE 2 . This means that the protein linear density is the same along short and long chains.

-but at low q, very interestingly, the scattering is different from the HA2 one: for the small mass it reaches a plateau. Thus the radius of gyration, hence the length of the rodlike complexes, are smaller. Indeed the scattering matches a model of finite length cylinder, as shown in Figure 8 for C Lyso = 40 g/L (the same fit can be performed at C Lyso =27 g/L). We find a rod length of around 15 nm, close to the average contour length of a short HA1 chain (see II.1). A more accurate fit would require a more accurate knowledge of the molecular weight distribution of HA but would not modify the main conclusion: the rod length is the contour length of one chain. This excludes the fact that different short chains would connect at their ends, i.e. build some kinds of "splices", to form longer rods.

[Figure 8] IV. Discussion.

Let us first summarize the experimental facts: for the three systems, where the HA concentration is constant, a consistent picture arises (with many common features at pH 4.7 and 7.4):

(i) At low protein content the low q scattering (recorded for long chains only) presents an important upturn with a well defined q -2.1 variation. We have shown that it cannot be attributed to the pure HA solution scattering. Therefore it should come from concentration fluctuations of HA or lysozyme. The fact that this signal is close to proportional to protein concentration at constant HA concentration suggests that it comes from proteins, and can be interpreted by concentrations inhomogeneities. In summary, except for inhomogeneities of concentration seen at low q lysozyme appears dispersed in the network of hyaluronan chains.

21

(ii) For higher protein content, we observe the central feature of this paper: a q -1 power law which can be interpreted, using absolute units, as rod-like alignments of proteins, probably along HA chains. The apparent axial radius of the rod is the average radius of the lysozyme. For long HA chains, the rod length is much larger than the sizes accessible in our q range, thus can be as large as the length of the chains. For much shorter contour length HA chains, the rods are also much shorter, of the order of the chain contour length.

(iii) At protein concentration slightly larger than the threshold for the rod behavior (C Lyso_rod ) for pH 7.4, or simultaneously to its onset, for pH 4.7 (lysozyme is 20% more charged), two facts occur for samples without salt:

-macroscopically, the mixtures phase-separate.

-submicrocopic scales are investigated by scattering, which displays, for long chains, an upturn at low q (not investigated for short HA1 chains), overshadowing the rod signal, while a shoulder appears simultaneously at large q. This can be due to the formation of large dense clusters, like found for lysozyme with other polymers. With PSS and with pectin, which both show dense globules, the low q features are similar, and at the q abscissa of the shoulder a peak is present, unambiguously associated to contact between two proteins 27,34 .

Let us now discuss the picture we propose, in particular for the rod like structure, and their relation with phase separation. The fact that the rod scattering is proportional to C Lyso (in monophasic samples) suggests that the number of lysozyme per rod does not change deeply until phase separation occurs. This is seen also in the way the scattering crosses over with the large q single lysozyme scattering: if the protein linear density was increasing, the front factor of the q -1 regime would vary, resulting in a different aspect of the connection with the large q scattering. What we see suggests that when increasing C Lyso around [-]/[+] intro = 5, more "decorated rods" of same density are formed. When increasing C Lyso a little more, the solution becomes too concentrated in these decorated rods, and starts to separate in two phases. Data of Figure 6 suggest that some rods may stay present in the supernatant while they can also be observed in the dense phase (see Discussion above). However, soon above the phase separation threshold for C Lyso , a low q upturn points out the formation of larger clusters. Here again they can be detected in both phases, but their scattering becomes dominant at the highest lysozyme concentrations, in the dense phase. It is possible, but not proven, that the clusters contain rods. For the largest added amount of protein, all complexes are in the dense phase, where many clusters are present.

Two next questions, actually correlated, concern the composition in lysozyme and hyaluronan of the rods: (i) what is their charge, i.e. are they neutral, and (ii) how many HA chains do they contain? As inferred by the concentration dependence of I(q) ~ C Lyso shown in Figure 5, we can neglect the scattering coming from the HA. We can then quantify the dressing effect as follows. Let us consider, in a volume V, N rods rods of length L. We define ∆ρ Lyso 2 the contrast between the lysozyme and the solvent, v Lyso the molecular volume occupied by one lysozyme, N is the number of lysozyme per rods. For q >> 1/R grod (R grod = L/√12), the expression for a q -1 scattering of a rod dressed at random by N proteins is I(q), cm -1 = ∆ρ Lyso 2 . (N rods /V).(N . v Lyso ) 2 .π /q.L (1a) q >> 1/R grod = ∆ρ Lyso 2 . Φ Lyso . v Lyso π /q.a,

defining the protein volume fraction : Φ Lyso = (N rods /V). (N. v Lyso ), and N/L = 1/a. The volume of protein per length, v Lyso / a , is the relevant parameter given by the q -1 law. We use data for 10 g/L of lysozyme because we can safely assume that the nominal concentration is the actual one for this sample; and that all proteins belong to the rods (I(q) ~ Φ Lyso , as discussed above). Fitting the curve in the q -1 regime to Eq. (1b), we obtain a value for the front factor of the 1/q law, F(Φ Lyso ) = Φ Lyso .

∆ρ Lyso 2 . π v Lyso / a.

We can then use the fact that the zero q limit of the scattering measured for pure lysozyme is:

I 0 = lim q-> 0 I(q) = Φ Lyso . ∆ρ Lyso 2 .v Lyso (2 )
From the values of F(Φ Lyso ) and of lim q-> 0 I(q) we get NOTE 3 a value a ~ 8 nm.

To end this part, we note that the contour length of a HA chain of molar mass 500 000 is L cHA = 1250 nm (see II.1). If the rod has the same length, its radius of gyration will be equal to R grod = L/√12 ~ 360 nm. This makes that q.R grod >> 1 down to our lowest q accessible: the Guinier regime lies at much lower q than available, and a more detailed mathematical fit is not useful.

Our result suggests that proteins are aligned, with a linear density of one protein (of size 4.5 × 3.0 × 3.0 nm 3 ) over a length a = 8 nm (+/-10%.). Assuming N rods = N HA , i.e. one single HA chain in the core of the rod, with one monomer each 1 nm, this would give a ratio of 1 lysozyme for 8 HA segments. Since the global lysozyme charge is of + 10 at pH 4.7, the rodlike complex would be close to neutral, i.e the inner charge ratio within a rod phase separation occurs at concentration just above 10 g/L. We can also remark that bundles of several HA per rod makes possible to create rods longer than one HA chain contour length, by connecting chains along themselves ("splices"). This is not supported by observations in the case where we could check this in practice, namely for short HA (HA1): the rod length given by the fit is equal to the contour length of HA extracted from the molecular weight within our accuracy. All together we do not favor such "multi-HA" rod alternative but cannot exclude it.

Salt prevents the formation of clusters: this can be explained by the reduction of the strength of electrostatic interactions. However, surprisingly, salt does not influence strongly the rod-like structures, as far as we can see from our limited set of samples. It is therefore questionable that the interactions are purely electrostatic. H bonds could play an important role. More studies should be done along this line. Seen from another point of view, the lack of salt effect means that the persistence length of the rod is not sensitive to ionic strength, at variance with the one of Hyaluronan itself 40 which shows the predicted behavior of a model semi-rigid polyelectrolyte 43,45 .

The rigidification of the rod could therefore be ensured not only by electrostatic repulsion along the chain but also by the binding of the lysozyme on the HA. Eventually, and not prejudging the exact origin of the attraction, we can propose the simple picture schematized in Scheme 3. Note that the distance between two neighbor proteins should NOT be constant, since no correlation corresponding to a privileged distance is observed in the scattering.

[Scheme 3]

The dense objects -clusters-detected at high protein content (diphasic samples, second Porod law at low q) have a size too large ( > 60 nm) to be determined accurately. Anyway, they are noticeably larger than the globules in complexes of lysozyme with PSS, which is flexible (L p0 = 1 nm). Larger globules have already been observed with pectin, which is semiflexible (L p0 = 10 nm).

Thus in term of clusters size, the effect of chain rigidity is similar with pectin and with hyaluronan.

On the contrary, there is not such similarity for the rod behavior: for pectin 36 , it has not been observed. This may be due to difference in architecture: hyaluronan is strictly linear, with a single repeating unit, while the backbone of pectin is more complex: though some sections of the chains are linear, blocks with dangling parts of different components are present. Also pectin is only partially charged.

Theoretically, exclusively on the basis of electrostatics, Zhang and Schklovskii 35 have predicted both large dense clusters ("condensation") for [-]/[+] intro close to 1, and complexes of small mass for

[-]/[+] intro further from 1. In some cases these complexes can be rod-like (chromatin-like structure).

They have also predicted a coexistence of extended parts and neutral globular parts corresponding to a situation of "disproportionation". The scattering in some cases, for [-]/[+] intro close to 1, can be interpreted as such a coexistence of two signals, one from clusters, which may well correspond to the condensates, and one from the rod complex. But, from the discussion above, it appears possible that the rods are neutral and coexist with charged species. Finally other origins than electrostatic ones for the rods are possible. More work on different globular charged species, like other proteins or other types of charged spheres could allow us to answer this question.

V. Conclusion.

Performing several SANS measurements on HA-lysozyme samples allowed us to observe different complex structures depending essentially on the charge ratio. With an excess of HA, a network-like structure appears. For a charge ratio [-]/[+] intro slightly higher than unity for both pHs, an original rod-like structure extending to a size close to the contour length of the HA chain, for low mass chains, and larger than accessible sizes by SANS (60 nm) for large mass chains, is clearly displayed by the SANS measurements. All features of this scattering can be explained by a picture of proteins aligned along one single HA chain (though one rod could in principle contain several HA chains in bundle). For lower charge ratio and low salt concentration, a phase separation occurs and clusters larger than 60 nm appear. Our data do not allow us to decide whether Lysozyme-HA interactions are purely electrostatic, in particular those leading to the rod shape complexes.

Therefore, further studies using other proteins are forecast.

ACKNOWLEDGMENTS.

We thank Institut Laue Langevin and Laboratoire Léon Brillouin for beam time allocation. SANS scattering plotted as q 4 I(q) as a function of q for samples of Ha1 (small chains, 10g/L) and lysozyme for charge ratio -/+ = 0.45, 0.68 and 0.9 at pH 4.7, 0.1 M (same data as in upper curves of Figure 2 in the text). This material is available free of charge via the Internet at http://pubs.acs.org.

Supporting Information Available

NOTE 1:

Using Equation (2) given in the Discussion section, I 0 = lim q-> 0 I(q) = Φ Lyso . ∆ρ Lyso 2 .v Lyso (2 ) and the values of density of contrast ∆ρ Lyso 2 = 14.44 10 20 cm -4 and of volume 15000.10 -24 cm 3

given in Table 5, we obtain: I 0 = Φ Lyso . 14.44 10 20 . 15000 10 -24 = 21.7 Φ Lyso .

Using I 0 = 0.28 cm -1 , we obtain Φ Lyso = 1.29 10 -2 .

Since Φ Lyso = C Lyso . V (here C Lyso = 20 g/L = 2. 10 -2 g/cm 3 ) we get a specific volume V = 1/d (d density) for lysozyme 0.645 g/cm 3 comparable to the value 0.63 g/cm 3 evaluated formerly as given in Table 5.

NOTE 2:

In the q -1 range, the scattering intensity from small mass HA1 complexes quasi overlaps the ones for the large mass (HA2) at same concentration (8g/L, 0.0484 Å -1 : 0.084 cm -1 large mass and 0.10 cm -1 small mass) at same pH and same concentration, or proportionality to concentration is seen (e.g. at q = 0.05 Å -1 , I(q) = 0.2 cm -1 , for 27 g/L, and 0.11cm -1 for 10 g/L).

NOTE 3: For 10 g/L, one has I(q) = 0.1 cm -1 for q = 0.057 Å -1 , giving F from Eq. ( 1). For C Lyso = 20 g/L, I 0 ~ 0.28 cm -1 (see NOTE 1), giving I 0 ~ 0.14 cm -1 for C Lyso = 10 g/L. Finally, we get: a = 0.14 π. / (0.1 * 0.057) = 78.5 Å.

Another way of evaluating a , more direct, is the following: in insert of Figure 5, the scattering from lysozyme -renormalized to 10g/L-and the rod scattering cross each other at q = 0.04 Å -1 .

Using equality between Eq. ( 1) and Eq. ( 2), and because the lysozyme scattering is quasi-constant in this "flat" regime, this equality is equivalent to π /(q.a) = 1, i.e. a = π /q ~ 78.5 Å. or hyaluronan statistical unit 42,43 . FIGURES The green and blue straight lines correspond respectively to q -1 and q -4 . Curves are shifted by a factor ten from the one below. The bottom one as well as the scattering of the pure HA2 (-) are in cm -1 . Data within the grey area come from the dense phases. For 15 g/L, & even more for 20 g/L, a small volume of dense phase lied in the bottom but scattering was measured from the supernatant. Same data normalized by C Lyso (not shown ) show overlap at large q in the region of scattering dominated by lysozyme, except for samples at 15g/L and 20g/L; the latter is too low by a factor 5. END of the paper.

TABLES:

Concentration

. 3 .Figure 2 and 3 7 and 7 . 4 . 2 .[Figure 2 ][Figure 3 ]

 323774223 Figure 2 and 3 are the SANS curves of different HA-lysozyme mixtures respectively at pH = 4.7 and 7.4. All scattering intensity data of figure 2 are cm -1 , but each curve, when going from the

Figure 2 .

 2 Figure 2. This upturn cannot be attributed to the HA scattering contribution: this is established

Figure 5 3 . 6 ) 2 .

 5362 Figure 5 shows the scattering of mixtures in the intermediate range of charge ratio (2.2 ≤ ≤ ≤ ≤ [-]/[+] intro ≤ ≤ ≤ ≤ 3.6) at pH = 4.7, shown already in Figure 2. The scattering corresponds either to

  [-]/[+] inner ~ 1. This is far from the average introduced charge ratio, here [-]/[+] intro = 3.6 for C HA = 10 g/L, and C Lyso = 10 g/L, which corresponds to a ratio of 1 protein for 35 HA segments. Note that it is possible that some chains pertain to dressed rods, in coexistence with others which are free. In this case, [-]/[+] inner could be equal to 1 over a large lysozyme concentration. This would likely account for phase separation of neutral non repulsive species over a wide range of [-]/[+] intro . New neutral rods are progressively formed when protein is added, and progressively separate into the dense phase. When [-]/[+] intro approaches 1, all HA has been consumed, and we obtain the situation where all complexes are in the dense phase in the bottom of the cell (see results of Figure6for 40 g/L of lysozyme). This scenario involves "disproportionation" between neutral complexes and free charged species.An alternative is that the number of HA per rod NHA /Nrods is larger than 1: this agrees with data since Eq.(1b) is not sensitive to NHA /Nrods. Values slightly larger 1 should not affect the scattering since the scattering of individual HA chains is around 20 times lower than the rod one (see insert of

Figure 5 )

 5 Figure 5).A ratio of 1 protein for 35 HA on each rod, corresponding to the hypothesis that there are

Figure SI. 1 .

 1 SANS scattering I(q) at pH = 7.4 shifted by a factor 10, for sample of Ha1 (small mass, 10g/L) and lysozyme. Figure SI.2. SANS scattering I(q) at pH = 7.4, for sample of HA2 (10g/L) plus lysozyme 3.32g/L, subtracted from the scattering of pure HA solution at same HA concentration, and scattering of pure lysozyme solution at same concentration. Figure SI.3.

Figure 1 .

 1 Figure 1. SANS I(q) as a function of q for pure HA2 (large mass) solution ( ■ 10g/L,) and pure

Figure 2 .

 2 Figure 2. SANS I(q) for mixtures of HA2 (large mass, 10 g/L) and lysozyme, at pH = 4.7. On the left of the curves the [-]/[+] intro values and the presence of 2 phases (2 ph.) are indicated. [-]/[+] intro , decreasing from bottom to top, correspond to increasing lysozyme concentration one phase samples ▬: 3.32, +: 6.6, •: 8, *: 10, 2 phases samples •: 15,▲: 20, ■: 26 and ♦: 40 g/L.The green and blue straight lines correspond respectively to q -1 and q -4 . Curves are shifted by a factor ten from the one

Figure 3 .

 3 Figure 3. SANS I(q) for HA2 (large mass, 10g/L) with lysozyme at pH=7.4 (curves shifted by a factor 10; bottom in cm -1 ). The charge ratio are decreasing from bottom to top, corresponding to

Figure 4 .

 4 Figure 4.

Figure 4 .

 4 Figure 4. SANS scattering I(q) in buffer at pH = 7.4 for a lysozyme solution ( ▲: 3.32g/L) and mixtures of HA2 (large mass, 10g/L) and lysozyme ( ▄ :3.32g/L, ◄:6.64g/L, ♦:8g/L (liquid phase),

Figure 5 . 7 shown already in Figure 2 .

 572 Figure 5. SANS I(q) (not normalized by concentration) as a function of q presenting a large q -1

Figure 6 .

 6 Figure 6. Comparison of supernatant and dense phase: SANS scattering I(q) for mixtures of HA2

Figure 8 .

 8 Figure 8.

Figure 8 .

 8 Figure 8. SANS scattering as a function of q for sample of HA1 (small mass, 10g/L) and lysozyme:

Table 1 .

 1 Composition of the different mixtures lysozyme/HA2 in buffer pH 4.7, I = 0.1 M.

		Concentrati	Charge ratio
	HA2 (g/L)	on lysozyme (g/L)	[-]/[+] intro
	10	3.32	10.7
	10	6.6	5.36
	10	8	4.4
	10	10	3.6
	10	15	2.4
	10	20	2.2
	10	26.4	1.35
	10	40	1.1

Table 2 .

 2 Composition of the different mixtures lysozyme/HA2 at pH 7.4, I = 0.03 M.

	Concentration	Concentration	Charge ratio
	HA1	lysozyme (g/L)	[-]/[+] intro
	(g/L)
	10	3.32	13.4
	10	8	5.5
	10	27	1.63
	10	40	1.4

Table 3 .

 3 Composition of the different mixtures for lysozyme/HA1 (small molecular weight), in buffer at pH 7.4, I = 0.03 M.

	Instrument	Diaphragm (mm 2 )	Wavelength (Å)	Distances (m) Collimations (m)
	PACE	7 mm diameter 6	1	2.5
			6	4.5	5
			13	4.5	5
	D11	7 X 10 mm 2	4.6	1.1	5.5
			4.6	5	10.8
			4.6	12	13.5
	D22	7 X 10 mm 2	6	2	8
			6	5	8
			6	17	17.5

Table 4 .

 4 Configuration of the different SANS experiments.

	Species	V = 1/d	V mol cm 3	ρ specie	Density of contrast
					with D 2 O ∆ρ 2 (cm -4 )
	Lysozyme	0.63 cm 3 /g	15000.10 -24	2.5 10 10 cm -2 14.44 10 20
	Hyaluronan	0.59 cm 3 /g	398 10 -24	3.6 10 10 cm -2 7.3. 10 20

Table 5 :

 5 Scattering density per unit volume, calculated as ρ = Σ i n b i /( Σ i m i v i ×1.66×10 -24 ) where V is the inverse of density d, ρ represents the scattering length per unit volume, b i the scattering length, m i the mass, and v i the specific volume of the species i, id est lysozyme or D 2 O molecule36

Scheme 2: Evolution of the visual aspect of the different samples (HA2 in buffer at pH=4.7, I buffer = 0.1 M and HA2 and HA1 at pH 7.4, , no salt, I buffer = 0.03 M as a function of [-]/[+] intro . The HA concentration is kept at 10g/L. The concentration in lysozyme is indicated besides each symbol.


Thomas Philip Runarsson

Marc Schoenauer

Michèle Sebag

Pilot, Rollout and Monte Carlo Tree Search Methods for Job Shop Scheduling

Greedy heuristics may be attuned by looking ahead for each possible choice, in an approach called the rollout or Pilot method. These methods may be seen as meta-heuristics that can enhance (any) heuristic solution, by repetitively modifying a master solution: similarly to what is done in game tree search, better choices are identified using lookahead, based on solutions obtained by repeatedly using a greedy heuristic. This paper first illustrates how the Pilot method improves upon some simple well known dispatch heuristics for the job-shop scheduling problem. The Pilot method is then shown to be a special case of the more recent Monte Carlo Tree Search (MCTS) methods: Unlike the Pilot method, MCTS methods use random completion of partial solutions to identify promising branches of the tree. The Pilot method and a simple version of MCTS, using the ε-greedy exploration paradigms, are then compared within the same framework, consisting of 300 scheduling problems of varying sizes with fixed-budget of rollouts. Results demonstrate that MCTS reaches better or same results as the Pilot methods in this context.

Introduction

In quite a few domains related to combinatorial optimization, such as constraint solving [START_REF] Xu | Satzilla: Portfolio-based algorithm selection for sat[END_REF], planning or scheduling [2], software environments have been designed to achieve good performances in expectation over a given distribution of problem instances. Such environments usually rely on a portfolio of heuristics, leaving the designer with the issue of finding the best heuristics, or the best heuristics sequence, for his particular distribution of problem instances.

The simplest solution naturally is to use the default heuristics, assumedly the best one on average on all problem instances. Another approach, referred to as Pilot or rollout method, iteratively optimizes the option selected at each choice point [START_REF] Duin | The Pilot method: A strategy for heuristic repetition with application to the Steiner problem in graphs[END_REF][START_REF] Lagoudakis | Reinforcement learning as classification: Leveraging modern classifiers[END_REF], while sticking to the default heuristics for other choice points. Yet another approach, referred to as Monte-Carlo Tree Search (MCTS) [START_REF] Kocsis | Bandit based monte-carlo planning[END_REF] and at the origin of the best current computer-Go players [START_REF] Gelly | Combining online and offline knowledge in uct[END_REF], has been proposed to explore the search space while addressing the exploration versus exploitation dilemma in a principled way; as shown by [START_REF] Asmuth | Learning is planning: near Bayes-optimal reinforcement learning via Monte-Carlo tree search[END_REF], MCTS provides an approximation to optimal Bayes decision. The MCTS approach, rooted in the multi-Armed bandit (MAB) setting [START_REF] Lai | Asymptotically efficient adaptive allocation rules[END_REF], iteratively grows a search tree through tree walks. For each tree walk, in each node (choice point) the selection of the child node (heuristics) is handled as a MAB problem; the search tree thus asymmetrically grows to explore the most promising tree paths (the most promising sequences of heuristics).

Whereas increasingly used today in sequential decision making algorithms including games [START_REF] De Mesmay | Bandit-Based Optimization on Graphs with Application to Library Performance Tuning[END_REF][START_REF] Rolet | Boosting active learning to optimality: A tractable monte-carlo, billiard-based algorithm[END_REF], to our best knowledge MCTS methods have rarely been used within the framework of combinatorial optimization, with the recent exception of [START_REF] Matsumoto | Monte-Carlo Tree Search for a reentrant scheduling problem[END_REF]. This paper investigates the application of MCTS to job-shop scheduling, an NP-hard combinatorial optimization problem. As each job-shop scheduling problem instance defines a deterministic optimization problem, the standard upper confidence bound applied to tree (UCT) framework used in [START_REF] Matsumoto | Monte-Carlo Tree Search for a reentrant scheduling problem[END_REF] does not apply. More precisely, the sought solution is the one with best payoff (as opposed to the one with best payoff on average); the MAB problem nested in the UCT thus is a max k-armed bandit problem [START_REF] Streeter | A simple distribution-free approach to the max k-armed bandit problem[END_REF][START_REF] De Mesmay | Bandit-Based Optimization on Graphs with Application to Library Performance Tuning[END_REF]. Along this line, the randomized aspects in UCT must be addressed specifically to fit deterministic problems. Specifically, a critical difficulty lies in the randomized default handling of the choice points which are outside the current search tree (in contrast, these choice points are dealt with using the default heuristics in the pilot methods). Another difficulty, shared with most MCTS applications, is to preserve the exploration/ exploitation trade-off when the problem size increases. A domain-aware randomized default handling is proposed in this paper, supporting a MCTSbased scheduling approach called Monte-Carlo Tree Scheduling (MCS). MCS is empirically validated, using well established greedy heuristics and the pilot methods based on these heuristics as baselines. The empirical evidence shows that Pilot methods significantly outperform the best-known default heuristics; MCS significantly outperforms on the Pilot methods for small problem sizes. For larger problem sizes, however, MCS is dominated by the best Pilot methods, which is partly explained from the experimental setting as the computational cost of the Pilot methods is about 4 times higher than that of the MCS one. That is, heuristic scheduling is more costly than random scheduling.

The paper is organized as follows. Job-shop scheduling is introduced in Section 2, together with some basic greedy algorithms based on domain-specific heuristics called dispatching rules. The generic pilot method is recalled in section 3. The general MCTS ideas are introduced in section 4; its adaptation to the job-shop scheduling problem is described and an overview of MCS is given. and together with its application to combinatorial problems, and to the jobshop scheduling problem. Section 5 is devoted to the empirical validation of the proposed approach. After describing the experimental setting, the section reports on the MCS results on different problem sizes, with the dispatching rules and the Pilot methods as baselines. The paper concludes with a discussion of these results and some perspectives for further research.

Scheduling is the sequencing of the order in which a set of jobs j ∈ J := {1, .., n} are processed through a set of machines a ∈ M := {1, .., m j }. In a job shop, the order in which a job is processed through the machines is predetermined. In a flow shop this order is the same for all jobs, and in a open shop the order is arbitrary. We will consider here only the job shop, where the jobs are strictlyordered sequences of operations. A job can only be performed by one type of machine and each machine processes one job at a time. Once a job is started it must be completed. The performance metric for scheduling problems is generally based on flow or dues date. Here we will consider the completion time for the last job or the so called makespan.

Each job has a specified processing time p(j, a) and the order through the machines is given by the permutation vector σ (σ(j, i) is the i th machine for job j). Let x(j, a) be the start time for job j on machine a, then x(j, σ(j, i)) ≥ x(j, σ(j, i -1) + p(j, σ(j, i -1)) j ∈ {1, .., n}, i ∈ {2, .., m j } (1)

The disjunctive condition that each machine can handle at most one job at a time is the following:

x(j, a) ≥ x(k, a) + p(k, a) or x(k, a) + p(k, a) ≥ x(j, a) (2)
for all j, k ∈ J, j = k and a ∈ M . The makespan can then be formally defined as z = max{x(j, σ(j, m j )) + p(j, m j ) | j ∈ J}.

Smaller problems can be solved using a specialized branch and bound procedure [START_REF] Brucker | Scheduling algorithms[END_REF] and an algorithmic implementation may be found as part of LiSA [START_REF] Bräsel | LiSA -Library of Scheduling Algorithms[END_REF]. Jobs up to 14 jobs and 14 machines can still be solved efficiently, but at higher dimensions, the problems rapidly become intractable. Several heuristics have been proposed to solve job shop problems when their size becomes too large for exact methods. One such set of heuristics are based on dispatch rules, i.e. rules to decide which job to schedule next based on the current state of all machines and jobs. A survey of over 100 such rules may be found in [START_REF] Panwalkar | A Survey of Scheduling Rules[END_REF]. Commonly used priority dispatch rules have been compared on a number of benchmark problems in [START_REF] Kawai | An efficient combination of dispatch rules for job-shop scheduling problem[END_REF]. When considering the makespan as a performance metric, the rule that selects a job which has the Most WorK Remaining (MWKR, the job with the longest total remaining processing time) performed overall best. It was followed by the rule that selects a job with the Shortest Processing Time (SPT), and by the rule that selects a job which the Least Operation Number (LOPN). These rules are among the simplest ones, and are by no means optimal. However, only these 3 rules will be considered in the remaining of this paper. In particular, experimental results of the corresponding 3 greedy algorithms can be found in Section 5.

The simplest way to use any of these rules is to embed them in a greedy algorithm: the jobs are processed in the order given by the repeated application of the chosen rule. Algorithm 1 gives the pseudo-code of such an algorithm. The variable t j represents which machine is next in line for job j (more precisely machine σ(j, t i )). When starting with an empty schedule, one would set t j ← 1 for j ∈ J and S = ∅. At each step of the algorithm, one job is chosen according to the dispatching rule R (line 2), and the job is scheduled on the next machine in its own list, i.e., the pair (job, machine) is added to the partial schedule S (line 3) (⊕ denotes the concatenation of two lists). The pilot method [START_REF] Duin | The Pilot method: A strategy for heuristic repetition with application to the Steiner problem in graphs[END_REF][START_REF] Voß | Looking ahead with the pilot method[END_REF] or equivalently the Rollout algorithm [START_REF] Bertsekas | Rollout algorithms for combinatorial optimization[END_REF] can enhance any heuristic by a simple look-ahead procedure. The idea is to add one-step look-ahead and hence apply greedy heuristics from different starting points. The procedure is applied repeatedly, effectively building a tree. This procedure is not unlike strategies used in game playing programs, that search a game trees for good moves. In all cases the basic idea is to examine all possible choices with respect to their future advantage. An alternative view is that of a sequential decision problem or dynamic programming problem where a solution is built in stages, whereby the components (in our cases the jobs) are selected one-at-atime. The first k components form a so called k-solution [START_REF] Bertsekas | Rollout algorithms for combinatorial optimization[END_REF]. In the same way as a schedule was built in stages in Algorithm 1, where the k-solution is the partial schedule S. However, for the Pilot method the decisions made at each stage will depend on a look-ahead procedure. The Pilot method is then described in Algorithm 2. The algorithm may seem a little more complicated than necessary, however, as will be seen in the next section this algorithm is a special case of Monte Carlo tree search. The heuristic rollout is performed B times and each time adding a node to the tree. Clearly if all nodes can be connected to a terminal node, the repetition may be halted before the budget B is reached. This is not shown here for clarity. Furthermore, a new leaf on the tree is chosen such that those closer to the root have priority else branches are chosen arbitrarily with equal probability. In some version of the Pilot method, the tree is not expanded breadth first manner but with some probability allows for depth first search.

This would be equivalent to executing line 8 with some probability. This is also commonly used in MCTS and is called progressive widening. The greedy algorithm 1 is then used as the Rollout algorithm on line 23. As will be seen in the following section, the key difference between the MCTS and Pilot method is in the way a node is found to expand in the tree and the manner in which a rollout is performed. Other details of the Algorithm 2 will also become clearer.

Monte Carlo Tree Search

Monte-Carlo Tree Search inherits from the so-called Multi-Armed Bandit (MAB) framework [START_REF] Lai | Asymptotically efficient adaptive allocation rules[END_REF]. MAB considers a set of independent k arms, each with a different payoff distribution. Here each arm corresponds to selecting a job to be dispatched and the payoff the results returned by a rollout or greedy heuristic. Several goals have been considered in the MAB setting; one is to maximize the cumulative payoff gathered along time (k-arm bandit) [START_REF] Auer | Finite-time analysis of the multiarmed bandit problem[END_REF]; another one is to identify the arm with maximum payoff (max-k arm) [START_REF] Cicirello | The max k-armed bandit: A new model of exploration applied to search heuristic selection[END_REF][START_REF] Streeter | A simple distribution-free approach to the max k-armed bandit problem[END_REF][START_REF] De Mesmay | Bandit-Based Optimization on Graphs with Application to Library Performance Tuning[END_REF]. At one extreme is the exploitation-only strategy (selecting the arm with best empirical reward); at the other extreme is the exploration-only strategy (selecting an arm with uniform probability).

When it comes to find a sequence of options, the search space is structured as a tree 5 . In order to find the best sequence, a search tree is iteratively used and extended, growing in an asymmetric manner to focus the exploration toward the best regions of the search space. In each iteration, a tree path a.k.a simulation is constructed through three building blocks: the first one is concerned with navigating in the tree; the second one is concerned with extending the tree and assessing the current tree path (reward); the third one updates the tree nodes to account for the reward of the current tree path.

Descending in the tree The search tree is initialized to the root node (current partial schedule). In each given node until arriving at a leaf, the point is to select among the child nodes of the current node (Fig. 1, left). For deterministic optimization problems, the goal is to maximize the maximum (rather than the expected) payoff. For this aim, a sound strategy has been introduced in [START_REF] Streeter | A simple distribution-free approach to the max k-armed bandit problem[END_REF] and used in [START_REF] De Mesmay | Bandit-Based Optimization on Graphs with Application to Library Performance Tuning[END_REF]. This approach, referred to as Chernoff rule, estimates the upper bound on the maximum payoff of the arm, depending on its number of visits and the maximum value gathered.

However, the main goal of this work is to bridge the gap between the Pilot method and MCTS algorithms. Indeed, the Pilot method, as presented in algorithm 2, can be viewed as an MCTS algorithm in which the strategy used to chose next child to explore is to choose the best child after one deterministic rollout using the dispatch rule at hand -a rather greedy exploitation-oriented strategy. Such strategy is very close to a simple rule to balance exploration and exploitation known in the MCTS world as -greedy: with probability 1 -, one selects the empirically best child node 6 (i.e. the one with maximum empirical value); otherwise, another uniformly selected child node is retained. Furthermore, similar to the Pilot method described in the previous section, unexplored nodes (line: 8 in Algorithm2) will have priority. However, line: 10 should be replaced by

Q(j) ← node.child[j].Q .
Extending the tree and evaluating the reward Upon arriving in a leaf, a new option is selected and added as child node of the current one; the tree is thus augmented of one new node in each simulation (Fig. 1, right). The simulation is resumed until arriving in a final state (e.g., when all jobs have been processed).

As already mentioned, the choices made in the further choice points in the Pilot method rely on the default heuristics (and the rollout is hence deterministic). In the MCTS method however, these choices must rely on randomized heuristics out of consistency with the MAB setting. The question thus becomes which heuristics to use in the so-called random phase (see section 4.2). Upon arriving in a final state, the reward associated to the simulation is computed (e.g., the makespan of the current schedule).

Fig. 1. Monte-Carlo Tree Search: the tree is asymmetrically grown toward the most promising region (in grey, the known part of the tree). Each simulation is made of a MAB phase (1); then the simulation is completed until arriving at a final state (2); finally, the first node of the Monte-Carlo path is added to the known tree, and the reward is computed and back-propagated to all nodes of the path that are in the known tree (3).

Updating the tree The number of visits of the nodes of the current tree that were in the path is incremented by 1; likewise, the cumulative reward associated to these nodes is incremented by the reward associated to the current path. Note that other statistics can be maintained in each node, such as the RAVE values [START_REF] Gelly | Combining online and offline knowledge in uct[END_REF], and must be updated there too.

Monte-Carlo Tree Schedule (MCS)

As already pointed out, solving a combinatorial problem can be viewed as a sequential decision making process, incrementally building a solution by choosing an element of a partial solution at a time (e.g., next town for TSP problems, of next machine to schedule for the job shop scheduling problem). In order to solve this sequential decision problem through a MCTS algorithm, several specific issues must be considered.

A first issue concerning the reward design has a significant impact on the exploration versus exploitation dilemma; it might require some instance-dependent parameter to reach a proper balance (see e.g., [START_REF] Fialho | Dynamic multi-armed bandits and extreme value-based rewards for adaptive operator selection in evolutionary algorithms[END_REF]). Indeed, in the case of job-shop scheduling for instance, different instances will have very different makespans.

A second issue concerns the heuristics to be used in the random phase (section 4.1). The original MCTS method [START_REF] Kocsis | Bandit based monte-carlo planning[END_REF] advocates pure random choices. Domain knowledge could however be used to propose a smarter procedure, e.g. using random selected dispatching rules for job-shop scheduling. Still, a lesson consistently learned from MCTS applications [START_REF] Gelly | Combining online and offline knowledge in uct[END_REF][START_REF] De Mesmay | Bandit-Based Optimization on Graphs with Application to Library Performance Tuning[END_REF] is that doing many simulations completed with a brute random phase is more effective than doing less simulations completed with a smart final phase. For instance in the domain of computer-Go, the overall results were degraded by using gnuGo in the random phase, compared to a uniform move selection. Likewise, the use of the three dispatching rules (described in Section 2) in the random phase was outperformed by a pure random strategy, uniformly selecting the next job to be considered. Here we have chosen to follow this path and our rollout phase consists of the purely random dispatching of jobs. Replacing this with line 23 in Algorithm 2, along with the ε-greedy policy, and the Pilot method is transformed into MCTS.

Another important detail must be taken into account: When performing random rollouts, we might forget the best choices found previously during the building of a schedule. For this reason, a global best found sequence is kept throughout the scheduling procedure. If a suboptimal choice is found in a later partial schedule (k-solution), the globally better choice previously found during a random rollout will be forced. In some sense the idea here is similar to that of the fortified rollouts used by the Pilot method [START_REF] Voß | Looking ahead with the pilot method[END_REF].

Finally, in MCTS, the stopping criterion is defined by the total number of simulations (i.e., rollouts here), and one single decision is taken after a complete tree exploration, chosen as the child of the root node with the maximum expected reward [START_REF] Gelly | Combining online and offline knowledge in uct[END_REF]. The situation is rather different here, and, in this first approach to MCTS for combinatorial optimization, similarly to the Pilot method, a single tree exploration is done, with a limited budget in terms of number of rollouts. A complete schedule is then built by descending the tree and always choose the child with maximum expected reward (makespan). This section reports on the experimental validation of the proposed approaches. After detailing the experimental setting, the results of the MCS method is reported and compared to the baseline methods, the greedy application of the three dispatching rules MWKR, SPT and LOPN (section 2), and the pilot methods built on these three dispatching rules (section 3).

Experimental Settings

All experiments have been conducted using the set of test instances proposed in [START_REF] Taillard | Benchmarks for basic scheduling problems[END_REF]. The machine orders for the jobs are randomly generated and the processing times are discrete values uniformly distributed between 1 and 200. Three different n × m problem sizes were generated using this setup, 6 × 6, 10 × 10 and 14 × 14.

The optimal makespans for one hundred instances generated of each size was then found using Brucker's branch and bound algorithm [START_REF] Brucker | Scheduling algorithms[END_REF]. A further four instance of size 20 × 20 are also tested [START_REF] Yamada | A genetic algorithm applicable to large-scale job shop Problems[END_REF] and compared with their best known solution [START_REF] Banharnsakun | Job Shop Scheduling with the Best-so-far ABC[END_REF].

For all methods except the greedy ones, the time budget is varied to assess the convergence behavior of the pilot and MCS optimization methods, considering a total of 100, 1,000 and 5,000 rollouts a.k.a. simulation. Each rollout corresponds to designing and evaluating a complete solution (computing its total makespan). It is worth noting that not all rollouts are equally expensive; the rollout based on a dispatching rule (as used in the pilot methods) is more computationally demanding than the random rollout used in MCS, all the more so as the size of the problem instance increases. Nevertheless, the fixed rollout budget is meant to allow CPU-independent comparisons and assess the empirical behavior of the methods under restricted computational resources (e.g. in real-world situations).

For each method, each problem size and each time budget, the result is given as the average over 100 problem instances of the normalized makespan (1. being the optimal value), together with the minimum, maximum and median values, and the standard deviation; the number of times where the optimal value was found is additionally reported.

While the greedy and pilot algorithms actually are deterministic 7 , MCS is not. The usual way to measure the performance of a stochastic algorithm on a given problem domain is through averaging the result out of a few dozen or hundred independent runs. For the sake of computational convenience however, MCS was run only once on each problem instance and the reported result is the average over the 100 independent instances.

The Greedy Algorithms

The results of the greedy algorithms are depicted in Table 1 for the three dispatching rules MWKR, SPT and LOPN (section 2), showing that MWKR and LOPN behave similarly and significantly outperform SPT. Further, the performances of SPT significantly decrease with the problem size, whereas MWKR and LOPN demonstrate an excellent scalability in the considered size range.

The Pilot Method

The results of the pilot method (section 3) related to the three above dispatching rules and three time budgets (100, 1000 and 5000) are displayed in table 2 for all three problem sizes 6 × 6, 10 × 10, and 14 × 14. For the sake of easy comparison with the greedy algorithm, the median performances respectively obtained on the same problem sizes displayed on Table 3.

As was expected, and demonstrated on some TSP instances by [START_REF] Duin | The Pilot method: A strategy for heuristic repetition with application to the Steiner problem in graphs[END_REF], the pilot method does improve on the greedy algorithm. With a time budget 100, a significant improvement is observed for all three methods, and confirmed by the number of times the optimal solution is discovered on problem size 6 x 6.

It is worth noting that the performance only very slightly improves when the time budget increases from 100 to 1000, and from 1000 to 5000, despite the significant increase in the computational effort. In particular, the optimal solutions are never discovered for higher problem sizes.

Lastly, the performance order of the three rules is not modified when using the pilot method: MWKR and LOPN significantly outperform SPT. As a consequence the Pilot method can be quite sensitive to the Pilot heuristic chosen.

Monte-Carlo Tree Schedule

Table 4 reports on the results of the MCS approach described in (section 4). On problem size 6x6, MCS significantly improves on the best Pilot method (MKWR with 5000 rollout budget), as also witnessed by the number of times the optimal solution is found. On problem size 10x10, the average and median performances are comparable; still, the optimal solution is found twice by MCS with a 5000 rollout budget, whereas it is never found by the Pilot method.

On problem size 14x14, Pilot (MWKR,5000) is significantly better than MCS. A first explanation for this fact relies on the computational effort: As already mentioned, the computational time required for a 5,000 rollout Pilot is circa 4 times higher than for a 5,000 rollout MCS. A second explanation is the fact that, as the tree depth increases with the problem size, it becomes necessary to adjust the parameters controlling the branching factor of the MCS tree. This can be achieved by introducing progressive widening (on-going work).

Larger Instances

The best known solutions (BKS) for the 20 × 20 benchmark problem [START_REF] Yamada | A genetic algorithm applicable to large-scale job shop Problems[END_REF] are taken from [START_REF] Banharnsakun | Job Shop Scheduling with the Best-so-far ABC[END_REF]. Here we demonstrate the performance of the MCS on problems that cannot be solved using exact methods. Only four instances are considered here, and the MCS is run 30 times on each instance. The method is unable to find any best known solution. Nevertheless, the performance does not degrade significantly when compared to the results obtained on the 10 × 10 problems.

Discussion and Perspectives

The main contribution of this paper is to demonstrate the feasibility of using MCTS to address job-shop scheduling problems. This result has been obtained by using the simplest exploration/exploitation strategy in MCTS, the ε-greedy strategy, defining the Monte-Carlo Tree Scheduling approach (MCS). The empirical evidence gathered from the preliminary experiments presented here shows that MCS significantly outperforms its competitors on small and medium size problems. For larger problem sizes however, the Pilot method with the best dispatching rule outperforms this first verions of MCS. This fact is blamed on our adversary experimental setting, as we compared methods based on the number of rollouts, whereas the computational cost of a rollout is larger by almost an order of magnitude in the Pilot framework, as compared to that of the MCS.

The MCS scalability can also be improved through reconsidering the exploration vs exploitation trade-off, ever more critical in larger-sized problem instances. First of all, the MAX-k-arm strategy should be tried in lieu of the simple ε-greedy rule. Furthermore, this tradeoff can be also adjusted by avoiding the systematic first trial of all possible children, as this becomes harmful for large number or arms (jobs here). It is possible to control when a new child node should be added in the tree, and which one. Regarding the former aspect, a heuristics referred to as Progressive Widening has been designed to limit the branching factor of the tree, e.g. [START_REF] Rolet | Boosting active learning to optimality: A tractable monte-carlo, billiard-based algorithm[END_REF] . Regarding the second aspect, the use of a Rapid Action Value Estimate (RAVE), first developed in the computer-Go context [START_REF] Gelly | Combining online and offline knowledge in uct[END_REF] can be very efficient to aggregate the various rewards computed for the same option (Queen Elisabeth), and guide the introduction of the most efficient rules/jobs in average.

Conclusion and outlook

This work has shown how the Pilot method may be considered a special case of MCTS, with an exploratory-only strategy to traversing the tree and using a deterministic rollout driven by the Pilot heuristic. It has demonstrated that the Pilot method can be sensitive to the chosen Pilot heuristic. As the chosen Pilot heuristic becomes more effective, so too may its computational costs. An extension of the Pilot method in the realm of MCTS algorithms, the MCS, has been proposed, using a simple -greedy strategy to traverse down the tree. However, more sophisticated strategies, such as the one based on the max-k bandit problem [START_REF] Streeter | A simple distribution-free approach to the max k-armed bandit problem[END_REF][START_REF] Cicirello | The max k-armed bandit: A new model of exploration applied to search heuristic selection[END_REF], need now be investigated. For larger problems, progres-sive widening should be an avenue for further research, as similar strategies have already been investigated in the Pilot framework. Finally, Rapid Action Value Estimates may not only be used to bias how the tree is traversed, possibly replacing the exploration term in the bandit formulas, but can also help to improve over the random rollouts.

Algorithm 1 :

 1 Greedy (Pilot) heuristic input : Partial sequence S0, t = (t1, . . . , tn), and heuristic R output: An objective to maximize, for example negative makespan while ∃j ∈ J ; tj < mj do 1 b = R(S, tj ; tj < mj) ; // Apply R to current partial schedule, get next job 2 S ← S ⊕ {(b, σ(b, t b ))} ; // Schedule job on its next machine 3 t b ← t b + 1 ; // Point to next machine for job b

Table 1 .

 1 Greedy algorithms: Performance statistics of the MWKR, SPT and LOPN rules on three problem sizes.

	Instance Heuristic min mean median stdev max #opt
	6 × 6	MWKR 1.000 1.155 1.151 0.084 1.384 2
		SPT	1.137 1.399 1.390 0.150 1.816 0
		LOPN 1.017 1.176 1.178 0.083 1.369 0
	10 × 10 MWKR 1.096 1.228 1.222 0.069 1.430 0
		SPT	1.303 1.654 1.644 0.166 2.161 0
		LOPN 1.103 1.216 1.208 0.061 1.369 0
	14 × 14 MWKR 1.159 1.264 1.261 0.052 1.399 0
		SPT	1.584 2.012 2.015 0.244 2.721 0
		LOPN 1.150 1.253 1.250 0.048 1.376 0

Table 3 .

 3 Comparison of median performances of Greedy and Pilot with different budgets, for the 3 heuristics (from Tables1 and 2).

				Algorithm (budget)
				Pilot (100) Pilot (1000) Pilot (5000)
	6 × 6	MWKR 1.151	1.050	1.030	1.014
		SPT	1.390	1.093	1.060	1.049
		LOPN 1.178	1.057	1.036	1.024
	10 × 10 MWKR 1.222	1.109	1.096	1.083
		SPT	1.644	1.221	1.188	1.168
		LOPN 1.208	1.114	1.105	1.092
	14 × 14 MWKR 1.261	1.155	1.138	1.129
		SPT	2.015	1.380	1.319	1.283
		LOPN 1.250	1.161	1.152	1.142
	Instance Heuristic		min mean median stdev max #opt
	6 × 6
		MCS(ε-greedy,100) 1.000 1.026 1.020 0.027 1.097 28
		MCS(ε-greedy,1000) 1.000 1.014 1.001 0.025 1.150 50
		MCS(ε-greedy,5000) 1.000 1.007 1.000 0.017 1.082 72
	10 × 10
		MCS(ε-greedy,100) 1.029 1.141 1.140 0.057 1.378 0
		MCS(ε-greedy,1000) 1.014 1.095 1.098 0.036 1.199 0
		MCS(ε-greedy,5000) 1.000 1.070 1.070 0.032 1.135 2
	14 × 14
		MCS(ε-greedy,100) 1.173 1.346 1.331 0.083 1.634 0
		MCS(ε-greedy,1000) 1.127 1.284 1.280 0.074 1.552 0
		MCS(ε-greedy,5000) 1.064 1.232 1.223 0.065 1.471 0

Table 4 .

 4 Monte-Carlo Tree Schedule. Performance statistics using ε-greedy and random scheduling.

Table 5 .

 5 Results for the MCS on four 20 × 20 instances. Performance statistics is given for 30 independent runs on each instance, yn01,. . . , yn04.

	Instance Heuristic	min mean median stdev max #BKS
	yn01	MCS(ε-greedy,100) 1.166 1.211 1.210 0.020 1.245	0
		MCS(ε-greedy,1000) 1.144 1.186 1.183 0.021 1.235	0
		MCS(ε-greedy,5000) 1.128 1.167 1.166 0.023 1.209	0
	yn02	MCS(ε-greedy,100) 1.135 1.185 1.181 0.024 1.228	0
		MCS(ε-greedy,1000) 1.123 1.156 1.153 0.023 1.218	0
		MCS(ε-greedy,5000) 1.090 1.130 1.130 0.023 1.174	0
	yn03	MCS(ε-greedy,100) 1.156 1.205 1.204 0.022 1.267	0
		MCS(ε-greedy,1000) 1.131 1.178 1.180 0.020 1.222	0
			1.110 1.151 1.148 0.023 1.199	0
	yn04	MCS(ε-greedy,100) 1.063 1.108 1.107 0.025 1.160	0
		MCS(ε-greedy,1000) 1.039 1.084 1.090 0.025 1.133	0
		MCS(ε-greedy,5000) 1.023 1.067 1.064 0.019 1.102	0

Actually, the search space may be structured as a graph if different paths can lead to a same state node. In the context of job-shop scheduling however, only a treestructured search space needs be considered.

[START_REF] Gelly | Combining online and offline knowledge in uct[END_REF] Typically ε = 0.1.