Aline V Probst

Geneviève Almouzni
email: genevieve.almouzni@curie.fr

Heterochromatin establishment in the context of genome-wide epigenetic reprogramming

Heterochromatin at pericentric satellites, characterized by a specific chromatin signature and chromocenter organization, is of paramount importance for genome function. Reestablishment of this organization after fertilization occurs in the context of genome-wide epigenetic reprogramming. Here, we summarize how the asymmetry in histone variants and post-translational modifications between paternal and maternal genomes and their respective pericentric heterochromatin domains evolves during early cleavage stages in mouse. We draw a parallel between these data and the burst of pericentric satellite transcription that occurs concomitantly with the dynamic reorganization of the pericentric domains into chromocenters in 2-cell embryos. Based on this new angle, we propose that a critical developmental transition at the 2-cell stage allows chromocenter formation by involving non-coding satellite transcripts to trigger specific chromatin changes.

The challenge of heterochromatin establishment

The classical definition of heterochromatin states that, in opposition to euchromatin, heterochromatin corresponds to a chromosomal region that remains condensed through the cell cycle [START_REF] Heitz | Das Heterochromatin der Moose[END_REF] . Within heterochromatin, transcription is generally repressed and heterochromatinization is critical for the transcriptional silencing of repetitive and transposable elements. In mouse, the predominant heterochromatin domain that is discernable by cytological techniques is pericentric heterochromatin [START_REF] Guenatri | Mouse centric and pericentric satellite repeats form distinct functional heterochromatin[END_REF] . Essentially composed of AT-rich (major) satellites (Figure 1a), which are arranged in tandem arrays of up to 2 megabases in length [START_REF] Lehnertz | Suv39h-mediated histone H3 lysine 9 methylation directs DNA methylation to major satellite repeats at pericentric heterochromatin[END_REF][START_REF] Vissel | Mouse major (gamma) satellite DNA is highly conserved and organized into extremely long tandem arrays: implications for recombination between nonhomologous chromosomes[END_REF] , pericentric heterochromatin domains from different chromosomes cluster to form chromocenters in interphase (Figure 1b). This particular architecture is found in most somatic cells, but the degree of clustering and the positioning of the chromocenters in the nucleus can vary between cell types [START_REF] Terranova | The reorganisation of constitutive heterochromatin in differentiating muscle requires HDAC activity[END_REF][START_REF] Solovei | Nuclear architecture of rod photoreceptor cells adapts to vision in mammalian evolution[END_REF] .

Pericentric heterochromatin flanks the centric domain where kinetochores form and has been proposed to play a role in chromatid cohesion and proper chromosome segregation.

At the molecular level, pericentric heterochromatin is characterized by specific epigenetic marks (Figure 2a) including DNA methylation and repressive posttranslational modifications. H3K9 trimethylation, which depends on the histone methyltransferases Suv39h1 and 2 7 , is the classic example of such a repressive mark. This histone mark is bound by the three isoforms of Heterochromatin Protein 1 (HP1α, β, γ) [START_REF] Bannister | Selective recognition of methylated lysine 9 on histone H3 by the HP1 chromo domain[END_REF][START_REF] Lachner | Methylation of histone H3 lysine 9 creates a binding site for HP1 proteins[END_REF] , which in turn recruit the H4K20 histone methyltransferases [START_REF] Schotta | A silencing pathway to induce H3-K9 and H4-K20 trimethylation at constitutive heterochromatin[END_REF] and DNA methyltransferases [START_REF] Lehnertz | Suv39h-mediated histone H3 lysine 9 methylation directs DNA methylation to major satellite repeats at pericentric heterochromatin[END_REF] to establish a transcriptionally repressed chromatin state. Retention of HP1 and spreading of heterochromatin is largely ensured by a self-sustaining loop that entails both the self-association of HP1 into a flexible homodimer and its ability to interact with Suv39h [START_REF] Aagaard | Functional mammalian homologues of the Drosophila PEV-modifier Su(var)3-9 encode centromere-associated proteins which complex with the heterochromatin component M31[END_REF][START_REF] Maison | HP1 and the dynamics of heterochromatin maintenance[END_REF] . Maintenance of this particular chromatin signature is required for proper centromere function since mice deficient in Suv39h methyltransferases lose H3K9me3 and HP1 at pericentric domains and show chromosome missegregation [START_REF] Peters | Loss of the Suv39h histone methyltransferases impairs mammalian heterochromatin and genome stability[END_REF] .

During the cell cycle, in particular following replication, epigenetic marks are diluted after the passage of the replication fork. Therefore, sophisticated mechanisms that exploit the mutual reinforcement of DNA and histone modifications are required to ensure inheritance of chromatin marks and maintenance of pericentric heterochromatin [START_REF] Maison | HP1 and the dynamics of heterochromatin maintenance[END_REF][START_REF] Probst | Epigenetic inheritance during the cell cycle[END_REF][START_REF] Loyola | PTMs on H3 variants before chromatin assembly potentiate their final epigenetic state[END_REF] .

Besides these maintenance mechanisms, one should also consider how heterochromatin is established de novo at pericentric satellites. Establishment takes place during the first cell cycles of development, which are characterized by genomewide epigenetic reprogramming. The most extreme situation is seen for paternal pericentric domains, since the highly specialized male gametes lose somatic heterochromatin marks, which thus have to be regained after fertilization to ensure proper cellular divisions.

In this review, we concentrate on recent work regarding the establishment of heterochromatin during pre-implantation development in mouse. We will discuss how pericentric domains are reorganized from their gamete-specific structures and the important changes in chromatin organization undergone in particular by the paternal pericentric domains in the context of genome wide epigenetic reprogramming. We will then review recent evidence for an implication of a specific post-translational modification of H3.3 and non-coding transcripts in the decisive developmental transition during the 2-cell stage of embryonic development, during which chromocenters form for the first time.

Specific organization of pericentric domains acquired during gametogenesis

Before two specialized gametes meet at fertilization, the chromatin of oocytes and spermatids has undergone important rearrangements during gametogenesis, which also extend to pericentric heterochromatin. During oogenesis, pericentric heterochromatin is remodeled, resulting in rings around the nucleolus in transcriptionally silent full-grown oocytes [START_REF] Zuccotti | Chromatin organization during mouse oocyte growth[END_REF] . This particular organization is reiterated later in the zygote [START_REF] Probst | Structural differences in centromeric heterochromatin are spatially reconciled on fertilisation in the mouse zygote[END_REF] and correlates with the developmental competence of the embryo, as only oocytes with this heterochromatin arrangement develop beyond the 2-cell stage when fertilized in vitro [START_REF] Zuccotti | The analysis of chromatin organisation allows selection of mouse antral oocytes competent for development to blastocyst[END_REF][START_REF] De La Fuente | Major chromatin remodeling in the germinal vesicle (GV) of mammalian oocytes is dispensable for global transcriptional silencing but required for centromeric heterochromatin function[END_REF] . Despite the dissolution of chromocenters, pericentric domains in full-grown oocytes maintain, to some extent, a somatic heterochromatin signature: pericentric chromatin is enriched in H3K9me3 and HP1β but lacks HP1α [START_REF] Meglicki | Constitutive heterochromatin during mouse oogenesis: the pattern of histone H3 modifications and localization of HP1alpha and HP1beta proteins[END_REF] .

