domain: info math nlin sdv

text:
Leonardo Trujillo
email: leonardo.trujillo@inria.fr

Paul Banse
email: paul.banse@inria.fr

Guillaume Beslon
email: guillaume.beslon@inria.fr

Inversion mutations attenuate complexity catastrophe in NK fitness landscapes

Context

In the Kauffman's NK model of rugged fitness landscapes [START_REF] Kauffman | The origins of order: Self-organization and selection in evolution[END_REF], besides the genome length N ∈ N, the integer K ∈ Z (0,N -1) , describes the epistatic interactions between loci and the contribution of each component to the total fitness-which depends on its own value as well as the values of K other loci. The total fitness f ∈ [0, 1) for a binary sequence x ∈ {0, 1} N is then defined as:

f (x) := 1 N N i=1 f i (x i , x i1 , . . . , x i K )
, with the fitness per locus f i which depends on the state of locus x i and K other loci x i K . It is usually assumed that the f i 's are given by independent and identically distributed random variables sampled from a given uniform probability distribution. Two popular schemes of interaction between loci are: the adjacent and random neighborhood models [1, p. 55]. On the other hand, evolution is simulated as adaptive walks, such that a starting genotype x varies through point mutations resulting in a mutated sequence y. Then, if f (y) > f (x), the mutated genotype is selected, otherwise other mutations on x are tested until the fitness increases. The evolutionary dynamics stops when local maximum of fitness is reached. As can be appreciated in figure 1 the average of local fitness maxima f K is not monotonic for different values of K.

In particular for point mutations (red points in fig. 1), Kauffman showed that the expected value of local fitness maxima is monotonically non-decreasing up to a certain value of K and then decreases such that lim K→N -1 f K = 1/2 [START_REF] Kauffman | The origins of order: Self-organization and selection in evolution[END_REF]. This decrease of fitness values toward 0.5 is the well-known "complexity catastrophe" [1, p. 52]. That is, as K increases, the number of possible values of f i is greater. But the number of conflicting constraints due to epistasis can also increase, implying that the accessible local maxima are lower and thus the expected fitness peaks decrease in height.

Results

The adaptive dynamics in the NK model have been studied mainly with point mutations. Nevertheless in molecular evolution there are also structural mutations changing more than one nucleotide, for instance: duplications, inversions and other chromosomal rearrangements. These different types of structural variations are completely overlooked in conventional analysis of the NK model. We show that chromosomal inversions reveal interesting features of adaptive dynamics. In particular, we communicate results from adaptive walks simulations and show that the complexity catastrophe can be attenuated via chromosome inversions. This is sketched in figure 1 for a genome of size N = 100 and inversion mutations with sizes ranging from 1%-a single locus (i.e. inversions are like point mutations)-up to 100% of the genome size, for patterns of adjacent and random (inset plot in fig. 1) epistatic interaction between loci. For the simplest case K = 0, with no epistatic interaction between neighboring loci, we can verify in fig. 1, that the average fitness for all inversions size percentages are equal f K=0 0.667. In this case, the landscape is smooth with only a single peak. This result also agrees with the analyt-ical result f K=0 = 2 3 [1, p. 55]. Then, for K > 0, the average fitness f K increases with K until reaching a maximum value of fitness. After these maximum, the fitness values decrease as K increases. When K → 99, the mean fitness converge to the same value, regardless of the type of epistatic interaction neighborhood. Now, what's new is that for inversions with sizes greater than 1%, the average fitness values are higher than those for mutations of a single locus. Indeed, for K → N -1, the average fitness trend is very different from that of point mutations [START_REF] Kauffman | The origins of order: Self-organization and selection in evolution[END_REF][START_REF] Solow | Understanding and attenuating the complexity catastrophe in Kauffman's NK model of genome evolution[END_REF]. The evolutionary process reaches higher expected fitness values f K=99 > 1/2, for both random and adjacent epistatic interactions, and thus attenuating the complexity catastrophe. Finally, let's note as a curious fact, that when the size of the inversion mutations is equal to 100% (blue points in fig. 1), then f I K=99 = 0.610. We conjecture that for inversion mutations when K → N -1, the complexity catastrophe must converge to the reciprocal of the golden ratio 1/ϕ = 2/(1 + √ 5) ≈ 0.618 . . ..

