Bastien Cazaux
email: cazaux@lirmm.fr

Thierry Lecroq
email: thierry.lecroq@univ-rouen.fr

Eric Rivals
email: rivals@lirmm.fr

From Indexing Data Structures to de Bruijn Graphs *

New technologies have tremendously increased sequencing throughput compared to traditional techniques, thereby complicating DNA assembly. Hence, assembly programs resort to de Bruijn graphs (dBG) of k-mers of short reads to compute a set of long contigs, each being a putative segment of the sequenced molecule. Other types of DNA sequence analysis, as well as preprocessing of the reads for assembly, use classical data structures to index all substrings of the reads. It is thus interesting to exhibit algorithms that directly build a dBG of order k from a pre-existing index, and especially a contracted version of the dBG, where non branching paths are condensed into single nodes. Here, we formalise the relationship between suffix trees/arrays and dBGs, and exhibit linear time algorithms for constructing the full or contracted dBGs. Finally, we provide hints explaining why this bridge between indexes and dBGs enables to dynamically update the order k of the graph.

Introduction

The de Bruijn graph (dBG) of order k on an alphabet Σ with σ symbols has σ k vertices corresponding to all the possible distinct strings of length k on the alphabet Σ and there is a directed edge from vertex u to vertex v if the suffix of u of length k -1 equals the prefix of v of length k -1. De Bruijn graphs have various properties and xy the concatenation of x and y. For every 1 ≤ i ≤ j ≤ |x|, x[i] denotes the i-th letter of x, and x[i .. j] denotes the substring or factor x [i]x[i + 1] . . . x [ j]. Let k be a positive integer. If |x| ≥ k, f irst k (x) is the prefix of length k of x and last k (x) is the suffix of length k of x. A substring of length k of x is called a k-mer of x. For i such that 1 ≤ i ≤ |x|k + 1, (x) k,i is the k-mer of x starting in position i, i.e. (x) k,i = x[i .. i + k -1]. Thus we have f irst k (x) = (x) k,1 and last k (x) = (x) k,|x|-k+1 . We denote by ♯(Λ) the cardinality of any finite set Λ.

Let S = {s 1 , . . . , s n } be a finite set of words. Let us denote the sum of the lengths of the input strings by S := ∑ s i ∈S |s i |. We denote by F S the set of factors of words of S. For a word w of F S ,

• Support S (w) is the set of pairs (i, j), where w is the substring (s i ) |w|, j . Support S (w) is called the support of w in S.

• RC S (w) (resp. LC S (w)) is the set of right context (resp. left context) of the word w in S, i.e. the set of words w ′ such that ww ′ ∈ F S (resp. w ′ w ∈ F S ).

• ⌈w⌉ S is the word ww ′ where w ′ is the longest word of RC S (w) such that Support S (w) = Support S (ww ′ ). In other words, such that w and ww ′ have exactly the same support in S.

• ⌊w⌋ S is the word w ′ where w ′ is the longest prefix of w such that Support S (w ′ ) = Support S (w).

• d S (w) := |⌈w⌉ S | -|w|.
In other words, ⌈w⌉ S is the longest extension of w having the same support than w in S, while ⌊w⌋ S is the shortest reduction of w with a support different from that of w in S. These definitions are illustrated in a running example, with S := {bacbab, cbabcaa, bcaacb, cbaac, bbacbaa}, presented in Fig. 1.

We give the definition of a de Bruijn graph for assembly (dBG for short), which differs from the original definition of a complete graph over all possible words of length k stated by de Bruijn [START_REF] De Bruijn | On bases for the set of integers[END_REF]. (V + , E + ), whose vertices are the k-mers of words of S and where an arc links u to v if and only if u and v are two successive k-mers of a word of S, i.e.:

V + := F S ∩ Σ k and E + := {(u, v) ∈ V + 2 | last k-1 (u) = f irst k-1 (v) and v[k] ∈ RC S (u)}.
Examples of arcs are displayed on Fig. 2.

Let us introduce now the notions of extensibility for a substring of S and that of a Contracted dBG (CdBG for short).

if ♯(LC S (w) ∩ Σ) = 1.
As S is clear from the context, we simply omit the "in S". Let w be a word of Σ ⋆ . The word w is said to be a unique k ′ -mer of S if and only if k ′ ≥ k and for all i ∈ [1..k ′k + 1], (w) k,i ∈ F S and for all j ∈ [1..k ′k], (w) k, j is right extensible and (w) k, j+1 is left extensible.

Definition 2.3 A contracted de Bruijn graph of order k, denoted by CDBG

+ k = (V + c , E + c ), is a directed graph where: V + c = {w ∈ Σ ⋆ | w is a k ′ -

mer unique maximal by substring and k ′ ≥ k} and E

+ c = {(u, v) ∈ V + c 2 | last k-1 (u) = f irst k-1 (v) and v[k] ∈ RC S (last k (u))}.
Note that in the previous definition, an element w in V + c does not necessarily belong to F S , since w may only exist as the substring of the agglomeration of two words of S. Thus, let w be a k ′ -mer unique maximal by substring with

k ′ ≥ k: last k (w) is not right extensible or RC S (last k (w)) ∩ Σ = {a} and last k-1 (w) • a is not left extensible, f irst k (w) is not left extensible or LC S ( f irst k (w)) ∩ Σ = {a} and a • f irst k-1 (w) is not right extensible.
With this argument, we have both following propositions.

Proposition 1 Let (u, v) ∈ E + c ; (last k (u), f irst k (v)) ∈ E + and there exists w ∈ V + such that (w, f irst k (v)) ∈ E + \{(last k (u), f irst k (v))} or (last k (u), w) ∈ E + \{(last k (u), f irst k (v))}. Proposition 2 Let (u, v) ∈ E + . If u is right extensible and v is left extensible, then there exists w ∈ V + c such that uv[k] is a substring of w. Otherwise, there exists (u ′ , v ′ ) ∈ E + c such that u = last k (u ′ ) and v = f irst k (v ′ ).
According to Prop. 1 and 2, CDBG + k is the graph DBG + k where the arcs (u, v) are contracted if and only if u is right extensible and v is left extensible.

Definition of de Bruijn Graphs with words

Let k be a positive integer. We define the following three subsets of F S .

• InitExact S,k = {w ∈ F S | |w| = k and d S (w) = 0} • Init S,k = {w ∈ F S | |w| ≥ k and d S ( f irst k (w)) = |w| -k} • SubInit S,k = InitExact S,k-1
A word of InitExact S,k is either only the suffix of some s i or has at least two right extensions, while the first k-mer of a word in Init S,k \ InitExact S,k has only one right extension.

Proposition 3 InitExact S,k = Init S,k ∩ {w ∈ F S | |w| = k}.
For w an element of Init S,k , f irst k (w) is a k-mer of S. Given two words w 1 et w 2 of Init S,k , f irst k (w 1 ) and f irst k (w 2 ) are distinct k-mers of S. Furthermore for each k-mer w ′ of S, there exists a word w of Init S,k such that f irst k (w) = w ′ . From this, we get the following proposition.

Proposition 4 There exists a bijection between Init S,k and the set of the k-mers of S.

According to Def. 2.1 and Prop. 4, each vertex of DBG + k can be assimilated to a unique element of Init S,k . To define the arcs between the words of Init S,k , which correspond to arcs of DBG + k , we need the following proposition, which states that each single letter that is a right extension of w gives rise to a single arc.

Proposition 5 For w ∈ InitExact S,k and a ∈ Σ ∩ RC S (w), there exists a unique w ′ ∈ Init S,k such that last k-1 (w)a is a prefix of w ′ .

The set Init S,k represents the nodes of DBG + k . Let us now build the set of arcs that is isomorphic to E + . Let w be a word of Init S,k and Succ(w) denote the set of successors of f irst k (w):

Succ(w) := {x ∈ Init S,k | ( f irst k (w), f irst k (x)) ∈ E + }.
We know that for each letter a in RC S (w), there exists an arc from f irst k (w) to f irst k (last |w|-1 (w)a) in DBG + k . We consider two cases depending on the length of w:

Case 1 |w| = k. According to Prop. 3, w ∈ InitExact S,k and hence last k-1 (w) ∈ SubInit S,k .
Therefore, the outgoing arcs of w in DBG + k are the arcs from w to w ′ satisfying the condition of Prop. 5. Then,

Succ(w) = ∪ a∈Σ∩RC S (w) ⌈last k-1 (w)a⌉ S . Case 2 |w| > k. As w is longer than k, it contains the next k-mer; hence f irst k (last |w|-1 (w)a) = f irst k (last |w|-1 (w)),
(w)) ∩ Σ, then last k-1 ( f irst k (w))a is left extensible if and only if ♯(Support S ( f irst k (w))) = ♯(Support S (last k-1 ( f irst k (w))a) \ {(i, 1) | 1 ≤ i ≤ n}).
We present a generic algorithm to build incrementally CDBG + k . In the following sections, we exhibit algorithms to compute DBG + k and CDBG + k for two important indexing structures.

4 Transition from the suffix tree to de Bruijn graphs A generalised ST (GST) can index the substrings of a set of words. Generally for this sake, all words are concatenated and separated by a special symbol not occurring elsewhere. However, this trick is not compulsory, and an alternative is to keep the indication of a terminating node within each node.

The Suffix Tree and its properties

The Generalised Suffix Tree (GST) of a set of words S is the suffix tree of S, where each word of S does not finish necessarily by a letter of unique occurrence. Hence, for each node v of the GST of S, we keep in memory the set, denoted by Suff S (v), of pairs (i, j) such that the word represented by v is the suffix of s i starting at position j. Let us denote by T the GST of S (from now on, we simply say the tree) and by V T its set of nodes. For v ∈ V T , Children(v) denotes its set of children and f (v) its parent. Some nodes of T may have just one child. The size of the union of Suff S (v) for all node v of T equals the number of leaves in the GST when the words end with a terminating symbol. Hence, the space to store T and the sets Suff S (.) is linear in S . By simplicity, for a node v of T , the word represented by v is confused with v. For each node v of T , v ∈ F S . As all elements of F S are not necessarily represented by a node of T , we give the following proposition. We consider the same two cases as for the construction of E + on p. 5, but in the case of a tree. Let v ∈ Init S,k .

