Amandine Fessard

Emmanuel Bourdon

Bertrand Payet

Fabienne Remize
email: fabienne.remize@univ-reunion.fr

Identification, stress tolerance and antioxidant activity of lactic acid bacteria isolated from tropically-grown fruits and leaves

Keywords: diversity, Weissella spp., Leuconostoc spp., antioxidant, stress adaptation

INTRODUCTION

Lactic acid bacteria (LAB) cover many different species, with very diverse physiological traits and ecology. They can be used as starters, probiotics, for ingredient biosynthesis or for bio-preservation.

Lactic acid fermentation of fruits and vegetables has regained attention over the last decade due to the multiple health advantages related to the consumption of fruits and vegetables compared to animal products and to the fast growing demand of healthy foods by increasingly conscious consumers. When applied to table olives, cabbage for sauerkraut or kimchi production or small fruits for pickles, this simple and valuable biotechnology results in a safety increase, in prolonged shelf-life and in changes of nutritional and sensorial properties [START_REF] Bourdichon | Food fermentations: microorganisms with technological beneficial use[END_REF][START_REF] Hugenholtz | Traditional biotechnology for new foods and beverages[END_REF][START_REF] Juodeikiene | Fermentation processes using lactic acid bacteria producing bacteriocins for preservation and improving functional properties of food products[END_REF][START_REF] Rodriguez | Food phenolics and lactic acid bacteria[END_REF]. In particular, the effects of lactic acid fermentation on antioxidant activity of fruits and vegetables were investigated [START_REF] Di Cagno | Effect of lactic acid fermentation on antioxidant, texture, color and sensory properties of red and green smoothies[END_REF], 2009;[START_REF] Filannino | Exploitation of the health-promoting and sensory properties of organic pomegranate (Punica granatum L.) juice through lactic acid fermentation[END_REF][START_REF] Noumo | Effect of pure culture fermentation on biochemical composition of Moringa oleifera lam leaves powders[END_REF][START_REF] Othman | Antioxidant phenolic compounds loss during the fermentation of Chétoui olives[END_REF][START_REF] Park | Effect of antioxidant activity in kimchi during a short-term and over-ripening fermentation period[END_REF][START_REF] Sun | Antioxidant activity of lactic-fermented Chinese cabbage[END_REF][START_REF] Wu | Antioxidant properties of Lactobacillus-fermented and nonfermented Graptopetalum paraguayense E. Walther at different stages of maturity[END_REF].

Depending on the studies, a more or less marked decrease or increase in antioxidant activity and changes in phenolic compounds have been reported. The differential effects of lactic acid fermentation observed between studies can be explained by the diversity of substrates, fermentation protocols and analytical methods used in these studies, but also by the diversity of LAB.

Edible fruits and leaves in warm-climate countries are often traditionally preserved as lactic fermented foods [START_REF] Franz | African Fermented Foods and Probiotics[END_REF][START_REF] Lan | Tropical traditional fermented food, a field full of promise. Examples from the Tropical Bioresources and Biotechnology programme and other related French-Vietnamese programmes on fermented food[END_REF][START_REF] Ng | Lactic acid bacterial fermentation on the production of functional antioxidant herbal Anoectochilus formosanus Hayata[END_REF][START_REF] Nguyen | A description of the lactic acid bacteria microbiota associated with the production of traditional fermented vegetables in Vietnam[END_REF]. In these cases, home-made products result from spontaneous fermentation or back-slopping [START_REF] Lan | Tropical traditional fermented food, a field full of promise. Examples from the Tropical Bioresources and Biotechnology programme and other related French-Vietnamese programmes on fermented food[END_REF][START_REF] Liu | Lactic acid bacteria in traditional fermented Chinese foods[END_REF][START_REF] Oguntoyinbo | In vitro fermentation studies for selection and evaluation of Bacillus strains as starter cultures for the production of okpehe, a traditional African fermented condiment[END_REF]) and fermentative bacteria originate from fruit phyllosphere and kitchen equipment. Spontaneous fermentation results from a competition between microorganisms where the most adapted ones will prevail. Hence, food fermentation processes are associated with several stresses, depending on the growth medium composition and other environmental conditions [START_REF] Giraffa | Studying the dynamics of microbial populations during food fermentation[END_REF][START_REF] Serrazanetti | Dynamic stresses of lactic acid bacteria associated to fermentation processes[END_REF]. For these reasons, autochthonous bacteria, well-adapted to their ecological niche, are recognized as the most efficient to perform fermentation.

In this study, we first aimed to assess the biotechnological diversity of LAB isolates from the surface of papaya, tomato or sliced cabbage grown under tropical warm-climate. A second objective was to select LAB for their future use as starter for healthy fermented fruit or vegetable juices. The Victoria cultivar of pineapple, produced in South West areas of Indian Ocean, recognized for its sensorial properties, was chosen as fermentation substrate. As bacteria ability to resist to acid juice and to maintain or increase antioxidant activity level is critical for fruit or vegetable fermentation, relevant phenotypic traits as growth yield, acidification rate, stress tolerance, antioxidant activity and exopolysaccharide formation were determined.

MATERIALS AND METHODS

Biological materials

LAB were isolated from tomatoes (Lycopersicon esculantum), sliced white cabbage (Brassica oleacera var. capitata) and papaya (Carica papaya) grown in Reunion Island and isolates were stored at -80°C. These food materials were obtained from local markets and stored for 24 h at 4°C in sterile bags before analysis. Sliced cabbage was directly used, whereas tomato and papaya were cut: a 1 cm-thick slice in the median part of the fruit was cut with a sterile scalpel and 25 g were sampled from the center of the slice to the external arc of circle. For isolation, 25 g sample was mixed with 25 g buffered peptone water in a stomacher for 1 min, and then serial decimal dilutions in the same buffer were spread on selective agar. All isolates share the ability to grow on MRS agar with cycloheximide and are catalase negative. Lactobacillus plantarum DSM2601 was used as reference strains for all experiments.

A single batch of commercial pasteurized pineapple juice (Pur Jus Ananas Victoria de la Réunion, ALBIUS) was used for all experiments.

Culture conditions

Isolates and DSM2601 were grown on MRS agar at 37°C for 72 h.

For isolate reactivation, one or two colonies or a loop of -80°C stock were suspended in 9 mL of BHI (Brain Heart Infusion) and incubated at 37°C for 48 h. Afterwards cultures were homogenized by vortex and 0.2 mL of the medium was used to inoculate 9 mL of BHI. This pre-culture was incubated at 37°C for 72 h. After 72 h, another tube of BHI broth was inoculated from this pre-culture and incubated at 37°C for 24 h. In BHI, cell population was estimated by measuring absorbance at 660 nm wavelength.

An adequate volume of juice was poured in autoclaved containers. The inoculation volume corresponded to an initial OD at 660 nm of 0.05. For short-term cultures, a volume of 40 mL of inoculated juice was incubated in 250 mL Erlenmeyer flasks at 25°C in a shaking incubator at 150 rpm for 48 h. Pasteurized juice was used as control. For each isolate and for both controls, the experiment was performed three times from independent pre-cultures.

Identification

DNA extraction was performed using Instagen protocol (Instagen Matrix, Biorad). The supernatant containing DNA was stored at -20°C.

Two primers (Eurogentec), RD1m 5'-GGM-TAC-CTT-ACG-AYT-TC-3' and FD1m 5'-AGA-GTT-TGA-TCH-TGG-CTC-AG-3', were used for DNA amplification. The reaction mixture contained buffer 1x, dNTP 2 mM, each primer 0.3 µM, MgCl 2 2.5 mM, and Taq polymerase 0.02 U.µL -1 (Diamond, Eurogentec).

The PCR reaction was performed in a 45 µL-volume with 10 µL of DNA solution. The PCR program comprised 35 cycles of denaturation for 40 s at 94°C, annealing for 40 s at 55°C and elongation for 1 min at 72°C. The cycles were preceded by a denaturation step at 94°C for 3 min and followed by an elongation step at 72°C for 10 min. PCR was performed with a Bio-Rad S100 Thermal Cycler. PCR products were separated by electrophoresis (60 min at 100 V) on 0.8% agarose gel in TAE 0.5x. DNA was detected with a GelDoc UV-illuminator system (Bio-Rad) after staining with ethidium bromide.

The 1 kb DNA ladder (Invitrogen) was used.

PCR product purification was performed with GenElute PCR Clean-up Kit (Sigma-Aldrich). PCR product was sequenced by Sanger method with FD1m primer (Eurofins). The obtained sequence was compared to Ribosomal Database Project [START_REF] Cole | Ribosomal Database Project: data and tools for high throughput rRNA analysis[END_REF]) and NCBI Nucleotide with BLASTN program. Alignments were performed with CLUSTAL OMEGA program (EMBL) [START_REF] Sievers | Fast, scalable generation of high-quality protein multiple sequence alignments using Clustal Omega[END_REF] and trees were built up with JalView [START_REF] Waterhouse | Jalview Version 2--a multiple sequence alignment editor and analysis workbench[END_REF].

A rep-PCR method based on (GTG) 5 primer was used to differentiate species. Reference strains DSM2601 (Lb. plantarum), DSM 20174 (Lb. plantarum Type strain), DSM 20188 (Leuconostoc citreum), DSM 5625 (Leuconostoc pseudomesenteroides), DSM 20193 (Leuc. pseudomesenteroides Type strain), DSM 15830 (Weissella koreensis Type strain), DSM 20196 (Weissella confusa Type strain), DSM 5625 (Weissella cibaria), DSM 15878 (W. cibaria Type strain) were used as control.

