Françoise Balthasart

Valérie Janez Plavec

Valérie Gabelica

Ammonium ion binding to DNA G-quadruplexes: do electrospray mass spectra faithfully reflect the solution-phase species?

Ammonium ion binding to DNA G-quadruplexes: do

electrospray mass spectra faithfully reflect the solution-phase species?

Introduction

Nucleic acid sequences containing series of adjacent guanines can form particular nucleic acid structures called G-quadruplexes [START_REF] Neidle | The structures of quadruplex nucleic acids and their drug complexes[END_REF][START_REF] Lane | Stability and kinetics of Gquadruplex structures[END_REF][START_REF] Burge | Quadruplex DNA: sequence, topology and structure[END_REF], in which four guanines can form G-quartets.

Sufficiently high ionic strength is required to favor the self-assembly of negatively charged strands. Moreover, the very nature of the cation also influences the G-quadruplex structure and stability [START_REF] Gray | Kinetics and mechanism of K + -and Na + -induced folding of models of human telomeric DNA into G-quadruplex structures[END_REF][START_REF] Phan | Human telomeric G-quadruplex: structures of DNA and RNA sequences[END_REF], because specific cation coordination occurs between the stacked G-quartets.

G-quadruplex structures can differ by their strand orientation (parallel/antiparallel), by the syn/anti conformation of each base relative to the deoxyribose, and by the placement of their loops. These three structural characteristics are inter-dependent [START_REF] Webba Da Silva | Geometric formalism for DNA quadruplex folding[END_REF].

Like many other cation-bound supramolecular assemblies [START_REF] Schalley | Mass Spectrometry and Gas-Phase Chemistry of Non-Covalent Complexes[END_REF], G-quadruplexes can be studied by mass spectrometry (for a recent review, see [START_REF] Yuan | Mass spectrometry of G-quadruplex DNA: formation, recognition, property, conversion, and conformation[END_REF]), with the restriction thatsolutions in which a physiological ionic strength (150 mM monovalent cations) would be ensured solely by Na + or K + cannot be used. Ammonium cations can be used instead [START_REF] Rosu | Triplex and quadruplex DNA structures studied by electrospray mass spectrometry[END_REF], as NH [START_REF] Gray | Kinetics and mechanism of K + -and Na + -induced folding of models of human telomeric DNA into G-quadruplex structures[END_REF] + ions also coordinate between G-quartets and thereby stabilize G-quadruplexes in solution [START_REF] Nagesh | Ammonium ion at low concentration stabilizes the Gquadruplex formation by telomeric sequence[END_REF][START_REF] Hud | Binding sites and dynamics of ammonium ions in a telomere repeat DNA quadruplex[END_REF][START_REF] Schultze | The effect of sodium, potassion and ammonium ions on the conformations of the dimeric quadruplex formed by the Oxytricha nova telomere repeat oligonucleotide d(G4T4G4)[END_REF].

When sufficient internal energy is provided to the biomolecule, neutral ammonia is lost following proton transfer to the biomolecule. Mass spectrometry analysis of G-quadruplexes from ammonium solutions therefore entails the following tradeoff.On the one hand, it is desirable to preserve these internal ammonium cations in the gas phase, because (1) detecting them is a strong indication that G-quadruplex structures existed in solution [START_REF] Rosu | Triplex and quadruplex DNA structures studied by electrospray mass spectrometry[END_REF], and [START_REF] Lane | Stability and kinetics of Gquadruplex structures[END_REF] preserving them is thought to be essential to preserve the structure in the gas phase [START_REF] Rueda | G-quadruplexes can maintain their structure in the gas phase[END_REF][START_REF] Gabelica | Stabilization and structure of telomeric and c-myc region intramolecular Gquadruplexes: The role of central cations and small planar ligands[END_REF][START_REF] Gabelica | Infrared Signature of DNA Gquadruplexes in the Gas Phase[END_REF].

On the other hand, it is desirable to get rid of ammonium ions bound to less specific sites like the phosphate groups, in order to obtain cleaner mass spectraand higher sensitivity.

In parallel G-quadruplex structures, the internal ammonium ions are much less labile in the gas phase than the other ammonium ions, so mass spectral peaks with the specific number of internal ammonium ions can be detected over a wide range of instrumental tuning settings [START_REF] Rosu | Triplex and quadruplex DNA structures studied by electrospray mass spectrometry[END_REF][START_REF] Gros | Guanines are a quartet's best friend: impact of base substitutions on the kinetics and stability of tetramolecular quadruplexes[END_REF][START_REF] Collie | Electrospray mass spectrometry of telomeric RNA (TERRA) reveals the formation of stable multimeric G-quadruplex structures[END_REF][START_REF] Ferreira | Mass spectrometry and ion mobility spectrometry of G-quadruplexes. A study of solvent effects on dimer formation and structural transitions in the telomeric DNA sequence d(TAGGGTTAGGGT)[END_REF]. In antiparallel structures, internal ammonium ions are usually more labile than in parallel structures [START_REF] Rosu | Triplex and quadruplex DNA structures studied by electrospray mass spectrometry[END_REF][START_REF] Ferreira | Mass spectrometry and ion mobility spectrometry of G-quadruplexes. A study of solvent effects on dimer formation and structural transitions in the telomeric DNA sequence d(TAGGGTTAGGGT)[END_REF], but the relative lability of inter-quartet vs. externally bound ammonium ions has not been investigated systematically. One previous MS/MS study focused on base loss and strand separation [START_REF] Mazzitelli | Gas-phase stability of Gquadruplex DNA determined by electrospray ionization tandem mass spectrometry and molecular dynamics simulations[END_REF], which are dissociation steps subsequent to ammonium loss.

Our objective is to address the following questions in the case of antiparallel G-quadruplexes produced from ammonium acetate solutions.To what extent do the mass spectra reflect the binding constants of ammonium ions in solution? What is the optimum instrumental tuning to determine the number of specific binding sites using the ammonium ion distribution detected in the mass spectra? Would similar conclusions be reached by different users on different instruments?What is the influence of ammonium ion loss on the gas-phase structure?