Proposition 8 The set of nodes of T is exactly the set of words w of F

Case 1 |v| = k (Fig. 4a). As v ∈ InitExact S,k , sl(v) ∈ SubInit S,k . Therefore, each child u of sl(v) is an element of Init S,k . Thus, the outgoing arcs of v in DBG + k are the arcs from v to the child u of sl(v) where the first letter of the label between sl(v) and u is an element of the right context of v. As the set of the first letters of the label between v and children of v is exactly RC S (v) ∩ Σ, the number of outgoing arcs of v in DBG + k is the number of children of v. To build the outgoing arcs of v in DBG + k , for each child u ′ of v, we associate v with the node of Init S,k between the root and sl(u ′ ), i.e. ⌈ f irst k (sl(u ′ ))⌉ S .

Case 2 |v| > k (Fig. 4b and4c). We have that sl

(v) is a node of V T . As |v| > k, |sl(v)| ≥ k.
Thus, there exists an element of Init S,k between the root and sl(v).

We associate v with this node, i.e. ⌈ f irst k (sl(v))⌉ S .

We illustrate these two cases in Fig. 3. For Case 1: v is 6 2 6 5 , sl(v) is 7 2 7 5 , the unique child u ′ of v is 3 4 , and sl(u In both cases, building the arcs of E + requires to follow the SL of some node. The node, say u, pointed at by a SL may not be initial. Hence, the initial node representing the associated first k-mer of u is the only ancestral initial node of u. We equip each such node u with a pointer p(u) that points to the only initial node on its path from the root. In other words, for any u / ∈ Init S,k such that |u| > k, one has p(u) := ⌈ f irst k (u)⌉ S . The algorithm to build the DBG + k is as follows. A first depth first traversal of T allows to collect the nodes of Init S,k and for each such node to set the pointer p(.) of all its descendants in the tree. Finally to build E + , one scans through Init S,k and for each node v one adds Succ(v) to E + using the formula given above. Altogether this algorithm takes a time linear in the size of T . Moreover, the number of arcs in E + is linear in the total number of children of initial nodes. This gives us the following result.

′ ) is 4 4 , which is in Init S,k . For Case 2: v is 1 5 , sl(v) is 2 5 , and ⌈ f irst k (sl(v))⌉ S is . (a) (b) (c)

Construction of CDBG + k

In Section 3, we have seen an algorithm that allows to compute directly CDBG + k provided that one can determine if a node v is right extensible and if next(v) is left extensible, where next(v) denotes the only successor of v. Let us see how to compute the extensibility in the case of a Suffix Tree.

By applying Prop. 6 in the case of tree, for an element v of Init S,k , f irst k (v) is right extensible if and only if |v| > k or ♯(Children(v)) = 1. Thus checking the right extensibility of a node takes constant time.

For the left extensibility of the single successor of a node, one only needs the size of support of some nodes (Prop. 7). Let us see first how to compute ♯(Support S (.)) on the tree, and then how to apply Prop. 7.

Proposition 11 Let v be a word of F S and V T (⌈v⌉ S ) denotes the set of nodes of the subtree rooted in ⌈v⌉ S . Support S (v) = ∪ v ′ ∈V T (⌈v⌉ S ) Suff S (v ′ ).

Along a traversal of the tree, we compute and store ♯(Support S (v)) and

♯(Support S (v) ∩ {(i, 1) | 1 ≤ i ≤ n}) for each node v in linear time in |T |.
Let v be a word of Init S,k such that

f irst k (v) is right extensible. Case 1 If |v| = k then f irst k (v) = v and ♯(Children(v)) = 1. Let u be the only child of v. Thus, |u| > k, ♯(RC S (v) ∩ Σ) = {u[k + 1]}, and last k-1 (v)u[k + 1] = f irst k (sl(u)). Hence, ♯(Support S (v)) = ♯(Support S ( f irst k (sl(u))) \ {(i, 1) | 1 ≤ i ≤ n}) and by Prop. 7, f irst k (sl(u)) is left extensible. Case 2 If |v| > k then ♯(RC S ( f irst k (v)) ∩ Σ) = {v[k + 1]} and last k-1 ( f irst k (v)) • v[k + 1] = last k ( f irst k+1 (v)) = f irst k (sl(v)). By Prop. 7, f irst k (sl(v)) is left exten- sible if and only if ♯(Support S ( f irst k (v))) = ♯(Support S ( f irst k (sl(v))) \ {(i, 1) | 1 ≤ i ≤ n}) As ♯(Support S ( f irst k (v))) = ♯(Support S (⌈ f irst k (v)⌉ S )) and ♯(Support S (v)\{(i, 1) | 1 ≤ i ≤ n}) = ♯(Support S (v)) -♯(Support S (v) ∩ {(i, 1) | 1 ≤ i ≤ n}), determining if next(v)
is left extensible takes constant time. To conclude, as for any initial node v, we can compute in O(1) its set of successors Succ(v), its right extensibility, and the left extensibility of its single successor, we obtain a complexity that is linear in the size of DBG + k , since each successor is accessed only once. This yields Theorem 12.

Theorem 12 For a set of words S, building the Contracted de Bruijn Graph of order k, CDBG + k takes linear time and space in |T | or in S .

dBG and CdBG from Suffix Array

For lack of space the reader is referred to [START_REF] Cazaux | From Indexing Data Structures to de Bruijn Graphs[END_REF] for the full details.

Theorem 13

The dBG of order k, CDBG + k , for a set of words S can be built in a time and space that are linear in S using the generalised suffix array of S.

6 Dynamically updating the order of DBG + . Genome assembly from short reads requires to test multiple values of k for the dBG. Indeed, the presence of genomic repeats, makes some order k appropriate to assemble non repetitive regions, and larger orders necessary to disentangle (at least some) repeated regions. Combining assemblies obtained from DBG + k for successive values of k is the key of IDBA assembler, but the dBG is rebuilt for each value [START_REF] Peng | IDBA A Practical Iterative de Bruijn Graph De Novo Assembler[END_REF]. Other tools also exploit this idea [START_REF] Bankevich | SPAdes: a new genome assembly algorithm and its applications to single-cell sequencing[END_REF]. It is thus interesting to dynamically change the order of the dBG. Here, we argue that starting the construction from an index instead of the raw sequences ease the update. On page 7, we mention which information are needed in general to build DBG + k . Assume the words are indexed in a suffix tree T (as in Section 4.2). Consider changing k to k -1. First, only the nodes of Init S,k whose parent represents a word of length k -1 are substituted by their parent in DBG + k-1 , all other nodes remain unchanged. Thus, any arc of order k either stays as such or has some of its endpoints shifted toward the parent node in T . In any case, updating an arc depends only on the nature of its nodes in DBG + k-1 (whether they belong to Init S,k-1 or InitExact S,k-1 ), and can be computed in constant time.

The same situation arises when changing k to k +1. First, only nodes of InitExact S,k change in DBG + k+1 : they are substituted by their children. Updating an arc also depends on the nature of its nodes: it can create a fork towards the children of the destination node if the latter changes, or it can be multiplied and join each children of the source to one children of the destination if both nodes change. Then, the label of the children in T indicate which children to connect to. It can be seen that updating from DBG + k to DBG + k+1 in either direction takes linear time in the size of T . Moreover, as updating the support of nodes in T is straightforward, we can readily apply the contraction algorithm to obtain CDBG + k+1 (see Section 4.3).

s 1 Figure 1 :

 11 Figure 1: Support S (ba) = {(1, 1), (1, 4), (2, 2), (4, 2), (5, 2), (5, 5)}, RC S (ba) = {ε, c, cb, cba, cbab, b, bc, bca, bcaa, a, ac, cbaa}, LC S (ba) = {ε, c, ac, bac, b, bbac} and d S (ba) = 0. One has RC S (ba) ∩ Σ = {a, b, c}. Thus, the word ba is not right extensible in S (see Def. 2.2).

Definition 2 . 1 s 1 Figure 2 :

 2112 Figure 2: Examples of arcs from DBG + k . (a) letters in the right context of ba, and (b) the successors of node ba in DBG + 2 ; one for each letter in RC S (w) ∩ Σ. (c) letters in the left context of ba, and (d) the predecessors of node ba in DBG + 2 .

Definition 2 . 2 (

 22 Extensibility) Let w be a word of F S , w is right extensible in S if and only if ♯(RC S (w) ∩ Σ) = 1 and w is left extensible in S if and only

Proposition 9

 9 S such that d S (w) = 0. We recall the notion of a suffix link (SL) for any node v of T (leaves included). Let sl(v) denote the node targeted by the suffix link of v, i.e. sl(v) = v[2 .. |v|]. By definition of a suffix tree, for all w ∈ F S , there exists a node v of T such that w is a prefix of v. Let v ′ the node of minimal length of T such that w is a prefix of v, then |v ′ | = |w| + d S (w), and therefore ⌈w⌉ S = v ′ . Let w ∈ F S . Then |⌈w⌉ S | ≥ |w| > | f (⌈w⌉ S )|, where f (⌈w⌉ S ) is the parent of ⌈w⌉ S in T .

7 2 7 5 6 5 bacbaaFigure 3 :

 553 Figure3: The GST for our running example and the constructed dBG for k := 2. Square nodes represent words that occur as a suffix of some s i , circle nodes are the other nodes of T . Grey nodes represent the vertices of the dBG. Each square node contains i j when it represents the suffix of s j starting at position i. The curved arrows are the edges of the dBG; those in dotted lines correspond to Case 1 and those in doubled lines to Case 2 (see p. 7).

4. 2

 2 Construction of DBG + k Let [x 1 ..x m ] be the set of k-mers of S. According to the definition of Init S,k and to Prop. 4, Init S,k = [⌈x 1 ⌉ S ..⌈x m ⌉ S ]. Thus, by Prop. 9, Init S,k = {v ∈ V T | | f (v)| < k and |v| ≥ k}. Similarly, InitExact S,k = {v ∈ V T | |v| = k}. Now, it appears clearly that InitExact S,k is a subset of Init S,k , since for all v ∈ V T , | f (v)| < |v|.

Figure 4 :

 4 Figure 4: Figures (a), (b) and (c) show Case 1 and Case 2 for the arcs of DBG + k . The grey node is v. The dashed arcs correspond to suffix links. The arcs of the dBG are in bold (a) for the Case 1 and in dotted lines (b) (c) for the Case 2.

