domain: phys chim

text:
Mitsuo Shoji
email: mshoji@ccs.tsukuba.ac.jp

Yuya Kitazawa

Akimasa Sato

Natsuki Watanabe

Mauro Boero

Yasuteru Shigeta

Masayuki Umemura

Enantiomeric Excesses of Aminonitrile Precursors determine the Homochirality of Amino Acids

Keywords: . Lyman-α (Lyα), Circularly Polarized Light (CPL), Symmetry-Adapted Cluster/Configuration Interaction (SAC-CI), Alanine (Ala), 2-

High enantiomeric excesses (ee) of L-amino acids, including non-proteinogenic amino acid isovaline (Iva), were discovered in the Murchison meteorite, but the detailed molecular mechanism responsible for the observed ee of amino acids remains elusive and inconsistent, because Iva has an inverted circular dichroism (CD) spectrum with respect to α-H amino acids, e.g. alanine. To address this issue, we resort to accurate ab initio calculations for amino acids and their precursors in the Strecker synthesis. We evaluated their photolysis-induced ee in the range of 5-11 eV including the Lyman alpha emission line (Lyα), the typical intensive 10.2 eV radiation ascribed to the early phase of galactic evolution. We show that only the aminonitrile precursors are characterized by positive ee in the Lyα region, explaining why right-handed circularly polarized Lyα (R-CP-Lyα) induces homologous L-amino acids. This study shows that the homochirality of amino acids is produced at the aminonitrile precursors stage. (150/150words)

Amino acids (AAs) are the fundamental building blocks of proteins in living organisms on Earth, and AAs, with the only exception of glycine, have a chiral center. Their enantiomeric forms, L- and D-AAs, are equally produced by nonbiological chemical syntheses. However, L-AAs are almost exclusively used in living systems. [START_REF] Meierhenrich | Amino acids and the asymmetry of life: caught in the act of formation 1st ed[END_REF] This AAs homochirality is thought to have originated in the early stage of chemical evolution when the AAs were synthesized non-biologically. Even if the early enantiomeric excess (ee) is very low, it can be enhanced through recrystallizations and polymerizations. [START_REF] Bonner | The origin and amplification of biomolecular chirality[END_REF][START_REF] Elsila | Meteoritic Amino Acids: Diversity in Compositions Reflects Parent Body Histries[END_REF][START_REF] Green | The macromolecular route to chiral amplification[END_REF] Since the first chiral symmetry-breaking event determines the selection of L- AAs or D-AAs, namely an L-or D-world on Earth, the origin of ee achieved by an asymmetrical event is of crucial importance. [START_REF] Bonner | The origin and amplification of biomolecular chirality[END_REF] Their presence and related ee of AAs in the Murchison meteorite, fell in Australia in 1969, provided an unprecedented clue about a cosmic origin of homochirality. [START_REF] Cronin | Enantiomeric excesses in meteoritic amino acids[END_REF] The detected AAs turn out to be not only proteinogenic but also abiotic, including β-and γ-amino acids, and their %ee were generally positive, where the %ee is defined as (CL -CD)/(CL + CD)×100 and CL and CD are the amounts of each enantiomer. Isotopic ratios of meteoritic AAs are different from the ratios of terrestrial ones, and high %ee were also measured in abiotic AAs such as isovaline (Iva). The observed %ee for AAs in the Murchison meteorite are 1.2, 0.4, 2.2 and 8.4 for alanine (Ala), 2aminobutyric acid (Aba), valine (Val) and Iva, respectively. [START_REF] Cronin | Amino Acid enantiomer excesses in meteorites: origin and significance[END_REF] These results have opened a novel paradigm about the cosmic origin of the homochirality. [START_REF] Cronin | Enantiomeric excesses in meteoritic amino acids[END_REF][START_REF] Cronin | Amino Acid enantiomer excesses in meteorites: origin and significance[END_REF][START_REF] Engel | Isotopic evidence for extraterrestrial non-racemic amino acids in the Murchison meteorite[END_REF][START_REF] Glavin | Enrichment of the amino acid L-isovaline by aqueous alteration on CI and CM meteorite parent bodies[END_REF] It has been proposed that ultraviolet (UV) circularly polarized light (CPL) in star-forming regions might have played a significant role in inducing ee in interstellar organic molecules which, in turn, were probably subsequently delivered to the early Earth by meteorites. [START_REF] Bailey | Circular polarization in star-formation regions: implications for biomolecular homochirality[END_REF] In star-forming regions, strong infrared CPL has been detected. [START_REF] Bailey | Circular polarization in star-formation regions: implications for biomolecular homochirality[END_REF][10][11] Laboratory experiments have shown that circular polarized light (CPL) irradiation produces an asymmetric photosynthesis and decomposition of AAs eventually leading to ee. [12][13][14][15][16][17][18] Based on photolysis experiments and circular dichroism (CD) measurement of L-AAs in the solid state, it has been proposed that the farultraviolet (FUV) region between 170 and 200 nm (7.3-6.2 eV) is the effective wavelength range to induce the homochirality, since the CD spectra have equally the positive and large magnitude for several key amino acids such as Ala, Aba and Val. [START_REF] Norden | Was photoresolution of amino acids the origin of optical activity in life[END_REF][START_REF] Meierhenrich | Circular dichroism of amino acids in the vacuum-ultraviolet region[END_REF][START_REF] Meinert | Anisotropy Spectra of Amino Acids[END_REF][START_REF] Kaneko | Natural circular dichroism spectra of alanine and valine films in vacuum ultraviolet region[END_REF][START_REF] Tanaka | Present status of vacuum ultraviolet natural circular dichroism measurement system using polarizing undulator at TERAS BL5 beamline[END_REF][START_REF] Tanaka | Chiroptical study of αaliphatic amino acid films in the vacuum ultraviolet region[END_REF] However, the CD spectra of Iva shows a reversed CD sign, suggesting that the production of D-Iva instead of L-Iva is induced by the FUV. [START_REF] Meierhenrich | Circular dichroism of amino acids in the vacuum-ultraviolet region[END_REF] Furthermore, CD alternates in sign and sum to zero over the whole spectrum according to the Kuhn-Condon sum rule. [START_REF] Kuhn | The physical significance of optical rotatory power[END_REF][START_REF] Condon | Theories of optical rotatory power[END_REF] Hence, to produce ee on AAs, the spectrum of UV CPL must be narrowed to a single band. It is known that strong Lyman-α (Lyα) radiation, peaked at 10.2 eV, is emitted from ionized hydrogen (HII) in star-forming regions. In particular, in the early evolutionary stage, the Milky Way is thought to have been be embedded in intense pan-galactic Lyα light. Such an early phase of galaxies is categorized as Lyα emitters (LAEs). [START_REF] Shibuya | What is the physical origin of strong Lyα emission? II. Gas kinematics and distribution of Lyα Emitters[END_REF][START_REF] Mori | The evolution of galaxies from primeval irregulars to present-day ellipticals[END_REF] Recently, it has been shown that high CPL of Lyα originates from scattering with interstellar dust. [START_REF] Fukushima | High circular polarization of near-infrared light induced by micronsized dust grains[END_REF][START_REF] Fukushima | Generation of high circular polarization of Lyman α photons responsible for biological homochirality[END_REF] Another unsolved issue is that the asymmetric photoreactions supposed to determine the final ee of AAs are not entirely clarified. Specifically, photosynthesis experiments have shown that 10.2 eV R-CPL produces 1.04 %ee of Ala 18 , whereas the CD values indicate that positive ee of α-H amino acids are achieved via L-CPL photodissociation. These results are mutually inconsistent. We remark that photoelectron circular dichroism (PECD) indicated that Ala, proline and serine are commonly photoionized by CP-Lyα with an identical angular anisotropy [START_REF] Maurice | Chiral asymmetry in the photoionization of gas-phase amino-acid alanine at Lymann-a radiation wavelength[END_REF][START_REF] Hadidi | Conformer-dependent vacuum ultraviolet photodynamics and chiral asymmetries in pure enantiomers of gas phase proline[END_REF][START_REF] Hadidi | Electron asymmetries in the photoionization of chiral molecules: possible astrophysical implications[END_REF][START_REF] Hartweg | Condensation effects on electron chiral asymmetries in the photoionization of serine: from free molecules to nanoparticles[END_REF] and the main photoionized product of Ala by CP-Lyα is a fragment of m/z=44, identified as CH3CH=NH2 + by releasing COOH. [START_REF] Pan | Intramolecular hydrogen transfer in the ionization process of a-alanine[END_REF] Photoreactions of Ala have been fully characterized, but they are not sufficient to explain their photosynthetic reactions. To this aim, we considered the possible formation of other chiral species prior to AAs, and these should be characterized. To address these crucial open issues, we investigated the initially induced ee for key AAs including Ala, Aba, Val, and Iva and all their precursors in the typical abiotic reactions, according to the Strecker synthesis (Fig. 1).