Fig. 1 .

 1 Fig. 1. The average value of local fitness maxima show that the complexity catastrophe is attenuated by inversion mutations. The behavior of the higher reached fitness vs the epistatic parameter K for point mutations (red) and inversions restricted to a certain size range (sizes values and colors nomenclature are displayed in the figures), averaged for 100 instances of adaptive walks simulations in NK landscapes with adjacent neighboring epistatic interactions. Inset: Display the results with random epistatic interactions.


Aymen Bouaziz
email: bouazizaymen18@yahoo.com

LOCAL LIMITS OF GALTON-WATSON TREES CONDITIONED ON LARGE WIDTH

Keywords: Mathematics Subject Classification. 60J80, 60B10, 05C05 Galton-Watson tree, random trees, local limits, width

We study the local convergence of critical Galton-Watson trees under various conditionings. We give a sufficient condition, which serves to cover all the previous cases, for the convergence in distribution of a conditioned Galton-Watson tree to Kesten's tree. We also propose an other proof to give the limit in distribution of a critical Galton-Watson tree, with bounded support, conditioned on having a large width.

Introduction

In [START_REF] Kesten | Subdiffusive behavior of random walk on a random cluster[END_REF], Kesten proved that a critical or sub-critical Galton-Watson (GW) tree conditioned on reaching at least height h converges in distribution (for the local topology on trees) as h goes to infinity toward the so-called sized-biased tree (that we call here Kesten's tree and whose distribution is described in Section 2.3). Since then, several different conditioning have been studied, in particular, the conditioning of extinction after large time, the conditioning of large total population size and the conditioning of large number of leaves. In [START_REF] Abraham | Local limits of conditioned Galton-Watson trees : the infinite spine case[END_REF], Abraham and Delmas provided a criterion for local convergence of finite random trees to Kestens tree, then gave short and elementary proofs of essentially all previous related results and some new ones. Later, in [START_REF] Abraham | Local limits of Galton-Watson trees conditioned of the number of the protected nodes[END_REF], we prove that a critical Galton-Watson tree conditioned on having a large number of marked vertices converges in distribution to Kesten's tree and we then apply this result to give the limit in distribution of a critical Galton-Watson tree conditioned on having a large number of protected nodes.

Let L(t) be the width of the tree t. Remark that this functional L is clearly monotone in the sense of [START_REF] He | Local Convergence of Critical Random Trees and Continuous-State Branching Processes[END_REF]; therefore, using Theorem 2.1 of [START_REF] He | Local Convergence of Critical Random Trees and Continuous-State Branching Processes[END_REF], we immediately get that a critical GW tree τ conditioned on {L(τ ) > n} converges in distribution toward Kesten's tree as n goes to infinity. In this paper, we propose another proof by generalizing somewhat the monotonicity property. Notice that the functional L does not satisfy additivity in [START_REF] Abraham | Local limits of conditioned Galton-Watson trees : the infinite spine case[END_REF]. Thus, considering the conditioning event {L(τ ) = n} is still an open problem.

We say that a probability distribution p = (p(0), p(1), . . .) on nonnegative integers is bounded, if the set {n ∈ N, p(n) > 0} is bounded. For any critical and bounded distribution p satisfying assumption (1), Xin He [START_REF] He | Local Convergence of Critical Random Trees and Continuous-State Branching Processes[END_REF] provides a positive answer to this question, more precisely he proves that a critical GW tree τ conditioned on {L(τ ) = n} converges in distribution toward Kesten's tree as n goes to infinity.

Provide an other proof of this result is the main objective of this paper. On the technical level, our proofs are extremely short and elementary, thanks in particular to the convenient framework in [START_REF] Abraham | Local limits of conditioned Galton-Watson trees : the infinite spine case[END_REF].

The paper is then organized as follows: In section 2, we recall briefly the framework we use for discrete trees and define the Galton-Watson tree τ and Kesten's tree τ * associated with offspring distribution p. In section 3, we state and prove our general result on local convergence of conditioned critical and sub-critical Galton-Watson trees and we apply it to the conditioning of large width, in the critical case, in Corollary 3.6, which is one of our main objective of this paper.

In section 4, we study the conditioning on having large width of a critical Galton-Watson tree, with bounded support, where we give an elementary and short proof. Finally, we generalized this result by considering a type of conditioning never treated.

Technical background on GW trees

2.1. The set of discrete trees.

We denote by N = {0, 1, 2, . . .} the set of non-negative integers and by N * = {1, 2, . . .} the set of positive integers. We recall Neveu's formalism [START_REF] Neveu | Arbres et processus de Galton-Watson[END_REF] for ordered rooted trees. Let

U = n≥0 (N * ) n
be the set of finite sequences of positive integers with the convention (N * ) 0 = {∅}. For u ∈ U, its length or generation |u| ∈ N is defined by u ∈ (N * ) |u| . If u and v are two sequences of U, we denote by uv the concatenation of the two sequences, with the convention that uv

= u if v = ∅ and uv = v if u = ∅. The set of ancestors of u is the set An(u) = {v ∈ U; ∃w ∈ U such that u = vw}.
The most recent common ancestor of a subset s of U, denoted by M (s), is the unique element u of ∩ u∈s An(u) with maximal length |u|. For two distinct elements u and v of U, we denote by u < v the lexicographic order on U i.e. u < v if u ∈ An(v) and u = v or if u = wiu and v = wjv for some i, j ∈ N * with i < j. We write

u ≤ v if u = v or u < v.
A tree t is a subset of U that satisfies:

• ∅ ∈ t.

• If u ∈ t, then An(u) ⊂ t.

• For every u ∈ t, there exists k u (t) ∈ N such that, for every i ∈ N * , ui ∈ t iff 1 ≤ i ≤ k u (t). The vertex ∅ is called the root of t. The integer k u (t) represents the number of offsprings of the vertex u ∈ t, and we call it the outdegree of the node u in the tree t. The maximal outdegree M (t) of a tree t is defined by M (t) = sup{k u (t), u ∈ t} The set of children of a vertex u ∈ t is given by:

C u (t) = {ui; 1 ≤ i ≤ k u (t)}. By convention, we set k u (t) = -1 if u ∈ t. A vertex u ∈ t is called a leaf if k u (t) = 0. We denote by L 0 (t) the set of leaves of t. A vertex u ∈ t is called a protected node if C u (t) = ∅ and C u (t) L 0 (t) = ∅,
that is u is not a leaf and none of its children is a leaf.

For a tree t, we denote by

Z(t) = Card({u ∈ t, |u| = n})
the size of the n-th generation of t, the height of t is defined by

H(t) = sup{|u|, u ∈ t}
and can be infinite. We define the width L(t) of t as:

L(t) = sup k≥0 Z k (t)•
We denote by T the set of trees, by T 0 = {t ∈ T; Card(t) < +∞} the subset of finite trees and by

T 1 = {t ∈ T; lim n-→+∞ |M ({u ∈ t; |u| = n})| = +∞}
the subset of trees with a unique infinite spine.

We say that a sequence of trees (t n , n ∈ N) converges locally to a tree t if and only if lim n→∞ k u (t n ) = k u (t) for all u ∈ U.

Let (T n , n ∈ N) and T be T-valued random variables. We denote by dist(T ) the distribution of the random variable T and write

lim n-→+∞ dist(T n ) = dist(T )
for the convergence in distribution of the sequence (T n , n ∈ N) to T with respect to the local topology. If t, t ∈ T and x ∈ L 0 (t) we denote by

t x t = {u ∈ t} ∪ {xv; v ∈ t }
the tree obtained by grafting the tree t on the leaf x of the tree t. For every t ∈ T and every x ∈ L 0 (t), we shall consider the set of trees obtained by grafting a tree on the leaf x of t:

T(t, x) = {t x t ; t ∈ T}.
For convergence in distribution in the set T 0 ∪ T 1 , we recall the following key characterization in [START_REF] Abraham | An introduction to Galton-Watson trees and their locals limits[END_REF].

Lemma 2.1. Let (T n ) n∈N and T be random trees taking values in the set T 0 ∪ T 1 . Then the sequence (T n ) n∈N converges in distribution to T if and only if:

(1) for every finite tree t ∈ T 0 , lim n-→+∞ P(T n = t) = P(T = t);

(2) for every finite tree t ∈ T 0 and every leaf x of t, lim inf n-→+∞ P(T n ∈ T(t, x)) ≥ P(T ∈ T(t, x)).

Galton Watson trees.

Let p = (p(n), n ∈ N) be a probability distribution on N. We assume that [START_REF] Abraham | Local limits of Galton-Watson trees conditioned of the number of the protected nodes[END_REF] p(0) > 0, p(0) + p(1) < 1, and µ :=

+∞ n=0 np(n) < +∞.
A T-valued random variable τ is a GW tree with offspring distribution p if the distribution of k ∅ (τ ) is p and it enjoys the branching property: for n ∈ N * , conditionally on {k ∅ (τ ) = n}, the subtrees (S 1 (τ ), . . . , S n (τ )) are independent and distributed as the original tree τ .

The GW tree and the offspring distribution are called critical (resp. sub-critical, super-critical) if µ = 1 (resp. µ < 1, µ > 1).

In the critical and sub-critical case, we have that a.s τ belongs to T 0 .

Kesten's tree.

Let p be an offspring distribution satisfying Assumption (1) with µ ≤ 1 (i.e. the associated GW process is critical or sub-critical). We denote by p * = (p * (n) = np(n)/µ, n ∈ N) the corresponding sizebiased distribution.

We define an infinite random tree τ * (the size-biased tree that we call Kesten's tree in this paper) whose distribution is described as follows:

There exists a unique infinite sequence (v k , k ∈ N * ) of positive integers such that, for every h

∈ N, v 1 • • • v h ∈ τ * , with the convention that v 1 • • • v h = ∅ if h = 0. The joint distribution of (v k , k ∈ N *
) and τ * is determined recursively as follows. For each h ∈ N, conditionally given (v 1 , . . . , v h ) and {u ∈ τ * ; |u| ≤ h} the tree τ * up to level h, we have:

This yields a short and an elementary proof of theorem 4.1 in [START_REF] He | Conditioning Galton-Watson trees on large maximal out-degree[END_REF]. In general, assume that p is critical, A satisfies the identity property in [START_REF] Abraham | An introduction to Galton-Watson trees and their locals limits[END_REF] and P(A(τ ) = n) > 0 for any n, Then by theorem 3.1, as n -→ +∞,

dist(τ |A(τ ) = n) -→ dist(τ * )• and as n -→ +∞, dist(τ |A(τ ) ≥ n) -→ dist(τ * )• Remark 3.4.
Assume that p is critical. If A satisfies the monotonicity property in [START_REF] He | Local Convergence of Critical Random Trees and Continuous-State Branching Processes[END_REF], which is equivalent to A(t x t ) ≥ A(t ) ∀t ∈ T, and P(A(τ ) ≥ n) > 0 for any integer n (consider n 0 = +∞), Then, using Theorem 3.1, we have as n -→ +∞:

dist(τ |A(τ ) ≥ n) -→ dist(τ * )•
Thus, the monotonicity property is a particular case of our result, which provide another and a short proof of Theorem 2.1 in [START_REF] He | Local Convergence of Critical Random Trees and Continuous-State Branching Processes[END_REF].

Remark 3.5. As a conclusion, Theorem 3.1 serves to cover all the different cases (identity, additivity and monotonicity) which allows to give a simple and short proof of theorem 2.2.1 and 2.2.4 in [START_REF] Abraham | An introduction to Galton-Watson trees and their locals limits[END_REF] As direct application, we can recover several specific conditionings in the critical case:

(1) Conditioning on extinction after large time, see [START_REF] Kesten | Subdiffusive behavior of random walk on a random cluster[END_REF][START_REF] Abraham | Local limits of conditioned Galton-Watson trees : the infinite spine case[END_REF], (A = H),

as n -→ +∞ dist(τ |H(τ ) ≥ n) -→ dist(τ * )•
(2) Conditioning on the total population size, (A = Card),

As n -→ +∞ dist(τ |Card(τ ) ≥ n) -→ dist(τ * )•
(3) Conditioning on the number of individuals having a given number of children: Let A be a non-empty subset of N. For a tree t, we denote by L A (t) the total number of nodes in the tree t with outdegree in A.

Assume that k∈A p(k) > 0. Then as

n -→ +∞ dist(τ |L A (τ ) ≥ n) -→ dist(τ * )• (4)
Conditioning on the number of protected nodes, see [START_REF] Abraham | Local limits of Galton-Watson trees conditioned of the number of the protected nodes[END_REF], Let A(t) be the number of protected nodes in the tree t. Then as

n -→ +∞ dist(τ |A(τ ) ≥ n) -→ dist(τ * )•
One of our original motivations for this result is the local convergence under the conditioning of large width. So right now we will apply Theorem 3.1 to this specific conditioning.

Since p 0 + p 1 < 1, we have P(L(τ ) ≥ n) > 0 for any n. Then Theorem 3.1 immediately gives the local convergence of critical GW trees to Kesten's tree, under the conditioning of large width.

Recall that the width L(t) of a tree t is defined to be

L(t) = sup k≥0 Z k (t)• Corollary 3.6. Assume that p is critical. Then as n -→ +∞, dist(τ |L(τ ) ≥ n) -→ dist(τ * )• 4.
The conditioning on the largest generation, critical case Theorem 4.1. Let τ be a critical GW tree with offspring distribution p satisfying (1) with bounded support and let τ * be a Kesten's tree associated to p. Let τ n be a random tree distributed according to τ conditionally on {L(τ

) = n}. Then as n -→ +∞, dist(τ n ) -→ dist(τ * )•
where the limit is understood along the infinite sub-sequence {n ∈ N : P(L(τ ) = n) > 0}.