Theorem 10

 10 For a set of words S, building the de Bruijn Graph of order k, DBG + k takes linear time and space in |T | or in S .

  Now, we can build integrally DBG +k or more exactly an isomorphic graph of DBG + k . Thus for simplicity, from now on we confound the graph we build with DBG + k . To do the same with CDBG + k , we need to characterise the concepts of right and left extensibility in terms of word properties. By the construction of DBG + k , we have the following results. Let w be a word of Init S,k . f irst k (w) is right extensible if and only if |w| > k or ♯(RC S (w) ∩ Σ) = 1. Let w be a word of Init S,k such that f irst k (w) is right extensible. Let the letter a be the unique element of RC S ( f irst k

	Proposition 6 Proposition 7

and there exists a unique outgoing arc of w: that from w to ⌈w[2 .. k]⌉ S . Indeed, by definition of Init S,k , ⌈w[2 .. k]⌉ S ∈ Init S,k , and thus Succ(w) = {⌈w[2 .. k]⌉ S }.

* This work is supported by ANR Colib'read (ANR-12-BS02-0008) and Défi MASTODONS SePhHaDe from CNRS.


Charles Burdet
email: charles.burdet@inserm.fr

Raphaël Lepeule

Xavier Duval

Marion Caseris

Christophe Rioux

Jean-Christophe Lucet

Yazdan Yazdanpanah

Quinolones versus macrolides in the treatment of legionellosis: a systematic review and meta-analysis

Keywords: Legionnaires-disease, Antimicrobial, Efficacy

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

Introduction

Legionella pneumophila [START_REF] Fields | Legionella and Legionnaires' disease: 25 years of investigation[END_REF] is the most common intracellular bacteria responsible for severe pneumonia. [START_REF] Blasi | Atypical pathogens and respiratory tract infections[END_REF] Its incidence was estimated to 1.2 per 100 000 inhabitants in 2010. [START_REF] Beaute | Legionnaires' disease in Europe, 2009-2010[END_REF] Risk factors include a male gender, a smoking habit, a history of chronic lung disease or immunosuppression, as well as travel and stay in large buildings, including hotels and hospitals. [START_REF] Fields | Legionella and Legionnaires' disease: 25 years of investigation[END_REF][START_REF] Greig | An outbreak of Legionnaires' disease at the Melbourne Aquarium, April 2000: investigation and case-control studies[END_REF][START_REF] Boer | A large outbreak of Legionnaires' disease at a flower show, the Netherlands[END_REF][START_REF] Che | Sporadic community-acquired Legionnaires' disease in France: a 2-year national matched case-control study[END_REF] Prognosis factors include appropriateness and timing of initial antimicrobial therapy. [START_REF] Viasus | Community-acquired Legionella pneumophila pneumonia: Single-centre experience with 214 hospitalised cases over 15 years[END_REF][START_REF] El-Ebiary | Prognostic factors of severe Legionella pneumonia requiring admission to ICU[END_REF] Legionellosis mostly presents as a mild-to-moderate disease. Severe systemic cases have been reported. [START_REF] De Lau | Acute disseminating encephalomyelitis following Legionnaires' disease[END_REF][START_REF] Antonarakis | An atypical complication of atypical pneumonia[END_REF][START_REF] Daumas | Acute tubulointerstitial nephritis complicating Legionnaires' disease: a case report[END_REF] The overall mortality has been estimated to 12%, [START_REF] Campese | Progress in the surveillance and control of Legionella infection in France, 1998-2008[END_REF] and to 15-20% in hospitalized patients. Mortality seems higher in nosocomial cases (15-40% versus 10-20% in community-acquired cases). [START_REF] Benin | Trends in legionnaires disease, 1980-1998: declining mortality and new patterns of diagnosis[END_REF] As a result, when initiating an empiric antimicrobial therapy for a severe pneumonia, current guidelines recommend to perform urinary diagnostic tests and to initiate a treatment for both Streptococcus pneumoniae, the most frequent bacteria involved in severe pneumonia, and Legionella spp. [START_REF] Mandell | Infectious Diseases Society of America/American Thoracic Society consensus guidelines on the management of communityacquired pneumonia in adults[END_REF][START_REF] Lim | BTS guidelines for the management of community acquired pneumonia in adults: update 2009[END_REF] Although erythromycin was the recommended treatment since the first reported outbreak of legionellosis, other agents have been developed. Recommended antimicrobials include quinolones and new macrolides. These recommendations are based on scarce data from in vitro and animal studies. Few data are available in humans and none allowed for a definitive conclusion. Consequently, the debate on which antimicrobial should be used in patients with legionellosis and/or to target Legionella spp. in patients with pneumonia is still ongoing.

No randomized clinical trial (RCT) has been performed for efficacy comparison. We performed a systematic review and meta-analysis to compare the clinical efficacy of a monotherapy of quinolone or macrolide in the treatment of legionellosis.

Material and methods

Data sources

Using Cochrane methodology, [START_REF] Higgins | Cochrane Handbook for Systematic Reviews of Interventions Version 5[END_REF] we conducted a systematic search of the literature. PubMed, Embase and the Cochrane Central Register of Controlled Trials databases were searched from 01/01/1985 to 01/31/2013. Search terms included: quinolone, fluoroquinolone, ofloxacin, ciprofloxacin, pefloxacin, trovafloxacin, levofloxacin, moxifloxacin, gatifloxacin, clinafloxacin, enoxacin, grepafloxacin, parfloxacin, norfloxacin, cinoxacin, macrolide, azithromycin, clarithromycin, erythromycin, spiramycin, roxithromycin. We also included related MeSH terms and Emtree entries. Two queries were performed. The first one ('legionellosis query', Table S1 as an example) aimed to identify studies providing data in legionellosis. In this query, 'legionella', 'legionnaire' and 'legionellosis' terms were added to those aforementioned. In the second query, all RCTs performed to compare antimicrobial efficacy in community-acquired pneumonia were searched ('RCTs in pneumonia query', Table S2 as an example). In this second query, the term 'pneumonia' was added.

Study selection

Title and abstract were independently assessed for eligibility by two authors (CB and RL).

Full text of eligible studies and congress abstracts were independently examined for final inclusion. The opinion of a third investigator (YY) was asked in case of disagreement.

Original studies providing data for comparison of the efficacy of quinolones and macrolides in legionellosis were included. In vitro and animal studies were excluded. Legionellosis diagnosis had to be proven using urinary antigen, serology, sputum or tracheal aspirate analyzed by culture or PCR.

Data extraction

Data were extracted using a standardized form: patient population, number of participating centres, number of patients included, antimicrobial agents and doses used, clinical outcomes, severity assessed by the Fine score and adverse effects.

Outcomes

Primary outcome was mortality in each treatment group. Secondary outcomes included clinical cure, time to apyrexia, length of hospital stay, occurrence of complications defined by studies' authors, need for mechanical ventilation and occurrence of adverse effects.

Risk of bias assessment

Risk of bias was assessed using the Newcastle-Ottawa scale. [START_REF] Wells | The Newcastle-Ottawa Scale (NOS) for assessing the quality of nonrandomised studies in meta-analyses[END_REF] This 8-item scale is suggested by the Cochrane collaboration for risk of bias assessment of nonrandomized studies. [START_REF] Higgins | Cochrane Handbook for Systematic Reviews of Interventions Version 5[END_REF] However we also used this scale for included RCTs.

Statistical analysis

The analysis focused on patients treated by antimicrobial monotherapy. β-lactams were not considered as effective anti-Legionella antimicrobials. We estimated pooled odds ratios and their 95% confidence intervals (95%CIs) comparing between quinolones and macrolides the probability of occurrence of qualitative outcomes. We estimated mean differences for time to apyrexia and length of hospital stay. Estimates were determined using a Mantel-Haenszel random effects model. [START_REF] Higgins | Cochrane Handbook for Systematic Reviews of Interventions Version 5[END_REF] Statistical heterogeneity was assessed using the chi-square test for heterogeneity and the I² statistic for measuring inconsistency. Analyses were performed using Review Manager v5.2 (Cochrane Collaboration, Oxford, United Kingdom).

Results

Identification of eligible studies

Databases queries identified 1005 articles and/or congress abstracts. Most were not eligible, and 96 full-text articles were retrieved and read for inclusion (Figure 1). Of those, 12 were finally included. All were original articles. [START_REF] Viasus | Community-acquired Legionella pneumophila pneumonia: Single-centre experience with 214 hospitalised cases over 15 years[END_REF][START_REF] Dournon | Comparison of the activity of three antibiotic regimens in severe Legionnaires' disease[END_REF][START_REF] Lode | Treatment of community-acquired pneumonia: A randomized comparison of sparfloxacin, amoxycillin-clavulanic acid and erythromycin[END_REF][START_REF] Gacouin | Severe pneumonia due to Legionella pneumophila: prognostic factors, impact of delayed appropriate antimicrobial therapy[END_REF][START_REF] Sokol | A prospective, double-blind, multicenter study comparing clarithromycin extended-release with trovafloxacin in patients with community-acquired pneumonia[END_REF][START_REF] Fogarty | Multicenter, Open-Label, Randomized Study to Compare the Safety and Efficacy of Levofloxacin versus Ceftriaxone Sodium and Erythromycin Followed by Clarithromycin and Amoxicillin-Clavulanate in the Treatment of Serious Community-Acquired Pneumonia in Adults[END_REF][START_REF] Garrido | Antimicrobial chemotherapy for Legionnaires' disease: levofloxacin versus macrolides[END_REF][START_REF] Querol-Ribelles | Levofloxacin versus ceftriaxone plus clarithromycin in the treatment of adults with community-acquired pneumonia requiring hospitalization[END_REF][START_REF] Sabria | Fluoroquinolones vs macrolides in the treatment of Legionnaires' disease[END_REF][START_REF] Haranaga | Intravenous ciprofloxacin versus erythromycin in the treatment of Legionella pneumonia[END_REF][START_REF] Nakamura | The clinical efficacy of fluoroquinolone and macrolide combination therapy compared with single-agent therapy against community-acquired pneumonia caused by Legionella pneumophila[END_REF][START_REF] Griffin | Macrolides versus quinolones in Legionella pneumonia: results from the Community-Acquired Pneumonia Organization international study[END_REF] Nine were observational cohort studies, [START_REF] Viasus | Community-acquired Legionella pneumophila pneumonia: Single-centre experience with 214 hospitalised cases over 15 years[END_REF][START_REF] Dournon | Comparison of the activity of three antibiotic regimens in severe Legionnaires' disease[END_REF][START_REF] Gacouin | Severe pneumonia due to Legionella pneumophila: prognostic factors, impact of delayed appropriate antimicrobial therapy[END_REF][START_REF] Garrido | Antimicrobial chemotherapy for Legionnaires' disease: levofloxacin versus macrolides[END_REF][START_REF] Querol-Ribelles | Levofloxacin versus ceftriaxone plus clarithromycin in the treatment of adults with community-acquired pneumonia requiring hospitalization[END_REF][START_REF] Sabria | Fluoroquinolones vs macrolides in the treatment of Legionnaires' disease[END_REF][START_REF] Haranaga | Intravenous ciprofloxacin versus erythromycin in the treatment of Legionella pneumonia[END_REF][START_REF] Nakamura | The clinical efficacy of fluoroquinolone and macrolide combination therapy compared with single-agent therapy against community-acquired pneumonia caused by Legionella pneumophila[END_REF][START_REF] Griffin | Macrolides versus quinolones in Legionella pneumonia: results from the Community-Acquired Pneumonia Organization international study[END_REF] of which six were retrospective. [START_REF] Dournon | Comparison of the activity of three antibiotic regimens in severe Legionnaires' disease[END_REF][START_REF] Gacouin | Severe pneumonia due to Legionella pneumophila: prognostic factors, impact of delayed appropriate antimicrobial therapy[END_REF][START_REF] Garrido | Antimicrobial chemotherapy for Legionnaires' disease: levofloxacin versus macrolides[END_REF][START_REF] Haranaga | Intravenous ciprofloxacin versus erythromycin in the treatment of Legionella pneumonia[END_REF][START_REF] Nakamura | The clinical efficacy of fluoroquinolone and macrolide combination therapy compared with single-agent therapy against community-acquired pneumonia caused by Legionella pneumophila[END_REF][START_REF] Griffin | Macrolides versus quinolones in Legionella pneumonia: results from the Community-Acquired Pneumonia Organization international study[END_REF] They were performed in Spain (n=4), [START_REF] Viasus | Community-acquired Legionella pneumophila pneumonia: Single-centre experience with 214 hospitalised cases over 15 years[END_REF][START_REF] Garrido | Antimicrobial chemotherapy for Legionnaires' disease: levofloxacin versus macrolides[END_REF][START_REF] Querol-Ribelles | Levofloxacin versus ceftriaxone plus clarithromycin in the treatment of adults with community-acquired pneumonia requiring hospitalization[END_REF][START_REF] Sabria | Fluoroquinolones vs macrolides in the treatment of Legionnaires' disease[END_REF] in France (n=2), [START_REF] Dournon | Comparison of the activity of three antibiotic regimens in severe Legionnaires' disease[END_REF][START_REF] Gacouin | Severe pneumonia due to Legionella pneumophila: prognostic factors, impact of delayed appropriate antimicrobial therapy[END_REF] and Japan (n=2). [START_REF] Haranaga | Intravenous ciprofloxacin versus erythromycin in the treatment of Legionella pneumonia[END_REF][START_REF] Nakamura | The clinical efficacy of fluoroquinolone and macrolide combination therapy compared with single-agent therapy against community-acquired pneumonia caused by Legionella pneumophila[END_REF] One was international. [START_REF] Griffin | Macrolides versus quinolones in Legionella pneumonia: results from the Community-Acquired Pneumonia Organization international study[END_REF] The three remaining studies were RCTs conducted in patients with pneumonia. [START_REF] Lode | Treatment of community-acquired pneumonia: A randomized comparison of sparfloxacin, amoxycillin-clavulanic acid and erythromycin[END_REF][START_REF] Sokol | A prospective, double-blind, multicenter study comparing clarithromycin extended-release with trovafloxacin in patients with community-acquired pneumonia[END_REF][START_REF] Fogarty | Multicenter, Open-Label, Randomized Study to Compare the Safety and Efficacy of Levofloxacin versus Ceftriaxone Sodium and Erythromycin Followed by Clarithromycin and Amoxicillin-Clavulanate in the Treatment of Serious Community-Acquired Pneumonia in Adults[END_REF] Two of them were performed in the USA, [START_REF] Sokol | A prospective, double-blind, multicenter study comparing clarithromycin extended-release with trovafloxacin in patients with community-acquired pneumonia[END_REF][START_REF] Fogarty | Multicenter, Open-Label, Randomized Study to Compare the Safety and Efficacy of Levofloxacin versus Ceftriaxone Sodium and Erythromycin Followed by Clarithromycin and Amoxicillin-Clavulanate in the Treatment of Serious Community-Acquired Pneumonia in Adults[END_REF] the third was international. [START_REF] Lode | Treatment of community-acquired pneumonia: A randomized comparison of sparfloxacin, amoxycillin-clavulanic acid and erythromycin[END_REF] Five of the 12 studies were conducted in a single centre. [START_REF] Viasus | Community-acquired Legionella pneumophila pneumonia: Single-centre experience with 214 hospitalised cases over 15 years[END_REF][START_REF] Gacouin | Severe pneumonia due to Legionella pneumophila: prognostic factors, impact of delayed appropriate antimicrobial therapy[END_REF][START_REF] Garrido | Antimicrobial chemotherapy for Legionnaires' disease: levofloxacin versus macrolides[END_REF][START_REF] Querol-Ribelles | Levofloxacin versus ceftriaxone plus clarithromycin in the treatment of adults with community-acquired pneumonia requiring hospitalization[END_REF][START_REF] Haranaga | Intravenous ciprofloxacin versus erythromycin in the treatment of Legionella pneumonia[END_REF]

Risk of bias

Overall risk of bias is represented in Figure S1. Representativeness of general population was satisfactory. Patients included in observational studies were all patients with a proven diagnosis of legionellosis presenting in participating centres. Patients included in RCTs were representative of immunocompetent patients with community-acquired pneumonia.

Ascertainment of therapy was performed using medical records or specific forms. All outcomes were prespecified and assessed using medical records or form completion. Follow up was adequate and long enough to ensure their assessment.

With the exception that by Dournon et al., [START_REF] Dournon | Comparison of the activity of three antibiotic regimens in severe Legionnaires' disease[END_REF] no observational study controlled for confounding. Dournon et al. matched quinolone-treated patients with erythromycin-treated patient for age, duration of Legionnaires' disease, immune status and requirement of mechanical ventilation. Patients treated with quinolone who received co-treatment with rifampicin and/or erythromycin were excluded from their analysis. Two RCTs did not stratify the randomization, [START_REF] Lode | Treatment of community-acquired pneumonia: A randomized comparison of sparfloxacin, amoxycillin-clavulanic acid and erythromycin[END_REF][START_REF] Sokol | A prospective, double-blind, multicenter study comparing clarithromycin extended-release with trovafloxacin in patients with community-acquired pneumonia[END_REF] and the other one stratified randomization on centre. [START_REF] Fogarty | Multicenter, Open-Label, Randomized Study to Compare the Safety and Efficacy of Levofloxacin versus Ceftriaxone Sodium and Erythromycin Followed by Clarithromycin and Amoxicillin-Clavulanate in the Treatment of Serious Community-Acquired Pneumonia in Adults[END_REF]

Patient characteristics in included studies

Overall, 879 patients with legionellosis were included (10 to 292 patients per study).

Mean age was 58.3 years, and 27.7% of patients were women (n=223/806). All patients were hospitalized at baseline, 55.1% (n=411/746) had an underlying disease, 19.8% (n=89/449) had a chronic obstructive pulmonary disease, and 65.9% (n=270/410) had a smoking habit.

Data on immunosuppression was available in only 2 studies. [START_REF] Dournon | Comparison of the activity of three antibiotic regimens in severe Legionnaires' disease[END_REF][START_REF] Nakamura | The clinical efficacy of fluoroquinolone and macrolide combination therapy compared with single-agent therapy against community-acquired pneumonia caused by Legionella pneumophila[END_REF] In those, 63.6% (n=14/22) and 75% (n=45/60) of patients were immunocompromised. The Fine score was ≥ 4 in 35.8% (n=213/595). [START_REF] Viasus | Community-acquired Legionella pneumophila pneumonia: Single-centre experience with 214 hospitalised cases over 15 years[END_REF][START_REF] Garrido | Antimicrobial chemotherapy for Legionnaires' disease: levofloxacin versus macrolides[END_REF][START_REF] Haranaga | Intravenous ciprofloxacin versus erythromycin in the treatment of Legionella pneumonia[END_REF][START_REF] Nakamura | The clinical efficacy of fluoroquinolone and macrolide combination therapy compared with single-agent therapy against community-acquired pneumonia caused by Legionella pneumophila[END_REF][START_REF] Griffin | Macrolides versus quinolones in Legionella pneumonia: results from the Community-Acquired Pneumonia Organization international study[END_REF] Overall, 71 of the 879 patients with legionellosis enrolled in included studies (8.1%) died during follow up.

687 patients with legionellosis were treated with a quinolone (n=377, 54.9%) or macrolide (n=310, 45.1%) monotherapy (Table 1). In studies providing the information, 26.0% (n=47/181) of quinolone-treated patients had a Fine score ≥ 4, versus 32.7% (n=36/110) of patients in the macrolide group. [START_REF] Garrido | Antimicrobial chemotherapy for Legionnaires' disease: levofloxacin versus macrolides[END_REF][START_REF] Haranaga | Intravenous ciprofloxacin versus erythromycin in the treatment of Legionella pneumonia[END_REF][START_REF] Nakamura | The clinical efficacy of fluoroquinolone and macrolide combination therapy compared with single-agent therapy against community-acquired pneumonia caused by Legionella pneumophila[END_REF][START_REF] Griffin | Macrolides versus quinolones in Legionella pneumonia: results from the Community-Acquired Pneumonia Organization international study[END_REF] Outcomes Mortality was reported in 8 studies (Figure 2A). [START_REF] Dournon | Comparison of the activity of three antibiotic regimens in severe Legionnaires' disease[END_REF][START_REF] Gacouin | Severe pneumonia due to Legionella pneumophila: prognostic factors, impact of delayed appropriate antimicrobial therapy[END_REF][START_REF] Garrido | Antimicrobial chemotherapy for Legionnaires' disease: levofloxacin versus macrolides[END_REF][START_REF] Querol-Ribelles | Levofloxacin versus ceftriaxone plus clarithromycin in the treatment of adults with community-acquired pneumonia requiring hospitalization[END_REF][START_REF] Sabria | Fluoroquinolones vs macrolides in the treatment of Legionnaires' disease[END_REF][START_REF] Haranaga | Intravenous ciprofloxacin versus erythromycin in the treatment of Legionella pneumonia[END_REF][START_REF] Nakamura | The clinical efficacy of fluoroquinolone and macrolide combination therapy compared with single-agent therapy against community-acquired pneumonia caused by Legionella pneumophila[END_REF][START_REF] Griffin | Macrolides versus quinolones in Legionella pneumonia: results from the Community-Acquired Pneumonia Organization international study[END_REF] Overall mortality occurred in 10.9% of patients treated with a macrolide (n=23/211) versus 4.0% of patients treated with a quinolone (n=10/253). The combined odds ratio of death when treated with quinolones versus macrolides was 0.5 [95%CI, 0.2; 1.3].

Clinical cure was evaluated in 4 studies. [START_REF] Lode | Treatment of community-acquired pneumonia: A randomized comparison of sparfloxacin, amoxycillin-clavulanic acid and erythromycin[END_REF][START_REF] Sokol | A prospective, double-blind, multicenter study comparing clarithromycin extended-release with trovafloxacin in patients with community-acquired pneumonia[END_REF][START_REF] Fogarty | Multicenter, Open-Label, Randomized Study to Compare the Safety and Efficacy of Levofloxacin versus Ceftriaxone Sodium and Erythromycin Followed by Clarithromycin and Amoxicillin-Clavulanate in the Treatment of Serious Community-Acquired Pneumonia in Adults[END_REF][START_REF] Garrido | Antimicrobial chemotherapy for Legionnaires' disease: levofloxacin versus macrolides[END_REF] It was defined as resolution of signs and symptoms of pneumonia at the test-of-cure visit, performed depending on studies between day 1 and day 21 after the end of antimicrobial therapy. One study did not provide clinical cure definition. [START_REF] Garrido | Antimicrobial chemotherapy for Legionnaires' disease: levofloxacin versus macrolides[END_REF] Clinical cure was observed in 100% of patients in 2 studies, [START_REF] Lode | Treatment of community-acquired pneumonia: A randomized comparison of sparfloxacin, amoxycillin-clavulanic acid and erythromycin[END_REF][START_REF] Sokol | A prospective, double-blind, multicenter study comparing clarithromycin extended-release with trovafloxacin in patients with community-acquired pneumonia[END_REF] which could not be used for computations. In the 2 other studies, the pooled odds ratio of clinical cure for treatment with a quinolone versus a macrolide was 2.3 [95%CI, 0.3; 16.9] (Figure 2B). [START_REF] Fogarty | Multicenter, Open-Label, Randomized Study to Compare the Safety and Efficacy of Levofloxacin versus Ceftriaxone Sodium and Erythromycin Followed by Clarithromycin and Amoxicillin-Clavulanate in the Treatment of Serious Community-Acquired Pneumonia in Adults[END_REF][START_REF] Garrido | Antimicrobial chemotherapy for Legionnaires' disease: levofloxacin versus macrolides[END_REF] One study provided data for analysis of time to apyrexia. [START_REF] Garrido | Antimicrobial chemotherapy for Legionnaires' disease: levofloxacin versus macrolides[END_REF] The time to apyrexia was shorter with quinolones than with macrolides, but the difference was not significant (mean difference, -4.8 hours [95%CI, -22.1; 12.5], Figure 2C). Three studies were available for the comparison of length of hospital-stay (Figure 2D). [START_REF] Garrido | Antimicrobial chemotherapy for Legionnaires' disease: levofloxacin versus macrolides[END_REF][START_REF] Nakamura | The clinical efficacy of fluoroquinolone and macrolide combination therapy compared with single-agent therapy against community-acquired pneumonia caused by Legionella pneumophila[END_REF][START_REF] Griffin | Macrolides versus quinolones in Legionella pneumonia: results from the Community-Acquired Pneumonia Organization international study[END_REF] One of them showed a significant reduction of the length of hospital-stay with quinolones versus macrolides (-2.8, 95%CI, -5.4; -0.2). [START_REF] Garrido | Antimicrobial chemotherapy for Legionnaires' disease: levofloxacin versus macrolides[END_REF] We found an overall significant mean reduction of 3.0 days with quinolones versus macrolides (95%CI, -5.3; -0.7). Test for heterogeneity was not significant (I²=0%, p=0.9).

Two studies were included in the analysis of complications (Figure 2E). [START_REF] Garrido | Antimicrobial chemotherapy for Legionnaires' disease: levofloxacin versus macrolides[END_REF][START_REF] Sabria | Fluoroquinolones vs macrolides in the treatment of Legionnaires' disease[END_REF] These studies defined complicated legionellosis either as the apparition of pleural effusion, empyema, mechanical ventilation or septic shock; [START_REF] Sabria | Fluoroquinolones vs macrolides in the treatment of Legionnaires' disease[END_REF] or renal failure, pleural effusion or admission to ICU. [START_REF] Garrido | Antimicrobial chemotherapy for Legionnaires' disease: levofloxacin versus macrolides[END_REF] The combined odds ratio of complications when treated with quinolones versus macrolides, was 0.5 [95%CI, 0.1; 1.6]).

