Master 2 I 2 VB: Infectiologie Immunité Vaccinologie Biomédicaments Master 2 IDOH

Keywords:

• Enormous surface of exchanges: the small intestine exhibits numerous folds (convolutions), and luminal face (internal) of is covered of villi.

• More than 300m 2 of surface in adults (more than a tennis court!).

• In contact with an abundant and complex microbiota : about 10 14 bacteria (including 10 12 bact/g of feces in the colon); nearly 1000 bacterial species per individual (metagenomics of the human microbiota)1 .

• Two parts: small intestine (proximal or anterior) and large intestine (distal or posterior).

• The small intestine: longest part of the tract. Three segments from the stomach to the large intestine Duodenum (receiving pancreatic, hepatic and bile secretions) Jejunum (40 to 90% in length according to species)

Ileum (at the junction to the large intestine)

• Approximately 3.5 fold the length of the body (about 6m in human).

• Location of the final steps of the digestion, allowing absorption of nutriments in the blood circulation.

• The large intestine: colon and rectum, storage of undigested elements (feces).

Comparison of epithelial cells between mucosae

Three main morphological types of epithelial cells, according to the mucosae • Squamous: flat, in alternate stacks. Constitute the sheath of the skin (epiderma) and of internal cavities (mouth, lungs).

• Cuboidal: round-shaped, subject to deformations and ensuring an elastic layer. Bordering the bladder and organs able to retain fluids.

• Columnar: narrow and high cells in single layer. Secretory and absorbing. Bordering the gastro-intestinal tract and forming the ciliated layer of the respiratory tract.

Three types of assembling:

Simples, stratified, pseudo-stratified. • The digestive tube is formed from endoderma : week 4 of gestation.

• Monolayer of epithelial cells with tight junctions : week 10.

• Differentiation of Goblet cells for the production of mucus : week 12.

• First synthesis of a-defensins by Paneth cells : week 13; production of lysozyme : week 20.

• Expression of FcRn from week 18 (transfer of passive immunity, IgG in the amniotic fluid around 12 weeks and in the milk).

• Follicles with B cells, T cells area and Peyer's patches : week 19 (after birth in mice).

Peyer's patches are lymphoid areas covered by a modified epithelium (« M » cells without microvilli but with microfolds).

Morphogenesis and cell differentiation

Mucosal barrier of the intestine : ontogeny The goal is to prevent the crossing of pathogens from the lumen to the lamina propria and blood circulation.

Barrier function of the intestine

Intrinsic barrier: physical characteristics of the epithelium, antimicrobial factors, production of defensins. • Help for digestion (Ruminococcus, Fibrobacter in ruminants).

• Degradation of glycoproteins of the mucus (mutual profit:

nutriments source for the flora and clearing of the mucus).

• Competition towards pathogens: competition for nutriments, production of bacteriocins, interference with signals of the quorum sensing.

• Angiogenesis and development of innate immunity 1 . • low number of accessible PRR at the apical surface of enterocytes.

• Negative regulation of NF-B pathway by commensal bacteria 2 .

2 A Neish et al., Science 2000, 289: 1560-1563.

Signals delivered to limit inflammatory responses of the epithelium: « inflammatory suppression ».

Information and reaction

Intestinal survey The epithelial crossing of microorganisms is possible but under control by sampling:

1. Direct crossing, through epithelial cells.

2. Crossing through M cells surrounding lymphoid follicles. The first encounter of an antigen (Ag) in the intestine triggers an inhibitory process to prevent specific cellular responses to this Ag (TCD4+ et TCD8+) following systemic immunization with the same Ag.

Tolerance to food antigens and to commensal flora

Prevention of a delayed hypersusceptibility to food antigens and to the commensal flora.

Immunosuppression

Oral tolerance

18

• Small intestine mucosae represents the site of induction of oral tolerance.

• Epithelial cells express non conventional MHC I et II molecules and do not possess co-stimulation molecules necessary for Ag presentation induction of anergy ?

• Intestinal T lymphocytes of the lamina propria are mostly effector/memory cells and not naive.

• Epithelial cells that have encountered an intestinal Ag may become suppressive towards specific CD8+ T cells by secretion of IL10 and of TGFb .

Mechanism

Oral tolerance

36

According to the dose of antigen:

• Low dose: immuno-suppression mediated by regulatory T cells (Treg).

• High dose: immuno-suppression mediated by anergy/deletion of Agspecific T cells. • The two a and b subfamilies of defensins are encoded by a cluster of at least 8 genes on the chromosome 8p23 in humans.

• Antimicrobial peptides are ≤ 5 kDa (30 to 50 AA) with a positive net charge and an amphipathic character.

• Most of AMPs display direct bactericidal activity with large spectrum (Gram+ and Gram-), at micromolar concentration in vitro.

• In natura: more than 2800 antimicrobial peptides registered in 2017 (>2000 from animals). Antimicrobial peptide database: http://aps.unmc.edu/AP/main.php 41

Characteristics of AMPs Ancestral components of innate immunity

Other antimicrobial factors:

In mice: CRS (cryptdin related sequence) peptides organized as homo-or hetero-dimers. BPI protein of 55kDa, component of polynuclear neutrophils, able to bind to lipid A of the LPS and to disorganize the outer membrane of Gram-bacteria.

Intestinal enzymes with antimicrobial activity: PLA2 and lysozyme, in the granules of Paneth cells and of neutrophils.

Angiogenin 4 (REG3 gamma).

42

Characteristics of AMPs

Ancestral components of innate immunity AMPs are highly conserved throughout evolution.

• Found in plants and animals (invertebrates and vertebrates).

• From moluscs to birds and to humans: β-defensins are the most ancestral, a-defensins appeared in mammals and θ-defensins restricted to primates.

• Analogy of signal sequences of avian b-defensins and of cytotoxic peptides of snake venom 1 .

• Structural analogy of platypus venom peptides, of the bovine neutrophil b-defensin 1 and of a neurotoxic peptide of sea-anemone.

• First defensins described more than 25 years ago from neutrophils extracts 2 . 1-Zhao et al., 2001, Infect. Immun. 69: 2684-2691. 2-Ganz T… Lehrer RI, 1985, J Clin Invest. 76:1427-35.

AMPs producing cells

Intestinal epithelial cells

AMPs producing cells Polynuclear granulocytes, neutrophils

In human PMNs :

-4 a -defensins stored in the azurophilic granules that will merge with phagosome.

-1 cathelicidin (LL-37) stored in secondary specific granules and delivered to extracellular milieu following degranulation.

The type and the number of AMPs in PMNs of mammals vary according to species.

Secretion of AMPs by PMNs and epithelial cells may be simultaneous (20 AMPs identified in the human skin).

Most of the AMPs are produced as pro-peptides: maturation by cleavage of the pro-region.

48

Structure of AMPs Secoondary structures

Highly compact peptides: a-helix conformation (mainly cathelicidins and some a -defensins) or b-sheet conformation (b-defensins), stabilized by disulfide bridges, or cyclic conformation (-defensins), composed of two hemi-defensins (in primates). The connectivity of the six cysteine residues in the sequence to constitute three disulfide bridges stabilizing the 3D structure : define the sub-family of defensins.

52

Structure of AMPs

a-defensins primary structure

In mice there are twenty isoforms of a-defensins called cryptdins. Cysteine number 1 is the first at the N-terminal extremity.

Structural homologies linked to sequence homologies 53

Structure of AMPs a-defensins mature peptides

In mice, cryptdins are matured in the granules of Paneth cells, with the protease MMP7 (matrix metalloprotease matrilysin).

In humans, the pro-form of HD5 is secreted, then matured by trypsin in the intestinal lumen. The active form can also be secreted 1 . • Cationic molecules-> affinity for the negative charges at the surface of bacterial membranes (more than on the surface of eukaryotic cells).

• Amphipathic molecules (analogous to detergents) -> disorganization of membranes and rupture of electrochemical gradients.

Micro-organisms with high osmotic pressure « blow out ».

58

Biological activity of AMPs

Model of pore formation by peptides with a-helix.

61

Biological activity of AMPs

Resistance of microbes to antimicrobial activity  Modification of the phosphatidyl glycerol with L-lysine (mprF gene of S.aureus).

 Alanylation of teichoic and lipoteichoic acid (dlt operon).

 Acylation of the lipid A of LPS (phoP-phoQ genes, pagP gene of Salmonella).

Reduce the net negative charge of the bacterial membrane limit the access of cationic AMPs

Globally limited bacterial means

Resistance of microbes to antimicrobial activity

  • Barrier function • Survey: sampling, control, information and reaction • Oral tolerance • Balance: homeostasis Master 2 I 2 VB: Infectiologie Immunité Vaccinologie Biomédicaments Master 2 IDOH: Infectious Diseases and One HealthLALMANACH A-C, UMR ISP, INRAE Centre Val de Loire, Nouzilly Tel: +33(0)247427547; mail: anne-christine.lalmanach@inrae.fr Mucosal barrier of the intestine: organisation and role 4 The intestinal tract Mucosal barrier of the intestine : morphology

  protrusions towards the lumen (A), covered by epithelial cells (B), themselves protruding microvilli towards the lumen (C).

8

  Connections between cells performed by specialised intercellular junctions: gap junctions (tubular protein polymers)Transmission of molecular messages between the cells. Synchronized cells...Mucosal barrier of the intestine : histologyStructure of intestinal epithelial cells 9

8

  bodies at the basis of each cilium are formed by centrioles. Transversal section: 9 doublets of microtubules and 2 central singlets constitute the architecture each cilium. Mucosal barriers : epithelial cells • Enterocytes  absorption • Enteroendocrine cells  hormone secretion • Paneth cells  antimicrobial peptide secretion • tuft cells  taste-chemosensory response • goblet cells  mucus production • microfold (M) cells  antigen sampling 12 Epithelial cells Mucosal barrier of the intestine : epithelial cells From: EC Martens et al, Nature Reviews Microbiology (16) 2018. Structure, function and production of the gut mucosal barrier: Model of large intestinal crypt architecture. The large intestine harbours commensal bacteria that ferment dietary fibre into short-chain fatty acids (SCFAs), which are an important energy source for colonic enterocytes and goblet cells. Mucus secreted by goblet cells continually replenishes the mucous layer that overlies the gut epithelium as a first barrier against commensal bacteria and invading pathogens. Secretory immunoglobulin A (IgA) and antimicrobial peptides (AMPs) are secreted into the mucus as a defence against pathogens and potentially harmful commensal bacteria. The colonic epithelium consists of enteroendocrine cells, tuft cells, cup cells, goblet cells and sentinel goblet cells, which are located at the crypt entrance to reduce bacterial encroachment into the crypt. each pole. Intermediate filaments in all the cytoplasm with some anchoring points at the plasma membrane Mucosal barrier of the intestine : epithelial cells 14 The renewing of epithelial cells is performed by proliferation, differentiation and migration of stem cells (SC, Lgr5+) from the basis of the crypts towards the top of the villi. At the top of the villi, epithelial cells die by apoptosis and exfoliate. These mechanisms are under the control of EGF, FGF, HGF et ITF. Mucosal barrier of the intestine : epithelial cells Renewal of intestinal epithelial cells: recent advances Adult stem cells (Lgr5+) of the intestine: relocation keeps up the numbers. From Azkanaz, M. et al. Nature 607, 548-554 (2022) • Labelling of Lgr5+ stem cell, either at the border or at the basis of the crypt. • Repeated imaging of the same crypt in a live mouse over many weeks, combined with mathematical modelling: Active border SC relocation in the small intest : retrograde migration (Wnt-dependent) Absence of retrograde migration in the crypts of the large intestine 16

  patches: dome with M cells surrounding lymphoid follicles Disseminated lymphoid follicles Immune cells of the lamina propria 18 Extrinsic barrier: to limit the quantity of pathogens reaching the surface of intestinal epithelium. Proteolysis and acidic stomach 