To answer these questions, we studied five DNA G-quadruplexes which structures and ammonium ion binding sites have been determined by NMR in ammonium solution (Figure 1).For bimolecular G-quadruplexes (dG 4 T 4 G 4 ) 2 (Figure 1A) and (dG 4 T 3 G 4 ) 2 (Figure 1B), the ammonium ion association constants are too high to be determined by NMR [START_REF] Sket | NH4+)-N-15 ion movement inside d(G(4)T(4)G(4))(2) G-quadruplex is accelerated in the presence of smaller Na+ ions[END_REF][START_REF] Podbevsek | Stacking and not solely topology of T3 loops controls rigidity and ammonium ion movement within d(G4T3G4)2 G-quadruplex[END_REF], so it can be considered that 100% of the G-quadruplexes contain three ammonium ions in solution. The structuraldifference lies in the placement of the loops: the T 4 loops in (dG 4 T 4 G 4 ) 2 are diagonal (bridging opposite corners of a G-quartet) [START_REF] Sket | NH4+)-N-15 ion movement inside d(G(4)T(4)G(4))(2) G-quadruplex is accelerated in the presence of smaller Na+ ions[END_REF], whereas the T 3 loops in (dG 4 T 3 G 4 ) 2 are lateral (bridging adjacent corners of a G-quartet) [START_REF] Podbevsek | Stacking and not solely topology of T3 loops controls rigidity and ammonium ion movement within d(G4T3G4)2 G-quadruplex[END_REF]. The G-quadruplex(dG 3 T 4 G 4 ) 2 (Fig. 1C) contains three G-quartets and two inner ammonium ion binding sites [START_REF] Crugelj | Small change in a G-rich sequence, a dramatic change in topology: new dimeric g-quadruplex folding motif with unique loop orientations[END_REF][START_REF] Sket | Identification of mixed di-cation forms of Gquadruplex in solution[END_REF][START_REF] Sket | Not all G-quadruplexes exhibit ion-channel-like properties: NMR study of ammonium ion (non)movement within the d(G(3)T(4)G(4))(2) quadruplex[END_REF][25].Its two strands are not equivalent:one strand has a long GT 4 diagonal loop, and the other strand has one T 4 lateral loop and one propeller loop with no base.The intramolecular quadruplex dG 4 (T 4 G 4 ) 3 (Fig. 1D) has one diagonal T 4 loop, two lateral T 4 loops, four G-quartets and three inner ammonium ions [25,[START_REF] Podbevsek | NMR evaluation of ammonium ion movement within a unimolecular G-quadruplex in solution[END_REF]. Finally, the sequence dG 2 T 2 G 2 TGTG 2 T 2 G 2 (Fig. 1E), also called the thrombin binding aptamer (or "TBA") forms an intramolecular G-quadruplex with three lateral loops, two G-quartets and one inner ammonium ion binding site [27]. TBA binding to cations such as Na + , K + , Sr 2+ has been studied by ESI-MS previously [START_REF] Vairamani | G-quadruplex formation of thrombin aptamer detected by electrospray ionization mass spectrometry[END_REF][START_REF] Wilcox | Method of measuring oligonucleotidemetal affinities: Interactions of the thrombin binding aptamer with K + and Sr 2+[END_REF][START_REF] Hong | Mass spectrometric studies of alkali metal ion binding on thrombin-binding aptamer DNA[END_REF], but the detection of ammonium ion binding to TBA has not yet been reported.For the latter three sequences, the ammonium ion binding constants have been determined previously by NMR [25,27], so the theoretical distribution of ammonium ions captured between the G-quartets of the quadruplexes in solution can be calculated (Table 1).

Experimental section

The samples were prepared as described in the Supporting Information S1. Four different mass spectrometers were used, in the negative ion mode: a Solarix 9.4T ESI-Q-FTICRMS (Bruker Daltonics, Bremen, Germany), a Q-TOF Ultima Global ESI-Q-TOFMS, a Synapt G1 and a Synapt G2 HDMS ESI-Q-IM-TOFMS (the latter three from Waters, Manchester, UK).

The effects of instrumental tuning on the ammonium ion preservation will be illustrated with the bimolecular quadruplex [(dG 4 T 4 G 4 ) 2 ] 5-(Figure 2 and Supporting Information S2), which is particularly sensitive to instrumental tuning [START_REF] Rosu | Triplex and quadruplex DNA structures studied by electrospray mass spectrometry[END_REF]. The softest possible conditions, taken as those giving the highest ratio between the 3-NH 4 peak and the 2-NH 4 peak, were sought on each mass spectrometer. The softest possible experimental conditions on each mass spectrometer are given in Supporting Information S2, with extended discussion of critical parameters.

Ion mobility calibration was carried out using oligonucleotides of known collision cross section (CCS), as described previously (supporting information of [START_REF] Arcella | The structure of triplex DNA in the gas phase[END_REF]).The prediction error (the CCS interval in which one has 95% chances of finding the true value usingthe calibration curve) is 1.6% and the confidence error (the CCS interval in which repeated measurements of molecules belonging to the dataset will be found) is 0.3%. The prediction error must be considered when comparing our experiments with experiments carried out on a different instrument or with calculations, and the confidence error must be considered when comparing different systems measured on the same instrument. The CCS distributions were fitted using quadruplex was chosen because it is very rigid [START_REF] Rueda | G-quadruplexes can maintain their structure in the gas phase[END_REF][START_REF] Gabelica | Fast gas-phase hydrogen/deuterium exchange observed for a DNA G-quadruplex[END_REF][START_REF] Gidden | Structural motifs of DNA complexes in the gas phase[END_REF],and its CCS peak displays a resolution of 75 on the Synapt G2 HDMS.

Results and discussion

Electrospray mass spectrometers are not equally suited to preserve specific inner ammonium ions

The Solarix ESI-FTICRMSand the Synapt G1 provided the softest experimental conditions (see Figure 2A for a typical spectrum).The two other Q-TOF type instruments were found harsher than the Synapt G1, but for different reasons.With the particular source of the Q-TOF Ultima Global mass spectrometer (Figure 2B), the 3-NH 4 /2-NH 4 ratio is similar to that obtained on the ESI-FTICRMS (Fig. 2A), but simultaneously, a peak with zero ammonium ion adducts is also observed. Therefore, a major fraction of the ions is produced in soft conditions, while a small fraction of the ions acquires a significantly higher internal energy, and the whole ESI-MS ammonium ion binding distribution does not reflect the solution phase distribution.On the Synapt G2 HDMS, ammonium loss was more abundant in the ion mobility mode than on all other mass spectrometers.

Collision-induced dissociation occurs inside the travelling wave ion mobility cell

In addition to ion heating before the IMS cell [START_REF] Merenbloom | How hot are your ions in TWAVE ion mobility spectrometry?[END_REF][START_REF] Morsa | Effective Temperature of Ions in Traveling Wave Ion Mobility Spectrometry[END_REF], ion heating could also occur inside travelling wave IMS cells, as reported for small singly charged ions [START_REF] Morsa | Effective Temperature of Ions in Traveling Wave Ion Mobility Spectrometry[END_REF][START_REF] Shvartsburg | Fundamentals of Traveling Wave Ion Mobility Spectrometry[END_REF]. However, as the extent of ion heating is supposed to decrease when the size of the system increases, increase when the charge increases, and decrease when the cell pressure increases, whether detectable ion heating inside the IMS cell would be observed for larger, multiply charged ions on a Synapt G2 mass spectrometer remained unknown. For [(dG 4 T 4 G 4 ) 2 •(NH 4 ) 3 ] 5-, lowering the IMS wave height from 40 V to 25 V (Figures2Cand 2D, respectively), or increasing the IMS wave velocity from 1000 m/s to 1600 m/s (see Supporting Information S2) leads to better preservation of the three ammonium ions, confirming that ion heating is partly occurring inside the IMS cell.

In some G-quadruplexes, inner ammonium ions are too labile to be fully retained in the gas phase structures For (dG 4 T 4 G 4 ) 2 (Fig. 2A) the bias of the ammonium ion distribution towards the 3-NH 4 species as the conditions soften is clear, but the 2-NH 4 peak remains at ~20%, for both charge states. The ammonium ammonium ion distributionsfor the other G-quadruplexes, recorded on the Solarix ESI-FTICRMS instrument in the softest possible conditions, are shown in Figure 3 (Supporting Information section S3 shows the full scan mass spectra, and zooms on the ammonium ion distribution of the two lowest charge states). For (dG 3 T 4 G 4 ) 2 (Fig. 3B) and dG 4 (T 4 G 4 ) 3 (Fig. 3C), the ammonium ion distribution mirrors the one expected from the solution phase NMR data (Table 1). The two othersequences, however, failed to give spectra close to the expected ammonium ion distribution. The mass spectra of the sequence (dG 4 T 3 G 4 ) 2 (Fig. 3A) show the 2-NH 4 species as the dominant peak in all conditions, for both charge states, despite the fact that this G-quadruplex contains exclusively three ammonium ions in solution. Ammonium ion loss at some late stage of electrospray (when solvent is still present) can be ruled out, because based both on the melting temperatures and on the ammonium ion exchange rates, the solution-phase stability of bimolecular G-quadruplexes in solution ranks in the following way: (dG 4 T 3 G 4 ) 2 >(dG 4 T 4 G 4 ) 2 >(dG 3 T 4 G 4 ) 2 . In the ESI-MS spectra, ammonium ion preservation ranks in the reverse order.As will be demonstrated below in the ion mobility section, ammonium ion preservation depends mainly on ammonium ion kinetic stability in the gas phase, not in solution.

ESI-MS spectra suggest additional specific ammonium ion binding sites

In some spectra, additional ammonium ions compared to the number trapped between the Gquartets can also be detected. The question is whether these extra ammonium ions are located at specific binding sites or rather bound to the phosphodiester backbones of the strands.

Specific binding sites would have higher binding strength in solution than ammonium counter-ion binding to the phosphate groups. If this higher binding strength in solution translates into a higher kinetic stability in the gas phase, the mass spectra could show a bias in the ammonium ion distribution towards a particular stoichiometry higher than the number of cations trapped between G-quartets. Note that ammonium ions in these external binding sites are invisible to NMR, either because of the short residence times, or because their partial hydration is making them equivalent to bulk ammonium ions.

Thrombin binding aptamer (TBA)

The TBA intramolecular G-quadruplex (Fig. 3D)differs from the quadruplexes reported above. The peak corresponding to two ammonium ions bound is the base peak for charge state 3-. The existence of a second cation binding site for the TBA in solution is currentlycontroversial [START_REF] Hong | Mass spectrometric studies of alkali metal ion binding on thrombin-binding aptamer DNA[END_REF][START_REF] Marathias | Determinants of DNA quadruplex structural type: sequence and potassium binding[END_REF][START_REF] Marathias | Structures of the potassium-saturated, 2:1, and intermediate, 1:1, forms of a quadruplex DNA[END_REF][START_REF] Russo | Highresolution structures of two complexes between thrombin and thrombin-binding aptamer shed light on the role of cations in the aptamer inhibitory activity[END_REF]. Our mass spectrometry results clearly show the preservation of an additional specific ammonium cation by the TBA in addition to the one likely bound between the G-quartets,suggestingthat a fraction of the population in solution possessed this additional cation. Interestingly, molecular dynamics simulation of cation (Na + and K + ) movement in the TBA in solution showed that cations can be transiently captured between the loops before replacing the central cation [START_REF] Reshetnikov | Cation binding to 15-TBA quadruplex DNA is a multiple-pathway cation-dependent process[END_REF][START_REF] Reshetnikov | Structural dynamics of thrombin-binding DNA aptamer d(GGTGGTGTGGTTGG) quadruplex DNA studied by large-scale explicit solvent simulations[END_REF]. Similar results were found in preliminary simulations made on TBA in the presence of ammonium cations in solution [A.V. Golovin, personal communication]. However, the change in ammonium ion distribution according to the charge state prevents the quantification of this species by MS. The 2:1 complex is very labile in the gas phase (see below), even for the lowest charge state, so it is also possible that the 2:1 complex is partially dissociated in the gas phase even in the softest possible conditions.

Sequences containing diagonal loops

In dG 4 (T 4 G 4 ) 3 (Fig. 3C), one additional ammonium ion is detected for charge state 6-, but the lack of bias towards a specific stoichiometry prevents attributing it unambiguously to a specific binding site. In contrast,in (dG 3 T 4 G 4 ) 2 (Fig. 3B), the peak with a total of 3 ammonium ions preserved is clearly more abundant than the peak with 4 ammonium ions. Note that for sensitivity reasons the spectrum in Fig. 3Bwas recorded with a drying gas temperature of 150°C instead of 20°C. The biased distribution towards the 3-NH 4 peak is even more clearly observed on the Q-TOF and on the Synapt G1 instruments (Supporting Information S4).The mass spectra therefore hint at the presence of one additional specific binding site. Finally, the G-quadruplex [(dG 4 T 4 G 4 ) 2 ] 5-(Fig. 2) a peak with 5 ammonium ions is retained, hinting at the presence of two such additional specific binding sites. Interestingly, X-ray crystallography studies showed that, in addition to binding between G-quartets, K + cations can also bind to the loops of (dG 4 T 4 G 4 ) 2 [START_REF] Haider | Crystal structure of the potassium form of an oxytricha nova G-quadruplex[END_REF]. As this structure with two equivalent diagonal loops takes up two additional ammonium ions, whereas G-quadruplexes (dG 3 T 4 G 4 ) 2 and dG 4 (T 4 G 4 ) 3 have only one diagonal loop each, we propose that outer G-quartets are additional ammonium ion binding sites and that the bases of the diagonal loops participate in the cation binding.

Guanines in the loops (G-quadruplexes (dG 3 T 4 G 4 ) 2 and TBA) also favor additional ammonium ion binding.These results alsorecall the capture of one additional ammonium ion between the outer G-quartets and heterocyclic ligands like telomestatin [START_REF] Rosu | Cation involvement in telomestatin binding to G-quadruplex DNA[END_REF][START_REF] Linder | Telomestatin: formal total synthesis and cation-mediated interaction of its seco-derivatives with Gquadruplexes[END_REF]. ESI-MS is the only experimental method capable of probing these outer-quartet specific binding sites directly, and will be very useful to reveal the existence of such binding sites in new systems.

However, the results will require further validation by molecular dynamics simulations or by ion titration experiments.

All inner ammonium ions are necessary to preserve the G-quadruplex fold in the gas phase

The previous ion mobility spectrometry studies already showed that the preservation of inner ammonium ions was associated with a better preservation of the solution-phase structure in the gas-phase [START_REF] Gabelica | Stabilization and structure of telomeric and c-myc region intramolecular Gquadruplexes: The role of central cations and small planar ligands[END_REF]. However, the quadrupole resolution in these past studies prevented probing the effects of internal energy increase and ammonium loss individually. Here, we systematically investigated the influence of the bias voltage (injection voltage in the ion mobility cell), of the number of preserved ammonium ions, and of the charge state on the CCS. A typical driftscope spectrum is shown in Supporting Information S5. After CCS calibration, the resultsare 4D-data (mass-intensity-CCS-bias), presented for clarity in two 2Dplots. Figure 4 shows representative data, and Supporting Information S6gathers the full dataset.The lower plot shows the evolution of the CCS with the bias voltage for each mass (here, for each number of ammonium ions retained), and the upper plot shows the relative abundance of each peak, indicating the relative gas-phase kinetic stability of ammonium ions in G-quadruplexes.

The collision cross sections of the species retaining the exact number of specific ions known to bind between G-quartets change little with the bias voltage or with the charge state. The centroid CCS of the species retaining all specific ammoniums are listed in Table 2, along with the CCS resolution calculated from the full width at half-maximum of the Gaussian peak fittings. The CCS peak widthsare wider than the instrumental resolution, and vary with the nature of the oligonucleotide, the charge state, and the voltage, suggesting that the CCS peaks correspond to a conformational ensemble rather than to a single gas-phase structure. The data in Table 2 constitute a solid basis for future work comparing experimental and calculated CCS.The Table reveals that, based on the collision cross section alone, it is problematic to assign the fold, even if it is preserved from the solution. For example, (dG 4 T 3 G 4 ) 2 and

(dG 3 T 4 G 4 ) 2 have the same number of bases, completely different folds (Figs. 1B and1C), and yet the same CCS at low charge state when retaining their specific number of ammonium ions.

For each bimolecular G-quadruplex, the loss of a single inner ammonium ion significantly changes the collision cross section. In general, in the lowest charge state the ammonium ion loss induces a slight crunch of the structure, whereas in the highest charge states it induces a dramatic expansion of the structure. For the most abundant charge state (5-for all dimers presented here), the direction of the change varies with the sequence. Moreover, the absence of change in CCS does not necessarily mean the absence of change in gas-phase structure. For example, for [(dG 4 T 4 G 4 ) 2 ] 5-(Figure 4A), the first ammonium ion loss induces an expansion of the structure, then the two subsequent ammonium ion losses induce consecutive crunches of the structure. Incidentally, the 1-NH 4 CCS is equal to the 3-NH 4 CCS. Therefore, to ensure preserving the G-quadruplex structure from the solution to the gas phase, the species with all specific inner ammonium ions and at relatively low charge state must be selected (even when this species is particularly labile, such as the 3-NH 4 species for (dG 4 T 3 G 4 ) 2 , see Fig. 4B.

In the case of intramolecular G-quadruplexes (Supporting Information Figure S6-2), for the two lowest charge states (including the most abundant charge state), the collision cross section does virtually not change upon ammonium ion loss. Ammonium loss involves proton transfer of the ammonium ions to the DNA, and hence the repartition of the charges over the DNA structure at total constant charge changes upon ammonia loss. This apparently is not always accompanied by a change of collision cross section for the lowest charge states, presumably because other salt bridge interactions in the denatured state overcome the Coulombic repulsion and the denatured state remains compact.

Ion mobility spectrometry helps to assign the number of inner ammonium ions

On the contrary to inner ammoniums, additional ammonium ions are not essential to preserve the gas-phase structure (compare the CCS of the 3-NH 4 and 2-NH 4 species in (dG 4 T 3 G 4 ) 2 ,Figure 4B, where the three inner ammonium ions are essential,with (dG 4 T 3 G 4 ) 2 ,Figure 4C, where only two inner ammonium ions are essential).Additional (i.e., outer-G-quartet) ammonium ions cause little changes of CCS (see for example the 3-NH 4 species for (dG 3 T 4 G 4 ) 2 in Fig. 4C). At the highest charge state, the mean CCS and the peak width of the intact complex increase with the bias voltage, but in lower proportion than when ammonium ion loss occurs. This suggests that the solution structure is preserved in the gas phase when all inner ammonium ions are preserved. Moreover, the most significant change in CCS is observed for the highest charge state (compare Figure 4C and4D). IMS experiments on the high charge state may not be ideal to derive structure from the CCS, but give the best indication that a specific number of ammonium ions are involved in the formation of a specific structure like a G-quadruplex. The number of ammonium ions needed to keep the CCS of the high charge state ions close to the CCS of the lower charge state ionsis equal to the number of inner ammonium ions in the solution structure.

Conclusions

Assigning the number of specific ammonium binding sites in G-quadruplexes using electrospray mass spectrometry is difficult. First, inner ammonium ions (i.e., those residing between G-quartets) are relatively labile in the gas phase in the case of antiparallel Gquadruplexes. Second, additional specific binding sites (i.e., outside G-quartets) also exist in solution and can be preserved by ESI-MS, butthe difference in gas-phase lability between ammonium ions bound at these additional specific sites and ammonium ions non-specifically attached to phosphate groups is less substantial. To reach reliable conclusions on ammonium ion binding in solution based on ESI-MS data, we make the following recommendations:

(1) Instrument choice is crucial. A good system to test instrumental conditions is the (dG 4 T 4 G 4 ) 2 5-bimolecular G-quadruplex, for which soft conditions should show the 3-NH 4 peak (all inner ammonium ions preserved) as the base peak. The 5-NH 4 peak (with two additional ammonium ions presumably bound between the external Gquartets and the diagonal loops) should also be visible.

(2) The gas-phase lability should be tested on a range of relative internal energies, andonly clear biases in the ammonium ion distribution can be interpreted as an indication of specific ammonium ion binding. This helps assigning the number of binding sites in solution.With regard to determination of ammonium ion equilibrium binding constants, when some lability is evident atconditions close to the softest achievable, the ammonium ion distribution will likely not reflect the solution-phase distribution.

(3) Ion mobility spectrometry helps assigning the number of inner ammonium ions as the minimum number of ammonium ions needed to obtain a near-constant CCS at all charge states.Indeed, all inner ammonium ions are necessaryand sufficient to preserve the structure from the solution to the gas phase, for the most abundant charge state produced from solutions at physiological ionic strength (150 mM NH 4 OAc). a Average values and standard deviations obtained from three measurements on the Synapt G1 HDMS at the three lowest bias voltages.The prediction error (95% confidence) is 1.6% in all cases.

Tables

PeakFit 4 . 11 .

 411 The instrumental ion mobility mobility resolution in the concerned m/z range is 22.5, determined as  FWHM of the G-quadruplex [(dTG 4 T) 4 •(NH 4 ) 3 ] 5-. This parallel G-

FiguresFigure 1 :

 1 Figures

Figure 2 :

 2 Figure 2: Influence of instrument choice and of traveling waves on ammonium ion preservation in [(dG 4 T 4 G 4 ) 2 ] 5-. The number of preserved ammonium ions is written in red. (A)

Figure 3 :

 3 Figure 3: Ammonium ion distrubutions recordedusingsoft instrumental conditions on the

Table 1 .

 1 Predicted distribution of ammonium ions preserved between the G-quartets of each Gquadruplex structure in solution, based on NMR data[START_REF] Sket | NH4+)-N-15 ion movement inside d(G(4)T(4)G(4))(2) G-quadruplex is accelerated in the presence of smaller Na+ ions[END_REF][START_REF] Podbevsek | Stacking and not solely topology of T3 loops controls rigidity and ammonium ion movement within d(G4T3G4)2 G-quadruplex[END_REF]25,27].

	G-quadruplex	0-NH 4	1-NH 4	2-NH 4	3-NH 4
	(dG 4 T 4 G 4 ) 2	0%	0%	0%	100%
	(dG 4 T 3 G 4 ) 2	0%	0%	0%	100%
	(dG 3 T 4 G 4 ) 2	0%	0.5%	99.5%	-
	dG 4 (T 4 G 4 ) 3	0.2%	3.8%	29%	67%
	TBA	3%	97%	-	-