Adverse effects

In the only study providing data on adverse events, [START_REF] Garrido | Antimicrobial chemotherapy for Legionnaires' disease: levofloxacin versus macrolides[END_REF] the three main reported events were gastrointestinal events (5 -7%), liver abnormalities (2 -3%) and phlebitis, which occurred more frequently in patients receiving clarithromycin than in those under levofloxacin therapy (p<0.01).

Discussion

This is the first systematic review and meta-analysis of the effectiveness of quinolones versus macrolides in the treatment of legionellosis. We found that despite a small number of studies addressing this issue in clinical settingsand a small number of patients in each study quinolones seem to have a higher effectiveness than macrolides. Quinolone therapy was significantly associated with a shorter length of hospital-stay, and we observed a trend toward a reduced mortality, a higher clinical cure, a lower time to apyrexia, and a lower rate of complications in patients receiving a quinolone.

Our analysis is unique. Published reviews on this topic did not use a systematic methodology for studies inclusion and results analysis. [START_REF] Ml | Treatment strategies for Legionella infection[END_REF][START_REF] Yu | Legionella: macrolides or quinolones?[END_REF] In the absence of RCTs, the type of analysis we conducted is the most accurate way to compare quinolones and macrolides effectiveness in patients with legionellosis and to improve management of this disease. This question has been investigated in experimental models. In all but one of the 19 intracellular models reviewed by Pedro-Botet and Yu, quinolones had a higher activity on Legionella pneumophila than macrolides. [START_REF] Ml | Treatment strategies for Legionella infection[END_REF] Levofloxacin was the most effective quinolone and azithromycin the most effective macrolide. In animal models of Legionella pneumophila infection, treatment with quinolones resulted in an increased survival. [START_REF] Ml | Treatment strategies for Legionella infection[END_REF] However, these experimental results may not be generalisable to humans. Despite a non-significant difference, results for all studied outcomes favoured quinolones. The absence of significance in these comparisons may be related to a lack of statistical power. However, none of the included studies attempted to control for confounding.