Their computed CD spectra are obtained by an accurate ab initio method. Our computational results provide convincing evidence for a crucial chemical species responsible for the origin of homochirality in amino acids. In our computational approach, the most stable conformations of chiral molecules were identified using the random connection (RC) method. [START_REF] Shoji | Comprehensive search of stable isomers of alanine and alanine precursors in prebiotic syntheses[END_REF] This RC method makes use of a simplest force field in the initial geometry optimization for an extensive search in the conformational space. Details are reported in our former study. [START_REF] Shoji | Comprehensive search of stable isomers of alanine and alanine precursors in prebiotic syntheses[END_REF] We investigated the molecules in both zwitterionic/cationic and non-ionic forms, although the molecules on icy dust surface are expected to take the zwitterionic/cationic form. After discussing the results on the zwitterionic/cationic form, we focus on those for the non-ionic/gas form. The related energetics upon structural optimization and vibrational frequency analysis for zero-point correction were performed at the B3LYP//6-311++G** theoretical level. For zwitterionic/cationic form in solvation, polarizable continuum model (PCM) was adapted. The DFT approach can reproduce the stable molecular structures with relative energies of accuracy comparable to those obtained by the higher accuracy CCSD(T) method for small size molecules. [START_REF] Shoji | Comprehensive search of stable isomers of alanine and alanine precursors in prebiotic syntheses[END_REF] Moreover, the DFT method has been shown to be applicable for a sufficient number of conformational samplings and larger size molecules. [START_REF] Shoji | Comprehensive search of stable isomers of alanine and alanine precursors in prebiotic syntheses[END_REF][START_REF] Shoji | Molecular mechanism of a large conformational change of the quinone cofactor in the semiquinone intermediate of bacteria copper amine oxidase[END_REF][START_REF] Hashimoto | Specific zinc binding to heliorhodopsin[END_REF][START_REF] Sato | Lya Irradiation in the Early Phase Milky Way Galaxy Is Responsible for Initiating the Homochirality of Amino Acid[END_REF] In the most stable conformations, photoabsorption (ε) and CD spectra have been computed. The CD value is defined as the difference of molar absorptivities between left-circular polarized light (CPL) and right-CPL, Δε = ε(L) -ε(R). The CD spectra were calculated at the Symmetry Adapted Cluster/Configuration Interaction (SAC-CI/cc-pVTZ) theoretical level [START_REF] Seino | SAC and SAC-CI calculations of excitation and circular dichroism spectra of straight-chain and cyclic dichalcogens[END_REF] for L-form enantiomers of Fig. 1. 150 excited states were included to evaluate the spectra up to the VUV region close to 12 eV. We assumed a Gaussian type distribution with a 0.60 eV bandwidth [START_REF] Seino | SAC and SAC-CI calculations of excitation and circular dichroism spectra of straight-chain and cyclic dichalcogens[END_REF][START_REF] Yabana | Application of the time-dependent local density approximation to optical activity[END_REF] to compare with experimental absorption and CD spectra of alanine, and their relative values are provided in the discussion of the spectra. We set the base lines of ε0(6.6eV) = 1.0 and Δε0(6.6eV) = 1.0 in L-alanine. This is a reasonable assumption since we introduced a scaled time parameter, t' in evaluating %ee (%eeCD), which corresponds to ξ for %eeg. [START_REF] Sato | Lya Irradiation in the Early Phase Milky Way Galaxy Is Responsible for Initiating the Homochirality of Amino Acid[END_REF] All the calculations were performed using the Gaussian16 program package. [START_REF] Frisch | Revision C.01[END_REF] Molecular structures were drawn using the visual molecular dynamics program. [START_REF] Humphrey | VDM: visual molecular dynamics[END_REF] Further theoretical and computational details are reported in the supporting information. An extended view of the absorption and CD spectra for all the species considered are presented in the supporting information (Figs. S1-S8).

Molecular structures of Ala, Aba, Val and Iva in the amino acid form (=Ala-AA, Aba-AA, Val-AA, Iva-AA) and their computed %ee spectra in zwitterionic/cationic form are shown in Fig. 2 (A) and (B). All the %ee values (%eeCD) are obtained by using the calculated CD values. As already discussed in our former study, [START_REF] Sato | Lya Irradiation in the Early Phase Milky Way Galaxy Is Responsible for Initiating the Homochirality of Amino Acid[END_REF] the %ee spectra for the first three AAs are rather similar and comparable to their corresponding experimental CD spectra [START_REF] Tanaka | Chiroptical study of αaliphatic amino acid films in the vacuum ultraviolet region[END_REF] ; %ee and CD values become positive in the FUV region around 6.6 eV and negative in the VUV region around 10 eV.

Comparisons between calculated and experimental CD spectra of AAs in zwitterionic form are shown in Fig. S1 of the supporting information. The small positive peak of L-Aba-AA at 8.6 eV reduces in the spectra at 298 K by considering the contribution from the second stable conformation at 0.436 kcal mol -1 , but remains unperturbed at 80 K (Fig. S1). [START_REF] Sato | Lya Irradiation in the Early Phase Milky Way Galaxy Is Responsible for Initiating the Homochirality of Amino Acid[END_REF] The %ee spectrum of L-Iva-AA (Fig. 2(B)) is characterized by a feature roughly opposite to the spectra of other αamino acids, i.e., negative at 6.7 eV (184 nm), positive at 7.5 eV (164 nm), negative at 8.7 eV (142 nm), and positive at 9.8 eV (127 nm). In the Lyα region around 10.2 eV, the %ee of L-Iva-AA is 0.5, hence reversed with respect to the negative %ee of other α-H amino acids.

In gas phase conditions, experimental CD spectra of L-Ala-AA, L-Aba-AA, L-Val-AA and L-Iva- AA were observed in the region 4.4-9.5 eV (280-130 nm). [START_REF] Meinert | Amino acid gas phase circular dichroism and implications for the origin of biomolecular asymmetry[END_REF] The CD spectra of the former three AAs have similar shapes with a positive peak at about 5.9 eV (210 nm), a negative peak at about 7.3 eV (170 nm) and a following positive peak at about 8.3 eV (150 nm). [START_REF] Meinert | Amino acid gas phase circular dichroism and implications for the origin of biomolecular asymmetry[END_REF] The CD spectra of L- Iva-AA is, instead, reversed, with a negative peak at 6.2 eV (200 nm), positive one at 7.0 eV (177 nm) and negative one at 8.1 eV (154 nm). [START_REF] Meinert | Amino acid gas phase circular dichroism and implications for the origin of biomolecular asymmetry[END_REF] Our calculated CD spectra of the former three AAs in the non-ionic form are substantially unchanged in terms of positive (215 nm, 208 nm, 206 nm), negative (180 nm, 166 nm, 156 nm), and positive (156 nm, 149nm (convex upward but with a value still negative), 138nm) peaks for L-Ala-AA, L-Aba-AA and L-Val-AA, respectively, and inverted peaks with negative 5.8 eV (214nm), positive 6.7 eV (186nm) and negative 7.5 eV (165nm) amplitudes for L-Iva-AA (Fig. S2). The gas phase CD spectra was observed at 460 K. On the theoretical front, the computed spectra can be further improved by estimating the contributions from higher energy conformations (Fig. S2). [START_REF] Meinert | Amino acid gas phase circular dichroism and implications for the origin of biomolecular asymmetry[END_REF] Here, we focus on the low temperature photodecomposition property in molecular cloud conditions (T<80 K), and their spectra by using the most stable conformations, being the contribution from higher energy conformations negligible.

Computed %ee spectra of AAs in non-ionic/gas form with the most stable conformations are shown in Fig. 3 (A) and (B). Although identical signs of %ee are induced at the 7.2 eV (172 nm) and 11 eV (113 nm) with negative and positive amplitudes, respectively (Fig. 3(B)), these do not originate from the 6.6 eV and 10.2 eV regions, and most of these AAs are located near to the crossing points. Therefore, AA in both zwitterionic and non-ionic forms cannot provide a convincing explanation of the common L-form induction in both the 6.6 eV FUV and 10.2 eV VUV regions. The first amino acid precursor in the Strecker synthesis is the amino propanal (AP). In this form, the computed %ee are shown in Fig. 2 (C). An evident feature is the fact that these spectra are characterized by peaks deeply different from those of AAs. In particular, the strong peak at 6.6 eV is absent. In the AP species, the common signature of %ee is represented by the peaks centered around 7.5-8.6 eV (165-145 nm) and 9.6-9.8 eV (127-129 nm) as negative and positive values, respectively. In the Lyα region, negative and large %ee were obtained for L-Iva-AP and L-Aba-AP, whereas both large and small positive %ee were found for L-Val-AP and L-Ala-AP. In the gas phase, common signatures of %ee at 6.6 eV and 9.8 eV as positive and negative amplitudes, respectively (Fig. 3(C)). In the Lyα region, %ee is positive for L-Aba, while %ee values for L-Val and L-Iva are negative. These results suggest that the AP species are unlikely to contribute to the origin of homochirality for all AAs.

The second amino acid precursor along the Strecker synthesis is amino nitrile (AN), for which we computed the %ee shown in Fig. 2 (D) and Fig. 3(D) for cationic and gas phase, respectively.

The spectra in cation (Fig. 2 (D)) are further shifted toward higher energy regions, with typical signatures represented by the peaks at 8.0-9.2 eV (155-135 nm) and 10.1-11.0 eV (123-113 nm) with negative and positive amplitudes, respectively. Hence, in the Lyα region, the %ee values turn out to be positive for all the ANs. We remark that the %ee of L-Iva-AN results to be 7.4, which is significantly larger in comparison with the 1-2 %ee of other ANs (see Table 1). These estimated %ee values are very close to the experimental ones in the Murchison meteorite. We remark that the magnitude of %ee depends on the extent of the photolysis and these, in turn, are highly influenced by amplification processes in aqueous alteration. Anyhow, a direct comparison between the computed %ee values and %ee detected in meteorites is clearly insightful and provides a solid basis to draw meaningful conclusions. For ANs in gas phase (Fig. 3(D)), %ee spectra are rather similar in the range 5.5-8 eV (230-155 nm) and 8-9 eV (155-140 nm) with negative and positive amplitudes, respectively. The broad region extending from 5.5 to 8 eV can be interpreted as stability upon the shift of light wavelength. However, in the Lyα region, only Iva has a negative %ee value, and the sign of %ee is not the same for all ANs. We note that strong correlations between %ee and the parent body aqueous alteration have been reported in former works. [START_REF] Elsila | Meteoritic Amino Acids: Diversity in Compositions Reflects Parent Body Histries[END_REF][START_REF] Glavin | Enrichment of the amino acid L-isovaline by aqueous alteration on CI and CM meteorite parent bodies[END_REF] This implies that the exact final ee values are not predictable.

Nonetheless, the positive sign of ee is unaffected and on this aspect the present study is mainly focused. We show in this work that the AN species in cation forms have common positive %ee values (L-amino acids are formed by R-CPL) in the Lyα region, which is consistent with asymmetric photosynthesis experiments by Modica et al. 18 Modica et al. 18 have shown that 6.6 eV R-CPL induced D-Ala (%ee < 0), in open contrast with the results of irradiation of 10.2 eV CPL.

