Yang Wang
email: yangw@nwpu.edu.cn

Jin-Kao Hao
email: jin-kao.hao@univ-angers.fr

Fred Glover
email: glover@opttek.com

Zhipeng Lü
email: zhipeng.lui@gmail.com

Qinghua Wu
email: qinghuawu1005@gmail.com

Solving the maximum vertex weight clique problem via binary quadratic programming

Keywords: Maximum Vertex Weight Clique, Binary Quadratic Programming, Probabilistic Tabu Search

In recent years, the general binary quadratic programming (BQP) model has been widely applied to solve a number of combinatorial optimization problems. In this paper, we recast the maximum vertex weight clique problem (MVWCP) into this model which is then solved by a Probabilistic Tabu Search algorithm designed for the BQP. Experimental results on 80 challenging DIMACS-W and 40 BHOSLIB-W benchmark instances demonstrate that this general approach is viable for solving the MVWCP problem.

Introduction

Given an undirected graph G = (V, E) with vertex set V and edge set E, a clique is a set of vertices C ⊆ V such that every pair of distinct vertices of C is connected with an edge in G, i.e., the subgraph generated by C is complete. The maximum clique problem (MCP) is to find a clique of maximum cardinality. An important generalization of the MCP, known as the maximum vertex weight clique problem (MVWCP), arises when each vertex i in G is associated with a positive weight w i . The MVWCP aims to find a clique of G with the maximum ∑ i∈C w i . It is clear that the MCP is a special case of the MVWCP with w i = 1 for each vertex.

The MCP is computationally difficult given that its associated decision problem is known to be NP-complete [START_REF] Garey | Computers and intractability: a guide to the theory of NP-Completeness[END_REF]. As a generalization of the MCP, the MVWCP has at least as the same computational complexity as the MCP.

Like the MCP, the MVWCP has important applications in many domains like computer vision, pattern recognition and robotics [START_REF] Ballard | Computer Vision[END_REF].

To solve these clique problems, a variety of solution algorithms have been reported in the literature. Examples of exact methods based on the general Branch-and-Bound (B&B) or Branch-and-Cut methods for the MCP (or its equivalent maximum stable set problem) can be found in [START_REF] Carraghan | An exact algorithm for the maximum clique problem[END_REF][START_REF] Konc | An improved branch and bound algorithm for the maximum clique problem[END_REF][START_REF] Li | An efficient branch-and-bound algorithm based on MAXSAT for the maximum clique problem[END_REF][START_REF] Macreesh | Multi-threading a state-of-the-art maximum clique algorithm[END_REF][START_REF] Östergård | A fast algorithm for the maximum clique problem[END_REF][START_REF] Rebennack | A branch and cut solver for the maximum stable set problem[END_REF][START_REF] Rebennack | A tutorial on branch and cut algorithms for the maximum stable set problem[END_REF][START_REF] Segundo | An exact bitparallel algorithm for the maximum clique problem[END_REF][START_REF] Tomita | An efficient branch-and-bound algorithm for finding a maximum clique with computational experiments[END_REF]. For the MVWCP, some exact algorithms are tightly related to the corresponding algorithms designed for the MCP [START_REF] Babel | A fast algorithm for the maximum weight clique problem[END_REF][START_REF] Östergård | A new algorithm for the maximum weight clique problem[END_REF] while other B&B based methods can be found in [START_REF] Warren | Combinatorial branch-and-bound for the maximum weight independent set problem[END_REF]. On the other hand, a number of heuristic algorithm have also been proposed to find sub-optimal solutions to the MVWCP, including an augmentation algorithm [START_REF] Manninno | An augmentation algorithm for the maximum weighted stable set problem[END_REF], a distributed computational network algorithm [START_REF] Bomze | Approximating the maximum weight clique using replicator dynamics[END_REF], a trust region technique algorithm [START_REF] Busygin | A new trust region technique for the maximum weight clique problem[END_REF], a phased local search algorithm [START_REF] Pullan | Approximating the maximum vertex/edge weighted clique using local search[END_REF], a multi-neighborhood tabu search algorithm [START_REF] Wu | Multi-neighborhood tabu search for the maximum weight clique problem[END_REF], and a breakout local search algorithm [START_REF] Benlic | Breakout local search for maximum clique problems[END_REF]. For an updated recent review of algorithms for these clique problems, the reader is referred to [START_REF] Wu | A review on algorithms for maximum clique problems[END_REF].

During the past decade, binary quadratic programming (BQP) has emerged as a unified model for numerous combinatorial optimization problems, such as max-cut [START_REF] Kochenberger | Solving large scale max cut problems via tabu search[END_REF][START_REF] Wang | Probabilistic GRASP-Tabu Search Algorithms for the UBQP problem[END_REF], set partitioning [START_REF] Lewis | A new modeling and solution approach for the set-partitioning problem[END_REF], set packing [START_REF] Alidaee | A new approach for modeling and solving set packing problem[END_REF], generalized independent set [START_REF] Kochenberger | An effective modeling and solution approach for the generalized independent set problem[END_REF] and maximum edge weight clique [START_REF] Alidaee | Solving the maximum edge weight clique problem via unconstrained quadratic programming[END_REF]. A review of the additional applications and the reformulation procedures can be found in [START_REF] Kochenberger | A unified modeling and solution framework for combinatorial optimization problems[END_REF][START_REF] Kochenberger | The Unconstrained binary quadratic programming problem: a survey[END_REF]. Using the BQP model to solve the targeted problem has the advantage of directly applying an algorithm designed for the BQP rather than resorting to a specialized solution method. Moreover, this approach proves to be competitive for several problems compared to specifically designed algorithms [START_REF] Alidaee | Solving the maximum edge weight clique problem via unconstrained quadratic programming[END_REF][START_REF] Kochenberger | Solving large scale max cut problems via tabu search[END_REF][START_REF] Lewis | A new modeling and solution approach for the set-partitioning problem[END_REF][START_REF] Wang | Probabilistic GRASP-Tabu Search Algorithms for the UBQP problem[END_REF].

There exists several studies on the application of the BQP model to solve the classic MCP [START_REF] Kochenberger | The Unconstrained binary quadratic programming problem: a survey[END_REF][START_REF] Pajouh | On characterization of maximal independent sets via quadratic optimization[END_REF][START_REF] Pardalos | A branch and bound algorithm for the maximum clique problem[END_REF]. However, for the more general MVWCP, no computational study has been reported in the literature using the BQP model. In this paper, we investigate for the first time the application of the BQP model to the MVWCP and solve the resulting BQP problem with the Probabilistic Tabu Search algorithm (BQP-PTS) designed for the BQP [START_REF] Wang | Probabilistic GRASP-Tabu Search Algorithms for the UBQP problem[END_REF]. Experimental results on 80 challenging DIMACS-W and 40 BHOSLIB-W instances demonstrate that this general BQP approach with the PTS algorithm performs quite well in terms of solution quality at the price of more computing time for some benchmark instances.

The rest of this paper is organized as follows. Section 2 illustrates how to transform the MVWCP into the form of the BQP. Section 3 presents our Probabilistic Tabu Search algorithm to solve the transformed BQP model.

Section 4 report the computational results and comparisons with other stateof-the-art algorithms in the literature. The paper concludes with Section 5.

2 Transformation to the BQP model

Linear model for the MVWCP

Given an undirected graph G = (V, E) with vertex set V and edge set E, each vertex associated with a positive weight w i , the binary linear programming model for the MVWCP can be formulated as follows [START_REF] Sengor | An analysis of maximum clique formulations and saturated linear dynamical network[END_REF]:

M ax f (x) = n ∑ i=1 w i x i subject to: x i + x j ≤ 1, ∀{v i , v j } ∈ E x i ∈ {0, 1}, i ∈ {1, . . . , n} (1)
where n = |V |, x i is the binary variable associated to vertex v i , E denotes the edge set of the complementary graph G.

Notice that if w i = 1 (i ∈ {1, . . . , n}), Eq. ( 1) turns into the linear model of the classic maximum clique problem.

Nonlinear BQP alternative

The linear model of the MVWCP can be recast into the form of the BQP by utilizing the quadratic penalty function g(x) = P x i x j (x i is binary, i ∈ {1, . . . , n}) to replace the inequality constraint of the MVWCP where P is a negative penalty scalar. Since the inequality constraint x i +x j ≤ 1 implies that x i and x j cannot receive value 1 at the same time, the infeasibility penalty function g(x) will equal to 0 if the inequality constraint is satisfied; otherwise g(x) will take a large penalty value 2P . To construct the nonlinear BQP model, each inequality constraint is replaced by the penalty function g(x) which is added to the linear objective of Eq. ( 1) and the nonlinear BQP model can be formulated as follows:

M ax xQx = n ∑ i=1 w i x i + n ∑ i=1 n ∑ j=1,j̸ =i w ij x i x j x i ∈ {0, 1}, i ∈ {1, . . . , n} (2)
where w ij = P if {v i , v j } ∈ E and 0 otherwise. This formulation is one of many nonlinear reformulations of the MVWCP and has been studied in previous work like [START_REF] Horst | Introduction to Global Optimization, Nonconvex optimization and its applications[END_REF]. The quadratic function will have the same objective value as the linear form subject to all penalty items equaling to 0, indicating that all constraints are satisfied. According to Eq.

(2), any violated constraint, i.e., for each {v i , v j } ∈ E, in a solution will add a penalty value 2P to the objective value. Thus, simply setting |P | > 0.5 ∑ i i=1 w i , where each linear objective function coefficient w i > 0, will enable an infeasible solution to get a large penalty value. Actually it suffices to set a smaller |P | > 0.5w m (w m is the maximal value among all w i , i ∈ {1, . . . , n}).

Under this setting, a good decision for improving an infeasible solution would be to remove vertices associated with violated constraints, making constraints gradually reduced and finally an infeasible solution become feasible. Consider that the quadratic penalty function should be negative under the case of a maximal objective, we select P = -1000 for the MVWCP benchmark instances tested in our experiments. With this choice, for any optimal solution

x of problem (2), g(x) = 0 holds. In other words, the subgraph constructed by the variables with the assignment of 1 in the optimized solution x forms a clique. An illustrative example of this transformation is given in Appendix.

Since Eq. ( 2) corresponds to the well-known BQP model, any algorithm designed for solving the BQP can be readily used to solve the MVWCP. In our case, we apply a probabilistic tabu search algorithm described in the next section.

Probabilistic tabu search algorithm

Metaheuristics are often used to solve hard optimization problems, such as quasi-human based heuristics [START_REF] He | A quasi-human algorithm for solving the three-dimensional rectangular packing problem[END_REF][START_REF] Wu | An effective quasi-human based heuristic for solving the rectangle packing problem[END_REF], variable neighborhood search [START_REF] Hansen | Variable neighborhood search: Principles and applications[END_REF], ant colony algorithm [START_REF] Dorigo | Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem[END_REF], probabilistic tabu search [START_REF] Glover | Tabu Search -Part I[END_REF][START_REF] Xu | Probabilistic tabu search for telecommunications network design[END_REF], etc. In this paper, we solve the MVWCP directly in the nonlinear BQP form as expressed in Eq.

(2) by adapting our previous Probabilistic Tabu Search algorithm (BQP-PTS) designed for the BQP [START_REF] Wang | Probabilistic GRASP-Tabu Search Algorithms for the UBQP problem[END_REF]. BQP-PTS is a multistart procedure, consisting of a greedy probabilistic solution construction phase and a sequel tabu search phase to optimize the objective function. These two phases proceed iteratively until a stopping condition is satisfied. Below we summarize the main ingredients of the BQP-PTS algorithm.

