Marta Oliveira

Caroline Sprengel Lima

Setha Ketavong

Eulogio J Llorent-Martínez

Hervé Hoste

Luísa Custódio
email: lcustodio@ualg.pt

Disclosing the bioactive metabolites involved in the in vitro anthelmintic effects of salt-tolerant plants through a combined approach using PVPP and HPLC-ESI-MSn

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Sample preparation. Dried ground samples were extracted with an 80% aqueous acetone solution (1:40, w/v), as previously used for the successful extraction of phenolic compounds and tannins from different salt-tolerant species [START_REF] Jallali | Variability of antioxidant and antibacterial effects of essential oils and acetonic extracts of two edible halophytes: Crithmum maritimum L. and Inula crithmoiides L[END_REF] , at 20-25 °C, for 16 h, under stirring. Afterwards, the residue was filtered using a qualitative filter (Whatman nº 4), and acetone was removed using a rotary evaporator under reduced pressure and temperature (approximately 40 °C). The residue was later freeze-dried and recovered to be used in the in vitro anthelmintic assays.

Phenolic content of the extracts. Total phenolic content (TPC).

The TPC of the extracts was estimated using the Folin-Ciocalteau (F-C) reagent [START_REF] Singleton | Colorimetry of total phenolics with phosphomolybdic-phosphotungstic acid reagents[END_REF] . Briefly, 5 µL of the extracts (10 mg mL -1 ) were added with 100 µL of the F-C reagent (1:10 in water, v/v) in 96-well plates, and left for 10 min at 20-25 °C, protected from light. After, it was added 100 µL of sodium carbonate (75 g L -1 , in water) and the plate incubated for 90 min in the dark. Absorbance was measured at 725 nm in a multiplate spectrophotometer reader (Biotek Synergy 4). A calibration curve was prepared using gallic acid as a standard. TPC was expressed as gallic acid equivalents (GAE; mg GAE g extract -1 , dry weight (DW)).

Total flavonoid content (TFC). TFC was determined by the aluminum chloride (AlCl 3 ) method [START_REF] Quettier-Deleu | Phenolic compounds and antioxidant activities of buckwheat (Fagopyrum esculentum Moench) hulls and flour[END_REF] , by mixing 50 µL of the extracts at 10 mg mL -1 with 50 µL of 2% AlCl 3 in methanol and left to incubate for 10 min at 20-25 °C Absorbance was measured at 415 nm in a multiplate spectrophotometer reader. A calibration curve was prepared using quercetin as a standard. TFC was expressed as quercetin equivalents (QE; mg QE g extract -1 , DW).

Condensed tannins content (CTC). CTC was evaluated by the 4-dimethylaminocinnamaldehyde-hydrochloric acid (DMACA-HCl) colorimetric method [START_REF] Li | The DMACA-HC1 protocol and the threshold proanthocyanidin content for bloat safety in forage legumes[END_REF] adapted to 96-well microplates [START_REF] Rodrigues | Unravelling the antioxidant potential and the phenolic composition of different anatomical organs of the marine halophyte Limonium algarvense[END_REF] . Ten microliters of the extracts (10 mg mL -1 ) were mixed with 200 µL of a methanol solution of DMACA (1%, w/v), and 100 µL of hydrochloric acid (37%, v/v). After a 15 min incubation period, absorbance was measured at 640 nm in a multiplate spectrophotometer reader. A calibration curve was prepared using catechin as a standard. The concentration of CT was expressed as catechin equivalents (mg CE g extract -1 , DW).

Chemical profiling by high-performance liquid chromatography with electrospray ionization mass spectrometric detection (HPLC-ESI-MS n

). HPLC-ESI-MS n analyses were performed with an Agilent Series 1100 HPLC system with a G1315B diode array detector (Agilent Technologies), and an ion trap mass spectrometer (Esquire 6000, Bruker Daltonics) with an electrospray interface. Separation was performed in a Luna Omega Polar C 18 analytical column (150 × 3.0 mm; 5 µm particle size) with a Polar C 18 Security Guard cartridge (4 × 3.0 mm), both purchased from Phenomenex. Detailed chromatographic conditions are available in Supplementary Material files. Compounds' identification was performed by mass spectrometry data. Compounds' quantitation was carried out by UV using analytical standards of neochlorogenic acid (320 nm), chlorogenic acid (320 nm), protocatechuic acid (280 nm), catechin (280 nm), sinapic acid (320 nm), ferulic acid (320 nm), quercetin (350 nm), apigenin (350 nm), and kaempferol (350 nm). Detection limits (3σ criterion) ranged between 0.06 and 0.15 mg L -1 . Calibration graphs were constructed in the 0.5-100 mg L -1 range. Peak areas at the corresponding wavelengths were plotted versus analyte concentration. Each analytical standard was used to quantify the corresponding compounds or compounds of the same chemical family for which the exact analytical standards were not available. Repeatability (n = 10) and intermediate precision (n = 9, three consecutive days) were lower than 4 and 8%, respectively. The robustness of the chromatographic method was evaluated by recording analyte signals at ± 2 nm of the optimum wavelength and by slightly varying the percentage of the mobile phase (2% changes), observing variations lower than 5% for all the analytes concerning the optimum conditions.

In vitro anthelmintic assays. Haemonchus contortus and Trichostrongylus colubriformis parasites. Thirdstage larvae (L3) and eggs were obtained from faeces of monospecifically infected caprine and ovine donors, with susceptible strains of H. contortus and T. colubriformis. L3 larvae had been maintained in culture flasks for 1 month, at 4 °C, before use in the Larval Exsheathment Inhibition Assay (LEIA), while eggs were collected on the day of the Egg Hatching Inhibition Assay (EHIA), and used up to 2 h after collection [START_REF] Jackson | In vitro methods for the primary screening of plant products for direct activity against ruminant gastrointestinal nematodes[END_REF] .

LEIA. LEIA was performed as previously described by Bahuaud and colleagues [START_REF] Bahuaud | Effects of four tanniferous plant extracts on the in vitro exsheathment of third-stage larvae of parasitic nematodes[END_REF] . The extracts were diluted in phosphate-buffered saline (PBS; 0.1 M phosphate, 0.05 M NaCl, pH 7.2), and incubated with L3 larvae (approx. 800 larvae per mL) at 23 °C for 3 h. Afterwards, larvae were washed and centrifuged with PBS 3 times, and the pellet resuspended in 200 µL of PBS. To initiate the LEIA, 40 µL of the test solution was used to count the proportion of ensheathed/exsheathed larvae at 0 min. The remaining larvae (160 µL) were then subjected to an artificially induced exsheathment by exposure to a solution of Milton (2% w/v sodium hypochlorite, 16.5% w/v sodium chloride) diluted in PBS. Milton optimal concentration was determined for each batch before use in order to ensure a gradual exhsheathment process, reaching 100% exsheathment in 60 min. After 20, 40, and 60 min exposure, the number of ensheathed and exsheathed larvae were counted under a microscope (400×). Four replicates were performed for each extract concentration, and the negative control, PBS, was run in parallel. Percentage of larvae exsheathment (LE) for each replicate was calculated according to the following formula: %LE = [(number of exsheathed larvae)/(number of exsheathed + ensheathed larvae) × 100].

EHIA. Faeces material was filtrated using a gaze hydrophyle compress for 2 times, transferred to a 25 µm sieve, and washed with distilled water. The residue was centrifuged three times using a saline saturated solution (d = 1.2) to concentrate the eggs, and the pellets were recovered in PBS for use in the experiments. Afterwards, the eggs were quantified, plated in 48-well sterile plates (100 eggs per well), and exposed to the extracts at concentrations ranging from 5000 to 78 µg mL -1 in PBS. Plates were incubated at 27 °C for 48 h in the dark, and the number of larvae and eggs, in each well, was registered after microscopic counting. Six replicates were performed for each extract concentration, and the negative PBS control was run in parallel. The percentage of egg hatching Polyvinylpolypyrrolidone (PVPP) treatment. PVPP is a polyphenol inhibitor that binds to tannins and flavonoids, removing these metabolites from the solution [START_REF] Doner | Binding of flavonoids by polyvinylpolypyrrolidone[END_REF] . To ascertain the role of the polyphenols in the anthelmintic activity of the extracts, PVPP was added at a ratio of 50:1 to the active ones, respectively for eggs and larvae assays, in PBS, and incubated overnight at 4 °C. The maximum concentration tested for LEIA was 1200 µg mL -1 ; for EHIA it was 2500 µg mL -1 . Thereafter, the samples were centrifuged for 10 min at 4500 rpm, and the supernatant depleted in polyphenols was tested in LEIA and EHIA assays. The extracts exposed or not to PVPP plus a negative control (PBS) were run in parallel.

Statistical analyses.

At least four replicates per concentration were included in all experiments. The results on phenolic content are expressed as mean ± standard error of the mean (SEM). Anthelmintic data are expressed as the concentrations inhibiting 50% of larval exsheathment or egg hatching (IC 50 values, µg mL -1 ), and 95% confidence intervals (CI), obtained by Probit analysis. SPSS Statistics v. 26.0 software was used to assess significant differences among IC 50 values, through relative median potency estimates, and among phenolic data, by one-way analysis of variance (ANOVA) followed by the post-hoc Tukey HSD test. Spearman correlations were calculated between the total flavonoids, total phenols, and the IC 50 values for LEIA on the 2 nematode species.

Results and discussion