Values of %ee for ANs in the cationic form are close to zero in Fig. 2(D), indicating that 6.6 eV CPL does not affect their asymmetric photolysis. Nonetheless, the broad and negative %ee of ANs in gas phase are consistent with the Modica's 6.6 eV result 18 . We expect that a minority of ANs take gas forms and are involved in asymmetric photolysis contributing to their non-zero %ee in the case of 6.6 eV irradiation.

Former theoretical studies have shown that hydrolysis of aminoacetonitrile to glycine is characterized by a higher electronic energy barrier (ΔE ≠ = 27-34 kcal mol -1 ) than the energy barrier in the formation of aminoacetonitrile (ΔE ≠ = 8-9 kcal mol -1 ). [START_REF] Woon | Pathways to glycine and other amino acids in untraviolet-irradiated astrophysical ices determined via quantum chemical modeling[END_REF][START_REF] Rimola | Deep-space glycine formation via Strecker-type reactions activated by ice water dust mantles. A computational approach[END_REF] The high energy barrier for hydrolysis suggests that the AN form, and not the AP or AA forms, is dominant in molecular clouds at temperatures T < 100 K. Elsila et al. reported that the carbon atom of the acid group of glycine is mainly derived from the carbon atom in HCN, not from other constituent such as CH3OH. [START_REF] Elsila | Mechanisms of amino acid formation in interstellar ice alalogs[END_REF] This observation, obtained by isotopic labeling, is consistent with the fact that the acid group of an amino acid is formed by hydrolysis of nitrile group in the Strecker type synthesis.

Moreover, it is also consistent with the typical observation that nitrile precursors are more stable under UV and cosmic rays irradiation in interstellar regions compared to amino acids. [START_REF] Bernstein | The lifetimes of nitriles (CN) and acids (COOH) during ultraviolet photolysis and their survival in space[END_REF] Therefore, amino nitrile can survive longer on meteorites. In the high-mass star forming region SgrB2, amino acetonitrile, the precursor of glycine, was detected, but 2-aminopropionitrile, Ala-AN, has never been observed so far, because they are below the limit of detection. [START_REF] Belloche | Detection of amino acetonitrile in Sgr B2(N)[END_REF][START_REF] Møllendal | Rotational spectrum of a chiral amino acid precursor, 2aminopropionitrile, and searches for it in Sagittarius B2(N)[END_REF] However, the detection of Ala-AN is a more practical probe with respect to the detection of Ala.

Our recent theoretical study also supports the notion that aminonitrile is the most stable molecule among the chiral precursors of AAs. This has been rationalized in terms of the minimum energy principle, namely, the most abundant molecule in the interstellar medium is directly correlated to its stability among all possible isomers. [START_REF] Shoji | Comprehensive search of stable isomers of alanine and alanine precursors in prebiotic syntheses[END_REF] Alanine and 2-aminopropanal (=Ala-AA, Ala-AP) are characterized by more stable isomers, N-ethylcarbamic acid and propenamide, with relative energies significantly lower by 10.3 and 23.9 kcal mol -1 , while 2-aminopropanenitrile (=Ala-AN) is the most stable among the isomers. Therefore, Ala-AN is expected to be the easiest chiral molecule formed in the Strecker synthesis to alanine.

In conclusion, our theoretical evaluation of the CD spectra of amino acid precursors via accurate ab initio method (SAC-CI) provide a clear indication on the induced ee of Ala, Aba, Val and Iva in their AA, AP and AN forms. From an astronomical standpoint, intense Lyα emissions around 10.2 eV are a dominant feature and can be strongly circular polarized. We found that a positive ee is present in all ANs in the 10.2 eV region, and is kept in the broad range of 10-11 eV. Therefore, we expect that aminonitriles are at the origin of homochirality of amino acids. Specifically, aminonitrile precursors are irradiated with R-CP-Lyα, and positive ee is formed upon photolysis.

We can infer that the formation of amino acids is possible by aqueous alteration, which requires heat and water molecules. Kawasaki and coworkers have shown that the %ee of an α-AN (Nbenzhydryl-α-p-tolylglycine nitrile) can increase up to 96% ee by spontaneous crystallization. [START_REF] Kawasaki | Spontaneous formation and amplification of an enantioenriched aamino nitrile: a chiral precursor for Strecker amino acid synthesis[END_REF] The remarkable property of AN is achieved by the preferential formation of a conglomerate crystal accompanied by a faster racemization in solution compared to AAs. [START_REF] Kawasaki | Spontaneous formation and amplification of an enantioenriched aamino nitrile: a chiral precursor for Strecker amino acid synthesis[END_REF] This result suggests that an amplification of ee can be achieved as soon as ANs are formed (and not AAs)

Fig. 1

 1 Fig. 1 Chiral intermediates leading to the formation of amino acid according to the Strecker

Fig. 2 (

 2 Fig. 2 (A) The most stable structures of L-amino acids: alanine (Ala), 2-aminobutyric acid (Aba),

  .

Table 1 .

 1 Calculated enantiomeric excesses (%ee) of chiral molecules: amino acid (AA), amino propanal (AP), amino nitrile (AN) under the R-CPL irradiation at 6.6 eV and 10.2 eV photon energies. Values in parentheses are at 6.6 eV.

  along the Strecker synthesis. Nowadays, sample return of uncontaminated extraterrestrial material is possible as provided by the Japan Aerospace Exploration Agency's (JAXA's) Hayabusa2 mission. A variety (10) Fukue, T. et al. Extended high circular polarization in the Orion massive star forming region: implications for the origin of homochirality in the solar system. Orig. Life Evol. Biosphere 2010, 40, 335-346. (11) Kwon, J. et al. Near-infrared circular polarization images of NGC 6334-V. Astrophys. J. Rubenstein, E.; Bonner, W. A.; Noyes, H. P.; Brown, G. S. Supernovae and life. Nature 1983, 306, 118. (13) Bailey, J. Chirality and the origin of life. Acta Astronautica 2000, 46, 627-631. (14) Meierhenrich, U. J. et al. Asymmetric vacuum UV photolysis of the amino acid leucine in the solid state, Angew. Chem. Int. Ed. 2005, 44, 5630-5634. (15) Nuevo, M. et al. Enantiomeric separation of complex organic molecules produced from irradiation of interstellar/circumstellar ice analogs. Adv. Space Res. 2007, 39, 400-404. (16) Marcellus, P. de et al. Non-racemic amino acid production by ultraviolet irradiation of achiral interstellar ice analogs with circularly polarized light, Astrophys. J. Lett. 2011, 727, L27. (17) Meinert, C. et al. Photonenergy-Controlled Symmetry Breaking with Circularly Polarized Light, Angew. Chem. Int. Ed. 2014, 53, 210-214. (18) Modica, P. et al. Enantiomeric excesses induced in amino acids by ultraviolet circularly polarized light irradiation of extraterrestrial ice analogs: a possible source of asymmetry for prebiotic chemistry. Astrophys. J. 2014, 788, 79-89.

	2013, 765, L6-L11.
	(12)

of amino acids of, at least, 23 species including β-amino acids were detected in Ryugu samples. [START_REF] Nakamura | On the origin and evolution of the asteroid Ryugu: a comprehensive geochemical perspective[END_REF] We stress the importance of detection of aminonitriles and their %ee values in asteroids and meteorites, which may provide a direct validation of the present theoretical results. Further analyses and theoretical investigations for other prebiotic molecules related to D-sugars and nucleobases will provide new insights into the chemical evolutions of molecules and the origin of life.

ASSOCIATED CONTENT Supplementary information file containing computational details, comparison to experimental CD spectra and numerical simulation of ee induction in different ε condition, is available from Web site.

AUTHOR INFORMATION

Notes

The authors declare no competing financial interests.


Jean-Lynce Gnanago

Tony Gerges

Laura Chastagnier

Emma Petiot

Vincent Semet

Philippe Lombard

Marquette Christophe

Michel Cabrera

Simon A Lambert

Christophe Marquette

Introduction

Tissue engineering for regenerative medicine have been developing for a few decades now and the number of applications is increasing to tackle the shortage of organ donors. From cartilage to skin, a wide range of tissues are currently being studied with the goal of restoring or replacing damaged tissues 1 . While massive progress has been achieved to produce 3D printed constructs, only few systems can allow both monitoring and 3D characterization of tissue constructs during their growth 2,3 . Despite a lower spatial resolution compared to optical modalities, Magnetic Resonance Imaging (MRI) allows non-destructive 3D characterizations of soft tissues based on multiscale parameters that are key in assessing tissue development [START_REF] Frese | Nondestructive monitoring of tissue-engineered constructs[END_REF][START_REF]Magnetic resonance imaging in tissue engineering[END_REF] . In this study, we decided to focus on characterizing the Apparent Diffusion Coefficient (ADC) known to be a marker of cell density [START_REF] Padhani | Diffusion-Weighted Magnetic Resonance Imaging as a Cancer Biomarker: Consensus and Recommendations[END_REF] and built a MR-bioreactor to probe the ADC of a growing tissue [START_REF]Magnetic resonance imaging in tissue engineering[END_REF][START_REF] Kotecha | Reduction of water diffusion coefficient with increased engineered cartilage matrix growth observed using MRI[END_REF] . Performing MR characterization of growing tissues is challenging because it requires to couple an imaging apparatus and a bioreactor which are usually not MR-compatible. To our knowledge, only one group tackled this issue by building a dedicated MRcompatible bioreactor [START_REF] Othman | The e -Incubator: A Magnetic Resonance Imaging-Compatible Mini Incubator[END_REF] to be used with a commercial surface MR coil. Generally, those coils are large (~1-10cm) compared to engineered tissues (~0.1-5cm) and thus do not allow optimal MRI conditions. In addition to that, using such a setup consisting in two devices adds complexity to an already complex modality, especially for non-experts. The resulting poor integration of the bioreactor and the MR coil can result in non-reproductible measurements. Hence, we decided to pursue our previous work [START_REF] Gnanago | Compact MRI bioreactor for real-time monitoring 3D printed tissueengineered constructs[END_REF] and propose here an improved MR-bioreactor for ADC assessment of a 3D printed tumor tissue model.