Patients treated with macrolides had higher severity of disease. This might favour quinolones.

Moreover, the macrolide agent used was mostly erythromycin, which is not the most effective macrolide agent as observed in in vitro studies. [START_REF] Ml | Treatment strategies for Legionella infection[END_REF] It was the only macrolide used in the study performed by Dournon et al, [START_REF] Dournon | Comparison of the activity of three antibiotic regimens in severe Legionnaires' disease[END_REF] in which the number of deaths in the macrolide group accounted for 40% of overall deaths observed in our review, and with a mortality rate of 50% in this group. This study has some other limitations. First, statistical methodology is limited by the observational design of most included studies. RCTs were not designed for a proper analysis in legionellosis. We used random effects modelling to limit inherent bias. Moreover, our results are strengthened by the absence of heterogeneity. Second, a small number of studies were included. Legionellosis is a rare disease. The systematic strategy used for inclusion aimed to minimize misidentifications and to limit publication bias. However, reporting bias is a recurrent problem in systematic reviews and unpublished work could not be retrieved by our search strategy. Third, we were not able to perform subgroup analysis and/or to adjust on disease severity or prognosis factors. Finally, we could not perform a face-to-face comparison of individual quinolones and macrolides as individual data were not available.

In light of our results, should we prefer quinolones or macrolides when treating a patient with a proven Legionella pneumonia? Our analysis does not provide a high level of evidence for conclusion. When answering this thorny question, risks associated with the administration of these antimicrobials should be considered. Quinolones are generally welltolerated drugs; serious adverse events are rare. There is a rare risk of cardiac toxicity with macrolides, but azithromycin is generally considered to be free of serious adverse effects. [START_REF] Svanstrom | Use of azithromycin and death from cardiovascular causes[END_REF][START_REF] Shehab | Emergency department visits for antibioticassociated adverse events[END_REF][START_REF] Corrao | Evidence of tendinitis provoked by fluoroquinolone treatment: a case-control study[END_REF] Both quinolones and macrolides have been associated with an increased risk of developing a Clostridium difficile infection, with a higher risk for quinolones. [START_REF] Brown | Meta-analysis of antibiotics and the risk of community-associated Clostridium difficile infection[END_REF] The emergence of bacterial resistance in the digestive microbiota has been documented with quinolones, [START_REF] Fantin | Ciprofloxacin dosage and emergence of resistance in human commensal bacteria[END_REF] but such consideration should not restrain their use when treating a potentially fatal infection.