PCR was performed according to [START_REF] Versalovic | Genomic fingerprinting of bacteria using repetitive sequence-based polymerase chain reaction[END_REF] with some modifications. The PCR reaction was performed in 50µL containing 10µL of DNA solution. The reaction mixture contains 1X buffer, dNTP 2mM, (GTG) 5 primer 5'-GTG-GTG-GTG-GTG-GTG-3' 2µM (Eurogentec), MgCl 2 4mM and Taq polymerase 0.0375 U.µL -1 (5 PRIME). The (GTG) 5 PCR program comprised 30 cycles of denaturation for 1 min at 94°C, annealing for 1 min at 40°C and elongation for 3 min at 72°C. The cycles were preceded by a denaturation step at 94°C for 5 min and followed by an elongation step at 72°C for 10 min. PCR was performed with a Bio-Rad S100 Thermal Cycler. PCR products were separated by electrophoresis in a 0.8% agarose gel (20 X 20) for 6 hours at 80 V in 1x TAE. DNA was detected as previously described by comparison with 1 kb and 100 bp DNA ladders (Nippon Genetics).

Electrophoretic profiles were analyzed with Phoretix 1D Pro software (Totallab, UK). Nearest Neighbor algorithm and Pearson coefficient correlation were used to build the dendrogram.

Exopolysaccharide (EPS) production

Screening for EPS producing phenotype was carried out from colony aspect after growth at 30°C during 72 h on MRS medium supplemented with 40 g.L -1 of sucrose. The phenotype was rated according to mucoid appearance with attributes: (-) non mucoid/non EPS-producing; (+) EPSproducing; (++) high EPS producing and (+++) very high EPS producing. The colony aspect of EPS producing isolates was described as liquid or creamy.

Acidification kinetics

Bacterial isolates were reactivated for 48 h at 37°C in BHI broth. They were inoculated in 150 mL of BHI broth. Volume of inoculation was calculated corresponding to an initial OD at 660 nm of 0.05.

Cultures were incubated at 25°C in a water bath under agitation at 100 rpm with a magnetic stirrer. A pH probe connected to an automated acquisition system (Consor multi-parameter analyser C3060) was plunged in each culture. The medium pH values were acquired for 72 h with a time interval of 5 min with CINAC Software. Acidification curve was obtained by plotting pH as a function of time. Each culture was performed in duplicate. Lag time λ was the time corresponding to an initial pH variation below 0.1. Minimal pH pH min was the final constant pH value. Maximum acidification rate V M , time to reach the maximum acidification rate without the lag phase t M and pH at maximal acidification rate pH M were determined from dpH/dt = f(t) curves obtained with Regressi Software.

Adaptation

Bacterial isolates were grown for 48 h at 37°C in BHI broth pH 6.8 and 0.2 mL fraction of this bacterial suspension was inoculated into 9-mL assay broths. The control medium used was BHI broth pH 6.8.

For acid stress adaptation, BHI broth acidified to pH 4.5 with HCl 2M was used. For osmotic stress adaptation, BHI broth containing 5% NaCl was used. For oxidative stress, BHI broth containing 0.025 % or 0.05 % H 2 O 2 or 0.07 % H 2 O 2 was used. OD at 660 nm was measured just after inoculation (OD 0 ) and after incubation at 37°C for 48 h (OD 48 ). Results were expressed as Log (OD 48 /OD 0 ). All adaptation assays were performed in triplicate for each isolate.

Analysis of pineapple juice

All chemicals were purchased from Sigma Aldrich. Reducing sugar content was determined according to Miller method [START_REF] Miller | Use of dinitrosalicylic acid reagent for determination of reducing sugar[END_REF]. Cell counts were performed after inoculation and after 48 h of incubation by MRS platting. Seven different assays were used to evaluate the antioxidant activity.

Each test was performed in independent triplicates for each sample and control.

Oxygen Radical Absorbance Capacity (ORAC) analysis

Oxygen Radical Absorbance Capacity (ORAC) analysis was used to determine antioxidant capacity of 5000-fold diluted, fermented or non-fermented, pineapple juices. The antioxidant activity of the

Erythrocytes hemolysis

In this assay, antioxidant activity of a sample corresponds to its capacity to inhibit erythrocyte oxidation by radicals generated from AAPH. Erythrocytes were separated from the plasma by centrifugation at 1000 x g for 5 min. The supernatant was removed and the same volume of 0.15 M NaCl solution was added. This washing step was repeated three times. Afterwards, erythrocyte solution was reconstituted by adding a volume of NaCl solution equivalent to initial plasma volume.

In a 96-well plate, 100 µL of 50-fold diluted erythrocytes were mixed with 10,000-fold diluted samples in 0.15 M NaCl. Then, 40 µL of 0.5 M AAPH solution was added in each well. The microplate was incubated at 37°C and hemolysis was followed by the decrease of absorbance at 450 nm (FLUOSTAR -BMG France). Omega-5 software was used to acquire absorbance values. Results are expressed in half time of hemolysis (HT50), determined from GraphPad Prism 2.01 with a Boltzman sigmoidal nonlinear regression. The equation was:

Y = Absi + ௦ି௦ ଵା ௫ ೇఱబషೣ ೞ
where Y is the absorbance at 450 nm, Absi the initial absorbance at 450 nm, Absf the final absorbance at 450 nm, and V-50 the half time hemolysis, expressed in min, and slope is the steepness of the curve.

OD 280nm measurement

Pineapple juice fermented or not was diluted 10-fold in ultrapure water, before the measurement of OD at 280 nm. Gallic acid was used as standard. Results are expressed as g.L -1 gallic acid equivalent (GAE).

Determination of total phenolic content

The Folin-Ciocalteau method with gallic acid (GA) as standard was used and samples were 100-fold diluted. In a 96-well plate, 15 µL of Folin reagent was mixed with 30 µL of each sample or standard.

After incubation for 4 min at ambient temperature, 60µL of Na 2 CO 3 700 mM was added to stop the reaction. Then 195 µL of distilled water was added. After incubation for 1 h at room temperature, absorbance at 760 nm was measured. Results were expressed as g.L -1 gallic acid equivalent (GAE).

2,2′-azinobis-(3-ethylbenzothiazoline-6-sulfonic acid) (ABTS) free radical scavenging activity

ABTS is oxidized by potassium persulfate K 2 S 2 O 8 to generate cation radical ABTS°+ which absorbs at 734 nm. Antioxidant compounds degrade this radical, resulting in a decrease of absorbance at 734 nm. To generate the cation radical ABTS°+, 5 mL of a solution of 7 mM ABTS was added to 5 mL of 2.45 mM potassium persulfate. ABTS°+ solution was then diluted in methanol in order to obtain an absorbance of 0.7 at 734 nm. Samples were 5-fold diluted in ultrapure water. In a transparent 96well plate, 280 µL of ABTS°+ was mixed with 20µL of sample. The blank was obtained with 20 µL of ultrapure water. After 5 min of incubation at 30°C in the Tecan Infinite M200 spectrofluorimeter, absorbance at 734 nm was measured. Trolox at concentrations 50 µM to 250 µM was used as standard. The % of inhibition was expressed for Trolox and for samples with the formula: % of inhibition = 100 -100 *

௦ ௦ ௦ .
The curve indicating % of inhibition versus Trolox concentrations was used as standard curve.

Antioxidant activity was expressed in mM TE.

1,1-Diphenyl-2-picrylhydrazyl (DPPH) free radical scavenging activity

Diphenyl-2-picrylhydrazyl (DPPH) assay was used to determine the free radical scavenging activity of fermented and non-fermented pineapple juice. In a 96-well plate, 150 µL of DPPH solution (0.2 mM in methanol) was mixed with 50 µL of 5-fold diluted sample. The mixture was then kept at room temperature for 30 min in the dark. The absorbance of the mixture was measured at 517 nm using microplate reader (Fluostar). Results were expressed as a % of inhibition of sample versus control.

Trolox was used as positive control.

Low-density lipoprotein (LDL) oxidation

LDL (1.019 -1.055 g.mL -1 ) were isolated by sequential ultracentrifugation of pooled plasma from normolipidemic subjects (Beckman centrifuge). After dialysis against PBS pH 7.4, LDL were assayed for protein content by the bicinchoninic acid method and stored at 4°C in the dark for no longer than 15 days. LDL oxidation was determined by measuring conjugated diene formation. Oxidation of LDL was conducted with 50 µL of 1.96 µg.µL -1 of LDL protein in the presence of 30 µL samples (10,000-fold dilution). Negative control consisted of 30 µL of distilled water. Reaction was started by adding 20 µL of CuSO 4 solution (80 µM). Conjugated diene absorbance was measured by spectrophotometry at 234 nm every 5 min during 2 h at 37°C by using a microplate reader (Fluostar). Results are expressed in half time oxidation (V-50), obtained from GraphPad Prism 2.01 with a Boltzman sigmoidal nonlinear regression, as for erythrocyte hemolysis assay. V-50 corresponds to the half time oxidation, expressed in min.

Statistics

All values are expressed as mean ± standard deviation.

Variance analysis and Student t-test have been used to compare the different treatments. If a significant difference was pointed out, Bonferroni test was used to test the difference between each treatment and control. Principal component analysis was performed with Pearson(n) matrix.

