Julien Aimonier-Davat
email: julien.aimonier-davat@univ-nantes.fr

Hala Skaf-Molli

Pascal Molli
email: pascal.molli@univ-nantes.fr

Processing SPARQL TOP-k Queries Online with Web Preemption

Keywords: Semantic Web, SPARQL, Web Preemption, top-𝑘 Queries QuWeDa'22:, October 23-24, 2022, Hangzhou, China

Processing top-𝑘 queries on public online SPARQL endpoints often runs into fair use policy quotas and does not complete. Indeed, existing endpoints mainly follow the traditional materialize-and-sort strategy. Although restricted SPARQL servers ensure the termination of top-𝑘 queries without quotas enforcement, they follow the materialize-and-sort approach, resulting in high data transfer and poor performance. In this paper, we propose to extend the Web preemption model with a preemptable partial top-𝑘 operator. This operator drastically reduces data transfer and significantly improves query execution time. Experimental results show a reduction in data transfer by a factor of 100 and a reduction of up to 39% in Wikidata query execution time.

Introduction

Context and motivation. In knowledge graphs, top-𝑘 queries allow users to search for the largest cities in the world, the longest rivers, the highest mountains, the oldest software, etc [START_REF] Ilyas | A survey of top-k query processing techniques in relational database systems[END_REF]. However, processing top-𝑘 queries on public SPARQL endpoints is challenging, mainly due to the fair-use policies of public endpoints that stop queries before termination [START_REF] Soulet | Anytime Large-Scale Analytics of Linked Open Data[END_REF][START_REF] Hasnain | SPORTAL: Profiling the Content of Public SPARQL Endpoints[END_REF]. For instance, a query that just looks for the 10 oldest people on Wikidata runs out of time (cf. figure 1a). Such a problem is not restricted to Wikidata. The query that returns the ten first classes ordered by their name timeout both on Wikidata and DBpedia (cf. figure 1b).

Why are top-𝑘 queries interrupted by quotas? Mainly because SPARQL engines follow the materialize-and-sort approach to answer top-𝑘 queries [START_REF] Magliacane | Efficient Execution of Top-K SPARQL Queries[END_REF], i.e. engines first materialize all the query results, then sort them according to the ORDER-BY clause, and finally keep and return the first 𝑘 results. To return the 10 oldest people on Wikidata, the query depicted in Figure 1a materializes more than 2,8M people. Related works. Many techniques have been proposed to provide early termination or early pruning when processing top-𝑘 queries [START_REF] Ilyas | A survey of top-k query processing techniques in relational database systems[END_REF]. In SPARQL, thanks to sorted access to data, a smart engine can decide to stop the query execution earlier because the remaining mappings are guaranteed not to be part of the top 𝑘 results [START_REF] Magliacane | Efficient Execution of Top-K SPARQL Queries[END_REF][START_REF] Wagner | Pay-as-you-go Approximate Join Top-k Processing for the Web of Data[END_REF]. Although early termination or early pruning can drastically improve execution time, none of them guarantee that a query will terminate before quotas on a public SPARQL endpoint.

To ensure termination of top-𝑘 queries, existing approaches rely on servers that ensure a fair-use policy without quotas, i.e. fairness is guaranteed by a restricted SPARQL interface.

Restricted SPARQL servers such as TPF [START_REF] Verborgh | Triple Pattern Fragments: A low-cost knowledge graph interface for the Web[END_REF], Web preemption [START_REF] Minier | SaGe: Web Preemption for Public SPARQL Query Services[END_REF] or SmartKG [START_REF] Azzam | SMART-KG: Hybrid Shipping for SPARQL Querying on the Web[END_REF] only support a restricted set of SPARQL operators that do not impact the responsiveness of the restricted server. Other SPARQL operators are supported by the client. To the best of our knowledge, efficient evaluation of top-𝑘 queries has not been studied in the context of restricted SPARQL servers. top-𝑘 queries are evaluated following the traditional materialize-and-sort approach, where materialization is done on the client-side. Even if queries are guaranteed to terminate, data transfer and execution time can be prohibitive.

The research question is to study how a restricted server can provide early termination or early pruning while ensuring the fairness of the server and the termination of top-𝑘 queries.

Approach and Contributions.

In this paper, we propose to extend Web preemption with a new preemptable top-𝑘 operator that ensures termination of top-𝑘 queries, while enabling the use of early pruning techniques. The contributions of the paper are the following: [START_REF] Ilyas | A survey of top-k query processing techniques in relational database systems[END_REF] We propose a preemptable top-𝑘 operator whose overhead does not depend on 𝑘, i.e. the server is fair whatever the value of the LIMIT clause. [START_REF] Soulet | Anytime Large-Scale Analytics of Linked Open Data[END_REF] We implement the top-𝑘 operators as an extension of the preemptable SaGe server. [START_REF] Hasnain | SPORTAL: Profiling the Content of Public SPARQL Endpoints[END_REF] The experimental results show that the new operators can improve query execution time by up to 60% and divide the data transfer by 100.

The remainder of this paper is organized as follows. Section 2 introduces SPARQL top-𝑘 queries and briefly recalls the definitions related to our proposal. Section 3 presents the approach for processing top-𝑘 queries using preemptable top-𝑘 operators. Section 4 presents our experimental results. Section 5 summarizes related works. Finally, conclusions and future work are outlined in Section 6.

Preliminaries and backgrounds

In this section, we briefly recall the definitions related to our proposal. We follow the notations from [START_REF] Harris | SPARQL 1.1 Query Language[END_REF][START_REF] Pérez | Semantics and complexity of SPARQL[END_REF] and consider three disjoint sets 𝐼 (IRIs), 𝐿 (literals) and 𝐵 (blank nodes). We denote the set 𝑇 of RDF terms as 𝐼 ∪ 𝐿 ∪ 𝐵. An RDF triple (𝑠, 𝑝, 𝑜) ∈ (𝐼 ∪ 𝐵) × 𝐼 × 𝑇 connects a subject 𝑠 through a predicate 𝑝 to an object 𝑜. An RDF graph 𝒢 is a finite set of RDF triples. We assume the existence of an infinite set 𝑉 of variables, disjoint from the previous sets. A mapping 𝜇 from 𝑉 to 𝑇 is a partial function 𝜇 ∶ 𝑉 → 𝑇. The domain of 𝜇, denoted by 𝑑𝑜𝑚(𝜇), is the subset of 𝑉 where 𝜇 is defined. A SPARQL graph pattern expression 𝑃 is defined recursively as follows:

1. A tuple from (𝑇 ∪ 𝑉 ) × (𝐼 ∪ 𝑉 ) × (𝑇 ∪ 𝑉 ) is a triple graph pattern.

TOP-k Queries

top-𝑘 queries return the top 𝑘 results according to a user-specified ranking (scoring) function. top-𝑘 SPARQL queries can be expressed using ORDER BY and LIMIT clauses that first impose an order on the result set and then limit the number of results. Following [START_REF] Magliacane | Efficient Execution of Top-K SPARQL Queries[END_REF], the ORDER BY clause can be formulated as a ranking function ℱ combining several ranking criteria {𝑏 1 , … , 𝑏 𝑛 }. Given a graph pattern 𝑃, a ranking criterion 𝑏(?𝑥 1 , … , ?𝑥 𝑚 ) is a function defined over a set of 𝑚 variables, where ∀ 𝑖∈[1,𝑚] ∶ ?𝑥 𝑖 ∈ 𝑣𝑎𝑟(𝑃). The evaluation of a ranking criterion 𝑏 on a mapping 𝜇, denoted by 𝑏[𝜇], is the substitution of all variables ?𝑥 𝑖 ∈ 𝑏 by the corresponding values from the mapping, i.e. 𝜇(?𝑥 𝑖 ). Given two mappings 𝜇 1 and 𝜇 2 , 𝜇 1 > 𝜇 2 according to a

