Steven Lepoutre

Alexandre Gauguet

Gérard Trénec

Matthias Büchner

J Vigué

Supplemental Material: "He-McKellar-Wilkens topological phase in atom interferometry"

Keywords: numbers: 03.65.Vf, 03.75.Dg, 39.20.+q FIG

I. AC-HMW CONNECTION

The Aharonov-Casher [1] phase and the He-McKellar [2] and Wilkens [3] phase are connected by electricmagnetic duality, as illustrated in figure 1. It is impossible to detect the He-McKellar-Wilkens (HMW) phase with such a scheme because magnetic monopoles are hypothetical particles [4]. The experiments proposed by Wilkens [3], by Wei et al. [5] and by Sato and Packard [6] do not involve magnetic monopoles but the propagation of polarizable atoms (or molecules) in magnetic fields, the electric dipole being induced by an electric field perpendicular to the magnetic field. The question whether such an experiment is a test of the He-McKellar-Wilkens idea is worth discussing. In our opinion, the important point is that an electric dipole d propagates in a magnetic field B perpendicular to d and to the atom velocity v. Magnetic monopoles would produce a diverging magnetic field, leading to a non-zero HMW phase ϕ HMW = (d × B) • vdt/ but the exact nature of the magnetic field source is irrelevant and any field configuration which yields a non vanishing HMW phase is a test of the HMW effect. The idea of Wilkens [3] is to use the same dipole direction on the two interferometer arms but different magnetic fields thanks to ferromagnetic material. Wei et al. [5] go one step further and propose to have states with opposite induced dipoles in a common homogeneous magnetic field. We may note that similar aspects were discussed for the Aharonov-Casher phase [7,8].

II. THE EXPERIMENTAL SETUP

In this section, we give further details about the interaction region used for the observation of the HMW phase: this interaction region is schematically represented in figure 1 of our letter.

The electric fields E are produced by two plane capacitors sharing a thin "septum" electrode [10]; the electrodes are in vertical planes so that the electric field is horizontal, along the x-axis. The septum is a 20 µm-thick aluminium foil, with a surface roughness better than 2 µm while the other electrodes are 5 mm-thick polished glass plates with an aluminium coating. Along the zdirection, two 5 mm-long guard electrodes surround a 48 mm-long high-voltage electrode, with 1 mm-wide gaps between high-voltage and guard electrodes. The capacitors are assembled by gluing together the electrodes and 1.1 mm-thick glass spacers. A specific procedure was used to glue the septum in order to keep it stretched even when the temperature rises [11]. The electric fields produced by each capacitor was investigated using polarizability phase shift measurements and by calculations [12]. Except near the guard electrodes, the electric field is homogeneous, with a modulus E(kV/m)≈ 0.9V , where V is the applied voltage in Volts. V can be positive or negative, in order to test the effect of field reversals.

When measuring the HMW phase shift, we equalize the polarizability phase shifts induced on the two interferometer arms by tuning the ratio of the voltages applied on the two capacitors with potentiometers, using a common power supply. In this way, the residual Stark phase shift is small, near 0.1 rad.

B. Magnetic field

The magnetic field B is designed to be vertical, along the y-axis, and homogeneous. It is produced by two rectangular coils in the (x,z) plane. These coils, which surround the capacitors, are located ∼ 5 mm above and below the capacitor mid-plane. Each coil is made of 2 layers of 7 turns of 1.5 mm-diameter enameled copper wire coiled on a common water cooled brass support. The support dimensions are 83 × 18 mm 2 . The two coils are connected in series. Thermal conduction is ensured by a high thermal conductivity glue (Stycast 2850 FT) and the coil temperature rises by about 10 K for a 20W Joule power, corresponding to a current I = 26 A, if applied 50% of the time as in most experiments. We have measured the magnetic field with a 3D Hall probe and found it in agreement with its calculated dependence. Over the region where the electric field is applied, the magnetic field is quasi-vertical and its value varies by less than 4%. At the coil center of symmetry, the field is given by B/I ≈ 5.6 × 10 -4 T/A, so that B max = 14.6 mT. The current I can also be positive or negative, in order to test the effect of field reversals.

The field homogeneity is not perfect and the small magnetic field gradient, which exists in the x-direction, induces Zeeman phase shifts. From the measured shifts, we deduce that the magnetic field difference between the two interferometer arms is about δB/B ∼ 10 -4 : this small difference is expected if the distance along the xaxis between the septum and the coil symmetry plane is about 200 µm, well within the defects of our construction. In order to cancel the Zeeman phase shifts, we have introduced a compensation coil which produces a magnetic field gradient between the two interferometer arms at another place so that the total magnetic phase shift vanishes. This compensation coil, located at mid-distance between the first and second laser standing waves, is made of 9 turns of 1.5 mm-diameter copper wire on a 30 mm-diameter support. The coil axis is horizontal, along the x-axis and the coil center is at about 10 mm from the interferometer arms. It creates a magnetic field gradient in the x-direction. This coil is cooled by thermal conduction through its support and temperature rise limits the compensation current I c to 5 A, corresponding to a maximum field seen by the atoms near 2 × 10 -3 T.

The detection of the HMW effect requires a measurement procedure which is not sensitive to the phase drift of the interferometer. This procedure is briefly described in our letter: it consists in alternating several configurations of the electric field E and the magnetic field B during a fringe sweep. We carefully checked that it does not induce any unwanted bias. In a first step, we have characterized our setup by recording fringes with only one field applied, sweeping a large range of V , I and I c values. Then, to measure the HMW phase shift, we recorded data for a set of (V, I) values represented in figure 2. Our first measurements were done with a 4-field procedure: during a fringe scan, the following values of (V, I) alternate ((0, 0), (V, 0), (V, I), (0, I)) as in figure 2 of our letter. We then modified this procedure to use a 6-field procedure ((0, 0), (+|V |, 0), (+|V |, I), (0, I), (-|V |, I), (-|V |, 0)) and most of the data was recorded in this way. The advantage of the 6-field procedure is to give more direct measurements of the effects of electric field reversals. To avoid high transient voltages associated to reversal of the coil currents, we have studied the effect of magnetic field reversal by recording successively data with same V value and opposite I values. We deduce from these measurements the value of ϕ EB (V, I) given by equation (4) of our letter but also ϕ E (V ) and ϕ B (I). We also get very accurate values of the relative visibility V r (V, I) = V(V, I)/V(0, 0) as well as V r (V ) = V(V )/V(0) and V r (I) = V(I)/V(0). All this information is used in the analysis of systematic effects due to small defects of our setup.

As ϕ HMW ∝ V I and as its expected value is small, we have collected data with moderate to large values of the V I product and this is why we have no data with |V I| < 4000 V.A. This choice was not optimum because systematic effects increase rapidly with the magnetic field and the data with |I| > 12 A has been discarded from the final analysis. Nevertheless, the data collected with large values of |I| has given very useful information on systematic effects.

IV. THEORY OF THE SIGNAL: PREDICTION OF SYSTEMATIC EFFECTS ON THE FRINGE PHASE AND VISIBILITY

Here we discuss the various phase shifts induced by the electric and magnetic field on the atom interferometer fringes and, for each phase shift, the origin of its dispersion. We then explain how these dispersions induce stray phase shifts and the way we evaluate these effects.

FIG. 2: Data set collected for the measurement of the HMW phase in the (I, V ) plane: a triangle for a 4-field procedure or a bullet for a 6-field procedure.

A. Origins of the various phase shifts

Any perturbation term U added to the atom Hamiltonian modifies the propagation phase of the atom. The fringe phase shift in an atom interferometer is given by:

ϕ dyn = - U (r) dt = - U ds v ( 1
)
where r is the atom position and the integral follows the unperturbed interferometer arms. In the second form, ds is the curvilinear element of the interferometer arms and v the atom velocity. This first order expression is valid if U is small enough with respect to the atom kinetic energy [13]. In our experiment, U = U Z (F, m F ) + U S , respectively the Zeeman and the Stark term. The associated dynamic phase shifts are the Stark (or polarizability) phase shift ϕ S and the Zeeman phase shift ϕ Z (F, m F ). Equation ( 1) is valid as long as the applied fields are small enough, which is the case in our experiment. We must also add the topological phase shifts ϕ AC and ϕ HMW respectively due to the Aharonov-Casher and He-McKellar-Wilkens effects to get the total fringe phase ϕ:

ϕ = ϕ d + ϕ S + ϕ Z (F, m F ) (2) +ϕ AC (F, m F ) + ϕ HMW
where ϕ d is the diffraction phase, which is used to scan the fringes.

The Stark term is U S = -2πε 0 αE 2 . With our maximum field E ≈ 770 kV/m (V ≈ 850 V), the Stark phase shift induced on each arm exceeds 300 rad. Thanks to a fine tuning of the ratio of the voltages applied to the two capacitors, the resulting Stark phase shift is small ϕ S ∼ 0.1 rad.

With the rather large magnetic field applied in the HMW interaction region, hyperfine uncoupling occurs so that we must include the hyperfine Hamiltonian and the Zeeman Hamiltonian in the perturbation term U Z (F, m F ). As in previous studies [14][15][16], we assume an adiabatic behavior: the magnetic field B direction is slowly varying in space so that the projection m F of the F angular momentum on an axis parallel to the local magnetic field B is constant. If we assume that the interferometer arms are very close to the z-axis and if δx (z) is the distance between the two arms, the Zeeman phase shift is given by:

