Marjorie Couton

Laurent Lévêque

Claire Daguin-Thiébaut

Thierry Comtet

Frédérique Viard
email: frederique.viard@umontpellier.fr

Water eDNA metabarcoding is effective in detecting non-native species in marinas, but detection errors still hinder its use for passive monitoring

Keywords: biological invasions, environmental DNA, metabarcoding, morphology, ports, quadrats

Marinas are high-priority targets for marine non-indigenous species (NIS), where they compose a large portion of the biofouling communities. The practicality of water samples collection makes environmental DNA (eDNA) metabarcoding an interesting tool for routine NIS surveys. Here the effectiveness of water-eDNA-metabarcoding to identify biofouling NIS, in ten marinas from western France, was examined. Morphological identification of specimens collected in quadrats brought out 18 sessile benthic NIS beneath floating pontoons. Water-eDNA-metabarcoding detected two thirds of them, failing to detect important NIS. However, sampling and bioinformatics filtering steps can be optimized to identify more species. In addition, this method allowed the detection of additional NIS from neighboring micro-habitats. Caution should however be taken when reporting putative novel NIS, because of errors in species assignment. This work highlights that water-eDNAmetabarcoding is effective for active (targeted) NIS surveys, and could be significantly improved for its further use in marine NIS passive surveys.

Introduction

As the number of marine introductions is growing worldwide [START_REF] Seebens | No saturation in the accumulation of alien species worldwide[END_REF], much effort is directed towards non-indigenous species (NIS) management. The implemented strategies can vary greatly from, limiting the spread of new species by applying regulation on vectors of introduction, to eradication protocols to remove invasive species from a particular area [START_REF] Robertson | A proposed unified framework to describe the management of biological invasions[END_REF]. Nevertheless, vectors of introductions are not efficiently regulated [START_REF] Carney | Evaluating the combined effects of ballast water management and trade dynamics on transfers of marine organisms by ships[END_REF], and measures of eradication are difficult to apply when nonindigenous species (NIS) have become too abundant or widespread [START_REF] Ojaveer | Classification of non-indigenous species based on their impacts: considerations for application in marine management[END_REF].

Monitoring NIS to detect new arrivals or to evaluate the spread of already established species, is thus crucial to support efficient management strategies [START_REF] Robertson | A proposed unified framework to describe the management of biological invasions[END_REF]. It is especially true in the primary introduction sites, such as ports or marinas. In such habitats, fouling communities from artificial hard substrates are often targeted since they include many NIS [START_REF] Dafforn | Shallow moving structures promote marine invader dominance[END_REF][START_REF] Leclerc | Habitat type drives the distribution of non-indigenous species in fouling communities regardless of associated maritime traffic[END_REF].

Diverse traditional approaches exist to monitor biofouling communities, from Rapid Assessment Surveys or full species inventories [START_REF] Lehtiniemi | Dose of truth-Monitoring marine nonindigenous species to serve legislative requirements[END_REF] to passive sampling strategies using settlement plates [START_REF] Dafforn | Shallow moving structures promote marine invader dominance[END_REF][START_REF] Outinen | The role of marinas in the establishment and spread of non-indigenous species in Baltic Sea fouling communities[END_REF]. Their inherent issues, however, might prevent their broad use by practitioners and hinder their efficiency.

Most of the problems with traditional approaches arise from the morphological identification of organisms. They require taxonomic expertise, and the time constraint of field sessions can lead to erroneous identification for complex taxa (eg the ascidians Botrylloides spp., Viard et al. 2019). Furthermore, these approaches do not allow the detection of introductions by (pseudo-)cryptic species, common among NIS, especially in biofouling assemblages [START_REF] Viard | Marine invasions enter the genomic era: three lessons from the past, and the way forward[END_REF][START_REF] Turon | Looks can be deceiving: Didemnum pseudovexillum sp. nov. (Ascidiacea) in European harbours[END_REF]. Finally, they are not always sufficient to discriminate species at early-settlement stages. There is thus a particular need for a new method solving these issues.

Molecular approaches, especially DNA metabarcoding, have been shown to overcome these limitations [START_REF] Zaiko | Metabarcoding approach for nonindigenous species surveillance in marine coastal waters[END_REF][START_REF] Rey | Considerations for metabarcoding-based port biological baseline surveys aimed at marine nonindigenous species monitoring and risk assessments[END_REF]. Metabarcoding has been successfully applied to various types of samples in the context of NIS surveys (eg plankton: [START_REF] Couton | Metabarcoding on planktonic larval stages: an efficient approach for detecting and investigating life cycle dynamics of benthic aliens[END_REF], sediment: Shaw et al. 2019, water: Borrell et al. 2017, homogenized organisms: [START_REF] Pearman | Metabarcoding as a tool to enhance marine surveillance of nonindigenous species in tropical harbors: A case study in Tahiti[END_REF], which provide different results, reflecting the composition of different communities [START_REF] Koziol | Environmental DNA metabarcoding studies are critically affected by substrate selection[END_REF][START_REF] Fernandez | Environmental DNA sampling protocols for the surveillance of marine non-indigenous species in Irish coastal waters[END_REF]. [START_REF] Rey | Considerations for metabarcoding-based port biological baseline surveys aimed at marine nonindigenous species monitoring and risk assessments[END_REF] suggested that, for NIS surveys, all types of samples (or a combination of several of them) should be simultaneously processed (see also [START_REF] Holman | Detection of introduced and resident marine species using environmental DNA metabarcoding of sediment and water[END_REF]). However, this might be hardly feasible for regular monitoring, as it would require expensive sampling tools and expertise that is not always available, and would be very time-consuming. In that context, water environmental DNA (eDNA) would be the sample type of choice as seawater can be easily and rapidly sampled in ports, even by non-experts with a minimal training, and the sampling protocol can be highly standardized [START_REF] Morisette | Strategic considerations for invasive species managers in the utilization of environmental DNA (eDNA): steps for incorporating this powerful surveillance tool[END_REF]. Moreover, being non-destructive, water sampling can be conducted as often as required, allowing fine temporal surveys, which is recommended as many NIS are short-lived and show seasonal patterns of abundance [START_REF] Couton | Metabarcoding on planktonic larval stages: an efficient approach for detecting and investigating life cycle dynamics of benthic aliens[END_REF]. Finally, water might allow to get a broader picture of NIS present in a given marina, encompassing at the same time species living in the water column or on the bottom [START_REF] Stat | Ecosystem biomonitoring with eDNA: metabarcoding across the tree of life in a tropical marine environment[END_REF].

Very few studies investigated the reliability of water-eDNA-metabarcoding to study benthic communities, even less when considering hard-bottom, and they provided contrasting results. For example, while [START_REF] Leduc | Comparing eDNA metabarcoding and species collection for documenting Arctic metazoan biodiversity[END_REF] and [START_REF] Antich | Marine biomonitoring with eDNA: Can metabarcoding of water samples cut it as a tool for surveying benthic communities?[END_REF] reported many false negatives (only up to 15% benthic species/MOTUs retrieved in water-eDNA samples), [START_REF] West | The applicability of eDNA metabarcoding approaches for sessile benthic surveying in the Kimberley region, north-western Australia[END_REF] recovered 70% of coral taxa. Many authors thus preferentially used bulk samples from scraping of either hard bottoms or settlement plates [START_REF] Duarte | Status and prospects of marine NIS detection and monitoring through (e)DNA metabarcoding[END_REF]. This approach, however, is not free of bias, and requires processing a large amount of biomass, which is time-consuming and destructive for the community (van der Loos and Nijland 2021). As an example, von Ammon et al. ( 2018) did not recover 7 NIS out of 48 after metabarcoding of bulk communities from settlement plates. On the other hand, the fact that several authors identified DNA of benthic species in water samples (eg [START_REF] Borrell | DNA in a bottle-Rapid metabarcoding survey for early alerts of invasive species in ports[END_REF][START_REF] Cordier | Multi-marker eDNA metabarcoding survey to assess the environmental impact of three offshore gas platforms in the North Adriatic Sea (Italy)[END_REF], particularly with species-specific approaches (eg [START_REF] Ardura | eDNA and specific primers for early detection of invasive species -A case study on the bivalve Rangia cuneata, currently spreading in Europe[END_REF][START_REF] Simpson | Real-time PCR detection of Didemnum perlucidum (Monniot, 1983) and Didemnum vexillum (Kott, 2002) in an applied routine marine biosecurity context[END_REF], is encouraging. The practicality of water-eDNA sampling drives the need to determine its reliability to monitor biofouling communities in marinas, to understand why metabarcoding is not always able to detect benthic species and to evaluate how these limitations could be overcome [START_REF] Trebitz | Early detection monitoring for aquatic nonindigenous species: Optimizing surveillance, incorporating advanced technologies, and identifying research needs[END_REF][START_REF] Blackman | Advancing the use of molecular methods for routine freshwater macroinvertebrate biomonitoringthe need for calibration experiments[END_REF][START_REF] Darling | The risks of using molecular biodiversity data for incidental detection of species of concern[END_REF][START_REF] Makiola | Key questions for next-generation biomonitoring[END_REF]. Some of the limitations inherent to the use of water-eDNA metabarcoding are already well known, and previous works made suggestions to circumvent them. One of these limitations is the degradation of DNA in water over time which can be partially addressed by using smaller marker regions [START_REF] Taberlet | Environmental DNA[END_REF]. Others, such as DNA transport and dilution or differential shedding rates between species can also be decreased by sampling as close as possible to the target community [START_REF] Antich | Marine biomonitoring with eDNA: Can metabarcoding of water samples cut it as a tool for surveying benthic communities?[END_REF]). However, even when all these factors are taken into account to maximize the chances of species detection, the likelihood of false detections or non-detections is still not negligible. It is therefore crucial to evaluate the remaining biases and investigate possible explanations. In addition, the whole process, from sampling to taxonomic assignment, has rarely been considered at once to determine which steps are the most critical to be optimized.

Here, the capacity of water-eDNA-metabarcoding to detect NIS from biofouling communities in marinas was investigated. The goals were to 1) evaluate the extent of species detection errors, and 2) explore the possible causes for these errors, and propose possible solutions. To this end, water sampling was carried out along floating pontoons in ten marinas and two seasons. This sampling strategy allowed to examine detectability at a regional scale and over time, the latter being particularly important as many benthic sessile NIS display short life cycles. Metabarcoding was performed using three markers (18S, COI, and 16S) to increase the detection capacity. Simultaneously, a list of sessile benthic NIS present in the study marinas was established by identifying morphologically and in situ species sampled within quadrats beneath the same floating pontoons. This list was used to evaluate the number of false negatives (species observed at the time of sampling but not recovered with eDNA), and explore various causes for metabarcoding detection failures, such as sampling effort or bioinformatics processing.

Materials and methods

Sampling