Total phenolics, total flavonoids and condensed tannins contents. The phenolic contents of the extracts are presented in Table 2. The phenolic content of the extracts is presented in Table 2. The total phenolic content of all species ranged between 14.2 and 226.3 mg GAE eq. g -1 DW extract while the total flavonoid content ranged between 13.3 and 45.4 mg QE g -1 DW. Lopes and colleagues (2016) reported higher TPC values for C. mariscus (254 mg GAE g -1 DW), C. soldanela (144 mg GAE g -1 DW), I. crithmoides (141 mg GAE g -1 DW), L. monopetalum (248 mg GAE g -1 DW) 80% acetone water extracts, except for P. lentiscus (130 mg g -1 DW), but lower flavonoid contents in comparison to our work (1.26-13.8 mg rutin g -1 DW) [START_REF] Lopes | Natural products from extreme marine environments: Searching for potential industrial uses within extremophile plants[END_REF] . In another work, H. italicum picardi infusions and decoctions of aerial organs have been previously described as rich sources of flavonoids (91.8-119 mg rutin 200 mL -1 ) [START_REF] Pereira | Chemical profiling of infusions and decoctions of Helichrysum italicum subsp. picardii by UHPLC-PDA-MS and in vitro biological activities comparatively with green tea (Camellia sinensis) and rooibos tisane (Aspalathus linearis)[END_REF] . Moreover, a lower combined TPC value was detected in P. coronopus leaves and flowers extracts of different polarities (72.1 mg GAE g -1 DW) but increased TFC levels (282.8 mg rutin g -1 DW) [START_REF] Pereira | Profiling of antioxidant potential and phytoconstituents of Plantago coronopus[END_REF] . In this study, total condensed tannins were detected only in three species, in the following concentration order: P. lentiscus > L. monopetalum > C. mariscus. In agreement, tannins were formerly detected in the same three formerly mentioned species, although at lower concentrations (6.63-38.7 mg CE g -1 DW, extract) [START_REF] Lopes | Natural products from extreme marine environments: Searching for potential industrial uses within extremophile plants[END_REF] . It is worth to mention that dissimilarities between our results and those of other authors may be the reflection of different extraction methodologies and standards employed as well as environmental and plant-related factors.

In vitro anthelmintic properties. ) and egg hatching processes (IC 50 = 197.7 and 223.9 µg mL -1 ), without significant differences between GIN species.

Lentisk is an evergreen shrub with high polyphenol content and previous results have shown both in vitro and in vivo anthelmintic properties [START_REF] Manolaraki | Anthelmintic activity of some Mediterranean browse plants against parasitic nematodes[END_REF][START_REF] Landau | Anthelmintic activity of Pistacia lentiscus foliage in two Middle Eastern breeds of goats differing in their propensity to consume tannin-rich browse[END_REF][START_REF] Azaizeh | Polyphenols from Pistacia lentiscus and Phillyrea latifolia impair the exsheathment of gastro-intestinal nematode larvae[END_REF][START_REF] Azaizeh | Seasonal variation in the effects of Mediterranean plant extracts on the exsheathment kinetics of goat gastrointestinal nematode larvae[END_REF] . In previous studies, P. lentiscus extracts (acetone, ethanol and/or water) exhibited less than 20% larvae exsheathment and migration at 1200 µg mL -129,31 . Nevertheless, the results for the in vitro egg hatching assay are herein, to the best of our knowledge, described for the first time.

Table 2. Phenolic content of acetone water extracts of selected plant species. n.d. not detected, TPC total phenolic content, expressed as mg gallic acid equivalents g -1 extract (mg GAE g -1 , DW), TFC total flavonoid content, expressed as mg quercetin equivalents g -1 extract (mg QE g -1 , DW), CTC condensed tannins content, expressed as mg catechin equivalents g -1 extract (mg CE g -1 , DW). Values are expressed as mean with standard deviation of the mean represented. *Data published in [START_REF] Oliveira | Seasonal variations of the nutritive value and phytotherapeutic potential of Cladium mariscus L. (Pohl.) targeting rumintant's production[END_REF] . Different letters superscript represent significant differences among species, for each assay (p < 0.05; Tukey HSD). Crucianella maritima 25.5 ± 0.9 g 20.4 ± 0.2 e n.d.

Following P. lentiscus, L. monopetalum, C. mariscus and H. italicum. picardi extracts exhibited the most promising results towards both GIN species and life stages (Table 3). Limoniastrum monopetalum is a highly salttolerant shrub, widely distributed in the Mediterranean area, and was as effective as P. lentiscus in LEIA (p < 0.05), with IC 50 values lower than 50 µg mL -1 (no significant difference between the two tested parasites; p > 0.05). In EHIA, L. monopetalum was also the most active species, besides P. lentiscus, with similar activity towards both parasites (IC 50 = 1999.9 and 2102.5 µg mL -1 , respectively). Cladium mariscus, or sawgrass, is an evergreen grasslike plant occurring in coastal saltmarshes in the Mediterranean region. C. mariscus extract inhibited L3 larvae exsheathment (IC 50 = 77.8-88.9 µg mL -1 ), without significant differences between both parasite species (p > 0.05). In contrast, in the EHIA, C. mariscus was more effective towards H. contortus (IC 50 = 1496.6 µg mL -1 ) than T. colubriformis (IC 50 = 2575.5 µg mL -1 ; p < 0.05). Helichrysum italicum subsp. picardi (everlasting) is an aromatic salt tolerant plant commonly found in sandy soils, such as sand dunes, along the Southern European coast. Everlasting extract exhibited IC 50 values ranging between 92.8-132.5 µg mL -1 on LEIA, and 2947.7-3707.5 µg mL -1 on EHIA. Interestingly, H. contortus larvae and eggs were more susceptible to the H. italicum picardi extract than those of T. colubriformis (p < 0.05).

It is well recognized that the anthelmintic activity is affected by the class, structure and concentration of secondary metabolites [START_REF] Hoste | Tannin containing legumes as a model for nutraceuticals against digestive parasites in livestock[END_REF] . Moreover, these metabolites have different effects, depending on the target parasite species and life development stages [START_REF] Hoste | Tannin containing legumes as a model for nutraceuticals against digestive parasites in livestock[END_REF] . A higher susceptibility of H. contortus in comparison to T. colubriformis, as observed for C. mariscus and H. italicum picardi extracts, has been previously documented for other bioactive plants, such as sainfoin, and individual chemical structures, depending on the ratios of prodelphinidins/procyanidins [START_REF] Paolini | In vitro effects of three woody plant and sainfoin on thrid-stage larvae and adult worms of three gastrointestinal nematodes[END_REF][START_REF] Brunet | Monomers of condensed tannins affect the larval exsheathment of parasitic nematodes of ruminants[END_REF][START_REF] Quijada | Anthelmintic activities against Haemonchus contortus or Trichostrongylus colubriformis from small ruminants are influenced by structural features of condensed tannins[END_REF] . The authors suggest that such differences can reflect dissimilarities on the composition of specific parasite sheath proteins, that interact differently with the chemical groups [START_REF] Brunet | Monomers of condensed tannins affect the larval exsheathment of parasitic nematodes of ruminants[END_REF][START_REF] Quijada | Anthelmintic activities against Haemonchus contortus or Trichostrongylus colubriformis from small ruminants are influenced by structural features of condensed tannins[END_REF] . The same conclusion can be driven for differences among parasite stages, as the eggshell and larvae coat differ in their structural components, which has also been recorded with conventional anthelmintic drugs [START_REF] Hoste | Tannin containing legumes as a model for nutraceuticals against digestive parasites in livestock[END_REF][START_REF] Mansfield | Characterization of the eggshell of Haemonchus contortus-I. Structural components[END_REF] . This may explain the results obtained for P. coronopus, which was more active against larvae exsheathment (IC 50 = 94.0 and 212.4 µg mL -1 ), and inactive towards eggs, of both parasite species, at the maximum concentration tested. Overall, IC 50 results obtained in LEIA are frequently reported as lower than EHA, suggesting that infective L3 larvae are more susceptible than eggs [START_REF] Oliveira | Anthelmintic activity of plant extracts from Brazilian savana[END_REF][START_REF] Zabré | Comparison of the in vitro anthelmintic effects of Acacia nilotica and Acacia raddiana[END_REF] .

Calystegia soldanella, C. maritima and M. marina co-occur in sand dunes along the Algarve coastline while I. crithmoides can be found in highly saline environments, such as saltmarshes. These four species were mildly to poorly active on both assays (Table 3). Interestingly, while I. crithmoides was mostly ineffective in this study, its related species, I. viscosa 70% ethanolic extract exhibit anthelmintic properties against the larvae exsheathment of a mixture of Teladorsagia circumcincta and T. colubriformis parasites [START_REF] Azaizeh | Seasonal variation in the effects of Mediterranean plant extracts on the exsheathment kinetics of goat gastrointestinal nematode larvae[END_REF] , suggesting significant chemical diversity among the genus.

Overall, the nine plant extracts had comparable effects between the two GIN species (Spearmen correlation; R 2 = 0.96; p < 0.01). In addition, a negative correlation between the total phenolic content and the anthelmintic activity was noted, particularly with H. contortus parasites (Spearmen correlation; R 2 = 0.783; p < 0.05), suggesting that these metabolites may be involved in the anti-parasitic nematode's effects.

Role of polyphenols in the anthelmintic activity: PVPP as a polyphenol binding agent.

In order to ascertain the role of polyphenols in the anthelmintic properties, the four plant extracts presenting results for both LEIA and EHIA were selected for further studies using PVPP. PVPP is a polyphenol inhibitor, as it binds to tannins and flavonoids, removing these metabolites from the solution [START_REF] Doner | Binding of flavonoids by polyvinylpolypyrrolidone[END_REF] . Thus, if after PVPP exposure a loss of the anthelmintic activity is observed, it can be assumed that polyphenols are most probably responsible for the activity once they were formerly removed.

The effects of the addition of PVPP to extracts on EHIA and LEIA are illustrated in Figs. 2 and3, respectively. The application of all the extracts with PVPP largely restored the egg hatching process (Fig. 2) to control values, suggesting that polyphenols are most probably involved in the inhibition of this life stage development. Vargas-Magaña and colleagues (2014), while exploring the role of polyphenols on the anthelmintic effects of several extracts of tannin-containing tropical plants on EHIA, concluded that the main mechanism of action was by impairing larvae eclosion from the eggs [START_REF] Vargas-Magaña | Anthelmintic activity of acetone-water extracts against Haemonchus contortus eggs: Interactions between tannins and other plant secondary compounds[END_REF] . Likewise, we noted a high number of larvae trapped inside the eggs after the application of these active extracts (data not shown).