ϕ Z (F, m F ) = - ∂U Z (F, m F ) ∂B ∂B ∂x δx (z) dz v (3)
Because of hyperfine uncoupling, the Zeeman energy shift and the Zeeman phase shift are complicated functions of F, m F and of the HMW coil current I. Although the relative field difference between the two interferometer arms is small, δB/B ∼ 10 -4 , the resulting phase shift is large, up to ϕ Z (F = 2, m F = ±2) ≈ ±11 rad for B = 14 mT. Because the Zeeman phase shift strongly depends of F and m F and because the atoms are distributed over the 8 ground state sub-levels, the fringe visibility becomes rapidly very small when the magnetic field increases [14][15][16]: for instance, the visibility vanishes when I ≈ 6 A. We compensate this Zeeman phase shift with the additional gradient produced by the compensation coil and we have found that compensation is obtained with I c ≈ |I| /3. However, the compensation coil produces a low field which can compensate only the linear part of the Zeeman phase shift. As shown in figure 3, this compensation is very efficient, with the relative fringe visibility being larger than 70% up to a current |I| = 12 A. When the HMW coil current is large, |I| > 15A, the compensator current was fixed I c = 5 A. The relative fringe visibility vanishes for |I| ≈ 18 A and presents a revival with a phase shift close to π for I = 23 A and a relative visibility near 70% (this revival is explained in [11]).

The HMW phase shift is given by equation (2) of our letter and its maximum value is ϕ HMW ≈ 27 mrad.

The AC phase shift [1] is given by:

φ AC (F, m F ) = - [E (r) × µ (F, m F )] • dr c 2 (4)
where µ (F, m F ) is the magnetic moment of the F, m F sub-level. The maximum value of the AC phase shift is |ϕ AC (F = 2, m F = ±2)| ≈ 70 mrad. In the interpretation of the observed data, we will use the theoretical value of the AC phase shift.

In equation 3, we have not included the Berry's phase [START_REF] Berry | Proc. R. Soc. Lond. A[END_REF] due to the fact that the direction of the magnetic field is not constant over the interferometer arms. The measured Berry's phase is the difference of the Berry's phases over the two interferometer arms and this difference is expected to be very small because the magnetic field homogeneity is very good: from the Zeeman phase shifts, we estimate that the relative difference of magnetic field δB/B is δB/B ≈ 10 -4 for the HMW coil and δB/B ≈ 10 -3 for the compensating coil. Moreover, the measured Berry's phase should not be sensitive to the presence of the electric field, because the Stark term is the same for all the hyperfine sub-levels with an excellent accuracy [12] and, as a consequence, the measured Berry's phase should have the same value in ϕ E+B (V, I) and in ϕ B (I) so that it should be fully canceled in ϕ EB (V, I).

A more complex Berry's phase involving the electric and magnetic fields was detected in the measurement of the electron dipole moment [START_REF] Abdullah | [END_REF]. This Berry's phase is proportional to the solid angle of the spatial circuit of the magnetic field directio, where the magnetic field is the one seen by the atom in its rest frame (this means that it includes the motional magnetic field due to the electric field). This Berry's phase is an edge effect, which is sensitive to the difference of transverse components of the magnetic fields at the two ends of the electric field region. As it involves the motional magnetic field due to the electric field, this effect is related to the AC phase (but the AC phase, which is proportional to the electric field and to the length of the path in the field, is not an edge effect). We have put figures in the formula of reference [START_REF] Abdullah | [END_REF] and the effect is completely negligible in our experiment: this can be explained by the fact that we use larger magnetic fields and lower electric fields.

B. Dispersion of the phase shifts

A dispersion of the fringe phase reduces the fringe visibility and, as below, it may also induce systematic errors on the phase measurements.

The Stark and Zeeman phase shifts are the only phases which depend on the atom velocity: equation (1) proves that ϕ S ∝ 1/v and equation (3)

proves that ϕ Z (F, m F ) ∝ 1/v 2 because δx (z) is proportional to 1/v.
The atomic beam velocity distribution is given by [12]:

P (v) = S u √ π exp -(v -u)S /u 2 ( 5
)
where u is the mean velocity and S is the parallel speed ratio. During the HMW measurements, the associated phase dispersion is not very large because the velocity distribution is narrow (with S ≈ 7 corresponding to a half-width at half maximum close to 10% of the mean velocity) and because the phase shifts are small: the largest phase shift is the Zeeman phase shift close to π near the fringe visibility revival with I ≈ 23 A. When the phase dispersion is small, it is possible to use analytic results to calculate the effects of the phase dispersion on the fringe phase and visibility: this calculation is described for the Stark phase shift in ref. [12] and for the Zeeman phase shift in [19] and it can be easily generalized to the case where the two phase shifts are simultaneously present.

The main source of phase dispersion comes from the fact that the signal is an average over different atom trajectories. Atom diffraction is based on the transfer of momentum from the laser standing wave to the atom. The laser beams being horizontal, the direct and diffracted beams are in the same horizontal plane, so that the interferometer signal measures the propagation phase difference on the two arms at the same altitude y. This phase difference is a function of the y-coordinate because of the applied fields are not perfectly independent of y. The electric field of a given capacitor is inversely proportional to the capacitor spacing and if the spacings of the two capacitors are different functions of y, the Stark phase shift is function of y. In the interaction region, the magnetic field gradient ∂B/∂x is a function of the altitude y; this function goes through a minimum for the y-value corresponding to the mid-distance between the two HMW coils but the interferometer arms are not well centered with respect to the HMW coils and field calculations show that ∂B/∂x can vary by up to 10% along the estimated height of the atomic beam. Finally, the diffraction phase ϕ d is also a function of y because the laser standing wave mirrors M i are not perfectly vertical (this effect is analyzed in ref. [20]). We have also considered the possible effects of contact potentials on the electric fields, i.e. spatial variations of the order of 100 mV of the electrode work function, but this effect appeared to be fully negligible in our experiment.

Finally, the Zeeman phase shift is a function of the F, m F sub-level. If we neglect the nuclear contribution to the Zeeman energy shift (this is a very good approximation), the 8 sub-levels form 4 pairs of levels with opposite Zeeman energy shifts: one pair is formed of the F = 2 m F = ±2 sub-levels and the three other pairs are formed of the levels having the same m F value. If the two levels inside each pairs give equal contributions to the detected signal, the measured Zeeman phase shift ϕ B vanishes [14,16]. During the HMW measurements, these contributions were close to such a perfect balance (this question is discussed below): ϕ B was always small, and its value is a sensitive test of the relative weights of the (F, m F ) sub-levels.

C. Effects of a phase shift dispersion

In this part, we study the consequence of a phase dispersion on the phase shift measurement and we consider only the phases ϕ d , ϕ S and ϕ Z , because the phases ϕ HMW and ϕ AC are so small that their dispersion cannot play a significant role. Two types of dispersions are taken into account in our analysis: the position distribution due to the y-distribution of intensity of the atomic beam and the distribution over the (F, m F ) sub-level. These dispersions modify the fringe visibility but also lead to systematic effects on the measured phase shift.

Let us first consider the case of the dispersion of the phase shift ϕ(y) with the y-coordinate. The atomic beam has a non-negligible size along the y-direction and we note P (y) the distribution of the atomic beam intensity along this coordinate, with dyP (y) = 1. The fringe signal for one sub-level is given by the following average:

I = I 0 dyP (y) [1 + V 0 cos (ϕ(y))] (6)
The average over y with the weight P (y) is noted ... and we define δϕ = ϕ(y) -ϕ . If we expand the equation ( 6) up to the third order in δϕ, we get the modified visibility V m and the modified phase shift ϕ m given by:

V m V 0 = 1 - δϕ 2 2 ϕ m = ϕ - δϕ 3 6 (7)
The relative visibility V m /V 0 reveals the dependence of the Stark and Zeeman phase shifts with the atom trajectory altitude y. In particular, when two perturbations a and b producing the phase shifts ϕ a and ϕ b are simultaneously present, the modified visibility V m and the modified phase shift ϕ m cannot be deduced from the knowledge of the same quantities when the two perturbations are acting separately: this is due to the cross terms δϕ a δϕ b , present in V m , and (δϕ a ) 2 δϕ b and

δϕ a (δϕ b ) 2 , present in ϕ m .
Besides the y-position distribution, we must sum the signals of the 8 (F, m F ) sub-levels. As the Zeeman phase shifts may be important, an expansion in powers of δϕ Z (F, m F ) would not be a good approximation and, using equation ( 7), we must evaluate the sum:

I = F,mF I F,mF 1 + V F,mF cos ϕ F,mF - δϕ 3 F,mF 6 (8)
The intensities I F,mF are normalized, F,mF I F,mF = 1 and their values are discussed below. The visibility V F,mF and the phase ϕ F,mF -δϕ 3 F,mF /6 of the contribution of the (F, m F ) sub-level to the signal are functions of F, m F . From this calculation, we deduce the modified fringe visibility V m and the fringe phase shift ϕ m for the complete signal and we define a complex reduced visibility:

V r = V m exp (iϕ m ) /V 0 (9)
which is used in figure 3. For instance, equation 7 proves that the value of V F,mF for a given F, m F sub-level is different in the presence or absence of the electric field, and the modifications are opposite inside a pair of levels with opposite Zeeman energy shifts. This is an important source of systematic effects. We have developed these calculations to analyze all the systematic phase shifts which may appear in our measurement of the HMW phase.

Their volume exceeds what can be described in this supplemental material. As a consequence we will present only some tests of these results.

D. Intensities of the F, mF sub-levels

The 8 (F, m F ) sub-levels are equally populated in the incoming atomic beam: we have taken care to prevent any strong magnetic field gradient which could deviate in a different way these sub-levels so that, for the incoming atomic beam, I F,mF = 1/8. However, the diffraction amplitudes depend on the hyperfine quantum number F , because the laser frequency detuning δ L (F ) is different for these two levels because of the ground state hyperfine splitting [21]. The interferometer transmission is thus a function of F but it is independent of m F : it can be described by parameter measuring the population imbalance. For a given laser power density in the standing waves, there is a value of the laser detuning which equalizes the interferometer transmissions for the two hyperfine levels and we have taken care to work near these optimum conditions. The measured Zeeman phase shift, which vanishes if these transmissions are equal, gives a sensitive test of the transmission ratio. We estimate that, in our measurements of the HMW phase, the intensities I F,mF deviate from their optimum value 1/8 = 12.5% by not more that ±1.5% and this deviation is quasi-random, with a negligible average value.

