Elaine Silva Dias
email: elainedias_bio@yahoo.com.br

Clémence Hatt
email: clemhatt@gmail.com

Perla Hamon
email: perla.hamon@ird.fr

Serge Hamon
email: serge.hamon@ird.fr

Michel Rigoreau
email: michel.rigoreau@rdto.nestle.com

Dominique Crouzillat
email: dominique.crouzillat@rdto.nestle.com

Claudia Marcia

Aparecida Carareto
email: carareto@ibilce.unesp.br

Alexandre De Kochko
email: alexandre.dekochko@ird.fr

Romain Guyot
email: romain.guyot@ird.fr

Marcia Aparecida Claudia

Carareto

Alexandre De

Large distribution and high sequence identity of a Copia-type retrotransposon in angiosperm families

Keywords: Copia25, transposable element, genome dynamics, sequence conservation, horizontal transfer, Rubiaceae

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

Introduction

Transposable elements (TEs) are the major component of plant genomes. TEs are typically "vertically" transmitted from parent to offspring. If a new insertion occurs in germ cells tissues, the new copy will be transmitted to the progeny. In certain cases, TEs can be horizontally transferred (HT) between reproductively isolated species. Although more than 200 cases of HT have been reported most of them involve animals [START_REF] Schaack | Promiscuous DNA: horizontal transfer of transposable elements and why it matters for eukaryotic evolution[END_REF]), mainly insects (mostly Drosophila), and few potential cases have been reported in plants [START_REF] Cheng | A new family of Ty1-copialike retrotransposons originated in the tomato genome by a recent horizontal transfer event[END_REF][START_REF] Diao | Horizontal transfer of a plant transposon[END_REF][START_REF] Fortune | Horizontal transfer of transposable elements in plants[END_REF][START_REF] Roulin | Evidence of multiple horizontal transfers of the long terminal repeat retrotransposon RIRE1 within the genus Oryza[END_REF]) with the exception of a very recent observation [START_REF] Baidouri | Widespread and frequent horizontal transfers of transposable elements in plants[END_REF]). The HTs concern both Class I (or Retrotransposon) and Class II (or Transposons) elements, and the mechanisms underlying TE HTs remain speculative in most of the cases (vectors could be pathogens, intracellular parasites, insects, etc.). Because TEs play a major role in the dynamics of genomes, their direct introduction into a "naïve" genome through HT may induce important consequences in chromosomal and genomic evolution. However, the detection of potential HT of TEs in complete genomes is relatively complex and requires highly sensitive methods to differentiate between unresolved sequence conservation and HT events (de Carvalho and Loreto 2012). In the absence of a clear mechanism underlying HT, cases of outstanding sequence conservation of TEs between evolutionarily distant plant species living in separate geographical areas have raised questions as to the existence of other mechanisms leading to this conservation [START_REF] Moisy | The Tvv1 retrotransposon family is conserved between plant genomes separated by over 100 million years[END_REF]). The recent availability of plant genome sequences [START_REF] Michael | The First 50 Plant Genomes[END_REF] gave new opportunities to identify and to characterize transposable elements and to gain a higher understanding of the evolutionary dynamics of these elements and their conservation between distantly related species.

The coffee genus (Coffea) that belongs to the Rubiaceae family, comprises 124 species, originating from Africa, Madagascar, the Mascarene Islands, Asia and Oceania [START_REF] Davis | Six species of Psilanthus transferred to Coffea (Coffeeae, Rubiaceae)[END_REF][START_REF] Davis | Psilanthus mannii, the type species of Psilanthus, transferred to Coffea[END_REF]. Coffea species are diploids (2n = 2x = 22) and generally allogamous. The notable exception is the self-fertilizing allotetraploid Coffea arabica (2n = 4x = 44), native to the Ethiopian highlands and originating from a recent hybridization of two different diploid ancestors, C. canephora and C. eugenioides [START_REF] Lashermes | Molecular characterisation and origin of the Coffea arabica L. genome[END_REF][START_REF] Yu | Micro-collinearity and genome evolution in the vicinity of an ethylene receptor gene of cultivated diploid and allotetraploid coffee species (Coffea)[END_REF]). The current possibility of accessing genomic and transcriptomic sequences of Coffea species has made it possible to expand our knowledge of the composition and behavior of TEs in these important species. The analysis of the C. canephora genome showed that these sequences contained about 50% of transposable elements [START_REF] Denoeud | The coffee genome provides insight into the convergent evolution of caffeine biosynthesis[END_REF]). The vast majority of them (85%) are retrotransposons with LTRs (LTR-RTs). The study of TEs in Coffea is very recent and the few individual TEs investigated to date show different dynamics between closely related coffee species [START_REF] Hamon | Two novel Ty1-copia retrotransposons isolated from coffee trees can effectively reveal evolutionary relationships in the Coffea genus (Rubiaceae)[END_REF]Yuyama et al. 2012).

In this study, LTR-RTs were identified in the C. canephora genome using BAC-end sequences (BESs) and 454 sequences. One of them, a Ty1-Copia element named Copia25, was characterized and analyzed under different aspects of its evolution because its nucleotide sequence showed unusually high similarities with distantly related plant genomes.

Furthermore, Copia25 was found quite similar to Rider, an active retrotransposon identified in the tomato with a rather unique evolutionary history. Rider activity has played a role in the origin of at least three different phenotypes of this species [START_REF] Jiang | Genome organization of the tomato sun locus and characterization of the unusual retrotransposon Rider[END_REF][START_REF] Jiang | Rider Transposon Insertion and Phenotypic Change in Tomato[END_REF][START_REF] Xiao | A retrotransposon-mediated gene duplication underlies morphological variation of tomato fruit[END_REF]). Since it is absent in Solanum tuberosum, it has been suggested that Rider appeared in the tomato by HT from Arabidopsis thaliana [START_REF] Cheng | A new family of Ty1-copialike retrotransposons originated in the tomato genome by a recent horizontal transfer event[END_REF]). The similarity shared between Copia25 and Rider makes the TE identified in C. canephora interesting to investigate, particularly for its activity and evolutionary dynamics. In the current study, we show that Copia25 is an active element in Coffea, widely present in Rubiaceae species. In addition, a phylogenetic analysis indicates outstanding conservation of Copia25 in coffee trees and in distantly related species, such as banana (Musa genus), a monocot. The different processes that can lead to high conservation of Copia25 in Angiosperms are discussed.

Materials and Methods

Genome sequencing

The Next-Generation Sequencing (NGSby Genomic 454 Pyrosequencing -GS Junior System Roche) was performed in two accessions of C. canephora Pierre ex A. Froehner and Craterispermum Sp. Novo Kribi (from Cameroon) [START_REF] Chevalier | Ecologie et distribution géographique des caféiers sauvages et cultivés[END_REF][START_REF] Maurin | Towards a Phylogeny for Coffea (Rubiaceae): identifying well-supported lineages based on nuclear and plastid DNA sequences[END_REF]).

The cultivars and the above-mentioned sequenced accessions grow in the IRD greenhouses (Montpellier, France), at the Kianjavato research station (Madagascar) or in the Nestlé R&D greenhouses (Tours, France). The total genomic DNA was extracted from young leaves using the Qiagen DNeasy Plant Mini Kit following the manufacturer's protocol. The library and sequencing for the NGS were performed at the Nestlé R&D laboratory according to the Roche/454 Life Sciences Sequencing Method. Data were submitted to GenBank, BioProject PRJNA242989.

Sequence Analyses

We used 131,412 BAC end sequences (BESs) [START_REF] Dereeper | BAC-end sequences analysis provides first insights into coffee (Coffea canephora P.) genome composition and evolution[END_REF]) obtained by Sanger sequencing and 106,459 sequences obtained by 454 Roche-NGS technology, both derived from the C. canephora HD200-94 accession. All sequences (Sanger and 454 Roche) were used for the assembly using AAARF (Assisted Automated Assembler of Repeat Families -DeBarry et al. 2008). The following parameters for the BLAST analyses and the Minimally Covered Sequences (MCS) construction and controlling "build" extensions were applied: minimum hit length: 150; minimum hit identity: 0.89; minimum coverage depth: 4; required MCS length: 150; maximum E-value: 1e -25 ; required coverage length: 150; minimum hit number: 2; required overlap between MCS and new query: 90; and maximum times a number sequence is used in each direction: 13. These parameters were those that gave best assembly results after several modification and assembly testing.

