A Roux

M Isaac

V Chabert

S A Denisov

N D Mcclenaghan

O Sénèque

Influence of Amino Acid Sequence in a Peptidic Cu + -Responsive Luminescent Probe Inspired by the Copper Chaperone CusF

Copper(I) is a soft metal ion that plays an essential role in living organisms and Cu + -responsive probes are required to detect Cu + ions in physiological conditions and understand its homeostasis as well as the diseases associated with its misregulation.

In this article, we describe a series of cyclic peptides, which are structurally related to the copper chaperone CusF, and that behave as Cu + -repsonsive probes. These peptide probes comprise the 16-amino acid loop of CusF cyclized by a b-turn inducer dipeptide and functionalized by a Tb 3+ complex for its luminescence properties. The mechanism of luminescence enhancement relies on the modulation of the antenna effect between a tryptophan residue and the Tb 3+ ion within the probe when Cu + forms a cation-p interaction with the tryptophan. Here, we investigate the influence of the amino acid sequence of these cyclic peptides on the copper-induced modulation of Tb 3+ emission and show that the rigid b-turn inducer Aib-D-Pro and insertion of the Tb 3+ complex close to its tryptophan antenna are required to obtain turn-on Cu + responsive probes. We also show that the amino acid sequence, especially the number and position of proline residues has a significant impact on metal-induced luminescence enhancement and metal-binding constant of the probes.

Introduction

Copper plays a crucial role in living organisms, in which it serves as a cofactor for several redox enzymes like oxidases or electron transfer proteins. [START_REF] Vest | Metallomics and the Cell[END_REF][START_REF] Rensing | Metallomics and the Cell[END_REF] The most common oxidation states in biological systems are +I and +II but in the reducing cellular environment, mobile copper is mainly in the +I oxidation state. However, since free Cu + can react with oxygen to yield superoxide (O2 •-), the first step in the generation of an oxidative stress, it is continually managed by proteins and its homeostasis is finely regulated. [START_REF] Kim | [END_REF]4 Deregulation of copper homeostasis is often associated with severe diseases such as the Wilson 5 or Menkes 6 diseases, or possibly neurodegenerative diseases. 7 In order to better understand the biology of copper, several synthetic fluorescent probes for Cu + as well as genetically encoded protein sensors have been designed. [8][9][10] Most of the synthetic probes operate on the basis of a photoinduced electron transfer (PET) switching mechanism, in which PET quenching of an excited fluorophore by a metal binding unit is blocked by metal binding. Genetically encoded sensors rely on modulation of fluorescence emission by conformational changes promoted by the metal ion using Förster resonance energy transfer (FRET).

We are developing luminescent probes for the detection of various bio-analytes, either metal cations [11][12][13] or biomolecules. 14 These probes are based (i) on binding domains of proteins (metal binding sites or biomolecule-binding domains) to benefit from their unparalleled recognition properties (selectivity for the target bio-analyte, dissociation constant in the suitable range for potential in vivo use, rapid dynamics of bio-analyte binding and dissociation) and (ii) on lanthanide(III) (Ln 3+ ) complexes as emitters in order to benefit from the desirable luminescence properties of Ln 3+ ions. Indeed, most Ln 3+ ions are luminescent with very interesting properties for biological applications: atom-like sharp emission bands at fixed wavelength depending on the Ln 3+ cation (each Ln 3+ having a fingerprint emission spectrum), low or no tendency to photobleaching and long luminescence lifetimes (in the µs to ms range), which allows time-gated detection to suppress background contribution of the biological medium (lifetime in the ns range). [START_REF] Bünzli | Lanthanide Luminescence[END_REF][START_REF] Bünzli | [END_REF][17][18][19][20][21][22][23] However, direct absorption of Ln 3+ ions is rather inefficient due to very low extinction coefficients (ca. 0.1-10 M -1 cm -1 ) but indirect excitation of Ln 3+ ion is possible through the so-called antenna effect, using a proximal chromophore that can absorb light and transfer its energy to the excited state of the Ln 3+ cation. 24 Such a chromophore is deemed an antenna. A general strategy to create a responsive probe consists in modulating the efficiency of the antenna effect, i.e. Ln 3+ sensitization, by an analyte. This can be achieved (i) by modulation of the distance between the antenna and the Ln 3+ ion or (ii) by modulation of the photophysical properties of the antenna (by intramolecular charge transfer or PET mechanism for instance or by chemical reaction). 18,19,[25][26][27][28][29][30] Another successful strategy for the design of lanthanide-based responsive probes is the modulation of the Ln 3+ coordination Please do not adjust margins Please do not adjust margins sphere, especially the number of coordinated water molecules (q), in order to change Ln 3+ emission through modulation of the non-radiative deactivation of the excited Ln 3+ ion. 31,19,25,28,30 We have recently described a Cu + -responsive luminescent probe, named LCC1 Tb , 11 demonstrating an original mechanism of antenna effect modulation, which differs from PET or FRET switching generally engineered in Cu + -responsive probes. [8][9][10] This probe is inspired from the copper-chaperone CusF, a copper-trafficking protein encountered in the periplasm of gram negative bacteria, [32][33][34][35] and comprises a terbium complex conjugated to a cyclic peptide. The establishment of a cation-p interaction between a tryptophan side chain and the copper ion plays a crucial role in the turn-on behaviour of this luminescent probe (vide infra). In this article, we describe several cyclic peptides that were synthesized during our search for a Cu +responsive probe inspired by the CusF binding site, which led to LCC1 Tb . Throughout this article, we discuss the influence of the amino acid sequence on the copper-sensing properties of these peptides in relation with the establishment of the cation-π interaction.

Results and discussion

Previously reported LCC1 Tb : structure and mechanism For the sake of clarity, this section contains details regarding the structure and the mechanism of LCC1 Tb that were previously published 11 but that are essential to understand the behaviour of the new molecules presented in the current article.

The copper-chaperone CusF, which served as a basis for the design of LCC1 Tb , binds Cu + selectively using a set of four amino acids located in a bent 16-amino acid β-hairpin loop: two methionines (Met/M), one histidine (His/H) and one tryptophan (Trp/W), whose aromatic side chain forms a cation-π interaction with the Cu + ion (Fig. 1A). LCC1 Tb (Fig. 1B) is a 18-amino acid cyclic peptide comprising a copper-binding loop derived from CusF and an Aib-D-Pro dipeptide to cyclize the loop (Aib = aminoisobutyric acid). Aib-D-Pro is an obligatory type-I' β-turn forming segment used to favour the formation of a β-sheet into the binding loop as in CusF (Fig. 1B). 36 As an emitting moiety, we chose a DOTA[Tb] chelate, which was grafted onto a side chain close to the tryptophan (Fig. 1B). The latter is a good antenna to sensitize Tb 3+ luminescence. In buffered water solutions, LCC1 Tb forms of a 1:1 complex with Cu + but it is not able to bind any other physiological metal cations (Na + , K + , Mg 2+ , Ca 2+ , Mn 2+ , Fe 2+ , Co 2+ , Ni 2+ , Cu 2+ and Zn 2+ ) due its thioether-containing coordination set, which can only bind soft metal cations. Cu + binding results in a 6.1-fold increase of the sensitized Tb 3+ emission (Fig. 1C). Additionally, LCC1 Tb and CusF share spectral features characteristic of the establishment of a cation-p interaction between the Cu + ion and the tryptophan indole, which includes a red-shift of the tryptophan p-p* transition and a quench of the tryptophan fluorescence (53% and 98% quench for LCC1 Tb and CusF, respectively). Metal cation-p interactions are known to efficiently enhance intersystem crossing (ISC), which increases the population of the excited triplet state of the fluorophore, thereby quenching its fluorescence. 37 A detailed study relying on both steady-state and time-resolved (from ns to ms timescale) emission spectroscopy has revealed the following interesting features concerning LCC1 Tb .

(i) An enhancement of the tryptophan excited triplet state population is observed in the presence of Cu + .

Please do not adjust margins Please do not adjust margins (ii) The terbium 5 D4 excited state is populated by electronic energy transfer from the tryptophan excited triplet state.

(iii) The Cu•LCC1 Tb complex exists in two different forms in equilibrium: one with the tryptophan forming the cation-p interaction and the other without the cation-p interaction (Fig. 1E). The former has a red-shifted p-p* transition, is not fluorescent and shows intense sensitized terbium emission whereas the latter has an unshifted p-p* transition, is fluorescent and shows weak terbium emission.

(iv) The cation-p interaction lowers the energy of the tryptophan excited triplet state by ca. 2300 cm -1 .

Hence, we can consider that in this system the mechanism for Cu + -responsive turn-on terbium emission is the following: the binding of Cu + to LCC1 Tb results in the establishment of a copper-tryptophan cation-p interaction that enhances ISC, leading to an increased population of the tryptophan excited triplet state and, consequently, to enhanced energy transfer to the Tb 3+ 5 D4 excited state, which emits more light (Fig. 1D).

In addition to Cu + , LCC1 Tb is also able to bind the nonphysiological cation Ag + , as does CusF. Indeed, these two cations have very similar coordination properties. The spectroscopic behaviour of LCC1 Tb is similar with both Cu + and Ag + including the same metal-induced enhancement factor for terbium emission (Fig. 1C). The main differences are a greater extent of fluorescence quenching in the case of Ag + (78%) and a lowering of tryptophan excited triplet state of ca. 500 cm -1 instead of 2300 cm -1 .

Probe design: first attempts