Biofouling communities immersed beneath floating pontoons (ie floating structures used as docks for mooring leisure boats) were sampled in ten marinas around Brittany (France; Fig. 1). These locations are known to harbour different fouling communities since they are spread over two ecoregions sensu [START_REF] Spalding | Marine ecoregions of the world: A bioregionalization of coastal and shelf areas[END_REF], namely the Celtic seas and the North European Atlantic Shelf, characterized by different hydrological and physical parameters and species assemblages, and encompassing a biogeographic transition zone between the Western English Channel and the NE Atlantic [START_REF] Gallon | Twenty years of observed and predicted changes in subtidal red seaweed assemblages along a biogeographical transition zone: inferring potential causes from environmental data[END_REF]. Although native species should particularly differ between these two regions, differences were also observed for NIS, as shown by previous Rapid Assessment Surveys [START_REF] Bishop | Repeated rapid assessment surveys reveal contrasting trends in occupancy of marinas by non-indigenous species on opposite sides of the western English Channel[END_REF]FV and LL, unpublished data). Since many biofouling species are short lived and seasonal, sampling was performed in fall (October) 2017 and spring (May-June) 2018. Two pontoons were selected in each marina, to include potential differences in environmental conditions such as water flow, salinity or type of boats docked (long distance travellers vs. local boats).

Seawater was collected every 5 m along a 50-m transect per pontoon. At each sampling point, 200 mL of seawater were collected in a plastic jar using a sterile 100-mL syringe fixed to a sampling rod and immersed at 1 m below the surface. A total volume of 2 L was thus collected per pontoon (after pooling all sampling points). To investigate the effect of sampled volume, in spring 2018, an additional 2-L replicate was collected, resulting in a total volume of 4 L per pontoon (the two 2-L replicates were processed separately). The seawater content of each jar was immediately filtered on site on a Millipore® Sterivex TM filter unit (0.22 µm) using a Masterflex® L/S® economy drive peristaltic pump. After filtration, 2 mL of preservation buffer (sucrose 0.75 M, Tris 0.05 M pH 8, EDTA 0.04 M) were added before storing the filter at -20°C in a portable freezer, until transfer to the laboratory. All consumables not sold as DNA-free were previously immersed in 12.5 % commercial bleach (ca. 0.65 % hypochlorite) for at least 30 min, rinsed with ultrapure water and placed under UV light for at least 15 min. The sampling rod was immersed in 12.5 % commercial bleach for at least 30 min before sampling in a given marina, and rinsed with tap water between each pontoon. Six controls (ie one in three different marinas for each season) were performed by sampling, for every control, 10 replicates of 200 mL of ultrapure water every 5 m along a 50m transect on a pontoon, with the same equipment, and after applying the aforementioned decontamination protocol, thus mimicking the seawater sampling protocol. The 10 replicates from a pontoon were then pooled, as were the real samples, to reach a total volume of 2 L per control.

A list of sessile benthic NIS present, at the time of water collection, in the biofouling community was established. Four taxonomic classes were targeted, namely Gastropoda, Bivalvia, Ascidiacea and Gymnolaemata known to include a substantial number of NIS in the study region [START_REF] Bishop | Repeated rapid assessment surveys reveal contrasting trends in occupancy of marinas by non-indigenous species on opposite sides of the western English Channel[END_REF] (see below for an explanation). Biofoulers were collected beneath pontoons at the same points where water samples were collected, to maximize the probability to sample the same taxa, as shown by [START_REF] Antich | Marine biomonitoring with eDNA: Can metabarcoding of water samples cut it as a tool for surveying benthic communities?[END_REF]. At each of the ten sampling points, all organisms within a 0.25-m² quadrat were scraped by divers and placed in a closing bag. Importantly, the scrapping was performed after the water sampling to avoid any contamination. Specimens (> ca. 5 mm) were morphologically identified on site, to the lowest possible taxonomic level (family, genus or species). The identified organisms were not systematically collected, nor barcoded but, as part of a previous work [START_REF] Couton | Metabarcoding on planktonic larval stages: an efficient approach for detecting and investigating life cycle dynamics of benthic aliens[END_REF], regular barcoding was carried out to get local references on the four taxonomic groups studied here. In order to refine field identification for erected bryozoans from the class Gymnolaemata, specimens were collected at each site for further laboratory identification.

DNA extraction

Caution was taken to avoid any contamination of DNA extracts, as recommended by [START_REF] Goldberg | Critical considerations for the application of environmental DNA methods to detect aquatic species[END_REF]. All equipment and bench surfaces were DNA decontaminated before use and consumables not sold as DNA-free were processed as detailed above. DNA was extracted from the Sterivex units using the NucleoSnap® Finisher Midi extraction kit (Macherey-Nagel) following the manufacturer's protocol with a few modifications (Supplementary Protocol 1).

Library preparation and sequencing

All steps were performed following strict rules for preventing contamination, such as UV irradiation of all tips, plates and tubes, and use of filter tips. Libraries were prepared using a dual-barcoded, dual-indexed two-step PCR procedure. Each DNA sample was amplified 15 times with each of the three primer pairs targeting a different marker: i) a 313-bp COI portion amplified using primers designed by [START_REF] Leray | A new versatile primer set targeting a short fragment of the mitochondrial COI region for metabarcoding metazoan diversity: application for characterizing coral reef fish gut contents[END_REF], ii) a 350-bp to 450-bp portion of the 18S rDNA V1-V2 region amplified using primers designed by [START_REF] Fonseca | Second-generation environmental sequencing unmasks marine metazoan biodiversity[END_REF], and iii) a 115-bp portion of the 16S rDNA amplified using primers designed by [START_REF] Kelly | Genetic signatures of ecological diversity along an urbanization gradient[END_REF] (fragment sizes excluding primers). Combining these markers would increase the detection ability, as they differ in their taxonomic coverage and resolution, and conservation of primer binding sites [START_REF] Couton | Metabarcoding on planktonic larval stages: an efficient approach for detecting and investigating life cycle dynamics of benthic aliens[END_REF][START_REF] Makiola | Key questions for next-generation biomonitoring[END_REF]. Detailed PCR protocols are available in Supplementary Protocol 2. Five tagged PCR replicates were performed for each sample and marker (Table S1). After this first PCR, the five tagged replicates from the same DNA extraction sample were pooled according to their intensity on the agarose gel visualisation. A second PCR was performed to complete Illumina® adapters and to tag samples with a unique dual-index combination (Table S2). Sequencing was performed for each marker separately on an Illumina® MiSeq sequencer. The COI and 18S markers were sequenced using a 600 cycles v3 protocol and the 16S marker was sequenced using a 300 cycles v2 protocol, both with two index reads.

Reads processing and filtering

After demultiplexing performed by the sequencing machine based on index combination (defining the samples), reads were assigned to each of the five PCR replicates according to their tag combination. Primers and tags were then removed using CUTADAPT v-2.8. A set of amplicon sequence variants (ASVs) was produced using DADA2 v-1.13.1 [START_REF] Callahan | DADA2: High-resolution sample inference from Illumina amplicon data[END_REF]; see Table S3 for detailed parameter values). When demultiplexing, reads can be falsely assigned to a sample when an index combination is not correctly recognized, which is referred to as 'index-jump' [START_REF] Taberlet | Environmental DNA: For Biodiversity Research and Monitoring[END_REF]). To assess this phenomenon, 12 index combinations, not used in the described PCR experiments, and chosen among the 96 available, were added to the MiSeq sequencing sample sheet in order to get the corresponding fastq files. For each ASV, the number of reads assigned to one of these internal control index combinations was divided by the total number of reads in the complete dataset for this same ASV. The maximal proportion occurring in an index control was recorded for each marker (Table S3). Any ASV that did not account for more than this maximal proportion in a sample was discarded from this sample. Furthermore, only ASVs found in at least two out of the five PCR replicates per sample were retained.

Taxonomic assignment

A first taxonomic assignment was performed to assess the proportion of reads assigned to metazoans. For that purpose, each dataset was aligned against references retrieved from the GenBank nt database using the ecotag command from OBITOOLS v-1.2.11 [START_REF] Boyer | OBITOOLS: a UNIXinspired software package for DNA metabarcoding[END_REF] with no minimum identity threshold. To perform taxonomic assignment at lower taxonomic levels, assignment was later performed by aligning all ASVs against a restricted reference database using the BLAST® command line tool [START_REF] Altschul | Basic local alignment search tool[END_REF]). This database was composed of sequences retrieved from GenBank and sequences produced locally [START_REF] Couton | Metabarcoding on planktonic larval stages: an efficient approach for detecting and investigating life cycle dynamics of benthic aliens[END_REF], targeting ten metazoan phyla commonly found in marinas: Annelida, Arthropoda (only Crustacea), Bryozoa, Chordata (only Actinopterygii, Chondrichthyes, and Tunicata), Cnidaria, Echinodermata, Mollusca, Nemertea, Platyhelminthes, and Porifera. Only alignments covering 99% of the subject sequence and displaying a minimum identity threshold (18S: 99%; COI: 92%; 16S: 97%) based on barcoding gaps computed from reference sequences (Figs. S1-S3), were considered. If one ASV matched with several references, it was assigned to the one with the highest identity percentage. If two alignments with different references had the same identity, the ASV was assigned to the lowest common taxonomic rank. All assignments to a rank higher than the family were classified as 'unassigned'.

To evaluate the ability of water-eDNA-metabarcoding to retrieve species observed in the field, the metabarcoding dataset was restricted to the four classes targeted in the quadrats survey (ie Ascidiacea, Bivalvia, Gastropoda, and Gymnolaemata). These classes were chosen because they are known to include a substantial number of NIS in marinas of the study region [START_REF] Bishop | Repeated rapid assessment surveys reveal contrasting trends in occupancy of marinas by non-indigenous species on opposite sides of the western English Channel[END_REF], and because the involved team members have a good expertise for their morphological identification. This expertise is further reinforced by a number of previous studies combining morphological and molecular approaches [START_REF] Bishop | The Southern Hemisphere ascidian Asterocarpa humilis is unrecognised but widely established in NW France and Great Britain[END_REF][START_REF] Bishop | Repeated rapid assessment surveys reveal contrasting trends in occupancy of marinas by non-indigenous species on opposite sides of the western English Channel[END_REF][START_REF] Viard | Cryptic diversity and database errors challenge non-indigenous species surveys: an illustration with Botrylloides spp. in the English Channel and Mediterranean Sea[END_REF][START_REF] Turon | Looks can be deceiving: Didemnum pseudovexillum sp. nov. (Ascidiacea) in European harbours[END_REF]). In addition, for these four classes, local reference data for native species and novel NIS were previously obtained [START_REF] Couton | Metabarcoding on planktonic larval stages: an efficient approach for detecting and investigating life cycle dynamics of benthic aliens[END_REF]). This selection thus allowed minimizing issues due to the incompleteness of reference databases, and better assess the effect of the taxonomic assignment step in the metabarcoding process (ie, use of a curated database).

Results

NIS observed in the field

From the 400 quadrat samples collected, 93 taxa were identified, with differences across sites and seasons (Table S4). Most (n=62) were identified to species, 20 to genus, 8 to family, and 3 to higher levels. Forty-seven sessile or poorly mobile taxa belonged to the four targeted classes (ie Ascidiacea, Bivalvia, Gastropoda, and Gymnolaemata). In these, 15 NIS (incl. two pairs pooled in the field: Botrylloides diegensis and B. violaceus, and Didemnum vexillum and D. pseudovexillum) and three cryptogenic species were identified (Table S4), all previously reported in the study area. Among the 47 taxa observed, only 43 were considered for assessing the ability of metabarcoding to detect them. Ruditapes sp. was removed from the positive control list because it lives buried in soft sediments and is thus likely to be inconsistently recovered in quadrat surveys. Membraniporella nitida, Scruparia ambigua, and Amathia gracilis were excluded because they usually did not fulfil the chosen size criteria of 5 mm, and thus the observed species list might also be biased across locations.