ranking function ℱ ({𝑏 1 , … , 𝑏 𝑛 }), denoted by ℱ [𝜇 1 ] > ℱ [𝜇 2 ], iff ∃ 𝑖∈[1,𝑛] ∶ 𝑏 𝑖 [𝜇 1 ] > 𝑏 𝑖 [𝜇 2 ] and ∀ 𝑗∈[1,𝑖[ ∶ 𝑏 𝑗 [𝜇 1 ] = 𝑏 𝑗 [𝜇 2 ].
In order to evaluate the ranking function ℱ, all the variables in 𝑣𝑎𝑟(𝑃) that contribute in the evaluation of ℱ must be bounded. Since OPTIONAL and UNION clauses can introduce unbound variables, we assume all the variables in 𝑣𝑎𝑟(𝑃) to be certain variables as defined in [START_REF] Schmidt | Foundations of SPARQL query optimization[END_REF], i.e. variables that are certainly bounded for every mapping produced by 𝑃. The relaxation of the certain variables constraint is part of the future work.

Web Preemption and TOP-k Queries

Web preemption [START_REF] Minier | SaGe: Web Preemption for Public SPARQL Query Services[END_REF] is the capacity of a Web server to suspend a running SPARQL query after a fixed quantum of time and resume the following waiting query. When suspending a query 𝑄, a preemptable server saves the internal state of all operators of 𝑄 in a saved plan 𝑄 𝑠 , which is sent to the client. The client can continue the execution of 𝑄 by sending 𝑄 𝑠 back to the server. When reading 𝑄 𝑠 , the server restarts query 𝑄 from where it has been stopped. As a preemptable server can restart queries from where they have been stopped and makes a progress at each quantum, it eventually delivers complete results after a bounded number of quanta.

However, Web preemption comes with overheads. The time of the suspend and resume operations represents the overhead in time of a preemptable server. The size of 𝑄 𝑠 represents the overhead in space of a preemptable server and may be transferred over the network each time the server suspends a query. To be tractable, a preemptable server has to minimize these overheads. For this purpose, a preemptable server only implements SPARQL operators that can be saved and resumed in bounded time, i.e. preemptable operators. Other operators are considered as not preemptable and implemented on the client. For instance, the SCAN, JOIN, UNION, LIMIT and FILTER operators just need to manage one mapping at a time, consequently, they can be saved and resumed in bounded time. On the other hand, some SPARQL operators require to materialize mappings, e.g. the ORDER BY operator requires materializing mappings before sorting, while the GROUP BY operator requires materializing the group keys (see [START_REF] Aimonier-Davat | Online approximative SPARQL query processing for COUNT-DISTINCT queries with Web Preemption[END_REF]). As materialization of mappings requires space resources that depends on the size of the data, they cannot be saved in bounded time.

Figure 3 illustrates how Web preemption processes the top-𝑘 query 𝑄 1 over the RDF graph 𝒢 1 , both depicted in Figure 2. First, the client decomposes the query 𝑄 1 into 𝑄 ′ 1 so that only preemptable operators are sent to the preemptable server, i.e. the ORDER BY and LIMIT clauses are removed from 𝑄 1 . Let us suppose that query 𝑄 ′ 1 requires 3 quanta to complete. At the end of each quantum 𝑞 𝑖 , the client receives the mappings 𝜔 𝑖 and asks for the following results by sending the saved plan 𝑄 𝑠 of 𝑄 ′ 1 back to the server. Once all mappings are obtained, the client sorts them according to the ranking function defined by the ORDER BY clause, and apply the slice operator to keep only the top 2 mappings.

Although top-𝑘 queries are expected to transfer only 𝑘 results, in the case of Web preemption, because the ORDER BY operator is implemented on the client-side, all mappings will be transferred anyway Moreover, this execution strategy prevents us from taking advantage of possible optimizations when evaluating SPARQL top-𝑘 queries, such as early termination or early pruning of partial mappings [START_REF] Ilyas | A survey of top-k query processing techniques in relational database systems[END_REF][START_REF] Wagner | Processing SPARQL Property Path Queries Online with Web Preemption[END_REF]. To overcome this issue, one solution could be to apply state-of-art solutions on the client-side. However, this solution requires computing joins on the client, which may drastically impact query execution performance [START_REF] Minier | SaGe: Web Preemption for Public SPARQL Query Services[END_REF]. Another solution is to implement a dedicated preemptable iterator to compute top-𝑘 queries on the server.

𝜔 3 = 𝑇 𝑄 ℱ = ⟨𝜇 1 , 𝜇 3 ⟩ Ω = Ω ∪ 𝜔 3 Ω = ⟨𝜇 1 , 𝜇 3 ⟩ 𝜔 1 = ∅, 𝑄 𝑠 [𝑇 𝑄 ℱ = ⟨𝜇 1 , 𝜇 2 ⟩] 𝑄𝑠 𝜔 2 = ∅, 𝑄 𝑠 [𝑇 𝑄 ℱ = ⟨𝜇 1 , 𝜇 3 ⟩] 𝑄𝑠 𝜔 3 , nil 𝑄 1

Preemptable TOP-k Operator

Given a ranking function ℱ, the computation of the top 𝑘 mappings only requires maintaining an ordered list of 𝑘 mappings. If we set an upper bound 𝐾 for 𝑘, a simple iterator as defined by Algorithm 1 is preemptable. Algorithm 1 is a simple adaptation of the "Top-N heapsort" algorithm that is commonly used in the Postgres database. The idea of the Top-N heapsort algorithm is to maintain in a main-memory buffer only the best 𝑘 mappings seen so far. In a realworld configuration, the upper bound 𝐾 should be set by the SPARQL endpoint administrator.

Algorithm 1 relies on a data structure When the query is suspended (resp. resumed) by the preemptable SPARQL server, Algorithm 1 just has to save 𝑇 𝑄 ℱ in 𝑄 𝑠 (resp. resume 𝑇 𝑄 ℱ from 𝑄 𝑠 ). As the time and space complexities of saving (resp. resuming) the iterator is in 𝒪(𝑚𝑖𝑛(𝑘, 𝐾 )), Algorithm 1 is preemptable.

𝑇 𝑄 ℱ that maintains a list of mappings 𝜇 1 , … , 𝜇 𝑛 such that ∀ 𝑖∈[1,𝑛[ , ℱ [𝜇 𝑖 ] ≤ ℱ [𝜇 𝑖+1 ].
However, Algorithm 1 has two drawbacks. First, it imposes a maximum value 𝐾 on the number of results returned by top-𝑘 queries. If users want to execute a top-𝑘 query 𝑄 with 𝑘 > 𝐾, they have to rely on the client-side solution, i.e. transferring and sorting all solutions of 𝑄 to end up keeping only 𝑘 solutions. Second, even if the size of the top-𝑘 is bounded by 𝐾, the overhead of saving and resuming the top-𝑘 can have a significant impact on the execution time and the data transfer (when 𝑄 𝑠 is sent to the client), as demonstrated in our experimental study. Problem Statement. Is it possible to implement a preemptable top-𝑘 iterator whose complexity does not depend on 𝑘?

Preemptable Partial TOP-k Iterator

The key idea to avoid depending on 𝑘 is to rely on partial top-𝑘. Using a preemptive Web server, the evaluation of a graph pattern 𝑃 over an RDF graph 𝒢 naturally creates a partition of mappings 𝜔 1 , ..., 𝜔 𝑛 over time, where 𝜔 𝑖 is produced during quantum 𝑞 𝑖 . Intuitively, a partial top-𝑘 is obtained by computing the top 𝑘 mappings on a partition of mappings 𝜔 𝑖 .

Instead of computing the whole top-𝑘 query on the server, which requires saving and resuming it each time the preemption occurs, the server only computes partial top-𝑘 𝑇 1 ℱ , … , 𝑇 𝑛 ℱ Algorithm 2: Server-Side Preemptable Partial top-𝑘 iterator.

Require: ℐ: previous iterator in the pipeline, ℱ: ranking function, 𝑘 ∈ ℕ + : limit 𝑘 of the top-𝑘 query, 𝐾 ∈ ℕ + : maximum limit 𝑘 for top-𝑘 queries, 𝑇 ℱ : empty list of ordered mappings according to ℱ, 𝜇 𝑡 : threshold to enter the top-𝑘. Data: 𝜇 𝑐 : last mapping read. that are sent to the client at the end of each quantum. Thus, a preemptable partial top-𝑘 iterator can be saved and resumed in bounded time.

To comply with the Web preemption model [START_REF] Minier | SaGe: Web Preemption for Public SPARQL Query Services[END_REF], the amount of data transferred to the client per quantum need to be bounded. Consequently, the size of a partial top-𝑘 𝑇 𝑖 ℱ is bounded by 𝐾. If 𝑇 𝑖 ℱ reaches 𝐾 mappings, it will trigger the end of the quantum 𝑞 𝑖 , and 𝑇 𝑖 ℱ will be sent to the client. Thus, end-users are no more limited by 𝐾, but reaching 𝐾 may degrade performance in terms of data transfer and execution time. When the query execution completes, the client just needs to merge all 𝑇 1 ℱ , … , 𝑇 𝑛 ℱ to compute the top 𝑘 solution mappings 𝑇 𝑄 ℱ of the query. However, because the server does not remember the top-𝑘 between quanta, it may transfer up to 𝑚𝑖𝑛(𝑘, 𝐾 ) mappings at each quantum, even if those mappings do not contribute to the top-𝑘. To avoid transferring too many useless mappings, the client sends to the server the mapping with the smallest rank 𝜇 𝑡 (for decreasing order), with the saved plan 𝑄 𝑠 . Using 𝜇 𝑡 as a threshold, the server can discard a part of the solution mappings that do not contribute to the top-𝑘.

Figure 5 illustrates how to compute query 𝑄 1 over the RDF graph 𝒢 1 using Algorithm 2 and 3. Algorithm 2 implements a preemptable iterator that computes a partial top-𝑘 𝑇 𝑖 ℱ based on the mappings produced by ℐ during a quantum 𝑞 𝑖 . Algorithm 3 merges partial top-𝑘 𝑇 𝑖 ℱ produced by the server until the query completes. Let us assume that query 𝑄 1 requires 3 quanta 𝑞 1 , 𝑞 2 and 𝑞 3 to complete, with two mappings produced per quantum. For 𝑞

Early Pruning of Partial Solution Mappings

To improve query execution time, state-of-art approaches try to guarantee early termination of top-𝑘 queries. Unfortunately, existing techniques rely on expensive sort operations that are not preemptable. Although early termination cannot be achieved using Web preemption, early pruning only requires knowing the mapping with the lowest rank among the top 𝑘 mappings [START_REF] Wagner | Processing SPARQL Property Path Queries Online with Web Preemption[END_REF][START_REF] Magliacane | Efficient Execution of Top-K SPARQL Queries[END_REF]. Intuitively, early pruning consists in pruning a partial mapping if its rank is smaller than the lowest of the 𝑘 so far computed mappings. For instance, let us suppose that query 𝑄 1 is executed using a join order that corresponds to the order of triple patterns in the query. In this case, we can use early pruning to skip all the articles published at ESWC. Following the execution depicted in Figure 5, it is known from the first quantum that none of the papers published at ESWC can enter the top-2, because the ESWC conference rank is higher than 2.

Early pruning can be very efficient but highly depends on the join order. Moreover, the opportunity for pruning arises only when 𝑘 (or more) complete results have been produced.

Experimental Study

The purpose of the experimental study is to answer the following questions: (1) Does using a preemptable top-𝑘 operator improve query execution performance? (2) What is the impact 𝑘 and the duration of a quantum on performance? (3) What is the impact of early pruning on performance? (4) How does this approach perform on real-world top-𝑘 queries?

Experimental Setup

To implement our approach, we used the SaGe query engine 1 . Following the Web preemption model, SaGe is divided into a Python preemptable Web server and a JavaScript Web client. top-𝑘 iterators, i.e. Algorithms 1 and 2, have been implemented as an extension of the SaGe preemptable Web server. To make experiments simpler, we created three custom Python clients:

• SaGe is our baseline, i.e. Web preemption without a top-𝑘 iterator. top-𝑘 queries are executed using the ORDER BY and LIMIT operators as explained in section 2.2 and depicted in Figure 3.

• SaGe-top-𝑘 executes top-𝑘 queries using Algorithm 1 defined in section 3. This corresponds to the adaptation of the "Top-N heapsort" operator that is already used in the Postgres database.

• SaGe-partial-top-𝑘 executes top-𝑘 queries using the partial top-𝑘 iterator defined in section 3.1. This corresponds to our contribution without early pruning enabled.

In all experiments, the maximum limit 𝐾, to be set by the SaGe server administrator, was fixed at 𝐾 = 10000. The maximum number of mappings that can be sent to the client per quantum was set at 10000.

Data and

Queries. We used the Waterloo SPARQL Diversity Benchmark (WatDiv2 ) [START_REF] Aluç | Diversified Stress Testing of RDF Data Management Systems[END_REF]. We re-used the RDF graph and the SPARQL queries from the SaGe [START_REF] Minier | SaGe: Web Preemption for Public SPARQL Query Services[END_REF] experimental study. The RDF graph contains 10 7 triples, while the workload contains 193 queries. From these 193 queries, we randomly picked 20 SPARQL conjunctive queries with different shapes and up to 10 joins per query. Because queries do not have ORDER BY clauses, we randomly generated an ORDER BY clause for each query, with up to 2 variables per clause. For the choice of the variables, we privileged those which take Literals as value. For the LIMIT 𝑘 clauses, we experiment different values of 𝑘, namely 10, 100, 1000, 10000.

To test our on real queries, we extracted 20 queries from the Wikidata query logs3 . Queries contain from 1 to 10 joins, an ORDER BY clause with a single variable, and a LIMIT 𝑘 operator with 𝑘 ∈ [START_REF] Ilyas | A survey of top-k query processing techniques in relational database systems[END_REF]10000]. Queries are executed on the 2017-03-13 dump of Wikidata4 with 2262M triples.

All RDF graphs are stored using HDT [START_REF] Fernández | Binary RDF representation for publication and exchange (HDT)[END_REF]. The HDT-backend of the SaGe query engine is used to query the RDF graphs. Code, configurations, queries, and RDF graphs can be found online for reproducible purposes 5 .

Evaluation Metrics. (1)

Execution Time is the time spent executing a query, from when the query is sent to the server until the client returns the last result. (2) Data Transfer is the number of bytes exchanged between the client and the server during the execution of a query. (3) Number of HTTP Calls is the number of HTTP requests sent to the server during the execution of a query.

Hardware Setup. We ran all experiments on a local cloud instance with Ubuntu 20.04.4 LTS, a AMD EPYC 7513 32-Core processor (the VM was configured with 16 vCPUs and 1 thread per core), 1TB SSD (part of a storage pool), and 64GB of RAM. Both the client and the server were running on the same machine.

Software Setup. We used Python v3.9.7, Virtuoso Open Source Edition v7.2.6 and SaGe as of July 24 2022 (7ea3468).

Experimental Results

We first ensured that our top-𝑘 iterators yield complete and correct results. We ran both Virtuoso and the different approaches to check if they provide complete and accurate results for each query using Virtuoso results as the ground truth. Does using a preemptable top-𝑘 operator improve query execution performance? Figure 6 presents the performance achieved by the different approaches on the WatDiv queries. First, let us consider only the results obtained with 𝑘 = 10, without enabling early pruning. We will then see what is the impact of 𝑘 and early pruning on performance. As expected, using a dedicated top-𝑘 iterator significantly improves query execution performance compared to SaGe. First, both SaGe-top-𝑘 and SaGe-partial-top-𝑘 significantly reduce data transfer compared to SaGe that requires to transfer all mappings to the client. SaGe-top-𝑘 only sends the top 𝑘 For each approach and each configuration (𝑑, 𝑘), the number of HTTP calls, the amount of data transferred, and the execution time are averages over the 20 WatDiv queries, with 3 executions per query. When early pruning is enabled, approaches are suffixed by -earlypruning. Note that the scale may vary from one plot to another. mappings, while SaGe-partial-top-𝑘 only transfers the top 𝑘 mappings seen during a quantum that are greater than the threshold computed by the client. Compared to SaGe, SaGe-top-𝑘 and SaGe-partial-top-𝑘 require sending fewer HTTP calls. Because SaGe transfers more mappings, it more often triggers the end of quanta. Indeed, Web preemption limits the number of mappings sent to the client per quantum [START_REF] Minier | SaGe: Web Preemption for Public SPARQL Query Services[END_REF]. When the limit is reached, it triggers the end of the quantum, even if there was time left, and the longer the duration of a quantum, the more likely it is to occur. In terms of execution time, both SaGe-top-𝑘 and SaGe-partial-top-𝑘 are close to SaGe. The slight difference can be explained because SaGe transfers more mappings, increasing serialization times.

What is the impact of 𝑘 and the duration of a quantum? As depicted in Figure 6, 𝑘 does not impact the number of HTTP calls. No matter the value of 𝑘, all approaches require seeing all solution mappings. Consequently, they need the same number of quanta to complete, regardless of 𝑘.

While 𝑘 does not impact the number of HTTP calls, it drastically affects the execution time of SaGe-top-𝑘. Algorithm 1 used by SaGe-top-𝑘 requires to save (resp. load) the current top 𝑘 results each time a query is suspended (resp. resumed). Consequently, when 𝑘 increases, the time spent suspending and resuming top-𝑘 queries increase accordingly. On the WatDiv queries, Figure 7 presents the time spent executing, saving, and resuming queries, both for the SaGe-top-𝑘 and the SaGe-partial-top-𝑘 approaches. As expected, when 𝑘 increases, SaGe-top-𝑘 makes Web preemption overheads increase drastically, to the point where the server spends more time saving and resuming queries than executing them. As a result, SaGe-top-𝑘 can require Figure 8: Average performance on Wikidata queries according to the duration of a quantum. Queries are executed using their default limit 𝑘. For each approach, the number of HTTP calls, the amount of data transferred, and the execution time are averages over the 20 Wikidata queries, with 3 executions per query. When early pruning is enabled, approaches are suffixed by -earlypruning. more time than SaGe to complete. The duration 𝑑 of a quantum also plays an important role. When 𝑑 is small, queries are more often suspended (resp. resumed), increasing Web preemption overheads. Thus, it is tractable to use the SaGe-top-𝑘 approach, but 𝐾 and 𝑑 must be carefully configured by the SPARQL endpoint administrator. The higher the duration of a quantum, the higher 𝐾 could be. Compared to SaGe-top-𝑘, 𝑘 does not impact SaGe-partial-top-𝑘 because the time complexity of saving and resuming a partial top-𝑘 iterator does not depend on 𝑘 (see Figure 7).

This property comes at the cost of an overhead on the data transfer compared to SaGe-top-𝑘. The partial top-𝑘 iterator does not remember the current state of the top-𝑘 between quanta. The only information it has is the threshold computed by the client. If the threshold becomes outdated during a quantum, the server may transfer useless solution mappings that do not contribute to the top-𝑘. Nevertheless, SaGe-partial-top-𝑘 is better than SaGe-top-𝑘 in almost all tested configurations. Because SaGe-top-𝑘 has to transfer the top 𝑘 results each time the query is suspended (resp. resumed), the data transfer can increase rapidly if 𝑘 is large or the query is suspended/resumed too often. In the worst case, SaGe-top-𝑘 can transfer more data than SaGe, i.e. more than all the query solutions.

What is the impact of early pruning? As depicted in Figure 6, early pruning has a significant impact on WatDiv queries. When 𝑘 ≤ 1000, we observe a 60% reduction of the execution time when using SaGe-partial-top-𝑘 (resp. SaGe-top-𝑘) with early pruning enabled, compared to SaGe-partial-top-𝑘 (resp. SaGe-top-𝑘) without early pruning. Because the opportunity for pruning arises only when 𝑘 (or more) complete results have been produced, early pruning has less impact when 𝑘 increases. As a result, we observe a smaller reduction, around 15%, when 𝑘 = 10000. Another critical factor is the join order. The earlier the variables used by the ranking function are evaluated, the more influential the pruning is likely to be. Finally, even if the threshold is only updated between quanta when using SaGe-partial-top-𝑘, it does not significantly impact the efficiency of early pruning compared to SaGe-top-𝑘.

How does this approach perform on real top-𝑘 queries? Figure 8 presents the performance of the different approaches on Wikidata queries, with and without early pruning. Compared to SaGe, both SaGe-top-𝑘 and SaGe-partial-top-𝑘 allow a significant reduction in terms of data transfer. However, SaGe-top-𝑘 requires 𝐾 and 𝑑 to be well configured to avoid increasing Web preemption overheads. As expected, all approaches behave in a similar way in terms of execution time. However, if early pruning is enabled when using SaGe-top-𝑘 and SaGe-partial-top-𝑘, we observe a 35% reduction compared to SaGe.

Related Works

State-of-the-art SPARQL query engines, such as Virtuoso and Jena, rely on a materializeand-sort [START_REF] Ilyas | A survey of top-k query processing techniques in relational database systems[END_REF] approach to process SPARQL top-𝑘 queries. This consists of computing all the matching solutions (e.g., thousands), even if only a limited number 𝑘 of solutions (e.g., ten) is requested [START_REF] Zahmatkesh | Towards a top-K SPARQL query benchmark generator[END_REF]. Consequently, these queries are often long-running queries that require a lot of CPU and memory resources to terminate. To ensure stable and responsive services to users, public SPARQL endpoints set up quotas, e.g. on the number of results returned to the client, the execution time, or the arrival rate. Therefore, many top-𝑘 queries cannot be executed online simply because they reach quotas of the fair-use policies [START_REF] Minier | SaGe: Web Preemption for Public SPARQL Query Services[END_REF][START_REF] Buil-Aranda | Strategies for Executing Federated Queries in SPARQL 1.1[END_REF][START_REF] Soulet | Anytime Large-Scale Analytics of Linked Open Data[END_REF]. Compared to existing public endpoints, our approach ensures that all top-𝑘 join queries terminate without materializing all results.

Early termination and early pruning are common techniques to speed-up the processing of top-𝑘 queries in databases [START_REF] Ilyas | A survey of top-k query processing techniques in relational database systems[END_REF]. Such techniques have been adapted for RDF and SPARQL in [START_REF] Dong | Top-k queries on RDF graphs[END_REF][START_REF] Magliacane | Efficient Execution of Top-K SPARQL Queries[END_REF][START_REF] Wagner | Pay-as-you-go Approximate Join Top-k Processing for the Web of Data[END_REF][START_REF] Wagner | Processing SPARQL Property Path Queries Online with Web Preemption[END_REF]. Early termination allows deciding if it is possible to stop the execution of a running top-𝑘 query. A top-𝑘 query can be stopped as soon as the remaining mappings are guaranteed not to be part of the top-𝑘 results. Early termination relies both on sorted access to data and the computation of upper bounds to enter the top-𝑘. Magliacane et al. [START_REF] Magliacane | Efficient Execution of Top-K SPARQL Queries[END_REF] propose a SPARQL engine-level implementation of rank-aware physical operators allowing early termination. The SPARQL-RANK execution model creates a rank-aware pipeline of operators that incrementally output a ranked set of mappings according to a user-defined scoring function. Unfortunately, rank-aware operators require to materialize the sorted mappings. Following the Web preemption model, rank-join operators are not preemptable because they cannot be saved and resumed in bounded time. Early termination can be further improved thanks to MS-tree indexes, allowing the computation of tighter upper bounds, as proposed by Dong et al. [START_REF] Dong | Top-k queries on RDF graphs[END_REF]. Such an approach is efficient, but the maintenance of extra indexes is costly. Yang et al. [START_REF] Shengqi | Fast top-k search in knowledge graphs[END_REF] propose the STAR framework. SPARQL queries are decomposed into sets of star-shaped queries for which an efficient algorithm to compute the top-𝑘 is provided. Thanks to a join algorithm and an upper bound schema that allows the computation of tight upper bounds, STAR can combine the top-𝑘 of star-shaped queries to compute the top-𝑘 of any SPARQL top-𝑘 query. However, just like SPARQL-RANK, Yang et al. use non-preemptable algorithms due to their space complexities. Wagner et al. [START_REF] Wagner | Pay-as-you-go Approximate Join Top-k Processing for the Web of Data[END_REF] propose an approach to compute top-𝑘 queries without complete result materialization that relies on a probabilistic early pruning method. Given a partial mapping 𝜇 𝑐 , the algorithm predicts with bounded accuracy the probability of 𝜇 𝑐 being part of the top-𝑘 results. Our approach makes use of early pruning, but we aimed to compute fully accurate results as in [START_REF] Wagner | Processing SPARQL Property Path Queries Online with Web Preemption[END_REF].

Conclusion

In this paper, we extended Web preemption with a partial top-𝑘 iterator, significantly improving queries performance. By relying on partial top-𝑘, we can compute top-𝑘 queries with arbitrary large and small values of 𝑘, without increasing Web preemption overheads. Moreover, with a dedicated top-𝑘 iterator, it becomes possible to use early pruning techniques to improve query execution time. In future work, we plan to work on a way to support early termination of top-𝑘 queries in the context of Web preemption. Another path we would like to explore is the evaluation of top-𝑘 queries when the ranking function is defined over aggregates. The evaluation of SPARQL aggregate queries using Web preemption also rely on a partial preemptable iterator [START_REF] Grall | Processing SPARQL Aggregate Queries with Web Preemption[END_REF][START_REF] Aimonier-Davat | Online approximative SPARQL query processing for COUNT-DISTINCT queries with Web Preemption[END_REF]. If our partial top-𝑘 iterator can be used over [START_REF] Grall | Processing SPARQL Aggregate Queries with Web Preemption[END_REF][START_REF] Aimonier-Davat | Online approximative SPARQL query processing for COUNT-DISTINCT queries with Web Preemption[END_REF], a dedicated approach may allow to significantly improve performance.

Figure 1 :

 1 Figure 1: top-𝑘 queries over RDF knowledge graphs

:

  a1 : c o n f e r e n c e :WWW . : a3 : c o n f e r e n c e : ISWC . : a5 : c o n f e r e n c e : ESWC . : a1 : p u b l i c a t i o n 2 0 2 1 . : a3 : p u b l i c a t i o n 2 0 2 2 . : a5 : p u b l i c a t i o n 2 0 2 1 . : a1 : c i t a t i o n s 20 . : a3 : c i t a t i o n s 15 . : a5 : c i t a t i o n s 10 . : a2 : c o n f e r e n c e : ISWC . : a4 : c o n f e r e n c e : ISWC . : a6 : c o n f e r e n c e : ESWC . : a2 : p u b l i c a t i o n 2 0 2

Figure 2 :

 2 Figure 2: A top-𝑘-join query over an RDF knowledge graph

2 q1𝜇 1 =q2𝜇 3 =q3𝜇 5 =Figure 3 : 1 q2 𝜇 3 = 2 q3𝜇 5 =

 213531325 Figure 3: Evaluation of 𝑄 1 on 𝒢 1 using Web preemption [7] without top-𝑘 iterators.

Figure 4 :

 4 Figure 4: Evaluation of 𝑄 1 on 𝒢 1 using Algorithm 1.

14 𝜇

 14 First, the algorithm fills 𝑇 𝑄 ℱ with the first 𝑘 mappings drawn from the Algorithm 1: Server-Side top-𝑘 iterator. Require: ℐ: previous iterator in the pipeline, ℱ: ranking function, 𝑘 ∈ ℕ + : limit 𝑘 of the top-𝑘 query, 𝐾 ∈ ℕ + : maximum limit 𝑘 for top-𝑘 queries. Data: 𝑇 𝑄 ℱ : ordered list of mappings according to ℱ, 𝜇 𝑐 : last mapping read, 𝜇 𝑡 : threshold to enter the top-𝑘. 1 Function GetNext(): 2 if 𝜇 𝑐 = 𝑛𝑖𝑙 then 𝜇 𝑐 = ℐ .𝐺𝑒𝑡𝑁 𝑒𝑥𝑡() 3 while 𝜇 𝑐 ≠ 𝑛𝑖𝑙 do 4 if 𝜇 𝑡 = 𝑛𝑖𝑙 ∨ ℱ [𝜇 𝑐 ] > ℱ [𝜇 𝑡 ] 𝑐 = ℐ .𝐺𝑒𝑡𝑁 𝑒𝑥𝑡() 15 if |𝑇 𝑄 ℱ | > 0 then return 𝑇 𝑄 ℱ .𝑝𝑜𝑝() 𝑐 ⟩ 30 Procedure Close(): 31 ℐ .𝐶𝑙𝑜𝑠𝑒() previous iterator ℐ. Then, each time a new mapping 𝜇 𝑐 is drawn from ℐ, 𝜇 𝑐 is compared with the mapping with the smallest rank in 𝑇 𝑄 ℱ , i.e. 𝜇 1 denoted by 𝜇 𝑡 in Algorithm 1. If ℱ [𝜇 𝑐 ] > ℱ [𝜇 𝑡 ], 𝜇 𝑐 replaces 𝜇 𝑡 in the top 𝑘. Once ℐ exhausted, Algorithm 1 incrementally returns 𝑇 𝑄 ℱ .

1 2 if 3 while 5 NonInterruptible 6 if 8 else 9 𝑇 11 𝜇 𝑐 = 𝑛𝑖𝑙 12 ifMaxTOPKLimitReached 16 𝜇

 235689111216 Function GetNext(): 𝜇 𝑐 = 𝑛𝑖𝑙 then 𝜇 𝑐 = ℐ .𝐺𝑒𝑡𝑁 𝑒𝑥𝑡() 𝜇 𝑐 ≠ 𝑛𝑖𝑙 do 4 if 𝜇 𝑡 = 𝑛𝑖𝑙 ∨ ℱ [𝜇 𝑐 ] > ℱ [𝜇 𝑡 ] then |𝑇 ℱ | < 𝑘 then 7 𝑇 ℱ .𝑎𝑑𝑑(𝜇 𝑐 ) ℱ .𝑟𝑒𝑚𝑜𝑣𝑒(𝜇 𝑡 ) 10 𝑇 ℱ .𝑎𝑑𝑑(𝜇 𝑐 ) |𝑇 ℱ | = 𝑘 then 13 𝜇 𝑡 = 𝑇 ℱ .𝑙𝑎𝑠𝑡() 14 if |𝑇 ℱ | ≥ 𝐾 then 15 raise 𝑐 = ℐ .𝐺𝑒𝑡𝑁 𝑒𝑥𝑡()

𝑄 ℱ = ⟨𝜇 1 ,Algorithm 3 : 2 𝜇 𝑡 = 𝑛𝑖𝑙 3 ( 5 while 6 ( 7 foreach

 1323567 𝜇 3 ⟩, the top 2 mappings of query 𝑄 1 on 𝒢 1 . Client-Side top-𝑘 iterator. Require: 𝑄: SPARQL top-𝑘 query. Data: ℱ: ranking function of 𝑄, 𝑘: limit 𝑘 of 𝑄, 𝑇 𝑄 ℱ : ordered list of mappings according to ℱ, 𝜇 𝑡 : threshold to enter the top-𝑘. 1 Procedure Open(): 𝑄 𝑠 , 𝑇 𝑄 ℱ ) = 𝐸𝑣𝑎𝑙𝑄𝑢𝑒𝑟𝑦(𝑄, 𝜇 𝑡 ) 𝑘 then 𝜇 𝑡 = 𝑇 𝑄 ℱ .𝑙𝑎𝑠𝑡() 𝑄 𝑠 ≠ 𝑛𝑖𝑙 do 𝑄 𝑠 , 𝑇 ℱ ) = 𝐸𝑣𝑎𝑙𝑄𝑢𝑒𝑟𝑦(𝑄 𝑠 , 𝜇 𝑡 ) 𝜇 𝑐 ∈ 𝑇 ℱ (𝜇 𝑡 ) ; 𝑇 𝑄 ℱ .𝑎𝑑𝑑(𝜇 𝑐 )

( a )

 a WatDiv queries with 𝑘 = 10 (b) WatDiv queries with 𝑘 = 100 (c) WatDiv queries with 𝑘 = 1000 (d) WatDiv queries with 𝑘 = 10000

Figure 6 :

 6 Figure 6: Average performance on the WatDiv queries according to 𝑘 and the duration 𝑑 of a quantum.For each approach and each configuration (𝑑, 𝑘), the number of HTTP calls, the amount of data transferred, and the execution time are averages over the 20 WatDiv queries, with 3 executions per query. When early pruning is enabled, approaches are suffixed by -earlypruning. Note that the scale may vary from one plot to another.

  (a) SaGe-partial-top-𝑘 (b) SaGe-top-𝑘

Figure 7 :

 7 Figure 7: Average Execution Time on the WatDiv queries, with Web preemption overheads. Measurements are averages over the 20 WatDiv queries, with 3 executions per query.

  1 , mappings 𝜇 1 and 𝜇 2 are produced by ℐ and inserted into 𝑇 1 ℱ . When preemption occurs, both 𝑄 𝑠 and 𝑇 1 ℱ are sent to the client. Then, the client merges 𝑇 1 ℱ into 𝑇 the client also sends the mapping with the smallest rank, i.e. 𝜇 2 , next to 𝑄 𝑠 . During quantum 𝑞 2 , mappings 𝜇 3 and 𝜇 4 are produced. Because both mappings have a higher rank than 𝜇 2 , they are both inserted into 𝑇 2 ℱ . However, if the server had known the current state of the top-𝑘, it would Evaluation of 𝑄 1 on 𝒢 1 using Algorithms 2 and 3. have known that 𝜇 4 does not contribute to the top-𝑘, but without remembering the whole top 𝑘, like Algorithm 1 in Figure 4, the server cannot safely reject 𝜇 4 . This scenario illustrates the overhead of relying on a partial top-𝑘 iterator. By knowing only 𝜇 𝑡 , the server may transfer mappings that do not contribute to the top-𝑘, such as 𝜇 4 . At the end of quantum 𝑞 2 , 𝑇 2 ℱ and 𝑄 𝑠 are sent to the client, 𝑇 2 ℱ is merged into 𝑇 𝑄 ℱ , and 𝜇 3 becomes the mapping with the lowest rank. Finally, during quantum 𝑞 3 , all generated mappings have a lower rank than 𝜇 3 , consequently, no new mappings are transferred to the client. The query completes with 𝑇

	quantum	Preemptable Server 𝑘 = 2	𝑄 1		Client
		ℱ ({?𝑟, 𝐷𝐸𝑆𝐶(?𝑐𝑠)})
	q1	𝜇 1 = {a: a1, r: 1, cs: 20} 𝜇 2 = {a: a2, r: 2, cs: 10} 𝜔 1 = 𝑇 ℱ = ⟨𝜇 1 , 𝜇 2 ⟩	𝜔 1 , 𝑄 𝑠 𝑄 𝑠 , 𝜇 𝑡	𝑇	𝑄 ℱ = ⟨𝜇 1 , 𝜇 2 ⟩ 𝜇 𝑡 = 𝜇 2
	q2	𝜇 3 = {a: a3, r: 2, cs: 15} 𝜇 4 = {a: a4, r: 2, cs: 12} 𝜔 2 = 𝑇 ℱ = ⟨𝜇 3 , 𝜇 4 ⟩	𝜔 2 , 𝑄 𝑠 𝑄 𝑠 , 𝜇 𝑡	𝑇	𝑄 ℱ = ⟨𝜇 1 , 𝜇 3 ⟩ 𝜇 𝑡 = 𝜇 3
	q3	𝜇 5 = {a: a5, r: 3, cs: 10} 𝜇 6 = {a: a6, r: 3, cs: 2} 𝜔 3 = 𝑇 ℱ = ∅	𝜔 3 , nil	𝑇	𝑄 ℱ = ⟨𝜇 1 , 𝜇 3 ⟩ 𝜇 𝑡 = 𝜇 3
				Ω = 𝑇	𝑄 ℱ = ⟨𝜇 1 , 𝜇 3 ⟩
	Figure 5:

𝑄 ℱ and sends 𝑄 𝑠 back to the server. Because |𝑇 𝑄 ℱ | = 2 = 𝑘,

https://sage.univ-nantes.fr

https://dsg.uwaterloo.ca/watdiv

https://iccl.inf.tu-dresden.de/web/Wikidata_SPARQL_Logs/en

https://www.rdfhdt.org/datasets

https://github.com/momo54/sage-orderby-experiment

Acknowledgments

This work is supported by the ANR-19-CE23-0014 DeKaloG project (CE23 -Intelligence artificielle) and the CominLabs MiKroloG project.


Cedric Saint

Nelly Caccia

Maud Darsonval

Marina Gregoire

Arthur Combeau

Grégory Jubelin

Florence Dubois-Brissonnet

Sabine Leroy

Romain Briandet
email: romain.briandet@inrae.fr

Mickaël Desvaux
email: mickael.desvaux@inrae.fr

Cédric Saint

Marina Grégoire

Spatially localized expression of glutamate decarboxylase gadB in Escherichia coli O157:H7 microcolonies in hydrogel matrix

Keywords: E. coli O157:H7, food matrix, microcolonies, local gene expression, gadB, fluorescent transcriptional fusions, confocal laser scanning microscopy (CLSM), Food safety. CLSM: stands for "Confocal Laser Scanning Microscopy"; LMPA: stands

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

1) Introduction

Escherichia coli is a commensal bacterium found in the gut of mammals that plays an integral part in the digestive process. However, some strains of E. coli are pathogenic and represent a public health issue when they reach the production lines of food industries. Besides obvious evisceration accidents contaminating the meat at the slaughter state, food contamination of animal products (meat and milk products), vegetable or water usually occur through direct or indirect fecal contamination [START_REF] Fairbrother | Escherichia coli: On-farm contamination of animals[END_REF][START_REF] Kintz | Transmission pathways for sporadic Shiga-toxin producing E. coli infections: A systematic review and meta-analysis[END_REF][START_REF] Fremaux | Long-term survival of Shiga toxin-producing Escherichia coli in cattle effluents and environment: an updated review[END_REF] . Storage conditions and holding temperature are then major contributors to bacterial growth and survival in food products [START_REF] Jackson | Heat resistance of Escherichia coli O157:H7 in a nutrient medium and in ground beef patties as influenced by storage and holding temperatures[END_REF] . Shigatoxin (Stx) encoding E. coli (STEC) are the third most common foodborne zoonosis in Europe [START_REF]The European Union One Health[END_REF] and amongst STEC, the serotype O157:H7 is a commonly identified agent in patients. E. coli O157:H7 are enterohaemorrhagic E. coli (EHEC) responsible for bloody diarrhea when the intestinal lining is broken by the presence of Stx. A possible outcome of Stx passing in the bloodstream is damage to the kidneys that can lead to a hemolytic uremic syndrome (HUS), which itself lead to fatal outcomes in 5% of cases [START_REF] Kaper | Pathogenic Escherichia coli[END_REF] . Children are especially at risk and E. coli O157:H7 is still the main cause of pediatric HUS [START_REF] Delignette-Muller | Quantitative risk assessment for Escherichia coli O157:H7 in frozen ground beef patties consumed by young children in French households[END_REF] . At the level of the European union, regulations ask for the absence of this pathogen in 25g of germinated seeds (Regulation CE 209/2013, amendment 2073/2055), but no equivalent exist for meat products. Precautionary measures for meats exist at a state level in the Union (France, DGAL/SSDSA/2016-353). However, the pathogen is still routinely detected at levels above 100 CFU/g in more than 1% of all red meats, the main vector of infection for this pathogen [START_REF]The European Union One Health[END_REF][START_REF] Devleesschauwer | Associating sporadic, foodborne illness caused by Shiga toxin-producing Escherichia coli with specific foods: a systematic review and meta-analysis of case-control studies[END_REF] .

Structured food matrices are a continuity of heterogeneous local microenvironments harboring multiple micro-gradients that can evolve with time and microbial activity [START_REF] Lobete | Recent trends in non-invasive in situ techniques to monitor bacterial colonies in solid (model) food[END_REF] . This leads bacterial cells in food matrices to face different biotopes in which their growth and behavior can diverge from observations in liquid laboratory media. Therefore, environmental conditions of food matrices can prompt high phenotypic diversity in microbial populations as the cells adapt to local microenvironments [START_REF] Schröter | Phenotypic Diversification of Microbial Pathogens-Cooperating and Preparing for the Future[END_REF][START_REF] Stewart | Physiological heterogeneity in biofilms[END_REF] . In comparison with their planktonic counterparts, phenotypic diversity in structured communities can influence bacterial fitness and behavior, such as increase expression of virulence genes [START_REF] Rantsiou | Expression of virulence genes of Listeria monocytogenes in food[END_REF] , higher tolerance to antimicrobials agents and thermal stress [START_REF] Costello | Modelling the microbial dynamics and antimicrobial resistance development of Listeria in viscoelastic food model systems of various structural complexities[END_REF][START_REF] Rowbury | Extracellular sensing and signalling pheromones switch-on thermotolerance and other stress responses in Escherichia coli[END_REF] , or improved cell motility [START_REF] Bhattacharjee | Bacterial hopping and trapping in porous media[END_REF] . While several studies reported emergent properties of bacterial community in food matrices at the population level [START_REF] Costello | Modelling the microbial dynamics and antimicrobial resistance development of Listeria in viscoelastic food model systems of various structural complexities[END_REF][START_REF] Antwi | Influence of a gel microstructure as modified by gelatin concentration on Listeria innocua growth[END_REF][START_REF] Kabanova | Microcalorimetric study of the growth of bacterial colonies of Lactococcus lactis IL1403 in agar gels[END_REF][START_REF] Skandamis | Colonial vs. planktonic type of growth: Mathematical modeling of microbial dynamics on surfaces and in liquid, semi-liquid and solid foods[END_REF][START_REF] Antwi | Modelling the combined effects of structured food model system and lactic acid on Listeria innocua and Lactococcus lactis growth in mono-and coculture[END_REF] , no experimental evidence has yet been reported on the spatial heterogeneity of gene expression at the scale of single cells.

The stomachal phase after food ingestion exposes bacteria to strong acidic pH conditions for several hours and is credited for the highest population reduction of the bacterial load. High tolerance to acidic conditions is therefore necessary for foodborne pathogens, and involved systems that regulate intracellular pH. The glutamic acid decarboxylase (GAD) is one among various systems of acid resistance (AR) commonly found in bacteria able to survive in extreme acid conditions [START_REF] Smith | Escherichia coli has two homologous glutamate decarboxylase genes that map to distinct loci[END_REF][START_REF] Cotter | A glutamate decarboxylase system protects Listeria monocytogenes in gastric fluid[END_REF][START_REF] Nomura | Lactococcus lactis contains only one glutamate decarboxylase gene[END_REF][START_REF] Waterman | The glutamate-dependent acid resistance system of Escherichia coli and Shigella flexneri is inhibited in vitro by l-trans-pyrrolidine-2,4dicarboxylic acid[END_REF][START_REF] Waterman | Transcriptional expression of Escherichia coli glutamate-dependent acid resistance genes gadA and gadBC in an hns rpoS mutant[END_REF] . In E. coli, the GAD system is a three components system: two glutamate decarboxylases, GadA and GadB, which use cytoplasmic free protons by converting glutamate into γ-aminobutyrate (GABA), and the glutamate/GABA antiporter GadC. When the pH is below 5.6, cytoplasmic GadB migrates near the inner membrane to maximize collaboration with transmembrane GadC [START_REF] Capitani | Crystal structure and functional analysis of Escherichia coli glutamate decarboxylase[END_REF] . While gadA is independent in chromosomic location and gadB and gadC are organized in operon, the expression of both gadA and gadBC is transcriptionally regulated by RpoS, two AraC-like regulators GadX and GadW, and by effectors with two inhibitors, the cyclic AMP receptor protein and H-NS. H-NS and RpoS in particular determine the temporal expression, the former inhibiting gadB expression, whereas RpoS promotes the transcription of gadB once the stationary phase is reached [START_REF] De Biase | The response to stationary-phase stress conditions in Escherichia coli: Role and regulation of the glutamic acid decarboxylase system[END_REF] .

To decipher and model fitness and behavior of E. coli O157:H7, synthetic microbial ecology approaches were used in structured food matrices where the complexity of the communities and the factors of influence are reduced to their minimum, but increased in their controllability [START_REF] De Roy | Synthetic microbial ecosystems: an exciting tool to understand and apply microbial communities[END_REF] . Such approaches have been used to describe how matrix parameters affect bacterial growth and morphodynamics of microcolonies [START_REF] Antwi | Influence of a gel microstructure as modified by gelatin concentration on Listeria innocua growth[END_REF][START_REF] Verheyen | Food microstructure and fat content affect growth morphology, growth kinetics, and preferred phase for cell growth of Listeria monocytogenes in fishbased model systems[END_REF] . In a recent contribution, we have shown that the volume, distribution and sphericity of microcolonies of E. coli O157:H7 in hydrogel are dependent of the size of the inoculum, but also on the concentration of acids and NaCl, two environmental stresses frequently encountered in food products [START_REF] Saint Martin | Spatial organisation of Listeria monocytogenes and Escherichia coli O157:H7 cultivated in gel matrices[END_REF] .

In this study, we took advantage of a hydrogel matrix to observe the local expression of gadB in E. coli O157:H7 cells in microcolonies using confocal laser scanning microscopy (CLSM).

To explore the existence of patterns of expression in microcolonies, bacterial strains with a dual transcriptional fluorescent reporter system were engineered to monitor the spatial expression of gadB at the single cell scale. In order to relate the impact that phenotypic heterogeneity in microcolonies can have on community function, the survival of planktonically grown cells to a strongly acidic media mimicking the stomachal passage was further assessed and compared to cells grown or dispersed in hydrogels.

2) Material and methods

Bacterial strains and culture conditions

From cryotubes stored at -80°C, the bacterial strain of E. coli (see genetic construction) was plated on Petri dishes with TSA (Tryptone Soya Agar, Oxoid, USA) and incubated overnight at 37°C. One bacterial colony was picked up and inoculated in TSB (Tryptone Soya Broth, Oxoid, England) before overnight incubation at 37°C under orbital shaking (200 rpm). When required, growth media were supplemented with chloramphenicol (Cm 25 μg/mL; EUROMEDEX, China). The strain Lactococcus lactis ssp. cremoris (Aerial N°2124) was incubated in the same conditions, but without antibiotic supplementation.

Genetic construction

The E. coli O157:H7 CM454 [START_REF] Gobert | Shiga Toxin Produced by Enterohemorrhagic Escherichia coli Inhibits PI3K/NF-κB Signaling Pathway in Globotriaosylceramide-3-Negative Human Intestinal Epithelial Cells[END_REF][START_REF] Chagnot | Colonization of the meat extracellular matrix proteins by O157 and non-O157 enterohemorrhagic Escherichia coli[END_REF] is the wild type strain in this study. We used a T7 polymerase (T7pol) amplification technique inspired from previous reports [START_REF] Graveline | Monitoring F1651 P-like fimbria expression at the single-cell level reveals a highly heterogeneous phenotype[END_REF][START_REF] Lim | A multistep epigenetic switch enables the stable inheritance of DNA methylation states[END_REF] , where the cassette T7pol::Cm R is inserted after the genetic sequence of the gene gadB using the Datsenko-Wanner [START_REF] Datsenko | One-step inactivation of chromosomal genes in Escherichia coli K-12 using PCR products[END_REF] recombination technique (supplementary material Figure S1). Regions of identity were added at the ends of the cassette by the forward primer: 5'CCGAAACTGCAGGGTATTGCCCAACAGAACAGCTTTAAACATACCTGATAACA GGAGGTAAATAATGCACACGATTAACATCGC3' and reverse primer:

5'AAATTGTCCCGAAACGGGTTCGTTTCGGACACCGTTACCGTTAAACATGGAGTT CTGAGGTCATTACTG3'. The correct insertion of T7pol::Cm R in the construct was verified by PCR using the forward primer 5'GGAAGACTACAAAGCCTCCC3' and reverse primer 5' TATTCCTGTCGGAACCGCAC3', for sequencing (Eurofins Genomics, Germany). Based on the sequence of the pHL40 plasmid [START_REF] Graveline | Monitoring F1651 P-like fimbria expression at the single-cell level reveals a highly heterogeneous phenotype[END_REF] , a new plasmid was synthetized (GeneArt, ThermoFisher Scientific, Germany) bearing the P T7pol ::GFPmut3::T p7pol as a GFP reporter but modified by insertion of P BBa_J23119 ::mCherry2::T BBa_B0062 (iGEM parts) for constitutive expression of a red fluorescent protein (RFP). This new plasmid, called pHL60, was transformed into competent gadB::T7pol::Cm R bacterial cells. This system is an indirect reporter of gadB transcription as the transcriptional fusion of gadB::T7 polymerase allows an amplified production of GFP (GFPmut3) from pHL60 and normalization of the level of expression respective to the constitutive expression of the RFP (mCherry2) from the same plasmid, to minimize variations of the fluorescence associated with variations in the number of plasmids from one cell to another. To validate the genetic construction, the reporting planktonic expression of gadB was tested on six pH values from 4.5 to 7.0 using a microplate reader (Synergy H1, Biotek) (Supplementary material Figure S2).

Transparent hydrogel matrices for fluorescent imaging

As previously described [START_REF] Saint Martin | Spatial organisation of Listeria monocytogenes and Escherichia coli O157:H7 cultivated in gel matrices[END_REF] , the hydrogel matrices were obtained by mixing TSB with 0.50 % low melting point agarose (LMPA) (UltraPure Agarose, Invitrogen, USA). After boiling, the liquid LMPA at neutral pH (pH=7) was cooled down to 40°C to prevent thermal stress before the bacterial inoculum was added to obtain 10 S3).