Greedy probabilistic construction of initial solutions

We construct a new solution for the general BQP model according to a greedy probabilistic construction heuristic. The construction procedure consists of two phases: one is to adaptively and iteratively select some variables to receive the value 1; the other is to assign the value 0 to the remaining variables. The pseudo-code of this construction procedure is shown in Algorithm 1.

First, the partial solution is set to be empty and all the variables of the problem instance are put into the set of the remaining variables V S. At each Algorithm 1 Outline of the greedy probabilistic construction heuristic Enlarge the partial solution with px = px ∪ {xs} 6:

Update V S with V S = V S \ {xs} 7: until CL = ∅ 8: Set x i = 0 for ∀x i ∈ V S iteration we construct a candidate list CL such that CL is a subset of V S and each variable in CL has a positive objective function increment OF I. Then we choose one variable from CL with a probability of 1/|CL| and assign it with the value 1. This variable with its assignment value is added into the partial solution and is removed from V S. This process continues until CL becomes empty. The last step is to assign the remaining variables in V S with value 0.

To quickly compute the objective function increment OF I, we maintain a vector IV , with each entry IV i recording the objective function increment when putting a variable x i with the value 1 into the partial solution. Initially, IV is computed as w i since the initial partial solution is empty. Once a variable x s joins into the partial solution, then each such entry IV i with its corresponding variable belonging to the set of the remaining variables V S is updated as

IV i = IV i + 2w si . Because of this additional vector, the complexity of this construction procedure is bounded by O(n) 2 .
Although this strategy is much simpler than that used in the original algorithm [START_REF] Wang | Probabilistic GRASP-Tabu Search Algorithms for the UBQP problem[END_REF], it was experimentally demonstrated to be effective. Notice that seen from the side of the MVWCP, CL is the set of vertices which form a clique with those in the partial solution. This strategy of constructing an initial solution is consistent with many specific maximum clique algorithms in the literature.

Tabu search

For each initial solution generated by the greedy probabilistic construction, we apply an extended version of the tabu search algorithm described in [START_REF] Wang | Probabilistic GRASP-Tabu Search Algorithms for the UBQP problem[END_REF] to further improve its quality. The tabu search algorithm in [START_REF] Wang | Probabilistic GRASP-Tabu Search Algorithms for the UBQP problem[END_REF] uses a simple oneflip move (flipping the value of a single variable x i to its complementary value 1 -x i ) to conduct the neighborhood search. Here we not only exploit the oneflip move but also incorporate a two-flip move (flipping the values of a pair of variables (x i , x j ) to their corresponding complementary values (1 -x i , 1 -x j )) [START_REF] Glover | Fast 2-flip Move Evaluations for Binary Unconstrained Quadratic Optimization Problems[END_REF]. The above two types of moves constitute the neighborhood structures N1 and N2.

One drawback of an N2 move is the amount of time it consumes. Considerable effort is required to evaluate all the two-flip moves because the neigh-borhood structure N2 generates n(n -1)/2 solutions at each iteration. To overcome this obstacle, we employ an instance of the Successive Filter candidate list strategy of [START_REF] Glover | Tabu Search[END_REF] by restricting our attention to moves in N2 that can be obtained as follows. The first step is to examine all the one-flip moves of the current solution x, and if any of these moves is improving we go ahead and select it. But if no one-flip move is improving, we limit attention to oneflip moves that produce an objective function value no worse than f (x) + 2P , where f (x) is the objective function value of x. (Recall that we are maximizing and the penalty P is negative. This implies that the candidate one-flip moves can violate at most a single additional constraint beyond those violated by x, since a single constraint is penalized as P x ij +P x ji and hence incurs a penalty of 2P .) Finally, only the one-flip moves that pass this filtering criterion are allowed to serve as the source of potential two-flip moves.

Tabu search typically introduces a tabu list to assure that solutions visited within a certain number of iterations, called the tabu tenure, will not be revisited [START_REF] Glover | Tabu Search[END_REF]. In the present study, each time a variable x i is flipped, this variable enters into the tabu list and cannot be flipped for the next T abuT enure iterations. For the neighborhood structure N1, our tabu search algorithm then restricts consideration to variables not forbidden by the tabu list. For the neighborhood structure N2, we consider a move to be non-tabu only if both variables associated with this move are not in the tabu list and only such moves are considered during the search process. According to preliminary experiments, we set T abuT enure(i) = 7 + rand(5) where rand(5) produces a random integer from 1 to 5.

For each iteration in our tabu search procedure, a non-tabu move is chosen according to the following rules: (1) if the best move from N1 leads to a solution better than the best solution obtained in this round of tabu search, we select the best move from N1, thus bypassing consideration of N2; (2) if no such move in N1 exists, we select the best move from the combined pool of N1 and N2. A simple aspiration criterion is applied that permits a move to be selected in spite of being tabu if it leads to a solution better than the current best solution. The tabu search procedure stops when the best solution cannot be improved within a given number µ of moves and we call this number the improvement cutoff. According to a preliminary experiment on parameter tuning, µ is set to be 5000 for all the instances except for san instances for which µ = 10. In fact, it was observed that for some san instances, it is more effective to restart the search than to make long tabu iterations.

In order to quickly calculate the gains of performing a move, we maintain a vector ∆ which is initialized as follows:

∆ i = { w i + ∑ n j=1,j̸ =i 2w ij x j (x i = 0) w i - ∑ n j=1,j̸ =i 2w ij x j (x i = 1) (3)
Then if a move corresponding to a one-flip move x i is performed, then we update the set of variables affected by this move using the following scheme [START_REF] Glover | Efficient evaluation for solving 0-1 unconstrained quadratic optimization problems[END_REF]:

∆ k =      -∆ k (k = i) ∆ k -2w ik (k ̸ = i, x k = x i ) ∆ k + 2w ik (k ̸ = i, x k = 1 -x i ) (4)
If a move corresponding to a two-flip move (x i , x j ) from the neighborhood N2 is performed, then we update the set of variables affected by this move using the following scheme [START_REF] Glover | Fast 2-flip Move Evaluations for Binary Unconstrained Quadratic Optimization Problems[END_REF]:

∆ k =      -∆ k -2w ij (k = i or k = j) ∆ k -2w ik + 2w jk (k ̸ = i, k ̸ = j, x k = x i , x k = 1 -x j ) ∆ k + 2w ik -2w jk (k ̸ = i, k ̸ = j, x k = x j , x k = 1 -x i ) (5)
Given the fact that the BQP-PTS algorithm is designed for the general BQP model (instead of the MVWCP model studied in the paper), the above presentation of BQP-PTS does not refer to the MVWCP. However, it is possible to give an interpretation of some operators used by BQP-PTS related to the MVWCP. For instance, the one-flip move for the BQP model can be considered as moving a single vertex in or out the current solution (clique).

On the other hand, such an interpretation will change depending on the target problem under consideration.

4 Experimental results

Benchmark instances

We used two sets of benchmark instances for our computational assessments.

The first set concerns 80 DIMACS-W instances proposed in [START_REF] Pullan | Approximating the maximum vertex/edge weighted clique using local search[END_REF], which were adapted from the well-known DIMACS instances1 for benchmark purpose to evaluate maximum clique algorithms. The second set is composed of 40 BHOSLIB-W instances2 , which were adapted from the BHOSLIB benchmarks with hidden optimum solutions [START_REF] Benlic | Breakout local search for maximum clique problems[END_REF]. The weighting method is to allocate weights to vertices according to the following scheme: for each vertex i, w i is set equal to i mod 200 + 1, which enables us to exactly replicate the instances without difficulty.

The DIMACS benchmarks comprise the following families of graphs: Random graphs (Cx.y and DSJCx.y of size x and density 0.y), Steiner triple graphs (MANNx with up to 3321 nodes and 5506380 edges), Brockington graphs with hidden optimal cliques (brockx 1, brockx 2, brockx 3, brockx 4 of size x), Gen random graphs with a unique known optimal solution (genx p0.9 z of size x), Hamming and Johnson graphs stemming from the coding theory, Keller graphs based on Keller's conjecture on tilings using hypercubes (with up to Algorithm 2 Outline of the tabu search algorithm 1: Input: a given solution x with its solution value f (x) 2: Output: the local optimal solution x * with its solution value f (x * ) 3: T L: an n-dimensional vector for maintaining the tabu list ∆: an n-dimensional vector for recording the move gain of performing each one-flip move 4: Initialize ∆ according to Eq. ( 3), T L i = 0 for all i = 1 to n 5: Set N onImp = 0, Iter = 0 6: while N onImp < µ (µ is called improvement cutoff) do 7:

Identify the best non-tabu one-flip move or the best one-flip move that is tabu but satisfies the aspiration rule from the neighborhood N1, say this move corresponds to flipping x i 8:

if f (x) + ∆ i > f (x * ) then 9:

x i = 1 -x i , f (x) = f (x) + ∆ i 10:
Update ∆ according to Eq. ( 4) 11:

Update Tabu List by setting T L i = Iter + T abuT enure i 12:

else 13:

Identify the best non-tabu move or the best tabu move that satisfies the aspiration rule from the neighborhood N1 and N2 14:

if this move corresponds to flipping x i then 15:

x i = 1 -x i ,f (x) = f (x) + ∆ i 16:
Update ∆ according to Eq. ( 4) 17:

Update Tabu List by setting T L i = Iter + T abuT enure i 18:

end if 19:

if this move corresponds to flipping x i and x j then 20:

x i = 1 -x i , x j = 1 -x j , f (x) = f (x) + ∆ i + ∆ j + 2w ij 21:
Update ∆ according to Eq. ( 5) 22:

Update Tabu List by setting T L i = Iter + T abuT enure i , T L j = Iter + T abuT enure j 23:

end if 24:

end if 25:

if f (x) > f (x * ) then 26:

x * = x, f (x * ) = f (x), N onImp = 0 27: else 28:

N onImp = N onImp + 1 29:

end if 30:

Iter = Iter + 1 31: end while 3361 verices and 4,619,898 edges), P-hat graphs (p hatx-z of size x), San random graphs (sanx y z of size x and density 0.y) and Sanr random graphs (sanrx-z with size x and density z). The BHOSLIB-W benchmarks have sizes ranging from 450 vertices and 17,794 edges up to 1534 vertices and 127,011 edges.

Experimental protocol

Our Probabilistic Tabu Search algorithm for the BQP model was programmed in C++ and compiled using GNU GCC on a PC with Pentium 2.83GHz CPU and 2GB RAM. We used the CPU clocks as the stop condition of our algorithm. Given the stochastic nature of BQP-PTS, each problem instance was independently solved 100 times.

For the DIMACS-W benchmarks, the time limit for a single run was set 1 as follows: 1 minute for instances of hamming, gen, c-fat, johnson, p hat, 2 sanr, keller except keller6 and mann a9; 5 minutes for instances of brock, 3 dsjc, san and C families except C2000.5, C2000.9, C4000.5; 60 minutes for 4 C2000.5, C2000.9 and keller6; 600 minutes for C4000.5, mann a27, mann a45, 5 mann a81. For the BHOSLIB benchmarks, the time limit was set as 60 min-6 utes.

Experimental results

8