Method

Based on our previous work based on plastronic techniques 2 8 , both the electrical and mechanical aspects of our MR-bioreactor were improved.

The coil geometry and the passive decoupling scheme remained unchanged but two electrical connections needed to be modified. First, the connection between the coil and the decoupling circuit integrated within the top cap has been made using a pair of twisted vias in order to avoid parasitic loops leading to imaging artifacts (figure 1a,1b). Second, the connection between the MR-bioreactor and the scanner has been displaced to an external 3D printed cover to reduce the mechanical load on the MR-bioreactor copper tracks (figure 1c). The connection between this cover and the MRbioreactor is made using shield fingers (figure 5a).

Mechanical stability and hence measurement repeatability of the experiments were improved with a bench support designed specifically our imaging platform (figure 5b,5c).

The imaging platform we used was equipped with a 7 T Bruker MRI Scanner running ParaVision 5.1 and a transmitting 72mm birdcage.

To illustrate the ability of our MR-bioreactor to obtain morphological images of small samples we 3D printed the logo of our laboratory and filled the MR-bioreactor with a 0.9% sodium chloride solution.

3D printed tissue models were provided by 3d.FAB platform. At time t=0, 3 tissues samples were printed and put inside a 37°C 5% CO2 dedicated incubator. The tissues samples were 80% porous hydrogel scaffolds containing HT29 cells and fibroblasts (CAF). Each week, one sample was placed in our MR-Bioreactor for MRI characterization. After the MRI experiment, a calcein-am marking of living cells was performed on the sample.

During the experiments, tissues were immersed in a 0.9 % sodium chloride solution to ensure tissue viability during the acquisition time. Fluid circulation was also needed for removing air bubbles.

The samples were imaged using three acquisition sequences:

-Two morphological sequences. One axial and one coronal Turborare T2 (Repetition time (TR)=3700ms, Echo time (TE)=20ms, 16 averages, Field-of-view(FOV)=1.92*1.92, 256² matrix, 400 microns slice thickness) -One quantitative EPI ADC diffusion sequence (TE=19.39ms, TR=5250ms, 8 segments, 8 averages, FOV=1.92*1.92, 128² matrix, b=0 100 200 300 500 750 1000 s/mm²) in order to quantify the ADC.

Regions of interest (ROI) were positioned within the sample. The ADC was computed using the ParaVision's post-processing tool.

Results

Figures 1a,1b demonstrate the artefact suppression using our twisted vias. Moreover, figures 1b,1c shows how having an additional connection with a connected cover between the MR-bioreactor and the terminal can be detrimental to the SNR.

A 40µm in plane resolution image of the logo of our laboratory can be seen figure 2.

A decreasing tendency of the ADC over the three weeks can be seen figure 3. On figure 5, the calcein AM marking of the living cells illustrate an increasing number of cells which is in agreement with the results shown by the ADC.

Conclusion

In this preliminary work, we were able to follow the cell density of our tissues. An analytical model [START_REF] Ellingson | Spatially quantifying microscopic tumor invasion and proliferation using a voxel-wise solution to a glioma growth model and serial diffusion MRI: Image Maps of Tumor Invasion and Proliferation[END_REF] along with a higher sampling rate would allow to derive the proliferation and cell motility from our measurements. However, that would necessitate to have a more precise positioning of the sample with no displacement or deformation which is challenging due to samples' mechanical properties and fluid circulation. In any case, those results are the first step towards in vitro 3D tumor tissue model characterization.

Figures

Figure 1 :

 1 Figure 1: Electronic conception of the MR-bioreactor and its effects (A) Previous work exhibiting an imaging artefact. (B) Second version with twisted vias and a direct connection to the scanner (C) Third version with twisted vias and a connection to the scanner using an additionnal 3D printed housing. (D) 3D Flash (150µm3 resolution TR=33,81ms, TE=15ms) image produced by the first prototype (E) 3D Flash (300µm3 resolution TR=33,81ms, TE=15ms) image produced by the second prototype (F) 3D Flash image (200µm3 resolution, TR=15ms,TE=3ms) produced by the third prototype.

Figure 2 :

 2 Figure 2: 3D Printed sample for our MR-bioreactor characterization. (A) A picture of the 3D printed sample made with the logo of our laboratory (B) The resulting turborare 2D (40µm in plane resolution, slice thickness=400µm, TR=2000ms, 8 avg) image using our MR-bioreactor.

Figure 3 :

 3 Figure 3: The evolution of the Apparent Diffusion Coefficient over the three weeks of experiments. The error bars are the standard deviation calculated with Paravision 5.1 post-processing tool.

Figure 4 :

 4 Figure 4: The MR-Bioreactor complete set-up. (A) A close-up of our MR-Bioreactor and its dedicated housing. (B) A view of the separated pieces of our MR-Bioreactor setup. 1. A centering ring designed to ensure the perfect alignement of the setup within the bore. 2. A PMMA bench carries the MRbioreactor inside the bore. 3. A support designed to adapt the bench to the MRI platform. (C) A complete view of the set-up in place.

Figure 5 :

 5 Figure 5: General view of the images acquired during the 3-week study using our MR-Bioreactor and a calcein am marking. Morphological images can be seen in the top row. The ADC maps can be seen in the middle row. The images of the living cells using a calcein am marking can be seen in the bottom row.

Acknowledgement

This work was supported by a grant from the Agence National de la Recherche (Estimate Project N° ANR-18-CE19-0009-01). The financial support provided by Ingénierie@Lyon, member of the Carnot Institutes Network (Metafab 3D project) for the postdoctoral scholarship of Dr T. Gerges is also acknowledged. Moreover, the role of CERMEP -Imagerie du vivant and especially Radu Bolbos is acknowledged.


Dr Ambrose A Melvin

Dr Bertrand Goudeau

Dr Wojciech Nogala

Alexander Kuhn
email: kuhn@enscbp.fr

Prof A Kuhn

Spatially Controlled CO2 Conversion Kinetics in Natural Leaves for Motion Generation

Living systems that can spontaneously exhibit directional motion belong to diverse classes such as bacteria, sperm and plank-ton. They have fascinated scientists in recent years to design completely artificial or biohybrid mobile objects. Natural ingredients, like parts of plants, have been used to elaborate miniaturized dynamic objects, which can move when they are combined with other, non-natural, building blocks. Herein, we report that the precise structural tailoring of natural plant leaves allows generating a spatially predefined and confined release of oxygen gas, due to the conversion of carbon dioxide. This constitutes the driving force for generating motion, which is solely due to the respiration of leaves by photosynthesis. The rate of gas evolution can be fine-tuned by changing the light intensity and the leaf size, allowing ultimately to control the motility of objects with dimensions ranging from the millimeter to the micrometer scale.

Introduction

Nature has designed highly sophisticated dynamic systems of various sizes over millions of years through gradual optimization. [START_REF] Bastos-Arrieta | [END_REF] Especially at small scales, natural swimmers with a large variety of functionalities have emerged during evolution, based on very versatile strategies for generating motion. [2] Unfortunately, these purely natural systems are not directly suitable for practical applications due to a lack of direct motion control. However, they have been a great source of inspiration for elaborating different synthetic and biohybrid swimmers. [START_REF] Bastos-Arrieta | [END_REF]3] Such (semi-)artificial swimmers have proven to be promising candidates for carrying out a large diversity of tasks for applications ranging from environmental remediation to nanomedicine.[4] These swimmers can be triggered and externally controlled, for example by light, magnetic, electric, and acoustic forces. [5] They can also be propelled by other mechanisms, based on the use of (bio)chemical fuel that results in self-electrophoresis or bubble generation, but with a certain risk that either the fuel or the reaction products are toxic. [5e,5f,6] Alternative options, providing onboard fuel, may have some potential problems, e.g. related to the complexity of the swimmer's architecture or its lifetime. Completely artificial swimmers might also have some drawbacks compared to their natural counterparts, especially when there is a need to follow a complex path, or to change body shape in order to adapt to different local environments. Consequently, biohybrid microswimmers were introduced as an interesting intermediate between natural and artificial swimmers. They are often composed of inanimate objects and microorganisms. The latter can use their flexible body parts such as flagella, [2b,7] and have been exploited e.g. for cargo delivery and biomedical applications. [8] Microorganisms also employ diverse sensory systems, hence allowing them to perform taxis based locomotion in various media and in the presence of different gradients of parameters such as light, temperature and pH, or oxygen and nutrient concentration. [9] Although still being in their early stage of development, biohybrids such as BacteriaBots have already shown potential for applications in drug delivery, as biomarkers, or motile whole cell sensors, [10] despite the fact that they are eventually also facing some problems e.g. in terms of scaling up their fabrication, lifetime and the interfacing of the biological with the synthetic part.[10b] In this context, bioinspired microswimmers using plant extracts have been proposed as an interesting alternative due to the easy fabrication process. [11] Based on a similar philosophy, the pigment chlorophyll and plant organelles have also been suggested to design elegant systems, either simply activated by light relying on natural photosynthesis, or using chemicals converted by a natural catalytic process, for powering motion at small scales. [12] As a complementary approach with respect to the literature we report herein the use of whole prisitine leaves for site-selective O2 evolution as a result of photosynthesis. The spatially controlled O2 evolution achieved by specific structural tailoring leads to the design of entirely natural macroand microswimmers. We want to stress that in the present study, in contrast to the majority of the systems reported in the literature, there is no need to use artificial classic chemical fuels, like hydrogen peroxide or other compounds such as for example sugar for some enzyme driven swimmers. The system works only with naturally present ingredients. Being absolutely independent of on-board or solution-based fuel, the objects are solely driven by the presence of light, water and carbon dioxide. This makes them a unique class of natural swimmers that might act in the future as a platform for developing original dynamic systems.

Results and Discussion

