Benjamin Girard

INVERSE ZERO-SUM PROBLEMS AND ALGEBRAIC INVARIANTS by

In this article, we study the maximal cross number of long zero-sumfree sequences in a finite Abelian group. Regarding this inverse-type problem, we formulate a general conjecture and prove, among other results, that this conjecture holds true for finite cyclic groups, finite Abelian p-groups and for finite Abelian groups of rank two. Also, the results obtained here enable us to improve, via the resolution of a linear integer program, a result of W. Gao and A. Geroldinger concerning the minimal number of elements with maximal order in a long zero-sumfree sequence of a finite Abelian group of rank two.

Introduction

Let G be a finite Abelian group, written additively. By exp(G) we denote the exponent of G. If G is cyclic of order n, it will be denoted by C n . In the general case, we can decompose G (see for instance [START_REF] Samuel | Théorie algébrique des nombres[END_REF]) as a direct product of cyclic groups

C n 1 ⊕ • • • ⊕ C nr where 1 < n 1 | . . . | n r ∈ N.
In this paper, any finite sequence S = (g 1 , . . . , g ℓ ) of ℓ elements from G will be called a sequence in G with length |S| = ℓ. Given a sequence S = (g 1 , . . . , g ℓ ) in G, we say that s ∈ G is a subsum of S when it lies in the following set, Σ(S) = i∈I g i | ∅ I ⊆ {1, . . . , ℓ} .

If 0 is not a subsum of S, we say that S is a zero-sumfree sequence. If ℓ i=1 g i = 0, then S is said to be a zero-sum sequence. If moreover one has i∈I g i = 0 for all proper subsets ∅ I {1, . . . , ℓ}, S is called a minimal zero-sum sequence.

In a finite Abelian group G, the order of an element g will be written ord(g) and for every divisor d of the exponent of G, we denote by G d the subgroup of G consisting of all elements of order dividing d:

G d = {x ∈ G | dx = 0} .
For every divisor d of exp(G), and every sequence S in G, we denote by α d the number of elements, counted with multiplicity, contained in S and of order d. Although the quantity Mathematics Subject Classification (2000): 11R27, 11B75, 11P99, 20D60, 20K01, 05E99, 13F05. α d clearly depends on S, we will not emphasize this dependence in the present paper, since there will be no risk of confusion.

Let P be the set of prime numbers. Given a positive integer n ∈ N * = N\{0}, we denote by D n the set of its positive divisors and we set τ (n) = |D n |. If n > 1, we denote by P -(n) the smallest prime element of D n , and we put by convention P -(1) = 1. For every prime p ∈ P, ν p (n) will denote the p-adic valuation of n. By D(G) we denote the smallest integer t ∈ N * such that every sequence S in G with |S| ≥ t contains a non-empty zero-sum subsequence. The number D(G) is called the Davenport constant of the group G.

Let G ≃ C n 1 ⊕ • • • ⊕ C nr ,
By d(G) we denote the largest integer t ∈ N * such that there exists a zero-sumfree sequence S in G with |S| = t. It can be readily seen that, for every finite Abelian group G, one has

d(G) = D(G) -1. If G ≃ C ν 1 ⊕• • •⊕C νs , with ν i > 1 for all i ∈ 1,
s , is the longest possible decomposition of G into a direct product of cyclic groups, then we set:

k * (G) = s i=1 ν i -1 ν i .
The cross number of a sequence S = (g 1 , . . . , g ℓ ), denoted by k(S), is then defined by:

k(S) = ℓ i=1 1 ord(g i )
.

The notion of cross number was introduced by U. Krause in [START_REF] Krause | A characterization of algebraic number fields with cyclic class group of prime power order[END_REF] (see also [START_REF] Krause | Zahlten Arithmetic in Krull monoids and the cross number of divisor class groups[END_REF]). Finally, we define the so-called little cross number k(G) of G:

k(G) = max{k(S)|S zero-sumfree sequence of G}.
Given a finite Abelian group G, two elementary constructions (see [START_REF] Geroldinger | Halter-Koch Non-unique factorizations. Algebraic, combinatorial and analytic theory[END_REF], Proposition 5.1.8) give the following lower bounds:

D * (G) ≤ D(G) and k * (G) ≤ k(G).
The invariants D(G) and k(G) play a key rôle in the theory of non-unique factorization (see for instance Chapter 9 in [START_REF] Narkiewicz | Elementary and analytic theory of algebraic numbers[END_REF], the book [START_REF] Geroldinger | Halter-Koch Non-unique factorizations. Algebraic, combinatorial and analytic theory[END_REF] which presents the different aspects of the theory, and the survey [12] also). They have been extensively studied during last decades and even if numerous results were proved (see Chapter 5 of the book [START_REF] Geroldinger | Halter-Koch Non-unique factorizations. Algebraic, combinatorial and analytic theory[END_REF], [START_REF] Gao | Geroldinger Zero-sum problems in finite abelian groups : a survey[END_REF] for a survey with many references on the subject, and [START_REF] Girard | A new upper bound for the cross number of finite Abelian groups[END_REF] for recent results on the cross number of finite Abelian groups), their exact values are known for very special types of groups only. In the sequel, we will need some of these values in the case of finite Abelian pgroups and finite Abelian groups of rank two, so we gather them in the following theorem (see [START_REF]Geroldinger The cross number of finite abelian groups[END_REF], [START_REF] Olson | A combinatorial problem on finite abelian groups I[END_REF] and [START_REF] Olson | A combinatorial problem on finite abelian groups II[END_REF]).

D(G) = r i=1 (p a i -1) + 1 = D * (G) and k(G) = r i=1 p a i -1 p a i = k * (G).
(ii) For every m, n ∈ N * , we have:

D(C m ⊕ C mn ) = m + mn -1 = D * (C m ⊕ C mn ).
In particular, we have

D(C n ) = n.
The aim of this paper is to study some inverse zero-sum problems of a special type. Instead of trying to characterize explicitly, given a finite Abelian group, the structure of long zero-sumfree sequences (see [START_REF] Gao | Geroldinger On the order of elements in long minimal zero-sum sequences[END_REF], [START_REF] Chen | Savchev Minimal zero-sum sequences of maximum length in the group C 3 ⊕ C 3k[END_REF], [START_REF] Gao | Inverse zero-sum problems[END_REF], [START_REF] Schmid | Inverse zero-sum problems II[END_REF] and [START_REF] Gao | Grynkiewicz Inverse zero-sum problems III, submitted[END_REF]), or the structure of zero-sumfree sequences with large cross number (see [START_REF] Geroldinger | On minimal zero sequences with large cross number[END_REF]), we study to what extent a zero-sumfree sequence can be extremal in both directions simultaneously. For instance, what is the maximal cross number of a long zero-sumfree sequence? Regarding this problem, we propose the following general conjecture.

Conjecture 1.2. -Let G ≃ C n 1 ⊕ • • • ⊕ C nr , with 1 < n 1 | . . . | n r ∈ N,
k(S) ≤ r i=1 n i -1 n i .
In particular, one has k(S) < r.

One can notice that Conjecture 1.2 is closely related to the distribution of the orders of elements in a long zero-sumfree sequence. As we will see in this paper, it provides, when it holds, useful informations on this question. In the following proposition, we gather what is currently known, to the best of our knowledge, on the structure of long zerosumfree sequences in finite Abelian groups of rank two. This result, due to W. Gao and A. Geroldinger, can be found under a slightly different form in [START_REF] Geroldinger | Halter-Koch Non-unique factorizations. Algebraic, combinatorial and analytic theory[END_REF], Proposition 5.8.4.

Proposition 1.3. -Let G ≃ C m ⊕ C mn ,
where m, n ∈ N * , be a finite Abelian group of rank two. For every zero-sumfree sequence S in G with |S| = d(G) = m + mn -2, the following two statements hold.

(i) For every element g ∈ S, one has m | ord(g) | mn.

(ii) The sequence S contains at least

m + mn -n 2m -2 P -(n) + 1 -1 ≥ m -1
elements with order mn.

The problem of the exact structure of a long zero-sumfree sequence in groups of the form G ≃ C m ⊕ C mn is also closely related to an important conjecture in additive group theory, which bears upon the so-called Property B. Let n ≥ 2 be an integer. We say that n has Property B if every zero-sumfree sequence in G ≃ C n ⊕C n with |S| = d(G) = 2n-2 contains some element repeated at least n -2 times.

Property B was introduced and first studied in [START_REF] Gao | Geroldinger On long minimal zero sequences in finite abelian groups[END_REF] (see also [START_REF] Geroldinger | Halter-Koch Non-unique factorizations. Algebraic, combinatorial and analytic theory[END_REF], Section 5.8, [START_REF] Lettl | Minimal zero-sum sequences in C n ⊕ C n[END_REF] and [START_REF] Gao | Inverse zero-sum problems[END_REF]). It is conjectured that every integer n ≥ 2 has Property B, and recently, it was proved that an integer n ≥ 2 has Property B if each prime divisor of n has this property (see [START_REF] Gao | Geroldinger On zero-sum sequences in Z/nZ⊕Z/nZ[END_REF], Section 8 and [START_REF] Gao | Grynkiewicz Inverse zero-sum problems III, submitted[END_REF]). Therefore, it remains to solve this problem for prime numbers. Regarding this, it can be shown that Property B holds for n = 2, 3, 5, 7 (see [START_REF] Gao | Geroldinger On zero-sum sequences in Z/nZ⊕Z/nZ[END_REF], Proposition 4.2), for n = 11, 13, 17, 19 (see [START_REF] Bhowmik | Schlage-Puchta The structure of maximal zero-sum free sequences II[END_REF]), and consequently for every integer n being representable as a product of these numbers. Moreover, W. Schmid proved in [START_REF] Schmid | Inverse zero-sum problems II[END_REF] that if some integer m ≥ 2 has Property B, then the zero-sumfree sequences in G ≃ C m ⊕ C mn with length d(G) = m + mn -2 can be characterized explicitly for all n ∈ N * . This result provides a unified way to prove Theorem 3.3 in [START_REF] Gao | Geroldinger On the order of elements in long minimal zero-sum sequences[END_REF] and Theorem in [START_REF] Chen | Savchev Minimal zero-sum sequences of maximum length in the group C 3 ⊕ C 3k[END_REF]. It also implies, assuming that Property B holds for every integer n ≥ 2, that Conjecture 1.2 holds true for every finite Abelian group of rank two.