In contrast to the oocyte genome, the sperm genome contains small basic proteins, the protamines, which facilitate high-density DNA packaging, and replace histones on all but 1% of the mouse sperm DNA [START_REF] Bench | DNA and total protamine masses in individual sperm from fertile mammalian subjects[END_REF] . Recent evidence suggests that, at least in human, some limited paternal histone marks are transferred to the embryo. In both mouse and human, nucleosomes from regulatory regions of certain genes with important functions in embryonic development are retained in the oocyte [START_REF] Hammoud | Distinctive chromatin in human sperm packages genes for embryo development[END_REF][START_REF] Brykczynska | Repressive and active histone methylation mark distinct promoters in human and mouse spermatozoa[END_REF] . At mouse pericentric heterochromatin domains, which cluster to a single chromocenter in the core of the sperm nucleus [START_REF] Haaf | Higher order nuclear structure in mammalian sperm revealed by in situ hybridization and extended chromatin fibers[END_REF] , replacement of histones by protamines takes place progressively and with slower kinetics than in euchromatin [START_REF] Van Der Heijden | Transmission of modified nucleosomes from the mouse male germline to the zygote and subsequent remodeling of paternal chromatin[END_REF] . Replacement is initiated by a wave of histone acetylation followed by the enrichment of specific histone H2A variants H2AL1/2 at pericentric satellites [START_REF] Govin | Pericentric heterochromatin reprogramming by new histone variants during mouse spermiogenesis[END_REF] . These histone variants are retained in the pericentric domains of mature sperm heads, potentially forming a new DNA-packaging structure devoid of H3/H4 dimers [START_REF] Govin | Pericentric heterochromatin reprogramming by new histone variants during mouse spermiogenesis[END_REF] . In addition, some nucleosomes containing histone H4 acetylated at position K8 and K12 co-localize in small discrete spots with the unique chromocenter in the sperm nucleus [START_REF] Van Der Heijden | Transmission of modified nucleosomes from the mouse male germline to the zygote and subsequent remodeling of paternal chromatin[END_REF] . This suggests a role of acetylated H4 in packaging centric heterochromatin [START_REF] Haaf | Higher order nuclear structure in mammalian sperm revealed by in situ hybridization and extended chromatin fibers[END_REF][START_REF] Van Der Heijden | Transmission of modified nucleosomes from the mouse male germline to the zygote and subsequent remodeling of paternal chromatin[END_REF] , which also contains the centromere-specific H3 variant Cenp-A [START_REF] Palmer | The centromere specific histone CENP-A is selectively retained in discrete foci in mammalian sperm nuclei[END_REF] . Thus, some chromatin-based structural information remains stable in centromere domains during spermatogenesis. One can hypothesize that the centromeric nucleosomal particle present at the centric domain can serve to promote the de novo establishment of correct heterochromatin features in the flanking pericentric domains, potentially through spreading of heterochromatin modifications. The immediate removal of the sperm-specific H2A variants that takes place following fertilization [START_REF] Wu | Testis-specific histone variants H2AL1/2 rapidly disappear from paternal heterochromatin after fertilization[END_REF] precludes their direct involvement in the re-establishment of somatic heterochromatin marks in the zygote. However, whether other architectural features or histone variants (i.e. Cenp-A) in the sperm impact chromatin organization in the embryo remains to be investigated.

In conclusion, important parental-specific reorganization affects pericentric domains during gametogenesis. While in the oocyte most of the somatic epigenetic heterochromatin marks are retained, male pericentric domains largely lose heterochromatin modifications. Therefore a de novo establishment of somatic heterochromatin features is required after fertilization in order to ultimately equalize the pericentric regions of distinct parental origins.

Dynamics of histone variants and epigenetic marks during early cleavage stages

Following fertilization, the oocyte completes meiosis II and extrudes one haploid genome in the form of the polar body, while the sperm genome decondenses. Two pronuclei form in the same cytoplasm, and the zygote resumes the first mitotic cell cycle.

During the entire zygote stage, the two parental genomes remain as separate entities characterized by distinct chromatin signatures and transcriptional competence [START_REF] Adenot | Differential H4 acetylation of paternal and maternal chromatin precedes DNA replication and differential transcriptional activity in pronuclei of 1-cell mouse embryos[END_REF][START_REF] Aoki | Regulation of transcriptional activity during the first and second cell cycles in the preimplantation mouse embryo[END_REF][START_REF] Bouniol | Endogenous transcription occurs at the 1-cell stage in the mouse embryo[END_REF][START_REF] Puschendorf | PRC1 and Suv39h specify parental asymmetry at constitutive heterochromatin in early mouse embryos[END_REF][START_REF] Santos | Dynamic chromatin modifications characterise the first cell cycle in mouse embryos[END_REF] . The two genomes finally align at the same metaphase plate during the first mitosis, but can be found spatially separated within the nucleus at least up to the 4-cell stage [START_REF] Mayer | Spatial separation of parental genomes in preimplantation mouse embryos[END_REF][START_REF] Probst | A strand-specific burst in transcription of pericentric satellites is required for chromocenter formation and early mouse development[END_REF][START_REF] Santenard | Asymmetry in histone H3 variants and lysine methylation between paternal and maternal chromatin of the early mouse zygote[END_REF] . The reason for this spatial separation has remained largely unsolved; however, one plausible explanation could be that the separated genomes sustain differential reprogramming which therefore allows the extensive chromatin remodeling of the paternal genome following fertilization.

Once the sperm has entered the egg, protamines are removed immediately and are replaced by histones to form nucleosomal structures. Since histone incorporation takes place outside the S-phase, the replacement H3 variant H3.3, which can be incorporated in a DNA synthesis-independent manner, is used to package paternal DNA into nucleosomes [START_REF] Santenard | Asymmetry in histone H3 variants and lysine methylation between paternal and maternal chromatin of the early mouse zygote[END_REF][36][START_REF] Torres-Padilla | Dynamic distribution of the replacement histone variant H3.3 in the mouse oocyte and preimplantation embryos[END_REF][START_REF] Tagami | Histone H3.1 and H3.3 complexes mediate nucleosome assembly pathways dependent or independent of DNA synthesis[END_REF] . Accordingly, the H3. In somatic cells, H3.3 is enriched at transcriptionally active regions [START_REF] Ahmad | The histone variant H3.3 marks active chromatin by replication-independent nucleosome assembly[END_REF] and associates preferentially with histone post-translational modifications (PTMs) that mark "active" chromatin [START_REF] Loyola | PTMs on H3 variants before chromatin assembly potentiate their final epigenetic state[END_REF] . Accordingly, the paternal genome is initially hyperacetylated at the time of H3.3 incorporation 28 and shows elevated transcriptional activity during the minor zygotic gene activation [START_REF] Aoki | Regulation of transcriptional activity during the first and second cell cycles in the preimplantation mouse embryo[END_REF][START_REF] Bouniol | Endogenous transcription occurs at the 1-cell stage in the mouse embryo[END_REF][START_REF] Puschendorf | PRC1 and Suv39h specify parental asymmetry at constitutive heterochromatin in early mouse embryos[END_REF] . However K4me3 on H3.3, another modification associated with gene activation, is lacking; this hints at embryo-specific functions of H3.3 independent of transcriptional activation [START_REF] Lepikhov | Differential dynamics of histone H3 methylation at positions K4 and K9 in the mouse zygote[END_REF] . The paternal pronucleus is further devoid of repressive histone marks such as H3K9me2 and me3 [START_REF] Santos | Dynamic chromatin modifications characterise the first cell cycle in mouse embryos[END_REF]44,[START_REF] Liu | Regulation of histone H3 lysine 9 methylation in oocytes and early pre-implantation embryos[END_REF] .

H2A variants are also uniquely distributed during pre-implantation development.

In contrast to somatic cells, H2AZ, macroH2A and the canonical H2A are not or rather poorly incorporated into chromatin during the early cleavage stages and possibly even actively removed after fertilization [START_REF] Chang | A maternal store of macroH2A is removed from pronuclei prior to onset of somatic macroH2A expression in preimplantation embryos[END_REF][START_REF] Nashun | Changes in the nuclear deposition of histone H2A variants during pre-implantation development in mice[END_REF] . In contrast, H2AX is particularly enriched in early embryos and its specific C-terminal domain is responsible for the observed selective incorporation [START_REF] Nashun | Changes in the nuclear deposition of histone H2A variants during pre-implantation development in mice[END_REF] . Furthermore, forced incorporation of H2AZ or macroH2A as fusion protein with the C-terminal domain of H2AX, results in developmental retardation [START_REF] Nashun | Changes in the nuclear deposition of histone H2A variants during pre-implantation development in mice[END_REF] .

Therefore, the absence of H2AZ and macroH2A is correlated with potency and potentially required for the dynamic changes in chromatin organization during early development. This hypothesis is in agreement with the observation that H2AZ

accumulates in differentiating cells of the inner cell mass (ICM) [START_REF] Rangasamy | Pericentric heterochromatin becomes enriched with H2A.Z during early mammalian development[END_REF] and is required for EScell differentiation [START_REF] Creyghton | H2AZ is enriched at polycomb complex target genes in ES cells and is necessary for lineage commitment[END_REF] .