We performed initial tests with leaves from various plants, trees, and shrubs such as pine trees, aloe vera, wild grass etc.. After this first screening, we decided to work only with leaves from certain plants (i.e. Galeopsistetrahit, Filipendula and Pyracantha coccinea). The reason for choosing finally Pyracantha for more detailed studies was that it showed a roughly ten times higher photosynthesis rate when compared to Galeopsistetrahit and Filipendula. This could probably be attributed to a higher chlorophyll content and stomatal density, as well as to the leaf form (morphological and anatomical features) [13]. A high stomatal density facilitates gas (CO2) diffusion inside the leave, improving its fixation by the photosynthetic process, resulting in improved oxygen evolution. In this context, Pyracantha coccinea provides the best performance, as its dark colored leaves are considered to have a high chlorophyll content and thus a favorable photosynthesis rate. Therefore, leaves from Pyracantha coccinea (Figure 1A) have been studied in more detail with respect to oxygen evolution triggered by illumination in the presence of water and CO2. Photosystem I and II, present in the thylakoid membranes of the leaves, are responsible for light absorption and the subsequent electron transfer chain,[14] leading to CO2 fixation, combined with oxygen evolution (Figure 1B). The latter needs to be transported via diffusion, either through dedicated air channels inside the leaves, providing a low-resistance internal pathway for the exchange of gases between the plant organs, or through the stomata pores, located in the lower epidermis of the leaves, in order to be released into the surroundings (Figure 1C). During photo-synthesis, the oxygen level inside the leaf increases, and when the stomata pores are open, the leaf can take in carbon dioxide and release oxygen, however in a spatially not very well-focused and rather undefined way. In order to better control and predetermine a specific location for oxygen release, it is necessary to create a low-resistance exit for oxygen at preferential sites of the leaf. This can be achieved by generating on purpose defects at certain spots of the leaf architecture. Looking at the global organization of a leaf with a network of small veins, connected in a hierarchical way to bigger veins, the most appropriate position to concentrate and collect the gas in an efficient way seems to be at the extremity of the primary vein going through the center of the leaf (Figure 1D). Spongy mesophyll cells, present around the veins, help the transport and exchange of gases during the process of photosynthesis. Thus, in the first set of experiments, the extremity of the primary vein has been sectioned with precision at the edge of the leaf.

Control of CO2 conversion kinetics

The leaves were initially washed and immersed overnight in water in the dark to ensure that no photosynthesis and hence no gas evolution occurs. The leaves were then tested for oxygen evolution in CO2 saturated water in the presence of UV-Vis light (150 W, 10 lumen/cm2) (Figure 1D). CO2 saturated water accelerates the process of photosynthesis, eventually increasing oxygen evolution. A sharp cut was made at the base of the leaves in order to generate a well-defined and focused flow of oxygen, and the structure of the cross-section was characterized by microscopy (Supporting Figure S1). In order to confirm that the observed bubble evolution (Supporting Video S1) is directly related to the effect of illumination, the impact of light intensity on the kinetics of oxygen evolution has been studied. Different light intensities i.e. 100, 80, 60, 40 and 20 % were used (Figure 2A first row, and Supporting Video S2). For 100 % light intensity, the number of bubbles released per minute was 450. This value gradually decreases to 420, 385, 290 and 200 bubbles/min for 80, 60, 40 and 20 % light intensity, respectively. From 60 to 100 % a saturation effect is observed (Figure 2B), most likely because the turnover of the photocatalytic system is at maximum speed and therefore a further increase in photon flux does not lead to a proportional improvement of the rate of gas production. As the number of active thylakoids exposed to light is the crucial ingredient for photosynthesis, the leaf size should also have an important impact on the rate of oxygen evolution. In order to verify this, the leaf has not only been opened at one extremity of the primary vein as before, but also at the opposite side by consecutive cuts starting from the tip, leading to shortened leaves with a length of 20, 15, 10, 5 and 0.5 mm, respectively (Figure 2A second row, and Supporting Video S3). In order to still focus the oxygen release at only one spot, the edge of the leaf closer to the initial tip, which now also has in principle an open vein, was blocked with epoxy resin to stop the local oxygen release. The graph (Figure 2B) indicates a gas production of 1050 bubbles/min for the initial leaf (20 mm size) and a constantly decreasing release rate for the shorter versions, i.e. 750, 300, 120, 55 and 2 bubbles/min for leaves with 15, 10, 5, 2.5 and 0.5 mm length, respectively. Moreover, the size of the individual bubbles also gradually shrinks, especially in the case of the 500 µm leaf. Thus, the observed significant decrease in the number and size of bubbles seems to be directly correlated with the active leaf area exposed to light, and consequently also with the number of thylakoids available for the photo-conversion. To further confirm that the oxygen originates from photosynthesis, leaves were tested in aqueous media under different conditions which should influence the efficiency of gas production. Solutions were either purged with nitrogen, or an herbicide (glyphosate) was added to the medium. Prolonged bubbling of nitrogen gas through water results in the complete removal of dissolved carbon dioxide from the aqueous medium, and thus photosynthesis is no longer possible. In the case of glyphosate, the leaves absorb the herbicide upon prolonged exposure. Its presence inside the leaf leads to an inactivation of Calvin cycle enzymes, [15] resulting in the disruption of photosynthesis. The profound negative effect on oxygen evolution observed in these control experiments is summarized in Figure 2C and Table S1. Further interesting insight into the oxygen evolution kinetics can be gained by performing experiments with a single leaf and evaluating the phase shift between light switching and the onset or the end of gas production (Figure 2D and Supporting Video S4). A typical hysteresis of around 4 seconds has been measured in both directions, even after 1000 cycles. This indicates that the bubble formation is not just a purely physical process, but that the underlying biochemical machinery has to start and stop, inducing a delay in the respiration process. Prolonged cycling does not cause any noticeable damage to the leaves, thus qualifying them as interesting building blocks for a new class of photosensitive and photostable swimmers. Interestingly and most importantly, the site of oxygen evolution can be chosen at will. In order to define a preferential site of release, epoxy resin was used to block oxygen evolution from the central vein, directing the gas into the secondary veins and towards the periphery of the leaf (Figure 2E and Supporting Video S5). In this case, bubbles are generated exclusively at the two corners of the leaf (Figure 2E central image). If one of these corners is also blocked by applying resin to the corresponding side veins, single site oxygen evolution is observed only at one one corner of the leaf (Figure 2E right image). Furthermore, in order to demonstrate that it is also possible to control the spot of oxygen evolution along the primary vein, three holes were generated (Figure 2F) along the central vein of a leaf, i.e. 1) on the left side close to the tip, 2) in the center and 3) on the right side close to the base. Oxygen evolution could be observed individually at all spots. This clearly illustrates the multisite activity of the leaves and it also allows choosing precisely the spot of oxygen evolution for the purpose of swimmer design.

Electrochemical investigation of gas evolution

On the basis of the light-controlled gas evolution from the leaves, we assume that the process is primarily triggered by photosynthesis. To further confirm this hypothesis, we analyzed the produced gas by cyclic voltammetry, verifying that the evolved gas is oxygen. For this purpose, we utilized a Pt microelectrode for reducing oxygen electrochemically, as schematically illustrated in Figure 3A. A meniscus has been established between a Pt microwire and the air/water interface in such a way that all the generated bubbles were directed towards the electrode (Supporting Video S6), in order to perform measurements analog to the concept of single entity impact electrochemistry. [16] In the presence of light, the produced bubbles generate a significant temporary increase in oxygen reduction current, illustrated by the periodic spikes occurring in the potential range from -0.1 to -0.8 vs Ag/AgCl (Figure 3B). This corresponds exactly to the domain of potential where oxygen reduction is possible, as indicated by the comparison of the cyclic voltamperograms recorded in the absence (Figure 3B black curve) and in the presence (Figure 3B red curve) of oxygen in the gas phase above the liquid.

The constant frequency of mechanical impacts of the individual bubbles translates a very regular gas production of the leaf (Figure 3C). The associated charge, obtained by integrating the current spikes (Figure 3D) also shows an almost perfect regularity, meaning that every gas bubble is fetched by the meniscus in a reproducible way.

Leaf based microswimmer

The possibility to use these tailored leaves as light-driven microswimmers has been tested by cutting the very tip of a leaf, resulting in an object with a natural V-shaped design. In the presence of light, individual oxygen bubbles are periodically formed at the position of the primary vein (Figure 4A and Supporting Video S7). This provides enough driving force to generate the motion of the microswimmer. Just after switching the light on, a transient evolution of velocity can be observed. The swimmer accelerates continuously until reaching a constant maximum speed of 1 mm/s after 10secs (Figure 4B and Figure 4D black curve). After switching the light off, the speed remains constant for 2-3 secs before reducing drastically, and motion stops completely after 15 secs (Figure 4C and Figure 4D red curve). As in this case the characteristic size of the swimmer is quite small, bubble production, which is roughly proportional to the surface exposed to light, is less abundant, but still leads to an average speed of 2 body length/s.

Leaf based macroswimmer

Unlike these microswimmers, whole leaves show a more uniform and constant speed right from the start (0.5 mm/s). As can be seen from Figure S2, pristine micro-and macro-swimmers have in the beginning of their trajectory a comparable speed. The higher surface area of the macro-swimmer should in principle allow the collection of more light and thus produce more oxygen bubbles. However, a big leave also needs more thrust in order to overcome the inertia due to a higher mass and more friction. These two antagonistic effects seem to compensate so that both leaves, irrespective of their size, have the same initial speed. After this first phase, which lasts a few seconds (t<5s, Figure S2), the macroswimmer keeps its constant speed, whereas the microswimmer still continues to accelerate, until reaching a roughly two times higher final speed. This increased velocity might be explained by the fact that for smaller swimmers the oxygen produced inside the leaf can be shuttled more efficiently towards the vein outlet due to a shorter transport path.

Motion at the air/water interface during illumination can be observed for pristine leaves, but the latter can also be combined with other materials and used as a true motor, integrated into biohybrid devices showing enhanced speed. As an example, a thin polymer film of ~200 micron thickness was used as a support to partially attach the leaf using epoxy resin (Figure 5A). A supported leaf of ~ 1 cm size was studied in terms of speed compared to a pristine leaf. Attaching the polymer sheet to the rear of the leaf, where oxygen bubbles exit the central vein, improves the gas release efficiency and thus the thrust and the speed of the swimmer, because bubbles can't escape to the air/liquid interface. The hybrid object has indeed a roughly two times higher velocity than the pristine leaf, despite its higher weight (Figure 5B and Supporting Video S8).

