Guyslain Naves

The hardness of routing two pairs on one face

, about the complexity of the edge-disjoint paths problem with terminals on the outer boundary of a planar graph. We also give a directed acyclic reduction. This proves that the arc-disjoint paths problem is NP-complete in directed acyclic graphs, even with only two demand arcs.

Introduction

The multiflow problem has been studied in combinatorial optimization for many years, both because of its theoretical interests and applications. Basically, we want to find integer flows between pairs of terminals, respecting capacity constraints. The general problem is NP-complete, with different types of constraints, see e.g. the survey of Frank [START_REF] Frank | Packing paths, circuits and cuts -a survey[END_REF]. The most general way to define constraints is to put capacities on the edges of the graph, in the same way as for the classical flow problem. When these capacities are 1 everywhere, this defines the edge-disjoint (or arc-disjoint) paths problem. Robertson and Seymour [START_REF] Robertson | Graph Minors XIII. The Disjoint Paths Problem[END_REF] proved that the multiflow problem is polynomial for undirected graphs, assuming that the total demand is fixed. Special interest has been shown for solving the problem in planar graphs (directed or not). Kramer and Van Leeuwen [START_REF] Kramer | The Complexity of Wire-Routing and Finding the Minimum Area Layouts for Arbitrary VLSI Circuits[END_REF] have shown that the undirected planar multiflow problem is NP-complete in the general case. Nevertheless, a good characterization theorem has been proved by Okamura and Seymour [START_REF] Okamura | Multicommodity flows in planar graphs[END_REF] for the edge-disjoint paths problem in planar Eulerian graphs, under the assumption that all terminals are on the boundary of a unique face of the graph. Despite sharpenings (see [START_REF] Frank | Edge-disjoint paths in planar graphs[END_REF], [START_REF] Okamura | Multicommodity flows in graphs[END_REF]), the non-Eulerian case remained open until 2007, when Schwärzler [START_REF] Schwärzler | On the complexity of the planar edge-disjoint paths problem with terminals on the outer boundary[END_REF] proved the NP-completeness of the edge-disjoint paths problem in planar graphs with all terminals on the boundary of the same face of the graph. Between Robertson and Seymour's result, and Schwärzler's result, one could ask if there is a polynomialtime algorithm for the edge-disjoint paths problem in planar graphs, when the number of different pairs of terminals is fixed, but each may be repeated many times. Especially when there are only two parallel classes of demands, with terminals lying on a single face of the graph. Actually, Schwärzler's proof can easily be modified to prove that the problem is still NP-complete with three pairs of terminals. In this paper we give a new reduction, proving that the problem is NP-complete with only two pairs of terminals. This solves a question of Müller [START_REF] Müller | On the complexity of the planar directed edge-disjoint paths problem[END_REF]. We will also give a directed version of our proof, showing that the arc-disjoint paths problem is NPcomplete, even if G is planar with two opposite parallel classes of demand edges st and ts where vertices s and t belong to the boundary of the same face of G. Both results strengthen [START_REF] Müller | On the complexity of the planar directed edge-disjoint paths problem[END_REF]. Finally, we prove the NP-completeness when G is a planar acyclic digraph and H consists of two pairs of terminals lying on the outer face of G.

Definitions

Let G = (V, E) be an undirected graph, and let c : E → N be a capacity function on the edges of G. Let H = (T, D) be an undirected graph with T ⊆ V , and r : D → N a demand function (or request). The multiflow problem is to find a multiset C of cycles of G + H satisfying the following conditions : (i) Each cycle of C contains exactly one edge of H.

(ii) For each edge of G, the number of cycles in C using it is less than its capacity.

(iii) For each edge of H, the number of cycles in C using it is exactly its request.

H is usually called the demand graph, T is the set of terminals. By cycle, we mean a closed sequence of distinct edges that are consecutive in the graph, or equivalently a connected Eulerian subgraph. The problem can easily be defined in digraphs, by replacing every occurrence of "cycle" by "directed cycle". Thus, an instance of the multiflow problem consists of a quadruple (G, H, r, c). In the following, c will always be supposed to be equal to 1. We will note P the set of paths obtained from C by ignoring the demand edges, and we will mainly speak about these paths instead of the cycles. A path is formally a sequence of distinct edges that are consecutive. Thus, cycles are closed paths. Two paths are edge-disjoint if their edge-sets are disjoint. We define directed paths and arc-disjoint paths analogously. When c is constantly equal to 1, the multiflow problem is known as the edge-disjoint paths problem (respectively the arc-disjoint paths problem). The graphs considered in this paper are always without loops, but parallel edges are allowed. Actually, whenever an edge e ∈ E(G) has a capacity greater than 1, we replace it by c(e) parallel edges. Let U ∈ V be a subset of a vertex set of the graph. We note δ (U) the set of edges having exactly one extremity in U. Every set of edges that can be written as δ (U) for some U is called a cut of the graph. In directed graphs, δ -(U) is the set of arcs entering U, δ + (U) is the set of arcs leaving U. When δ (U) = δ + (U), we say that