Reprogramming DNA methylation marks also reinforces the epigenetic asymmetry between the two genomes. The paternal genome, which is highly methylated [START_REF] Farthing | Global mapping of DNA methylation in mouse promoters reveals epigenetic reprogramming of pluripotency genes[END_REF] , shows a significant loss of DNA methylation during the first hours after fertilization [START_REF] Mayer | Demethylation of the zygotic paternal genome[END_REF][START_REF] Santos | Dynamic reprogramming of DNA methylation in the early mouse embryo[END_REF] . The reprogramming occurs genome-wide and includes repetitive sequences like LINE elements and early retrotransposons [START_REF] Wossidlo | Dynamic link of DNA demethylation, DNA strand breaks and repair in mouse zygotes[END_REF] . Given the rapidity of this loss, active demethylation processes have been suggested [START_REF] Santos | Dynamic reprogramming of DNA methylation in the early mouse embryo[END_REF][START_REF] Reik | Stability and flexibility of epigenetic gene regulation in mammalian development[END_REF] . Recent studies support this scenario, but suggest rather complex dynamic and sequence-dependent methylation changes involving single-stranded DNA breaks and base excision repair (BER) processes [START_REF] Wossidlo | Dynamic link of DNA demethylation, DNA strand breaks and repair in mouse zygotes[END_REF][START_REF] Hajkova | Genome-wide reprogramming in the mouse germ line entails the base excision repair pathway[END_REF] or the elongator complex to promote paternal demethylation [START_REF] Okada | A role for the elongator complex in zygotic paternal genome demethylation[END_REF] . The implication of DNA repair is supported by the presence of foci of the DNA damage marker γH2A.X in pre-replicative stages that are enhanced upon blockage of DNA polymerases [START_REF] Wossidlo | Dynamic link of DNA demethylation, DNA strand breaks and repair in mouse zygotes[END_REF] , and accumulation of BER pathway proteins in the male pronucleus [START_REF] Hajkova | Genome-wide reprogramming in the mouse germ line entails the base excision repair pathway[END_REF] .

The exact trigger for BER, however, remains to be determined. Deamination of 5methylcytosine (5mC) has long been suggested to play a role in DNA demethylation and recent data have shown an effect on methylation levels during the DNA reprogramming process in primordial germ cells (PGCs) in the absence of the Activation-induced cytidine deaminase (AID) [START_REF] Rai | DNA demethylation in zebrafish involves the coupling of a deaminase, a glycosylase, and gadd45[END_REF][START_REF] Popp | Genome-wide erasure of DNA methylation in mouse primordial germ cells is affected by AID deficiency[END_REF] . An alternative trigger for BER could be the modification of 5mC to the recently identified intermediate 5-hydroxymethylcytosine (5hmC) 53, 55, 59- 61 , which is then removed by a DNA glycosylase. Support for this possibility comes from (i) the difference in demethylation rates observed by 5mC antibodies and bisulfite sequencing, a technique that cannot distinguish between the two modifications, and (ii) the presence of Tet1, one of the enzymes catalyzing this reaction, in PGCs [START_REF] Wossidlo | Dynamic link of DNA demethylation, DNA strand breaks and repair in mouse zygotes[END_REF][START_REF] Hajkova | Genome-wide reprogramming in the mouse germ line entails the base excision repair pathway[END_REF][START_REF] Tahiliani | Conversion of 5-methylcytosine to 5hydroxymethylcytosine in mammalian DNA by MLL partner TET1[END_REF] .

Interestingly, the maternal genome is protected from this initial active DNA demethylation by a process that involves the DNA-binding protein Stella (also known as PGC7) [START_REF] Nakamura | PGC7/Stella protects against DNA demethylation in early embryogenesis[END_REF] . How this protein, which is present in both parental pronuclei, shields maternal DNA methylation globally and how it ensures the selective protection of DNA methylation at imprinted genes in the paternal pronucleus needs to be resolved. Likely candidates for selective recruitment of Stella to DNA are some maternal-specific histone modifications like H3K9me2 and me3 [START_REF] Santos | Dynamic chromatin modifications characterise the first cell cycle in mouse embryos[END_REF] . Following the initial paternal-specific DNA methylation reprogramming, both parental genomes are further subjected to passive DNA demethylation during the subsequent cell cycles 63 before the genome of ICM cells becomes specifically remethylated in blastocysts [START_REF] Santos | Dynamic reprogramming of DNA methylation in the early mouse embryo[END_REF] .

Much has been speculated on the functional meaning of the epigenetic asymmetry between the two parental genomes. For example, it has been suggested that it could facilitate selective transcriptional activation of genes in the paternal or maternal genome and help avoid repeating reductional divisions in a cytoplasm programmed for meiosis [START_REF] Santos | Dynamic chromatin modifications characterise the first cell cycle in mouse embryos[END_REF][START_REF] Wiekowski | Changes in histone synthesis and modification at the beginning of mouse development correlate with the establishment of chromatin mediated repression of transcription[END_REF] . The epigenetic asymmetry potentially contributes to keeping distinct chromatin states at loci subject to genomic imprinting and expressed in a parent-oforigin specific manner [START_REF] Surani | Reprogramming of genome function through epigenetic inheritance[END_REF] . At other loci, however, like the pericentric satellite domains, the different chromatin features must be reconciled.

Distinct chromatin signatures of the two parental pericentric domains

The pericentric domains reorganize dynamically following fertilization to form rings around the nucleolar-like bodies (Figure 2b and 3a) [START_REF] Probst | Structural differences in centromeric heterochromatin are spatially reconciled on fertilisation in the mouse zygote[END_REF][START_REF] Martin | Genome restructuring in mouse embryos during reprogramming and early development[END_REF] , similar to the organization in the oocyte nucleus. Given that this organization is achieved in normal and in parthenogenetic embryos, this supports a developmental stage-specific organization that is initially independent of the parental origin and the epigenetic marks of the parental genomes [START_REF] Probst | Structural differences in centromeric heterochromatin are spatially reconciled on fertilisation in the mouse zygote[END_REF][START_REF] Probst | A strand-specific burst in transcription of pericentric satellites is required for chromocenter formation and early mouse development[END_REF] . Even during reprogramming of embryonic stem (ES) or somatic cell nuclei in eggs, this arrangement of satellite repeats is repeated, suggesting that it is an essential hallmark of the genome-wide reprogramming process [START_REF] Martin | Genome restructuring in mouse embryos during reprogramming and early development[END_REF][START_REF] Maalouf | Trichostatin A treatment of cloned mouse embryos improves constitutive heterochromatin remodeling as well as developmental potential to term[END_REF] . While in the zygote, few chromocenters are occasionally observed in the maternal pronucleus [START_REF] Probst | Structural differences in centromeric heterochromatin are spatially reconciled on fertilisation in the mouse zygote[END_REF] , it is during the 2-cell stage that both parental pericentric domains progressively organize from ring structures into chromocenters (Figure 3a). The chromocenters are then retained during the remaining cleavage stage of pre-implantation development [START_REF] Probst | Structural differences in centromeric heterochromatin are spatially reconciled on fertilisation in the mouse zygote[END_REF][START_REF] Probst | A strand-specific burst in transcription of pericentric satellites is required for chromocenter formation and early mouse development[END_REF] . In addition to the maternal-paternal separation in 2-cell stage embryos, centromeres in most nuclei cluster to one side of the nucleus, adopting a configuration termed the Rabl configuration [START_REF] Rabl | Über Zellteilung[END_REF] . The significance of this spatial organization remains unclear but could reflect the chromosome arrangement in anaphase and exert certain constraints on nuclear organization at this developmental stage [START_REF] Rabl | Über Zellteilung[END_REF][START_REF] Merico | H3K64 trimethylation marks heterochromatin and is dynamically remodeled during developmental reprogramming[END_REF] .