Initial attempts to model the binding site of CusF used linear peptides incorporating the M2HW coordination set, but these peptides precipitated in the presence of Cu + or Ag + . Suspecting the formation of aggregates, we sought to restrict conformational freedom using a cyclic peptide for more precise control of the nuclearity and stoichiometry of the complex, with the expectation to favour the formation of 1:1 species. The sequence of the copper-binding loop of E. coli CusF is I 34 HHDPIAAVNWPEMTM 49 (coordinating amino acids are underlined). Besides the four coordinating amino acids H, W, M and M at positions 36, 44, 47 and 49, respectively, several amino acids might be important for the proper folding of the metal binding site and the establishment of the cation-p interaction. The crystal structure of E. Coli CusF 33 (Fig. 1B) shows that this loop is folded into a b-hairpin that is bent at the level of the two prolines facing each other. Since proline is usually not encountered in b-strands, we reasoned that these two prolines are important for the bending of the b-hairpin, which allows interaction between the tryptophan side chain and the copper ion. Several hydrophobic contacts are also observed between the side chains of the coordinating histidine (H 36 ) and tryptophan (W 44 ), the valine (V 42 ) and the second isoleucine (I 39 ) of the loop. Sequence alignment of CusF homologues shows that valine, isoleucine or leucine residues with alkyl side chains are always encountered at positions 39 and 42. 32 Therefore, V 42 and I 39 were considered important. A first cyclic peptide, LCC0( D P-P) Tb (Fig. 2), was designed as a model of the CusF binding loop. It comprises 18 amino acids including the important amino acids of the CusF binding loop as well as a D-Pro-L-Pro dipeptide to close the ring. Robinson et al. have shown that this dipeptide is an excellent template to induce the formation of b-hairpins in cyclic peptides that reproduce the conformation of natural b-hairpins in proteins. [38][39][40][41] We have already successfully used this template in the design of cyclic peptide-based models of zinc finger sites presenting bhairpins. [42][43][44] Several supposedly non essential amino acids of the CusF binding loop were changed: (i) a glycine was needed for synthesis purposes to avoid epimerization during cyclization and it was introduced in place of D 37 ; (ii) H 35 and N 43 were replaced by lysines to provide positively charged amino acids to ensure solubility of the peptide and (iii) I 34 was changed for a lysine to take advantage of its amino side chain to easily graft the DOTA ligand. This position was chosen to insert the Tb 3+ complex in order to preserve, as far as possible, the CusF binding loop sequence in this first model. The synthesis of LCC0( D P-P) Tb and other peptides is described in the ESI. The metal binding properties of this peptide were investigated with Ag + and Cu + in degassed HEPES buffer (10 mM, pH 7.5). Indeed, all peptides presented throughout this article behave in a similar way with Ag + or Cu + as previously observed for LCC1 Tb . The titration of LCC0( D P-P) Tb by Ag + in HEPES buffer monitored by tryptophan fluorescence (lex = 280 nm) shows a quenching of the tryptophan emission upon addition of Ag + with a plateau above 1 eq. of added metal cation, attesting to the formation of a 1:1 complex (Fig. 3A). In addition to the tryptophan fluorescence quench (44%), a slight red-shift of the p-p* transition (ca. 2 nm) is observed upon formation of the Ag•LCC0( D P-P) Tb complex (Fig. 3B). These two features are indicative of the establishment of the cation-p interaction but they are rather weak in intensity compared to CusF (98% fluorescence quench and ca. 12 nm-shift of the p-p* transition

V A A I P G H K K P D P M T M E P W K V A A I P G H K K D P Aib M T M E P W K V A A I P G H K K G P M T M E P W K LCC0( D P-P) Tb LCC0(Aib-D P) Tb LCC0(P-G) Tb K A A I P G H K Q D P Aib M T M E P W Aib LCC1 Tb Tb Tb Tb Tb K A A I P G H K Q D P Aib M T M E P W G LCC1(G) Tb Tb K A P I A E H K Q D P Aib M T M A P W G LCC2 Tb Tb K A P I A E H K Q D P Aib M T M A G W Q LCC3 Tb Tb K A A I P G H K Q D P Aib M T M E P W K LCC1(Aib) Tb
Tb This journal is © The Royal Society of Chemistry 20xx

Please do not adjust margins Please do not adjust margins as evaluated at the half-height of the band). A similar behaviour is observed with Cu + . Concerning the sensitized terbium emission in degassed solutions, addition of Ag + leads to a small increase of Tb 3+ emission (10%) whereas a 60% decrease is observed with Cu + (Fig. 3C). The excitation spectra for tryptophan fluorescence (lem = 357 nm) and terbium emission (lem = 545 nm) were also recorded (Fig. S2 of ESI). Interestingly, the terbium emission excitation spectra of the Ag + and Cu + complexes are shifted with respect to the free peptide whereas those of fluorescence emission are not. This has been described previously for LCC1 Tb . It reveals that two species are in equilibrium for the complexes: one with a tryptophan forming the cation-p interaction (with red-shifted p-p* transition absorption, non fluorescent tryptophan and emissive terbium) and one without cation-p interaction (with unshifted p-p* transition absorption, fluorescent tryptophan and weakly emissive terbium) as depicted in Fig. 1E.

Influence of the cyclizing dipeptide

In order to assess the influence of the cyclizing dipeptide, we changed the D-Pro-L-Pro dipeptide for Aib-D-Pro or L-Pro-Gly dipeptides. D-Pro-L-Pro and Aib-D-Pro are two rigid turn templates that induce a b-sheet. D-Pro-L-Pro induces a flat bsheet whereas the two b-strands are twisted in the case of Aib-D-Pro, as are those in proteins. 36 L-Pro-Gly is a less rigid dipeptide that is less prone to induce b-strands. The corresponding peptides, LCC0(Aib-D P) Tb and LCC0(P-G) Tb , bind 1 equivalent of Ag + or Cu + as does LCC0( D P-P) Tb . They behave mostly as LCC0( D P-P) Tb but with some differences. For both peptides, a partial quenching of the tryptophan fluorescence and a red-shift of the p-p* transition are observed. However, compared to LCC0( D P-P) Tb , the quenching is higher for LCC0(Aib-D P) Tb and lower for LCC0(P-G) Tb (Fig. 4A). The same trend is observed for the red-shift of the p-p* transition (Fig. 4B). This indicates a greater tendency to form the cation-p interaction for LCC0(Aib-D P) Tb (the equilibrium in Fig. 1E is shifted toward the "Fluo OFF" form) compared to LCC0( D P-P) Tb and a lower tendency for LCC0(P-G) Tb . As for LCC0( D P-P) Tb , addition of Ag + to LCC0(Aib-D P) Tb led to a modest (5%) increase of Tb 3+ emission whereas it led to a 17% quench in the case of LCC0(P-G) Tb (Fig. 5B). For both peptides, addition of Cu + resulted in a lower Tb 3+ emission (Fig. 5). Fig. 5 (A) Quantum yields (lex = 280 nm) of tryptophan fluorescence emission (left) and terbium luminescence emission (right) for metal-free (black), Cu + -bound (red) and Ag +bound (blue) peptides determined by comparison with LCC1 Tb in anaerobic conditions. 11 Solid black, red and blue lines correspond to the emission of LCC1 Tb and its complexes, for comparison purpose. (B) Tryptophan (left) and terbium (right) emission intensity of Cu + -bound (red) and Ag + -bound (blue) relative to metal-free peptide. The black solid line corresponds to the emission of the metal-free peptide normalized to 1.

The conformation of peptides was examined by circular dichroism (CD). The CD spectra of LCC0( D P-P) Tb and LCC0(Aib-D P) Tb present a strong negative signal at 200 nm (Fig. 6A,B). They Please do not adjust margins are characteristic of peptides with an undefined conformation (random coil). Addition of Ag + to LCC0( D P-P) Tb leads to a less negative CD signal at 200 nm with a marked shoulder at 223 nm and small positive band at 240 nm (ESI). These features are more pronounced for Ag•LCC0(Aib-D P) Tb with a much reduced negative ellipticity at 200 nm, two positive bands at 208 nm and 240 nm and a negative band at 223 nm. This indicates a better propensity of LCC0(Aib-D P) Tb to fold upon metal binding. In order to gain more insight into the conformational behaviour, LCC0(Aib-D P) La , the diamagnetic analogue of LCC0(Aib-D P) Tb with lanthanum replacing terbium, was prepared and analysed by 1 H NMR. Its spectrum in H2O/D2O showed broad resonances in agreement with conformational motions. In the presence of Ag + (1.0 eq.), the NMR signals become even broader attesting again to the conformational flexibility of the silver complexes. Interestingly, several peaks were observed for the tryptophan indole NH resonance around 10 ppm in agreement with the coexistence of complexes with bound and unbound tryptophan deduced from photophysical studies. Finally, the apparent Ag + binding constants K of the three LCC0 peptides (K = [Ag•LCC0 Tb ]/([Ag + ][LCC0 Tb ])) were measured using imidazole as a competitor (Table 1 and ESI). 45 LCC0(P-G) Tb shows the lowest affinity among the three LCC0 peptides. Overall, among D-Pro-L-Pro, L-Pro-Gly and Aib-D-Pro dipeptide templates, the latter seems to be the best suited to combine the best ability to establish the cation-p interaction and to form the tightest complexes.

Fig. 6 CD spectra of solutions of (A) LCC0( D P-P) Tb , (B) LCC0(Aib-D P) Tb , (C) LCC1 Tb , (D) LCC1(Aib) Tb , (E) LCC2 Tb and (F) LCC3 Tb (20 µM) in phosphate buffer (20 mM, pH 7) in their metal-free (black), Cu + -bound (red) and Ag + -bound (blue) forms.

Influence of the lanthanide chelate position

Within the LCC0 peptide family, the DOTA[Tb] complex is quite remote from its tryptophan antenna. Reasoning that the distance between the terbium complex and the tryptophan antenna could be an issue for the terbium sensitization process and the luminescence response of the probe, the DOTA[Tb] complex was grafted closer to the tryptophan. The crystal structure of CusF shows hydrophobic contacts between the tryptophan indole and the alkyl side-chains of Val42. 33 Having reasoned that the four-carbon side chain of a lysine could establish similar contacts, valine was substituted by a lysine with an appended DOTA ligand. Aib-D-Pro was selected as a cyclizing dipeptide and a glutamine was introduced next to the D-Pro. This led to peptide LCC1 Tb (Fig. 1 and2). 11 Regarding structural aspects, the CD spectra of LCC1 Tb and its metal complexes (Fig. 6) are reminiscent of those of LCC0(Aib-D P) Tb with a random coil signature in the absence of cation and bands at 208 nm (+), 223 nm (-) and 240 nm (+) for the silver complex. The copper complex displays the same bands at 208 nm (+) and 223 nm (-) but not the band at 240 nm. Compared to LCC0(Aib-D P) Tb , the tryptophan emission of LCC1 Tb is similar in the absence of metal cation but lower in the presence of both Cu + and Ag + cations (Fig. 5). The greater quenching of tryptophan emission observed in the presence of the cations parallels the bigger redshift of the p-p* band (5 nm vs 3 nm for Ag + ) indicating a greater tendency to establish the cation-p interaction in the case of LCC1 Tb . This may be ascribed to the valine-to-lysine mutation that would favour the tryptophan-bound forms of the copper or silver complexes. Displacing the Tb 3+ complex has also a major effect (i) on the terbium emission quantum yield, which is higher for both the metal-free and the metal-bound probe when the Tb 3+ ion closer to the tryptophan antenna, and (ii) on the probe response with a ca. 6-fold increase of terbium emission upon Cu + or Ag + binding for LCC1 Tb , resulting in an interesting turn-on response for both Cu + and Ag + (Fig. 5B) as described in a previous communication 11 and as summarized in the introduction. In addition to favouring the cation-p position compared to peptides of the LCC0 family, changing the position of the lysine-DOTA residue slightly increases the affinity for Cu + and Ag + (Table 1). Please do not adjust margins Please do not adjust margins

Influence of the binding loop sequence