In contrast to EHIA, results with PVPP varied on LEIA (Fig. 3): the application of the L. monopetalum extract, resulted in 60-70% of larvae exsheathment of both parasite species after PVPP addition for 60 min, in contrast to 0% in the non-treated sample; the extract from H. italicum picardi pre-incubated with PVPP remained mostly completely active. Subtle changes were observed for C. mariscus (approx. 20-40% of larvae exsheathment after 60 min of treatment) for both parasite species, while P. lentiscus had only around 20% of larvae exsheathment at 60 min, after PVPP treatment. These results suggest that other bioactive metabolites, alone or in synergy, can be present in all extracts tested, especially for H. italicum picardi, P. lentiscus, and C. mariscus. In agreement with our results, other authors already reported that P. lentiscus extracts remain active on GIN larvae migration after exposure to PVPP [START_REF] Manolaraki | Anthelmintic activity of some Mediterranean browse plants against parasitic nematodes[END_REF] .

The remaining activity on LEIA for the majority of the extracts tested should be carefully analyzed, and two scientific questions arise. First, was the ratio of PVPP used insufficient to cope with the high phenolic content of the extracts? Despite being commonly used, Manoloraki et al. (2010) questioned this hypothesis when testing P. lentiscus for larvae migration after PVPP addition, since this species has a high polyphenol content, comparable to our results [START_REF] Manolaraki | Anthelmintic activity of some Mediterranean browse plants against parasitic nematodes[END_REF] . On the other hand, are other bioactive metabolites present in the extracts that are also effective in inhibiting larvae exsheathment? For instance, different authors suggest that terpenes may be responsible for the remaining in vitro and in vivo anthelmintic properties of P. lentiscus after the addition of PVPP or polyethylene glycol (PEG), a similar inhibitor of polyphenols [START_REF] Manolaraki | Anthelmintic activity of some Mediterranean browse plants against parasitic nematodes[END_REF][START_REF] Landau | Anthelmintic activity of Pistacia lentiscus foliage in two Middle Eastern breeds of goats differing in their propensity to consume tannin-rich browse[END_REF] . Additionally, Botura and colleagues (2013) described that the flavonoid fraction of Agave sisalana Perrine (sisal) had higher activity on egg hatching, while the saponin fraction had mostly larvicidal effects [START_REF] Botura | In vitro ovicidal and larvicidal activity of Agave sisalana Perr. (sisal) on gastrointestinal nematodes of goats[END_REF] . In an attempt to address these scientific questions, and elucidate the possible metabolites involved, we have conducted an HPLC-ESI-MS n comparative analysis on the active samples, before and after PVPP treatment.

HPLC-ESI-MS n comparative analysis of the chemical profile of non-treated and treated-PVPP samples. The HPLC-ESI-MS n analysis was performed in the most active extracts, with and without PVPP.

Obtained chromatograms are represented in Fig. 4 while the chemical profile of each species is depicted in Tables 4,5, 6 and 7. The characterization of the compounds is detailed in Supplementary Material files.

The main constituents of P. lentiscus extract were flavonoid glycosides (mainly from myricetin and quercetin; approx. 53 mg g -1 DW), and galloylquinic acid and di-O-galloylquinic acid isomers (60 mg g -1 DW; Table 4; Suppl. files, Table I). In agreement to our findings, Romani et al. (2002) detected a high concentration of galloyl derivatives (5.3% DW), and a substantial amount of myricetin and quercetin glycosides (1.5% DW), extracted from a 70% ethanol solution of leaves [START_REF] Romani | Identification and quantification of galloyl derivatives, flavonoid glycosides and anthocyanins in leaves of Pistacia lentiscus L[END_REF] . Hydrolysable tannins are a group of gallic acid esters associated with polyols (e.g., glucose, glucitol, quinic acid), and the etherification or oxidation of the galloyl groups leads to the formation of complex structures (gallotannins and ellagitannins) [START_REF] Castañeda | A gallotannin-rich fraction from Caesalpinia spinosa (Molina) Kuntze displays cytotoxic activity and raises sensitivity to doxorubicin in a leukemia cell line[END_REF] . Plant extracts containing hydrolysable tannins with gallic acid units were more effective as anthelmintics than those containing condensed tannins [START_REF] Katiki | Anthelmintic effect of plant extracts containing condensed and hydrolyzable tannins on Caenorhabditis elegans, and their antioxidant capacity[END_REF] . Nevertheless, the oligomerization and molecular weight of tannins may affect the anthelmintic activity, as is the case, for example, of elagitannins and condensed tannins [START_REF] Quijada | Anthelmintic activities against Haemonchus contortus or Trichostrongylus colubriformis from small ruminants are influenced by structural features of condensed tannins[END_REF][START_REF] Karonen | Ellagitannins inhibit the exsheathment of Haemonchus contortus and Trichostrongylus colubriformis larvae: The efficiency increases together with the molecular size[END_REF] . Other metabolites present in lower concentrations in P. lentiscus extract with reported anthelmintic effects include flavan-3-ols and its galloyl derivatives, namely epigallocatechin (6.4 mg g -1 DW), gallocatechin gallate (6.8 mg g -1 DW) and catechin (5.0 mg g -1 DW). Molan et al. (2003) found that the presence of the galloyl group on flavan-3-ols was crucial for the activity on T. colubrifomis egg hatching (20% vs. 100% inhibition at 1 mg mL -1 ), and also more effective on immobilizing infective larvae (100% inhibition at 100-150 µg mL -1 ) [START_REF] Molan | Effect of flavan-3-ols on in vitro egg hatching, larval development and viability of infective larvae of Trichostrongylus colubriformis[END_REF] .

In P. lentiscus PVPP-treated samples, the concentration of flavonoid glycosides (0.17 mg g -1 DW) and galloylquinic acid (2.2 mg g -1 DW) drastically dropped (Suppl. files, Table I), which may justify the restoration of the egg hatching. On the other hand, the presence of these compounds in lower concentrations may explain the remaining activity on larvae. Nevertheless, compounds 2, 58, and 78 remained in this sample, and may also account for the activity.

Caffeoylquinic and dicaffeoylquinic acids were the most abundant compounds in H. italicum picardi extract (150 mg g -1 DW), followed by quercetin-O-glucosides (approx. 31 mg g -1 DW; Table 5; Suppl. files, Table II). These findings were expected, since previous works identified high contents of these metabolites in aerial organs of the same species [START_REF] Pereira | Chemical profiling of infusions and decoctions of Helichrysum italicum subsp. picardii by UHPLC-PDA-MS and in vitro biological activities comparatively with green tea (Camellia sinensis) and rooibos tisane (Aspalathus linearis)[END_REF][START_REF] Gonçalves | Phenolic profile, antioxidant activity and enzyme inhibitory activities of extracts from aromatic plants used in Mediterranean diet[END_REF] . Borges and colleagues (2019) found a significant correlation between the phenylpropanoid content (particularly chlorogenic acid, 1,3-dicaffeoylquinic, and 3,5-dicaffeoylquinic acids), and the ovicidal activity of 17 plant extracts from Pantanal wetlands against Haemonchus placei [START_REF] Borges | Discovery of potential ovicidal natural products using metabolomics[END_REF] . Additionally, chlorogenic acid exhibited an IC 50 value of 92.4 μg mL -1 against L3 larvae exsheathment of H. contortus, and was also effective on preventing larvae hatching from eggs (IC 50 = 520.8 μg mL -1 ) [START_REF] Mancilla-Montelongo | Evaluation of cinnamic acid and six analogues against eggs and larvae of Haemonchus contortus[END_REF] . These results point out the potential of caffeoylquinic and dicaffeoylquinic acids to be the active metabolites of H. italicum picardi extracts. However, some O-glycosides are also present that may contribute to the detected activity. For example, Barrau and colleagues (2005) tested the activity of 3 flavonol glycosides (quercetin-3-O-rutinoside or rutin, kaempferol-3-rutinoside or nicotiflorin, and isorhamnetin-3-rutinoside or narcissin), and all reduced the migration of H. contortus L3 larvae in 25-35% when applied at 1200 µg mL -148 .

In H. italicum picardi PVPP-treated sample, although in lower concentrations, caffeoylquinic and dicaffeoylquinic acids remained in solution (8.3 mg g -1 DW), from which chlorogenic acid was the main compound (6.3 mg g -1 DW; Suppl. files, Table II). The high activity observed for the extract from H. italicum picardi treated with PVPP on larvae exsheathment is most likely due to the high content of chlorogenic acid remaining in the sample [START_REF] Mancilla-Montelongo | Evaluation of cinnamic acid and six analogues against eggs and larvae of Haemonchus contortus[END_REF] . Still, other caffeoylquinic and dicaffeoylquinic acids are present (2 mg g -1 DW) that might also add to its effects. On the other hand, in EHIA the lower amount of these compounds in the PVPP-treated sample may have not be sufficient to inhibit egg hatching, since this process was completely restored. In fact, Borges and colleagues (2019) suggest that the concentration of monomeric and dimeric chlorogenic acid derivatives that enter in contact with eggs seems to be determinant for the activity, as observed for Melanthera latifolia ethanolic extract that had low concentrations of these compounds. and was considered inactive (up to 80% egg hatching at 50 mg mL -1 ) [START_REF] Borges | Discovery of potential ovicidal natural products using metabolomics[END_REF] .