While both parental pericentric satellites retain DNA methylation [START_REF] Santos | Dynamic chromatin modifications characterise the first cell cycle in mouse embryos[END_REF][START_REF] Bernstein | Mouse polycomb proteins bind differentially to methylated histone H3 and RNA and are enriched in facultative heterochromatin[END_REF] , these domains reveal strikingly distinct properties at the level of their histone modifications in the zygote (Figure 2b). Maternal pericentric satellites are marked by H3K64me3, H3K9me3 and H4K20me3 and bind HP1β [START_REF] Probst | Structural differences in centromeric heterochromatin are spatially reconciled on fertilisation in the mouse zygote[END_REF][START_REF] Santos | Dynamic chromatin modifications characterise the first cell cycle in mouse embryos[END_REF]70 . HP1α, undetectable in the oocyte and the zygote [START_REF] Meglicki | Constitutive heterochromatin during mouse oogenesis: the pattern of histone H3 modifications and localization of HP1alpha and HP1beta proteins[END_REF][START_REF] Puschendorf | PRC1 and Suv39h specify parental asymmetry at constitutive heterochromatin in early mouse embryos[END_REF] only starts to be detected in 2-cell embryos [START_REF] Probst | A strand-specific burst in transcription of pericentric satellites is required for chromocenter formation and early mouse development[END_REF] . This points to differential dynamics of these two HP1 isoforms. The paternal pericentric domains, which become enriched in the histone variant H3.3 [START_REF] Santenard | Asymmetry in histone H3 variants and lysine methylation between paternal and maternal chromatin of the early mouse zygote[END_REF] , lack the typical somatic marks including H3K9me3. The low levels of HP1β observed at paternal pericentric satellites further underline an asymmetric distribution compared to the corresponding maternal regions [START_REF] Probst | Structural differences in centromeric heterochromatin are spatially reconciled on fertilisation in the mouse zygote[END_REF][START_REF] Santos | Dynamic chromatin modifications characterise the first cell cycle in mouse embryos[END_REF][START_REF] Santenard | Asymmetry in histone H3 variants and lysine methylation between paternal and maternal chromatin of the early mouse zygote[END_REF] , and suggest the existence of an H3K9me3-independent localization. Thus, analyzing this time window should help to reveal interesting features of inheritance versus acquisition of the three HP1 isoforms during the earliest stages of development.

Instead of the typical pericentric heterochromatin modifications found in somatic cells, paternal pericentric domains are enriched in the alternative repressive chromatin factors, the Polycomb group binding proteins (Figure 2b). The Polycomb repressive complex 2 (PRC2) through its enzymatic activity responsible for trimethylation of H3K27me3 is required for PRC1 binding at certain genes [START_REF] Bernstein | Mouse polycomb proteins bind differentially to methylated histone H3 and RNA and are enriched in facultative heterochromatin[END_REF] and in general to euchromatin in embryos [START_REF] Puschendorf | PRC1 and Suv39h specify parental asymmetry at constitutive heterochromatin in early mouse embryos[END_REF] . However the interdependency of the two complexes might be different at pericentric domains. While paternal pericentric domains in late zygotes acquire H3K27me3 at the time of DNA replication [START_REF] Santenard | Asymmetry in histone H3 variants and lysine methylation between paternal and maternal chromatin of the early mouse zygote[END_REF] , PRC1 components are already found associated with paternal satellite repeats shortly after gamete fusion [START_REF] Puschendorf | PRC1 and Suv39h specify parental asymmetry at constitutive heterochromatin in early mouse embryos[END_REF] . More importantly, embryos deficient for maternal and zygotic Enhancer of zeste homolog 2 (Ezh2), the methyltransferase responsible for H3K27 methylation, still specifically retain PRC1 components at paternal pericentric domains suggesting that mechanisms distinct from those in euchromatin operate at these domains to stabilize PRC1 proteins. In embryos deficient for the histone methyltransferase Suv39h2 both parental pericentric domains are devoid of H3K9me3. Interestingly, in this situation H3K27me3 and PRC1 are also found in maternal pericentric satellites. Therefore, Suv39h2-dependent somatic heterochromatin modifications block the accumulation of PRC1 complexes, which suggests that PRC1 might function as a back-up repressive system [START_REF] Puschendorf | PRC1 and Suv39h specify parental asymmetry at constitutive heterochromatin in early mouse embryos[END_REF] . While methylation of H3K27 seems to be dispensable for PRC1 enrichment at paternal pericentric heterochromatin, the H3 position 27 lysine residue itself is critical for preimplantation development [START_REF] Santenard | Asymmetry in histone H3 variants and lysine methylation between paternal and maternal chromatin of the early mouse zygote[END_REF] . In agreement with the specific enrichment of H3.3 in pericentric heterochromatin [START_REF] Santenard | Asymmetry in histone H3 variants and lysine methylation between paternal and maternal chromatin of the early mouse zygote[END_REF] , the expression of a mutated form of H3.3, but not H3.1, carrying an arginine instead of a lysine at position 27 (K27R), induces developmental phenotypes. Expression of H3.3K27R leads to impaired development, relocalization of pericentric satellites away from the NLBs, loss of HP1β from pericentric domains and defective chromosome segregation. However, the way in which the expression of H3.3K27R, which accumulates specifically at paternal pericentric chromatin, also affects HP1 association to maternal domains remains to be elucidated. Nevertheless, paternal centromere function seems to be particularly compromised in embryos expressing H3.3K27R since the misaligned chromosomes are of paternal origin [START_REF] Santenard | Asymmetry in histone H3 variants and lysine methylation between paternal and maternal chromatin of the early mouse zygote[END_REF] .

Together, these observations imply that the histone H3.3 variant with particular modifications at its K27 residue is critical for proper pericentric heterochromatin organization. This is important during the early stages of mouse embryonic development, before the parental asymmetry is lost and pericentric domains become indistinguishable at the 8-cell stage [START_REF] Puschendorf | PRC1 and Suv39h specify parental asymmetry at constitutive heterochromatin in early mouse embryos[END_REF][START_REF] Merico | H3K64 trimethylation marks heterochromatin and is dynamically remodeled during developmental reprogramming[END_REF] (Figure 3a).

Strand-specific expression of pericentric satellites and their role in chromocenter formation and embryonic development

In recent years a role for non-coding RNA in heterochromatin establishment has emerged. In fission yeast, despite the transcriptional repressed state of heterochromatin, there is clear evidence that transcription of the pericentric outer repeats and their subsequent processing has a role in the establishment of heterochromatin [START_REF] Grewal | Heterochromatin revisited[END_REF]73 .

Specifically, mutant strains in components of the RNAinterference (RNAi) pathway, like the ribonuclease Dicer, show reduced levels of the critical heterochromatin marks, H3K9 methylation and the HP1 homologue Swi6, at the pericentric repeats [START_REF] Volpe | Regulation of heterochromatic silencing and histone H3 lysine-9 methylation by RNAi[END_REF] . The bidirectional transcription of the outer repeats is regulated during the cell cycle and occurs in a discrete time window in S-phase, most likely facilitated by dilution of heterochromatin marks as a consequence of replication of the domain [START_REF] Chen | Cell cycle control of centromeric repeat transcription and heterochromatin assembly[END_REF][START_REF] Kloc | RNA interference guides histone modification during the S phase of chromosomal replication[END_REF] . These transcripts are processed to small RNAs, which then direct histone modifiers to the pericentric repeats to reestablish histone modifications, Swi6/HP1 binding and consequently transcriptional silencing.