AAARF "builds" were analyzed using BLASTx (min E-value 1e -4 ) against public protein sequence databases (uniprot_sprot; http://www.uniprot.org/), and transposable element databases available in Repbase [START_REF] Jurka | Repbase Update, a database of eukaryotic repetitive elements[END_REF] http://www.girinst.org/repbase/) and Gypsy DB 2.0 (http://gydb.org - Llorens et al. 2011). The graphical dot-pot (Dotter -Sonnhammer and Durbin 1995) was also performed. The final annotations of each "build" were edited in Artemis [START_REF] Carver | ACT: the Artemis Comparison Tool[END_REF]). Validation of LTR-RT "build" structures was performed by comparative analysis with public Coffee BAC sequences, from the NCBI and the genome of C. canephora (Denoeud et al. 2014 -coffee-genome.org). Five BAC clones for C. canephora (EU164537, HQ696512, HQ696507, HQ696513 and HM635075) and 12 BAC clones for C. arabica (GU123896, GU123899, GU123898, GU123894, GU123897, GU123895, HQ696508, HQ696510, HQ696509, HQ696511, HQ834787 and HQ832564) were downloaded from GenBank, accounting for a total of 3,023 Mb. BLASTN searches (Evalue < 1e -150 ) against public Expressed Sequenced Tags (ESTs) databases from C. canephora and C. arabica were used to evaluate the transcription of the builds.

Estimation of the Copia25 copy number using 454 sequencing survey

BLASTN searches were carried out with the full-length Copia25 sequence (from BAC HQ696507) as query. Reads with more than 90% of nucleotide identity with Copia25 over a minimum of 80% of the read lengths were considered as potential fragments of the element.

Cumulative lengths of aligned reads to Copia25 were used to extrapolate the contribution of the element to each genome size investigated.

Identification of Copia25 in plant genomes

The sequence trimmed from AAARF was blasted against the C. canephora genome, as well as against 40 angiosperm and one non-angiosperm genome sequences available in the public databases of NCBI, Phytozome and Gramene (Table S1). BLASTN was used to search for the complete nucleotide sequence or the coding region of Copia25 in the genomes. The retrieved sequences were analyzed using LTRharvest [START_REF] Ellinghaus | LTRharvest, an efficient and flexible software for de novo detection of LTR retrotransposons[END_REF]) in order to recover only the sequences with a structure similar to retrotransposons. These sequences were compared to the amino acid sequence of the Copia25 reverse transcriptase (RT) using TBLASTN and against the Ty1-Copia retrotransposon databases of plants (Repbase http://www. girinst.org) resulting in 98 sequences from 34 species (Table S2).

Molecular analysis

The DNA of 24 Rubiaceae species (Table S3, Fig. S1) was extracted by using DNeasy Plant mini-kit (QIAGEN). The DNA of the Musa species was donated by Dr. A. D'hont (CIRAD, France). Primers were designed on intact RT region of C. canephora Copia25 genomic sequences using Primer3 (http://bioinfo.ut.ee/primer3-0.4.0/primer3/) (Forward: 5' GGG GTT GAA GAT GCA AGG TA 3'; Reverse: 5' AGC TGC TCC CAA ATC TTT CA 3'). For the reaction, 0.625 unit of Taq polymerase (Invitrogen), 20 ng genomic DNA, 1 mM of MgCl2, 1 X buffer, 0.08 mM of dNTPs and 0.4 mM of each primer were used for a final volume of 25 µL. PCR conditions were as follows: initial denaturation (94 °C, 120 s); followed by 40 cycles of denaturation (94 °C, 30 s), annealing (55 °C, 30 s) and extension (72 °C, 180 s). Each PCR product was analyzed by gel electrophoresis on 1.2% agarose gel, purified (DNA GFX DNA & Gel Band, GE) and cloned (TOPO XL Cloning kit, Invitrogen) according to the manufacturer specifications. The plasmids extracted were sequenced using the specific primers. The Copia25 sequences were registered under the GenBank Accession Numbers KM439056 to KM439101. For the reverse transcription polymerase chain reaction (RT-PCR) 1 μg of the total RNA from leaves of C. canephora, C. eugenioides and C. arabica was treated with RQ1 RNase-Free DNase (Promega) and reverse-transcribed using ImProm-II™ Reverse Transcription System (Promega). The synthesized cDNA served as templates for RT-PCR. DNA contamination was checked using the primers of the gene sucrose synthase (SUS10/SUS11 - [START_REF] Marraccini | RBCS1 expression in coffee: Coffea orthologs, Coffea arabica homeologs, and expression variability between genotypes and under drought stress[END_REF]). RT-PCR was performed using the same specific primers according to the protocol described as before, with 50 ng of cDNA.

Evolutionary Analyses

Phylogenetic analyses were performed with MEGA 5.2 [START_REF] Kumar | MEGA: a biologist-centric software for evolutionary analysis of DNA and protein sequences[END_REF]) on sequence datasets aligned with the MAFFT program. Each phylogeny was reconstructed using the best model using Find Best DNA/Protein Model (Maximum Likelihood) in Mega 6 [START_REF] Tamura | MEGA6: molecular evolutionary genetics analysis version 6.0[END_REF]), with 1000 replicates; the bootstrap consensus tree inferred is taken to represent the evolutionary history of the taxa analyzed. All positions containing gaps and missing data were eliminated. As rates of synonymous substitution are not available for Rubiaceae (genes or TEs), and because LTR sequences (non-coding regions) and those from the RT domain (coding region) may evolve differently, two rates, estimated for grasses and palms, were used.

The age of insertion of Copia25 within C. canephora genome was estimated using the molecular clock equation, as previously described [START_REF] Moisy | The Tvv1 retrotransposon family is conserved between plant genomes separated by over 100 million years[END_REF][START_REF] Sanmiguel | The paleontology of intergene retrotransposons of maize[END_REF][START_REF] Wicker | Genome-wide comparative analysis of copia retrotransposons in Triticeae, rice, and Arabidopsis reveals conserved ancient evolutionary lineages and distinct dynamics of individual copia families[END_REF], where k was the Kimura 2-parameter distance between both LTRs of the same copy, and r is 1.3 x 10 -8 base substitutions per site per year [START_REF] Ma | Rapid recent growth and divergence of rice nuclear genomes[END_REF]. The Kimura 2-parameter method of distance estimation of non-coding nucleotide sequences was used for LTR distance estimation [START_REF] Sanmiguel | Nested retrotransposons in the intergenic regions of the maize genome[END_REF]). However, gene conversion between LTR of the same element could be a source of errors in estimating insertion time. This putative error is not taken into account in our analysis since conversion of LTR remains poorly understood in plant genomes. The age of the ancestor of the Copia25 sequences was also estimated using the molecular clock equation, using Ks (number of synonymous substitutions per synonymous site) and the rate of synonymous substitutions as 6.5 x 10 -9 base substitutions per site per year [START_REF] Gaut | Substitution rate comparisons between grasses and palms: synonymous rate differences at the nuclear gene Adh parallel rate differences at the plastid gene rbcL[END_REF] for the RT domain [START_REF] Vitte | LTR retrotransposons in rice (Oryza sativa, L.): recent burst amplifications followed by rapid DNA loss[END_REF]).

In order to investigate whether Copia25 was under selective pressure a codon substitution model was used to estimate ω (Ka/Ks). The ω ratio measures the direction and the magnitude of selection on amino acid changes, with values of ω < 1, = 1, and > 1 indicating negative purifying selection, neutral evolution, and positive selection, respectively. To estimate ω two approaches were used: (i) the Ka/Ks pairwise ratio for species with the full-length polyprotein sequence available (coffee, potato, tobacco and banana); and (ii) likelihood ratio tests (LRTs) for a simplified phylogeny (Fig. S2) containing species representatives of each of the Rubiaceae tribes and potato, tobacco and banana, using 315 nt of the RT domain. Premature stop codons were removed from the sequences for both analyses. For the pairwise Ka/Ks, the reference sequences of the Copia25 Subfamilies 1 and 2 (chr7_16264485-16269785 and chr8_8081742-8086630 respectively) were compared with their homologous sequences in potato, tobacco and banana. Ka and Ks were obtained using DnaSP v5 [START_REF] Librado | DnaSP v5: a software for comprehensive analysis of DNA polymorphism data[END_REF]. Selective pressure acting on COSII (conserved orthologs group) genes of potato, banana and coffee [START_REF] Wu | Combining bioinformatics and phylogenetics to identify large sets of single-copy orthologous genes (COSII) for comparative, evolutionary and systematic studies: a test case in the euasterid plant clade[END_REF]) was also investigated. The COSII sequences in potato and C. canephora are available on the Sol Genomics Network website (http://solgenomics.net).

515 COSII accessions present in single copy in potato and coffee were blasted (BLASTn) against the Musa acuminata CDSs (D 'Hont et al. 2012 -http://banana-genome.cirad.fr/) in order to obtain the Musa COSII sequences. Seven COSII sequences showing the highest sequence identity were used to calculate the Ka/Ks ratio and nucleotide identity (Table S4).

The second approach used different ω ratio parameters for different branches on the phylogeny [START_REF] Anisimova | Multiple Hypothesis Testing to Detect Lineages under Positive Selection that Affects Only a Few Sites[END_REF][START_REF] Yang | Synonymous and nonsynonymous rate variation in nuclear genes of mammals[END_REF]. To estimate the log likelihood values (LRT), a one-ratio model was used. This model assumes the same ω free or fixed (ω = 1) parameter for the entire tree, Model I and Model II, respectively. A two-ratio model was used to estimate the LRTs for specific clades on the phylogeny, since we assumed that the sequence group of interest (separately for Ixora, Model III = ω free, and Model IV = ω fixed; and, for Musa, Model V = ω free, and Model VI = ω fixed) has a different ωF from that of the ωB background. For the pairs of models (I vs II, III vs IV, V vs VI)), the log likelihood values were compared in a hypothesis test (X 2 ). These analyses were implemented using the codeml program in the PAML package [START_REF] Yang | PAML: a program package for phylogenetic analysis by maximum likelihood[END_REF].

Results

Assembly of repeated sequences with BAC-end Sanger sequences and 454 random reads from C. canephora

Sanger and 454 sequences from C. canephora (accession HD200-94) were used to identify and characterize the TEs. Two bacterial artificial chromosome (BAC) libraries were recently constructed from the same plant and a total of 134,827 Sanger sequences (mean size 683 bp) were generated from BAC-end sequences (BES) and released [START_REF] Dereeper | BAC-end sequences analysis provides first insights into coffee (Coffea canephora P.) genome composition and evolution[END_REF]).

In addition, 106,459 random 454 Roche reads (mean size 423 bp) were also generated from the same plant (Table S5).

In all, Sanger and 454 sequences represent 137,104,866 bp (241,286 sequences), giving an estimated coverage of 19.5% of the C. canephora genome (710 Mb). They were used together to assemble repeated sequences using the Assisted Automated Assembler of Repeat Families Algorithm (AAARF, DeBarry et al. 2008). A total of 1,306 "builds" (also called contigs) were generated with a length ranging from 135 to 24,745 bp, and a mean length of 1,306 bp. Most of them (45%) have a length comprised between 0.5 and 1 kb. In total, 317 builds showed similarities with TE proteins available in public databases after translating the assembled sequences. Fifty-two of them, showing sizes larger than 3 kb, were selected for the subsequent analysis. Forty-nine out of 52 showed strong similarity to LTR-RT proteins (Table S6 andTable S7). Over the 49 contigs, 12 elements were removed due to non-canonical (complex) structure, suggesting incorrect assembly, and in a significant number of builds, manual corrections were made (Table S6, 10 builds labeled with ‡), following the same procedure as described in De Barry et al. (2008). The 37 remaining builds with canonical TE structures showed exclusively similarities with LTR-RT proteins, suggesting that it may represent the main abundant transposable element family in the C. canephora genome (Table 1). These 37 potential retrotransposon builds, were manually annotated, and incomplete structures of all them were found (Fig. S3). According to the structural annotation, the were classified as "LTR-I-LTR" when the internal region and both complete or partial LTRs were present; as, "I" if only an internal region was present, as "LTR-I" with complete or partial 5' LTR with an internal region, and, "I-LTR" with an internal region and complete or partial 3' LTR (Table S6).

The 37 LTR-RT builds were used as query for similarity search (BLASTn) for complete or partial copies present in the available Coffea BAC clones sequences (Table S6).