Conclusion

In conclusion, the possibility of using pristine leaves as main ingredient for the design of macro-and microscopic swimmers, soley based on natural carbon dioxide conversion, has been successfully demonstrated. The respiration of the leaves, involving oxygen liberation by photosynthesis, was studied as a function of light intensity, leaf size and the composition of the aqueous medium. Precise tailoring of the leaves allows a perfect control of the gas release at specific predefined sites. The high sensitivity and stability of the leaves with respect to UV-Vis illumination, and its direct impact on oxygen evolution kinetics, emphasizes the potential of photosynthesis for bubble-based propulsion. However, UV light might lead to a faster degration of the leaves and represents only a small fraction of the naturally available light energy.Therefore the concept was also tested with wavelengths exclusively in the range of visible light. The natural photosystem of plants is supposed to work best for visible light. Plant pigment molecules typically absorb light in the wavelength range from 700 nm to 400 nm. Chlorophyll for example has a maximum of absorption around 450 and 650 nm. Thus, some gas release experiments have been also performed using a long pass filter with a cut-on wavelength of 500nm (Figure S3). This means that it is only possible to stimulate light absorption by chlorophyll in the higher wavelength region (650-680nm). Nevertheless, an efficient gas evolution is again observed at the location that has been predefined by cutting (Supporting Video S9). This allows envisioning the development of a class of totally natural autonomous swimmers, which might show even more exotic behavior when moving for example in a structured field of sun light. Finally, using the leaves, or parts of them, as building blocks of hybrid swimmers reveals additional interesting features, such as an increased momentum, and opens perspectives for the development of bioinspired dynamic systems with higher complexity, allowing eventually also fundamental studies concerning collective behavior.

Figure 1 .

 1 Figure 1. Schematic overview of the oxygen evolution mechanism in Pyracantha coccinea leaves (A) Picture of collected Pyracantha coccinea leaves (B) Photochemical reaction path (PSI and PSII) during photosynthesis. (C) Schematic microscopic view of a leaf cross section during oxygen evolution (D) Macroscopic view of oxygen transport towards the central vein and its release as bubbles at the artificially created outlet.

Figure 2 .

 2 Figure 2. Light-driven variations of oxygen evolution from leaves. (A) First row: Optical images of the oxygen evolution of a leaf exposed to different light intensities i.e. 100, 80, 60, and 40 % (100 % corresponds to 10 lumen/cm2). Second row: Different leaves with sizes of 20, 10, 5 and 0.5 mm were tested under UV-Vis light irradiation (100 %). Arrows indicate the individual bubbles (B) Graphical representation of the number of bubbles vs light intensity and leaf size. (C) Histogram of the oxygen evolution rate in different aqueous media. 1-CO2 saturated water, 2-air-saturated water, 3-N2

Figure 3 .

 3 Figure 3. Oxygen evolution confirmation. (A) Schematic illustration of oxygen evolution and its electrochemical analysis on a Pt microelectrode. (B) Voltamperometric curves of oxygen reduction with either CO2 or O2 present in the gas phase above the liquid (C) i vs t plot extracted from the experiment of Figure B, illustrating the mechanical impact of the oxygen bubbles on the microelectrode. (D) Correlation between faradaic current and collected charge for each impact of an oxygen bubble at the microelectrode.

Figure 4 .

 4 Figure 4. Light triggered microswimmer motion. (A) Optical images of the localized oxygen production at the primary vein of a microswimmer, (B) and (C) Trajectory of the microswimmer during acceleration and deceleration, respectively. The black circle in (B) indicates the position of the swimmer when the light is switched off, whereas the white circle in (C) corresponds to the final rest position of the swimmer. (D) Plot of the displacement as a function of time during acceleration and deceleration of the microswimmer. A UV-VIS lamp (150 W) was used for illumination.

Figure 5 .

 5 Figure 5. Comparison of pristine and hybrid macroswimmers. (A) Schematic illustration of oxygen evolution from a pristine and supported leaf. (B) Distance traveled as a function of time for an allnatural and a hybrid macroswimmer. (C) and (D) Trajectories of a pristine and supported leaf, respectively. The size of the leaves is around 1 cm, 100 % intensity of a lamp with 150 W power.

Acknowledgements

The authors are grateful for financial support by the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation program (grant agreement n° 74125, ERC Advanced grant ELECTRA).


Mieczyslaw A Klopotek
email: mieczyslaw.klopotek@ipipan.waw.pl

Slawomir T Wierzchoń
email: slawomir.wierzchon@ipipan.waw.pl

Robert A Klopotek
email: r.klopotek@uksw.edu.pl

Mieczys Law

A K Lopotek

T Wierzchoń

Robert A K Lopotek

k-means Cluster Shape Implications

Keywords: cluster shape, motion-consistency, outer-consistency, incremental clustering, perfect cluster separation, clusterability

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Sufficiently diverse corpora of test data for the development and implementation of algorithms, in particular of clustering algorithms, constitute an immanent challenge [START_REF] Pei | Synthetic data generator for clustering and outlier analysis[END_REF]. While various efforts like crowdsourcing produce considerable resources, tasks like fine-tuning or prevention of overfitting require still bigger sets of labeled data. Therefore, ways are sought on how to derive a new tagged set from an existent one without violating clustering algorithm assumptions.

Therefore, the axiomatization of clustering algorithm properties are of interest. Kleinberg [START_REF] Kleinberg | An impossibility theorem for clustering[END_REF] introduced interesting clustering invariant properties like scaling-invariance and consistency. Scaling invariance means that the cluster structure should be preserved if all distances between data points are multiplied by a constant. Consistency means that the clustering should be preserved if distances between data points in the cluster are not increased, and distances between data points from distinct clusters are not decreased. Regrettably, the consistency transform (CT ) cannot be applied to data being subject of k-means clustering to generate a new labeled data set because this algorithm does not have the consistency property [8]. Hence other properties like the inner or outer consistency [START_REF] Ackerman | Towards property-based classification of clustering paradigms[END_REF] need to be investigated. The inner-consistency transform is identical with CT except for distances between data points from distinct clusters are unchanged. The outer-consistency transform is identical with CT except for distances between data points within each cluster are unchanged. But innerconsistency property is not possessed by k-means [START_REF] Ackerman | Towards property-based classification of clustering paradigms[END_REF] and what is worse, in a fixed-dimensional space the inner CT reduces typically to identity transform [START_REF]Clustering algorithm consistency in fixed dimensional spaces[END_REF] which is of no value for test data generation. The outer consistency, on the other hand, with respect to k-means is of little value under continuous setting because it requires synchronized motion of all clusters -one cluster alone cannot be moved. This paper investigates how the outer-consistency constraints can be relaxed to what we call motion-consistency. It shall be defined as follows: Definition 1. Cluster area is any solid body containing all cluster data points. Gap between two clusters is the minimum distance between the cluster areas, i.e., Euclidean distance between the closest points of both areas.

Definition 2. Given a clustered data set embedded in a fixed dimensional Euclidean space, the motion-transformation is any continuous transformation of the data set in the fixed dimensional space that (1) preserves the cluster areas (the areas may only be subject of isomorphic transformations) and ( 2) keeps the minimum required gaps between clusters (the minimum gaps being fixed prior to transformation). By continuous we mean: there exists a continuous trajectory for each data point such that the conditions (1) and ( 2) are kept all the way. Definition 3. A clustering method has the property of motion-consistency, if it returns the same clustering after motion-transformation.

Compared to outer-consistency, or even the consistency, we weaken the constraints imposed on the distances between points, because the distances between data points of different data sets do not need to be increased, but only the distances between cluster areas (gaps) should not be decreased below certain values.

We demonstrate for k-means that it is advantageous to define the cluster area as a ball centered at its gravity center and encompassing all the data points of a cluster. Wherever we speak about a ball, we mean a hyper-ball that is the region enclosed by a hyper-sphere, that is an n-ball for n-dimensional Euclidean space R n . k-means, one of the most popular algorithms, exists in a multitude of versions. For an extensive overview of the general concept of k-means and versatile versions of it, see e.g., [START_REF] Wierzchoń | Modern Clustering Algorithms[END_REF]. We refer here to the following ones: (1) random-seed k-means, that is one with random initial seeding of cluster centers, (2) random-set k-means, that is one with the random initial assignment of data points to clusters, (3) k-means++, that is one with seeding of clusters according to a heuristic minimizing the distance to the closest cluster (4) k-means-ideal that is an "oracle" algorithm that finds the clustering minimizing absolutely the k-means objective. We consider so-called batch versions.

Moving Clusters -Motion-Consistency

As was observed in [START_REF] Everitt | Cluster Analysis[END_REF], clustering algorithms make implicit assumptions about the clusters' definition, shape, and other characteristics and/or require some predetermined free parameters. The shape of the clusters may constitute the foundation for choosing the right number of clusters to split the data into [START_REF] Chiang | Intelligent choice of the number of clusters in k-means clustering: An experimental study with different cluster spreads[END_REF]. In this section, let us ask what should be the shape of the area covered by the k-means clusters. The usual way to look at the k-means clusters is one of the so-called Voronoi regions [START_REF] Schreiber | A Voronoi diagram based adaptive k-means-type clustering algorithm for multidimensional weighted data[END_REF]. These regions are polyhedrons such that any point within the area of the polyhedron is closer to its cluster center than to any other cluster center. Obviously, the outer polyhedrons (at least one of them) can be moved away continuously from the rest without overlapping any other region so that at least the motion-transformation is applicable non-trivially. However, does the motion-consistency hold? A closer look at the issue tells us that it is not. As k-means terminates, the neighboring clusters' polyhedra touch each other via a hyperplane such that the straight line connecting centers of the clusters is orthogonal to this hyperplane. This causes that points on the one side of this hyperplane lie more closely to the one center, and on the other to the other one. But if we move the clusters in such a way that both touch each other along the same hyperplane, then it happens that some points within the first cluster will become closer to the center of the other cluster and vice versa.