Table 2 .

 2 Collision cross sections and CCS peak resolution for the intact G-quadruplexes containing all inner ammonium ions.

	G-quadruplex	3-		4-		5-		6-	7-
		Ų a   FWHM	Ų a	 FWHM	Ų a	 FWHM	Ų a	 FWHM Ų a  FWHM
	(dG 4 T 4 G 4 ) 2 •(NH 4 ) 3			802 ± 3	17.0 801.9 ± 0.6	18.7 803.4 ± 0.4	14.9
	(dG 4 T 3 G 4 ) 2 •(NH 4 ) 3			740.2 ± 1.2	15.8 746.7 ± 0.7	12.2 753.2 ± 1.3	10.5
	(dG 3 T 4 G 4 ) 2 •(NH 4 ) 2			740 ± 3	13.6 747.3 ± 1.7	12.0	762 ± 3	10.0
	dG 4 (T 4 G 4 ) 3 •(NH 4 ) 3					896.6 ± 0.6	15.1 915.4 ± 1.2	12.9 940 ± 5	10.8
	TBA•NH 4	565.9 ± 1.0	11.8	583 ± 2	9.7 624.6 ± 1.7	7.5

Acknowledgements

This work was supported by the Fonds de la Recherche Scientifique-FNRS (research associate position and FRFC Grant 2.4528.11 to VG),the EU COST action MP0802, the Slovenian research agency [ARRS, P1-0242 and J1-4020], EU FP7 projects with acronyms EAST-NMR [228461] and Bio-NMR [261863],and the Cooperation Agreement between Wallonia-Brussels and the Republic of Slovenia.