Ten LTR-RT builds showed high levels of nucleotide conservation with nine C. canephora (4) and C. arabica (5) BAC sequences (BLAST E-value cutoff: 10e -100 ; Table S6). Moreover, some builds showed similarities with Coffea transcriptomic sequences. Indeed, 15 and four LTR-RT builds were found in C. canephora and C. arabica ESTs, respectively (Table S7).

Characterization of Copia25, a Ty1-Copia LTR retrotransposon in Coffee trees

Among the retrotransposons identified in C. canephora sequences (accession HD200-94), the sequence of one Ty1-Copia element, hereafter named Copia25, showed high BLASTN scores across various distantly related plant genomes, suggesting that Copia25 has a singular evolutionary history. Copia25 also showed an overall structure similarity to Rider (EU195798), an active retrotransposon found conserved between distant dicot species [START_REF] Cheng | A new family of Ty1-copialike retrotransposons originated in the tomato genome by a recent horizontal transfer event[END_REF][START_REF] Jiang | Rider Transposon Insertion and Phenotypic Change in Tomato[END_REF]), as indicated by dot-plot alignment (not shown). The Copia25 reassembled contig was blasted (BLASTN 10e -100 , Table S6) against C. arabica and C. canephora BAC sequences. It was found in C. canephora but with an uncommon arrangement, which appears to be a tandem of two elements sharing one LTR sequence in the median of the structure (accession HQ696507). In C. arabica, in turn, a complete sequence of 5,382 bp was found. This sequence is flanked by two perfect 5-bp TSDs (5'-GGAAC-3'), and its two LTRs are both 530 bp long and show high sequence identity (99.2%) (accession HQ832564 -Fig. S4). This copy is localized on a homologous region to C. canephora, most probably the C. canephora sub-genome within C. arabica, but it is absent in the syntenic region in both 126 [START_REF] Moschetto | Studies on the effect of genotype on cup quality of Coffea canephora[END_REF][START_REF] Yu | Micro-collinearity and genome evolution in the vicinity of an ethylene receptor gene of cultivated diploid and allotetraploid coffee species (Coffea)[END_REF]) and HD200-94 C. canephora genotypes [START_REF] Denoeud | The coffee genome provides insight into the convergent evolution of caffeine biosynthesis[END_REF].

A search was also made for the Copia25 contig (using Censor) in the C. canephora genome [START_REF] Denoeud | The coffee genome provides insight into the convergent evolution of caffeine biosynthesis[END_REF]) and 72 full-length copies were identified. All of them showed premature stop codons in the pol coding region, indicating that none of them is potentially functional. Nonetheless, similarity searches showed high sequence identity between Copia25 and Expressed Sequence Tags (98 and 99% of nucleotide identity with DV679393 and GT681881, respectively). In addition, the Copia25 RT regions were successfully amplified by RT-PCR on RNA extracted from C. canephora, C. arabica and C. eugenioides leaves (Fig. S5).

Full-length Copia25 copies exist throughout the C. canephora genome mainly in genepoor and LTR-RTs rich areas. The majority of them are located in the non-anchored set of scaffolds (pseudo-chromosome "0") (Fig. 1a; Table S8). The sharing of structural characteristics among group of sequences of a TE family might indicate the occurrence of subfamilies. In such cases, the different groups have different most recent ancestral copyi.e. different mother (or master) copy -, which independently originated copies. A Maximum Likelihood with the distance corrected by General Time Reversible model and 1000 replicates phylogenetic tree was produced using the pol (2,640 nt) nucleotide sequence of the 72 fulllength Copia25 copies. Based on the tree topology, two clusters were segregated (Fig. 1b). Following Wicker's parameters (Wicker et al. 2007) segregating criterion they are hereafter considered as subfamilies, one harboring 44 copies (Subfamily 1) and the other 28 (Subfamily 2). Only one copy did not group with either of the two clusters; this copy was discarded from further analyses. In each subfamily, the sequence with the perfect structure (based on the best conservation of both LTRs and the presence of an intact or few stop codons in the ORF coding for the polyprotein) was chosen as a reference sequence for the subfamily (Subfamily 1: chr7_16264485-16269785; Subfamily 2: chr8_8081742-8086630). These two sequences are 87.8% identical, and have 9.8% of InDels. The differences between them are mainly concentrated in the LTR region, where the identity is only 71%, and InDels reach 15%, resulting in only 59% of overlap. Such difference results in poor LTR alignment of the 72 copies. Additionally, Subfamily 2 presents a 208 bp deletion in the UTL 5' (Untranslated Leader) region. The corrected distances (Tamura-3 parameters) within each subfamily are 0.123 and 0.138 respectively, for Subfamily 1 and 2, and 0.222 between subfamilies (overall mean of 0.174). The divergence between the two LTRs of each copy was calculated and an insertion time was inferred. Subfamily 1 showed a mean time of insertion of 2.97 ± 0.204 Mya (minimum: 0.5, maximum: 5.2 Mya) and Subfamily 2 showed a mean time of insertion of 4.53 ± 0.399 Mya (minimum: 1.3, maximum 10.1 Mya) (Fig. 2, Table S8).

Presence of Copia25 in the Rubiaceae family

In order to investigate the evolution of Copia25, sequence similarity searches and PCR amplifications were used to search for its presence in the Coffea genus and in other Rubiaceae species. First, 11 genotypes representing 10 Coffea species (including ex-Psilanthus) and Craterispermum sp. Novo kribi were surveyed using high-throughput 454 Roche sequencing.

The number of bases produced for each species and the estimated genome coverage according the genome sizes are shown in the Table 2. The 454 sequences were used to survey the presence of highly conserved Copia25 sequences, using as criteria: 90% minimal nucleotide identity over 80% of the sequence length. The number of Copia25 conserved sequences found for each species and their respective cumulative length according to the genome size are available in the Table 2. Sequences fitting these criteria were present in all Coffea genomes studied here, but not in Craterispermum. The cumulative length of Copia25 reads was estimated to range from 186 to 1,513 kb of estimated cumulative sequences in diploid species and 842 kb in the allotetraploid C. arabica (Table 2).

The presence of Copia25 was also investigated by PCR amplification and sequencing of the product in 13 Coffea and 11 other Rubiaceae species (Table S3, Fig. S1). The Copia25 RT region was amplified and sequenced in 13 Coffea species, three from West Africa (C. S9).

Copia25 distribution among monocots and dicots

Besides the Rubiaceae species, similar Copia25 sequences were sought among the 40 available plant sequences representing the angiosperm clades, and one non-angiosperm species using BLASTN. Similar Copia25 sequences were found in 34 species but not in the remaining eight ones, as follows: Arabidopsis lyrata, Carica papaya, Cucumis sativus, Fragaria vesca, Linum usitatissimum, Selaginella moellendorffii, Phoenix dactylifera and Zea mays (Table S1).

In the 34 genomes where sequences similar to Copia25 were found, these latter were extracted for further phylogenetic analysis. Using a fragment of 750 bp from the RT region, a phylogeny was reconstructed using Maximum Likelihood, with the distance corrected by Tamura 3-parameter and 1000 replicates in order to investigate the relationships among the Copia25 sequences (Fig. 3, Fig. S6 and Tables S10 andS11). One well-supported (95% bootstrap value) phylogenetic clade was found to include C. canephora Copia25 and sequences belonging to four dicotyledonous species: Nicotiana benthamiana, N. tabacum, S. tuberosum (Solanaceae) and Ricinus communis (Euphorbiaceae), and more surprisingly, three monocotyledonous species, Musa accuminata and M. balbisiana (Musaceae), and, in a basal position, Eleais guineensis (Arecaceae). These sequences were considered homologous to Copia25 because they share over 80% sequence identity over 80% of their length in the reverse transcriptase domain (Wicker et al. 2007), except for R. communis and E. guinensis.

Since these two species cluster within the clade and share, with Copia25, over 70% of identity they were considered to belong to the same family.

Besides the Copia25 clade, additional Ty1-Copia sequences related to it, clustered in strongly-supported clades composed of species of the same family, which supports a hypothesis of vertical inheritance (Fig. 3). It is the case of the elements found in the monocotyledonous family of Poaceae where all of them cluster in a clade with a 94% bootstrap value. A similar occurrence was found in the Malvaceae species (100%) and in Fabaceae (98%) species, but it is also weakly supported among Brassicaceae (79%). The exceptions in this context are the particular strongly-supported relationships between Medicago truncatula (Fabaceae) and Mimulus guttatus (Phrymaceae) (94%), among Populus trichocarpa (Salicaceae), Gossypium hirsutum (Malvaceae) and Malus domestica (Rosaceae) (100%), and finally between Solanum lycopersicum (Solanaceae) and Arabidopsis thaliana (Brassicaceae) (100%).

The reconstructed phylogeny using only sequences recovered from public databases (Fig. 3) did not show a clear relationship between the sequences from coffee tree and those from other species in the clade. In an effort to better understand the relationships of Copia25 showed an overall nucleotide identity of 74.1% and 79.6% for Subfamily 1 and 2, respectively, and an overall amino acid sequence identity rate of 81.7% (similarity: 79.8%) with Subfamily 1, and 81.60% (similarity: 80.1%) with Subfamily 2 (Fig. 5a). Their LTRs were also extracted and aligned, showing a high identity rate (53.9% between Musa and the reference sequence of Subfamily 1; and 59.4% with the Subfamily 2 reference sequence) (Fig. 5b). This level of identity is indeed quite significant for non-coding regions and considering the species divergence, i.e. about 150 Mya [START_REF] Chaw | Dating the monocot-dicot divergence and the origin of core eudicots using whole chloroplast genomes[END_REF][START_REF] Wikstrom | Evolution of the angiosperms: calibrating the family tree[END_REF]).