Acidic digestion challenge

To test the ability of E. coli O157:H7 population to survive the strong acidic stress during the stomachal passage, 3 ml of planktonic cells (TSB), planktonic cells grown in TSB and then encased in gel matrix (TSB-LMPA) or gel-colonies cultures (LMPA) (72h, 20°C, pH=7 or pH=5) were transferred in 27 ml of NaCl 9g/L saline solution (control groups) or 27 ml of a saline solution adjusted with HCl (5 M) to a pH of 2. The cups were then incubated at 37°C for 4 hours under a 90-rpm shaking to simulate matrix digestion. All media were then homogenized to disperse bacteria (IKA Ultra-Turrax T25; Janke Kunkel) and the resulting suspensions were immediately plated on agar for enumeration and determination of the log reduction in CFU/ml before and after acidic treatment.

Statistics

Graphics and ANOVA variance analysis were performed with Prism 9 (GraphPad; CA, USA). Differences were considered significant when P<0.05 with P being the critical probability associated with the Fisher test.

3) Results

Spatial patterns of gadB expression in gel-microcolonies

Mean radius of microcolonies grown in neutral or acidic hydrogel showed little differences between neutral (28 µm) and acidic conditions (27 µm), the repartition of populations around these values was noted to not be statistically significant (Figure 1, obtained from measurement on 40 colonies, P>0.05). However, at pH 5, microcolonies appear more circular than at pH = 7 and they harbor at their edge a streamer population shedding from the colony core, forming a crown around it (Figure 2).