•

  1 L.Hooper et al., 2001, Science, 291: 881-884.Barrier function of the intestineComponents ensuring a barrier function 20 Prevent an excessive response to food antigens and to the harmless commensal flora (tolerance) Establish a protective immune response against intestinal pathogens (reaction) Barrier function of the intestine Components ensuring a barrier function 21 Sampling, control, information and reaction Sampling allows immediate reaction if pathogen recognition: innate immunity Call for specific help if outflanking enemy: adaptive immunity Intestinal survey PRR = pattern-recognition receptors Toll-like receptors TLR1-TLR2 -> Lipoproteins TLR4 -> LPS TLR5 -> Flagellin TLR9 -> non-methylated CpG motifs of bacterial DNA Nod-like receptors (NLRs) NOD1, NOD2 (NF-kB pathway) NLRP3, NLRC4 (Caspase 1 pathway) On enterocytes, phagocytes and dendritic cells (DC) 22 Discrimination between beneficial commensal flora and harmful pathogens: recognition of molecular patterns at the surface of microbes (MAMPs) by receptors (PRR) MAMPs = Microbe-associated molecular patterns LPS by PRR trigger inflammatory response (inflam. cytokines) and the production of chemokines to recruit phagocytes. Stimulation of the epithelium by PAMPs: activation of the NF-B pathway. Expression of IL-8 (CXCL8), IL-1b, GMCSF, CXCL1 et MCP-1 (CCL2). Recruitment of polynuclear neutrophils, macrophages and activation of the inflammatory response : IL-1, IL-6, TNF-a, … Innate immunity cells are called to fight: phagocytes first! Abnormally enhanced access to PRR of enterocytes. IBD (inflammatory bowel disease): Crohn 's disease and ulcerative colitis. Reaction to commensal bacteria. « Hyper-response » to MAMPs (NOD2= susceptibility gene to Crohn's disease) 1,2 . Development of IBD in IL-2 deficient mice. Induction of human b-defensins 2 and 3 is blocked during Crohn'Weak exposure of molecular patterns (MAMPs): commensal MAMPS are covered by IgAs 1 . 1 AJ Macpherson & T Uhr, Science 2004, 303:1662-1665.

29«

  Camouflage » of the commensal flora : role of secretory IgA Produced mainly by B220+ IgM+ lymphocytes, plasmacytes. 1 and 2: binding of dimeric IgA (dIgA) to polyIg receptor (pIgR) at the basolateral side of the epithelium and transcytosis (via endosomal network). 3: Cleavage of the large extracellular domain of pIgR, releasing secretory IgA linked to the secretory component into the intestinal lumen.

  lymphocytes (IEL): mostly CD8+, TCRab or TCR  positive with restricted repertoire non conventional MHCI of intestinal epithelial cells (IEC).The trafficking of primed lymphocytes : via the lymph thoracic duct then blood circulation and mucosal homing from high endothelial venules.IELs express aEb7 integrin interacting with E-cadherin of IECs (intercellular adhesion).T-lymphocytes of the lamina propria are effector / memory cells coming from the migration of primed T-cells: Priming by dendritic cells (DC) in lymphoid follicles and draining lymph nodes recirculation and mucosal homing of T-cells.Information and reaction towards specific immune responseIntestinal surveyT and B lymphocytes stimulated in the MALT (mucosa associated lymphoid tissue) acquire receptors for mucosal homing: a4b7 integrin.

Regulatory

  of mucosal innate immunity: intrinsic barrier function.• Two major families of AMPs in animals : Cathelicidins: large diversity of primary and secondary structure, but a highly conserved pro-region (N-term domain cathelin, C-term domain LL37 in humans). Defensins: a, b, or . About 50 a and 90 b in mammals.

  Intestinal epithelial cellsDefensins identified from Paneth cells: a-defensins in the secretory granules.Strategic position to protect multipotent stem cells of the epitheliumDifferentiated enterocytes of the large intestine can produce b-defensins and cathelicidins. Localization of HD5 mRNA (left, silver staining) peptide (right, brown peroxydase product) 1 . 1 G. Diamond & C.L. Bevins, Clin. Immunol. Immunopathol. 1998, 88: 221-225. E. Porter et al. Infect. Immun. 1997, 65: 2389-2395. 44 AMPs producing cells Paneth cells granules contain adefensins that can be released upon stimulation. 1 Salzman N et al, 2003, Nature, 422: 522-526 HIS, antisense RNA probe Transgenic mice for human a-defensin 5 (HD5) exhibit low intestinal colonization by Salmonella when inoculated orally, by comparison to control mice 1 .

1D

  Ghosh et al., 2002, Nature Immunol. 3: 583-590.Production of the active form by cleavage of the proin vivo: KO mice for the genes of AMPs Camp -/-mice: susceptible to Streptococcus, herpes simplex virus, Escherichia coli and vaccinia virus. mBD1 -/-mice: susceptible to Haemophilus influenzae, Staphylococcus.

62

  Biological activity of AMPsSecretion of proteases for the degradation of AMPs External membrane protease of S. Typhimurium (pgtE)  V8 protease and aureolysin of S. aureus (targeting LL37) Efflux pumps to remove AMPs  mtrCDE gene of Neisseria gonorrhoeae  qacA gene of Staphylococcus aureus

Lepage P. et al,

2013, Gut, 62:146-158.

Y. Ogura et al.,

2001, Nature, 411: 603. 2 J. P. Hugot et al., 2001, Nature, 411: 599.

AMPs producing cells

Epithelial cells express b-defensins constitutively or inducibly (hBD=human beta-defensin):

-hBD1, hBD3 and hBD4 expressed constitutively by small and large intestine epithelial cells.

-hBD2 expression induced by inflammatory cytokines, by IL-17 1 , by PAMP receptors pathways: TLR2 and TLR4 2 , NOD2/CARD15 3 .

-hBD2 expression stimulated by BCG 4 , by Campylobacter jejuni 5 … 1- Kao et al. 2004, J. Immunol. 173 : 3482-3491. 2-Vora et al. 2004, J. Immunol. 173 : 5398-5405. 3-Voss et al. 2006, J. Biol. Chem. 281 : 2005-2011. 4-Mendez-Samperio et al. 2006, Cell Immunol. 239, 61-66. 5-Zilbauer et al. 2005, Infect. Immun. 73 : 7281-7289.

Intestinal epithelial cells

46

AMPs producing cells

Reguation of expression

• Cathelicidins are less regulated by TLR and/or cytokines.

• Cathelicidins are positively regulated by histones acetylation.

• Cathelicidins are positively regulated by vitamin D (1,25 D3).

• Di-hydroxy vitamin D3 is able to positively regulate TLRs expression.

Feed back loop to amplify production of various AMPs

Biological activity of AMPs Some peptides are cell-penetrating peptides (CPP) and can bind to DNA : inhibition of replication, transcription, and bacterial destruction.

Mechanisms of antimicrobial activity 60

Biological activity of AMPs

No deleterious effect on host cells: hypothesis

• Less negative charges at the surface of eukaryotic cells :

phospholipids with negative polar head (PS) are found in the inner leaflet of the lipid bilayer.

• Cholesterol content of eukaryotic (not prokaryotic) membranes ensures a rigid lipid bilayer less prone to disorganization.

• Protective role of serum proteins, of the extracellular matrix.

• Cytotoxic concentrations for eukaryotic cells are largely above microbicidal concentrations (MIC LL37 and b-defensins in the order of µM, cytotoxic concentration > 30µM) .

63

Biological activity of AMPs

A unique human a-defensin 6: not antimicrobial

Biological activity of AMPs

Much more than antimicrobial: chemotactic activity Measurement of the chemotactic activity: cell migration assay using the « Transwell® » system.

Counting of the cells in the lower chamber.

Biological activity of AMPs

With chemotactic activity for DCs and T cells, defensins may link innate and adaptive immunity.

hBD2 and CCL20 display similar 3D structure and share the same affinity for the CCR6 receptor Recruitment of dendritic cells (DC) and T cells.

Remark: Conversely, some chemokines display direct bactericidal activity analogous to AMPs.

HNP1 and HNP2 (a-defensins) hBD3 and hBD4 (ß-defensins)


Mucosal response to pathogenic enterobacteria 1 Master 2 I 2 VB: Infectiologie Immunité Vaccinologie Biomédicaments

Keywords: normal residents. 4 major phyla: firmicutes (Lactobacillus spp., Clostridiales) spp.), Bacteroidetes, Actinobacteria, Proteobacteria., Pathobionts : potentially harmfull when weakness of the barrier. Enterococcus spp., Clostridium difficile., Enteric pathogens : 1.5 million deaths worldwide in 2012 Secretory diarrhoea: Vibrio cholerae, E.T.Escherichia coli, inhibit enterocytes Na+ transporter, increase Cl-secretion Inflammatory diarrhoea: Salmonella spp., Campylobacter spp., neutrophilic infiltrate

of a peculiar host-Salmonella relationship: Intestinal carriage in birds. 2 • Microbial communities in the gut • Salmonella as emblematic pathogenic enterobacteria • First contact of Salmonella with intestinal epithelium -Initial steps -Epithelial sensing -Mucosal response • The fate of Salmonella after epithelial crossing • Systemic response to infection, adaptive immunity • Critical cytokine response: major role of IFN- Mucosal response to pathogenic enterobacteria

Microbial communities in the gut

Microbial communities in the gut

Recognition of commensal motifs by host receptors downregulates inflammation and induce production of antimicrobial proteins (Reg3, a-defensins) and IgA :