Homologous sequences to Copia25-Musa from the M. balbisiana genome (B genome) were also found in the sequenced M. acuminata genome (A genome; D 'Hont et al. 2012). These homologous sequences show high sequence identity (e.g. Chr9: 16119963-16124880; 91.1% of identity) between the two banana genomes that diverged by about 4.6 Mya [START_REF] Lescot | Insights into the Musa genome: Syntenic relationships to rice and between Musa species[END_REF]).

Evolution of Copia25 in monocots and dicots

To investigate the evolution of Copia25 in detail, we used the nucleotide sequences of Copia25 from M. balbisiana, C. canephora, S. tuberosum and N. benthamiana for pairwise sequence comparisons. The results summarized in Supplementary Table S12 show higher identity between the Copia25 of coffee and banana than between all the other species. We compared the identity of Copia25 with the identities of seven COSII sequences showing the highest sequence identity between banana and coffee. These genes share an average of 74.7% of identity between banana and coffee, while the coding region of Copia25 shows 85%. For the Copia25 polyprotein and these seven COSII genes, we performed a pairwise Ka/Ks (nonsynonymous per synonymous substitution ratio) analysis by comparison of banana, potato, tobacco and coffee sequences. Both COSII and Copia25 were under purifying selection, however they were found more relaxed in Copia25 (minimum: 0.233, maximum: 0.287) than in COSII (minimum: 0.038, maximum: 0.215) sequences.

The LRT results reinforce the proposition of the purifying selection acting on the

Copia25 sequences (Table 3) The LRTs of the Ixora and Musa clades were estimated separately. For these, a two-ratio model was applied, since we assumed that the sequence group of interest has a different ωF from that of the ωB background (Model III: ω free, and Model IV: ω fixed, for Ixora clade; and Model V: ω free, and Model VI: ω fixed, for the Musa clade). Purifying selection was also detected for Ixora clade (0.127, 2 ℓ = 33.568, p < 0.01), while for the Musa clade the ω value did not differ from neutral evolution (Table 3). The negative selective pressure would explain the narrow relationship between the coffee and banana sequences. However, the negative selection for Copia25 and COS, and the neutrality for Copia25 in Musa clade indicate that this alone does not explain their clustering in the phylogeny.

The divergence time of two sequences harbored by two species from their common ancestral sequence was estimated by using both COSII and Copia25. The estimated divergence time using Copia25 sequences for Musa and Coffea is much lower than for COSII sequences. While the latter ones ranged from 94.5 to 181.8 Mya, when using Copia25 the time was 35.5 and 31.7 Mya. Indeed, the estimated divergence time using the Copia25 from banana and the Solanaceae species is similar to that found for coffee, tobacco and potato. The high similarity and the Ks values for the comparisons between coffee and banana with the other Solanaceae species indicate that the Copia25 sequence could be a recent guest in banana species genome.

Discussion

Copia25 in the Rubiaceae family

In this study, we identified an expressed Ty1-Copia in the C. canephora genome,

Copia25, and analyzed it under various aspects, providing a broad insight into its evolution.

Copia25 was found distributed in several species of the Coffea genus from Africa, the Indian Ocean Islands and Indonesia. The occurrence of Copia25 in these species denotes that it could be present in the ancestor of this phylogenetic group and has been inherited by the derived [START_REF] Chaw | Dating the monocot-dicot divergence and the origin of core eudicots using whole chloroplast genomes[END_REF][START_REF] Wikstrom | Evolution of the angiosperms: calibrating the family tree[END_REF]). This discontinuous and incongruent distribution in dicots and monocots highlights a complex evolutionary history of Copia25 in plants that could be traced back to the origin of angiosperms.

Copia25-Coffea clusters in a strongly supported clade (100% bootstrap value) with homologous sequences from three Solanaceae species, S. tuberosum, N. tabacum and N. benthamiana, and Musaceae species, Musa spp.. However, the nucleotide identity between

Copia25-Coffea and Copia25-Musa is higher than the one observed between Coffea and potato and tobacco, and even in the comparison between Musa and Solanaceae (S. tuberosum: 77.4%; N. benthamiana: 77.2%). When the seven orthologous (COSII) genes showing the highest sequence conservation are compared among the same species, the nucleotide identity between C. canephora and M. balbisiana ranged from 67.8% to 80.2%, less than the Copia25 polyprotein identity for the same species comparison (Subfamily 1: 84.5% and Subfamily 2: 85.5%). Equivalent identities were also found in the gag region. Such outstandingly high conservation raises questions about the molecular mechanisms, which are at its origin.

Conservation of TEs between distantly related genera could be the result of different and non-exclusive processes [START_REF] Capy | The strange phylogenies of transposable elements: are horizontal transfers the only explantation?[END_REF][START_REF] Cummings | Transmission patterns of eukaryotic transposable elements: arguments for and against horizontal transfer[END_REF][START_REF] Schaack | Promiscuous DNA: horizontal transfer of transposable elements and why it matters for eukaryotic evolution[END_REF][START_REF] Wallau | The evolutionary history of mariner-like elements in Neotropical drosophilids[END_REF]) such as: (i) domestication, (ii) conservation of functional sites, (iii) similarity of evolutionary rates, (iv) purifying selection and (v) horizontal transfer. The first two scenarios cannot explain the conservation of Copia25 across genera, since only portions of the TE are generally domesticated and because the mechanisms of conserving functional sites exclusively involve coding regions. High sequence identity was found for the full-length sequences of Copia25, including non-coding LTR regions. Similar TE evolutionary rate in distinct species is an attractive hypothesis to explain the conservation observed in Copia25.

However, the TE evolutionary rate depends on multiple parameters such as the specific TE activity and the efficiency of TE host control mechanisms. Such a scenario remains unlikely since these evolutionary mechanisms should be identical in several distantly-related species.

The fourth process, a purifying selection, would explain the high identity of a given TE between distantly related species. The Ka/Ks ratio estimated for pairwise comparisons of Copia25 between Musa and Coffea sequences is low (< 0.3), denoting purifying selection and explaining the conservation and the activity (at least until very recently) of this particular element. However, the Ks values between Coffea and Solanaceae, Musa and Solanaceae and Musa and Coffea species are at least twice as low for Copia25 as for COSII sequences. This observation suggests that other evolutionary processes besides purifying selection might be involved in Copia25 conservation. Finally, HTs of TEs, an occurrence suggested but rarely confirmed in plants [START_REF] Diao | Horizontal transfer of a plant transposon[END_REF][START_REF] Baidouri | Widespread and frequent horizontal transfers of transposable elements in plants[END_REF][START_REF] Fortune | Horizontal transfer of transposable elements in plants[END_REF]) may explain the strong conservation level in coding and non-coding regions, and the sparse distribution of TEs. However, HT scenarios first require ecological, chronological, and geographical distribution overlapping between the species involved in the potential transfer to be seriously considered. These requirements are not expected for Musa and Coffea, but a chronological and geographical distribution overlap might have existed for the Musa and Ixora species. The Ixora genus belongs to the Ixoroideae subfamily of the Rubiaceae family such as the Coffea genus, but both belong to different tribes, Ixoreae and Coffeeae (Fig. S1).

The genus Musa evolved and diversified in tropical Asia [START_REF] Liu | Phylogenetic analyses of the banana family (Musaceae) based on nuclear ribosomal (ITS) and chloroplast (trnL-F) evidence[END_REF], and the Musa lineage ancestor originated ~50 Mya [START_REF] Christelova | A multi gene sequence-based phylogeny of the Musaceae (banana) family[END_REF]). Likewise, the Ixora genus originated in South-East Asia, in Borneo in particular [START_REF] Lorence | Revision of Ixora (Rubiaceae) in the Marquesas Islands (French Polynesia)[END_REF]), and its ancestral lineage originated 30 to 50 Mya [START_REF] Tosh | Evolutionary history of the Afro-Madagascan Ixora species (Rubiaceae): species diversification and distribution of key morphological traits inferred from dated molecular phylogenetic trees[END_REF]). Therefore, the ancestors of Musa and Ixora could have shared the same period and geographical origin. The hypothesis of the HT of Copia25 between the ancestors of Ixora and Musa is therefore supported by the chronological and geographical distribution of species. This hypothesis is also supported by the high global sequence identity as well as by the Ks values, which are much lower for Copia25 than for the COSII, suggesting that its presence is recent in the Musa genome. Furthermore, the phylogeny of Copia25 RT including the Musa and Rubiaceae species sequences clearly indicates a strong relationship between Copia25-Musa and Copia25-Ixora (Fig. 4). This relationship does not result from similar selective pressure acting in both groups (as showed by LRT analyses, which exclude purifying selection as the process responsible for sequence similarity) and thus reinforces the proposition of HT. The putative period of Copia25 transfer from Ixora to Musa can be estimated by the molecular clock equation using the RT sequences (375 nt; Ks ranged from 0.25 to 0.56). The estimated age range from 19 to 43 Mya is congruent with the period when the ancestors of both genera shared geographical distribution. This estimation must be considered with caution because of the short sequence used for establishing the time of divergence and because the molecular clock used is not calibrated for Rubiaceae. Our results thus suggest a potential and ancestral HT of Copia25 from Ixora to Musa (Fig. S8).

With the facility for plants to inter-cross and given the autonomy of their germ line, plant genomes have a natural propensity to transfer genetic material. They also have a high content of LTR-RTs, elements whose cytoplasmic multiplication phase heightens the likelihood of being captured and exchanged among other species, thus favoring potential HT.

Thanks to the fast-growing number of data sequences available, more studies are being conducted involving several species. Their results reveal scenarios of complex evolution, particularly those concerning TEs. Here, our detailed analyses of Copia25 in angiosperms disclose the complexity of the evolutionary dynamics of this ancient element, involving several processes including sequence conservation, rapid turnover, stochastic losses and horizontal transfer. Additional information on the presence and the activity of Copia25 in angiosperms is required to precisely identify the mechanism involved in such remarkable conservation of a transposable element harbored by large and divergent groups of plant species. The insertion time was estimated using the Kimura 2-parameter between both LTRs of the same copy and the following molecular clock equation with r = 1.3 x 10 -8 [START_REF] Ma | Rapid recent growth and divergence of rice nuclear genomes[END_REF]. Fig. 3 Phylogeny of the RT domain from sequences similar to the Copia25 elements in the 29 plant genomes analyzed. The phylogeny was reconstructed using Maximum Likelihood, with the distance corrected by Tamura 3-parameter, and 1000 replicates; the bootstrap consensus tree inferred is taken to represent the evolutionary history of the taxa analyzed. All positions containing gaps and missing data were eliminated. There were a total of 602 nucleotide sites in the final dataset; and a total of 98 nucleotide sequences. A discrete Gamma distribution was used to model evolutionary rate differences among sites (2 categories (+G, parameter = 1.7864)). The rate variation model allowed for some sites to be evolutionarily invariable ([+I], 10.1863% sites). The highlighted clade corresponds to the Copia25 family; in blue, the monocot species in Copia25 clade; the number in parentheses is the number of sequences collapsed in the tree. Species abbreviation: S. tuberosum Solanum tuberosum (potato), N. tabacum: Nicotamia tabacum (tobacco), N. benthamiana The phylogeny was reconstructed using Maximum Likelihood, with the distance corrected by Tamura 3-parameter, and 1000 replicates; the tree with the highest log likelihood (-4739.5265) is shown. A discrete Gamma distribution was used to model evolutionary rate differences among sites (2 categories (+G, parameter = 1.1187)). The tree is drawn to scale, with branch lengths measured by number of substitutions per site. All positions containing gaps and missing data were eliminated. There were a total of 313 positions in the final dataset; and a total of 69 nucleotide sequences. Only the bootstrap values over 50% are shown. In green, the clade corresponding to the cluster between Copia25 Musa and Ixora sequences; in blue, the monocot species. The number of collapsed sequences is indicated in parentheses. Species abbreviation: S. tuberosum Solanum tuberosum (potato), N. tabacum: Nicotamia tabacum (tobacco), N. benthamiana Nicotamia benthamiana, R. communis; Ricinus communis (castor oil)