Microscopic observations of the fluorescence reporting the expression of gadB in cells inside microcolonies (Figure 2) show radically different patterns between the two hydrogels. In neutral pH conditions, the gene is expressed at a basal level throughout the whole microcolony with no specific spatial arrangement (Figure 2A, supplementary material Figure S4). By contrast, the expression of gadB is strongly overexpressed in the periphery of the colonies formed in acidic hydrogel (Figure 2B, supplementary material Figure S4). Those qualitative observations were reinforced by a quantitative exploration of the radial distribution of gadB expression (Figure 3). For both hydrogels, the genetic expression is monitored by the green fluorescent intensity normalized with the red constitutive fluorescent intensity. 3D kymographs integrating 40 independent microcolonies (X-axis) for each condition represent in color code gadB transcription from the center of the microcolony (Y-axis, d CM =0 µm) to the edges of the colonies and beyond. Where in neutral pH hydrogel gadB expression is low and almost constant over the radius of the microcolonies (Figure 3A), acidic hydrogels present a sharp band of gadB over-expression in between 25 and 30 µm from the center of the microcolonies (Figure 3B). This is consistent with the observed spatial expression as the radius of the microcolonies is 27-28 µm (±5 µm) in these experimental conditions.

Interestingly, when microcolonies merge as they grow, they behave like a single colony in regard to the peripheral gadB spatial expression. Similarly, if two microcolonies are in near contact, the two sides facing each other do not present an over-expression of gadB or the shedding of single cells visible in other areas of the periphery (supplementary material Figure S5).