An important consequence of the quasi-equal population of the 8 (F, m F ) sub-levels concerns the AC phase shift. In each pair of F, m F sub-levels with opposite Zeeman energy shifts, the sub-levels have opposite magnetic moments and they have accordingly opposite AC phase shifts. The existence of the AC phase shifts induces only a very small shift of the measured phase; this shift does not vanish only because, following equation ( 7), the contributions of the two levels have not the same visibility. The presence of the AC phase shift substantially modifies the measured fringe visibility as shown below in figure 5.

E. Concluding remarks

In this part, we have given an overview of the way we developed a detailed description of the signal of our atom interferometer. This detailed description, which is quite complex, will be published elsewhere. The interest of this analysis is that it gives an understanding of most of the defects of our interferometer and it predicts the variations of the fringe visibility and the existence of systematic phase shifts due to cross effects appearing when the electric and magnetic fields are simultaneously applied. We are going to test some predictions of this model in the next section.

V. SOME TESTS OF SYSTEMATIC EFFECTS

We first present here some results obtained with the application of either the magnetic field or the electric field. In a next step, we will discuss results involving the simultaneous application of both fields.

A. Magnetic field only

We have developed analytic expressions to represent the Zeeman phase shifts ϕ Z (F, m F ) as a function of F, m F and of the currents I in the HMW coil and I C in the compensator. The compensator field is always weak enough and the phase shifts are well described by linear Zeeman effect i.e. ϕ Z (F, m F ) ∝ |I c | (the independence with the sign of the current is due to adiabatic following) and only one parameter must be fitted on the experimental data to describe these phase shifts. The HMW coils produce a considerably larger magnetic field which induces hyperfine uncoupling. In order to describe the variations of ϕ Z (F, m F ) with the current |I|, we have expressed ϕ Z (F, m F ) by a power expansion in |I| up to the third order, so that 3 parameters must be fitted on experimental data to describe all the Zeeman phase shifts. However, the accuracy of this expansion decreases at large fields, the relative deviations being equal to 3% for the m F = ±1 sub-levels and 12% for the m F = 0 sublevels with the strongest magnetic field B = 1.4×10 -2 T. This lack of accuracy is the main weakness of our model. A supplementary refinement was needed to take into account the weak inhomogeneity of the laboratory field, i.e. the field when I = I c = 0 (this refinement requires the introduction of 3 additional parameters). This field is weak enough to yield linear Zeeman phase shifts and its presence slightly breaks the parity of ϕ Z (F, m F ) with regards to I or I c and it induces a quasi-discontinuity near I = I c = 0 (see figure 3).

Finally, the analytic expressions describing the variations of ϕ Z (F, m F ) with I and I C have been fitted on a very large data set involving 150 measurements using the HMW coils, the compensation coil, or both acting simultaneously. This fit involved 9 parameters: 7 parameters related to the magnetic field, the parallel speed ratio S describing the atomic beam velocity distribution and one extra parameter describing the population imbalance between the F = 1 and F = 2 levels: the 8 parameters are fitted with a single value for all the experimental data points while the population imbalance parameter must be separately fitted for different series of experiments as it varies with the laser frequency detuning. We cannot describe these results in detail but the fitted values of most parameters are very well defined with error bars of the order of a few percent. We present in figure 3 the visibility as a function of the current I in the HMW coils, with the compensator in operation. The good agreement between our model and the measured data proves that our model describes well the Zeeman phase shifts.

B. Electric field only

FIG. 4: Relative visibility Vr (V, I = 0) as a function of the applied voltage V , for two series of measurements performed with different adjustment of the mirrors of the laser standing waves. In both cases, the full (red) line represents the fit of the data which is described in the text.

We will not discuss the experiments done with a voltage applied to one capacitor only: these experiments have been used to characterize the capacitors and the atomic beam velocity distribution. We discuss here only the measurements performed with almost the same Stark phase shift on both arms so that the measured Stark phase shifts is small, ϕ S ≈ 0.1 rad. We have not found very interesting results when studying ϕ S itself: if the temperature is not fully stabilized during the experiment, ϕ S presents drifts because the temperatures of the two capacitors drift with different rates. On the contrary, the visibility gives important information on the ydependence of the Stark phase shift ϕ S and of the diffraction phase ϕ d . We must also take into account the AC phase in the presence of the laboratory magnetic field. Figure 4 presents the relative visibility for two series of measurements performed with two different alignments of the standing wave mirrors i.e. with two different functions ϕ d (y). In all experiments, the relative visibility V r (V ) = V m (V ) /V 0 is well described by a fourth order polynomial of V with a constant term equal to 1 and a null third order term, as predicted by our calculations. The fourth order coefficient is fairly independent of the mirror alignment and it simply measures the spatial dispersion of ϕ S ; the first order term is directly sensitive to the AC phase and the second order term is sensitive to the correlation of the spatial dependences of δϕ d (y) and of δϕ S (y). We are going to discuss the effect of the AC phase on the visibility in the next section.

C. Concluding remarks

In this section, we have presented some tests of our model which describes the phase and the visibility of the interference fringes in the presence of an applied electric or magnetic field. The description of the Zeeman phase shifts is complicated by hyperfine uncoupling and by the inhomogeneity of the laboratory magnetic field when the currents in the HMW and compensator coils are both vanishing but the model works well and its accuracy is very good, except for the largest values of the magnetic field produced by the HMW coil. The main effect of the Zeeman interaction is to modify the fringe visibility and these modifications are very well explained by our model. The electric field induces the Stark and Aharonov-Casher phase shifts: the measured phase shifts are weak and sensitive to thermal distortions of the capacitors but the dispersion of these phase shifts, which is due to the capacitor defects on one hand and to the F, m F -dependence of the Aharonov-Casher phase shift on the other hand, induces variations of the fringe visibility which are well described by our calculations.

VI. SIMULTANEOUS APPLICATION OF THE ELECTRIC AND MAGNETIC FIELDS

¿From the measured data, we get ϕ EB (V, I) defined by equation (4) of our letter and its counterpart for the relative visibility, V EB (V, I) = [V (V, I) V (0, 0)] / [V (V, 0) V (0, I)]. This quantity measures the non-additive character of the visibility modifications by the electric and magnetic perturbations. Our model predicts the variations with V and I of ϕ EB and V EB : the various terms which appear in the model predictions can be easily sorted out by their parity with respect to V -or I-reversal. In order to compare the model prediction with experimental results, we isolate in the measured data the component which has a given parity with respect to V -or I-reversal: this is done by combining data for opposite values of V and/or of I and taking either the half difference or the average.

A. The V -odd part of the relative visibility, VEB (V, I)

We first illustrate the efficiency of our model by comparing the variations with the current I of the V -odd part of the visibility V EB (V, I): this V -odd part is given by the difference ∆

V V EB = [V EB (V, I) -V EB (-V, I)] /2.
Our model predicts that this quantity is non-zero because of the AC phase and 5 compares some measurements of ∆ V V EB to its calculated values following equation (10): the agreement is reasonably good, the more so as there is no fitted parameter. The model results are very sensitive to the Zeeman phase shifts and these measurements are a good qualitative test for the consistency of the calculated Zeeman phase shifts. Our model predicts that the main systematic effects in ϕ EB (V, I) are even with respect to V -and Ireversals. We illustrate this term by considering the average M V ϕ EB = [ϕ EB (V, I) + ϕ EB (-V, I)] /2: this quantity would vanish in the absence of defects, as ϕ HMW is odd with respect to V -and I-reversals. Our model predicts that the dominant term in M V ϕ EB is given by:

∆ V V EB = - 2 mF =-1 ϕ AC (F = 2, m F ) sin ϕ Z (F = 2, m F ) 2 mF =-1 cos ϕ Z (F = 2, m F ) (10) Figure
M V ϕ EB = - 2 mF =-1 δϕ S δϕ Z sin ϕ Z 2 mF =-1 cos ϕ Z (11)
The F = 2, m F dependence of ϕ Z and δϕ Z being omitted for simplification. In figure 6, we compare some measurements of M V ϕ EB and the predictions of our model in this case which also includes a smaller, higher-order term: thus two parameters have been fitted on the complete data set. Their values agree with expectations deduced from independent measurements or estimates of δϕ S and δϕ Z (F, m F ).

FIG. 6: Measured values of MV ϕEB(V, I) as a function of I, with V = 800 V. The dots are the measured data and the curve is the result of our model. As in figure 5, thick vertical (grey) lines correspond to the cancelation of the visibility due to the dispersion of the magnetic phase shifts.

C. A stray phase shift which is not predicted by our model

This stray phase shift is odd with respect to Vreversal and even with respect to I-reversal.

To extract this term, we first take the combination ∆ V ϕ EB (V, I) = [ϕ EB (V, I) -ϕ EB (-V, I)] /2 which is the odd with respect to V -reversal and we take the average for opposite I-values given by M I (∆ V ϕ EB ) = [∆ V ϕ EB (V, I) + ∆ V ϕ EB (V, -I)] /2. The measured values of this quantity are plotted in figure 7 as a function of the voltage V for all the data points with the current I varying in the range from 5 to 25 A. Surprisingly, this quantity does not depend on the current I, whereas it involves the simultaneous application of both fields.

The data points are well fitted by a third-order odd polynomial in V (i.e. the sum of a term in V and a term in V 3 ). The fact that this effect is odd with V suggests a role of contact potentials but we have verified that the order of magnitude of M I (∆ V ϕ EB ) is not in agreement with other pieces of information which proves the very small influence of contact potentials. We presently have no explanation for this observation, which is still under investigation. Fortunately, the fact that this phase shift is independent of I provides a simple way of eliminating it from the HMW measurement.

VII. DETECTION OF THE HMW PHASE SHIFT

