Frédéric Delsuc

Michael J Stanhope

Emmanuel J P Douzery
email: douzery@isem.univ-montp2.fr

MOLECULAR SYSTEMATICS OF ARMADILLOS (XENARTHRA, DASYPODIDAE): CONTRIBUTION OF MAXIMUM LIKELIHOOD AND BAYESIAN ANALYSES OF MITOCHONDRIAL AND NUCLEAR GENES

Keywords:

whether they are published or not. The documents may come

Molecular systematics of armadillos (Xenarthra, Dasypodidae): contribution of maximum likelihood and Bayesian analyses of mitochondrial and nuclear genes.

INTRODUCTION

The mammalian order Xenarthra (armadillos, anteaters and sloths) has long been of special interest in attempts at understanding mammalian phylogenetics [START_REF] Gregory | The orders of mammals[END_REF].

Primarily based on seemingly primitive features of the reproductive anatomy and physiology, this enigmatic placental group has been thought to represent the earliest offshoot of the placental tree [START_REF] Mckenna | Toward a phylogenetic classification of the Mammalia[END_REF][START_REF] Novacek | Mammalian phylogeny: Shaking the tree[END_REF][START_REF] Shoshani | Higher taxonomic relationships among extant mammals based on morphology, with selected comparisons of results from molecular data[END_REF]. Despite this longstanding interest, modern molecular systematic techniques have only recently been applied to the phylogeny of extant xenarthrans [START_REF] Van Dijk | The virtues of gaps: Xenarthran (Edentate) monophyly supported by a unique deletion in αa-crystallin[END_REF][START_REF] Delsuc | The evolution of armadillos, anteaters and sloths depicted by nuclear and mitochondrial phylogenies: Implications for the status of the enigmatic fossil Eurotamandua[END_REF][START_REF] Delsuc | Molecular phylogeny of living xenarthrans and the impact of character and taxon sampling on the placental tree rooting[END_REF]. Moreover, large scale molecular studies have shown that this undoubtedly monophyletic order, is the sole constituent of one of the four major placental clades [START_REF] Madsen | Parallel adaptative radiations in two major clades of placental mammals[END_REF]Murphy et al., 2001a).

Also, molecular surveys have emphasized Xenarthra's fundamental importance for understanding the origins of placental mammals, by showing that it is among the oldest placental groups with living representatives [START_REF] Madsen | Parallel adaptative radiations in two major clades of placental mammals[END_REF]Murphy et al., 2001a,b;[START_REF] Delsuc | Molecular phylogeny of living xenarthrans and the impact of character and taxon sampling on the placental tree rooting[END_REF]. This order has its origins in South America where it experienced a radiation that gave birth to a prodigious diversity of fossil forms during the Tertiary [START_REF] Patterson | The fossil mammal fauna of South-America[END_REF][START_REF] Mckenna | Classification of mammals above the species level[END_REF]. Thirty contemporaneous xenarthran species represent the vestiges from this past diversity. Almost confined to the Neotropics, their diversity is composed of 21 armadillo, four anteater, and five sloth species [START_REF] Wetzel | Systematics, distribution, ecology, and conservation of South American Edentates[END_REF][START_REF] Vizcaíno | Identificación específica de las "mulitas", género Dasypus (Mammalia, Dasypodidae), del noroeste argentino. Descripción de una nueva espécie[END_REF].

Both morphological [START_REF] Engelmann | The phylogeny of the Xenarthra[END_REF][START_REF] Patterson | The ear region in xenarthrans (= Edentata, Mammalia). Part I. Cingulates[END_REF][START_REF] Patterson | The ear region in xenarthrans (= Edentata, Mammalia). Part II. Sloths, anteaters, palaeanodonts, and a miscellany[END_REF] and molecular [START_REF] Van Dijk | The virtues of gaps: Xenarthran (Edentate) monophyly supported by a unique deletion in αa-crystallin[END_REF][START_REF] Delsuc | The evolution of armadillos, anteaters and sloths depicted by nuclear and mitochondrial phylogenies: Implications for the status of the enigmatic fossil Eurotamandua[END_REF][START_REF] Delsuc | Molecular phylogeny of living xenarthrans and the impact of character and taxon sampling on the placental tree rooting[END_REF][START_REF] Madsen | Parallel adaptative radiations in two major clades of placental mammals[END_REF]Murphy et al., 2001a,b) studies unambiguously support the division of Xenarthra into the suborders Cingulata, i.e., armadillos (Dasypoda: Dasypodidae) and Pilosa, i.e., anteaters (Vermilingua: Myrmecophagidae) plus sloths (Folivora: Megalonychidae and Bradypodidae). The phylogenetic relationships and taxonomy of living pilosans are well understood. The two modern tree-sloth's genera Bradypus (three-toed sloths) and Choloepus (two-toed sloths) are classified in the two distinct families Bradypodidae and Megalonychidae, respectively, reflecting their numerous morphological differences and a possible diphyletic origin from two separate fossil groups [START_REF] Webb | The interrelationships of tree sloths and ground sloths[END_REF][START_REF] Höss | Molecular phylogeny of the extinct ground sloth Mylodon darwinii[END_REF][START_REF] Greenwood | A molecular phylogeny of two extinct sloths[END_REF]. Regarding anteaters, the giant anteater (Myrmecophaga tridactyla) and the tamanduas (Tamandua) are classically associated to the exclusion of the arboreal pygmy anteater (Cyclopes didactylus). Such a relationship, first proposed on the basis of myological [START_REF] Reiss | Myology of the feeding apparatus of myrmecophagid anteaters (Xenarthra: Myrmecophagidae)[END_REF] and morphological [START_REF] Gaudin | The phylogeny of the Myrmecophagidae (Mammalia, Xenarthra, Vermilingua) and the relationship of Eurotamandua to the Vermilingua[END_REF] characters, has been confirmed by molecular studies which supported an early emergence of the pygmy anteater within Vermilingua [START_REF] Delsuc | The evolution of armadillos, anteaters and sloths depicted by nuclear and mitochondrial phylogenies: Implications for the status of the enigmatic fossil Eurotamandua[END_REF][START_REF] Delsuc | Molecular phylogeny of living xenarthrans and the impact of character and taxon sampling on the placental tree rooting[END_REF].

Of particular interest are the relationships among extant armadillos. Cingulata represents the earliest and most speciose xenarthran lineage with 21 living species classified into eight genera [START_REF] Wetzel | Taxonomy and distribution of armadillos, Dasypodidae[END_REF][START_REF] Vizcaíno | Identificación específica de las "mulitas", género Dasypus (Mammalia, Dasypodidae), del noroeste argentino. Descripción de una nueva espécie[END_REF]. This ecologically and morphologically diverse group is currently divided into the five tribes Chlamyphorini, Euphractini, Priodontini, Tolypeutini and Dasypodini [START_REF] Wetzel | Taxonomy and distribution of armadillos, Dasypodidae[END_REF][START_REF] Mckenna | Classification of mammals above the species level[END_REF]. The tribe Chlamyphorini contains two species of fairy armadillos (genus Chlamyphorus) restricted to the sandy plains and pampas of Northern Argentina, Paraguay and Bolivia [START_REF] Wetzel | Taxonomy and distribution of armadillos, Dasypodidae[END_REF]. Little is known about the biology and conservation status of these cryptic animals, at least partly because of their mainly nocturnal and subterranean way of life [START_REF] Meritt | The fairy armadillo Chlamyphorus truncatus Harlan[END_REF]. Hairy armadillos (Euphractini) form a zoogeographically homogeneous group centered in dry open habitats from the high puna of Bolivia to pampas and savannas of Brazil, Paraguay and Argentina [START_REF] Wetzel | Taxonomy and distribution of armadillos, Dasypodidae[END_REF]. The three genera Chaetophractus, Euphractus and Zaedyus are morphologically very close and their interrelationships remain puzzling [START_REF] Engelmann | The phylogeny of the Xenarthra[END_REF]. The tribe Priodontini groups the endangered giant armadillo (Priodontes maximus) with naked-tailed armadillos from the genus Cabassous. These two fossorial genera possess characteristically shaped carapaces and enlarged manus claws specialized for digging [START_REF] Wetzel | Taxonomy and distribution of armadillos, Dasypodidae[END_REF]. They also share the particularity of having unusual spoon-shaped spermatozoon that are among the largest that can be found in mammals [START_REF] Cetica | Evolutionary sperm morphology and morphometry in armadillos[END_REF]. The tribe Tolypeutini includes only two species of three-banded armadillos (Tolypeutes) which are the only members of the family capable of entirely rolling into a ball to escape predators [START_REF] Wetzel | Taxonomy and distribution of armadillos, Dasypodidae[END_REF]. Finally, the tribe Dasypodini comprises seven species of longnosed armadillos classified in the single genus Dasypus [START_REF] Wetzel | The subgenera and species of long-nosed armadillos, genus Dasypus L[END_REF][START_REF] Vizcaíno | Identificación específica de las "mulitas", género Dasypus (Mammalia, Dasypodidae), del noroeste argentino. Descripción de una nueva espécie[END_REF] which are unique in being the only vertebrates to reproduce by obligate monozygotic polyembryony [START_REF] Galbreath | The evolution of monozygotic polyembryony in Dasypus[END_REF][START_REF] Loughry | Polyembryony in armadillos[END_REF]. Among them, the nine-banded armadillo (Dasypus novemcinctus) has the largest distribution, as a consequence of its recent and ongoing invasion of the Southern United-States [START_REF] Taulman | Recent range expansion and distributional limits of the nine-banded armadillo (Dasypus novemcinctus) in the United States[END_REF]. Interestingly, at least three species from this genus (D. novemcinctus, D. hybridus and D. sabanicola) are the only known animals, with the exception of human, in which the causative agent of leprosy (Mycobacterium leprae) can develop both naturally or experimentally [START_REF] Storrs | Leprosy in wild common long-nosed armadillos Dasypus novemcinctus[END_REF]. This unforeseen attribute, coupled with the systematic production of clonal sibships, has conferred armadillos with great promise for medical research, and the nine-banded armadillo was established early on as a model for leprosy studies [START_REF] Storrs | Leprosy in the armadillo: New model for biomedical research[END_REF]. The establishment of a well defined taxonomic framework for armadillos might thus provide directions for investigating the potential of other species as biomedical models, since the development of an anti-leprosy vaccine has proven difficult using the nine-banded armadillo [START_REF] Storrs | A lost talisman: Catastrophic decline in yields of leprosy bacilli from armadillos used for vaccine production[END_REF].