• TLR2 of DCs recognizes polysaccharide A (PSA, capsular) of Bacteroides f. and induce regulatory T cells (Tregs, producing IL10).

• Bacteroides t. inhibits pro-inflammatory cytokines transcription by exporting NFB (p65) via PPARγ from epithelial cell nucleus.

• Sampling of commensal bacteria by CX3CR1+ mucosal dendritic cells induce the production and secretion of sIgA (neutralizing bacteria and toxins in the lumen). Salmonella as emblematic pathogenic enterobacteria • IL-1 and IL-18 (via caspase 1), IL-23

• IL-6 • TNF-a 21
First contact of Salmonella with intestinal epithelium

Epithelium response to Salmonella

The IL-23 -T H 17 axis:

• IL-23: production by TLR and NLR stimulated mucosal DCs  Salmonella Typhimurium: acylation of lipid A, modification with aminoarabinose.

Salmonella strategies of survival and dissemination

Live happy, live hiding : stay invisible from anti-bacterial factors  Persistance inside macrophages within phagosomes: inhibition of the fusion with lysosome.

 Probability of dissemination via circulating macrophages and dendritic cells.

24

First contact of Salmonella with intestinal epithelium  Induction of apoptosis/pyroptosis in macrophages (via SipB on caspase1) and/or inflammatory response (IL-1).

26

 TLR4 is critical for early cytokine production and killing of bacteria by macrophages. TLR4 and TLR2 are involved in the control of bacterial burden and the host survival1, 2

The fate of Salmonella after epithelial crossing  Important bacterial burden reduced by neutrophils: by production of ROS, nitric oxide, antimicrobial peptides,

Salmonella in circulating cells

 Salmonella does not multiply within DC but may stay and multiply within inactivated macrophages.

 Extra-intestinal dissemination of Salmonella within phagocytes/DC CD18+ 2 according to the serotype. In the spleen, 2 days after oral infection (in mice)

In the spleen, 5 days after oral infection (in mice)

Activation, probable emigration towards mucosal effector sites. Kirby et al. J. Immunol. 2002, 169:4450-4459. 32 Systemic response to infection, adaptive immunity

Lessons learned from murine models of Salmonella infection

Epithelial receptors towards immune cells:

• ICAM1: constitutive and up-regulated by Salmonella In gamma-interferon gene knock out mice (IFN- -/-), oral inoculation with an attenuated strain of Salmonella * :

• No resolution of the infection but septicemia in 2 weeks

• No increase in CD4+ and CD8+ T cell populations Comparison of chicken inbred lines divergently selected according to the level of Salmonella colonization in the caecum.

•
• Oral inoculation of S. Enteritidis.

• Analysis of bacterial burden: bacterial counts in the caecum.