We believe that quinolones might be preferred for proven legionellosis, especially in patients with severe legionellosis. Empirical antimicrobial therapy for patients with severe pneumonia might benefit of a combination of a β-lactam and a quinolone, when a Legionella infection is suspected. However, in patients with mild pneumonia from uncertain origin, the potential negative impact of quinolones on the digestive microbiota should be balanced with their possible higher efficacy than macrolides. This analysis should be confirmed by an international trial. With almost 5000 cases reported in Europe by the European Legionnaires' Disease Surveillance Network in 2011, [START_REF] Ecdc | Legionnaires' disease in Europe[END_REF]

Total (95% CI)

Total events Heterogeneity: Tau² = 0.00; Chi² = 0.83, df = 1 (P = 0.36); I² = 0% Test for overall effect: Z = 0.85 (P = 0.39)

Events
Q M Q M Q M Q M Q M Q M Q M Q M Q M Q M Q M

  We searched additional references among the following scientific conferences from 2000 to 2012: Interscience Conference on Antimicrobial Agents and Chemotherapy, European Congress of Clinical Microbiology and Infectious Diseases, Infectious Disease Society of America and American Thoracic Society. Search terms included: 'legionella', 'legionnaire' and 'legionellosis'.

  such trial would bring a definitive conclusion to the recurrent question of antimicrobial selection in Flowchart of studies inclusion. RCTs, randomized controlled trials.Figure 2. Comparison of quinolones and macrolides effectiveness in Legionella pneumonia.A, analysis of mortality; B, analysis of clinical cure; C, analysis of the time to apyrexia (hours); D, analysis of length of hospital stay (days); E, analysis of the occurrence of complications.

	Figures
	Figure 1. 808 records identified through			242 records identified through
	the 'legionellosis' query Quinolones	Macrolides	the 'RCTs in pneumonia' query Odds Ratio	Odds Ratio
	Study or Subgroup	Events	Total	Events	Total	Weight	M-H, Random, 95% CI	M-H, Random, 95% CI
	Dournon 1990	2	7	10	20	20.9%	0.40 [0.06, 2.57]
	Gacouin 2002	2	3	2	2	5.4%	0.33 [0.01, 12.82]
	Blazquez-Garrido 2005	1	143	0	65	7.0%	1.38 [0.06, 34.30]
	Querol-Ribelles 2005	0	8	1	3	5.9%	0.10 [0.00, 3.24]
	Sabria 2005 Haranaga 2006	3 1005 records screened after 54 6 76 35.3% 0 9 2 18 7.3%	0.69 [0.16, 2.87] 0.35 [0.02, 8.02]
	Nakamura 2009	1	duplicates removed 12 0 4	6.3%	1.17 [0.04, 34.52]
	Griffin 2010	1	17	2	23	11.7%	0.66 [0.05, 7.89]
	Total (95% CI)		253		211	100.0%	0.54 [0.23, 1.26]
	Total events Heterogeneity: Tau² = 0.00; Chi² = 1.82, df = 7 (P = 0.97); I² = 0% 10 23 Test for overall effect: Z = 1.42 (P = 0.16)	909 records excluded: -review, n=480 -not a comparative study, n=202 0.01 Favours Quinolones Favours Macrolides 0.1 1 10 100
							-not a clinical study, n=175
							-not a study in legionellosis or pneumonia, n=52
	Study or Subgroup
	Fogarty 2004
	Blazquez-Garrido 2005		96 full-text articles
			assessed for eligibility
							84 full-text articles excluded:
							-no comparison in legionellosis, n=49
							-no data for comparison of quinolones and macrolides, n=32
							-not a original study, n=2
							-congress abstract published as article, n=1
			12 studies included
			in analysis
	Legionella pneumonia.

Table 365 Table 1 .

 3651 Main characteristics and outcomes of the studies included in the analysis according to monotherapy treatment group. AZM, 366 azithromycin; CIP, ciprofloxacin; CLR, clarithromycin; ERY, erythromycin; LVX, levofloxacin; RXM, roxithromycin; M, macrolide 367 monotherapy; OFX, ofloxacin; PEF, pefloxacin; PAZ, pazufloxacin; Q, quinolone monotherapy; SD, standard deviation; SPX, sparfloxacin; 368 TVA, trovafloxacin. Missing data of presented variables were not available in the corresponding studies. 369 370

	Study	Enrolment period	Number of patients with legionellosis	Agent(s) used (n)	Mean age (years)	Proportion of women (%)	Underlying disease, n (%)	Fine score ≥4, n (%)	Overall mortality, n (%)	Mean time to apyrexia, hours (SD)	Mean hospital stay, days (SD)	Secondary complication, n (%)	Clinical cure, n (%)

Funding

This study was supported by internal funding.

Meetings

This work has been presented in the 53rd Interscience Conference on Antimicrobial Agents and Chemotherapy, held in Denver, USA, from 10 to 13 September 2013 (Poster L-1319).

This work has been presented in the 15th Journées Nationales d'Infectiologie, held in Bordeaux, France, from 11 to 13 June 2014 (Poster I-07).

Transparency declaration

Pr. Yazdanpanah has received travel grants, honoraria for presentation at workshops, and consultancy honoraria from Bristol-Myers Squibb, Gilead, Merck, Pfizer, Roche, Tibotec, and ViiV Healthcare.

Other authors reported no conflict of interest.


Bruno Conejo
email: bconejo@caltech.edu

Nikos Komodakis
email: nikos.komodakis@enpc.fr

Sebastien Leprince
email: leprincs@caltech.edu

Jean Philippe Avouac
email: avouac@gps.caltech.edu

Inference by Learning: Speeding-up Graphical Model Optimization via a Coarse-to-Fine Cascade of Pruning Classifiers

.

Introduction

Graphical models in computer vision Optimization of undirected graphical models such as Markov Random Fields, MRF, or Conditional Random Fields, CRF, is of fundamental importance in computer vision. Currently, a wide spectrum of problems including stereo matching [START_REF] Meltzer | Globally optimal solutions for energy minimization in stereo vision using reweighted belief propagation[END_REF][START_REF] Kim | Visual correspondence using energy minimization and mutual information[END_REF], optical flow estimation [START_REF] Roth | Fields of experts: a framework for learning image priors[END_REF][START_REF] Kohlberger | Domain decomposition for variational optical-flow computation[END_REF], image segmentation [START_REF] Kumar | Obj cut. In CVPR[END_REF][START_REF] Kim | Image segmentation using higher-order correlation clustering[END_REF], image completion and denoising [START_REF] Freeman | Learning low-level vision[END_REF], or, object recognition [START_REF] Felzenszwalb | Pictorial structures for object recognition[END_REF][START_REF] Bergtholdt | A study of parts-based object class detection using complete graphs[END_REF] rely on finding the mode of the distribution associated to the random field, i.e., the Maximum A Posteriori (MAP) solution. The MAP estimation, often referred as the labeling problem, is posed as an energy minimization task. While this task is NP-Hard, strong optimum solutions or even the optimal solutions can be obtained [START_REF] Boykov | Fast approximate energy minimization via graph cuts[END_REF]. Over the past 20 years, tremendous progress has been made in term of computational cost, and, many different techniques have been developed such as move making approaches [START_REF] Boykov | Fast approximate energy minimization via graph cuts[END_REF][START_REF] Kolmogorov | What energy functions can be minimized via graph cuts?[END_REF][START_REF] Kumar | Map estimation of semi-metric mrfs via hierarchical graph cuts[END_REF][START_REF] Komodakis | Fast, approximately optimal solutions for single and dynamic mrfs[END_REF][START_REF] Rother | Optimizing binary mrfs via extended roof duality[END_REF], and message passing methods [START_REF] Felzenszwalb | Efficient belief propagation for early vision[END_REF][START_REF] Wainwright | Map estimation via agreement on trees: messagepassing and linear programming[END_REF][START_REF] Kolmogorov | Convergent tree-reweighted message passing for energy minimization[END_REF][START_REF] Komodakis | Mrf optimization via dual decomposition: Message-passing revisited[END_REF]. A review of their effectiveness has been published in [START_REF] Szeliski | A comparative study of energy minimization methods for markov random fields with smoothness-based priors[END_REF][START_REF] Kappes | A comparative study of modern inference techniques for discrete energy minimization problems[END_REF]. Nevertheless, the ever increasing dimensionality of the problems and the need for larger solution space greatly challenge these tech-niques as even the best ones have a highly super-linear computational cost and memory requirement relatively to the dimensionality of the problem.

Our goal in this work is to develop a general MRF optimization framework that can provide a significant speed-up for such methods while maintaining the accuracy of the estimated solutions. Our strategy for accomplishing this goal will be to gradually reduce (by a significant amount) the size of the discrete state space via exploiting the fact that an optimal labeling is typically far from being random. Indeed, most MRF optimization problems favor solutions that are piecewise smooth. In fact, this spatial structure of the MAP solution has already been exploited in prior work to reduce the dimensionality of the solution space.

Related work A first set of methods of this type, referred here for short as the super-pixel approach [START_REF] Shi | Normalized cuts and image segmentation[END_REF], defines a grouping heuristic to merge many random variables together in super-pixels. The grouping heuristic can be energy-aware if it is based on the energy to minimize as in [START_REF] Kim | Variable grouping for energy minimization[END_REF], or, energyagnostic otherwise as in [START_REF] Felzenszwalb | Efficient graph-based image segmentation[END_REF][START_REF] Shi | Normalized cuts and image segmentation[END_REF]. All random variables belonging to the same super-pixel are forced to take the same label. This restricts the solution space and results in an optimization speed-up as a smaller number of variables needs to be optimized. The super-pixel approach has been applied with segmentation, stereo and object recognition [START_REF] Kim | Variable grouping for energy minimization[END_REF]. However, if the grouping heuristic merges variables that should have a different label in the MAP solution, only an approximate labeling is computed. In practice, defining general yet efficient grouping heuristics is difficult. This represents the key limitation of super-pixel approaches.