Cladium mariscus acetone water extracts were previously reported as a rich source of polyphenols, particularly tannins by spectrophotometric methods, and chlorogenic, ferulic, and syringic acids were detected in higher amounts, through HPLC-DAD analysis [START_REF] Lopes | Natural products from extreme marine environments: Searching for potential industrial uses within extremophile plants[END_REF][START_REF] Oliveira | Seasonal variations of the nutritive value and phytotherapeutic potential of Cladium mariscus L. (Pohl.) targeting rumintant's production[END_REF] . In agreement, in this study, C. mariscus extract was mainly composed of flavan-3-ols (epigallocatechin, catechin), proanthocyanidins (5.1 mg g -1 DW), luteolin, C-glycosyl luteolin, a kaempferol glucoside, and an apigenin flavone (9.5 mg g -1 DW; Table 6; Suppl. files, Table III). Flavan-3-ols and proanthocyanidins have well recognized anthelmintic effects [START_REF] Molan | Effect of flavan-3-ols on in vitro egg hatching, larval development and viability of infective larvae of Trichostrongylus colubriformis[END_REF][START_REF] Molan | Green tea flavan-3-ols and oligomeric proanthocyanidins inhibit the motility of infective larvae of Teladorsagia circumcincta and Trichostrongylus colubriformis in vitro[END_REF] , and therefore, they are most likely involved in the activity of C. mariscus extract. Also, the activity of the flavonoid luteolin on H. contortus larvae exsheathment has been previously established (IC 50 = 17.1 and < 71.5 µM) [START_REF] Klongsiriwet | Synergistic inhibition of Haemonchus contortus exsheathment by flavonoid monomers and condensed tannins[END_REF] . Interestingly, Klongsiriwet and colleagues (2015) found that luteolin, even at low concentrations (30 μM), display synergistic effects with procyanidins, leading to a fivefold lower IC 50 of the mixture in comparison to the procyanidin fraction alone (75.9 vs. 356 μg mL -1 ) [START_REF] Klongsiriwet | Synergistic inhibition of Haemonchus contortus exsheathment by flavonoid monomers and condensed tannins[END_REF] . www.nature.com/scientificreports/ investigation of the anthelmintic properties of its glycosides is lacking. In general, C-glycosyl flavones exhibit antioxidant and anti-inflammatory properties [START_REF] Zeng | Advances in studying of the pharmacological activities and structure-activity relationships of natural C-glycosylflavonoids[END_REF] , and two flavone-C-glycosides namely isoschaftoside and schaftoside shown strong toxicity (LC 50 = 114.66 μg mL -1 and 323.09 μg mL -1 ) against the plant-parasitic nematode Meloidogyne incognita [START_REF] Du | Nematocidal flavone-C-glycosides against the root-knot nematode (Meloidogyne incognita) from Arisaema erubescens tubers[END_REF] . Moreover, it is worth noticing that compounds 20 and 39 are still unidentified, although present in PVPP-treated samples. Previous works identified several phenolic compounds in L. monopetalum extracts including gallic, vanillic, ferulic, syringic, p-hydroxybenzoic, protocatechuic, chlorogenic, and trans-cinnamic acids, and also quercetin, apigenin, amentoflavone, flavones, methyl gallate, and myricetin [START_REF] Trabelsi | Solvent effects on phenolic contents and biological activities of the halophyte Limoniastrum monopetalum leaves[END_REF][START_REF] Bouzidi | Limoniastrum monopetalum stems as a new source of natural colorant for dyeing wool fabrics[END_REF] . In the current work, the main metabolites identified in L. monopetalum extract were epigallocatechin, phenolic acids and derivatives, isorhamnetin sulfate, pinoresinol, methylated flavonoids sulfate and two oxylipins (Table 7). However, some of the major compounds, namely the methylated flavonoids sulfate 67, 71, 76, and 80 were not identified, as well as the minor metabolites 33, 46, and 55. The production of sulfated metabolites by plants is pointed out as an evolutionary trait to thrive in aquatic saline habitats, and part of the plant heavy metal detoxification mechanism [START_REF] Aquino | Rising from the sea: Correlations between sulfated polysaccharides and salinity in plants[END_REF][START_REF] Cambrollé | Evaluation of zinc tolerance and accumulation potential of the coastal shrub Limoniastrum monopetalum (L.) Boiss[END_REF] . Indeed, L. monopetalum is a halophytic and metal accumulator shrub that thrives in saltmarshes under harsh biotic and abiotic stresses (e.g., tidal fluctuations, salinity, heavy metal soils, sunlight exposure, UV radiation). Sulfated phenolics were previously identified in other halophyte species, such as Limonium caspium (Willd.) Gams [START_REF] Gadetskaya | Sulfated phenolic compounds from Limonium caspium: Isolation, structural elucidation, and biological evaluation[END_REF] and Halimione portucaloides (L.) Aellen [START_REF] Vilela | Screening of lipophilic and phenolic extractives from different morphological parts of Halimione portulacoides[END_REF] . The pharmacological interest in sulphated flavonoids increased in the last decades, mainly driven by its hydrophobic nature, and many reported biological activities, like anti-coagulant, anti-viral, antioxidant, anti-inflammatory, antimicrobial [START_REF] Correia-Da-Silva | Emerging sulfated flavonoids and other polyphenols as drugs: Nature as an inspiration[END_REF] .

Besides epigallocatechin (9.46 mg g -1 DW), the concentration of isorhamnetin sulfate (65) was high in L. monopetalum (6.4 mg g -1 DW) as well as phenolic acids and its derivatives (10.3 mg mL -1 DW; 7, 16, 24, 32). Delgado-Nuñez and colleagues (2020) attributed the main anthelmintic effects of Prosopis laevigata Willd. M. Johnston to isorhamnetin, which caused 100% of mortality on H. contortus eggs at the lowest concentration tested (700 µg mL -1 ), being also effective towards larvae (IC 50 = 2.07 mg mL -1 ) [START_REF] Delgado-Núñez | Isorhamnetin: A nematocidal flavonoid from Prosopis laevigata leaves against Haemonchus contortus eggs and larvae[END_REF] . The glycoside isorhamnetin-3-rutinoside decreased H. contortus L3 migration by 35% at 120 µg mL -148 . However, the activity of its sulfate structure is not reported. Among different classes of phenolic compounds, phenolic acids (i.e., caffeic acid, ferulic acid, and gallic acid) were the most potent anthelmintic metabolites against both H. contortus egg hatching (IC 50 values = 0.56-4.93 µg mL -1 ) and larval development (IC 50 = 22-33 µg mL -1 ) [START_REF] Sprengel Lima | Anthelmintic effect of Pterogyne nitens (Fabaceae) on eggs and larvae of Haemonchus contortus: Analyses of structure-activity relationships based on phenolic compounds[END_REF] . Nevertheless, one should keep in mind that structural modifications, such as glycosylation, methylation, and sulfation, may affect the bioactivity observed. For example, the substitution by a sugar unit in the quercetin structure showed a twofold increase in the larvicidal activity of rutin [START_REF] Sprengel Lima | Anthelmintic effect of Pterogyne nitens (Fabaceae) on eggs and larvae of Haemonchus contortus: Analyses of structure-activity relationships based on phenolic compounds[END_REF] . Still, studies concerning the anthelmintic effects of sulphated phenolics are missing. Since these metabolites are the main suspects as bioactive components of L. monopetalum extract, it would be interesting for further works to be conducted, not only confirming the anthelmintic effects of isolated compounds but also clarifying the role of sulfate in structure-activity relationship studies.

After PVPP treatment, the activity of L. monopetalum extract on larvae exsheathment was restored by approximately 60-70% to the control values. Although the remaining compounds may have contributed to the overall activity, the major anthelmintic effects were annulated. As some main metabolites of L. monopetalum (67, 71, 76, 80) remain to be identified and quantified, further studies on this species are required to completely understand its bioactive compound (s) and related anthelmintic properties.

Concluding remarks

Due to the constant diffusion of resistance to synthetic anthelmintics in worm populations, the search for plants with antiparasitic activities and their bioactive metabolites that can be used for integrated control approaches of GIN, has expanded over the last 20 years [START_REF] French | Plant-based solutions to global livestock anthelmintic resistance[END_REF] . Extremophile plants, in particular salt-tolerant species, may represent an untapped reservoir of anthelmintic compounds for such purpose. To the best of our knowledge, this study explores for the first time the in vitro anthelmintic properties of eight salt-tolerant species, namely H. italicum subsp. picardi, I. crithmoides, C. soldanela, C. mariscus, M. marina, P. coronopus, L. monopetalum, and C. maritima, against two GIN species and life stages. Pistacia lentiscus, L. monopetalum, C. mariscus, and H. italicum subps. picardi were the most active against both parasite species and life stages (eggs and L3) targeted. The comparative HPLC-ESI-MS n analysis coupled with the use of PVPP unraveled that different bioactive metabolites may be involved in the anthelmintic properties: flavonoid glycosides and galloylquinic acid isomers in P. lentiscus; caffeoylquinic and dicaffeoylquinic acids and quercetin glycosides in H. italicum picardi; proanthocyanins, phenolic acids, and luteolin in C. mariscus; and sulphated and/or methylated flavonoids in L. monopetalum. Further work should be pursued to complete the identification of the main metabolites of L. monopetalum, since this species exhibited the most promising results after P. lentiscus. As recently comprehensively reviewed by Spiegler et al. [START_REF] Spiegler | Medicinal plant extracts and plant-derived polyphenols with anthelmintic activity against intestinal nematodes[END_REF] and Liu and colleagues [START_REF] Liu | Plant-based natural products for the discovery and development of novel anthelmintics against nematodes[END_REF] , polyphenols have been the most extensively studied compounds regarding their anthelmintic effects but the number of other individual phenolic compounds and their structural diversity investigated is still limited, particurlary towards these two GIN species. Therefore, future work should focus on fully elucidate the activity of the main potential bioactive metabolites identified in this work, either alone and/or in synergy, and provide information on structure-activity effects. Still, the results obtained in this study for L. monopetalum, C. mariscus, and H. italicum subsp. picardi warrant further investigations on the potential use of these species either as nutraceutical and/or phytotherapeutic options and/or as sources of anthelmintic compounds against GIN in ruminants.