Figure legends

(

  HD200-94 a double haploid from the Congolese diversity group, also used for whole genome sequencing -Denoeud et al. 2014, http://coffee-genome.org -, and BUD15 from Uganda), as well as in one accession from each of the following taxa: C. arabica L. (ET39 from Ethiopia), C. eugenioides S. Moore (DA56 from Kenya), C. pseudozanguebariae Bridson (08107 from Kenya), C. heterocalyx Stoff (JC65 from Cameroon), C. racemosa Lour (IA56 from Mozambique), C. humblotiana Baill (A.230 from Comoros), C. millotii J.-F. Leroy (exdolichophylla, A.206 from Madagascar) and C. tetragona Jum. & H. Perrier (A.252 from Madagascar), Coffea (ex-Psilanthus) horsfieldiana (Miq.) J.-F. Leroy (HOR from Indonesia)

  stenophylla, C. humilis and C. ebracteolatus), one from West/Central Africa (C. canephora), three from East Africa (C. costatifructa, C. pseudozanguebariae and C. eugenioides), one from Northeast Africa (C. arabica), and five from Indian Ocean Islands (C. millotiiexdolichophylla -, C. perrieri, C. resinosa, C. tetragona and C. vianneyi) (Chevalier 1946; Maurin et al. 2007). The same region was also amplified and sequenced in 11 other Rubiaceae species: Bertiera iturensis, Tricalysia congesta, Oxyanthus formosus, Ixora sp., I. coccínea, I. finlaysoniana, I. foliicalyx, Polysphaeria parvifolia, Coptosperma sp., Pyrostria sp., and Craterispermum schwenfurthii. The final dataset contains 319 nucleotides, and the nucleotide identity varied from 62% to 100% among different sequences comparisons (Table

  among the species present in the Copia25 clade, we reconstructed a new Maximum Likelihood phylogeny (with the distance corrected by Tamura 3-parameter and 1000 replicates), adding RT sequences obtained from several Rubiaceae species and three Musaceae species (M. accuminata, M. balbisiana and M. boman) (Fig. 4 and Fig. S7). As shown in Fig. 4, the unrooted phylogenetic tree revealed that Copia25-Musa is nested into the Rubiaceae species as shown by a closer well-supported relationship (bootstrap value 92%) between Copia25-Musa and Copia25-Ixora and between Craterispermum sp. and all Rubiaceae and Musaceae species (bootstrap value 65%). Rubiaceae and Musaceae Copia25 are clearly separated from Solanaceae by high bootstrap value (92) and a topology structure. This result suggested that Rubiaceae and Musaceae Copia25 constitute a unique evolutionary lineage (Fig. 4). To further confirm the close relationship between Copia25-Coffea and Copia25-Musa, we first aligned each Copia25-Coffea sequence (Copia25 C. canephora reference sequence of Subfamily 1 and 2) with the Copia25-Musa (M. balbisiana AC186755). The alignments

  . The log likelihood values using a one-ratio model (Model I: ω free, and Model II: ω fixed) for the entire phylogenetic tree (Fig S2) were significantly lower than the neutral expectation, indicating purifying selection (0.191, 2 ℓ = 239.308, p < 0.01).

  lineages. Our proposition of its presence in the Coffea lineage ancestor is reinforced by the occurrence of Copia25 in at least two of the three subfamilies of the Rubiaceae family, Rubioideae (Craterispermum schwenfurthii) and Ixoroideae (Coffea spp., Ixora spp., Bertiera iturensis, Coptosperma sp., Oxyanthus formosus, Polysphaeria parvifolia, Pyrostria sp., Tricalysia cloneongesta), also suggesting its ancient evolutionary history in Rubiaceae. Altogether these data suggest the presence of Copia25 in both of the Rubiaceae subfamilies preceding their ancient divergence. High sequence identity of Copia25 of over 150 My of plant genome evolution Our similarity searches and molecular biology approaches revealed patchy conservation of Copia25. They show high sequence identity between a monocot genus of the Musaceae family and two different dicotyledonous families in Asteridae: the Rubiaceae and Solanaceae families. While monocot and dicot species diverged about 150 Mya, the Asteridae and Rosidae lineages diverged ~114 Mya. More recently, Rubiaceae and Solanaceae diverged from their common ancestor about 83 Mya

Fig. 1

 1 Figure legendsFig. 1 Distribution and phylogenetic relationship of the copies of Copia25 identified in the C. canephora genome. a Distribution of full-length copies (black lines) and fragmented copies of Copia25 (red dashes) along the 11 C. canephora pseudo-molecules. The gene density along pseudo-molecules is represented in grey while the LTR retrotransposons are represented in red in a separate layer. Fragmented copies are defined as a minimum of 90% nucleotide conservation and 10 to 80% coverage of full-length copies. b Phylogeny reconstructed using the pol of the full-length copies of Copia25. The phylogeny was reconstructed using Neighbor joining, with the distance corrected by General Time Reversible model, and 1000 replicates. All positions containing gaps and missing data were eliminated. There were a total of 2,640 nucleotides in the final dataset. Only the bootstrap values over 70 are shown. Represented in blue are the sequences of Subfamily 1, and in red, Subfamily 2. Fig. 2 Estimation of the insertion time distribution (in millions of years) of the 72 full-length Copia25 (Subfamily 1 and 2) copies identified in the C. canephora genome.The insertion time was estimated using the Kimura 2-parameter between both LTRs of the same copy and the following molecular clock equation with r = 1.3 x 10 -8[START_REF] Ma | Rapid recent growth and divergence of rice nuclear genomes[END_REF]. Fig.3Phylogeny of the RT domain from sequences similar to the Copia25 elements in the 29 plant genomes analyzed. The phylogeny was reconstructed using Maximum Likelihood, with the distance corrected by Tamura 3-parameter, and 1000 replicates; the bootstrap consensus tree inferred is taken to represent the evolutionary history of the taxa analyzed. All positions containing gaps and missing data were eliminated. There were a total of 602 nucleotide sites in the final dataset; and a total of 98 nucleotide sequences. A discrete Gamma distribution was used to model evolutionary rate differences among sites (2 categories (+G, parameter = 1.7864)). The rate variation model allowed for some sites to be evolutionarily invariable ([+I], 10.1863% sites). The highlighted clade corresponds to the Copia25 family; in blue, the monocot species in Copia25 clade; the number in parentheses is the number of sequences collapsed in the tree. Species abbreviation: S. tuberosum Solanum tuberosum (potato), N. tabacum: Nicotamia tabacum (tobacco), N. benthamiana: Nicotamia benthamiana, C. canephora: Coffea canephora (coffee), R. communis; Ricinus communis (castor oil), E. guineensis: Elaeis guineensis (African oil palm), S. italica: Setaria italica (Foxtail millet), S. bicolor: Sorghum bicolor (sorghum), O. sativa: Oryza sativa (rice), T. aestivum: Triticum aestivum (wheat), H. vulgare: Hordeum vulgare (barley),B. distachyon: Brachypodium distachyon, V. vinifera: Vitis vinifera (grape), Gossypium (cotton),A. trichopoda: Amborella trichopoda, G. max: Glycine max (soybean), P. vulgaris: Phaseolus vulgaris (common bean), C. cajan: Cajanus cajan (pigeon pea), L. japonicus: Lotus japonicus, M. truncatula: Medicago truncatula, E. grandis: Eucalyptus grandis, T. cacao: Theobroma cacao, F. ananasa: Fragaria x ananasa (strawberry), P. trichocarpa: Populus trichocarpa, G. hirsutum: Gossypium hirsutum, M. domestica: Malus domestica (apple), A. thaliana: Arabidopsis thaliana, S. lycopersicum: Solanum lycopersicum (tomato), M. guttatus: Mimulus guttatus, C. sinensis: Clementina sinensis, B. rapa: Brassica rapa.

Fig. 4

 4 Fig. 4 Phylogenetic analysis ofCopia25 RT domain homologs. The phylogeny was reconstructed using Maximum Likelihood, with the distance corrected by Tamura 3-parameter, and 1000 replicates; the tree with the highest log likelihood(-4739.5265) is shown. A discrete Gamma distribution was used to model evolutionary rate differences among sites (2 categories (+G, parameter = 1.1187)). The tree is drawn to scale, with branch lengths measured by number of substitutions per site. All positions containing gaps and missing data were eliminated. There were a total of 313 positions in the final dataset; and a total of 69 nucleotide sequences. Only the bootstrap values over 50% are shown. In green, the clade corresponding to the cluster between Copia25 Musa and Ixora sequences; in blue, the monocot species. The number of collapsed sequences is indicated in parentheses. Species abbreviation: S. tuberosum Solanum tuberosum (potato), N. tabacum: Nicotamia tabacum (tobacco), N. benthamiana Nicotamia benthamiana, R. communis; Ricinus communis (castor oil), E. guineensis: Elaeis guineensis (African oil palm) and C. means Coffea. Fig. 5 Comparison between Copia25 and Copia25-Musa. a/b Dot plot alignment between the full-length copy of Copia25 (reference sequences, Subfamilies 1 (a) and 2 (b)) and the Copia25-Musa found in a genomic segment of the Musa balbisiana BAC clone (horizontal axis; AC186755 100804-105774). c Nucleotide alignment of 5' LTR of Copia25 Subfamily 2 and Copia25-Musa.

Fig. 5

 5 Fig. 4 Phylogenetic analysis ofCopia25 RT domain homologs. The phylogeny was reconstructed using Maximum Likelihood, with the distance corrected by Tamura 3-parameter, and 1000 replicates; the tree with the highest log likelihood(-4739.5265) is shown. A discrete Gamma distribution was used to model evolutionary rate differences among sites (2 categories (+G, parameter = 1.1187)). The tree is drawn to scale, with branch lengths measured by number of substitutions per site. All positions containing gaps and missing data were eliminated. There were a total of 313 positions in the final dataset; and a total of 69 nucleotide sequences. Only the bootstrap values over 50% are shown. In green, the clade corresponding to the cluster between Copia25 Musa and Ixora sequences; in blue, the monocot species. The number of collapsed sequences is indicated in parentheses. Species abbreviation: S. tuberosum Solanum tuberosum (potato), N. tabacum: Nicotamia tabacum (tobacco), N. benthamiana Nicotamia benthamiana, R. communis; Ricinus communis (castor oil), E. guineensis: Elaeis guineensis (African oil palm) and C. means Coffea. Fig. 5 Comparison between Copia25 and Copia25-Musa. a/b Dot plot alignment between the full-length copy of Copia25 (reference sequences, Subfamilies 1 (a) and 2 (b)) and the Copia25-Musa found in a genomic segment of the Musa balbisiana BAC clone (horizontal axis; AC186755 100804-105774). c Nucleotide alignment of 5' LTR of Copia25 Subfamily 2 and Copia25-Musa.

  of the Copia25 copy number in Coffea genomes using 454 sequencing survey. Only 454 reads with a minimum of 90% of nucleotide identity and over 80% of the read length were considered. value estimates from other ex-Psilanthus accessions in absence of clear data for C. horsfieldiana.

Fig. 1

 1 Fig. 1 Distribution and phylogenetic relationship of the copies of Copia25 identified in the C. canephora genome. a Distribution of full-length copies (black lines) and fragmented copies of Copia25 (red dashes) along the 11 C. canephora pseudomolecules. The gene density along pseudo-molecules is represented in grey while the LTR retrotransposons are represented in red in a separate layer. Fragmented copies are defined as a minimum of 90% nucleotide conservation and 10 to 80% coverage of fulllength copies. b Phylogeny reconstructed using the pol of the full-length copies of Copia25. The phylogeny was reconstructed using Neighbor joining, with the distance corrected by General Time Reversible model, and 1000 replicates. All positions containing gaps and missing data were eliminated. There were a total of 2,640 nucleotides in the final dataset. Only the bootstrap values over 70 are shown. Represented in blue are the sequences of Subfamily 1, and in red, Subfamily 2.

Fig. 2

 2 Fig. 2 Estimation of the insertion time distribution (in millions of years) of the 72 full-length Copia25 (Subfamily 1 and 2) copies identified in the C. canephora genome. The insertion time was estimated using the Kimura 2-parameter between both LTRs of the same copy and the following molecular clock equation with r = 1.3 x 10 -8 (Ma and Bennetzen 2004).

Fig. 3

 3 Fig.3Phylogeny of the RT domain from sequences similar to the Copia25 elements in the 29 plant genomes analyzed. The phylogeny was reconstructed using Maximum Likelihood, with the distance corrected by Tamura 3-parameter, and 1000 replicates; the bootstrap consensus tree inferred is taken to represent the evolutionary history of the taxa analyzed. All positions containing gaps and missing data were eliminated. There were a total of 602 nucleotide sites in the final dataset; and a total of 98 nucleotide sequences. A discrete Gamma distribution was used to model evolutionary rate differences among sites (2 categories (+G, parameter = 1.7864)). The rate variation model allowed for some sites to be evolutionarily invariable ([+I], 10.1863% sites). The highlighted clade corresponds to the Copia25 family; in blue, the monocot species in Copia25 clade; the number in parentheses is the number of sequences collapsed in the

Fig. 4

 4 Fig. 4 Phylogenetic analysis ofCopia25 RT domain homologs. The phylogeny was reconstructed using Maximum Likelihood, with the distance corrected by Tamura 3parameter, and 1000 replicates; the tree with the highest log likelihood(-4739.5265) is shown. A discrete Gamma distribution was used to model evolutionary rate differences among sites (2 categories (+G, parameter = 1.1187)). The tree is drawn to scale, with branch lengths measured by number of substitutions per site. All positions containing gaps and missing data were eliminated. There were a total of 313 positions in the final dataset; and a total of 69 nucleotide sequences. Only the bootstrap values over 50% are shown. In green, the clade corresponding to the cluster between Copia25 Musa and Ixora sequences; in blue, the monocot species. The number of collapsed sequences is

Fig. 5

 5 Fig. 5 Comparison between Copia25 and Copia25-Musa. Dot plot alignment between the full-length copy of Copia25 (reference sequences, a Subfamilies 1 and b 2) and the Copia25-Musa found in a genomic segment of the Musa balbisiana BAC clone (horizontal axis; AC186755 100804-105774). c Nucleotide alignment of 5' LTR of Copia25 Subfamily 2 and Copia25-Musa.

  value estimates from other ex-Psilanthus accessions in absence of clear data for C. horsfieldiana.

  communis -Euphorbiaceae (Rosidae -dicot) E. gui neensi s -Arecaceae (Areci dae -m onocot) Click here to download Colour figure: Fig4-5_Rub-Gen.eps

  : Nicotamia benthamiana, C. canephora: Coffea canephora (coffee), R. communis; Ricinus communis (castor oil), E. guineensis: Elaeis guineensis (African oil palm), S. italica: Setaria italica (Foxtail millet), S. bicolor: Sorghum bicolor (sorghum), O. sativa: Oryza sativa (rice), T. aestivum: Triticum aestivum (wheat), H. vulgare: Hordeum vulgare (barley), B. distachyon: Brachypodium distachyon, V. vinifera: Vitis vinifera (grape), Gossypium (cotton), A. trichopoda: Amborella trichopoda, G. max: Glycine max (soybean), P. vulgaris: Phaseolus vulgaris (common bean), C. cajan: Cajanus cajan (pigeon pea), L. japonicus: Lotus japonicus, M. truncatula: Medicago truncatula, E. grandis: Eucalyptus grandis, T. cacao: Theobroma cacao, F. ananasa: Fragaria x ananasa (strawberry), P. trichocarpa: Populus trichocarpa, G. hirsutum: Gossypium hirsutum, M. domestica: Malus domestica (apple), A. thaliana: Arabidopsis thaliana, S. lycopersicum: Solanum lycopersicum (tomato), M. guttatus: Mimulus guttatus, C. sinensis: Clementina sinensis, B. rapa: Brassica rapa.

  , E. guineensis: Elaeis guineensis (African oil palm) and C. means Coffea.

Table 1 Summary of the AAARF assembly.

 1 Only contigs larger than 3 Kb (52 over 317) and with a correct assembly structure (37 over 52) were analyzed.

Table 3 Likelihood ratio test for testing models of sequence evolution for Copia25 retrotransposons.

 3

	Model		Parameter	ℓ	2 ℓ	ωB	ωF	Conclusion
	One-ratio	Model I Model II	ω free ω = 1	-2469.160 -2588.814	239.308**	0.191 -	--	Purifying selection in the Copia25 tree
	Two-ratio Model III Model IV	ω free ω = 1	-2468.462 -2485.246	33.568**	0.198 0.198	0.127 1	Purifying selection in the Ixora Copia25 clade
		Model V Model VI	ω free ω = 1	-2463.734 -2464.998	2.526	0.169 0.168	0.552 1	Neutral evolution in the Musa Copia25 clade
	Critical values of X 2 , 1 df: *: 3.84; **: 6.63; 2 ℓ = 2 (l1-l0)

Table 1

 1 Summary of the AAARF assembly. Only contigs larger than 3 Kb (52 over 317) and with a correct assembly structure (37 over 52) were analyzed.

Table

  Click here to download Table:Tables.docx

Table 2 Estimation of the Copia25 copy number in Coffea genomes using 454 sequencing survey.

 2 Only 454 reads with a minimum of 90% of nucleotide identity and over 80% of the read length were considered.

Acknowledgments

This research was supported Agropolis Fondation through the "Investissement d'avenir" program (ANR-10-LABX-0001-01) under the reference ID 1002-009 and 1102-006, CAPES (Grants 01/2010 to CMAC and fellowship 9127-11-9 to ESD), Brazilian agencies FAPESP (Fundação de Amparo à Pesquisa do Estado de São Paulo -Grant 2013/15070-4 to CMAC and fellowship 2011/18226-0 to ESD) and CNPq (Conselho Nacional de Desenvolvimento Científico e Tecnológico -Grant 306493/2013-6 to CMAC) and French agency ANR (Agence Nationale de la Recherche; Genoplante ANR-08-GENM-022-001). Acknowledgments to Dr. A. D'Hont for providing Musa spp. DNA samples; Herman E. Taedoumg for providing Craterispermum samples; Dr. P. De Block for providing Rubiaceae samples; Dr. J-J. Rakotomalala for providing Mascarocoffea samples. Acknowledgements to Philippe Lashermes and the Coffee Genome Consortium for the availability of the C. canephora BACend sequences and draft genome.

Conflict of Interest

The authors declare that they have no competing interests.

Electronic supplementary material

The paper contains supplementary material, File 1.

Supplementary material

Click here to download Supplementary material: Final_PMB_SM.docx


Nestor V Nestoridis
email: nestornestoridis@yahoo.gr

Dimitrios M Thilikos

Square Roots of Minor Closed Graph Classes

Keywords: square roots of graphs, branch-width, carving-width, graph minors

Let G be a graph class. The square root of G contains all graphs whose square belong in G. We prove that if G is non-trivial and minor closed, then all graphs in its square root have carving-width bounded by some constant depending only on G. As a consequence, every square root of such a graph class has a linear time recognition algorithm.

Introduction

Let G be a graph class. The square root of G is defined as the graph class

√ G = {G | G 2 ∈ G},
where the square G 2 of a graph G is the graph obtained from G after adding edges between all pairs of vertices that share a common neighbor.

In [START_REF] Harary | A criterion for planarity of the square of a graph[END_REF], Harary, Karp, and Tutte provided a complete characterization of the graphs in √ P where P is the class of all planar graphs. Notice that planar graphs are minor closed, i.e. a minor of every graph in P also belongs in P.

According to the characterization of [START_REF] Harary | A criterion for planarity of the square of a graph[END_REF], all graphs in √ P are outerplanar and have bounded degree. This implies that graphs in √ P have a very specific "tree-like" structure and it is a natural question whether this is the case for more general graph classes. In this paper we extend this result, in the sense that the same tree-like property holds for every minor closed graph class that is non-trivial (i.e. that does not contain all graphs). In fact, we prove (in Section 3) that, in this case, the correct "tree-likeness" property if given by the parameter of carving-width, introduced by Seymour and Thomas in [START_REF] Seymour | Call routing and the ratcatcher[END_REF]. As a consequence, we prove in Section 4 that the square root of any non-trivial minor closed graph class has a linear time recognition algorithm. This extends the algorithmic results of [START_REF] Ling Lin | Algorithms for square roots of graphs[END_REF] where a linear time algorithm was given for recognizing the square roots of planar graphs.

Definitions

We next give some definitions that are necessary in order to formally define carving width. This will permit us to give the formal statement of our combinatorial result.

Boundaries in graphs and hypergraphs. In this paper we deal with graphs and hypergraphs. For a (hyper)graph G we denote by V (G) its vertex set and by E(G) the set of its (hyper)edges.

If S ⊆ V (G) (resp. F ⊆ E(G)) we denote S = V (G) \ S (resp. F = E(G) \ F ).
Given a vertex set S ⊆ V (G), we define by E G (S) as the set of hyperedges containing vertices in S. For simplicity we also denote

E G (v) = E G ({v}). We also define ∆(G) = max{|E G (v)| | v ∈ V (G)}. Given a set S ⊆ V (G), we define ∂ G (S) = E G (S) ∩ E G (S).
Notice that ∂ G is a symmetric function, i.e. for every S ⊆ V (G), ti holds that ∂ G (S) = ∂ G (S). Also given a set F ⊆ E(G), we set

∂ * G (F ) = ( f ∈F f ) ∩ ( f ∈F f )
Given a hypergraph G we define its dual as the hypergraph

G * = (E(G), {E G (v) | v ∈ V (G)}).
Notice that the hypergraphs G and G * have the same incidence graph with the roles of their two parts reversed. Given a set S ⊆ V (G) (resp. F ⊆ E(G)) we denote by S * (resp. F * ) their dual hyperedges (resp. vertices) in G * . Using duality, we also define ∆ * (G) = ∆(G * ). Clearly, for a simple graph G, ∆ * (G) = 2. Moreover, the above definitions imply that for every

F ⊆ E(G), (∂ * G (F )) * = ∂ G * (F * ).
A graph H is a minor of a graph G, and we write H ≤ G, if H can be obtained by some subgraph of G after contracting edges (the contracting an edge e = {x, y} is the operation that introduces removes x and y from G and introduces a new vertex v e that is made adjacent with all the neighbors of x and y in G, except from x and y). A graph class G is minor closed if every minor of a graph in G is also a graph in G.

Carving-width. Given a tree T we denote the set of its leaves by L(T ) and we call it ternary if all vertices in V (T ) \ L(T ) have degree 3. A carving decomposition of a hypergraph G is a pair (T, ρ), where T is a ternary tree and ρ is a bijection from V (G) to L(T ). The bridge function β : E(T ) → 2 E(G) of a carving decomposition maps every edge e of T to the set ∂ G (ρ -1 (L(T ))) where T is one of the two connected components of T \ e. The width of (T, ρ) is equal to max e∈E(T ) |β(e)| and the carving-width of G, cw(G), is the minimum width over all carving decompositions of G. The following observation is a direct consequence of the definitions.

Observation 1. For every hypergraph G, it holds that ∆(G) ≤ cw(G).

The main combinatorial result of this paper is the following. Theorem 1. For every non-trivial minor closed graph class G there is a constant c G such that all graphs is √ G have carving-width at most c G .

The proof of Theorem 1 uses the parameter of branch-width defined in [START_REF] Robertson | Graph minors. X. Obstructions to tree-decomposition[END_REF].

Branch-width.

A branch decomposition of a graph G is a pair (T, τ ), where T is a ternary tree and τ is a bijection from E(G) to L(T ). The boundary function ω : E(T ) → 2 V (G) of a branch decomposition maps every edge e of T to the set ∂ * G (ρ -1 (L(T ))) where T is one of the two connected components of T -{e}. The width of (T, τ ) is equal to max e∈E(T ) |ω(e)| and the branchwidth of G, bw(G), is the minimum width over all branch decompositions of G.

The following observation is a direct consequence of the duality between the functions ∂ G and ∂ * G .

Observation 2. For every hypergraph G it holds that bw(G) = cw(G * ).

Walls and squares

Walls. A wall of height k, k ≥ 1, is obtained from a ((k + 1) × (2k + 2))-grid with vertices (x, y), x ∈ {0, . . . , 2k + 1}, y ∈ {0, . . . , k}, after removing the "vertical" edges {(x, y), (x, y + 1)} for odd x + y.We denote such a wall by W k . A subdivided wall of height k is obtained by the wall W k with some edges of W k replaced by paths without common internal vertices. If, in such a subdivided wall, all edges have been subdivided at least once, then we say that it is properly subdivided.

The following result follows from the results in [START_REF] Robertson | Graph minors. V. Excluding a planar graph[END_REF] and [START_REF] Robertson | Graph minors. X. Obstructions to tree-decomposition[END_REF].

Proposition 1 ([6] and [7]

)). There is a function g : N → N such that every graph G with branchwidth at least g(k) contains the (k × k)-grid as a minor.