In this section, we verify the effectiveness of our BQP approach with the 9 BQP-PTS algorithm on the 80 DIMACS-W instances and 40 BHOSLIB-W 10 instances. Furthermore, we compare this general BQP approach with three re-11 cent and powerful heuristics which are specially dedicated to the MVWCP: the 12 PLS W algorithm [START_REF] Pullan | Approximating the maximum vertex/edge weighted clique using local search[END_REF], the multi-neighborhood tabu search algorithm MS/TS 13 [START_REF] Wu | Multi-neighborhood tabu search for the maximum weight clique problem[END_REF] and the breakout local search BLS [START_REF] Benlic | Breakout local search for maximum clique problems[END_REF]. The solution values inferior to the best known ones are marked in bold. BQP-PTS, as a general solver, does not benefit from such advantages.

23

Table 2 shows the results of the BQP-PTS approach compared to those 24 of the MN/TS and BLS algorithms for the BHOSLIB-W benchmarks (the 25 PLS W algorithm does not report results for the BHOSLIB-W benchmarks). Finally, we also evaluated our BQP-PTS approach for the (unweighted) maximum clique instances. Without bothering to show tabulated results, we observed that BQP-PTS was able to attain the best known results for 77 of 80 DIMACS instances except for C2000.9 (79 vs 80), MANNa 45 (344 vs 345), MANNa 81 (1098 vs 1100) and for all the 40 BHOSLIB instances. Such a performance can be considered as quite good even compared to the best performing MCP algorithms presented in the recent review [START_REF] Wu | A review on algorithms for maximum clique problems[END_REF]. However, our BQP-PTS algorithm requires more computing time than specific MCP algorithms, in particular when it is applied to solve some very difficult instances.

Conclusion

We recast the maximum vertex weight clique problem (MVWCP) into the binary quadratic programming (BQP) model, which was solved by a Probabilistic Tabu Search algorithm. Experiments on two sets of challenging DIMACS-W and BHOSLIB-W benchmarks indicate that this general BQP approach is viable for solving the MVWCP problem. In particular, without incorporation of domain specific knowledge, this approach was able to attain the best known results for 76 out of 80 DIMACS-W instances and for all the 40 BHOSLIB-W instances within reasonable computing times. For the conventional maximum clique problem, the BQP approach achieved similar performances by attaining the best known results for 77 out of 80 DIMACS instances and for all the 40 BHOSLIB instances. However, our BQP approach is more time consuming than specific algorithms especially for some very difficult instances and some parameters need to be tuned to achieving its best performance. These computational outcomes demonstrate that the general BQP model constitutes an interesting alternative to solve these clique problems without calling for specific heuristics.

For future consideration, it would be interesting to explore using the Probabilistic Tabu Search design not only within the restart part of our method, but also periodically within the improving part of our method which currently consists of a relatively simple form of tabu search. Another interesting research line is to investigate automatic parameter tuning techniques to obtain a general and parameter free BQP solver.

M ax f (x) = 2x 1 + 3x 2 + 4x 3 + 5x 4 + 2x 5 + 3x 6 s.t. x 1 + x 3 ≤ 1;

x 1 + x 4 ≤ 1; x 1 + x 6 ≤ 1;

x 2 + x 4 ≤ 1; x 2 + x 6 ≤ 1;

x 3 + x 5 ≤ 1;

x 3 + x 6 ≤ 1;

x 5 + x 6 ≤ 1.

(6)

Choosing the scalar penalty P = -15, we obtain the following BQP model:

M ax f (x) = 2x 1 + 3x 2 + 4x 3 + 5x 4 + 2x 5 + 3x 6 -30x 1 x 3 -30x 1 x 4 -30x 1 x 6 -30x 2 x 4 -30x 2 x 6 -30x 3 x 5 -30x 3 x 6 -30x 5 x 6 [START_REF] Busygin | A new trust region technique for the maximum weight clique problem[END_REF] which can be re-written as:

( x 1 x 2 x 3 x 4 x 5 x 6 ) ×         2
        ×         x 1 x 2 x 3 x 4 x 5 x 6         (8)
Solving this BQP problem yields x 3 = x 4 = 1 (all other variables equal zero) and the optimal objective function value is 9.

7

 7

6

 6

  15 -15 0 -15 3

1 :

 1 Let px denote the partial solution and V S denote variables not in the partial solution, initialize px = ∅, V S = {x 1 , x 2 , . . . , xn}

	2: repeat
	3:	Construct a candidate list CL ⊂ V S where each variable x j in CL has a positive objective function increment OF I, calculated as OF I j = w j + ∑ x i ∈px w ij
	4:	Choose randomly one variable xs from CL with a probability of 1/|CL| and set xs = 1
	5:

14 Table 1 :

 141 Computational comparisons of the BQP-PTS approach with the PLS, MS/TS and BLS algorithms on the set of DIMACS-W instances Table1presents the experimental results for the DIMACS-W benchmarks,

	(Continued. . . )
	Instance	Best	BQP-PTS Succ.	Time	Best	PLSW [31] Succ.	Time	Best	MS/TS [39] Succ. Time	Best	BLS [5] Succ.	Time
	johnson16-2-4 johnson32-2-4 p hat300-1 p hat300-2 p hat300-3 p hat500-1 p hat500-2 p hat500-3 p hat700-1 p hat700-2 p hat700-3 p hat1000-1 p hat1000-2 p hat1000-3 p hat1500-1 p hat1500-2 p hat1500-3 san200 0.7 1 san200 0.7 2 san200 0.9 1 san200 0.9 2 san200 0.9 3 san400 0.5 1 san400 0.7 1 san400 0.7 2 san400 0.7 3 san400 0.9 1 san1000 sanr200-0.7 sanr200-0.9 sanr400-0.5 sanr400-0.7	548 2033 1057 2487 3774 1231 3920 5375 1441 5290 7565 1514 5777 8111 1619 7360 10321 3370 2422 6825 6082 4748 1455 3941 3110 2771 9776 1716 2325 5126 1835 2992	100 40 100 100 100 100 100 100 100 100 100 100 100 100 95 100 9 100 100 100 100 100 100 100 100 99 100 100 100 100 100 100	< ϵ 26.71 0.03 0.02 0.04 0.17 < ϵ 0.36 0.30 0.03 2.07 3.78 0.09 0.65 17.25 3.61 34.14 0.06 0.41 0.02 0.02 0.64 5.74 2.64 6.81 42.54 0.31 40.93 0.08 < ϵ 1.41 0.47	548 2033 1057 2487 3774 1231 3925 5361 1441 5290 7565 1514 5777 7986 1619 7328 10014 3370 2422 6825 6082 4748 1455 3941 3110 2771 9776 1716 2325 5126 1835 2992	100 100 100 100 47 100 --100 100 12 100 87 -100 4 -100 66 100 100 72 100 100 100 100 100 -100 5 100 100	< ϵ 44.68 0.01 19.36 418.11 0.42 --0.20 78.51 718.40 7.61 940.62 -48.91 1056.19 -< ϵ 397.38 < ϵ < ϵ 219.68 200.44 0.03 0.05 4.41 < ϵ -0.62 182.54 0.67 141.50	548 2033 1057 2487 3774 1231 3920 5375 1441 5290 7565 1514 5777 8111 1619 7360 10321 3370 2422 6825 6082 4748 1455 3941 3110 2771 9776 1716 2325 5126 1835 2992	100 100 100 100 47 100 100 100 100 100 100 100 87 100 100 100 96 100 100 100 100 72 100 100 100 100 100 100 100 100 100 100	0.23 0.53 0.02 < ϵ 0.02 0.03 < ϵ 0.10 0.03 0.02 0.38 0.08 0.11 1.23 0.06 0.82 188.38 0.17 0.02 0.13 0.21 < ϵ 0.06 13.68 43.34 0.05 1.29 13.01 < ϵ < ϵ 0.02 < ϵ	548 2033 1057 2487 3774 1231 3920 5375 1441 5290 7565 1514 5777 8111 1619 7360 10321 3370 2422 6825 6082 4748 1455 3641 3110 2771 9776 1716 2325 5126 1835 2992	100 100 100 100 47 100 100 100 100 100 100 100 87 100 100 100 100 100 100 100 100 100 100 98 33 100 100 100 100 100 100 100	0.01 0.48 0.01 0.02 0.01 0.04 0.01 0.05 0.01 0.02 0.13 0.07 0.04 0.41 0.14 0.18 1.78 30.65 0.01 23.68 0.19 0.02 0.22 -166 0.05 6.25 4.94 0.01 < ϵ 0.04 0.03
	Instance	Best	BQP-PTS Succ.	Time	Best	PLSW [31] Succ.	Time	Best	MS/TS [39] Succ. Time	Best	BLS [5] Succ.	Time
	brock200 1 brock200 2 brock200 3 brock200 4 brock400 1 brock400 2 brock400 3 brock400 4 brock800 1 brock800 2 brock800 3 brock800 4 C125.9 C250.9 C500.9 C1000.9 C2000.5 C2000.9 C4000.5 DSJC500.5 DSJC1000.5 keller4 keller5 keller6 MANN a9 MANN a27 MANN a45 MANN a81 hamming6-2 hamming6-4 hamming8-2 hamming8-4 hamming10-2 hamming10-4 gen200 p0.9 44 gen200 p0.9 55 gen400 p0.9 55 gen400 p0.9 65 gen400 p0.9 75 c-fat200-1 c-fat200-2 c-fat200-5 c-fat500-1 c-fat500-2 c-fat500-5 c-fat500-10 johnson8-2-4 johnson8-4-4	2821 1428 2062 2107 3422 3350 3471 3626 3121 3043 3076 2971 2529 5092 6955 9254 2466 10999 2792 1725 2186 1153 3317 8062 372 12277 34194 111137 1 100 100 100 100 100 100 100 100 100 100 100 8 100 100 100 100 71 72 19 100 81 100 100 2 100 4 2 1072 100 134 100 10976 100 1472 100 50512 67 5129 8 5043 100 5416 100 6718 100 6940 100 8006 100 1284 100 2411 100 5887 100 1354 100 2628 100 5841 100 11586 100 66 100 511 100	0.02 0.08 0.09 0.22 0.72 1.00 0.57 4.01 3.95 42.29 8.22 105.53 0.02 0.05 0.21 37.50 1366.51 2711.97 19902.77 3.82 115.42 0.05 5.34 3418.36 0.01 22864.81 17524.05 6167.28 < ϵ < ϵ 0.80 < ϵ 24.47 32.49 0.02 0.43 0.28 0.11 0.67 0.01 0.34 0.20 0.20 3.10 1.15 1.29 < ϵ < ϵ	2821 1428 2062 2107 3422 3350 3471 3626 3121 3043 3076 2971 2529 5092 6822 8965 2466 10028 2792 1725 2186 1153 3317 7382 372 12264 34129 110564 -100 100 100 100 32 61 100 100 100 69 100 100 100 17 -5 18 --100 100 100 100 -100 --1072 100 134 100 10976 100 1472 100 50512 100 5086 1 5043 100 5416 100 6718 2 6935 4 8006 100 1284 100 2411 100 5887 100 1354 100 2628 100 5841 100 11586 100 66 100 511 100	0.19 0.02 0.01 0.70 437.19 415.95 12.04 0.05 31.46 893.42 3.35 3.77 8.08 247.69 -344.74 711.27 --0.95 47.76 0.02 119.24 -< ϵ ---< ϵ < ϵ < ϵ < ϵ < ϵ 1433.07 4.44 0.05 340.11 200.79 < ϵ < ϵ < ϵ < ϵ < ϵ 0.01 < ϵ < ϵ < ϵ < ϵ	2821 1428 2062 2107 3422 3350 3471 3626 3121 3043 3076 2971 2529 5092 6955 9254 2466 10999 2792 1725 2186 1153 3317 8062 372 12281 34192 111128 1 100 100 100 100 32 61 100 100 100 100 100 100 100 100 100 100 100 22 100 100 100 100 100 5 100 1 1 1072 100 134 100 10976 100 1472 100 50512 100 5129 100 5043 100 5416 100 6718 100 6940 100 8006 100 1284 100 2411 100 5887 100 1354 100 2628 100 5841 100 11586 100 66 100 511 100	< ϵ < ϵ < ϵ < ϵ 0.03 0.03 0.03 4.70 0.05 0.20 0.08 49.70 0.02 0.06 0.07 8.90 1.84 168.11 80.56 0.04 0.20 0.03 3.17 606.15 < ϵ 88.28 390.58 832.24 < ϵ < ϵ < ϵ < ϵ 0.92 2.21 < ϵ 0.33 0.15 0.04 0.88 0.14 0.06 0.02 0.73 0.33 0.14 0.06 < ϵ < ϵ	2821 1428 2062 2107 3422 3350 3471 3626 3121 3043 3076 2971 2529 5092 6955 9254 2466 10999 2792 NA NA 1153 3317 8062 NA 12281 34229 111237 1072 134 10976 1472 50512 5129 5043 5416 6718 6940 8006 NA NA NA NA NA NA NA 66 511	100 100 100 100 100 100 100 100 100 69 100 100 100 100 100 100 100 74 100 NA NA 100 100 44 NA 16 1 1 100 100 100 100 100 100 100 100 2 100 100 NA NA NA NA NA NA NA 100 100	< ϵ 0.03 0.01 0.01 0.05 0.08 0.26 7.60 0.13 0.51 0.50 339.07 0.01 0.06 0.25 12.33 2.1 1152.78 179.89 NA NA 0.04 0.65 1980.16 NA 396.58 929.41 2942.54 < ϵ < ϵ 0.12 < ϵ 6.64 26.86 0.01 1.75 0.18 0.05 0.43 NA NA NA NA NA NA NA < ϵ < ϵ