Proof. We consider A(t) = L(t) with n 0 = 1 that is

A n = {t ∈ T; L(t) = n}• Since p(0) + p(1) < 1, the set {n ∈ N : P(L(τ ) = n) > 0} is infinite.
Let t ∈ T 0 , x ∈ L 0 (t) and n be a large enough integer. We consider

K = sup{n ∈ N, p(n) > 0} < +∞
be the supremum of the support of p. We have

∀ |x| ≤ s ≤ H(t) Z s (t) + Z s-|x| (τ ) ≤ L(t) + K s-|x| < n
We deduce that, L satisfies the property identity, that is:

L(t * x τ ) = n ⇐⇒ L(τ ) = n
According to Theorem 3.1, we deduce the convergence and hence end the proof.

We can generalize these results concerning the width by considering: Let A be a non-empty subset of N. For a tree t and s a non-negative integer, we write The case A = {0}, L (s) A (t) represents the number of leaves in generation s of t and S A (t) the maximum number of leaves in the same generation. We can also have L As, for all t ∈ T 0 , x ∈ L 0 (t) and n be a large enough integer, ∀ |x| ≤ s ≤ H(t) L

L

A

  (t) = {u ∈ t; |u| = s and k u (t) ∈ A} the set of individuals, in generation s, whose number of children belongs to A and L