The statistical analysis was performed using GraphPad Prism 2.01 (GraphPad Software, Inc) or XLSTAT (Addinsoft). Degrees of significance are indicated as follow: * p < 0.05, ** p < 0.01, *** p < 0.001, ns = not significant.

RESULTS

Isolation and molecular identification

LAB population was determined from the different samples of papaya, tomato and sliced cabbage, purchased from local markets (Table1). The surface of the two fruits was characterized by LAB population comprised between 5.1 and 5.8 log 10 cfu.g -1 , while sliced cabbage contained higher LAB population with 9.2 to 10.0 log 10 cfu.g -1 . Isolates were recovered from these samples on the basis of colony morphological differences and microscopy differences. Out of 64 LAB isolates, 10 isolates from six samples were chosen based on morphological differences and identified by 16S rRNA coding region partial sequencing (Table 1). They belong to three different genera. Leuconostoc spp. was the most frequent. Isolates from papaya covered the three genera.

In order to distinguish species with highly identical 16S rRNA genomic sequences, a rep-PCR was applied. Similar profiles were obtained for isolates S9 and S13, S17 and S29, S5 and S6 and S12 and S27 respectively. Their comparison to reference strain profiles increased the accuracy of species assignment (Table 1 andFigure S1).

EPS producing isolates

Three isolates exhibited a negative EPS producing phenotype: S17, S29 and DSM2601. The isolates S5, S6, S9 and S10 resulted in high (+++) creamy colony phenotypes. The isolates S12 and S27 resulted in poor (+) liquid colony phenotypes. The isolates S13 and S14 did not succeed to grow under the test conditions.

Acidification kinetics

The 10 isolates were grown in BHI, a nutrient-rich broth, for 72h and pH was monitored every 5 min. Two profiles of acidification were observed by plotting dpH/dt as a function of time (Figure 1). W. cibaria and Lactobacillus spp. isolates exhibited a single acidification peak whereas Leuconostoc spp.

isolates showed two peaks of acidification. From those profiles, several parameters were extracted: lag time, time for the first acidification peak (t M ), maximal acidification rate (V M ), pH at maximal rate (pH M ) and minimal pH observed during the culture (Table 2). These parameters were used as variables for a principal component analysis, with isolates as observations (Figure 2). The two projection axes, F1 and F2, were representative of variables and accounted for 83.71%. Interestingly, the isolates grouped according to their genus. Leuconostoc spp. exhibited a long lag phase, a low V M and a high minimal pH. Both W. cibaria and Lactobacillus spp. exhibited a short lag phase and a low minimal pH, but W. cibaria showed a high V M contrarily to Lactobacillus spp.

One or two isolates of each genus were grown under the same conditions, but in MRS broth (Table 2). In this medium, the double peak profile was not observed for Leuconostoc spp. isolate. In MRS broth, maximal acidification rates were 2.4 to 4.5 fold higher than in BHI and minimal pH, pH M and lag time were lower. Except for lag time, these parameters followed the same tendencies between isolates in BHI and in MRS broth.

Growth and adaptation to sub-lethal stress

An assay to evaluate isolate adaptation to different stress was standardized. The control condition showed that two isolates, S9 and S13, both Leuconostoc citreum, exhibited a poor growth in BHI over 48 h at 30°C, with an OD variation of less than 0.2 (Figure 3a). For other isolates, 48 h OD variation without stress was comprised between 0.4 and 0.9.

For these eight isolates, the stress adaptation assay was applied to evaluate adaptation to low pH, to high sodium chloride level or to oxidative stress, in respect to control condition (Figure 3b,c).

Oxidative stress adaptation was tested with two concentrations of hydrogen peroxide, 0.025% and 0.05% (Figure 3b). The lowest H 2 O 2 level resulted for S12 and S27, both W. cibaria isolates, in a 40% decrease of 48h-growth compared to non-stressing condition, whereas other isolates growth did not significantly decrease. The effect of 0.05% H 2 O 2 level was much more marked: growth of all isolates was affected but in different proportion. For instance, the effect of 0.05% H 2 O 2 was more pronounced on the growth of S12 and DSM2601 (p-value<0.001) whereas the effect on S14 was not significant. A level of 0.07% H 2 O 2 was tested, and none of the isolates was able to adapt to this concentration. Two isolates, S5 and S6, which belong to Leuc. mesenteroides, were particularly sensitive to pH, whereas S17 and S29, identified as Lb. paraplantarum/pentosus were the most tolerant (Figure 3c). For W. cibaria, isolate S12, contrarily to isolate S27, was not able to grow in the presence of 5% NaCl (Figure 3c). The highest salt tolerance was observed for S5 (Leuc. mesenteroides), S10 and S14 (Leuc. pseudomesenteroides), DSM2601 and S27 (W. cibaria).

From the obtained data, four isolates demonstrated the best ability to adapt tested stress individually: S10 and S14 (Leuc. pseudomesenteroides), S17 (Lactobacillus paraplantarum/pentosus) and S27 (W. cibaria).

Pineapple antioxidant capacity modulation

Each isolate was inoculated into pasteurized pineapple juice and incubated for 48 h at 25°C with agitation. Pineapple juice exhibited an initial pH of 3.6 and an initial reducing sugar level of 94.4 ± 10.0 g.L -1 . After 48h, no significant decrease in pH was observed and a significant growth was observed only for isolates S5, S12 and S17.

Antioxidant capacity was evaluated from seven different assays: ORAC, ABTS, hemolysis test, OD280nm measurement, DPPH, Folin-Ciocalteau, and LDL oxidation. Pasteurized juice was used as control.

From ORAC, ABTS, erythrocyte hemolysis, DPPH and OD 280nm assays, no significant difference could be observed between samples fermented with different isolates, neither between fermented juices versus control condition. The ORAC value for pineapple juice was 187 ± 11 mM TE. For ABTS assay, pineapple juice value was 57.0 ± 3.2 mM TE. Hemolysis test showed a HT50 (time for halfhemolysis) value of 103 ± 49 min for 100-fold diluted juice, and DPPH assay resulted in a value of 42.6 ± 2.1 g GAE.L -1 for control juice. The measurement of OD at 280 nm of pineapple juice resulted in 300 ± 18 g GAE.L -1 . Contrary to the above, Folin-Ciocalteau and LDL oxidation assays showed a number of variations (Figure 4). Folin-Ciocalteau assay resulted in 1.15 ± 0.05 g GAE.L -1 for pineapple juice. Pineapple juice fermented with isolate S14 (Leuc. pseudomesenteroides) exhibited a Folin-Ciocalteau value of 1.43 ± 0.25 g GAE.L -1 . The two values significantly differed with a p-value of 0.06. Other fermented juices did not differ from the control.

From LDL oxidation assay, the determination of V50, the time for half-LDL oxidation, was used to compare samples and control. Distilled water was used as control and showed a V50 value of 56.6 ± 0.8 min. A 10 4 -fold diluted juice did not exhibit a significant difference compared to water, but the use of 10 3 -fold diluted juice resulted in an absence of measurable oxidation of LDL by copper. Only the juice fermented with S27 (W. cibaria) and 10 4 -fold diluted exhibited a significant delayed oxidation versus control with a V50 value of 59.7 ± 1.6 min. The other diluted fermented juice did not differ from the control.

DISCUSSION

The interest in fruit or vegetable foods, and particularly in lactic fermented foods, has considerably increased over the last decade as these foods can significantly contribute to a healthy diet. In the present study, lactic acid bacteria were isolated from papaya, tomato or sliced cabbage samples, identified by molecular method and characterized for phenotypic traits related to technological properties relevant for food fermentation. A special focus was made on antioxidant activity, choosing an acidic fruit juice and a short incubation time for testing.

The sampled fruits and vegetables exhibited very diverse levels of LAB, with population ranging between 5.1 and 10.0 cfu.g -1 . The highest population was observed for sliced cabbage, a ready-to-eat vegetable, for which cutting resulted in increased surface and nutrient availability. We limited our study to 10 isolates chosen from morphological diversity criterion, and those isolates were showed to belong to five different species and three genera. Whereas Weissella spp. and Leuconostoc spp. are frequently isolated from fermented foods, starters used in vegetable food fermentation essentially belong to Lactobacillus spp. Interestingly, isolates exhibited very different fermentation kinetics parameters. The use of acidification kinetics as a tool to monitor fermentation performance has been developed more than 25 years ago [START_REF] Spinnler | Automatic method to quantify starter activity based on pH measurement[END_REF] and has been widely applied to characterize dairy starters [START_REF] Cachon | Characterization of lactic starters based on acidification and reduction activities[END_REF][START_REF] Latrille | Characterizing acidification kinetics by measuring pH and electrical conductivity in batch thermophilic lactic fermentations[END_REF][START_REF] De Souza Oliveira | Effect of inulin on growth and acidification performance of different probiotic bacteria in co-cultures and mixed culture with Streptococcus thermophilus[END_REF][START_REF] Xanthopoulos | Characterization and classification of Streptococcus thermophilus and Lactobacillus delbrueckii subsp. bulgaricus strains isolated from traditional Greek yogurts[END_REF]). However, this tool has never been previously used to characterize Leuconostoc spp. or Weissella spp. Our study revealed that Weissella cibaria can act as a potent acidifier. No significant decrease of pH was observed during short-term fermentation of pineapple juice, probably as a consequence of the low initial pH (3.6). Dairy bacteria grown in milk exhibited V M values that range between 0.2 and 1.2 UpH.h -1 and T M between 3 and 10h [START_REF] Cachon | Characterization of lactic starters based on acidification and reduction activities[END_REF][START_REF] Latrille | Characterizing acidification kinetics by measuring pH and electrical conductivity in batch thermophilic lactic fermentations[END_REF][START_REF] De Souza Oliveira | Effect of inulin on growth and acidification performance of different probiotic bacteria in co-cultures and mixed culture with Streptococcus thermophilus[END_REF][START_REF] Xanthopoulos | Characterization and classification of Streptococcus thermophilus and Lactobacillus delbrueckii subsp. bulgaricus strains isolated from traditional Greek yogurts[END_REF]. In our study, the values of V M on MRS broth ranged between 0.10 and 0.15 UpH.h -1 whatever the species, which is by far much lower than V M observed in dairy studies. MRS broth is recommended for LAB culture: as expected, even lower V M were observed in BHI. Interestingly, acidification kinetics in BHI showed genus related patterns, hereby characterized by V M , t M , pH M , minimal pH and lag time. Differences between slow and rapid fermentative isolates and between high and low acidifiers were easily pointed out in this medium.