One way to overcome this limitation is to mimic the multi-scale scheme used in continuous optimization by building a coarse to fine representation of the graphical model. Similarly to the superpixel approach, such a multi-scale method, relies again on a grouping of variables for building the required coarse to fine representation [START_REF] Kohli | Uncertainty driven multi-scale optimization[END_REF][START_REF] Lombaert | A multilevel banded graph cuts method for fast image segmentation[END_REF][START_REF] Perez | Restriction of a markov random field on a graph and multiresolution statistical image modeling[END_REF]. However, contrary to the super-pixel approach, if the grouping merges variables that should have a different label in the MAP solution, there always exists a scale at which these variables are not grouped. This property thus ensures that the MAP solution can still be recovered. Nevertheless, in order to manage a significant speed-up of the optimization, the multi-scale approach also needs to progressively reduce the number of labels per random variable (i.e., the solution space). Typically, this is achieved by use, for instance, of a heuristic that keeps only a small fixed number of labels around the optimal label of each node found at the current scale, while pruning all other labels, which are therefore not considered thereafter [START_REF] Conejo | Fast global stereo matching via energy pyramid minimization[END_REF]. This strategy, however, may not be optimal or even valid for all types of problems. Furthermore, such a pruning heuristic is totally inappropriate (and can thus lead to errors) for nodes located along discontinuity boundaries of an optimal solution, where such boundaries are always expected to exist in practice. An alternative strategy followed by some other methods relies on selecting a subset of the MRF nodes at each scale (based on some criterion) and then fixing their labels according to the optimal solution estimated at the current scale (essentially, such methods contract the entire label set of a node to a single label). However, such a fixing strategy may be too aggressive and can also easily lead to eliminating good labels.

Proposed approach Our method simultaneously makes use of the following two strategies for speeding-up the MRF optimization process:

(i) it solves the problem through a multi-scale approach that gradually refines the MAP estimation based on a coarse-to-fine representation of the graphical model, (ii) and, at the same time, it progressively reduces the label space of each variable by cleverly utilizing the information computed during the above coarse-to-fine process.

To achieve that, we propose to significantly revisit the way that the pruning of the solution space takes place. More specifically:

(i) we make use of and incorporate into the above process a fine-grained pruning scheme that allows an arbitrary subset of labels to be discarded, where this subset can be different for each node, (ii) additionally, and most importantly, instead of trying to manually come up with some criteria for deciding what labels to prune or keep, we introduce the idea of relying entirely on a sequence of trained classifiers for taking such decisions, where different classifiers per scale are used.

We name such an approach Inference by Learning, and show that it is particularly efficient and effective in reducing the label space while omitting very few correct labels. Furthermore, we demonstrate that the training of these classifiers can be done based on features that are not application specific but depend solely on the energy function, which thus makes our approach generic and applicable to any MRF problem. The end result of this process is to obtain both an important speed-up and a significant decrease in memory consumption as the solution space is progressively reduced. Furthermore, as each scale refines the MAP estimation, a further speed-up is obtained as a result of a warm-start initialization that can be used when transitioning between different scales.

Before proceeding, it is worth also noting that there exists a body of prior work [START_REF] Shekhovtsov | Maximum persistency in energy minimization[END_REF] that focuses on fixing the labels of a subset of nodes of the graphical model by searching for a partial labeling with the so-called persistency property (which means that this labeling is provably guaranteed to be part of an optimal solution). However, finding such a set of persistent variables is typically very time consuming. Furthermore, in many cases only a limited number of these variables can be detected. As a result, the focus of these works is entirely different from ours, since the main motivation in our case is how to obtain a significant speed-up for the optimization.

Hereafter, we assume without loss of generality that the graphical model is a discrete pairwise CRF/MRF. However, one can straightforwardly apply our approach to higher order models.

Outline of the paper We briefly review the optimization problem related to a discrete pairwise MRF and introduce the necessary notations in section 2. We describe our general multi-scale pruning framework in section 3. We explain how classifiers are trained in section 4. Experimental results and their analysis are presented in 5. Finally, we conclude the paper in section 6.

Notation and preliminaries

To represent a discrete MRF model M, we use the following notation

M = V, E, L, {φ i } i∈V , {φ ij } (i,j)∈E . (1)
Here V and E represent respectively the nodes and edges of a graph, and L represents a discrete label set. Furthermore, for every i ∈ V and (i, j) ∈ E, the functions φ i : L → R and φ ij : L 2 → R represent respectively unary and pairwise costs (that are also known connectively as MRF potentials φ = {φ i } i∈V , {φ ij } (i,j)∈E ). A solution x = (x i ) i∈V of this model consists of one variable per vertex i, taking values in the label set L, and the total cost (energy) E(x|M) of such a solution is

E(x|M) = i∈V φ i (x i ) + (i,j)∈E φ ij (x i , x j ) .
The goal of MAP estimation is to find a solution that has minimum energy, i.e., computes

x MAP = arg min x∈L |V| E(x|M) .
The above minimization takes place over the full solution space of model M, which is L |V| . Here we will also make use of a pruned solution space S(M, A), which is defined based on a binary function A : V × L → {0, 1} (referred to as the pruning matrix hereafter) that specifies the status (active or pruned) of a label for a given vertex, i.e.,

A(i, l) = 1 if label l is active at vertex i 0 if label l is pruned at vertex i (2)
During optimization, active labels are retained while pruned labels are discarded. Based on a given A, the corresponding pruned solution space of model M is defined as

S(M, A) = x ∈ L |V| | (∀i), A(i, x i ) = 1 .

Multiscale Inference by Learning

In this section we describe the overall structure of our MAP estimation framework, beginning by explaining how to construct the coarse-to-fine representation of the input graphical model.

Model coarsening

Given a model M (defined as in ( 1)), we wish to create a "coarser" version of this model

M ′ = V ′ , E ′ , L, {φ ′ i } i∈V ′ , {φ ′ ij } (i,j)∈E ′ .
Intuitively, we want to partition the nodes of M into groups, and treat each group as a single node of the coarser model M ′ (the implicit assumption is that nodes of M that are grouped together are assigned the same label). To that end, we will make use of a grouping function g : V → N . The nodes and edges of the coarser model are then defined as follows

E ′ . V ′ = {i ′ | ∃i ∈ V, i ′ = g(i)} , (3)
E ′ = {(i ′ , j ′ ) | ∃(i, j) ∈ E, i ′ = g(i), j ′ = g(j), i ′ = j ′ } . (4)
Furthermore, the unary and pairwise potentials of M ′ are given by

(∀i ′ ∈ V ′ ), φ ′ i ′ (l) = i∈V|i ′ =g(i) φ i (l) + (i,j)∈E|i ′ =g(i)=g(j) φ ij (l, l) , (5)
(∀(i ′ , j ′ ) ∈ E ′ ), φ ′ i ′ j ′ (l 0 , l 1 ) = (i,j)∈E|i ′ =g(i),j ′ =g(j) φ ij (l 0 , l 1 ) . ( 6
)
With a slight abuse of notation, we will hereafter use g(M) to denote the coarser model resulting from M when using the grouping function g, i.e., we define g(M) = M ′ . Also, given a solution x ′ of M ′ , we can "upsample" it into a solution x of M by setting

x i = x ′ g(i)
for each i ∈ V. We will use the following notation in this case: g -1 (x ′ ) = x. We provide a toy example in supplementary materials.

Coarse-to-fine optimization and label pruning

To estimate the MAP of an input model M, we first construct a series of N +1 progressively coarser models (M (s) ) 0≤s≤N by use of a sequence of N grouping functions (g (s) ) 0≤s<N , where M (0) = M and (∀s), M (s+1) = g (s) (M (s) ) . This provides a multiscale (coarse-to-fine) representation of the original model., where the elements of the resulting models are denoted as follows:

M (s) = V (s) , E (s) , L, {φ (s) i } i∈V (s) , {φ (s) ij } (i,j)∈E (s)
In our framework, MAP estimation proceeds from the coarsest to the finest scale (i.e., from model M (N ) to M (0) ). During this process, a pruning matrix A (s) is computed at each scale s, which is used for defining a restricted solution space S(M (s) , A (s) ). The elements of the matrix A (N ) at the coarsest scale are all set equal to 1 (i.e., no label pruning is used in this case), whereas in all other scales A (s) is computed by use of a trained classifier f (s) .

More specifically, at any given scale s, the following steps take place: i. We approximately minimize (via any existing MRF optimization method) the energy of the model M (s) over the restricted solution space S(M (s) , A (s) ), i.e., we compute

x (s) ≈ arg min x∈S(M (s) ,A (s) ) E(x|M (s) ) .
ii. Given the estimated solution x (s) , a feature map z (s) : V (s) × L → R K is computed at the current scale, and a trained classifier f (s) : R K → {0, 1} uses this feature map z (s) to construct the pruning matrix A (s-1) for the next scale as follows

(∀i ∈ V (s-1) , ∀l ∈ L), A (s-1) (i, l) = f (s) (z (s) (g (s-1) (i), l)) .
iii. Solution x (s) is "upsampled" into x (s-1) = [g (s-1) ] -1 (x (s) ) and used as the initialization for the optimization at the next scale s -1. Note that, due to ( 5) and ( 6), it holds E(x (s-1) |M (s-1) ) = E(x (s) |M (s) ). Therefore, this initialization ensures that energy will continually decrease if the same is true for the optimization applied per scale. Furthermore, it can allow for a warm-starting strategy when transitioning between scales.

The pseudocode of the resulting algorithm appears in Algo. 1.

Algorithm 1: Inference by learning framework

Data: Model M, grouping functions (g (s) ) 0≤s<N , classifiers (f (s) ) 0<s≤N Result: x (0) Compute the coarse to fine sequence of MRFs:

M (0) ← M for s = [0 . . . N -1] do M (s+1) ← g (s) (M (s)
) Optimize the coarse to fine sequence of MRFs over pruned solution spaces:

(∀i ∈ V (N ) , ∀l ∈ L), A (N ) (i, l) ← 1 Initialize x (N ) for s = [N...0] do Update x (s) by iterative minimization: x (s) ≈ arg min x∈S(M (s) ,A (s) ) E(x|M (s) ) if s = 0 then Compute feature map z (s)
Update pruning matrix for next finer scale: s) for initializing solution x (s-1) at next scale: x (s-1) ← [g (s-1) ] -1 (x (s) )