U is a directed cut. We define d(U) := |δ (U)| and similarly d + (U) and d -(U). Let C be a cut of G + H. C is a tight cut if c(C ∩ E) -r(C ∩ D) = 0.
If this difference is negative, the multiflow problem is not feasible. When H is reduced to a single edge, the famous max-flow-min-cut result states that a multiflow exists if and only if this difference is never negative (see Menger's theorem [START_REF] Menger | Zur allgemeinen Kurventheorie[END_REF]). When C is a tight cut, each edge of C is entirely used in any solution of the multiflow problem : there are as many paths through each edge as its capacity. In directed graphs, tight cuts are the cuts δ

(U) of G + H with c(δ + G (U)) -r(δ - H (U)) = 0.
A planar graph is a graph that has an embedding in the plane without intersection of the edges (or arcs). Let P 1 and P 2 be two edge-disjoint paths in G. P 1 and P 2 cross at vertex v ∈ V (G) if there are four edges e 1 , . . . , e 4 incident to v, appearing in this order around v, such that e 1 and e 3 are consecutive in P 1 and e 2 , e 4 are consecutive in P 2 . However, two paths may have a common vertex without crossing, see Figure 1. A crossing is a triple (P, Q, u) such that P and Q crosses at vertex u.

Outline of the proof

We will prove the NP-completeness of the edge-disjoint paths problem with only two pairs of terminals, by reduction from 3-SAT. Before giving the full proof, which is quite technical, we explain the main ideas of the reduction. Consider an instance of 3-SAT, consisting of clauses over a set of variables. We build a graph in the form of a grid, with as many columns as there are clauses, and as many rows as twice the number of variables. In this grid, the intersection of each row with each column is one of two basic graphs. These two graphs, called XCH and LIC should have the following properties. They have two vertices of degree one in their left and right sides, and four -actually two pairs -at their top and their bottom. We suppose that there will always be two paths either from the two left top vertices or from the two right ones, going through them from top to bottom (vertical paths). We will also always route one or two paths from left to right (horizontal paths).

If there are two horizontal paths, then the two vertical paths can only be routed diagonally. The behaviours of XCH and LIC are different if there is only one horizontal paths. In that case, in XCH, the vertical paths are still forced to go diagonally through the graph, but in LIC, they can be routed vertically. Figures 2 and3 illustrate the possible routing through the two graphs (and what we mean by diagonally and vertically). The typical behaviour for these gadgets is to change the vertical paths from one side to the other (Lemmas 4 and 6). We say that they shift the paths. The only special case when the two vertical paths can stay on the same side is the following : there is a LIC and a single horizontal path. In that special case, the gadget keeps the paths (Lemma 7). The reduction is basically the following : there are two consecutive rows for each variable, and we route three paths along these two rows. Thus, one path will follow one row, and the two other paths will follow the other row, deciding a variable assignment. We also route two paths in each column, and we ask that these two paths are kept an odd number of times. Because of the properties of LIC and XCH, the two vertical paths can be kept in a particular gadget if and only if this gadget is a LIC and there is only one horizontal path in the corresponding row. We place LIC on those particular intersections for which the literal associated with the row appears in the clause encoded by the column. Thus, we ensure that whenever vertical paths are kept, the corresponding clause is made valid by the chosen assignment. Then we must guarantee that the two paths associated with each column are kept at least once (actually an odd number of times). This is done by asking these two paths to be routed from the two left pair of uppermost vertices of the column, to the two rightmost lower vertices. Because the number of rows is even (twice the number of variables), paths must indeed be kept an odd number of times. Finally, we can add two common terminals for the vertical paths, and two others for the horizontal paths, achieving the desired restriction to two edges of demand. Unfortunately, there are several difficulties in implementing this reduction. Mainly, XCH and LIC does not exist, with the prescribed properties. Actually, the main difficulty is to enforce that the horizontal paths stay on their respective rows. We will prove that with our gadgets, the horizontal paths cannot go through more than three rows in each column (Lemma 8). Our solution is then to create a buffer consisting of a large number of rows, between the rows encoding the variables. Similarly, we must prove that the vertical paths stay in their columns (Lemmas 10 and 12). This will be done, by using the property that our graph is nearly Eulerian (almost each vertex has even degree). This fact will help us to prove that the edges not in a solution induce cycles and a small set of paths, called no-paths. One of the main lemmas states that the extremities of each no-path are determined (Lemma 11). More exactly, there will be exactly one no-path per variable. Considering horizontal paths and no-paths together, many cuts are tight for them. Consequently, vertical paths cannot use the edges contained in these cuts : each vertical path intersects only one column. Then, local properties of XCH and LIC allow us to conclude the proof.

Preliminaries

Uncrossing the paths

We can suppose without loss of generality that each pair of paths induces at most one crossing :

Lemma 1. Let (G, H) be an instance of the edge-disjoint paths problem with G planar. There is a solution for (G, H) if and only if there is a solution such that each pair of paths crosses at most once, and two paths with the same extremities do not cross.

Proof. Let P be a solution minimizing the number of crossings. We can assume that every path is simple. Suppose that two paths P 1 and P 2 induce more than one crossing. Let u and v be the first and second crossings between P 1 and P 2 , starting from one extremity of P 1 . We decompose P i in three paths Q i ∪ R i ∪ S i where R i has extremities u and v. Then replacing P 1 and P 2 by

P ′ 1 = Q 1 ∪ R 2 ∪ S 1 and P ′ 2 = Q 2 ∪ R 1 ∪ S 2 ,
we show that the number of crossings is reduced, contradicting the minimality of P. In every vertex except u and v, the paths are not locally modified, thus the number of crossings is not changed. The number of crossings between P ′ 1 and P ′ 2 is reduced by at least 2. Then, the neighbourhood of vertex u (and symmetrically v) is divided into four parts. A path going through two consecutive parts crosses one of P 1 and P 2 , and one of P ′ 1 and P ′ 2 . A path going through two opposite parts crosses both P 1 and P 2 . This proves the number of crossing is decreased. Finally, if P 1 and P 2 have a common extremity u, and crosses at v, the same transformation applies again, decreasing the number of crossing by at least one.

Solutions will always be supposed uncrossed (each pair of paths with different extremities induces at most one crossing) and simple. The following is an easy consequence of uncrossing : Lemma 2. Let G be a planar graph, a, b, c and d four vertices on the boundary of the infinite face of G, occuring in this order. Let P be an uncrossed set of (a, c)-paths and (b, d)-paths mutually edge-disjoint. Then, all (a, c)-paths cross the (b, d)-paths in the same order.

Proof. There is a crossing neither between the (b, d)-paths, nor between the (a, c)-paths, so we can choose P among the (b, d)-paths such that all the other (b, d)-paths are on the same side. We prove the lemma by induction on the number of (b, d)-paths. P can be closed to a cycle by adding a curve on the infinite face of G. Then by Jordan's theorem, P separates the (b, d)-paths from a (say). All (a, c)-paths, starting from a must cross P before the other (b, d)-paths. Using induction on the (b, d)-paths minus P concludes the proof.

Forbidding crossing

It happens to be useful to have in the proof an Eulerian graph. This is not possible since the edge-disjoint paths problem with terminals on the boundary of the infinite face is polynomially solvable as soon as all the inner vertices have even degrees [START_REF] Okamura | Multicommodity flows in planar graphs[END_REF], [START_REF] Frank | Edge-disjoint paths in planar graphs[END_REF]. We introduce the following restriction : every vertex will be of degree four, but in some of them, paths will not be allowed to cross each other. This effect can easily be achieved by replacing those special vertices by a cycle of length 4, as described in Figure 4 Formally, we define the following problem, and show that it is equivalent to the original one :

Problem 1 (Extended Planar Edge-Disjoint Paths).

INPUT : a planar graph G, a demand graph H with V (H) ⊆ V (G), and U ⊆ V (G).

OUTPUT : Is there a solution to the edge-disjoint paths problem (G, H) such that for every u ∈ U, there is no crossing at u ? Let G v be the graph obtained from G by replacing a vertex v of degree 4 by a cycle of length 4, according to Figure 4. The equivalence with the planar edge-disjoint paths problem is a consequence of the following obvious lemma : Lemma 3. Let (G, H,U) be an instance of the extended planar edge-disjoint path problem. Let v be a vertex of G of degree 4. Then there is a solution to (G v , H,U) if and only if there is a solution to (G, H,U ∪ {v}).

G v G v =⇒
In the following, we will always study instances of the extended problem. Vertices of U are called non-crossing vertices. In the figures, we will represent vertices not in U (crossing vertices) by bold points. Note that there is no restriction over no-paths, they can cross other no-paths or paths at every vertex.

Implementing XCH and LIC

Basic graphs

We give the graphs encoding the gadgets XCH and LIC, and detail their respective properties. Let XCH be the graph depicted in Figure 5. The crossing vertices are a, b, c and d. We note Then S 1 and S 2 are either an (s 1 , s ′ 3 )-path and an (s 2 , s ′ 4 )-path, or an (s 3 , s ′ 1 )-path and an (s 4 , s ′ 2 )-path. Proof. Let P be as described in the lemma. As the (S, S ′ )-paths must cross the (T, T ′ )-paths, there are at least 4 crossings in P. We know that these crossings occur in vertices a, b, c and d, and the (T, T ′ )-paths (resp. the (S, S ′ )-path) do not cross each other. Suppose ab is in an (S, S ′ )-path, then ac and bd must belong to distinct (T, T ′ )-paths, and cd is in the second (S, S ′ )-path. Then au 2 , bu 5 , cu 8 , du 11 are in (T, T ′ ) paths, and au 3 , bu 7 , cu 6 and du 10 are in (S, S ′ )-paths. As there is no other crossing except in the four central vertices, the (S, S ′ )-paths are connected to s ′ 1 , s ′ 2 , s 3 and s 4 . The case when ab belongs to a (T, T ′ )-path is similar and gives the other solution.

S = {s 1 , s 2 , s 3 , s 4 }, S ′ = {s ′ 1 , s ′ 2 , s ′ 3 , s ′ 4 }, T = {t 1 ,t 2 } and T ′ = {t ′ 1 ,t ′ 2 }. d c b a u 12 u 11 u 10 u 9 u 8 u 7 u 6 u 5 u 4 u 3 u 2 u 1 t ′ 2 t ′ 1 t 2 t 1 s ′ 4 s ′ 3 s ′ 2 s ′ 1 s 4 s 3 s 2 s 1
These paths exist, as shown by Figure 6. Lemma 5. Let P be a set of three edge-disjoint paths in XCH that satisfies :

(i) P contains exactly two ({s 1 , s 2 }, S ′′ )-paths, and S ′′ is either {s ′ 1 , s ′ 2 } or {s ′ 3 , s ′ 4 }, (ii) P contains exactly one (T, T ′ )-path.

Then, S ′′ = {s ′ 3 , s ′ 4 }. Here we find the first differences between the graph XCH and its ideal model given in Section 3. We need to suppose that the two vertical paths come from the same side (through s 1 and s 2 or s 3 and s 4 ), and leave also at the same side . We need to prove that this is actually the case, but we can already remark that it is true in the particular case when the gadgets above and below are XCH with two horizontal paths, by Lemma 4.

Proof. If not, then there is a set P of three edge-disjoint paths, a (t,t ′ )-path Q, an (s 1 , s ′ 1 )-path P 1 and an (s 2 , s ′

2 )-path P 2 . As Q must cross the two other paths, all paths contain at least one of a, b, c and d. Then, Q uses one edge of u 2 a, u 5 b, u 7 b, u 10 d, and both P 1 and P 2 use two of these edges, contradicting the edge-disjointness of the paths.

Let LIC be the graph depicted in Figure 7. We note again

S = {s 1 , s 2 , s 3 , s 4 }, S ′ = {s ′ 1 , s ′ 2 , s ′ 3 , s ′ 4 }, T = {t 1 ,t 2 } and T ′ = {t ′ 1 ,t ′ 2
}. Lemma 6. Let P be a set of edge-disjoint paths in LIC that satisfy :

(i) P contains exactly 2 ({s 1 , s 2 }, S ′′ )-paths, where S ′′ is either {s ′ 1 , s ′ 2 } or {s ′ 3 , s ′ 4 }, (ii) P contains exactly 2 (T, T ′ )-paths.
Then, S ′′ = {s ′ 3 , s ′ 4 }. Moreover, there cannot be another (S ∪ T, S ′ ∪ T ′ )-path. Proof. Suppose S ′′ = {s ′ 1 , s ′ 2 }. Let C be the cut {u 7 , u 9 , u 10 }. Let Q be the (t 2 , T ′ )-path, P 1 the (s 1 , s ′ 1 )-path and P 2 the (s 2 , s ′

2 )-path. All three different paths meet C, and d(C) = 6. Moreover, there is no crossing in C, thus considering δ (C), u 5 u 7 is used by Q and bu 7 , du 10 by P 1 and P 2 . Now, there are four distinct paths entering

C ′ = {u 1 , u 2 , u 5 }, but d(C ′ ) = 6, contradiction.
As the edges of δ ({a, b, c, d}) are all used by P, there is no other (S ∪ T, S ′ ∪ T ′ )-path. Lemma 7. There exist a (T, T ′ )-path P, an (s 1 , s ′ 1 )-path P 1 and an (s 2 , s ′ 2 )-path P 2 , pairwise edge-disjoint, in LIC. There exist a (T, T ′ )-path P, an (s 3 , s ′

d c b a u 12 u 11 u 10 u 9 u 8 u 7 u 6 u 5 u 4 u 3 u 2 u 1 t ′ 2 t ′ 1 t 2 t 1 s ′ 4 s ′ 3 s ′ 2 s ′ 1 s 4 s 3 s 2 s 1
3 )-path P 1 and an (s 4 , s ′ 4 )-path P 2 , pairwise edge-disjoint, in LIC.

Proof. See Figure 8.

With these four lemmas, the ideal behaviour of XCH and LIC is not reached by the two gadgets: paths can still go from S ∪ S ′ to T ∪ T ′ , and we did not prove that the vertical paths must use either the two rightmost edges or the two leftmost edges between two consecutives gadgets.

Aggregating gadgets

In order to build the graph for the reduction, we need to aggregate gadgets in the form of a grid, using XCH and LIC in the crossing of rows and columns. This is done by linking the edges incident to corresponding vertices of degree 1. Figure 9 shows how we build the grid, and gives the notation that we will use. Moreover, we define X := {x i : i ∈ 1, 4n } and X ′ := {x ′ i : i ∈ 1, 4n } where n is the number of columns, and similarly Y := {y i : i ∈ 1, 2p } and Y ′ := {y ′ i : i ∈ 1, 2p } where p is the number of rows. We call i th vertical cut the set of edges V i := { f i, j k : j ∈ 1, p , k ∈ 1, 2 }, and j th horizontal cut the set of edges

H j := {e i, j k : i ∈ 1, n , k ∈ 1, 4 }. Vertex v in M(i, j) will be denoted v i, j . f 2,3 2 f 2,3 1 f 2,2 2 f 2,2 1 f 2,1 2 f 2,1 1 f 0,3 2 f 0,3 1 f 0,2 2 f 0,2 1 f 0,1 e 1,0 3 e 1,0 2 e 1,0 1 f 1,3 2 f 1,3 1 f 1,2 2 f 1,2 1 f 1,1 2 f 1,1 1 M(2, 3) M(1, 3) M(2, 2) M(1, 2) M(2, 1) M(1, 1) x ′ 8 x ′ 7 x ′ 6 x ′ 5 x ′ 4 x ′ 3 x ′ 2 x ′ 1 y ′ 6 y ′ 5 y ′ 4 y ′ 3 y ′ 2 y ′ 1 y 6 y 5 y 4 y 3 y 2 y 1 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 Figure 9: A grid of dimension 2 × 3.
The following lemma will help us to explain why the horizontal paths cannot go through more than two different gadgets in each column, justifying the buffers. More exactly, the no-paths can be vertically moved by at most 2 rows in each column, so the buffers must contain at least 4 times the number of columns plus 2.

Lemma 8. Let G be a grid of dimension 1 × 3, built exclusively with LIC. Let P be a set of edge-disjoint paths, consisting of two (X, X ′ )-paths A and B, a ({y 1 , y 2 }, y ′ 1 )-path C, a (y 3 , y ′ 2 )-path D, a (y 4 , y ′ 3 )-path E, a (y 5 , y ′ 4 )-path F, a (y 6 , y ′ 5 )-path H and an (X ′ , y ′ 6 )-path I. Then y 1 and y 2 are disconnected from X ′ in G \ E(P) (or equivalently, there is no no-path from {y 1 , y 2 } to X ′ ).

Note that this lemma is still true if some of the LIC graphs are replaced by XCH. Figure 10 shows the extremities of each path. Proof. Suppose that there is a ({y 1 , y 2 }, X ′ )-no-path Q. Note that Q can cross other paths at non-crossing vertices. We can take P uncrossed (uncrossing the paths does not change the set of edges used by the solution), and without loss of generality, A is routed on the left of B.

A, B, I, Q H F E D C, Q I H F E D C A, B

R L s

′ s x ′ 2 x ′ 1 x 2 x 1
Figure 11: There is no solution to this edge-disjoint paths problem, with 5 paths between s and s ′ , see Lemma 9. We need a last "local" lemma, proving that without the presence of a LIC, the vertical paths of a column are shifted. This fills the holes of Lemma 5. As the no-paths only use three rows of each column (this is not fully proved yet), we will only need to study the case with a grid of 3 rows.

Lemma 9.

Let G be a grid of XCH of dimension 1 × 3. Then there is no set of edge-disjoint paths consisting of five (Y,Y ′ )-paths, one (x 1 , x ′ 1 )-path and one (x 2 , x ′ 2 )-path.

Proof. Suppose that these paths exist. We distinguish two special cuts δ (L) and δ (R). There are exactly 12 vertices for crossings, and 10 are needed. The (Y,Y ′ )-paths use 5 edges of δ (L) and 5 of δ (R). The (x 1 , x ′ 1 )path A and the (x 2 , x ′ 2 )-path B both use an even number of edges in these two cuts. Moreover, they can do at most 2 crossings in each of the three groups of four crossing vertices (corresponding to the crossing vertices of an XCH graph), thus they go through each of these groups. Then each uses at least 6 edges in the two cuts, and because of parity, A uses 4 edges of δ (L) and 2 of δ (R), and B uses 2 edges of δ (L) and 4 edges of δ (R). Because d(L) = d(R) = 12, there cannot be more. Thus, each (Y,Y ′ )-path uses exactly one edge of δ (R), and one of δ (L). Then, in the central XCH graph, there are exactly one edge of δ (L) and one edge of δ (R) used by A, and two edges of δ (R) used by B. At least two edges of δ (L) must be used by the (Y,Y ′ )-paths, and at most one of δ (R). But this leads to a contradiction, as each (Y,Y ′ )-path cannot use more than one edge in any of the two cuts.

Reduction

Let ϕ be a Boolean formula in conjunctive normal form, every clause is composed of 3 literals, with n ≥ 3 clauses over a set of p ′ ≥ 3 variables. We encode the formula in a graph G ϕ , a grid of XCH and LIC with n columns. We need two rows for each variable, plus between every two of these rows, and after the last one, a buffer consisting of q = 4(p ′ + 3)n + 2 rows. Then, the grid has exactly p = 2p ′ (q + 1) rows. The i th variable X i corresponds to rows 1 + 2(i -1)(1 + q) and q + 2 + 2(i -1)(1 + q). Intuitively, one no-path will be routed through one of these two rows (but actually, we can only enforce that it will stay near one of them). All the other rows are parts of buffers, and then contain only XCH. Row 1 + 2(i -1)(1 + q) corresponds to the assignment of true to X i , so there is a LIC in each column corresponding to the clause where X i appears positively. Similarly, row q + 2 + 2(i -1)(1 + q) corresponds to the assignment of false Proof. There are exactly np gadgets in the graph, among which exactly 3n are LIC. The number of crossing vertices is exactly 4np + 6n. Moreover, there are 2n vertical paths, crossing each of the 2pp ′ horizontal paths. At most 2n(p ′ + 3) crossing vertices are not used to cross paths. As the number of rows in a buffer is q = 4(p ′ + 3)n + 2, there are at least two consecutive rows where all the crossing vertices are used to cross paths. Then we can apply Lemma 10 : there is no no-path going from the top to the bottom of a buffer. Because of the parity of vertices, G \ P is a W ∪W ′ -join, and can be decomposed in cycles and some paths with extremities in W ∪ W ′ , but there can only be (w i , w ′ i )-paths, as all other possible paths would have to go through a buffer.

This leads to a key consequence : Lemma 12. Every vertical path is contained in one column.

Proof. 2pp ′ horizontal paths and p ′ no-paths are routed through each vertical cut, which contains exactly 2p edges. Then vertical paths cannot use edges of vertical cuts.

Proof of the reduction Theorem 1. The planar edge-disjoint paths problem is strongly NP-complete, even if the demand graph has only two edges, with terminals lying on the boundary of the infinite face of the input graph.

Proof. We use the graph of polynomial size built in Section 6. Suppose that the formula is satisfiable, and consider an assignment satisfying ϕ. We route two horizontal paths through each row with the following exceptions, where we route only one horizontal path :

• in row 1 + 2(k -1)(1 + q) if the value of variable k is true, • in row q + 2 + 2(k -1)(1 + q) if the value of variable k is false
Then, for each column, we switch the two vertical paths, using Figure 6, except in the row corresponding to the first variable satisfying the clause associated with the column, where we keep the vertical paths. This is possible by Lemma 7, as there is a LIC at this intersection. The vertical paths of each column are kept exactly once. Then these paths are valid, whence the edge-disjoint paths problem has a solution. Suppose now that there is a solution to the edge-disjoint paths problem. By Lemma 12, the vertical paths do not intersect vertical cuts, and each no-path or horizontal path intersects each vertical path only once. We show that each no-path can use at most 3 distinct rows in each column (and thus are separated by at least q -2n -1 rows), iteratively on the columns of the grid. This is done by applying Lemma 8 (because there is no other no-path in the two nearest rows). Then, for each k ∈ 1, p ′ , the (w k , w ′ k )-path cannot intersect both the rows between 2(q + 1)(k -1) -2 and 2(q + 1)(k -1) + 4, and the rows between 2(q + 1)(k -1) + q -1 and 2(q + 1)(k -1) + q + 5, as q > 2n + 5. If it intersects the first group, we set the variable V k to true, otherwise we set it to false. We consider an arbitrary column. In each row except for p ′ distinct groups of three consecutive rows, there are two horizontal paths traversing the gadget from left to right, as in the hypothesis of Lemmas 4 and 6. Moreover, by construction, there are XCH above and below every LIC, so we can effectively apply Lemmas 4 and 6 to all the gadgets, except a block of five consecutive gadgets for each variable, which contains the intersection of the corresponding no-path with the given column. Now, for each of these blocks, if there are only XCH, the first and fifth gadgets follow Lemma 4, and by Lemma 9, the vertical paths cannot be shifted here. Otherwise, there is a LIC and a no-path in one of the three nearest rows, thus the variable assignment validates the corresponding clause (the fact that the no-path is not forced to pass through the LIC has no consequence, as long as it must be close enough). Then whenever the vertical paths are not shifted, the clause associated with the column is satisfied. As each column sees its vertical paths kept at least once, each clause is satisfied, thus the assignment is feasible for ϕ.

Directed case

Using a folkloric reduction, the following result is an obvious consequence of Theorem 1. Corollary 1. The arc-disjoint paths problem is strongly NP-complete, even if G is planar, the demand graph has only two arcs and the terminals lie on the boundary of the infinite face of G.

We use again the grids of subgraphs, but with different subgraphs, to prove the following theorem : Theorem 2. The planar arc-disjoint paths problem is NP-complete, even if G is acyclic and H consists of two sets of parallel edges.

We will reduce from SATISFIABILITY. Let C 1 ∧ . . . ∧ C n be a formula with n clauses, over the set of variables {X 1 , . . . , X p }. Let G 1 be a grid with n columns and 2p rows, where each point G 1 (i, j), i ∈ 1, 2p , j ∈ 1, n of the grid is a special subgraph, defined as follows (see figure 13):

• G 1 (2i -1, j) is the graph YES if X i appears positively in C j , • G 1 (2i, j) is the graph YES if X i appears negatively in C j ,
• G 1 (i, j) is NO in all other cases.

Claim 1. The formula is satisfiable if and only if there is a set P of arc-disjoint paths in G 1 such that :

(i) for each j ∈ 1, n , there is a path P j in

P from c ∈ G 1 (1, j) to b ′ ∈ G 1 (2p, j), (ii) for each i ∈ 1, p , there is a path Q i in P either from a ∈ G 1 (2i -1, 1) to a ′ ∈ G 1 (2i -1, n) or from a ∈ G 1 (2i, 1) to a ′ ∈ G 1 (2i, n).
Proof. Suppose that P exists. For all i ∈ 1, p , if Q i has extremities a ∈ G 1 (2i-1, 1) and a ′ ∈ G 1 (2i-1, n), then assign value false to X i , otherwise assign value true. Horizontal cuts and vertical cuts are directed, thus every path Q i , (i ∈ 1, p ) is contained in a single row and every path P j , j ∈ 1, n , is contained in a single column. For each path P j , j ∈ 1, n , let i be the index of the first row where P j goes through the left edge between G 1 (i, j) and G 1 (i + 1, j). Then P j is the only path that goes through G 1 (i, j), and G 1 (i, j) is a YES graph. If i is even, it means that X i 2 appears negatively in C j and this variable has value false, thus C j is satisfied. Otherwise Xi+1 2 appears positively in C j and the value of this variable is true, thus C j is also satisfied. Then the formula is satisfied. The converse is obvious.

We just have to enforce paths to be as required in the previous claim. Condition (i) is easy to satisfy. To check condition (ii) we need some gadgets, depicted in Figure 14.

Claim 2. Let P 1 be a path between a and one of a i , i ∈ {1, 2}, and P 2 be a path between b and b j , j ∈ {1, 2}, in IF, LL or TT. If P 1 and P 2 are arc-disjoint, then i = j. Claim 3. There are not two arc-disjoint paths in VV, one from b 2 to b and the other from a 1 to a.

Claim 2 and Claim 3 can be readily checked. We will also need the graph ON introduced in Figure 15. We now describe the full graph for the reduction. G is build from G 1 in the model of Figure 16. G is built from a grid with 2p + n columns and 2p rows. The subgrid defined by columns p + 1 to p + n and rows 1 to p is G 1 . Note that two rows in G(2p + 1i, i) and G(p + i, n + p + i), for all i ∈ 1, p , are special graph IF, TT, LL and VV respectively. Others are either NO or ON, according to the figure. Rows, columns, vertical cuts and horizontal cuts are defined in the same way as in Section 6. We add four terminals, one for each side of the grid (see the figure).

G 1 correspond to one row in G. Squares G(i, i), G(p + 1 -i, n + p + i), TT IF LL VV b a b 1 b 2 a 2 a 1 b 2 b 1 a a 2 a 1 b b a 1 a 2 b 2 b 1 a 2 a 1 b 2 b 1 a a b
We add a demand of 2p from s 1 to s 2 , and 2p + n from t 1 to t 2 .

Claim 4. G is acyclic.

Proof. Observe that in the grid, all arcs are from left to right or from top to bottom, and the special graphs are all acyclic.

Claim 5. There is exactly one path going from top to bottom in each column of G, this path never leaves the column. There is exactly one path going from left to right in each row of G, this path never leaves the row.

Proof. Because vertical and horizontal cuts are directed, and {s 1 }, {s 2 }, {t 1 }, {t 2 } are tight cuts. Proof. (of Theorem 2) Claim 6 proves that the path in G 1 satisfies the condition (ii) of Claim 1: if there is a solution to the arc disjoint path problem, the formula is satisfiable. The converse is also true, it is sufficient to extend the solution for G 1 naturally. As the construction is obviously polynomial, we found a Karp reduction between the two problems. The arc-disjoint paths problem being in NP, Theorem 2 is proved. Note that we can identify t 1 with s 2 , and t 2 with s 1 , thus proving that it is still true with G + H planar and only two terminals.

Corollary 2. The arc-disjoint paths problem in planar graphs is NP-complete, even if the demand graph has only two arcs, with one of request 1 (one flow plus one path).

Proof. We modify the preceding reduction. We remove t 1 and t 2 , and add arcs from the bottom of a column, to the top of the next column to the left. This preserves planarity. Then we add a demand arc from the bottom of the leftmost column to the top of the rightmost column, with demand 1. We keep the arc s 2 s 1 . The new demand must be routed through the new arcs because of the vertical tight cuts. Thus, this transformation preserves the property of the original reduction.

The problem where the total amount of demands is fixed remains open in digraphs, and in particular, the special case where we want to find a cycle in a planar digraph, that goes through two specified vertices. This last problem is mentioned in [START_REF] Schrijver | Combinatorial Optimization : Polyhedra and Efficiency[END_REF].

Figure 1 :

 1 Figure 1: The two paths on the left do not cross, those on the right cross each other.

Figure 2 :

 2 Figure 2: Possible routings through XCH and LIC.

Figure 3 :

 3 Figure 3: Additional routings for LIC. When there is only one horizontal path, the vertical paths are not forced to be diagonal.

Figure 4 :

 4 Figure 4: How to forbid the crossing of paths at vertex v.

Figure 5 :

 5 Figure 5: The graph XCH. There are only four crossing vertices a, b, c and d. All the inner vertices have degree 4.

Figure 6 :

 6 Figure 6: Existence of the paths for Lemma 4.

Figure 7 :

 7 Figure 7: Graph LIC. Except two additional crossing vertices, it is similar to XCH.

Figure 8 :

 8 Figure 8: Existence of the paths for Lemma 7.

Figure 10 :

 10 Figure 10: There is no solution to this edge-disjoint paths problem, even if Q can cross other paths at every vertex. Edges contained in some tight cut are drawn thick.

  Because of tight cuts, M(1, 1) contains C, M(1, 2) contains E, and M(1, 3) contains H. In M(1, 2), E goes through u 6 , (u 3 and u 4 are non-crossing vertices, and at least one of the paths A, B or D goes through these vertices) and uses u 6 c or u 6 u 8 . For the same reason, E goes through u 7 and uses u 7 u 5 or u 7 b. Consider in M(1, 2) the cuts C 1 := {u 5 u 7 , u 5 b, ab, ac, u 6 c, u 6 u 8 } and C 2 := {u 5 u 7 , u 7 b, bd, cd, cu 8 , u 6 u 8 }. There are exactly four paths routed through these two cuts, and E must use three edges from at least one of them, because it can use neither u 10 d nor au 3 . Then F cannot go through C 1 , proving that it can cross A or B only at vertex d in M(1, 2). Similarly, in M(1, 3), using path H and the same two cuts (we call them C ′ 1 and C ′ 2 ), F can only cross A or B at vertex a. Because of Lemma 2 and the tight cut between M(1, 2) and M(1, 3), F crosses A in a of M(1, 3) and then crosses B in d of M(1, 2). As F cannot use edges in both C 1 and C ′ 2 , F must traverse d of M(1, 2) and a of M(1, 3) from left to right or from right to left, an odd number of times. This is indeed a contradiction.

Figure 13 :

 13 Figure 13: In NO, there is no path from c to b ′ , whereas it is possible in YES, as long as no other path goes through the graph.

Figure 14 :Figure 15 : 1 Figure 16 :

 1415116 Figure 14: Four special subgraphs, from top to bottom and left to right : IF, LL, TT, VV. First three have the property that if there are two arc-disjoint paths, one between a and a i and the other between b and b j , then i = j.

Claim 6 .

 6 If a horizontal path leaves G 1 by the lower edge of its row in the (n + p) th vertical cut, then the same path enters G 1 by the lower edge of its row in the p th vertical cut.Proof. In each square ON or NO, there is exactly one path from b to b ′ or from c to c ′ , and one path from a to a ′ , because of properties of these gadgets. Consequently, a vertical path leaves an IF gadget by the left if and only if it enters the LL gadget of the same column by the left. Similarly for paths between LL and VV, for paths between TT and VV, for paths between IF and G 1 and for paths between G 1 and TT. If a path leaves G 1 by the lower edges of its row, say row i ∈ 1, p , then it enters G(i, 2p + n + 1i) by vertex b 2 . The vertical path of column 2p + n + 1i leaves G(i, 2p + n + 1i) by vertex a 2 by Claim 2, and then enters G(2p + 1i, 2p + n + 1i) by vertex a 1 . Thus the horizontal path in row 2p + 1i goes in G(2p + 1i, 2p + n + 1i) using vertex b 1 by Claim 3, and leaves G(2p + 1i, i) by vertex a 1 . Using Claim 2, the vertical path in column i goes in G(2p + 1i, i) by vertex b 1 , thus goes out G(i, i) by vertex a 1 . By Claim 2 again, the horizontal path of row i leaves G(i, i) by b 1 , and then enters G 1 by the lower edge, proving the claim.

to X i , so there is a LIC in each column corresponding to the clause where X i appears negatively. All other subgraphs are XCH. In summary, M(i, j) is a LIC if and only if :

• either j = 1 + 2(i -1)(1 + q) and X i appears positively in the j th clause,

• or j = q + 2 + 2(i -1)(1 + q) and X i appears negatively in the j th clause.

We add two terminals for the vertical paths, x and x ′ . As the number of rows is even, and we want the vertical paths to be shifted an odd number of times, we add the following edges : xx 4k+1 , xx 4k+2 , x ′ 4k+3 x ′ and x ′ 4k+4 x ′ for each k ∈ 0, n -1 . Thus we enforce the parity of the number of shifts. Moreover, to reduce the number of odd vertices, we add the edges x 4k+3 x 4k+4 and x ′ 4k+1 x ′ 4k+2 for each k ∈ 0, n -1 . For each variable X i , i ∈ 1, p ′ , we add two new vertices w i and w ′ i , and the edges w i y j and w ′ i y ′ j for all j ∈ 4(i -1)(q + 1) + 1, 4(i -1)(q + 1) + 2q + 4 (that is w i is connected to the vertices of Y between the two rows encoding X i ). These new vertices will be the extremities of the no-paths. Then we add two terminals for the horizontal paths y and y ′ . y is connected to w i by 2q + 3 parallel edges, and to every vertex of Y that still have a degree one by a single edge. Symmetrically, y ′ is connected to w ′ i by 2q + 3 parallel edges, and to every vertex of Y ′ not adjacent to some w ′ i . Thus y and y ′ have degrees 2pp ′ . Finally we demand to find 2n (x, x ′ )-paths and 2pp ′ (y, y ′ )-paths, defining the demand graph H ϕ . The vertices of odd degree in G ϕ + H ϕ are the vertices of

The following cuts are tight : δ (x), δ (x ′ ), δ (y) and δ (y ′ ). Figure 12 gives an overview of the reduction. We define precisely the vertical paths to be the (x, x ′ )-path of a solution, and the horizontal paths are the (y, y ′ )-paths. We say that two paths are parallel if they are both horizontal, or both vertical, otherwise they are orthogonal.

No-paths

Let P be a solution to the edge-disjoint paths problem (G ϕ , H ϕ ). By considering P as a set of cycles of G ϕ + H ϕ containing exactly one edge from E(H ϕ ), the vertices of G ϕ have the same degrees in G ϕ + H ϕ and G ϕ + H ϕ \ E(P). So the edges of the complementary graph of the solution P is a

The following lemma proves that the no-paths cannot traverse the buffers, implying that the vertical paths stay in their respective columns. This last fact will allow us to apply the previous lemmas.

Lemma 10. Let G be a grid of dimension n × p. Let P be an uncrossed set of (X, X ′ )-paths and (Y,Y ′ )paths pairwise edge-disjoint. Suppose there exists i ∈ 2, p -2 such that for all j ∈ 1, n , M(i, j) and M(i + 1, j) are XCH and there are exactly four crossings of paths of P in M(i, j) and in M(i + 1, j). Then, there is no no-path between a vertex of row i -1 and a vertex of row i + 2.

Proof. Let i ∈ 2, p -2 such that each crossing vertex of rows i and i + 1 is used for a crossing, and suppose there is a no-path Q between rows i -1 and i + 2. Then Q must pass through u 5 u 7 or u 6 u 8 in some M( j, i), say u 6 u 8 by symmetry, and then passes through e j,i 3 , e j,i 4 , e j+1,i 1 or e j+1,i 2 (because all the a, b, c and d vertices are used by paths). Let P 1 , P 2 , P 3 , P 4 be the paths going through edges c j,i u j,i 8 , d j,i u j,i 11 , a j,i+1 u j,i+1 3 , c j,i+1 u j,i+1 6 respectively. We consider the cut

}, intersected by these four paths and Q. Because |C| = 8, at most four different paths and no-paths intersect C. As the solution is uncrossed, P 1 and P 2 are different and parallel, and P 3 and P 4 also. There is no crossing vertex among U, thus P 2 = P 3 . By Lemma 1, P 1 , P 2 and P 4 are crossed by their orthogonal paths in the same order, then P 1 = P 4 . We remark that j = n, otherwise the routing is not possible. At least one of P 1 , P 2 and Q must go through U ′ = {u j+1,i , say P 1 (the other cases are isomorphic). Then, we can consider the cycle consisting of the subpath of P 1 between c j,i and c j,i+1 , the edges c j,i+1 a j,i+1 and c j,i d j,i and the subpath of P 2 between d j,i and a j,i+1 . Because of Lemma 1, no path can enter inside this cycle, but it contains at least one crossing vertex in rows i and i + 1, leading to a contradiction. Lemma 11. The complementary Q of P can be decomposed into cycles and one (w i , w ′ i )-path for each i ∈ 1, p ′ .


Ewa Pasquereau-Kotula

Laurence Du

Odile Sismeiro

Natalia Pietrosemoli

Hugo Varet

Rachel Legendre

Patrick Trieu-Cuot

Laurence Du Merle

Shaynoor Dramsi
email: shaynoor.dramsi@pasteur.fr

Transcriptome profiling of human colcells exposed to the gut pathobiont Streptococcus gallolyticus subsp. gallolyticus

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

Introduction

Colorectal cancer (CRC) is the third leading malignancy worldwide and the second most common cause of cancer mortality, regardless of gender [START_REF]Colorectal cancer-IARC n[END_REF]. The majority of CRC cases are sporadic, occurring in people without a family history or genetic predisposition [START_REF] Rustgi | The genetics of hereditary colon cancer[END_REF]. Environmental risk factors such as lifestyle, diet, smoking and gut microbiota contribute significantly to the development of sporadic CRCs [START_REF] Garrett | The gut microbiota and colon cancer[END_REF]. Streptococcus gallolyticus was one of the first bacterium to be strongly associated with CRC by epidemiological studies [START_REF] Mccoy | Enterococcal endocarditis associated with carcinoma of the sigmoid; report of a case[END_REF][START_REF] Ballet | Infective endocarditis due to Streptococcus bovis. A report of 53 cases[END_REF][START_REF] Lieberman | Use of colonoscopy to screen asymptomatic adults for colorectal cancer. Veterans Affairs Cooperative Study Group 380[END_REF][START_REF] Corredoira | Clinical characteristics and significance of Streptococcus salivarius bacteremia and Streptococcus bovis bacteremia: a prospective 16-year study[END_REF][START_REF] Boleij | Clinical Importance of Streptococcus gallolyticus infection among colorectal cancer patients: systematic review and meta-analysis[END_REF]. In line with the literature, we showed that SGG prevalence in the French population (patients with normal colonoscopies) is about 32.5%, and it is increased to 50% in the stools of patients with adenocarcinomas [START_REF] Pe ´richon | Detection of Streptococcus gallolyticus and Four Other CRC-Associated Bacteria in Patient Stools Reveals a Potential "Driver" Role for Enterotoxigenic Bacteroides fragilis[END_REF].

Streptococcus gallolyticus has been subdivided into three subspecies, subsp. gallolyticus (SGG), subsp. pasteurianus (SGP) and subsp. macedonicus (SGM). SGG (formerly known as S. bovis type I) is an extracellular opportunistic pathogen responsible for septicemia and endocarditis in the elderly. SGP causes bacteremia, endocarditis, urinary tract infection in elderly and immunodeficient people, septicemia and meningitis in newborns and intrauterine infections in pregnant woman [START_REF] Li | Microbiological and clinical characteristics of Streptococcus gallolyticus subsp. pasteurianus infection in China[END_REF][START_REF] Matesanz | Is Streptococcus bovis a urinary pathogen?[END_REF][START_REF]Late-onset Streptococcus pasteurianus sepsis in a preterm baby in a neonatal intensive care unit n.d[END_REF][START_REF] Binghuai | Intrauterine infection and post-partum bacteraemia due to Streptococcus gallolyticus subsp. pasteurianus[END_REF]. SGM, the genetically closest SGG relative is generally considered as safe and non-pathogenic specie [START_REF] Vuyst | Streptococcus macedonicus, a multi-functional and promising species for dairy fermentations[END_REF][START_REF] Maragkoudakis | The Combined Use of Whole-cell Protein Extracts for the Identification (SDS-PAGE) and Enzyme Activity Screening of Lactic Acid Bacteria Isolated from Traditional Greek Dairy Products[END_REF]. SGM is a homofermentative lactic acid bacterium which was first isolated from a typical Greek cheese obtained by natural fermentation [16]. A couple of studies have reported that some SGM strains possess probiotic properties [START_REF] Laiño | Characterization of folate production and probiotic potential of Streptococcus gallolyticus subsp. macedonicus CRL415[END_REF][START_REF] Khaldi | Streptococcus macedonicus strains isolated from traditional fermented milks: resistance to gastrointestinal environment and adhesion ability[END_REF]. Among the gallolyticus subspecies, only SGG is associated with CRC, suggesting that SGG-specific attributes contribute to this association.

In the last decade, several groups have contributed in deciphering the mechanisms explaining SGG association with CRC [START_REF] Kumar | Streptococcus gallolyticus subsp. gallolyticus promotes colorectal tumor development[END_REF][START_REF] Kumar | Variations among Streptococcus gallolyticus subsp. gallolyticus strains in connection with colorectal cancer[END_REF][START_REF] Aymeric | Colorectal cancer specific conditions promote Streptococcus gallolyticus gut colonization[END_REF][START_REF] Taylor | A type VII secretion system of Streptococcus gallolyticus subsp. gallolyticus contributes to gut colonization and the development of colon tumors[END_REF][START_REF] Pasquereau-Kotula | The oncogenic role of Streptococcus gallolyticus subsp. gallolyticus is linked to activation of multiple cancer-related signaling pathways[END_REF]. Previously, our group showed that SGG strain UCN34 takes advantage of the tumoral environment to better colonize the murine colon in the Notch/ APC model [START_REF] Aymeric | Colorectal cancer specific conditions promote Streptococcus gallolyticus gut colonization[END_REF]. Almost simultaneously, another group showed that SGG strain TX20005 enhanced colon tumor development through activation of Wnt/β catenin signaling pathway [START_REF] Kumar | Streptococcus gallolyticus subsp. gallolyticus promotes colorectal tumor development[END_REF][START_REF] Kumar | Variations among Streptococcus gallolyticus subsp. gallolyticus strains in connection with colorectal cancer[END_REF]. Very recently, we showed that SGG strain UCN34 accelerates tumor development in the murine AJ/AOM model by altering multiple signaling pathways in epithelial and underlying stromal cells, including all three MAPK families, mTOR, and integrin/ILK [START_REF] Ewa | Global proteomic identifies multiple cancer-related signaling pathways altered by a gut pathobiont associated with colorectal cancer[END_REF]. Whether SGG contributes to tumor initiation and/or progression in human colonic cells remained an open question and prompted this study. We decided to evaluate the consequences of SGG infection on the transcriptome of human colonic cells by comparing non-transformed fetal cells (FHC) and cancerous HT29 cells derived from a colon adenocarcinoma. A recent study reported the transcription profiling of in vitro cultured human colorectal adenocarcinoma HT29 cells infected with SGG for 4 h in which 44 genes were significantly up-(21 genes) or down-regulated (23 genes) [START_REF] Taddese | Streptococcus gallolyticus Increases Expression and Activity of Aryl Hydrocarbon Receptor-Dependent CYP1 Biotransformation Capacity in Colorectal Epithelial Cells[END_REF]. Most up-regulated genes were involved in detoxification or bio-activation of toxic compounds [START_REF] Taddese | Streptococcus gallolyticus Increases Expression and Activity of Aryl Hydrocarbon Receptor-Dependent CYP1 Biotransformation Capacity in Colorectal Epithelial Cells[END_REF], which might alter intestinal susceptibility to DNA damaging events and on long-term contribute to carcinogenesis.

Tumour initiation is the first step in cancer development, where normal cells transform into cancerous cells due to genetic (mutations) or epigenetic changes [START_REF] Hanahan | The hallmarks of cancer[END_REF]. When a critical gene involved in regulating cell growth and division, such as a proto-oncogene or a tumour suppressor gene, undergoes a mutation that disrupts its normal function, it can lead to uncontrolled cell growth [START_REF] Hanahan | The hallmarks of cancer[END_REF]. Epigenetic changes affect gene expression without altering DNA sequences, mostly through DNA methylation and histone modifications [START_REF] Zhang | Epigenetics in Health and Disease[END_REF]. These changes can silence tumour suppressors or activate proto-oncogenes, promoting uncontrolled cell growth [START_REF] Zhang | Epigenetics in Health and Disease[END_REF]. In many cases, these initial genetic changes lead to the formation of benign growth called polyps or adenomas which can progress to malignancy over time if additional genetic alterations occur. These genetic alterations can affect genes involved in cell growth, cell cycle regulation, DNA repair and apoptosis. CRC is associated with genomic instability defined as chromosomal instability (CIN) and microsatellite instability (MSI). Tumour progression refers to processes that drive the growth and spread of an existing tumour. This can involve mechanisms that stimulate the division of cancer cells, inhibit cell death (apoptosis), promote angiogenesis (formation of new blood vessels to supply the tumour), enhance metastasis (spread of cancer to other parts of the body), and create a microenvironment conducive to tumour growth [START_REF] Fares | Molecular principles of metastasis: a hallmark of cancer revisited[END_REF]. Both stages (initiation and progression) are critical in understanding the development and progression of CRC.

We aimed here to identify host pathways specifically induced by SGG which could contribute to tumor initiation or/and progression. To identify cancer-related genes or pathways activated in vitro upon infection with SGG, we performed a global transcriptome analysis of normal human colonic cells (FHC) and cancerous (HT29) cells after 24 h of co-culture. We also decided to compare gene expression profiles of normal vs cancerous colonic cell in response to SGG vs SGM to infer more robust conclusions. We reasoned that if SGG is an oncogenic bacterium involved in tumor initiation, we should see a specific transcriptomic signature on normal, non-transformed cells such as the FHC cell line (CRL-1831, ATCC) [29], which is an epithelial cell line isolated from the large intestine of a 13-week-old human embryo. The second possibility being that SGG acts as an accelerator of tumor and thus will have a much stronger impact on pre-transformed cells such as HT29 cell line (HTB-38, ATCC) [30] which is a human colorectal adenocarcinoma cell line with epithelial morphology.

We present here a comprehensive analysis of the transcriptome alterations induced by SGG infection in normal colonic cells and in tumoral colonic cells. A total of 2,090 genes were differentially altered in tumoral HT29 cells as compared to 128 genes in normal FHC cells, suggesting that SGG is rather a tumor accelerator than an initiator which fits well with our previous in vivo data showing that SGG contribute to tumor acceleration in chemically initiated CRC mouse model [START_REF] Pasquereau-Kotula | The oncogenic role of Streptococcus gallolyticus subsp. gallolyticus is linked to activation of multiple cancer-related signaling pathways[END_REF].

Materials and methods

Bacterial strains and culture conditions

SGG UCN34 [START_REF] Rusniok | Genome sequence of Streptococcus gallolyticus: insights into its adaptation to the bovine rumen and its ability to cause endocarditis[END_REF] and SGM strain CIP105683T [START_REF] Proutière | Gallocin A, an Atypical Two-Peptide Bacteriocin with Intramolecular Disulfide Bonds Required for Activity[END_REF] were grown at 37˚C in Todd Hewitt Yeast (THY) broth in standing filled flasks or on THY agar plates (Difco Laboratories).

Cell culture

The human normal colon epithelial cell line FHC (ATCC: CRL-1831 [29]) was cultured in DMEM/F12 medium (Gibco, France) supplemented with 20% heat-inactivated calf serum and additional factors (25 mM HEPES; 10 ng/mL cholera toxin; 0.005 mg/mL insulin; 0.005 mg/ mL transferrin; 100 ng/mL hydrocortisone; EFG 20 ng/mL; 10% SVF) to sustain their growth and could be passed 5-10 times only. The human cancerous cell line HT-29 (ATCC: HTB-38 [30]) was cultivated in DMEM with 10% heat-inactivated calf serum and supplemented with 25 mM HEPES. The cells were cultured in ventilated T75 flasks at 37˚C and 5% CO 2 .

Infection of epithelial cells with bacteria

FHC cells were seeded into 6-well plates at a density of 2 x 10 5 cells per well and HT29 cells at 4 x 10 5 cells per well and incubated for 16-20 hours. Stationary phase bacteria were scratched from fresh THY plates (overnight culture) and washed with sterile phosphate buffered saline, pH 7.4 (PBS) to get an OD 600 of 1 (corresponding to 6.5 x 10 8 CFU). Bacteria were diluted in DMEM (Gibco, Ref. 12320032, low glucose, pyruvate, HEPES) at the following concentrations (i) SGM of 6.5 x 10 5 CFU/ml and (ii) SGG UCN34 of 6.5 x 10 4 CFU/ml. Cells are washed once with DMEM and then infected with the medium containing the bacteria by adding 2 ml of bacterial suspension per well in the 6-well plate. For the non-treated (NT) condition, only 2 ml of fresh media was added. For each condition, a complete 6-well plate was used and then pooled together to obtain enough cellular material for further RNA extraction. Trimethoprim (Sigma, Ref. T7883), a bacteriostatic antibiotic was added at 50 μg.ml -1 final concentration after 6 h of co-culture to prevent media acidification due to bacterial growth. The total co-culture incubation time was 24 h. Total RNA was extracted from cell monolayers with the RNeasy Plus Mini kit (Qiagen, USA), according to the manufacturer's instructions. Three independent replicates for each condition were performed and analyzed. RNAs were conserved at -80˚C and used in transcriptome Illumina assay and quantitative RT-PCR.

Transcriptome Illumina analysis

Total RNA from three independent replicates of each experimental condition: FHC NT (n = 3), FHC SGM (n = 3), FHC SGG UCN34 (n = 3), HT29 NT (n = 3), HT29 SGM (n = 3), HT29 SGG UCN34 (n = 3) were checked on RNA 6000 Nano chips (Bioanalyzer, Agilent) for its quality and integrity. Directional libraries were prepared using the TruSeq Stranded mRNA Sample preparation kit following the manufacturer's instructions (Illumina). Libraries were checked for quality on DNA 1000 chips (Bioanalyzer, Agilent). Quantification was performed with the fluorescent-based quantitation Qubit dsDNA HS Assay Kit (Thermo Fisher Scientific). Sequencing was performed as a Single Read Multiplexed run for 65 bp sequences on HiSeq 2500 sequencer (Illumina). The multiplexing level was 6 samples per lane. Reads were cleaned of adapter sequences and low-quality sequences using cutadapt version 1.11 [START_REF] Martin | Cutadapt removes adapter sequences from high-throughput sequencing reads[END_REF]. Only sequences at least 25 nucleotides in length were considered for further analysis. STAR version 2.5.0a [START_REF] Dobin | STAR: ultrafast universal RNAseq aligner[END_REF], with default parameters, was used for alignment on the reference genome (Human genome hg38 from Ensembl). Genes were counted using featureCounts version 1.4.6-p3 [START_REF] Liao | featureCounts: an efficient general purpose program for assigning sequence reads to genomic features[END_REF] from Subreads package (parameters: -t exon -g gene_id -s 1). Count data were analyzed using R version 3.5.1 [START_REF]The R Project for Statistical Computing n[END_REF] and the Bioconductor package DESeq2 version 1.20.0 [START_REF] Love | Moderated estimation of fold change and dispersion for RNA-seq data with DESeq2[END_REF]. The normalization and dispersion estimation were performed with DESeq2 using the default parameters and statistical test for differential expression were performed applying the independent filtering algorithm. A generalized linear model including the replicate effect, the cell line, the infection status as well as the cell line-infection interaction was set up to test for the differential expression between the conditions. For each pairwise comparison, raw p-values were adjusted for multiple testing according to the Benjamini and Hochberg (BH) procedure [START_REF] Benjamini | Controlling the False Discovery Rate: A Practical and Powerful Approach to Multiple Testing[END_REF] and genes with an adjusted p-value lower than 0.05 were considered differentially expressed.

Gene Set Enrichment analysis (GSEA) was performed using the Camera (competitive gene set test accounting for inter-gene correlation) [START_REF] Wu | Camera: a competitive gene set test accounting for inter-gene correlation[END_REF] method from the limma R package (version 3.34.9). Functional annotation of the genes was obtained using the Hallmark gene sets, the KEGG and Reactome biological pathway and the Gene Ontology collections from the MSigDB database (GSEA, UC San Diego, CA, USA) [START_REF] Liberzon | The Molecular Signatures Database (MSigDB) hallmark gene set collection[END_REF]. GSEA was performed on the complete count matrix and gene sets with p-value � 0.05 were considered statistically significant. Ingenuity Pathway Analysis (IPA) was performed using genes differentially expressed between SGG UCN34 and SGM to specifically identify diseases associated to those genes.

Each principal component analysis (PCA) is based on the variance-stabilized transformed count matrix that has been adjusted for the replicate effect using the removeBatchEffect function or the limma R package (version 3.52.4).

Gene expression analysis

Total RNA was extracted from cell monolayers with the RNeasy mini kit (Qiagen, USA), according to the manufacturer's instructions. First-strand cDNA synthesis was performed using the iScript cDNA synthesis kit (Biorad). To do so, a 20 μL solution was prepared with 1 μg of RNA, 4 μL of the 5X iScript reaction mix, 1 μL of the iScript Reverse Transcriptase, and completed with RNase free water. The reverse transcription program was as follows: 5 min at 25˚C, 30 min at 42˚C, 5 min at 85˚C and 15 min at 15˚C. cDNAs were diluted to the hundredth and stored at -20˚C. Quantitative real-time PCR was performed using SsoFast Eva-Green Supermix (Bio-Rad) with EvaGreen as fluorescent dye according to the manufacturer's protocol. Primers used for amplification of cDNA are specified in S1 Table . GAPDH, a housekeeping gene, was used as internal control for normalization. Fold difference of mRNA levels was calculated using the ΔΔCt method. All PCR reactions were performed in duplicates and repeated three independent times.

Statistical analysis

Mann-Whitney nonparametric test was used to test for statistical significance of the differences between the different group parameters. p values of less than 0.05 were considered statistically significant.

Results

Comparison of host transcriptomic responses in normal and tumoral colonic cells exposed to SGG

To unravel the effects of SGG on gene expression of human colonic cells, a global transcriptome was performed in normal FHC and tumoral HT29 cells following 24 h of co-culture with SGG UCN34 vs SGM. The experimental protocol is schematized in To ensure proper growth and health of normal colonic FHC cells, transcriptomics experiments were performed under sub-confluent conditions (50-60% of confluence). To compare properly the adhesion of SGG and SGM to FHC and HT29 cells, adhesion assay on 100% confluent monolayers were performed and showed that SGM adheres as well as SGG on both cell lines after 24 h of co-culture (Fig 2D).

Analysis of differentially expressed genes (adjusted p-value < 0.05 and log2 fold change (FC) > 0.5 or < -0.5) between cells co-cultured with SGM bacteria vs control NT condition revealed that SGM did not induce any transcriptional changes on HT29 and FHC cells. Only two genes were found dysregulated in FHC cells (Fig 1B). These results indicate that SGM constitutes an appropriate control bacterium to decipher the specific pathogenic traits of SGG. Next, we focused on comparing SGG vs SGM conditions in more details. We identified 128 differentially expressed genes (adjusted p-value < 0.05 and log2 fold change (FC) > 0.5 or < 0. ). It is worth noting that the 2 up-regulated genes were: (i) CDC like kinase 1 (CLK1) and (ii) DNA polymerase beta (POLB). CLK1 plays a crucial role in the regulation of proliferation, invasion and migration in gastric cancer and was described as a novel therapeutic target [START_REF] Babu | Phosphoproteomic analysis identifies CLK1 as a novel therapeutic target in gastric cancer[END_REF]. POLB performs base excision repair (BER) in case of DNA damage and is often imbalance in CRC [START_REF] Leguisamo | Base excision repair imbalance in colorectal cancer has prognostic value and modulates response to chemotherapy[END_REF]. In general, our results show that SGG induces specific transcriptomic signature dependent on the cell type (normal or cancerous) suggesting different consequences of SGG presence in healthy colon vs colon with cancerous lesions. cells/well and HT29: 4 x 10 5 cells/well) and incubated for 16-20 hours. Cells were infected with bacteria: SGG UCN34 (6.5 x 10 4 CFU/ml) and SGM (6.5 x 10 5 CFU/ml). Trimethoprim (50 μg/ml) was added to the wells after 6 hours of co-culture to prevent bacterial over-growth. The total infection time was 24 h. Total RNA was prepared, processed and sequenced using Illumina technology. This experiment was performed in triplicate (n = 3). B. Table recapitulating the transcriptional changes in FHC and HT29 induced by SGM vs NT and SGG UCN34 vs SGM conditions. Criteria for significant gene changes were as follows: adjusted p < 0.05 and log2 fold change (FC) > 0.5 or < -0.5). C. Venn diagram showing that 41 genes regulated upon SGG UCN34 infection were in common between FHC and HT29 cells. D. PCA of transcriptome samples in FHC cells: SGG (n = 3); SGM (n = 3) and NT (n = 3). E. PCA of transcriptome samples in HT29 cells: SGG (n = 3); SGM (n = 3) and NT (n = 3). D and E. Each PCA is based on the variance-stabilized transformed count matrix that has been adjusted for the replicate effect using the remove BatchEffect function or the limma R package (version 3.52.4). https://doi.org/10.1371/journal.pone.0294868.g001 hand. The 6 up-regulated genes (IL-20, CLK1, SORBS2, ERG1, PIM1, SNORD3A) are involved in cancer development [START_REF] Weirauch | Functional role and therapeutic potential of the pim-1 kinase in colon carcinoma[END_REF][START_REF] Luo | LncRNA SNORD3A specifically sensitizes breast cancer cells to 5-FU by sponging miR-185-5p to enhance UMPS expression[END_REF][START_REF] Luo | Novel prognostic model predicts overall survival in colon cancer based on RNA splicing regulation gene expression[END_REF][START_REF] Liu | Interleukin 20 receptor A expression in colorectal cancer and its clinical significance[END_REF][START_REF] Wang | The Role of the Transcription Factor EGR1 in Cancer[END_REF][START_REF] Zhang | NOVA1-Mediated SORBS2 Isoform Promotes Colorectal Cancer Migration by Activating the Notch Pathway[END_REF]. Interleukin 20 (IL-20) is a cytokine assigned to the interleukin 10 family described as tumor promoting [START_REF] Niess | The Interleukin-20 Cytokines in Intestinal Diseases[END_REF]. Sorbin and SH3 domain containing 2 (SORBS2) promotes colon cancer migration though activation of the Notch pathway [START_REF] Zhang | NOVA1-Mediated SORBS2 Isoform Promotes Colorectal Cancer Migration by Activating the Notch Pathway[END_REF]. Small nucleolar RNA, C/D box 3A (SNORD3A) was shown to be involved in doxorubicin resistance in human osteosarcoma cells through modulating multiple genes promoting proliferation, ribosome biogenesis, DNA damaging sensing, and DNA repair [START_REF] Godel | Small Nucleolar RNAs Determine Resistance to Doxorubicin in Human Osteosarcoma[END_REF]. Early growth response 1 (ERG1) is implicated in the regulation of cell growth, proliferation, differentiation and apoptosis in CRC [START_REF] Wang | The Role of the Transcription Factor EGR1 in Cancer[END_REF][START_REF] Myung | Expression of early growth response-1 in colorectal cancer and its relation to tumor cell proliferation and apoptosis[END_REF]. Proto-oncogene serine/threonine-protein kinase (Pim-1) promotes CRC growth and metastasis [START_REF] Zhang | Pim1 supports human colorectal cancer growth during glucose deprivation by enhancing the Warburg effect[END_REF]. We confirmed the up-regulation of these 6 genes using quantitative RT-PCR analysis (Fig 3B ). 11 pathways were predicted to be activated (from light grey to pink) and 3 to be down-regulated (blue) (Fig 3E).