A direct consequence of Proposition 1 is the following.

Lemma 1. There exists a function f such that every graph G with branchwidth at least f (k) contains a properly subdivided wall of height k as a subgraph.

Proof. Let W k be the graph taken from a k-wall if we subdivide each edge once. Notice that W k is a subgraph of the ((4k + 3) × (4k + 3))-grid.

The lemma follows from Proposition 1 and the fact that minor relation and topological minor relation are identical when the host graph has maximum degree 3 (notice that ∆(W k ) ≤ 3).

Let H be a ((k + 1) × (2k + 2))-grid where k is a positive odd integer. Let also W k a spanning subgraph that is a k-wall as explained above. Let also G be a subdivision of W k where the non-subdivision vertices are denote as coordinates of H (we call these vertices original). In particular, we denote the vertex of H with coordinates i, j by a i,j (see Figure 1). For i ∈ {0, . . . , k-1} and j ∈ {0, . . . , 2k+1} where i+j is even, we denote by P (v) i,j the path that has replaced the edge {a i,j , a i+1,j } in W k and we call these paths vertical. For i ∈ {0, . . . , k} and j ∈ {0, . . . , 2k}, we denote by P (h) i,j the path that has replaced the edge {a i,j , a i,j+1 } and we call these paths horizontal We denote by L i , i ∈ {0, . . . , k} the path