Taxonomic assignment of sequence reads

The MiSeq runs yielded 15,754,233 reads, 13,108,322 reads, and 13,396,162 reads for 18S, COI, and 16S, respectively, resulting in 3972, 4258, and 347 unique ASVs. After filtering, all samples (all tagged PCR replicates combined for each sample) contained a mean of 253,600 reads, 188,853 reads, and 199,910 reads for 18S, COI, and 16S, respectively.

Only a small proportion of reads were assigned to Metazoa for 18S (23%) and COI (24%), contrasting with the results for 16S (98%; Fig. 2). The most abundant metazoan phyla identified across markers were Arthropoda, Chordata, Cnidaria, Annelida, and Mollusca, totalizing 88%, 35% and 76% of the reads for 18S, COI and 16S, respectively, with sharp differences between markers. For instance, bryozoans accounted for 14% of 16S reads but for less than 1% of 18S and COI reads. Differences were also observed when assigning ASVs to the ten targeted metazoan phyla. For instance, almost three times more taxa were identified with 18S, and almost four times more species were identified with COI, as compared to 16S (Table 1). Overall (60 2-L samples), 557 taxa including 409 species were identified by at least one marker, over the ten selected phyla (Table S5-S8). Among the 154 taxa from the four classes compared with morphological data, 114 were identified at the species-level across all markers (Table S5).

Recovery of species known to be present by water-eDNA-metabarcoding

Half of the 43 taxa (n=21) observed in quadrats were unambiguously recovered by water-eDNA-metabarcoding (Fig. 3, column Tot). A higher number were identified with 18S (14) as compared to COI (10) and 16S (5), with 18S being more efficient for Ascidiacea, and the two latter being more suited for Bivalvia and Gymnolaemata (Fig. 3). Four species could not be recovered because reference sequences were lacking for any of the three markers. Five taxa were not identified because of identical reference sequences (ie lack of taxonomic resolution with the markers used). For example, Ascidiella aspersa and A. scabra were distinguished in the quadrats sampling, based on morphology, when metabarcoding only identified them at the genus level, because of identical 18S references for the two species, and amplification failure for this genus with COI and 16S (Figs. S4-S5).

Focusing on the 18 NIS and cryptogenic taxa known to be present, a large proportion (66.7 %) were detected in eDNA with at least one marker (Table 2). Out of the six taxa not recovered, four (Botrylloides violaceus, Crassostrea gigas, Bugulina stolonifera, and B. simplex) had reference sequences identical to sequences of closely related species, resulting in the assignment to the genus. For instance, Bugulina stolonifera and B. simplex share the same sequence for the only marker able to retrieve them (16S). The other two NIS (Didemnum vexillum, and Tricellaria inopinata) remained undetected despite the availability of references for at least one marker, their large abundance in some locations, and their presence in almost all localities at both seasons, suggesting PCR amplification biases with the markers used.

The recovery rate of NIS by water-eDNA-metabarcoding was much lower when examining in details the distribution of taxa, across localities and seasons, with only 23.9 % overlap (119 out of 498 cases; Fig. 3). Focusing on NIS or cryptogenic species, out of the 239 occurrences in quadrats, only 73 (30.5 %) were successfully recovered with water-eDNAmetabarcoding (Fig. 3).

Additional detections with water-eDNA-metabarcoding