To detect the HMW phase, we may use the fact that it is odd with respect to V -reversal and I-reversal. Moreover, we must reject the largest possible part of the stray phase shifts. These ideas have led to study the difference ϕ f inal (V, I) = [ϕ EB (V, I) -ϕ EB (V, -I)] /2 : in this way, the largest stray phase shifts predicted by our model and also the I-independent unpredicted stray phase shift are both eliminated, because these two terms are both even with respect to I-reversal.

In our letter, we have plotted only the data with |I| ≤ 12 A because the stray phase shifts increase rapidly for larger currents and the data was corrected for the AC contribution to the phase shift. In figure 8, we present all the collected data without any correction for the contribution of the AC phase shift. We have used different symbols to distinguish the measurements done with |I| ≤ 12 or > 12A and we have made separate fits of these two sets of data using ϕ f inal (V, I) = αV I + β. The fit results are:

α = (-194 ± 6) × 10 -8 rad/VA β = (7 ± 4) × 10 -4 rad if |I| ≤ 12 A (12)
and

α = (-216 ± 14) × 10 -8 rad/VA β = (-26 ± 19) × 10 -4 rad if |I| > 12 A (13)
In both fits, the intercept β for V I = 0 is compatible with a vanishing value, as expected. The data with |I| ≤ 12 A is less dispersed than the data with |I| > 12 A and this appears clearly on the error bar of the slope α. From the spatial dependence of the magnetic and electric fields and lithium atom electric polarizability [12], we have predicted the value of the slope of the HMW phase as a function of V I product, ϕ HMW (V, I) /(V I) = -128 × 10 -8 rad/VA. The modulus of the fitted slope is larger than the predicted value for the two fits and the discrepancy is equal 52% if |I| 12 A and 69% if |I| > 12 A. We think that some residual stray phase shift has not been completely eliminated and the resulting error increases with the modulus of the current |I|. As a consequence, we consider that, even for the data set with |I| 12 A, the discrepancy between the expected slope and the measured slope of ϕ f inal vs V I is still dominated by this residual systematic effect.

In ϕ f inal , there is a minor contribution of the AC phase shift which can be calculated thanks to our model with no adjustable parameter. We have calculated this correction which never exceeds 3 mrad for the data set with |I| 12 A and we have made this correction in figure 3 of our letter. This last correction reduces the discrepancy on the slope of the measured phase ϕ f inal vs. V I to 31%.

VIII. CONCLUDING REMARKS

The analysis briefly summarized here explains how we have proceeded to extract the HMW phase shift from stray phase shifts due to defects of the interaction region. Indeed, thanks to its odd parity with respect to V -reversal and I-reversal, we have been able to distinguish this phase shift from various systematic effects which have been observed and fairly well explained. The description of these systematic effects is rather complex because several defects must be taken into account and also because the signal is a weighted average over 8 sublevels. The analytical model we have developed to describe systematic effects on ϕ EB and V EB explains our observations in a consistent way but, in its present form, this model is not sufficient to give very accurate values of the systematic phase shifts which would be needed to extract precisely the HMW contribution to the observed phase. We attribute the discrepancy between the measured slope of ϕ f inal vs V I and the expected slope of ϕ HMW as due to residual systematic effects.

In conclusion, thanks to a thorough analysis of systematic effects, we have been able to detect the HMW phase shift but it is difficult to estimate the systematic part of our error bar. We think that it would be interesting to make a more precise measurement but this will be possible only if we are able to reduce systematic effects. The first mean will be to use smaller values of the HMW current I so that the description of the Zeeman phase shifts will be more accurate, but the most efficient technique is to eliminate the average over the 8 sub-levels which is the main source of systematic errors. Atomic beams pumped in a single sub-level with a high purity (typically more than 97% of the population can be in the selected state) have been achieved with sodium [22] and cesium [23] and we think that it should be possible to achieve a similar result with lithium. It is possible to pump the atoms either in any one of the two m F = 0 sub-levels or in the F = 2, m F = +2 or -2 sub-levels. The Zeeman effect of the F = 2, m F = +2 or -2 sub-levels is purely linear and we think that these levels would be a better choice than the m F = 0 sub-level which have a non-zero field-dependent magnetic moment as soon as hyperfine uncoupling is not negligible. With an optically pumped beam in the F = 2, m F = +2 or -2 sub-level, the measurement will give the sum of the HMW and AC phase and we can separate the two contributions by changing the sign of m F , thus changing the sign of the AC phase without changing the HMW phase.

It will be also very interesting to verify that the HMW phase is independent of the atom velocity. In our experiment, it is possible to vary the lithium beam mean velocity by changing the carrier gas, from 700 m/s (with krypton) up to 3400 m/s (helium) [24] but the distance between interferometer arms, which varies like 1/v, becomes too small to introduce a septum when v 2000 m/s, if we use first-order diffraction. We can run the interferometer with second-order diffraction but the presence of weak first-order diffraction beams makes the experiment less clean and limits the quality of the phase measurements. With a velocity range from 700 -2000 m/s, a test of the variation of the HMW phase with velocity would be possible and significant if the error bar on the HMW phase is reduced near 10%.

FIG. 3 :

 3 FIG. 3: Real part of the complex relative visibility V r defined by equation 9 as a function of the current I in the HMW coil. The current Ic in the compensating coil being equal to Ic ≈ |I| /3 when |I| < 15 A and to IC = 5 A when |I| > 15 A. The points are measured data and the curve is the result of our analytic model fitted on a very large data set.

FIG. 5 :

 5 FIG. 5: ∆V VEB(V, I) with V = 800 V is plotted as a function of the applied current I A in the HMW coil. The squares represent our measured values while the thin (red) line is the result of our model. The thick vertical (grey) lines indicate the I-values for which the visibility vanishes as a result of the dispersion of ϕZ with F, mF . The modification of the visibility diverges for these values of the current I.

FIG. 7 :

 7 FIG.7:The phase shift combination MI (∆V ϕEB) (V, I) is plotted as a function of the applied voltage V . The full line is a fit with an odd polynomial in V up to third order.

FIG. 8 :

 8 FIG. 8: Measured values of ϕ f inal as a function of the V I product. The data points with |I| ≤ 12 A are plotted in red as well as their fit represented by a dotted line. The data points with |I| > 12 A are plotted in black as well as their fit represented by a dashed line. The expected dependence of ϕHMW with V I is represented by a black full line.


Jacques Nicolas

To Detect and to Analyze Sequence Repeats whatever their Origin

i. Summary

The development of numerous programs for the identification of mobile elements raises the issue of the founding concepts that are shared in their design. This is necessary for at least three reasons. First, the cost of designing, developing, debugging and maintaining software could present a danger of distracting biologists from their main bioanalysis tasks that require a lot of energy. Some key concepts on exact repeats are always underlying the search for genomic repeats and we recall the most important ones. All along the chapter, we try to select practical tools that may help the design of new identification pipelines.

Second, the huge increase of sequence production capacities requires to use the most efficient data structures and algorithms to scale up tools in front of the data deluge. This paper provides an up-to-date glimpse on the art of string indexing and string matching.

Third, there exists a growing knowledge on the architecture of mobile elements built from literature and the analysis of results generated by these pipelines. Besides data management which has led to the discovery of new families or new elements of a family, the community has an increasing need in knowledge management tools in order to compare, to validate or simply to keep trace of mobile elements models. We end the paper with first considerations on what could help the near future of such research on models.

ii. Key words: Repeats, Seeds, String index, Pattern matching, DNA parsing, Grammatical models.

Introduction

The many types of repeats that occur in genomic sequences have been largely described in the literature and new types are often discovered in newly sequenced species. The management of such a quantity of families rests on dedicated databases [START_REF] Jurka | Repbase Update, a database of eukaryotic repetitive elements[END_REF] or software pipelines like REPET (see [START_REF] Flutre | Considering transposable element diversification in de novo annotation approaches[END_REF] and the chapter inside this volume). Besides the study of these natural repeat families, biologists are routinely concerned with sequence comparison, a task that relies on the search of words common to a given set of sequences and is almost always based on the pre-computation of a repeat index on the sequences. This issue became even more critical with the advent of Next Generation Sequencing technologies, which is leading each laboratory to access or to produce an increasing quantity of sequence data. Considering that whole genome sequencing is becoming an ordinary practice on bacteria and the analysis of the genetic diversity of eukaryotic populations by means of large scale re-sequencing projects becomes a general trend. In this context, the presence of repeats causes major assembly issues and requires further algorithmic developments.

On the theoretical side, it is important to try describing all these repeats with a set of precise common concepts in order to better understand their structure and to rationalize the design of search algorithms. Simplified generic models are used to capture important formal properties of biological repeats. Most of them are issued from problems that arose in other domains such as data compression or web indexing. Among the corresponding studies, those addressing the fundamental problem of looking for exact repeats prevail. This paper proposes a quick review of concepts at the core of any repeat model in a 1 51 sequence, mostly focusing on exact repeats. It seems clear to us that any people interested in large scale study of genomic repeats should have a good understanding of these concepts and we have tried to point all along the chapter at efficient tools that could help turning theory into practice.

Working on exact repeats

Exact repeats are words with several identical occurrences that are possibly overlapping.