New results and plan of the paper

In this article, we prove that Conjecture 1.2 holds for several types of finite Abelian groups. To begin with, in Section 3, we prove some consequences of this conjecture in the cases where it holds. For instance, Conjecture 1.2, if true, would imply simultaneously two classical and long-standing conjectures related to the Davenport constant of finite Abelian groups of the form C r n .

Proposition 2.1. -Let n, r ∈ N * be such that Conjecture 1.2 holds for the group C r n . Then, one has the following equality:

D(C r n ) = r(n -1) + 1. Moreover, every zero-sumfree sequence S in C r n with |S| = d(C r n ) = r(n -1
) consists only of elements with order n.

More generally, Conjecture 1.2, if true, would provide the following general upper bound for the Davenport constant of a finite Abelian group.

Proposition 2.2. -Suppose that Conjecture 1.2 holds for G ≃ C n 1 ⊕ • • • ⊕ C nr , with 1 < n 1 | . . . | n r ∈ N.
Then, one has the following inequality:

D(G) ≤ r i=1 n r n i (n i -1) + 1 = D * (G) + r i=1 n r n i -1 (n i -1) .
Then, in Section 3 also, we prove that Conjecture 1.2 holds true for finite cyclic groups and finite Abelian p-groups.

Proposition 2.3. -Conjecture 1.2 holds for the following groups G.

(i) G is a finite cyclic group.

(ii) G is a finite Abelian p-group.

In Section 4, we present a general method which was introduced in [14] so as to study the cross number of finite Abelian groups. Then, using this method, we prove in Section 5 two important lemmas, which will be useful in the study of the special case of finite Abelian groups of rank two.

In Section 6, we prove the two main theorems of this paper. The first one states that Conjecture 1.2 holds for every finite Abelian group of rank two. As already mentioned in Section 1, this result supports Property B (see [START_REF] Schmid | Inverse zero-sum problems II[END_REF]).

k(S) ≤ m -1 m + mn -1 mn .
In particular, one always has k(S) < 2.

The second theorem, which is proved in Section 6 as well, is an effective result which states that, in a finite Abelian group of rank two, most of the elements of a long zerosumfree sequence must have maximal order. This result improves significantly the statement of Proposition 1.3 (ii). (i) If n is a prime power, then S contains at least mn -1 elements with order mn. (ii) If n is not a prime power, then S contains at least

4 5 mn + (n -5) 5
elements with order mn.

It may be observed that for every group G ≃ C m ⊕ C mn , where m, n ∈ N * and n ≥ 2, there exists a zero-sumfree sequence S in G with |S| = d(G) = m + mn -2, and which does not contain strictly more than mn -1 elements with order mn. Indeed, let (e 1 , e 2 ) be a basis of G, with ord(e 1 ) = m and ord(e 2 ) = mn. Then, it suffices to consider the zero-sumfree sequence S consisting of the element e 1 repeated m-1 times and the element e 2 repeated mn -1 times. From this point of view, Theorem 2.5 proves to be "nearly optimal". In addition, the general method presented in Section 4 can be successfully used to prove an analogue of Theorem 2.5 in the case of finite Abelian p-groups (see [START_REF] Girard | Inverse zero-sum problems in finite Abelian p-groups[END_REF]).

Finally, in Section 7, we will present and discuss a general conjecture concerning the maximal possible length of a zero-sumfree sequence with large cross number, which can be seen as a dual version of Conjecture 1.2.

Proofs of Propositions 2.1, 2.2 and 2.3

To start with, we prove the two corollaries of Conjecture 1.2 announced in Section 2.

Proof of Proposition 2.1. -Let S be a zero-sumfree sequence in G ≃ C r n with maximal length |S| = d(G) = D(G) -1.
Then, one has the following inequality:

D(G) -1 n = |S| n ≤ k(S) ≤ r n -1 n , which implies that D(G) ≤ r(n -1) + 1 = D * (G)
, and since D * (G) ≤ D(G) always holds, the equality follows. Consequently, one has:

k(S) = r n -1 n = D(G) -1 n = |S| n ,
and so, every element g of S verifies ord(g

) = exp(G) = n. Proof of Proposition 2.2. -Let S be a zero-sumfree sequence in G ≃ C n 1 ⊕ • • • ⊕ C nr , with 1 < n 1 | . . . | n r ∈ N, such that |S| = d(G) = D(G) -1.
Then, one has the following inequality:

D(G) -1 n r = |S| n r ≤ k(S) ≤ r i=1 n i -1 n i ,
which implies the desired result.

We prove now that Conjecture 1.2 holds true for finite cyclic groups and finite Abelian p-groups.

Proof of Proposition 2.3. -(i) Let n ≥ 2 be an integer and let S be a zero-sumfree sequence in

C n with |S| ≥ d * (C n ) = n -1.
Then, it is well-known (see for instance [START_REF] Geroldinger | Halter-Koch Non-unique factorizations. Algebraic, combinatorial and analytic theory[END_REF], Theorem 5.1.10 (i)) that there exists g ∈ C n with ord(g) = n such that S is of the following form: S = (g, . . . , g n-1 times

).

Consequently, we obtain:

k(S) = n -1 n ,
which gives the desired result.

(ii) Let p ∈ P, r ∈ N * , and

G ≃ C p a 1 ⊕ • • • ⊕ C p ar , with a 1 ≤ • • • ≤ a r and a i ∈ N * for all i ∈ 1,
r , be a p-group. By Theorem 1.1 (i), one has:

k(G) = r i=1 p a i -1 p a i = k * (G).
Then, for every zero-sumfree sequence S in G, in particular for those verifying |S| ≥ d * (G), one indeed has, by the very definition of the little cross number:

k(S) ≤ k(G) = r i=1 p a i -1 p a i ,
and the proof is complete.

Outline of a new method

Let G be a finite Abelian group, and let S be a sequence of elements in G. The general method that we will use in this paper (see also [START_REF] Girard | A new upper bound for the cross number of finite Abelian groups[END_REF] and [START_REF] Girard | Inverse zero-sum problems in finite Abelian p-groups[END_REF] for applications of this method in two other contexts), consists in considering, for every

d ′ , d ∈ N such that 1 ≤ d ′ | d | exp(G), the following exact sequence: 0 → G d/d ′ ֒→ G d π (d ′ ,d) → G d G d/d ′ → 0.
Now, let U be the subsequence of S consisting of all the elements whose order divides d.

If, for some 1

≤ d ′ | d | exp(G)
, it is possible to find sufficiently many disjoint non-empty zero-sum subsequences in π (d ′ ,d) (U), that is to say sufficiently many disjoint subsequences in U the sum of which are elements of order dividing d/d ′ , then S cannot be a zero-sumfree sequence in G.

So as to make this idea more precise, we proposed in [START_REF] Girard | A new upper bound for the cross number of finite Abelian groups[END_REF] to introduce the following number, which can be seen as an extension of the classical Davenport constant.

Let G ≃ C n 1 ⊕ • • • ⊕ C nr , with 1 < n 1 | . . . | n r ∈ N, be a finite Abelian group and d ′ , d ∈ N be two integers such that 1 ≤ d ′ | d | exp(G). By D (d ′ ,d) (G) we denote the smallest integer t ∈ N * such that every sequence S in G d with |S| ≥ t contains a subsequence with sum in G d/d ′ .
Using this definition, we can prove the following simple lemma, which is one possible illustration of the idea we presented. This result will be useful in Section 5 and states that given a finite Abelian group G, there exist strong constraints on the way the orders of elements have to be distributed within a zero-sumfree sequence.

≤ d ′ | d | exp(G).
Given a sequence S of elements in G, we will write T for the subsequence of S consisting of all the elements whose order divides d/d ′ , and we will write U for the subsequence of S consisting of all the elements whose order divides d (In particular, one has T ⊆ U). Then, the following condition implies that S cannot be a zero-sumfree sequence:

|T | + |U| -|T | D (d ′ ,d) (G) ≥ D ( d d ′ , d d ′ ) (G). Proof. -Let us set ∆ = D ( d d ′ , d d ′ ) (G).
When it holds, this inequality implies that there are ∆ disjoint subsequences S 1 , . . . , S ∆ of S, the sum of which are elements of order dividing d/d ′ . Now, by the very definition of D ( d d ′ , d d ′ ) (G), S has to contain a non-empty zero-sum subsequence. Now, in order to obtain effective inequalities from the symbolic constraints of Lemma 4.1, one can use a result proved in [START_REF] Girard | A new upper bound for the cross number of finite Abelian groups[END_REF], which states that for any finite Abelian group G and every 1 ≤ d ′ | d | exp(G), the invariant D (d ′ ,d) (G) is linked with the classical Davenport constant of a particular subgroup of G, which can be characterized explicitly. In order to define properly this particular subgroup, we have to introduce the following notation.

For all i ∈ 1, r , we set:

A i = gcd(d ′ , n i ), B i = lcm(d, n i ) lcm(d ′ , n i ) and υ i (d ′ , d) = A i gcd(A i , B i ) .
For instance, whenever d divides n i , we have

υ i (d ′ , d) = gcd(d ′ , n i ) = d ′ , and in particular υ r (d ′ , d) = d ′ .
We can now state our result on D (d ′ ,d) (G) (see [START_REF] Girard | A new upper bound for the cross number of finite Abelian groups[END_REF], Proposition 3.1).

Proposition 4.2. -Let G ≃ C n 1 ⊕ • • • ⊕ C nr , with 1 < n 1 | . . . | n r ∈ N, be a finite Abelian group and d ′ , d ∈ N be such that 1 ≤ d ′ | d | exp(G)
. Then, we have the following equality:

D (d ′ ,d) (G) = D C υ 1 (d ′ ,d) ⊕ • • • ⊕ C υr(d ′ ,d) .

Two lemmas related to zero-freeness in

G ≃ C m ⊕ C mn
In this section, we show how the method presented in Section 4 can be used in order to obtain two key lemmas for the proofs of Theorems 2.4 and 2.5. To start with, we prove the following

Lemma 5.1. -Let G ≃ C m ⊕ C mn , where m, n ∈ N * , n ≥ 2,