• Analysis of expression of immune response target genes (in the caecal

  From:Perez-Lopez et al., Nature Reviews Immunology, 2016, 16:135-148.• Microbial communities in the gut • Salmonella as emblematic pathogenic enterobacteria • First contact of Salmonella with intestinal epithelium -Initial steps -Epithelial sensing -Mucosal response • The fate of Salmonella after epithelial crossing • Systemic response to infection, adaptive immunity • Critical cytokine response: major role of IFN- Mucosal response to pathogenic enterobacteria 7 8

Shigella

  and Listeria engulf inside the cell, in a vacuole. • Microbial communities in the gut • Salmonella as emblematic pathogenic enterobacteria • First contact of Salmonella with intestinal epithelium -Initial steps -Epithelial sensing -Mucosal response • The fate of Salmonella after epithelial crossing • Systemic response to infection, adaptive immunity • Critical cytokine response: major role of IFN- Mucosal response to pathogenic enterobacteria 15 Epithelium sensing of Salmonella At the surface: LPS sensing by TLR4 -> signal transduced via MyD88 and TRIF. Intracellularly: Muramyl dipeptide (MDP) sensing by NLR NOD2; T3SS molecules sensing by NLR NOD1 and NOD2 -> signal transduced via CARD Kinase (RICK) Salmonella with intestinal epithelium When Salmonella reaches the sub-epithelial area: Flagellin sensing by TLR5 expressed -at the basolateral surface of epithelial cells => CCL20 prod 1 -at the surface of dendritic ¢ (CD11c+) of the lamina propria => IL23 prod Activation of NF-B pathway Flagellin sensing inside resident macrophages by NLRC4 2, 3 Activation of Caspase 1 (IL1 and IL18 secretion) • Microbial communities in the gut • Salmonella as emblematic pathogenic enterobacteria • First contact of Salmonella with intestinal epithelium -Initial steps -Epithelial sensing -Mucosal response • The fate of Salmonella after epithelial crossing • Systemic response to infection, adaptive immunity • Critical cytokine response: major role of IFN- Mucosal response to pathogenic enterobacteria 19 Production of chemokines attracting immune cells: • IL-8 (CXCL8) for neutrophils • MCP-1 (CCL2) for monocytes • MIP-1a (CCL3) for neutrophils and macrophages • CCL20 (MIP3a) for immature dendritic cells Correlates with histological observation of phagocytes infiltrate in infected intestinal lamina propria. Phagocytes called to fight. 20 Epithelium response to Salmonella First contact of Salmonella with intestinal epithelium Production of inflammatory cytokines:

2

  Vazquez-Torres A. et al., Nature 1999, 401: 804-808.  Apoptotic bodies generated after macrophage infection and induced cell death: taken up by bystander dendritic cells 1 .1Yrlid and Wick, 2000, J. Exp. Med. 191:613-624.Phagocytes may serve as vehicle27 The fate of Salmonella after epithelial crossing Phagocytes are in the heart of the fight 28 Infected liver: Hematoxylin/Eosine staining. Granuloma aspect (neutrophils), full of bacteria. Infected macrophage : Scanning electron microscopy. Salmonella attached. Murine infected cell: Transmission electron microscopy. Intra-vacuolar Salmonella. The fate of Salmonella after epithelial crossing Salmonella found in mesenteric lymph nodes (24-48h p.i.) then in spleen and liver.  Salmonella found in Peyer's patches, 6h post infection per os. The fate of Salmonella after epithelial crossing • Microbial communities in the gut • Salmonella as emblematic pathogenic enterobacteria • First contact of Salmonella with intestinal epithelium -Initial steps -Epithelial sensing -Mucosal response • The fate of Salmonella after epithelial crossing • Systemic response to infection, adaptive immunity • Critical cytokine response: major role of IFN- Mucosal response to pathogenic enterobacteria 31 Bacterial multiplication which does not stay unseen, cells of the secondary lymphoid organs wake-up: Decrease of T-cell populations (TCRa+, NK1.1-).  Decrease of the NK population (NK1.1+, TCR a-)  Decrease of the NKT population (NK1.1+, TCR a+)

  CD1d: Presentation of bacterial lipid antigens (mycobacteria) 33 Systemic response to infection, adaptive immunity Lessons learned from murine models of Salmonella infection Systemic response to infection, adaptive immunity Lessons learned from murine models of Salmonella infection 34  Primed T cells detected 6-12h in Peyer's patches and 9-12h in mesenteric lymph nodes of mice after oral infection 1 .  Priming initiated by CD11c+ CCR6+ dendritic cells attracted to the infected epithelium by CCL20.  Mice lacking T-bet+ Th1 cells are unable to resolve the infection 2 .  Th1 cells are major source of IFN-.  Neutrophils have been recently pointed out as a source of IFN- 3 .  Human genetic disorders linked to fatal salmonellosis : invalidated IFN- and IFN-R genes 4 . 1 Mc scorley SJ et al, 2002, Immunity, 16(3):665-77.

•

  No increase in expression of MHCII and VCAM1Deficiency of intestinal and systemic immunity without IFN- * Bao S. et al.,Immunology 2000, 99: 464-472. 35 Systemic response to infection, adaptive immunityLessons learned from murine models of Salmonella infection• Microbial communities in the gut • Salmonella as emblematic pathogenic enterobacteria • First contact of Salmonella with intestinal epithelium . et al., J. Exp.Med. 2000, 192: 1237-1248. 37 Macrophages as major host target cells of Salmonella: the success of the host fight depends on their activation by IFN-.Bacterial clearance under the control of host IFN-From Lalmanach AC and Lantier F, Microbes and Infection, 1999.General overview of what happens in infected sites38 Bacterial clearance under the control of host IFN- From JR Kurtz, JA Goggins and JB McLachlan Immunology Letters, 2017 Intestinal carriage of Salmonella in birds • Resistance of birds to Salmonella intestinal carriage • Role of defensins in the protection of birds • Insights into protective role of microbiota Master 2 I 2 VB: Infectiologie Immunité Vaccinologie Biomédicaments Master 2 IDOH: Infectious Diseases and One Health LALMANACH A-C, UMR ISP, INRAE Centre Val de Loire, Nouzilly Tel: +33(0)247427547; mail: anne-christine.lalmanach@inrae.fr Illustration of a peculiar host-Salmonella relationship: Intestinal carriage in birds. • Intestinal carriage of Salmonella in birds • Resistance of birds to Salmonella intestinal carriage • Role of defensins in the protection of birds • Insights into protective role of microbiota Master 2 I 2 VB: Infectiologie Immunité Vaccinologie Biomédicaments Master 2 IDOH: Infectious Diseases and One Health LALMANACH A-C, UMR ISP, INRAE Centre Val de Loire, Nouzilly Tel: +33(0)247427547; mail: anne-christine.lalmanach@inrae.fr 44 Resistance of birds to Salmonella intestinal carriage Identification of host factors involved in the resistance: genes differentially expressed between resistant (R) and susceptible (S) birds Approach:

•

  and AvBD7 (in agreement with data from heterophils ICM/MS) 52 Role of defensins in the intestinal protection of birds Preparation of AvBDs for structural and functional analysis  Extraction and purification from chicken bone marrow, rich in AvBDs Separation and analysis procedures: et al. 2009. Antimicrob Agents Chemother. 53: 4647-55. 61 Insights into protective role of microbiota First elements for consideration  Phenotype of resistance to caecal infection : linked to the microbiota composition • Transferable trait, through transfer of adult microbiota: An adult flora (from at least 3 weeks old chickens) given to newly hatched chicks protects against subsequent infection and does not induce inflammation Varmuzova K et al., Frontiers in Microbiology, 2016. 62 Insights into protective role of microbiota Future prospects Standardize and preserve an efficient commensal consortium against Salmonella infection • Deciphering mechanisms of protection of the host  Bacterial metabolites involved,  Immune response factors involved,  Crosstalk between them…

Salmonellosis, a major public health concern

  Associated to consumption of contaminated food products from animals

	Salmonella as emblematic pathogenic enterobacteria
	Meet, ham,  Two major Salmonella serotypes (more than 2/3 recorded Fish and saussages… derived strains), (poultry, pig, products S. Enteritidis 20,2% S.Typhimurium beef and others) 9,2%
	Ubiquist: many host animal species (by contrast to
	host specific serotypes inducing systemic typhoid disease) Sea food Cheese
	5,4%	4,6%
	 70% of foodborne outbreaks
	 Stagnation of the sanitary situation since 5 years

• Enteric pathogens : Salmonellosis second most commonly reported zoonose, after campylobacteriosis, in humans (ECDC-EFSA source 2019: doi: 10.2903/j.efsa.2019.5926. European Union Summary Report on Zoonoses, EFSA Journal 2014;12(2):3547 9 •

major concern for veterinary and public health Salmonellosis : a One Health problem

	Eggs and
	egg-derived
	products
	22%
	Fruits and
	vegetables
	5,4%

• Causative contamnated food products in Europe in 2012 10 Salmonella as emblematic pathogenic enterobacteria Salmonellosis, a

contact of Salmonella with intestinal epithelium

	• Microbial communities in the gut
	• Salmonella as emblematic pathogenic enterobacteria
	• First -Initial steps
	-Epithelial sensing
	-Mucosal response

detection of bacterial products in the lumen: LPS by TLR4. Bacterial amyloid curli fibrils and lipoproteins by TLR2. Epithelial cell surface remodelling by Salmonella : to favor internalization by triggering process

	First contact of Salmonella with intestinal epithelium
	Initiated by adhesion (fimbriae of Salmonella)
	Involvement of the Type Three Secretion System (T3SS) of Salmonella,
	encoded by SPI1:
	•SipB + SipC form a « syringe » inside the host cell membrane.
	•SopE injected activates GTPases .
	•Actin polymerization stabilized par SipA , negative regulation by SptP.
	Induction of membrane remodelling, by modifications of
	cytoskeletton. Formation of pseudopodes and internalization
	Remark: If Salmonella is devoid of TTSS, entry by « zippering process ».
	13
	Initial steps
	 Luminal capture by
	dendritic cells (dendrites
	expressing tight junction
	components) 1 .
	 Active entry through M
	cells and epithelial cells:
	Salmonella TTSS

• The fate of Salmonella after epithelial crossing • Systemic response to infection, adaptive immunity • Critical cytokine response: major role of IFN- Mucosal response to pathogenic enterobacteria 11 First contact of Salmonella with intestinal epithelium 1 Rescigno M. et al., Nat. Immunol. 2001, 2: 361-367.

12  Possible

Initial steps Comparison between Salmonella, Listeria and Shigella Once inside, Listeria destroys the vacuole (with LLO) to reach the cytoplasm, aggregates actin (with ActA) to move in the cell and to neighbor cells (like Shigella).

	LLO: listeriolysin	Salmonella in the vacuole, inhibits fusion with lysosome
	EE: early endosome LE: late endosome Ly: lysosome	(via Rab5 et 7), survives and multiplies using genes encoded by SPI2.

14

First contact of Salmonella with intestinal epithelium

Epithelium response to Salmonella The IL-23 -T H 17 axis: amplification of host defense mechanisms

	Defensin response: important antibacterial weapon of
	epithelium
	 FliC (flagellar protein) of Salmonella Enteritidis induce HBD2
	IL-22  Matrilysin MMP7 (maturation of a-defensins) KO mice •IL-23: stimulates T H 17, NKT, dT and ILC to produce IL-17 and expression in Caco-2 epithelial cells
	Susceptibility to lethal infections by
	•IL17 and IL22: stimulate epithelial cells to proliferate (tissue Salmonella Typhimurium
	repair), to produce lipocalin2 and calprotectin 1,2 , Fe3+ and Low efficiency in the clearance of entero-Zn2+ chelators, and to produce antimicrobial defensins pathogenic bacteria
	 Transgenic mice for the gene of human a-defensin HD5
	Resistant to pathogenisc effects of Salmonella
	Typhimurium 1

•IL-17 induces CXC chemokines-dependent recruitment of neutrophils 1 Behnsen J et al, 2014, Immunity, 40 (2): 262-73. 2 Dixon BR et al, 2016, PLOS One, 11(2):e0148514. doi: 10.1371 22 First contact of Salmonella with intestinal epithelium Godinez I et al, 2011, Cellular Microbiology, 13(11): 1639-47. 1 Salzman et al, 2003, Nature, 422:522 23 First contact of Salmonella with intestinal epithelium

Salmonella strategies of escape from defensins

 Salmonella Typhimurium: negative regulation of a-defensins and lysozyme expression (dependent on PhoP virulence regulator).

on the activation state of phagocytes: neutrophils, macrophages and dendritic cells

	Mucosal response to pathogenic enterobacteria
	• Microbial communities in the gut
	• Salmonella as emblematic pathogenic enterobacteria
	• First contact of Salmonella with intestinal epithelium
	-Initial steps
	-Epithelial sensing
	-Mucosal response
	• The fate of Salmonella after epithelial crossing
	• Systemic response to infection, adaptive immunity
	• Critical cytokine response: major role of IFN-

25

Dependent

 Salmonella is taken up by macrophages and/or dendritic cells.

 Bacterial survival in macrophages if non activated. Salmonella blocks oxidative burst (inhibition of NADPH oxidase) by SPI2.

Sierro et al,

2001, PNAS, 98 (24):13722-27. 2 Mlao EA et al, 2006, Nat Immunol, 7:569-75. 3 Franchi L. et al. 2006. Nat. Immunol, 7:576-82.

Weiss DS et al,

2004, J Immunol, 172:4463. 2 Sivick KE et al, 2014, Cell host Microbes, 15:203.

Ravindran R et al, 2005, J Immunol, 175(7): 4603-10.

Spees AM et al, 2014, Infect. Immun. 82: 1692-97.

Ottenhoff TH et al, 2003, Adv Exp Med Biol.

531:279-94.

Intestinal carriage of Salmonella in birds

Poultry is a reservoir for Salmonella:

• Contamination of the food chain (eggs, meat).

• Colonisation of the digestive tract of birds by S. Enteritidis, contamination poultry flocks.

• Chicks are susceptible to the infection : more young the animals are, more high is the level of mortality.

• Chickens and adults : intestinal persistence in the caecum, asymptomatic with fecal shedding.

• Horizontal transmission (between congeneers).

• Vertical transmission (hen to eggs).

42

Means of fight:

• Genetic selection of resistant animals • In absence of former systemic and of collateral infection.

 Heterogeneous levels of intestinal colonisation (Low Shedders/ Super Shedders) 1 :

• When transmission is reduced between congeners.

 Low shedding phenotype is intrinsic : linked to the chick • By blockage of the colonisation. P et al., Environmental Microbiology, 2018. 60 Insights into protective role of microbiota Kempf F et al., Environmental Microbiology, 2020.

Menanteau


David Cohen-Steiner
email: david.cohen-steiner@inria.fr

André Lieutier
email: andre.lieutier@3ds.fr

Julien Vuillamy
email: julien.vuillamy@3ds.fr

Lexicographic optimal homologous chains and applications to point cloud triangulations

Keywords: Simplicial homology, Point cloud triangulation, Delaunay triangulation Mathematics Subject Classification (2010) 68U05

This paper considers a particular case of the Optimal Homologous Chain Problem (OHCP) for integer modulo 2 coefficients, where optimality is meant as a minimal lexicographic order on chains induced by a total order on simplices. The matrix reduction algorithm used for persistent homology is used to derive polynomial algorithms solving this problem instance, whereas OHCP is NP-hard in the general case. The complexity is further improved to a quasilinear algorithm by leveraging a dual graph minimum cut formulation when the simplicial complex is a pseudomanifold. We then show how this particular instance of the problem is relevant, by providing an application in the context of point cloud triangulation.

Introduction

Problem statement

The computation of minimal simplicial homology generators has been a wide subject of interest for its numerous applications related to shape analysis, computer graphics or computer-aided design. Coined in [START_REF] Dey | Optimal homologous cycles, total unimodularity, and linear programming[END_REF], we recall the Optimal Homologous Chain Problem (OHCP):

Problem 1 (OHCP) Given a -chain in a simplicial complex and a set of weights given by a diagonal matrix of appropriate dimension, find the 1 -norm minimal chain Γ min homologous to :

Γ min = min Γ,
|| • Γ|| 1 such that Γ = + +1 and Γ ∈ ( ) , ∈ +1 ( )

It has been shown that OHCP is NP-hard in the general case when using coefficients in Z 2 [START_REF] Chambers | Minimum cuts and shortest homologous cycles[END_REF][START_REF] Chen | Hardness results for homology localization[END_REF]. However, we consider a specialization of this problem: the Lexicographic Optimal Homologous Chain Problem (Lex-OHCP). Using coefficients in Z 2 , minimality is now meant according to a lexicographic order on chains induced by a total order on simplices. Formulated in the context of OHCP, this would require ordering the simplices using a total order and taking a weight matrix with generic term = 2 , where is the rank along the total order, allowing the 1 -norm minimization to be equivalent to a minimization along the lexicographic order.

Contributions

After providing some required definitions and notations (Section 2), we show how an algorithm based on the matrix reduction algorithm used for the computation of persistent homology [START_REF] Edelsbrunner | Computational Topology -an Introduction[END_REF] allows to solve this particular instance of OHCP in

( 3 ) worst case complexity (Section 3). Using a very similar process, we show that the problem of finding a minimal -chain bounding a given ( -1)-cycle admits a similar algorithm with the same algorithmic complexity (Section 4). Section 5 then considers Lex-OHCP in the case where the simplicial complex is a strongly connected ( + 1)-pseudomanifold. By formulating it as a Lexicographic Minimum Cut (LMC) dual problem, the algorithm can be improved to a quasilinear complexity:

the cost of sorting the dual edges and performing a O ( ( )) algorithm based on disjoint-sets, where is the number of dual edges and is the inverse Ackermann function. Finally, Section 6 legitimizes this restriction of OHCP by characterizing the quality of lexicographic optimal homologous chains, namely in the context of point cloud triangulation. After defining a total order closely related to the Delaunay triangulation, we provide details on an open surface algorithm given a boundary as well as a watertight surface reconstruction algorithm given an interior and exterior information.

Related work

Several authors have studied algorithm complexities for the computation of 1 -norm optimal cycles in homology classes [9, 10, 13-15, 21-23, 27, 37]. However, to the best of our knowledge, considering lexicographic-minimal chains in their homology classes is a new idea. When minimal cycles are of codimension 1 in a pseudomanifold, the idea of considering the minimal cut problem on the dual graph has been previously studied [START_REF] Sullivan | A crystalline approximation theorem for hypersurfaces[END_REF]. In particular, Chambers et al. [START_REF] Chambers | Minimum cuts and shortest homologous cycles[END_REF] have considered graph duality to derive complexity results for the computation of optimal homologous cycles on 2-manifolds. Chen et al. [START_REF] Chen | Hardness results for homology localization[END_REF] also use a reduction to a minimum cut problem on a dual graph to compute minimal non-null homologous cycles on -complexes embedded in R . Their polynomial algorithm (Theorem 5.2.3 in [START_REF] Chen | Hardness results for homology localization[END_REF]) for computing a homology class representative of minimal radius is reminiscent of our algorithm for computing lexicographic minimal representatives (Algorithm 4). In a recent work [START_REF] Dey | Computing minimal persistent cycles: Polynomial and hard cases[END_REF], Dey et al. consider the dual graph of pseudo-manifolds in order to obtain polynomial time algorithms for computing minimal persistent cycles. Since they consider arbitrary weights, they obtain the O ( 2 ) complexity of best known minimum cut/maximum flow algorithms [START_REF] Orlin | Max flows in o(nm) time, or better[END_REF]. The lexicographic order introduced in our work can be derived from the idea of a variational formulation of the Delaunay triangulation, first introduced in [START_REF] Chen | Mesh smoothing schemes based on optimal delaunay triangulations[END_REF] and further studied in [START_REF] Alliez | Variational tetrahedral meshing[END_REF][START_REF] Chen | Efficient mesh optimization schemes based on optimal delaunay triangulations[END_REF]. Finally, many methods have been proposed to answer the problem of surface reconstruction in specific acquisition contexts [START_REF] Kazhdan | Screened poisson surface reconstruction[END_REF][START_REF] Labatut | Robust and efficient surface reconstruction from range data[END_REF][START_REF] Li | Globfit: consistently fitting primitives by discovering global relations[END_REF]: [START_REF]Eurographics 2014 -State of the Art Reports[END_REF] classifies a large number of these methods according to the assumptions and information used in addition to geometry. In the family of purely geometric reconstruction based on a Delaunay triangulation, one early contribution is the sculpting algorithm by Boissonnat [START_REF] Boissonnat | Geometric structures for three-dimensional shape representation[END_REF]. The crust algorithm by Amenta et al. [START_REF] Amenta | A new voronoi-based surface reconstruction algorithm[END_REF][START_REF] Amenta | A simple algorithm for homeomorphic surface reconstruction[END_REF] and an algorithm based on natural neighbors [START_REF] Boissonnat | Smooth surface reconstruction via natural neighbour interpolation of distance functions[END_REF] were the first algorithms to guarantee a triangulation of the manifold under sampling conditions. However, these general approaches usually have difficulties far from these sampling conditions, in applications where point clouds are noisy or under-sampled. This difficulty can be circumvented by providing additional information on the nature of the surface [START_REF] Carvalho | An algorithm for calculating topdimensional bounding chains[END_REF][START_REF] Dey | Tight cocone: A water-tight surface reconstructor[END_REF][START_REF] Edelsbrunner | Surface Reconstruction by Wrapping Finite Sets in Space[END_REF]. Our contribution lies in this category of approaches. We provide some topological information of the surface: a boundary for the open surface reconstruction and interior and exterior regions for the closed surface reconstruction.

Definitions

Simplicial complexes

Consider an independent family = ( 0 , . . . , ) of points of R . We call a dsimplex spanned by A the set of all points:

= =0
, where ∀ ∈ {0.. }, ≥ 0 and

=0 = 1
Any simplex spanned by a subset of is called a face of .

A simplicial complex is a collection of simplices such that every face of a simplex of is in and the intersection of two simplices of is either empty or a common face.

Simplicial chains

Let be a simplicial complex of dimension at least . The notion of chains can be defined with coefficients in any ring but we restrict here the definition to coefficients in the field Z 2 = Z/2Z. A d-chain with coefficients in Z 2 is a formal sum of -simplices :

= , with ∈ Z 2

and ∈

We denote ( ) the vector space over the field Z 2 of -chains in the complex .

Interpreting the coefficient ∈ Z 2 = {0, 1} in front of simplex as indicating the existence of in the chain , we can view the -chain as a set of simplices : for a -simplex and a -chain , we write that ∈ if the coefficient for in is 1.

With this convention, the sum of two chains corresponds to the symmetric difference on their sets. In what follows, a -simplex can also be interpreted as the -chain containing only the -simplex .

Boundary operator

For a -simplex = [ 0 , . . . , ], the boundary operator is defined as the operator:

:

( ) → -1 ( ) = def. =0 [ 0 , . . . , , . . . , ]
where the symbol means the vertex is deleted from the array. The kernel of the boundary operator = Ker is called the group of -cycles and the image of the operator = Im +1 is the group of -boundaries. We say two -chains and are homologous if -= +1 , for some ( + 1)-chain .

Lexicographic order

We assume now a total order on the -simplices of , 1 < • • • < , where = dim ( ). From this order, we define a lexicographic total order on -chains.

Definition 1 (Lexicographic total order) For 1 , 2 ∈ ( ):

1 2 ⇐⇒ def.          1 + 2 = 0 or max = max { ∈ 1 + 2 } ∈ 2
This total order naturally extends to a strict total order on ( ).

3 Lexicographic optimal homologous chain

Problem statement

In this section, we define a particular instance of OHCP (Problem 1), the Lexicographic Optimal Homologous Chain Problem (Lex-OHCP):

Problem 2 (Lex-OHCP) Given a simplicial complex with a total order on the -simplices and a -chain ∈ ( ), find the unique chain Γ min defined by :

Γ min = min Γ ∈ ( ) | ∃ ∈ +1 ( ) , Γ -= +1 Definition 2 A -chain ∈ ( ) is said reducible if there is a -chain Γ ∈ ( )
(called reduction) and a ( + 1)-chain ∈ +1 ( ) such that:

Γ and Γ -= +1
If this property cannot be verified, the -chain is said irreducible. If is reducible, we call total reduction of the unique irreducible reduction of . If is irreducible, is said to be its own total reduction.

Problem 2 can be reformulated as finding the total reduction of .

Boundary matrix reduction

With = dim ( ) and = dim +1 ( ), we now consider the -by-boundary matrix +1 with entries in Z 2 . We enforce that rows of the matrix are ordered according to a given strict total order on -simplices 1 < • • • < , where the -simplex is the basis element corresponding to the ℎ row of the boundary matrix. The order of columns, corresponding to an order on ( + 1)-simplices, is not relevant for this section and can be chosen arbitrarily.

For a matrix , the index of the lowest (i.e. closest to the bottom) non-zero coefficient of a non-zero column is denoted by low( ), or sometimes low( ) when we want to explicit the considered matrix.

Algorithm 1 is a slightly modified version of the boundary reduction algorithm presented in [START_REF] Edelsbrunner | Computational Topology -an Introduction[END_REF]. Indeed, for our purpose, we do not need the boundary matrix storing all the simplices of all dimensions and apply the algorithm to the sub-matrix +1 : +1 ( ) → ( ). One checks easily that Algorithm 1 has O ( 2 ) time complexity. We now introduce a few lemmas useful for solving Problem 2. We allow

. , ).

Lemma 1 A -chain is reducible if and only if at least one of its -simplices is reducible.

Proof If there is a reducible -simplex ∈ , is reducible by the -chain = -+ ( ), where ( ) is a reduction for . We suppose to be reducible. Let Γ be a reduction for and the ( + 1)chain such that Γ -= . We denote max = max { ∈ -Γ}. Note that max is homologous to Γ -+ max . The chain Γ -+ max only contains simplices smaller than max , by definition of the lexicographic order (Definition 1). We have thus shown that if is reducible, it contains at least one simplex that is reducible.

Lemma 2 After matrix reduction (Algorithm 1), a non-zero column

≠ 0 can be described as

= low( ) + Γ, where Γ is a reduction for low( ) .
Proof As all matrix operations performed on by the reduction algorithm consist of sums of columns of +1 , each non-zero column of is in the image of +1 . Therefore, there exists a ( + 1)-chain such that = low( ) + Γ = +1 , which, is equivalent in Z 2 to Γlow( ) = +1 . By definition of the low of a column, we also have immediately: Γ low( ) . For each non-zero column, the largest simplex is therefore reducible by the other -simplices of the column.

Lemma 3 After matrix reduction (Algorithm 1), there is a one-to-one correspondence between the reducible -simplices and non-zero columns of :

∈ ( ) is reducible ⇐⇒ ∃ ∈ {1.. }, ≠ 0 and low( ) =
Proof Lemma 2 shows immediately that the simplex corresponding to the lowest index of a non-zero column is reducible. Suppose now that a -simplex ˜ is reducible and let Γ be a reduction of it: ˜ + Γ = +1 and Γ ˜ . Algorithm 1 realizes the matrix factorization = +1 • , where matrix is invertible [START_REF] Edelsbrunner | Computational Topology -an Introduction[END_REF]. It follows that Im = Im +1 . Therefore, non-zero columns of span Im +1 and since

˜ + Γ = +1 ∈ Im +1 , there is a family ( ) ∈ = ( low( ) , Γ ) ∈ of columns of such that : ˜ + Γ = ∈ low( ) + Γ
Every low( ) represents the largest simplex of a column, and Γ a reduction chain for low( ) . As observed in section VII.1 of [START_REF] Edelsbrunner | Computational Topology -an Introduction[END_REF], one can check that the low indexes in are unique after the reduction algorithm. Therefore, there is a max ∈ such that for all in \ { max }, low( ) < low( max ), which implies:

max = max ∈ ∈ low( ) + Γ = max ∈ ˜ + Γ = ˜
We have shown that for the reducible simplex ˜ , there is a non-zero column max with ˜ = low( max ) as its largest simplex. Proof In Algorithm 2, let Γ -1 be the value of the variable Γ after iteration . Since the iteration counter decreases from to 1, the input and output of the algorithm are respectively Γ and Γ 0 . At each iteration, Γ -1 are either equal to Γ or Γ + . Since ∈ Im +1 , Γ -1 is in both cases homologous to Γ . Therefore, Γ 0 is homologous to Γ . We are left to show that Γ 0 is irreducible. From Lemma 1, it is enough to check that it does not contain any reducible simplex.

Let

be a reducible simplex and let us show that ∉ Γ 0 . Two possibilities may occur:

-if ∈ Γ , then Γ -1 = Γ + . Since low( ) = , we have ∈ and therefore ∉ Γ -1 .
-if ∉ Γ , then Γ -1 = Γ and again ∉ Γ -1 .

Furthermore, from iterations -1 to 1, the added columns contain only simplices smaller than and therefore ∉ Γ -1 ⇒ ∉ Γ 0 .

Observe that using an auxiliary array allows to compute the correspondence low( ) → in time O [START_REF] Alliez | Variational tetrahedral meshing[END_REF]. The column addition nested inside the loop lead to a O ( Problem 3 Given a simplicial complex K with a total order on the -simplices and a -chain Γ 0 ∈ ( ), find :

Γ min = min Γ ∈ ( ) | Γ = Γ 0
Problem 4 Given a simplicial complex with a total order on the -simplices and a ( -1)-cycle , check if is a boundary:

= def. Γ ∈ ( ) | Γ = ≠
If it is the case, find the minimal -chain Γ bounded by :

Γ = min
In Problem 4, finding a representative Γ 0 in the set ≠ such that Γ 0 = is sufficient: we are then taken back to Problem 3 to find the minimal -chain Γ min such that Γ min = Γ 0 = .

Boundary reduction transformation matrix

As in Section 3, we will derive an algorithmic solution to Problem 3 from the result of the boundary matrix reduction algorithm. Note that, unlike Section 3 that used the +1 boundary operator, we are now considering , meaning the given total order on -simplices applies to the greater dimension. An arbitrary order can be taken for the ( -1)-simplices to build the matrix . Indeed, if we see the performed reduction in matrix notation as = • , the minimization steps in this section will be performed on the transformation matrix , whose rows do follow the given simplicial ordering.

The number of zero columns of is the dimension of = Ker [START_REF] Edelsbrunner | Computational Topology -an Introduction[END_REF]. Let's denote it by Ker = dim( ). By selecting all columns in corresponding to zero columns in , we obtain the matrix Ker , whose columns Ker 1 , . . . , Ker Ker form a basis of .

We first show a useful property on the matrix Ker . Note that the low index for any column in Ker is well defined, as is invertible. Proof Before the boundary matrix reduction algorithm, the initial matrix is the identity: the low indexes are therefore unique. During iterations of the algorithm, the matrix is right-multiplied by an column-adding elementary matrix 0 , , adding column 0 to with 0 < .

0 , =                           1 1 1 0 . . . 1 . . . 1
Therefore, the indexes {low( ), ∈ } stay on the diagonal (i.e. low( ) = ) during the reduction algorithm and are therefore unique. The restriction of to Ker does not change this property.

If

∈ Ker \ {0}, can be written as a non-zero linear combination = ∈ Ker of columns of Ker . By unicity of the lows of Ker , the largest low of the combination, i.e. max ∈ {low( Ker )}, is in and has to be the low of .

Total reduction with imposed boundary

We apply a similar total reduction algorithm as previously introduced in Section 3 but using the matrix Ker . In the following algorithm, = dim ( ). In Algorithm 3, we denote by Γ -1 the value of variable Γ after iteration . Since iteration counter is decreasing from to 1, the input and output of the algorithm are respectively Γ and Γ 0 . Since Ker ∈ Ker , at each iteration Γ -1 = Γ therefore Γ 0 = Γ . We are left to show the algorithm's result is the minimal solution.

Suppose there is Γ ★ such that Γ ★ = Γ and Γ ★ Γ 0 . Let's consider the difference Γ 0 -Γ ★ , and its largest element index low(Γ 0 -Γ ★ ) = , with ∈ Γ 0 and ∉ Γ ★ by Definition 1 of the lexicographic order. As Γ 0 -Γ ★ ∈ Ker \ {0}, there has to be a column Ker in Ker where low Ker = , from Lemma 4. Two possibilities may occur at iteration :

-if ∈ Γ , then Γ -1 = Γ + Ker . Since = low( ), we have ∈ Ker and therefore ∉ Γ -1 .

-if ∉ Γ , then Γ -1 = Γ and again ∉ Γ -1 .

However, from iterations -1 to 1, the added columns Ker contains only simplices with indices smaller than and therefore we obtain ∉ Γ -1 ⇒ ∉ Γ 0 , a contradiction to the definition of as the largest element of Γ ★ -Γ 0 .

Finding a representative of B A

As previously mentioned, solving Problem 4 requires deciding if the set is empty and in case it is not empty, finding an element of the set . Algorithm 3 can then be used to minimize this element under imposed boundary. In the following algorithm, = dim -1 ( ) and = dim ( ).

Proposition 3 Algorithm 4 decides if the set is non-empty, and in that case, finds

a representative Γ 0 such that Γ 0 = in O ( 2 ) time complexity.
Proof We start by two trivial observations from the definition of a reduction. First, is a boundary if and only if its total reduction is the null chain. Second, if a non-null chain is a boundary, then its greatest simplex is reducible.

If, at iteration , 0 [ ] ≠ 0, then is the greatest simplex in 0 . In the case has no column such that low( ) = , is not reducible by Lemma 3 and therefore 0 is not a boundary. Since and 0 differ by a boundary (added columns of ), is not a boundary either. This means the set is empty.

The main difference with the previous chain reduction is we keep track of the column

Algorithm 4: Finding a representative

Inputs: A ( -1)-chain , a boundary matrix reduced by Output: A -chain Γ 0 bounded by if is a boundary.

Γ 0 ← 0 ← for ← to 1 do if 0 [ ] ≠ 0 then if ∃ ∈ {1.. } with low( ) = in then 0 ← 0 + Γ 0 ← Γ 0 + else
The set is empty. end end end operations in Γ 0 . If the total reduction of is null, we have found a linear combination

( ) ∈ such that = ∈ .
We have also computed Γ 0 as the sum of the corresponding columns in : Γ 0 = ∈ . As = • , we can now verify:

Γ 0 = ∈ = ∈ =

Efficient algorithm for codimension 1 (dual graph)

In this section we focus on Problem 5, a specialization of Problem 2, namely when is a subcomplex of a ( + 1)-pseudomanifold.

Problem statement

Recall that a -dimensional simplicial complex is said pure if it is of dimension and any simplex has at least one coface of dimension .

Definition 3 A d-pseudomanifold is a pure -dimensional simplicial complex for which each ( -1)-face has exactly two -dimensional cofaces.

Definition 4

The dual graph of a -pseudomanifold M is the graph whose vertices are in one-to-one correspondence with the -simplices of M and whose edges are in one-to-one correspondence with ( -1)-simplices of M : an edge connects two vertices 1 and 2 of the graph if and only if corresponds to the ( -1)-face with cofaces corresponding to 1 and 2 .

Definition 5 A strongly connected -pseudomanifold is a -pseudomanifold whose dual graph is connected.

Given a strongly connected ( + 1)-pseudomanifold M and 1 ≠ 2 two ( + 1)simplices of M, we consider a special case of Problem 2 where = M \ { 1 , 2 } and

= 1 :
Problem 5 Given a strongly connected ( + 1)-pseudomanifold M with a total order on the -simplices and two distinct ( + 1)-simplices ( 1 , 2 ) of M, find:

Γ min = min Γ ∈ (M) | ∃ ∈ +1 (M \ { 1 , 2 }) , Γ -1 =
Definition 6 Seeing a graph as a 1-dimensional simplicial complex, we define the coboundary operator 0 : 0 ( ) → 1 ( ) as the linear operator defined by the transpose of the matrix of the boundary operator 1 : 1 ( ) → 0 ( ) in the canonical basis of simplices.

For a given graph = (V, E), V and E respectively denote its vertex and edge sets.

For a -chain ∈ (M) and a ( + 1)-chain ∈ +1 (M), ˜ and ˜ denote their respective dual 1-chain and dual 0-chain in the dual graph (M) of M. We easily see that:

Remark 1 For a set of vertices V 0 ⊂ V, 0 V 0 is exactly the set of edges in = (V, E) that connect vertices in V 0 with vertices in V \ V 0 .
Remark 2 Let M be a ( + 1)-pseudomanifold. If ∈ (M) and ∈ +1 (M), then ˜ = 0 ˜ ⇐⇒ = +1 .

Codimension 1 and Lexicographic Min Cut (LMC)

The order on -simplices of a ( + 1)-pseudomanifold M naturally defines a corresponding order on the edges of the dual graph: 1 < 2 ⇐⇒ ˜ 1 < ˜ 2 . This order extends similarly to a lexicographic order on sets of edges (or, equivalently,

1-chains) in the graph.

In what follows, we say a set of edges Γ disconnects ˜ 1 and ˜ 2 in the graph (V, E)

if ˜ 1 and ˜ 2 are not in the same connected component of the graph (V, E \ Γ).

Given a graph with weighted edges and two vertices, the min-cut/max-flow problem [START_REF] Edmonds | Theoretical improvements in algorithmic efficiency for network flow problems[END_REF][START_REF] Orlin | Max flows in o(nm) time, or better[END_REF] consists in finding the minimum cut (i.e. set of edges) disconnecting the two vertices, where minimum is meant as minimal sum of weights of cut edges. We consider a similar problem where the minimum is meant in term of a lexicographic order: the Lexicographic Min Cut (LMC).

Problem 6 (LMC) Given a connected graph = (V, E) with a total order on E and two vertices ˜ 1 , ˜ 2 ∈ V, find the set ΓLMC ⊂ E minimal for the lexicographic order , that disconnects ˜ 1 and ˜ 2 in .

In order to avoid to introduce non essential formal definitions, the coboundary operator is defined over chains since, for finite simplicial complexes, the canonical inner product defines a natural bijection between chains and cochains. Proof Problem 5 can be equivalently formulated as:

Proposition 4 Γ min is solution of Problem 5 if and if only its dual 1-chain

Γ min = min +1 ( 1 + ) | ∈ +1 (M \ { 1 , 2 }) (1)
Using Observation 2, we see that Γ min is the minimum in Equation ( 1) if and only if its dual 1-chain Γmin satisfies:

Γmin = min 0 ( ˜ 1 + ˜ ) | ˜ ⊂ V \ { ˜ 1 , ˜ 2 } (2)
Denoting ΓLMC the minimum of Problem 6, we need to show that ΓLMC = Γmin .

As ΓLMC disconnects ˜ 1 and ˜ 2 in = (V, E), ˜ 2 is not in the connected component of

˜ 1 in (V, E \ ΓLMC ). We define ˜ as the connected component of ˜ 1 in (V, E \ ΓLMC ) minus ˜ 1 . We have that ˜ ⊂ V \ { ˜ 1 , ˜ 2 }. Consider an edge ∈ 0 ( ˜ 1 + ˜ ). From Observation 1, connects a vertex ∈ { ˜ 1 } ∪ ˜ with a vertex ∉ { ˜ 1 } ∪ ˜ .
From the definition of ˜ , ΓLMC disconnects and in , which in turn implies ∈ ΓLMC .

We have therefore shown that 0 ( ˜ 1 + ˜ ) ⊂ ΓLMC . Using Equation ( 2), we get:

Γmin 0 ( ˜ 1 + ˜ ) ΓLMC (3)
Now we claim that if there is a ˜ ⊂ V \ { ˜ 1 , ˜ 2 } with Γ = 0 ( ˜ 1 + ˜ ), then Γ disconnects ˜ 1 and ˜ 2 in (V, E). Consider a path in from ˜ 1 to ˜ 2 . Let be the last vertex of the path that belongs to { ˜ 1 } ∪ ˜ and the next vertex on the path (which exists since ˜ 2 is not in { ˜ 1 } ∪ ˜ ). From Observation 1, we see that the edge ( , ) must belong to Γ = 0 ( ˜ 1 + ˜ ). We have shown that any path in connecting ˜ 1 and ˜ 2 has to contain an edge in Γ and the claim is proved. In particular, the minimum Γmin disconnects ˜ 1 and ˜ 2 in (V, E). As ΓLMC denotes the minimum of Problem 6, ΓLMC Γmin which, together with Equation (3), gives us ΓLMC = Γmin . We have therefore shown the minimum defined by Equation (2) coincides with the minimum defined in Problem 6.

Algorithm for Lexicographic Min Cut

In light of the new problem equivalency, we will study an algorithm solving Problem 6. As we will only consider the dual graph for this section, we leave behind the dual chain notation: vertices ˜ 1 and ˜ 2 are replaced by 1 and 2 , and the solution to the problem is simply noted Γ LMC . The following lemma exposes a constructive property of the solution on subgraphs.

Lemma 5 Consider Γ LMC solution of Problem 6 for the graph

= (V, E) and

1 , 2 ∈ V. Let 0 be an edge in V × V such that 0 < min{ ∈ E}. Then: -The solution for (V, E ∪ { 0 }) is either Γ LMC or Γ LMC ∪ { 0 }. Γ LMC Γ LMC Γ LMC ∪ { 0 }.
As 0 < min{ ∈ E}, there is no set in E ∪ { 0 } strictly between Γ LMC and Γ LMC ∪ { 0 } for the lexicographic order. It follows that Γ LMC is either equal to Γ LMC or Γ LMC ∪ { 0 }. The choice for Γ LMC is therefore ruled by the property that it should disconnect 1 and 2 : if 1 and 2 are connected in (V, E ∪ { 0 } \ Γ LMC ), Γ LMC does not disconnect 1 and 2 in (V, E ∪ { 0 }) and Γ LMC ∪ { 0 } has to be the solution for (V, E ∪ { 0 }). On the other hand, if 1 and 2 are not connected in

(V, E ∪ { 0 } \ Γ LMC ), then both Γ LMC and Γ LMC ∪ { 0 } disconnect 1 and 2 in (V, E ∪ { 0 }), but as Γ LMC Γ LMC ∪ { 0 }, Γ LMC ∪ { 0 } is not the solution for (V, E ∪ { 0 }).
Building an algorithm from Lemma 5 suggests a data structure able to check if vertices 1 and 2 are connected in the graph: the disjoint-set data structure, introduced for finding connected components [START_REF] Galler | An improved equivalence algorithm[END_REF], does exactly that. In this structure, each set of elements has a different root value, called representative. Calling the operation MakeSet on an element creates a new set containing this element. The FindSet operation, given an element of a set, returns the representative of the set. For all elements of the same set, FindSet will of course return the same representative.

Finally, the structure allows merging two sets, by using the UnionSet operation. After this operation, elements of both sets will have the same representative.

We now describe Algorithm 5. The algorithm expects a set of edges sorted in decreasing order according to the lexicographic order.

Algorithm 5: Lexicographic Min Cut

Inputs: = ( V, E) and 1 , 2 ∈ V, with E = { , = 1, . . . , } in decreasing order Output:

Γ LMC Γ LMC ← for ∈ V do MakeSet(v) end for ∈ E in decreasing order do = ( 1 , 2 ) ∈ V × V 1 ← FindSet( 1 ), 2 ← FindSet( 2 ) 1 ← FindSet( 1 ), 2 ← FindSet( 2 ) if { 1 , 2 } = { 1 , 2 } then Γ LMC ← Γ LMC ∪ else UnionSet( 1 ,
(V, E).
The complexity of the MakeSet, FindSet and UnionSet operations have been shown to be respectively O (1), O ( ( )) and O ( ( )), where ( ) is the inverse Ackermann function on the cardinal of the vertex set [START_REF] Tarjan | Worst-case analysis of set union algorithms[END_REF]. Assuming sorted edges as input of the algorithm -which is performed in O ( ln( )), the algorithm runs in O ( ( )) time complexity.

The similarity of Algorithm 5 with Kruskal's algorithm for minimum spanningtree suggests an even better theoretical time complexity, by using Chazelle's algorithm [START_REF] Chazelle | A minimum spanning tree algorithm with inverse-ackermann type complexity[END_REF] for minimum spanning-tree, running in O ( ( )) complexity without requiring sorted edges.

Application to point cloud triangulation

In all that precedes, the order on simplices was not specified and one can wonder if choosing such an ordering makes the specialization of OHCP too restrictive for it to be useful. In this section, we give a concrete example where this restriction makes sense and provides a simple and elegant application to the problem of point cloud triangulation. Whereas all that preceded dealt with an abstract simplicial complex, we now consider a bijection between vertices and a set of points in Euclidean space, allowing to compute geometric quantities on simplices. acute triangle , R B ( ) = R C ( ). Based on [START_REF] Cohen-Steiner | Lexicographic optimal chains and manifold triangulations[END_REF][START_REF] Cohen-Steiner | Regular triangulations as lexicographic optimal chains[END_REF], we define the total order on 2-simplices:

1 ≤ 2 ⇐⇒          R B ( 1 ) < R B ( 2 ) or R B ( 1 ) = R B ( 2 ) and R C ( 1 ) ≥ R C ( 2 ) (4)
Under generic condition on the position of points, we can show this order is total. In what follows, the lexicographic order is induced by this order on simplices. The following proposition from [START_REF] Cohen-Steiner | Regular triangulations as lexicographic optimal chains[END_REF] shows a strong link between the simplex ordering and the 2D Delaunay triangulation. As the 2D Delaunay triangulation has some well-known optimality properties, such as maximizing the minimal angle, we can hope that using the same order to minimize 2-chains in dimension 3 will keep some of those properties. In fact, it has been shown that for a Čech or Vietoris-Rips complex, under strict conditions linking the point set sampling, the parameter of the complex and the reach of the underlying manifold of Euclidean space, the minimal lexicographic chain using the described simplex order is a triangulation of the sampled manifold [START_REF] Cohen-Steiner | Lexicographic optimal chains and manifold triangulations[END_REF]. Experimental results (Figure 2) show that this property remains true relatively far from these theoretical conditions.

Open surface triangulation

Given a point cloud sampling an open surface and a 1-cycle sampling the boundary of the surface, we generate a Čech complex of the point cloud using the Phat library [START_REF] Bauer | Phat -persistent homology algorithms toolbox[END_REF].

The parameter of the complex should be sufficient to capture the homotopy type of the surface to reconstruct and should contain the provided boundary cycle. After constructing the 2-boundary matrix, we apply the boundary reduction algorithm, slightly modified to store the transformation matrix (Section 4.2). We then apply Algorithm 4 to find out if a 2-chain bounded by the cycle exists in the current Čech complex. In this case, we get a chain bounded by the provided cycle and apply Algorithm 3 to minimize the chain under imposed boundary. Otherwise, we might have to increase the Čech parameter to capture the homotopy type of the surface to reconstruct [START_REF] Attali | Vietoris-rips complexes also provide topologically correct reconstructions of sampled shapes[END_REF][START_REF] Chazal | A sampling theory for compact sets in euclidean space[END_REF]. Figure 1 shows results of this method.

Closed surface triangulation

Using Algorithm 5 requires a strongly connected 3-pseudomanifold: we therefore use a 3D Delaunay triangulation, for its efficiency and non-parametric nature, using the CGAL library [START_REF] Jamin | 3D triangulations[END_REF], and complete it into a topological 3-sphere by connecting, for any triangle on the convex hull of the Delaunay triangulation, its dual edge to an "infinite" dual vertex.

Experimentally, sorting triangles does not require exact predicates: the R B and R C quantities can simply be calculated in fixed precision. The quasilinear complexity of Algorithm 5 makes it competitive in large point cloud applications. Outliers are naturally ignored and, being parameter free, the algorithm adapts to non uniform point densities, as seen in the closeup of Figure 4. The choice of 1 and 2 defines the location of the closed separating surface and are chosen interactively. Although we could devise an algorithm where these inputs are not required -the algorithm would simply merge regions until only two connected components remain -this would only work for uniform and non-noisy point clouds but not make for a robust algorithm. On the contrary, adding multiple interior and exterior regions can guide the algorithm by providing better topological constraints, as depicted in Figure 3.

Algorithm 5 requires to be slightly modified to take as input multiple 1 , 2 : after creating all sets with MakeSet, we need to combine all 1 sets together, and all 2 sets together. The algorithm remains unchanged for the rest.

Fig. 1

 1 Fig. 1 Open surface triangulations under imposed boundaries (red cycles).

Algorithm 1 :

 1 Reduction algorithm for the +1 matrix Input: A boundary matrix +1 Output: A reduced boundary matrix R = +1 for ← 1 to do while ≠ 0 and ∃ 0 < with low( 0 ) = low( ) do ← + 0 end end ourselves to consider each column of the matrix , formally an element of Z 2 , as the corresponding -chain in the basis ( 1 , . .

3. 3 Algorithm 2 :Proposition 1

 321 Total reduction algorithm Combining the three previous lemmas give the intuition on how to construct the total reduction solving Problem 2: Lemma 1 allows to consider each simplex individually, Lemma 3 characterizes the reducible nature of a simplex using the reduced boundary matrix and Lemma 2 describes a column of the reduction boundary matrix as a simplex and its reduction. We now present Algorithm 2, referred to as the total reduction algorithm. For a -chain Γ, Γ[ ] ∈ Z 2 denotes the coefficient of the ℎ simplex in the chain Γ. Total reduction algorithm Inputs: A -chain Γ, the reduced boundary matrix Output: The total reduction of Γ for ← to 1 do if Γ[ ] ≠ 0 and ∃ ∈ {1.. } with low( ) = in then Γ ← Γ + end end Algorithm 2 finds the total reduction of a given -chain in O ( 2 ) time complexity.

4

  Lexicographic-minimal chain under imposed boundary4.1 Problem statementThis section will study a variant of Lex-OHCP (Problem 3) in order to solve the subsequent problem of finding a minimal -chain bounding a given ( -1)-cycle (Problem 4).

Lemma 4

 4 Indexes low( Ker ) ∈ {1.. Ker } are unique. If ∈ Ker \{0}, there exists a unique column Ker max of Ker with low( Ker max ) = low( ).

Proposition 2 Algorithm 3 :

 23 Algorithm 3 computes the solution for Problem 3 in O ( 2 ) time complexity. Total reduction variant Inputs: A -chain Γ and Ker Output: The minimal chain with the same boundary as Γ for ← to 1 do if Γ[ ] ≠ 0 and ∃ ∈ {1.. Ker } with low( ) = in Ker then Γ ← Γ + Ker end end Proof The proof is similar to the one of Proposition 1.

  Γmin is solution of Problem 6 on the dual graph (M) of M where ˜ 1 and ˜ 2 are respective dual vertices of 1 and 2 .

2 ) end end Proposition 5

 25 Algorithm 5 computes the solution of Problem 6 for a given graph (V, E) and two vertices 1 , 2 ∈ V. Assuming the input set of edges E are sorted, the algorithm has O ( ( )) time complexity, where is the cardinal of E and the inverse Ackermann function.Proof We denote by the ℎ edge along the decreasing order and Γ LMC the value of the variable Γ LMC of the algorithm after iteration . The algorithm works by incrementally adding edges in decreasing order and tracking the growing connected components of the set associated with 1 and 2 in (V, { ∈ E, ≥ } \ Γ LMC ), for = 1, . . . , .At the beginning, no edges are inserted, and Γ 0 LMC = is indeed solution for (V, ). With Lemma 5, we are guaranteed at each iteration to find the solution for(V, { ∈ E, ≥ })by only adding to Γ -1 LMC the current edge if 1 and 2 are connected in { ∈ E, ≥ } \ Γ -1 LMC , which is done in the if-statement. If the edge is not added, we update the connectivity of the graph (V, { ∈ E, ≥ } \ Γ LMC ) by merging the two sets represented by 1 and 2 . After each iteration, Γ LMC is solution for (V, { ∈ E, ≥ }) and when all edges are processed, Γ LMC is solution for

6. 1

 1 Simplicial ordering Recent works have studied a characterization of the 2D Delaunay triangulation as a lexicographic minimum over 2-chains. Denote by R B ( ) the radius of the smallest enclosing ball and R C ( ) the radius of the circumcircle of a 2-simplex . For an

Fig. 2

 2 Fig. 2 Watertight reconstructions under different perturbations. Under small perturbations (first two images from the left), the reconstruction is a triangulation of the sampled manifold. A few non-manifold configurations appear however under larger perturbations (Rightmost image).

Proposition 6 (

 6 Proposition 7.9 in [19]) Let P = { 1 , . . . , } ⊂ R 2 with ≥ 3 be in general position and let P be any 2-dimensional complex containing the Delaunay triangulation of P. Denote by P ∈ 1 ( P ) the 1-chain made of edges belonging to the boundary of convex hull CH (P). If Γ min = min Γ ∈ 2 ( P ) , Γ = P , the simplicial complex |Γ min | support of Γ min is the Delaunay triangulation of P.

Fig. 3

 3 Fig.[START_REF] Amenta | A simple algorithm for homeomorphic surface reconstruction[END_REF] Providing additional topological information can improve the result of the reconstruction. Here, the lexicographic order on 1-chains is induced by edge length comparison.

Fig. 4

 4 Fig. 4 Closed surface triangulation of 440K points in 7.33 seconds. Beside the point cloud, the only user input is one inner tetrahedron. The closeup shows that small features are correctly recovered.

  2 ) time complexity for Algorithm 2. It follows that Problem 2 can be solved in O ( 2 ) time complexity, by applying successively Algorithms 1 and 2, or in O ( 3 ) complexity if is the size of the simplicial complex.

David Cohen-Steiner et al.-Γ LMC ∪ { 0 } is solution for (V, E ∪ { 0 }) if and only if 1 and 2 are connected in (V, E ∪ { 0 } \ Γ LMC ). Proof Let's call Γ LMC the solution for (V, E ∪ { 0 }). Since Γ LMC ∩ E disconnects 1 and 2 in (V, E), one has Γ LMC Γ LMC . Since Γ LMC ∪ { 0 } disconnects 1 and 2 in (V, E ∪ { 0 }), we also have Γ LMC Γ LMC ∪ { 0 }. Therefore,


Romain Gwoziecki

Julien Buckley

Cyrille Le Royer

Laura Vauche

Blend Mohamad

Charlotte Gillot

Matthew Charles

William Vandendaele

Marie-Anne Jaud

Véronique Sousa

Recent

; R Modica

A Constant

F Iucolano

Recent advances in GaN power devices development at CEA-LETI

est destinée au dépôt

I. INTRODUCTION

GaN-on-Si High Electron Mobility Transistors (HEMTs) are considered as one of the major solutions to address medium power applications in the 650V range [START_REF] Roccaforte | An Overview of Normally-Off GaN-Based High Electron Mobility Transistors[END_REF]. Among the different device architectures that benefit from the high conduction properties of the two-dimensional electron gas (2DEG), induced by the presence of the AlGaN/GaN heterojunction, those with normally-off behaviors are desired to simplify device driver design [START_REF] Roccaforte | An Overview of Normally-Off GaN-Based High Electron Mobility Transistors[END_REF]. Two main device architectures enabling normally-off behavior are of major interest today: pGaN-gate technology and insulated-gate technology [START_REF] Roccaforte | An Overview of Normally-Off GaN-Based High Electron Mobility Transistors[END_REF]. Despite its manufacturing maturity and market availability [2], pGaN-gate transistors are still suffering from a limited gate endurance to overvoltage. Indeed, during commutation in standard power converter topologies, circuit instabilities lead to gate voltage overshoot phenomena compromising normal transistor functionality. In addition, other needs concerning power devices are related to addressing higher blocking voltages (BV), typically 1200V or above. A vertical structure is an efficient way to increase the breakdown voltage and allows higher current density with respect to a lateral architecture. Due to the difficulty of controlling the high electric field located near the surface, lateral devices typically take up an order of magnitude more surface area than their vertical counterparts [3].

II. 650V MOS-CHANNEL HEMT DEVICES

A. Technology and device fabrication

In Fig. 1 we show a schematic of the MOS-channel HEMT device structure [START_REF] Viey | Investigation of nBTI degradation on GaN-on-Si E-mode MOSc-HEMT[END_REF]. The GaN stack is grown by metalorganic The reference epitaxial stack includes a transition layer followed by a thick C doped GaN (GaN:C > 1μm). An unintentionally doped GaN layer (GaN:UID), followed by the AlGaN barrier, is grown to form the channel : a 2DEG is formed at the AlGaN/GaN interface.

The insulated MIS-gate stack is fabricated via full etching of the AlGaN barrier, followed by Atomic Layer Deposition (ALD) of an Al2O3 oxide, gate-metal deposition and patterning. Field plate architectures are also embedded to smooth the electrical field between gate and drain in the blocking regime. Finally, source and drain ohmic contacts are formed using a Ti/Al stack followed by annealing.

B. MOS-channel HEMT device results

Fig. 2 shows an example of ID(VG) characteristics at room temperature with excellent performance: Vth=+1V, SS=88mV/dec. These curves illustrate the intrinsic gain of this architecture with respect to pGaN gate: gate current is very low (ID/IG >8 decades in Fig. 1, versus ~3 decades for pGaN [START_REF]IGT60R070D1 data sheet: 600V CoolGaN™ enhancement-mode Power Transistor[END_REF]). The extracted low field mobility µ = 225 cm²/V/s outperforms most published MOS channel HEMT results (see review [START_REF] Roccaforte | An Overview of Normally-Off GaN-Based High Electron Mobility Transistors[END_REF]). Note that MOSc HEMT technology is capable of supporting high Vg, such as 20V (not shown here), which outperforms pGaN. Fig. 3 illustrates the linear Ron as a function of gate length LG and gate-to-drain distance LGD from 25°C to 150°C. The 2DEG resistance is the main contributor to the total Ron, and shows the largest temperature dependency. Fig. 4 shows the ratio of Ron variation with temperature Ron(T)/Ron(25°C) for two LGD values and a comparison with pGaN data from [START_REF]IGT60R070D1 data sheet: 600V CoolGaN™ enhancement-mode Power Transistor[END_REF]. 1 CEA, LETI, MINATEC Campus, F-38054 Grenoble, France and Univ.

Grenoble

Alpes, F-38000 Grenoble, France (e-mail: romain.gwoziecki@cea.fr); 2 STMicroelectronics, 95121 Catania, Italy, 3 STMicroelectronics, 37100 Tours, France.

III. VERTICAL GAN DEVICES DEVELOPMENT

Vertical GaN devices in principle allow the Ron.A/BV (Ron.A: specific resistance in mOhm.cm²) factor of merit to be reduced with respect to lateral devices. Until now, the best results according to this metric have been obtained using native GaN substrates [START_REF] Fu | [END_REF]. One key point is understanding the root cause of device off-state leakage. Experimental leakage current measured on vertical GaN-on-Si Schottky diodes (Fig. 5) have been compared to TCAD simulations (Fig. 6). The current is explained by a combination of several physical mechanisms with Poole-Frenkel emission being dominant at high temperature and high voltages. A possible origin for the discrepancy with TCAD at lower temperatures could be defects either due to etching of GaN and/or related to the fluorine implant [START_REF] Maurya | IMAPS[END_REF]. IV. CONCLUSION Fully recessed insulated-gate normally-off GaN MOSchannel HEMTs have been successfully fabricated on 200mm Si-wafers with a fully CMOS compatible Au-free process for 650V applications. Typical devices show strongly reduced gate current and a lower temperature coefficient of Ron with respect to pGaN. For the future higher voltage applications, strong Ron/BV gain is expected from vertical GaN devices with the requirement of a good control of conducting defects in order to limit reverse leakage.

  The work on lateral HEMT devices was funded by the French national program "Programme d'Investissements d'Avenir PSPC n°9 -G-Mobility". Vertical GaN work was supported by GaNeXT (Labex, laboratoire d'excellence) under the project "VertiGaN". The epitaxy of vertical devices on GaN was developed at CNRS-CRHEA. chemical vapor deposition (MOCVD) on 200 mm Si wafers:

Fig. 1

 1 Fig. 1 Schematic cross-section of the CEA-LETI GaN-on-Si fully recessedgate MOS-channel HEMT architecture for 650V applications.

Fig. 2 Fig. 3 Fig. 4

 234 Fig. 2 Measured drain current and gate leakage (ID, IG) as function of gate voltage VGS, in log scale (Inset: linear scale for ID) -Lg,eff=0.29µm.

Fig. 5

 5 Fig. 5 Device cross-section with 5µm GaN epitaxy layer grown on 2-inch substrate (Schottky contact is Pt capped with Au) [7] Model Width/ Region Trap Energy (eV)