Our next investigations were directed towards the amino acids that compose the binding loop. Firstly, when looking at the Ramachandran plot 46,47 of the crystal structure of CusF, we noticed that asparagine 43 (Asn43) of the copper-binding loop has backbone dihedral angles j and y ‡ values of + 60° and + 44°, respectively, which lies in the sparsely populated left-handed ahelix region of the Ramachandran plot. These values are rarely encountered for L-amino acids because of steric clashes arising between the main chain and the side chain but more frequently for glycine, which is achiral and has no side chain. Interestingly, several CusF homologues feature a glycine at position 43. 32 Therefore, we decided to assess the influence of having a glycine or an Aib residue, which is also non-chiral but restricts more than glycine the conformational space, at this position (Nside of tryptophan) in LCC1 Tb . For this purpose, peptides LCC1(G) Tb and LCC1(Aib) Tb (Fig. 2) were synthesized and analysed. Both peptides are able to establish the cation-p interaction as demonstrated by characteristic features mentioned above and both show turn-on sensitized terbium emission upon metal binding (Fig. 5B). The emission properties of LCC1(G) Tb are almost identical to those of LCC1 Tb (Fig. 5A), indicating that the Asn-to-Gly mutation has limited impact. The only noticeable difference is a higher binding constant for LCC1(G) Tb compared to LCC1 Tb (Dlog K = 0.5 and 0.7 for Cu + and Ag + , respectively; Table 1). More differences are observed between LCC1 Tb and LCC1(Aib) Tb . The latter displays a slightly higher red-shift of the p-p* absorption (6 nm vs 5 nm), a higher tryptophan emission in the free form and a lower one in the metal-bound form, which gives a greater quenching of tryptophan emission upon metal binding, and higher sensitized terbium emission in both the free and metal-bound forms (Fig. 5). Unfortunately, this translates into a lower metal-induced enhancement of sensitized terbium emission (3.6-and 3.0-fold for Cu + and Ag + , respectively, in the case of LCC1(Aib) Tb compared to 6.1-and 6.0-fold for LCC1 Tb , in anaerobic conditions; Fig. 5B). Nevertheless, LCC1(Aib) Tb forms significantly more stable complexes than LCC1 Tb (Dlog K = 0.9 and 1.5 for Cu + and Ag + , respectively; Table 1). CD provides some clues to explain this behaviour. The CD spectra of the metal-free form is less negative at 200 nm for LCC1(Aib) Tb compared to LCC1 Tb and a negative band at 223 nm is clearly observed in the spectrum of the Aib variant, which is not observed in the parent probe (Fig. 6C,D). The spectra of the metal-bound forms show the bands at 208 nm (+), 223 nm (-) and 240 nm (+, Ag + only) but they are slightly more intense in the case of the Aib variant.

Altogether, the Asn-to-Aib mutation seems to limit conformational motions of the peptide and to stabilize a certain fold. This is beneficial to metal affinities and emission quantum yields but detrimental to the probe response, mainly because of higher emission of terbium in the free form. The Aib residue, by rigidifying the cyclic peptide scaffold may lower non-radiative deactivation of tryptophan resulting in a higher fluorescence emission and in a more efficient Tb 3+ sensitization. This effect may be more pronounced in the metal-free form than in the metal-bound form where the metal ion contributes to the rigidification of the scaffold also. By looking at the sequence alignment of CusF homologues, 32 we noticed that the two prolines of the metal binding loop are not always at the same position and in some cases, one of them is missing. Indeed, some homologues have a proline in position 40 instead of 38 and others have only a single proline either at position 40 or 45. Therefore, starting from LCC1 Tb , we implemented the sequence of the Cu-binding loop of Klebsiella pneumonia CusF, 32 with two prolines at positions 40 and 45, and that of Cupriavidus metallidurans CH34 C-terminal domain of SilB, 48 with a single proline at position 40, into the cyclic peptide to give LCC2 Tb and LCC3 Tb probes, respectively (Fig. 2). Both LCC2 Tb and LCC3 Tb form 1:1 complexes with Ag + and Cu + and behave as turn-on emission probes regarding terbium emission (Fig. 5B), as does the parent probe LCC1 Tb . However, the redshift of the p-p* absorption upon Ag + binding is lower (4 nm) in the case of LCC3 Tb compared to LCC1 Tb and LCC2 Tb (5 nm), suggesting a lower capacity to establish the cation-p interaction. The quantum yield of tryptophan emission is higher for metal-free LCC2 Tb and LCC3 Tb than for LCC1 Tb (Fig. 4). As for the Aib variant of LCC1 Tb , this goes along with a more structured peptide as deduced from comparison of CD spectra, which shows a negative band at 220 nm for both metal-free LCC2 Tb and LCC3 Tb (Fig. 6E,F). Additionally, the terbium emission of those metal-free peptides is higher than that of LCC1 Tb , as is the Aib variant. In the Cu + -or Ag + -bound forms, LCC2 Tb has a similar tryptophan quantum yield as LCC1 Tb but that of LCC3 Tb is higher Please do not adjust margins Please do not adjust margins (Fig. 4). Together with the lower red-shift of the p-p* absorption of the latter, this suggests that LCC3 Tb has a lower tendency to form the cation-p interaction compared to LCC1 Tb and LCC2 Tb . Indeed, the molar fraction of complex with metal-bound tryptophan seems to be higher for peptides with two prolines than those with a single proline. The consequence is a lower terbium emission of the metal-bound species in the case of the peptide with a single proline compared to the two-proline probes. Altogether, although responding to Cu + or Ag + , LCC2 Tb and LCC3 Tb present a less significant metal-induced enhancement of terbium emission than LCC1 Tb (Fig. 5B, 4.1-, 2.5-and 6.1-fold, respectively, in the case of Cu + and 4.5-, 3.8and 6.0-fold in the case of Ag + ). Regarding binding constants, LCC3 Tb has the same affinity for Cu + and Ag + as LCC1 Tb whereas LCC2 Tb forms more stable complexes (Dlog K = 0.8 and 0.7 for Cu + and Ag + , respectively; Table 1). Finally, LCC2 Tb and LCC3 Tb were studied by time-resolved emission spectroscopy. Tryptophan fluorescence was observed on the ns time-scale. In both the metal-free and Ag + -bound forms, the fluorescence decay is bi-exponential with a short lifetime around 0.9 ns and a longer around 4.5 ns (Table 2). This is typical of tryptophan fluorescence and these values are similar to those determined for LCC1 Tb . 11 Terbium emission was observed in the time-gated mode on the µs and ms time scales. As for LCC1 Tb , the terbium emission rise time lies in the 15-25 ms range.

Tryptophan phosphorescence, which could be observed in the case of the Cu + and Ag + complexes only, has a decay time of ca. 20 ms that matches the rise time of terbium emission within error (± 2 µs). This indicates that in the case of LCC2 Tb and LCC3 Tb , the sensitizing mechanism involves electronic energy transfer from the triplet excited state of tryptophan to the 5 D4 excited state of terbium, as previously observed for LCC1 Tb . The sensitization mechanism is thus not modified. To summarize, LCC1 Tb , LCC2 Tb and LCC3 Tb display turn-on terbium luminescence response to Cu + and Ag + and have very similar behaviour (Fig. 5). However, the single-proline variant (LCC3 Tb ) displays lowered terbium luminescence modulation compared to the two-proline probes. For the two-proline probes, the position of the proline influences both luminescence response and binding constants.