In mammals, non-coding RNA molecules have been implicated in establishment of different types of heterochromatin, for example, the Xist RNA on the inactive Xchromosome [START_REF] Masui | RNA and protein actors in X-chromosome inactivation[END_REF] as well as Kcnq1ot1 [START_REF] Terranova | Polycomb group proteins Ezh2 and Rnf2 direct genomic contraction and imprinted repression in early mouse embryos[END_REF] and Air at imprinted loci. These long non-coding RNA molecules are thought to function either via formation of a transcriptionally silent compartment that excludes Polymerase II or through a direct recruitment of repressive chromatin modifiers to the chromatin locus [START_REF] Chaumeil | A novel role for Xist RNA in the formation of a repressive nuclear compartment into which genes are recruited when silenced[END_REF][START_REF] Nagano | The Air noncoding RNA epigenetically silences transcription by targeting G9a to chromatin[END_REF][START_REF] Pandey | Kcnq1ot1 antisense noncoding RNA mediates lineage-specific transcriptional silencing through chromatin-level regulation[END_REF][START_REF] Ponting | Evolution and functions of long noncoding RNAs[END_REF] . At the pericentric domains, a yet unidentified RNA component is required for HP1 binding [START_REF] Maison | Higher-order structure in pericentric heterochromatin involves a distinct pattern of histone modification and an RNA component[END_REF][START_REF] Muchardt | Coordinated methyl and RNA binding is required for heterochromatin localization of mammalian HP1alpha[END_REF] , and non-coding major satellite transcripts of heterogeneous length transcribed by RNA Polymerase II have been found in ES and somatic cells [START_REF] Lehnertz | Suv39h-mediated histone H3 lysine 9 methylation directs DNA methylation to major satellite repeats at pericentric heterochromatin[END_REF][START_REF] Cohen | Transcription of satellite DNA in mouse L-cells[END_REF][START_REF] Gaubatz | Mouse satellite DNA is transcribed in senescent cardiac muscle[END_REF][START_REF] Schoeftner | Developmentally regulated transcription of mammalian telomeres by DNA-dependent RNA polymerase II[END_REF][START_REF] Rudert | Transcripts from opposite strands of gamma satellite DNA are differentially expressed during mouse development[END_REF][START_REF] Lu | Proliferation-dependent and cell cycle regulated transcription of mouse pericentric heterochromatin[END_REF] . While their transcription is cell cycle regulated, in contrast to fission yeast, no direct link could be established between the time of their expression and processing and maintenance of heterochromatin marks during the cell cycle [START_REF] Probst | Epigenetic inheritance during the cell cycle[END_REF][START_REF] Lu | Proliferation-dependent and cell cycle regulated transcription of mouse pericentric heterochromatin[END_REF] . However, the role of transcripts of pericentric major satellites in the initial establishment of heterochromatin organization had not been addressed.

Recent studies have now shown that pericentric satellites are indeed transcribed during early cleavage stages [START_REF] Puschendorf | PRC1 and Suv39h specify parental asymmetry at constitutive heterochromatin in early mouse embryos[END_REF][START_REF] Probst | A strand-specific burst in transcription of pericentric satellites is required for chromocenter formation and early mouse development[END_REF][START_REF] Santenard | Asymmetry in histone H3 variants and lysine methylation between paternal and maternal chromatin of the early mouse zygote[END_REF] . Only limited amounts of transcripts were found in oocytes, suggesting that they are not stored like some other maternal transcripts, but are first transcribed during the minor zygotic gene activation in late zygotes. Major satellites then undergo a peak in expression at the 2-cell stage before being downregulated by the 4cell stage 34 (Figure 3a). Even though the peak correlates with the major wave of gene activation, the observed burst followed by a rapid downregulation is particular to major satellites, as other non-coding RNAs such as TERRA behave in a distinct manner [START_REF] Probst | A strand-specific burst in transcription of pericentric satellites is required for chromocenter formation and early mouse development[END_REF] .

Remarkably, this peak in expression correlates with the dynamic rearrangement of pericentric satellites from ring-structures to chromocenters (Figure 3a), which implies a link between chromocenter formation and the observed expression dynamics [START_REF] Probst | Structural differences in centromeric heterochromatin are spatially reconciled on fertilisation in the mouse zygote[END_REF][START_REF] Probst | A strand-specific burst in transcription of pericentric satellites is required for chromocenter formation and early mouse development[END_REF][START_REF] Martin | Genome restructuring in mouse embryos during reprogramming and early development[END_REF] .

In fission yeast, transcription of pericentric repeats occurs bidirectionally and in mammals both strands are transcribed [START_REF] Rudert | Transcripts from opposite strands of gamma satellite DNA are differentially expressed during mouse development[END_REF] . Intriguingly, the analysis of transcripts with probes that distinguish between the Forward and Reverse strands revealed a strandspecific regulation of the two transcripts. A major peak in expression of the Forward strand during S-phase of the 2-cell stage is followed by expression of the Reverse strand in the G2 phase of the cell cycle. Expression of Forward transcripts takes place even in embryos arrested at the G1/S border. This expression pattern therefore underlies an intrinsic developmental clock rather than strictly depend on cell-cycle progression. The two transcripts differ in their localization, as the Forward transcripts coat parts of the pericentric domains, whereas the Reverse transcripts appear as distinct spots on the pericentric satellite rings (Figure 3b). Forward transcripts are expressed predominantly from the paternal genome and are accordingly reduced in parthenogenetic embryos in which both pronuclei are of female origin and therefore retain somatic heterochromatin modifications at pericentric satellites. Expression at paternal pericentric domains is potentially favored by the lack of somatic heterochromatin marks and the relative enrichment of H3.3 in paternal compared to maternal pericentric satellites [START_REF] Santenard | Asymmetry in histone H3 variants and lysine methylation between paternal and maternal chromatin of the early mouse zygote[END_REF] . Interestingly, one study found H3.3 at pericentric heterochromatin in mouse embryonic fibroblasts (MEFs), where it depends on DAXX 39 .

Less H3.3 incorporation due to depletion of DAXX or H3.3 results in reduced pericentric satellite expression 39 . In contrast, absence of the K27 residue on H3.3 [START_REF] Santenard | Asymmetry in histone H3 variants and lysine methylation between paternal and maternal chromatin of the early mouse zygote[END_REF] or lack of a functional PRC1 complex [START_REF] Puschendorf | PRC1 and Suv39h specify parental asymmetry at constitutive heterochromatin in early mouse embryos[END_REF] cause increased satellite expression in embryos. While the observed increase in expression in H3.3K27R expressing embryos is rather subtle, loss of PRC1 has a clear effect on satellite expression in agreement with the H3K27me3independent recruitment of the PRC1 complex [START_REF] Puschendorf | PRC1 and Suv39h specify parental asymmetry at constitutive heterochromatin in early mouse embryos[END_REF] .

Interestingly, depletion of major satellite transcripts by microinjection of Locked

Nucleic Acid (LNA)-DNA gapmers during the first two cell cycles of embryonic development results in developmental arrest during the G2 phase at the 2-cell stage.

The arrested embryos fail to complete the reorganization of their pericentric satellites into chromocenters, thus supporting the presence of active mechanisms contributing to chromocenter clustering and the functional relevance of pericentric transcripts in this process. However, the exact mechanism by which pericentric satellite transcripts operate remains to be dissected. Given that, during the 2-cell stage, both transcripts are found within the same nucleus, they could potentially form double stranded RNA molecules, which could be further processed to trigger heterochromatin formation.

Indeed, microinjection of a double stranded major RNA molecule can rescue developmental arrest and the lagging chromosome phenotype observed at the 2-cell stage when a mutant form of H3.3K27 is expressed [START_REF] Santenard | Asymmetry in histone H3 variants and lysine methylation between paternal and maternal chromatin of the early mouse zygote[END_REF] . Alternatively, major RNA could recruit and stabilize heterochromatin components.

An intriguing candidate for a chromatin protein to be recruited by major transcripts is HP1, which can bind RNA via its hinge domain [START_REF] Muchardt | Coordinated methyl and RNA binding is required for heterochromatin localization of mammalian HP1alpha[END_REF] and specifically interacts in a posttranslationally modified form with major Forward transcripts (Maison et al, in press).

Recruitment of HP1, together with a histone methyltransferase, could then lead to spreading of heterochromatin marks [START_REF] Maison | HP1 and the dynamics of heterochromatin maintenance[END_REF][START_REF] Probst | Epigenetic inheritance during the cell cycle[END_REF] and to the progressive replacement of PRC1 components by somatic histone modifications. Indeed, embryos expressing HP1β proteins that lack the hinge domain showed HP1β loss from pericentric satellites and chromosome segregation defects similar to embryos expressing the H3.

Concluding remarks and future perspectives