1

where the columns under headings of BQP-PTS, PLS W , MN/TS and BLS list 2 respectively the best solution values Best obtained by each algorithm, number 3 of times to reach Best over 100 runs Succ., and the average CPU time T ime (in 4 seconds) to reach Best. Notice that an entry with < ϵ signifies the average CPU 5 time was less than 0.01 second and N A signifies the results are unavailable.

7

  From Table1, we observe that BQP-PTS obtains 76 best solutions for the

	8
	9	evaluated 80 instances, better than 67 of PLS W and competitive with 77 of
	10	MN/TS and 78 of BLS. For the 2 failed cases, BQP-PTS achieves the second
	11	best solutions. In addition, BQP-PTS has a success rate of 100% to reach the
	12	best solutions for 64 instances, 12 more than PLS W but 4 and 5 less than
	13	MN/TS and BLS, respectively. Finally, BQP-PTS reaches the best known
	14	results within a reasonable time (less than 30 minutes) for most instances,
	15	except for 7 instances of C and MANN families. The long computing time for
	16	these instances could be attributed to their difficulty (in fact, the reference
	17	MVWCP heuristics also need longer time to attain their best solutions for
	18	these instances than for other instances). In particular, PLS W can only attain
	19	its indicated best values for some of these C and MANN instances (as well
	20	as some other instances) under a long and relaxed time condition (indicated
	21	by '-' in Table 1). Moreover, unlike the dedicated MVWCP algorithms which
	22	incorporate problem specific implementation to ensure their search efficiency,

Table 2

 2 Computational comparisons of the BQP-PTS approach with the MS/TS and BLS algorithms on the set of BHOSLIB-W instances

	Instances		BQP-PTS			MN/TS				BLS
		Best	Succ.	Avg	Time	Best	Succ.	Avg	Time	Best	Succ.	Avg	Time
	frb30-15-1	2990	100	2990	4.90	2990	100	2990	0.35	2990	100	2990	1.12
	frb30-15-2	3006	100	3006	1.58	3006	100	3006	3.45	3006	100	3006	8.15
	frb30-15-3	2995	100	2995	5.80	2995	100	2995	4.72	2995	100	2995	11.67
	frb30-15-4	3032	100	3032	1.04	3032	100	3032	0.12	3032	100	3032	0.33
	frb30-15-5	3011	100	3011	2.13	3011	100	3011	3.01	3011	100	3011	3.64
	frb35-17-1	3650	100	3650	6.59	3650	100	3650	25.80	3650	100	3650	68.45
	frb35-17-2	3738	100	3738	183.17	3738	96	3736.84	72.09	3738	100	3738	197.42
	frb35-17-3	3716	100	3716	15.54	3716	100	3716	7.72	3716	100	3716	11.58
	frb35-17-4	3683	100	3683	5.60	3683	77	3678.31	94.03	3683	100	3683	232.36
	frb35-17-5	3686	100	3686	3.73	3686	100	3686	8.09	3686	100	3686	20.00
	frb40-19-1	4063	100	4063	87.72	4063	83	4062.15	85.57	4063	96	4062.8	291.14
	frb40-19-2	4112	100	4112	76.39	4112	87	4111.16	134.58	4112	100	4112	439.81
	frb40-19-3	4115	100	4115	171.07	4115	19	4108.3	215.98	4115	46	4111.72	778.75
	frb40-19-4	4136	100	4136	758.82	4136	89	4135.56	96.65	4136	98	4135.92	333.89
	frb40-19-5	4118	100	4118	96.63	4118	90	4117.6	178.89	4118	88	4117.52	343.82
	frb45-21-1	4760	100	4760	896.25	4760	44	4748.66	126.26	4760	58	4754.3	982.32
	frb45-21-2	4784	100	4784	92.94	4784	47	4775.86	228.03	4784	100	4784	307.06
	frb45-21-3	4765	100	4765	150.64	4765	26	4756.9	125.35	4765	88	4764.76	641.03
	frb45-21-4	4799	100	4799	453.15	4799	43	4772.41	174.73	4799	96	4797.24	576.80
	frb45-21-5	4779	100	4779	34.17	4779	82	4777.38	193.82	4779	100	4779	206.60
	frb50-23-1	5494	20	5487.90	1911.49	5494	6	5484.74	186.62	5494	11	5486.41	1221.72
	frb50-23-2	5462	15	5452.65	2338.40	5462	3	5434.14	149.66	5462	5	5440.22	2837.74
	frb50-23-3	5486	100	5486	418.35	5486	53	5480.29	158.71	5486	98	5485.98	537.96
	frb50-23-4	5454	28	5453.3	1957.22	5454	9	5451.69	176.41	5454	14	5453.14	1190.43
	frb50-23-5	5498	100	5498	751.84	5498	89	5495.7	110.85	5498	100	5498	388.18
	frb53-24-1	5670	43	5660.35	981.33	5670	5	5637.94	233.22	5670	13	5652.18	1056.82
	frb53-24-2	5707	25	5694.3	1265.70	5707	6	5676.56	145.22	5707	3	5685.32	147.65
	frb53-24-3	5640	90	5639.35	1486.24	5640	15	5610.79	215.79	5640	48	5629.38	984.53
	frb53-24-4	5714	25	5700.75	1753.36	5714	7	5645.61	449.39	5714	13	5676.16	1604.50
	frb53-24-5	5659	6	5653.05	2802.83	5659	5	5628.77	294.00	5659	4	5642.5	278.91
	frb56-25-1	5916	19	5877.3	1035.00	5916	3	5836.85	308.90	5916	5	5860.82	1764.87
	frb56-25-2	5886	3	5861.3	1428.18	5872	1	5807.7	73.25	5886	1	5838.96	1013.85
	frb56-25-3	5859	1	5831.6	449.24	5859	1	5799.38	181.93	5859	1	5811	101.48
	frb56-25-4	5892	5	5869.3	1756.22	5892	3	5839.16	104.58	5892	12	5860.86	1256.90
	frb56-25-5	5853	1	5811.5	3549.57	5839	1	5768.39	322.70	5853	1	5787.04	4386.60
	frb59-26-1	6591	67	6585.05	2228.21	6591	3	6547.53	166.20	6591	17	6571.6	1435.99
	frb59-26-2	6645	40	6614.45	1820.56	6645	3	6567.07	212.49	6645	13	6602.34	1834.93
	frb59-26-3	6608	1	6567.55	2561.16	6608	1	6514.18	232.77	6608	1	6542.74	507.93
	frb59-26-4	6592	5	6533.5	3322.64	6592	1	6498.37	318.39	6592	6	6526.5	952.34
	frb59-26-5	6584	9	6554.55	747.80	6584	1	6522.57	161.47	6584	5	6546.94	1512.09

Table 2

 2 Best for each algorithm. From Table2, we observe that

	3

lists the best solution values Best, number of times hitting Best over 1 100 runs Succ., the average solution values and the average CPU time T ime 2 (in seconds) to reach

http://cs.hb g.psu.edu/txn131/clique.html

http://www.nlsde.buaa.edu.cn/∼kexu/benchmarks/graph-benchmarks.htm

Acknowledgment

We are grateful to the reviewers and the editors for their comments which help us to improve the paper. This work was supported by National Natural Science Foundation of China (Grant No. 71501157, 71371154) and Northwestern Polytechnical University (Grant No. 3102015RW007).

Appendix

To illustrate the transformation from the MVWCP to the BQP, we consider the following graph: Its linear formulation according to Eq. ( 1) is:


A Leoni Swart

Laura Gomez-Valero

Carmen Buchrieser

Hubert Hilbi
email: hilbi@imm.uzh.ch

Evolution and function of bacterial RCC1 repeat effectors

Keywords: Acanthamoeba, amoebae, bacterial evolution, Coxiella, Dictyostelium, effector protein, endoplasmic reticulum, endosome, host-pathogen interaction, Legionella, macrophage, microtubule, pathogen vacuole, phosphoinositide lipid, small GTPase, type IV secretion, vesicle trafficking Icm/Dot, intracellular multiplication/defective organelle trafficking, GAP, GTPase activating protein, GEF, guanine nucleotide exchange factor, LCV, Legionellacontaining vacuole, leg, Legionella eukaryotic gene, MTOC, microtubule organizing center, PI, phosphoinositide, PtdIns, phosphatidylinositol, RCC1, regulator of chromosome condensation 1, T4SS, type IV secretion system TGN, trans-Golgi network

Intracellular bacterial pathogens harbor genes, the closest homologues of which are found in eukaryotes. Regulator of chormosome condensation 1 (RCC1) repeat proteins are phylogenetically widespread and implicated in protein-protein interactions, such as the activation of the small GTPase Ran by its cognate guanine nucleotide exchange factor, RCC1.

Legionella pneumophila and Coxiella burnetii, the causative agents of Legionnaires' disease and Q fever, respectively, harbor RCC1 repeat coding genes. L. pneumophila secretes the RCC1 repeat "effector" proteins LegG1, PpgA and PieG into eukaryotic host cells, where they promote the activation of the pleiotropic small GTPase Ran, microtubule stabilization, pathogen vacuole motility and intracellular bacterial growth as well as host cell migration.

The RCC1 repeat effectors localize to the pathogen vacuole or the host plasma membrane and target distinct components of the Ran GTPase cycle, including Ran modulators and the small GTPase itself. C. burnetii translocates the RCC1 repeat effector NopA into host cells, where the effector localizes to nucleoli. NopA binds to Ran GTPase and promotes the nuclear accumulation of Ran(GTP), thus pertubing the import of the transcription factor NF-κB and innate immune signaling. Hence, divergent evolution of bacterial RCC1 repeat effectors defines the range of Ran GTPase cycle targets and likely allows fine-tuning of Ran GTPase activation by the pathogens at different cellular sites.