Fig. 1 (

 1 Fig. 1 (A) Crystallographic structure of CusF (pdb 2VB2 33 ) showing the copper binding site. (B) Amino acid sequence of LCC1 Tb , chelating moieties in red. (C) Luminescence emission spectra (lex = 280 nm) of LCC1 Tb (black), Cu•LCC1 Tb (red) and Ag•LCC1 Tb (blue) in a degased HEPES buffer (10 mM, pH 7.5). (D) Simplified Jablonski-Perrin diagram of LCC1 Tb and pertinent photophysical processes (ISC = intersystem crossing, EET = electronic energy transfer). (E) Metal binding equilibrium showing the two forms of the M•LCC1 Tb complex (M + = Ag + or Cu + ).

Fig. 2

 2 Fig. 2 Cyclic peptides used in this study. Coordinating amino acids are shown in red. Major changes from one peptide to the other are shown in blue.

Fig. 3 (

 3 Fig. 3 (A) Fluorescence titration (lex = 280 nm) of LCC0( D P-P) Tb by Ag + in HEPES buffer (10 mM, pH 7.5). (B) Electronic absorption spectra of LCC0( D P-P) Tb (black) and Ag•LCC0( D P-P) Tb (blue). (C) Time-gated Tb 3+ emission spectra (lex = 280 nm, 200 µs delay time) of LCC0( D P-P) Tb (black), Ag•LCC0( D P-P) Tb (blue) and Cu•LCC0( D P-P) Tb (red).

Fig. 4

 4 Fig. 4 Influence of the dipeptide template on spectroscopic features: (A) Comparison of the red-shift of the p-p* transition between Ag + complexes of LCC0( D P-P) Tb , LCC0(Aib-D P) Tb and LCC0(P-G) Tb . (B) Comparison of the tryptophan fluorescence quench upon Ag + (blue) or Cu + (red) binding to peptides LCC0( D P-P) Tb , LCC0(Aib-D P) Tb and LCC0(P-G) Tb .

  This journal is © The Royal Society of Chemistry 20xx

Table 1

 1 Cu + and Ag + binding constants K (in M -1 ) at pH 7.5 for the peptides used in this study, determined by competition experiments with imidazole (nd = not determined).

		log K (± 0.2)
	Peptide	Cu +	Ag +
	LCC0( D P-P) Tb	nd	6.8
	LCC0(Aib-D P) Tb	nd	6.8
	LCC0(P-G) Tb	nd	5.7
	LCC1 Tb	9.4 a	7.3 a
	LCC1(G) Tb	9.9	8.0
	LCC1(Aib) Tb	10.3	8.8
	LCC2 Tb	10.2	8.0
	LCC3 Tb	9.2	7.2

a Data taken from reference 11.

Table 2

 2 Summary of life times measured by time resolved emission spectroscopy.

	Compound a	Tryptophan fluorescence	Tryptophan phosphorescence	Tb 3+ luminescence	Tb 3+ luminescence
		decay / ns (± 0.2 ns)	decay / µs (± 2 µs)	rise / µs (± 2 µs)	decay / ms (± 0.01 ms)
	LCC1 Tb	0.9 (13 %), 4.8 (87 %)	not detected	23	1.98
	Cu•LCC1 Tb	0.7 (16 %), 3.9 (84 %)	16	16	1.90
	Ag•LCC1 Tb	0.9 (17 %), 4.2 (83 %)	19	18	1.95
	LCC2 Tb	1.0 (10 %), 4.8 (90 %)	not detected	17	1.97
	Cu•LCC2 Tb	0.7 (17 %), 4.1 (83 %)	13	14	1.93
	Ag•LCC2 Tb	1.1 (18 %), 4.6 (82 %)	18	22	1.96
	LCC3 Tb	0.9 (9 %), 4.2 (91 %)	not detected	19	1.99
	Cu•LCC3 Tb	0.7 (12 %), 3.8 (88 %)	14	15	1.93
	Ag•LCC3 Tb	1.1 (13 %), 4.1 (87 %)	23	23	1.97

a Data for LCC1 Tb are taken from reference 11.

This journal is © The Royal Society of Chemistry 20xx J. Name., 2013, 00, 1-3 | 7

Acknowledgements

OS acknowledge the Agence Nationale de la Recherche (ANR-12-BS07) and the Labex ARCANE (ANR-11-LABX-0003) for financial support.

Conclusions

In this article, we have investigated the influence of amino acid sequence in a family of bio-inspired Cu + -responsive peptide probes. These probes are 18-amino acid cyclic peptides comprising the 16-amino acid copper-binding loop of the CusF protein, a periplasmic copper chaperone in gram-negative organisms. The loop is closed by a dipeptide turn. The copperbinding site is composed of two methionine thioethers, the imidazole ring of histidine and the indole ring of a tryptophan, which establishes a cation-p interaction with Cu + in CusF. A Tb 3+ complex is grafted onto one of the amino acid side chains of the cyclic peptide to provide a luminescence reporter. In this system, the tryptophan amino acid serves as an antenna to sensitize Tb 3+ luminescence. A key point in the design of turnon probes in this system is to reproduce the cation-p interaction because it increases ISC within the tryptophan indole, thereby allowing more energy to be transferred to the 5 D4 Tb 3+ excited state, resulting in an enhanced Tb 3+ emission in the presence of Cu + . 11 By studying this family of peptides, we have highlighted several factors that govern the cation-p interaction and thus, the behaviour of the probe. First, the ring-closing dipeptide plays a crucial role in the establishment of the cation-p interaction. Indeed, we found that a rigid b-turn inducer such as D-Pro-L-Pro or Aib-D-Pro is required, whereas a flexible one (e.g. Pro-Gly) is not suitable. However, Aib-D-Pro, which favours the formation of twisted b-sheets, is more efficient than D-Pro-L-Pro at forcing the interaction between the indole and the Cu + ion. The second requirement is to place the Tb 3+ complex very close to its tryptophan antenna. Taking into account these two requirements, we have obtained several turn-on Cu + -and Ag +responsive probes displaying variable luminescence quantum yields, metal-induced luminescence enhancement (ranging from 2.5 to 6.1 for Cu + and from 3 to 6 for Ag + ) and affinities (ranging from 10 9.2 to 10 10.3 M -1 for Cu + and 10 7.2 to 10 8.8 M -1 for Ag + ). We have shown that having two prolines in the metalbinding loop is better than a single proline, providing probes with higher luminescence enhancement and higher metalbinding constants. This highlights the influence of conformational flexibility within the cycle. Nevertheless, this cyclic peptide scaffold seems rather tolerant to amino acid sequence changes provided that the Aib-D-Pro dipeptide is used as a closing turn and that the Tb 3+ complex is close to the tryptophan. Regarding the strength of the cation-p interaction that is superior in CusF compared to our probes, as judged by the red-shift of the p-p* transition (12 nm) and the almost complete quench of tryptophan fluorescence, we believe that there is still room to improve this system, by trying to preorganize the metal-free peptide into a conformation that is the same as the metal-bound form establishing the cation-p interaction as it is the case for CusF. Our efforts are now directed toward the replacement of the tryptophan indole by other aromatic antenna to sensitize luminescence of other Ln 3+ and shift excitation and emission wavelength towards lower energy.

Conflicts of interest

There are no conflicts to declare.

Notes and references ‡ j is defined by the backbone dihedral angle created by Ci-1-Ni-Cai-Ci along the peptide chain and y is defined by the dihedral angle created by Ni-Cai-Ci-Ni+1.


Quentin Baert

Anne-Cécile Caron

Maxime Morge

Jean-Christophe Routier
email: christophe.routier@univ-lille.fr

Anne-Cecile Baert

Maxime Caron

Jean Morge

Kostas Stathis
email: kostas.stathis@rhul.ac.uk

A Location-Aware Strategy for Agents Negotiating Load-balancing

We study a novel location-aware strategy for distributed systems where cooperating agents perform the load-balancing. The strategy allows agents to identify opportunities within a current unbalanced allocation, which in turn triggers concurrent and one-tomany negotiations amongst agents to locally reallocate some tasks. The tasks are reallocated according to the proximity of the resources and they are performed in accordance with the capabilities of the nodes in which agents are situated. This dynamic and on-going negotiation process takes place concurrently with the task execution and so the task allocation process is adaptive to disruptions (task consumption, slowing down nodes). We evaluate the strategy in a multi-agent deployment of the MapReduce design pattern for processing large datasets. Empirical results demonstrate that our strategy significantly improves the overall runtime of the data processing.

I. Introduction

The problem of load balancing and task allocation in distributed systems manifests itself in many applications such as cloud computing, peer-to-peer and ad-hoc networks, pervasive computing, online social networks and big data processing. In this work we are concerned with a class of such practical applications where (a) some of the resources, e.g. data, required to successfully execute a task are distributed at different network nodes, and (b) some of the nodes may encounter potential execution hazards, e.g. slowing down nodes or communication lags. As several resources are necessary to perform a task, any initial allocation inevitably requires fetching some of these resources from other nodes, thus incurring an extra time cost for task execution [START_REF] Jiang | A survey of task allocation and load balancing in distributed systems[END_REF]. In this class of applications the task allocation can be challenged during the task execution and should capitalize upon the way resources are distributed in the system.

In order to tackle the problem of load balancing and task allocation in applications such as those that motivate this work, multi-agent technologies have received a lot of attention, especially those based on market-based scheduling, for example see [START_REF] Walsh | A market protocol for decentralized task allocation[END_REF], [START_REF] Shehory | Methods for task allocation via agent coalition formation[END_REF], [START_REF] Turner | Distributed strategy adaptation with a prediction function in multi-agent task allocation[END_REF]. Apart from decentralization, i.e. avoiding performance bottlenecks due to global control, we show here that a multi-agent approach for situated task allocation supports two additional crucial requirements (a) concurrency -where task reallocation and task executions are concurrent, and (b) adaptation -where task reallocation is triggered when a disruptive event is performed. We assume that agents are cooperative, viz., they share the same objective: minimizing the global runtime. We also assume there is no shared knowledge, including any knowledge about the whole task allocation. However, agents have a model of their peers, i.e. they are able to compute the cost of tasks for their peers. We further assume that a task can be performed by any single agent without preemption and precedence order. A task is indivisible, without deadline and not shareable i.e. a task belongs to only one agent at a time.

The work formalizes the multi-agent situated task allocation problem. By adopting a market-based approach, we totally decentralize the load-balancing, whereby cooperative agents try to minimize the completion time of the last task to perform, i.e. the makespan. For this purpose, we propose a novel location-aware strategy for agents to perform the load-balancing. Our work significantly extends [START_REF] Baert | Adaptive Multi-agent System for Situated Task Allocation[END_REF] with a formal framework for a negotiation strategy and its full experimental results that are in line with [START_REF] Baert | Fair multi-agent task allocation for large datasets analysis[END_REF], where the locality of resources is taken into account. When agents identify opportunities within a current unbalanced allocation, they trigger concurrent and one-to-many negotiations to locally reallocate some tasks. The tasks are reallocated according to the proximity between the required resources and the nodes executing the tasks. This dynamic and ongoing task reallocation process takes place concurrently with the task execution and so the distributed system is adaptive to disruptive phenomena (task consumption, slowing down nodes).

We consider as a practical application the distributed deployment of the MapReduce design pattern in order to process large datasets on a cluster [START_REF] Dean | MapReduce: Simplified data processing on large clusters[END_REF], as with Hadoop [START_REF]Apache Hadoop[END_REF]. Even if some skews in real-world datasets lead to poor load-balancing [START_REF] Kwon | Managing skew in Hadoop[END_REF], a centralized scheduler cannot be used as a baseline to compare with our approach due to the large number of tasks. However, multi-agent negotiation allows task reallocation during the reduce phase in order to decrease the job runtime. Our approach is validated for such an application since the preliminary empirical results show that the location-aware strategy allows to improve the overall runtime of the data processing.

The paper is structured as follows. After an overview of the related work in Sec. II, we formalize the multiagent situated task allocation problem and we define in Sec. III the socially rational task delegation considered by the agents in order to locally improve the task allocation. Sec. IV sketches the iterated negotiation process which is concurrent with task consumptions. Sec. V describes the location-aware strategy, i.e. how agents choose which task to perform/negotiate. Our practical application and empirical validation are described in Sec. VI. Finally, Sec. VII summarizes our contribution and outlines our future work.

II. Related work

Classical scheduling problems have been the subject of extensive research producing offline schedulers for some simple models [START_REF] Chen | Handbook of combinatorial optimization[END_REF]. The problem of minimizing the makespan (the completion time of the last task to perform) with n tasks on m unrelated machines (i.e. with different capabilities), denoted R||C max , is NP-hard [START_REF] Horowitz | Exact and approximate algorithms for scheduling nonidentical processors[END_REF]. Pseudo-polynomial algorithms developed for this problem include: the earliest completion time heuristic [START_REF] Ibarra | Heuristic algorithms for scheduling independent tasks on nonidentical processors[END_REF] (ECT), the local search heuristics [START_REF] Hariri | Heuristics for scheduling unrelated parallel machines[END_REF], the branch and bound algorithm [START_REF] Martello | Exact and approximation algorithms for makespan minimization on unrelated parallel machines[END_REF] and two-phase heuristics based on linear programming [START_REF] Lenstra | Approximation algorithms for scheduling unrelated parallel machines[END_REF]. Even if the ECT heuristic is an approximation algorithm which gives acceptable results with very small computational requirements, centralized algorithms cannot be applied to our scenario with a large number of tasks (i.e. 82, 283 keys in Sec. VI). The location-aware strategy is a decentralized local search heuristic.

Multi-agent scheduling [START_REF] Jiang | A survey of task allocation and load balancing in distributed systems[END_REF] has received significant attention for load-balancing problems in distributed systems, but it is different from the classical scheduling problems due to the following requirements:

• Scalability: global control causes a performance bottleneck as it must collect status information of the entire system in real time. Instead, task allocation can be negotiated by agents representing the nodes [START_REF] Walsh | A market protocol for decentralized task allocation[END_REF], [START_REF] An | Automated negotiation with decommitment for dynamic resource allocation in cloud computing[END_REF]. • Responsiveness: classical scheduling problems are static. The inaccurate estimation of tasks execution time, made worse by disruptive phenomena (task consumption, slowing down nodes, etc.), may require major modifications in the existing allocation to stay optimal [START_REF] Turner | Distributed strategy adaptation with a prediction function in multi-agent task allocation[END_REF]. Rather than continuously recomputing an optimal allocation, some local modifications during the tasks processing can improve the loadbalancing [START_REF] Attiya | Task allocation for maximizing reliability of distributed systems: A simulated annealing approach[END_REF], [START_REF] Yin | Task allocation for maximizing reliability of a distributed system using hybrid particle swarm optimization[END_REF], [START_REF] Kang | Task allocation for maximizing reliability of distributed computing systems using honeybee mating optimization[END_REF].

Most of the existing works adopting the market-based approach (e.g. [START_REF] Walsh | A market protocol for decentralized task allocation[END_REF], [START_REF] Garg | Double auction-inspired meta-scheduling of parallel applications on global grids[END_REF]) model the load-balancing problem as a non-cooperative game in order to optimize usercentric metrics rather than system-centric ones such as the global runtime we consider in this paper. Contrary to our work, [START_REF] Shehory | Methods for task allocation via agent coalition formation[END_REF] consider task assignments to groups of agents as necessary since tasks cannot be performed by a single reliable agent. In this paper, we assume that a task, which can be performed by any single agent without preemption and precedence order, is indivisible, not shareable (i.e. a task belongs to only one agent at a time) and without deadline. [START_REF] Damamme | The Power of Swap Deals in Distributed Resource Allocation[END_REF] has studied multi-agent resource allocation but their work is restricted to the assignment of a single resource per agent. We assume here that a bundle of tasks can be assigned to each agent. In the continuity of [START_REF] Sandholm | Contract types for satisficing task allocation[END_REF], [START_REF] Endriss | Negotiating socially optimal allocations of resources[END_REF], [START_REF] Nongaillard | Reallocation problems in agent societies: A local mechanism to maximize social welfare[END_REF] proposes potentially distributable solving methods using agent-based negotiation for resource allocation. Even if the network topology is out of the scope of our work (agents are fully connected in our practical application), we go a step further by effectively decentralizing the negotiation, and by challenging this allocation during task processing.

For the processing of real-world datasets by the distributed deployment of the MapReduce design pattern, it is well known that data skews are widespread and they can lead to poor load-balancing [START_REF] Kwon | Managing skew in Hadoop[END_REF]. In particular the partitioning skew occurs when one reducer processes a larger number of keys than others. Since the job ends when all the reduce tasks are finished, the job runtime is penalized by the most loaded reducer. This data skew is tackled by [START_REF] Chen | SAMR: A self-adaptive MapReduce scheduling algorithm in heterogeneous environment[END_REF], [START_REF] Liroz-Gistau | FP-Hadoop: efficient execution of parallel jobs over skewed data[END_REF] using parametrization based on prior knowledge about the data and the distributed computing environment. We address this issue with the dynamic and adaptative task reallocation which is concurrent with the task consumption. Thus, reallocation is adaptative to the data processing. This enables us to tackle the following real-world issues: (a) the lack of prerequisite knowledge over the data, (b) the inaccurate estimation of task execution time, and (c) the execution hazards (slowing down nodes, communication lag). To the best of our knowledge, no other proposal is scalable and responsive, like ours.

III. Situated task allocation

We formalize here the multi-agent situated task allocation (MASTA) problem where tasks have different costs (runtime) for different agents due to the resource locality.

Definition 1 (MASTA):

A multi-agent situated task allocation problem of size (k, m, n) with k ≥ 1, m ≥ 2 and n ≥ 1 is a tuple M AST A = N ode, A, T , l, d, c s.t.: • N ode = {node 1 , . . . , node k } is a set of k nodes; • A = {1, . . . , m} is a set of m agents; • T = {τ 1 , . . . , τ n } is a set of n tasks to perform; • l : A → N
ode is a function which returns the location of an agent; • d : T × N ode → N + is a function which specifies how many resources for a task are on a particular node;

• c : T × N ode → R * + specifies the cost of a task τ at a given location such that the tasks with more local resources are cheaper:

∀i, j ∈ A, d(τ, l(i)) > d(τ, l(j)) ⇒ c i (τ, l(i)) ≤ c(τ, l(j)) (1)
In the rest of the paper, l i , c i (τ ) and d i (τ ) denote l(i), c(τ, l i ) and d(τ, l i ), respectively. Similarly, we denote d τ = node∈N ode d(τ, node). We say that τ is local, partially local,

or distant for agent i if d i (τ ) = d τ , d i (τ ) < d τ , or d i (τ ) = 0, respectively.
We consider a particular MASTA problem and we evaluate the task allocation from a collective viewpoint by considering the maximum completion time, i.e. the makespan.

Definition 2 (Task allocation/Workload/Makespan): A task allocation P is a partition of tasks among agents, i.e a set of m task bundles {P (1), . . . , P (m)} such that:

∪ i∈A P (i) = T (2) ∀i ∈ A, ∀j ∈ A \ {i}, P (i) ∩ P (j) = ∅ (3)
The workload of the agent i ∈ A in the allocation P is defined as:

w i (P ) = τ ∈P (i) c i (τ ) (4)
The makespan of P is defined as:

C max (P ) = max{w i (P ) | i ∈ A} (5)
We define the socially rational task delegation considered by the agents in order to locally improve the task allocation.

Definition 3 (Socially rational task delegation): Let P be a task allocation. The delegation δ of the task τ from agent i to agent j is defined s.t. the resulting allocation δ(P ) = {P (1), . . . , P (m)} is as follows:

∀k ∈ A \ {i, j}, P (k) = P (k) (6)
P (i) = P (i) \ {τ } ∧ P (j) = P (j) ∪ {τ } (7)
The delegation is socially rational iff:

w j (P ) + c j (τ ) < w i (P ) (8)
Since a socially rational task delegation δ strictly decreases the local makespan between the two agents, it does not increase the global makespan (C max δ(P ) ≤ C max (P )). We can now denote Γ i (P ) the set of socially rational task delegations that an agent i can initiate:

Γ i (P ) = {τ ∈ P (i) | w j (P ) + c j (τ ) < w i (P )} (9)
A task allocation P is said stable if no agent can perform a socially rational task delegation. Property 1: A non-stable task allocation can always lead to a stable one using a finite number of socially rational task delegations.

Proof 1: Let P a task allocation and W P =< w i1 , . . . , w im > the vector of the workloads in decreasing order where w ir denotes the r th largest workload. If P is not stable, there exists a socially rational task delegation δ which leads to P = δ(P ). Formally, ∃i, j ∈ A, max w i (P ), w j (P ) < max w i (P ), w j (P ) [START_REF] Chen | Handbook of combinatorial optimization[END_REF] ∧∀k ∈ A \ {i, j}, w k (P ) = w k (P ) [START_REF] Horowitz | Exact and approximate algorithms for scheduling nonidentical processors[END_REF] It implies that W P < W P in the lexicographic order. Formally,

∃r ∈ [1, m] ∀r < r, W P (r ) = W P (r ) ∧ W P (r) < W P (r)
Since there is a finite number of allocations and the order is strict, there is a finite number of socially rational task delegations.

Let us consider the following walk-through example.

Example 1: Let M AST A ex =< N ode, A, T , l, d, c > a problem of size (2, 2, 7), where N ode = {node 1 , node 2 }, A = {1, 2} and T = {τ 1 , . . . , τ 7 } with l(1) = node 1 , l(2) = node 2 .
The locations and costs of tasks are represented in Tab. I. Let us consider the task allocations P mks Let P = δ 1 (P ) be the task allocation where δ 1 is the delegation of τ 6 from agent 1 to agent 2. Since w 1 (P ) = 38 and w 2 (P ) = 40, δ 1 improves the makespan (i.e. C max (P ) = 40). However P is not stable. Let P = δ 2 (P ) be the task allocation where δ 2 is the delegation of τ 1 from agent 2 to agent 1. Even if P is not optimal (C max (P ) > C max (P mks)), P is stable.

τ 1 τ 2 τ 3 τ 4 τ 5 τ 6 τ 7 d 1 (τ k ) 1 0 3 6 1 6 0 d 2 (τ k ) 0 4 6 12 4 1 7 c 1 (τ k ) 1 8

IV. Negotiation process

We sketch here the iterated negotiation process which is concurrent with task consumptions. When a task is performed, it is removed from the set of tasks, and so the multi-agent system tries to minimize the makespan with respect to this new MASTA problem.

A task consumption is a disruptive event which modifies the MASTA problem and the task allocation.

Definition 4 (Task consumption): Let P be the current task allocation for the problem M AST A = N ode, A, T , l, d, c . The consumption γ of the task τ by agent i leads to the task allocation P = γ(P ) for the problem M AST A = N ode, A, T , l, d, c such that:

T = T \ {τ } (12)
P (i) = P (i) \ {τ } (13) ∀j ∈ A \ {i}, P (j) = P (j) (14)
Obviously, task consumption may decrease the makespan. The sequence of task consumptions, which removes all the tasks from the initial allocation until a final empty one ⊥, consists of an iteration of MASTA problems. Decentralized task delegation process. Agents operate in concurrent, one-to-many and single-round negotiations for task delegations. Each negotiation, which is based on the Contract Net Protocol [START_REF] Smith | The contract net protocol: High-level communication and control in a distributed problem solver[END_REF], includes three decision steps: (a) the choice of the task to negotiate by the strategy of the initiator described in Sec. V, (b) the refusals/bids from the peers based on the social rationality of the task delegation, and (c) the selection of the winning bid by the initiator, e.g. the bidder with the smallest workload. Several negotiations involving different groups of agents may concurrently occur and agents can bid in several simultaneous negotiations as in [START_REF] Alrayes | Concurrent bilateral negotiation for open e-markets: the CONAN strategy[END_REF]. The concurrency of task delegations improves the responsiveness of the task reallocation. Even if an agent which is involved in a negotiation as a bidder cannot initiate another negotiation (and conversely), agents can simultaneously bid in concurrent negotiations. In order to tackle the eager bidder problem [START_REF] Schillo | The eager bidder problem: a fundamental problem of dai and selected solutions[END_REF], we adopt a conservative approach where the task delegations are warranted to be socially rational [START_REF] Baert | Negotiation Strategy of Divisible Tasks for Large Dataset Processing[END_REF]. Therefore, several task delegations can be concurrently negotiated.

Since there is no shared knowledge, an agent has partial and not necessarily true beliefs about the current allocation P . Indeed, agent i knows its own workload w i (P ) and it has a belief base: B i (P ) = w i 1 (P ), . . . , w i i-1 (P ), w i i+1 (P ), . . . , w i m (P ) (15) where w i j (P ) is the belief of agent i about the workload of agent j in the allocation P .

The set of potential socially rational task delegations Γ B i (P ) that an agent i can initiate in the task allocation P is based on its belief base B i (P ). Formally,

Γ B i (P ) = {τ ∈ P (i) | w i j (P ) + c j (τ ) < w i (P )}. ( 16
)
Similarly, the computation of the local makespan by the initiator of a negotiation is based on its belief base, possibly inaccurate. This is the price to pay for the decentralization. However, an agent informs its peers about their workload when they are triggered for the first time, within the negotiation messages, and after each task consumption. Therefore, the bidder belief base is updated and the latter rejects the task delegations which are not socially rational. Therefore, a successful negotiation can only reach a socially rational task delegation, and so tends to improve the makespan.

Concurrent consumptions and delegations. Task delegations and task consumptions are concurrent and complementary since a task removal may allow new socially rational task delegations. Fig. 1 represents their impact on the allocation until all of the tasks are performed. Starting from the initial allocation P 0 , agents perform socially rational task delegations to improve the makespan (e.g. the path from P 0 to P k ) until a task consumption (e.g. the edge from P k to P 0 ), which eventually interrupts the path toward a stable allocation (e.g. the path from P k to P 0 represented in grey). A task consumption may occur when the agents have reached a stable allocation (e.g. P stable ) or not (e.g. P k ).

Socially rational task delegation

V. Location-aware strategy

During the overall process, task negotiations and task consumptions are concurrent. The strategy of an agent allows to select the next potential socially rational delegation and the next task to perform.

Definition 5 (Strategy): Let P be an allocation, the strategy of agent i is the couple (perf orm i , negotiate i ) where:

• perf orm i : 2 T → T ∪ {⊥}, selects the next task to perform within P (i) or none (denoted ⊥) if P (i) = ∅; • negotiate i : 2 T → T ∪ {⊥}, selects the next task to negotiate within Γ B i (P ) or none (denoted ⊥) if Γ B i (P ) = ∅. Local agnostic strategy. In a first approach, an agent i can perform the largest task in its bundle and negotiate the smallest one in the set of potential socially rational delegations. Formally,

> τ = argmax τ ∈P (i) {c i (τ )} ( 17
) < τ = argmin τ ∈Γ B i (P ) {c i (τ )} (18)
where > τ and < τ denote the next task to perform and the next one to negotiate, respectively. This strategy only requires that the agent sorts the tasks by their costs. However, resource fetching consumes time and represents an extra cost for task execution.

In order to measure the locality of tasks, we define the local availability ratio of an agent i for a task as the ratio between the number of local resources for this task with respect to the agent and the total number of resources for the task: Definition 6 (Local availability ratio): The local availability ratio of the agent i for the task τ (denoted o i (τ )) is defined as:

o i (τ ) = d i (τ ) d τ ( 19
)
The maximum local availability ratio for the task τ is:

ô(τ ) = max i∈A {o i (τ )} ( 20
)
Location-aware strategy. Intuitively, an agent should perform first the tasks which may cost more for its peers and it should negotiate first the tasks which may cost less for its peers. According to this strategy, an agent performs first the large local tasks and it negotiates first the large distant ones based on its local beliefs and knowledge, i.e. the local availability ratios and the task costs. This strategy is built on a data structure, called local-aware bundle.

The local-aware bundle of agent i (see Fig. 2) is divided in three subbundles in accordance with the local availability ratios of the agent for the tasks.

1) The maximum local bundle (denoted M B) contains the tasks such that agent i owns at least one resource and there is no other agent which owns more resources for this task. Formally,

∀τ ∈ M B, o i (τ ) = 0 ∧ o i (τ ) = ô(τ ) (21)
In M B, the tasks are sorted in decreasing order of cost (cf. left of Fig. 2).

2) The intermediate local bundle (denoted IB) contains the tasks which are partially local. Formally,