F Feng

J Fatome

A Sysoliatin

Y Chembo

S Wabnitz

C Finot

Wavelength conversion and temporal compression of a pulse train using a dispersion oscillating fibre

We demonstrate the generation of a picosecond pulse train taking advantage of the cross gain occurring in a dispersion oscillating fibre. The resulting frequency-converted signal is detuned by more than 20 nm from the pump and can be temporally compressed by a factor 2 compared to the input sinusoidal pump wave.

Introduction:

In order to alleviate the bandwidth limitations of optoelectronic modulations or the complexity of mode-locked fibre lasers, the generation of high repetition pulse sources has strongly benefited in the past from various strategies relying on the use of the Kerr effect of silica to convert a sinusoidal signal into a train of wellseparated optical pulses. For example, multiple-four wave mixing in anomalous dispersion fibres or nonlinear reshaping in normally dispersive fibres followed by a linear compensating segment are two efficient ways to achieve such a transformation [START_REF] Pitois | Generation of 20-Ghz Picosecond Pulse Trains in the Normal and Anomalous Dispersion Regimes of Optical Fibers[END_REF]. A more recently demonstrated technique relies on the nonlinear reshaping of a sinusoidal beating into a train of Akhmediev breathers [START_REF] Fatome | High-Quality Optical Pulse Train Generator Based on Solitons on Finite Background[END_REF]. A very different approach takes advantage of the parametric gain experienced by a continuous seed under a sinusoidal pumping: the exponential and instantaneous gain leads to a very high level of amplification in the most intense areas of the sinusoidal profile of the pump whereas the signal remains quasi unamplified around its temporal minima. The efficiency of this approach has been demonstrated in a parametric amplifier [START_REF] Hansryd | Wavelength Tunable 40 Ghz Pulse Source Based on Fibre Optical Parametrc Amplifier[END_REF] based on a fibre with constant longitudinal anomalous dispersion.

In this contribution, we show that other parametric processes can also be suitable for frequency conversion and pulse train generation applications. More specifically, we demonstrate that it is possible to take advantage of newly developed fibres having a longitudinally oscillating dispersion profile. Given the periodic variation of their properties, such fibres exhibits new gain regions that we here exploit [START_REF] Smith | Modulational Instabilities in Fibers with Periodic Dispersion Management[END_REF][START_REF] Droques | Experimental Demonstration of Modulation Instability in an Optical Fiber with a Periodic Dispersion Landscape[END_REF].

Experimental set-up: The experimental setup that has been developed is illustrated in Fig. 1. The pump is made of a continuous wave at 1540 nm delivered by a distributed feedback laser (DFB) that is intensity modulated by a Niobate Lithium modulator driven by a sinusoidal clock operating at a frequency of 10 GHz. The sinusoidal pump waveform is first amplified and then sliced by a second optical modulator to decrease the repetition rate of the source down to 2.5 GHz. An optical bandpass filter (OBPF) is then used to prevent excessive build-up of amplified spontaneous emission (ASE) before the light being launched in a high power erbium-doped fibre amplifier with an output power of 28 dBm (corresponding to a peak power of 6 W). The pump is combined by a 90/10 coupler with a seed signal at 1563.2 nm delivered by a second external cavity laser that is amplified in order to reach the mW level. Next, pump and signal are launched in a 400-m long dispersion oscillating fibre (DOF) with the following parameters: spatial period of the sinusoidal dispersion profile  = 20 m, peak-to-peak amplitude of the dispersion change DAmp = 1.2 ps/km/nm, a normal average value of dispersion DAv = -0.4 ps/km/nm at the pump wavelength, and nonlinear coefficient of 10 W -1 /km -1 . More details on the index profile and drawing techniques of this fibre can be found in refs. [START_REF] Finot | Competing Four-Wave Mixing Processes in Dispersion Oscillating Telecom Fiber[END_REF][START_REF] Bogatyrev | A Single-Mode Fiber with Chromatic Dispersion Varying Along the Length[END_REF]. At the output of the fibre, an optical bandpass filter is used to isolate the generated idler (wavelength 1518 nm). The idler temporal and spectral profiles are monitored on a 70-GHz photodiode associated with a high speed-sampling oscilloscope (bandwidth 70 GHz) and on an optical spectral analyser, respectively. Spectral analysis: We have plotted in Fig. 2 the initial spectrum of the pump wave launched into the fibre (dotted grey line). From the spectrum recorded at the output of the fibre in absence of filtering and seed signal, we can clearly point out the growth of resonant gain sidebands from the spontaneous amplified emission (grey solid line) [START_REF] Droques | Dynamics of the Modulation Instability Spectrum in Optical Fibers with Oscillating Dispersion[END_REF][START_REF] Armaroli | Tunable Modulational Instability Sidebands Via Parametric Resonance in Periodically Tapered Optical Fibers[END_REF]. Those sidebands exhibit a gain in excess of 40 dB, and are detuned by more than 20 nm from the pump that lies in the normal dispersion regime of the DOF [START_REF] Finot | Competing Four-Wave Mixing Processes in Dispersion Oscillating Telecom Fiber[END_REF]. However, those sidebands are narrower than the ones typically observed in anomalous fibres, which may limit the tunability of the conversion efficiency as well as the spectral extent of the pulse that can be processed. From the output spectrum, we can also notice the generation of additional regularly spaced sidebands, originating from multiple four wave mixing between the pump and the resonant sidebands [START_REF] Finot | Competing Four-Wave Mixing Processes in Dispersion Oscillating Telecom Fiber[END_REF]. A continuous signal seed within the resonant gain bandwidth at 1563.2 nm undergoes both amplification as well as spectral broadening through parametric-gain and cross-phase modulation, respectively.

Fig. 2 Optical spectra of the pump wave (dotted dark grey line) compared with the spectra at the output of the DOF with and without seed (black and light grey solid line respectively). The gain sidebands that are linked to the resonant gain are designated by QPM whereas the ones linked to the multiple four wave mixing between the pump and the resonant sidebands are marked by MFWM.