be a finite Abelian group of rank two, and let S be a zero-sumfree sequence in

G with |S| ≥ d * (G) = m + mn -2.
Then, for every ℓ ∈ D n \{n}, one has the following inequality:

d∈D ℓ α md ≤ m -1.
Proof. -Let S be a zero-sumfree sequence in G ≃ C m ⊕ C mn with |S| ≥ d * (G) = m + mn -2. Let ℓ ∈ D n \{n}, d ′ = n/ℓ and d = mn, which leads to d/d ′ = mℓ. We also set m ′ = gcd(d ′ , m). Now, let T and U be the two subsequences of S which are defined in Lemma 4.1. In particular, one has T ⊆ U = S, and by Proposition 1.3 (i), we obtain:

|T | = d∈D ℓ α m d.
To start with, we determine the exact value of D (d ′ ,d) (G). One has:

υ 1 (d ′ , d) = m ′ gcd m ′ , lcm(d,m) lcm(d ′ ,m) = m ′ gcd m ′ , d d ′ m ′ m = m ′ gcd (m ′ , m ′ ℓ) = 1,
and, since υ 2 (d ′ , d) = d ′ , one obtains, using Proposition 4.2 and Theorem 1.1 (ii), the following equalities:

D (d ′ ,d) (G) = D C υ 1 (d ′ ,d) ⊕ C υ 2 (d ′ ,d) = D C n ℓ = n ℓ .
Now, let us suppose that one has |T | ≥ m. Since ℓ ∈ D n \{n}, we obtain the following inequalities:

|T | + |U| -|T | D (d ′ ,d) (G) ≥ |T | + ℓ (m + mn -2 -|T |) n ≥ m + ℓ (mn -2) n = (m + mℓ -1) - ℓ n + n -ℓ n > (m + mℓ -1) - ℓ n = D ( d d ′ , d d ′ ) (G) - 1 D (d ′ ,d) (G) ,
and, according to Lemma 4.1, S must contain a non-empty zero-sum subsequence, which is a contradiction. Thus, one has |T | ≤ m -1, which is the desired result. Now, let n ≥ 2 be an integer, and p 1 , . . . , p r be its distinct prime divisors. Given m ∈ N * and a zero-sumfree sequence S in G ≃ C m ⊕ C mn with |S| ≥ d * (G) = m + mn -2, Lemma 5.1 implies that the integers α md ∈ N, where d ∈ D n \{n}, have to satisfy the following r linear constraints:

d∈D n/p i α md ≤ m -1, for all i ∈ 1, r .
In the next lemma, we solve a linear integer program on the divisor lattice of n, in order to obtain the maximum value of the function

(α md ) d∈Dn\{n} → d∈Dn\{n} α md d
under the r above constraints (the reader interested by linear programming methods is referred to the book [START_REF] Schrijver | Theory of linear and integer programming[END_REF], for an exhaustive presentation of the subject).

Lemma 5.2. -Let m, n ∈ N * , with n ≥ 2, and let (x d ) d∈Dn\{n} be a sequence of positive integers, such that for every prime divisor p of n, one has the following linear constraint:

d∈D n/p x d ≤ m -1.
Then, one has the following inequality, which is best possible:

d∈Dn\{n} x d d ≤ m -1.
Proof. -Let n ≥ 2 be an integer, and p 1 , . . . , p r be its distinct prime divisors. For every k ∈ 0, m-1 , let also S k be the set of all the sequences of positive integers x = (x d ) d∈Dn\{n} which verify the above linear constraints, and being such that x 1 = mk -1. Now, we can prove, by induction on k ∈ 0, m -1 , that the following statement holds.

For every sequence x ∈ S k , one has

d∈Dn\{n} x d d ≤ m -1.
If k = 0, then for every x ∈ S 0 , the linear constraints imply that x d = 0 for all d ∈ D n \{1, n}, which gives the following equality:

d∈Dn\{n} x d d = m -1.
Assume now that the statement is valid for k -1 ≥ 0. Let us define the following map:

f : D n \{n} → {A | ∅ A ⊆ 1, r } d → {i ∈ 1, r | d ∈ D n/p i }.
Let x ∈ S k and let L be the set of the elements d ∈ D n \{1, n} such that one has x d ≥ 1. By definition, and for every d ∈ D n \{n}, |f (d)| is the number of linear constraints in which the variable x d appears. Thus, for every prime divisor p of n, x n/p appears in only one linear constraint, and we may assume, without loss of generality, that we have:

d∈D n/p x d = m -1.
Hence, for every i ∈ 1, r , the set L ∩ D n/p i is non-empty, and one obtains:

d∈L f (d) = 1, r .
Let us consider a non-empty subset L ′ of L verifying the following equality:

d∈L ′ f (d) = 1, r ,
and being of minimal cardinality regarding this property. Since f (d) is a non-empty set for every d ∈ D n \{n}, the following property has to hold:

d∈L ′′ f (d) 1, r for all ∅ L ′′ L ′ .
Now, one can notice the following two facts. Then, for all i ∈ 1, s , one has the following inequality:

|A i | ≤ r -s + 1.
Proof.

-By symmetry, it suffices to prove that one has |A 1 | ≤ rs + 1. Assume to the contrary that |A 1 | ≥ rs + 2. Since, for all i ∈ 1, s -1 , the set A i+1 must contain at least one element from 1, r \ (A 1 ∪ • • • ∪ A i ), one obtains the following inequality:

|A 1 ∪ • • • ∪ A i+1 | ≥ |A 1 ∪ • • • ∪ A i | + 1.
Therefore, we deduce by an easy induction argument that one has

|A 1 ∪ • • • ∪ A s-1 | ≥ (r -s + 2) + (s -2) = r, and so A 1 ∪ • • • ∪ A s-1 = 1, r , which is a contradiction.
Fact 2. For every d ∈ D n \{n}, one has the following inequalities:

d ≥ min f -1 (f (d)) ≥ i∈ 1,r \f (d) p νp i (n) i ≥ 2 r-|f (d)| .
Now, using Facts 1 and 2, we can prove the desired result, by considering the sequence y = (y d ) d∈Dn\{n} obtained from x in the following way:

y d =      x 1 + 1 if d = 1, x d -1 if d ∈ L ′ , x d otherwise.
It is readily seen that y ∈ S k-1 . Therefore, Facts 1 and 2 give the following inequalities:

m -1 ≥ d∈Dn\{n} y d d =   d∈Dn\{n} x d d   + 1 - d∈L ′ 1 d ≥   d∈Dn\{n} x d d   + 1 - d∈L ′ 1 2 r-|f (d)| ≥   d∈Dn\{n} x d d   + 1 - d∈L ′ 1 2 |L ′ |-1 ≥   d∈Dn\{n} x d d   + 1 - |L ′ | 2 |L ′ |-1 ≥ d∈Dn\{n} x d d ,
which completes the proof.

Proofs of the two main theorems

To start with, we show that every finite Abelian group of rank two satisfies Conjecture 1.2. The following proof of Theorem 2.4 consists in a direct application of Lemmas 5.1 and 5. If n = 1, then the desired result follows directly from Proposition 1.3 (i), since every element of S has order m. Now, let us suppose that n ≥ 2. Using Proposition 1.3 (i), we obtain:

k(S) = d∈Dmn α d d = d∈Dn α md md ,
and we can distinguish two cases.

Case 1. α mn ≥ mn -1. In this case, applying Proposition 1.3 (i), one obtains:

d∈Dn\{n} α md = |S| -α mn ,
which implies the following inequalities:

k(S) = d∈Dn\{n} α md md + α mn mn ≤ |S| -α mn m + α mn mn ≤ |S| -(mn -1) m + mn -1 mn = m -1 m + mn -1 mn .
Case 2. α mn ≤ mn -1. Then, by Lemmas 5.1 and 5.2, we obtain:

k(S) = d∈Dn\{n} α md md + α mn mn ≤ m -1 m + α mn mn ≤ m -1 m + mn -1 mn ,
which completes the proof. Now, we prove Theorem 2.5, which gives a lower bound for the number of elements with maximal order in a long zero-sumfree sequence of a finite Abelian group of rank two.

|S| -α mn = d∈D p a-1 α md ≤ m -1,
which indeed implies that

α mn ≥ |S| -(m -1) = m + mn -2 -(m -1) = mn -1.
(ii) If τ (n) ≤ 3, then n has to be a prime power, and the desired result follows by (i). Now, let us suppose that D n = {d 0 = 1 < d 1 < d 2 < d 3 . . . } contains at least four elements. In particular, one has n ≥ 6.

By Lemmas 5.1 and 5.2, one has:

d∈Dn\{n} α md md ≤ m -1 m , that is d 1 α m n d 1 mn + d 2 α m n d 2 mn + d 3 α m n d 3 mn + d∈Dn d>d 3 d α m n d mn ≤ m -1 m . (1)
Now, we can distinguish two cases.

2 α m n 2 mn + 3 α m n 3 mn + 4 α m n 4 mn + 5    d∈Dn d>d 3 α m n d mn    ≤ m -1 m . (2) But since d∈Dn d>d 3 α m n d = |S| -α mn -α m n 2 -α m n 3 -α m n 4 , relation (2)
implies:

5 m + mn -2 -α mn mn -3 α m n 2 mn -2 α m n 3 mn - α m n 4 mn ≤ m -1 m , that is 5 m + mn -2 -α mn mn - α m n 2 + α m n 4 mn -2 α m n 2 + α m n 3 mn ≤ m -1 m ,
Now using the fact that, by Lemma 5.1, one has:

α m n 2 + α m n 4 ≤ m -1 as well as α m n 3 ≤ m -1, we obtain 5 m + mn -2 -α mn mn - m -1 mn -2 2 (m -1) mn ≤ m -1 m , which is equivalent to 5 mn -1 -α mn mn ≤ m -1 m , that is 5(mn -1) -n(m -1) ≤ 5α mn ,
and thus 4 5 mn + (n -5) 5 ≤ α mn , which is the desired result.

Case 2. d 3 ≥ 5. Then (1) implies:

d 1 α m n d 1 mn + d 2 α m n d 2 mn + 5    d∈Dn d≥d 3 α m n d mn    ≤ m -1 m . (3) But since d∈Dn d≥d 3 α m n d = |S| -α mn -α m n d 1 -α m n d 2 , relation (3) implies
: 5 m + mn -2 -α mn mn + (d 1 -5) α m n 2 mn + (d 2 -5) α m n d 2 mn ≤ m -1 m .
Therefore, since d 1 ≥ 2 and d 2 ≥ 3, we have

5 m + mn -2 -α mn mn -3 m -1 mn -2 m -1 mn ≤ m -1 m , that is 5 mn -1 -α mn mn ≤ m -1 m ,
which leads to 4 5 mn + (n -5) 5 ≤ α mn , and the proof is complete.

A concluding remark

Given a finite Abelian group G, the investigation of the maximal possible length of a zero-sumfree sequence S in G with large cross number may also be of interest. Concerning this question, we propose the following general conjecture, which can be seen as a dual version of Conjecture 1.2. It can easily be seen, by Theorem 1.1 (i), that Conjecture 7.1 holds true for finite Abelian p-groups. Even in the case of finite cyclic groups which are not p-groups, this problem is still wide open. Yet, in this special case, the following result supports the idea that a zero-sumfree sequence with large cross number has to be a "short" sequence. Theorem 7.2. -Let n ∈ N * be such that n is not a prime power, and let S be a zerosumfree sequence in C n verifying k(S) ≥ k * (C n ). Then, one has the following inequality:

|S| ≤ n 2 .
Proof. -So as to prove this result, we will use the notion of index of a sequence in a finite cyclic group, which was introduced implicitly in [START_REF] Kleitman | An addition theorem on the integers modulo n[END_REF], Conjecture p.344, and more explicitly in [START_REF] Chapman | Minimal zero sequences and the strong Davenport constant[END_REF]. Let g ∈ C n with ord(g) = n, and let S = (g 1 , . . . , g ℓ ) = (n 1 g, . . . , n ℓ g), where n 1 , . . . , n ℓ ∈ 0, n -1 , be a sequence in C n . We define:

S g = ℓ i=1 n i n .
Since, for every i ∈ 1, ℓ , we have gcd(n i , n) n = 1 ord(g i ) ,

one can notice that S g ≥ k(S) for all g ∈ C n with ord(g) = n. Then, the index of S, denoted by index(S), is defined in the following fashion: index(S) = min g ∈ Cn ord(g) = n S g . Now, if n is not a prime power and S is a zero-sumfree sequence in C n such that k(S) ≥ k * (C n ), one obtains, by the very definition of the index, the following inequalities:

index(S) ≥ k(S) ≥ k * (C n ) > 1.
Therefore, using a result of Savchev and Chen (see Theorem 9 in [START_REF] Savchev | Long zero-free sequences in finite cyclic groups[END_REF]), one must have the following inequality:

|S| ≤ n 2 ,
which completes the proof.

In particular, Theorem 7.2 implies that Conjecture 7.1 holds true for all the cyclic groups of the form C 2p a , where p ∈ P and a ∈ N.

  with 1 < n 1 | . . . | n r ∈ N, be a finite Abelian group. We set: D * (G) = r i=1 (n i -1) + 1 as well as d * (G) = D * (G) -1.

Theorem 2 . 4 .

 24 -Let G ≃ C m ⊕ C mn , where m, n ∈ N * , be a finite Abelian group of rank two. For every zero-sumfree sequence S in G with |S| ≥ d * (G) = m + mn -2, the following inequality holds:

Theorem 2 . 5 .

 25 -Let G ≃ C m ⊕ C mn , where m, n ∈ N * , be a finite Abelian group of rank two. For every zero-sumfree sequence S in G with |S| = d(G) = m + mn -2, the following two statements hold.

Lemma 4 . 1 .

 41 -Let G be a finite Abelian group and d ′ , d ∈ N be two integers such that 1

Fact 1 .i 1 ,

 11 For every d ∈ L ′ , one has |f (d)| ≤ r -|L ′ | + 1, and in particular, |L ′ | ≤ r. This fact is a straightforward consequence of the following combinatorial lemma. Lemma 5.3. -Let r ∈ N * and A 1 , • • • , A s be s non-empty subsets of 1, r verifying i∈ 1,s A i = 1, r , and i∈I A r for every subset ∅ I 1, s .

2 .

 2 Proof of Theorem 2.4. -Let G ≃ C m ⊕ C mn , where m, n ∈ N * , be a finite Abelian group of rank two, and let S be a zero-sumfree sequence in G with |S| ≥ d * (G) = m + mn -2. Since, by Theorem 1.1 (ii), one has d(G) = d * (G), we obtain that |S| = d * (G) = m + mn -2.

Proof of Theorem 2 . 5 .

 25 -Let G ≃ C m ⊕ C mn , where m, n ∈ N * , be a finite Abelian group of rank two, and let S be a zero-sumfree sequence in G with |S| = d(G) = m + mn -2.(i) Let p ∈ P and a ∈ N be such that n = p a . If a = 0, then G ≃ C m ⊕ C m and, by Proposition 1.3 (i), every element of S has order m. Now, let us suppose that a ≥ 1, Then, by Lemma 5.1, one has:

Case 1 .

 1 d 3 = 4. Then d 1 = 2, d 2 = 3 and (1) implies:

Conjecture 7 . 1 .

 71 -Let G be a finite Abelian group and G ≃ C ν 1 ⊕ • • • ⊕ C νs , with ν i > 1 for all i ∈ 1, s , be its longest possible decomposition into a direct product of cyclic groups. Given a zero-sumfree sequence S in G verifying k(S) ≥ k * (G), one always has the following inequality:

  Theorem 1.1. -The following two statements hold.

(i) Let p ∈ P, r ∈ N * and a 1 ≤ • • • ≤ a r , where a i ∈ N * for all i ∈ 1, r . Then, for the p-group G ≃ C p a 1 ⊕ • • • ⊕ C p ar , we have:

  be a finite Abelian group. Given a zero-sumfree sequence S in G verifying |S| ≥ d * (G), one always has the following inequality:

Acknowledgments

I am grateful to my Ph.D. advisor Alain Plagne for his help during the preparation of this paper. I would like also to thank Alfred Geroldinger and Wolfgang Schmid for useful remarks on a preliminary version of this work.


Sophie S Abby

Eric Tannier

Manolo Gouy

Vincent Daubin
email: daubin@biomserv.univ-lyon1.fr

Detecting lateral gene transfers by statistical reconciliation of phylogenetic forests

Background: To understand the evolutionary role of Lateral Gene Transfer (LGT), accurate methods are needed to identify transferred genes and infer their timing of acquisition. Phylogenetic methods are particularly promising for this purpose, but the reconciliation of a gene tree with a reference (species) tree is computationally hard. In addition, the application of these methods to real data raises the problem of sorting out real and artifactual phylogenetic conflict.

Results:

We present Prunier, a new method for phylogenetic detection of LGT based on the search for a maximum statistical agreement forest (MSAF) between a gene tree and a reference tree. The program is flexible as it can use any definition of "agreement" among trees. We evaluate the performance of Prunier and two other programs (EEEP and RIATA-HGT) for their ability to detect transferred genes in realistic simulations where gene trees are reconstructed from sequences. Prunier proposes a single scenario that compares to the other methods in terms of sensitivity, but shows higher specificity. We show that LGT scenarios carry a strong signal about the position of the root of the species tree and could be used to identify the direction of evolutionary time on the species tree. We use Prunier on a biological dataset of 23 universal proteins and discuss their suitability for inferring the tree of life.

Conclusions:

The ability of Prunier to take into account branch support in the process of reconciliation allows a gain in complexity, in comparison to EEEP, and in accuracy in comparison to RIATA-HGT. Prunier's greedy algorithm proposes a single scenario of LGT for a gene family, but its quality always compares to the best solutions provided by the other algorithms. When the root position is uncertain in the species tree, Prunier is able to infer a scenario per root at a limited additional computational cost and can easily run on large datasets.

Background

The systematic reconstruction of molecular phylogenies based on the diversity of genes found in complete genomes reveals an unforeseen degree of incongruence among gene trees. Different reasons, either biological or methodological, explain this diversity of patterns. First, evolutionary mechanisms such as gene duplication and loss, lateral gene transfer (LGT) and incomplete lineage sorting generate gene histories that deviate from that of species [START_REF] Boussau | Genomes as documents of evolutionary history[END_REF]. In unicellular organisms, and particularly Bacteria and Archaea, most of the real phylogenetic conflict is likely the result of LGT [START_REF] Doolittle | Phylogenetic classification and the universal tree[END_REF][START_REF] Gogarten | Prokaryotic evolution in light of gene transfer[END_REF]. On the other hand, the reconstruction of gene histories based on sequence alignments is not trivial, and many artifacts are known which produce aberrant phylogenies due to stochastic effects or inadequate models of sequence evolution [START_REF] Philippe | Early-branching or fast-evolving eukaryotes? An answer based on slowly evolving positions[END_REF][START_REF] Brinkmann | An empirical assessment of long-branch attraction artefacts in deep eukaryotic phylogenomics[END_REF][START_REF] Rodríguez-Ezpeleta | Detecting and overcoming systematic errors in genome-scale phylogenies[END_REF][START_REF] Than | Confounding factors in HGT detection: statistical error, coalescent effects and multiple solutions[END_REF]. A challenge in the understanding of the patterns and processes of genome evolution is therefore to sort out these different sources of conflict.