P h i,0 ⊕ • • • ⊕ P h i,2k
, we direct it from a i,0 to a i,2k and we call it i-th line of G. We also define, for l ∈ {0, . . . , k}, the l-th meander of G as the path

M l = P (v) 0,2l ⊕ P (h) 1,2l ⊕ P (v) 1,2l+1 ⊕ P (h) 2,2l ⊕ P (v) 2,2l ⊕ . . . ⊕P (v) k-2,2l+1 ⊕ P (h) k-1,2l ⊕ P (v) k-1,2l .
Finally, for every original vertex a i,j where 0 ≤ j ≤ 2k (1 ≤ j ≤ 2k + 1), we define right G (a i,j ) (left G (a i,j )) as the vertex of the directed path L i that appears right after (before) a i,j . W k . A subdivided wall of height k is obtained by the wall W k with some edges of W k replaced by paths without common internal vertices. If, in such a subdivided wall, all edges have been subdivided at least once, then we say that it is properly subdivided.

dddd1

The following result follows from the results in [START_REF] Robertson | Graph minors. V. Excluding a planar graph[END_REF] and [START_REF] Robertson | Graph minors. X. Obstructions to tree-decomposition[END_REF].

Proposition 1 ([6] and [7]

)). There is a function g : N ! N such that every graph G with branchwidth at least g(k) contains the (k ⇥ k)-grid as a minor.

A direct consequence of Proposition 1 is the following.

Lemma 1. There exists a function f such that every graph G with branchwidth at least f (k) contains a properly subdivided wall of height k as a subgraph.

Proof. Let W 0 k be the graph taken from a k-wall if we subdivide each edge once. Notice that W 0 k is a subgraph of the ((4k + 3) ⇥ (4k + 3))-grid. The lemma follows from Proposition 1 and the fact that minor relation and topological minor relation are identical when the host graph has maximum degree 3 (notice that (W 0 k )  3). ⇤

5,11 , L2 and the 2-meander M2 are depicted in G. Notice that x = leftG(a 14,7 ) and y = right G (a 14,7 ).

We denote by K r the complete graph on r vertices. Also we use the notation K r,q for the complete bipartite graph with parts of size r and q. Lemma 2. Let k be a positive odd integer. If G is a properly subdivided wall of height k, then K k+2 ≤ G 2 .

Proof. For each i ∈ {0, . . . , k} we define the path P i of G 2 as follows: If L i = (x 0 , x 1 , . . . , x m ) is the i-th horizontal path of G, then Li = (x 0 , x 2 , x 4 , . . . , x m ) where m = m or m = m -1 depending on whether m is even or not. We set S = i∈{0,...,k} V ( Li ).

Our next step is to define the paths Q j of G 2 , l ∈ {0, . . . , k}. Let M l be the l-th meander of G. Following the definition of a meander, we denote

• P (v) i,2l = (y i,2l
1 , . . . , y i,2l w i,2l ), for even i ∈ {0, . . . , k -1} (assuming that y i,2l 1 = a i,2l and y i,2l w i,2l = a i+1,2l ),

• P (v) i,2l+1 = (y i,2l+1 1
, . . . , y i,2l+1 w i,2l+1 ), for odd i ∈ {0, . . . , k -2} (assuming that y i,2l+1 1 = a i,2l+1 and y i,2l+1 w i,2l+1 = a i+1,2l+1 ),

• P (h) i,2l = (z i,2l 1 , . . . , z i,2l m i,2l ), i ∈ {1, . . . , k -1} (assuming that z i,2l 1 = a i,2l
and z i,2l m i,2l = a i,2l+1 ).

We claim that for each i, l ∈ {0, . . . , k} there is an edge e i,l in G 2 with one endpoint in Li and the other in Ml . Indeed it is easy to see that one can take