Temporal analysis: The temporal profile of the pump pulse is plotted in Fig. 3a and is compared with the idler wave obtained after propagation in the DOF and optical bandpass filtering. Both saturated and unsaturated regimes are investigated and in both cases, a backgroundfree pulse train with significant temporal narrowing is observed (with temporal durations of 21 and 15 ps respectively, i.e. temporal compression factors of 1.7 and 2.4 compared to the initial duration of 37 ps). As we shall see, the regime of amplification, as well as the central wavelength of the signal, also influence the temporal waveform of the idler [START_REF] Vedadi | Experimental Investigation of Pulse Generation with One-Pump Fiber Optical Parametric Amplification[END_REF]. Indeed, the idler pulse intensity profile is close to a Gaussian shape (full grey circles) in the unsaturated amplification, whereas the idler pulse becomes parabolic-like in the saturated regime (full black diamonds). Let us also point out that the regime of operation crucially affects the stability of the converted pulse train, so that a trade-off between short duration and stability was experimentally found based on an empirical basis. Indeed, due to the exponential amplification experienced in the unsaturated regime, intensity noise of the pump converts into major fluctuations of the amplified waves [START_REF] Hammani | Extreme Statistics in Raman Fiber Amplifier : From Analytical Description to Experiments[END_REF]. On the contrary, saturation of the amplifier efficiently limits those detrimental shot-to-shot fluctuations as illustrated on Fig. 3b. Let us finally add that, due to the cross-phase modulation induced by the pump on the signal, the recorded pulses are not transform limited (the corresponding timebandwidth product is equal to 4). a b Fig. 3 a. Temporal intensity profiles of the pump (dashed black line) compared with the profile of the idler wave obtained (after OBPF) for the amplifier running in the unsaturated and saturated regimes (solid grey and black lines, respectively). Full grey circles and full black diamonds represent a Gaussian and parabolic fits of the temporal intensity profile respectively. b. Oscilloscope trace in persistent mode of the idler wave for amplifier running in the saturated regime.

Conclusion:

We have demonstrated in this contribution that the wavelength-conversion/generation of GHz trains of picosecond pulses through parametric gain is not restricted to the usual case of parametric amplification in a fibre with anomalous dispersion. Using a pump lying in the normal dispersion regime is also possible, thanks to a resonant quasi-phase matched process induced by the periodic sinusoidal modulation of the dispersion profile. When compared with other possible schemes such as phase-matching induced by the fourth-order dispersion coefficient, we expect that our proposed technique is more tolerant with respect to longitudinal stochastic fluctuations of the fibre properties. We also believe that improvements in the drawing process may enable in the future shorter spatial periods of the dispersion oscillation, so that larger wavelength shifts would become feasible.

Fig. 1

 1 Fig. 1 Experimental setup. CW : continuous wave laser ; IM : intensity modulator ; EDFA : erbium doped fibre amplifier (HP : High Power); PG : pattern generator ; OBPF : optical bandpass filter ; PC : polarization controller; DOF : dispersion oscillating fibre.

