Simona Grusea
email: gruseas@yahoo.com

Measures for the exceptionality of gene order in conserved genomic regions

Keywords: AMS 2000 subject classifications: Primary: 60C05; secondary: 92D15 gene order comparison, distance between permutations, transposition distance, exact distribution, random uniform permutation, conserved genomic regions, reference region approach

We propose in this article three measures for quantifying the exceptionality of gene order in conserved genomic regions found by the reference region approach. The three measures are based on the transposition distance in the permutation group. We obtain analytic expressions for their distribution in the case of a random uniform permutation, i.e. under the null hypothesis of random gene order. Our results can be used to increase the power of the significance tests for gene clusters which take into account only the proximity of the orthologous genes and not their order.

Introduction

The biological context

Comparing genomic organization between different species may help to decipher the evolutionary history of species and also to better understand the biology of nowadays species.

Orthologous genes are two genes, in two different species, that descend from the same gene at the ancestor of the two species, as the result of a speciation event. They tend, in general, to have similar functions. Therefore, finding a group of orthologous genes in close proximity in the genomes of two different species may be the mark of evolutionary relatedness between the two species or the sign of a functional relationship among these genes, together with a functional selective pressure acting on them. But for this to be the case, the observed orthologous gene clusters between the two genomes have to be significant, i.e. very improbable to have appeared by chance.

Over evolutionary time scales, the gene order in one genome can be affected by various genome rearrangement events, like inversions, translocations, transpositions, chromosomic fissions and fusions. Hence, in the absence of certain constraints due to functional selective pressures, the gene order is rapidly randomized. This is one reason why, in general, the null hypothesis taken in the significance tests for gene clusters is the hypothesis of random gene order.

In the literature various definitions for gene clusters exist, and also different statistical tests for detecting gene clusters which are significant from the point of view of the proximity of the orthologs (see [START_REF] Bergeron | The algorithmic of gene teams[END_REF][START_REF] Danchin | Statistical evidence for a more than 800-millionyear-old evolutionarily conserved genomic region in our genome[END_REF][START_REF] Durand | Tests for gene clustering[END_REF][START_REF] Hoberman | The incompatible desiderata of gene cluster properties[END_REF][START_REF] Hoberman | The statistical analysis of spatially clustered genes under the maximum gap criterion[END_REF][START_REF] Raghupathy | Individual gene cluster statistics in noisy maps[END_REF]).

Here we choose a very unrestrictive definition for a gene cluster. We call conserved genomic region or gene cluster two chromosomic regions, in two different species, that have in common a certain number of orthologous genes, not necessarily adjacent or in the same order in the two genomes. We do not impose any restriction on the gap length between consecutive orthologs.

Suppose that we have found an orthologous gene cluster which is significant from the point of view of the proximity of the genes. One might want to take into account also the order of the orthologs in this cluster, considering that the gene clusters in which the gene order is more similar are even more biologically significant.

The goal of this work is to find "good" measures for quantifying the degree of conservation of the order of the orthologs in conserved genomic regions. Here, "good" means both biologically relevant and computationally accessible.

We present in this article three measures based on the transposition distance in the permutation group, together with analytic expressions for their distributions under the null hypothesis of random gene order. Our results may serve as a tool to increase the power of the statistical tests for detecting significant gene clusters.

There are different approaches when searching for gene clusters (see [START_REF] Durand | Tests for gene clustering[END_REF]). In this article we focus on the case where the gene clusters were found by the "reference region" approach, which consists in starting with a fixed genomic region in a certain species A, called the reference region, and searching for significant orthologous gene clusters in the whole genome of another species B.

A genome will be seen as an ordered set of genes. In this article we are only considering the case of genomes with a single chromosome. Also, we are treating only the case of no multigene families, i.e. we suppose that each gene from the reference region in A has at most one ortholog in the genome B.

Previous work

The literature on this subject is just at its beginnings. Sankoff and Haque [START_REF] Sankoff | Power boosts for clusters tests[END_REF] propose three adjacency disruption measures for comparing the order of the orthologs which are in common between two clusters in two genomes. They investigate in more detail the "maximum adjacency disruption" criterion, giving analytic formulas for some values of its distribution under random gene order and also simulation results. They also note the difficulty of taking into account, in a single statistical test, both the proximity of the orthologs and their order.

Recently, Xu and Sankoff [START_REF] Xu | Tests for gene clusters satisfying the generalized adjacency criterion[END_REF] used a parametrized definition of gene clusters based on the notion of generalized adjacency, which allows to take into account gene content and gene order at the same time. For cluster sizes smaller than 4, they derived exact values for the expected number of clusters. For larger cluster sizes, they used simulations to study the distribution of the number of clusters.

In the "genome rearrangements" literature, several genomic distances have been studied, which take into account one or a combination of different types of genomic events: reversals, translocations, chromosomic fissions and fusions, biological transpositions, block-interchanges -see [START_REF] Li | Algorithmic approaches for genome rearrangement: a review[END_REF] for a review.

The problem with using these distances as test statistics comes from the fact that their distribution for a random uniform permutation is in general unknown and there are very few theoretical results on this subject. Recently, Doignon and Labarre [START_REF] Doignon | On Hultman numbers[END_REF] have found the distribution of the number of alternating cycles in the bicolored breakpoint graph of a random (unsigned) permutation, which can be used to deduce the exact distribution of the "block-interchange" distance of Christie [START_REF] Christie | Sorting permutations by block-interchanges[END_REF]. Sankoff and Haque [START_REF] Sankoff | The distribution of genomic distance between random genomes[END_REF] and Xu, Zheng and Sankoff [START_REF] Xu | Paths and cycles in breakpoint graphs of random multichromosomal genomes[END_REF], using a constructive approach, have obtained asymptotic estimates for the distribution of the number of cycles in the breakpoint graph of two random signed permutations, which can be further used to estimate the distribution of the genomic distances based on the breakpoint graph.

The transposition distance

All the three measures that we propose in this article are based on the mathematical transposition distance in the permutation group.

A mathematical transposition applied to a permutation exchanges two elements (not necessarily adjacent) in the permutation. A rigorous definition will be given in the next section.

The genomic equivalent operation would be the exchange of two genes (not necessarily adjacent) in the genome. Therefore, the mathematical transpositions do not model a real biological operation.

The transposition distance is very "nice" from the computational point of view, but could it also be useful in the biological context?

One positive answer to this question is given by Eriksen and Hultman in [START_REF] Eriksen | Estimating the expected reversal distance after a fixed number of reversals[END_REF], where they describe an analogy between mathematical transpositions and genomic reversals. They show that the expected transposition distance in S n after applying t random transpositions to the identity is a very good approximation for the expected reversal distance of a genome with n genes (seen as a signed permutation) after applying t random reversals to the identity. By obtaining a closed formula for the first, they propose an estimate by the method of moments for the true evolutionary distance between two genomes. They show that their method compares well to the best results obtained through other methods.

Similarities between the distributions of the two distances are also discussed in [START_REF] Berestycki | A phase transition in the random transposition random walk[END_REF].

The paper is organized as follows. In Section 2 we present the mathematical framework and formulate the problem. In Sections 3, 4 and 5 we propose three measures for the degree of conservation of gene order in a conserved genomic region, and for each of these measures we derive its exact distribution in the case of a random uniform permutation. Section 6 is dedicated to some concluding remarks and ideas for future work.

We think that the originality of the measures presented in Sections 4 and 5 comes from the fact that they are taking into account not only the order of the genes which are in common between the two clusters, but also the positions of the other orthologs. These measures are specifically adapted to the case where the gene clusters are found by the reference region approach.

We hope that the results obtained in this article are interesting not only in the genomic comparison context, but also in themselves, as a modest contribution to the giant pool of results about the transposition distance in the permutation group.

The mathematical framework

Let n denote the number of genes in the reference region in A which have one and only one ortholog in B.

The null hypothesis that we consider is H 0 : random gene order in the genome B, under which all the n! possible orderings of the n orthologs have the same probability to occur. We label the n orthologs in such a way that their order in the reference region is given by the identity permutation Id n , and we let π denote the permutation representing their order in the genome B.

Under the null hypothesis of random gene order in the genome B, π is a random permutation of n elements, uniformly chosen with probability 1/n!.

For a permutation π ∈ S n , we will use the notation π = [π(1), ..., π(n)].

Suppose that we are interested in the gene order in a certain conserved genomic region R in the genome B, which contains h orthologs and starts with the i-th ortholog, labelled π(i).

In what follows h and i will be fixed. We would like to find a way to quantify the conservation of the gene order in the region R compared to the order of the genes in the reference region.

Notation 1. For a permutation σ ∈ S n and for i ∈ {1, ..., n -h + 1}, we denote by σ i,h the restriction of σ to the set {i, i + 1, ..., i + h -1}, i.e.

σ i,h = [σ(i), ..., σ(i + h -1)].
Note that π i,h contains the labels of the h orthologs from the region of interest R.