Figure 1 .

 1 Figure 1. Salt-tolerant species prospected from the Algarve region, Southern Portugal.

Figure 2 .

 2 Figure 2. Effect of the application of PVPP on extracts of 4 selected plants, on the egg hatching inhibitory assay (EHIA) for H. contortus and T. colubriformis at concentration of 2500 µg mL -1 , either treated [PVPP(+)] or not [PVPP(-)] with PVPP.

Figure 3 .

 3 Figure 3. Effect of the application of PVPP on extracts of 4 selected plants, on L3 larvae exsheathment assay (LEIA) for H. contortus and T. colubriformis at concentration of 2500 µg mL -1 , either treated [PVPP(+)] or not [PVPP(-)] with PVPP.

Table 1 .

 1 Plant collection details, including collected organs, date, location and voucher number. Aerial organs: L leaves, S stems, FR fruits, FL flowers, I inflorescences.

	Species/family	Voucher No. Aerial organs Date	Location/coordinates
	Helichrysum italicum subsp. picardi (Asteraceae) XBH32	L/FL	Jul 2017	Tavira (37° 07′ 51.8″ N, 7° 36′ 37.6″ W)
	Inula crithmoides (Asteraceae)	XBH04	L/S/FL	Oct 2017 Olhão (37° 01′ 11.7″ N, 7° 53′ 04.8″ W)
	Pistacia lentiscus (Anacardiaceae)	XBH06	L/S/FR	Jan 2018	Portimão (37° 07′ 34.7″ N, 8° 36′ 02.3″ W)
	Cladium mariscus (Cyperaceae)	XBH03	L/I	Jul 2017	Faro (37° 01′ 03.3″ N,7° 59′ 18.1″ W)
	Calystegia soldanella (Convolvulaceae)	XBH07	L/S/FL	Apr 2018 Portimão (37° 07′ 23.1″ N, 8° 36′ 10.7″ W)
	Medicago marina (Fabaceae)	XBH41	L/S/FL	Apr 2018 Portimão (37° 07′ 23.1″ N, 8° 36′ 10.7″ W)
	Plantago coronopus (Plantaginaceae)	XBH02	L	Jan 2018	Olhão (37° 01′ 32.8″ N, 7° 53′ 04.4″ W)
	Limoniastrum monopetalum (Plumbaginaceae) XBH05	L/S	Jul 2017	Portimão (37° 07′ 34.7″ N, 8° 36′ 02.3″ W)
	Crucianella maritima (Rubiaceae)	XBH40	L/S	Apr 2017 Portimão (37° 07′ 23.2″ N, 8° 36′ 12.3″ W)

Table 3

 3

	summarizes the results of the in vitro activity of salt-tolerant

Table 3 .

 3 In vitro anthelmintic activity of acetone extracts of selected plants on H. contortus and T. colubriformis, by L3 larvae exsheathment (LEIA) and egg hatching assays (EHIA). Results are expressed as IC 50 values (µg mL -1 ) and 95% confidence intervals in brackets. n.d. not determined since IC 50 is higher than 5000 µg mL -1 . Capital and small letters represent significant statistical differences among botanical species (rows) and GIN species (columns) for each assay, respectively, based on Relative Median Potency Estimates.

		LEIA		EHIA
	Species	H. contortus	T. colubriformis	H. contortus	T. colubriformis
	Helichrysum italicum subsp. picardi	92.8 Ab (78.9-107.4)	132.5 Bcd (112.0-157.1)	2947.7 Ac (2772.5-3136.1) 3707.5 Bd (3494.4-3941.5)
	Inula crithmoides	300.8 Ac (231.5-391.2) 1030.8 Be (731.3-1563.0) n.d.	n.d.
	Pistacia lentiscus	27.8 Aa (21.3-36.8)	29.7 Aa (22.2-39.7)	197.7 Aa (158.3-243.8)	223.9 Aa (185.0-268.7)
	Calystegia soldanella	270.6 Ac (204.9-368.2)	270.8 Ad (197.7-384.4)	n.d.	n.d.
	Cladium mariscus	88.9 Ab (66.3-118.7)	77.8 Abc (60.6-100.0)	1496.6 Ab (1326.5-1698.9) 2575.5 Bc (2324.1-2881.8)
	Medicago marina	222.6 Ac (179.8-278.6)	211.2 Ad (159.7-282.2)	n.d.	3860.5 d (3501.6-4343.8)
	Plantago coronopus	94.0 Ab (71.6-121.2)	212.4 Bd (156.3-292.6)	n.d.	n.d.
	Limoniastrum monopetalum	39.4 Aa (33.2-46.4)	47.9 Aab (37.1-60.4)	1999.9 Ab (1693.6-2408.2) 2102.5 Ab (1813.2-2477.8)
	Crucianella maritima	447.2 Ad (302.5-707.7) 1024.5 Be (616.9-2153.1) n.d.	n.d.

Table 4 .

 4 Chemical profile of the extract of Pistacia lentiscus aerial organs. Column "PVPP" indicate if the compound was also present in the corresponding extract treated with PVPP.

			[M-H] -
	No.	Rt (min)	m/z	m/z (% base peak)	Assigned identification	PVPP
	2	1.9	191	MS2 [191]: 173 (100)	Quinic acid	+
				MS2 [495]: 343 (100), 325 (14), 169 (16)
	5	2.2	495	MS3 [495 → 343]: 191 (99), 169 (100), 125 (20)	Di-O-Galloylquinic acid
				MS4 [495 → 343 → 169]: 125 (100)
	6	2.9	343	MS2 [343]: 191 (100), 169 (15), 125 (4)	Galloylquinic acid	+
	9	4.6	305	MS2 [305]: 261 (31), 221 (35), 219 (71), 179 (100), 165 (38) (Epi)gallocatechin
	13	7.2	495	MS2 [495]: 343 (100), 325 (7), 169 (13) MS3 [495 → 343]: 191 (100), 169 (77), 125 (10)	Di-O-Galloylquinic acid
	14	7.8	495	MS2 [495]: 343 (100), 325 (36), 191 (12), 169 (15) MS3 [495 → 343]: 191 (40), 173 (9), 169 (100), 125 (10)	Di-O-Galloylquinic acid
	15	8.4	183	MS2 [183]: 168 (100) MS3 [183 → 168]: 124 (100)	Methyl gallate
	17	8.8	289	MS2 [289]: 245 (100), 205 (40), 203 (14), 179 (22), 151 (9)	Catechin
	30	13.4	457	MS2 [457]: 331 (22), 305 (21), 169 (100) MS3 [457 → 169]: 125 (100)	(Epi)gallocatechin gallate
				MS2 [631]: 479 (100)
	34	15.5	631	MS3 [631 → 479]: 317 (100), 316 (93), 179 (10)	Myricetin-hexoside-gallate
				MS4 [631 → 479 → 317]: 271 (100), 179 (38)
	38	16.6	625	MS2 [625]: 317 (100), 316 (87) MS3 [625 → 317]: 271 (100), 179 (90), 151 (22)	Myricetin-O-rutinoside	+
	41	17.1	493	MS2 [493]: 317 (100) MS3 [493 → 317]: 179 (100), 151 (29)	Myricetin-O-glucuronide
	43	17.5	479	MS2 [479]: 317 (100), 316 (97) MS3 [479 → 317]: 271 (100), 179 (66), 151 (12)	Myricetin-O-hexoside
				MS2 [615]: 463 (100), 301 (42)
	45	18.8	615	MS3 [615 → 463]: 301 (100)	Quercetin-hexoside-gallate
				MS4 [615 → 463 → 301]: 179 (98), 151 (100)
	47	19.6	449	MS2 [449]: 317 (44), 316 (100) MS3 [449 → 316]: 271 (100), 179 (26)	Myricetin-O-pentoside
	49	20.1	463	MS2 [463]: 317 (95), 316 (100) MS3 [463 → 316]: 271 (100), 179 (80), 151 (20)	Myricetin-O-deoxyhexoside	+
	51	20.9	463	MS2 [463]: 301 (100) MS3 [463 → 301]: 179 (100), 151 (50)	Quercetin-O-hexoside
	58	22.6	373 (+)	MS2 [373]: 211 (100), 193 (34), 175 (16), 135 (22), 119 (14) Hydroferuloylglucose	+
	61	23.4	433	MS2 [433]: 301 (100) MS3 [433 → 301]: 271 (100), 179 (87), 151 (68)	Quercetin-O-pentoside
	62	23.5	447	MS2 [447]: 285 (100) MS3 [447 → 285]: 255 (100), 229 (37), 227 (33)	Kaempferol-O-hexoside
	66	24.8	447	MS2 [447]: 301 (100) MS3 [447 → 301]: 179 (48), 151 (100)	Quercetin-O-deoxyhexoside	+
	70	26.7	585	MS2 [585]: 301 (100) MS3 [585 → 301]: 179 (100), 151 (98)	Quercetin-pentoside-gallate
	73	29.0	431	MS2 [431]: 285 (100) MS3 [431 → 285]: 257 (93), 255 (100), 241 (55), 229 (36)	Kaempferol-O-deoxyhexoside	+
	74	30.2	569	MS2 [569]: 285 (100) MS3 [569 → 285]: 285 (100), 257 (37), 151 (86)	Kaempferol-pentoside-gallate
	78	33.0	507	MS2 [507]: 461 (100), 293 (36)	Unknown	+
	79	36.0	285	MS2 [285]: 285 (100), 241 (23)	Luteolin
	81	39.1	327	MS2 [327]: 291 (24), 229 (100), 211 (25), 171 (89)	Oxo-dihydroxy-octadecenoic acid +
	82	40.6	329	MS2 [329]: 311 (31), 229 (96), 211 (100), 171 (60)	Trihydroxy-octadecenoic acid	+

Vol:.(1234567890) Scientific Reports | (2021) 11:24303 | https://doi.org/10.1038/s41598-021-03472-9