The search for approximate repeats is always based on the search for exact repeats that reflect the presence of the repeated structure and serve as anchor points during the exploration. Exact repeats have been extensively studied, starting from simple k-grams or k-mers, which are just words of fixed size k. A fundamental issue is to limit the number of representatives that are necessary in order to describe all "interesting" repeats. The notion of maximality is quite natural in this respect but not so trivial to define properly. For instance, given the string GTTCGTTTCTTA, the single letter T is repeated seven times in the string, making it the exact repeat with the maximal number of occurrences. Frequency alone is however unlikely to be useful and one has to add a criterion on the length of interesting repeats. Most of people working on sequences are familiar with statistics that help to distinguish repeats with an unexpected number of occurrences with respect to their length (see e.g. ( 3), ( 6)). Counting unexpected words is not easy because strings have combinatorial properties that have to be taken into account (see for instance section 2.3), a problem that becomes even harder in strings like genomic sequences that are structured and contained many particular patterns. The first step in any analysis is thus to be able to 1 61 explore the set of repeats without being hampered by combinatorial effects. In other terms, in genomics like in other texts, the context of word appearance matters and repeats are in some way made of letters appearing in a common context. In the string instance before, GT is a repeat made of co-occurring repeats G and T that are mutual contexts of their occurrences. In this example in fact, every occurrence of G is followed by an occurrence of T. The fact that G appears with the right context T with probability 1 renders repeat GT strictly more interesting than repeat G. The next section investigates in more details such properties.

A bestiary of simple repeats

The simplest idea of maximality is to look for each position at longest repeated substrings ending at this position (longest repeated suffixes) and present elsewhere in the string.

(very useful for plagiarism detection !).. For instance in the previous string at ending position 6, GT is the longest repeated suffix (it ends at 6 and has another occurrence ending at 2). Considering the occurrence of repeat T at this position is suboptimal in the sense that a longer repeat ends at the same position, conveying potentially more information. Some authors have designed very efficient algorithms for this task (4), and the visualization software FORRepeats has been developed on this basis [START_REF] Lefebvre | FORRepeats: detects repeats on entire chromosomes and between genomes[END_REF]. Note that every time GT occurs in the preceding string, GTT also occurs. So "longest" means "longest up to a certain position". In order to select only the string GTT, the concept of maximal repeat is necessary. A maximal repeat is a word that cannot be extended to the left or to the right without decreasing its number of occurrences in the sequence. Maximal 1 71 repeats (MR) have very nice properties since they contain longest repeats, they are never more numerous than the number of sequence characters and they contain all other repeats. Moreover these repeats can be used as basic blocks to compute error-prone repeats and they have a well defined mathematical structure of inclusion: the intersection of two MR remains a MR. As a consequence of this last property, small words are generally maximal repeats: in string GTTCGTTTCTTA, since GTT and TTC are maximal repeats, then TT is for instance also a MR. Some authors select for this reason supermaximal repeats, the set of MR that are not included in another MR. Note however that this does not guarantee anymore to cover the whole set of repetitions, e.g. the last occurrence of TT in our example is lost if only supermaximal repeats are retained. Another more interesting variation with respect to applications consists to fix a lower bound for the number of occurrences of a repeat. A multi-repeat of multiplicity k is a repeat with at least k occurrences. Maximal multi-repeats are naturally defined has multi-repeats with at least two occurrences surrounded by two different pairs of characters. Multi repeats are particularly useful in the context of multiple sequences. In this case, it may be useful to define both a multiplicity per sequence and a multiplicity over the set of sequences (quorum). In case of multiple sequences, it is sometimes possible to distinguish query sequences and target sequences. New types of maximal repeats are then relevant.

Maximal substring matches are words present in both the query and the target with at least one occurrence in the query and one in the target surrounded by different pairs of characters. If these two occurrences are the sole occurrences of the word in the target and

1 81
the query, it is called a maximal unique match and if the word is the whole query, it is called a complete match.

Repeats in general may occur everywhere in the string, possibly at overlapping positions.

Genomic sequences offer sometimes more constrained distributions. The occurrences of tandem repeats have to be consecutive in genomic sequences contrary to interspersed repeats. Technically, the term used to denote consecutive copies is repetition. The study of repetitions in sequences constitutes a foundation of stringology, a field concerned with the combinatorial study of strings and initiated at the beginning of the previous century by A. Thue. Sequences have subsequences that form periodic signals in the same way than numerical functions and this serves as the basis for very efficient pattern matching algorithms. Thus the sequence ACAAACAAAC has period 4 (for every position P, the character at P is the same than the character at P+4) and is a repetition made of the word ACAA. Maximal repetitions or runs may be defined in the same way than maximal repeats and corresponds to an abstract notion of tandem repeat purely generated by amplification and with no mutation: it denotes repetitions that cannot be extended to the left or to the right without losing their periodicity -in the example, AAA is a run of A starting at positions 3 and 7 but AA is not since it has period 1 like AAA-. Once again, maximality does not guarantee to get the longest runs. For instance, the sequence ACAACACAACAG starts with the run ACAACA of period 3 but contains a longer run, namely ACAACACAACA of period 5. Maximal repetitions are representative of all repetitions and contain branching tandem repeats, a concept used in Vmatch defined as squares ww which are not followed by the first letter of word w.

1 91

Suffix array: the leading data structure for tools working on repeats in a sequence

Genomics has been one of the driving forces together with web searching in the development of new index structures on sequences. Conversely, virtually all new developments for genome scale sequence analysis should be concerned with progress made in sequence data structure elaboration. Since various tasks have to be fulfilled on genomic sequences that may reach several giga base pairs, it is of utmost importance to achieve fast sequence pre-treatments that render such tasks independent of the length of the sequence. In practice, this requires the development of indexing algorithms with a linear or sub-linear behaviour in time and space. A suffix tree is a sequence structure made of a hierarchical dictionary of the sub-sequences starting at each position, each level of the tree corresponding to different possibilities of subsequence beginning and each leaf to a subsequence position. For instance, the suffix tree of ATATAC is tree( A(T(1,3),C(5)), C(6), T [START_REF] Flutre | Considering transposable element diversification in de novo annotation approaches[END_REF][START_REF] Lefebvre | An improved algorithm for finding longest repeats with a modified factor oracle[END_REF]). Suffix trees have long been the most efficient way to index sequence and allows the search of any word in a sequence in a time proportional to its length. However, since there is a big performance gap between main memory and disk storage and current computers have only several gigabytes of main memory, even the strict linear bound on algorithms may be insufficient for some usages -the most efficient suffix tree implementation requires 12 bytes per nucleic acid-.

1

A1

In the current state of the art, the best structure is the suffix array, a simple list of starting positions in a sequence sorted according to the ascending lexicographical order of each corresponding subsequence. For instance the suffix array of sequence GTTCGTTTCTTA is [START_REF] Homann | mkESA: enhanced suffix array construction tool[END_REF][START_REF] Lefebvre | An improved algorithm for finding longest repeats with a modified factor oracle[END_REF][START_REF] Abouelhoda | Replacing suffix trees with enhanced suffix arrays[END_REF][START_REF] Jurka | Repbase Update, a database of eukaryotic repetitive elements[END_REF][START_REF] Lefebvre | FORRepeats: detects repeats on entire chromosomes and between genomes[END_REF][START_REF] Nong | Linear Suffix Array Construction by Almost Pure Induced-Sorting[END_REF][START_REF] Reinert | Probabilistic and Statistical Properties of Finite Words in Finite Sequences[END_REF][START_REF] Puglisi | A taxonomy of suffix array construction algorithms[END_REF][START_REF] Pokrzywa | BWtrs: A tool for searching for tandem repeats in DNA sequences based on the Burrows-Wheeler transform[END_REF][START_REF] Flutre | Considering transposable element diversification in de novo annotation approaches[END_REF][START_REF] Manber | Suffix arrays: A new method for on-line string searches[END_REF][START_REF] Ussery | Word Frequencies and Repeats[END_REF], in accordance with the lexicographical order of suffixes A, CGTTTCTTA, CTTA, GTTCGTTTCTTA, GTTTCTTA, TA, TCGTTTCTTA, TCTTA, TTA, TTCGTTTCTTA, TTCTTA, TTTCTTA. Note how repeats are naturally clustered in contiguous positions in the array: for instance the last four elements of the array are positions of repeats TT. Proposed in 1990 by Manber and Myers [START_REF] Manber | Suffix arrays: A new method for on-line string searches[END_REF], the structure has been made largely available via a number of studies and implementations (8) since the work of M. Abouelhoda, S. Kurtz and E. Ohlebusch [START_REF] Abouelhoda | Replacing suffix trees with enhanced suffix arrays[END_REF] showing that suffix arrays can replace suffix trees in every aspect. In practice, some additional pre-computed tables are necessary towards this aim -based on explicit recording of prefixes common to two consecutive entries in the array-, a minor change with respect to the main structure. Suffix arrays are closely related to the so-called Burrows-Wheeler transform (BWt2 ), a reversible permutation of sequence characters that tends to generate runs in the transformed sequence. This nice property has been first used to design efficient lossless data compressors such as bzip2. It is now increasingly used in genomics. We mention here an efficient tool, BWtrs [START_REF] Pokrzywa | BWtrs: A tool for searching for tandem repeats in DNA sequences based on the Burrows-Wheeler transform[END_REF], able to look at all runs, that is, all maximal exact tandem repeats at eukaryotic genome-wide scale. This tool improves on previous ones either by its memory consumption or the fact that it is not limited in small length repeat motif like microsatellites, nor to specific alphabet. BWtrs accepts a 1

2B1

Genbank or user-defined sequence in the FASTA format and four input parameters: the minimum and maximum motif size of tandem repeats, their minimum total length and the minimum number of units (repeat ratio).

As for suffix trees, suffix array can be built with a linear time and space complexity. The best implementation available to date is probably SAIS, which has been conceived by G.

Nong (SA-IS, [START_REF] Nong | Linear Suffix Array Construction by Almost Pure Induced-Sorting[END_REF]) and further enhanced by Y. Mori. It is based on a clear divide-andconquer recursive approach and uses only 5 bytes per character. In practical applications, it may be useful to get a more complete package, including the management of auxiliary tables, allowing multiple sequences and able to make profit of multiple CPU computers via multithreading. The Bielefeld University proposes an open source program, mkESA, which answers all these constraints [START_REF] Homann | mkESA: enhanced suffix array construction tool[END_REF]. Its output is compatible with mkvtree, another widely used implementation included in the package Vmatch ((9), see section 3).