Legionella species -amoebae-resistant agents of Legionnaires' disease

Legionella species are Gram-negative, ubiquitous environmental bacteria (Newton et al.,

3

A total of at least 65 different Legionella species has been identified to date [START_REF] Parte | LPSN -List of prokaryotic names with standing in nomenclature (bacterio.net), 20 years on[END_REF], of which almost half have been associated with human infections [START_REF] Newton | Molecular pathogenesis of infections caused by Legionella pneumophila[END_REF].

Among the many Legionella species, Legionella pneumophila and Legionella longbeachae are the clinically most relevant and together account for approximately 95% of the reported Legionnaires' disease cases. In most parts of the world, L. pneumophila causes more than 90% of the infections; however, in Australia and New Zealand, L. pneumophila and L. longbeachae are responsible for approximately 46% and 30% of the cases, respectively [START_REF] Yu | Distribution of Legionella species and serogroups isolated by culture in patients with sporadic community-acquired legionellosis: an international collaborative survey[END_REF], Newton et al., 2010[START_REF] Whiley | Legionella longbeachae and legionellosis[END_REF]. Among the 16 different known L. pneumophila serogroups, the large majority of the human infections are caused by serogroup 1, even though this serogroup is not overrepresented in the environment [START_REF] Doleans | Clinical and environmental distributions of Legionella strains in France are different[END_REF].

Legionella species are opportunistic if not "accidental" human pathogens, which are almost exclusively transmitted through contaminated aerosols from natural or technical water sources [START_REF] Mercante | Current and emerging Legionella diagnostics for laboratory and outbreak investigations[END_REF]. While the human lung is considered a dead-end for the pathogen, an isolated incidence of a person-to-person transmission of L. pneumophila has been reported [START_REF] Correia | Probable person-to-person transmission of Legionnaires' disease[END_REF]. In this instance, the transmission of a clonal strain from an infected person to another caused the death of the two people involved due to legionellosis.

Intracellular growth of L. pneumophila and formation of the pathogen vacuole

L. pneumophila grows in free-living protozoa and macrophages of the innate immune system employing an apparently conserved mechanism (Gomez-Valero et al., 2011a[START_REF] Al-Quadan | Exploitation of evolutionarily conserved amoeba and mammalian processes by Legionella[END_REF]. Macrophage resistance is a prerequisite for Legionella pathogenesis. In order to replicate within host cells, L. pneumophila forms a unique, degradation-resistant compartment, the Legionella-containing vacuole (LCV). In the course of its maturation, the LCV does not acidify or fuse with lysosomes, but the compartment extensively communicates with several vesicle trafficking pathways including the endosomal, secretory and retrograde 4 routes [START_REF] Isberg | The Legionella pneumophila replication vacuole: making a cosy niche inside host cells[END_REF][START_REF] Asrat | Bacterial pathogen manipulation of host membrane trafficking[END_REF][START_REF] Personnic | Subversion of retrograde trafficking by translocated pathogen effectors[END_REF][START_REF] Bärlocher | Formation of the Legionella replicative compartment at the crossroads of retrograde trafficking[END_REF], Steiner et al., 2018). The initial and decisive stage of LCV formation is characterized by a phosphoinositide lipid conversion, where endosomal phosphatidylinositol 3-phosphate (PtdIns(3)P) is replaced by secretory PtdIns(4)P [START_REF] Weber | Legionella pneumophila exploits PI(4)P to anchor secreted effector proteins to the replicative vacuole[END_REF][START_REF] Weber | Live-cell imaging of phosphoinositide dynamics and membrane architecture during Legionella infection[END_REF], Weber et al., 2018, Swart et al., 2020a). This process is followed by the recruitment, activation and modification of small GTPases of the Arf [START_REF] Nagai | A bacterial guanine nucleotide exchange factor activates ARF on Legionella phagosomes[END_REF][START_REF] Goody | Modulation of small GTPases by Legionella[END_REF], Rab [START_REF] Kagan | Legionella subvert the functions of rab1 and sec22b to create a replicative organelle[END_REF][START_REF] Brombacher | Rab1 guanine nucleotide exchange factor SidM is a major phosphatidylinositol 4phosphate-binding effector protein of Legionella pneumophila[END_REF], Hoffmann et al., 2014[START_REF] Sherwood | Autophagy evasion and endoplasmic reticulum subversion: The yin and yang of Legionella intracellular infection[END_REF], Rap [START_REF] Schmölders | Comparative proteomics of purified pathogen vacuoles correlates intracellular replication of Legionella pneumophila with the small GTPase Ras-related protein 1 (Rap1)[END_REF] and Ran family (see below). Finally, at late steps of LCV maturation, the pathogen vacuole tightly associates but does not fuse with the endoplasmic reticulum (ER) in macrophages [START_REF] Swanson | Association of Legionella pneumophila with the macrophage endoplasmic reticulum[END_REF][START_REF] Tilney | How the parasitic bacterium Legionella pneumophila modifies its phagosome and transforms it into Page 30 of 36 rough ER: implications for conversion of plasma membrane to the ER membrane[END_REF] and amoebae [START_REF] Abu Kwaik | The phagosome containing Legionella pneumophila within the protozoan Hartmannella vermiformis is surrounded by the rough endoplasmic reticulum[END_REF][START_REF] Lu | Dynamic properties of Legionella-containing phagosomes in Dictyostelium amoebae[END_REF][START_REF] Weber | Live-cell imaging of phosphoinositide dynamics and membrane architecture during Legionella infection[END_REF].

In addition to small GTPases of several different families, large oligomeric GTPases also play a role in L. pneumophila infection [START_REF] Escoll | Legionella pneumophila modulates mitochondrial dynamics to trigger metabolic repurposing of infected macrophages[END_REF], Steiner et al., 2017). Atlastin3 (Atl3/Sey1) localizes to ER tubules and catalyzes homotypic membrane fusion events. This large GTPase promotes ER remodeling around the LCV, pathogen vacuole expansion and intracellular bacterial replication [START_REF] Steiner | ER remodeling by the large GTPase atlastin promotes vacuolar growth of Legionella pneumophila[END_REF]. Furthermore, the mitochondrial Dynamin1-like large GTPase (Dnm1l) mediates mitochondrial fragmentation during L. pneumophila infection [START_REF] Escoll | Legionella pneumophila modulates mitochondrial dynamics to trigger metabolic repurposing of infected macrophages[END_REF].

Arguably the most important L. pneumophila virulence factor essential for LCV formation is the Icm/Dot (intracellular multiplication/defective organelle trafficking) type IV secretion system (T4SS) [START_REF] Segal | Host cell killing and bacterial conjugation require overlapping sets of genes within a 22-kb region of the Legionella pneumophila genome[END_REF][START_REF] Vogel | Conjugative transfer by the virulence system of Legionella pneumophila[END_REF][START_REF] Kubori | The type IVB secretion system: an enigmatic chimera[END_REF]. The Icm/Dot T4SS is conserved among Legionella spp. [START_REF] Burstein | Genomic analysis of 38 Legionella species identifies large and diverse effector repertoires[END_REF], Gomez-Valero et al., 2019c), and in the case of L. pneumophila secretes more than 300 different "effector" proteins into eukaryotic host cells [START_REF] Burstein | Genomescale identification of Legionella pneumophila effectors using a machine learning approach[END_REF][START_REF] Zhu | Comprehensive identification of protein substrates of the Dot/Icm type IV transporter of Legionella pneumophila[END_REF][START_REF] Lifshitz | Computational modeling and experimental validation of the Legionella and Coxiella virulence-related type-IVB secretion signal[END_REF][START_REF] Qiu | Legionella and Coxiella effectors: strength in diversity and activity[END_REF]. The effectors subvert pivotal process in target cells, including membrane trafficking, cytoskeleton dynamics or signal transduction, and some of them catalyze hitherto unknown 5 biological reactions [START_REF] Hubber | Modulation of host cell function by Legionella pneumophila type IV effectors[END_REF][START_REF] Hilbi | Secretive bacterial pathogens and the secretory pathway[END_REF][START_REF] Haneburger | Phosphoinositide lipids and the Legionella pathogen vacuole[END_REF][START_REF] Sherwood | A Rab-centric perspective of bacterial pathogenoccupied vacuoles[END_REF][START_REF] Finsel | Formation of a pathogen vacuole according to Legionella pneumophila: how to kill one bird with many stones[END_REF][START_REF] Qiu | Legionella and Coxiella effectors: strength in diversity and activity[END_REF]. A number of effectors target components commandeering eukaryotic membrane dynamics. These include small GTPases and PI lipids, but also the vacuolar H + -ATPase [START_REF] Xu | Inhibition of host vacuolar H + -ATPase activity by a Legionella pneumophila effector[END_REF], the autophagy machinery [START_REF] Choy | The Legionella effector RavZ inhibits host autophagy through irreversible Atg8 deconjugation[END_REF][START_REF] Horenkamp | The Legionella anti-autophagy effector RavZ targets the autophagosome via PI3P-and curvature-sensing motifs[END_REF][START_REF] Rolando | S1P-lyase targets host sphingolipid metabolism and restrains autophagy[END_REF][START_REF] Arasaki | Legionella effector Lpg1137 shuts down ER-mitochondria communication through cleavage of syntaxin 17[END_REF][START_REF] Yang | Elucidation of the anti-autophagy mechanism of the Legionella effector RavZ using semisynthetic LC3 proteins[END_REF], or the retromer coat complex and other components of the retrograde trafficking pathway [START_REF] Weber | Pathogen trafficking pathways and host phosphoinositide metabolism[END_REF][START_REF] Finsel | The Legionella effector RidL inhibits retrograde trafficking to promote intracellular replication[END_REF], Bärlocher et al., 2017a[START_REF] Romano-Moreno | Molecular mechanism for the subversion of the retromer coat by the Page 28 of 36 Legionella effector RidL[END_REF], Welin et al., 2018[START_REF] Yao | Mechanism of inhibition of retromer transport by the bacterial effector RidL[END_REF].

Co-evolution of Legionella with protozoa and acquisition of eukaryotic genes

Free-living protozoa represent a privileged environmental niche of Legionella species. While some protozoa kill and digest L. pneumophila [START_REF] Amaro | Diverse protist grazers select for virulence-related traits in Legionella[END_REF][START_REF] Boamah | From many hosts, one accidental pathogen: The diverse protozoan hosts of Legionella[END_REF], there is indeed a tremendous diversity of environmental hosts, and L. pneumophila has been shown to replicate in at least 30 different protozoan species, including amoebae (e.g., Acanthamoeba, Hartmanella, Naegleria, Vahlkampfia and Dictyostelium spp.) and ciliates (e.g., Tetrahymena and Paramecium spp.) [START_REF] Fields | The molecular ecology of Legionellae[END_REF][START_REF] Boamah | From many hosts, one accidental pathogen: The diverse protozoan hosts of Legionella[END_REF][START_REF] Swart | Acanthamoeba and Dictyostelium as cellular models for Legionella infection[END_REF]. The intimate contact and co-evolution with these primordial predators is believed to render environmental protozoa an "evolutionary crib" for pathogen evolution [START_REF] Greub | Microorganisms resistant to free-living amoebae[END_REF][START_REF] Molmeret | Amoebae as training grounds for intracellular bacterial pathogens[END_REF], Gomez-Valero et al., 2013). In fact, it was recently experimentally demonstrated that the cumulative selective pressures of multiple and diverse amoebal hosts shapes the virulence of L. pneumophila for macrophages, and -as a corollarydetermines pathogenesis in humans [START_REF] Park | Combinatorial selection in amoebal hosts drives the evolution of the human pathogen Legionella pneumophila[END_REF].