In depth analysis of the transcriptomic responses of normal colonic cells

In depth analysis of the transcriptomic responses of tumoral colonic cells

SGG altered the expression of as many as 2,090 genes in tumoral colonic human HT29 cells. https://doi.org/10.1371/journal.pone.0294868.g003 much higher in tumoral HT29 cells than for normal FHC cells (� 2). The most 10 up-regulated genes are: TSLP, SPX, BHLHA15, GPR1, NGFR, ZNF27B, KLHDC7B, LAMP3, KRT17 and ATF3. The up-regulation of these 10 genes was confirmed independently using quantitative RT-PCR (Fig 4B). Both techniques gave similar fold changes between SGG and SGM (R = 0.77; Fig 4C). Importantly, 6 out of 10 most up-regulated genes were involved in CRC development. Indeed, the high expression of thymic stromal lymphopoietin (TSLP) in cancer cells correlates with a poor prognosis for CRC patients [START_REF] Obata-Ninomiya | Emerging role for thymic stromal lymphopoietin-responsive regulatory T cells in colorectal cancer progression in humans and mice[END_REF]. Basic helix-loop-helix family Pathway Analysis (IPA) using genes differentially expressed between SGG UCN34 and SGM. Molecules indicate the number of genes associated with indicated diseases and disorders. A right-tailed Fisher's Exact Test was used to calculate a p-value determining the probability that each biological function and/or disease assigned to that data set is due to chance alone. E. Network of representation of the 9 significantly enriched HALLMARK gene sets upon SGG infection on HT29 cells. Each node (circle) represents a gene set. Node size is proportional to the number of genes present in the dataset and belonging to the gene set. Node colors reflect the average expression directionality (based on the average of the log fold expression for each gene belonging to the gene set) (red = over expressed; blue = down regulated; grey = no statistically significant difference in expression). The intensity of the color is proportional to the strength of the average expression. Each edge connecting two nodes means that two gene sets share the same genes. The edge width is proportional to the number of genes shared among the two gene sets. Edges are shown only if at least two genes are shared among the two gene sets (11 edges). https://doi.org/10.1371/journal.pone.0294868.g004 member a15 (BHLHA15) is involved in CRC initiation through YAP/Wnt pathway activation [START_REF] Hayakawa | BHLHA15-Positive Secretory Precursor Cells Can Give Rise to Tumors in Intestine and Colon in Mice[END_REF]. Lysosomal associated membrane protein 3 (LAMP3) and zinc finger protein 274 (ZNF27B) are both up-regulated in CRC patients [START_REF] Sun | Prognostic value of LAMP3 and TP53 overexpression in benign and malignant gastrointestinal tissues[END_REF][START_REF] Rooney | The candidate oncogene ZNF217 is frequently amplified in colon cancer[END_REF]. Keratin 17 (KRT17) is an oncogene in several types of cancer and is used as a biomarker of CRC [START_REF] Ji | Keratin 17 upregulation promotes cell metastasis and angiogenesis in colon adenocarcinoma[END_REF]. Activating transcription factor 3 (ATF3) is promoting tumor growth in CRC [START_REF] Ku | Master Regulator Activating Transcription Factor 3 (ATF3) in Metabolic Homeostasis and Cancer[END_REF].