The story of sequence data structures does not end here. Research studies are now focusing on compressing the BWT while keeping interesting average computing time.

Given the current increase of main memory capacity on computers, further compression is only useful for very large strings and it is not completely clear which impact it will have an on the analysis of genomic sequences. We anticipate that the added value will come from structures taking into account basic operations needed in this context: dynamic structure adjustment for genome re-sequencing projects, management of internal mutation or insertion/deletion (indel) in repeats, management of palindromic secondary structures.

For instance, T. Schnattinger et al. [START_REF] Schnattinger | Bidirectional search in a string with wavelet trees[END_REF] have recently presented a promising technique tested on the search for miRNA genes, using a variation on wavelet trees allowing 1 221 bidirectional search and thus adapted to palindromic repeats. A wavelet tree is a natural companion of BWt originating from the field of data compression, coding sequences without loss through a tree of bit strings.

Introducing don't care positions in exact repeats

A striking characteristic of genomic sequences is that possible variations occur in a non uniform way along the positions. This reflects the existence of various biases such as the GC content or of many repeats, and more generally this is a consequence of the fact that genomic sequences are highly constrained sequences. Since all comparison methods are based on the search of exact repeats that are then extended (the seeds), this has important consequences on the sensitivity/specificity that can be achieved with respect to the length of the detected repeats. To get high sensitivity requires to limit the size of seeds as much as possible, while being specific requires both a lower bound size for these seeds (in practice Blast is used with a default seed length k=11 on DNA sequences) and to filter low complexity repeats from sequences before any search in order to get meaningful statistics of scores. A program like Blast is particularly confused by the existence of interspersed repeats. A number of tools have been developed using k-mer seeds as Blast does for the identification of genomic repeats (e.g. Repeatscout [START_REF] Price | De novo identification of repeat families in large genomes[END_REF] or ReAS [START_REF] Li | ReAS: Recovery of ancestral sequences for transposable elements from the unassembled reads of a whole genome shotgun[END_REF] ). For large genomes, authors recommend to use k=12 and more generally, for a genome of size n, k≅log4(n) gives the best results. Since a few years, a number of improvements have been carried out on Blast-like algorithms in order to choose better seeds with increased sensitivity for a same computational cost. The idea is to introduce don't care positions -jokers-along the seed (spaced seeds) and more generally some constraints on the allowed matches at each position (subset seeds). Considering simple combinatorial effects on words helps to understand the interest of spaced seeds in the reduction of dependencies. Given for instance an occurrence of word TTTT at some position, the probability to get at least another occurrence of the same word at the next three positions is 0.25, whereas it is 0.0625 for ATAT and 0 for the word ATTT. Spaced seeds and multiple spaced seeds (optimal set of seeds instead of a single one) have been used in the tool PatternHunter [START_REF] Li | highly sensitive and fast homology search[END_REF] and recent versions of Blast. The YASS software designed by L. Noe and G. Kucherov (17) is going a step further extending Blast with the use of subset seeds. YASS has proved to be useful for the pairwise aligment of mobile elements [START_REF] Weber | Mammalian Small Nucleolar RNAs Are Mobile Genetic Elements[END_REF][START_REF] Grzebelus | Diversity and structure of PIF/Harbinger-like elements in the genome of Medicago truncatula[END_REF]. Seeds may be specified using a seed motif built over a three-letter alphabet #, @ and -, where # stands for a nucleotide match, -for a don't care symbol and @ for a match or a transition -A/G or C/T-, transitions taking precedence over transversions, in both coding and noncoding regions. For instance, using the pattern ##@-##, the sequence CGCCCG will be a hit on sequence ACGTACGT on position 2 since they can be aligned with a transition T/C and a substitution A/C. Note that no score is used here. The weight of a pattern, defined as the number of # plus half the number of @, is the main characteristic of seed selectivity/sensitivity, together with the seed model itself. For instance, the pattern ######### is the Blast motif used with parameter k=9, meaning that nine consecutive 1 241 characters have to be present in order to start an alignment. Its weight is 9 and its sensitivity is 0.453, estimated with respect to alignments of size 50 generated with a simple Bernouilli sequence model. If one is interested in other patterns of weight 9, of size at most 14 and containing 2 @ and 8 #, that is, allowing 2 transitions and requiring 8 matching positions, the pattern ##@-#@#--#-### can been shown to have far greater sensitivity (0.625) and to be optimal with respect to the seed model. Designing an optimal set of seeds depends on the application at hand and programs exist to generate them.

Iedera [START_REF] Kucherov | A unifying framework for seed sensitivity and its application to subset seeds[END_REF] can be used as a pre-processing step to YASS for this purpose. It allows a number of parameters to be taken into account for seed selection and can be applied to DNA or protein sequences [START_REF] Roytberg | On Subset Seeds for Protein Alignment[END_REF]. At first sight, it seems hard to apply seed models on proteins since seeds have to be very short (w=3 for Blast) and hits have to consider the similarity of aligned sequences instead of just a match. However, subset seeds provide a good way to manage similarity without the need for score and in practice, for sufficiently long matches it is possible to improve the search sensitivity through the design of appropriate seeds. Idera has been used for instance in the software Plast, a parallel alignment search tool dedicated to the comparison of large protein banks that runs 3 to 5 times faster than the NCBI-BLAST software on this task [START_REF] Nguyen | PLAST: parallel local alignment search tool for database comparison[END_REF].

A recent approach has further demonstrated the interest of studying seeds, introducing a new idea of adaptive seed. Among other experiments, S. Kielbasa et al. [START_REF] Kiełbasa | Adaptive seeds tame genomic sequence comparison[END_REF] show an impressive comparison of chimpanzee and human Y chromosomes. This genomic region is known to be hard to compare due to a very low information content correlated to its 1 251 repeat richness and a number of rearrangements. In 2010, J. Hughes et al. succeed in sequencing the male-specific region of the chimpanzee Y chromosome and published a surprising paper in Nature [START_REF] Hughes | Chimpanzee and human Y chromosomes are remarkably divergent in structure gene content[END_REF] claiming that >30% of its content share no alignment with the human corresponding region. This corresponds to an unexpectedly high level of divergence since this level reduces to less than 2% for the rest of the genome. Authors used ClustalW with default parameters in their analysis. S. Kielbasa et al. show by using adaptive seed based comparison that the level of divergence is in fact less than 14%. It remains a high level but this implies that their method recover more than 15% possible alignments. Adaptive seeds are for any target sequence and starting position in a query the shortest seeds at this position such that the matching sequence occurs at most f times in the target, f being a fixed parameter threshold. The idea is to explore a large set of seeds (the seed length is not fixed a priori) and to quickly select the most promising ones on the basis of their level of specificity. Adaptive seeds can be computed very directly using a suffix array data structure and moreover, they are compatible with spaced and fixed seeds, leading to adaptive spaced seeds and adaptive subset seeds. In the Human/Chimpanzee Y chromosome study, repeats are made of microsatellites that have to be masked (detection of tandem repeats) and other classes of repeats such has LINEs and SINEs that have to be kept in order to increase the sensitivity of the search. S. Kielbasa et al.have developed downloadable software, Last [START_REF] Kiełbasa | Adaptive seeds tame genomic sequence comparison[END_REF], and a restricted version that can be run on a web server.

1 261
We end this section with some remarks on the way to extend exact seeds to get approximate matches taking into account possible variations. Consider first the case where only mutations occur inside repeat copies. Seeds are extended to the left while the number of mutations remains acceptable and no other seed is reached. The resulting leftextended seeds are then extended to the right while the total number of mutations remains acceptable, possibly integrating other seeds. This way, all maximal matches are reported.

If insertions and deletions are allowed, it is necessary to maintain a set of extension possibilities instead of a single value at each step. Note that the algorithm remains linear with the respect of sequence length or number of seeds but is cubic with respect to the number of errors. Under natural constraints on the cost of indel with respect to match/mismatch 3 and with the assumption that the total number of differences remains small, it is better to use it rather than the cost for constraining the search and the corresponding approach by a greedy algorithm becomes quadratic instead of cubic. window-based calculation for small dotplots to a suffix-array based computation looking at all repeats of a given length for large-scale dotplots, something that was out of reach of programs like Dotter. Gepard is compatible with the Vmatch package ( 9) and offers a command-line mode or a Java Webstart run mode. Annotated sequences can also be uploaded from the PEDANT database. Figure 1 displays a dotplot of a CRISPR (Clustered Regularly Interspaced Short Palindromic Repeats) region in the bacterial genome of H. ochraceum, a repeat-rich region where repeats form a skeleton of regularly spaced words flanking foreign genomic material.

Landscapes and Pygrams

Dotplots present the disadvantages of a quadratic representation: apart from the computational complexity, it entails an interpretation complexity that may hinder the understanding of structures made of complex repeat arrangements. We have proposed to take maximal repeat as a basis for the visualization of all repeats. Pygram (26) introduces the pyramid diagram, an abstract representation of the organization of repeated structures in genomic sequences. A pyramid diagram is a hierarchical representation of repeats along the sequence that makes use of the fact that intersections of MR are MR. Choosing a different color for each MR and displaying the smallest on top of the largest repeats, this property ensures that no maximal repeat will be masked by others. Technically, a Pygram for a genome sequence S is a bi-dimensional plot where S and all its maximal Pygrams have been the basis of the visualization software TandemGraph that has been used for tandem repeat display along the human genome and is proposed in the database TRedD [START_REF] Sokol | TRedD: A database for tandem repeats over the edit distance[END_REF]. Pygrams are also used in the CRISPR database Crispi (28).

The Modulome/Mobilome