Table 5 .

 5 Characterization of the compounds present in the extract of Helichrysum italicum picardi aerial organs. Column "PVPP" indicate if the compound was also present in the corresponding H. italicum picardi treated PVPP sample.

			[M-H] -
	No.	Rt (min)	m/z	m/z (% base peak)	Assigned identification	PVPP
				MS 2 [377]: 341 (100)
	1	1.8	377	MS 3 [377 → 341]: 179 (100), 161 (95), 143 (34)	Disaccharide (HCl adduct)	+
				MS 4 [377 → 341 → 179]: 143 (94), 119 (100)
	2	1.9	191	MS 2 [191]: 173 (48), 111 (100)	Quinic acid	+
	3	2.1	315	MS 2 [315]: 153 (100) MS 3 [315 → 153]: 123 (100), 108 (49)	Dihydroxybenzoic acid-O-hexoside	+
	4	2.1	353	MS 2 [353]: 191 (100), 179 (26), 135 (7)	Caffeoylquinic acid	+
	8	3.7	315	MS 2 [315]: 153 (100) MS 3 [315 → 153]: 109 (100)	Dihydroxybenzoic acid-O-hexoside	+
	10	5.3	353	MS 2 [353]: 191 (100), 179 (37), 135 (9)	Neochlorogenic acid	+
	18	9.0	353	MS 2 [353]: 191 (100), 179 (4), 173 (5), 135 (3)	Chlorogenic acid	+
	26	11.2	179	MS 2 [179]: 135 (100)	Caffeic acid
				MS 2 [609]: 447 (100), 285 (37)
	29	12.2	609	MS 3 [609 → 447]: 285 (46), 284 (100), 255 (50), 151 (20)	Kaempferol-dihexoside	+
				MS 4 [609 → 447 → 285]: 255 (100), 243 (15), 227 (17)
				MS 2 [479]: 317 (100)
	36	16.4	479	MS 3 [479 → 317]: 317 (100), 203 (10), 195 (16), 165	Unidentified-O-hexoside
				(21)
				MS 2 [515]: 353 (100), 191 (12)
	44	18.0	515	MS 3 [515 → 353]: 191 (100), 179 (44), 173 (13), 135	Dicaffeoylquinic acid
				(13)
	50	20.8	463	MS 2 [463]: 301 (100) MS 3 [463 → 301]: 179 (24), 151 (100)	Quercetin-O-hexoside
	54	21.6	493	MS 2 [493]: 331 (100) MS 3 [493 → 331]: 316 (100)	Mearnsetin-O-hexoside
	56	22.2	477	MS 2 [477]: 315 (100), 314 (16) MS 3 [477 → 315]: 300 (100)	Isorhamnetin-O-hexoside
				MS 2 [515]: 353 (100), 179 (18), 173 (21)
	59	22.7	515	MS 3 [515 → 353]: 191 (48), 179 (62), 173 (100), 135	Dicaffeoylquinic acid
				(10)
				MS 2 [433]: 301 (100), 271 (12)
	61	23.4	433	MS 3 [433 → 301]: 271 (68), 255 (100), 179 (18), 151	Quercetin-O-pentoside
				(55)
	63	24.1	515	MS 2 [515]: 353 (100), 191 (7), 179 (3) MS 3 [515 → 353]: 191 (100), 179 (58), 135 (21)	Dicaffeoylquinic acid	+
	68	25.4	431	MS 2 [431]: 269 (100) MS 3 [431 → 269]: 225 (100)	Apigenin-O-hexoside	+
				MS 2 [515]: 353 (100), 179 (12), 173 (18)
	69	26.5	515	MS 3 [515 → 353]: 191 (13), 179 (68), 173 (100), 135	Dicaffeoylquinic acid	+
				(15)
	72	27.4	463	MS 2 [463]: 301 (100) MS 3 [463 → 301]: 179 (100), 151 (76)	Quercetin-O-hexoside
				MS 2 [609]: 463 (100), 301 (47)
	77	32.7	609	MS 3 [609 → 463]: 301 (100), 271 (4)	Quercetin-O-deoxyhexoside-O-hexoside
				MS 4 [609 → 463 → 301]: 179 (62), 151 (100)

Table 6 .

 6 Characterization of the compounds present in the extract of Cladium mariscus aerial organs. Column "PVPP" indicate if the compound was also present in the corresponding C. mariscus treated PVPP sample.

			[M-H] -
	No.	Rt (min)	m/z	m/z (% base peak)	Assigned identification	PVPP
				MS 2 [377]: 341 (100)
	1	1.8	377	MS 3 [377 → 341]: 179 (100), 161 (24), 143 (13), 119 (25),	Disaccharide (HCl adduct)	+
				113 (20)
	9	4.6	305	MS 2 [305]: 261 (7), 221 (43), 219 (72), 179 (100), 165 (35) (Epi)gallocatechin
	11	7.0	577	MS 2 [577]: 451 (38), 425 (100), 407 (96), 305 (21), 289 (45), 287 (17)	Procyanidin dimer
	12	7.2	305	MS 2 [305]: 261 (12), 221 (55), 219 (77), 179 (100), 165 (26)	(Epi)gallocatechin
	17	8.8	289	MS 2 [289]: 245 (100), 205 (43), 203 (28), 179 (24)	Catechin
	18	9.0	353	MS 2 [353]: 191 (100), 179 (3), 173 (4), 135 (1)	Chlorogenic acid*	+
	19	9.3	865	MS 2 [865]: 739 (54), 713 (41), 695 (100), 577 (52), 451 (29), 407 (54), 405 (23), 289(19), 287 (41)	Proanthocyanidin trimer
	20	9.5	429	MS 2 [429]: 267 (100) MS 3 [429 → 267]: 205 (100), 113 (82)	Unknown	+
	21	9.9	577	MS 2 [577]: 451 (69), 441 (17), 425 (30), 305 (100), 289 (10), 287 (8)	Proanthocyanidin dimer
	22	10.1	865	MS 2 [865]: 739 (76), 695 (100), 577 (83), 451 (18), 407 (97), 287 (58)	Proanthocyanidin trimer
				MS 2 [561]: 543(18), 435 (58), 409 (73), 425 (46), 289
	23	10.1	561	(100), 271 (41)	Proanthocyanidin dimer
				MS 3 [561 → 289]: 245 (100), 205 (57), 203 (30)
	25	10.9	577	MS 2 [577]: 451 (25), 441 (9), 425 (100), 407 (61), 305 (43), 289 (33), 287 (10)	Proanthocyanidin dimer
	27	11.5	577	MS 2 [577]: 451 (28), 425 (10), 305 (100), 289 (4), 287 (6) Proanthocyanidin dimer
	28	12.1	289	MS 2 [289]: 245 (100), 205 (48), 203 (19), 179 (25), 161 (10)	Epicatechin
	31	13.7	579	MS 2 [579]: 561 (16), 519 (16), 489 (100), 459 (99), 429 (18), 399 (50), 369 (14)	Luteolin-C-hexoside-C-pentoside	+
	35	15.9	563	MS 2 [563]: 545 (14), 503 (15), 473 (48), 443 (100), 383 (37), 353 (43)	Apigenin-C-hexoside-C-pentoside	+
	37	16.5	447	MS 2 [447]: 429 (14), 357 (70), 327 (100), 285 (3)	Luteolin-6-C-glucoside (isoorientin)	+
	39	17.0	461	MS 2 [461]: 341 (100), 313 (66), 298 (37)	Unknown	+
	40	17.0	549	MS 2 [549]: 531 (12), 489 (26), 459 (100), 441 (13), 429 (10), 399 (64), 369 (25)	Luteolin 6-C-pentosyl-8-C-pentoside +
	42	17.3	563	MS 2 [563]: 503 (22), 473 (100), 443 (69), 383 (61), 353 (97)	Apigenin-C-hexoside-C-pentoside	+
	53	21.4	447	MS 2 [447]: 285 (100) MS 3 [447 → 285]: 285 (100), 241 (47), 151 (10)	Kaempferol-O-hexoside
	57	22.2	417	MS 2 [417]: 399 (22), 357 (100), 327 (49) MS 3 [417 → 357]: 339 (100), 311 (24), 297 (82), 285 (93)	Luteolin-C-pentoside
	60	22.8	243	MS 2 [243]: 225 (100), 201 (50), 199 (23), 157 (20)	Unknown
	75	32.1	485	MS 2 [485]: 375 (100), 357 (13) MS 3 [485 → 375]: 357 (100), 333 (22), 265 (39)	Unknown
	79	36.0	285	MS 2 [285]: 285 (100), 267 (5), 243 (2), 241 (3)	Luteolin