Control experiments performed with a constitutive expression of the green fluorescence protein did not show the spatialization of the expression as presented above (supplementary material Figure S3). A time-course microscopic analysis allows the observation of gadB expression spatialization in acidic hydrogels as early as microcolonies become visible under the microscope, ~48h after inoculation (data not shown). Finally, the spatial repartition of dead cells in gel-microcolonies as shown by live/dead fluorescent staining indicated a random distribution of the red dead cells, with no preferential localization in the microcolonies associated with cells expressing gadB (supplementary material Figure S6).

Following those results, E. coli O157:H7 was then cultured in the presence of Lactococcus lactis ssp. cremoris (Figure 4). The ability of L. lactis to produce in-situ lactic acid is used to replicate the natural acidification of food matrix containing L. lactis (cheese), or where a progressive accumulation of lactic acid occurs (meat). Exploration of the hydrogel was performed 72-96h after inoculation. Contrary to observations where lactic acid is added in the hydrogel preparation [START_REF] Saint Martin | Spatial organisation of Listeria monocytogenes and Escherichia coli O157:H7 cultivated in gel matrices[END_REF] , microcolonies of E. coli O157:H7 are present and possess the same morphology as seen in mono-cultures in the acidic condition (Figure 4A). Close up on 50 µm thick slices of microcolonies of E. coli O157:H7 in close proximity to microcolonies of L.