Generally, moving the clusters will change their structure (points switch clusters) unless the points lie actually not within the polyhedrons but rather within paraboloids with appropriate equations. Then moving along the border, hyperplane will not change cluster membership (locally, that is, the data points of the two considered clusters will not switch cluster membership given that we fixed all other clusters and consider reclustering of these two clusters only). But the intrinsic cluster borders are now paraboloids. The problem will occur again if we relocate the clusters allowing for touching along the paraboloids.

Hence the question can be raised: What shape should the k-means clusters have in order to be (locally) immune to movement of whole clusters?

Assume that only one cluster would move. Let us consider the problem of susceptibility to class membership change within a 2D plane containing the two cluster centers and the motion vector of the moving cluster. Let the one cluster center be located (for simplicity) at the point (0,0) in this plane and the other at (2x 0 , 2y 0 ) for some x 0 , y 0 . Let further the border of the first cluster be characterised by a (symmetric) function f (x) and let the shape of the border of the other one g(x) be the same, but rotated by 180 o around (x 0 , y 0 ): g(x) = 2y 0 -f (2x 0 -x). Let both have a touching point (we excluded already a straight line and want to have convex smooth borders). From the symmetry conditions one easily sees that the touching point must be (x 0 , y 0 ). As this point lies on the surface of f (), y 0 = f (x 0 ) must hold. Any point (x, f (x)) of the border of the first cluster must be closer to its centre (0, 0) than to the centre (2x 0 , 2y 0 ) of the other:

(x -2x 0 ) 2 + (f (x) -2f (x 0 )) 2 -x 2 -f 2 (x) ≥ 0 (1) That is -x 0 (x -x 0 ) -f (x 0 ) (f (x) -f (x 0 )) ≥ 0
Let us consider only positions of the center of the second cluster below the X axis (y 0 < 0). In this case f (x 0 ) < 0. Further let us concentrate on x > x 0 . We get f (x)-f (x0)

x-x0

≥ x0 -f (x0) . In the limit, when x approaches x 0 , f (x 0 ) ≥ x0 -f (x0) . By analogy for x < x 0 in the limit x → x 0 we get:

f (x 0 ) ≤ x0 -f (x0) This implies f (x 0 ) = -1 f (x0) x0
(2)

f (x0) x0
is the directional tangent of the straight line connecting both cluster centres. f (x 0 ) is tangential of the borderline of the first cluster at the touching point of both clusters. The equation above means both are orthogonal. But this property implies that f (x) must define (a part of) a circle centred at (0, 0). As the same reasoning applies at any touching point of the clusters, a k-means cluster would have to be (hyper)ball-shaped in order to allow the movement of the clusters without elements switching cluster membership.

We know that most k-means versions tend to stick at local minima. We see here immediately that some kind of local minima is preserved under motionconsistency transform.

Theorem 1. If random-set k-means has a local minimum in ball form that is such that the clusters are enclosed into equal radius balls centered at the respective cluster centers, and gaps are fixed at zero, then the motion-transform preserves this local minimum.

Proof. For k = 2, this is obvious from the above consideration. For k > 2 consider just each pair of clusters to see that no cluster change occurs.

The tendency of k-means to recognize best ball-shaped clusters has been known long ago, but we are not aware of presenting such an argument for it.

Motion-Consistency Property for Two Clusters

The preservation of local minima does not guarantee the preservation of the global minimum even if the global minimum has the above-mentioned ball form.

A sufficient separation between the enclosing balls is needed, as we will show again for k = 2.

Let us consider, under which circumstances a cluster C 1 of radius r 1 containing n 1 elements would take over n 21 elements (i.e. subcluster C 21 ) of a cluster C 2 of radius r 2 of cardinality n 2 , if we perform the motion-consistency transform. As only (sub)cluster centres are of interest in our investigation, we can concentrate on the plane spanned by the gravity centres c1, c21, c22 of C 1 , C 21 , C 22 , see left most Cluster forming c11-c21, c12-c22

x y q c11 q c12 q c21 q c22 q q q
-15 -10 -5 0 5 10 15 Cluster forming c12-c22, c11-c21

x y q c11 q c12 q c21 q c22 q q q
-15 -10 Cluster forming c11-c22, c12-c21

x y q c11 q c12 q c21 q c22 q q Fig. 2. Extreme cases to be considered when looking for a sufficient gap to avoid alternative clustering with a split of both clusters.

So in order for the clusters C 1 , C 2 to constitute the global optimum

SSC(C 1 ) + SSC(C 2 ) ≤ SSC(C 1 ∪ C 21 ) + SSC(C 22 ) must hold. But SSC(C 2 ) = SSC(C 21 ) + SSC(C 22 ) + n 21 • r 2 21 + n 22 • r 2 22 SSC(C 1 ∪ C 21 ) = SSC(C 1 ) + SSC(C 21 ) + n 1 n 21 n 1 + n 21 (r 1 + r 2 + g -r 21 ) 2 Hence (r 2 21 + r 21 • r 22 )(n 21 /n 1 + 1) -r 1 -r 2 + r 21 ≤ g As r 22 = r21n21 n2-n21 r 21 n 2 n 1 n 1 + n 21 n 2 -n 21 -r 1 -r 2 + r 21 ≤ g
Let us consider the worst-case when the elements to be taken over are at the edge of the cluster region (r 21 = r 2 ). Then

r 2 n 2 n 1 n 1 + n 21 n 2 -n 21 -r 1 ≤ g
The lower limit on g will grow with n 21 , but n 21 ≤ 0.5n 2 , because otherwise r 22 would exceed r 2 . Hence in the worst case

r 2 n 2 n 1 n 1 + n 2 /2 n 2 /2 -r 1 ≤ g r 2 2(1 + 0.5n 2 /n 1 ) -r 1 ≤ g (3)
In case of clusters with equal sizes and equal radius this amounts to

g ≥ r 1 ( √ 3 -1) ≈ 0.7r 1
But there exists the theoretical possibility that both clusters are split into subclusters, which then may form pairwise clusters different from the original C 1 , C 2 . This is symbolically illustrated in the right Fig. 1. As only (sub)cluster centres are of interest in our investigation, we can concentrate on the 3D subspace spanned by the gravity centres c11, c12, c21, c22 of subclusters C 11 , C 12 , C 21 , C 22 . Furthermore, distances between subcluster gravity centers from different clusters will decrease if we rotate the lines c11, c12 and c21, c22, so that they lie in a 2D plane. So we need in fact to consider this 2D plane in worst-case analysis, as in Fig. 1, though the results apply to any high-dimensional space. In an analogous way as above, we can derive (as a simple exercise) explicit requirements on minimum gap g needed in order to ensure that such a re-clustering will not happen. The worst cases of subcluster center positions to be considered are depicted in Fig. 2. In each case, the 50%-50% split of a cluster into subclusters turns out to be requiring the biggest gap. We conclude Theorem 2. k-means algorithm with k = 2 possesses the property of motionconsistency if (1) the k-means clustering global minimum Γ has the property that each cluster can be enclosed in a ball and (2) the gaps between balls fulfil the condition of taking the maximum of the gaps derived from Fig. 2, Fig. 1 and (3) the gap between clusters would not be decreased below the gap value from (2) during the motion.

Note that under k-means objective, the globally optimal clustering is also pairwise optimal, but the inverse does not hold.

This means that Motion-Consistency transform can turn an optimal clustering to an unoptimal one for k > 2.

It should be emphasized that we consider here about the local optimum of kmeans. With the aforementioned gap size, the global k-means minimum may lie elsewhere, in a clustering possibly without gaps. Also, the motion-transformation preserves as a local minimum the partition it is applied to. Other local minima and global minimum can change.

Note that the motion-consistency (applicable for k = 2 in k-means) is more flexible for the creation of new labeled data sets than outer-consistency.

Perfect Ball Clusterings

The problem with k-means (-random and ++) is the discrepancy between the theoretically optimized function (k-means-ideal) and the actual approximation of this value. It appears to be problematic even for well-separated clusters.

First, let us point to the fact that well-separatedness may keep the algorithm in a local minimum.

It is commonly assumed that a good initialization of a k-means clustering is one where the seeds hit different clusters. It is well-known that under some circumstances, the k-means does not recover from poor initialization, and as a consequence, a natural cluster may be split even for well-separated data.

Hitting each cluster may not be sufficient as neighboring clusters may be able to shift the cluster center away from its cluster. Hence let us investigate what kind of well-separability would be sufficient to ensure that once clusters are hit by one seed each, they would never lose the cluster center.