A (s-1) (i, l) = f (s) (z (s) (g (s-1) (i), l)) Upsample x (

Features and classifier for label pruning

For each scale s, we explain how the set of features comprising the feature map z (s) is computed and how we train (off-line) the classifier f (s) . This is a crucial step for our approach. Indeed, if the classifier wrongly prunes labels that belong to the MAP solution, then, only an approximate labeling might be found at the finest scale. Moreover, keeping too many active labels will result in a poor speed-up for MAP estimation.

Features

The feature map z (s) : V (s) × L → R K is formed by stacking K individual real-valued features defined on V (s) × L. We propose to compute features that are not application specific but depend solely on the energy function and the current solution x (s) . This makes our approach generic and applicable to any MRF problem. However, as we establish a general framework, specific application features can be straightforwardly added in future work.

Presence of strong discontinuity This binary feature, PSD (s) , accounts for the existence of discontinuity in solution x (s) when a strong link (i.e., φ ij (x

(s) i , x (s)
j ) > ρ) exists between neighbors. Its definition follows for any vertex i ∈ V (s) and any label l ∈ L :

PSD (s) (i, l) = 1 ∃(i, j) ∈ E (s) | φ ij (x (s) i , x (s) j ) > ρ 0 otherwise ( 7
)
Local energy variation This feature represents the local variation of the energy around the current solution x (s) . It accounts for both the unary and pairwise terms associated to a vertex and a label.

As in [START_REF] Hu | A quantitative evaluation of confidence measures for stereo vision[END_REF], we remove the local energy of the current solution as it leads to a higher discriminative power. The local energy variation feature, LEV (s) , is defined for any i ∈ V (s) and l ∈ L as follows:

LEV (s) (i, l) = φ (s) i (l) -φ (s) i (x (s) i ) N (s) V (i) + j:(i,j)∈E (s) φ (s) ij (l, x (s) j ) -φ (s) ij (x (s) i , x (s) j ) N (s) E (i) (8) with N (s) V (i) = card{i ′ ∈ V (s-1) : g (s-1) (i ′ ) = i} and N (s) E (i) = card{(i ′ , j ′ ) ∈ E (s-1) : g (s-1) (i ′ ) = i, g (s-1) (j ′ ) = j}.
Unary "coarsening" This feature, UC (s) , aims to estimate an approximation of the coarsening induced in the MRF unary terms when going from model M (s-1) to model M (s) , i.e., as a result of applying the grouping function g (s-1) . It is defined for any i ∈ V (s) and l ∈ L as follows

UC (s) (i, l) = i ′ ∈V (s-1) |g (s-1) (i ′ )=i |φ (s-1) i ′ (l) - φ (s) i (l) N (s) V (i) | N (s) V (i) (9)
Feature normalization The features are by design insensitive to any additive term applied on all the unary and pairwise terms. However, we still need to apply a normalization to the LEV (s) and UC (s) features to make them insensitive to any positive global scaling factor applied on both the unary and pairwise terms (such scaling variations are commonly used in computer vision). Hence, we simply divide group of features, LEV (s) and UC (s) by their respective mean value.

Classifier

To train the classifiers, we are given as input a set of MRF instances (all of the same class, e.g., stereo-matching) along with the ground truth MAP solutions. We extract a subset of MRFs for offline learning and a subset for on-line testing. For each MRF instance in the training set, we apply the algorithm 1 without any pruning (i.e., A (s) ≡ 1) and, at each scale, we keep track of the features z (s) and also compute the binary function X (s) MAP : V (s) × L → {0, 1} defined as follows:

(∀i ∈ V, ∀l ∈ L), X (0)
MAP (i, l) = 1, if l is the ground truth label for node i 0, otherwise

(∀s > 0)(∀i ∈ V (s) , ∀l ∈ L), X (s) MAP (i, l) = i ′ ∈V (s-1) :g (s) (i ′ )=i X (s-1) MAP (i ′ , l) ,
where denotes the binary OR operator. The values 0 and 1 in X (s) MAP define respectively the two classes c 0 and c 1 when training the classifier f (s) , where c 0 means that the label can be pruned and c 1 that the label should not be pruned.

To treat separately the nodes that are on the border of a strong discontinuity, we split the feature map z (s) into two groups z contains only features where PSD (s) = 1 (strong discontinuity). For each group, we train a standard linear C-SVM classifier with l 2 -norm regularization (regularization parameter was set to C = 10). The linear classifiers give good enough accuracy during training while also being fast to evaluate at test time During training (and for each group), we also introduce weights to balance the different number of elements in each class (c 0 is much larger than c 1 ), and to also strongly penalize misclassification in c 1 (as such misclassification can have a more drastic impact on the accuracy of MAP estimation). To accomplish that, we set the weight for class c 0 to 1, and the weight for class c 1 to λ card(c0) card(c1) , where card(•) counts the number of training samples in each class. Parameter λ is a positive scalar (common to both groups) used for tuning the penalization of misclassification in c 1 (it will be referred to as the pruning aggressiveness factor hereafter as it affects the amount of labels that get pruned). During on-line testing, depending on the value of the PSD feature, f (s) applies the linear classifier learned on group z (s) 0 if PSD (s) = 0, or the linear classifier learned on group z (s)

1 if PSD (s) = 1.

Experimental results

We evaluate our framework on pairwise MRFs from stereo-matching, image restoration, and, optical flow estimation problems. The corresponding MRF graphs consist of regular 4-connected grids in this case. At each scale, the grouping function merges together vertices of 2 × 2 subgrids. We leave more advanced grouping functions [START_REF] Kim | Variable grouping for energy minimization[END_REF] for future work. As MRF optimization subroutine, we use the Fast-PD algorithm [START_REF] Komodakis | Fast, approximately optimal solutions for single and dynamic mrfs[END_REF]. We make our code available on-line [4]. and φ(l 0 , l 1 ) = 25 min(||l 0l 1 || 2 2 , 200). We train the classifier on the Penguin image stereo-pair (256 labels), and use House (256 labels) for testing (dataset [START_REF] Szeliski | A comparative study of energy minimization methods for markov random fields with smoothness-based priors[END_REF]). For the optical flow estimation, we estimate a subpixel-accurate 2D displacement field between two frames by extending the stereo matching formulation to 2D. Using the dataset of [START_REF] Baker | A database and evaluation methodology for optical flow[END_REF], we train the classifier on Army (1116 labels), and test on RubberWhale (625 labels) and Dimetrodon (483 labels). For all experiments, we use 5 scales and set in (7) ρ = 5 wpq with wpq being the mean value of edge weights.

Experimental setup

Evaluations We evaluate three optimization strategies: the direct optimization (i.e., optimizing the full MRF at the finest scale), the multi-scale optimization (λ = 0, i.e., our framework without any pruning), and our Inference by Learning optimization, where we experiment with different error ratios λ that range between 0.001 and 1.

We assess the performance by computing the energy ratio, i.e., the ratio between the current energy and the energy computed by the direct optimization, the best label agreement, i.e., the proportion of labels that coincides with the labels of the lowest computed energy, the speed-up factor, i.e., the ratio of computation time between the direct optimization and the current optimization strategy, and, the active label ratio, i.e., the percentage of active labels at the finest scale.

Results and discussion

For all problems, we present in Fig. 2 the performance of our Inference by Learning approach for all tested aggressiveness factors and show in Fig. 3 estimated results for λ = 0.01. We present additional results in the supplementary material.

For every problem and aggressiveness factors until λ = 0.1, our pruning-based optimization obtains a lower energy (column (c) of Fig. 2) in less computation time, achieving a speed-up factor (column (a) of Fig. 2) close to 5 for Stereo-matching, above 10 for Optical-flow and up to 3 for image restoration. (note that these speed-up factors are with respect to an algorithm, FastPD, that was the most efficient one in recent comparisons [START_REF] Kappes | A comparative study of modern inference techniques for discrete energy minimization problems[END_REF]). The percentage of active labels (Fig. 2 and is always above 99% for λ 0.1. As expected, less pruning happens near label discontinuities as illustrated in column (d,e,f) of Fig. 3 justifying the use of a dedicated linear classifier. Moreover, large homogeneously labeled regions are pruned earlier in the coarse to fine scale.

Conclusion and future work

Our Inference by Learning approach consistently speeds-up the graphical model optimization by a significant amount while maintaining an excellent accuracy of the labeling estimation. On most experiments, it even obtains a lower energy than direct optimization.

In future work, we plan to experiment with problems that require general pairwise potentials where message-passing techniques can be more effective than graph-cut based methods but are at the same time much slower. Our framework is guaranteed to provide an even more dramatic speedup in this case since the computational complexity of message-passing methods is quadratic with respect to the number of labels while being linear for graph-cut based methods used in our experiments. We also intend to explore the use of application specific features, learn the grouping functions used in the coarse-to-fine scheme, jointly train the cascade of classifiers, and apply our framework to high order graphical models.

Figure 1 :

 1 Figure 1: Black circles: V, Black lines: E, Red squares: V ′ , Blue lines: E ′ .

0

  contains only features where PSD (s) = 0 and z (s) 1

  For the stereo matching problem, we estimate the disparity map from images I R and I L where each label encodes a potential disparity d (discretized at quarter of a pixel precision), with MRF potentials φ p (d) = ||I L (y p , x p )-I R (y p , x p -d)|| 1 and φ pq (d 0 , d 1 ) = w pq |d 0 -d 1 |, with the weight w pq varying based on the image gradient (parameters are adjusted for each sequence). We train the classifier on the well-known Tsukuba stereo-pair (61 labels), and use all other

  (a) Speed-up (b) Active label ratio (c) Energy ratio (d) Label agreement

Figure 2 :

 2 Figure 2: Performance of our Inference by Learning framework: (Top row) stereo matching, (Middle row) optical flow, (Bottom row) image restoration. For stereo matching, the Average Middlebury curve represents the average value of the statistic for the entire Middlebury dataset [6] (2001, 2003, 2005 and 2006) (37 stereopairs).

  column (b)) strongly correlates with the speed-up factor. The best labeling agreement (Fig.2 column (d)) is never worse than 97% (except for the image restoration problems because of the in-painted area)

Figure 3 :

 3 Figure 3: Results of our Inference by Learning framework for λ = 0.1. Each row is a different MRF problem. (a) original image, (b) ground truth, (c) solution of the pruning framework, (d,e,f) percentage of active labels per vertex for scale 0, 1 and 2 (black 0%, white 100%).

This work was supported by USGS through the Measurements of surface ruptures produced by continental earthquakes from optical imagery and LiDAR project (USGS Award G13AP00037), the Terrestrial Hazard Observation and Reporting Center of Caltech, and the Moore foundation through the Advanced Earth Surface Observation Project (AESOP Grant 2808).