Lactis clearly shows the same spatial patterns of gadB expression as previously encountered for the mono-cultures in acidic media (Figure 4B).

Increased survival to acidic stomachal stress of E. coli grown in gel-microcolonies

As the capacity of survival to stomachal acidic stress of E. coli O157:H7 populations is of interest for public health safety, the acid resistance of bacteria grown planktonically or in hydrogel matrices was evaluated by enumeration on agar after acid stress.

Cultures of E. coli O157:H7 adjusted to 10 4 CFU/ml were incubated at neutral (pH=7) or acid pH (pH=5) in either TSB or LMPA. After 96h of incubation at 20°C, the populations reached values of log CFU/ml of 9.4/9.6 in TSB at pH neutral/acid and 9.5/8.6 in LMPA at pH neutral/acid.

Bacteria grown in planktonic conditions (TSB) were highly sensitive to the 4-hours exposition to pH=2 with a total loss of the culturable population (9 log reduction) (Figure 5). In contrast, cells grown as spatially organized colonies in LMPA for 96h presented a statistically high tolerance to this strong acidic stress (P<0.05). The best tolerance was observed for the microcolonies incubated at a pH of 5 with a log reduction as low as 0.29 log CFU/ml, statistically significantly lower than the reduction observed for microcolonies incubated at neutral pH, where the log reduction is 0.78 CFU/ml (P<0.05). To test for interferences of the hydrogel to bacterial acidic stress, planktonic populations cultivated in TSB were encased in LMPA just before the survival test. Log reduction of these control planktonic populations suspended in LMPA presented significant similar sensitivity than planktonic TSB culture (P>0.05), indicating no buffering effect of agarose to stomachal acidic stress.

4) Discussion

The behavior of microbial population in laboratory liquid growth media can strongly deviate from what is observed in real solid food matrices [START_REF] Skandamis | Colonial vs. planktonic type of growth: Mathematical modeling of microbial dynamics on surfaces and in liquid, semi-liquid and solid foods[END_REF][START_REF] Pin | Validating predictive models of food spoilage organisms[END_REF][START_REF] Smith | Evaluation of a Clostridium perfringens predictive model, developed under isothermal conditions in broth, to predict growth in ground beef during cooling[END_REF][START_REF] Baka | Influence of food intrinsic complexity on Listeria monocytogenes growth in/on vacuum-packed model systems at suboptimal temperatures[END_REF][START_REF] Baka | Salmonella Typhimurium and Staphylococcus aureus dynamics in/on variable (micro)structures of fish-based model systems at suboptimal temperatures[END_REF][START_REF] Baka | Dynamics of Listeria monocytogenes at suboptimal temperatures in/on fish-protein based model systems: Effect of (micro)structure and microbial distribution[END_REF] . The environmental heterogeneity of structured media is listed as one of the four main causes of cellular variation, among genetic variation, aging and stochasticity of gene expression [START_REF] Bury-Moné | Stochasticity of gene expression as a motor of epigenetics in bacteria: from individual to collective behaviors[END_REF] . As such, it can trigger a large diversity of phenotypic cell expression in the same biotope, promoting the cohabitation of cells with different spectra of behaviors, such as stress response or virulence [START_REF] Caniça | Antibiotic resistance in foodborne bacteria[END_REF][START_REF] Nielsen | Comparison of heat stress responses of immobilized and planktonic Salmonella enterica serovar Typhimurium[END_REF] . Structured food are not an optimal medium from an exploration perspective as the opacity of numerous food matrices prevents live imaging and microscopic approaches. To overcome these limitations, several studies take advantage of synthetic hydrogelled systems to simplify and control the parameters of growth of embedded bacteria. Here, low melting point agarose is used as a gelling agent in which cells can be dispersed without thermal stress and with tunable textures and media compositions. Thus, in a recent contribution, we have been able to mimic the texture of various food environments such as grounded meat or cheese [START_REF] Saint Martin | Spatial organisation of Listeria monocytogenes and Escherichia coli O157:H7 cultivated in gel matrices[END_REF] . The experiments presented in this work show that the morphology of microcolonies in the media complemented with HCl are different from the neutral pH control, in particular bacteria are shedding from the periphery of the microcolonies. This effect can be explained by a combined action of relaxed gel structures due to low pH and the higher motility of E. coli O157:H7 when acidic conditions are encountered [START_REF] Saint Martin | Spatial organisation of Listeria monocytogenes and Escherichia coli O157:H7 cultivated in gel matrices[END_REF][START_REF] Su | Lysogenic infection of a Shiga toxin 2-converting bacteriophage changes host gene expression, enhances host acid resistance and motility[END_REF] .

In this study, we observed a clear overexpression of gadB for a subpopulation of cells localized in the periphery of microcolonies formed in acidic hydrogels. This gene is overexpressed at levels 2-3 times higher than in neutral conditions, which is in accordance with results obtained in planktonic conditions (Supplementary material Figure S2). We confirmed that this spatialization was neither associated with dead cells (supplementary material Figure S6), nor a limitation of oxygen for GFP maturation in the center of the microcolony (supplementary material Figure S3). The use of a single plasmid bearing both the genes for the constitutive and induced fluorescence means that, at the image analysis step, we prevented bias due to differences in plasmid copy numbers or differences in coloration from a mix of dye/genetic reporters [START_REF] Cinquin | Structure and fluorescence intensity measurements in biofilms[END_REF] . The use of two lasers with different properties of matrix penetration could lead to a bias in the Z axis, but 3D analysis of all the cells in a microcolony reduces the bias as any offset at the bottom of the agglomerate is compensated by an opposite offset at the top.

Spatial patterns of genetic expression were previously reported for other genes in other bacterial species in surface biofilms either on solid or liquid, such as localized expression of E. coli sigma factors and type 1 pili, as well as Pseudomonas aeruginosa β-lactamase in biofilms [START_REF] Lenz | Localized gene expression in Pseudomonas aeruginosa biofilms[END_REF][START_REF] Floyd | Adhesive Fiber Stratification in Uropathogenic Escherichia coli Biofilms Unveils Oxygen-Mediated Control of Type 1 Pili[END_REF][START_REF] Klauck | Spatial organization of different sigma factor activities and c-di-GMP signalling within the three-dimensional landscape of a bacterial biofilm[END_REF] . To our knowledge, such patterns of gene expression were never reported in food or hydrogel matrices. Last experiments of co-cultures of E. coli O157:H7 and L. lactis demonstrate that the pattern of gadB expression could naturally occur in food matrix through a progressive accumulation and diffusion of lactic acid in the media, such as in cheese or meat products.