The comparison of growth yield between un-stressing and stressing conditions is critical since fermentation generally results from bacterial competition in a stressing environment [START_REF] Serrazanetti | Dynamic stresses of lactic acid bacteria associated to fermentation processes[END_REF]. Indeed, most fruits and many vegetables exhibit a low pH. Moreover, addition of salt in vegetable preparations is often used as a selective agent. Stress adaptation ability widely differed between isolates, even within the same species. Interestingly, S12 and S27, both W. cibaria, shared similar (GTG) 5 profile, but showed different stress adaptation ability. On the contrary, S17 and S29, both Lb. paraplantarum/pentosus, shared similar (GTG) 5 profile and showed same adaptation patterns. Several mechanisms are involved in LAB stress tolerance: glutathione system [START_REF] Kim | Enhancing acid tolerance of Leuconostoc mesenteroides with glutathione[END_REF][START_REF] Zhang | Engineering the antioxidative properties of lactic acid bacteria for improving its robustness[END_REF], the so-called general stress response or acid tolerance response (ATR) (van de [START_REF] Van De Guchte | Stress responses in lactic acid bacteria[END_REF], and the ability to detoxify reactive oxygen species, thanks to antioxidant enzymes [START_REF] An | Coexpression of the superoxide dismutase and the catalase provides remarkable oxidative stress resistance in Lactobacillus rhamnosus[END_REF][START_REF] Bruno-Bárcena | Role of antioxidant enzymes in bacterial resistance to organic acids[END_REF][START_REF] Ramesh | Comparative evaluation of selected strains of lactobacilli for the development of antioxidant activity in milk[END_REF]. Although LAB are catalase negative, other enzymes, such as superoxide dismutase, peroxidases or NADH oxidases might be involved in detoxification. These key-activities deserve to be determined in the most resistant isolates.

Recently, a relationship between redox regulation mechanisms and production of exopolysaccharides (EPS) was shown in Lactobacillus casei [START_REF] Zhang | Engineering the antioxidative properties of lactic acid bacteria for improving its robustness[END_REF]. Moreover, many EPS, produced by Leuconostoc spp., were shown to exhibit antioxidant activities by themselves [START_REF] Li | Structural elucidation and antioxidant activities of exopolysaccharides from Lactobacillus helveticus MB2-1[END_REF][START_REF] Pan | Antioxidant activity of an exopolysaccharide purified from Lactococcus lactis subsp. lactis 12[END_REF]. As Weissella spp. is a high EPS producer, investigation of the activities of enzymes involved in intracellular redox balance and oxidative stress detoxification is of particular importance for this genus.

The contribution of a short fermentation time to the antioxidant capacity of pineapple juice was poor. Only two antioxidant capacity tests, Folin-Ciocalteau and LDL oxidation assays, showed significant differences between fermented juice and control. Noteworthy enough, this fermentation step did not result in a loss of antioxidant capacity of juice. Other studies have pointed differences in antioxidant capacity after fermentation. For instance, in olives, in green or red smoothies or in pomegranate juice, fermentation with Lb. plantarum, alone or associated with W. cibaria or Pediococcus pentosaceus, decreased the antioxidant capacity [START_REF] Di Cagno | Effect of lactic acid fermentation on antioxidant, texture, color and sensory properties of red and green smoothies[END_REF][START_REF] Filannino | Exploitation of the health-promoting and sensory properties of organic pomegranate (Punica granatum L.) juice through lactic acid fermentation[END_REF][START_REF] Othman | Antioxidant phenolic compounds loss during the fermentation of Chétoui olives[END_REF]. In other studies, over a very short time (8-17h) of fermentation of tempeh (soybean seeds) or tomato juice with Lb. plantarum, the antioxidant capacity was maintained [START_REF] Di Cagno | Effect of autochthonous lactic acid bacteria starters on health-promoting and sensory properties of tomato juices[END_REF][START_REF] Starzyńska-Janiszewska | Effect of controlled lactic acid fermentation on selected bioactive and nutritional parameters of tempeh obtained from unhulled common bean (Phaseolus vulgaris) seeds[END_REF]. Conversely, fermentation of white cabbage over 7 days, with Lb. plantarum and/or Leuc. mesenteroides, showed a two-fold increase in the antioxidant capacity measured with ORAC [START_REF] Martinez-Villaluenga | White cabbage fermentation improves ascorbigen content, antioxidant and nitric oxide production inhibitory activity in LPS-induced macrophages[END_REF]. Similarly, the antioxidant activity of soymilk increased by three-fold after 24h fermentation with a Lb. rhamnosus starter [START_REF] Marazza | Enhancement of the antioxidant capacity of soymilk by fermentation with Lactobacillus rhamnosus[END_REF]. The relationship between antioxidant capacity modulation and changes in composition or enzyme activities deserve to be extensively investigated.

Based on stress tolerance, four isolates appeared resistant: S10, S14, S17 and S27. They were distributed over the four species identified. All four isolates revealed very different acidification kinetics. Among those, only S14 and S27 modulated significantly the juice antioxidant capacity. The applied method is thus relevant to identify potential starters which may be used to perform mild or strong, slow or rapid food fermentation. A larger screening of isolates, completed with enzymatic activity screening, could highlight relationships between stress resistance, ability to modulate antioxidant capacity and enzyme activities.

Isolate S14 belong to Leuc. pseudomesenteroides species and isolate S27 to W. cibaria. These species are commonly identified from fermented vegetables, including cabbage and olive [START_REF] Di Cagno | Exploitation of vegetables and fruits through lactic acid fermentation[END_REF]). However, their use as starters is not yet described. In addition, the physiological properties of Weissella spp. are still poorly known, but recently niche specific features were highlighted at genomic level [START_REF] Lynch | Genomics of Weissella cibaria with an examination of its metabolic traits[END_REF]. The S27 isolate showed in this study a high potential for its use as starter for fermented fruit or vegetable juices. An experimental plan with different fruit juices and different fermentation durations is warranted in order to determine the safety and the sensorial properties of the resulting food.

TABLES

Figure S1

Dendrogram for Weissella spp isolates and reference strains using (GTG) 5 genotyping.