The genus Legionella belongs to the γ-proteobacteria and is characterized by a large genetic diversity [START_REF] Gomez-Valero | Genome dynamics in Legionella: the basis of versatility and adaptation to intracellular replication[END_REF]. To date, the genomes of 58 Legionella species, including L. pneumophila and L. longbeachae, have been fully sequenced and annotated by bioinformatics means [START_REF] Burstein | Genomic analysis of 38 Legionella species identifies large and diverse effector repertoires[END_REF][START_REF] Gomez-Valero | Evolutionary dissection of the Dot/Icm system based on comparative genomics of 58 Legionella Species[END_REF]. The genomes show 6 a high plasticity, harbor many mobile genetic elements and contain around 10% strainspecific genes. The large diversity among Legionella species is owing to widespread horizontal gene transfer among members of the genus, other bacterial species, and -given the omnipresence of "eukaryotic-like" genes -presumably also with eukaryotic host cells [START_REF] Cazalet | Evidence in the Legionella pneumophila genome for exploitation of host cell functions and high genome plasticity[END_REF][START_REF] De Felipe | Evidence for acquisition of Legionella type IV secretion substrates via interdomain horizontal gene transfer[END_REF], Gomez-Valero et al., 2011b, Gomez-Valero et al., 2019a).

Upon sequencing the genome of L. pneumophila, a wide variety of genes encoding eukaryotic-like proteins and eukaryotic domain-carrying proteins were identified, reflecting the long-standing co-evolution of the bacterium with eukaryotic host cells and highlighting potential virulence factors [START_REF] Cazalet | Evidence in the Legionella pneumophila genome for exploitation of host cell functions and high genome plasticity[END_REF][START_REF] De Felipe | Evidence for acquisition of Legionella type IV secretion substrates via interdomain horizontal gene transfer[END_REF]. Indeed, many of these proteins turned out to be substrates of the Icm/Dot T4SS and likely target host cell processes by functioning analogously to their eukaryotic homologues. However, only a few of these effector proteins have been biochemically and cell biologically characterized in detail to date.

The first Icm/Dot substrate identified, RalF, contains a Sec7 domain and functions as a guanine nucleotide exchange factor (GEF) for the ADP ribosylation factor (Arf) family of small GTPases, which recruits and activates Arf1 to LCVs [START_REF] Nagai | A bacterial guanine nucleotide exchange factor activates ARF on Legionella phagosomes[END_REF][START_REF] Amor | The structure of RalF, an ADP-ribosylation factor guanine nucleotide exchange factor from Legionella pneumophila, reveals the presence of a cap over the active site[END_REF][START_REF] Alix | The capping domain in RalF regulates effector functions[END_REF][START_REF] Folly-Klan | A novel membrane sensor controls the localization and ArfGEF activity of bacterial RalF[END_REF]. RomA (LegAS4) contains a SET domain and covalently modifies histones through its methyltransferase activity [START_REF] Li | SET-domain bacterial effectors target heterochromatin protein 1 to activate host rDNA transcription[END_REF][START_REF] Rolando | Legionella pneumophila effector RomA uniquely modifies host chromatin to repress gene expression and promote intracellular bacterial replication[END_REF]. LpSpl (LegS2) is a close relative of the eukaryotic sphingosine 1-phosphate lyase (Spl), additionally harbors a C-terminal type IV secretion signal, and inhibits the host cell autophagy pathway in L. pneumophila-infected cells [START_REF] Degtyar | A Legionella effector acquired from protozoa is involved in sphingolipids metabolism and is targeted to the host cell mitochondria[END_REF], Abu Khweek et al., 2016[START_REF] Rolando | S1P-lyase targets host sphingolipid metabolism and restrains autophagy[END_REF].

LubX [START_REF] Kubori | Legionella translocates an E3 ubiquitin ligase that has multiple U-boxes with distinct functions[END_REF], LegU1 [START_REF] Ensminger | E3 ubiquitin ligase activity and targeting of BAT3 by multiple Legionella pneumophila translocated substrates[END_REF] and AnkB [START_REF] Al-Khodor | A Dot/Icm-translocated ankyrin protein of Legionella pneumophila is required for intracellular proliferation within human macrophages and protozoa[END_REF][START_REF] Price | Molecular mimicry by an F-box effector of Legionella pneumophila hijacks a conserved polyubiquitination machinery within macrophages and protozoa[END_REF][START_REF] Ensminger | E3 ubiquitin ligase activity and targeting of BAT3 by multiple Legionella pneumophila translocated substrates[END_REF], Lomma et al., 2010) are Icm/Dot-translocated U-box or F-box-containing E3 ubiquitin ligases that catalyze ubiquitination reactions. Furthermore, AnkB [START_REF] Ivanov | Lipidation by the host prenyltransferase machinery facilitates membrane localization of Legionella pneumophila effector proteins[END_REF][START_REF] Price | Exploitation of conserved eukaryotic host cell farnesylation machinery by an F-box effector of Legionella pneumophila[END_REF], as well as LegG1 (alias MitF, 7 Lpg1976) and PieG (Lpp1959) [START_REF] Ivanov | Lipidation by the host prenyltransferase machinery facilitates membrane localization of Legionella pneumophila effector proteins[END_REF][START_REF] Rothmeier | Activation of Ran GTPase by a Legionella effector promotes microtubule polymerization, pathogen vacuole motility and infection[END_REF][START_REF] Swart | Divergent evolution of Legionella RCC1 repeat effectors defines the range of Ran GTPase cycle targets[END_REF]) contain a C-terminal CAAX motif, which is lipidated by the host prenylation machinery to facilitate membrane localization.

Legionella species harbor eukaryotic-like RCC1 repeat coding genes