The heat map shown in

IPA analysis revealed that most differentially expressed genes were involved in cancer disease (1,902 out of 2,090;

Discussion

Colorectal cancer (CRC) is the third most common cause of cancer mortality worldwide. The colon is a very singular organ, colonized by a vast and complex community of microorganisms, known as the gut microbiota. Strong evidence supports a role of the microbiota in colon cancer development. Streptococcus gallolyticus subsp. gallolyticus (SGG) was one of the first bacteria to be associated with colon tumors in humans. This association is so robust that colonoscopy is highly recommended to patients diagnosed with an invasive infection to SGG. Thus, understanding the role of SGG in colon cancer is critical to developing novel diagnostic and/or therapeutic strategies. Here we aimed to identify transcriptomic alterations in human colonic cells cultivated in vitro during interaction with the CRC-associated gut pathobiont SGG. As a control condition for comparison, we have chosen host cells infected with the genetically closest but non-pathogenic bacterium SGM. As expected for a commensal bacterium, SGM did not induce any significant transcriptional changes on human colonic cells. In contrast, SGG altered a higher number of genes (2,090) in tumoral HT29 cells as compared to normal FHC cells (128 genes). Most of these genes were associated with cancer disease and transcriptional profiling analysis suggest that SGG is rather a weak tumor initiator and potentially a strong tumor accelerator. This result fits well with our recent in vivo data showing that SGG contributes to tumor development in mouse pre-treated with a chemical mutagen such as azoxymethane (AOM) [START_REF] Pasquereau-Kotula | The oncogenic role of Streptococcus gallolyticus subsp. gallolyticus is linked to activation of multiple cancer-related signaling pathways[END_REF].

SGG induced a rather weak pro-tumor transcriptional signature on normal colonic FHC cells but was still specific (few genes exhibiting altered transcriptional profile with a low fold change). All the most up-regulated genes (IL-20, CLK1, SORBS2, ERG1, PIM1, SNORD3A) are involved in cancer development [START_REF] Babu | Phosphoproteomic analysis identifies CLK1 as a novel therapeutic target in gastric cancer[END_REF][START_REF] Weirauch | Functional role and therapeutic potential of the pim-1 kinase in colon carcinoma[END_REF][START_REF] Luo | LncRNA SNORD3A specifically sensitizes breast cancer cells to 5-FU by sponging miR-185-5p to enhance UMPS expression[END_REF][START_REF] Liu | Interleukin 20 receptor A expression in colorectal cancer and its clinical significance[END_REF][START_REF] Zhang | NOVA1-Mediated SORBS2 Isoform Promotes Colorectal Cancer Migration by Activating the Notch Pathway[END_REF]. We postulate that activation of all these genes could contribute to pre-cancerous transformation of colonic cells on long-term. Only two genes, clk1 and polB, were found up-regulated in both FHC and HT29 cells, suggesting a role in cell proliferation and/or DNA damage. We have not been able to show a significant effect of SGG UCN34 on host cell proliferation (HT29 and HCT116) by direct counting of epithelial colonic cells [START_REF] Pasquereau-Kotula | The oncogenic role of Streptococcus gallolyticus subsp. gallolyticus is linked to activation of multiple cancer-related signaling pathways[END_REF]. To test experimentally whether SGG can induce DNA damage of colonic cells, DNA damage quantification using confocal microscopy (γH2AX foci detection [START_REF] Kuo | Gamma-H2AX-a novel biomarker for DNA double-strand breaks[END_REF]) in human colonic Caco-2 cells was performed showing a slight but not significant increase of DNA breaks induced by SGG as compared to SGM [START_REF] Pasquereau-Kotula | The oncogenic role of Streptococcus gallolyticus subsp. gallolyticus is linked to activation of multiple cancer-related signaling pathways[END_REF]. As positive control, we used the Escherichia coli expressing the genotoxic toxin colibactin. Of note, Taddese et al. also evaluated the DNA damaging effect of SGG UCN34 using the DNA comet assay and showed that SGG alone had no effect while this bacterium increased the DNA damaging effect induced by the mutagen polycyclic aromatic hydrocarbon 3-methylcholanthrene [START_REF] Taddese | Streptococcus gallolyticus Increases Expression and Activity of Aryl Hydrocarbon Receptor-Dependent CYP1 Biotransformation Capacity in Colorectal Epithelial Cells[END_REF]. This result again fits well with the accelerating role of SGG.

Taddese et al [START_REF] Taddese | Streptococcus gallolyticus Increases Expression and Activity of Aryl Hydrocarbon Receptor-Dependent CYP1 Biotransformation Capacity in Colorectal Epithelial Cells[END_REF] also performed a global transcriptome on HT29 cells exposed to SGG UCN34 in acute conditions (4 h and a multiplicity of infection of 20). They found 44 genes differentially regulated (21 genes upregulated and 23 downregulated). The most up-regulated gene was CYP1A1 (3.01-fold change) encoding cytochrome P450 suggesting that SGG can modify the capacity of intestinal epithelial or pre-cancerous cells to de-toxify dietary components. CYPA1 (2.69-fold change) was also found up-regulated in our experimental set up (S2 Table ). No other gene was found in common in our experimental conditions after 24 h of coculture with SGG UCN34. Our approach with a low multiplicity of infection and longer time of co-culture vs 4 h from Taddese et al [START_REF] Taddese | Streptococcus gallolyticus Increases Expression and Activity of Aryl Hydrocarbon Receptor-Dependent CYP1 Biotransformation Capacity in Colorectal Epithelial Cells[END_REF] revealed much more changes (2,090 vs 44 genes) and specific pro-tumoral shift. Thus, longer infection at low-bacterial dose appears physiologically relevant and informative. Longer co-culture conditions (48 h and 72 h) were tested but were toxic to the host colonic cells. It is worth mentioning that this experimental set up was used previously to demonstrate a pro-proliferative effect of SGG TX20005 on HT29 cells through activation of Wnt/β-catenin pathway [START_REF] Kumar | Streptococcus gallolyticus subsp. gallolyticus promotes colorectal tumor development[END_REF]. We therefore carefully checked this signaling pathway in our data but found no evidence for activation of Wnt/β-catenin by SGG UCN34.

A growing number of researchers have shown the contribution of Unfolded Protein Response (UPR) in CRC development [START_REF] Huang | Unfolded protein response in colorectal cancer[END_REF]. Our transcriptomic data shows clear induction of UPR by SGG in colonic epithelial cells (S2 Fig) . Almost all genes were up-regulated (red color). UPR operates as a metabolic shift increasing cancer cell survival and adaptation to cope with major intrinsic and environmental challenges, promoting metastasis and angiogenesis, modulating inflammatory/immune responses [START_REF] Urra | Endoplasmic Reticulum Stress and the Hallmarks of Cancer[END_REF]. The ER stress induced by SGG (S3 Fig) could be a consequence of: (i) bacterial adhesion factors; (ii) bacterial secreted toxins/ effectors; or (iii) nutritional stress (glucose deprivation) [START_REF] Celli | Bacteria, the ER and the Unfolded Protein Response: Friends or Foes?[END_REF][START_REF] Kalimuthu | Glucose deprivation-induced endoplasmic reticulum stress response plays a pivotal role in enhancement of TRAIL cytotoxicity[END_REF]. Group A Streptococcus, an extracellular human pathogen, was shown to induce ER stress to retrieve host nutrients such as asparagine and to increase host cell viability [START_REF] Baruch | Induction of endoplasmic reticulum stress and unfolded protein response constitutes a pathogenic strategy of group A streptococcus[END_REF]. It is worth mentioning that SGG efficiently utilizes glucose and glycolysis metabolites for its own multiplication in HT29 culture spent medium [START_REF] Boleij | Bacterial Responses to a Simulated Colon Tumor Microenvironment[END_REF]. Thus, we cannot completely rule out that it is the glucose consumption by SGG during proliferation in the cell culture medium that induced the strong UPR response detected at 24 h of co-culture. ER stress-mediated activation of the UPR is a double-edge sword in cancer development. During ER stress, cells either survive by inducing adaptation mechanisms or suicide by apoptosis. PERK is the most dominant branch of UPR to accelerate metastasis, as it can promote angiogenesis through increased expression of vascular endothelial growth factor (VEGF). Both PERK (2.82-fold change) and VEGF (2.38-fold change) expression were increased in our transcriptomic data. Of note, ER stress activates the TOR pathway through ATF6 [START_REF] Allen | ER Stress Activates the TOR Pathway through Atf6[END_REF]. We thus hypothesize that activation of ATF6 by SGG (S3 Fig) may lead to TOR pathway activation, a major signaling pathway identified recently by our global proteomics analysis [START_REF] Pasquereau-Kotula | The oncogenic role of Streptococcus gallolyticus subsp. gallolyticus is linked to activation of multiple cancer-related signaling pathways[END_REF].

GSEA analysis suggests also that SGG may trigger up-regulation of TNFα signaling via NFκB. The transcriptional factor NF-κB plays a crucial role in the host response to microbial infection through orchestrating innate and adaptive immune functions [START_REF] Liu | NF-κB signaling in inflammation[END_REF]. Its activity is linked to gastrointestinal cancer initiation and development through induction of chronic inflammation, cellular transformation and proliferation [START_REF] Peng | The NF-κB Signaling Pathway, the Microbiota, and Gastrointestinal Tumorigenesis: Recent Advances[END_REF]. The modulation of NF-κB signaling pathway was shown for several pathogens (e.g. Helicobacter pylori, Fusobacterium nucleatum, Peptostreptococcus anaerobius, E. coli pks+, B. fragilis bft+) which was directly linked to their oncogenic potential [START_REF] Peng | The NF-κB Signaling Pathway, the Microbiota, and Gastrointestinal Tumorigenesis: Recent Advances[END_REF].

In conclusion, our data indicate that SGG, an opportunistic gut pathobiont associated with colorectal cancer, can alter host cell transcription in human colonic cells whereas the nonpathogenic commensal bacterium SGM do not. Comparing normal and tumoral responses, our results suggest that SGG accelerates colon tumor development rather than initiates this process and the strong activation of the UPR response by SGG needs to be further investigated.

  Fig 1A and the number of differentially expressed genes is shown in Fig 1B. Both infected conditions were compared to the control non-treated (NT) cells. The initial inoculum for SGG and SGM was calculated experimentally to have the same number of bacteria at the end of experiment at 24 h post infection (Fig 2A). As shown in Fig 2B and 2C, SGG adhere tightly to normal FHC colonic cells and makes bacterial aggregates (white narrow). A different pattern was observed in HT29 cells with most of the bacteria adhering to the cell-free surface covered with extracellular matrix secreted by the tumoral cells. A few SGG were found adhering and making aggregates partly on cells and partly on the cell culture surface (white narrow) (Fig 2B). The control bacterium SGM adheres well to both cell types (white narrow) (Fig 2B).

  5) in FHC cells with most of them being down-regulated (109 genes) and only 19 being up-regulated (Fig 1B and S2 Table). Interestingly, we identified 2,090 differentially expressed genes (1,025 down-and 1,065 up-regulated) in HT29 cells (Fig 1B and S3 Table). Only 41 genes were found in common in FHC and HT29 (2 up-and 39 down-regulated; Fig 1C and S4 Table

  Principal component analysis (PCA) shows a clear separation of SGG group from SGM and NT and less good separation in between SGM and NT groups in FHC (Fig 1D) and HT29 cells (Fig 1E), confirming the specific SGG-induced gene changes.

SGG

  altered the expression of 128 genes in normal colonic human FHC cells. The heat map shown in Fig 3A displaying the six most up-regulated genes and two down-regulated genes clearly shows the existence of 2 groups: SGG on one hand and SGM and NT on the other

Fig 1 .

 1 Fig 1. Comparison of host transcriptomic responses in normal FHC and tumoral HT29 colonic cells exposed to SGG vs SGM. A. Experimental design of cell-bacteria co-culture used for transcriptomic study (created with BioRender.com). Cells were seeded onto 6-wells plate (FHC: 2 x 105 cells/well and HT29: 4 x 10 5 cells/well) and incubated for 16-20 hours. Cells were infected with bacteria: SGG UCN34 (6.5 x 10 4 CFU/ml) and SGM (6.5 x 10 5 CFU/ml). Trimethoprim (50 μg/ml) was added to the wells after 6 hours of co-culture to prevent bacterial over-growth. The total infection time was 24 h. Total RNA was prepared, processed and sequenced using Illumina technology. This experiment was performed in triplicate (n = 3). B. Table recapitulating the transcriptional changes in FHC and HT29 induced by SGM vs NT and SGG UCN34 vs SGM conditions. Criteria for significant gene changes were as follows: adjusted p < 0.05 and log2 fold change (FC) > 0.5 or < -0.5). C. Venn diagram showing that 41 genes regulated upon SGG UCN34 infection were in common between FHC and HT29 cells. D. PCA of transcriptome samples in FHC cells: SGG (n = 3); SGM (n = 3) and NT (n = 3). E. PCA of transcriptome samples in HT29 cells: SGG (n = 3); SGM (n = 3) and NT (n = 3). D and E. Each PCA is based on the variance-stabilized transformed count matrix that has been adjusted for the replicate effect using the remove BatchEffect function or the limma R package (version 3.52.4).

  ). Both techniques gave similar fold changes between SGG and SGM (R = 0.97; Fig 3C). These results were analyzed using the Ingenuity Pathway Analysis (IPA, Qiagen) showing that most of the differentially expressed genes were involved in cancer disease (118 out of 128; Fig 3D). Gene Set Enrichment Analysis (GSEA) with Camera showed 14 gene sets from the HALLMARK collection significantly changed: (i) oxidative phosphorylation (OXPHOS); (ii) adipogenesis; (iii) reactive oxygen species (ROS); (iv) cholesterol homeostasis; (v) interferon alpha (IFNα) response; (vi) myc targets v1; (vii) protein secretion; (viii) fatty acid (FA) metabolism; (ix) epithelial to mesenchymal transition (EMT); (x) interferon gamma (IFNγ)