∀τ ∈ IB, 0 < o i (τ ) < ô(τ ). ( 22
)
In IB, the tasks are sorted in decreasing order of local availability ratio and the tasks with the same local availability ratio are sorted in decreasing order of cost (cf. center of Fig. 2).

3) The distant bundle (denoted DB) contains the tasks which are distant. Formally,

∀τ ∈ DB, o i (τ ) = 0. ( 23
)
In DB, the tasks are sorted in increasing order of cost (cf. right of Fig. 2). When an agent looks for a task to perform, it starts from the top of the maximum local bundle, i.e. the largest local task. When an agent looks for a task to negotiate, it starts from the bottom of the distant bundle (i.e. the largest distant task) and it selects the first one which is a potential Fig. 2: The local-aware bundle contains the maximum local bundle (at left), the intermediate local bundle (at center) and the distant bundle (at right). The rectangle size represents the cost of the task. The arrows depict the order in which an agent looks for a task to perform/negotiate. socially rational delegation according to its beliefs, B i (P ). Formally,

• An agent looks for the task to perform

> τ ∈ M B s.t. ∀τ ∈ M B \ { > τ }, c i ( > τ ) ≥ c i (τ ). ( 24
)
When M B = ∅, it looks for

> τ ∈ IB s.t. ∀τ ∈ IB \ { > τ }, o i ( > τ ) > o i (τ ) ∨ o i ( > τ ) = o i (τ ) ∧ c i ( > τ ) ≥ c i (τ ) . ( 25
)
Then, when IB = ∅, it looks for