The question of identifying LGTs based on phylogenies typically applies to the following data: first, a gene phylogeny, characterized by an unrooted tree topology, with branch lengths and statistical support for internal branches; and second, some knowledge of the evolutionary relationships among the organisms represented in this tree, ideally a rooted species phylogeny. Events of LGT can then be invoked to explain the topological discrepancies between the two trees. Among the various approaches that have been proposed to resolve the prob-lem of tree reconciliation, the MAF (maximum agreement forest), and the closely related SPR (subtree pruning and regrafting) arguably represent the most appropriate models for the replacement of genes by LGT. The MAF problem consists in finding the smallest number of edges to cut in both trees in order to obtain two identical "forests" of rooted subtrees [START_REF] Rodrigues | Some Approximation Results for the Maximum Agreement Forest Problem[END_REF][START_REF] Rodrigues | The maximum agreement forest problem: Approximation algorithms and computational experiments[END_REF]. The SPR problem also corresponds to minimizing the number of subtrees to cut in a tree, but adds extra complexity by searching for the optimal place to regraft them. In the case of a rooted species tree, both approaches are equivalent to minimizing the number of LGTs that occurred in the gene family. These problems are known to be computationally difficult, but several algorithms have been proposed, notably to efficiently address the SPR problem. For instance, Than and Nakhleh have proposed a decomposition approach, implemented in the RIATA-HGT program [START_REF] Nakhleh | RIATA-HGT: A Fast and Accurate Heuristic for Reconstructing Horizontal Gene Transfer[END_REF][START_REF] Than | SPR-based Tree Reconciliation: Non-binary Trees and Multiple Solutions[END_REF], which identifies regions of the tree where the conflict can be resolved independently, and thus significantly reduces the complexity of the SPR reconciliation in many cases. EEEP also implements such a decomposition [START_REF] Beiko | Phylogenetic identification of lateral genetic transfer events[END_REF], and adds the possibility to restrict the type of SPR moves to those that immediately reduce the discordance among trees.

Obviously, an incorrectly reconstructed gene tree will lead to the inference of erroneous LGTs. It is therefore essential to take into account all information at hand on the reliability of the observed topological conflict, such as the length and support of all branches. Methods of LGT detection based on topological comparisons sometimes propose ways to incorporate the statistical information of the gene tree [START_REF] Than | SPR-based Tree Reconciliation: Non-binary Trees and Multiple Solutions[END_REF][START_REF] Than | Integrating Sequence and Topology for Efficient and Accurate Detection of Horizontal Gene Transfer[END_REF][START_REF] Beiko | Phylogenetic identification of lateral genetic transfer events[END_REF]. RIATA-HGT [START_REF] Than | SPR-based Tree Reconciliation: Non-binary Trees and Multiple Solutions[END_REF] first performs a purely topological reconciliation that proposes a collection of LGT scenarios. Each transfer is associated with a value which depends on the statistical support of the conflict it resolves in the gene tree, and the user can choose to ignore LGTs under a given threshold. EEEP [START_REF] Beiko | Phylogenetic identification of lateral genetic transfer events[END_REF] uses a different approach in which internal branches of the gene tree having a statistical support below a given threshold are collapsed a priori, before the trees are reconciled.

The two approaches described above have been implemented and tested on simulated datasets [START_REF] Than | SPR-based Tree Reconciliation: Non-binary Trees and Multiple Solutions[END_REF][START_REF] Beiko | Phylogenetic identification of lateral genetic transfer events[END_REF]. The main concern in both simulation setups was to evaluate time performance and the ability of the methods to recover the number of simulated LGTs in a gene tree. However, biologists are usually interested not only in the number of LGTs but more importantly in identifying the actual events of gene transfer, i.e. the exact set of species that are "misplaced" in the gene tree. Both approaches generally propose a number of evolutionary scenarios, but their accuracy has not been evaluated so far.

Here, we use simulations to explore the ability of different methods to detect events of transfers based on gene trees reconstructed from sequences. We introduce a greedy algorithm called "Prunier" [START_REF] Prunier Homepage | [END_REF], which uses information on topology, statistical support and branch lengths to quickly identify a maximum statistical agreement forest (MSAF) that corresponds to a most parsimonious scenario of transfer. Prunier uses a customizable statistical agreement function. Two implementations of this function were tested: a fast one based on branch support, and a more advanced one which uses the expected likelihood weights (ELW) test [START_REF] Strimmer | Inferring confidence sets of possibly misspecified gene trees[END_REF]. We show that working on reconstructed trees strongly affects the ability of different methods to identify transfer events. Although all methods can roughly estimate the number of LGTs that occurred in a gene history, the accuracy of proposed scenarios varies largely. In comparison with other methods, Prunier has lower false positive rate, which makes it a more accurate approach to detect LGTs in almost all simulated situations, especially for complicated gene histories. When tested on biological data of 23 universal proteins with hypothetical reference trees, Prunier revealed high rates of LGT, in particular in genes that are known to be prone to transfer. However, the degree of conflict in these genes raises concern on the approach used to reconstruct universal trees.

Results

Prunier Algorithm Objectives