Fig 2 .

 2 Fig 2. Cellular model of SGG UCN34 and SGM 24 h co-culture with human colonic normal FHC and cancerous HT29 cells. A. Number of planktonic and adherent bacteria numerated on 100% confluent cells using the experimental conditions set up for transcriptomics. Confluent cells seeded in 6-well plate were inoculated with 6x10 5 of SGM and 6x10 4 of SGG. After 6 h of co-culture at 37˚C in the incubator, trimethoprim (50μg/ml) was added into cell culture media to avoid bacterial growth and cell toxicity and co-culture was continued for 18 h. Planktonic and adherent bacteria were numerated on THY agar plates. Mann-Whitney test shows that no significant difference (ns) between SGG and SGM (p = 0.33; p = 0.66). B. 3D reconstruction of z-stack obtained by confocal microscopy. DAPI (blue), Phalloidin (red) and SGG UCN34 or SGM (green). C. Colored confocal pictures show DAPI nuclei labeling (blue), Phalloidin (red) and SGG UCN34 or SGM (green). Scale bar: 50 μm. https://doi.org/10.1371/journal.pone.0294868.g002

  Fig 4A displays the 10 most up-regulated genes and one down-regulated gene. Of note, the fold-change level (�10-fold) in up-and down-regulated genes was