Let us investigate the working hypothesis that two clusters are well separated if we can draw a ball of some radius ρ around true cluster center of each of them, and there is a gap between these balls. We claim (see [START_REF]On the discrepancy between Kleinberg's clustering axioms and k-means clustering algorithm behavior[END_REF]) that Theorem 3. If the distance between any two cluster centres A, B is at least 4ρ AB + , > 0, where ρ AB is the radius of a ball centred at A and enclosing its cluster (that is cluster lies in the interior of the ball) and it also is the radius of a ball centred at B and enclosing its cluster, then once each cluster is seeded the clusters cannot loose their cluster elements for each other during k-meansrandom and k-means++ iterations.

Before starting the proof, let us introduce related definitions. Definition 4. We shall say that clusters centred at A and B and enclosed in balls centred at A, B and with radius ρ AB each are nicely ball-separated, if the distance between A, B is at least 4ρ AB + , > 0. If all pairs of clusters are nicely ball separated with the same ball radius, then we shall say that they are perfectly ball-separated.

Obviously, if there exists a perfect ball clustering into k-clusters in the data set, then after invariance transform as well as after consistency transform, there exists a perfect ball clustering into k-clusters in the data set. Let us restrict ourselves to clusterings with at least three data points in a cluster (violation of the most general richness, but nonetheless a reasonable richness, let us call it reachness-3++. In this case, it is obvious that if the perfect ball clustering exists then, it is unique. This means automatically that if k-means would be able to detect the perfect ball clustering into k clusters, then it would be consistent in the sense of Kleinberg. Therefore it is worth investigating whether or not k-means can detect a perfect ball clustering.

If the data set had a perfect ball clustering into k clusters (of at least 2 elements), but not into k -n 1 nor into k + n 2 clusters, where 1 ≤ n 1 ≤ k -2, 1 ≤ n 2 ≤ n/2 -k are natural numbers,then under application of Kleinberg's consistency transform, the new data set can both have a perfect ball clustering into k -n 1 and into k + n 2 clusters. Hence the Kleinberg's impossibility theorem holds also within the realm of perfect ball clusterings.

Proof. For the illustration of the proof see Figure 3.

q q q q -5 0 5 -5 0 5 separation x y q A q B q q k m O q C q D q C' q D' q M q H q S q E q F q E' q F' q F* q E* q X' q Y' q l
Fig. 3. An illustrative figure for proof of 4 radius distance ensuring good separability.

Consider two points A, B be two ball centers and two points, X, Y , one being in each ball (presumably the cluster centers at some stage of the k-means algorithm). To represent their distances faithfully, we need at most a 3D space.

Let us consider the plane established by the line AB and parallel to the line XY . Let X and Y be projections of X, Y this plane. Now let us establish that the hyperplane π orthogonal to X, Y , and passing through the middle of the line segment XY , that is the hyperplane containing the boundary between clusters centered at X and Y does not cut any of the balls centered at A and B. This hyperplane will be orthogonal to the plane of the Figure 3 and so it will manifest itself as an intersecting line l that should not cross circles around A and B, being projections of the respective balls. Let us draw two solid lines k, m between circles O(A, ρ) and O(B, ρ) tangential to each of them. Line l should lie between these lines, in which case the cluster center will not jump to the other ball. Let the line X Y intersect with the circles O(A, ρ) and O(B, ρ) at points C, D, E, F as in the figure. It is obvious that the line l would get closer to circle A, if the points X', Y' would lie closer to C and E, or closer to circle B if they would be closer to D and F .

Therefore, to show that the line l does not cut the circle O(A, ρ), it is sufficient to consider X = C and Y = E. (The case with ball Ball(B, ρ) is symmetrical).

Let O be the center of the line segment AB. Let us draw through this point a line parallel to CE that cuts the circles at points C , D , E and F . Now notice that centric symmetry through point O transforms the circles O(A, ρ),O(B, ρ) into one another, and point C into F and D into E . Let E * and F * be images of points E and F under this symmetry. In order for the line l to lie between m and k, the middle point of the line segment CE shall lie between these lines.

Let us introduce a planar coordinate system centered at O with X axis parallel to lines m, k, such that A has both coordinates non-negative, and B nonpositive. Let us denote with α the angle between the lines AB and k. As we assume that the distance between A and B equals 4ρ, then the distance between lines k and m amounts to 2ρ(2 sin(α) -1). Hence the Y coordinate of line k equals ρ(2 sin(α) -1). So the Y coordinate of the center of the line segment CE shall be not higher than this. Let us express this in vector calculus:

4(y OC + y OE )/2 ≤ ρ(2 sin(α) -1)
Note, however that

y OC + y OE = y OA + y AC + y OB + y BE = y AC + y BE = y AC -y AE * = y AC + y E * A
So let us examine the circle with center at A. Note that the lines CD and E * F * are at the same distance from the line C'D'. Note also that the absolute values of direction coefficients of tangentials of circle A at C' and D' are identical. The more distant these lines are, as line CD gets closer to A, the y AC gets bigger, and y E * A becomes smaller. But from the properties of the circle, we see that y AC increases at a decreasing rate, while y E * A decreases at an increasing rate. So the sum y AC + y E * A has the biggest value when C is identical with C and we need hence to prove only that

(y AC + y D A )/2 = y AC ≤ ρ(2 sin(α) -1)
Let M denote the middle point of the line segment C D . As point A has the coordinates (2ρ cos(α), 2ρ sin(α)), the point M is at distance of 2ρ cos(α) from

A. But C M 2 = ρ 2 -(2ρ cos(α)) 2 .
So we need to show that ρ 2 -(2ρ cos(α)) 2 ≤ (ρ(2 sin(α) -1)) 2 . In fact we get from the above 0 ≤ 1 -sin(α) which is an obvious trigonometric relation.

Incremental k-means

It is not hard to demonstrate that if the perfect-ball separation was found, it does not suffice to state that we reached a global minimum of k-means. Moreover, even if the global minimum of k-means is a perfectly ball separated set of clusters, it does not mean that motion-transformation keeping this property will yield a new clustering being optimal for k-means.

However, there exists a version of k-means for which a perfectly ball separated set of clusters is the global optimum. Hence the motion-transform keeping the perfect ball separation keeps the optimum. We will introduce this algorithm in this section and demonstrate the respective property.

Ackerman and Dasgupta [START_REF] Ackerman | Incremental clustering: The case for extra clusters[END_REF] study clusterability properties of incremental clustering algorithms. They introduce an incremental version of a very popular k-means algorithm (for an extensive overview of k-means versions see [START_REF] Wierzchoń | Modern Clustering Algorithms[END_REF]).

They introduced the perfect clustering with the property that the smallest distance between elements of distinct clusters is larger than the distance between any two elements of the same cluster. They demonstrate that there exists an incremental algorithm discovering the perfect clustering that is linear in k with respect to space. But their incremental (sequential ) k-means fails to do so.

Their case study is interesting because it demonstrates that the cluster shape plays a role -each cluster has to be enclosed into a convex envelope. The problem of incremental k-means is caused by the fact that this envelope is not ball-shaped.

Data: the data points xi, i = 1, . . . , m, the required number of clusters k Result: T -the set of cluster centres Set T = (t1, . . . , t k ) to the first k data points; Initialize the counts n1, n2, . . . , n k to 1; while any data point unvisited do Acquire the next example, t k+1 . Set n k+1 = 1; Find i, j ∈ {1, . . . , k + 1}, i < j such the distance between ti and tj is the smallest one among distances between t1, . . . , t k/+1 . Replace ti = (tini + tjnj)/(ni + nj),

thereafter ni = ni + nj; if j = k + 1 then replace tj = t k+1 , nj = n k+1 end end
Algorithm 1: Sequential (incremental) k-means, our modification Let us discuss at this point a bit the notions of perfect separation. In their Theorem 4.4. Ackerman and Dasgupta [START_REF] Ackerman | Incremental clustering: The case for extra clusters[END_REF] show that the incremental k-means algorithm, as introduced in their Algorithm 2.2 , is not able to cluster correctly data that is perfectly clusterable (their Definition 4.1). The reason is quite simple. The perfect separation refers only to separation of data points, and not to points in the convex hull of these points. But during the clustering process, the candidate cluster centres are moved in the convex hulls, so that they can occasionally get too close to data points of the other cluster. To avoid this effect, we will use the just introduced concept of perfect ball separation (see Def. 4)

Under the perfect-ball-separation as introduced here their incremental kmeans Algorithm 2.2. (Sequential k-means) will discover the structure of the clusters after a modification (Algorithm 1):

Data: T = (t1, . . . , t k ) be the resulting set of cluster centres from the Algorithm 1. Result: Clusterability decision Initialize the furthest neighbours f1, f2, . . . , f k with t1, t2 . . . , t k respectively;

while any data point unvisited do Acquire the next example, x; if ti is the closest centre to x and x is further away from ti than fi then Replace fi with X; end end Compute distances between corresponding ti and fi, pick the highest one; Compute distances between each pair ti, tj and pick the lowest one; if the latter is 4 times or more higher than the former one then

We got a perfect ball clustering else Perfect ball clustering was not found end Algorithm 2: Sequential k-means, our modification -second pass The reason is as follows. Perfect ball separation ensures that there exists an r of the enclosing ball such that the distance between any two points within the same ball is lower than 2r, and between them is bigger than 2r. So whenever Ackerman's incremental k-mean merges two points, they are the points of the same ball. Upon merging, the resulting point lies again within the ball. Theorem 4. The incremental k-means algorithm will discover the structure of perfect-ball-clustering.

Proof. If t i , t j are points within the ball enclosing a single cluster, then also (t i n i + t j n j )/(n i + n j ) will lie within the same ball. If t k+1 stems from a cluster not represented by t 1 , . . . , t k , then k + 1 will not be in the pair (i, j) of closest elements, because their distance is more than 2ρ, while those within a cluster at most 2ρ. On the other hand, t i , t j would not stem from two different clusters because t 1 , . . . , t k , because the distance within a cluster is at most 2ρ, while the distance between elements from distinct clusters is at most 2ρ. In this way, no t l , l = 1, . . . , k will lie outside of balls representing clusters. Furthermore, its position will be calculated only based on data points from the same cluster. Furthermore, it will be the average position of those points, so finally, after the full pass, all t l will represent the k different cluster centers.

The incremental k-means algorithm returns only a set of cluster centers without stating whether or not we got a perfect ball clustering. However, if we are allowed to inspect the data for the second time, such information can be provided. See Algorithm 2: A second pass for other algorithms from Ackerman and Dasgupta section 2 would not yield such a decision.

Conclusions

We derived in this paper the intended shape of a k-means cluster (a ball centered at cluster gravity center) as a necessary condition of clustering preserving motion-transformation of the dataset. This shape preserves ball-shaped local minima for k-means algorithm with random initial partition. We have also derived, for ball-shaped clusters for k = 2, gap condition for motion-transformation that preserves the global minimum of k-means. We have also shown that incremental k-means is able to find the perfect ball-shaped clustering. Therefore the motion-transform keeping the perfect ball separation will preserve the incremental-k-means clustering. Thus we have discovered a couple of transformations that preserve various aspects of clustering, suitable for deriving new labeled datasets from existent ones, as implied by our Theorems 1, 3, 2, 4.

Fig. 1 .Fig. 1 .

 11 Fig. 1. Possible alternatives to the basic clustering into {C1, C2}. Left figure: one cluster is split into two clusters. Central figure: upon this split, one cluster takes over a subcluster of the other cluster. Right figure: both clusters are split into subclusters that form new clusters, as indicated in Fig. 2.