The complex repeat architecture characteristic of every mobile element family is an interesting source of knowledge on the way they have evolved but is hardly depicted by the previous display modes. Two converging facts contribute to this difficulty. First, the variations inside a given family lead to a complex multiple alignment since starting from identical copies of an ancestor sequence, mutation, deletions or large insertions cumulate over time to produce very divergent copies. This is particularly observable in the case of non autonomous elements. These copies exhibit generally a modular structure where modules may appear in various orderings. Second, graphical tools on multiple alignments often consider them as multidimensional data that have to be projected into a 2D space like dotplots. For tools like VISTA [START_REF] Brudno | Multiple whole genome alignments and novel biomedical applications at the VISTA portal[END_REF] or GATA [START_REF] Nix | GATA: a graphic alignment tool for comparative sequence analysis[END_REF], a reference sequence has to be chosen so as to ensure a linear number of projections with respect to the number of sequences in the family. A generic software allowing beautiful and sophisticated graphics for all genomic comparison tasks has been designed by M. Krzywinski: Circos (31) uses a concentric circular layout, a practical way to display multiple information together with relationships between pairs of positions with connecting ribbons, which encode the 1 2A1 position, size, and orientation of related genomic elements. Circos can produce either bitmap images or high quality vector images. It offers many options and graphical representations (line, histogram and scatter plots, heat maps, connectors...) with a major concern of producing accurate, discernable and flexible display. For these reasons, it is a valuable asset in the development of new comparison tools with high quality outputs.