A

  (t) = Z s (t) and so S A (t) = L(t) the largest generation by taking A = N.Since p(0) + p(1) < 1 and k∈A p(k) > 0, the set {n ∈ N : P(S A (τ ) = n) > 0} is infinite.

  ≤ L(t) + K s-|x| < nThe same work as in the previous proof allows to prove Theorem 4.2. Let τ be a critical GW tree with offspring distribution p satisfying (1) with bounded support and such that k∈A p(k) > 0. Let τ * be a Kesten's tree associated to p. Then as n -→ +∞,dist(τ |S A (τ ) = n) -→ dist(τ * )•where the limit is understood along the infinite sub-sequence {n ∈ N : P(S A (τ ) = n) > 0}. anddist(τ |S A (τ ) ≥ n) -→ dist(τ * )•Note that this type of conditioning is never treated.

Acknowledgements. Sincere thanks to anonymous referees for their comments and suggestions, which improved considerably the presentation of this paper.

• The number of children (k u (τ * ), u ∈ τ * , |u| = h) are independent and distributed according to p if u = v 1 • • • v h and according to p * if u = v 1 . . . v h . • Given {u ∈ τ * ; |u| ≤ h + 1} and (v 1 , . . . , v h ), the integer v h+1 is uniformly distributed on the set of integers {1, . . . , k

Remark 2.2. Notice that by construction, a.s. τ * ∈ T 1 has a unique infinite spine. And following Kesten [START_REF] Kesten | Subdiffusive behavior of random walk on a random cluster[END_REF], the random tree τ * can be viewed as the tree τ conditioned on non extinction. Following [START_REF] Abraham | An introduction to Galton-Watson trees and their locals limits[END_REF], for t ∈ T 0 and x ∈ L 0 (t), we have:

(2)

In the particular case of a critical offspring distribution (µ = 1), we get for all t ∈ T 0 and x ∈ L 0 (t):

Main result

Let A be an integer-valued function defined on T which is finite on T 0 and let n 0 ∈ N ∪ {+∞} be given. We define for all n ∈ N * , the subset of trees

Common values of n 0 that will be considered are 1 and +∞.

The following theorem states a general result concerning the local convergence of critical and sub-critical GW tree τ conditioned on A n toward Kesten's tree and its proof is in fact a straighforward adaptation of the proof of theorem 3.1 in [START_REF] Abraham | Local limits of conditioned Galton-Watson trees : the infinite spine case[END_REF].

We denote by

the conditional law of τ given {τ ∈ A n }.

Theorem 3.1. Assume that assumption (1) hold, µ ≤ 1 and that P(τ ∈ A n ) > 0 for n large enough. Then, if for all t ∈ T 0 and x ∈ L 0 (t),

(3) lim inf n-→+∞

As n -→ +∞, We have

Proof. Since µ ≤ 1, we have a.s τ ∈ T 0 and τ * ∈ T 1 . So we will use Lemma 2.1 to prove the convergence.

Using [START_REF] Abraham | Local limits of conditioned Galton-Watson trees : the infinite spine case[END_REF] or else [START_REF] Bertoin | On largest offspring in a critical branching process with finite variance[END_REF], we have for every t ∈ T 0 , x ∈ L 0 (t) and t ∈ T 0 :

Let t ∈ T 0 and x ∈ L 0 (t). For such n we get:

So, we obtain that 2), we deduce that:

, we deduce that:

(5) lim inf

Furthermore, for all t ∈ T 0 and all n > A(t), we have

Finally, by Lemma 2.1, we have proved this result.

We have several remarks related to Theorem 3.1.

Remark 3.2. However, it seems that the above proof is almost copied from the proof of Theorem 3.1 in [START_REF] Abraham | Local limits of conditioned Galton-Watson trees : the infinite spine case[END_REF], it is easy to see that the sufficient condition in Theorem 3.1 is a particular case of this result.

Remark 3.3. We apply Theorem 3.1 to the Conditioning on the maximal out-degree: Let τ be a critical Galton-Watson tree and let n be a large enough integer, we have for every t ∈ T 0 , x ∈ L 0 (t):