Important new findings have enabled us to define a critical developmental transition during which the organization of pericentromeric repeats in chromocenters is established. The importance, respectively, of major satellite transcription and incorporation of specific histone variants for proper pericentric heterochromatin organization opens up new avenues to understand the possible interdependency of these events. Future work should help identify how these events relate to other major rearrangements, including the sophisticated DNA demethylation mechanisms that are emerging, and determine key elements involved in the parental asymmetry. The situation observed in the mouse embryo provides an example of a major visible rearrangement of pericentric heterochromatin and it will be important to investigate whether similar principles are exploited in other situations where major nuclear reorganization affects these regions, such as in Rod cell photoreceptors or during primordial germ cell reprogramming [START_REF] Solovei | Nuclear architecture of rod photoreceptor cells adapts to vision in mammalian evolution[END_REF][START_REF] Hajkova | Chromatin dynamics during epigenetic reprogramming in the mouse germ line[END_REF] . The parameters evidenced herein may thus prove valuable markers for genome wide reprogramming.

Words: 4 216

Histone H3 variants: In mouse, five major histone H3 variants can be distinguished.

The replicative variants H3.1 and H3.2 are expressed and assembled into chromatin during S-phase, the replacement variant H3.3 is assembled throughout the cell cycle [START_REF] Tagami | Histone H3.1 and H3.3 complexes mediate nucleosome assembly pathways dependent or independent of DNA synthesis[END_REF] , and the centromeric protein A (CENP-A) during early G1-phase [START_REF] Jansen | Propagation of centromeric chromatin requires exit from mitosis[END_REF] . The H3t variant is testis specific.

DNA methylation:

Covalent attachment of a methyl group to a DNA base, in general cytosine.

Epigenetic information:

The classical definition for epigenetic information includes heritable information leading to changes in gene function that take place without alteration to the DNA sequence [START_REF] Riggs | Epigenetic Mechanisms of Gene Regulation[END_REF] . To date candidates for carriers of epigenetic information are chromatin modifications including DNA methylation, histone posttranslational information, histone variants, non-histone chromatin binding proteins, higher order organization and nuclear RNA (reviewed in [START_REF] Probst | Epigenetic inheritance during the cell cycle[END_REF] ).

Polycomb group binding proteins: Repressive chromatin binding proteins, responsible for maintenance of cell identity found in two complexes (polycomb repressive complex 1 and 2). Chromocenters are occasionally observed in maternal pronuclei only [START_REF] Probst | Structural differences in centromeric heterochromatin are spatially reconciled on fertilisation in the mouse zygote[END_REF] and are retained in the polar body (PB). The maternal pericentric domains show somatic heterochromatin marks [START_REF] Probst | Structural differences in centromeric heterochromatin are spatially reconciled on fertilisation in the mouse zygote[END_REF][START_REF] Santos | Dynamic chromatin modifications characterise the first cell cycle in mouse embryos[END_REF]44 and transient enrichment in H3K64me3 70 . They bind HP1β however lack HP1α [START_REF] Santos | Dynamic chromatin modifications characterise the first cell cycle in mouse embryos[END_REF] . Despite the genome-wide DNA demethylation of the paternal genome, DNA methylation is retained in the paternal pericentric rings [START_REF] Mayer | Demethylation of the zygotic paternal genome[END_REF]95 . Paternal pericentric domains are specifically enriched in the histone replacement variant H3.3, show H3K9me1, H3K27me1 and H3K27me3 and are enriched in proteins of the Polycomb repressive complex 1, a repressive back-up system [START_REF] Puschendorf | PRC1 and Suv39h specify parental asymmetry at constitutive heterochromatin in early mouse embryos[END_REF] . HP1β has been observed in some studies at paternal pericentric domains [START_REF] Probst | Structural differences in centromeric heterochromatin are spatially reconciled on fertilisation in the mouse zygote[END_REF][START_REF] Santos | Dynamic chromatin modifications characterise the first cell cycle in mouse embryos[END_REF] , suggesting that HP1β might initially be recruited to paternal satellite DNA in a mechanism independent of H3K9me3.

  3 histone chaperone histone regulator A (HIRA) is observed in the paternal pronucleus at the earliest stages 36 . However, in light of the identification of H3.3 deposition complexes including death domain associated protein DAXX and DEK 39-41 , the implication of other chaperones in H3.3 deposition at this moment in development should also be considered. The selective incorporation of H3.3 in the paternal genome results in asymmetry in histone H3 variants between the two parental genomes. Only a few hours later, during DNA replication, the canonical H3 variants are incorporated for the first time into the paternal genome.

  3 K27R mutant form. In contrast, the chromodomain responsible for binding to H3K9me3 is dispensable for proper HP1β localization[START_REF] Santenard | Asymmetry in histone H3 variants and lysine methylation between paternal and maternal chromatin of the early mouse zygote[END_REF] . Together, these data point towards a decisive developmental transition during the 2-cell stage of embryonic development, during which chromocenters form for the first time in development. This requires both the crucial K27 residue of H3.3 and likely a functional PRC1 complex, as well as regulated expression of the pericentric satellites, in order to ensure proper centromere function on the paternal genome.Presently, it is unclear how the expression of major satellites is controlled in time and space and which promoters or transcription factors are responsible for the strandspecific expression patterns observed in the 2-cell stage embryo. Furthermore, the way in which this expression is rapidly downregulated at the end of the 2-cell stage and whether a combination of transcriptional and post-transcriptional silencing pathways is at work remain to be determined. While the formation of double-stranded intermediates of the two transcripts and their further processing is an attractive hypothesis, strandspecific probes reveal both distinct expression timing and localization and rarely showed co-localization of the two transcripts in the nucleus. However the possibility that under these experimental conditions double stranded RNA is undetectable cannot be excluded. Small amounts of double stranded pericentric transcripts or their degradation products, as shown in Schizosaccharomyces pombe73 , might be sufficient to trigger heterochromatin formation, which is then propagated and consolidated in the subsequent cell cycles by RNA-independent mechanisms. Further work is clearly required to explore the possible connection between RNAi and heterochromatin establishment during mouse development. Given the specific interaction of HP1 with Forward transcripts and the requirement of the hinge domain for proper localization of HP1β in 2-cell embryos, recruitment of HP1 by nascent Forward transcripts to paternal chromatin is another possibility; however both pathways could function in parallel.

Figure 1 .

 1 Figure 1. Pericentric heterochromatin organization in somatic cells

Figure 2 .

 2 Figure 2. Asymmetry in epigenetic marks at pericentric domains in the mouse

Figure 3 .

 3 Figure 3. Dynamic reorganization and expression of pericentric satellites during

Acknowledgments

We apologize for not having been able to quote all colleagues for their contribution and thank M. Casanova, J. Clark and D. Filipescu for critical reading of the manuscript and M. Casanova for help with Figure 3.

Glossary

Heterochromatin: A chromosomal region that remains condensed throughout the cell cycle and that is characterized by a specific chromatin signature.

Constitutive Heterochromatin: Defined in opposition to facultative heterochromatin (e.g. the inactive X-chromosome) as a chromosomal region that on both homologous chromosomes responds to heterochromatinization in the same way during development 91 .

Pericentric Heterochromatin: A heterochromatic region adjacent to chromatin containing the centromere-specific histone H3 variant CenH3 and which is considered to be typical constitutive heterochromatin. However, recent evidence suggests that mouse pericentric heterochromatin does not comply with this definition from the earliest cleavage stages onwards [START_REF] Puschendorf | PRC1 and Suv39h specify parental asymmetry at constitutive heterochromatin in early mouse embryos[END_REF][START_REF] Santos | Dynamic chromatin modifications characterise the first cell cycle in mouse embryos[END_REF][START_REF] Probst | Pericentric heterochromatin: dynamic organization during early development in mammals[END_REF] .

Chromocenter: A cluster of constitutive heterochromatin from different chromosomes that is formed during interphase

Pre-implantation development: Development of a mammalian embryo from the zygote to the blastocyst stage.

Reprogramming:

The reversal of an epigenetic state, resulting in an altered cellular identity. In mammals, genome-wide reprogramming takes place in primordial germ cells (PGCs) and in the early embryo.


Antoine Dutot

Damien Olivier

Guilhelm Savin
email: guilhelm.savin@litislab.fr

CENTROIDS: A DECENTRALIZED APPROACH

Keywords: complex system, self-organization, centroid, ant algorithm