Unfortunately, this tool is lacking a true dedicated programming language and a complete user manual butmany tutorials are available on the web and show in details the wide range of Circos display modes. Figure 4 (see also the book's cover) highlights some of the possibilities of Circos on LTR retrotransposon data. For casual users, it is highly recommended to use predefined configuration files and Perl script utilities such as tableviewer -dedicated to the graphical display of data tables-. To our knowledge, there exists to date no specific Circos environment for the study of mobile element repeats, apart from a small tool, Circoletto [START_REF] Darzentas | Circoletto: visualizing sequence similarity with Circos[END_REF], combining Blast with Circos.

We have proposed a tool dedicated to the visualization of families of mobile elements, ModuleOrganizer [START_REF] Tempel | ModuleOrganizer: detecting modules in families of transposable elements[END_REF], an extension of DomainOrganizer (33) that represents a given family of TE sequences as an assembly of elementary blocks called modules. A module is a flexible motif present in at least two sequences of a family of transposable elements and built on a succession of maximal repeats. Flexibility is founded on two simple criteria that delimit the possible spacers between consecutive repeats: the length of the spacer should not be greater than the linked part and the distance between spacers should not exceed a certain threshold. We have proposed to create such modules by a recursive 1 3B1 assembly method working on the set of maximal repeats present in the family sequences and added the possibility to detect palindromic modules or truncated modules. Each sequence may then be summarized by a vector of counters associated to module occurrences. The method results in a hierarchical graphical view of sequences segmented into modules, a representation that allows the exploration of transformations that have occurred between them (see Figure 3 on the analysis of a non autonomous family).

Perspective: modelling repeats

The common approach for the analysis of particular families is the development of dedicated pipelines assembling on-the shelf tools and tuning their parameters to get the best cover of known repeats while excluding repeats associated to other families. Among recent workflows characteristic of the variety of available programs, one can cite REPET ((2) and chapter inside this volume) and REPCLASS [START_REF] Feschotte | Exploring repetitive DNA landscapes using REPCLASS, a tool that automates the classification of transposable elements in eukaryotic genomes[END_REF], some general pipelines for the annotation of transposable elements; DAGGPAWS [START_REF] Estill | The DAWGPAWS pipeline for the annotation of genes and transposable elements in plant genomes[END_REF], a workflow established to annotate transposable elements in plants or MITE-Hunter [START_REF] Han | MITE-Hunter: a program for discovering miniature inverted-repeat transposable elements from genomic sequences[END_REF], a pipeline that focuses on small class II non autonomous transposable elements such as MITE. These are valuable resources that reflect an increasing knowledge on the way mobile elements are generated and evolve over time.

What is the next step?

1 321
From one side, pipelines are costly to develop and even more to maintain. Most of them use a (possibly large) parameter sets that may be hard to tune for a new data set because it is not direct to link input parameters with the desired result. Once empirical identification methods have been designed that produce good results, a high added value can be produced by people trying to rationalize them and to formalize the type of repeats that have been characterized. This can also help to solve a major issue on the fact that user have to test and compare the results of an increasing number of programs. This can also help to solve a minor issue on the fact that elements in few copy number (e.g. up to 3) are generally ignored since automatic methods have to rely on multiple occurrences of repeats for their detection.

From the other size, there exist expert centres that have acquired through large scale scans of genomes and observation of multiple instances of repeat families a good grasp of some of their major features. How to transform such expertise into scientific hypotheses that can be tested and validated on an increasing volume of genomic sequences?

We are convinced that major improvements on these questions can only be achieved by combining two types of developments: the development of generic, efficient solvers for a variety of well defined string matching problems; and the development of generic languages for modelling the complex architecture of repeats naturally occurring in genomic sequences. The rest of this section elaborates further on these two key ideas.

1 331

Vmatch, a general framework for the search of similarities in genomes

The field of word algorithmics and stringology has clearly matured since a few years in the sense that practical programs have been developed for a broader audience. It is now possible to develop efficient pipelines with reduced code acting on top of generic softwares computing well defined string selections. Vmatch ( 9) is a package resulting from continued efforts for years in the field of indexing and pattern matching for genomic sequences (a previous version was called Reputer) and is maintained since 2003 by S.

Kurtz. It offers a flexible framework where one can proceed to a very large variety of queries. Vmatch is free for academic research and can be obtained after downloading a license agreement form. It proposes a command language whose complete possibilities are described through associated user manuals [START_REF] Kurtz | The Vmatch large scale sequence analysis software[END_REF].

The first step in using Vmatch is to build an efficient index of the sequences to be analysed. This is the role of command mkvtree, which accepts all common sequence input formats -it even accepts gzipped files-and can be further specified with many options for the construction of auxiliary search tables or the specification of the alphabet used for sequences. The alphabet may be any user-defined alphabet not larger than 250 printable symbols. It is specified by a file storing a series of lines of equivalent lettersuseful for protein sequences-and a last line of wild card characters. Another command, mkdna6idx, generates a 6 frame translation index of DNA sequences. Once the index is built, the command vmatch allows a number of different matching tasks, including Blast-like operations. It is possible to extract almost all types of fundamental repeats that have been described in section 1: maximal repeats, supermaximal repeats, branching tandem repeats, maximal substring matches, reverse complemented, matches of length k and approximate matches with errors… Furthermore, there exists a rich palette of possible post-processing treatments on the set of solutions, either with predefined options or with user-defined C code. Basically, solutions may be sorted, filtered from sequences for masking purpose, clustered together according to pairwise similarities or positions, or chained together in order to obtain maximally covering subsets of matches.

First steps in modelling

Instead of developing brand new pipelines for an in depth treatment of each mobile element family, it is tempting to go a step further and directly describe their characteristics in a suitable language that is then compiled in order to generate an operational searching procedure. A purely structural approach has some advantages with respect to more procedural approaches. Unlike de novo repeat discovery methods, structure-based methods rely on detecting specific models of transposable elements (TE) architecture, rather than just the expected results of the transposition process (i.e. dispersed repeats with similar boundaries). Potentially, they can detect low copy number families, have high specificity to detect TE repeats and can provide a preliminary Funding the analysis on models is a tendency that is particularly observable on well known families of mobile elements such as LTR retrotransposons (LTRR) for which a global architecture can be easily described (Figure 5). The SMaRTFinder platform for instance [START_REF] Morgante | A Structured motifs search[END_REF] has been developed to conduct efficient searches in DNA for structured sets of motifs, including those shared among LTRR. A structured motif is an ordered set of motifs and a list of intervals specifying the distances between motifs. In the case of LTRR elements, these motifs can be LTR end motifs, the PBS or PPT, or the DNA sequence of a highly conserved domain in an ORF. This generalized approach first starts by locating instances of individual motifs (using suffix trees in this case) and then solves a constraint satisfaction problem, by constructing a graph with motif instances as nodes and edges between nodes which satisfy order and distance constraints. Zhang and Zaki have then proposed an improvement of this method with SMOTIF [START_REF] Zhang | SMOTIF: efficient structured pattern and profile motif search[END_REF]. More recently, LTRharvest [START_REF] Ellinghaus | LTRharvest, an efficient and flexible software for de novo detection of LTR retrotransposons[END_REF] incorporates in a flexible way the knowledge on LTR transposon structural features.

Using formal languages, it is possible to define at a more abstract level such structures.

Formal languages are a framework introducing models as a set or rewriting rules acting on a starting axiom. The set of rules is called a grammar. For instance, a protein in a bacterial genome may be roughly recognized using the following grammar: In such model, the left part of a rule rewrites into its right part. Any genomic sequence that can be generated by a finite application of such rules, starting from the axiom rule, is accepted as a putative ORF by the model. Conversely, it is possible to check (i.e. to parse) a given sequence by applying the rules from right to left. Among general bioinformatics tools for genomic sequences modelling, a major contribution in this framework is due to D. Searls. He was the first to supervise developments allowing users to conceive grammars representing their biological models, and parse real genomic 1 371 sequences with them (42, 43). One of the key ideas of D. Searls is to try to find a balance between the well-founded framework of algebraic languages, a particular class of languages that offer a good expressivity/ efficiency trade-off, and the necessity to describe easily basic biological mechanisms such as copy (direct or reverse) that is at the core of genome evolution of. He has proposed to introduce in grammars a new kind of object for this purpose, the string variable, which can represent any substring and be subject to various constraints and transformations. The resulting formalism is called SVG, for String Variable Grammars. From the point of view of expressivity on biological sequences, this allows to take into account hierarchical aspects of life and presence of copies. For instance in the case of LTRR, the top level rule of the grammar could be represented by the following expression -it is given for illustration purpose only and does not pretend to be fully realistic-: Logol is a highly descriptive language (45) dedicated to the representation and search of complex models on biological sequences. Models use constrained string variables (supporting overlaps, substitution and distance errors) that can be subject to various transformations (e.g. inverse complement), gaps, and repetitions of a pattern along the sequence, negation and alternatives to define different possibilities. As in every formal grammar components can be grouped in a view to get a high level representation of a subset of components.

1

To sum up, the analysis of TE is clearly facing exciting new challenges that are going beyond the routine procedure of sequence data gathering, Blast comparison, and production of descriptive statistics. We have briefly presented principles and tools that allow to efficiently compare and display sequence structures at genome scale. The word "structure" that usually refers to 2D or 3D spatial characteristics of proteins has now to be applied on DNA sequences to denote the issue of understanding the complex architecture of modules that make genomic families. Such structures are closely related to the family associated mechanisms and are thus providing invaluable hints for a better understanding of their role. Mobile elements seem to offer a particularly interesting field of research with respect to this structural analysis. From one side, they are generally hard to analyse using standard local comparison procedures due to the existence of embedded and degenerated structures. On the other side, there exist general transposition mechanisms that constrain the architecture of mobile elements and a growing knowledge on this

1 3A1
architecture built from literature and the results generated by analysis pipelines.

Moreover, a same sequence generally contains ancient and recent copies of a given element and this is a unique opportunity with respect to the understanding of the conservation of structures during the evolution of sequences.

The future of bioinformatics will lie in a gradual transition from data management to knowledge management tools, that is, a transition towards more explicit models that can be confronted, refined and validated on the large base of whole genome studies. As in other contexts, the development of new tools is a matter of supply and demand.

Producing and keeping a precise trace of mobile elements models, whatever the modelling language used for this purpose and even if tools are still lacking, would be a valuable contribution to the advances in this domain.

1 231

 1

  Various kinds of tools displaying repeats at genome level have been proposed in the past, one of the oldest and still in use being dotplots. Dotplot is a quadratic representation of repeats, crossing in a 2D array a sequence either with itself or another sequence. The possibilities of this type of representation have been greatly enhanced since a few years by integrating suffix array indexing possibilities. Gepard (25) can switch from a classical 1 271

1 281

 1 repeats are mapped along the x-axis. Given an x-axis magnifying factor zx and a y-axis magnifying factor zy, mapping is defined as follows: the ith nucleotide of S is located at position (i/zx,0), and the MR of size m located at position i within S corresponds to an isosceles triangle (a pyramid) of height d m/ zy and base [i/zx, (i+ m)/zx] on the x-axisd =1 for a MR on the normal strand or -1 for a MR on the reverse strand-. The pygrams may be considered as a rational reconstruction of landscapes -defined by B. Clift, G. Stormo et al. in 1986 and extended in 1998-, fully characterizing the structure that is displayed without requiring the computation of intermediate repeats. Pygram introduces various practical improvements over landscapes (two-strand display, zoom lenses) and offers several additional features, including frequency visualization and multigenome repeat analysis. Most important, Pygram visualization is closely associated with a querysystem designed to locate repeats that share specific properties. When combined, the query system and visual interface provide an efficient repeat browser that is useful for discovering unexpected structures in genomes.

Figure 2 ,

 2 Figure 2, provides the pygram of the CRISPR structure of figure1. The zoomed region

1 341

 1

1

 1

1 351

 1 structural classification of the newly identified TE. In contrast to homology-based methods, structure-based methods are less biased by similarity to the set of known elements.

1 361

 1 Axiom → Start Codons Stop. Start → NotC TG Stop → TAG| TGA | TAA Codons→ Codon Codons→ Codon Codons Codon → Na Na Na NotC-> A | G | T Na-> A | C| G | T

1 461

 1

Figure 1 .Figure2. Pygrams of the same genomic regions than in figure 1 Figure 3 .Figure 4 :

 1134 Figure 1. Dotplots produced by Gepard. The right dotplot has been obtained by

Figure 5 . 1 481Figure 1 :Figure 2 :

 5112 Figure 5. Abstract structure of a LTR Retrotransposon

1 1 4A1Figure 3 : 1 5B1Figure 4 :

 11314 Figure 3: Module organization of Foldback4 in the D. melanogaster genome

1 31

 31

If SA denotes the suffix array of sequence s then BWt[i], the i th letter of the BWt, is the s[SA[i]-1 mod|s|].In our example, it corresponds to string TTTACTTTCGTG.

Acknowledgement

This work was supported in part by a grant from the Agence Nationale de la Recherche [project Modulome ANR-05-MMSA-0010-01].

1 421


Christophe Crespelle

Philippe Gambette

(Nearly-)Tight Bounds on the Linearity and Contiguity of Cographs

(Nearly-)Tight Bounds on the Linearity and Contiguity of Cographs

Christophe Crespelle, Philippe

Extended Abstract

Introduction. Linearity and contiguity are graph parameters introduced to obtain ecient codings of neighborhoods in graphs, by decomposing each neighborhood as a union of p intervals chosen in one or several orders on the vertices [START_REF] Crespelle | Ecient Neighbourhood Encoding for Interval Graphs and Permutation Graphs and O(n) Breadth-First Search[END_REF]. Indeed, storing an order of the vertices as well as a pair of pointers for each of the p intervals of this order (one pointer for the beginning of the interval and one for the end), with xed p, allows to store the graph in O(n) space (instead of O(n + m) with adjacency lists) and access the neighborhood of any vertex v in O(d) time (instead of O(n) with adjacency matrices), where d is the degree of v.

More formally, a closed p-interval-model of a graph G = (V, E) is a linear order σ on V such that ∀v ∈ V, ∃(I 1 , . . . , I p ) ∈ (2 V ) p such that ∀i ∈ 1, p, I i is an interval of σ and N [x] = 1≤i≤p I i . The closed contiguity of G, denoted by cont(G), is the minimum integer p such that there exists a closed p-interval-model of G. A closed p-line-model of a graph G = (V, E) is a tuple (σ 1 , . . . , σ p ) of linear orders on V such that ∀v ∈ V, ∃(I 1 , . . . , I p ) ∈ (2 V ) p such that ∀i ∈ 1, p, I i is an interval of σ i and N [x] = 1≤i≤p I i . The closed linearity of G, denoted by lin(G), is the minimum p such that there exists a closed p-line-model of G.

Not much is known about these parameters, which cannot be bounded by a constant even in very restricted graph classes, like interval or permutation graphs [START_REF] Crespelle | Ecient Neighbourhood Encoding for Interval Graphs and Permutation Graphs and O(n) Breadth-First Search[END_REF]. We focus here on the contiguity and linearity of cographs (graphs without induced P 4 subgraphs), whose very constrained structure can be represented by their cotree, a rooted tree with two kinds of nodes labeled by P and S, giving a tight upper bound for the asymptotic contiguity of cographs and an upper bound for their linearity. To this aim, we rst establish a min-max theorem on the link between the rank of rooted trees and their decompositions into paths.

A min-max theorem on the rank of a tree. The rank [START_REF] Ehrenfeucht | Learning Decision Trees from Random Examples[END_REF][START_REF] Gavaldà | Thérien Algebraic Characterizations of Small Classes of Boolean Functions[END_REF] of a tree T is the maximal height of a complete binary tree obtained from T by edge contractions, that is rank(T ) = max{h(T ) | T complete binary tree, minor of T }.

A path partition of a tree T is a partition {P 1 , . . . , P k } of V (T ) such that for any i, the subgraph T [P i ] of T induced by P i is a path, as shown in Figure 1(a). The partition tree of a path partition P, denoted by T p (P) and illustrated in Figure 1(b), is the tree whose nodes are P i 's and where the node of T p (P) corresponding to P i is the parent of the node corresponding to P j i some node of P i is the parent in T of the root of P j . The height of a path partition P of a tree T , denoted by h(P), is the height h(T p (P)) of its partition tree. The path-height of T is the minimal height of a path partition of T , that is ph(T ) = min{h(P) | P path partition of T }.

(a) (b)

Figure 1: A tree T and a path partition P = {P 1 , P 2 , P 3 , P 4 , P 5 , P 6 } of T (a), as well as the partition tree of P (b).

Lemma 1 For a rooted complete binary tree T , rank(T ) = ph(T ) = h(T ).

Theorem 2 For any rooted tree T , we have rank(T ) = ph(T ).

Upper bounds for contiguity and linearity of cographs. We now combine the results of the previous section with a decomposition of the cotree of the input cograph into paths, in order to obtain a constructive proof that the contiguity of any cograph is at most O(log n). This decomposition is obtained recursively, using a root-path decomposition of the cotree, thanks to the Caterpillar Composition Lemma below.

A root-path decomposition (see Fig. 2) of a rooted tree T is a set {T 1 , . . . , T p } of disjoint subtrees of T , with p ≥ 2, such that every leaf of T belongs to some T i , with i ∈ [1..p], and the sets of parents in T of the roots of T i 's is a path containing the root of T .

cont(G[X i ]).

Lemma 4 Given a rooted tree T such that rank(T ) = k ≥ 1, there exists a root-path decomposition {T 1 , . . . , T p } of T such that for each i ∈ [1..p], rank(T i ) ≤ k -1.

Lemma 5 Let G be a cograph and T its cotree. We have cont(G) ≤ 2 rank(T ) + 1.

Theorem 6 The closed contiguity of a cograph is at most logarithmic in its number of vertices, or more formally, if G = (V, E) is a cograph, then cont(G) ≤ 2 log 2 |V | + 1.

Lower bounds for contiguity and linearity of cographs. Finally, we focus on cographs whose cotrees are complete binary trees, and obtain a tight lower bound for their asymptotic contiguity as well as a lower bound for their asymptotic linearity.

Theorem 7 Let G be a cograph whose cotree is a complete binary tree. Then, cont(G) = Ω(log n) and lin(G) = Ω(log n/ log log n).

Figure 2 :

 2 Figure 2: The root-path decomposition {T 1 , . . . , T p } of a rooted tree T .