> τ ∈ DB s.t. ∀τ ∈ DB \ { > τ }, c i ( > τ ) ≤ c i (τ ). ( 26
)
Finally, when M B = IB = DB = ∅, the agent has no task to perform.

• An agent looks for the task to negotiate

< τ ∈ DB s.t. ∀τ ∈ DB ∩ Γ B i (P ) \ { < τ }, c i ( < τ ) ≥ c i (τ ). (27)
Then, when DB = ∅, it looks for

< τ ∈ IB s.t. ∀τ ∈ IB ∩ Γ B i (P ) \ { < τ }, o i ( < τ ) < o i (τ ) ∨ o i ( < τ ) = o i (τ ) ∧ c i ( < τ ) ≥ c i (τ ) . (28)
Then, when IB = ∅, it looks for

< τ ∈ M B s.t. ∀τ ∈ M B ∩ Γ B i (P ) \ { < τ }, c i ( < τ ) ≤ c i (τ ). (29)
Finally, when such a task is not found the agent stops to negotiate. It is worth noticing that the leximax order over the intermediate local bundle promotes the principle that an agent should perform large local tasks and negotiate large distant ones. When an agent browses the intermediate local bundle, it starts from the tasks with a high local availability ratio in order to perform them and it starts from the tasks with a low local availability ratio in order to negotiate them. When the agent considers tasks which have the same local availability ratio, it always browses them in the same order: from the costliest to the less costly task (cf. Fig. 2). Thus, when the agent browses the intermediate local bundle to look for a task to perform, it considers the most local and costliest task. When the agent browses the intermediate local bundle to look for a task to negotiate, it considers the less local and costliest task.

τ 1 τ 2 τ 3 τ 4 τ 5 τ 6 τ 7 o 1 (τ k ) 1 0 0.
c i (τ ) = d i (τ ) + 2 d τ -d i (τ ) = 2d τ -d i (τ ) (30)
Tab. II represents the local availability ratios of the agents for all the tasks. Let us consider the allocation where agent 1 owns all the tasks. According to the local agnostic strategy, agent 1 cannot discriminate amongst τ 2 and τ 6 for delegation since these tasks have the same cost for the agent. According to the location-aware strategy and its bundle given in Fig. 3, agent 1 considers:

• the execution of the tasks τ 6 , τ 1 , τ 4 , τ 3 , τ 5 , τ 2 , then τ 7 ; • the negotiation of the tasks τ 7 , τ 2 , τ 5 , τ 4 , τ 3 , τ 1 , then τ 6 . The location-aware strategy leads agent 1 to perform τ 6 and to negotiate τ 7 in order to decrease the makespan since τ 6 is almost local and τ 7 is distant. In particular, agent 1 executes τ 6 before τ 1 since τ 6 is more expensive (cf. Tab. I). We emphasize that the tasks in the intermediate local bundle are sorted first by local availability ratio, then by cost. Whether agent 1 is seeking to negotiate or perform a task, it will consider the tasks which have the same local availability ratio in the same order (e.g. τ 4 , then τ 3 ).

VI. Practical application

We apply our framework to revisit the distributed deployment of the MapReduce design pattern in order to process large datasets on a cluster [START_REF] Dean | MapReduce: Simplified data processing on large clusters[END_REF]. Within such a cluster a MapReduce job consists of two successive phases: map and reduce. During the map phase, nodes filter in parallel input data and generate key-value pairs written into data chunks. During the reduce phase, nodes process in parallel the keys and their individual lists of values. In order to transfer map output to the corresponding reduce tasks, the partitioning specifies that all the values for each key are grouped together and make sure that all the values of a single key go to the same reducer. This partitioning is fixed a priori; in Hadoop it is evaluated modulo the number of reducers by default.

Even though Hadoop distributes keys evenly across reducers, some reducers are still assigned more data because the assigned key groups contain significantly more values [START_REF] Kwon | Managing skew in Hadoop[END_REF]. Thus, the reducers' runtime is highly uneven. By revisiting MapReduce with our location-aware strategy we allow agents to perform the load-balancing and thus improve the job runtime. For this purpose, we specify the cost function in conformance with Eq. 1.

Definition 7 (Locality-based linear cost function): The locality-based linear cost function for agent i ∈ A is defined s.t.:

c i (τ ) = ρ∈chunksτ c i (ρ), with c i (ρ) = |ρ| if l ρ = l i κ × |ρ| otherwise (31
) where chunks τ denotes the d τ data chunks (ρ 1 , . . . , ρ dτ ) required by task τ , |ρ| is the size of chunk ρ, and l ρ its location. We arbitrarily use κ = 10. The ingenuousness and inaccuracy of the cost function is removed by the dynamic and adaptive task reallocation which allows us to best exploit the computation nodes.

We have developed a multi-agent version of the MapReduce pattern in a distributed system setting using the MAS4Data test-bed [START_REF]MAS4Data[END_REF]. MAS4Data is implemented in Akka [START_REF] Lightbend | Akka toolkit[END_REF] for highly concurrent, distributed, and resilient message-driven applications. Even if fault-tolerance of nodes is out of the scope of this paper, we assume that: (a) the message transmission delay is arbitrary but not negligible, (b) the messages sent between a given pair of agents is such that their order is always preserved and (c) messages may be lost. For (c) we have included acknowledgments and deadline mechanisms in the interaction protocol used between agents. In addition, to decrease the complexity related to the design of a reducer agent, we have adopted a modular agent architecture that allows for concurrent operation between negotiation and performance of reduce tasks, as well as separation between communicative and decision making behaviours.

Our experiments have been performed on 16 PCs with 4 cores Intel(R) i7 and 16GB RAM each. They are based on a 8 Gio dataset (82, 283 keys) which has been generated such that the initial task allocation (cf. Fig. 5) is poorly load-balanced in order to check that the proximity between the data resources and the processing nodes has an impact on the makespan and so on the job runtime. The initial task allocation is the outcome of the partitioning of the MapReduce process. In other words, when there is no negotiation, MAS4Data has the same behaviour as Hadoop.

Fig. 4 compares the median job runtimes when the agents adopt the local agnostic strategy or the locationaware one with 10 runs for each (re)allocation. We observe that the location-aware strategy significantly improves the runtime, around -7.6%. For comparison, the job runtime without challenging the Hadoop default partitioning is 853 seconds (around +100%). We deduce that the price of the negotiation can be neglected regarding the impact of the load-balancing. Moreover, the negotiation allows to decrease the job runtime and even more with the locationaware strategy. Due to the observable nondeterminism of distributed execution, we consider a distinctive runtime. Fig. 5 compares the task allocation when all the tasks have been performed independently of whether they have been negotiated (or not) amongst the 16 agents in accordance with the local agnostic strategy or the location-aware one 1 . Both strategies are compared ex-post. We observe that the makespan of the initial allocation is approximately 3.3 10 8 , around 2.5 10 8 (-24%) for the negotiation with the local agnostic strategy and 2 10 8 (-30.7%) for the location-aware one. We deduce that the cost of the negotiation, in particular with the location-aware strategy, is less than the time saved by the load-balancing.