A previous study based on nuclear markers [START_REF] Delsuc | Molecular phylogeny of living xenarthrans and the impact of character and taxon sampling on the placental tree rooting[END_REF] failed to fully resolve the phylogeny of armadillos but identified three major lineages which correspond to the subfamilies Dasypodinae (Dasypus), Tolypeutinae (Tolypeutes, Cabassous, Priodontes) and Euphractinae (Euphractus, Chaetophractus, Zaedyus), previously defined on morphological grounds by [START_REF] Mckenna | Classification of mammals above the species level[END_REF]. The lack of resolution within the subfamilies Tolypeutinae and Euphractinae might stand in the relatively slow evolutionary rate of these nuclear genes [START_REF] Delsuc | Molecular phylogeny of living xenarthrans and the impact of character and taxon sampling on the placental tree rooting[END_REF]. Therefore, we turned to two faster evolving mitochondrial genes with the hope of collecting more informative sites to discern between alternative phylogenetic hypotheses within these two clades. Two mitochondrial markers undergoing potentially contrasted mutational and selective constraints were chosen: the protein-coding NADH dehydrogenase subunit 1 (ND1), and the ribosomal RNA-coding 12S rRNA. These two mitochondrial genes have been previously used for example to examine the relationships between xenarthrans and pangolins [START_REF] Cao | Conflict among individual mitochondrial proteins in resolving the phylogeny of eutherian orders[END_REF][START_REF] Delsuc | The evolution of armadillos, anteaters and sloths depicted by nuclear and mitochondrial phylogenies: Implications for the status of the enigmatic fossil Eurotamandua[END_REF]. Complete sequences of these genes were obtained for 13 xenarthran species representing all living genera except the rare Chlamyphorus. The new mitochondrial sequences were added to the data set of [START_REF] Delsuc | Molecular phylogeny of living xenarthrans and the impact of character and taxon sampling on the placental tree rooting[END_REF] composed of the three proteincoding nuclear genes: α2B Adrenergic receptor (ADRA2B), Breast Cancer Susceptibility exon 11 (BRCA1), and von Willebrand Factor exon 28 (VWF), to obtain a combined data set of 6,869 aligned nucleotide sites. We compared the evolutionary dynamics of these five genes in regards to pattern and rate of nucleotide substitutions, and employed maximum likelihood (ML; [START_REF] Felsenstein | Evolutionary trees from DNA sequences: A maximum likelihood approach[END_REF] and Bayesian phylogenetics (Huelsenbeck et al., 2001), to reconstruct the phylogeny of armadillos, with special reference to the subfamilies Tolypeutinae and Euphractinae.

MATERIAL & METHODS

Taxon sampling and data acquisition

We sampled 13 xenarthran species spanning 12 of the 13 extant genera (Table 1). Total DNAs were extracted from 95% ethanol preserved tissue samples stored in the mammalian tissue collection of the Institut des Sciences de l'Evolution de Montpellier [START_REF] Catzeflis | Animal tissue collections for molecular genetics and systematics[END_REF]. Complete mitochondrial 12S rRNA sequences (12S rRNA) were amplified using primers R1 and S2 [START_REF] Douzery | Molecular evolution of the mitochondrial 12S rRNA in Ungulata (Mammalia)[END_REF]. Complete sequences of the NADH dehydrogenase 1 gene (ND1) were amplified using primers R11 = 5'-TTTCTCCCAGTACGAAAGGAC-3' (forward) and N1 = 5'-CTATTATTTACTCTATCAAAGTAA-3' (reverse) located in the 16S rRNA and Ile tRNA genes, respectively. PCR products were purified from 1% agarose gels using Amicon Ultrafree-DA columns (Millipore). Automatic sequencing (Big Dye Terminator cycle kit) of purified PCR products was performed on both strands on an ABI 310 (PE Applied Biosystems) using PCR primers plus M1 = 5'-GGTAATTGCRTAARACTTAAACCTTT-3' (forward) located in the Leu tRNA and the ND1 internal primer N2 = 5'-TCRGCTADRAARAATAGGGC-3' (reverse). The 14 new xenarthran sequences have been deposited in the EMBL databank. Taxonomy and accession numbers referring to all sequences used in this study are indicated in Table 1.

Sequence alignment

The ND1 and 12S rRNA new sequences were manually aligned with existing sequences obtained by [START_REF] Cao | Conflict among individual mitochondrial proteins in resolving the phylogeny of eutherian orders[END_REF] and [START_REF] Delsuc | The evolution of armadillos, anteaters and sloths depicted by nuclear and mitochondrial phylogenies: Implications for the status of the enigmatic fossil Eurotamandua[END_REF], respectively, using the ED editor of the MUST package [START_REF] Philippe | MUST: A computer package of management utilities for sequences and trees[END_REF]. We excluded a glutamic acid repeat region of ADRA2B, a 21 nucleotide long repeated region of BRCA1 [START_REF] Madsen | Parallel adaptative radiations in two major clades of placental mammals[END_REF], and also hypervariable regions of 12S rRNA [START_REF] Springer | Secondary structure and patterns of evolution among mammalian mitochondrial 12s rRNA molecules[END_REF]. All introduced gaps were treated as missing data in subsequent analyses. The five individual data sets of 13 xenarthran taxa are: ADRA2B (1158 sites), BRCA1 (2793 sites), VWF (1162 sites), ND1 (957 sites) and 12S rRNA (898 sites). We also considered three additional data sets: the nuclear concatenation of ADRA2B + BRCA1 + VWF (NUC: 5113 sites), the mitochondrial concatenation of ND1 and 12S rRNA (MITO: 1855 sites), and the complete combined data set (COMB: 6968 sites). The five pilosan taxa (anteaters and sloths) were used as outgroups for rooting the cingulate (armadillos) subtree in all subsequent phylogenetic analyses. Alignments are available upon request.

Phylogenetic analyses

Phylogenetic analyses were conducted using Maximum Likelihood (ML) and Bayesian approaches. These probabilistic methods based upon explicit models of sequence evolution were favored because they are known to be robust to a number of systematic biases of phylogenetic reconstruction (Huelsenbeck et al., 2001;[START_REF] Swofford | Bias in phylogenetic estimation and its relevance to the choice between parsimony and likelihood methods[END_REF][START_REF] Sullivan | Should we use model-based methods for phylogenetic inference when we know that assumptions about among-site rate variation and nucleotide substitution pattern are violated?[END_REF]. A likelihood framework also provides us with the ability to statistically compare competing hypotheses and topologies [START_REF] Huelsenbeck | Phylogenetic methods come of age: Testing hypotheses in an evolutionary context[END_REF][START_REF] Goldman | Likelihood-based tests of topologies in phylogenetics[END_REF][START_REF] Whelan | Molecular phylogenetics: State-of-the-art methods for looking into the past[END_REF].

Maximum Likelihood

We first determined the best fitting model of sequence evolution for each data set using Modeltest 3.06 [START_REF] Posada | MODELTEST: Testing the model of DNA substitution[END_REF]. The Akaike Information Criterion (AIC; [START_REF] Akaike | A new look at the statistical model identification[END_REF] indicated that different models were appropriate to best describe the underlying evolutionary process of these eight datasets: TrN+Γ for ADRA2B, TrN+I+Γ for ND1, TVM+Γ for BRCA1 and NUC, GTR+Γ for 12S rRNA, and the GTR+I+Γ model for VWF, MITO and COMB (see [START_REF] Posada | Selecting the best-fit model of nucleotide substitution[END_REF] for a detailed description of these models). However, to render ML analyses comparable between PAUP* version 4.0b10 [START_REF] Swofford | PAUP*. Phylogenetic analysis using parsimony (* and other methods)[END_REF] and PAML version 3.11 [START_REF] Yang | PAML: A program package for phylogenetic analysis by maximum likelihood[END_REF], the latter of which does not allow the use of invariant sites, we chose to use the General Time Reversible model (GTR; [START_REF] Yang | Estimating the pattern of nucleotide substitution[END_REF] plus a gamma (Γ) distribution with eight categories (GTR+Γ 8 ; Yang, 1996a). Using the same model for each data set also afforded the ability to adequately compare the evolutionary dynamics of the five genes in terms of substitution pattern and rate of evolution. We verified that using this GTR+Γ 8 model did not change the results of ML searches, in terms of the highest likelihood topologies for any of the datasets. This sensitivity analysis suggested that our results were relatively insensitive to subtle deviations between the GTR+Γ 8 model and the best fitting model for a particular data set [START_REF] Buckley | Exploring among-site rate variation models in a maximum likelihood framework using empirical data: Effects of model assumptions on estimates of topology, branch lengths, and bootstrap support[END_REF][START_REF] Buckley | The effects of nucleotide substitution model assumptions on estimates of nonparametric bootstrap support[END_REF].

ML base composition stationarity assumptions were evaluated for each of the eight data sets by the χ 2 test implemented in TREE-PUZZLE 5.0 [START_REF] Strimmer | Quartet puzzling: A quartet maximum-likelihood method for reconstructing tree topologies[END_REF]. ML phylogenetic analyses consisted of heuristic searches with Tree Bisection Reconnection (TBR) branch swapping, performed with a Neighbor-Joining (NJ) starting tree. Optimal base composition, substitution rate matrix, and among site substitution rate heterogeneity parameters, were simultaneously estimated during the ML heuristic searches. Reliability of nodes was estimated by ML Bootstrap Percentages (BP ML ) [START_REF] Felsenstein | Confidence limits on phylogenies: An approach using the bootstrap[END_REF] obtained after 500 pseudoreplications, using the previously estimated ML parameters, with NJ starting trees and TBR branch swapping.

Bayesian approach

The Bayesian approach to phylogenetic reconstruction [START_REF] Rannala | Probability distribution of molecular evolutionary trees: A new method of phylogenetic inference[END_REF][START_REF] Yang | Bayesian phylogenetic inference using DNA sequences: A Markov chain Monte Carlo method[END_REF] was implemented using MrBayes 2.01 (Huelsenbeck and Ronquist, 2001).

Metropolis-coupled Markov chain Monte Carlo (MCMCMC) sampling was performed with five incrementally heated chains that were simultaneously run for 1,000,000 generations, using the program default priors as starting values for GTR+Γ 8 model parameters. To check for potentially poor mixing of MCMCMC, each analysis was repeated twice. The convergence of MCMCMC was monitored by examining the value of the marginal likelihood through generations.

Convergence of substitution rate and rate heterogeneity model parameters was also checked. As previously observed by [START_REF] Miller | An examination of the monophyly of morning glory taxa using Bayesian phylogenetic inference[END_REF], the chains reached convergence more rapidly for the likelihood function than for model parameters. However, the high numbers of generations (1,000,000) run here permitted to reach stationarity of likelihood model parameters for our relatively small data sets. Bayesian Posterior Probabilities (PP) were obtained from the 50% majority rule consensus of 25,000 trees sampled every 20 generations after removing the 25,000 first trees as the "burn-in" stage. We verified that PP did not undergo significant variations between independently repeated runs even when performing only 200,000 generations instead of 1,000,000 (i.e., PP variations were less than 0.05).

Since Bayesian Posterior Probabilities have recently been shown to provide overestimates of phylogenetic support [START_REF] Suzuki | Overcredibility of molecular phylogenies obtained by Bayesian phylogenetics[END_REF], we also computed Bootstrapped Bayesian Posterior Probabilities (BP Bay ) following the new approach of Douady et al. (2003a), as a more conservative measure of Bayesian support. First, 100 bootstrap pseudo-replicates drawn irrespective of codon positions were generated for each data set using the program CODONBOOTSTRAP 3.0 (available from Jonathan P. Bollback at http://brahms.ucsd.edu/software.html). Second, for each pseudo-replicate, MCMCMC sampling of trees was performed as previously described, except that the five chains were run for only 100,000 generations. A conservative one-half of the 5,000 trees sampled from the posterior probability distribution were systematically discarded as "burn-in", to maximize the probability that the chains reached stationarity in each bootstrap resampled data set. Finally, we picked BP Bay from the overall 50% majority rule consensus of the 100 x 2,500 = 250,000 saved trees.

Statistical tests of alternative hypotheses

Since our genes belong to different cellular compartments (nuclear and mitochondrial) and markedly differ in function, it is likely they evolve under different selective pressures. To accommodate expected differences in evolutionary dynamics between genes, and especially between nuclear and mitochondrial loci, we followed the approach of Yang (1996b) for analyzing multiple genes. This approach, which allows each gene to evolve under its own model in a "partitioned likelihood model", resulted in a general and significant increase in loglikelihood. For example, in the case of the combined data set, the parameter rich model incorporating five independent sets of 31 free parameters-three base frequencies, five GTR rates, one Gamma shape, and 22 branch lengths for a 13 taxon tree with a basal trifurcationmore appropriately described the underlying evolutionary processes than a single GTR+Γ 8 model. The AIC decreased from 58,085.86 (= 2 x 29,011.93 + 2 x 31) to 56,208.06 (= 2 x 27,949.03 + 2 x 31 x 5) when an independent set of base, GTR+Γ 8 , and branch length parameters was attributed to each gene. Partitioned ML models were used in PAML to compute loglikelihoods and confidence probability values for alternative phylogenetic hypotheses.

A posteriori selected topologies [START_REF] Goldman | Likelihood-based tests of topologies in phylogenetics[END_REF] were statistically compared to the best ML topology by the test of [START_REF] Kishino | Evaluation of the maximum likelihood estimate of the evolutionary tree topologies from DNA sequence data, and the branching order in Hominoidea[END_REF] applying the [START_REF] Shimodaira | Multiple comparisons of log-likelihoods with applications to phylogenetic inference[END_REF] correction for multiple comparisons (SH test). One potential problem in using the SH test is that the results of the test are in part dependent on the number of competing topologies examined [START_REF] Goldman | Likelihood-based tests of topologies in phylogenetics[END_REF]. As an alternative, the use of the parametric SOWH test [START_REF] Swofford | Phylogenetic inference[END_REF] has been advocated [START_REF] Goldman | Likelihood-based tests of topologies in phylogenetics[END_REF]. However, this test was not used here, because it is associated with high computational burden and has been shown to be misleading in some cases, being prone to Type I errors, even when using the most sophisticated models of sequence evolution [START_REF] Buckley | Model misspecification and probabilistic tests of topology: Evidence from empirical data sets[END_REF]. Moreover, the SH test is thought to be accurate when the number of candidate trees is small [START_REF] Shimodaira | An approximately unbiased test of phylogenetic tree selection[END_REF].

RESULTS & DISCUSSION

Evolutionary properties of the five genes

Striking differences in base composition are displayed by the five genes. Within Xenarthra, the nuclear genes ADRA2B and VWF appear G+C-rich (72.1% and 65.4%, respectively), whereas BRCA1 is rather A+T rich (61.9%). The two mitochondrial markers 12S rRNA and ND1 present exactly the same excess of A+T (58%) relative to G+C (42%). Although the frequencies of Adenine and Thymine are nearly identical for these two genes (37 / 38% for A and 20 / 21% for T), ND1 exhibits a notably small proportion (7.0%) of Guanine. Base composition stationarity assumptions were evaluated by a χ 2 test which compares the nucleotide composition of each sequence to the frequency distribution assumed in the maximum likelihood model. All gene sets appeared homogenous in terms of base composition with only Cyclopes deviating from stationarity for ND1 (P = 0.04).

Comparative plots of ML estimated GTR+Γ 8 parameters provides an easily visualized means of contrasting the evolutionary dynamics of the five genes (Figure 1). This graphical representation highlights the fundamental differences between nuclear and mitochondrial genes for Xenarthra in terms of pattern and rate of nucleotide substitutions. The two mitochondrial genes ND1 and 12S rRNA are characterized by marked excesses of transitions over transversions and exhibit elevated evolutionary rates, approximately five and two fold faster respectively than the fastest nuclear gene (ADRA2B) (Figure 1). These faster rates of molecular evolution are coupled with strong among site rate heterogeneity, as indicated by low values of the gamma shape parameter (α = 0.22 and 0.29, respectively) (Figure 1). The strong rate heterogeneity disclosed in the ND1 gene might find its origin in contrasted patterns of substitution and evolutionary rates among its three codon positions. Also observing such a strong rate heterogeneity in the 12S rRNA was not unexpected as it has been previously reported in the case of sigmodontine rodents [START_REF] Sullivan | Among-site rate variation and phylogenetic analysis of 12S rRNA sigmodontine rodents[END_REF]. It likely reflects the mosaic structure of this gene, consisting of slowly evolving stems, and faster evolving loops, related to secondary base-pairing interactions [START_REF] Springer | Secondary structure and patterns of evolution among mammalian mitochondrial 12s rRNA molecules[END_REF]. A strong bias toward C-T transitions is detected here for this gene (Figure 1). Thus, saturation might be reached at fast evolving positions, particularly those within loops, which are prone to this type of change [START_REF] Springer | Secondary structure and patterns of evolution among mammalian mitochondrial 12s rRNA molecules[END_REF]. Among nuclear genes, BRCA1 was the slowest evolving gene and exhibited the lowest among site rate heterogeneity (α = 1.41: Figure 1). This relative among site rate homogeneity is explained by the atypical evolutionary pattern of this gene, with first, second and third codon positions evolving in a strikingly similar manner [START_REF] Adkins | Molecular phylogeny and divergence time estimates for major rodent groups: Evidence from multiple genes[END_REF][START_REF] Delsuc | Molecular phylogeny of living xenarthrans and the impact of character and taxon sampling on the placental tree rooting[END_REF]. These differences in evolutionary dynamics between genes are reflected in the number and percentage of variable sites observed in each individual data set. For example, about 49.6% of the ND1 sites appeared variable whereas only 24.3% in BRCA1. Given such differences in nucleotide variability, these genes are expected to markedly differ in their phylogenetic resolving power, mitochondrial genes providing more informative sites at taxonomic level such as the one of family Dasypodidae.

Phylogenetic results

Results from individual genes

The maximum likelihood phylograms inferred from each of the five individual genes are presented in Figure 2. At first glance, it is striking to note that the analysis of each individual gene yielded phylogenies which are topologically incompatible with each other (Figure 2). However, each gene supported the monophyly of the three armadillo subfamilies: Dasypodinae, Tolypeutinae and Euphractinae with the noteworthy exception of the 12S rRNA (Figure 2; Table 2). This gene produced a topology different from the other four by placing the three-banded armadillo Tolypeutes as the sister group of all other Dasypodidae, and thus breaking the otherwise strongly supported monophyly of the subfamily Tolypeutinae (Figure 2). However, this alternative topology is poorly supported and this gene tends towards a general lack of resolution, except for relationships among euphractine armadillos. The topological instability and general lack of resolution exhibited by this gene may be a consequence of nucleotide saturation related to the strong mutational bias toward C-T transitions (Figure 1). Moreover, model sensitivity analyses revealed that this topology is unstable and largely dependent upon the likelihood model used. Notably, phylogenetic reconstruction with this gene appeared to be sensitive to the number of discrete rate categories used to describe the gamma distribution (either 4, 5, 6, 7, or 8 ; data not shown). These observations underline difficulties to accommodate the strong rate heterogeneity induced by the stems-loops structure and suggest to be cautious when interpreting phylogenetic results issued from the analyses of this gene [START_REF] Sullivan | Among-site rate variation and phylogenetic analysis of 12S rRNA sigmodontine rodents[END_REF]. The incorporation of structural information in substitution models specific to the evolution of basepaired regions of mammalian mitochondrial RNAs seems promising [START_REF] Jow | Bayesian phylogenetics using an RNA substitution model applied to early mammalian evolution[END_REF]. However, frequent and clustered site-specific rate variation has been detected in the mitochondrial 16S rRNA gene of insects [START_REF] Misof | An empirical analysis of mt 16S rRNA covarion-like evolution in Insects: site-specific rate variation is clustered and frequently detected[END_REF], suggesting that this gene-and presumably other ribosomal molecules-evolve under a covarion-like process. It is thus suggested that phylogenetic analyses of the 12S rRNA xenarthran data set under a covarion-like model might help to recover a topology compatible with other genes. As an alternative explanation for the basal position of Tolypeutes among armadillos, we cannot rule out the possibility that the corresponding 12S rRNA sequence of the three-banded armadillo we obtained is a unwittingly amplified divergent mitochondrial-derived nuclear pseudogene. Indeed, even if the use of secondary structure features might help to detect rRNA nuclear paralogs, it has been shown that the identification of 12S rRNA nuclear insertions may prove to be very difficult [START_REF] Olson | Using secondary structure to identify ribosomal numts: cautionary examples from the human genome[END_REF].

Apart from the peculiar 12S rRNA topology, all other topologies agreed in grouping the subfamilies Tolypeutinae and Euphractinae with moderate (ADRA2B and VWF) to strong (BRCA1 and ND1) support (Figure 2; Table 2). However, conflicts exist between genes about relationships within these two subfamilies (Figure 2; Table 2). Indeed, within tolypeutines, the VWF, 12S rRNA and ND1 genes favor a Cabassous + Priodontes clade, whereas ADRA2B prefers Priodontes + Tolypeutes, and BRCA1 Cabassous + Tolypeutes, each with almost equivalent moderate support (Figure 2; Table 2). The situation is even more complicated in the case of the euphractines where the three possible alternatives appear strongly supported by different genes: ADRA2B supports Euphractus + Zaedyus, BRCA1 and 12S rRNA prefers Euphractus + Chaetophractus, and VWF and ND1 Chaetophractus + Zaedyus (Figure 2; Table 2).

The statistical significance of the topological incongruence between the five individual genes was evaluated by performing crossed SH tests [START_REF] Delsuc | Molecular phylogeny of living xenarthrans and the impact of character and taxon sampling on the placental tree rooting[END_REF][START_REF] Huchon | Rodent phylogeny and a timescale for the evolution of Glires: Evidence from an extensive taxon sampling using three nuclear genes[END_REF]. In these tests, the highest-likelihood topologies obtained with individual genes were compared against each other under each of the five character matrices (Table 3). The results indicate that none of the individual data sets significantly rejects the ML topology of the other four, with the exception of the atypical 12S rRNA ML topology under the ADRA2B, BRCA1 and ND1 data sets (Table 3). This reinforces the earlier observation regarding the peculiar nature of the 12S rRNA topology, and the fact that it is likely the result of a phylogenetic artifact related to the particular evolutionary behavior of this gene (see also [START_REF] Sullivan | Among-site rate variation and phylogenetic analysis of 12S rRNA sigmodontine rodents[END_REF]. However, these tests conclude that despite apparently high topological incongruence, each individual gene leads to a phylogenetic estimate compatible with the signal provided by the others. This conclusion is also corroborated by the fact that seemingly incongruent regions between trees are restricted to nodes involving short internal edges, despite being strongly supported in certain cases (Figure 2). Thus, with the exception of the 12S rRNA tree, individual trees appear to be "different" but are nonetheless "similar" [START_REF] Penny | Trees from languages and genes are very similar[END_REF], based on the results of the conservative SH test.

Results from the nuclear, mitochondrial and combined data sets

Combining signal from different data sets in phylogenetic analyses has long been a matter of controversy (Huelsenbeck et al., 1996). Here we adopted the "conditional combination" approach which proposes to statistically test the homogeneity of a priori defined data partitions before combining them in an overall approach [START_REF] Bull | Partitioning and combining data in phylogenetic analysis[END_REF]. The homogeneity of the signal carried by each individual gene was statistically evaluated by crossed SH tests in which the highest-likelihood topologies obtained with individual genes were compared against those obtained from nuclear (ADRA2B + BRCA1 + VWF), mitochondrial (12S rRNA + ND1) and all gene combinations. These tests indicated that none of the five individual data sets significantly rejects the ML topology resulting from either the nuclear, mitochondrial, or all gene combinations (Table 3). This suggests that combining individual genes in a priori defined data partitions leads to a phylogenetic estimate compatible with the signal contributed by each individual gene.

The ML phylograms obtained from the nuclear and mitochondrial combinations are compared in Figure 3. There are clear topological differences between the two phylogenies. Once again the conflicting areas involve relationships within the subfamilies Tolypeutinae and Euphractinae. The nuclear concatenation favors the grouping of Cabassous and Tolypeutes (BP ML =52 / PP=0.70 / BP Bay =50) within Tolypeutinae, whereas the mitochondrial genes support a Cabassous + Priodontes clade (69 / 0.99 / 68). Within Euphractinae, the nuclear partition groups Euphractus and Zaedyus (56 / 0.85 / 58), whereas the mitochondrial combination prefers Euphractus + Chaetophractus (54 / 0.83 / 50). It is, however, noteworthy that these topological conflicts implicate short and statistically poorly supported internal branches, except the possible relationship between Cabassous and Priodontes, which is moderately supported by the mitochondrial data set (Figure 3; Table 2). As a consequence of the lack of resolution within these two subfamilies, partitioned SH tests failed to statistically distinguish between alternative hypotheses (Table 4). Apart from these discrepancies, both the nuclear and mitochondrial combination unequivocally supported the monophyly of the three armadillo subfamilies and strongly favored the early emergence of Dasypodinae within Dasypodidae (Figure 3; Table 2).

Alternatives breaking the monophyly of the Tolypeutinae + Euphractinae clade were statistically rejected by the nuclear data set (Table 4).

The maximum likelihood phylogram obtained from the combined data set is presented in Figure 4. This topology is fully congruent with the one yielded by the analysis of the mitochondrial data set (see Figure 3). Examination of the relative contribution of each gene to total branch lengths reveals the preponderant role of the two mitochondrial genes. Predictably, the contribution of these faster evolving genes is particularly relevant in the definition of short internal branch lengths within Dasypodidae (Figure 4). The concatenation of the five genes adds support to the respective monophyly of the three subfamilies and to the close relationship between Tolypeutinae and Euphractinae (Figure 4; Table 2). Partitioned SH tests indicated that alternatives to such a relationship are significantly worse when using the combined data set (Table 4). However, irresolution persists within these two subfamilies. The combination of the five genes favors the classical grouping of Cabassous + Priodontes within tolypeutines but with low statistical support (54 / 0.87 / 52). It equally poorly supports a Chaetophractus + Euphractus clade within euphractines (60 / 0.97 / 54). Once again, the partitioned likelihood SH tests are inconclusive regarding the alternatives to the best topology with each hypothesis remaining almost equally likely (Table 4).

Topological incongruence and rapid cladogenesis events

It is clear from our results that Bayesian posterior probabilities (PP) were systematically higher than ML bootstrap proportions (BP ML ) (Table 2 ; Figures 234). This propensity has been noted by other authors, who tried to compare the two measures of phylogenetic support [START_REF] Leaché | Molecular systematics of the Eastern Fence Lizard (Sceloporus undulatus): A comparison of parsimony, likelihood, and Bayesian approaches[END_REF][START_REF] Whittingham | Phylogeny of the tree swallow genus, Tachycineta (Aves: Hirundinidae), by Bayesian analysis of mitochondrial DNA sequences[END_REF][START_REF] Wilcox | Phylogenetic relationships of the dwarf boas and a comparison of Bayesian and bootstrap measures of phylogenetic support[END_REF]. In our case, and others (Buckley et al. 2002;Douady et al., 2003b), this tendency led to a situation where high PP were obtained for mutually exclusive nodes inferred from different data sets (Table 2). Thus, based solely on this estimator, one might conclude that there was incongruence between our different data sets. However, some of these conflicts were not so strongly supported by BP ML .

Furthermore, the use of bootstrap resampling under the Bayesian approach (BP Bay )-as suggested by Douady et al. (2003a)-rendered the two indices comparable by lowering PP (Table 2). These observations seem to support the views that: (i) PP tends to provide overestimates of phylogenetic support as recently shown in simulation studies by [START_REF] Suzuki | Overcredibility of molecular phylogenies obtained by Bayesian phylogenetics[END_REF]; (ii) a more conservative approach might be to incorporate bootstrap in Bayesian analyses [START_REF] Waddell | Very fast algorithms for evaluating the stability of ML and Bayesian phylogenetic trees from sequences data[END_REF]Douady et al., 2003a).

The use of bootstrap resampling under Bayesian analyses was able to eliminate conflicting support within the subfamily Tolypeutinae, but strong incongruence persisted within Euphractinae (Table 2). Also, apart from VWF which is uninformative for this question, the four remaining markers exclusively supported one of the three alternative hypotheses: ADRA2B supports Euphractus + Zaedyus (BP ML = 92 / BP Bay = 86), BRCA1 (BP ML = 96 / BP Bay = 92) and 12S rRNA (BP ML = 99 / BP Bay = 98) supports Euphractus + Chaetophractus, and ND1 supports Chaetophractus + Zaedyus (BP ML = 92 / BP Bay = 88). Further understanding regarding the origin of these conflicting signals emerged from the examination of the ML inferred number of apomorphies supporting each alternative (Table 2). Nuclear genes contain too few relevant sites to draw firm conclusions for relationships within subfamilies. Indeed, their combination provides only 18 + 10 = 28 relevant sites over 5113 to distinguish between alternatives within the subfamilies Tolypeutinae and Euphractinae, respectively (Table 2). The strongly supported conflict between ADRA2B and BRCA1 within Euphractinae rests on only three incompatible apomorphies. Thus, incompatibility between these two genes may be the result of stochastic effects associated with a low number of pertinent informative sites. By contrast, mitochondrial genes bring a greater number of informative sites and apomorphies relevant for reconstructing relationships within subfamilies. Hence, 20 of the 23 relevant apomorphies in ND1 supported Chaetophractus + Zaedyus whereas the 14 relevant 12S rRNA apomorphies exclusively supported Chaetophractus + Euphractus. The causes of incongruence between these two mitochondrial loci are not obvious. One possible reason might lie in the previously mentioned particular evolutionary behavior of the 12S rRNA gene in Xenarthra. In addition, Zaedyus appeared as a very fast evolving taxon for this gene (Figure 2) and its phylogenetic position might be influenced by a potential long branch attraction artifact [START_REF] Felsenstein | Cases in which parsimony or compatibility methods will be positively misleading[END_REF][START_REF] Hendy | A framework for the quantitative study of evolutionary trees[END_REF]).

Owing to the high number of incompatible apomorphies observed between genes, it is not surprising that the combination of the five genes failed to resolve the phylogenetic relationships among Tolypeutinae and Euphractinae (Table 2 ; Figure 5). Thus, despite the inclusion of more rapidly evolving mitochondrial genes, we were not able to resolve the two remaining uncertainties in Xenarthra phylogeny. The low bootstrap support values associated with almost equal distributions of apomorphies among alternative hypotheses suggest the occurrence of rapid cladogenesis in Tolypeutinae and Euphractinae, leaving only short time windows for molecular synapomorphies to accumulate. Certainly, relative incongruence between different genes is not unexpected when lineages likely diverged within a short period of time. Hybridization, incomplete lineage sorting or assortment of ancestral polymorphism are commonly cited as potential causes of incongruence between gene and species trees [START_REF] Maddison | Gene trees in species trees[END_REF]. The persistence of ancestral polymorphism coupled with the differential survival of alleles has been shown to significantly account for the difficulties encountered in accurately resolving the hominoid trifurcation between human, chimpanzee and gorilla [START_REF] Satta | DNA archives from our nearest relative: The trichotomy problem revisited[END_REF][START_REF] O'huigin | Contribution of homoplasy and of ancestral polymorphism to the evolution of genes in anthropoid primates[END_REF]. Our results, thus, tend to confirm the nuclear based hypothesis [START_REF] Delsuc | Molecular phylogeny of living xenarthrans and the impact of character and taxon sampling on the placental tree rooting[END_REF] of two parallel episodes of fast diversification during the evolutionary history of extant armadillos, which have led to two difficult-to-resolve trifurcations within the subfamilies Tolypeutinae and Euphractinae. The reconstruction of a reliable molecular time-scale for the chronicle of xenarthran evolution might help to identify the grounds of these events. from the British Systematics Association. This is the contribution ISEM 2002-080 of the Institut des Sciences de l'Evolution de Montpellier (UMR 5554 -CNRS). Note: Log-likelihoods values of ML topologies inferred from each data set were computed using each of the eight data matrices and then compared to the corresponding highest log-likelihood value (in bold). The difference in log-likelihood derived from these crossed comparisons and corresponding confidence P values of the SH test (between brackets) are also indicated. A * indicates that the tested topology is significantly worse at the 5% level than the best ML topology for the corresponding data set.

TABLES

Fig. 4 .

 4 Fig. 4. Maximum likelihood tree obtained from the combined data set (6968 sites) under the GTR+Γ Γ Γ Γ 8 model. Maximum likelihood estimates of model parameters were: A=0.29,

  Figure 1(Delsuc et al.)

FigureFigure 4 (

 4 Figure 2(Delsuc et al.)

Table 1 :

 1 Taxonomy and Accession Numbers for sequences used in this study.Note: 1 Species B. variegatus (Brown-throated Three-toed Sloth). 2 Sequences new to this study.

	Taxonomy	Species	Common name	ADRA2B	BRCA1	VWF	ND1	12S rRNA
	XENARTHRA
	PILOSA
	Bradypodidae	Bradypus tridactylus	Pale-throated Three-toed Sloth	AJ251179 AF284002	U31603	AB011218 1 AF038022
	Megalonychidae	Choloepus didactylus	Southern Two-toed Sloth	AJ427375 AF484229 AJ278160 AJ505830 2 AJ278152
	Myrmecophagidae Myrmecophaga tridactyla	Giant Anteater	AJ427373 AF484232 AJ278157 AJ505831 2 AJ278153
		Tamandua tetradactyla	Collared Anteater	AJ427374 AF284001 AJ278161 AB011216 AJ278154
		Cyclopes didactylus	Pygmy Anteater	AJ315943 AF484231 AJ278156 AJ505832 2 AJ278155
	CINGULATA
	Dasypodidae
	Dasypodinae	Dasypus novemcinctus	Nine-banded Armadillo	AJ427366 AF484222 AJ278158	Y11832	Y11832
		Dasypus kappleri	Great Long-nosed Armadillo	AJ427367 AF484223 AJ427361 AJ505833 2 AJ505825 2
	Euphractinae	Euphractus sexcinctus	Six-banded Armadillo	AJ427368 AF484224 AJ427364 AJ505834 2 AJ505826 2
		Chaetophractus villosus	Larger Hairy Armadillo	AJ315935 AF284000 AF076480 AJ505835 2	U61080

Table 2 :

 2 Maximum likelihood bootstrap support (BP ML ), Bayesian posterior probabilities (PP), bootstrapped Bayesian posterior probabilities (BP Bay ) and ML inferred number of apomorphies (Apo) supporting different alternative phylogenetic relationships between and within the three armadillo subfamilies.

			ADRA2B			BRCA1			VWF
		BP ML PP BP Bay Apo	BP ML PP BP Bay Apo BP ML PP BP Bay Apo
	DASYPODIDAE
	EUPHRACTINAE + TOLYPEUTINAE	56	0.79	63	9	99	1.00 100 15	58	0.77	50	3
	EUPHRACTINAE + DASYPODINAE	42	0.21	35	13	-	-	-	0	23	0.09	26	0
	TOLYPEUTINAE + DASYPODINAE	-	-	-	0	-	-	-	5	17	0.14	20	0
	Tolypeutinae
	Cabassous + Priodontes	-	0.07	10	0	17	-	25	1	59	0.73	55	5
	Cabassous + Tolypeutes	26	0.16	26	1	76	0.94	68	2	16	0.10	22	3
	Priodontes + Tolypeutes	68	0.77	63	3	-	-	7	0	22	0.17	17	4
	Euphractinae
	Euphractus + Chaetophractus	-	-	-	0	96	1.00	92	3	18	0.22	27	1
	Euphractus + Zaedyus	92	0.98	86	3	-	-	-	0	35	0.44	33	1
	Chaetophractus + Zaedyus	6	-	9	0	-	-	-	0	40	0.34	40	1

Table 3 :

 3 Results from standard[START_REF] Shimodaira | Multiple comparisons of log-likelihoods with applications to phylogenetic inference[END_REF] crossed tests of topological congruence between the eight data sets.

	Data sets

Table 4 :

 4 Results of partitioned[START_REF] Shimodaira | Multiple comparisons of log-likelihoods with applications to phylogenetic inference[END_REF] tests of alternative hypotheses depicting phylogenetic relationships between and within the three armadillos subfamilies. Log-likelihoods of selected topologies were compared with PAML using independent ML models (GTR+Γ 8 ) for each gene. The highest likelihood is given between square brackets. ∆ln L / S. E. = ratio between the log-likelihood difference of a phylogenetic alternative relative to the best hypothesis and its standard error. P SH = P value of the SH test with multiple-comparison correction; a * indicates that the tested hypothesis is significantly rejected at the 5% level.KH indicates that the tested hypothesis is significantly rejected at the 5% level by the[START_REF] Kishino | Evaluation of the maximum likelihood estimate of the evolutionary tree topologies from DNA sequence data, and the branching order in Hominoidea[END_REF] test. Comparative evolutionary dynamics of the five genes within Xenarthra.Maximum likelihood estimates of substitution rate and among site heterogeneity parameters under the GTR+G 8 model are graphically represented. From left to right: GTR rate matrix parameters for transitions A↔G and C↔T (gray bars) and transversions A↔C, A↔T, C↔G and G↔T=1 (white bars), rate between genes relative to the slowest one, i.e. BRCA1 (black bars), and α parameter of the Γ 8 distribution (horizontally hatched bars). Exact values of the different estimated parameters can be found in Table2. Fig. 2. Maximum likelihood topologies obtained from the five individual data sets under the GTR+Γ Γ Γ Γ 8 model. Maximum likelihood estimates of model parameters can be found in

		Nuclear		Mitochondrial	Combination
	Topologies	∆ ∆ ∆ ∆ln L / S. E.	P SH	∆ ∆ ∆ ∆ln L / S. E.	P SH	∆ ∆ ∆ ∆ln L / S. E.	P SH
	DASYPODIDAE
	EUPHRACTINAE + TOLYPEUTINAE	[-17272.22]	Best	[-10617.99]	Best	[-27949.03]	Best
	EUPHRACTINAE + DASYPODINAE	24.34/9.42 KH <0.05 *	10.46/6.65	0.24	32.96/11.39 KH <0.05 *
	TOLYPEUTINAE + DASYPODINAE	23.31/9.66 KH <0.05 *	12.16/6.13 KH 0.17	33.28/11.35 KH <0.05 *
	Tolypeutinae
	Cabassous + Priodontes	2.46/3.60	0.67	[-10617.99]	Best	[-27949.03]	Best
	Cabassous + Tolypeutes	[-17272.22]	Best	4.29/6.27	0.55	0.24/6.09	0.82
	Priodontes + Tolypeutes	2.50/3.57	0.67	7.26/5.21	0.37	4.41/4.48	0.66
	Euphractinae
	Euphractus + Chaetophractus	0.79/4.99	0.77	[-10617.99]	Best	[-27949.03]	Best
	Euphractus + Zaedyus	[-17272.22]	Best	6.83/5.03	0.41	4.52/6.23	0.61

Table 2 .

 2 Values at nodes indicate maximum likelihood and Bayesian support expressed by A↔T=1.56, C↔G=0.57, C↔T=15.89, G↔T=1.00; α=0.29 for the mitochondrial data set. Values at nodes indicate maximum likelihood and Bayesian support expressed by maximum likelihood bootstrap (BP ML ) / Bayesian posterior probability (PP) / bootstrapped posterior probability (BP Bay ). Nodes marked with a star (*) are supported by 100 / 1.00 / 100.Topological conflicts are indicated by crossed broken lines. Note that the scale is the same for the two topologies illustrating the contrast in substitution rate between nuclear and mitochondrial genes.

	maximum likelihood bootstrap (BP ML ) / Bayesian posterior probability (PP) / bootstrapped
	posterior probability (BP Bay ). Nodes marked with a star (*) are supported by 100 / 1.00 / 100.
	Note that different scales are used for nuclear (ADRA2B, BRCA1 and VWF) and
	mitochondrial (ND1 and 12S rRNA) genes illustrating the large difference in evolutionary
	rate between these markers. D. is an abbreviation for Dasypus.
	Fig. 3. Comparison of maximum likelihood topologies obtained from the nuclear (5113
	sites) and mitochondrial (1855 sites) data sets under the GTR+Γ Γ Γ Γ 8 model. Maximum
	likelihood estimates of model parameters were: A=0.28, C=0.26, G=0.25, T=0.21;
	A↔C=0.91, A↔G=4.69, A↔T=0.71, C↔G=1.96, C↔T=4.73, G↔T=1.00; α=0.60 for the
	nuclear data set; and A=0.37, C=0.29, G=0.13, T=0.21; A↔C=2.16, A↔G=9.47,

ACKNOWLEDGMENTS

We would like to thank the associated editors Wilfried W. de Jong, Mark S. Springer and Michael J. Stanhope for inviting us to contribute to this special issue on mammalian phylogeny.

We are grateful to François Catzeflis for giving access to tissue samples and laboratory facilities. This work would not have been possible without the help of the following individuals and institutions in providing us with xenarthran samples: Tammie L. Bettinger (Cleveland Metroparks Zoo, US), Pablo Carmanchahi, Pablo Cetica, Jorgue Omar García and Rodolpho Rearte (Complejo Ecológico Municipal de Presidencia Roque Sàenz Peña, Chaco, Argentina), Guillermo Anibal Lemus, Jesus Mavarez, Guillermo Perez Jimeno, Mariella Superina, and Jean-Christophe Vié and his team "Faune Sauvage" in French Guiana. Wilfried W. de Jong and two anonymous reviewers provided helpful comments on the manuscript. This work has been supported by the TMR Network "Mammalian phylogeny" (contract FMRX -CT98 -022) of the European Community and by the Génopôle Montpellier Languedoc-Roussillon. FD acknowledges the financial support of a MENRT doctoral grant (contract 99075) and a grant


This preface introduces the first special issue out of a series of workshops on Homotopy Type Theory and Univalent Foundations. This recent area of research finds its roots in the seminal work of Martin Hofmann and Thomas Streicher on the structure of Martin-Löf identity types [START_REF] Hofmann | The groupoid interpretation of type theory[END_REF]. But the main research program has been foreseen by Vladimir Voevodsky, who, from its initial motivation of formalizing his results in homotopy theory, has initiated what is now called the univalent foundations program [START_REF]The Univalent Foundations Program: Homotopy Type Theory: Univalent Foundations of Mathematics[END_REF]. Borrowing ideas from homotopy theory, the goal of the univalent foundations program is to leverage dependent Type Theory to a formal framework that could replace Set Theory for the foundations of mathematics.

This special issue gathers research contributions of some of the most prominent researchers of the field that we briefly outline below.

The univalence axiom in cubical sets. Authors: Marc Bezem, Thierry Coquand and Simon Huber.

This paper shows that the central axiom of the univalent foundations holds in a model of Type Theory based on (Kan) cubical sets. The univalence axiom has originally been justified by Vladimir Voevodsky using the simplicial sets model, but the cubical sets model is the first model of a univalent type theory which can be expressed in a constructive setting and thus is amenable to a concrete implementation.

Canonicity for Cubical Type Theory. Author: Simon Huber Cubical type theory is a univalent type theory reflecting the structure of the cubical sets model where there is a direct access to the manipulation of n-dimensional cubes. In this type theory, the univalence axiom is provable. This paper shows that cubical type theory satisfies a canonicity property which implies in particular that any natural number in a context build from only name variables is judgmentally Stockholm University, Sweden • Inria, France equal to a numeral. This result shows that cubical type theory is a convenient theory to be implemented and to compute with.

Guarded Cubical Type Theory. Authors: Lars Birkedal, Aleš Bizjak, Ranald Clouston, Hans Bugge Grathwohl, Bas Spitters and Andrea Vezzosi.

This papers proposes to extend Guarded Type Theory, a type theory with guarded recursive types, to a cubical setting, in order to provide better reasoning on equality proofs. The resulting theory provides a computational interpretation of extensionality for guarded recursive types.

The James construction and π 4 (S 3 ) in homotopy type theory. Author: Guillaume Brunerie.

This paper is part of a recent area of research emerging from Homotopy Type Theory and its facility to formalize homotopy theoretic constructions directly in type theory, what is called synthetic homotopy theory. More precisely, this paper presents the formalization in Agda of the James construction and use it to prove that the fourth homotopy group of the 3-dimensional sphere is of the form Z/nZ, which is a standard result in homotopy theory.

From signatures to monads in UniMath. Authors: Benedikt Ahrens, Ralph Matthes, Anders Mörtberg.

This work is about formalizing the construction of initial algebras in UniMath, which is a core type theory based on the univalent foundations, making use of as few type constructors as possible, originally initiated by Vladimir Voevodsky. The idea of UniMath is to keep the kernel of theory as small as possible, in order to provide a minimal foundational theory. This work about initial algebras is thus a way to add some kind of inductive types in the theory of UniMath and there associated induction principles.

  Preface: Special Issue on Homotopy Type Theory and Univalent Foundations

	Peter Lefanu Lumsdaine • Nicolas Tabareau
	Received: date / Accepted: date
	To Martin Hofmann and Vladimir Voevodsky,


Imeen Ben Salah

Sébastien Kramm

Cédric Demonceaux

Pascal Vasseur

Navigability Graph Extraction From Large-Scale 3D Point Cloud

This paper presents a novel method for summarizing and compression of large-scale 3D models into compact spherical representations. The information is combined into a set of optimized spheres in order to facilitate its use by systems with limited resources (smartphones, robots, UAVs, ...). This vision-based summarizing process is applied in a fully automatic way using jointly photometric, geometric and semantic information of the studied environment. The main contribution of this research is to provide a navigability graph that maximizes the significance of the contents of its nodes while maintaining the full visibility of the environment. Experimental results in summarizing large-scale 3D map demonstrate the feasibility of our approach and evaluate the performance of the algorithm.

I. INTRODUCTION

Digitize the world into 3D models has been an active research topic for decades due to the modernization of 3D sensors. To date, modern mobile scanning systems make it easy to produce High-quality 3D Point Clouds. In other respects, the introduction of High-Definition (HD) [START_REF] Heiko | Autonomous driving in the icityhd maps as a key challenge of the automotive industry[END_REF] and semantic maps have greatly participated in the enhancement of the accuracy of navigation systems. Such HD maps usually occupy a large amount of storage space and require a high processing capacity with severe time constraints. In order to store and transmit effectively this type of maps by navigation systems with limited resources (computation / memory), the size of these maps must be reduced. Hence, we need an efficient algorithm to summarize and compress a 3D map while preserving the essential information for navigation.

II. PREVIOUS WORKS

High-quality maps are required for a wide range of applications, particularly for applications where constant localization or feature tracking is crucial. Hence understanding a maps structure and evaluating map quality is very useful for accurate navigation [START_REF] Zhen | Robust localization and localizability estimation with a rotating laser scanner[END_REF]. Furthermore, In some navigation tasks, setting a full-size map on a mobile device (car, robot, etc.) poses several difficulties in time and memory consumption. To solve this problem there are two possible approaches: map compression or map summarizing using only significant information. Over the past decade, several compression approaches have been proposed in the literature. Several feature-based visual SLAM systems [START_REF] Mur-Artal | Orb-slam: a versatile and accurate monocular slam system[END_REF], [START_REF] Pirker | Cd slam-continuous localization and mapping in a dynamic world[END_REF] have been proposed to sample and compress a map. These types of methods, based on the selection of the keyframe and the bag of Word concepts. Another compression method has been proposed in [START_REF] Hornung | Octomap: An efficient probabilistic 3d mapping framework based on octrees[END_REF]. This method is based on probability mapping using Octrees to eliminate redundant information. Another compression algorithms have been proposed in [START_REF] Dymczyk | Keep it brief: Scalable creation of compressed localization maps[END_REF], [START_REF] Dymczyk | The gist of maps-summarizing experience for lifelong localization[END_REF]. They aim to select 3D points from the initial map based on hundreds of descriptors requiring significant memory size. A novel compression method has been proposed in [START_REF] Contreras | O-poco: Online point cloud compression mapping for visual odometry and slam[END_REF]. This method consists in sampling a point cloud by selecting the features useful for future relocalization. An approach to map reduction was proposed in [START_REF] Steiner | Location utilitybased map reduction[END_REF]. It aims to select only the places that are particularly suitable for localization using the location utility metric. To simplify the process of appearancebased navigation, a selection process is applied to choose the key/reference features in the environment. For instance, in visual memory based approaches, a set of relevant and distinctive areas (images) are acquired and used during navigation for comparison with the current position. In the work of Cobzas [START_REF] Cobzas | Image-based localization with depth-enhanced image map[END_REF], a panoramic memory of images is created by combining acquired images with depth information extracted from a laser scanner. In this image database, only the salient information will be retained [START_REF] Benhimane | Linear and quadratic subsets for template-based tracking[END_REF] without degrading the performance during navigation. In order to build this image database, some techniques have been developed to guarantee the maximum efficiency in the choice of useful information. A spherical representation has been proposed by M. Meilland et al. [START_REF] Meilland | Dense omnidirectional rgb-d mapping of large-scale outdoor environments for real-time localization and autonomous navigation[END_REF]. This spherical representation is built by merging different images acquired by a set of cameras with the depth information extracted from a laser scanner. All existing methods for summarizing maps are based mainly on geometric or photometric characteristics to select the most salient information. However, these characteristics are insufficient for good perception and understanding of the environment. A combination of geometric, photometric and semantic characteristics when selecting information allows us to have a compact, precise and useful summary. Our work aims to perform several navigation tasks using only a map summary of the environment. This map should be not only compact but also coherent with the perception of the agent. To provide this map summary, we propose a new method dealing with large-scale 3D point clouds. The output of our summarizing method is a set of spherical images. Our main contributions are:

• We propose an efficient algorithm for summarizing maps based on geometric, photometric and semantic characteristics. • We formulate map summarizing process as a multiobjective optimization problem.

• We propose a new scalable representation of summarized map using a navigability graph whose nodes are augmented and labeled spherical images. The remainder of this paper is organized as follows. Section III is dedicated to the problem formulation and presents an overview of our approach. The complete map summarization process is described in Sections IV and V. Before conclusion and perspectives, experimental results and discussions are presented in Section VI.

III. PROBLEM MODELING

In this article, we aim at summarizing a 3D point cloud to a compact set of spherical images. Our objective is to reduce the number of spheres while maintaining a high level of significant information for navigation and localization. The final set of spheres must guarantee a compromise between three objectives:

• Maximize the visibility • Maximize the Entropy • Minimize the number of spheres The first goal is to maximize the visibility 𝑉 of the studied environment. The visibility of a 3D point 𝑐 corresponds to all points visible from this point. Geometrically, we can define the visibility of a point 𝑐 by the set of points, such that for each point 𝑝, the segment 𝑝𝑐 does not intersect any obstacle. We define the visibility 𝑉 as: 𝑉 (𝑐) = { 𝑝 ∈ 𝑅 3 / 𝑝 is visible from 𝑐} The second objective is the entropy 𝐸 which expresses the quantity of visible salient information from a viewpoint. We define the entropy of a sphere as the amount of significant information projected onto it [START_REF] Ben Salah | Extraction d'un graphe de navigabilité à partir d'un nuage de points 3d enrichis[END_REF], [START_REF] Salah | Summarizing large scale 3d point cloud for navigation tasks[END_REF]. In our previous work [START_REF] Salah | Summarizing large scale 3d point cloud for navigation tasks[END_REF] it was found that using this entropy we are able to select the optimal viewpoint for representing as best as possible a 3D cloud.

The third objective is the number of spheres which must be minimized in order to reduce the size (cost) of the summary map. To modelize this problem, we introduce some notations. Let us suppose that the 3D map is composed of 𝑁 3D points with color and semantic information. 𝒞 = {𝑃 𝑖 (𝑋 𝑖 , 𝑌 𝑖 , 𝑍 𝑖 ) → {𝑅 𝑖 , 𝐺 𝑖 , 𝐵 𝑖 , 𝐿 𝑖 )}, 𝑖 = 1..𝑁 }. We define the navigable areas Γ as the 2D polygon whose edges represent the borders of the navigable areas. To reduce the data, we propose to represent the different information into some augmented spherical images. To do this, let us consider 𝑎 = (𝑋 𝑔 , 𝑌 𝑔 , 𝑍 𝑔 ) a point in Γ and let us create the augmented 3D spherical image centered in 𝑎 by projecting 𝑉 (𝑎) in the corresponding subcloud into the unit sphere centered in 𝑎. Thus, this spherical image contains all the information which can be seen from 𝑎. The goal of this paper is to reduce the number 𝑛 of augmented spheres needed to describe the 3D maps. Thus, we want to develop a method for creating a minimal set of spheres 𝑔 𝑛 = {𝑔 𝑗 , 𝑗 = 1..𝑛}. These spheres should respect the previous objectives We then propose to formulate this summary process of a point cloud as a multi-objective optimization problem. One of the approaches proposed to solve multi-criteria problems is the lexicographic approach [START_REF] Michael P Fourman | Compaction of symbolic layout using genetic algorithms[END_REF]. This method optimizes the objectives separately and sequentially and generates an optimal solution at every sequential optimization stage.

min 𝑛 𝑔 𝑛 such as { #(∪ 𝑛 𝑗=1 𝑉 (𝑔 𝑗 )) 𝛽.𝑁, 𝛽 ∈ [0..1] 𝐸(𝑔 𝑗 ) 𝜆, 𝜆 ∈ [0..1], 𝑗 = 1..𝑛 (1)
In our case, the objective functions are initially arranged in importance order. First, we should guarantee that the full scene was visited when choosing the best viewpoints by maximizing the visibility. Then we search among these viewpoints that maximize the entropy. Finally, we minimize the number of spheres.

Figure 1 shows the different steps of the optimization process.

A. Visibility Optimization

The first step of the optimization process is the maximization of the visibility. In this stage, we must guarantee that each point of the cloud is visible from at least one point of view.

The first stage of the problem is solved as follows:

𝑓 1 : ⎧ ⎪ ⎨ ⎪ ⎩ 𝒫 * 1 = {𝑃 ∈ Γ}, such as ∪ 𝑃 ∈𝒫 * 1 𝑉 (𝑃 ) = 𝒞 (2)
𝒫 * 1 is a path built from a set of points guaranteeing a maximum visibility of the studied environment. Indeed, each point of 𝒞 is visible by at least one point of 𝒫 * 1 . We propose to adapt the art gallery problem to maximize the visibility. The art gallery problem was presented as a question by the German painter Paul Klee: how much guards do we need to guard a room ?

This problem consists in finding in a polygon the optimal number of guards required to view the totality of the polygon. A variety of this problem is known as the "Watchman route". This problem consists in finding a path inside a polygon Γ so that each point in Γ will be visible from a certain point of this path 𝒫 * 1 . To guarantee a maximum of visibility in our 3D scene, we propose to calculate the watchman route in the polygon Γ that represents the navigable areas of the scene. Several algorithms have been proposed to calculate the watchman route by taking as input a group of target points to visit [START_REF] Carlsson | Finding the shortest watchman route in a simple polygon[END_REF], [START_REF] Dror | Touring a sequence of polygons[END_REF], [START_REF] Packer | Computing multiple watchman routes[END_REF]. The majority of all these algorithms are looking for the optimal watchman route that minimizes the total traveled distance. In our case, we must ensure the visibility of the edges inside the polygon and also the visibility outside the polygon. With this intention, we propose to decompose the start polygon into 𝑘 convex polygons. To simplify the problem, we consider that the visibility through the exteriors edges of the polygons is possible and we consider that the interiors edges of the polygons as obstacles.

To visualize the totality of a convex area, only one point of view (the center) is sufficient. From this statement, the path will be built from the points of view 𝑃 𝑘 selected in each convex area. Several algorithms have been proposed to decompose a polygon in multiple areas. Keil's algorithm [START_REF] Mark | Polygon decomposition[END_REF], [START_REF] Keil | On the time bound for convex decomposition of simple polygons[END_REF]] consists in splitting a polygon into many convex subpolygons by eliminating all reflex vertices. In a polygon, a vertex is called "convex" if the internal angle of the polygon, that is, the angle formed by the two edges at the vertex, is less than 𝜋 radians. otherwise, it is called "reflex".

Keil's algorithm works by examining every possible way to remove the reflexity of these vertices. We suggest the use of Mark Bayasit's algorithm [START_REF] Bayazit | Decomposing polygons into convex regions[END_REF] which is an optimized version of the Keil's algorithm. The best point of view in a convex sub-polygon is the center of this convex area. By connecting each center of the under-polygons with the nearest center, we will obtain the watchman route 𝑃 * 1 . This path enables us to guarantee the total coverage of the studied environment. Figure 2 shows an example of a polygon decomposition in multiple convex areas and the associated watchman route. watchman route in a polygon. This set of points 𝑃 * 1 becomes a new constraint for the optimization of the entropy 𝐸.

B. Entropy Optimization

We intend to find out among the points on the watchman route 𝑃 * 1 those which maximize the entropy 𝐸 while ensuring that the majority of the environment areas are still visible. The expression of this new problem is:

𝑓 2 : ⎧ ⎪ ⎨ ⎪ ⎩ 𝑃 * 2 = {𝑃 𝑙 ∈ 𝒫 * 1 , 𝑙 = 1..𝑛/ 𝐸(𝑃 𝑙 ) 𝜆, 𝜆 ∈ [0..1]} such as #(∪ 𝑛 𝑙=1 𝑉 (𝑃 𝑙 )) 𝛽.𝑁, 𝛽 ∈ [0..1] (3) 𝑃 *
2 is a set of the points (centers of spheres) allowing to find a compromise between both objectives that are visibility and entropy. 𝜆 and 𝛽 are two parameters of regulation of the two criteria entropy and visibility. In order to treat the large-scale point clouds, we propose to split the initial one into several sub-clouds. For each point in 𝑃 * 2 , we define a cylindrical search window of radius 𝑟. Each window is a sub-cloud of 𝑃 containing a part 𝒫 * 1 of the watchman route. The entropy criterion is optimized on 𝒫 * 1 of each sub-cloud. The calculation of the entropy 𝐸 was detailed in our previous work [START_REF] Salah | Summarizing large scale 3d point cloud for navigation tasks[END_REF]. Our goal is to determine the best set of viewpoints allowing the capture of a maximum amount of salient points and guaranteeing a good visibility of the environment.

The entropy optimization is carried out in each sub-cloud on 𝜋 = {𝑃 ∈ 𝒫 * 1 }. In each sub-cloud, we aim to find on 𝜋 the set of spheres that maximize the entropy while keeping a maximum visibility of the scene when we gather the visibility of all spheres on 𝒫 * 1 . First, we evaluate the entropy of the vertices colored with black in Figure 3 and the middle of each pair of consecutive vertices. Among every two consecutive vertices and their centers colored in blue, we only keep two points having the highest entropy. for every sub-cloud, we select vertices with entropy higher than 𝜆. In each iteration, we compute the number of all points visible from the selected vertices colored in violet. Only the spheres whose union of their visibility is higher than 𝛽𝑁 are selected. Figure 3 shows the different steps of this optimization process. The last step

IV. MINIMIZING THE NUMBER OF SPHERES

In this section, we present the last step of our algorithm allowing to minimize of the size 𝑛 of 𝑃 * 2 . The output of this optimization process is the optimal set of spheres 𝑔 𝑛 with minimal size 𝑛 allowing a good visibility of the complete scene and capturing the maximum number of salient points. In addition, we have proposed to calculate the similarity between neighbored spheres to eliminate redundant information. The similarity between two spheres is computed using their statistical correlation. This correlation expresses the rate of variation of photometric, semantic and geometrical information between the compared spheres. In [START_REF] Meilland | Dense omnidirectional rgb-d mapping of large-scale outdoor environments for real-time localization and autonomous navigation[END_REF], this parameter is calculated using the Median Absolute Deviation operator (MAD) which represents the difference (error) of intensity between the two spheres 𝑆 𝑝ℎ𝑜𝑡 . Theoretically, two spheres are considered similar if the value of MAD is lower than a threshold 𝜎. In the same way, we propose to add a semantic measure of similarity 𝑆 𝑠𝑒𝑚 between two spheres. This measure consists in calculating the number of similar pixels with the same labels. We also added a geometrical similarity measure by using the geometrical descriptor FPFH [START_REF] Radu | Fast point feature histograms (fpfh) for 3d registration[END_REF]. By comparing the histograms of each sphere, we obtain a measure of geometrical similarity 𝑆 𝑔𝑒𝑜𝑚 .

𝑆 𝑝ℎ𝑜𝑡 = med(|𝑝(𝑥) -med(𝑝(𝑥))|) 𝑆 𝑠𝑒𝑚 = med(|𝑠(𝑥) -med(𝑠(𝑥))|) 𝑆 𝑔𝑒𝑜𝑚 = med(|𝑔(𝑥) -med(𝑔(𝑥))|) 𝑆 = 𝑚𝑒𝑎𝑛(𝑆 𝑝ℎ𝑜𝑡 + 𝑆 𝑔𝑒𝑜𝑚 + 𝑆 𝑠𝑒𝑚 ) (4)
In these equations, 𝑝(𝑥), 𝑠(𝑥) and 𝑔(𝑥) are respectively the vectors containing the errors. The expression of the problem is the following:

𝑓 3 : {𝑚𝑖𝑛#({𝑃 ∈ 𝑃 * 2 ‖ ∪ 𝑃 𝑉 (𝑃 ) 𝛽.Γ, 𝑆 ≤ 0.5, 𝛽 ∈ [0..1] } (5)
By removing similar spheres that have the same visibility, we will get an optimal set of spheres.

V. EXPERIMENTAL RESULTS

A. Evaluation

To evaluate the quality of a map and estimate its performances during the localization, several solutions have been proposed. The solution suggested by Zhen et al. [START_REF] Zhen | Robust localization and localizability estimation with a rotating laser scanner[END_REF] consists in calculating a requirement called localizability. This criterion is calculated from the geometric characteristics in each direction for each point in the map. We also propose to evaluate the quality of our solution through the calculation of the recall and the precision as defined in our previous work [START_REF] Salah | Summarizing large scale 3d point cloud for navigation tasks[END_REF]. We also calculate the compression rate between the initial cloud and the final set of spherical images.

B. Results

We have applied our method to a large environment. This large-scale point cloud contains over 50 millions of 3D labeled points and represents a trajectory of 80 𝑚. In this dataset, we have 8 classes of labels, namely {1: man-made terrain, 2: natural terrain, 3: high vegetation, 4: low vegetation, 5: buildings, 6: hard scape, 7: scanning artefacts, 8: cars}. An additional label {0: unlabeled points} unlabeled points. In our summarizing process, points labeled "buildings", are considered among the most salient points for localization. This dataset permitted the evaluation of our solution's performance by using all semantic, photometric and geometric characteristics together. Figure 4 shows the decomposition of the polygon (navigable areas) into several convex polygons.

Each color represents a different polygon. The output of this summary process is a compact set of 20 spherical images. The mean distance between all the spheres is around 4 𝑚. We have obtained a compression ratio of 90% of this map. We also tested our algorithm on our own database which describes a part of Rouen city as shown in figure 5. 6. As a result, we have obtained we measured up to 54 spherical images with a mean distance between all the spheres of 3,7 𝑚. Figure 7 shows an example of RGB-D-L spherical images. We have obtained a compression ratio of 98% of this map. Compared to our previous work [START_REF] Ben Salah | Summarizing large scale 3d point cloud for navigation tasks[END_REF], we measured up to 3% improvement in the compression performance. Since the most significant inspiration for spherical representation comes from work of Meilland et.al [START_REF] Meilland | Dense omnidirectional rgb-d mapping of large-scale outdoor environments for real-time localization and autonomous navigation[END_REF], we decided to compare our results with their work. We have found a 2% improvement in the compression ratio due to the optimal positioning of spherical view-points in the scene. The final step is to build the navigability graph by connecting the spheres inside the navigability polygon with edges. Each edge is weighted by the distance between the two corresponding spheres as shown in figure 8. This graph can be used in several applications such as navigation or localisation of mobile robot thanks to its minimal size and the relevance of the data it contains. To evaluate our solution, we have computed Recall and Precision [START_REF] Salah | Summarizing large scale 3d point cloud for navigation tasks[END_REF]. To do that, we have built our ground truth dataset. For each point in the first dataset, we have attributed a label {0: irrelevant for localization, 1: relevant for localization}. Most of the relevant points belong to buildings thanks to their geometric shapes. As a result, we have significantly decreased the size of the map. Nevertheless, we have succeeded to keep a maximum number of salient points. We have achieved a Recall of 60% and Precision of 80 % while guaranteeing maximum visibility of the environment. All the spheres are positioned in a way to capture the maximum possible points belonging to the facades of the buildings. For the first dataset, the obtained set of spheres allow viewing 80% of the scene (𝛽 = 0.8). The choice of the 𝛽 has an impact on the compression ratio. In fact, setting 𝛽 to 1 will favor the visibility on the entropy. Thus the number of selected spheres will increase to cover all the environment and thus their global size. The choice of the 𝜆 has an impact on the relevance of the 3D points in the summary map and consequently on the recall and the precision. Indeed if 𝜆 is set to 0.5 at least half the points will be salient. therefore, we have chosen 𝜆 = 0.7. For the second dataset, we have computed the Localizability of each spherical image, as defined in [START_REF] Zhen | Robust localization and localizability estimation with a rotating laser scanner[END_REF], all spheres are easily localizable since they all have high localizability values. This ensures a good localization in the sphere graph. Our algorithm guarantees maximum visibility and entropy of Reducing the size of the initial map allows to gain in term of memory and time of computation. Indeed we can integrate easily this minimal graph on navigation system with low resources or send it over a network from a server to an agent.

VI. CONCLUSIONS

The developed method throughout this paper allows summarizing efficiently a large-scale point cloud. The summarizing process is based on the extraction of several spherical views representing sub-clouds of the initial map. This spherical representation contains semantic, photometric and geometric information. This new method of summarizing 3D maps allows us to facilitate several navigation tasks when applied in intelligent transportation systems (localization, route planning, obstacle avoidance, ...) by reducing significantly the calculation time and the required memory size. We also believe that using semantic information permits the development of a precise summary map by rejecting unnecessary localization data such as points belonging to dynamic objects (cars, pedestrians, ... ). In our future work, we aim to extend our algorithm to treat the case where the navigable areas that would contain holes. Using the set of spherical views and the navigable area to produce a navigation graph can facilitate multiple navigation tasks especially on navigation systems with limited resources. Using this graph we can propose an adapted path to be followed by the agent according to its mobility capabilities (car, pedestrian, bike, mobile robot, ...).

VII. ACKNOWLEDGMENTS

Fig. 1 .

 1 Fig. 1. Optimization process

Fig. 2 .

 2 Fig. 2. Calculation of watchman route in a polygon

Fig. 3 .

 3 Fig. 3. Entropy Optimization

Fig. 4 .

 4 Fig. 4. Polygon Extraction And Spheres Positioning

Fig. 5 .

 5 Fig. 5. Rouen's city 3D Point Cloud

Fig. 6 .

 6 Fig. 6. Semantic segmentation

Fig. 8 .

 8 Fig. 8. Navigability Graph

This work takes part in the ANR-15-CE23-0010-01 pLaT-INUM project. This project has been funded with the support from the French National Research Agency (NRA).