Fig 3 .

 3 Fig 3. Transcriptional responses of human normal FHC cells upon SGG infection. A. Heat map of transcriptomic data displaying the top six up-regulated and two down-regulated genes. The heatmap is based on the variance-stabilized transformed (VST) count matrix. Rows and columns have been re-ordered thanks to a hierarchical clustering using the correlation and Euclidean distances respectively and the Ward aggregation criterion. Color scale ranges from -2 to +2 as the rows of the matrix have been centered. B. Relative quantification (2 -ΔΔCt ) of mRNA levels at 24 h of infection with SGG, SGM or non-treated (NT). C. Correlation of fold changes between transcriptome and quantitative real time PCR for the 8 genes shown in B. D. Top Disease and Bio Functions using Ingenuity Pathway Analysis (IPA) using genes differentially expressed between SGG UCN34 and SGM. Molecules indicate the number of genes associated with indicated diseases and disorders. A righttailed Fisher's Exact Test was used to calculate a p-value determining the probability that each biological function and/or disease assigned to that data set is due to chance alone. E. Network representation of the 14 significantly enriched HALLMARK gene sets upon SGG infection on FHC cells. Each node (circle) represents a gene set. Node size is proportional to the number of genes present in the dataset and belonging to the gene set. Node colors reflect the average expression directionality (based on the average of the log fold expression for each gene belonging to the gene set) (red = over expressed; blue = down regulated; grey = no statistically significant difference in expression). The intensity of the color is proportional to the strength of the average expression. Each edge connecting two nodes means that two gene sets share the same genes. The edge width is proportional to the number of genes shared among the two gene sets. Edges are shown only if at least two genes are shared among the two gene sets (30 edges).