Fig. 6 depicts the number of tasks t such that α ≤ o i (t) < α + 0.1 where agent i performs t. The initial task allocation is poorly load-balanced since there are more 1 Our preliminary empirical analysis shows that: (a) information status (meta-communication) is free with respect to resource fetching in the context of large dataset processing and (b) there is no added value to have more than one reducer agent per node/disk. than 4.6 10 4 tasks such as o i (τ ) = 0. We observe that the location-aware strategy promotes the performance of tasks which are mostly local, i.e. o i (τ ) ≥ 0.5. This is not the case for the local agnostic strategy. For instance, there are 171 tasks that have been performed by an agent which owns 60% of the chunks (i.e. resources) using the location-aware strategy but none with the local agnostic one. Since the location-aware strategy promotes the execution of tasks by the nodes which are closer to the chunks, the loadbalancing is improved and so the job runtime is decreased.

VII. Conclusion

In this paper, we have formalized the multi-agent situated task allocation problem to develop a location-aware strategy for addressing the load balancing problem in distributed systems. The strategy adopts a market-based approach that allows us to decentralize load-balancing in order to minimize the makespan, i.e. the completion time of the last task to perform. During the overall process, task negotiations allow agents that use the strategy to reallocate the tasks concurrently with task consumption. The strategy also enables agents to select the next potential socially rational delegation and the next task to perform. According to their local beliefs and knowledge, the agents perform first large local tasks and they negotiate first large distant ones. In order to validate our approach, we have developed a prototype where agents negotiate the reduce tasks of the MapReduce design pattern in a distributed setting. Our experimental results show that, for such an application, the proposed location-aware strategy improves the application's load-balancing and so the job execution time.

We are currently evaluating our prototype with numerous and representative experiments with real-word datasets with various jobs/clusters. Some of these settings suggest that we need to extend our strategy to negotiate (a) task swaps to improve the makespan of stable allocations, and (b) task bundles in order to speedup the negotiation process. Even if our adaptive and dynamic approach tackles the problem of drop of performance, our long-term future work should take into account fault tolerance and so data replication.

Fig. 1 :

 1 Fig. 1: Concurrent task consumptions (vertical edges) and task delegations (horizontal edges).

Fig. 3 :

 3 Fig. 3: The local-aware bundle of agent 1

Fig. 4 :

 4 Fig. 4: The median job execution times (and the standard deviations) with the trivial strategy and the locality-based one (10 runs).

Fig. 5 :

 5 Fig. 5: Initial task allocation (Hadoop) and ex-post task allocation with the local agnostic strategy and the locationaware one.

Fig. 6 :

 6 Fig. 6: Number of tasks (with a logarithmic scale) per local availability ratio of the performing agent.

TABLE I :

 I

Locations and costs of tasks and P such that P mks = {{τ 1 , τ 3 , τ 5 , τ 6 }, {τ 2 , τ 4 , τ 7 }} and P = {{τ 2 , τ 4 , τ 6 }, {τ 1 , τ 3 , τ 5 , τ 7 }}. P mks is optimal since C max (P mks) = 35 (w 1 (P mks) = 33 and w 2 (P mks) = 35). It is not the case of P since w 1 (P ) = 46, w 2 (P ) = 27, and so C max (P ) = 46.

TABLE II :

 II Local availability ratiosExample 2 (Local-aware bundle): Recall Ex. 1 where we assume, for illustration purposes, that a remote resource is twice more expensive than a local one. Formally,

Acknowledgment

This work is supported by the call ULille "Internationalisation Actions bilatérales". We thank the reviewers for their comments.


L Maczyta

P Bouthemy

O Le Meur

UNSUPERVISED MOTION SALIENCY MAP ESTIMATION BASED ON OPTICAL FLOW INPAINTING

Keywords: Motion saliency, optical flow inpainting, video analysis

The paper addresses the problem of motion saliency in videos, that is, identifying regions that undergo motion departing from its context. We propose a new unsupervised paradigm to compute motion saliency maps. The key ingredient is the flow inpainting stage. Candidate regions are determined from the optical flow boundaries. The residual flow in these regions is given by the difference between the optical flow and the flow inpainted from the surrounding areas. It provides the cue for motion saliency. The method is flexible and general by relying on motion information only. Experimental results on the DAVIS 2016 benchmark demonstrate that the method compares favourably with state-of-theart video saliency methods.

INTRODUCTION

Motion saliency map estimation corresponds to the task of estimating saliency induced by motion. More specifically, regions whose motion departs from the surrounding motion should be considered as dynamically salient. Estimating motion saliency can be useful for a number of applications, such as navigation of mobile robots or autonomous vehicles, alert raising for video-surveillance, or attention triggering for video analysis. In contrast to video saliency approaches, we estimate motion saliency based on motion information only. Indeed, we do not resort to any appearance cues to make the method as general as possible. Furthermore, the method does not require any supervised (or unsupervised) learning stage. Our main contribution will consist in introducing flow inpainting to address in an original way the motion saliency problem.

Video saliency has been first developed as an extension of image saliency, with the objective to extract salient objects in videos. Considering video means that temporal information becomes available, and that motion is usable as an additional saliency cue. In [START_REF] Wang | Consistent video saliency using local gradient flow optimization and global refinement[END_REF], Wang et al. rely on intra-frame boundary information and contrast, as well as motion to predict video saliency. In [START_REF] Le | Contrast based hierarchical spatial-temporal saliency for video[END_REF], Le and Sugimoto propose a centersurround framework with a hierarchical segmentation model. In [START_REF] Karimi | Spatio-temporal saliency detection using abstracted fully-connected graphical models[END_REF], Karimi et al. exploit spatio-temporal cues and represent videos as spatio-temporal graphs with the objective of minimizing a global function.

Apparent motion in each frame is strongly influenced by camera motion. While some approaches directly combine spatial and temporal information without first cancelling the camera motion such as in [START_REF] Fang | Video saliency incorporating spatiotemporal cues and uncertainty weighting[END_REF][START_REF] Kim | Spatiotemporal saliency detection using textural contrast and its applications[END_REF][START_REF] Mahapatra | Coherency based spatio-temporal saliency detection for video object segmentation[END_REF], other methods explicitly compensate the camera motion such as in [START_REF] Le Meur | Predicting visual fixations on video based on low-level visual features[END_REF][START_REF] Huang | Video saliency map detection by dominant camera motion removal[END_REF].

Recently, deep learning methods have been explored to estimate saliency in videos. In [START_REF] Wang | Video salient object detection via fully convolutional networks[END_REF], Wang et al. propose a CNN exploiting explicitly the spatial and temporal dimensions, yet without computing any optical flow. In [START_REF] Le | Video salient object detection using spatiotemporal deep features[END_REF], Le and Sugimoto resort to spatio-temporal deep features to predict dynamic saliency in videos. They extend conditional random fields (CRF) to the temporal domain, and they make use of a multi-scale segmentation strategy. In [START_REF] Wang | Saliency-aware geodesic video object segmentation[END_REF], Wang et al. introduce saliency information as a prior for the task of video object segmentation (VOS), by using spatial edges and temporal motion boundaries as features.

The methods presented above are mostly directed toward the problem of video saliency, that is, extracting foreground objects departing from their context due to their appearance and motion. We are more specifically concerned with the problem of motion saliency, which is more general in some way, and highlights motion discrepancy only. Configurations of interest may arise due to motion only, as in crowd anomaly detection [START_REF] Pérez-Rúa | Detection and localization of anomalous motion in video sequences from local histograms of labeled affine flows[END_REF] (a person moving differently than the surrounding crowd, or similarly an animal in a flock or a herd, a car in the traffic, a cell in a tissue). In addition, appearance can be of very limited use or even helpless for some types of imagery, like thermal video or fluorescence cell microscopy.

The rest of the paper is organised as follows. Section 2 presents our method for motion saliency estimation. Section 3 reports comparative results with state-of-the-art methods for video saliency. Section 4 contains concluding comments.

MOTION SALIENCY ESTIMATION

As stated in the introduction, we estimate motion saliency maps in video sequences only from optical flow cues. We ex- pect that the optical flow field will be distinguishable enough in salient regions. We have to compare the flow field in a given area, likely to be a salient moving element, with the flow field that would have been induced in the very same area with the surrounding motion. The former can be computed by any optical flow method. The latter is not directly available, since it is not observed. Yet, it can be predicted by a flow inpainting method. This is precisely the originality of our motion saliency approach. Our method is then two-fold. We extract candidate salient regions and compare the inpainted flow to the original optical flow in these regions. A discrepancy between the two flows is interpreted as an indicator of motion saliency. In addition, we combine a backward and forward processing. Our overall framework is illustrated in Figure 1.

Extraction of inpainting masks

First, we have to extract the masks of the regions to inpaint. We will rely on the optical flow field computed over the image, and more precisely on its discontinuities. Indeed, the silhouette of any salient moving element should correspond to motion boundaries, since its motion should differ from the surrounding motion. The surrounding motion will be generally given by the background motion, also referred to as global motion in the sequel.

For the motion boundary extraction, one could directly apply a threshold on the norm of the gradient of the velocity vectors. This is however likely to produce noisy contours. Instead, we choose to rely on the classical contour extraction method proposed by Canny [START_REF] Canny | A computational approach to edge detection[END_REF]. For this, we convert the optical flow to its HSV representation which is commonly used for visualisation, the hue representing the direction of motion and the saturation its magnitude (see Fig. 2).

Then, we build region masks from these possibly fragmented contours as illustrated in Figure 1. Contours are first organised into connected parts. For each connected part, the convex envelope is computed and dilated with a 5x5 kernel. Each final region mask is given by the corresponding union of overlapping dilated convex envelopes. By construction, re-gion masks tend to be larger than actual salient areas. Nevertheless, this is desirable for inpainting, since inpainting must start from global motion information only. Yet, a too rough mask can decrease the accuracy of motion inpainting, especially for the salient areas which are non convex (see Fig. 1). The masks are then refined by applying the GrabCut algorithm [START_REF] Rother | Grabcutinteractive foreground extraction using iterated graph cuts[END_REF] on the HSV representation of the optical flow. To avoid small localisation errors which would include salient pixels in the inpainting mask, a dilatation with a 5x5 kernel is again applied to the resulting mask.

Optical flow inpainting

We dispose of a set R of inpainting masks in the image domain Ω. The issue now is to perform the flow inpainting in these masks from the surrounding motion. We have investigated three inpainting techniques to achieve it: two PDEbased methods [START_REF] Telea | An image inpainting technique based on the fast marching method[END_REF][START_REF] Bertalmio | Navierstokes, fluid dynamics, and image and video inpainting[END_REF] and a parametric method. Since the background motion to inpaint is globally smooth, a diffusionbased approach for inpainting is well-suited.