The centroid of a graph is a structure composed of nodes closest from all others. This suggests the presence of center of mass average of all edges, weighted by the local density or specific weight. To compute this centroid in a classic way needs a global view of the graph environment. In this paper, we propose an algorithm using ant colony is proposed to compute an approximate solution of the centroid using a local view of the graph. This allows to study the centroids of complex networks such as protein-protein interaction networks and also those generated by social interactions or Internet, for example.

Introduction

Complex systems are constituted by interactive numerous entities. These entities and their interactions define an interaction network which evolves in the time. We can use a dynamic graph [START_REF] Dutot | Graphstream: A tool for bridging the gap between complex systems and dynamic graphs[END_REF][START_REF] Pigné | Modélisation et traitement décentralisé des graphes dynamiques : Application aux réseaux mobiles ad hoc[END_REF] to model this network and to describe its evolution. Through this graph, we can detect some properties emerging from interactions between entities.

A lot of real networks exhibit non-trivial properties. These complex networks present generally patterns of connection between their entities such as particular degree distribution, high clustering coefficient, hierarchical structure or communities. These features emerge from interactions and evolve in the time, notably, the selforganization defining a group of entities whose members maintain privileged interactions. The challenge is to detect them [START_REF] Bertelle | Organization detection using emergent computing[END_REF] and to define metrics. We assume that the notion of centers and centroids can help us in this approach.

It is impossible to make a reification of the whole graph because of numerous elements which consitute itself, however that is possible to distributed this graph over a set of machines. In such cases, each machine only has a local view of the graph. This local view raises problems when trying to use algorithms needing a global view of the graph.

Let us add another problem, the dynamic of the environment. In fact nodes and edges can appear or disap-pear, and attributes of elements can evolve, that makes obsolete the previously computed solution. Most algorithms are not able to use a previous solution to update it and they have to compute a new solution from scratch.

Ant System paradigm [START_REF] Dorigo | The ant system: Optimization by a colony of cooperating agents[END_REF] allows to define metaheuristic where computation is distributed over a set of agents called ants. These ants explore the graph and make local action on crossed nodes and edges. The wellknown Traveling Salesman Problem is given as practical example of problem that can be solved with an ant system.

We are interested here by finding a structure called centroid of a graph using an ant system. This paper is divided into two parts: section 2 is a state of art about centroid in literature while section 3 describes the ant heuristic and shows results on several graph categories.

Centers and Centroids

The term centroid is used in several scientific fields such as geometry or physics. Centroid is also used in human sciences to summarize, for example, a set of spatial points. The centroid of an object is its barycenter or its geometric center. In the case of a weighted object with uniform density, the centroid of this object is its center of mass. Centroid evokes the idea of a balancing point of the object. The following describes the concept of centroid applied to graphs. We not provide here a full referencing of properties or theorems about centroids but only an approach of what is a centroid in a graph. The concept of center being associated to the one of centroid, it is described to.

Centers and centroids are in literature the object of many works. From C. Jordan giving a proof of their existence in every tree [START_REF] Jordan | Sur les assemblages des lignes[END_REF] to P. J. Slater generalizing their definitions [START_REF] Slater | Centers to centroids in graphs[END_REF], through parts of graph theory books [START_REF] Ore | Theory of graphs[END_REF][START_REF] Harary | Graph Theory[END_REF].

In the following, some notations are used and have to be defined first. G designates a connected graph with V (G) its node set and E(G) its edge set. T designates a tree. op(e, u), with e = (u, v) an edge, designates the vertex v, the opposite of the vertex u according to e. d(a, b) is the distance between two nodes a and b, i.e the number of edges in the shortest path between these two nodes. e(v) is the eccentricity [START_REF] Harary | Graph Theory[END_REF] of a node v and it is Figure 1: Weights of non-leaf nodes in a tree as defined in [START_REF] Harary | Graph Theory[END_REF].

the maximal distance between v and any other node as defined in equation 1. The distance d(v) of a node v is the sum of distance between v and the other nodes as defined in equation 2. The weight of a node v in a tree T is the maximum number of nodes in any branch of v. The figure 1 shows the weight of non-leaf nodes.

e(v) = max x∈V (G) (d(v, x)) (1)
d(v) = x∈V (G) d(v, x) (2)
The concept of center and centroid have been first defined for trees [START_REF] Jordan | Sur les assemblages des lignes[END_REF][START_REF] Ore | Theory of graphs[END_REF][START_REF] Harary | Graph Theory[END_REF] and then extended to graphs.

A node c 0 of a graph G is considered as a central point of G [START_REF] Harary | Graph Theory[END_REF] if its eccentricity e(c 0 ) is minimal for G as defined in equation 3. The set of these central points define the center of G.

e(c 0 ) = min v∈V (G) (d(v)) (3)
There are usually qualified centers. Center of gravity of a graph G is the set of nodes that minimize the function m() defined in equation 4. A mass center of a tree T is a node with minimal weight.

m(v) = 1 |V (G)| x∈V (G) d(v, x) 2 (4)
The centroid of a graph G is a set of nodes called centroid points [START_REF] Harary | Graph Theory[END_REF]. One defines the centroid as the subgraph induced by these centroid points [START_REF] Truszczynski | Centers and centroids of unicyclic graphs[END_REF], i.e the subgraph H of G with V (H) is the set of centroid points and

E(H) = {(u, v)|(u, v) ∈ E(G); u, v ∈ V (H)}.
There are several functions in literature to characterize centroid points. In [START_REF] Harary | Graph Theory[END_REF], the author defines centroid points of a tree T as the nodes with minimal weight, i.e the mass centers of the tree. One defines centroid points of a finite, connected, undirected graph G [6] using distance of a node (equation 2): centroid points are nodes with minimal distance. The figure 2 shows distance value of nodes. The subgraph induced by nodes with minimal distance is the centroid of G.

Slater defines the k-centrum of G [START_REF] Slater | Centers to centroids in graphs[END_REF] allowing to link definitions of center and centroid. "The sum of the klargest vertex distances to" a node v is denoted r k (v) and is defined in equation 5. The set of nodes of a graph G that minimize is called the k-centrum of G and is denoted

C(G; k). When k = 1, r 1 (v) is the eccentricity of v so C(G; 1) is the center of G. When k = n with n = |V (G)|, r n (v) is the distance of v so C(G; n) is the centroid of G. r k (u) = max S⊆V (G);|S|=k s∈S d(u, s) (5)
3 Decentralized algorithm

Definition

We are interested here by describing an heuristic that aims to find centroid of a graph using only local informations. This is an ant-based algorithm [START_REF] Dorigo | The ant system: Optimization by a colony of cooperating agents[END_REF] where an ants colony explores a graph, dropping informations on elements, nodes and edges. These dropped informations are a form of indirect communication, called stigmergy, which allows ants to collaborate to find a solution. In such algorithms, one defines a behavior for ants that we denoted here the step of ants. The algorithm consists in a loop in which the step method of each ant is triggered. The goal of this approach is to provide an algorithm that does not need a global reification of the environment (the graph) and that can handle dynamic of the environment by updating the solution. This algorithm computes an approximate centroid.

We consider that each node has a mass, which is initially the same for all nodes and ants are able to take a part of node mass and to distribute the taken mass on other nodes. The final aim is to increase mass of centroid nodes and decrease mass of outlying nodes, the most massive nodes being parts of the centroid.

A ant a is composed of a few attributes:

pos a , the node position of the ant;

phn max (a) and mass max (a) that are described in the following;

tmass a , the mass transported by a;

-a tabu list used to avoid to back track.

While ants are exploring the graph, they drop pheromones on edges they crossed. For an edge e, the measure phe(e) is the load of pheromones of e and for a node n, phn(n) is the sum of phe(e i ) where e i is an edge adjacent to n. These pheromones evaporate through time according to a factor ρ, so we have:

phe i+1 (e) = phe i (e) × ρ, ∀e ∈ E(G)
where i is the iteration of the algorithm. Each ant a remembers maximum pheromone load phn max (a) and maximum node mass mass max (a) that it has been found. Like pheromones, these two values evaporate through time to keep an up-to-date value reflecting the current state of the environment. The choice of the next edge to cross e i adjacent to the ant position has a probability distribution P (e i ) based on pheromone load and described in equation 6. The constant α helps to control the importance of pheromone load in choosing the next edge to cross. The function η a (e) defined in equation 7 is used to influence ants choice in the aim of leading them to massive nodes according to a parameter λ ∈ [0; 1] : if λ is close to zero, then the probability of edges to be choosen is all the higher as the mass of the opposite node is high, else if λ is close to one, mass of node has no effect in the choice of the next edge.