For comparing two permutations we will use the transposition distance in the symmetric group S n , which we denote d trp .

We recall that a transposition in the group S n is a cycle of length 2. The composition to the right of a given permutation π = [π(1), ..., π(n)] with a transposition (i, j) results in the permutation π • (i, j) = [π(1), ..., π(i -1), π(j), π(i + 1), ..., π(j -1), π(i), π(j + 1), ..., π(n)],

in which the elements π(i) and π(j) are interchanged.

The permutation group S n is generated by the set of all the transpositions. For two permutations π, σ ∈ S n , the transposition distance d trp (π, σ) is the minimum number of transpositions needed to transform π into σ or conversely.

We will use the following two classical results about permutations (see [START_REF] Diaconis | Group Representations in Probability and Statistics[END_REF], p. 118 for the first one and [START_REF] Comtet | Advanced Combinatorics: The Art of Finite and Infinite Expansions[END_REF], p. 234 for the second one).

Lemma 1. If σ is a permutation of n elements, then

d trp (σ, Id n ) = n -c(σ),
where c(σ) denotes the number of cycles in the disjoint cycle decomposition of σ, counting also the singletons.

Lemma 2. The number of permutations of n elements which have k disjoint cycles is given by the signless Stirling number of the first kind s(n, k) (see Definition 1(ii)).

Definition 1. We have the following equivalent definitions for the signless Stirling number of the first kind, which we denote s(n, k) (see [START_REF] Comtet | Advanced Combinatorics: The Art of Finite and Infinite Expansions[END_REF], chapter V):

(i) s(n, k), n ≥ k ≥ 0 satisfy the recurrence relation s(n + 1, k) = ns(n, k) + s(n, k -1), (1)
with boundary conditions s(0, 0) = 1 and s(n, 0) = 0 for n > 0.

(ii) For n ≥ k ≥ 1, s(n, k) equals the number of permutations of n elements which have k cycles in the disjoint cycle decomposition.

(iii) For n ≥ k ≥ 1, s(n, k) is the coefficient of the term x k in the expansion of x (n) = x(x + 1) • • • (x + n -1).

A first distance

A first idea, and the most simple one, is to compare only the order of the h orthologous genes in the region R, given by π i,h , with their order in the reference region, given by the restriction Id n | {π(i),...,π(i+h-1)} .

Note that under the null hypothesis, π i,h is a random permutation of h elements chosen among n and hence, for 0 ≤ d ≤ h -1, we have

P(d trp (π i,h , Id n | {π(i),...,π(i+h-1)} ) ≤ d) = P(d trp (σ, Id h ) ≤ d),
where σ is a random permutation of h elements. the probability that a random permutation of n elements has at least k cycles in its disjoint cycle decomposition.

Using Lemma 1 and Lemma 2, we obtain

Proposition 3. For 0 ≤ d ≤ h -1, we have P(d trp (π i,h , Id n | {π(i),...,π(i+h-1)} ) ≤ d) = p(h, h -d).
Notice that the distance considered here takes into account only the relative order of the h orthologs which are common to the reference region and to the orthologous region R, and it ignores the positions of the other orthologs.

A second distance

Because we are interested in measuring the conservation of the gene order between the reference region and the region R, another idea is to still ignore the order of the other n -h orthologs in the genome B, but to take into account their positioning in the reference region.

We consider the following "distance":

d(π, Id n ) := min{d trp (σ, Id n ) : σ ∈ S n , σ i,h = π i,h },
i.e. we take the minimum over all possible orderings in B of the other orthologs outside the region R.

Note that d(π, Id n ) depends only on π i,h and not on the whole permutation π.

Consequently, d is not a real distance from the mathematical point of view, as we can have d(π, Id n ) = 0 without necessarily having π = Id n . For d(π, Id n ) to vanish it is sufficient to have

π i,h = [i, ..., i + h -1].
In order to stress the fact that d(π, Id n ) depends only on π i,h , in what follows we will denote it d(π i,h , Id n ).

We have the following result.

Proposition 4. d(π i,h , Id n ) = h -cc(π i,h ),
where cc(π i,h ) denotes the number of cycles of π which contain only elements belonging to {i, ..., i + h -1}. We will call these cycles " closed cycles of π i,h ".

Proof. Indeed, by Lemma 1, we have

d(π i,h , Id n ) = n -max{c(σ) : σ ∈ S n , σ i,h = π i,h },
and it suffices to note that the maximum is attained by the unique permutation σ • verifying σ • i,h = π i,h and for which the elements from {1, ..., n}\{i, ..., i+h-1} are all in distinct cycles. The permutation σ • has exactly cc(π i,h ) + n -h cycles and hence

d(π i,h , Id n ) = n -c(σ • ) = h -cc(π i,h ).
In the next theorem we give the distribution of d(π i,h , Id n ) under the null hypothesis.

Theorem 5. For 0 ≤ d ≤ h -1, we have

P(d(π i,h , Id n ) ≤ d) = 1 n h h m=h-d n -m -1 n -h -1 p(m, h -d).
Proof. Let M denote the r.v. representing the number of elements from {i, ..., i+ h -1} which are included in closed cycles of π i,h . We will compute P(d(π i,h , Id n ) ≤ d) by conditioning on the values of M :

P(d(π i,h , Id n ) ≤ d) = h m=h-d P(d(π i,h , Id n ) ≤ d|M = m)P(M = m). (2)
The key observation is that the conditional distribution of cc(π i,h ) given M = m is the same as the distribution of the number of cycles in a random permutation of m elements. Hence

P(d(π i,h , Id n ) ≤ d|M = m) = p(m, h -d).
(

) 3
It remains to find the distribution of M . Recall that, under H 0 , π i,h is a random permutation of h elements chosen among n. So, for h -d ≤ m ≤ h :

P(M = m) = |{π i,h : M = m}| h! n h . (4)
Every π i,h determines a unique permutation σ • such that σ • i,h = π i,h and having all the elements from {1, ..., n} \ {i, ..., i + h -1} in distinct cycles.

Hence |{π i,h : M = m}| equals the number of permutations in S n having all the elements from {1, ..., n} \ {i, ..., i + h -1} in n -h distinct cycles and such that exactly m elements among i, i + 1, ..., i + h -1 do not belong to any of those cycles.

We then obtain

|{π i,h : M = m}| = k1,...,k n-h ≥0 k1+•••+k n-h =h-m h k 1 , ..., k n-h , m m! n-h j=1 k j ! (5) = h! n -m -1 n -h -1 ,
where k 1 , ..., k n-h count the number of elements from {i, i + 1, ..., i + h -1} which are in the cycles determined, respectively, by each of the elements in {1, ..., n} \ {i, ..., i + h -1}. The multinomial coefficient stands for the number of choices for those k 1 + • • • + k n-h elements. The product of factorials counts the number of different ways of forming the n -h cycles. For example, the cycle number j contains k j +1 elements and there are k j ! different cyclic permutations of those elements. The m! term represents the number of ways of permuting the remaining elements from {i, i + 1, ..., i + h -1}, elements which will form the closed cycles of π i,h . The last equality follows from the identity:

   (k 1 , ..., k ) : k j ≥ 0, ∀j, j=1 k j = s    = s + -1 -1 . (6)
To prove this identity, we first make the change of variables k j := k j + 1, j = 1, ..., and then we use the "bars and stars" idea to notice that

   (k 1 , ..., k ) : k j ≥ 1, ∀j, j=1 k j = s +   
represents the number of ways of separating s + stars arranged on a line, into nonempty groups. This number is exactly the binomial coefficient from the right-hand side of [START_REF] Comtet | Advanced Combinatorics: The Art of Finite and Infinite Expansions[END_REF], because one has to place -1 bars in -1 of s + -1 places available.

From ( 3) and (4) we deduce that for every m ∈ {h -d, ..., h}:

P(M = m) = n-m-1 n-h-1 n h . (7)
By substituting ( 6) and ( 2) into (1), the formula in the statement of the theorem follows.

A third distance

From the biological point of view, a disadvantage of the previous distance is the fact that it is very restrictive with respect to the position of the cluster R in the genome B.

For taking into account eventual genomic transpositions or translocations that could have changed the position of R with respect to the other orthologs in B, we think that a better idea would be to use the following "distance":

d * (π, Id n ) := min{d trp (σ, Id n ) : σ ∈ S n , σ i * ,h = π i,h }, (8)
where i * := arg max 1≤j≤n-h+1 |{π i , ..., π i+h-1 } ∩ {j, ..., j + h -1}| .

We need to make a convention for the case when we have more than one maximum point. We decide, for example, to assign i * the smallest such value. As in the case of d, d * (π, Id n ) depends only on π i,h and not on the whole permutation π, hence d * is not a real distance from the mathematical point of view. For d * (π, Id n ) to vanish it suffices to have π i,h = [j, ..., j + h -1], for some j ∈ {1, ..., n -h + 1}.