Within the four targeted classes, 114 species were detected with water-eDNAmetabarcoding. All species identified were classified as 'expected' vs. 'unexpected', based on previous knowledge on their presence/absence in the study area, as reported in the Roscoff biological species inventory (http://abims.sb-roscoff.fr/inventaires/) and in the literature, or as reported before by the team members involved in this study. Eighteen species were 'unexpected' species, and thus might be novel NIS for the study area. Sixteen of them were assigned with more than 99% identity (Table S9). All were, however, identified with only one marker, except Mytilus trossulus, identified with COI and 16S. None of them were seen in the quadrats.

Regarding the distribution of taxa across localities, water-eDNA-metabarcoding identified taxa in localities where they were not reported based on quadrats sampling in eight cases (eg Ascidia mentula in SM and BLO during spring; Fig. 3). Of these eight cases, only three are associated to a NIS or a cryptogenic species (Crepidula fornicata in MB, Watersipora subatra in ET, and Bugulina fulva in ET). Moreover, water-eDNAmetabarcoding efficiently identified three Molgula species (Molgula socialis, M. bleizi, and M. complanata) when only the genus could be confidently recovered in the field. Finally, this method allowed the identification of two additional NIS, Mya arenaria and Ruditapes philippinarum, known to be present in the study region but living buried in soft sediments.

Effect of the sampling strategy on taxa detection by water-eDNA-metabarcoding

Less than half of the taxa from the ten metazoan phyla (42.5 %) were shared between the two pontoons sampled in a given locality with water-eDNA-metabarcoding (Fig. 4). The proportion of shared taxa ranged between 22.6 % (CAM, fall) and 50.8 % (PG, fall).

Similarly, the total number of taxa was slightly higher when merging the results obtained with the two 2-L replicates (482 taxa) than when using only one of them (436 and 428, for the two series analysed separately), over all marinas, in the spring sampling. This result is consistent at every pontoon, with a significantly higher number of taxa when using 4 L of water than when using one of the two 2-L samples (Wilcoxon tests for paired data: V = 0, P < 0.001 for the two series). When focusing on the four targeted classes, the number of taxa unique to one 2-L replicate ranged from 0 to 8 for 16S and 18S and 0 to 7 for COI (Fig. 5). The proportion of reads assigned to these unique taxa was very low for 16S (ranged from 0 to 24 %; mean value: 1.6 %), but was substantially higher for 18S (ranged from 0 to 66.1 %; mean value: 6.8 %), and even higher for COI (ranged from 0 to 100 %; mean value: 29.5 %). This proportion was largely influenced by the total number of reads associated to all species from the four target groups within each replicate for the different markers. These numbers ranged from 5,439 to 381,749 reads with 16S (mean: 116,582.1), 109 to 37,921 reads with 18S (mean: 8,370.6), and 1 to 6,191 reads with COI (mean: 1,764.7). For example, in the replicates of the pontoon 2 from AW, only two species from the four groups were identified with COI, one different in each replicate associated with 13 and 51 reads respectively (Fig. S6), leading to the proportion of 100% (Fig. 5).

Discussion

The growing 'hardening' of marine coastal areas offers a wide range of new artificial substrates for fouling organisms, many being non-indigenous species (NIS). Regular monitoring of ports and marinas is thus critical for implementing efficient management strategies [START_REF] Trebitz | Early detection monitoring for aquatic nonindigenous species: Optimizing surveillance, incorporating advanced technologies, and identifying research needs[END_REF]. In that sense, species detection through water-eDNAmetabarcoding is an appealing approach promising fast and easy sampling, and reduced costs.

However, its reliability and the extent of its biases when focusing on benthic NIS are still unclear [START_REF] Holman | Detection of introduced and resident marine species using environmental DNA metabarcoding of sediment and water[END_REF][START_REF] Antich | Marine biomonitoring with eDNA: Can metabarcoding of water samples cut it as a tool for surveying benthic communities?[END_REF]. In particular, one need to assess the risks of both false negatives (which species are not detected and why; eg [START_REF] Hansen | The sceptical optimist: challenges and perspectives for the application of environmental DNA in marine fisheries[END_REF]) and false positives (detecting species which are not truly present; [START_REF] Darling | What do you mean by false positive?[END_REF]. Here, the effectiveness of water-eDNA-metabarcoding to identify the presence of biofouling animals (particularly NIS) over the study area was shown, as it correctly recovered half of the 43 taxa, and two third of the 18 NIS or cryptogenic species observed in the field. In addition, as expected, water-eDNA-metabarcoding retrieved species from adjacent and non-targeted micro-habitats, refined the assignment at the species level for 2 taxa identified at higher taxonomic level in the field, and detected one previously unreported species, putatively a novel NIS, in the study area. However, others species remained undetected in eDNA, with important discrepancies locally. These limitations, and solutions to circumvent them, are discussed below.

Improving the quality of reference data and targeting several markers is needed to increase the detection effectiveness

Half of the species observed in quadrats, and one-third of NIS, were not recovered with water-eDNA-metabarcoding, including abundant ones. For instance, the solitary tunicate Ascidiella aspersa, native in the study area, and invasive in other coastal areas in the world, was found in every quadrat sample, reaching up to 384 individuals m -2 in MB (Table S4), but remained unassigned with metabarcoding. The detection failure was due to both a lack of resolution with 18S for this genus (same sequence as A. scabra), and amplification failures for COI and 16S (Figs. S4-S5). Six other abundant NIS (tunicates: Botrylloides violaceus, Didemnum vexillum; bryozoans: Tricellaria inopinata, Bugulina simplex, and Bugulina stolonifera; bivalves: Crassostrea gigas) also remained undetected in the molecular dataset.

At a first glance, these results contrast with those by [START_REF] Antich | Marine biomonitoring with eDNA: Can metabarcoding of water samples cut it as a tool for surveying benthic communities?[END_REF] in which abundant benthic MOTUs were more easily detected in water-eDNA than rare ones. However, in their study, the benthic data were obtained from bulk metabarcoding, and abundant benthic species might have also been missed because of amplification biases or low marker resolution.

The substantial proportion of false negatives observed highlights flaws that may still impede the routine use of water-eDNA-metabarcoding. Those include species-specific DNA shedding rate and decay [START_REF] Andruszkiewicz | Environmental DNA shedding and decay rates from diverse animal forms and thermal regimes[END_REF][START_REF] Holman | How does eDNA decay affect metabarcoding experiments?[END_REF], differential primer binding efficiency between taxa [START_REF] Piñol | The choice of universal primers and the characteristics of the species mixture determine when DNA metabarcoding can be quantitative[END_REF], and issues related to taxonomic assignment. As several studies targeting benthic species showed the occurrence of their DNA in water using species-specific methods (eg [START_REF] Simpson | Real-time PCR detection of Didemnum perlucidum (Monniot, 1983) and Didemnum vexillum (Kott, 2002) in an applied routine marine biosecurity context[END_REF]) their shedding rate must be sufficient for detection. This is why more effort should be dedicated to design new primers targeting markers with high resolution, where the sensitivity of each primer should be reported to identify easily species that cannot be detected with them [START_REF] Xia | Screening marker sensitivity: Optimizing eDNA-based rare species detection[END_REF]. For instance, although abundant in quadrats from every location, the invasive colonial ascidian Didemnum vexillum, was not recovered in water-eDNA, whereas [START_REF] Simpson | Real-time PCR detection of Didemnum perlucidum (Monniot, 1983) and Didemnum vexillum (Kott, 2002) in an applied routine marine biosecurity context[END_REF] detected it in water samples from Australia using species-specific primers. Similarly, the invasive tunicate B. violaceus remained undetected because of identical sequences with congeneric species, although it can be distinguished from the introduced B. diegensis and native B. leachii using genus-specific primers [START_REF] Couton | High-throughput sequencing on preservative ethanol is effective at jointly examining infraspecific and taxonomic diversity, although bioinformatics pipelines do not perform equally[END_REF]. Issues related to taxonomic resolution/accuracy were here (partly) addressed by combining several markers, as suggested by [START_REF] Zhang | Metabarcoding using multiplexed markers increases species detection in complex zooplankton communities[END_REF], and by producing reference sequences for at least one marker for each NIS observed within quadrats.

The availability of reference sequences is another well-known problem, which depends on the marker, COI being the most populated in public databases [START_REF] Porter | Over 2.5 million COI sequences in GenBank and growing[END_REF], or on the taxonomic group. For instance, a barcode search in BOLD revealed that only 14% and 5% of the 2,925 and 5,651 accepted species, for the classes Ascidiacea and Gymnolaemata, respectively, were associated to a COI sequence (WoRMS and BOLD search in August 2020), a proportion that could even be lower when considering quality [START_REF] Paz | Gap analysis of DNA barcoding in ERMS reference libraries for ascidians and cnidarians[END_REF]. This proportion seems higher for NIS: [START_REF] Briski | Are genetic databases sufficiently populated to detect non-indigenous species?[END_REF] reported proportions of 59% and 72% of 45 and 36 NIS, for the same two classes and marker, respectively. These higher values might be explained by the long-lasting and still increasing use of DNA barcoding in the study of marine NIS [START_REF] Duarte | Assessment of species gaps in DNA barcode libraries of non-indigenous species (NIS) occurring in European coastal regions[END_REF]. Such an imbalance in the proportion of sequences available for native and non-indigenous species might, in turn, increase the risk of false detections of new introductions, as will be discussed below.

Improving sampling strategy, data production and data processing to overcome limitations

Increasing the sampling effort and optimizing data processing can substantially decrease the detection failures of water-eDNA-metabarcoding. Sampling water at two pontoons in each marina allowed increasing (sometimes doubling) the number of metazoan taxa recovered. For example, in the three marinas where it was detected with water-eDNAmetabarcoding in spring (BL, CAM, and SM), Asterocarpa humilis was identified from one pontoon only. Furthermore, doubling the volume of water filtered improved the detection of rare species (ie low number of reads), which might be particularly useful for NIS early detection. Although the sampling effort (volume and number of replicates) is within the range of that recommended and/or mostly used in other studies (eg [START_REF] Grey | Effects of sampling effort on biodiversity patterns estimated from environmental DNA metabarcoding surveys[END_REF][START_REF] Holman | Detection of introduced and resident marine species using environmental DNA metabarcoding of sediment and water[END_REF][START_REF] Duarte | Status and prospects of marine NIS detection and monitoring through (e)DNA metabarcoding[END_REF], it was not sufficient to recover all the species observed in the field.

The sampling standards (eg water volume, sampling points) should thus be increased substantially when targeting specific benthic species, such as particular NIS, because their DNA might be scarce in the water, especially those lacking pelagic stages [START_REF] Leduc | Comparing eDNA metabarcoding and species collection for documenting Arctic metazoan biodiversity[END_REF]. This would still keep reduced labor-and time-costs in the field as compared to traditional methods (sampling and analyzing 400 quadrats in the field required eight people over two weeks per season). The results also underlined the importance of seasonal sampling, a much less addressed issue. Because many biofoulers, such as tunicates or erected bryozoans, are short-lived, their abundance can vary greatly depending on the season. Their DNA shedding and decay rates can also differ throughout the year (eg reproduction period; Salter 2018; [START_REF] Wacker | Downstream transport and seasonal variation in freshwater pearl mussel (Margaritifera margaritifera) eDNA concentration[END_REF]. The tunicate Ciona robusta, for example, would not have been identified from spring samples only, which is congruent with what is known about its settlement period (mostly in late summer/autumn) in the study area [START_REF] Bouchemousse | Do settlement dynamics influence competitive interactions between an alien tunicate and its native congener?[END_REF]. In this regard, sampling effort should be maximized, with an emphasis on spatial and temporal replicates.

Data filtering steps are crucial in any metabarcoding analysis, notably to avoid false positives, but it may decrease detection sensitivity. Here, all taxa identified were retained after index-jump and replicate filtering in the whole dataset, with three exceptions (Musculus sp., Bugulina stolonifera, and B. simplex; Figs. S7-S8) but the detection capacity was much lower at the unit level (ie 'species-site-date' combination). Before any corrections, water-eDNAmetabarcoding recovered a given taxon in 41% of all units. This number dropped to 22% after corrections, with 106 units of water-eDNA-metabarcoding detection disappearing.

Considering NIS or cryptogenic species, this proportion decreased from 56% to 30% (Figs.

S7-S8

). PCR replicate filtering, used to limit false positives due to PCR errors [START_REF] Alberdi | Scrutinizing key steps for reliable metabarcoding of environmental samples[END_REF][START_REF] Tsuji | Evaluating intraspecific genetic diversity using environmental DNA and denoising approach: A case study using tank water[END_REF], resulted in 32% loss of detection (Figs. S4-S5), while most losses (68%) occurred after index-jump filtering. Choosing filtering parameters is thus critical and depends on the study aim. For example, von Ammon et al. ( 2018) kept all OTUs, even singletons, to increase their chance of detecting rare species, advocating that the cost of missing even one rare NIS would be higher than that of a false positive. This option might, however, lead to a dramatic increase in the number of false detections due to index-jump. Indeed, in the dataset, all index-jump controls exhibited reads belonging to several ASVs. Index-jump is an important issue very delicate to account for in metabarcoding studies [START_REF] Taberlet | Environmental DNA[END_REF], and more work needs to be done to find the right compromise between the proportion of false positives and false negatives in the context of benthic NIS detection.

Another way to circumvent filtering issues would be to increase the proportion of reads associated to the target species. Most filtering procedures indeed rely on the fact that errors are in low abundance. In most studies, ours included, using universal primers [START_REF] Cowart | Metabarcoding is powerful yet still blind: a comparative analysis of morphological and molecular surveys of seagrass communities[END_REF][START_REF] Grey | Effects of sampling effort on biodiversity patterns estimated from environmental DNA metabarcoding surveys[END_REF][START_REF] Collins | Non-specific amplification compromises environmental DNA metabarcoding with COI[END_REF], the vast majority of either 18S or COI reads were not assigned to metazoans (in this study, 77% and 76%, respectively). As a consequence, the DNA from many biofoulers was likely not amplified in the first place. For example, each species detected within the four targeted classes represented less than 1% of read abundances, except for Ciona intestinalis with 18S (2.9%; Table S9). More effort should thus be directed toward the development of new primer sets for more restricted groups of organisms that could be multiplexed to increase the taxonomic range [START_REF] Zhang | Metabarcoding using multiplexed markers increases species detection in complex zooplankton communities[END_REF][START_REF] Corse | One-locus-several-primers: A strategy to improve the taxonomic and haplotypic coverage in diet metabarcoding studies[END_REF][START_REF] West | eDNA metabarcoding survey reveals fine-scale coral reef community variation across a remote, tropical island ecosystem[END_REF].

Erroneous species assignment challenges the opportunity to detect novel introduced species

One expected outcome of water-eDNA-metabarcoding is the detection of species new to a given area, either introduced or expanding their current distribution range, and not actively looked for (ie passive surveillance). Over the four targeted classes, 18 species yet unreported in the study area were recovered (Table S9). Most were, however, likely the result of erroneous assignments. For example, the ascidian Clavelina meridionalis, known from the southern hemisphere and yet unreported in Europe, was identified by 18S only, with 99.16 % identity. No reference sequence, however, was available for the closely-related native C. lepadiformis, observed in the field and identified with COI (100% identity) that reliably distinguishes these species [START_REF] Pérez-Portela | Phylogenetic relationships of the Clavelinidae and Pycnoclavellidae (Ascidiacea) inferred from mtDNA data[END_REF]. In total, eight species were identified with 18S only, including six showing identity below 100%. Considering the low taxonomic resolution of 18S, and that most of them have native congeners in the study area, these eight species were not considered as novel introduced species, in the absence of other evidence. Three other species were assigned with 100% identity with COI, and might thus be true identifications, yet still not necessarily novel introduced species. Indeed, the tunicate Polycarpa tenera might have been previously misreported in the study area as the Mediterranean species P. gracilis [START_REF] Monniot | Ascidies littorales et bathyales récoltées au cours de la campagne Biaçores: Phlébobranches et Stolidobranches[END_REF][START_REF] Vazquez | The genus Polycarpa (Ascidiacea, Styelidae) on the Atlantic and Mediterranean coasts of the Iberian Peninsula[END_REF]. Similarly, the gastropod Cerithiopsis petanii, described from the Croatian coast [START_REF] Prkić | Description of two new Cerithiopsis from the Croatian coast, with comments on the Cerithiopsis tubercularis complex (Gastropoda, Cerithiopsidae)[END_REF], belongs to the C. tubercularis species complex [START_REF] Modica | DNA-barcoding of sympatric species of ectoparasitic gastropods of the genus Cerithiopsis (Mollusca: Gastropoda: Cerithiopsidae) from Croatia[END_REF], reported in the study area. It could have thus been overlooked by previous surveys. The only likely new record would then be Haminoea orteai, reported in the Mediterranean Sea and the southern part of the Northeast Atlantic [START_REF] Garabedian | Haminoea orteai Talavera, Murillo and Templado, 1987 (Mollusca: Gastropoda: Heterobranchia: Cephalaspidea), a widespread species in the Mediterranean and northeastern Atlantic[END_REF].

Knowing the evolutionary history of the targeted species is also important to avoid false positives. In this study's dataset, ASVs from both mitochondrial markers were assigned to Mytilus trossulus although very similar to M. edulis references (only one gap). The reference sequences for M. trossulus corresponded to individuals from the Baltic Sea, a wellknown hybrid zone between M. trossulus and M. edulis, where the mitochondrial genome of M. trossulus has been fully introgressed by the mitochondrial genome of M. edulis [START_REF] Kijewski | Introgression and mitochondrial DNA heteroplasmy in the Baltic populations of mussels Mytilus trossulus and M. edulis[END_REF]. Aligning the COI ASVs with sequences of M. trossulus from Scotland, which have retained their ancestral mitochondrial genome [START_REF] Zbawicka | Scottish Mytilus trossulus mussels retain ancestral mitochondrial DNA: Complete sequences of male and female mtDNA genomes[END_REF], led to 83.4% identity only, confirming they were not M. trossulus but M. edulis.

These case studies demonstrate that passive detection of novel NIS by using water-eDNA-metabarcoding could lead to false positives, as pointed by [START_REF] Darling | The risks of using molecular biodiversity data for incidental detection of species of concern[END_REF].

Therefore, results need to be confirmed using alternative methods, either traditional and/or more sensitive and targeted molecular approaches such as individual barcoding, qPCR or digital PCR [START_REF] Borrell | Metabarcoding and post-sampling strategies to discover non-indigenous species: A case study in the estuaries of the central south Bay of Biscay[END_REF][START_REF] Harper | Needle in a haystack? A comparison of eDNA metabarcoding and targeted qPCR for detection of the great crested newt (Triturus cristatus)[END_REF][START_REF] Wood | A comparison of droplet digital polymerase chain reaction (PCR), quantitative PCR and metabarcoding for species-specific detection in environmental DNA[END_REF][START_REF] Ardura | Stress resistance for unraveling potential biopollutants. Insights from ballast water community analysis through DNA[END_REF].

Benefitting from metabarcoding of water samples to monitor a wider range of habitats

While water-eDNA-metabarcoding did not recover all species observed, it detected many more taxa by encompassing a wider range of environments. Marinas are composed of diverse micro-habitats, such as pillars, seawalls, floating pontoons, and soft-sediment bottoms, displaying different faunal assemblages and NIS contributions [START_REF] Leclerc | Habitat type drives the distribution of non-indigenous species in fouling communities regardless of associated maritime traffic[END_REF], which all contribute to the local pool of eDNA. Traditional standardized surveillance protocols (eg [START_REF] Hewitt | Revised protocols for baseline port surveys for introduced marine species: survey design sampling protocols and specimen handling[END_REF][START_REF] Helcom | Joint Harmonised Procedure for the Contracting Parties of OSPAR and HELCOM on the Granting of Exemptions Under International Convention for the Control and Management of Ships' Ballast Water and Sediments[END_REF] usually target water, sediment, and various hard substrates to encompass the whole diversity of marinas, but with important time and labor costs. This study showed that water-eDNA-metabarcoding can provide data over a wide range of habitats. Considering the 96 expected species identified with water-eDNA-metabarcoding over the four target classes (Table S9), only 35 were biofoulers, four might eventually live fixed (occasionally producing a byssus; Aequipecten opercularis, Limaria hians, Mimachlamys varia, and Venerupis corrugata), 28 were softbottom species, and 30 were motile gastropods. Focusing on NIS, the bivalves Mya arenaria and Ruditapes philippinarum, known from the study area, were recovered by water-eDNAmetabarcoding, while neither targeted nor expected in quadrats because of their burrowing lifestyle.

A wide variety of management strategies exists, depending on the targeted species but also on the phase of the introduction process this species has reached [START_REF] Robertson | A proposed unified framework to describe the management of biological invasions[END_REF]).

These include measures on transport vectors to limit new arrivals, containment measures to avoid the spread of already established NIS, or suppression or eradication measures to limit the impact of introduced NIS. Whatever the management strategy implemented, however, supporting activities (sensu [START_REF] Robertson | A proposed unified framework to describe the management of biological invasions[END_REF]) are required. In particular there is a dire need to identify NIS and monitor them over time and space, either to report new arrivals or to investigate their spread and putative impact of reported ones. According to the results, water-eDNA-metabarcoding could be a perfect tool for monitoring species in this context. The wide variety of targeted habitats and the ease of sampling allow both for the investigation of NIS spread and putative impact on the communities, as well as allowing for regular sampling.

As a conclusion, the fact that two thirds of NIS present at the time of water sampling were effectively recovered by water-eDNA-metabarcoding supports that this technique is a valuable fast and cost-efficient monitoring method, although not yet ready to be used as a unique tool for marine NIS passive surveillance programs. This results also show that species detection errors (false positives or false negatives) can be limited thanks to the use of multiple markers, the design of suitable primer sets (as performed in [START_REF] Westfall | A new approach to molecular biosurveillance of invasive species using DNA metabarcoding[END_REF], an increased sampling effort, and the building of reliable curated reference databases, including databases specific to NIS [START_REF] Darling | Recommendations for developing and applying genetic tools to assess and manage biological invasions in marine ecosystems[END_REF].

Figures with caption

  Figure 1 A. Location of the sampling sites. SM = Saint-Malo, SQ = Saint-Quay-Portrieux, PG = Perros-Guirec, BLO = Bloscon-Roscoff, AW = L'Aber Wrac'h, MB = Moulin Blanc-Brest, CAM = Camaret-sur-Mer, CON = Concarneau, ET = Étel, TRI = La Trinité-sur-Mer. B. Picture of one of the study marina (SQ), showing sampled pontoons. C. Sampling method (ie, diving under the pontoons) for morphological identification. D. Picture showing all the specimens scraped in a quadrat after sorting on site. E. Seawater sampling method, with seawater collected in a plastic jar using a sterile 100-mL syringe fixed to a sampling rod. Photo credits: Frédérique Viard (B), Wilfried Thomas (C), Laurent Lévêque (D), and Yann Fontana (E).

Figure 2

 2 Figure 2 Percentage of reads assigned to different kingdoms (left) or metazoan phyla (right), over all samples, for each of the three markers, as well as for quadrats data (Quad).

Figure 3

 3 Figure3Comparison between water-eDNA-metabarcoding and morphology-based detection. Only the taxa observed within quadrats and belonging to the four targeted classes are considered. Taxa found with both methods within the same marina are displayed in green, those found only in quadrats are in red, and those only found in water-eDNA are in yellow. The first two panels correspond to samples from fall 2017 and spring 2018, respectively. Metabarcoding detection is recorded across all markers. The column Tot represents the presence of each taxon in the whole dataset. The last three columns represent the presence of a taxon in the whole dataset (all marinas and dates combined) for each marker separately. Black crosses indicate the lack of reference sequences for a particular taxon and D indicates that this marker was not able to discriminate a particular taxon. The grey area represents species that were not isolated during morphological identification in fall 2017. They were all pooled in a unique category called 'erected bryozoans'. See Fig.1for location codes.

Figure 4

 4 Figure 4 Proportion of taxa recovered with water-eDNA-metabarcoding across all markers or within quadrats, in samples from the two pontoons of a marina for a given season (shared) or in samples from only one pontoon (unique). See Fig. 1 for location codes.

Figure 5

 5 Figure 5 Proportion of reads associated to taxa found in only one of the two 2-L replicates (unique taxa) for each pontoon of each marina. This proportion is calculated by dividing the sum of reads for unique taxa by the sum of all reads for the four target groups in each replicate. The results for each replicate are shown separately (one bar per replicate). The number of unique taxa is indicated at the top of each bar. See Fig. 1 for location codes. Results are presented separately for each marker. Detailed and additional data (values per taxa unique to one replicate and for taxa shared between pontoons) are provided in Fig. S6.

Acknowledgments

We thank the Diving and Marine core service from the Roscoff Biological Station, particularly Yann Fontana, Wilfried Thomas and Mathieu Camusat for the quadrat sampling, and Jérôme Coudret and Stéphane Loisel for their help for the field work. We thank Gwenn Tanguy from the Biogenouest Genomer Platform for advice and access to the sequencing facilities, and the Biogenouest ABIMS Platform for access to the calculation and storage resources. This project was supported by the TOTAL Foundation (project AquaNIS2.0). MC acknowledges a PhD grant by Région Bretagne (ENIGME ARED project) and Sorbonne Université (ED 227 'Sciences de la Nature et de l'Homme').

Data availability statement

Raw sequences were deposited on NCBI SRA: BioProject PRJNA744352. The metabarcoding and analyses scripts used in this study are available at https://github.com/joarwrie/benthic_NIS_detection

Disclosure statement

The authors report that there are no competing interests to declare. Table 1 Number and proportion (in parentheses) of ASVs and reads assigned to one of the reference sequences from the restricted database targeting ten metazoan phyla, for each marker (18S, COI, and 16S). The number indicated for 'Taxa' includes assignments to species-, genus-and family-level. The last three columns indicate the number of species, genera and families detected.

Tables

ASVs

Reads Taxa Species Genus Family 18S 16S 173 (49.9%) 7,311,390 (54.6%) 104 65 78 70


Philippe Balbiani
email: balbiani@irit.fr

Szabolcs Mikulás
email: szabolcs@dcs.bbk.ac.uk

Decidability and Complexity via Mosaics of the Temporal Logic of the Lexicographic Products of Unbounded Dense Linear Orders

Keywords: Linear temporal logic, lexicographic product, satisfiability problem, decidability, complexity, mosaic method, decision procedure

This article considers the temporal logic of the lexicographic products of unbounded dense linear orders and provides via mosaics a complete decision procedure in nondeterministic polynomial time for the satisfiability problem it gives rise to.

Introduction

The mosaic method originates in algebraic logic, see [START_REF] Németi | Decidable versions of first order logic and cylindric-relativized set algebras[END_REF], where the existence of a model is proved to be equivalent to the existence of a finite set of partial models verifying some conditions. It has also been applied for proving completeness and decidability of temporal logics over linear flows of time. See [5, section 6.4], or [START_REF] Caleiro | On the mosaic method for many-dimensional modal logics: a case study combining tense and modal operators[END_REF][START_REF] Marx | The mosaic method for temporal logics[END_REF][START_REF] Marx | Local variations on a loose theme: modal logic and decidability[END_REF][START_REF] Reynolds | A decidable temporal logic of parallelism[END_REF]. For their use, specialized systems such as temporal logics must be combined with each other. This has led to the development of techniques for the combination of linear flows of time such as the classical operation of Cartesian product [START_REF] Gabbay | Many-Dimensional Modal Logics: Theory and Applications[END_REF][START_REF] Gabbay | Products of modal logics, part 1[END_REF][START_REF] Kurucz | Combining modal logics[END_REF][START_REF] Reynolds | On the products of linear modal logics[END_REF]. Within the context of modal logic, the operation of lexicographic product of Kripke frames has been introduced as a variant of the operation of Cartesian product. It has also been used for defining the semantical basis of different languages designed for time representation and temporal reasoning from the perspective of non-standard analysis. See [START_REF] Balbiani | Time representation and temporal reasoning from the perspective of non-standard analysis[END_REF][START_REF] Balbiani | Axiomatization and completeness of lexicographic products of modal logics[END_REF][START_REF] Balbiani | Axiomatizing the temporal logic defined over the class of all lexicographic products of dense linear orders without endpoints[END_REF].

In [START_REF] Balbiani | Axiomatizing the temporal logic defined over the class of all lexicographic products of dense linear orders without endpoints[END_REF], the temporal logic of the lexicographic products of unbounded dense linear orders has been considered and its complete axiomatization has been given. The purpose of this paper is to apply the mosaic method for providing a complete decision procedure in nondeterministic polynomial time for the satisfiability problem this temporal logic gives rise to. Its section-by-section breakdown is as follows. Section 2 formally introduces the lexicographic products of unbounded dense linear orders and presents the syntax and the semantics of the temporal logic we will be working with. Sections 3 defines mosaics and collections of mosaics satisfying saturation properties. In Section 4 and 5, we prove the completeness and soundness, respectively, of the mosaic method. Applying these result we prove in Section 6 that the satisfiability problem for our temporal logic is decidable in nondeterministic polynomial time.

Products of Unbounded Dense Linear Orders

Let F 1 = (T 1 , < 1 ) and F 2 = (T 2 , < 2 ) be linear orders. Their lexicographic product is the structure F = (T, ≺ 1 , ≺ 2 ) where

-T = T 1 × T 2 ,
-≺ 1 and ≺ 2 are binary relations on T defined by (s 1 , s 2 )

≺ 1 (t 1 , t 2 ) iff s 1 < 1 t 1 and (s 1 , s 2 ) ≺ 2 (t 1 , t 2 ) iff s 1 = t 1 and s 2 < 2 t 2 .
We define the binary relation

≺ on T by (s 1 , s 2 ) ≺ (t 1 , t 2 ) iff (s 1 , s 2 ) ≺ 1 (t 1 , t 2 ) or (s 1 , s 2 ) ≺ (t 1 , t 2 )
. The effect of the operation of lexicographic product may be described informally as follows: given two linear orders, their lexicographic product is the structure obtained by replacing each point of the first one by a copy of the second one. The global intuitions underlying such an operation is based upon the fact that, depending on the accuracy required or the available knowledge, one can describe a temporal situation at different levels of abstraction. See [4, section I.2.2], or [START_REF] Euzenat | Time granularity[END_REF] for details. In Fig. 1 below, we have

s 1 < 1 t 1 and s 2 < 2 t 2 .
As a result, we have (s

1 , s 2 ) ≺ 2 (s 1 , t 2 ), (s 1 , s 2 ) ≺ 1 (t 1 , s 2 ), (s 1 , s 2 ) ≺ 1 (t 1 , t 2 ), (s 1 , t 2 ) ≺ 1 (t 1 , s 2 ), (s 1 , t 2 ) ≺ 1 (t 1 , t 2 ) and (t 1 , s 2 ) ≺ 2 (t 1 , t 2 ).
It is now time to meet the temporal language we will be working with. Let At be a countable set of atomic formulas (with typical members denoted p, q, etc). We define the set L t of formulas of our temporal language (with typical members denoted ϕ, ψ, etc.) as follows:

-ϕ := p | ⊥ | ¬ϕ | (ϕ ∨ ψ) | G 1 ϕ | G 2 ϕ | H 1 ϕ | H 2 ϕ, ✲ F1 ✻ F2 q s1 q t1 q s2 q t2 q (s1, s2) q (t1, s2)
q (s1, t2) q (t1, t2) the formulas G 1 ϕ, G 2 ϕ, H 1 ϕ and H 2 ϕ being read "ϕ will be true at each point within the future of but not infinitely close to the present point", "ϕ will be true at each instant within the future of and infinitely close to the present instant", "ϕ has been true at each point within the past of but not infinitely close to the present point" and "ϕ has been true at each point within the past of and infinitely close to the present point". We adopt the standard definitions for the remaining Boolean connectives. As usual, we define for all i ∈ {1, 2},

-F i ϕ := ¬G i ¬ϕ, -P i ϕ := ¬H i ¬ϕ, -✸ i ϕ := ϕ ∨ F i ϕ ∨ P i ϕ.
The notion of a subformula is standard.

-M, (s 1 , s 2 ) |= G i ϕ iff M, (t 1 , t 2 ) |= ϕ for every (t 1 , t 2 ) ∈ T 1 × T 2 such that (s 1 , s 2 ) ≺ i (t 1 , t 2 ), -M, (s 1 , s 2 ) |= H i ϕ iff M, (t 1 , t 2 ) |= ϕ for every (t 1 , t 2 ) ∈ T 1 × T 2 such that (t 1 , t 2 ) ≺ i (s 1 , s 2 ).
As a result, for all i ∈ {1, 2},

-M, (s 1 , s 2 ) |= F i ϕ iff M, (t 1 , t 2 ) |= ϕ for some (t 1 , t 2 ) ∈ T 1 × T 2 such that (s 1 , s 2 ) ≺ i (t 1 , t 2 ), -M, (s 1 , s 2 ) |= P i ϕ iff M, (t 1 , t 2 ) |= ϕ for some (t 1 , t 2 ) ∈ T 1 × T 2 such that (t 1 , t 2 ) ≺ i (s 1 , s 2 ), -M, (s 1 , s 2 ) |= ✸ 2 ϕ iff M, (s 1 , t) |= ϕ for some t ∈ T 2 .
M is said to be a model for ϕ iff there exists (s 1 , s 2 ) ∈ T 1 × T 2 such that M, (s 1 , s 2 ) |= ϕ. In this case, we shall also say that ϕ is satisfied in M. Let C 1 and C 2 be classes of linear orders. We shall say that a formula ϕ is satisfiable with respect to (C 1 , C 2 ) iff there exists a linear order F 1 = (T 1 , < 1 ) in C 1 , there exists a linear order F 2 = (T 2 , < 2 ) in C 2 and there exists a valuation

V : At → ℘(T 1 ×T 2 ) such that (F 1 , F 2 , V ) is a model for ϕ. The temporal logic of (C 1 , C 2 )
is the set of all formulas ϕ such that ¬ϕ is not satisfiable with respect to (C 1 , C 2 ). The class of all unbounded dense linear orders will be denoted C ud . [START_REF] Balbiani | Axiomatizing the temporal logic defined over the class of all lexicographic products of dense linear orders without endpoints[END_REF] considers the temporal logic of (C ud , C ud ) and gives its complete axiomatization. The satisfiability problem of this temporal logic is to determine whether a given formula ϕ is satisfiable with respect to (C ud , C ud ).

In order to provide a complete decision procedure in nondeterministic polynomial time for it, we use mosaics.

Until the end of this paper, ξ will denote a fixed formula and Γ will denote the least set of formulas such that ✸ 2 ξ ∈ Γ (recall that ✸ 2 ϕ is defined as ϕ ∨ F 2 ϕ ∨ P 2 ϕ) and ⊤ ∈ Γ , Γ is closed under subformulas and single negations (we identify ¬¬γ with γ) and

-if G 1 ϕ ∈ Γ or H 1 ϕ ∈ Γ , then G 2 ϕ, H 2 ϕ ∈ Γ , -if F 1 ϕ ∈ Γ or P 1 ϕ ∈ Γ , then ✸ 2 ϕ ∈ Γ .
Recall that ξ has at most |ξ| subformulas. Closing this set under single negations gives us at most 2 × |ξ| formulas. Then ✸ 2 ξ yields 2 × |ξ| + 10 formulas (subformulas and their negations). The first requirement above introduces at most 2 new formulas plus their negations, and the last requirement introduces at most 10 new formulas (with negations), for every ϕ. Thus we get that |Γ | ≤ 14 × (2 × |ξ| + 10) + 2 (the 2 is for ⊤ and ⊥).

Let λ be a function such that dom(λ) ⊆ Γ is closed under single negations and ran(λ) ⊆ {0, 1}. We say that λ is adequate if

-⊤ ∈ dom(λ) and λ(⊤) = 1, -for every γ ∈ dom(λ), we have λ(¬γ) = 1 -λ(γ), -for every γ ∨ρ ∈ dom(λ), we have λ(γ ∨ρ) ≥ λ(γ) provided that γ ∈ dom(λ), λ(γ ∨ ρ) ≥ λ(ρ) provided that ρ ∈ dom(λ), and λ(γ ∨ ρ) = max{λ(γ), λ(ρ)} if both γ, ρ ∈ dom(λ).
The reason for the complicated form of the last condition is that generally we do not require that dom(λ) is closed under subformulas. However, when we state a requirement that λ(γ) ∈ {0, 1}, then we implicitly require that γ ∈ dom(λ).

Definition 1. Let i ∈ {1, 2} and (σ, τ ) be a pair of adequate functions. We define the following coherence properties.

G i -coherence σ(G i ϕ) = 1 implies τ (G i ϕ) = τ (ϕ) = 1. H i -coherence τ (H i ϕ) = 1 implies σ(H i ϕ) = σ(ϕ) = 1.
1. A 1-mosaic is a pair (σ, τ ) such that σ and τ are adequate functions, (σ, τ ) satisfies G 1 -and H 1 -coherence and the following transfer conditions.

G-transfer σ(G 1 ϕ) = 1 implies τ (G 2 ϕ) = τ (H 2 ϕ) = 1. H-transfer τ (H 1 ϕ) = 1 implies σ(G 2 ϕ) = σ(H 2 ϕ) = 1. 2. A 2-mosaic is a pair (σ, τ ) such that σ and τ are adequate functions with full domain dom(σ) = dom(τ ) = Γ , (σ, τ ) satisfies G 2 -and H 2 -coherence and the following uniformity conditions. G 1 -uniformity σ(G 1 ϕ) = τ (G 1 ϕ). H 1 -uniformity σ(H 1 ϕ) = τ (H 1 ϕ).
As an example of mosaics take a model M = (F 1 , F 2 , V ) with unbounded, dense linear orders

F 1 = (T 1 , < 1 ) and F 2 = (T 2 , < 2 ) and a valuation V : At → ℘(T 1 × T 2 ). Denote T := T 1 × T 2 . Define for every (s, t) ∈ T , λ (s,t) : Γ → {0, 1} by
λ (s,t) (γ) := 1 if M, (s, t) |= γ 0 otherwise (1)
for every γ ∈ Γ . It is straightforward to check that for every (s, t), (u, v) ∈ T with s < 1 u, the pair (λ (s,t) , λ (u,v) ) is a 1-mosaic (with full domain) -for every (s, t), (s, u) ∈ T with t < 2 u, the pair (λ (s,t) , λ (s,u) ) is a 2-mosaic.

For every s ∈ T 1 , define κ s as follows:

κ s (γ) :=      1 if λ (s,u) (γ) = 1 for every u ∈ T 2 0 if λ (s,u) (γ) = 0 for every u ∈ T 2 undefined otherwise (2)
for every γ ∈ Γ . Then κ s is an adequate function and (κ s , κ t ) is a 1-mosaic whenever s < 1 t. An i-SSM will correspond to a flow of time in dimension i. Definition 2. Let i ∈ {1, 2}. An i-saturated set of mosaics, an i-SSM, is a collection M of i-mosaics such that M satisfies the Density, No-endpoints and the corresponding i-saturation conditions below.

Density If (σ, τ ) ∈ M , then there is µ such that (σ, µ), (µ, τ ) ∈ M . No-endpoints If (σ, τ ) ∈ M , then there are µ, ν such that (µ, σ) ∈ M and (τ, ν) ∈ M . F 1 -saturation-insertion If (σ, τ ) ∈ M , σ(F 1 ϕ) = 1 and τ (F 1 ϕ) = τ (✸ 2 ϕ) = 0, then there is µ such that µ(✸ 2 ϕ) = 1 and (σ, µ), (µ, τ ) ∈ M . F 2 -saturation-insertion If (σ, τ ) ∈ M , σ(F 2 ϕ) = 1 and τ (F 2 ϕ) = τ (ϕ) = 0,
then there is µ such that µ(ϕ) = 1 and (σ, µ), (µ, τ ) ∈ M .

P 1 -saturation-insertion If (σ, τ ) ∈ M , τ (P 1 ϕ) = 1 and σ(P 1 ϕ) = σ(✸ 2 ϕ) = 0, then there is µ such that µ(✸ 2 ϕ) = 1 and (σ, µ), (µ, τ ) ∈ M . P 2 -saturation-insertion If (σ, τ ) ∈ M , τ (P 2 ϕ) = 1 and σ(P 2 ϕ) = σ(ϕ) = 0, then there is µ such that µ(ϕ) = 1 and (σ, µ), (µ, τ ) ∈ M . F 1 -saturation-expansion If (σ, τ ) ∈ M and τ (F 1 ϕ) = 1, then there is µ such that µ(✸ 2 ϕ) = 1 and (τ, µ) ∈ M . F 2 -saturation-expansion If (σ, τ ) ∈ M and τ (F 2 ϕ) = 1, then there is µ such that µ(ϕ) = 1 and (τ, µ) ∈ M . P 1 -saturation-expansion If (σ, τ ) ∈ M and σ(P 1 ϕ) = 1, then there is µ such that µ(✸ 2 ϕ) = 1 and (µ, σ) ∈ M . P 2 -saturation-expansion If (σ, τ ) ∈ M and σ(P 2 ϕ) = 1, then there is µ such that µ(ϕ) = 1 and (µ, σ) ∈ M .
That is, besides the Density and No-endpoint conditions, a 1-SSM should satisfy the F 1 -saturation and P 1 -saturation conditions and a 2-SSM should satisfy the F 2 -saturation and P 2 -saturation conditions. We say that M is an i-SSM for ϕ if there is (µ, ν) ∈ M such that µ(ϕ) = 1 or ν(ϕ) = 1. Let us continue with our example. The collections

{(λ (s,t) , λ (u,v) ) : (s, t) ≺ 1 (u, v)} and {(κ s , κ u ) : s < 1 u}
of 1-mosaics are 1-SSMs. Fix s ∈ T 1 and consider the set M s of 2-mosaics defined by

M s := {(λ (s,t) , λ (s,u) ) : t, u ∈ T 2 , t < 2 u}.
It is easy to check that M s is a 2-SSM for every s ∈ T 1 . A 1-supermosaic will be a 1-mosaic of two 2-SSMs.

Definition 3. Let M be a 2-SSM. We define λ M by λ M (γ) :=      1 if µ(γ) = ν(γ) = 1 for every (µ, ν) ∈ M 0 if µ(γ) = ν(γ) = 0 for every (µ, ν) ∈ M undefined otherwise (3)
for every γ ∈ Γ . Observe that λ M is an adequate function.

A 1-supermosaic is a pair (M, N ) of 2-SSMs such that (λ M , λ N ) is a 1-mosaic.

In our example, for every s, t ∈ T 1 such that s < 1 t, the pair (M s , M t ) is a 1-supermosaic. A saturated set of 1-supermosaics will correspond to a flow (in dimension 1) of flows (in dimension 2).

Definition 4. A saturated set of 1-supermosaics, a 1-SSS, is a collection Σ of 1-supermosaics such that {(λ M , λ N ) : (M, N ) ∈ Σ} is a 1-SSM.
We say that Σ is a 1-SSS for ϕ if there is (M, N ) ∈ Σ such that λ M (✸ 2 ϕ) = 1 or λ N (✸ 2 ϕ) = 1. Observe that then there is a 2-mosaic (σ, τ ) in one of the 2-SSMs in one of the 1-supermosaics of Σ such that σ(ϕ) = 1 or τ (ϕ) = 1. In our example the set

Σ M := {(M s , M t ) : s, t ∈ T 1 , s < 1 t}
is a 1-SSS and in fact a 1-SSS for ξ if there is (s, t) ∈ T 1 ×T 2 such that M, (s, t) |= ξ. Our running example should convince the reader that satisfiability of ξ implies the existence of a 1-SSS for ξ. But we want to be more economical in creating the 1-SSS; we will describe the procedure for creating a smaller 1-SSS in Section 5.

First we show how to create a model from a 1-SSS, though.

Completeness

In this section we show the completeness of the mosaic approach. We will need the following.

Definition 5. Let i ∈ {1, 2} and W = (W, <, λ) be a structure such that (W, <) is a linear order and λ q is an adequate function for every q ∈ W . We say that W is i-consistent if it satisfies for every q ∈ W , the corresponding i-completness and i-soundness conditions below.

G i -soundness If λ q (G i γ) = 1, then λ p (G i γ) = λ p (γ) = 1 for every p ∈ W such that q < p. H i -soundness If λ q (H i ρ) = 1, then λ p (H i ρ) = λ p (ρ) = 1 for every p ∈ W such that p < q. F 1 -completeness If λ q (F 1 γ) = 1, then there is p ∈ W such that q < p and λ p (✸ 2 γ) = 1. F 2 -completeness If λ q (F 2 γ) = 1,
then there is p ∈ W such that q < p and λ p (γ) = 1. P 1 -completeness If λ q (P 1 ρ) = 1, then there is p ∈ W such that p < q and λ p (✸ 2 γ) = 1. P 2 -completeness If λ q (P 2 ρ) = 1, then there is p ∈ W such that p < q and λ p (γ) = 1.

That is, a 1-consistent structure must satisfy the G 1 -soundness, H 1 -soundness, F 1 -completeness and P 1 -completeness conditions, and a 2-consistent structure satisfies the G 2 -soundness, H 2 -soundness, F 2 -completeness and P 2 -completeness conditions. Let W = (W, <, λ) be a structure such that (W, <) is a linear order and λ q is an adequate function for every q ∈ W . A future defect of W is a pair (q, γ) such that λ q (F i γ) = 1 but there is no p > q such that λ p satisfies the requirements in the F i -completeness condition above. Past defects are defined similarly. Below we will construct a i-complete (i.e., without defects) and i-sound structure from an i-SSM, see Case 1 and 2 in the proof of Lemma 1 below, where we construct the required future and past witnesses for the defects. In addition, we need that the constructed structure is dense and without endpoints. That is why we will need Case 3 and 4, where we construct new successors and predecessors for each point in the linear order, which in the limit of the construction yields a dense linear order without endpoints. Lemma 1. Let i ∈ {1, 2}. Assume that M is an i-SSM for ϕ. Then there is an i-consistent structure Q M = (Q M , <, λ) such that (Q M , <) is isomorphic to the rationals Q and λ q (ϕ) = 1 for some q ∈ Q M .

Proof. We will define the order (Q M , <) and the adequate functions λ q by induction. To this end let us have a countable enumeration D of potential defects {(q, γ, k) : q ∈ Q, γ ∈ Γ, k ∈ {1, 2, 3, 4}} such that every item appears infinitely often. The value of k will indicate the type of the potential defect: future, past, successor, predecessor.

By assumption there is an i-mosaic (µ, ν) ∈ M such that µ(ϕ) = 1 or ν(ϕ) = 1. In the base step of the construction we define the finite order Q 1 = {0, 1} with 0 < 1 and functions λ 0 = µ and λ 1 = ν. Obviously the soundness conditions restricted to Q 1 hold.

For the inductive step assume that we constructed a sound structure Q n consisting of a finite order (Q n , <) = (q 0 < q 1 < . . . < q n ) and adequate functions λ q for q ∈ Q n such that (λ qj , λ qj+1 ) ∈ M for every j < n. Let D(n) = (q, γ, k). If q / ∈ Q n , then we define Q n+1 := Q n . Otherwise we consider the following four cases. If none of the four cases below holds, then we let

Q n+1 := Q n .
Case 1 k = 1, λ q (F i γ) = 1 and for every r ∈ Q n with q < r, we have λ r (✸ 2 γ) = 0 in case i = 1, or λ r (γ) = 0 in case i = 2. We will construct the required witness in the future of q. First assume that for every r with q < r, we have λ r (F i γ) = 1 (note that this includes the case q = q n ). The i-mosaic (λ qn-1 , λ qn ) ∈ M . By F i -saturation-expansion there is an i-mosaic

(λ qn , µ) ∈ M such that -µ(✸ 2 γ) = 1 if i = 1 -µ(γ) = 1 if i = 2.
In this case we define (Q n+1 , <) := (q 0 < q 1 < . . . < q n < p) for some p ∈ Q such that q n < p and let λ p := µ. Next assume that there is r with q < r such that λ r (F i γ) = 0. Let m be such that q m is minimal in Q n with respect to this property. Consider the i-mosaic (λ qm-1 , λ qm ) ∈ M . By F i -saturationinsertion there is an adequate function µ such that (λ qn-1 , µ), (µ,

λ qn ) ∈ M and -µ(✸ 2 γ) = 1 if i = 1 -µ(γ) = 1 if i = 2.
Then we let (Q n+1 , <) := (q 0 < . . . < q m-1 < p < q m < . . . < q n ) for some p ∈ Q such that q m-1 < p < q m and define λ p := µ. Case 2 k = 2, λ q (P i γ) = 1 and for every r ∈ Q n with r < q we have λ r (✸

2 γ) = 0 if i = 1, or λ r (γ) = 0 if i = 2.
A completely analogous construction to Case 1 provides the required witness in the past of q. Case 3 k = 3.

We will construct a new successor for q. In the case q = q n , consider (λ qn-1 , λ qn ) ∈ M . By the No-endpoints condition, we have an i-mosaic (λ qn , µ) ∈ M . We define (Q n+1 , <) := (q 0 < q 1 < . . . < q n < p) for some p ∈ Q such that q n < p and let λ p := µ. Now assume that q = q m < q n . Consider the i-mosaic (λ qm , λ qm+1 ) ∈ M . Then there is an adequate function µ such that (λ qm , µ), (µ, λ qm+1 ) ∈ M , by the Density condition. Then we let (Q n+1 , <) := (q 0 < . . . < q m < p < q m+1 < . . . < q n ) for some p ∈ Q such that q m-1 < p < q m and define λ p := µ. Case 4 k = 4.

A completely analogous construction to Case 3 provides a new predecessor of q.

It is easy to check that Q n+1 is sound in every case, since it consists of elements of M . Let Q M = (Q M , <) := n∈ω Q n (recall that we defined λ q in the step we created q for every q ∈ Q M ). It is easy to see that (Q M , <) is a countable linear order which is dense and does not have endpoints (by Case 3 and 4), hence isomorphic to Q. Since we considered every potential defects infinitely often, it follows that Q M does not contain any future or past defect in dimension i.

That is, if i = 1 and λ q (F 1 γ) = 1, then there is p ∈ Q M such that q < p and λ p (✸ 2 γ) = 1, and if i = 2 and λ q (F 2 γ) = 1, then there is p ∈ Q M such that q < p and λ p (γ) = 1 (and similarly for past formulas). Hence Q M is i-consistent. ⊓ ⊔ Next we apply Lemma 1 in both dimensions to construct a model from a 1-SSS.

Lemma 2. If there is a 1-SSS for ξ, then there is a model M for ξ. Furthermore, M can be chosen to be the lexicographic product of the rationals with some valuation

V : M = (Q, Q, V ). Proof. Let Σ be a 1-SSS for ξ. Thus Σ is a collection of 1-supermosaics (M, N ) such that {(λ M , λ N ) : (M, N ) ∈ Σ} is a 1-SSM. Furthermore, there is (M, N ) ∈ Σ such that λ M (✸ 2 ξ) = 1 or λ N (✸ 2 ξ) = 1.
We apply Lemma 1 to get the 1-consistent structure

Q Σ = (Q Σ , < 1 , λ) such that (Q Σ , < 1 ) is isomorphic to Q and λ q (✸ 2 ξ) = 1 for some q ∈ Q Σ . By the construction of Q Σ , for every q ∈ Q Σ , there is a 2-SSM M such that λ q = λ M .
Thus we can assume that there is a function f : q → M with domain Q Σ . For every q ∈ Q Σ , we apply Lemma 1 to f (q) = M . Hence, we get a 2-consistent structure Q f (q) = (Q f (q) , < 2 , λ) such that (Q f (q) , < 2 ) is isomorphic to Q, and for every r q ∈ Q f (q) , the adequate function λ rq has full domain Γ (since f (q) = M is a 2-SSM).

Let us replace every q ∈ Q Σ with the copy (Q f (q) , < 2 ) of Q (say, mapping q to 0). Thus we get a grid Q × Q such that the elements (q, r) have the property that r = r q ∈ Q f (q) . Hence to every (q, r) ∈ Q × Q we can associate a full adequate function λ (q,r) := λ rq .

Let M = (Q, Q, V ) be the model defined by the valuation V :

V (p) := {(q, r) ∈ Q × Q : λ (q,r) (p) = 1}
for every atomic proposition p. An easy formula-induction, using 1-consistency of (Q Σ , < 1 , λ) and 2-consistency of (Q f (q) , < 2 ), establishes that M, (q, r) |= ϕ iff λ (q,r) (ϕ) = 1 for every ϕ ∈ Γ . Since we have λ q (✸ 2 ξ) = 1 for some q ∈ Q Σ , we also get that λ(q, r)(ξ) = 1 for some r ∈ Q f (q) by F 2 /P 2 -completeness. Hence M, (q, r) |= ξ, that is, M is a model satisfying ξ. ⊓ ⊔

Soundness

For the reverse direction we also compute an upper bound on the size of the required 1-SSS. Definition 6. Let W i = (W i , < i , λ) be an i-consistent structure. For i = 1 we define the following transfer conditions: for every p, q ∈ W 1 such that p < 1 q, G-transfer λ p (G

1 ϕ) = 1 implies λ q (G 2 ϕ) = λ q (H 2 ϕ) = 1, H-transfer λ q (H 1 ϕ) = 1 implies λ p (G 2 ϕ) = λ p (H 2 ϕ) = 1.
For i = 2 we define the following uniformity conditions: for every p, q ∈ W 2 ,

G 1 -uniformity λ p (G 1 ϕ) = λ q (G 1 ϕ), H 1 -uniformity λ p (H 1 ϕ) = λ q (H 1 ϕ).
We will need the following technical lemma.

Lemma 3. Fix i ∈ {1, 2}. Let W i = (W i , < i , λ) be an i-consistent structure such that (W i , < i ) is a dense, linear order without endpoints. Assume that W i satisfies the Gand H-transfer conditions if i = 1, and the G 1 -and H 1 -uniformity conditions if i = 2. Let u ∈ W i and γ ∈ Γ such that λ u (γ) = 1. Then there is an i-SSM M i for γ of size at most (4 × |Γ |) 2 . In fact, M i can be chosen such that for some

U i ⊆ W i with |U i | ≤ 4 × |Γ | M i = {(λ u , λ v ) : u, v ∈ U i , (∃u ′ ∈ W i )(∃v ′ ∈ W i )u ≡ u ′ & v ≡ v ′ & u ′ < i v ′ } where w ≡ w ′ iff λ w = λ w ′ .
Proof. For every w, w ′ ∈ W i , we let w ≡ w ′ iff λ w = λ w ′ . Note that there are finitely many equivalence classes, since Γ is finite. For every formula ϕ ∈ Γ , let W i (ϕ) := {w ∈ W i : λ w (ϕ) = 1}. Let w ϕ be a maximal element of W i (ϕ) (provided that W i (ϕ) is not empty) in the following sense:

(∀w ′ ∈ W i (ϕ))(∃w ′′ ∈ W i (ϕ))w ′ ≤ i w ′′ & w ′′ ≡ w ϕ .
The existence of a maximal element can be easily shown. For every ϕ ∈ Γ choose a maximal element w ϕ from W ϕ . Similarly, for every ϕ ∈ Γ , choose a minimal element w ϕ from W i (ϕ). Let

W - i = {w ϕ , w ϕ : ϕ ∈ Γ }. Note that |W - i | ≤ 2 × |Γ |.

The problem with W -

i is that it may not contain "enough" points to cure density defects. Indeed, consider the unique points in W - i , i.e., those w ∈ W - i such that for every w ′ = w, λ w = λ w ′ . Note that the set X of unique points can be linearly ordered: x 1 < i x 2 < i . . . < i x m . Now consider two unique points x j , x j+1 ∈ W - i such that there is no z ∈ W i with x j < i z < i x j+1 in W i and z ≡ z ′ ∈ W - i for some z ′ . Then we would not be able to insert a point into the mosaic (λ xj , λ xj+1 ).

So let us expand W - i with the required witnesses for density defects. Take the enumeration x 0 < i x 1 < i . . . < i x m of unique points. Since < i is a dense order, there are infinitely many points in each open interval ]x j , x j+1 [= {x : x j < i x < i x j+1 }. Thus, we can choose a point s ∈ ]x j , x j+1 [ such that there are infinitely many points t in ]x j , x j+1 [ with λ s = λ t . Let us denote such a chosen s by s j for every 0 ≤ j < m. Define U

i := W - i ∪ {s j : 0 ≤ j < m}. Note that |U i | ≤ 4 × |Γ |. We claim that M i := {(λ u , λ v ) : u, v ∈ U i , (∃u ′ ∈ W i )(∃v ′ ∈ W i )u ≡ u ′ & v ≡ v ′ & u ′ < i v ′ } is the required i-SSM. Clearly, |M i | ≤ (4 × |Γ |) 2 .
The elements of M i are G iand H i -coherent because W i is sound. The transfer (for i = 1) and uniformity (for i = 2) conditions also hold, since W i has the corresponding properties. Thus every element of M i is an i-mosaic. It remains to show the saturation conditions.

For the F i -saturation-expansion requirement assume that (λ u , λ v ) ∈ M and λ v (F i ϕ) = 1. Let v ′ ∈ W such that v ≡ v ′ . Since λ v ′ (F i ϕ) = 1 and W i is F i -complete, there is z ∈ W i such that v ′ < i z and Temporal logics in which one can assign a proper meaning to the association of statements about different grained temporal domains have been considered. See [START_REF] Euzenat | Time granularity[END_REF][START_REF] Gagné | A nonstandard temporal deductive database system[END_REF][START_REF] Nakamura | Reasoning about hybrid systems based on a nonstandard model[END_REF] for details. Nevertheless, it seems that the results concerning the issues of axiomatization/completeness and decidability/complexity presented in [START_REF] Balbiani | Axiomatizing the temporal logic defined over the class of all lexicographic products of dense linear orders without endpoints[END_REF] and in this paper constitute the first steps towards a temporal logic based on different levels of abstraction. Much remains to be done.

For example, one may consider the lexicographic products of special linear flows of time like Z, Q and R. Concerning the issues of axiomatization and completeness, could transfer results for completeness similar to the ones obtained by Kracht and Wolter [START_REF] Kracht | Properties of independently axiomatizable bimodal logics[END_REF] within the context of independently axiomatizable bimodal logics be obtained in our lexicographic setting? Concerning the issues of decidability and complexity, all normal extensions of S4.3, as proved in [START_REF] Bull | That all normal extensions of S4.3 have the finite model property[END_REF][START_REF] Fine | The logics containing S4.3[END_REF], possess the finite model property and all finitely axiomatizable normal extensions of K4.3, as proved in [START_REF] Zakharyaschev | All finitely axiomatizable normal extensions of K4.3 are decidable[END_REF], are decidable. Moreover, it follows from [START_REF] Litak | All finitely axiomatizable tense logics of linear time flows are CoN P -complete[END_REF] that actually all finitely axiomatizable temporal logics of linear time flows are CoN P -complete. Is it possible to obtain similar results in our lexicographic setting? Or could undecidability results similar to the ones obtained by Reynolds and Zakharyaschev [START_REF] Reynolds | On the products of linear modal logics[END_REF] within the context of the products of the modal logics determined by arbitrarily long linear orders be obtained in our lexicographic setting?

There is also the question of associating with < 1 and < 2 the until-like connectives U 1 and U 2 and the since-like connectives S 1 and S 2 , the formulas ϕU 1 ψ, ϕU 2 ψ, ϕS 1 ψ and ϕS 2 ψ being read as one reads the formulas ϕU ψ and ϕSψ in classical temporal logic, this time with < 1 and < 2 . As yet, nothing has been done concerning the issues of axiomatization/completeness and decidability/complexity these new temporal connectives give rise to.

Fig. 1 .

 1 Fig. 1. Illustration of ≺1 and ≺2

  It is usual to omit parentheses if this does not lead to any ambiguity. The size of a formula ϕ, in symbols |ϕ|, is the number of symbols of ϕ. A model is a structure M = (F 1 , F 2 , V ) where F 1 = (T 1 , < 1 ) and F 2 = (T 2 , < 2 ) are linear orders and V :At → ℘(T 1 × T 2 ) is a valuation. Satisfaction is a ternary relation |= between a model M = (F 1 , F 2 , V ), a pair (s 1 , s 2 ) ∈ T 1 × T 2and a formula ϕ. It is defined by induction on ϕ as usual. In particular, for all i ∈ {1, 2},

Let w be the maximal element in W 1 (✸ 2 ϕ) or W 2 (ϕ) (depending on the value of i) that we put in U i . By the maximality of w, there is z ′ ∈ W i such that z ≤ i z ′ and z ′ ≡ w. By this observation, we get that (λ v , λ w ) ∈ M i as required.

For the F i -saturation-insertion requirement we work out only the case i = 2, since the case i = 1 is completely analogous. So assume that (λ

as well. Thus we can insert the appropriate mosaics into (λ u , λ v ).

Checking the saturation conditions for past formulas is completely analogous. The No-endpoints requirement follows from the fact that (W i , < i ) is an unbounded linear order. Indeed, let (λ u , λ v ) ∈ M i and v ′ ∈ W i such that v ≡ v ′ . Then there is w ∈ W i such that v ′ < i w and λ w (⊤) = 1. Let w be the be the maximal element of W i (⊤). Then (λ v , λ w ) ∈ M i as required.

It remains to show the Density condition. Let (λ u , λ v ) ∈ M i be an arbitrary mosaic and u

So assume that both u ′ and v ′ are unique, say u ′ = x j and v ′ = x j+k . But we defined s j ∈ ]x j , x j+1 [ in this case, and we have (λ u , λ sj ) and (λ sj , λ v ) in M i . Hence we can insert the required mosaics into (λ u , λ v ) in this case as well.

Finally note that we chose a representative from the equivalence class W i (γ), hence M i is indeed an i-SSM for γ.

⊓ ⊔

We are ready to state the reverse of Lemma 2. In the proof, we will apply Lemma 3 in both the "vertical" and "horizontal" dimensions.

Lemma 4. If ξ is satisfiable, then there is a 1-SSS Σ 1 for ξ of size polynomial in terms of the size of ξ. In fact, the number of elements in Σ 1 is bounded by

Proof. Assume that ξ is satisfied in a model, say, M = ((T 1 , < 1 ), (T 2 , < 2 ), V ) and M,(s, t) |= ξ. We recall the definition of λ (p,q) from (1): for every (p, q) ∈ T 1 ×T 2 ,

2 is a 2-consistent structure that satisfies G 1 -and H 1 -uniformity. By applying Lemma 3 we get a 2-SSM M p 2 for ξ (and in fact for ✸ 2 ξ) such that

We define λ p := λ N with N = M p 2 for every p ∈ T 1 . It is straightforward to verify that (T 1 , < 1 , λ) is a 1-consistent structure that satisfies G-and H-transfer. Hence we can apply Lemma 3. Thus there is a 1-SSM Σ 1 for ✸ 2 ξ such that ⊓ ⊔

Complexity

We are ready to provide a complete decision procedure in nondeterministic polynomial time for the satisfiability problem of the temporal logic of the lexicographic products of unbounded dense linear orders.

Theorem 1. The satisfiability problem with respect to (C ud , C ud ) is decidable in nondeterministic polynomial time.

Proof. Given a formula ξ, let us proceed as follows. By Lemma 2 and 4 the above decision procedure is complete.

⊓ ⊔

Recall that in Lemma 2 we constructed a model (Q, Q, V ) for ξ based on the rationals from a 1-SSS for ξ, the existence of which is equivalent to satisfiability of ξ by Lemma 4. Thus we have the following.

Theorem 2. The logic of (C ud , C ud ) coincides with the logic of the lexicographic product (Q, Q) of the rationals with the standard ordering.