Fig 4 .

 4 Fig 4. Transcriptional respo0nses of human tumoral HT29 cells upon SGG infection. A. Heat map of transcriptomic data displaying the top ten up-regulated and one down-regulated genes. The heatmap is based on the variance-stabilized transformed (VST) count matrix. Rows and columns have been re-ordered thanks to a hierarchical clustering using the correlation and Euclidean distances respectively and the Ward aggregation criterion. Color scale ranges from -2 to +2 as the rows of the matrix have been centered. B. Relative quantification (2 -ΔΔCt ) of mRNA levels at 24 h of infection with SGG, SGM and non-treated (NT). C. Correlation of fold changes between transcriptome and quantitative real time PCR for the 11 genes shown in B. D. Top Disease and Bio Functions using Ingenuity Pathway Analysis (IPA) using genes differentially expressed between SGG UCN34 and SGM. Molecules indicate the number of genes associated with indicated diseases and disorders. A right-tailed Fisher's Exact Test was used to calculate a p-value determining the probability that each biological function and/or disease assigned to that data set is due to chance alone. E. Network of representation of the 9 significantly enriched HALLMARK gene sets upon SGG infection on HT29 cells. Each node (circle) represents a gene set. Node size is proportional to the number of genes present in the dataset and belonging to the gene set. Node colors reflect the average expression directionality (based on the average of the log fold expression for each gene belonging to the gene set) (red = over expressed; blue = down regulated; grey = no statistically significant difference in expression). The intensity of the color is proportional to the strength of the average expression. Each edge connecting two nodes means that two gene sets share the same genes. The edge width is proportional to the number of genes shared among the two gene sets. Edges are shown only if at least two genes are shared among the two gene sets (11 edges).

  Fig 4D). In HT29 cells, 9 HALLMARK gene sets were significantly enriched, four of them were predicted to be activated: (i) unfolded protein response (UPR); (ii) protein secretion; (iii) TNFα signaling via NF-kB; (iv) Heme metabolism and five gene sets were predicted to be down-regulated: (v) E2F targets (t); (vi) G2M checkpoint; (vii) KRAS signaling; (viii) myc targets (t) v2 and (ix) epithelial to mesenchymal transition (EMT) (Fig 4E and S8 Table). KEGG Pathway Analysis reveals a clear up-regulation of "Protein processing in endoplasmic reticulum (ER)" (48/169 total (41 up / 7 down) S5 Table). IPA tool revealed that the top canonical pathways were UPR and ER stress (S1 Fig) but no directionality (activation or down-regulation) was attributed. The visualization of UPR in presented in S2 Fig and ER stress in S3 Fig. Taking together, transcriptomic data in HT29 cells shows massive pro-tumoral shift with strong induction of ER stress and UPR activation by SGG.

  5