See materials and methods for cluster analysis and tree building.

  sample was determined from its capacity to reduce fluorescein oxidation by peroxyl radicals generated with AAPH (2,2'-Azobis [2-methyl-propionamidin]dihydrochloride). Briefly, in a black 96well plate, 25 µL of sample were mixed with 150 µL of 0.0838 µM fluorescein prepared in 1 M phosphate buffer pH 7.4. After 15 min of incubation at 37°C in the TECAN INFINITE M200 spectrofluorimeter, 25 µL of 153 mM AAPH were added in each well. Decrease in fluorescence corresponding to fluorescein oxidation was measured at excitation and emission wavelengths of 485 and 530 nm respectively. Trolox at concentrations of 20, 50 and 100 µM was used as standard. The area under the curve (AUC) was determined automatically for each sample and for each Trolox concentration. Standard curve was established by plotting AUC versus Trolox concentration. Antioxidant activity was expressed as µM Trolox equivalent.

Figure 1

 1 Figure 1

Figure 3

 3 Figure3

Figure 4

 4 Figure 4

  Figure 1

  Figure 2

Table 1 :

 1 Origin and identification of isolates

	Isolate Origin	Numeration	16S partial	% ID	Species	(GTG)5 profile
			(cfu.g -1 )	sequence (bp)
	S5	Papaya	1.33 10 5	430	99% LN774434.1	Leuc. mesenteroides/pseudomesenteroides Leuc.
							mesenteroides
	S6	Papaya	1.33 10 5	939	99% KJ477421.1	Leuc. mesenteroides/pseudomesenteroides Leuc.
							mesenteroides
	S9	Papaya	1.33 10 5	941	99% AB904775.1; HF562952.1 Leuc. holzapfelii/citreum	Leuc. citreum
	S10	Papaya	1.33 10 5	945	99% GQ351323.1	Leuc. mesenteroides/pseudomesenteroides ND*
	S13	Tomato	6.64 10 5	915	99% KF879147.1; AB904775.1 Leuc. holzapfelii/citreum	Leuc. citreum
	S14	Sliced	1.57 10 9	921	99% KF879168.1	Leuc. mesenteroides/pseudomesenteroides ND
		cabbage
	S12	Papaya	1.33 10 5	935	99% AB761300.1	W. cibaria/confusa	W. cibaria
	S27	Sliced	1.07 10 10	879	100% HF562959	W. cibaria/confusa	W. cibaria
		cabbage
	S17	Papaya	1.30 10 5	879	99% KJ690749.1; KJ690750.1	Lb. plantarum/paraplantarum/pentosus	Lb. paraplantarum
							/pentosus
	S29	Tomato	6.64 10 5	614	99% KC914585.1;	Lb. plantarum/paraplantarum/pentosus	Lb. paraplantarum
					KP189214.1		/pentosus
	DSM	Pickled	-			Lb. plantarum
	2601	cabbage
	* ND: not determined

Table 2 :

 2 Parameters of acidification (mean ± standard deviation)

	Isolate	Lag time (h)	pH min	V M (mU pH.h -1 )	pH M	t M (h)
				Growth in BHI (initial pH 6.8)
	S5	11.42 ±	3.42	5.9 ± 0.1	32 ±	1	6.3 ± 0.2	4.29 ±	0.41
	S6	10.92 ±	0.59	5.8 ± 0.1	33 ±	1	6.3 ± 0.1	4.25 ±	0.24
	S9	5.13 ±	0.77	5.9 ± 0.1	38 ±	5	6.4 ± 0.1	4.00 ±	0.59
	S10	4.17 ±	0.59	6.2 ± 0.2	38 ±	7	6.4 ± 0.1	3.00 ±	0.47
	S13	19.58 ±	0.59	6.2 ± 0.4	26 ±	9	6.5 ± 0.3	4.75 ±	1.71
	S14	17.75 ±	0.59	6.1 ± 0.1	31 ±	6	6.4 ± 0.1	5.58 ±	0.59
	S12	6.58 ±	2.24	4.9 ± 0.1	66 ±	3	6.1 ± 0.1	5.13 ±	0.12
	S27	2.04 ±	1.24	4.9 ± 0.1	50 ±	1	6.1 ± 0.6	6.25 ±	1.36
	S17	10.96 ±	0.06	5.6 ± 0.1	43 ±	1	6.2 ± 0.1	11.29 ±	0.35
	S29	11.54 ±	1.00	5.7 ± 0.1	43 ±	7	5.7 ± 0.1	10.79 ±	0.41
	DSM2601	8.13 ±	0.65	4.5 ± 0.1	33 ±	1	5.8 ± 0.1	12.38 ±	1.47
				Growth in MRS broth (initial pH 5.7)
	S5	4.92		4.1	118		5.1	5.33
	S10	6.67		4.2	105		5.0	8.33
	S27	3.17		3.7	156		4.8	10.08
	DSM2601	3.75		3.7	150		4.8	10.50

ACKNOWLEDGEMENTS

This study was supported by grants from the structure Fédérative Environnement, Biodiversité et Santé, University of La Reunion. AF PhD is supported by a fellowship from the "Conseil Regional de La Réunion et l'Europe". We thank Pr Teeshan Bahorun, Centre of Excellence for Biomedical and Biomaterials Research, University of Mauricius, for careful reading.


Nikos Karanikolas

Renaud Blanch

Sylvain Bouveret

Edge-Compressed Majority Graph: Where Social Choice Meets Information Visualization

Collective decisions are everywhere: choosing central or local governments, selecting a candidate to hire for an open position, choosing a restaurant to share a dinner with some friends are examples of collective decision making situations. Social Choice provides a lot of methods which can help people making a decision in such situations. However, the diversity of these voting procedures and the mathematical background necessary to understand them can be seen as obstacles to the use of these methods in everyday situations by laypersons. We claim that information visualization techniques can help a lot the democratization of social choice, by providing people with some easily interpretable information and, in the end, helping them making informed collective decisions. In this paper, we present the Edge-Compressed Majority Graph, a technique dedicated to the visualization of the majority graph of a preference profile. Using an insight-based evaluation method, we show that this technique gives better results in conveying information about the preferences than other classical visualization techniques.

Introduction

The need for collective decisions has played an important role from the beginning of mankind's first organized societies till nowadays. Democracy, which is considered from an ethical point of view the ideal form of government is based on elections, where all citizens have an equal say in the decisions that affect their lives. A major problem that arises in democratic societies is how to interpret the will of people and bring out a satisfying collective decision. Social Choice, and especially Voting Theory, is the field that addresses the problem by providing a set of methods aiming at aggregating a set of individual preferences into a collective preference or decision. The paradigmatic problem is here to aggregate a set of N rankings representing the voters preferences on a set of m candidates into a collective ranking using a voting rule.

Throughout the history of social choice many rules have been proposed, and each one of them is trying to reflect the socially fairest outcome. In the case where there are only two candidates (and an odd number of voters), majority voting1 is unanimously considered a perfect method of selecting the winner. However, when there are three candidates or more, no such obvious rule choice exist, and there exists numerous voting methods that all have different axiomatic properties. Among these methods, a prominent family of rules are based on the Condorcet principle. This principle was introduced by Nicolas de Condorcet, the founding father of the mathematical theory of voting, who suggested a rule that extends majority voting to multiple candidates [START_REF] De Condorcet | Essai sur l'application de l'analyse à la probabilité de décisions rendues à la pluralité de voix[END_REF]. A candidate x is said to beat candidate y in a pairwise election (comparison) if the majority of voters prefer x to y, i.e., rank x above y. A candidate that beats every other candidate in a pairwise election is the winner of the entire election. Such a Condorcet winner, when it exists, is generally considered a good social consensus. The family of Condorcet-consistent voting rules aim at reconciling the Condorcet winner with the fact that it may not exist, by electing it when it exists. This family includes, among others, Simpson's rule, Copeland's method, [START_REF] Copeland | A reasonable social welfare function[END_REF], Dodgson's rule [START_REF] Black | Theory of Committees and Elections[END_REF] and Young's method [START_REF] Young | Extending Condorcet's rule[END_REF]. Some of these methods are based on the (weighted) majority graph: a directed graph where each node represents a candidate and the arc (x, y) exists if and only if x beats y in a pairwise comparison. Even if some Condorcet-consistent methods are not directly based on it, the majority graph is a good way to understand the rationale behind these methods (namely, pairwise comparisons).

A fundamental question of Social Choice is the choice of the voting rule to use when there are three candidates or more, as different voting rules can yield very different collective preferences (and hence different winners). The traditional approach in social choice theory is prescriptive: facing a collective decision making problem, a society will choose a voting procedure that satisfies good axiomatic properties (monotonicity, reinforcement...). However, making an informed choice about the voting method requires a strong mathematical background that most people do not have, leaving them with no solution but to choose a black-box voting method by default. We believe that a good alternative is to use (graphical) information visualization techniques to help people understanding the structure of preferences without prescribing any ranking given by a voting method.

The domain of Information Visualization (InfoVis) deals with designing visual representations of abstract information to help the user increasing her knowledge about the internal structure of the data and causal relationships in it. Information Visualization aims at providing techniques for the users to make discoveries, decisions, or explanations about patterns, groups of items, or individual items. Most works in InfoVis aim at providing visualization techniques that do not require any strong mathematical background or knowledge from the user for her to be able to interpret the information. Our research direction is to try to apply these techniques on social choice problems, where the information we want to visualize is the votes and the interpretation of these votes.

As a first step, we focus, in this work, on the visualization of the weighted majority graph. We believe that the weighted majority graph is an interesting intermediate aggregation level between the complete preference profile and the collective preference issued by a particular voting rule. It already contains compressed information about the individual preferences but can still act as a proxy for a lot of Condorcet-consistent voting rules. We also believe that a decision maker can learn a lot of information about the structure of individual and collective preferences from an efficient graphical representation of the weighted majority graph. It should be noticed, though, that choosing a representation based on this graph is not neutral. It orients the decision towards candidates that are good according to the Condorcet principle. This is not without loss of generality and will favour some types of candidates.

Giving an efficient graphical representation of the majority graph is not straightforward. Being a complete directed graph, the traditional node-link representation quickly becomes unusable as the number of candidates grows. In this paper, we propose (in Section 4) a visualization called the Edge-Compressed Majority Graph, and compare it with the classical node-link representation and a representation based on the adjacency matrix. The experiments (provided in Section 5) show that people are able to extract a lot more useful pieces of information from the Edge-Compressed Majority Graph visualization technique than from the other classical ones.

Related work

The application of Information Visualization in Social Choice is a relatively new field, however visualization in elections is widely used in many forms. Occasionally, there are many graphs and animations published in the newspapers or news websites visualizing the results of different kinds of political elections. However, most voting rules used in political contexts do not ask the voters to give their preferences in the form of linear orders (rankings), but rather ask e.g. either to give one's preferred candidate, or to approve a set of candidates. This is why techniques based on the majority graph (like Condorcet consistent rules and the visualization techniques we use in this paper) are not relevant in this context. This motivated us to study meticulously the visualization of more complex election settings and voting rules, like the one promoted by Social Choice theorists.

To the best of our knowledge, the study of visualization techniques applied to Condorcetconsistent voting rules is new. However, the usage of majority graphs in this kind of voting rules have been being studied for years in the Social Choice literature, with the application of tournament solutions. One such method, which was proposed by Copeland [START_REF] Copeland | A reasonable social welfare function[END_REF], constitutes one of the most important tournament solutions. Other significant tournament solutions were proposed by Levchenkov [START_REF] Levchenkov | Social choice theory : a new sight[END_REF][START_REF] Grivko | Intrinsic properties of the self-consistent choice rule[END_REF]; Fishburn [START_REF] Fishburn | Condorcet social choice functions[END_REF] and Miller [START_REF] Miller | A new solution set for tournaments and majority voting: Further graphtheoretical approaches to the theory of voting[END_REF]; and Banks [START_REF] Banks | Sophisticated voting outcomes and agenda control[END_REF]. An analytic survey of tournament solutions can be found in Laslier's book [START_REF] Laslier | Tournament Solutions and Majority Voting[END_REF].

Perhaps the closest work to our approach is the one by Betzler et al. [START_REF] Betzler | Theoretical and empirical evaluation of data reduction for exact Kemeny Rank Aggregation[END_REF]. In their work, they propose a set of data reduction techniques to compute the winner of the Condorcetconsistent Kemeny's rule (which is NP-hard to compute). One of their data reduction techniques is based on the computation of clusters of candidates using the strongly connected components in the majority graph. As we will see in Section 4, our Edge Compression Majority Graph uses a very similar reduction technique. The main difference is that we use it for visualization purposes, where Betzler et al. use it for theoretical (complexity) results.

Preliminaries

We consider a set N = {1, . . . , n} of voters and a set C of m candidates. Each voter i has a linear order i on C, where x i y means that voter i prefers candidate x to y. Let L C be the set of linear preferences over C. A preference profile = 1 , . . . , n ∈ L n C is a collection of preferences for all the voters. A voting correspondence is a mapping f : L n C → 2 C \ {∅} from preference profiles to non empty subsets of candidates, the co-winners of the election. A voting rule maps a preference profile to a unique winner. Most voting rules are built from the composition of a voting correspondence and a tie-breaking rule.

Let ∈ L n C . The majority margin m is the function that maps each pair (x, y) of candidates to the difference between the number of voters that prefer x to y and the number of voters that prefer y to x, namely: m(x, y) = |{i ∈ N : x i y}| -|{i ∈ N : y i x}|. The majority relation is the binary relation Maj defined as the subset of elements (x, y) ∈ N 2 such that m(x, y) ≥ 0. The binary relation Maj is the strict part of Maj ; therefore if x Maj y, we say that x (strictly) beats y in a pairwise election (or comparison). The majority graph is the directed graph representing Maj . A Condorcet winner is a candidate that strictly beats every other candidate in a pairwise election.

Among the set of Condorcet-consistent voting rules, some of them are based on the majority relation. In particular, the Copeland rule works as follows. For each candidate x, the Copeland score of x is the number of candidates y such that x Maj y. The candidate with the highest Copeland score is the winner of the election. Some other Condorcetconsistent voting rules, among which the Kemeny rule, are based on the information provided in the weighted majority graph. Finally, some rules use the information contained in the full preference profile. In particular, the Dodgson rule works as follows. For each candidate x, the Dodgson score of x is the smallest number of sequential exchanges of adjacent candidates in the preference profile needed to make x a Condorcet winner.

In the following, we will have to resort to a Condorcet consistent voting rule when an order is required for some specific graphical attribute (as is the case in the Pairwise Comparison Matrix and our Edge-Compressed Majority Graph techniques. Dodgson's voting rule is intuitively appealing and one of the most well-studied voting rules in the literature. However it is hard to compute since the Dodgson score decision problem is NP-complete, as shown by Bartholdi, Tovey and Trick [START_REF] Bartholdi | Voting schemes for which it can be difficult to tell who won the election[END_REF]. In order to apply a Condorcet-consistent voting rule that will be computed efficiently (polynomial time) we will use the one proposed by Caragiannis et al. [START_REF] Caragiannis | Socially desirable approximations for Dodgson's voting rule[END_REF]. They proposed the following Dodgson approximation rule which is an extension of Tideman's simplified Dodgson rule [20, pages 199-201]. Consider a profile ∈ L n C and a candidate x. If a candidate x is a Condorcet winner, then it has Extended Tideman's Simplified Dodgson (ETSD) score sc Td (x, ) = 0. Otherwise:

sc Td (x, ) = m • sc Td (x, ) + m(log m + 1), (1)
where sc Td (x, ) is simplified Dodgson score of candidate x defined as:

sc Td (x, ) = y∈A\{x} max {0, n -2 • |{i ∈ N : x i y}|}. (2)
The candidate with the minimum score wins.

Visualizing the majority graph

In this section we describe how we graphically visualize weighted majority graphs. We consider three types of visualization techniques: the Pairwise Comparison Matrix, the Weighted Majority Graph and the Edge-Compressed Majority Graph. All of these techniques aim at extracting a synthetic information from a voting situation in order to allow a decision maker understand the structure of the voting profile. Clearly, the general purpose of our work is to provide a set of visual representations of the voting data which are clearly understandable without prior knowledge on any voting method. We also emphasize that all of our methods can be employed for the visualization of any kind of weighted tournament graph, whether they represent the weighted majority graph of a voting situation or not. Before introducing our visualization techniques, we should note that ordering the candidates is a crucial aspect. This is inherent to graphical visualization, since most graphical attributes naturally induce an ordering (e.g. left-to-right for abscissa, top-to-bottom for ordinate, green-to-red for colors). To deal with this aspect, we had two obvious choices. Either randomly map values of graphical attributes (x, y, color...) to candidates or choose a specific ordering and use graphical attributes to convey it. We chose the second approach for the sake of graphical clarity (randomness yield representations that are harder to read and interpret). We have used a Condorcet-consistent aggregation method, more precisely ETSD scores (sc Td ) (because of its similarity to the Dodgson's), as input order to the graphical representations. 2 We know that this is at the price of inducing a strong bias in the way users perceive the visualization.

Pairwise Comparison Matrix

The first visualization technique is the Pairwise Comparison Matrix (PCM), which simply displays the majority margin between each pair of candidates using a matrix of colors. Every entry of the matrix a i,j represents the majority margin m(i, j), with i, j ∈ 1, m , encoded The Godfather (Le Parrain)

The Shawshank Redemption (Les Evadés)

A. Pairwise Comparison Matrix

Fight Club

The Matrix (Matrix)

Forrest Gump

Star Wars

Pulp Fiction Schindler's List (La Liste de Schindler)

The Lord of the Rings (Le Seigneur des anneaux)

The Dark Knight (Le Chevalier Noir)

The Godfather (Le Parrain)

The Shawshank Redemption (Les Evadés)

B. Weighted Majority Graph

Fight Club

Condorcet Winner

The Matrix

Star Wars

Schindler's List

The Lord of the Rings

Pulp Fiction

Forrest Gump

The Dark Knight

The Godfather

The Shawshank Redemption

C. Edge-Compressed Majority Graph

Figure 1: Different visualizations for the movie poll using a green to red color scale. More precisely, we use the "diverging category with ten data classes" (10-class RdYlGn) scale [START_REF] Brewer | Colorbrewer 2.0[END_REF] and map the values (percentage) to these colors. When m(i, j) > 0 (resp. < 0), a i,j is a variant of green (resp. red) color where the saturation level is simply m(i, j)/n (resp. m(j, i)/n). If m(i, j) = 0 the a i,j cell is a yellowish color. The rows and columns are ordered according to the ETSD score of the corresponding candidate. An example of PCM is shown in Figure 1.A. The data set used in this figure is the movie poll data set described in Section 5.1.

Weighted Majority Graph

The next visualization technique is the Weighted Majority Graph (WMG), which is a simple node-link representation of the majority graph with directed arcs for the strict part of the majority relation and undirected edges when two candidates tie. The weight of each arc (x, y) equals to m(x, y) and thus the sum of weights of the incoming arcs for a node x equals the simplified Dodgon score of candidate x. We use the width of each arc (x, y) as a graphical attribute encoding the weight of (x, y). Moreover, the graphical layout displays the candidate(s) who have the minimum simplified Dodgson score at the top. An example of the WMG for the aforementioned movie poll can be seen in Figure 1.B.

Edge-Compressed Majority graph

The last visualization technique, which is the one we propose, is the Edge-Compressed Majority Graph (ECMG). Our objective is to improve upon the WMG by providing a visualization where the most valuable information -namely, comparisons between candidates and voting cycles-can be easily extracted. Our method distinguishes the candidates that can be linearly ordered from the ones that are involved in cycles. The novelty of our technique is that it only shows the edges between the candidates of the latter type. In order to do that, we combine edge compression techniques in the visualization of dense graphs [START_REF] Dwyer | Edge compression techniques for visualization of dense directed graphs[END_REF] with the use of the axis y as a graphical attribute encoding a linear ordering. Moreover, we rely on concepts specific to Voting Theory, and especially on the properties of the Smith set [START_REF] Smith | Aggregation of preferences with variable electorate[END_REF], to perform the edge compression. The Smith set is the smallest non-empty set of candidates in a particular election such that each member of this set beats every other candidate outside the set in a pairwise comparison.

The edge compression algorithm works as follows. Starting from the whole set of candidates C, we compute a Smith set, and append it to the list of clusters. Then we reapply the same procedure iteratively on the remaining majority graph until no candidate remains. We end up with a sequence of clusters formed by the successively computed Smith sets. These clusters have the nice property that every node inside the same cluster have exactly the same set of arcs with nodes outside the cluster. This set of arcs can thus be "compressed" using arcs between clusters.

The algorithm we use for the computation of a Smith set is an adaptation from the algorithm presented in the Wiki for Election Methods [START_REF] Electowiki | Maximal elements algorithms[END_REF], that is an adjusted version of the Floyd-Warshall algorithm. We can observe that we could have used a different graphtheoretic perspective, because our technique can be seen equivalent to a decomposition into the strongly connected components of a directed graph. This decomposition can produce the same clusters of candidates and then we can apply a topological ordering on the components to get the same results as in our technique. Note that the Smith sets found during our technique are exactly the same as the strongly connected components of the graph given the following condition about ties: when there is a tie between two candidates then the undirected edge must be replaced by 2 directed edges heading towards both directions. The difference in time complexity for both techniques is not remarkable, so we preferred the Smith set decomposition because the implementation is simpler and relies also on notions of voting theory. Note that the computation of the Smith set needs time O(m 3 ) using the adaptation of the Floyd-Warshall algorithm and thus globally runs in O(m 4 ). We could have used the Kosaraju algorithm for computing the Smith set and thus reducing the time complexity of our technique to O(m 3 ) but we preferred a simpler implementation and the complexity does not really matter as the number of candidates (m) is in general low.

Graphical representation of the cluster graph At this point, we have to represent graphically a sequence of clusters -each cluster being a subgraph of the majority graph. The intuitive meaning of this sequence is that each candidate in a cluster is better than all the other candidates in the subsequent clusters. A natural way of representing linear orders is to use the abscissa or the ordinate as the graphical attribute encoding the rank of each element in the order. In our visualization, we use the latter, and the clusters are displayed on top of each other from the first to the last one. Doing this, we do not need to draw any arc between the clusters as the relation between two clusters can be naturally deduced from their respective ordinates.

Each cluster is displayed as a circle (or rectangle) containing the subgraph of the majority graph. If a cluster contains only one candidate we do not draw the border of this cluster but directly draw the candidate itself.

Each candidate (inside a cluster) is drawn as a circle, whose size and color depend on the candidate's ETSD score. Note that we use the minimum and maximum scores of the whole set of candidates and not only the ones belonging to the cluster. We do that in order to have a global visual representation of the candidates, otherwise there might be a case where a losing candidate that belongs to a lower ranked cluster has bigger size than a candidate who beats her. We use the same voting rule as above because, as already mentioned, it is easily computed and also produces less ties among the candidates compared to other Condorcet-consistent rules, like the Copeland's rule. Imagine the case where there are multiple members of a Smith set, then the Copeland's method often yields ties. For example, if there is a three-candidates voting cycle, each candidate will have exactly one loss, and there will be an unresolved tie between the three and there is no winner declared. On the other hand ETSD procedure computes the score for each candidate by adding the majority margins which is more unlikely to be the same for two candidates. Therefore, this rule is important in order to rank the nodes inside the cluster (of nodes) composing the Smith set and thus have a better visual appearance. In order to compute the circle's diameter for a node we use the following procedure: we assign maximum and minimum values of diameter that correspond to the candidates having the minimum and maximum scores accordingly, and then the node's diameter is calculated proportionately according to these values. The node's color is computed from the score. First, we choose a palette of 8 colors that extends from blue color to red (the palette used is the diverging 8-class spectral [START_REF] Brewer | Colorbrewer 2.0[END_REF]). Blue color is assigned to the candidate with the minimum score while red color to the candidate with the maximum score. Then, we compute the difference between the maximum and minimum scores of the candidates and divide this distance in 7 intervals of equal size, where the endpoints of the intervals correspond to each one of the 8 colors. Every candidate is assigned then to the appropriate interval according to her score. The color of the candidate is computed by the linear interpolation in the RGB color space of the endpoints of the interval she belongs to.

After computing all nodes' attributes, our algorithm checks the size of the Smith set. When the set is a singleton then the node corresponding to the sole candidate of the Smith set is drawn with the computed diameter and color. Otherwise, the members of the Smith set form a cluster of nodes. When there is a total (linear) order on the members of the Smith set3 then the nodes are drawn inside a rectangle in a vertical arrangement. The candidate of the set with the minimum score is ranked on top of the rectangle and the other candidates follow her according to their score. 4 If two or more candidates have the same score, then they are drawn at the same ordinate. Now, when there is not a total order on the members of the Smith set then voting cycles between candidates occur and the nodes are drawn inside a circle. The nodes inside the circle are drawn according to their candidate's score, where a candidate is drawn on a higher vertical position compared to another candidate if the former has score less or equal to the latter one.

The final step of our technique is edge drawing. Any edge of the graph represents the result of the pairwise comparison between two candidates. A directed edge is drawn as an arrow from candidate x to candidate y if and only if x beats y. If the result of the pairwise comparison between two candidates is a tie then an undirected edge is drawn as a dotted curve (or line). The edges (directed or undirected) are drawn using cubic Bézier curves, circular arcs or straight lines. The edge type depends on the position of the nodes as we try to find the best visual way to represent them. Specifically, the type of an edge is drawn according to the following guidelines, depending on whether the encompassing cluster is circular (i) or rectangular (ii). Case (i): If the nodes in the graph are close to each other then the edge is a circular arc that follows the perimeter of the cluster's circle, otherwise it is a cubic Bézier curve. Case (ii): If the nodes in the graph are close to each other then the edge is a straight line, otherwise it is a cubic Bézier curve.

The algorithm for the computation of the ECMG visualization is presented in Appendix (Algorithm 1). This algorithm resorts to procedure ComputeSmithSet for computing the Smith set on a given set of candidates, and to Algorithm 2 to draw the clusters of nodes (successive Smith sets). This latter algorithm in turn resorts to two procedures DrawNode and SortNode which are respectively in charge of drawing a circular node of a given diameter and color at given position, and to sort a list of candidates in descending order according to the ETSD score. An example of the ECMG for the aforementioned movie poll can be seen in Figure 1.C.

Experimental Evaluation

So as to perform the evaluation we have conducted an experiment comparing the aforementioned three visualization techniques. During the experiment different datasets were shown to the users using our visualization techniques. The users were then asked to make observations about the information they could extract. These observations have then been quantified using an insight-based method [START_REF] Saraiya | An insight-based methodology for evaluating bioinformatics visualizations[END_REF][START_REF] North | A comparison of benchmark task and insight evaluation methods for information visualization[END_REF]. We have used this method because a classical task-based evaluation methodology did not comply with the nature of the voting problem, and thus would have not properly evaluated the relevance of our technique.

Data Sets and Visualizations

In order to evaluate our technique we used data from three different voting polls. The data sets are the preference profiles for specific elections. The first data set was about a movie poll, where we asked people (voters) to rank their favorite movies (candidates) from the 70s and later. The preference profile can be seen in the appendix (Figure 2). The value (number) in the entry a i,j of the matrix gives the ranking of candidate j in the preference of voter i, e.g., voter "#2" ranks "The Shawshank Redemption" as her 8 th choice while "Forrest Gump" as her first choice.

The two other data sets are synthetic preference profiles: we chose a number of m candidates, assigned to them a probability distribution of being chosen, and then built N votes by sampling the candidates without replacement according to the probability distribution. This gives us random preferences, but with a bias that makes some candidates most likely to be at the beginning of the preferences, and thus most likely to be a Condorcet winner.

The results of the elections for the aforementioned polls were displayed using the proposed techniques, i.e, the Pairwise Comparison Matrix (Section 4.1), the Weighted Majority Graph (Section 4.2) and the Edge-Compressed Majority Graph (Section 4.3).

Participants and Protocol

In order to evaluate the visualization techniques we designed the following protocol for our experiment. It was conducted with six participants. None of them had any background in Social Choice nor in Voting Theory. The protocol consisted of three phases. In the first phase, a short tutorial of 15 minutes was given to the participants explaining all the necessary information in order for them to get familiar with the experimental setting. We started off with the analysis of the key aspects of Voting Theory, i.e., the voting problem and the Condorcet criterion, and then we presented a brief introduction of the three visualization techniques. In the second phase of our experiment, that lasted about 30 minutes, each user was given a specific poll from the data sets described above. The results of the poll were shown to the user with each of the three techniques one at a time in a random order. When the synthetic data sets were used, we changed the labels of the candidates when the new technique was shown so that the participants would not be biased about the data set that they had just previously seen. The users were instructed to look carefully at the techniques and report their observations (insights) with all the information they could extract out of the polls. When the users felt they could not gain any other information out of one technique we proceeded to the next one. We took notes during the session but also videotaped the whole procedure for later identification and analysis of all individual occurrences of insights. In the third and final phase of the experiment, the users were asked to make general comments about the techniques and to express their personal preference regarding the technique they found the most appropriate one for the data sets.

Results

In order to analyze the results of our experiment we have studied the insights gathered by the participants. We present our findings about the insight characteristics and the participants' general comments.

Evaluation on Insight Metrics

During our analysis we used various insight metrics which are summarized in Table 1 Insights We measured the total number of insights, i.e., the total number of observations about the information a user could extract. We used the following 4 categories (ranking, margin, comparisons, hypotheses) in order to categorize the insights and assigned specific domain value points for each category reflecting the importance of the information extracted. The insights regarding information about the ranking of the candidates, as well as the insights about the difference in the margin of victory/loss in terms of voters for a given pairwise comparison were given 1-2 points. The insights regarding information about the results of pairwise comparisons between candidates were given 3-4 points. More specifically, we gave 3 points if a single pairwise comparison was detected while 4 points were given for each pairwise comparison if multiple comparisons were spotted at a glance. Last, the insights regarding hypotheses and more critical remarks were given 5 points. For example, the most observed critical remark by the participants was the identification of Condorcet Paradox. Recall that the participants didn't have any background on voting theory but identified the cycle(s) between the candidates and speculated that there is no winner in this(ese) case. In conclusion, we noticed that the total number of insights is slightly greater in the ECMG compared to the PCM and both of these techniques have a huge difference with the WMG.

Categories of Insights

Given that the number of insights is fairly equal for the ECMG and the PCM techniques, a clearer conclusion can be made by looking at the insights per category. We can see that the number of insights for the ranking of candidates is approximately the same for all the techniques, as well as the number of insights regarding the margins. We see that the ECMG has a strong lead when compared to the other two techniques in the number of insights concerning the information about the pairwise comparisons. We can see that ECMG has 302 insights while PCM has 203 and WMG has 131. A similar pattern is also seen if we categorize the observations of pairwise comparisons into single or not. The 276 out of 302 comparisons observed with the ECMG were about multiple comparisons spotted at a glance while PCM had 189 and WMG 110. Regarding the number of hypotheses and the critical remarks, we notice that ECMG is much superior compared to the two other techniques (16 versus 7 and 5). Given the importance of the pairwise comparisons in the Voting Theory and the qualitative nature of the insight method it is clear that the ECMG technique outperforms the other two techniques when taking into account the categorization of the insights.

Domain Value

The domain value is critical in evaluating the techniques as it reflects (in a quantitative way) the quality of the observations. We use the aforementioned categorybased point system for measuring the quality of each insight, and sum up all the points in order to compute the total domain value. This quantification of the information extracted by the participants allows to take into account the significance of the pairwise comparisons and other principal elements of the Voting Theory. The ECMG technique achieved the highest score among all three techniques, i.e., 1310 points. The PCM comes second with a score of 950 points and the WMG technique performs the lowest score, reaching a total of 604 points. We can remark here that the differences between the scores of the techniques are significant and thus ECMG outperforms the other two techniques in terms of the total domain value.

Average Time of First Insight This metric measures the time that passes from the beginning of the session until the occurrence of the first insight made by the user. A shortest time on observing the first insight implies that participants are able to grab information quicker and thus have a shorter learning time. In 85% of the cases, the first insight that was made by the users was about the candidate who is the winner of the election. The participants needed half the time to observe the first insight when the ECMG technique was used in comparison with the WMG and almost a third of the time compared to the PCM. Given that a high percentage of the first insight is referring to a crucial information about the elections, we can imply that the ECMG technique is dominant over the other techniques regarding the time needed for the first data extraction.

Total Time and Insights per Minute When measuring time it is also important to measure the total time and the insights observed per minute. The total time measures the time needed for the participants to feel that they could not gain any further information out of the graph. Having the total time lower for one technique has two interpretations. The first is that the technique is more efficient because users needed less time to complete the extraction of information. The second is that users gave up because of lack of interest as they felt they could not gain any more information. The results reveal that the ECMG technique was faster and also produced more insights giving an average 52.8 insights per minute, while PCM had 44.4 and WMG had 32.5. After analyzing the results we conclude that ECMG is the most efficient technique from time perspective because time was less and despite that, more insights were found giving the technique the highest ratio of insights/minute.

Participant Comments on Visualization Techniques

In order to complete the evaluation of the visualization techniques we asked users to comment and express their opinion (positive or negative) according to the difficulties they encountered. At the end, the participants were asked to perform an evaluation on the techniques by ranking them and assigning a score according to their level of satisfaction. The findings for each technique are the following.

Pairwise Comparison Matrix

The PCM technique achieved a mean rating of 7.16/10 according to the preferences of the users, which ranks the technique second. The technique was the most preferable one according to one user, i.e., 16.7% of the users. A general comment made by most of the participants was that it is a good technique to show the results of single pairwise comparisons and the margins of difference but it is not good to see the Condorcet cycles. Most users said that it is a good way to visualize ranking. Generally most participants agreed that you can extract the same amount of information as in ECMG but you need longer time. There were some rare comments about the color degradation which caused difficulty in identifying the results of the pairwise comparisons when the margins of differences between the candidates were narrow. Lastly, one user did not find this technique as visually attractive as the other ones.

Weighted Majority Graph The WMG technique was the least preferable one as it was ranked third by all participants and scored a rating of 4.83/10. Most of the participants (83%) noticed that the presentation is unclear. They commented that it was complex to see the edges as they were crossing each other and it was also hard to distinguish the arrows on the candidates. Therefore they said that they needed time and concentration to figure out the pairwise comparisons. Another major criticism was about the ranking according to the extended Tideman's simplified Dodgson rule, which they found difficult to see.

Edge-Compressed Majority Graph

The ECMG technique was the best one according to all participants but one and acquired a mean score of 8.83/10. Regarding the ranking of the candidates according to extended Tideman's simplified Dodgson rule most users (83%) agreed that it was easy to detect, apart from one user who found it difficult to distinguish the ties in ranking. The great majority of the users (83%) found the technique as a natural and straightforward method for displaying the results of the pairwise comparisons between the candidates. In particular, they said that it is really clear to follow the fewer edges and the "up to down" layout of the graph. Also half of the users added that it was a nice technique for representing the voting cycles and the Condorcet paradox.

Discussion of Results

Overall, the results showed the superiority of the ECMG over the other techniques. The ECMG technique produced a slightly higher number of insights compared to the PCM but the insights were of higher value because they were mostly referring to pairwise comparisons and new hypotheses. ECMG had a mean domain value of 4.16 per insight while PCM had 3.13 and WMG had 2.77. This finding was also confirmed by the participants' comments about the visualization of comparisons in all three techniques. We found very promising that the hypotheses made by the users confirmed our initial expectations that the ECMG can provide an alternative method for interpreting the ranking, given the various discrepancies in voting rules. The experimental results revealed that the participants had the tendency to give their own rankings which sometimes were different from the extended Tideman's simplified rule ranking. Therefore, we think that, from a social point of view, someone can use our technique to obtain the ranking according to her assumptions and priorities given that voting rules can produce various rankings for the same poll. In this way we can confirm the expectation imposed at the beginning of our research that the ECMG is the intermediate step between the individual preferences and the collective ranking.

Furthermore ECMG was the only technique without any incorrect insights. It also had more than twice as many critical remarks and hypotheses than both PCM and WMG. Concerning time, the ECMG surpassed the other two techniques because it required less time for the first insight to be observed, and also less time in total while more insights were found. The time perspective is also widely acknowledged by the participants, who found ECMG the fastest way of observing the results. Finally, the participants' personal evaluation and ranking of all three techniques revealed the dominance of ECMG.

Conclusion and Future Work

In this paper, we have proposed three techniques for graphically representing the weighted majority graph of an election. Two of them, PCM and WMG, are classical visualization techniques for directed graphs. The last one, ECMG is original and based on edge-compression techniques. Experiments carried out with non specialist users show that the ECMG yields a lot more insights than the two other techniques, and hence that it is more efficient in providing information about the structure of the collective preference.

As future work, we plan to integrate the ECMG to the set of visualization proposed on the Whale 3 web application [START_REF] Bouveret | Whale 3[END_REF], so as to make it directly available to the users of this system. We also plan to investigate visualization techniques for other families of voting rules that are not based on pairwise comparisons. Another important challenge is to find interesting techniques that represent basic theorems and notions of Social Choice e.g., visualizing the discrepancies that occur for the same preference profile among different voting rules. if the graphical layout is empty then Algorithm 2

7:

draw the M G(S i ) on the top of the graphical layout Let C = C \ S i 12:

i ← i + 1

13:

end while 14: end procedure

  Fight Club The Matrix (Matrix) Forrest Gump Star Wars Pulp Fiction Schindler's List (La Liste de Schindler) The Lord of the Rings (Le Seigneur des anneaux) The Dark Knight (Le Chevalier Noir)

Figure 2 :C ← the set of candidates 3 :

 23 Figure 2: Preference Profile for the Movie poll.

8 : else 9 :

 89 draw the M G(S i ) on the graphical layout under M G(S i-1 )

Table 1 :

 1 and are thoroughly analyzed in the following paragraphs. Overview of the Results.

		PCM WMG ECMG
	Insights (total)	304	218	315
	Insight Categories
	Ranking	35	37	39
	Comparisons	203	131	302
	Margins	42	38
	Hypotheses/Remarks	7	5	16
	Inaccurate	3	4	0
	Domain Value	950	604	1310
	Avg. time of 1st insight (sec)	13	10	5
	Total time	6 : 51 6 : 43	5 : 58
	Participant's evaluation (out of 10) 7.16	4.83	8.83

In majority voting, each voter only votes for one candidate (her top one). The candidate receiving the highest number of votes wins the election.

Note that using Tideman's would lead to the same ranking as the Td . We prefer to use the latter rule because it is a Dodgson-approximation and thus preserves the characteristics of Dodgson's rule (e.g., the proximity of candidates to becoming Condorcet winners). Td has the advantage over Dodgson's that it is polynomial and satisfies a lot of well-known social choice properties, like monotonicity and homogeneity.

Recall that the order of the members in the Smith set is done according to their score.

We use ETSD rule to compute the score.

Appendix

The preference profile for the movie poll The data set used in the following figures is the movie poll data set described in Section 5.1 and depicted in the following figure 2. In this election setting we have 22 voters with each one having a numerical id and 10 candidates corresponding to the movies.

Algorithm 2 Majority graph visualization