In what follows we will denote

d * (π, Id n ) by d * (π i,h , Id n ).
We denote by σ • the unique permutation which attains the minimum in ( 7), hence has all the elements from {1, ..., n} \ {i * , ..., i * + h -1} in distinct cycles.

As in Proposition 4, we have

d * (π i,h , Id n ) = h -cc(σ • i * ,h ),
where cc(σ • i * ,h ) denotes the number of "closed cycles of σ • i * ,h ", i.e. the number of those cycles of σ • which do not contain any elements from {1, ..., n} \ {i * , ..., i * + h -1}.

Let

L * := |{π i , ..., π i+h-1 } ∩ {i * , ..., i * + h -1}| . Let 0 ≤ d ≤ h -1.
For computing the probability P(d * (π i,h , Id n ) ≤ d) we will condition on the values of L * :

P(d * (π i,h , Id n ) ≤ d) = h =h-d P(d * (π i,h , Id n ) ≤ d|L * = )P(L * = ).
Note that L * must be greater than h -d, because we need to have at least h -d closed cycles of σ • i * ,h and hence at least h -d elements in common between {σ • i * , ..., σ • i * +h-1 } and {i * , ..., i * + h -1}. Next we will compute the conditional probabilities. We will prove:

Proposition 6. For 0 ≤ d ≤ h -1 and h -d ≤ ≤ h, we have P(d * (π i,h , Id n ) ≤ d|L * = ) = 1 h m=h-d h -m -1 h --1 p(m, h -d).
Proof. We denote by M * the number of elements from {i * , ..., i * + h -1} which are included in closed cycles of σ • i * ,h . By further conditioning on M * we obtain:

P(d * (π i,h , Id n ) ≤ d|L * = ) = m=h-d P(M * = m|L * = )p(m, h -d). (9)
Indeed, we have

P(d * (π i,h , Id n ) ≤ d|L * = , M * = m) = P(d * (π i,h , Id n ) ≤ d|M * = m) = p(m, h -d).
Let P = {π i , ..., π i+h-1 }. Under the null hypothesis, P is a random combination of h elements out of n.

Notice that i * and L * are completely determined by P and that M * is completely determined given a permutation of P.

We have

P(M * = m|L * = ) = P:L * = P(M * = m|P)P(P|L * = ). (10)
Fix P s.t. L * = . Then P(M * = m |P) equals the number of permutations of P s.t. M * = m divided by h!.

Let I := {i * , ..., i * + h -1} \ P and J := P \ {i * , ..., i * + h -1}. Both I and J have h -elements.

Notice that the number of permutations of P for which M * = m equals the number of permutations σ • in S n verifying the following conditions:

(i) every element from I is in a cycle with exactly one element from J ;

(ii) there are no two elements of I or two elements of J in the same cycle;

(iii) all the elements from {1, ..., n} \ (P∪I ∪ J ) are fixed points;

(iv) there are exactly m elements from P∩{i * , ..., i * +h-1} which do not belong to any of the h -cycles determined by the h -pairs formed by one element from I and one element from J ;

(v) σ • (J ) = I.

We obtain

P(M * = m|P) = 1 h! (h -)! k1,...,k h-≥0 k1+•••+k h-= -m k 1 , ..., k h-, m m! h- j=1 k j ! (11) = h-m-1 h--1 h
(using ( 5)).

Indeed, we have (h -)! ways of pairing the elements from I with the elements from J , and each of these pairings determines h -disjoint cycles. In the above formula, k 1 , ..., k h-denote the number of elements from P∩{i * , ..., i * + h -1} which belong to those h -cycles, respectively. The multinomial coefficient stands for the choice of these elements and the product of factorials counts the number of possibilities for forming the cycles. Consider, for example, the first cycle and denote by a and b its elements from I and J , respectively. This cycle contains k 1 + 2 elements, but we have the restriction σ • (b) = a and hence we have only k 1 ! ways of forming it. The m! term counts the number of ways of permuting the m elements which form the closed cycles of σ • i * ,h .

Note that the formula [START_REF] Eriksen | Estimating the expected reversal distance after a fixed number of reversals[END_REF] is the same for all P satisfying L * = and hence, from (9), we deduce

P(M * = m|L * = ) = h-m-1 h--1 h
.

Substituting into (8), the formula in the statement follows.

It remains to find the distribution of

L * = max 1≤j≤n-h+1 |P ∩ {j, ..., j + h -1}| ,
where P = {π i , ..., π i+h-1 } is a random combination of h elements among n.

Note that we can associate to each P a unique sequence x of zeros and ones, of length n, in the following manner: for every k = 1, ..., n, we let x k = 1 if and only if k ∈ P. Hence, under the null hypothesis of random gene order, x is a random sequence formed by h ones and n -h zeros.