Table 7 .

 7 Characterization of the compounds present in the extract of Limoniastrum monopetalum aerial organs. Column "PVPP" indicate if the compound was also present in the corresponding L. monopetalum treated PVPP sample.

			[M-H] -
	No.	Rt (min)	m/z	m/z (% base peak)	Assigned identification	PVPP
				MS 2 [377]: 341 (100)
	1	1.8	377	MS 3 [377 → 341]: 179 (100), 161 (3), 143 (14), 119 (24), 113	Disaccharide (HCl adduct)	+
				(6)
	7	3.2	169	MS 2 [169]: 125 (100)	Gallic acid
	9	4.6	305	MS 2 [305]: 261 (21), 221 (53), 219 (57), 179 (100)	(Epi)gallocatechin
	12	7.2	305	MS 2 [305]: 261 (17), 221 (32), 219 (49), 179 (100), 165 (25)	(Epi)gallocatechin
	16	8.6	303	MS 2 [303]: 223 (100) MS 3 [303 → 223]: 208 (100), 179 (37), 164 (35), 149 (5)	Sinapic acid sulfate	+
	24	10.2	273	MS 2 [273]: 193 (100), 178 (17), 149 (38), 134 (7)	Ferulic acid sulfate	+
	32	13.8	457	MS 2 [457]: 329 (100), 169 (31) MS 3 [457 → 169]: 125 (100)	Gallic acid derivative	+
	33	14.4	457	MS 2 [457]: 329 (100), 245 (26), 203 (23), 165 (24) MS 3 [457 → 329]: 314 (100)	Unknown	+
	46	19.1	252	MS 2 [252]: 212 (100), 204 (4)	Unknown
	48	19.8	609	MS 2 [609]: 301 (100) MS 3 [609 → 301]: 179 (100), 151 (78)	Rutin
	52	21.2	477	MS 2 [477]: 301 (100) MS 3 [477 → 301]: 179 (90), 151 (100)	Quercetin-O-glucuronide
	55	21.7	567	MS 2 [567]: 331 (100) MS 3 [567 → 331]: 316 (100), 179 (67), 151 (33)	Unknown
	64	24.1	437	MS 2 [437]: 357 (100), 151 (52) MS 3 [437 → 357]: 342(5), 311 (6), 151 (100), 136 (24)	Pinoresinol	+
	65	24.4	395	MS 2 [395]: 315 (100) MS 3 [395 → 315]: 300 (100), 271 (8), 255 (13)	Isorhamnetin sulfate
				MS 2 [425]: 345 (100)
	67	25.2	425	MS 3 [425 → 345]: 330 (100), 315 (34)	Methylated flavonoid sulfate
				MS 4 [425 → 345 → 330]: 315 (100), 285 (74)
				MS 2 [425]: 345 (100), 330 (15)
	71	27.2	425	MS 3 [425 → 345]: 330 (100)	Methylated flavonoid sulfate
				MS 4 [425 → 345 → 330]: 315 (100), 271 (10)
				MS 2 [439]: 359 (100)
	76	32.5	439	MS 3 [439 → 359]: 344 (100)	Methylated flavonoid sulfate	+
				MS 4 [439 → 359 → 344]: 329 (100)
	80	36.9	439	MS 2 [439]: 359 (100) MS 3 [439 → 359]: 344 (100), 329 (18)	Methylated flavonoid sulfate
	81	39.1	327	MS 2 [327]: 291 (27), 229 (100), 211 (70), 209 (44), 171 (77)	Oxo-dihydroxy-octadecenoic acid +
	82	40.6	329	MS 2 [329]: 311 (14), 229 (100), 211 (44), 171 (18)	Trihydroxy-octadecenoic acid	+

Scientific Reports | (2021) 11:24303 | https://doi.org/10.1038/s41598-021-03472-9

Scientific Reports | (2021) 11:24303 | https://doi.org/10.1038/s41598-021-03472-9

Acknowledgements

The authors would like to acknowledge Dr. Nicolas Fabre and Valérie Cristofolli, from the Faculty of Pharmacy, Université Paul Sabatier Toulouse III, France, for their technical assistance during the preparation and lyophilization of the plant extracts.

was made by Dr. Luísa Custódio (CCMAR). Voucher specimens were

Funding

This work was supported by Foundation for Science and Technology (FCT), the Portuguese National Budget funding (GreenVet-ALG-01-0145-FEDER-028876 and UIDB/04326/2020 projects), the bilateral PESSOA project between France and Portugal (37956XD) and the PRIMA project HaloFarMs (2019-SECTION2-16). Marta Oliveira acknowledges FCT for the PhD grant SFRH/BD/123658/2016. Luísa Custódio was supported by FCT Scientific Employment Stimulus (CEECIND/00425/2017). Caroline Sprengel-Lima acknowledges CAPES (finance code 001) for the scholarship and the Doctoral Program Sandwich Abroad (Grant 88881.187940/2018-01).

www.nature.com/scientificreports/ Having this in mind, the combination of proanthocyanidins and luteolin in C. mariscus extract could act synergistically in the inhibition of the egg hatching. Nevertheless, the activity on LEIA was only partially restored after PVPP addition (approx. 20-40% larvae exsheathment), i.e., the remaining metabolites are still exhibiting anthelmintic properties. In PVPP-treated samples, mainly C-glycosyl flavones (1.07 mg g -1 DW) and, to a less extent chlorogenic acid, remained in solution while the catechin derivatives and luteolin were removed (Table 6; Suppl. files, Table III). As previously addressed, chlorogenic acid exhibits significant anthelmintic activity in vitro against H. contortus larvae exsheathment and egg hatching [START_REF] Mancilla-Montelongo | Evaluation of cinnamic acid and six analogues against eggs and larvae of Haemonchus contortus[END_REF] . Despite the activity described for luteolin, the

Competing interests

The authors declare no competing interests.


Marius Bozga
email: marius.bozga@imag.fr

Radu Iosif
email: radu.iosif@imag.fr

Vassiliki Sfyrla
email: vassiliki.sfyrla@imag.fr

An Efficient Algorithm for the Computation of Optimum Paths in Weighted Graphs

The goal of this paper is to identify a more efficient algorithm for the computation of the path of minimum ratio (i.e. the quotient of the weight divided by the length) in a weighted graph. The main application of this technique is to improve the efficiency of reachability analysis for flat counter automata with Difference Bound Matrix constraints on transitions. A previous result showed that these paths could be defined using Presburger arithmetic. However, this method is costly, as the complexity of deciding satisfiability of Presburger formulae has a double exponential lower bound. Our solution avoids the use of Presburger arithmetic, by computing the function between any n ∈ N and the weight of the minimal path of length n. The function is computed iteratively, by computing the minimal fixed point of a system of set constraints, involving semilinear sets. This requires a min operator on linear sets, which is implemented using rewrite rules.

Introduction

Flat counter automata [START_REF] Comon | Multiple Counters Automata, Safety Analysis and Presburger Arithmetic[END_REF], [START_REF] Finkel | How to compose presburger-accelerations: Applications to broadcast protocols[END_REF], [START_REF] Boigelot | On iterating linear transformations over recognizable sets of integers[END_REF] have received a lot of attention recently, as they represent an important class of infinite-state systems, for which the reachability and termination problems are decidable. These results have been used in a number of successful verification tools, e.g. FAST [START_REF] Bardin | Fast: Fast accelereation of symbolic transition systems[END_REF], LASH [START_REF] Wolper | Verifying systems with infinite but regular state spaces[END_REF] or TREX [START_REF] Annichini | Trex: A tool for reachability analysis of complex systems[END_REF].

Comon and Jurski show in [START_REF] Comon | Multiple Counters Automata, Safety Analysis and Presburger Arithmetic[END_REF] that the reachability problem for a flat counter automaton can be expressed in Presburger arithmetic, given that the automata have transition guards that are conjunctions of relations of the form xy ≤ c, where x and y denote either the current or the future (primed) values of the counters, and c is an integer constant. These constraints are known as Difference Bound Matrix (DBM). To our knowledge, their result concerns the most general class of flat counter automata, considered so far.

Recent work by Bozga, Iosif and Lakhnech [START_REF] Bozga | Flat parametric counter automata[END_REF] addresses the same class of counter automata as the one in [START_REF] Comon | Multiple Counters Automata, Safety Analysis and Presburger Arithmetic[END_REF], but presents a simplified proof of decidability, based on the translation of a control loop with a DBM constraint into a weighted automaton, such that, for each pair of counters x and y of the original loop, we have x 0y n ≤ w, where w is the weight of the minimum weight path of length n between given states of the weighted automaton. Moreover, it can be shown that the minimal weight is a linear function of the length n of the path. Computing this weight, as a function of the length, i.e. w = α • n + β, for some α, β ∈ Z is crucial in order to express the global relation between the input and output values of the counters. However, for the purposes of the proof in [START_REF] Bozga | Flat parametric counter automata[END_REF], full Presburger arithmetic was used in order to define this function.

The goal of this paper is therefore to present a more efficient method for the computation of the minimum weight function in a given weighted graph. We introduce a new approach to this problem, which overpasses the method based on Presburger arithmetic. Our method is based on the computation of the least fixed point of a system of set constraints on semilinear sets. This computation is shown to terminate if an entire elementary cycle is considered at the time, rather than just single edges. Since the number of elementary cycles is exponential in the number of nodes, we consider only the elementary cycles of minimum ratio (= the weight of the cycle divided by its length). It can be shown that the number of optimal cycles is polynomial in the number of graph nodes. Moreover, a polynomial-time algorithm for finding these elementary cycles has been reported in [START_REF] Cochet-Terrasson | Numerical computation of spectral elements in max-plus algebra[END_REF]. In order for the solution of the system of set constraints to be a function, i.e. a set of pairs n, w that is a functional relation, we use a min(X) operator that returns, for any semilinear set X the set of minimal points. For efficiency reasons, this operator has been implemented using a set of rewriting rules, that work on semilinear sets.

The techniques described in this paper have been implemented, the result being a tool for the analysis of flat counter systems, which is to be released soon.

Notation and Definitions

For the rest of the paper, let us consider a fixed weighted graph G = V, E, w , where:

-V is a finite set of nodes, -E ⊆ V × V the set of edges. -w : E → Z is the weight function. A path π in a graph is a sequence of nodes v 0 , v 1 , ..., v n such that π = (v 0 , v 1 , ..., v n ), where (v i , v i+1 ) ∈ E, ∀i = 1, ..., n.
The length |π| is equal to the number of edges of the path. The weight w(π) is equal to the sum of the weights on the path. A path between two nodes s and t is called optimal of length m if there is no other path of length m and with smaller weight.

A cycle c is a path such that the start node and the end node are the same. The cycle mean ρ(c) is defined as w(c) |c| . A cycle is called elementary if there is a sequence of nodes in which there is never twice the same node. An elementary cycle is called critical if it has the minimum cycle mean amongst all the elementary cycles of the graph. A node is critical if it belongs to a critical cycle.

A linear set a 0 + a 1 N + ... + a n N where a 0 , a 1 , ..., a n ∈ Z k denote the set of all points x ∈ Z k of the form x = a 0 + n i=1 x i a i , where x i ∈ N. A semilinear set is a finite union of linear sets.