The human regulator of chromatin condensation 1 (RCC1) is the founding member of the RCC1 repeat family (http://pfam.xfam.org/family/PF00415). RCC1 harbors seven RCC1 repeats of 51-68 residues and is a GEF for the small Ran (Ras-like nuclear) GTPase [START_REF] Bischoff | Catalysis of guanine nucleotide exchange on Ran by the mitotic regulator RCC1[END_REF]. Using the internal repeat profiles of the 7-bladed propeller structures of eukaryotic RCC1 and the prokaryotic β-lactamase inhibitor protein II (BLIP II) allowed the definition of the RCC1-like repeat family of propeller proteins [START_REF] Stevens | RCC1-like repeat proteins: a pangenomic, structurally diverse new superfamily of beta-propeller domains[END_REF]. The RCC1 repeats harbor only very little primary amino acid sequence identity and occur in 3-7 repeats per protein. RCC1 repeats are wide-spread among metazoans (animals, plants, fungi), unicellular eukaryotes, archaea and prokaryotes. The wide distribution of RCC1 repeats and their conservation among a range of organisms likely reflects the versatile nature of this motif [START_REF] Stevens | RCC1-like repeat proteins: a pangenomic, structurally diverse new superfamily of beta-propeller domains[END_REF].

Bioinformatics analysis revealed that among the genomes of Legionella species sequenced more than 57% (32 out of 56) are predicted to produce one or multiple RCC1 repeat proteins [START_REF] Gomez-Valero | Evolutionary dissection of the Dot/Icm system based on comparative genomics of 58 Legionella Species[END_REF] (Figure 1). The seemingly random distribution of RCC1 repeat proteins throughout the genus Legionella, together with the observation that not all species within the same clade contain RCC1 repeat proteins, suggests that the proteins were independently acquired rather than originating from a common ancestor. Furthermore, recent studies concluded that DNA interchange between different Legionella species is rare [START_REF] Burstein | Genomic analysis of 38 Legionella species identifies large and diverse effector repertoires[END_REF][START_REF] Joseph | Dynamics of genome change among Legionella species[END_REF]. An independent and exogenous acquisition of RCC1 repeat coding genes is in agreement with a vital role for Legionella-host cell interactions.

Nonetheless, RCC1 repeat effectors are apparently not essential for Legionella pathogenicity, since there is no correlation between the presence of RCC1 repeat proteins and the source of the isolate (clinical or environmental). L. longbeachae, the second most common etiological agent of Legionnaires' disease, apparently lacks RCC1 repeat effectors [START_REF] Cazalet | Analysis of the Legionella longbeachae genome and transcriptome uncovers unique strategies to cause Legionnaires' disease[END_REF] (Figure 1). In contrast, L. waltersii, which has also been linked to a clinical case [START_REF] König | Legionella waltersii--a novel cause of pneumonia?[END_REF], harbors as many as 15 RCC1 repeat coding genes.

Phylogenetic analyses of these homologues revealed a cluster, indicating that they might have evolved through gene duplication. However, the functional significance of this high number of RCC1 repeat coding genes is not known.

Little is known about the origin of RCC1 repeat proteins, although it is suggested that prokaryotes acquired their RCC1 repeats via horizontal gene transfer from eukaryotes [START_REF] Gomez-Valero | Genome dynamics in Legionella: the basis of versatility and adaptation to intracellular replication[END_REF]. In order to obtain further insights into the origin of L. pneumophila RCC1 repeat effectors, we constructed a phylogenetic tree for one of the proteins, PieG (Figure 2). Phylogenetic trees obtained with either distances and likelihood methods were similar and indicated clustering of L. pneumophila PieG with eukaryotic proteins closer than with prokaryotic proteins. The closest eukaryotic sequence belongs to the amoeba Naegleria fowleri, an experimentally validated host of L. pneumophila [START_REF] Boamah | From many hosts, one accidental pathogen: The diverse protozoan hosts of Legionella[END_REF]. Moreover, amoebae-infecting viruses such as Marseillevirus [START_REF] Scola | Looking at protists as a source of pathogenic viruses[END_REF], also harbor RCC1 repeat proteins, which group close to L. pnemophila PieG (Figure 2). These findings support the notion of horizontal gene transfer from a protozoan hosts or from a coinfecting virus as the origin of Legionella RCC1 repeat coding genes.

L. pneumophila RCC1 repeat coding genes are distributed in two main strain clusters RCC1 repeat coding genes are conserved in the genomes of all 59 L. pneumophila strains sequenced to date [START_REF] Swart | Divergent evolution of Legionella RCC1 repeat effectors defines the range of Ran GTPase cycle targets[END_REF]. While some L. pneumophila strains contain two distinct RCC1 repeat coding genes (e.g., strain Philadelphia-1: legG1/lpg1976 and 9 ppgA/lpg2224), others contain only one single gene (e.g., strains Paris or Lens: pieG/lpp1959) or additionally a duplicated ppgA gene. Accordingly, the RCC1 repeat coding genes are distributed in two main clusters: the "Philadelphia-1" cluster and the " Paris-Lens" cluster, respectively [START_REF] Swart | Divergent evolution of Legionella RCC1 repeat effectors defines the range of Ran GTPase cycle targets[END_REF].

Another emerging pattern is that all but one strains in the "Philadelphia-1" cluster contain a split pieG gene (yielding lpg1975 and legG1). Based on the distribution pattern, it is more likely that the ppgA gene was acquired by an ancestral L. pneumophila strain harboring pieG rather than that the ppgA gene was lost from a genome. This further suggests that the split of pieG (or duplication and modification of ppgA) happened as a subsequent step, and possibly as a result of the acquisition of ppgA [START_REF] Swart | Divergent evolution of Legionella RCC1 repeat effectors defines the range of Ran GTPase cycle targets[END_REF].

Many RCC1-repeat proteins adopt the complex β-propeller fold [START_REF] Renault | The 1.7 A crystal structure of the regulator of chromosome condensation (RCC1) reveals a seven-bladed propeller[END_REF][START_REF] Lim | Crystal structure and kinetic analysis of beta-lactamase inhibitor protein-II in complex with TEM-1 beta-lactamase[END_REF][START_REF] Stevens | RCC1-like repeat proteins: a pangenomic, structurally diverse new superfamily of beta-propeller domains[END_REF], possibly aided by specific eukaryotic chaperones. PpgA and PieG are predicted to have a similar seven-bladed tertiary structure, whereas LegG1 is truncated and thus lacks three blades. Arguably, production of two full-length, eukaryotic-like RCC1 repeat proteins is challenging for the bacterial folding machinery, which resulted in the split of pieG and production of the more easily foldable LegG1. In agreement with this notion, LegG1 is soluble and can easily be purified from E. coli, whereas PpgA and PieG form aggregates upon heterologous production in E. coli [START_REF] Swart | Divergent evolution of Legionella RCC1 repeat effectors defines the range of Ran GTPase cycle targets[END_REF].

L. pneumophila RCC1 repeat effectors target different Ran GTPase cycle components

The 25 kDa Ran protein is the most abundant small GTPase in the cell and a pleiotropic regulator of different processes in eukaryotic cells [START_REF] Joseph | Ran at a glance[END_REF][START_REF] Yudin | Ran on tracks--cytoplasmic roles for a nuclear regulator[END_REF]. Ran GTPase is the master regulator of nucleo-cytoplasmic transport [START_REF] Stewart | Molecular mechanism of the nuclear protein import cycle[END_REF], controls mitotic spindle assembly during cell division and post-mitotic nuclear envelope formation [START_REF] Goodman | Mitotic spindle morphogenesis: Ran on the microtubule cytoskeleton and beyond[END_REF][START_REF] Clarke | Spatial and temporal coordination of mitosis by Ran GTPase[END_REF], and governs non-centrosomal microtubule dynamics in the cytoplasm [START_REF] Schulze | RanBP10 is a cytoplasmic guanine nucleotide exchange factor that modulates noncentrosomal microtubules[END_REF]. Ran is activated by the GEF RCC1, which 10 facilitates the exchange of GDP with GTP [START_REF] Bischoff | Catalysis of guanine nucleotide exchange on Ran by the mitotic regulator RCC1[END_REF]. RCC1 is regulated by phosphorylation, e.g., during mitosis by the tumor suppressor RASSF1A, which induces Ran(GTP)-dependent microtubule hyperstability. Moreover, the cytoplasmic Ran GEF RanBP10 positively regulates the stability of non-centrosomal microtubules in non-mitotic cells, and accordingly, depletion of RanBP10 disrupts the microtubule cytoskeleton [START_REF] Schulze | RanBP10 is a cytoplasmic guanine nucleotide exchange factor that modulates noncentrosomal microtubules[END_REF]. Ran is inactivated by the Ran GTPase-activating protein 1 (RanGAP1) together with Ran binding protein 1 (RanBP1), which exclusively binds to activated Ran [START_REF] Joseph | Ran at a glance[END_REF][START_REF] Yudin | Ran on tracks--cytoplasmic roles for a nuclear regulator[END_REF].

L. pneumophila strains produce the Icm/Dot-translocated RCC1 repeat proteins LegG1 (31 kDa, 3 repeats) [START_REF] De Felipe | Evidence for acquisition of Legionella type IV secretion substrates via interdomain horizontal gene transfer[END_REF][START_REF] De Felipe | Legionella eukaryotic-like type IV substrates interfere with organelle trafficking[END_REF], PpgA (66 kDa, 2 repeats) [START_REF] Ninio | A Legionella pneumophila effector protein encoded in a region of genomic plasticity binds to Dot/Icm-modified vacuoles[END_REF], and PieG (53 kDa, 2 repeats) [START_REF] Ninio | A Legionella pneumophila effector protein encoded in a region of genomic plasticity binds to Dot/Icm-modified vacuoles[END_REF][START_REF] Ivanov | Lipidation by the host prenyltransferase machinery facilitates membrane localization of Legionella pneumophila effector proteins[END_REF] (Figure 3). LegG1, PpgA and PieG play important roles in pathogen-host interactions, since L. pneumophila mutant strains lacking the corresponding genes (single or double mutants) are impaired for intracellular replication in macrophages and Dictyostelium discoideum, and outcompeted by the parental strain in amoebae competition assays using Acanthamoeba castellanii as a host cell [START_REF] Rothmeier | Activation of Ran GTPase by a Legionella effector promotes microtubule polymerization, pathogen vacuole motility and infection[END_REF][START_REF] Swart | Divergent evolution of Legionella RCC1 repeat effectors defines the range of Ran GTPase cycle targets[END_REF].

LegG1, PpgA and PieG target distinct components of the Ran GTPase cycle, thereby promoting Ran activation [START_REF] Rothmeier | Activation of Ran GTPase by a Legionella effector promotes microtubule polymerization, pathogen vacuole motility and infection[END_REF][START_REF] Swart | Divergent evolution of Legionella RCC1 repeat effectors defines the range of Ran GTPase cycle targets[END_REF]. Namely, LegG1 interacts with the GEF RanBP10, PpgA with RanGAP1, and PieG with both Ran GTPase as well as RanGAP1 [START_REF] Swart | Divergent evolution of Legionella RCC1 repeat effectors defines the range of Ran GTPase cycle targets[END_REF]. Since all three L. pneumophila RCC1 repeat effectors increase the cellular amount of Ran(GTP), we hypothesize that LegG1 activates the GEF RanBP10, PpgA inhibits the GAP RanGAP1, and PieG stabilizes Ran(GTP) by binding to the active GTPase, and/or inhibiting RanGAP1 (Figure 4). By targeting a Ran GEF or a Ran GAP, the L. pneumophila RCC1 repeat effectors act differently from other Icm/Dot substrates, which directly show GEF or GAP activity or covalently modify small GTPases (of 11 the Rab family) to modulate their activity [START_REF] Machner | Targeting of host Rab GTPase function by the intravacuolar pathogen Legionella pneumophila[END_REF][START_REF] Ingmundson | Legionella pneumophila proteins that regulate Rab1 membrane cycling[END_REF][START_REF] Goody | Modulation of small GTPases by Legionella[END_REF][START_REF] Sherwood | A Rab-centric perspective of bacterial pathogenoccupied vacuoles[END_REF].

Unexpectedly, LegG1 (the N-terminal part of PieG) targets a different component of the Ran GTPase cycle than full-length PieG. Hence, the split of pieG -the hallmark of the L. pneumophila "Philadelphia-1" cluster -alters the target of the corresponding protein. This substrate switch can be experimentally reversed upon fusion of legG1 with the upsteam ORF, lpg1975 [START_REF] Swart | Divergent evolution of Legionella RCC1 repeat effectors defines the range of Ran GTPase cycle targets[END_REF]) (Figure 3). By targeting the Ran modulator RanBP10, instead of the small GTPase itself, LegG1 might exert an additional level of control in the modulation of the Ran GTPase cycle. Furthermore, through acquisition of PpgA, strain Philadelphia-1 targets not only a Ran GEF, but additionally also a Ran GAP. Overall, divergent evolution of L. pneumophila RCC1 repeat effectors expands the range of target components of the Ran GTPase cycle and thus might fine-tune Ran activation in L. pneumophila-infected cells.

L. pneumophila RCC1 repeat effectors localize to distinct cellular compartments

The small GTPase Ran has pleiotropic functions in different cellular compartments [START_REF] Joseph | Ran at a glance[END_REF][START_REF] Yudin | Ran on tracks--cytoplasmic roles for a nuclear regulator[END_REF]. Hence, the unrestricted activation of Ran is likely detrimental to host cells. To avoid interference with Ran-regulated processes at different subcellular sites, Ran modulation needs to be spatially controlled. Nucleo-cytoplasmic transport, e.g., is tightly regulated by chromatin-bound RCC1 and cytoplasmic RanGAP1, and a re-distribution of the regulators leading to disruption of the Ran(GTP) gradient across the nuclear envelope has disastrous consequences for RNA export from the nucleus [START_REF] Izaurralde | The asymmetric distribution of the constituents of the Ran system is essential for transport into and out of the nucleus[END_REF].

The L. pneumophila RCC1 repeat effectors LegG1, PpgA and PieG localize to different subcellular compartments (Figure 4). Upon ectopic production in mammalian cells, D. discoideum or yeast, LegG1 and PieG are prenylated at their C-terminal CAAX site and localize to vesicular structures in the cells, or to LCVs in L. pneumophila-infected D. discoideum [START_REF] Ninio | A Legionella pneumophila effector protein encoded in a region of genomic plasticity binds to Dot/Icm-modified vacuoles[END_REF][START_REF] Ivanov | Lipidation by the host prenyltransferase machinery facilitates membrane localization of Legionella pneumophila effector proteins[END_REF][START_REF] Swart | Divergent evolution of Legionella RCC1 repeat effectors defines the range of Ran GTPase cycle targets[END_REF]. Moreover, upon 12 translocation by the Icm/Dot T4SS in L. pneumophila-infected cells, LegG1 also localizes to LCVs and activates Ran in the vicinity of the pathogen vacuole [START_REF] Rothmeier | Activation of Ran GTPase by a Legionella effector promotes microtubule polymerization, pathogen vacuole motility and infection[END_REF]. In contrast, ectopically produced PpgA exclusively localizes to the plasma membrane in D. discoideum amoebae as well as in the yeast model [START_REF] Swart | Divergent evolution of Legionella RCC1 repeat effectors defines the range of Ran GTPase cycle targets[END_REF]. Analogously to a LegG1-dependent Ran(GTP) gradient emanating from the LCV, PpgA might activate Ran at the plasma membrane and promote the formation of a Ran(GTP) gradient and microtubule stabilization at the cell cortex (Figure 4).

In agreement with a distinct subcellular activity of LegG1 on LCVs, the RCC1 repeat effector does not seem to affect the nuclear localization of the Icm/Dot substrate RomA. The L. pneumophila effectors RomA (LegAS4) is transported across the nuclear envelope dependent on its nuclear localization signal (NLS), likely driven by the Ran(GTP) gradient [START_REF] Li | SET-domain bacterial effectors target heterochromatin protein 1 to activate host rDNA transcription[END_REF][START_REF] Rolando | Legionella pneumophila effector RomA uniquely modifies host chromatin to repress gene expression and promote intracellular bacterial replication[END_REF]. Overall, these observations suggest that the modulation of Ran by L. pneumophila RCC1 repeat effectors is strictly controlled by their distinct cellular localization.

L. pneumophila RCC1 repeat effectors promote LCV motility and host cell migration