P (e) = phe(e) α × η a (e) (6)
η a (e) = λ + (1λ) × mass(op(e, pos a )) mass max (a)

The second part of the ant behavior is the ability to distribute node mass on other nodes. Each ant a has an attribute tmass a corresponding to the mass being transported. If tmass a is null, the ant takes a quantity q of the mass of its current position bounded between parameters tmass min and tmass max , else the ant a computes a quantity drop(a, n), defined in equation 8 to drop on its current position n.

drop(a, n) = tmass a × phn(n) phn max (8)
The algorithm is a loop where evaporation of pheromones is made and where the behavior of each ant is triggered as described in algorithm 1. This behavior consists in choosing an edge to cross, cross it and then to transfer some mass. The algorithm describing this behavior is algorithm 2. a, the ant t, mass transported by a p, position of a m, mass of p begin forall edge i adjacent to p do compute P[i] randomly choose edge according to P p = ope(e, p) /* cross chosen edge */ if t == 0 then alea ← random(tmass min , tmass max ) q ← min(alea, m) t ← t + q m ← m-q else q = drop(a, p) t ← t-q m ← m + q end

Results

We compare here results of our ant algorithm with result of a classic algorithm consisting in computing all shortest paths of the graph using a Floyd-Warshall algorithm [START_REF] Cormen | Introduction to Algorithms[END_REF] and then to use the previous results to compute the distance of each node as defined previously in equation 2. The complexity of this algorithm is O(n 3 ) with n is the amount of nodes. Values of parameters used in tests are available on table 5.

To compare results, one has to define a condition to stop the loop of the ant algorithm. For each node, the stabilization of the node is a measure described in equation 10 and computed from previous and current masses and bounded between 0 and 1 that indicates the evolution of the node mass : 0 means that the mass is strongly evolving, 1 means that the mass is stable. This allows the definition of the stabilization of the graph described in equation 11 which is the average value of node stabilization. The algorithm can stop when stabilization of the graph reaches a given threshold ǫ. For tests we used ǫ = 0.99.

dif f t (n) = |mass t-1 (n) -mass t (n)| mass t (n) ( 9
)
stab t (n ∈ V (G)) = min(1, 1 -dif f t (n)) ( 10
)
stab t (G) = n∈V (G) stab t (n) |V (G)| (11)
Several kinds of graph have been considered for tests :

1. Trees built using a preferential attachment algorithm [START_REF] Barabási | Emergence of scaling in random networks[END_REF] as shown on figure 4; 2. Graphs built using a Dorogotvsev Mendes algorithm [12] that produces graphs with a power-low degree distribution ;

3. Two-dimensional grids ;

4. Two-dimensional grids with random holes. When a node v of C A is not in C C , we can define the shortest distance γ(v) between v and any node of C C normalized by the diameter of the graph. The measure Γ is the average value of γ(v) : if equals to 0 then both centroids are confused, else higher is the value, farther are the centroids.

Comparison of results focuses on differences between computation time and between computed centroid. If

Conclusion on results

Two points have to be considered in studying results. The first one is the computation time needed by the algorithm, the second one is the quality of the solution. From results we can observe that the ant-algorithm is significantly faster than the classic algorithm. In addition, ant-algorithm is able to handle dynamic of graph by updating its current solution, whereas the classic algorithm needs to start from scratch. So, in these tests that use static graphs, benefits of the ant algorithm about the robustness of its solution within the ambit of a dynamic evolution of the graph.

Quality of the solution is harder to assess because it can be dependent on how is used this solution. We focus on how the ant-algorithm solution S a matches the classic one S c by observing size difference between these two solutions and the average of shortest distance from nodes in S a to any node of S c , denoted Γ. Unlike time difference, size difference and Γ are more heterogeneous. Best matches is for trees (table 1) followed by graphs generated with Dorogovtsev-Mendes algorithm (table 2): size difference is less than one and Γ is low. For grids (table 3) and incomplete grids (table 4), S a is far from S c : ants find more centroid points which are not close to centroid points of S c .

Conclusion

We have proposed in this paper a new heuristic to compute an approximate centroid of a graph. This algorithm uses an ant system with ants that explore the graph dropping pheromone on crossed edges and moving the mass of nodes.

The algorithm has been applied to several static graph categories and results compared with the one of a greedy deterministic algorithm. This comparison shows that the ant algorithm is significantly faster than the classic one and the quality of its solution depends on the graph category: the centroid of ants algorithm is really close of the classic one for trees but for grid solution is far. However, we have made these tests on static graphs whereas this new ant algorithm aims to be applied on dynamic graphs, providing a robust solution. More, the ant algorithm provides a distributed and decentralized computation of the solution allowing to use it on massive graphs.

Further work

A first future work is to compute centroid of dynamic graphs using this algorithm to test the robustness of the solution.

Then we have to study the impact of parameter values on the algorithm solution and to find a way the determine an optimal value for these parameter according to the graph.

12 Figure 2 :

 122 Figure 2: Distances of nodes. Bold structure is the centroid of the graph.

Figure 3 :

 3 Figure 3: The local view of the environment of an ant: the black node is the current position and gray nodes are its neighborhood.

Algorithm 1 : 2 :

 12 Global ant algorithm Data: -G, the graph, E(G) is the edge set -A, set of ants begin repeat forall edge e ∈ E(G) do phe(e) ← phe(e)×ρ forall ant a ∈ A do execute step of a until stop condition is reached end Algorithm Step of an ant Data:

Figure 4 :

 4 Figure 4: In this tree of 50 nodes, ants have detected the optimal centroid (the biggest black node), i.e the centroid computed by the classic algorithm.

  time A is the computation time of the ant algorithm and time C the one of the classic algorithm, then t ∆ = time Atime C time C express the gain or loss of time of the ant algorithm compared to the classic one. If C A is the centroid computed by ants and C C the one computed by the classic algorithm, then s ∆ = |C A | -|C C | express the size difference between both centroids.

Table 1 :

 1 Results for preferential attachment trees

	nodes	51	101	501	1001
	edges	50	100	500	1000
	t∆	-37.1%	-84.2%	-98.6%	-99.0%
	σ(t∆)	38.03%	5.07%	0.51%	0.00%
	s∆	+0.5	+0.4	+0.5	+0.5
	σ(s∆)	1.13	0.77	0.77	0.87
	Γ	7.7%	6.7%	5.0%	4.0%
	σ(Γ)	8.6%	7.3%	5.2%	4.1%

Table 2 :

 2 Results for dorogovtsev-mendes graphs

	nodes	53	103	503	1003
	edges	103	203	1003	2003
	t∆	-34.2%	-79.1%	-97.9%	-99.0%
	σ(t∆)	19.84%	5.28%	0.30%	0.00%
	s∆	+1.5	+0.7	+0.6	+0.6
	σ(s∆)	2.67	1.13	0.83	0.68
	Γ	10.4%	6.2%	4.3%	3.7%
	σ(Γ)	9.4%	5.8%	3.8%	3.4%

Table 3 :

 3 Results for grids

	nodes	36	121	256
	edges	60	220	480
	t∆	-15.9%	-89.3%	-96.7%
	σ(t∆)	31.99%	2.48%	0.78%
	s∆	+2.9	+11.4	+13.3
	σ(s∆)	3.51	6.83	9.69
	Γ	17.4%	17.8%	13.8%
	σ(Γ)	4.7%	2.4%	1.8%

Table 4 :

 4 Results for incomplete grids

	nodes	22	93	214
	edges	53	292	730
	t∆	+197.8%	-77.8%	-94.4%
	σ(t∆)	122.77%	3.52%	0.88%
	s∆	+4.1	+9.2	+13.7
	σ(s∆)	2.81	5.87	8.87
	Γ	25.3%	19.4%	15.1%
	σ(Γ)	9.1%	5.2%	2.0%

Table 5 :

 5 Parameters value

	ǫ	0.99
	λ	0.50
	α	1.00
	pheromon drop	0.03
	pheromon evaporation	0.86