PLOS ONE | https://doi.org/10.1371/journal.pone.0294868 November 30, 2023

Acknowledgments

We thank Jean Yves-Coppe ´e for the design of the transcriptome experiment, Alix Decobert for help with q RT-PCR and Tarek Msadek for critical reading of the manuscript.

This work was supported by the Institut National contre le Cancer (INCA, grant PLBIO16-025) and from the French Government's Investissement d'Avenir program, Laboratoire d'Excellence Integrative Biology of Emerging Infectious Diseases (grant no. ANR-10-LABX-62-IBEID). E.P-K received a 2-year Roux-Cantarini post-doctoral fellowship. The funders had no role in study design, data collection and analysis, decision to publish, or preparation of the manuscript.

All data generated or analyzed during this study are included in this published article and its supplementary information files. In addition, the raw datasets of the transcriptomic study were deposited on the GEO portal under the accession number GSE232211.

Supporting information

S1 Fig. Top 5 canonical pathways altered by SGG UCN34 in HT29 cells visualized using IPA software. The data set used in this analysis was genes differentially expressed between SGG UCN34 and SGM detected in HT29 after 24 h of infection. Canonical pathways that were most significant to the data set were identified from the QIAGEN Ingenuity Pathway Analysis library of canonical pathways. Canonical pathways with p-values < 0.05 (Fischer's exact test) were statistically significant. The activation Z-score was calculated to predict activation or inhibition of transcriptional regulators based on published findings accessible through the Ingenuity knowledge base. Regulators with Z-score greater than 2 (positive Z-score) or less than -2 (negative Z-score) were significantly activated (orange) or inhibited (blue). Regulators with Z-score of 0 are represented in white and those for which the Z-score couldn't be calculated are shown in grey.