We apply the image inpainting method based on fast marching [START_REF] Telea | An image inpainting technique based on the fast marching method[END_REF] as done in [START_REF] Strobel | Flow and color inpainting for video completion[END_REF] for video completion, which is a different goal than ours. We similarly extend the Navier-Stokes based image inpainting method of [START_REF] Bertalmio | Navierstokes, fluid dynamics, and image and video inpainting[END_REF] to flow inpainting. We adopt the floating point representation of the velocity vectors {ω(p), p ∈ Ω} with ω(p) ∈ R 2 . The two components of the flow vectors are inpainted separately. Finally, we developed a parametric alternative. We assume that the surrounding motion, i.e., the background motion, can be approximated by a single affine motion model. The latter is estimated by the robust multiresolution method Motion2D [START_REF] Odobez | Robust multiresolution estimation of parametric motion models[END_REF]. The inpainting flow is then simply given by the flow issued from the estimated affine motion model over the masks. The three variants are respectively named MSI-fm, MSI-ns and MSI-pm (MSI stands for Motion Saliency Inpainting).

Motion saliency map computation

The residual flow, i.e., the difference between the optical flow and the inpainted flow, is then computed over the masks r, r ∈ R. The motion saliency map g, normalised within [0, 1], is derived from the residual flow as follows:

∀p ∈ R, g(p) = 1 -exp(-λ||ω inp (p) -ω(p)|| 2 ), ( 1
)
where ω is the optical flow, ω inp the inpainted flow, g(p) = 0 for p / ∈ R, and λ modulates the saliency score. Function g expresses that non-zero residual motion highlights salient moving elements. Parameter λ allows us to establish a tradeoff between robustness to noise and ability to highlight small but still salient motions.

Let us note that, if we were interested in an explicit motion segmentation, that is, producing binary maps, we would just need to set λ to a high value. Indeed, by applying a threshold τ to g(p), we can deduce from (1) that p will be segmented if:

||ω inp (p) -ω(p)|| 2 - ln(1 -τ ) λ . ( 2
)
With τ arbitrarily set to 1 2 (the middle value of [0, 1]), the decision depends only on λ. Pixels with residual flow magnitude greater than ln (2) λ will be segmented. This shows that our method is flexible, since we can shift from the motion saliency problem to the video segmentation problem just by tuning parameter λ.

Finally, we propose to further leverage the temporal dimension to reduce the number of false positive, in particular close to motion boundaries. To do this, we introduce a bidirectional processing (see Fig. 1). The whole workflow is applied twice in parallel, backward and forward, that is, to the image pair I(t), I(t -1) and the image pair I(t), I(t + 1). This yields two motion saliency maps, which we combine by taking their pixel-wise minimum. The reported experimental results for our main method and the NM method introduced in Section 3.3, will include this bidirectional processing.

EXPERIMENTAL RESULTS

Experimental setting

For the computation of the optical flow, we employ FlowNet 2.0 [START_REF] Ilg | Flownet 2.0: Evolution of optical flow estimation with deep networks[END_REF]. This algorithm can run almost in real time and estimates sharp motion boundaries. This is important for the successful extraction of inpainting masks.

For all the experiments, the parameters are set as follows. The Canny edge detector is applied to the image smoothed with a Gaussian filter of standard deviation σ = 5. The two thresholds for the Canny edge detector are set to 20 and 60 respectively. For the inpainting algorithm, a radius of 5 pixels around the region to inpaint is used. Finally, the parameter λ for the computation of the saliency map has been set to 3 2 . There is no available benchmark dedicated to motion saliency. Therefore, we choose the DAVIS 2016 dataset for the evaluation of our method. This dataset has been initially introduced in [START_REF] Perazzi | A benchmark dataset and evaluation methodology for video object segmentation[END_REF] for the video object segmentation (VOS) task. It has also been recently used to evaluate methods estimating saliency maps in videos, as in [START_REF] Wang | Video salient object detection via fully convolutional networks[END_REF][START_REF] Le | Video salient object detection using spatiotemporal deep features[END_REF]. For the VOS task, the object to segment is a foreground salient object of the video, which has a distinctive motion compared to the rest of the scene. It makes this dataset exploitable for motion saliency estimation, although appearance plays a role. Fig. 3. From left to right: one image from the video, binary ground truth, motion saliency maps predicted by our method MSI-ns, and the estimated forward residual flow (displayed with the motion colour code of Fig. 2).

Qualitative evaluation

First, we present a visual evaluation of our method MSI-ns, which turns out to be the best of the three variants as reported in Table 1. Fig. 3 displays the output of our method for frames of the videos soapbox, cows and kite-surf of the DAVIS 2016 dataset and for two other types of videos. In the fourth example (lawn video), a rectangular region in the lawn was artificially moved in the image as indicated by the ground truth. It provides us with an example where the only discriminative information is supplied by the undergone motion. The fifth image comes from the park video of the changedetection.net dataset [START_REF] Goyette | Changedetection.net: A new change detection benchmark dataset[END_REF]. It was acquired with a thermal camera, providing us with an example where appearance is of limited help.

Both computed motion saliency maps and residual flows are shown in Fig. 3. Indeed, the residual flow, although an intermediate step in our method, is meaningful on its own. It provides valuable additional information about the direction and magnitude of salient motions in the scene. It could be viewed as an augmented saliency map.

For the soapbox example, the salient element with clearly distinctive motion has been almost perfectly extracted. The cows example exhibits an interesting behaviour. The cow is globally moving, except for its legs which are intermittently static. This illustrates the difference between the video object segmentation task, for which the whole cow should be segmented, and the motion saliency estimation task, for which the elements of interest are elements with distinctive motion. Our method consistently does not involve the two legs in the saliency map.

In the kite-surf example, the sea foam has a non rigid but strong motion, and consequently, it is likely to belong to the Method STCRF [START_REF] Le | Video salient object detection using spatiotemporal deep features[END_REF] MSI-ns MSI-pm MSI-fm VSFCN [START_REF] Wang | Video salient object detection via fully convolutional networks[END_REF] RST [START_REF] Le | Contrast based hierarchical spatial-temporal saliency for video[END_REF] LGFOGR [START_REF] Wang | Consistent video saliency using local gradient flow optimization and global refinement[END_REF] salient moving region, whereas for the VOS task, the kitesurfer is the only foreground object to segment as defined in the ground truth.

In the lawn example, the square region is easy to detect when seeing the video, but is much harder to localize in a single frozen image. Our method based on optical flow is able to recover the salient moving region. Finally, in the park example involving an IR video with less pronounced appearance, our method also yields a correct motion saliency map.

Quantitative comparison

We introduce a naive method (named NM) to motion saliency estimation to better assess the contribution of the main components of our method. It merely consists in first computing the dominant (or global) motion in the image. To this end, we estimate an affine motion model with the robust multiresolution algorithm Motion2D [START_REF] Odobez | Robust multiresolution estimation of parametric motion models[END_REF]. No inpainting masks are extracted. The residual flow contributing to the motion saliency map is now the difference, over the whole image, between the computed optical flow and the estimated parametric dominant flow. As reported in Table 1, we observe that the method NM yields poor performance. It demonstrates the importance of the flow inpainting approach for motion saliency.

Table 1 also collects comparative results of our three variants, MSI-ns, MSI-pm and MSI-fm, with state-of-the-art methods for saliency map estimation in videos: LGFOGR [START_REF] Wang | Consistent video saliency using local gradient flow optimization and global refinement[END_REF], SAG [START_REF] Wang | Saliency-aware geodesic video object segmentation[END_REF], RST [START_REF] Le | Contrast based hierarchical spatial-temporal saliency for video[END_REF], STCRF [START_REF] Le | Video salient object detection using spatiotemporal deep features[END_REF] and VSFCN [START_REF] Wang | Video salient object detection via fully convolutional networks[END_REF]. Results of these methods are those reported in [START_REF] Le | Video salient object detection using spatiotemporal deep features[END_REF], except for [START_REF] Wang | Video salient object detection via fully convolutional networks[END_REF], for which we used saliency maps provided by the authors to compute the metrics.

We carried out the experimental evaluation on the test set of DAVIS 2016, which contains 20 videos. The quantitative evaluation on the DAVIS 2016 dataset is useful, but may generate a (small) bias. The available ground truth on DAVIS 2016 may not fully fit the requirements of the motion saliency task as illustrated in Fig. 3 and commented in Section 3.2, since it is object-oriented and binary.

For the evaluation, we use the Mean Average Error (MAE), F-Adap and F-Max metrics, that we compute the same way as in [START_REF] Le | Video salient object detection using spatiotemporal deep features[END_REF]. The MAE is a pixel-wise evaluation of the saliency map g compared to the binary ground truth. F-Adap and F-Max are based on the weighted F-Measure, in which the weight β 2 is set to 0.3 following [START_REF] Le | Video salient object detection using spatiotemporal deep features[END_REF]:

F β = (1 + β 2 )P recision × Recall β 2 × P recision + Recall (3)
F-Adap involves an adaptive threshold on each saliency map based on the mean and standard deviation of each map, while F-Max is the maximum of the F-Measure for thresholds varying in [0,255].

Our method MSI-ns obtains consistently satisfactory results, as it ranks second for the three metrics. The two other variants, MSI-pm and MSI-fm, respectively rank third and fourth, but follow MSI-ns by a small margin. Let us recall that we obtain our results without any learning on saliency and any appearance cues in contrast to [START_REF] Le | Video salient object detection using spatiotemporal deep features[END_REF], which performs the best. Our parametric and diffusion-based flow inpainting methods have close performance on the DAVIS 2016 dataset. However, the latter should be more easily generalisable, since the surrounding motion cannot be always approximated by a single parametric motion model.

Regarding the computation time, the MSI-ns method takes 10.3s to estimate the motion saliency map for a 854x480 frame on a 2.9 GHz processor. Our code is written in Python and can be further optimised. Notably, the forward and backward streams of the workflow could be parallelised.

CONCLUSION

We proposed a new paradigm to estimate motion saliency maps in video sequences based on optical flow inpainting. It yields valued saliency maps to highlight the presence of motion saliency in videos. We tested our method on the DAVIS 2016 dataset, and we obtained state-of-the-art results, while using only motion information and introducing no learning stage. This makes our method of general applicability. Additionally, the computed residual flow on its own provides augmented information on motion saliency, which could be further exploited. Our current method relies on three successive frames. Future work will aim to further leverage the temporal dimension by exploiting longer-term dependencies.

Fig. 1 .

 1 Fig. 1. Overall framework of our method for motion saliency map estimation with the two backward and forward streams.

Fig. 2 .

 2 Fig. 2. Colour code (left) for the corresponding optical flow field (right).

Table 1 .

 1 Comparison with state-of-the-art methods for saliency map estimation on the test set of DAVIS 2016. In bold, the best performance; the second best. We also indicate whether the method relies on appearance information, on motion information, and whether it is supervised.

	SAG [11]	NM

This work was supported in part by the DGA and the Région Bretagne as co-funding of Léo Maczyta's PhD thesis