Therefore, L * counts the maximum number of 1's within any window of length h in a random sequence formed with h 1's and (n -h) 0's. This variable appears in the literature on scan statistics and it is called discrete conditional scan statistic, as it is a scan statistic in the case of i.i.d. Bernoulli r.v.'s, conditional on the number of successes (1's).

Several exact formulas for the distribution of the conditional discrete scan statistic exist in the literature, for different particular cases for the parameters, and also various approximations and bounds (see [START_REF] Glaz | Scan Statistics[END_REF], chapter 12).

Here we will derive an exact expression for its distribution in the most general case, by adapting the results obtained by Huntington and Naus [START_REF] Huntington | A simpler expression for kth nearest neighbor coincidence probabilities[END_REF] in the conditional continuous settings. We have not seen this result in the literature, although it might have already appeared. We now give a proof of it. We follow the ideas from the proof of Huntington and Naus [START_REF] Huntington | A simpler expression for kth nearest neighbor coincidence probabilities[END_REF] and use a result of Naus [START_REF] Naus | Probabilities for a generalized birthday problem[END_REF].

Let X j , j = 1, ..., n be i.i.d. Bernoulli random variables.

Notation 3. For 1 ≤ k ≤ n -j + 1, j = 1, ..., n, we denote

X j,k := X j + • • • + X j+k-1 . Let N h := max 1≤i≤n-h+1 X i,h .
Notice that

P(L * = ) = P(N h = |X 1,n = h). (12)
Let 2 ≤ a ≤ n. We will give the result in the general settings where we condition on having a successes (1's). We have the following result.

Proposition 7. If we denote by L the integer part of n h and we let b = n -Lh, then, for 2 ≤ k ≤ a:

P(N h < k|X 1,n = a) = (b!) L+1 [(h -b)!] L n a Q k det |d (k) ij | det |g (k) ij |,
where

Q k = {(n 1 , ..., n 2L+1 ) : n i ∈ N, 2L+1 i=1 n i = a, n i + n i+1 < k, ∀i = 1, ..., 2L}
and the determinants are of size (L + 1) × (L + 1) and L × L respectively, with

d (k) ij = 1 c (k) ij !(b -c (k) ij )! , g (k) ij = 1 f (k) ij !(h -b -f (k) ij )! , where c (k) ij = - 2j-2 s=2i n s + (j -i)k, if 1 ≤ i ≤ j ≤ L + 1 2i-1 s=2j-1 n s -(i -j)k, if 1 ≤ j < i ≤ L + 1 and f (k) ij = - 2j-1 s=2i+1 n s + (j -i)k, if 1 ≤ i ≤ j ≤ L 2i s=2j n s -(i -j)k, if 1 ≤ j < i ≤ L.
Proof. We divide the n Bernoulli trials into 2L + 1 groups, the odd-numbered groups, I 2i-1 , i = 1, ..., L + 1, being of size b and the other ones, I 2i , i = 1, ..., L, of size h -b: I 2i-1 = {(i -1)h + 1, ..., (i -1)h + b}, i = 1, ..., L + 1 I 2i = {(i -1)h + b + 1, ..., ih}, i = 1, ..., L.

For i = 1, ..., 2L + 1, we will denote by n i the number of 1's in the i-th group, i.e.

n i = j∈Ii X j .
Conditional on X 1,n = a, the joint distribution of the n i 's is:

P(n 1 , ..., n 2L+1 |X 1,n = a) = L+1 i=1 b n2i-1 L i=1 h-b n2i n a , if 2L+1 i=1 n i = a. (13)
We denote

S 1 = L+1 i=1 I 2i-1 , S 2 = L i=1 I 2i , m r = max i∈Sr X i,h , r = 1, 2.
Then N h = max(m 1 , m 2 ). Notice that, given {n i }, m 1 and m 2 are independent. Consequently,

P(N h < k|{n i }) = P(m 1 < k|{n i })P(m 2 < k|{n i }). ( 14
)
The idea is to find the conditional distributions of m 1 and m 2 given {n i } and then to average over the joint distribution of {n i }.

We give here only the derivation of P(m 1 < k|{n i }), the conditional distribution of m 2 is found analogously.

For i = 1, ..., L + 1 and t = 1, ..., b we will denote

Y i (t) := X (i-1)h+1,t
the number of 1's in the first t trials of the i-th odd-numbered group

I 2i-1 . Note that Y i (b) = n 2i-1 .
The key observation is that, given {n i }, m 1 < k provided that {n i } is in the set Q k defined in the statement, and further that

X (i-1)h+t+1,h < k, for all t = 1, ..., b -1, i = 1, ..., L. But X (i-1)h+t+1,h = Y i+1 (t) + n 2i + n 2i-1 -Y i (t),
thus we can write

P(m 1 < k|{n i }) = P( b t=1 L i=1 {Y i (t) + α i > Y i+1 (t) + α i+1 }|{n i }), (15)
where

α i -α i+1 = k -n 2i-1 -n 2i > 0, i = 1, ..., L
and hence

α i := (L -i + 1)k - 2L j=2i-1 n j , i = 1, ..., L + 1. (16)
The probability in the right-hand side of ( 14) appears in a variant of the L-candidate ballot problem (see Naus [START_REF] Naus | Probabilities for a generalized birthday problem[END_REF]).

Using the relation (2.5) from Naus [START_REF] Naus | Probabilities for a generalized birthday problem[END_REF] we obtain

P(m 1 < k|{n i }) = det |h ij |, (17)
where, for i, j = 1, ..., L + 1:

h ij = n 2i-1 !(b -n 2i-1 )! (n 2i-1 + α i -α j )!(b -n 2i-1 -α i + α j )! , (18)
with the convention h ij = 0 if any of the factorial terms is negative. From ( 15), ( 16) and ( 17) we deduce that, for {n i } in Q k , we have

P(m 1 < k|{n i }) = R det |d (k) ij |, (19)
where

R = L+1 i=1 n 2i-1 !(b -n 2i-1 )! and d (k)
ij are as given in the statement. In a similar way we can show that

P(m 2 < k|{n i }) = T det |g (k) ij |, (20)
where

T = L i=1 n 2i !(h -b -n 2i )! and g (k)
ij are as in the statement. By substituting [START_REF] Sankoff | Power boosts for clusters tests[END_REF] and ( 19) into (13) and then averaging over the distribution of the n i 's, given in [START_REF] Hoberman | The incompatible desiderata of gene cluster properties[END_REF], the formula in the statement follows.

From relation [START_REF] Glaz | Scan Statistics[END_REF], Proposition 6 and Proposition 7 we deduce the following result about the distribution of d * (π i,h , Id n ). Note that the values for n and h which are typical for our application are not too large (n is of the order of 100) and hence there is no problem in computing the distribution of N h given by Proposition 7.

Conclusion

Among the three "distances" presented in this article, we think that from the biological point of view the first one and the third one are the most interesting.

Our result on the distribution of the second distance may however have an interest in itself, mathematically speaking, or one may find some better applications to other problems.

While the third distance is specifically adapted to the reference region approach, the first distance could also be used in whole genome comparisons or window sampling approaches.

Based on the first idea, of comparing only the order of the orthologs which are in common between the two clusters, one could imagine replacing the transposition distance with another distance, maybe more relevant biologically. For example, we could use the block-interchange distance of Christie [START_REF] Christie | Sorting permutations by block-interchanges[END_REF] and the results of Doignon and Labarre [START_REF] Doignon | On Hultman numbers[END_REF] on its distribution.

A natural continuation of this work would be to try to obtain analogous results in the case of signed permutations (when we take into account also genes' orientation) or in the case of multipermutations (when we can have multiple orthologs in the genome B for a given gene in the reference region, as a result of duplication events occurred after the speciation of the two species). The case of multichromosomal genomes could also be considered.

Another important question to be considered is how to cleverly combine, in a single statistical test, the proximity of the orthologs and their order.

Notation 2 .

 2 For 1 ≤ k ≤ n, we will denote by p(n, k)

Theorem 8 .h

 8 For 0 ≤ d ≤ h -1, we have P(d * (π i,h , Id n ) ≤ d) -m -1 h --1 p(m, h -d),whereP(L * = ) = P(N h < + 1|X 1,n = h) -P(N h < |X 1,n = h)and the two conditional probabilities are given by Proposition 7.

Acknowledgements

This work was partially supported by the ANR MAEV under contract ANR-06-BLAN-0113.

I would like to thank Etienne Pardoux, my thesis advisor, for many helpful discussions during this work, and Pierre Pontarotti, my second thesis advisor, for interesting biological discussions.

I also wish to thank Anthony Labarre for explaining to me his results on the number of cycles in the breakpoint graph.

I am grateful to the referee for his/her helpful suggestions, which have contributed to the improvement of the presentation of this article and have provided interesting ideas for future work.


Simona Grusea

On the distribution of the number of cycles in the breakpoint graph of a random signed permutation

Keywords: Markov processes, probabilistic algorithms, distribution functions, biology and genetics

We use the finite Markov chain embedding technique to obtain the distribution of the number of cycles in the breakpoint graph of a random uniform signed permutation. This further gives a very good approximation of the distribution of the reversal distance between two random genomes.

I. INTRODUCTION

A. The biological context

Comparing genomic organization between different species may help to decipher the evolutionary history of species and also to better understand the biology of contemporary species.

Orthologous genes are two genes, in two different species, that descend from the same gene at the ancestor of the two species, as the result of a speciation event. They tend, in general, to have similar functions. Therefore, finding a group of orthologous genes in close proximity in the genomes of two different species may represent a sign for evolutionary or functional relationships between these genes. For this to be the case, the observed orthologous gene clusters have to be significant, i.e. very improbable to have appeared by chance.

During the evolutionary time, the gene order in one genome can be affected by various genome rearrangement events, like inversions, translocations, transpositions, chromosomic fissions and fusions. Hence, in the absence of certain constraints due to functional selective pressures, the gene order is rapidly randomized. This is one reason why, in general, the null hypothesis taken in the significance tests for gene clusters is the hypothesis of random gene order.

In the "genomic comparison" literature various definitions for gene clusters exist, and also different statistical tests for detecting gene clusters which are significant from the point of view of the proximity of the orthologs (see [START_REF] Bergeron | Formal models of gene clusters[END_REF], [START_REF] Bergeron | The algorithmic of gene teams[END_REF], [START_REF] Blin | Finding nested common intervals efficiently[END_REF], [START_REF] Bocker | Computation of median gene clusters[END_REF], [START_REF] Danchin | Statistical evidence for a more than 800-million-year-old evolutionarily conserved genomic region in our genome[END_REF], [START_REF] Durand | Tests for gene clustering[END_REF], [START_REF] Hoberman | The incompatible desiderata of gene cluster properties[END_REF], [START_REF] Hoberman | The statistical analysis of spatially clustered genes under the maximum gap criterion[END_REF], [START_REF] Raghupathy | Gene cluster statistics with gene families[END_REF], [START_REF] Zhu | Generalized gene adjacencies, graph bandwidth, and clusters in Yeast evolution[END_REF]). On the other hand, one might want to take into account also the order of the orthologs in these gene clusters, considering that the clusters in which the gene order is exceptionally conserved are even more biologically significant. [START_REF] Sankoff | Power boosts for cluster tests[END_REF] propose three adjacency disruption measures for comparing the order of the orthologs which are in common between two clusters in two genomes. They investigate August 27, 2010 DRAFT in more detail the "maximum adjacency disruption" criterion, giving analytic formulas for some values of its distribution under random gene order and also simulation results. Grusea [START_REF] Grusea | Measures for the exceptionality of gene order in conserved genomic regions[END_REF] propose three measures based on the mathematical transposition distance between permutations, for assessing the exceptionality of the gene order in conserved genomic regions found by the reference region approach, and obtains analytic expressions for the distribution of these distances in the case of a uniform random permutation. In [START_REF] Corteel | Common intervals in permutations[END_REF], Corteel et al. analyze the distribution of the number of common intervals in the case of a uniform random permutation and also study some generalized common intervals, in which gaps of a certain size are permitted.

Sankoff and Haque

In the "genome rearrangements" literature, several more biologically relevant distances have been studied, which take into account one or a combination of different types of genomic events: reversals, translocations, chromosomic fissions and fusions, biological transpositions, block-interchanges -see [START_REF] Li | Algorithmic approaches for genome rearrangement: a review[END_REF] for a review. The problem with using these distances as test statistics comes from the fact that their distributions for a random permutation are very difficult to obtain and there are very few results on this subject.

Recently, Doignon and Labarre [START_REF] Doignon | On Hultman numbers[END_REF] and Bona and Flynn [START_REF] Bona | The average number of block interchanges needed to sort a permutation and a recent result of Stanley[END_REF] have found, in two different ways, the distribution of the number of (edge-disjoint) alternating cycles in the bicolored breakpoint graph of a random unsigned permutation, which can be used to deduce the exact distribution of the "block-interchange" distance of Christie [START_REF] Christie | Sorting permutations by block-interchanges[END_REF]. However, for signed permutations, corresponding to the case when gene orientation is also known, the exact distribution of the number of cycles in the breakpoint graph is still unknown.

Sankoff and Haque [START_REF] Sankoff | The distribution of genomic distance between random genomes[END_REF] use a constructive approach to obtain asymptotic estimates for the distribution of the number of cycles in the breakpoint graph of two random signed permutations.

Xu et al. [START_REF] Xu | Paths and cycles in breakpoint graph of random multichromosomal genomes[END_REF] and Xu [START_REF] Xu | The distance between randomly constructed genomes[END_REF] use a similar approach to study the case of multichromosomal genomes.

The comparison of two genomes induces a decomposition of the genomes into synteny blocks (or conserved segments), chromosomic segments containing orthologous genes in the same or reverse order in the two genomes (see [START_REF] Choi | Algorithms for the extraction of synteny blocks from comparative maps[END_REF], [START_REF] Nadeau | Lengths of chromosomal segments conserved since divergence of man and mouse[END_REF]). The genomes could then be seen as permutations (unsigned or signed) of the set of synteny blocks. Some authors extend the notion of synteny block, allowing for some micro-rearrangements inside the synteny blocks (see [START_REF] Pevzner | Genome rearrangements in mammalian evolution: lessons from human and mouse genomes[END_REF]).

In the present work we are interested in finding the exact distribution of the number of alternating cycles in the breakpoint graph of a random signed permutation. The knowledge of August 27, 2010 DRAFT this distribution provides a very good approximation for the distribution of the reversal distance for a random signed permutation. This further allows us to use the reversal distance as a test statistic for assessing the exceptionality of the gene order in conserved genomic regions or of the order of the synteny blocks between two genomes.

We use the finite Markov chain embedding technique of Fu and Koutras [START_REF] Fu | Distribution theory of runs: a Markov chain approach[END_REF] to obtain the distribution of the number of cycles in the breakpoint graph of a random signed permutation via a product of transition probability matrices of a certain finite Markov chain.

B. The breakpoint graph and the reversal distance

We let S n denote the permutation group of order n. The reversal of the interval (i, j) in the signed permutation π reverses the subsequence π(i), ..., π(j) while changing their signs, hence produces the signed permutation

π ′ = [π(1), ..., π(i -1), -π(j), -π(j -1), ..., -π(i + 1), -π(i), π(j + 1), ..., π(n)].
For π ∈ B n , we let d rev (π, Id) denote its reversal distance, i.e. the minimum number of reversals needed to transform π into the identity permutation Id = [+1, ..., +n].

Bafna and Pevzner [START_REF] Bafna | Genome rearrangements and sorting by reversals[END_REF] introduced the concept of breakpoint graph of a permutation and noticed important links between the cycle decomposition of this graph and the reversal distance. The breakpoint graph of a signed permutation is defined as follows. Given a signed permutation π in B n , we first transform it into an unsigned permutation π ′ ∈ S 2n by replacing the positive elements +i by the pair (2i -1, 2i) and the negative elements -i by the pair (2i, 2i -1). For instance, the

signed permutation π = [+3, -4, -2, +1, +5] is transformed into π ′ = [5, 6, 8, 7, 4, 3, 1, 2, 9, 10].
We then extend π ′ by adding two more elements, one at the beginning, which we will denote S (for Start) and one at the end, which we will denote T (for Terminus).

The breakpoint graph of the signed permutation π ∈ B n is the graph

G(π) = (V, B ∪ C),
having the set of vertices V = {S, 1, 2, ..., 2n, T } and the edge set partitioned into two subsets:

August 27, 2010 DRAFT More precisely, if for every element a of the permutation π we denote respectively by a L and a R the left and right elements in the pair associated to a in π ′ , then we will have a solid edge between a R and b L if a and b are consecutive in π. We have also solid edges between S and (π 1 ) L and between (π n ) R and T . We have dashed edges between the vertices 2i -1 and 2i, for every i = 1, ..., n, between S and 1 and between 2n and T .

Note that each vertex in G(π) is of degree 2, having exactly one solid edge and one dashed edge incident to it. Consequently, the breakpoint graph decomposes uniquely into disjoint alternating cycles, i.e. cycles in which the solid edges and the dashed edges alternate. For a given cycle, we call its length the number of solid edges, or equivalently, the number of dashed edges it contains.

In the example from Fig. 1, the breakpoint graph of the permutation π = [+3, -4, -2, +1, +5] decomposes into two alternating cycles, one of length 1 and one of length 5.

For a signed permutation π ∈ B n , we will denote c(π) the number of alternating cycles in the breakpoint graph G(π). The reason for introducing c(π) in [START_REF] Bafna | Genome rearrangements and sorting by reversals[END_REF] was that it is easily seen to give the following lower bound, for every π ∈ B n

d rev (π, Id) ≥ n + 1 -c(π). ( 1
)
Hannenhalli and Pevzner [START_REF] Hannenhalli | Transforming cabbage into turnip: polynomial algorithm for sorting signed permutations by reversals[END_REF] proved that for every signed permutation π ∈ B n we have the exact formula

d rev (π, Id) = n + 1 -c(π) + h(π) + f (π), (2)
where h(π) is the number of hurdles in G(π) and f (π) is 1 if π is a fortress and 0 otherwise (see [START_REF] Hannenhalli | Transforming cabbage into turnip: polynomial algorithm for sorting signed permutations by reversals[END_REF] for the definitions of hurdle and fortress).

August 27, 2010 DRAFT

The problem of computing the reversal distance for signed permutations (without giving an optimal sequence of reversals) can be solved in linear time (see Bader et al. [START_REF] Bader | A linear-time algorithm for computing inversion distance between signed permutations with an experimental study[END_REF]). The problem becomes more complicated if one wants also an optimal sequence of reversals. The most efficient sorting algorithms at present are the one by Tannier et al. [START_REF] Tannier | Advances on sorting by reversals[END_REF], than runs in O(n 3/2 √ log n), and the algorithm by Swenson et al. [START_REF] Swenson | Sorting signed permutations by inversions in O(n log n) time[END_REF] that runs in O(n log n) time for almost all permutations.

Caprara [START_REF] Caprara | On the tightness of the alternating-cycle lower bound for sorting by reversals[END_REF] showed that genomes containing hurdles are very rare. For example, less than one percent of the genomes with 8 genes contain hurdles and only one in 10 5 genomes with 100 genes. Swenson et al. [START_REF] Swenson | Hurdles hardly have to be heeded[END_REF] proved that the probability that a random signed permutation on n elements contains a hurdle is O(n -2 ) and the probability that it contains a fortress is O(n -15 ).

It was also shown that the bound (1) approximates the reversal distance extremely well for both simulated (see Kececioglu and Sankoff [START_REF] Kececioglu | Exact and approximation algorithms for sorting by reversals, with application to genome rearrangement[END_REF]) and biological data (see Bafna and Pevzner [START_REF] Bafna | Genome rearrangements and sorting by reversals[END_REF]).

Kececioglu and Sankoff [START_REF] Kececioglu | Exact and approximation algorithms for sorting by reversals, with application to genome rearrangement[END_REF] observed that the average difference between this bound and the exact distance is less than 1 for a random permutation.

One can therefore use the bound (1) as a very good approximation for the reversal distance.

Moreover, in the case of unichromosomal genomes, the bound (1) agrees exactly with the double-cut-and-join (DCJ) distance introduced by Yancopoulos et al. [START_REF] Yancopoulos | Efficient sorting of genomic permutations by translocation, inversion and block interchange[END_REF]. For more details on this distance see also [START_REF] Bergeron | A unifying view of genome rearrangements[END_REF].

The goal of the present work is to find the distribution of c(Π) for a random (uniform) signed permutation Π.

II. THE DISTRIBUTION OF c(Π)

A. The finite Markov chain embedding technique

For obtaining the distribution of c(Π) for a random signed permutation Π, we use the finite Markov chain embedding technique introduced by Fu and Koutras [START_REF] Fu | Distribution theory of runs: a Markov chain approach[END_REF].

Let X n (n a non-negative integer) be a non-negative integer random variable. As in Definition (iii) for every x = 0, 1, ..., ℓ we have

P(X n = x) = P(Y n ∈ C x ).
August 27, 2010 DRAFT

The distribution of X n can in this case be obtained via a product of transition matrices of the Markov chain (Y t ) 1≤t≤n . Indeed, if we define, for every 2 ≤ t ≤ n, the transition matrix P t := (P t (y, z)) y,z∈E by

P t (y, z) = P(Y t = z|Y t-1 = y), ∀y, z ∈ E,
then, by Theorem 2.1 in [START_REF] Fu | Distribution theory of runs: a Markov chain approach[END_REF], we have

P(X n = x) = µ 1 P 2 • • • P n ∑ i:a i ∈Cx e i , (3)
where

µ 1 = (P(Y 1 = a 1 ), ..., P(Y 1 = a m ))
is the row vector of the initial probability of the Markov chain and, for each i = 1, ..., m, e i is the column vector having 1 at the i-th coordinate and 0 elsewhere.

B. The construction of the Markov chain

Let n be a fixed positive integer. We start with Π 1 being a random uniform signed permutation with one element, hence Π 1 = [+1] with probability 1/2 and Π 1 = [-1] with probability 1/2.

For every t = 2, ..., n, we let Π t represent the random signed permutation of t elements which is obtained from Π t-1 by inserting at random the element t uniformly into one of the t possible positions, with the "+" sign with probability 1/2 and the "-" sign with probability 1/2, the sign being independent of the position.

Note that (Π t ) 1≤t≤n is an inhomogeneous Markov chain with initial distribution

P(Π 1 = [1]) = P(Π 1 = [-1]) = 1/2
and the following transition probability matrices: for every

2 ≤ t ≤ n, M t (σ, σ +,i ) = P(Π t = σ +,i |Π t-1 = σ) = 1 2t , M t (σ, σ -,i ) = P(Π t = σ -,i |Π t-1 = σ) = 1 2t , where σ +,i := [σ 1 , ..., σ i-1 , t, σ i , ..., σ t-1 ], σ -,i := [σ 1 , ..., σ i-1 , -t, σ i , ..., σ t-1 ]
August 27, 2010 DRAFT and M t (σ, σ ′ ) = 0 for every other σ ′ ∈ B t .

It is easy to see that for every t = 1, ..., n, Π t is a random signed permutation of t elements, uniformly chosen among the 2 t t! elements of B t . In our case, the random variable of interest is

X n := c(Π n )
, which we will show to be finite Markov chain embeddable. We construct a finite Markov chain (Y t ) 1≤t≤n verifying the conditions (i),(ii) and (iii), as follows.

For every t = 1, ..., n we denote by K j,t , j = 1, ..., n + 1 the random variables representing the number of cycles of length j in the breakpoint graph of the permutation Π t . We also denote by L t the length of the cycle in G(Π t ) which contains the terminal point T . For every t = 1, ..., n we obviously have K j,t = 0 for j = t + 2, ..., n + 1 and

t+1 ∑ j=1 jK j,t = t + 1, t+1 ∑ j=1 K j,t = c(Π t ).
We let

Y t := (L t , K 1,t , ..., K n+1,t ), t = 1, ..., n.
We call Y t the type of the permutation Π t . For example, the permutation π = [+3, -4, -2, +1, +5] from Fig. 1 is of type (1, 1, 0, 0, 0, 1, 0). Note that for every 1 ≤ t ≤ n, Y t takes values in the finite set

E t =    (ℓ, k 1 , ..., k t+1 , 0, ..., 0 n-t ) : ℓ ∈ {1, ..., t + 1}, t+1 ∑ j=1 jk j = t + 1, k ℓ ≥ 1    .
Let us denote -→ k := (k 1 , ..., k n+1 ). We have

P(c(Π n ) = x) = P(Y n ∈ C x ),
where, for every x = 1, 2, ..., n + 1,

C x = { (ℓ, -→ k ) : n+1 ∑ j=1 k j = x, n+1 ∑ j=1 jk j = n + 1, k ℓ ≥ 1 } .
We will show that (Y t ) 1≤t≤n is an inhomogeneous Markov chain. The initial distribution of

Y 1 is P(Y 1 = (1, 2, 0, 0, ..., 0)) = P(Y 1 = (2, 0, 1, 0, ..., 0)) = 1/2,
the case Y 1 = (1, 2, 0, 0, ..., 0) corresponding to Π 1 = [+1] and the case Y 1 = (2, 0, 1, 0, ..., 0) to

Π 1 = [-1]. For 2 ≤ t < n, write Y t-1 = (ℓ, -→ k ). Note that necessarily k ℓ ≥ 1.
August 27, 2010 DRAFT We have the following result.

Proposition 1: (Y t ) 1≤t≤n is an inhomogeneous Markov chain of initial distribution

P(Y 1 = (1, 2, 0, 0, ..., 0)) = P(Y 1 = (2, 0, 1, 0, ..., 0)) = 1/2
and the following transition probabilities.

If Y t-1 = (ℓ, -→ k ), with k ℓ ≥ 1, then the possible transitions are to Y t = (ℓ ′ , -→ k ′ ), where (i) ℓ ′ = ℓ + 1 and -→ k ′ = -→ k -e ′ ℓ + e ′ ℓ+1 , with probability ℓ/(2t); (ii) ℓ ′ = j, with 1 ≤ j ≤ ℓ, and -→ k ′ = -→ k -e ′ ℓ + e ′ j + e ′ ℓ+1-j , with probability 1/(2t); (iii) ℓ ′ = ℓ + x + 1, with 1 ≤ x ≤ t -ℓ, x ̸ = ℓ and -→ k ′ = -→ k -e ′ ℓ -e ′ x + e ′ ℓ+x+1 , with probability xk x /t; (iv) ℓ ′ = 2ℓ + 1 and -→ k ′ = -→ k -2e ′ ℓ + e ′ 2ℓ+1
, with probability ℓ(k ℓ -1)/t, where for each i, e ′ i is the row vector having 1 at the i-th coordinate and 0 elsewhere. Proof: For a permutation π of type (ℓ, -→ k ), we will show that

P(Y t = (ℓ ′ , -→ k ′ )|Π t-1 = π) depends only on ℓ ′ , -→ k ′ , ℓ, -→ k . This easily implies that (Y t ) 1≤t≤n is a Markov chain.
Suppose now that Π t-1 = π, with π being of type (ℓ, -→ k ). In Fig. 2 we have the disjoint cycle decomposition of the breakpoint graph of the permutation

Π 5 = π = [+4, -2, -1, +5, +3].
In this case we have ℓ = 5 and -→ k = (1, 0, 0, 0, 1, 0).

We will investigate the changes produced in the breakpoint graph when inserting the new element ±t, at random, into one of the t possible positions of the permutation π, with the "+" sign with probability 1/2 and the "-" sign with probability 1/2.

The modifications concerning the dashed edges are simple. Disregarding the sign of ±t, the dashed edge between 2(t -1) and T is deleted and replaced by a dashed edge between 2(t -1)

and 2t -1, and then another dashed edge is added between 2t and T (see for example Fig. 3).

August 27, 2010 DRAFT Concerning the solid edges: we choose at random a solid edge among the t solid edges in the breakpoint graph of π, we delete it and then add two other solid edges to connect the two extremities of the deleted edge to 2t -1 and 2t respectively, in one of the two possible ways.

The choice of the solid edge to be deleted corresponds to the choice of the position in the permutation π where ±t is inserted. The way in which we connect the two extremities of the deleted edge to 2t -1 and 2t respectively, corresponds to the sign of the element t.

More precisely, if we choose to insert the element ±t in the position i, where 2 ≤ i ≤ t -1, then we will delete the solid edge between (π(i -1)) R and (π(i)) L . If we insert +t, then we will add two solid edges between (π(i -1)) R and 2t -1 and between 2t and (π(i)) L . If we insert -t, then we will add two solid edges between (π(i -1)) R and 2t and between 2t -1 and

(π(i)) L .
If we choose to insert the element ±t in the position 1, i.e. at the beginning of the permutation π, then we will delete the solid edge between S and (π(1)) L . If we insert +t we add two solid edges between S and 2t -1 and between 2t and (π(1)) L , and if we insert -t we add two solid edges between S and 2t, and between 2t -1 and (π(1)) L .

If we choose to insert ±t in the position t, i.e. at the end of the permutation π, then we will delete the solid edge between (π(t)) R and T . If we insert +t we add two solid edges between (π(t -1)) R and 2t -1 and between 2t and T , and if we insert -t we add two solid edges between (π(t -1)) R and 2t and between 2t -1 and T .

The cases (i) and (ii) in the statement correspond to the deletion of a solid edge from the cycle containing T , and the cases (iii) and (iv) correspond to the deletion of a solid edge belonging August 27, 2010 DRAFT to a cycle not containing T .

If we delete a solid edge belonging to the cycle of size ℓ which contains T , then we have two possible situations, depending on the deleted solid edge and on the permutation π. One situation is that, when we insert +t, the cycle containing T grows to the length ℓ + 1 (see Fig. 3), and when we insert -t it splits into two smaller cycles, of sizes which sum to ℓ + 1 (see Fig. 4). The other possible situation is the converse, i.e. when we insert -t the cycle containing T becomes of size ℓ + 1 (see Fig. 5), and when we insert +t it splits into two smaller cycles, of sizes which sum to ℓ + 1 (see Fig. 6).

The event that the cycle containing T becomes of size ℓ + 1 occurs with probability ℓ/(2t), because we have ℓ possible solid edges to choose in the cycle containing T . In the case when the cycle containing T splits into two cycles, the new size j of the cycle which will contain T is chosen at random, uniformly between 1 and ℓ. The size of the second cycle is then simply ℓ + 1 -j. Each size j corresponds to a specific choice for the deleted solid edge, hence the event that the cycle containing T splits into two cycles and the size of the new cycle which will contain T becomes j, occurs with probability 1/(2t).

If we delete a solid edge from a cycle not containing T , then, disregarding the sign of t, this cycle will merge with the one containing T . If the cycle from which we have deleted a solid edge was of size x, then in the breakpoint graph of Π t the cycle containing T will be of size

ℓ + x + 1.
In (iii), x represents the length of the cycle not containing T from which we choose a solid edge to be deleted. If x ̸ = ℓ, the probability that this event occurs equals xk x /t, because we August 27, 2010 DRAFT have k x cycles of length x that we can choose, and each of them contains x solid edges.

The case (iv) corresponds to the case x = ℓ, when we have only k ℓ -1 possibilities to choose a cycle of size ℓ not containing T .

Proposition 1 describes the entries of the transition probability matrix P t of the inhomogeneous Markov chain (Y t ) t . As described in (3), we can therefore obtain the distribution of c(Π n ) via the product of n transition matrices of this Markov chain.

C. Numerical results

We have implemented an iterative procedure which, for a given n, computes numerically the distribution of Y n and then the distribution of c(Π n ). At each step t = 1, ..., n -1, we compute the distribution of Y t+1 from the distribution of Y t , using the transition probabilities described , as m → ∞.

In Table I and Table II

III. CONCLUDING REMARKS

In this article we have obtained the distribution of the number of alternating cycles in the breakpoint graph of a random signed permutation, in the form of a product of transition probability matrices of a certain finite Markov chain, using the finite Markov chain embedding technique.

A drawback of our method is the fact that our Markov chain is inhomogeneous and of large dimension, which induces a high computational complexity.

A plan for a future work is to find a closed analytic formula for the exact distribution of the number of cycles in the breakpoint graph of a random signed permutation.

August 27, 2010 DRAFT

Fig. 1 .

 1 Fig. 1. The breakpoint graph of the permutation π = [+3, -4, -2, +1, +5].

Fig. 2 .

 2 Fig. 2. The disjoint cycle decomposition of G(π), for π = [+4, -2, -1, +5, +3].

Fig. 3 .

 3 Fig. 3. For Π6 = [+4, -2, -1, +6, +5, +3] the cycle containing T grows to the length ℓ ′ = ℓ + 1 = 6. The element +6 is inserted into Π5 = [+4, -2, -1, +5, +3] in position i = 4, corresponding to the deletion of the solid edge 1-9.

Fig. 4 .

 4 Fig. 4. For Π6 = [+4, -2, -1, -6, +5, +3] the cycle containing T splits into two and ℓ ′ = 3. The element -6 is inserted into Π5 = [+4, -2, -1, +5, +3] in position i = 4, corresponding to the deletion of the solid edge 1-9.

Fig. 5 .

 5 Fig. 5. For Π6 = [-6, +4, -2, -1, +5, +3] the cycle containing T grows to the length ℓ ′ = ℓ + 1 = 6. The element -6 is inserted into Π5 = [+4, -2, -1, +5, +3] in position i = 1, corresponding to the deletion of the solid edge S-7.

Fig. 6 .

 6 Fig. 6. For Π6 = [+6, +4, -2, -1, +5, +3] the cycle containing T splits into two and ℓ ′ = 2. The element +6 is inserted into Π5 = [+4, -2, -1, +5, +3] in position i = 1, corresponding to the deletion of the solid edge S-7.

in Proposition 1 .

 1 The complexity of our algorithm is O(n 2 × p(n + 1)), where p is the partition function, i.e. for every positive integer m, p(m) is the number of integer partitions of m. AnAugust 27, 2010 DRAFT

  we give the distribution of c(Π) for a random uniform signed permutation Π of 20 and 30 elements, respectively. In the two tables p k denotes the probability that c(Π) takes the value k. For the values of k not appearing in the tables the corresponding probabilities are negligible. On a Pentium 4 processor, 3.1 Mhz, 512 Mb, the computation time was 13s for n = 20, 300s for n = 30, 4 × 10 3 s for n = 40 and 4 × 10 4 s for n = 50.

TABLE I THE

 I DISTRIBUTION OF c(Π) FOR A RANDOM SIGNED PERMUTATION Π ∈ B20.

		k	1	2	3	4	5	6	7	8	9
		p k	0.19213 0.34805 0.27688 0.13047 0.04126 0.00938 0.00160 0.00021 0.00002
							TABLE II
			THE DISTRIBUTION OF c(Π) FOR A RANDOM SIGNED PERMUTATION Π ∈ B30.
	k	1	2	3		4	5	6	7	8	9	10
	p k	0.15849 0.31791 0.28690 0.15704 0.05909 0.01639 0.0035 0.00059 0.00008 0.00001
	asymptotic expression for p(m) is given by
				p(m) ∼	exp(π 4m √ (2m)/3) √ 3

ACKNOWLEDGEMENTS

I would like to thank Etienne Pardoux, my thesis advisor, for all his support during this work, and Pierre Pontarotti, my second thesis advisor, for helpful biological discussions. I also wish to thank Anthony Labarre for explaining me his results on the number of cycles in the breakpoint graph of a random unsigned permutation.

This work was partially supported by the ANR MAEV under contract ANR-06-BLAN-0113.


Luciana Benotti
email: luciana.benotti@gmail.com

Alexandre Denis
email: alexandre.denis@loria.fr

CL system: Giving instructions by corpus based selection

The CL system uses an algorithm that, given a task-based corpus situated in a virtual world, which contains human instructor's speech acts and the user's responses as physical actions, generates a virtual instructor that helps a user achieve a given task in the virtual world. In this report, we explain how this algorithm can be used for generating a virtual instructor for a game-like, task-oriented virtual world such as GIVE's.

Introduction

There are two main approaches toward automatically producing dialogue utterances. The most used one is the generation approach, in which the output is dynamically assembled using some composition procedure, e.g. grammar rules. The other is the selection approach, in which the task is to pick the appropriate output from a corpus of possible outputs. The selection approach has only been used in conversational systems that are not task-oriented such as negotiating agents (Gandhe and Traum, 2007a), question answering characters [START_REF] Kenny | Virtual patients for clinical therapist skills training[END_REF], and virtual patients [START_REF] Leuski | Building effective question answering characters[END_REF]. In this paper, we describe the algorithm used by the system CL for giving instructions by selecting utterances from automatically annotated human-human corpora. Our algorithm is the first one proposed for doing generation by selection for task-oriented systems, for details see [START_REF] Benotti | Giving instructions in virtual environments by corpus based selection[END_REF].

The advantages of corpus based generation are many. To start with, it affords the use of complex and human-like sentences without detailed analysis. Moreover, the system may easily use recorded audio clips rather than speech synthesis and recorded video for animating virtual humans. Finally, no rule writing by a dialogue expert or manual annotations is needed. Nowadays, most conversational systems require extensive human annotation efforts in order to be fit for their task [START_REF] Rieser | Learning human multimodal dialogue strategies[END_REF]. Semantic annotation and rule authoring have long been known as bottlenecks for developing conversational systems for new domains.

The disadvantage of corpus based generation is that the resulting dialogue may not be fully coherent. [START_REF] Bayan | Using dialogue corpora to retrain a chatbot system[END_REF][START_REF] Bayan | Using corpora in machine-learning chatbot systems[END_REF] present a method for learning pattern matching rules from corpora in order to obtain the dialogue manager for a chatbot. Gandhe and Traum (2007b) investigate several dialogue models for negotiating virtual agents that are trained on an unannotated human-human corpus. Both approaches report that the dialogues obtained by these methods are still to be improved because the lack of dialogue history management results in incoherences. Since in task-based systems, the dialogue history is restricted by the structure of the task, the absence of dialogue history management is alleviated by tracking the current state of the task.

In the next section we introduce the corpora used by the CL system. Section 2 presents the two phases of our algorithm, namely automatic annotation and generation through selection. In Section 3 we present a fragment of an interaction with a virtual instructor generated using the GIVE-2 Corpus [START_REF] Gargett | The GIVE-2 corpus of giving instructions in virtual environments[END_REF] and our algorithm. Finally, Section 5 discusses its advantages and drawbacks with respect to hand-coded systems.

The algorithms

Our algorithm consists of two phases: an annotation phase and a selection phase. The annotation phase is performed only once and consists of automatically associating the DG instruction to the DF reaction. The selection phase is performed every time the virtual instructor generates an instruction and consists of picking out from the annotated corpus the most appropriate instruction at a given point.

The automatic annotation

The basic idea of the annotation is straightforward: associate each utterance with its corresponding reaction. We assume that a reaction captures the semantics of its associated instruction. Defining reaction involves two subtle issues, namely boundary determination and discretization. We discuss these issues in turn and then a formal definition of reaction.

We define the boundaries of a reaction as follows. A reaction R k to an instruction U k begins right after the instruction U k is uttered and ends right before the next instruction U k+1 is uttered. In the following example, instruction 1 corresponds to the reaction 2, 3, 4 , instruction 5 corresponds to 6 , and instruction 7 to 8 . As the example shows, our definition of boundaries is not always semantically correct. For instance, it can be argued that it includes too much because 4 is not strictly part of the semantics of 1. Furthermore, misinterpreted instructions (as 5) and corrections (e.g., 7) result in clearly inappropriate instruction-reaction associations. Since we want to avoid any manual annotation, we decided to use this naive definition of boundaries anyway.

The second issue that we address here is discretization of the reaction. It is well known that there is not a unique way to discretize an action into subactions. For example, we could decompose action 2 into 'enter the room' or into 'get close to the door and pass the door'. Our algorithm is not dependent on a particular discretization. However, the same discretization mechanism used for annotation has to be used during selection, for the dialogue manager to work properly. For selection (i.e., in order to decide what to say next) any virtual instructor needs to have a planner and a planning problem: i.e., a specification of how the virtual world works (i.e., the actions), a way to represent the states of the virtual world (i.e., the state representation) and a way to represent the objective of the task (i.e., the goal). Therefore, we decided to use them in order to discretize the reaction.

For the virtual instructor we present in Section 3 we used the planner LazyFF and the planning problem provided with the GIVE Framework. The planner LazyFF is a reimplementation (in Java) of the classical artificial intelligence planner FF [START_REF] Hoffmann | The FF planning system: Fast plan generation through heuristic search[END_REF]. The GIVE framework [START_REF] Gargett | The GIVE-2 corpus of giving instructions in virtual environments[END_REF] provides a standard PDDL [START_REF] Hsu | New features in SGPlan for handling soft constraints and goal preferences in PDDL3.0[END_REF] planning problem which formalizes how the GIVE virtual worlds work. Now we are ready to define reaction formally. Let S k be the state of the virtual world when uttering instruction U k , S k+1 be the state of the world when uttering the next utterance U k+1 and Acts be the representation of the virtual world actions. The reaction to U k is defined as the sequence of actions returned by the planner with S k as the initial state, S k+1 as the goal state and Acts as the actions.

Given this reaction definition, the annotation of the corpus then consists of automatically associating each utterance to its (discretized) reaction. The simple algorithm that implements this annotation is shown in Figure 1.

Selecting what to say next

In this section we describe how the selection phase is performed every time the virtual instructor generates an instruction.

The instruction selection algorithm, displayed in Figure 2, consists in finding in the corpus the set of candidate utterances C for the current task plan P (P is the sequence of actions that needs to be executed in the current state of the virtual world in order to complete the task). We define C = {U ∈ Corpus | P starts with In other words, an utterance U belongs to C if the first actions of the current plan P exactly match the reaction associated to the utterance U . All the utterances that pass this test are considered paraphrases and hence suitable in the current context. While the plan P doesn't change, because the DF is staying still, the virtual instructor offers alternative paraphrases of the intended instruction. Each paraphrase is selected by picking an utterance from C and verbalizing it, at fixed time intervals (every 3 seconds). The order in which utterances are selected depends on the length of the utterance reaction (in terms of number of actions), starting from the longest ones. Hence, in general, instructions such as "go back again to the room with the lamp" are uttered before instructions such as "go straight", because the reaction of the former utterance is longer than the reaction of the later.

It is important to notice that the discretization used for annotation and selection directly impacts the behavior of the virtual instructor. It is crucial then to find an appropriate granularity of the dis-cretization. If the granularity is too coarse, many instructions in the corpus will have an empty reaction. For instance, in the absence of the representation of the user orientation in the planning domain, instructions like "turn left" and "turn right" will have empty reactions making them indistinguishable during selection. However, if the granularity is too fine the user may get into situations that do not occur in the corpus, causing the selection algorithm to return an empty set of candidate utterances. It is the responsibility of the virtual instructor developer to find a granularity sufficient to capture the diversity of the instructions he wants to distinguish during selection.

A sample interaction

In this section we illustrate the interaction between the CL system and a DF. On Figures 4 to 7 we show an excerpt of an interaction between the system and a DF. The figures show a 2D map from top view and the 3D in-game view. In Figure 4, the user, represented by a blue character, has just entered the upper left room. He has to push the button close to the chair. The first candidate utterance selected is "red closest to the chair in front of you". Notice that the referring expression uniquely identifies the target object using the spatial proximity of the target to the chair. This referring expression is generated without any reasoning on the target distractors, just by considering the current state of the task plan and the user position. The generation of the ellipsis of the button or the chair is a direct consequence of the utterances normally said in the corpus at this stage of the task plan (that is, when the user is about to manipulate this object). From the point of view of referring expression algorithms, the referring expression may not be optimal because it is over-specified (a pronoun would be preferred as in "click it"), Furthermore, the instruction contains a spelling error ('closet' instead of 'closest'). In spite of this non optimality, the instruction led our user to execute the intended reaction, namely pushing the button.

Right after the user clicks on the button (Figure 6), the system selects an utterance corresponding to the new task plan. The player position stayed the same so the only change in the plan is that the button no longer needs to be pushed. In this task state, DGs usually give acknowledgements and this is then what our selection algorithm selects: "good".

After receiving the acknowledgement, the user turns around and walks forward, and the next action in the plan is to leave the room (Figure 7). The system selects the utterance "go back to the room with the lamp" which refers to the previous interaction. Again, the system keeps no representation of the past actions of the user, but such utterances are the ones that are found at this stage of the task plan.

We show in Figure 3 all candidate utterances selected when exiting the room in Figure 7. That is, for our system purposes, all the utterances in the figure are paraphrases of the one that is actually uttered in Figure 7. As we explained in Section 2.2, the utterance with the longest reaction is selected first ("go back to the room with the lamp"), the second utterance with the longest reaction is selected second ("ok go back again to the room with the lamp"), and so on.

Portability to other virtual environments

The other systems that participated in the challenge do not need a corpus in a particular GIVE virtual world in order to generate instructions for any GIVE virtual world, while our system cannot do without such corpus. As a result these systems are more complex (e.g. they include domain independent algorithms for generation of referring expressions) and take a longer time to develop.

Our algorithm is independent of any particular virtual world. It can be ported to any other instruction giving task (where the DF has to perform a physical task) with the same effort than required to port it to a new GIVE world. This is not true for the other systems that participated in the GIVE-2.5 Challenge. The inputs of our algorithm are an offthe-shelf planner, a formal planning problem representation of the task and a human-human corpus collected on the very same task the system aims to instruct. It is important to notice that any virtual instructor, in order to give instructions that are both causally appropriate at the point of the task and relevant for the goal cannot do without such planning problem representation. Furthermore, it is quite a normal practice nowadays to collect a human-human corpus on the target task domain. It is reasonable, then, to assume that all the inputs of our algorithm are already available when developing the virtual instructor.

Another advantage of our approach is that virtual instructor can be generated by developers without any knowledge of generation of natural language techniques. Furthermore, the actual implementation of our algorithms is extremely simple as shown in Figures 1 and2. This makes our approach promising for application areas such as games and simulation training.

Conclusions

In this paper we presented the system CL, which uses a novel algorithm for doing generation by corpus based selection from human-human corpora without manual annotation.

The algorithms we presented solely rely on the plan to define what constitutes the context of uttering. It may be interesting though to make use of other kinds of features. For instance, in order to integrate spatial orientation and differentiate "turn left" and "turn right", the orientation can be either added to the planning domain or treated as a context feature. While it may be possible to add orientation in the planning domain of GIVE, it is not straightforward to include the diversity of possible features in the same formalization, like modeling the global discourse history or corrections.

In sum, this paper presents the first existing algorithm for fully-automatically prototyping taskoriented virtual agents from corpora. The generated agents are able to effectively and naturally help a user complete a task in a virtual world by giving her/him instructions.

  DG(1): hit the red you see in the far room DF(2): [enters the far room] DF(3): [pushes the red button] DF(4): [turns right] DG(5): hit far side green DF(6): [moves next to the wrong green] DG(7): no DF(8): [moves to the right green and pushes it]

1:

  Acts ← world possible actions 2: for all utterance U k in the corpus do 3: S k ← world state at U k 4: S k+1 ← world state at U k+1 5: U k .Reaction ← plan(S k , S k+1 , Acts) 6: end for

Figure 1 :

 1 Figure 1: Annotation algorithm

Figure 2 :

 2 Figure 2: Selection algorithm

Figure 4 :

 4 Figure 4: "red closest to the chair in front of you" After receiving the instruction the user gets closer to the button as shown in Figure 5. As a result of the

Figure 5 :

 5 Figure 5: "the closet one"

Figure 7 :

 7 Figure 7: "go back to the room with the lamp"