e i,l = {a i,2l , left(a i,2l )} if (i, l) ∈ {(0, k), (k, k)} {a i,2l
, right(a i,2l )} otherwise Now we are ready to prove that G 2 contains K k+2 as a minor. For this, we first remove from G 2 all edges that are neither edges of paths in M ∪ L nor edges in E = {e i,l | (i, l) ∈ {0, . . . , k} 2 }. Then we contract all edges of the remaining graph except from those in E and we end up to a graph isomorhpic to K k+1,k+1 that, in turn, can be further contracted to K k+2 .

Extended carving-decompositions. Let us relax the definition of a carving decomposition in the case of graphs in the following way: let G be a graph, T be a ternary tree rooted on some, say r, of its leaves, and a surjection σ : L(T ) \ {r} → V (G). As T is rooted each edge of T can be seen as a directed edge pointing towards the root. Let f = (x, y) be such an edge and let T x and T y be the two connected components of T \f such that r ∈ V (T y ). Let also V x = σ(L(T x )) and V y = σ(L(T y )). We define the bridge set of f as

β(f ) = {{a, b} ∈ E(G) | a ∈ V x and b ∈ V y \ V x }.
We call each such pair (T, σ) an extended carving decomposition of G and we define its width as the maximum |β(f )| over all f ∈ E(T ).

Lemma 3. If G has an extended carving decomposition of width at most k, then it also has a carving decomposition of width at most k.

Proof. Let (T, σ) be such an extended carving decomposition. We apply on (T, σ) the following transformation until this is not possible any more: if for some v, in σ -1 (v) contains at least two vertices a and b then replace σ by σ \ {(a, v)} and replace T by the tree that is obtained if we remove a and then we dissolve the resulting vertex of degree 2. It is easy to see that each new pair (T, σ) has width at most k. Also when the above procedure finishes, σ -1 is a bijection from V (G) to L(T ) \ {r}. If now we remove r from T and dissolve the resulting vertex of degree 2, we have a branch decomposition (T , σ -1 ) of G with width at most k.

Lemma 4. For every graph G, cw(G) ≤ ∆(G) • bw(G).
Proof. We set δ = ∆(G). Let (T, τ ) be a branch decomposition of G with width at most k. We now define an extended carving decomposition (T , σ) of G as follows: Take T and for each v ∈ L(T ) we define two new vertices v 1 and v 2 and we make them adjacent to v. For each such v where τ -1 (v) = {z, w}, we set σ(v 1 ) = z and σ(v 2 ) = w. In the resulting tree we pick arbitrarily an edge, we subdivide it and we make the subdivision vertex adjacent with new vertex r. In the resulting graph T , r will be the root. Let f = (x, y) be an edge of T . We set

X = σ(L(T x )) \ σ(L(T y )), Y = σ(L(T y )) \ σ(L(T x )) and S = σ(L(T x )) ∩ σ(L(T y ))
. Notice that ω(f ), as defined by the branch decomposition (T, µ), is exactly the set S, therefore S is a separator of G and |S| ≤ k. We conclude that each edge in ω(f ) has one endpoint in S and the other in Y . As each vertex in S has degree ≤ ∆(G), we obtain that ω(f ) ≤ k • d. Therefore, (T , σ) is an extended branch decomposition of G with width ≤ k • d. The lemma now follows from Lemma 3.

We are now ready to prove the main result of this paper.

Proof of Theorem 1. As G is non-trivial class we choose a graph H ∈ G and we assume that H has h vertices. As G is minor closed, G excludes K h as a minor. Therefore if G ∈ √ G, then G 2 does not contain K h as a minor. From Lemma 1, G does not contain as a subgraph a properly subdivided wall of height ≥ h -2. From Lemma 1, bw(G) < f (h -2). Notice also that ∆(G) ≤ h -1. Then, from Lemma 4, cw(G) < (h -1) • f (h -2) and the Theorem follows if we set c G = (h -1) • f (h -2).

In the rest of this section we will also bound the branch-width of the squares of the graphs in G. This will be useful for the algorithmic consequences of our results in Section 4.

Lemma 5. For every graph G it holds that cw(G 2 ) ≤ 2•(cw(G)) 2 -cw(G).

Proof. Let (T, ρ) be a carving decomposition of G of width at most k. We will prove that (T, ρ) is a carving decomposition of G 2 of width at most 2k 2k. We use the notation β and β in order to distinguish the bridge sets for G and G 2 respectively. Let

f ∈ E(T ). As ∆(G) ≤ cw(G), it is enough to prove that β (f ) ≤ 2 • k • (∆(G) -1) + k.
To prove this, we first define S = ρ -1 (T ) where T is one of the connected components of T -{e}. We define L = S ∩ ( e∈β(f ) e) and R = S ∩ ( e∈β(f ) e). Finally, for each e = {x, y} ∈ β(f ) where x ∈ L and y ∈ R, we define the sets

Q R (e) = {{x, z} | z ∈ N G (y) ∩ S} Q L (e) = {{z, y} | z ∈ N G (x) ∩ S} We claim that each edge e = {v, u} ∈ β (f ) \ β(f ) belongs in Q R (e) ∪ Q L (e)
for some e ∈ β(f ). For this, suppose that e = {v, u} where v ∈ S and u ∈ S. As e is not an edge in G and there is a vertex z ∈ V (G) such that {v, z}, {z, u} ∈ E(G). If z ∈ S then {z, u} ∈ β(e) and therefore e ∈ Q L (e) for e = {z, u}. If z ∈ S then {v, z} ∈ β(e) and therefore e ∈ Q R (e) for e = {v, z}. In both cases, the claim holds.

Notice now that for each e = {x, y} ∈ β(f

), |Q R (e) ∪ Q L (e)| = |Q R (e)| + |Q L (e)|. As |Q R (e)| ≤ |N G (y)| -1 ≤ ∆(G) -1 and |Q L (e)| ≤ |N G (x)| -1 ≤ ∆(G) -1, we conclude that |Q R (e) ∪ Q L (e)| ≤ 2 • (∆(G) -1). Therefore |β (f ) \ β(f )| ≤ 2 • k • (∆(G) -1) and the claim follows. Lemma 6. Let G be a class that is minor closed and let G ∈ √ G. Then bw(G 2 ) ≤ 4 • c 2 G -2 • c G . Proof. Let G 2 be a graph in G. From Theorem 1, cw(G) ≤ c G and, from Lemma 5, cw(G 2 ) ≤ 2 • c 2 G -c G .
As G 2 is a graph, we have that ∆ * (G 2 ) = 2. This together with Observation 2 and Lemma 4, implies that bw

(G 2 ) ≤ 4 • c 2 G -2 • c G .

Linear time recognition of √ G

In this section we study the complexity of the following problem when G is a minor closed graph class.

Square Root of G

Instance: A graph G. Question: is G a member of √ G?
Before we deal with the above problem, we briefly expose some known facts on the recognition of minor closed graph classes. Let G be such a class. We denote by obs(G) the set of minor minimal graph that do not belong in G. Notice that any two graphs in obs(G) are incomparable with respect to the minor relation. In their Graph Minors series, Robertson and Seymour [START_REF] Robertson | Graph minors. XX. Wagner's conjecture[END_REF] proved that each such set is finite, and therefore the size of its graphs is bounded by some constant c G . Therefore, to check whether an input graph G is a member of some minor-closed G, it sufices to check whether some graph on obs(G) is a minor of G. If this is the case, return NO as answer, otherwise return YES. In the same series of papers, Robertson and Seymour proved that to check whether a fixed size graph H is a minor of an n-vertex graph G can be done in O(n 3 ) steps. Morever, when the input graph G has branchwidth at most k, this check can be done in time f (k) • n, that is linear in n (see e.g. [START_REF] Robertson | Graph minors. XIII. The disjoint paths problem[END_REF][START_REF] Adler | Faster parameterized algorithms for minor containment[END_REF][START_REF] Illya | Branch decompositions and minor containment[END_REF]). We use this fact to prove our main algorithmic result.

Theorem 2. For every non-trivial graph class G that is minor closed, there exists an algorithm deciding √ G in linear time.

Proof. Let c G be the constant of Theorem 1 and let G be an input graph to the problem of the recognition of √ G. If ∆(G) > c G , then, from Observation 1, cw(G) > c G and the answer to the problem is NO. Assuming that ∆(G) ≤ c G , the computation of G 2 can be done in linear time. From Lemma 6, if G ∈ √ G, then the branchwidth of G 2 is at most c G = 4•c 2 G -2•c G . We now check whether bw(G 2 ) ≤ c G , e.g. using the algorithm of [START_REF] Hans | Constructive linear time algorithms for branchwidth[END_REF]. If the answer is negative, then we safely return NO. Otherwise, it remains to check whether G ∈ G for a graph of bounded branchwidth and this can be done in linear time as commented above.

Figure 1 :

 1 Figure 1: A properly subdivided wall G of height 8. The big (resp. small) vertices are the original (subdivision) vertices. The paths P (v) 3,7 , P (h) 5,11 , L2 and the 2-meander M2 are depicted in G. Notice that x = leftG(a 14,7 ) and y = right G (a 14,7 ).

Figure 1 :

 1 Figure 1: A properly subdivided wall G of height 8. The big (resp. small) vertices are the original (subdivision) vertices. The paths P

For each even i ∈ {0, . . . , k -1}, we set P (v) i,2l = (ȳ i,2l 1 , y i,2l 2 , . . . , y i,2l w i,2l -1 , ȳi,2l w i,2l ) where ȳi,2l 1 =

and for each odd i ∈ {0, . . . , k -1}, we set

) where ȳi,2l+1

Observe that for each i ∈ {1, . . . , k -1} and l ∈ {0, . . . , k} the vertices in P

i,2l \ S induce a path in G 2 which we denote by P (h) i,2l . Notice, that for every odd i ∈ {1, . . . , k -2} it holds that

Also, for every even i ∈ {2, . . . , k -1} is also holds that

From ( 1)-( 4) we obtain that

is a path in G 2 for each l ∈ {0, . . . , k}.

As paths in M = { Ml | l ∈ {0, . . . , k}} avoid all vertices of S, we have that for each i, l ∈ {0, . . . , k} V ( Li )∩V ( Ml ) = ∅. Moreover, by construction, any two paths in M are vertex disjoint. Recall also that the same holds for the paths in L = { Li | i ∈ {0, . . . , k -1}}.