Then, we explored the consequences of growing populations in a structured media in regards of survival to an exposition to low pH media. Results showed that, regardless of the initial pH, populations incubated in a semi-solid media have a better tolerance to acid stress than those grown in liquid broths, where no surviving cells were detected. This underlines limitations in modeling food-borne pathogens behavior in food from data obtained in liquid conditions, as previously shown in other studies [START_REF] Skandamis | Colonial vs. planktonic type of growth: Mathematical modeling of microbial dynamics on surfaces and in liquid, semi-liquid and solid foods[END_REF][START_REF] Pin | Validating predictive models of food spoilage organisms[END_REF][START_REF] Smith | Evaluation of a Clostridium perfringens predictive model, developed under isothermal conditions in broth, to predict growth in ground beef during cooling[END_REF][START_REF] Ross | Modeling Microbial Growth Within Food Safety Risk Assessments[END_REF] .

It has been suggested from other studies that the components of the matrix could have a buffer effect that protects embedded cells by preventing the drop in pH. Our tests show that planktonic populations dispersed in hydrogel did not present the same survival fitness that those cultivated as microcolonies in the same hydrogel. The hypothesis of a buffer effect due to hydrogel interference was tested for bacteria incubated in hydrogel and it was statistically rejected. This is supported by another study in a gelified dairy matrix, where food related bacteria were dispersed without incubation in the gel before application of the acidic stress. It was reported that no protective effect existed compared to the same conditions in liquid media [START_REF] Hernández-Galán | Effect of dairy matrices on the survival of Streptococcus thermophilus, Brevibacterium aurantiacum and Hafnia alvei during digestion[END_REF] .

A parameter that could explain this difference of survival between the populations incubated or not in the hydrogels would be the spatial organization of cells. The hydrogels showed evidence of deliquescence such as unraveling of filaments and loss of stiffness but maintained enough structural integrity to ensure the microcolonies did not disperse. The ability of spatially organized populations of bacterial cells to better survive acid stress was described for pathogenic bacteria but also for auxiliary microbiota and probiotics, such as Lactobacillus strains [START_REF] Heumann | Intestinal release of biofilm-like microcolonies encased in calciumpectinate beads increases probiotic properties of Lacticaseibacillus paracasei[END_REF][START_REF] Chamignon | Evaluation of the Probiotic Properties and the Capacity to Form Biofilms of Various Lactobacillus Strains[END_REF] . The bacteria could secrete extracellular polymeric substances (EPS) when grown in communities as described in biofilms [START_REF] Lee | Structure and Function of the Escherichia coli Protein YmgB: A Protein Critical for Biofilm Formation and Acid-resistance[END_REF][START_REF] Wood | Insights on Escherichia coli biofilm formation and inhibition from wholetranscriptome profiling[END_REF] . For E. coli O157:H7, tolerance of the bacteria to low pH could further involve the DNA binding protein Dps which is known to enhance survivability when local nutrients are exhausted [START_REF] Jeong | Acid stress damage of DNA is prevented by Dps binding in Escherichia coli O157:H7[END_REF][START_REF] Ho Choi | Contribution of dps to acid stress tolerance and oxidative stress tolerance in Escherichia coli O157:H7[END_REF] .

From this study in a hydrogel matrix, gadB appeared to be more expressed at the periphery of the E. coli O157:H7 microcolonies in acidic conditions. This correlated with an increased tolerance to the type of acid stress that can be encountered by bacterial cells after ingestion of food. These findings are of interest for public health as they underline possible differences between liquid and solid food products on the infectious dose and bacterial virulence. In this case, the tolerance to acidity could mean an increase in the bacterial load that can survive in the digestive system as well as a phenotype more likely to colonize the gut lining. In order to alleviate public health issues, differences in bacterial behavior in planktonic conditions versus microcolonies could be considered when integrating phenotypic heterogeneity in risk assessment. Modeling pathogens growth and survival should take in account the gelled environments where the spatialization of genetic expression and its resulting populational effects could deeply affect pathogens behavior and virulence after ingestion.

Declaration of competitive interest

None drafting and revising critically the manuscript for important intellectual content. All authors 374 have declared no competing interests. The rise in expressed fluorescence is not linear with greater leaps of intensity below pH=6.0.

Points over time show that fluorescence intensity at pH 4.5 can be 3-4 times higher than reported values for the pH=7.0 control. The lag time before the green fluorescence is detected is high at pH 7.0 (15 hours) compared to pH=5.5 where it starts after eight hours. In media pH=5.0 and pH=4.5, the lag time becomes progressively longer (12 then 14 hours).

Figure 1 :

 1 Figure 1: Radius of the microcolonies. Representation of the radius of the microcolonies in µm, the width of each figure represents the concentration of the number of values. For each case, the slashed line is the mean value of radius, and dotted lines delimit the 75 % probability interval. Radius values were calculated from 40 independent microcolonies.

Figure 2 :

 2 Figure 2: Representative images of gadB spatial patterns of expression for E. coli O157:H7 cultivated in neutral (pH=7) or acidic (pH=5) hydrogels. A series of 5µm slices of microcolonies is presented in control LMPA pH=7 (A) and the acid matrix LMPA pH=5 (B). The red fluorescence is constitutive and the green fluorescence is expressed as a function of gadB transcription. Supplementary material Figure S3 presents the same representation for a control constitutive GFP expression in both conditions.

Figure 3 :

 3 Figure 3: Relative expression of gadB in function of the distance from the center of microcolony. In this representation, the relative gadB expression is expressed as the ratio of green fluorescence intensity over red fluorescent intensity (GFP reporter/RFP constitutive) in function of the distance from the center of the microcolony (d CM ) for forty microcolonies grown in neutral (A) or acidic hydrogels (B).

Figure 4 :

 4 Figure 4: Spatial patterns of expression of gadB for E. coli O157:H7 in the presence of Lactococcus lactis ssp. cremoris, cultivated at neutral pH in hydrogels. (A) Visualization at 96h of microcolonies of E. coli O157:H7 co-inoculated from 10 3 CFU/ml to 10 5 CFU/ml, with L. lactis inoculated at 10 3 CFU/ml, in a hydrogel at neutral pH. The red fluorescence is constitutive and the green fluorescence is expressed as a function of gadB transcription. (B) Microcolonies of E. coli O157:H7 close or in contact with L. lactis microcolonies. The two rightmost pictures were taken at 96h and the one on the left at 72h. L. lactis microcolonies are visualized in the bottom images thanks to the transmission detection (indicated by white arrows).

Figure 5 :

 5 Figure 5: Population log-reduction of planktonic cultures and hydrogel microcolonies of E. coli O157:H7 upon acidic exposure. Bacterial cells were exposed for 4 hours at a pH of 2 (HCl). Representation of the mean reduction of population log between the control and survival groups. Bacteria incubated and tested in planktonic are on the top (TSB), those incubated in planktonic but encased in hydrogels before the test are on the middle (TSB-LMPA), and the results for populations incubated and tested in hydrogels are on the bottom (LMPA). A star indicates a significant difference between values (P<0.05). Data resulted from at least six biological replicates.

Figure S2 :

 S2 Figure S2: Relative expression of gadB in a population in function of time and under different acidity levels. The fluorescence of planktonic populations of E. coli O157:H7 gadB::GFP are represented in function of the OD 600 . For each curve representing the mean signal over time, the standard deviation of values is shown as an area of lighter color. These curves show that detected fluorescence becomes incrementally brighter with decreasing pHs.

Figure S3 :

 S3 Figure S3: Qualitative presentation of the constitutive GFP spatial expression in microcolonies at pH=7 or pH=5. A control group with a constitutive GFP to verify that at pH=7 (up) and/or pH=5 (down) the fluorescence of the green fluorescence is not already spatialized. Each image is a 5µm slice of a stack.

Figure S4 :

 S4 Figure S4: Qualitative presentation of gadB spatial expression in microcolonies at pH=7 or pH=5. Microscopic observations of the expression of gadB in the control LMPA pH=7 (top) and in the acid matrix LMPA pH=5 (bottom). For both groups, the 2 successive rows use a 40X then a 63X objective to present a collection of microcolonies and a close observation of a single example. Each image is shown as a 3-dimensional representation (leftmost column) and in each case a series of 5 µm slices show both fluorescent channels (middles columns) and the overlay (Rightmost column). The first row of each condition was

Figure S5 :

 S5 Figure S5: The case of joint microcolonies. Examples where two microcolonies of E. coli O157:H7 are touching or merging in LMPA pH=5. White arrows indicate the separation between each microcolonies.

Figure S6 :

 S6 Figure S6: Live/Dead staining in the gel microcolonies. Bacterial cells in microcolonies grown in neutral (left side) or acidic (right side) were labeled with the cell impermeant propidium iodine (red, dead cells) and the cell permeant SYTO 9 (Green, all cells).

  [START_REF] Jackson | Heat resistance of Escherichia coli O157:H7 in a nutrient medium and in ground beef patties as influenced by storage and holding temperatures[END_REF] CFU/ml. When necessary, the medium was adjusted to acidic pH= 5 with HCl. After homogenizing and gentle stirring to avoid bubble formation, the inoculated gel matrix was immediately distributed in each well of a 96-well

	microscope	(CLSM)	at	the	INRAE	MIMA2	imaging	platform

microtiter plate of microscopic grade (µClear, Greiner Bio-One, France). The microtiter plates were then incubated at 20°C and observed under CLSM after 96 hours of incubation.