The host components of LCVs are instrumental for its architecture and function. In order to determine these components, proteomics analysis was performed using pathogen vacuoles purified from infected D. discoideum amoebae [START_REF] Urwyler | Proteome analysis of Legionella vacuoles purified by magnetic immunoseparation reveals secretory and endosomal GTPases[END_REF][START_REF] Schmölders | Comparative proteomics of purified pathogen vacuoles correlates intracellular replication of Legionella pneumophila with the small GTPase Ras-related protein 1 (Rap1)[END_REF], murine RAW 264.7 macrophage-like cells [START_REF] Hoffmann | Functional analysis of novel Rab GTPases identified in the proteome of purified Legionella-containing vacuoles from macrophages[END_REF] and primary bonemarrow-derived macrophages from A/J mice [START_REF] Naujoks | IFNs modify the proteome of Legionella-containing vacuoles and restrict infection via IRG1-derived itaconic acid[END_REF]. This approach revealed that α-and β-tubulin, Ran GTPase, RanBP1, RanBP2, RanGAP1, RCC1 and RCC2 are LCV components, and accordingly, might be host components functionally implicated in pathogen vacuole formation and function. Indeed, Ran and RanBP1 were validated as LCVs components by fluorescence microscopy, and Ran, RanBP1 as well as RanGAP1 were 13 implicated in intracellular replication of L. pneumophila by RNA interference [START_REF] Rothmeier | Activation of Ran GTPase by a Legionella effector promotes microtubule polymerization, pathogen vacuole motility and infection[END_REF][START_REF] Swart | Divergent evolution of Legionella RCC1 repeat effectors defines the range of Ran GTPase cycle targets[END_REF].

Microtubules, alongside with actin and intermediate filaments, form the cytoskeleton that maintains cell shape and internal organization and plays an essential role for intracellular trafficking processes and cell migration (Etienne-Manneville, 2013). Microtubules are tubular polymers of α-and β-tubulin heterodimers, which originate from a membrane-less organelle called MTOC (microtubule organizing center) located in the vicinity of the nuclear envelope.

Long-range vesicle movements inside a cell as well as the distribution and stability of organelles and endocytic compartments require microtubules and associated motor proteins called kinesins, dyneins and myosins, which via specific adaptors transport cargoes along the microtubular tracks (Etienne-Manneville, 2013).

The L. pneumophila RCC1 repeat effectors LegG1, PpgA and PieG promote the intracellular motility of LCVs, and for LegG1 it has been shown that this occurs by stabilizing microtubules on the LCV membrane and also throughout the host cell [START_REF] Rothmeier | Activation of Ran GTPase by a Legionella effector promotes microtubule polymerization, pathogen vacuole motility and infection[END_REF], Hilbi et al., 2014[START_REF] Swart | Divergent evolution of Legionella RCC1 repeat effectors defines the range of Ran GTPase cycle targets[END_REF]. LegG1 interacts with the Ran GEF RanBP10 (see above), which also harbors a β-tubulin binding domain [START_REF] Schulze | RanBP10 is a cytoplasmic guanine nucleotide exchange factor that modulates noncentrosomal microtubules[END_REF]. Accordingly, LegG1 might directly link Ran activation and microtubule stabilization through this cytoplasmic Ran GEF.

Besides their involvement in trafficking of endocytic compartments and the LCV, microtubules are also of key importance for the structure, distribution and function of organelles such as the mitochondria and the Golgi apparatus. Accordingly, microtubule stabilization likely accounts for the effect of LegG1 (MitF) on mitochondrial dynamics and function during L. pneumophila infection [START_REF] Escoll | Legionella pneumophila modulates mitochondrial dynamics to trigger metabolic repurposing of infected macrophages[END_REF], as well as for the LegG1dependent disruption of Golgi cisternae in L. pneumophila-infected cells [START_REF] Rothmeier | Activation of Ran GTPase by a Legionella effector promotes microtubule polymerization, pathogen vacuole motility and infection[END_REF]. Taken together, the studies reveal that the modulation of the microtubule cytoskeleton 14 by LegG1 affects pathogen vacuole dynamics, host cell vesicle trafficking and organelle integrity.

Another cellular process depending on the microtubule cytoskeleton is cell migration [START_REF] Friedl | Collective cell migration in morphogenesis, regeneration and cancer[END_REF]. Migration is a polarized cellular process, where a protrusive leading edge is opposed to a retracting trailing edge. At the cell front, cortical actin is the primary stimulus for motion, while the microtubule network undertakes a regulatory function in coordinating rear retraction. During migration, the MTOC undergoes reorientation towards the side facing the direction of motion, allowing the microtubules to polarize from the center to the periphery of the cell [START_REF] Wehrle-Haller | Actin, microtubules and focal adhesion dynamics during cell migration[END_REF][START_REF] Kaverina | Regulation of cell migration by dynamic microtubules[END_REF].

L. pneumophila inhibits chemotaxis as well as random host cell migration by means of the small signaling molecule LAI-1 (Legionella autoinducer-1, 3-hydroxypentadecane-4-one) [START_REF] Simon | Interkingdom signaling by the Legionella quorum sensing molecule LAI-1 modulates cell migration through an IQGAP1-Cdc42-ARHGEF9-dependent pathway[END_REF] as well as through Icm/Dot-translocated effectors [START_REF] Simon | Icm/Dot-dependent inhibition of phagocyte migration by Legionella is antagonized by a translocated Ran GTPase activator[END_REF], Simon et al., 2015a). While the effector(s) inhibiting cell migration are not known, LegG1, PpgA and PieG rather promote the random and chemotactic migration of protozoan or mammalian phagocytes [START_REF] Rothmeier | Activation of Ran GTPase by a Legionella effector promotes microtubule polymerization, pathogen vacuole motility and infection[END_REF][START_REF] Simon | Icm/Dot-dependent inhibition of phagocyte migration by Legionella is antagonized by a translocated Ran GTPase activator[END_REF][START_REF] Swart | Divergent evolution of Legionella RCC1 repeat effectors defines the range of Ran GTPase cycle targets[END_REF]. At least in the case of LegG1, the inhibition of phagocyte migration proceeds through Ran.

Similar to LegG1, overproduction of PpgA positively affects host cell motility [START_REF] Swart | Divergent evolution of Legionella RCC1 repeat effectors defines the range of Ran GTPase cycle targets[END_REF]. Moreover, migration of amoeba infected with the ∆legG1-∆ppgA double mutant is "hyper-inhibited", suggesting that both proteins function in concert to stimulate host cell motility. However, LegG1 and PpgA probably employ distinct mechanisms to promote host migration since the former localizes to the LCV membrane and the latter to the plasma membrane, where the local accumulation of Ran(GTP) is expected to increase microtubule stability and hence, promote forward movement. LegG1-dependent microtubule modulation affects vesicular trafficking and thus, might indirectly enhance host cell migration. In summary, the L. pneumophila RCC1 repeat effectors promote cell migration either directly or perhaps indirectly through the activation of Ran and microtubule stabilization.

Coxiella burnetii -an obligate intracellular pathogen causing Q fever

Coxiella burnetii is the causative agent of a zoonotic disease called Q ("querry") fever, which is transmitted through aerosols and manifests as an acute or chronic ailment [START_REF] Dragan | Coxiella burnetii: international pathogen of mystery[END_REF]. The obligate intracellular bacterium replicates in a large lysosomal/autophagosomal compartment, the Coxiella-containing vacuole (CCV), characterized by an acidic pH, acid hydrolases and cationic peptides [START_REF] Voth | Lounging in a lysosome: the intracellular lifestyle of Coxiella burnetii[END_REF]. Like L. pneumophila, C. burnetii employs an Icm/Dot T4SS to translocate ca. 150 effector proteins into host cells [START_REF] Qiu | Legionella and Coxiella effectors: strength in diversity and activity[END_REF]. In fact, T4SS-dependent secretion appears to function very similarly in the two pathogens [START_REF] Zamboni | Coxiella burnetii express type IV secretion system proteins that function similarly to components of the Legionella pneumophila Dot/Icm system[END_REF][START_REF] Lifshitz | Computational modeling and experimental validation of the Legionella and Coxiella virulence-related type-IVB secretion signal[END_REF], and L. pneumophila can be used as a surrogate host to deliver C. burnetii effectors [START_REF] Carey | The Coxiella burnetii Dot/Icm system delivers a unique repertoire of type IV effectors into host cells and is required for intracellular replication[END_REF].

The C. burnetii RCC1 repeat effector NopA activates Ran GTPase in host cell nucleoli

Among the few characterized C. burnetii effectors one is called NopA (Nucleolar protein A) [START_REF] Burette | Modulation of innate immune signaling by a Coxiella burnetii eukaryotic-like effector protein[END_REF]. NopA is a Icm/Dot-translocated effector, which contains 4 RCC1 repeats in the C-terminal part. As only few amino acids define an RCC1 repeat, the repeats share only little sequence identity. Accordingly, C. burnetii nopA does not show significant homology with the L. pneumophila RCC1 repeat genes. Upon infection or ectopic production, NopA localizes to nucleoli in the host nucleus, where it binds to and activates the small GTPase Ran. The nucleolar accumulation of Ran(GTP) perturbs nucleocytoplasmic transport and the import of the transcription factor NF-κB. As a result, the production of cytokines and innate immune signaling is impaired by the C. burnetii effector NopA [START_REF] Burette | Modulation of innate immune signaling by a Coxiella burnetii eukaryotic-like effector protein[END_REF].

Conclusions and outlook

Intracellular bacterial pathogens produce RCC1 repeat effectors, which localize to different subcellular compartments and subvert the host cell Ran GTPase cycle. L. pneumophila 16 produces the RCC1 repeat effectors LegG1, PpgA and PieG, which divergently evolved to target distinct components of the Ran GTPase cycle. The RCC1 repeat effectors localize to different subcellular compartments, such as the LCV or the plasma membrane, allowing spatial regulation of Ran activation and the generation of local Ran(GTP) gradients leading to microtubule stabilization. C. burnettii produces the RCC1 repeat effector NopA, which localizes to nucleoli, binds to and activates Ran GTPase, and perturbs nucleocytoplasmic transport and NF-κB-dependent gene expression. These features of bacterial RCC1 repeat effectors -the expansion of host cell targets as well as distinct subcellular localizationslikely allow the pathogens to fine-tune Ran activation rather than risking unrestricted activation of the pleiotropic small GTPase. Future studies will address the biochemical characterization of bacterial RCC1 repeat effectors and the mechanism(s), by which these effectors subvert pivotal Ran-dependent host processes, such as LCV motility, vesicle trafficking, organelle integrity, cell migration and gene expression. Ran(GTP) gradient across the nuclear envelope is created by the Ran GEF RCC1 and RanGAP1 localizing in the nucleus or cytoplasm, respectively. The Ran(GTP) gradient is depicted ranging from yellow (high Ran(GTP) concentration) to white (high Ran(GDP) concentration). MTOC: microtubule organizing center.

Figure legends Figure 1 .

 legends1 Figure legends

Figure 2 .

 2 Figure 2. Phylogenetic tree of the RCC protein Lpp1959 from Legionella species and

Figure 3 .

 3 Figure 3. L. pneumophila RCC1 repeat proteins. Schematic overview and position of

Figure 4 .

 4 Figure 4. Distinct subcellular localization of L. pneumophila RCC1 repeat effectors and

Acknowledgements

We would like to thank Christophe Rusniok for advice and help with bioinformatics analyses.

Research in the laboratory of H. H. was supported by the Swiss National Science Foundation (SNF; 31003A_153200, 31003A_175557), the OPO foundation and the Novartis Foundation for Medical-Biological Research. Work in the C. B. laboratory was financed by the Institute Pasteur, the Agence Nationale de la Recherche (ANR; ANR-10-LABX-62-IBEID) and the Fondation pour la Recherche Médicale (FRM; EQU201903007847).

Conflict of Interest

The authors declare no conflict of interest.