Acknowledgments: We acknowledge the financial support of the Conseil Regional de Bourgogne (Pari Photcom) and the funding of the Labex ACTION program (ANR-11-LABX-01-01). The experimental work has benefited from the PICASSO Platform of the University of Burgundy. This research was funded by Fondazione Cariplo, grant n.2011-0395. A.S. acknowledges support from a Landau Network-Cariplo Foundation fellowship and the Russian Foundation for Basic Research, project no. 14-02-00856. F. Feng, J. Fatome and C. Finot (Laboratoire Interdisciplinaire Carnot de Bourgogne, UMR 6303 Université de Bourgogne-CNRS, 9 av. A. Savary, 21078 Dijon Cedex, FRANCE) A. Sysoliatin (Fiber Optics Research Center, 11933 Moscow, Russia) Y.K. Chembo (FEMTO-ST/Optics department, UMR 6174 CNRS-University of Franche-Comté, 16 route de Gray, 25030 Besançon Cedex, France) S. Wabnitz (Dipartimento di Ingegneria dell'Informazione, Università degli Studi di Brescia, via Branze 38, 25123, Brescia, Italy) E-mail: christophe.finot@u-bourgogne.fr


Winn Voravuthikunchai

Bruno Crémilleux

Frédéric Jurie

Histograms of Pattern Sets for Image Classification and Object Recognition

This paper introduces a novel image representation capturing feature dependencies through the mining of meaningful combinations of visual features. This representation leads to a compact and discriminative encoding of images that can be used for image classification, object detection or object recognition. The method relies on (i) multiple random projections of the input space followed by local binarization of projected histograms encoded as sets of items, and (ii) the representation of images as Histograms of Pattern Sets (HoPS). The approach is validated on four publicly available datasets (Daimler Pedestrian, Oxford Flowers, KTH Texture and PASCAL VOC2007), allowing comparisons with many recent approaches. The proposed image representation reaches state-of-the-art performance on each one of these datasets.

Introduction

The representation of images, and more specifically the representation of the dependencies between visual features is a central question in computer vision. Interestingly, since a few years, pattern mining has been shown to be a promising avenue for discovering these dependencies e.g. [START_REF] Fernando | Effective use of frequent itemset mining for image classification[END_REF][START_REF] Gilbert | Scale invariant action recognition using compound features mined from dense spatio-temporal corners[END_REF][START_REF] Quack | Efficient mining of frequent and distinctive feature configurations[END_REF][START_REF] Yuan | Mining discriminative cooccurrence patterns for visual recognition[END_REF]. Pattern mining algorithms are used for extracting a subset of 'meaningful' groups of features (so-called patterns), such as groups of features which frequently appear together in the images of a given class. These algorithms use safe pruning strategies to extract patterns without having to evaluate all possible feature combinations, which is typically not tractable. In addition, since these algorithms use exhaustive search, the extracted patterns provide a fairly complete picture of the information content of the data.

Despite the use of pruning strategies, these mining algorithms are limited by the potential size of the search space which grows exponentially with the number of features. Most of the work in the literature addresses this problem by reducing the number of visual features and by down-scaling the problem to the mining of image subregions. However, large visual vocabularies are necessary to capture variations of object's appearance and obtaining good performance, while mining patterns in sub-regions cuts-off the possibility to capture dependencies between distant features. Another issue raised by the use of mining algorithms is the production of binary visual features. Indeed, mining algorithms can process items (binary elements) that are included or not in the image. Such a binary representation is different from common image representations such as the Local Binary Patterns (LBP), the Histograms of Oriented Gradients (HOG), or the Bag-of-Words (BoW), which are real-valued histograms. Transforming these histogrambased representations into sets of meaningful items -with minimum information loss -is still an open issue.

Once the patterns are discovered, the following question raised by the use of mining algorithms for computer vision tasks is how to use them. In the literature, patterns are often used as new features. Due to the number of patterns (usually very high i.e. up to several millions), encoding each pattern as a single image feature in the learning process is often not feasible. A post processing step for selecting a smaller subset of patterns is usually applied e.g. [START_REF] Fernando | Effective use of frequent itemset mining for image classification[END_REF]. However, finding the best subset is a nontrivial combinatorial problem for which greedy search is often the only feasible solution. Unfortunately, greedy search is not guaranteed to find a globally optimal solution, despite it's high computational cost. Another drawback of pattern selection is that some useful patterns can be inopportunely discarded.

This paper addresses the three previously mentioned issues (i.e. vocabulary size, binary visual items, and usage of mined patterns) by proposing a new framework for discovering sets of interesting groups of features from real-valued image representations (such as the LBP, HOG, BoW), and for efficiently constructing an distinctive image representation from the so-discovered patterns (Figure 1 gives an overview of the approach). It opens a new avenue for taking benefit of the integration of data mining techniques in computer vision applications.

In this context, our contribution is threefold. First, we propose a new method for transforming real-valued vectors (e.g. histogram-based image representations) into binary item transactions (set of binary visual elements), using random projections and adaptive thresholding. The proposed method addresses the two first mentioned problem regarding the dimensionality and the binarization loss. The patterns are mined from multiple sets of low-dimensional (projected) features and embed the relative order of initial real-valued representation (Section 3.1). Second, we introduce the concept of Histograms of Pattern Sets (HoPS); HoPS consist in finding interesting patterns (with the help of standard pattern mining algorithms), and using some relevant statistics of these patterns to represent images, hence condensing the information. Consequently, no pattern selection is required, which is an answer to the third issue (Section 3.2). Finally, we perform an extensive experimental validation on several different supervised image classification and object recognition/detection tasks. The proposed approach not only gives better performance than the baseline algorithms neglecting feature dependencies, but it also reaches state-of-the art performance on most of these tasks.

Related Work

Pattern mining allows the discovery of sets of features capturing local regularities and has been reported as being an efficient tool for discovering relevant dependencies between visual features (e.g. [START_REF] Fernando | Effective use of frequent itemset mining for image classification[END_REF][START_REF] Gilbert | Scale invariant action recognition using compound features mined from dense spatio-temporal corners[END_REF][START_REF] Nowozin | Weighted substructure mining for image analysis[END_REF][START_REF] Quack | Efficient mining of frequent and distinctive feature configurations[END_REF][START_REF] Sivic | Video data mining using configurations of viewpoint invariant regions[END_REF][START_REF] Wang | Instantly telling what happens in a video sequence using simple features[END_REF][START_REF] Yuan | Mining discriminative cooccurrence patterns for visual recognition[END_REF]). These methods differ in the way they transform images into sets of items which can be mined out.

Several works suggest extracting keypoints and representing local descriptors by visual words. The list of visual words contained in the image is then seen as a transaction [START_REF] Nowozin | Weighted substructure mining for image analysis[END_REF][START_REF] Quack | Efficient mining of frequent and distinctive feature configurations[END_REF][START_REF] Sivic | Video data mining using configurations of viewpoint invariant regions[END_REF]. However, such a coding is very sparse, losing potentially interesting information. Dense local fea-tures overcome this limitation, but in this case most of the visual words will appear at least once in the image, leading to transactions containing all possible items. Consequently, rather than encoding the whole image as a single transaction, [START_REF] Fernando | Effective use of frequent itemset mining for image classification[END_REF][START_REF] Wang | Instantly telling what happens in a video sequence using simple features[END_REF] divide the images into rectangular regions and produce one set of items per region. In addition to limiting the number of visual words per transactions, it allows the discovery of spatial relations between densely sampled quantized features. However, a drawback is that the combinations of features with high mutual separation distance cannot be discovered. Since the encoding has been reduced to local regions, a visual word can as, a consequence, appear multiple times in a single image region. Then, not representing its frequency would lead to an important binarization loss. To address this issue, [START_REF] Fernando | Effective use of frequent itemset mining for image classification[END_REF] proposed a method using visual word frequencies when building items. This method improves the performance but exponentially increases the dimensionality of the binary features, which is not desirable, and also limits the size of the visual vocabulary that can be used. Reducing the size of the vocabulary is not a good option since vocabulary size is positively correlated with good performance. Differently, [START_REF] Yao | Grouplet: A structured image representation for recognizing human and object interactions[END_REF][START_REF] Yuan | Mining discriminative cooccurrence patterns for visual recognition[END_REF] mine patterns from high-level semantic features for which smaller representational space are needed. However, such techniques can work only if the high-level features are correctly detected, which is an open question. In contrast, we show Section 3.1 how our binarization approach is able to preserve the information of the initial real-valued representation while providing a limited number of items.

The approaches using data mining for visual recognition also differ in the way they use mined patterns. Surprisingly, frequent patterns are often used [START_REF] Fernando | Effective use of frequent itemset mining for image classification[END_REF][START_REF] Quack | Efficient mining of frequent and distinctive feature configurations[END_REF] even if contrast measures e.g. emerging patterns [START_REF] Novak | Supervised descriptive rule discovery: A unifying survey of contrast set, emerging pattern and subgroup mining[END_REF] would allow -by construction and more efficiently -to produce discriminative patterns suitable for classification tasks. As the set of frequent patterns can be very large (e.g. several millions) and redundant, a post-processing step is usually applied to select a tractable subset of discriminant patterns. [START_REF] Fernando | Effective use of frequent itemset mining for image classification[END_REF] proposed an algorithm to select the frequent patterns that are discriminative, representative, and non-redundant. However, there is no efficient way to generate a set of patterns that can satisfy global constraints (e.g. cover all data while giving good prediction accuracy) [START_REF] Bringmann | The chosen few: On identifying valuable patterns[END_REF] and all of the mentioned methods require costly or ad-hoc post-processing stages for selecting the patterns. In contrast, the proposed histogram of pattern sets does capture the discriminative power of the whole set of patterns and provides an efficient image representation for supervised tasks.

Method

As mentioned in the introduction, the proposed method has two steps: (i) real-valued histograms are turned into lists of binary items, Section 3.1 (Fig. 1, green block), and (ii) image representations are computed from histograms of mined patterns, Section 3.2 (Fig. 1, red block). The discovering of patterns is done using standard mining algorithms.

In order to illustrate the presentation of the method, we use the bag-of-words (BoW) representation as a prototypical example i.e. an image I is represented as an histogram of visual words h = (p(w 0 |I), . . . , p(w d |I)), where L = {w 0 , . . . , w d } is a vocabulary of size d. Any histogrambased representation, such as those used in our experiments, falls into this formalism and can be used in the same way.

From real-valued vectors to binary items

Pattern mining algorithms cannot be used to process high-dimensional real-valued representations as (i) pattern mining algorithms handle only binary items, and (ii) although pattern mining algorithms are very efficient in extracting patterns from a large number of transactions (e.g. millions), they can only tackle a moderate number of items, typically up to a few hundreds, depending on the density of the data. This is due to the search space which grows exponentially with the number of items. As image representations usually have several thousand components, mining patterns from such high-dimensional image data is not only slow but also memory consuming.

Multiple projections of the original representation into small dimensional spaces is one of the key ideas for addressing this issue. The rational for doing this is that (i) following the Johnson-Lindenstrauss lemma, representing high-dimensional data by multiple projections leads to good approximations of the data e.g. [START_REF] Jégou | Aggregating local image descriptors into compact codes[END_REF] and (ii) mining is more efficient when the dimensionality is low. In practice, the projection is done by simply randomly selecting p visual words from the original BoW. This can be seen as projecting the original d-dimensional data to a p-dimensional subspace where the projection matrix is obtained by randomly choosing the p basis vectors from the standard basis (more complex projections have been investigated, without improving the performance). Let R denote the d × p projection matrix, such that h p = h × R, ∀h p ∈ H p . H p is denoted as the set of p-dimensional projected histograms. Once the histogram is projected, the bins whose values are among the top-K highest values are set to '1' while other bins are set to '0' (e.g. if the histograms are projected into a 10-d space and if k = 4, we will obtain 10-bit histogram signatures having 4 ones and 6 zeros). More formally, h bp j = 1 ⇐⇒ h p j ≥ τ where τ = h p rank k (h p ) , and rank k (h) returns the index of the histogram bin with the k th highest value (Figure 2). This process to obtain binary representation bears some similarity with Locality-Sensitive Hashing (LSH) [START_REF] Gionis | Similarity search in high dimensions via hashing[END_REF]. However, the main difference is that in LSH, a fixed threshold is used instead of top-K. The motivation in using top-K binarization instead of a fixed threshold is to reduce and control the size of the search space. Top-K binarization en- sures that all images will be represented by exactly K items. Moreover, we believe (as illustrated by [START_REF] Xie | Use bin-ratio information for category and scene classification[END_REF]) that the relative frequency of visual words is more important than their absolute frequency.

We repeat this two-step process several times. After a sufficient number of projections, the relative order of the feature frequencies is captured. To illustrate this, let us consider the toy example given Figure 3. The original BoW representation contains four different real-valued features namely p(A), p(B), p(C), and p(D). The first random process selects the visual words A, B, and C. When applying the top-K binarization with K = 2, the visual words A and C are kept (and considered as a transaction). This infers that both p(A) and p(C) have higher values than p(B). After the second random projection, the fact that p(C) is smaller than p(A) and p(D) can also be deduced. From these two iterations, we are able to conclude that (i) both p(A) and p(D) are higher than p(C), and (ii) p(C) is higher than p(B). In this example, it is not possible to determine which one of p(A) or p(D) is higher. However, this information can be discovered if we negate the features h p * = (1h p 0 , . . . , 1h p p ) and apply the same binarization1 . Section 4.1 gives experiments showing that multiple random projections can handle the instability which occurs with a single projection.

As an alternative to random projections, we evaluated the use of principal component analysis (PCA) to reduce the dimensionality of input histograms. However, we obtained much worse results, which can be explained by the fact that it produces a single (low-dimentional) representation per input vector and therefore loses a lot of information once thresholded. In contrast, the proposed method to transform real-valued vectors into multiple sets of binary transactions reduces the dimensionality as well as limits the loss caused by the binarization process.

Representing images by histograms of patterns

Each random projection generates a set of binary items so-called a transaction. At this stage, standard data mining algorithms can be used to discover interesting combinations of features in each projection-related transactions. Data Mining has defined several types of patterns, but Frequent Patterns (FPs) [START_REF] Agrawal | Mining association rules between sets of items in large databases[END_REF] and Jumping Emerging Patterns (JEPs) [START_REF] Dong | Efficient mining of emerging patterns: discovering trends and differences[END_REF] are among the most common ones. Given a specified minimum threshold F min , a pattern (i.e. a set of items) is frequent if it appears in no less than F min transactions. Finding the exhaustive set of patterns is a major issue. Fortunately, the collection of frequent patterns can be condensed by the set of frequent closed patterns [START_REF] Uno | An efficient algorithm for enumerating closed patterns in transaction databases[END_REF]. The intuition is that a closed pattern condenses a set of patterns whose frequency is computed from the same transactions. By definition, closed patterns are patterns to which it is impossible to add any item without decreasing its frequency. We can therefore derive frequent patterns from closed patterns, resulting in a lower complexity: mining closed patterns is on average polynomial in the number of items [START_REF] Lhote | Average number of frequent (closed) patterns in bernouilli and markovian databases[END_REF] whereas usual techniques are exponential in the worst case. While FP mining is designed for discovering patterns from single classes, JEP mining is based on the growth-rate a contrast measure [START_REF] Novak | Supervised descriptive rule discovery: A unifying survey of contrast set, emerging pattern and subgroup mining[END_REF] -and is relevant for two-class problems. More precisely, a JEP is defined as a pattern appearing in one and only one class. If the frequency of a JEP is no less than F min , it is called a frequent JEP. Closed patterns make the mining of JEP mining much easier. Indeed, closed patterns have optimal growth rates, as they concentrate those patterns having highest growth rate values [START_REF] Li | Mining statistically important equivalence classes and delta-discriminative emerging patterns[END_REF]. In the following, we take benefit from the good properties JEPS offer regarding the representation of classes.

One key idea of the paper is to compute statistics of patterns found for each random projection to build the new image representation. The complete representation is indeed obtained by aggregating histograms of the whole set of patterns coming from the different projections. For supervised tasks -which are those considered in this paper -JEPs are highly relevant as they are discriminative by construction. More precisely, for each random projection, a set of positive JEPs (found only in the positive images) and a set of negative JEPs (found only in the negative images) are ex- tracted. We therefore build a histogram with two bins, the first is the count of positive JEPs (those found in positive images) and the other is the count of negative JEPs. For P random projections, we hence obtain a (2 × P )-dimensional histogram image representation, so-called the HoPS representation. The HoPS representation is intended to be used with classifiers. The underlying idea is to condense the information given by the set of patterns, rather than using each individual pattern as an individual image feature. As mentioned in the introduction, the number of patterns is high and using each pattern as a feature would result in a too large representation.

Toy example

Figure 4 shows a toy example illustrating the encoding of HoPS using JEPs. There are 6 image histograms (4 training ones for discovering the JEPs, and 2 for testing). The dimensionality of the input space is d = 6 while the dimensionality of the projected space is p = 4. We set the number of random projection P to 1 in order to simplify the illustration (the other projections follow the same principle). This projection is such that the projected vectors are made of the 1st, 3rd, 5th and the 6th component of the original ones. In this example K = 3, meaning that the 3 visual words having the highest probabilities are kept in the transactions. After obtaining the transactions (also given in Figure 4), the JEPs with minimum frequency threshold F min = 1 are computed. In this example, positive JEPs are {A,C,F}, {C,E,F}, and {C,F} while {A,E,F} is the single negative JEP. Note that e.g. {C} is not generated by our method since {C} is not a closed pattern ({C} is covered by {C,F}.) Finally, the two test images are coded by counting the number of positive and negative JEPs. The final representation consists in these two values, i.e. (2, 0) for image 5 and (0, 1) for image 6.

Complexity analysis

Encoding new images is very fast: the histogram binarization procedure involves the search of the k-th highest values, which can be done in O(p × log(k)) using a partial sort algorithm. Counting the JEPs supported by the transactions can be done in O(N p ) where N p is the number of mined patterns. To give some insights about the run time, encoding 100,000 images with 500 JEPs (which is in average the number of JEPs in our experiments), on a single core of CPU, takes around 0.3 second for the binarization and around 1 sec. for counting JEPs. Regarding training, mining the JEPs takes about 1 sec. with the typical settings/datasets used in our experiments.

Experiments

These experiments validate our approach on several supervised classification tasks. These experiments show that HoPS are compact, perform well, and are very generic. HoPS are generic in the sense that they can be built on top of various histogram-based image representations. In our experiments, HOG, LTP and FLH are used, but other could be considered.

We validated HoPS in four recognition tasks: (a) texture recognition on the KTH-TIPS2a dataset [START_REF] Caputo | Class-specific material categorisation[END_REF], (b) pedestrian recognition on the Daimler Multi-Cue, Occluded Pedestrian Classification dataset [START_REF] Enzweiler | Multi-cue pedestrian classification with partial occlusion handling[END_REF], (c) image classification on the Oxford-Flowers 17 dataset [START_REF] Nilsback | Automated flower classification over a large number of classes[END_REF], and (d) object detection on the PASCAL VOC 2007 dataset [START_REF] Everingham | The pascal visual object classes challenge[END_REF]. The type of patterns used are positive/negative JEPs. We use the code of DPMdelta [START_REF] Li | Mining statistically important equivalence classes and delta-discriminative emerging patterns[END_REF] to extract them. We set the F min threshold to 1% of the number of positive images. For many categories, the number of positive images is about one hundred and 1% is the minimum frequency that can be set. For each task, HoPS is compared against the baseline which is the original first order representation i.e. without taking into account feature dependencies. The same classifier and the same protocol are used for HoPS and the baseline representation. Since all of the representations including HoPS are histograms, we L1-normalize and square-root the representations before training linear SVM classifiers.

Influence of the parameters

To get some insight on the proposed method, we present several experiments on a simplified dataset and show the influence of the parameters on the behaviour of the algorithm (especially the performance). This simple dataset is a subpart of the KTH-TIPS2a [START_REF] Caputo | Class-specific material categorisation[END_REF] dataset, in which the lettuce leaf category is considered as the positive class while the remaining categories are considered as the negative class. We observed that there results generalize to other categories. The training set contains 3,420 images with 324 positives. The category of test images are predicted taking HoPS as input, and the performance is measured by the Average Precision (AP). As low-level features, we use single scale circular sampling of uniform-LTP, as proposed by [START_REF] Tan | Enhanced local texture feature sets for face recognition under difficult lighting conditions[END_REF]. Consequently, the HoPS are computed from 118-d histograms of LTP.

To encode HoPS, there are three key parameters to be considered: (i) the number of projections (P ), (ii) the di-mensionality of the projection space (p) and (iii) the number of items (K) per transactions obtained by top-K binarization of the projected histograms.

Regarding the number of random projections (P ), Figure 5a shows the AP as a function of P for different values of K and p. The AP increases with P until it saturates. As described in Section 3.1, the loss from binarization can be reduced by applying multiple projections. It seems that after a certain number of projections, the information contained in the original representation is well covered, explaining why the performance stops increasing. P depends on the dimensionality of the original feature d. In the toy example, in Figure 3, there are only 4 features, and only 2 random selections are sufficient to cover the relative order of the features. Clearly, when the original feature has higher dimensions, more random processes are required to capture the relative order of the features.

The influence of the binarization threshold (K) is represented Figure 5(b), which shows the performance according to the number of items (K) and the dimensionality of the projection space (p). K has been set from 2 to 18 while p varies from 10% to 100% of the size of the input dimensionality (in this experiment d = 118). We observed that K and p are correlated. The optimal score is reached when K is set to about 20% of p.

Finally, the impact of the size of the projection space p is illustrated Figure 5(b). p has to be chosen accordingly to the dimension of the input space d. Let's refer once again to the toy example in Figure 3 to explain this. In the toy example, if instead of 3, p was set to 4 which is equal to d, there will be only one possible transaction per image. After the top-K binarization, only the information that p(A) and p(D) are higher than p(C) and p(B) would be encoded. The relative order between p(A) and p(D), and the relative order between p(C) and p(B) could not be discovered. For this reason p should not be too high. In addition, as discussed earlier that p and K are related to each other, setting p to a high value leads to a high value of K. Recall that the mining complexity increases with K, although different values of p can result in similar performance, a low value of p is preferred. However, if p is too small, transactions will not have enough items and finding useful combinations will not be possible. This explains behavior observed in Figure 5(b).

In the forthcoming experiments (next sections), the parameters are cross-validated using a validation set.

Non-linear SVM and combination of first and higher order features.

As the proposed representation encodes some nonlinearities of the features, it is interesting to compare it against a non-linear classifier applied to the features taken as independent (i.e. the original histogram). In this experiment, we compared the performance of a linear SVM using our HoPS with a RBF-χ 2 SVM (known to perform well on histograms) using histograms of the original features. The parameters of the RBF-χ 2 kernel were set by cross validation. We computed the Average Precision (AP) on the 11 classes of the KTH-TIPS2a dataset and report in Table 1 the mean Average Precision (mAP). It is worth pointing out that the HoPS used with a linear classifier outperformed the first order features with the non-linear SVM. As combining, by a simple concatenation, first-order features (histograms of features) and HoPS gave a slightly better performance than HoPS alone, this combination has been done in all classification experiments.

Image classification

Our primary motivation for doing these experiments was to provide comparison with the approach of [START_REF] Fernando | Effective use of frequent itemset mining for image classification[END_REF], the most recent pattern mining based approach on image classification. The interesting point is that the authors made the image features (FLH) for the Oxford-Flowers 17 database publicly available 2 , allowing us to give some meaningful comparisons (as our patterns are made from strictly the same low-level image features as theirs).

The Oxford-Flowers 17 database 3 contains 17 flower categories with 80 images per category. To compare results, we followed the same protocol as [START_REF] Fernando | Effective use of frequent itemset mining for image classification[END_REF], i.e. 20-fold cross validation, and reported the mean classification accuracy (mA). Results are given in Table 2. Note that we did not give comparisons with the features of [START_REF] Fernando | Effective use of frequent itemset mining for image classification[END_REF] obtained by combining shape (FLH S) and color (FLH C), as the authors has only publicized FLH S features. With a mA of 93.8 ± 1.4, our 2 http://homes.esat.kuleuven.be/˜bfernand/eccv_flh 3 http://www.robots.ox.ac.uk/˜vgg/data/flowers method mA(%) Nilsback [START_REF] Nilsback | Automated flower classification over a large number of classes[END_REF] 88.3 ± 0.3 CA [16] 89.0 L1BRD [START_REF] Xie | Use bin-ratio information for category and scene classification[END_REF] 89.0 ± 0.6 FLH S [START_REF] Fernando | Effective use of frequent itemset mining for image classification[END_REF] (baseline) 92.0 ± 1.5 HoPS (ours)

93.8 ± 1.4

Table 2: Comparison with state-of-the-art results on the Oxford Flower 17 dataset. Method mA(%) Chen et al. [START_REF] Chen | WLD: A Robust Local Image Descriptor[END_REF] 64.7 Caputo et al. [START_REF] Caputo | Class-specific material categorisation[END_REF] 71.0 LHS [START_REF] Sharma | Local higher-order statistics (lhs) for texture categorization and facial analysis[END_REF] 73.0 ± 4.7 Color+MLBP [START_REF] Li | Recognizing materials from virtual examples[END_REF] 73.1 ± 4.6 histogram of LTP (baseline) 69.9 ± 3.0 HoPS (ours) 75.0±3.3

Table 3: mean accuracy(mA) on the KTH-TIPS2a dataset.

approach outperformed the performance of all the recent approaches we are aware of, including [START_REF] Fernando | Effective use of frequent itemset mining for image classification[END_REF].

Texture recognition

The experiments on texture recognition have been done on the KTH-TIPS2a [START_REF] Caputo | Class-specific material categorisation[END_REF] dataset, which is a dataset including images of 11 different materials (e.g. wool, linen, cork). For each material there are 4 image samples in which the samples were photographed at 9 scales, 3 poses and 4 different illumination conditions. The evaluation was done by following the protocol proposed in [START_REF] Caputo | Class-specific material categorisation[END_REF], which consists in reporting the mean Accuracy (mA) over the 4 runs (multiclass classification). During each run, all images of one sample were taken for testing while the remaining images of the 3 samples were used for training. As in Section 4.1, the features used for the experiments were 118-d histograms of uniform-LTP features [START_REF] Tan | Enhanced local texture feature sets for face recognition under difficult lighting conditions[END_REF]. As shown in Table 3, our method improves the performance the baseline more than 5%, validating the relevance of modeling the dependency between features. In addition, our method significantly outperformed other approaches4 .

Object detection

The experiments on object detection are achieved on the PASCAL VOC 2007 dataset, consisting in 9,963 images of 20 different object classes with 5,011 training images and 4,952 testing images. The task is to predict bounding boxes of the objects of interest if they are present in the images. It is the most popular dataset for object detec-tion and several competitive methods have been proposed for this dataset. Note that it is very difficult to improve results on this dataset. The top recently reported results are only slightly different.

We built on the well known part-based detector [START_REF] Felzenszwalb | Object detection with discriminatively trained partbased models[END_REF] version 5 (the latest released). As our goal is to validate the proposed image representation (and not to propose a new detector), we used the detection framework of [START_REF] Felzenszwalb | Object detection with discriminatively trained partbased models[END_REF] as it is but replaced the original image features (HOG) by ours in the scoring function. Following several works showing that combining texture and shape together gives better results (e.g. [START_REF] Hussain | Feature sets and dimensionality reduction for visual object detection[END_REF][START_REF] Zhang | Boosted local structured hog-lbp for object localization[END_REF]), we combined LTP and HOG features. In practice, the representation was obtained as follows. We first rescaled the bounding boxes of training object (roots and parts obtained by using the standard pre-trained detector) to the size of 128 × 128 pixels. Uniform LTP features were then extracted from a 6 × 6 non-overlapping grid, giving a total dimension of 4,248.

With the combination of (HOG+LTP), we obtained a gain of 1.0% mAP over the original detector. Then, the distribution of HOGs and LTPs are used as the input of our algorithm for computing the HoPS. As shown in Table 4, the gain of our full system is of 1.7% mAP over the original detector. We believe than the improvement is less on this dataset as JEP suffers from the very high imbalance of the positive/negative samples in this task (i.e. few hundreds positives vs hundred thousand negatives). Other types of patterns which can handle this issue have to be investigated. Since our method is independent of the type of patterns used, JEPs can easily be replaced by other types of patterns. Nevertheless, JEPs improve the baseline. Most of all, we achieved state-of-the-art result on this extremely competitive dataset.

Pedestrian recognition

The Daimler pedestrian classification dataset [START_REF] Enzweiler | Multi-cue pedestrian classification with partial occlusion handling[END_REF] consists of manually labeled pedestrian and non-pedestrian bounding boxes in images captured from a vehicle. The images have a resolution of 48 x 96 pixels with a 12-pixel border around the pedestrians. The dataset is split into three subsets (i) 52,112 non-occluded pedestrian samples for training (ii) 25,608 non-occluded pedestrians for testing and (iii) 11,160 partially occluded pedestrian samples, also for testing.

For our baseline, we extracted Histograms of Oriented Gradients (HOG) descriptors (HOG) from intensity grayscale images, using the same setting as in [START_REF] Enzweiler | Multi-cue pedestrian classification with partial occlusion handling[END_REF], which is 12 orientation bins and 6x6 pixel cells, accumulated to overlapping 12 × 12 pixel blocks with a spatial shift of 6 pixels. As shown in Figure 6 our baseline is already better than the best result of [START_REF] Enzweiler | Multi-cue pedestrian classification with partial occlusion handling[END_REF] which combined intensity, stereo, and optical flow, probably due to the square-root normalization. The proposed HoPS improves significantly over the base- line, with a reduction of about 30% of the false positive rate. HoPS outperforms other state-of-the-art approaches such as [START_REF] Wang | An hog-lbp human detector with partial occlusion handling[END_REF] as well.

Conclusions

This paper proposes a new method for discovering dependencies between image features, and encode them through Histograms of Pattern Sets (HoPS). The key of the proposed approach lies in (i) multiple random selections and top-K binarization -making pattern mining tractable while minimizing the information loss caused by the binarization -allowing to represent images by compact sets of meaningful transactions, and (ii) the introduction of Histograms of Pattern Sets, shown to be a very efficient and compact way to represent images. The proposed approach is generic and can be built on top of several image features. The proposed approach is validated on four different datasets, achieving state-of-the-art performance in the context of image classification and object detection.

Figure 1 :

 1 Figure 1: Overview of the approach: image histograms are tranformed into lists of binary items by projecting them into low-dimensional spaces (e.g. R 1 , ..., R p ) and by top-K binarizing their projections (Section 3.1). Patterns are then mined from each set of training transactions. Images are finally encoded by counting the number of patterns found in each projection. The counts are concatenated to obtain the HoPS representation (Section 3.2).

Figure 2 :

 2 Figure 2: Top-K binarization. Numbers inside bins are ranking orders. Trans. {1,2,6,9} is produced in this case.

Figure 3 :

 3 Figure 3: Toy example showing that after two random projections followed by top-K (K = 2) binarizations, relative relations between the BoW features are preserved and implicitely encoded within the representaion.

Figure 4 :

 4 Figure 4: Toy example showing how patterns are obtained.

Figure 5 :

 5 Figure 5: Influence of the parameters on the behavior of the algorithm. Kernel 1st order HoPS 1st + HoPS Linear 68.8 74.1 75.0 RBF-χ 2 71.2 73.7 74.0

Figure 6 :

 6 Figure 6: Pedestrian recognition on the non-occluded testset of Daimler pedestrian dataset.

Table 1 :

 1 Comparing linear / non-linear classifiers (mAP).

Table 4 :

 4 23.3 26.2 40.9 9.8 9.4 21.4 39.3 43.2 24.0 12.8 14.0 9.8 16.2 33.5 37.5 22.1 12.0 17.5 14.7 33.4 28.9 UCI [6] 27.1 28.8 56.2 3.2 14.2 29.4 38.7 48.7 12.4 16.0 17.7 24.0 11.7 45.0 39.4 35.5 15.2 16.1 20.1 34.2 35.4 LEO [35] 29.4 55.8 9.4 14.3 28.6 44.0 51.3 21.3 20.0 19.3 25.2 12.5 50.4 38.4 36.6 15.1 19.7 25.1 36.8 39.3 29.6 Oxford-MKL [28] 32.1 37.6 47.8 15.3 15.3 21.9 50.7 50.6 30.0 17.3 33.0 22.5 21.5 51.2 45.5 23.3 12.4 23.9 28.5 45.3 48.5 LS [34] 34.3 36.7 59.8 11.8 17.5 26.3 49.8 58.2 24.0 22.9 27.0 24.3 15.2 58.2 49.2 44.6 13.5 21.4 34.9 47.5 42.3 CA [2] 34.8 34.5 61.1 11.5 19.0 22.2 46.5 58.9 24.7 21.7 25.1 27.1 13.0 59.7 51.6 44.0 19.2 24.4 33.1 48.4 49.7 DPM rel.5 [10] 33.7 33.2 60.3 10.2 16.1 27.3 54.3 58.2 23.0 20.0 24.1 26.7 12.7 58.1 48.2 43.2 12.0 21.1 36.1 46.0 43.5 LTP+HOG (baseline) 34.7 36.2 60.7 10.8 18.6 27.4 53.7 59.2 24.2 20.0 25.8 26.9 14.0 59.3 49.7 43.1 12.1 22.4 38.5 48.4 43.6 HoPS (ours) 35.4 37.0 60.7 11.2 18.6 27.8 54.5 59.1 26.9 20.5 25.8 29.0 15.3 59.9 49.8 43.0 13.4 23.2 38.4 48.8 45.1 Comparison with state-of-the-art approaches on the PASCAL VOC 2007 dataset.

	mAP	plane	bike	bird	boat	bottle	bus	car	cat	chair	cow	table	dog	horse	mbike	person	plant	sheep	sofa	train	tv
	Best 2007 [9]

For the experiments on image classification and object recognition/detection, an image transaction is the concatenation of two sets, the non-negate and the negate top-K visual words.

We did not report the results of[START_REF] Caputo | Class-specific material categorisation[END_REF] using multi scale features and complex decision trees (with non-linear classifiers at every node), as our point is to demonstrate the strength of our features for a given classifier.