All microscopic observations were performed with a Leica HCS-SP8 confocal laser scanning (https://doi.org/10.15454/1.5572348210007727E12). The GFP (GFPmut3; λ ex 500; λ em 513) and RFP (mCherry2; λ ex 589; λ em 610) were excited respectively with laser bands 488 nm and 561 nm. For Live/dead exploration, SYTO9 (λ ex 485; λ em 501) and IP (λ ex 535; λ em 617) were excited respectively with laser bands 488 nm and 561 nm. Observations were carried out with a water immersion 63x objective lens (numerical aperture of 1.20) for 184µm x 184µm fields.

Bidirectional acquisition speed of 600 Hz allows a frame rate of 2.3 images per second. For 3D stack analysis, a 1 µm step between z levels was used. For each condition, a minimum of 60 stacks were acquired in over a dozen independent wells. Microscopic images were treated on IMARIS v9.64 (Bitplane, Switzerland) to generate sections and projections. Kymograms reporting the spatial analysis of gadB expression in microcolonies were performed using BiofilmQ v0.2.2

[START_REF] Hartmann | Quantitative image analysis of microbial communities with BiofilmQ[END_REF]

. BiofilmQ image segmentation was performed with a threshold value set at 0.1 with cubes of 1.8 µm (vox of 10). The absence of radial fluorescence gradients in microcolonies of E. coli O157:H7 constitutively expressing GFP was verified prior experiments with gadB expression (supplementary material Figure

Acknowledgments

This work was supported in part by INRAE and ANR (Agence National de la Recherche) PathoFood project (n°ANR-17-CE21-0002). The partners of the ANR PathoFood are acknowledged for fruitful discussions about L. monocytogenes and E. coli O157:H7 behavior in food matrices. Cédric Saint Martin was a PhD Research Fellow granted by the ANR PathoFood. Julien Deschamps (INRAE) is warmly acknowledged for assistance with Confocal Laser Scanning Microscopy at the Mima2 imaging platform (https://doi.org/10.15454/1.5572348210007727E12).

elongated by PCR with two primers (gadBt7_FW and gadBt7_RV) so that a homology sequence exists with insertion site. This site is located between the gene interest gadB (in blue) and gadC (in yellow). On the right the low copy plasmid pHL60 bearing the fluorophore encoding genes is represented. It contains the constitutively expressed mCherry2 (in red) sequence and gfpmut3 (in green) under the control of the T7 pol promoter (in purple), as well as a gentamicin resistance gene gm r (in pink).


Elodie Mezzatesta

Soufiane El Kamel

Annie Perraud

Cathy Vieillescazes

Carole Mathe
email: carole.mathe@univ-avignon.fr.

Anthropological and analytical studies of two Egyptian human mummies' heads from Deir-el-Medineh

Keywords: Ancient Egypt, mummification practices, GC-MS, FTIR

This paper focused on a multidisciplinary study of mummification balms' constituents from two Egyptian mummies' heads belonging to the Osteology collection of the Confluences museum in Lyon (France). These individuals come from the same necropolis, Deir el-Medineh in Upper Egypt. They were coated with particular substances not often encountered in studies of mummification balms. The objective was to identify the composition of the two types of samples found on each individual: an amorphous material resembling mummy balm and a sandy substance. The knowledge of the anthropology and the mummification practices associated to analytical chemistry study of the balms permitted to obtain a global characterization of these persons. The FTIR and GC-MS results notably permitted to observe (i) the presence of fat and beeswax within the amorphous black samples and (ii) the presence of natron, fatty matter and mastic resin within the sandy samples; this types of samplings are uncommon in ancient Egypt.

INTRODUCTION

Mummification was a fundamental part of funerary practice in ancient Egypt. The Egyptians believed rebirth in the afterlife and, in order to be able to access this afterlife, it was necessary to preserve the body [START_REF] Buckley | Chemical investigations of the organic embalming agents employed in ancient egyptian mummification[END_REF]. The application of balms was a key part of the mummification process in ensuring successful and lasting preservation of the body. A wide variety of natural substances can be used in the formulation of balms, including plant oils or animal fats, di-or triterpenic resins, bitumen or even beeswax [START_REF] Buckley | Complex organic chemical balms of Pharaonic animal mummies[END_REF][START_REF] Nicholson | Ancient Egyptian Materials and Technology[END_REF]. Given the molecular richness of these materials, their identification within an archaeological sample represents a real challenge. Indeed, these materials can undergo oxidation, degradation and alteration processes, naturally with time (aging) or due to anthropic factors, such as heating temperature. Degraded molecules can play an important role in species identification. To carry out this work, it was necessary to use different analytical techniques, each providing complementary information, such as Fourier transform infrared spectroscopy (FTIR) and gas chromatography coupled to a mass spectrometer (GC-MS) [START_REF] Charrié-Duhaut | Molecular and isotopic archaeology: Top grade tools to investigate organic archaeological materials[END_REF]. The aim of this study was to provide a better knowledge of the mummification process for these two individuals by analyzing the chemical composition of their mummification balms. Two individuals were chosen because of the unusual but identical appearance of their balm.

MATERIALS AND METHODS

Archaeological samples

The Osteology collection of the Confluences museum in Lyon (France) contains about 250 Egyptian mummies' heads and skulls, which were collected at the end of the 19th century. Louis Lortet and Ernest Chantre brought back from their excavations in Egypt mummies' skulls and heads. All the mummified heads constitute a important collection for the anthropologic study of ancient Egypt. The choice to take only the heads of the mummies to come back in France corresponded to the anthropologists' practices at the end of the 19th century and much knowledge about individuals has unfortunately been lost forever. Two individuals were selected for this study: Nos. 30000150 and 30000306.

Infrared spectroscopy

A Thermo Scientific™ Nicolet™ iN10 and iZ10 Fourier transform infrared spectrometer in transmission mode and a DTGS (Deuterated Triglycine Sulfate) detector were used. The main iN10 module is an integrated microscope for imaging and the iZ10 add-on module that allows analysis of KBr pellets without imaging. For a transmission analysis, the sample is placed in the infrared beam, the energy generated is measured to give a spectrum. The DTGS detector is a pyroelectric thermodetector, which means that it reacts to a change in temperature due to a variation in electrical polarization. It is sensitive from 4000 to 400 cm -1 and operates at room temperature. All the resulting spectra were interpreted from the bands obtained and their respective wave numbers, but also with the help of a database containing spectra of reference materials and according to scientific literature.

Solvents and reagents

All solvents and reagents were of analytical grade. Hexane and N,Obis(trimethylsilyl)trifluoroacetamide/Trimethylchlorosilane (BSTFA/TMCS) were supplied by Sigma-Aldrich.

Dichloromethane was supplied by Merck.

2.4. Gas Chromatography -Mass Spectrometry (GC-MS) 2.4.1. Apparatus GC-MS analyzes were performed with a Thermo Scientific Focus gas chromatographic system composed by a Thermo Scientific Al 3000 auto-sampler coupled with an ITQ 700 ion trap mass spectrometer (Thermo Fisher Scientific). A GC fused silica capillary column Thermo trace GOLD TG-5MS (5% diphenyl / 95% dimethylpolysiloxane, 30 m length × 0.25 mm i.d. × 0.25 μm film thickness) was used. The carrier gas was helium with a constant flow of 1 mL.min -1 . 1μL of sample was injected in splitless mode. Mass spectra were recorded in electron impact mode with an electron ionization voltage of 70 eV, an ionization time of 25,000 μs and a mass range of 40-650 m/z. The injector temperature was set at 250 °C. Transfer line, ion trap and manifold temperatures were respectively set at 300 °C, 200 °C and 50 °C The separation was achieved with the following temperature programme: 50 °C with a 2 min hold, increased at 10°C.min -1 to 200 °C, then at 2.5 °C.min -1 to 310 °C, finally increased at 8°C.min-1 to 330 °C and held isothermally for 3 min.

Preparation of samples

10 mg of material was extracted with 1 mL of dichloromethane (DCM) and ultrasonic was delivered for 10 minutes. The solution was then centrifuged for 10 minutes at 6000 rpm. The supernatant was left aside and the solid pellet could be extracted once again. This phase was carried out twice more. Under a stream of nitrogen, the three portions were collected, mixed, and evaporated to dryness. The extract was trimethylsilylated in 200 µL of BSTFA/TMCS (99/1 v/v) and heated at 70°C for 30 minutes. The mixture was then evaporated to dryness and dissolved in 0.2 to 1 mL of a hexane/DCM mixture (1/1, v/v). 1µL of the solution was injected in the GC-MS apparatus. The analyzes by gas chromatography of balms' samples Nos. 3000150a and 30000306a provided a very high proportion of fatty matter. It has been possible to identify lauric, myristic, palmitic, stearic, palmitoleic and oleic acids, and also beeswax and traces of diterpenic resin. This mixture of substances is very common in the formulation of balms [START_REF] Abdel-Maksoud | A review on the materials used during the mummification processes in ancient Egypt[END_REF][START_REF] Brettell | Organic residue analysis of Egyptian votive mummies and their research potential[END_REF]. It is however possible to note that the chromatograms of these two samples coming from two different individuals are perfectly similar.

RESULTS AND DISCUSSION

For the two other samples Nos. 30000150b and 30000306b, a first approach was realized by infrared spectroscopy given the heterogeneity of the matters and their sandy aspect. The figure 3 H bonds, at 1705 cm -1 for the C=O bond, and the deformation bands at 1460, 1380 and 1235 cm -1 of these bonds [START_REF] Bruni | Identification of archaeological triterpenic resins by the non-separative techniques FTIR and 13C NMR: The case of Pistacia resin (mastic) in comparison with frankincense[END_REF]. The comparison of this spectrum with the data bank of the apparatus shows a correlation with more than 80% with mastic resin. These results are identical for the sample 30000150b. Thus, it was possible to conclude that these sand grains were composed of two types of substances: an inorganic matter attributed to natron and an organic one. The organic part was analyzed by gas chromatography. In samples Nos. 30000150b and 30000306b (Fig 4), numerous fatty acids, monocarboxylic fatty acid (MC), were detected indicating the presence of fatty substances. This type of fatty acids indicates an unaltered fatty matter. In addition, triterpenic compounds, such as moronic and oleanonic acids were identified. All these molecules allow to define the formulation of these samples: fatty substance probably a plant oil or an animal fat in mixture with the resin of Pistacia lentiscus also called mastic resin.

Conclusion

The two individuals Nos. 30000150 and 30000306 have embalming substances with identical composition. This chemical balm composition was already described in the literature [START_REF] Łucejko | An analytical approach based on X-ray diffraction, Fourier transform infrared spectroscopy and gas chromatography/mass spectrometry to characterize Egyptian embalming materials[END_REF]. However, balm matter can be distinguish from sandy matter. The "balm" part is composed mainly of fat and beeswax, while the "sand" part contains natron, fatty substance and mastic resin. According to the authors' knowledge is the first time that balm matter associated to sandy matter were studied. It is possible to hypothesize that the embalming of these individuals was carried out in the same embalming atelier in Deir-el-Medineh with a particular know-how.

  The mummy's head No. 300000150 (Fig 1A) is a mature adult man from Deir-el-Medineh. Concerning the mummification practices, there were a brain removal by trans-ethmoidal way with nasal and endocranial stuffing by a heterogeneous mixture. The mummy's head No 30000306 (Fig 2A) is a young adult woman from Deir-el-Medineh. The skull is characterized by a post-mortem bilateral temporoparietal and left occipital fracture line. Concerning the mummification practices, there were a brain removal by ethmoidal way. For both of the individuals, two samplings were realized; the first one were balm matter, a black, shiny amorphous substance commonly observed on mummies and the second one were colored sand grains not often encountered. For the balm matter, the sample Nos. 30000150a (Fig 1B) comes from left ear and the sample No. 30000306a (Fig 2B), right temple. For the sandy matter, the samples Nos. 30000150b (Fig 1C) and 30000306b (Fig 2C) are respectively present inside the surface of the skulls. Radiocarbon dating was not made because of the degradation state of the tissues.

  presents the FT-IR analyzes of the material grains of the sample 3000306b. Two different spectra were obtained by analyzing the material grains of the archaeological sample. The infrared spectrum (Fig 3A) is characteristic of an inorganic compound because it has several bands between 1200 and 600 cm -1 and does not absorb between 4000 and 1200 cm -1 . Two bands at 1150 and 1110 cm -1 and two others at 640 and 614 cm -1 correspond to the elongation vibrations of the S-O bond of sodium sulfate. It is one of the main constituents of natron. Many bands are visible on the spectrum (Fig 3B), including bands characteristic of organic matter: the elongation bands at 3420 cm -1 , specific of O-H bonds, around 2960 cm -1 characteristic of C-

Figure 1 :

 1 Figure 1: Mummy No. 30000150 (A), balm sampling (B), sandy matter (C).

Figure 2 :

 2 Figure 2: Mummy No. 30000306 (A), balm sampling (B), sandy matter (C).

Figure 3 :

 3 Figure 3: Infrared spectrum from mummy No. 3000306a.

Figure 4 :

 4 Figure 4: TIC chromatograms from mummy Nos. 30000150b and 30000306b.

Acknowledgments:

The authors wish to thank the Museum of Confluences in Lyon (notably Dr Didier Berthet, conservator). This work was supported by the LabEx ARCHIMEDE under the program "Investissement d'Avenir" ANR-11-LABX-0032-01. The research has been funded by a PhD grant given by The French Ministry of Higher Education and Research.