Given two sets A, B ⊆ Z k , we define A ⊕ B = {a + b|a ∈ A, b ∈ B}. It could be shown that if A and B are semilinear sets, then A ⊕ B does so.

The Problem

Let u, v ∈ V be two nodes in the graph, and P uv be the relation between lengths and weights of paths from u to v: P uv = {(m, w) | ∃π from u to v such that |π| = m, w(π) = w}. This set is semilinear, for any nodes u and v. This could be proved either directly, or by using the Presburger formula defined in [START_REF] Bozga | Flat parametric counter automata[END_REF]. Now, the set of optimal paths from u to v is:

min

P uv = {(m, w) | (m, w) ∈ P uv and ∀(m, w ′ ) ∈ P uv ⇒ w ≤ w ′ }
This set is also semilinear, given that P uv is semilinear.

Our aim is to effectively compute min P st for some given s and t by overpassing the construction in [START_REF] Bozga | Flat parametric counter automata[END_REF] which produces a Presburger formula that is too complex to be useful in practice.

Our Solution

The Initial Approach

Let s ∈ V be a fixed node in the graph.

The sets P sv are the least fixpoint solution with 0 0 ∈ P ss of the following system of equations, for all v:

P sv = e=(u,v)∈E P su ⊕ 1 w(e)
These equations give a direct way to compute the sets P sv as the limit of the sequences P (k) sv defined as follows:

P (k+1) sv = e=(u,v)∈E P (k) su ⊕ 1 w(e)
started with P (0) ss = 0 0 and P (0) sv = ∅ for all v = s. Unfortunately, the computation above cannot be carried out iteratively because the limit cannot be reached in a finite number of steps, if there are cycles in the graph.

Nevertheless, we can extend the equations above to take into account the elementary cycles(EC), as follows:

P sv = e=(u,v)∈E P su ⊕ 1 w(e) ⊕ c∈EC(v) |c| w(e) N
Now, it can be shown that by iterating these equations, we always reach the limit in a finite number of steps (cf. Theorem 1). The second step is to extract the set of minimal points out of a semilinear set (cf. Section 4.3).

The Improved Approach

A problem with the previous approach is that it requires to compute and use all the elementary cycles in the graph. Or, it is well known that their number is at worst exponential.

Since we are interested in computing the optimal paths, we restrict ourselves to elementary critical cycles(ECC) only and optimal paths. That is, we attempt to compute sets X sv as the least fixpoint solution with 0 0 ∈ X ss to the system of equations, for all v:

X sv = min   e=(u,v)∈E X su ⊕ 1 w(e) ⊕ c∈ECC(v) |c| w(c) N  
As before, we compute the sets X sv as the limit of sequences X (k) sv defined as follows:

X (k+1) sv = min   e=(u,v)∈E X (k) su ⊕ 1 w(e) ⊕ c∈ECC(v) |c| w(c) N   started with X (0)
ss = 0 0 and X (0) sv = ∅ for all v = s. The following theorem states the correctness of the improved approach: Theorem 1. Given a weighted graph G = V, E, w , for all pairs of nodes u, v ∈ V we have: -[correctness] the limit set X uv is semilinear, and X uv = min P uv , -[termination] the sequence X (k) uv converges in a finite number of steps.

To calculate the critical cycles, we use the Howard's algorithm [START_REF] Denardo | Multichain markov renvewal programs[END_REF], which is known to perform in a remarkable almost linear average execution time.

Implementing the min Operator

The previous approaches requires the min operator to be implemented on semilinear sets X. The formal definition of this operator is: min

X = {(m, w) | (m, w) ∈ X and ∀(m, w ′ ) ∈ X ⇒ w ≤ w ′ }
This operator is effectively implemented by the set of rewriting rules given in table 1.

The rule (1) applies to linear sets having more than one generator and reduces their number by one. In this transformation, the optimal generator is kept (the

(1) Y + " m1 w1 « N + " m2 w2 « N ❀ M/m 2 -1 S k=0 Y + " m1 w1 « N + " km2 kw2 « [w1/m1 ≤ w2/m2, M = lcm(m1, m2)] (2)
" m0 w0 « + " m1 w1 « N ∪ " m ′ 0 w ′ 0 « + " m2 w2 « N ❀ M/m 1 -1 S k=0 " m0 + km1 w0 + kw1 « + " M w1M/m1 « N ∪ M/m 2 -1 S k=0 " m ′ 0 + km2 w ′ 0 + kw2 « + " M w2M/m2 « N [m1 = m2, gcd(m1, m2)|(m0 -m ′ 0 ), M = lcm(m1, m2)] (3)
" m0 w0 « + " m w1 « N ∪ " m ′ 0 w ′ 0 « + " m w2 « N ❀ n 1 S k=0 " m0 + km w0 + kw1 « ∪ n 2 S k=0 " m ′ 0 + km w ′ 0 + kw2 « ∪ " m0 + (n1 + 1)m w0 + (n1 + 1)w1 « + " m w1 « N [m|(m0 -m ′ 0 ), w1 < w2, n1 = max(0, [((w0 -w ′ 0 ) + w2(m ′ 0 -m0)/M )/(w2 -w1)])] [ n2 = max(0, [((w0 -w ′ 0 ) + w1(m ′ 0 -m0)/M )/(w2 -w1)])] (4)
" m0 w0 « + " m w « N ∪ " m ′ 0 w ′ 0 « + " m w « N ❀ n-1 S k=0 " m0 + km w0 + kw « ∪ " m ′ 0 w ′ « + " m w « N [m|(m0 -m ′ 0 ), m ′ 0 ≥ m0, n = (m ′ 0 -m0)/m, w ′ = min(w ′ 0 , w0 + nw)] (5)
" m0 w0 « + " m w « N ∪ " m ′ 0 w ′ 0 « ❀ " m0 w0 « + " m w « N [m|(m0 -m ′ 0 ), m ′ 0 ≥ m0, w ′ 0 ≥ w0 + w(m ′ 0 -m0)/m] (6)
" m0 w0 « + " m w « N ∪ " m ′ 0 w ′ 0 « ❀ n-1 S k=0 " m0 + km w0 + kw « ∪ " m ′ 0 w ′ 0 « ∪ " m0 + (n + 1)m w0 + (n + 1)w « + " m w « N [m|(m0 -m ′ 0 ), m ′ 0 ≥ m0, w ′ 0 < w0 + w(m ′ 0 -m0)/m, n = (m ′ 0 -m0)/m] (7)
" m0 w0 « ∪ " m0 w ′ 0 « ❀ " m0 w0 « [w0 ≤ w ′ 0 ]
Table 1. Rewriting rules for the min operator one having the best ration w/m) while the others are taken only a finite number of times. The rules [START_REF] Bardin | Fast: Fast accelereation of symbolic transition systems[END_REF][START_REF] Boigelot | On iterating linear transformations over recognizable sets of integers[END_REF][START_REF] Bozga | Flat parametric counter automata[END_REF] apply to a semilinear sets containing precisely two overlapping linear sets with one generator each (i.e., sequences). The rule (2) handles the case where the generators have distinct periods (m values) and simply 'split' them in order to obtain a common period (the least common multiple of both periods). Then, rules [START_REF] Boigelot | On iterating linear transformations over recognizable sets of integers[END_REF][START_REF] Bozga | Flat parametric counter automata[END_REF] select the minimum amongst two overlapping linear sets having the same period. Notice that rule (3) applies for the case where the generator weights are different, and rule (4) applies for the case where the generator weights are the same.

Rules [START_REF] Cochet-Terrasson | Numerical computation of spectral elements in max-plus algebra[END_REF][START_REF] Comon | Multiple Counters Automata, Safety Analysis and Presburger Arithmetic[END_REF] apply to semilinear sets containing precisely two overlapping linear sets, one with no generator (i.e, an isolated point) and one with some generator (a sequence). Rule [START_REF] Cochet-Terrasson | Numerical computation of spectral elements in max-plus algebra[END_REF] handles the case where the isolated point has a bigger value than the one provided by the sequence, and rule (6) the converse. Finally, rule [START_REF] Denardo | Multichain markov renvewal programs[END_REF] applies for two isolated points choosing the minimal one.

The following theorem states the corectness of this method:

Theorem 2. Let X be a semilinear set in two dimensions (m, w):

1.

[soundness] If X rewrites to X ′ using one of the rules above then min X = min X ′ . 2. [completness] If X cannot be rewritten by any of the rules then min X = X; 3. [termination] Any derivation of X using the rules above eventually terminates in a finite number of steps.

An Example

Consider the graph G given in figure 1. We are interested to obtain optimal paths from the node 1 to all other nodes in the graph.

The system of equations is the following:

X 11 = min X 12 ⊕ 1 3 ⊕ 2 4 N X 12 = min X 11 ⊕ 1 1 ⊕ 2 4 N X 13 = min X 11 ⊕ 1 2 X 13 ⊕ 1 2 X 14 ⊕ 1 2 ⊕ 2 3 N X 14 = min X 13 ⊕ 1 1 ⊕ 2 3 N X 15 = min X 14 ⊕ 1 2
After solving the above system, the minimal solution is the following:

Conclusions

We have addressed the problem of finding minimal ratio paths in a weighted graph. This problem is of interest to the verification community, as it provides an effective method for the analysis of flat counter automata with DBM constraints, which is one of the most general class of infinite state systems, known to be decidable. Our solution relies on computing the least fixed point of a system of set constraints. This computation is accelerated by adding one elementary cycle at the time, and using a performant algorithm to select the elementary cycles of minimal ratio. Then computing the minimum function is done by applying exhaustively a set of rewriting rules. The techniques presented have been implemented in a tool for the analysis of flat counter automata which is to be released soon.

Fig. 1 .

 1 Fig. 1. (a) an example graph (b) the graph annotated with critical nodes and critical cycles