The phylogenetic detection of lateral gene transfers relies on differences between a gene tree T G , with branch lengths and support values, and a reference species tree T S on the same set of species S. Our method takes both trees as input. For clarity, we will suppose that the species tree is rooted, though the method offers the possibility of using an unrooted reference tree as input, with a reasonable increase in complexity (see Material and Methods). The input gene tree is always unrooted, and a byproduct of the procedure is to output a restrained set of root locations on the gene tree. Here we consider that topological differences between T S and T G can result either from LGT or from stochastic effects in the process of gene tree reconstruction. Therefore, an agreement function is needed to decide whether observed topological differences among trees are significant or not. Examples of such functions are maximum-likelihood tests comparing trees given a sequence alignment: KH (Kishino-Hasegawa [START_REF] Kishino | Evaluation of the maximum likelihood estimate of the evolutionary tree topologies from DNA sequence data and the branching order in hominoidea[END_REF], SH , AU (approximately unbiased [START_REF] Shimodaira | An approximately unbiased test of phylogenetic tree selection[END_REF] or ELW (expected likelihood weights [START_REF] Strimmer | Inferring confidence sets of possibly misspecified gene trees[END_REF] tests. Because these tests all take unrooted trees as input, we used additional criteria to be able to handle the disagreement for the position of the root when necessary (see Material and Methods). We also propose a faster alternative which simply considers the statistical support of internal branches. Two (sub-)trees are said to disagree if they fail the agreement function.

If a species tree and a gene tree disagree (based on the agreement function), the objective is to decompose them into a statistically agreeing forest. For a subset S i of the set of species S, we note T(S i ) the subtree of T containing exactly S i where internal nodes of degree 2 are contracted. We aim at partitioning the set of species Sinto a minimum number of subsets S 1 ,...,S k such that for each subset S i , the two subtrees T S (S i ) and T G (S i ) agree, and all T S (S i ) as well as all T G (S i ) are disjoint. We call this partition a maximal statistical agreement forest (MSAF), in reference to the maximal agreement forest [START_REF] Rodrigues | Some Approximation Results for the Maximum Agreement Forest Problem[END_REF][START_REF] Rodrigues | The maximum agreement forest problem: Approximation algorithms and computational experiments[END_REF], which is the particular case where the agreement function gives a positive answer only if the two compared (sub-)trees are homomorphic (have the same topology).

Among S 1 ,...,S k , only one subset contains the root of the species tree. This is the non-transferred "backbone" of the tree as the root is its most ancient node and cannot acquire a gene from one of its descendants. The other T S (S i ) of the forest are interpreted as LGTs that occurred in the last common ancestor of S i ,. Their number (k-1) is the minimum number of transfer events that have to be invoked to explain the significant differences between the two trees.

Greedy Algorithm

We use a greedy procedure to approach the maximum statistical agreement forest of two trees (see Fig. 1). Conflicting edges of the gene tree are those inducing bipartitions that are not in the species tree. A transfer event is characterized by a subtree T G (S i ) that is in agreement with the corresponding T S (S i ) but whose position is conflicting. In other words, an LGT results in a non conflicting edge whose removal decreases the conflict among trees. A non conflicting edge e cuts T S in two subtrees, one containing the root, the other defining a common clade S i . If T G (S i ) and T s (S i ) agree, the "conflict score" of e is a function (detailed in Material and Methods) of the number and support of the conflicting edges that are eliminated if e is removed from the tree. We consider the non conflicting edge with the highest conflict score as defining the most likely transfer. The procedure (Fig. 1) can be briefly described as follows:

• While the gene tree and species tree disagree: ▪ Remove the edge defining a statistically agreeing common clade with maximal conflict score Often, several edges have the same conflict score. In this case, a different criterion is used to choose what edge to cut among top rating edges. We first use the alignment of the gene family to estimate branch lengths on both the gene and reference trees using Treefinder [START_REF] Jobb | TREEFINDER: a powerful graphical analysis environment for molecular phylogenetics[END_REF]. Then, for each candidate edge, we compute the difference between its lengths in both trees and cut the one with the highest difference. We hence remove the branch that is most affected when constrained to its reference position. In practice, branch lengths are estimated only once. This step appears to be necessary in most gene families and it accounts for most of the computing time in the "fast" implementation of Prunier.

Because only non conflicting edges are removed, the procedure always produces two subtrees, one of which is in agreement by construction, and the other (which contains the root) can be used recursively as an input of the function. Eventually, a statistical agreement forest is reached and each component of this forest which does not contain the root of T G is interpreted as originating from a transfer event. A scenario of transfer can readily be constructed from the comparison of T G with the forest.

The algorithm and its implementation are fully detailed in the Material and Methods section. In particular, the definition of the agreement function, conflict score and the position of the root are discussed.

Accuracy on simulated LGTs

We used the procedure described in [START_REF] Galtier | A model of horizontal gene transfer and the bacterial phylogeny problem[END_REF] (see Material and Methods for details) to generate 330 gene trees and corresponding sequence alignments with increasing number (from 0 to 10) of LGTs. Gene trees were simulated with subtree pruning and regrafting (SPR) operations from a 40-taxa rooted reference tree. Gene sequences were simulated along gene trees with variable rates of evolution among branches and sites (See Material and Methods for details). Maximum-likelihood (ML) trees were reconstructed using the resulting alignments. We used a different model of substitution than that used for sequence simulations to increase the chance of topological conflict resulting from reconstruction artifacts. All results of the simulation procedure are available as supplemental information (additional file 1, "simulated_dataset_prunier.zip").

We compared the performances of RIATA-HGT [START_REF] Than | SPR-based Tree Reconciliation: Non-binary Trees and Multiple Solutions[END_REF] (available in the PhyloNet package [START_REF] Than | PhyloNet: a software package for analyzing and reconstructing reticulate evolutionary relationships[END_REF], EEEP [START_REF] Beiko | Phylogenetic identification of lateral genetic transfer events[END_REF] and Prunier based on this simulated dataset.

Accuracy of detected transfer events

Rather than focusing on the accuracy of the number of detected LGTs as in previous simulation studies [START_REF] Nakhleh | RIATA-HGT: A Fast and Accurate Heuristic for Reconstructing Horizontal Gene Transfer[END_REF][START_REF] Beiko | Phylogenetic identification of lateral genetic transfer events[END_REF][START_REF] Than | SPR-based Tree Reconciliation: Non-binary Trees and Multiple Solutions[END_REF], we concentrated on the comparison of inferred scenarios with the true (simulated) one. Among the proposed LGT events, we counted the number of true and false positives (respectively TP and FP) for each method. In subsequent comparisons, all three methods used the same threshold for branch support: for EEEP, branches under this threshold are collapsed a priori; for RIATA-HGT, among all inferred transfers only those crossing a branch above this threshold were retained; and for Prunier, two trees were in agreement if they had no conflicting edges above this threshold. Fig. 2 shows the number of TP (fig. 2A) and FP (fig. 2B) as a function of the true number of LGT events, with a threshold of 0.90 (see additional files 2 and 3 for results with a 0.60 threshold:

"TP_HGT_multi-scenar_BP60.pdf" and "FP_HGT_multi-scenar_BP60.pdf" ). For clarity, the results of another agreement function based on the ELW test [START_REF] Strimmer | Inferring confidence sets of possibly misspecified gene trees[END_REF] (Prunier-slow) which gave results very close to Example of reconciliation of an unrooted gene tree T G with a rooted species tree T S by searching for the maximum statistical agreement forest (MSAF). In the gene tree, blue branches are those common to the two trees whereas red branches indicate conflicting edges, i.e., those found in T G but not in T S . Support values are shown for conflicting edges. In this example, two rounds are needed to reconcile the two trees. The agreement function "Agree" corresponds here to the "fast" version of Prunier: a gene (sub-)tree is considered in statistical agreement with the species (sub-)tree if no conflicting edge above 80 exists. At each round, clades corresponding to common edges (blue branches) are ranked by decreasing scores. This score reflects the conflict (combination of the support values) removed when the edge is cut (symbolized by "Rm{clade}"). The highest scoring subtree candidate to transfer is removed if it is in agreement with the species tree. The output of Prunier is a statistical agreement forest (SAF), composed of a reconciled backbone subtree (non-transferred sequences: {ABFGHIK}) and as many reconciled subtrees (transferred sequences) as lateral gene transfers (LGT). In this example, two LGT events are inferred: {J} and {CDE} have been transferred.

!

"" # $% & ' ( (" )! $% # ' & (" )! *+* , -+ . !
Prunier-fast are not presented. While Prunier gives a single scenario, both RIATA-HGT and EEEP generally propose several solutions that are equivalent in terms of number of events. We chose to show the performance of these programs by recording both the worst (with minimum TP and maximum FP) and best (i.e. with maximum TP and minimum FP) scenarios.

To obtain an idea of the best possible estimate of the number of detectable LGTs in our simulations, we ran RIATA-HGT on the true gene trees (those used for sequence simulations), and kept as a reference the best scenario proposed (see Material and Methods for why not all transfers are detectable). For this reference, the estimated number of transfers is quite accurate but the number of FP increases with the number of transfers, remaining under 2 (fig. 2B). The three methods have different behaviors with increasing number of transfers. RIATA-HGT performs relatively well at identifying true transfer events (fig. 2A), but consistently infers false positives, even when no transfers have been simulated (fig. 2B). Surprisingly, this number of FP does not increase significantly with the number of transfers. EEEP is very good at detecting zero or one transfer, but then increasingly fails at producing any transfer scenario, with more than 50% of failure for the 10-transfer category. Prunier is comparable to RIATA-HGT for the detection of TP (fig. 2A), but has lower rates of FP (fig. 2B). The rate of FP increases with the number of simulated transfers to reach the same level as RIATA-HGT with 10 transfers.

Accuracy of transfer scenarios

Many studies trying to resolve controversial phylogenetic relationships among species have used LGT detection as a first step to retrieve sets of orthologous genes (e.g., [START_REF] Brown | Universal trees based on large combined protein sequence data sets[END_REF][START_REF] Lerat | From gene trees to organismal phylogeny in prokaryotes: the case of the gamma-Proteobacteria[END_REF][START_REF] Ciccarelli | Toward automatic reconstruction of a highly resolved tree of life[END_REF][START_REF] Fitzpatrick | Genome phylogenies indicate a meaningful alpha-proteobacterial phylogeny and support a grouping of the mitochondria with the Rickettsiales[END_REF][START_REF] Williams | A robust species tree for the alphaproteobacteria[END_REF]. In such case, it is essential that all LGT events are correctly detected in a gene family. We thus measured the proportion of gene trees in which all events of LGT were LGT events detected in maximum-likelihood gene trees are displayed as a function of the real number of transfers per tree. Results were computed with a support threshold for topological conflict significance of 0.90. As EEEP and RIATA-HGT may propose multiple scenarios, grey areas represent the variability between the worst and the best scenarios. Areas are delimited by blue borders for RIATA-HGT and green borders for EEEP. Prunier (fast version) results are drawn in magenta. The black curves symbolize the reference boundary: those curves were obtained using RIATA-HGT (best scenario selected) on true gene trees (before sequence simulation). The green numbers below the true positives area of EEEP represent the number of unresolved cases (either quoted as "Unsolved" by the program, or resulting from a program crash). The blue numbers above RIATA-HGT TP area indicate the two cases for which the program crashed. A program crash is counted as 0 TP and 0 FP. The grey line shows a relationship 1:1 between the two axes. The estimated number of transfers by each method is the sum of the curves shown in A and B.

correctly identified (100% TP and 0% FP) (Fig. 3, see additional file 4 "Pc_true_LGT_events_BP60.pdf" for results with a 0.60 threshold). For Prunier and EEEP, the percentage of exact scenarios is high for low numbers of transfers, but drops relatively quickly to zero. For gene families with three transfers, these methods predict the correct scenario in about 50% of the cases. For RIATA-HGT, the proportion of correctly predicted scenarios is low even with few transfers, owing to its high rate of false positives.

Transferred sequences

The positive predictive value (PPV) is the proportion of transferred sequences among those predicted to be transferred. The negative predictive value (NPV) is the proportion of non-transferred sequences among those predicted to be non-transferred. In this evaluation, we do not present the results for EEEP as its rate of failure with high rates of transfers precludes fair comparisons among approaches. We measured the predictive power of RIATA-HGT, selecting the best among all inferred scenarios, and Prunier for a set of simple agreement functions, defined by thresholds ranging from 0.50 to 0.95 (Fig. 4). We also tested for Prunier another agreement function which uses comparisons of the likelihood of entire tree topologies by the ELW test [START_REF] Strimmer | Inferring confidence sets of possibly misspecified gene trees[END_REF] (Prunierslow). All values were computed on the 330 simulated gene trees.

The NPV is very similar among both methods (between 75% and 80%), and variations of the agreement function have only little effect on this value, although for all parameters, RIATA-HGT is slightly better than Prunier. In contrast, the PPV varies greatly with the threshold, especially for Prunier, but with consistently higher PPV than RIATA-HGT. These results can be summarized by computing the accuracy of the two methods, which is the proportion of correctly classified sequences (transferred or not). The accuracy ranges between 73% and 77% (mean of 74%) for RIATA-HGT, and lies between 77% and 79% (mean of 78%) for Prunier.

Impact of the root of the species tree on reconstructed scenarios

Prunier proposes by default a scenario for every possible root of the species tree (see Materials and Methods). Different rootings of the species tree are expected to give different LGT scenarios, because the choice of a root constrains the clades that can be transferred. Especially, the number of transfer events is expected to be different. We examined the possibility that LGTs could inform on the true position of the root. For each of the 77 possible roots of our 40 leaves species tree, we counted the number of inferred LGTs in the 330 simulated gene families. For instance, the total number of LGTs ranged between 1370 and 1549 with a threshold of 0.90. The true root was among the two locations with the minimal number of LGT, the other one being on a neighboring edge. However, a Wilcoxon paired test showed that only 50 among the 77 possible roots were significantly different from the best root. This establishes LGT as a potential tool for rooting species trees but suggests that many gene families and relatively high rates of transfer are necessary to discern the true root.

Application to a biological dataset

We used the dataset of Brown and colleagues [START_REF] Brown | Universal trees based on large combined protein sequence data sets[END_REF] which contains 23 universal proteins distributed in 45 species from the three domains of life. This study pioneered a number of more recent analyses in which LGTs are searched in order to obtain a set of orthologous genes that can be concatenated to resolve a specific question [START_REF] Ciccarelli | Toward automatic reconstruction of a highly resolved tree of life[END_REF][START_REF] Fitzpatrick | Genome phylogenies indicate a meaningful alpha-proteobacterial phylogeny and support a grouping of the mitochondria with the Rickettsiales[END_REF][START_REF] Williams | A robust species tree for the alphaproteobacteria[END_REF]. In their article, Brown et al. focused on the elimination of gene transfers among domains, by manually removing those gene families that supported a nonmonophyletic bacterial domain. Nine gene families were removed on this criterion, which reduced the dataset to 14 genes. Two different species trees were reconstructed: a first one based on the whole dataset (23 genes), which was deemed artifactual due to LGT and a second one based on the cleansed dataset (14 genes). The two trees mainly disagreed on the position of the early diverging bacterial phyla, respectively spirochaetes and hyperthermophiles.

Although detecting transferred genes with a certain reference tree and using the remaining sequences to infer a tree would be a circular reasoning, it is possible to use our algorithm to test the hypothesis that a dataset is devoid of LGT. We ran Prunier (slow and fast version with a threshold of 0.80 and 0.90) using both trees as a reference, and looked at the number of transfers inferred in the 23 genes. The simulation results showed very similar results for the slow and fast version of Prunier (for example, the number of detected transfers by the slow and fast methods and the threshold of 0.80 were correlated with R = 0.97). With real data, we also observed a high correlation among different agreement methods (the best being between slow and fast_0.80: R = 0.63) but with marked differences for some gene families. For instance the initiation factor 2 (IF-2) gene tree is found to be completely congruent with the 23-gene reference tree using the slow test, while the fast version infers 9 transfers. Reciprocally, some other genes showed higher transfer rates with the slow test, for instance ribosomal protein S11 where 13 (23-gene tree) or 11 (14-gene tree) LGTs were detected with the slow version versus one with the fast version, for both reference trees. The mean number of transfers invoked in the two sets of genes identified by Brown et al. is significantly different, for the fast version, regardless of the reference tree (Wilcoxon test between numbers of transfer events for each tree shown in Table 1: p-value = 0.04 for both fast_0.80 and fast_0.90 with the 23-gene tree, p-value = 0.004 and 0.03 with the 14-gene tree for fast_0.80 and fast_0.90, respectively). This suggests that the manual criterion originally used by Brown et al. [START_REF] Brown | Universal trees based on large combined protein sequence data sets[END_REF] for gene exclusion correctly identified genes with high transfer rates. Nevertheless, many among the 14 genes retained in the second dataset show a significant amount of transfers with our method. This raises the question of whether the combination of such a limited amount of genes with such a strong degree of conflict can really yield a reliable species tree.

Discussion

Detecting LGTs using phylogenetic approaches is a challenge for several reasons. First, the reconstruction of optimal scenarios explaining the discrepancies between two trees is a complex algorithmic problem. Second, in practice, not all of these discrepancies require a biological explanation, because reconstructed gene trees are imper- fect representations of a true gene history. We aimed at testing approaches that propose reconciliation scenarios in the typical situation faced by biologists, i.e., the comparison of an unrooted gene tree reconstructed from sequences with a rooted reference. Two published methods, EEEP and RIATA-HGT corresponded to these criteria. We propose here a new algorithm that applies to this situation, along with an evaluation of its performance in comparison to EEEP and RIATA-HGT on a simulated dataset.

Simulating LGT

It is difficult to simulate datasets that compare to real ones, in particular in terms of the phylogenetic artifacts they produce. We used a procedure [START_REF] Galtier | A model of horizontal gene transfer and the bacterial phylogeny problem[END_REF] that creates SPR movements on a rooted reference tree and then simulates different evolutionary rates among branches of the tree and sequence sites, attempting to produce as realistic as possible gene alignments. We then reconstructed ML trees with a model of sequence evolution different from the one used for sequence simulation.

The results of our simulations show that working on reconstructed gene trees poses a substantial problem to LGT detection methods. This is evident from the comparison of the result of RIATA-HGT when used on simulated vs. reconstructed gene trees (Reference vs. RIATA-HGT results in Fig. 2 to 4). The best scenario among those provided by RIATA-HGT on the simulated gene trees (without sequence simulation) was used as a measure of the best scenario inferable. According to this reference, most transfers (>80%) are detectable and the expected amount of false positives is relatively low (Fig. 2B).

All methods were able to correctly identify simulated LGT events to a certain extent. EEEP appeared quite accurate when proposing a solution, but its frequency of failure (that is, the program stops without LGT scenario output) makes it difficult to use with high levels of transfers. In contrast, the two other programs almost always gave a result and generally produced reasonably good solutions, even with complex transfer scenarios. However, RIATA-HGT is characterized by high rates of false positives which explain a consistently low proportion of exact RIATA-HGT scenarios even with few LGT events (Fig. 3).

A new approach for transfer detection driven by statistical criterion

Our new approach, Prunier, sequentially cuts branches that are found to generate significant conflict among trees. We reasoned that a fast way to reach agreement between trees is to first cut those branches that are responsible for the highest part of the conflict. Accordingly, Prunier relies on a ranking of branches that are common to the two trees based on the amount of conflict that is removed when the branch is cut. In the current implementation, this amount of conflict is a function that depends on the statistical support of internal branches in the gene tree (see Material and Methods) and the branch with the highest rank is cut first. The algorithm is thus directed by statistical information provided by branch support in the gene tree and estimating the statistical support of branches is a prerequisite of the application of Prunier. This contrasts with EEEP and RIATA-HGT, where branch support is only used to discard some irrelevant groupings. These approaches rely on combinatorial algorithms that search to enumerate all topological solutions. In contrast, Prunier uses statistical information in the gene tree to guide its search and avoid non significant transfer events to be invoked. As a result, RIATA-HGT and EEEP usually propose a set of scenarios that are equivalent in terms of number of transfers, when Prunier always proposes a unique scenario. Although providing a single solution is not necessarily an advantage, the scenarios found by Prunier are always better than the best among those proposed by RIATA-HGT, as Prunier consistently infers fewer false positives for equivalent number of true positives. In comparison with EEEP, the algorithmic shortcut used by Prunier does not seem to alter the performance in terms of quality of the results but appears as a gain in efficiency as Prunier always terminates. We can presume that the type of statistics used by Prunier for branch support is critical for its performance. The LR-ELW values computed by the Treefinder program [START_REF] Jobb | TREEFINDER: a powerful graphical analysis environment for molecular phylogenetics[END_REF] seem to give good results, at least with simulated datasets, but others like bootstrap could also be tested.

Program parameters: threshold and agreement function

Concerning the choice of a support threshold in the fast version, it is important to tune this parameter according to user needs. Higher support value thresholds should be favored when seeking transfer events with high confidence. In contrast, lower thresholds should be preferred when trying to identify orthologous sequence sets. However, the negative predictive value (NPV) does not vary a lot when decreasing the threshold, whereas the positive predictive value (PPV) drops quickly (Fig. 4). This suggests that higher threshold values are a relatively good choice in all situations. When comparing Prunier in its fast and slow versions on simulated data, it appeared that using the maximum-likelihood test ELW as an agreement function instead of a function based on branch support values did not improve the quality of transfer detection (Fig. 4), and that the resulting LGT scenarios are strongly correlated. In this case, it does not seem beneficial to use such a computationally intensive method in Prunier. However, in contrast with simulated results, the fast and slow implementations of Prunier gave correlated but sometimes contrasting estimates of LGT numbers on a real dataset (Table 1). It is difficult to argue for the use of "slow" vs. "fast" agreement functions on such data. However, all methods detected a large number of transfers in most gene families, including those conserved for concatenation. This means that there remains a strong phylogenetic conflict among concatenated genes. Interestingly, tRNA synthetases, which have been reported as prone to transfer, yield particularly high numbers of LGTs.

Rooting the species tree

One particular feature of Prunier is its ability to search efficiently for scenarios of LGT using an unrooted reference tree, thereby proposing different solutions for different possible roots. Interestingly, different roots in the species tree yield different LGT scenarios, and an overall score could be computed on all 330 gene trees. We showed that the best rooted tree (minimum number of LGTs) is the true root of the reference tree. This suggests that non-optimal roots tend to produce more LGTs than the true one. This echoes with previous reports that LGT events, when seen as a shared character, could sometimes provide phylogenetic information [START_REF] Huang | Ancient horizontal gene transfer can benefit phylogenetic reconstruction[END_REF]. We demonstrate here that Prunier provides information for rooting the reference tree, since the true root position was the best (with high support threshold value) or among the best (for lower threshold values, data not shown) in terms of LGT number. Although the number of gene trees necessary to unambiguously root a reference tree is probably high, the LGT criterion could be used to exclude potential roots.

Conclusions

We propose a new method, Prunier, based on the statistical reconciliation of a gene tree and a reference tree by searching for the maximum statistical agreement forest. We compared Prunier and two other programs, EEEP [START_REF] Beiko | Phylogenetic identification of lateral genetic transfer events[END_REF] and RIATA-HGT [START_REF] Than | SPR-based Tree Reconciliation: Non-binary Trees and Multiple Solutions[END_REF] on a simulated dataset attempting to reflect realistic conditions of gene families analyses. Prunier performance and robustness demonstrates its appeal over other tested methods. It proposes a unique scenario of LGTs that compares to the best selected scenarios of the two other methods, produces fewer false positives, in particular compared to RIATA-HGT, and is able to infer true transfer events even for the most complex gene histories, what EEEP fails to do. Being fast and accurate, Prunier can be used to study phylogenomic datasets.

Methods

Implementation and availability of Prunier

Prunier is implemented in C++ language, using the Bio++ library [START_REF] Dutheil | Bio++: a set of C++ libraries for sequence analysis phylogenetics, molecular evolution and population genetics[END_REF]. Maximum-likelihood (ML) estimation of branch lengths and trees, and ELW tests are performed by Treefinder [START_REF] Jobb | TREEFINDER: a powerful graphical analysis environment for molecular phylogenetics[END_REF]. It is available at: http://pbil.univ-lyon1.fr/software/prunier

Dealing with possible rootings

We have presented the MSAF problem with a rooted species tree and an unrooted gene tree as input. However, the exact position of the root of the species tree is often not known. A solution would be to try every root, and give as many scenarios as there are branches in T S . But many root positions are equivalent in the sense that an

LGT scenario for a given root is also valid for all roots that are not included in a transferred subtree. We developed a way to explore more efficiently a set of root positions. Prunier can take two unrooted trees as input, and output several statistical agreement forest (SAF) decompositions, one for each set of equivalent roots.

Let R be a subset of edges of T S , denoting the possible root locations. R, T S and T G are sets of edges, so set operations or \ are used. At first, R might be either the set of all edges in T S , if no information is available on the root position in the species tree, or any subset of branches given by the user. A non conflicting edge e of T S cuts T S into two disjoint subtrees T S (S i ) and T S (S j ). S j is a possible common clade if Ris not fully included in T S (S i ). For each possible common clade S i a conflict score is computed if T G (S i ) statistically agrees with T S (S i ) and the top scoring S i is selected. If for the top scoring S i , (T S (S i R) = Ø, S i is considered as a group of transferred species and is removed from T S and T G . If (T S (S i ) R) = Ø, the two possible positions of the root, R T S (S i ) and R T S (S j ), are examined: either the root is not in S i and S i is considered as a group of transferred species or the root is in S i and the next top scoring common clade is searched with R = R T S (S i ). It results in a bifurcating procedure where the number of explored scenarios is lower than the number of possible roots of T S . The procedure to approach the MSAF can be described as follows:

Input: two unrooted trees T S and T G , and a subset R of edges of T S where the root may lie: {T S , T G , R}.

Output: a decomposition in a SAF for each root position contained in R.

• If T S and T G disagree: ▪ Find the common clade S i , such that T S (S i ) and

Definition of the Agreement function

A MSAF of a species tree and a gene tree has two types of components: a backbone tree where the root of the species tree lies, which is interpreted as the set of non transferred sequences, and as many subtrees as inferred transfers. The backbone tree in T G contains the root but without information on its exact position. In contrast, all transferred subtrees are rooted by the backbone in both T S and T G . An appropriate agreement function must hence handle both rooted (transferred) and unrooted (backbone) trees.

The method can potentially handle any agreement function. We implemented two variants, respectively called "slow" and "fast" versions.

-A "slow" implementation that depends on the ELW test with a default p-value of 0.05 [START_REF] Strimmer | Inferring confidence sets of possibly misspecified gene trees[END_REF]. Because ELW is an unrooted test, our agreement function first checks for the presence of a well supported bipartition in conflict with the position of the root. The threshold for this additional criterion is set by default at 0.90.

-A "fast" implementation where two (rooted or unrooted) trees are said to be in agreement if the two trees do not contain any supported conflicting edge according to a user defined threshold. This test handles both rooted and unrooted trees.

Scoring candidate transfers

For each edge e of the tree, we have a support value SV(e). In our implementation, we use the LR-ELW (local rearrangement ELW) support values given by Treefinder [START_REF] Jobb | TREEFINDER: a powerful graphical analysis environment for molecular phylogenetics[END_REF], but any other statistics can be used.

For each clade S i , let e 1 ,...,e n be the conflicting edges of T G and T S that are no longer conflicting in T G \S i and T S \S i .The score of S i is defined by: This value is meant to assess the amount of conflict the group S i is responsible for. The power law, empirically set to the value of 5, is a way of favoring groups removing highly supported conflicting bipartitions.

Simulations of LGT

We used the program described by Galtier [START_REF] Galtier | A model of horizontal gene transfer and the bacterial phylogeny problem[END_REF] to simulate LGT and sequence alignments. This program starts from a rooted species tree and modifies it to introduce evolutionary rate variations between species. Then gene trees are generated from the reference trees. Transfers are created by subtree pruning and regrafting (SPR operations) of random clades, where donors and acceptors are drawn according to a Poisson law. Time constraints are given by branch lengths, allowing transfers to occur only between contemporary lineages. Variations of evolutionary rate among genes (diameter of the tree), and between lineages are finally introduced. Then artificial sequences are simulated along each gene tree, under a given model of substitution. Evolution of sequences also includes random substitution rate variations between sites.

We simulated a dataset based on a 40-taxon species tree, with a uniform gene length distribution between 100 and 400 amino-acids, under a JTT model of substitution [START_REF] Jones | The rapid generation of mutation data matrices from protein sequences[END_REF]. Number of transfers increased from 0 to 10. We simulated 30 alignments and trees per number of gene transfers, resulting in a final dataset of 330 simulations.

In order to increase the level of difficulty of our simulated dataset, and thus come closer to real biological datasets, maximum-likelihood (ML) gene trees were reconstructed with Treefinder [START_REF] Jobb | TREEFINDER: a powerful graphical analysis environment for molecular phylogenetics[END_REF] (WAG [START_REF] Whelan | A general empirical model of protein evolution derived from multiple protein families using a maximum-likelihood approach[END_REF] + G8 + I + F) from the simulated gene alignments. The simulated dataset can be downloaded at http://pbil.univ-lyon1.fr/ software/prunier/simulated_dataset_prunier/ or found in the additional file 1: "simulated_dataset_prunier.zip".

Dealing with invisible LGT

Certain simulated transfers have no impact on the phylogeny, and thus are phylogenetically undetectable, even if they are biologically sound. A transfer between sister taxa, or between a father and his son will not provoke any topological conflict. These transfers were filtered out, in order to quantify how many transfer events, among those detectable, have been correctly detected. Nevertheless, one has to keep in mind that these transfers might exist, and that the number of detected LGTs is therefore underestimated by phylogenetic methods of transfer detection. Multiple transfers can also be indistinguishable when ancestors of sister groups independently received gene from a same species. For example if two sister groups receive a gene from the same donor, a detection based on topology discrepancies would infer one LGT instead of two. These transfers were not sorted out and some instances of such transfers can be present in the dataset. This is why we used a topological reconciliation of simulated gene trees before sequence simulation to roughly estimate the amount of detectable transfers.

Benchmark on simulations: estimating the performance of LGT detection methods

Different statistics were used to evaluate the performance of all LGT detection programs. For transfer events, we calculated the number of true and false positives (TP and FP). It was not possible to compute a number of true and false negatives (TN and FN) for transfer events because sequences that are not cut out of the tree do not correspond to a single event. Therefore, we also defined TP, FP, TN and FN for leaves of the tree that were either correctly or incorrectly cut out by an inferred transfer event. This allowed us to compute a sensitivity (true positive rate), specificity, positive and negative predictive values (PPV the precision, and NPV respectively), and accuracy (P standing for positives, N standing for negatives) such that:

Comparing root scenarios

In order to compare scenarios of transfers between all possible roots, we performed all possible paired-Wilcoxon tests between number of transfers per gene families, and applied to the computed p-values a false discovery rate correction for multiple comparisons [START_REF]R: A Language and Environment for Statistical Computing[END_REF].

Biological dataset

We used the dataset of Brown and colleagues [START_REF] Brown | Universal trees based on large combined protein sequence data sets[END_REF] (Table 1). This dataset gathers 23 universal proteins, present in 45 species of the three kingdoms of life. These proteins are mainly part of the translational apparatus (tRNA synthetases and ribosomal proteins). The others play a role in transcription, replication or other basal metabolic functions. We ran Prunier (slow and fast versions, the latter with two different support value thresholds: 0.80 and 0.90) on these genes, using both reference trees proposed by Brown et al.: the initial 23-gene tree, and the 14-gene tree obtained on a cleansed set of genes, after the removal of 9 genes suspected of lateral gene transfer on the basis of the non-monophyly of the bacterial domain.

Figure 1

 1 Figure 1Prunier algorithm: example of a Prunier run. Example of reconciliation of an unrooted gene tree T G with a rooted species tree T S by searching for the maximum statistical agreement forest (MSAF). In the gene tree, blue branches are those common to the two trees whereas red branches indicate conflicting edges, i.e., those found in T G but not in T S . Support values are shown for conflicting edges. In this example, two rounds are needed to reconcile the two trees. The agreement function "Agree" corresponds here to the "fast" version of Prunier: a gene (sub-)tree is considered in statistical agreement with the species (sub-)tree if no conflicting edge above 80 exists. At each round, clades corresponding to common edges (blue branches) are ranked by decreasing scores. This score reflects the conflict (combination of the support values) removed when the edge is cut (symbolized by "Rm{clade}"). The highest scoring subtree candidate to transfer is removed if it is in agreement with the species tree. The output of Prunier is a statistical agreement forest (SAF), composed of a reconciled backbone subtree (non-transferred sequences: {ABFGHIK}) and as many reconciled subtrees (transferred sequences) as lateral gene transfers (LGT). In this example, two LGT events are inferred: {J} and {CDE} have been transferred.

Figure 3 Figure 2

 32 Figure 3Inference of correct complete LGT scenarios. Proportion of correctly inferred LGT scenarios, i.e. scenarios with 100% TP and 0% FP as a function of the true number of LGT. Results were obtained with a support threshold for topological conflict significance of 0.90. As EEEP and RIATA-HGT may propose multiple scenarios, grey areas represent the variability between the worst and the best scenarios. Areas are delimited by blue borders for RIATA-HGT and green borders for EE-EP. Prunier (fast version) results are plotted in magenta. The black curve symbolizes the reference boundary was obtained using RIATA-HGT (best scenario selected) on true gene trees.

Figure 4

 4 Figure 4 Accuracy of transferred sequences detection. RIATA-HGT (best scenarios selected) and Prunier (fast version) results are respectively indicated by triangles and circles. The color code corresponds to the different support values tested as a threshold for topological conflict significance. The figure represents the positive predictive value as a function of the negative predictive value (see Material and Methods) of the two methods. Black lines represent the limits given by RIATA-HGT on true trees. These statistics show how often predictions are correct when sequences are classified as transferred (PPV) or not transferred (NPV). A perfect method would have PPV = 1 and NPV = 1.

Table 1 : Analysis of 23 universal gene families with Prunier with two reference trees Protein Alignment length LGT inferred by Prunier (slow and fast version) (* indicates LGT diagnosis by Brown et al. ) 23 genes tree reference tree 14 genes tree reference tree

 1

	Slow	Fast-80	Fast-90	Slow	Fast-80	Fast-90

  Recursively run the program with input {T S \T S (S i ), T G \T G (S i ), R\T s (S i )}, and add S i to the SAF // 2 nd hypothesis on rooting: T S (S i ) does not contain the root, we prune it • For each possible root of the initial set R, output the SAF.

	▪
	É
		É
	É
	É	É
	É
	É
	É

T G (S i ) agree, with maximum conflict score ▪ If (T S (S i ) R) ≠ Ø then Recursively run the program with input {T S , T G , T S (S i ) R} // 1 st hypothesis on rooting: T s (S i ) contains the root, we choose another set of species S i

Université de Lyon; Université Lyon 1; CNRS; INRIA; UMR 5558, Laboratoire de Biométrie et Biologie Evolutive, 43 boulevard du 11 novembre 1918, F-69622 Villeurbanne, France Full list of author information is available at the end of the article

Acknowledgements

SSA is supported by the French "Ministére de l'enseignement supérieur et de la recherche" and the University of Lyon 1. The authors thank Nicolas Galtier for providing his program for transfer simulations, Julien Dutheil for his help in using the Bio++ library, Bastien Boussau and Alain Guénoche for fruitful discussions, Simon Penel, Stéphane Delmotte and Bruno Spataro for recommendations using computational resources. The authors also thank the cc-in2p3 for computational resources. This work has been supported by the Agence Nationale de la Recherche grant ANR-08-EMER-011-03 "PhylAriane" and BLAN08-1_335186 "EcoGenome".

Availability and requirements

• Project name: Prunier • Project home page: http://pbil.univ-lyon1.fr/software/prunier • Operating systems: Linux and Mac OS • Programming language: C++ (Bio++ library: http:/ /kimura.univ-montp2.fr/BioPP/ ) • Other requirements: Treefinder: http:// www.treefinder.de/ • License: freeware • Any restrictions to use by non-academics: none

Additional material