Kaige Shi

Logesh Mathivathanan

Athanassios K Boudalis

Philippe Turek

Indranil Chakraborty

Raphael G Raptis

Nitrite Reduction by Trinuclear Copper Pyrazolate Complexes: An Example of a Catalytic, Synthetic Polynuclear NO Releasing System

come   L'archive ouverte pluridisciplinaire

Introduction

Nitrite is an important player of the biogeochemical nitrogen cycle, being reduced biologically to nitric oxide by Cu-, Fe-, or Mo-containing enzymes, [START_REF] Maia | How Biology Handles Nitrite[END_REF] and oxidized to nitrate by Mo-containing ones, while analogous processes are also involved in the abiotic N 2 cycle. [START_REF] Doane | The Abiotic Nitrogen Cycle[END_REF] Copper-containing nitrite reductase enzymes (CuNIR) comprise type-I and -II copper centers, with electrons shuttled from the type-I site to the catalytic, nitrito-binding type-II site. [START_REF] Maia | How Biology Handles Nitrite[END_REF][START_REF] Merkle | Binding and Activation of Nitrite and Nitric Oxide by Copper Nitrite Reductase and Corresponding Model Complexes[END_REF] Nitrite is toxic to humans, requiring removal from drinking water when present, [START_REF] Cervantes | Nitrogen Removal from Wastewaters at Low C/N Ratios with Ammonium and Acetate as Electron Donors[END_REF] but also functions as a nitric oxide store in the blood, releasing NO under cell hypoxic conditions with numerous physiological responses. [START_REF] Blood | On the Journey from Toxin to Therapy[END_REF] The photolysis of nitrous acid to NO and OH-radicals is the main source of the latter in the atmosphere. [START_REF] Gomez Alvarez | Unexpectedly High Indoor Hydroxyl Radical Concentrations Associated with Nitrous Acid[END_REF] Synthetic transition metal nitrite compounds, especially those of Fe and Cu, are of interest in relation to the mechanism of the activity of nitrite reductase enzymes. [START_REF] Wasser | Nitric Oxide in Biological Denitrification: Fe/Cu Metalloenzyme and Metal Complex NOx Redox Chemistry[END_REF][START_REF] Timmons | Converting between the Oxides of Nitrogen Using Metal-Ligand Coordination Complexes[END_REF] However, as a ligand, nitrite has not been studied in as much detail as its fully oxidized nitrate congener (a CCDC search on 26/4/2019 gave 2106 entries for Cu-ONO 2 , but only 141 for Cu-ONO and 34 for Cu-NO 2 (Cambridge Structural Database version 5.0, update Feb. 2019)), possibly because of its instabilitynitrite is often either oxidized to nitrate or reduced to NO, even under mild conditions. Neither has the function of a Cu I/II -NO 2 center in CuNIR been fully understood; while multiple model studies have pointed to redox-induced release of N 2 O and NO from the Cu I/II centers of CuNIR, the order of events (i.e., nitritecentered, or metal-centered reduction occurs first) has not been fully elucidated. [START_REF] Peterson | Copper Enzymes[END_REF] Whereas several synthetic Fe II /Cu I nitrito complexes have been shown to release NO, and many Cu IInitrito complexes have been reported, only a handful of synthetic Cu II and Fe II NO-releasing complexes are known, to date. [START_REF] Merkle | Binding and Activation of Nitrite and Nitric Oxide by Copper Nitrite Reductase and Corresponding Model Complexes[END_REF][START_REF] Kundu | Copper(II) Activation of Nitrite: Nitrosation of Nucleophiles and Generation of NO by Thiols[END_REF][START_REF] Sakhaei | Nitric Oxide Release via Oxygen Atom Transfer from Nitrite at Copper(II)[END_REF][START_REF] Sanders | NO 2 -Activation and Reduction to NO by a Nonheme Fe(NO 2 ) 2 Complex[END_REF][START_REF] Matson | Facile Nitrite Reduction in a Non-Heme Iron System: Formation of an Iron(III)-Oxo[END_REF] To our knowledge, there is no example of a polynuclear complex with more than one nitrite ligand in the literature. In contrast, examples of mononuclear Cu II complexes with two or three nitrito ligands in various coordination modes are known. [START_REF] Roger | An Investigation into the Unusual Linkage Isomerization and Nitrite Reduction Activity of a Novel Tris(2-Pyridyl) Copper Complex[END_REF][START_REF] Woollard-Shore | Nitrite Reduction by Copper Complexes[END_REF] In earlier work, we have shown that trinuclear copper(II) complexes of the formula [Cu 3 (µ 3 -O)(µ-4-R-pz) 3 X 3 ] zpz -= pyrazolato anion; R = H, CH(O), Cl, Br and ONO; X -= Cl -, NCS -, CH 3 COO -, CF 3 COO -and pyridine; z = chargecan be oxidized to the corresponding z + 1, formally Cu II 2 Cu III , species. [START_REF] Angaridis | Synthesis and Structural Characterization of Trinuclear Cu II -Pyrazolato Complexes Containing µ 3 -OH, µ 3 -O, and µ3-Cl Ligands. Magnetic Susceptibility Study of[END_REF][START_REF] Rivera-Carrillo | Tuning of the [Cu 3 (μ-O)] 4+/5+ Redox Couple: Spectroscopic Evidence of Charge Delocalization in the Mixed-Valent [Cu 3 (μ-O)] 5+ Species[END_REF] In one case, the mixed-valent R = H and X -= PhCOO -complex was crystallographically characterized. [START_REF] Mezei | First Structural Characterization of a Delocalized, Mixed-Valent, Triangular Cu 3 7+ Species: Chemical and Electrochemical Oxidation of a Cu II 3 (µ 3 -O) Pyrazolate and Electronic Structure of the Oxidation Product[END_REF] The E 1/2 -values for the aforementioned oxidation follow the expected trend for the various terminal X-ligands: the higher X is in the spectrochemical series, [START_REF] Hitchman | Transition Metal Nitrite Complexes[END_REF][START_REF] Atkins | Inorganic Chemistry[END_REF] the easier the oxidation. Following-up on this observation, we show here that when X - = ONO -the one-electron oxidation of the all- We also present a new pyrazolato complex, with 4-phenylpyrazolato bridging ligands,

Cu II complex [Cu 3 (µ 3 -O)(µ-pz) 3 (ONO) 3 ] 2-,
(PPN)[Cu 3 (µ 3 -OH)(µ-4-Ph-pz) 3 (ONO) 3 ] (3). Compound 3 is redox-inert,

Experimental Section

Materials and Methods

All reagents were purchased from commercial sources and used as received. Solvents were purified using standard techniques. [START_REF] Armarego | Purification of Laboratory Chemicals[END_REF] [PPN] 2 [Cu 3 (µ 3 -Cl) 2 (µ-pz) 3 Cl 3 ] was prepared according to a literature procedure. [START_REF] Angaridis | Synthesis and Structural Characterization of Trinuclear Cu II -Pyrazolato Complexes Containing µ 3 -OH, µ 3 -O, and µ3-Cl Ligands. Magnetic Susceptibility Study of[END_REF] Elemental analyses (C, H, N) were performed by Galbraith Laboratories, Inc., Knoxville, Tennessee. IR spectra were recorded on a Spectrum One Perkin-Elmer FT-IR Spectrophotometer (ATR mode) in the 4000-600 cm -1 region. Electrochemical measurements were performed under Ar atmosphere at ambient temperature in a BAS-Epsilon electrochemical measurement system using a three-electrode system (glassy carbon working, Pt-wire auxiliary and Ag/AgNO 3 reference electrodes), using 0.1 M TBAPF 6 /CH 2 Cl 2 as the supporting electrolyte.

Ferrocene was used as the internal standard. Potentials are reported vs. Fc + /Fc.

Single crystal X-ray diffraction data were collected on a Bruker D8 QUEST CMOS system equipped with a TRIUMPH curved-crystal monochromator and a Mo-Kα fine-focus X-ray tube with graphite monochromated Mo-Kα radiation (λ = 0.71073 Å) at ambient or low temperature using the APEX3 or APEX2 suite. 22 Frames were integrated with the Bruker SAINT software package using a narrow-frame algorithm. Absorption effects were corrected using the multi-scan method (SADABS). [START_REF] Sadabs; Bruker | [END_REF] Structures were solved by intrinsic phasing methods with ShelXT [START_REF] Sheldrick | SHELXT -Integrated Space-Group and Crystal-Structure Determination[END_REF] and refined with ShelXL using full-matrix least-squares minimization Using Olex2. [START_REF] Dolomanov | OLEX2: A Complete Structure Solution, Refinement and Analysis Program[END_REF] All nonhydrogen atoms were refined anisotropically. Hydrogen atoms positions were calculated and fixed by HFIX with their thermal ellipsoids riding on those of their carbon atoms.

EPR spectra of 1 were recorded on a Bruker ESP300 spectrometer using a Bruker 4102ST S5).

Quantitative measurement of NO generated from 1 and 3 by addition of thiophenol.

Release of NO was quantitatively determined as NO amperograms using the inNO-T nitric oxide monitoring system (Innovative Instruments, Inc). An AmiNO-100 sensor was dipped into an open vial containing 5 x 10 -5 M CH 2 Cl 2 solutions of 1 or 3 under constant stirring. The released NO was measured in pA/nM response curves, which were converted to nM of NO by calibration with standard NaNO 2 /KI/H 2 SO 4 solutions, according to the procedures described by the manufacturer.

Results

Compound 1 was obtained from a metathetical reaction of the chloro-terminated complex [START_REF] Angaridis | Synthesis and Structural Characterization of Trinuclear Cu II -Pyrazolato Complexes Containing µ 3 -OH, µ 3 -O, and µ3-Cl Ligands. Magnetic Susceptibility Study of[END_REF] [Cu 3 (µ 3 -O)(µ-pz) 3 Cl 3 ] 2-with excess NaNO 2 in CH 2 Cl 2 and was recrystallized from Compound 3 was prepared from its corresponding Cl-terminated compound, 2, using a similar method as described above for 1; adding an excess of NaNO 2). A similar H-bonded dimer-oftrimers mediating magnetic interactions between the two Cu 3 units was recently reported by us. [START_REF] Mathivathanan | Interactions between H-Bonded [Cu II 3 (µ 3 -OH)] Triangles; a Combined Magnetic Susceptibility and EPR Study[END_REF] The Cu-(µ 3 -OH) distances of 3 are longer than the Cu-(µ 3 -O) of 1, as expected, but rather short compared to other Cu 3 -(µ 3 -OH) complexes reported in the literature by us and others. [START_REF] Angaridis | Synthesis and Structural Characterization of Trinuclear Cu II -Pyrazolato Complexes Containing µ 3 -OH, µ 3 -O, and µ3-Cl Ligands. Magnetic Susceptibility Study of[END_REF][START_REF] Mezei | Effect of Copper-Substitution on the Structure and Nuclearity of Cu(II)-Pyrazolates: From Trinuclear to Tetra-, Hexa-and Polynuclear Complexes[END_REF][START_REF] Pandolfo | Trinuclear Copper(II) Pyrazolate Compounds: A Long Story of Serendipitous Discoveries and Rational Design[END_REF] In the infrared spectrum of compound 1 (Figure S6), the asymmetric nitrite stretches, ν as (N-O), are identified with strong bands at 1439 cm -1 and 1377 cm -1 , whereas the symmetric ν sym (N-O) is assigned to a band at 1259 cm -1 , in agreement with those reported for other nitrito complexes in the literature. [START_REF] Woollard-Shore | Nitrite Reduction by Copper Complexes[END_REF][START_REF] Lehnert | Synthesis and Spectroscopic Characterization of Copper(II)-Nitrito Complexes with Hydrotris(Pyrazolyl)Borate and Related Coligands[END_REF] The corresponding bands for 3 appear at 1436 cm -1 , 1360 cm -1 and 1114 cm -1 (Figure S7). [START_REF] Woollard-Shore | Nitrite Reduction by Copper Complexes[END_REF] N-labeling studies by others of an  2 -ONO Cu II -complex have revealed that the IR-active O-N-O bending vibration of nitrite, (ONO), occurs at 877 cm -1 . [START_REF] Lehnert | Synthesis and Spectroscopic Characterization of Copper(II)-Nitrito Complexes with Hydrotris(Pyrazolyl)Borate and Related Coligands[END_REF] A similar weak band is observed at 872 cm -1 for 1 and 848 cm -1 for 3. The  1 -and  2 -ONO binding modes do not differ significantly in vibrational spectra, as has already been reported elsewhere. To assess the stability of the complexes in solution, EPR spectra in frozen CH 2 Cl 2 were recorded for 1 and 3 at 4.2 K (Figure 3). Both spectra exhibited similar characteristics typical of antiferromagnetically-coupled half-integer spin triangles experiencing antisymmetric exchange (or Dzyaloshinksii-Moriya) interactions, previously manifested in other complexes of this family. [START_REF] Mathivathanan | Interactions between H-Bonded [Cu II 3 (µ 3 -OH)] Triangles; a Combined Magnetic Susceptibility and EPR Study[END_REF][START_REF] Boudalis | Towards Ionic Liquids with Tailored Magnetic Properties: Bmim + Salts of Ferro-and Antiferromagnetic Cu II 3 Triangles[END_REF] The spectra of 1(3) consist of an absorption-like peak at g = 2.14(2.18) and a derivative feature at g = 1.87(1.84), with a broad trough centered at g = 1.73(1.74). The absorption-like peaks are attributed to the g || resonances and appear significantly broadened, due to unresolved, or partially resolved, hyperfine interactions. The derivative features are attributed to the g  resonances and they owe their low g-values to antisymmetric exchange interactions that induce a high anisotropy to the ground S T = 1/2 state. [START_REF] Rakitin | EPR Spectra of Trigonal Clusters[END_REF][START_REF] Tsukerblat | Magnetochemistry and Spectroscopy of Transition Metal Exchange Clusters[END_REF] The broad profile of these features has been explained by the combination of distributions of the magnetic exchange interactions (Jstrain) acting in tandem with the antisymmetric exchange interactions. [START_REF] Sanakis | Evidence for Antisymmetric Exchange in Cuboidal [3Fe-4S] + Clusters[END_REF][START_REF] Sanakis | J-Strain and Antisymmetric Exchange in a Polynuclear Compound Containing the {Fe 3 O} 7+ Core[END_REF] The presence of these broad derivative features with g < 2 is compelling evidence that the EPR spectra correspond to exchange-coupled systems with S T = 1/2 ground states, and not paramagnetic S = 1/2 mononuclear Cu II complexes. ] (vide infra), followed by an irreversible oxidation at ~0 V (Figure 4). In contrast, a reduction to a [Cu 3 5+ ] species is not accessible within the potential window (+1.50 V to -1.00 V, vs. Fc + /Fc) of this study. Compound 3 is redox-inert, but becomes redox-active upon in situ addition of a base, which deprotonates the µ 3 -OH group, showing a reversible oxidation at +0.004 V. We have previously described the solution characterization of a series of [Cu 3 (µ 3 -O)(µ-4-R-pz) 3 X 3 ] z complexes and shown that substitution at the bridging pyrazole 4-position (R) and at the terminal ligand positions (X) influence the redox potential, revealing a trend that follows the order of electron withdrawing/releasing properties of the substituents. [START_REF] Rivera-Carrillo | Tuning of the [Cu 3 (μ-O)] 4+/5+ Redox Couple: Spectroscopic Evidence of Charge Delocalization in the Mixed-Valent [Cu 3 (μ-O)] 5+ Species[END_REF] Compound 1 has the lowest oxidation potential (Table 1), an expected result given the position of the O-bound nitrite higher in the spectrochemical series. Chemical oxidation by a stoichiometric amount of benzoyl peroxide in CH 2 Cl 2 results in formation of the formally Cu II 2 Cu III -compound, {MV-Cu 3 }, accompanied by visible color change from greenish blue to reddish brown (Figure S8) with the appearance of new absorption band at 9191 cm -1 (9004 cm -1 for 3, Figure S9) in the near-IR part of the electronic spectrum (Figure 5). The latter is tentatively assigned to an intervalence charge transfer (IVCT) band, characteristic of mixed-valent species. Computational analysis of the related chloroterminated compound [Cu 3 (µ 3 -O)(µ-pz) 3 Cl 3 ] -has previously shown charge delocalization over metals and ligands in the HOMO with equal participation of all three Cu-centers. [START_REF] Mezei | First Structural Characterization of a Delocalized, Mixed-Valent, Triangular Cu 3 7+ Species: Chemical and Electrochemical Oxidation of a Cu II 3 (µ 3 -O) Pyrazolate and Electronic Structure of the Oxidation Product[END_REF] Murray et al.

have recently argued that such [Cu 3 E] 3+ -mixed-valence systems should be called simply "covalent". [START_REF] Cook | Chalcogen Impact on Covalency within Molecular [Cu 3 (μ 3 -E)] 3+ Clusters (E = O, S, Se): A Synthetic, Spectroscopic, and Computational Study[END_REF] Analysis of this band by the Hush method results in a parameter = 0.63, classifying {MV-Cu 3 } as a Robin-Day type-III, strongly delocalized system. [START_REF] Concepcion | Probing the Localizedto-Delocalized Transition[END_REF][START_REF] Robin | Mixed Valence Chemistry-A Survey and Classification[END_REF][START_REF] Allen | Intervalence-Transfer Absorption. Part 1. Qualitative Evidence for Intervalence-Transfer Absorption in Inorganic Systems in Solution and in the Solid State[END_REF] In ambient temperature solution, the IVCT bands collapse and the absorption spectra match those of compounds 1 and 3 (Figure S10); this is further confirmed by FT-IR spectra (Figure S11) and unit cell determination of the recrystallized reaction product. Free nitrite ions can be easily oxidized to nitrate by even mild oxidizing agents. However, here the coordinated nitrites of 1 and 3 are shielded from the oxidants by the easier metal-based oxidation. The +3 oxidation state of copper is not easily accessible and rarely encountered, in contrast to its more common +2 and +1 states. Cu III -complexes have so far been isolated mostly with F and CF 3 ligands, or under the protection of sterically restricting coordination environments. [START_REF] Willert-Porada | Synthesis and X-Ray Structure of Bis(Trifluoromethyl)(N,N-Diethyldithiocarbamato)-Copper; a Remarkably Stable Perfluoroalkylcopper(III) Complex[END_REF][START_REF] Romine | Easy Access to the Copper(III) Anion [Cu(CF 3 ) 4 ][END_REF][START_REF] Santo | Diamagnetic-Paramagnetic Conversion of Tris(2-Pyridylthio)Methylcopper(III) through a Structural Change from Trigonal Bipyramidal to Octahedral[END_REF][START_REF] Ribas | Aryl C-H Activation by Cu II To Form an Organometallic Aryl-Cu III Species: A Novel Twist on Copper Disproportionation[END_REF][START_REF] Furuta | Doubly N-Confused Porphyrin: A New Complexing Agent Capable of Stabilizing Higher Oxidation States[END_REF][START_REF] Dhar | Effects of Charged Ligand Substituents on the Properties of the Formally Copper(III)-Hydroxide ([CuOH] 2+ ) Unit[END_REF][START_REF] Neisen | Formally Copper(III)-Alkylperoxo Complexes as Models of Possible Intermediates in Monooxygenase Enzymes[END_REF][START_REF] Spaeth | Determination of the Cu(III)-OH Bond Distance by Resonance Raman Spectroscopy Using a Normalized Version of Badger's Rule[END_REF] Some mononuclear Cu( 2 -O 2 ) complexes can be interpreted as Cu IIIperoxides or Cu II -superoxides. [START_REF] Mirica | Structure and Spectroscopy of Copper-Dioxygen Complexes[END_REF] The involvement of Cu III species in Cu I -catalyzed C-C bond formation reactions (known since the turn of the 20 th century) [START_REF] Fischer | Palladium-and Copper-Mediated N-Aryl Bond Formation Reactions for the Synthesis of Biological Active Compounds[END_REF] had been proposed, but only recently has it been demonstrated convincingly by studies employing rapid-injection NMR techniques. [START_REF] Bertz | Rapid Injection NMR in Mechanistic Organocopper Chemistry. Preparation of the Elusive Copper(III) Intermediate[END_REF] Various Cu III -mediated and -catalyzed reactions have been reported. [START_REF] Van Koten | Organocopper Compounds: From Elusive to Isolable Species, from Early Supramolecular Chemistry with RCuI Building Blocks to Mononuclear R 2-n Cu II and R 3m Cu III Compounds. A Personal View[END_REF][START_REF] Casitas | The Role of Organometallic Copper(III) Complexes in Homogeneous Catalysis[END_REF][START_REF] Hickman | High-Valent Organometallic Copper and Palladium in Catalysis[END_REF] Crosscoupling reactions forming C-S, C-Se and C-P bonds, catalyzed by a Cu III /Cu I -cycle have been reported recently. [START_REF] Font | Catalytic C-S, C-Se, and C-P Cross-Coupling Reactions Mediated by a Cu I /Cu III Redox Cycle[END_REF] A Cu II 2 Cu III -intermediate has been suggested as the catalytically-active species in the oxygenation of alkanes by oxygenases, such as particulate methane monooxygenase (pMMO). [START_REF] Chen | Development of the Tricopper Cluster as a Catalyst for the Efficient Conversion of Methane into MeOH[END_REF][START_REF] Shiota | Role of Tyrosine Residue in Methane Activation at the Dicopper Site of Particulate Methane Monooxygenase: A Density Functional Theory Study[END_REF] While the involvement of that oxidation state in enzymatic processes is disputed, [START_REF] Balasubramanian | Oxidation of Methane by a Biological Dicopper Centre[END_REF] synthetic Cu II 2 Cu III enzyme mimics have been suggested to carry out demanding chemical reactions, such as O-insertion into C-C and C-H bonds, [START_REF] Chen | Development of the Tricopper Cluster as a Catalyst for the Efficient Conversion of Methane into MeOH[END_REF][START_REF] Chen | Facile O-Atom Insertion into C C and C H Bonds by a Trinuclear Copper Complex Designed to Harness a Singlet Oxene[END_REF][START_REF] Lionetti | Metal-Templated Ligand Architectures for Trinuclear Chemistry: Tricopper Complexes and Their O 2 Reactivity[END_REF] including CH 4 to CH 3 OH oxidation. [START_REF] Chan | Efficient Oxidation of Methane to Methanol by Dioxygen Mediated by Tricopper Clusters[END_REF] excess of the 1:3 ratio did not cause metal reduction, consuming NaNO 2 and producing NO instead, indicating that the system is catalytic. Spectroscopic monitoring of the reaction of 1 or 3 with PhSH (Figure 6) shows the progressive formation of colorless {Cu I 3 } and regeneration of 3 upon NaNO 2 addition. Biological nitrite reduction by CuNIR proceeds at the type-II site by electrons derived from the oxidation of Cu I to Cu II at the type-I site:

Cu + + NO 2 -+ 2H +  Cu 2+ + NO + H 2 O
In the present case, however, the source of electrons is the sacrificial PhSH. Further experiments are required to determine whether reduction of nitrite takes place directly, or it is preceded by a metal-centered reduction to Cu I -nitrite, followed by intramolecular redox rearrangement resulting in the observed products.

The results of this preliminary study show that the trinuclear Cu II species 1 and 3 mediate the following reaction:

NO 2 -+ PhSH  NO + OH -+ ½ PhSSPh
In a closed system, this reaction will proceed until the buildup of hydroxide either decomposes the catalyst to Cu(OH) 2 , or leads to formation of [Cu(-OH)(-pz*)] n species. [START_REF] Ahmed | From Ordinary to Extraordinary: Insights into the Formation Mechanism and PH-Dependent Assembly/Disassembly of Nanojars[END_REF] Blanks run without PhSH, or without 1 (or 3), or with just 1 (or 3) and no proton donor, did not produce NO (Figure S5). During the NO sensing experiments with the amiNO-T meter, no NO response was seen until PhSH was added.

In summary, we have described two trinuclear copper pyrazolato complexes that activate recently, because of their potential therapeutic applications. [START_REF] Wonoputri | Copper Complex in Poly(Vinyl Chloride) as a Nitric Oxide-Generating Catalyst for the Control of Nitrifying Bacterial Biofilms[END_REF][START_REF] Yang | Metal-Phenolic Surfaces for Generating Therapeutic Nitric Oxide Gas[END_REF][START_REF] Paolucci | Dynamic Multinuclear Sites Formed by Mobilized Copper Ions in NO x Selective Catalytic Reduction[END_REF] To the best of our knowledge, compound 1 is the first homogeneous copper-catalyst and the first polynuclear-polynitrite NO releasing system reported to date; there is one example of an homogeneous iron-based catalyst. 12

Supporting Information

Crystallographic and structure refinement data, UV-vis and luminescence spectra monitoring the NO release 1 and 3, infrared and 1 H-NMR spectra. CCDC-1857948 to 1857950 contain the supplementary crystallographic data for this paper. These data can be obtained free of charge via www.ccdc.cam.ac.uk/conts/retrieving.html (or from the Cambridge Crystallographic Data

  becoming redox-active upon in situ deprotonation by addition of a base during electrochemistry experiments. Most importantly, we present here an initial report of the catalytic NO-release mediated by compounds 1 and 3 upon stoichiometric addition of PhSH as an one-eletron donor.

CH 2

 2 Cl 2 /Et 2 O at ambient temperature, resulting in purple X-ray quality crystals of (PPN) 2 [Cu 3 (µ 3 -O)(µ-pz) 3 (ONO) 3 ], 1 (monoclinic, P2 1 /c space group). It consists of a ninemembered [Cu-N-N] 3 metallacycle in which the Cu-atoms are held together by trans pyrazolato bridges, accommodating an almost planar Cu 3 (µ 3 -O) core (Figure 1). Complex 1 contains two  1 -O and one  2 -O,O nitrite ligands, with a C 2 axis going through the nitrogen of the  2 -ONO ligand, Cu-and µ 3 -O-atoms.

Figure 1 .and 3 . 15 Scheme 1 .

 13151 Figure 1. Ball-and-stick representation of 1. Color coding: Cyan, Cu; blue, N; red, O; black, C. H-atoms and PPN counter ions not shown for clarity. Selected interatomic distances (Å) and angles (º): CuCu: 3.248(5), 3.261(7); Cu-(µ 3 -O): 1.874(2), 1.880(1); Cu-N: 1.947(2) -1.959(2); Cu-O(NO): 2.349(3), 2.015(2), 2.653(4); Cu-O-Cu: 119.85(5), 120.30(1).

Figure 3 .Copper-based oxidation of 1 and 3 . 1

 331 Figure 3. X-band EPR spectra of complexes 1 (black) and 3 (red) in frozen CH 2 Cl 2 solutions (4.2 K). Experimental conditions for 1: f = 9.43 GHz, mod. ampl. = 2 G pp , micr. power = 2 mW; for 3: f = 9.31 GHz, mod. ampl. = 5 G pp , micr. power = 2.44 mW.

Figure 4 .

 4 Figure 4. Cyclic voltammograms (solid lines) and differential pulse voltammograms (dashed lines) of compound 1 (black) and 3 (red) in CH 2 Cl 2 with TBAPF 6 as the supporting electrolyte.

Figure 5 .

 5 Figure 5. UV-vis-NIR spectra of 1 (black) and {MV-Cu 3 } (red). Inset: IVCT band.

Figure 6 . 1 and 3 ,

 613 Figure 6. UV-vis spectroscopic monitoring of reaction of 3 upon stepwise addition of PhSH and NaNO 2 /MeOH in CH 2 Cl 2 .Quantitative measurement of NO

  terminal -O-nitrito ligands towards reduction, with release of NO, and stabilize them against oxidation to nitrates. The copper centers of complexes 1 and 3 differ from those encountered in CuNIR with regard to their coordination geometry: 1 and 3 contain Cu-atoms with square planar trans-N 2 O 2 coordination, while the mononuclear CuNIR are in a tetrahedral N 3 O environment. The X-ray structural data for 1 and 3 indicate that the  1 O, but not the  2 O,O, coordination mode of nitrite results in activation of an N-O bond. Addition of oxidizing agents to 1 or deprotonated 3 causes initially a copper-based oxidation to unstable mixed-valent [Cu 3 ] 7+ species. In contrast, PhSH, a reducing reagent capable of reducing both copper and nitrite, results in NO release. The NO releasing reaction is analogous to the well-known process of Snitrosothiols: 2RSNO  RSSR + 2NO. The catalytic release of NO by heterogeneous catalysts consisting of copper-based materials immobilized on solid supports have received attention

  After filtration and treatment of the filtrate with 10 mL Et 2 O, purple crystals of 1 were formed by slow evaporation at ambient temperature; Yield, 62%. Anal. Calcd./Found for C 81 H 69 N 11 Cu 3 O 7 P 4 (%) C, 59.44/59.77; H, 4.28/4.23; N, 9.49/9.41. FTIR (cm -1 ): 1439 (m), 1377 (m),  as (ONO); 1259 (s),  in CH 2 Cl 2 (15 mg, 0.092 mmol) or 3 (15 mg, 0.006 mmol) was prepared in a small vial. This vial was placed inside a larger one containing a solution of CoTPP (6.2 mg, 0.009 mmol) in 2 mL CH 2 Cl 2 and the larger vial was capped with a septum. A solution

	Synthesis of (PPN) 2 [Cu 3 (µ 3 -O)(µ-pz) 3 (ONO) 3 ] (1)
	To a 4 mL CH 2 Cl 2 solution of (PPN) 2 [Cu 3 (µ 3 -Cl) 2 (µ-pz) 3 Cl 3 ] (100 mg, 0.058 mmol) was added a
	solution of NaNO 2 (20.3 mg, 0.029 mmol) in 0.5 mL H 2 O and 2 mL MeOH. The reaction
	mixture was stirred for 24 h at ambient temperature.
	rectangular cavity operating in the TE102 mode. For variable-temperature experiments the cavity
	was fitted in an ESR900 dynamic continuous flow cryostat and the temperature was regulated
	with an Oxford ITC4 Intelligent Temperature Controller. EPR spectra of 3 were collected on a
	Bruker EMXplus spectrometer fitted with an EMX microX bridge and a Bruker ER4122SHQE
	cavity operating in the TE011 mode. For low temperature experiments, the cavity was fitted with
	an ESR900 dynamic continuous flow cryostat controlled with an Oxford ITC503S Intelligent
	Temperature Controller. EPR solutions were prepared in dry CH 2 Cl 2 freshly distilled over CaH 2
	and deoxygenated by freeze-thaw cycles and flame-sealed in the EPR tubes.

s (ONO); 1114 (s), 1052 (m), 997 (w), 872 (w), (ONO); 722 (s), 689 (s).

[START_REF] Maia | How Biology Handles Nitrite[END_REF]

H-NMR (CDCl 3 , ppm): 39.96 (3H, w 1/2 = 88 Hz); 37.21 (6H, w 1/2 = 145 Hz). UV-vis (CH 2 Cl 2 , cm -1 ): 28111, 36152, 37087, 38704. UV-vis (THF, cm -1 ): 14537, 29389, 36328, 37373, 38407.

Synthesis of (PPN

)[Cu 3 (μ 3 -OH)(μ-4-Ph-pz) 3 Cl 3 ]•CH 2 Cl 2 (2)

A mixture of CuCl 2

•2H 2 O (0.12 mmol, 20.5 mg), 4-Ph-pzH (0.12 mmol, 17.3 mg), NaOH (0.16 mmol, 6.4 mg), PPNCl (0.02 mmol, 11.8 mg) was stirred in CH 2 Cl 2 (15 mL) for 24 h. After filtration, the product was recrystallized by slow Et 2 O vapor diffusion into the CH 2 Cl 2 solution. Yield, 72%. Anal. Calcd./Found for C 64 H 54 Cl 5 Cu 3 N 7 OP 2 : C, 56.39/56.34; H, 4.00/3.99; N, 7.19/7.21.

Synthesis of (PPN

) 2 [Cu 3 (μ 3 -OH)(μ-4-Ph-pz) 3 (ONO) 3 ]•(CH 2 Cl 2 ) 0.5 (3)

To a 4 mL CH 2 Cl 2 solution of 2 (0.071 mmol, 100 mg) was added a solution of NaNO 2 (0.35 mmol, 24.6 mg) in 2 mL MeOH, and the reaction mixture was mixed at room temperature overnight. The mixture was filtered and X-ray quality crystals of 3 were obtained by treating the filtrate with 4 mL hexane. Well-shaped crystals of 3 suitable for X-ray diffraction were obtained after three days.

Yield

, 80%. Anal. Calcd./Found for C 127 H 108 Cl 2 Cu 6 N 20 O 14 P 4 : C, 56.31/56.06; H, 3.95/4.02; N, 10.35/10.19. FTIR: 1436 (w), 1360 (w),  as (ONO); 1215 (m),  s (ONO); 1114 (s), 1056 (m), 952(w), 848(w), d (ONO); 758 (m), 722 (s), 684 (s). 1H-NMR (DMSO-d 6 , ppm): 38.32 (6H, w 1/2 =186 Hz), 15.89 Hz, 19.17 Hz, 17 Hz). UV-vis (CH 2 Cl 2 , cm -1 ): 26692, 38469;

UV-vis (THF, cm -1 ): 27528, 38154.

Qualitative detection of NO generated from 1 and 3 by addition of thiophenol: Method A: A solution of 1 of PhSH (2.88 µL, 0.028 mmol; 1:3 stoichiometry), in 2 mL CH 2 Cl 2 was carefully injected to the solution of 1 via a syringe. UV-vis spectrum of the CoTPP solution was recorded after 2 h and spectral changes were observed due to NO binding to CoTPP (Figures

S3, S4

). The experiment was repeated with varying equivalents of PhSH (1:1, 1:2, 1:3, 1:4, 1:5 and 1:6). A blank experiment was conducted with the larger vial containing CoTPP (6.2 mg, 0.009 mmol) in 2 mL CH 2 Cl 2 and a smaller vial containing equimolar quantities of NaNO 2 and PhSH. No shift in the UV-vis absorption spectrum of CoTPP was observed after 2 h (Figure

  2 in MeOH to a solution of 2 in CH 2 Cl 2 produced 3 in a high yield and X-ray quality crystals were grown by slow diffusion of Et 2 O vapors into its CH 2 Cl 2 solution. Whereas 2 crystallizes in monoclinic P2 1 /n (TableS1, Fig.S2), compound 3 crystallizes in the triclinic ̅ space group with a whole molecule in the asymmetric unit. Three nitrite ligands are κ 1 -O-coordinated to Cu-centers with Cu-O ONO bonding distances of 2.026(3), 2.141(4) and 2.062(4) Å and non-bonded Cu•••O distances of 2.481(5), 2.476(4) and 2.553(5) Å. Of the three nitrito ligands, one is syn to theµ 3 -OH group while the other two are anti. The µ 3 -OH groups from adjacent Cu 3 -units form strong H-bonds with the

	bound O of the nitrito ligand [O(H) … O: 2.771(7) Å] (Figure

Table 1

 1

		. E 1/2 values of the [Cu 3	7+ /Cu 3	6+ ] couple of [Cu 3 (µ 3 -O)(µ-4-R-pz) 3 X 3 ] z vs. Fc + /Fc.
	R	X	E 1/2 (V)	Reference
	H	ONO	-0.133	This work
	H	Cl	-0.013	18
	Ph	ONO	+0.004	This work
	H	CF 3 CO 2	+0.131	18
	H	NCS	+0.253 (E pa )*	17
	H	py	+0.400	17

Funding Sources

National Science Foundation, USA (CHE-1213683 and CHE-1445803) Horizon 2020 research and innovation programme under the Marie Sklodowska-Curie grant, European Union; agreement No 746060 (project "CHIRALQUBIT").

Centre, 12 Union Road, Cambridge CB21EZ, UK; fax: (+44)1223-336-033; or deposit@ccdc.cam.ac.uk).

Scheme 2. Overall reactions investigated in the article. Cu II 3 is compound 1 or 3; pz* is pyrazolato (1) and 4-phenylpyrazolato (3); {Cu II 3 } is a transient species that has not been isolated; MV-Cu 3 is [Cu 3 (µ 3 -O)(µ-pz*) 3 (ONO) 3 ] 1-.

Ligand-based reduction of 1 and 3

To examine the NO releasing capabilities of 1 and 3, PhSH was used as a proton and electron donor, while the NO gas released was trapped by tetraphenylporphyrinatocobalt(II) (CoTPP) in a closed two-vial system. The diagnostic shift of absorption maximum from 528 nm to 535 nm of the former indicated CoTPP(NO) formation (Figure S3 & S4). When the ratio of Cu II 3 to PhSH is in the 1:1 to 1:3 range, NO release is triggered (Scheme 2 and Figures S3 andS4) leaving a green solution, presumed to be a solvent-stabilized Cu II species, {Cu II 3 }, which was not isolated.

Reaction with additional PhSH caused the solution to become colorless, indicating reduction to a Cu(I) species, {Cu I 3 }. Addition of hexane to this reaction mixture caused precipitation of a pale yellow solid containing PhSSPh as determined by FT-IR (Figure S12). Upon addition of nitrite in a vessel open to the atmosphere, the colorless {Cu I 3 } is readily cycled back to Cu II 3 , as confirmed by recrystallization and unit cell determination, with no NO production. However, when excess NaNO 2 was present together with 1 or 3 in the reaction vessel, addition of PhSH in

Author Contributions

The manuscript was written through contributions of all authors. All authors have given approval to the final version of the manuscript. # These authors contributed equally.

ACKNOWLEDGMENT


Rachel Horta Arduin
email: rachel.horta_arduin@ensam.eu

Guilhen Grimaud

Bertrand Laratte

Nicolas Perry

Horta Arduin

Plastics in WEEE Screens: Difficulties and Opportunities to Improve the Recycling Rate

Keywords: E-waste, WEEE, Recycling, Plastics, Flame retardants, Recycling rate

Nowadays the screens collected by the official e-waste schemes in France are mostly comprised of Cathode Ray Tube (CRT). Nevertheless, Flat Panel Display (FPD) collection should increase in the following years. Among other differences in material compositions, FPD screens have higher plastic content. In order to keep complying with the recycling targets for screens, as well as to increase the recycling performance per material, it is necessary to improve plastics recycling. The goal of this study is to quantify the plastic flows in screens generated, collected and recycled in France and to identify the current scenario of plastic recycling. The presence of flame retardants and additives in the plastics, the variety of polymer types, as well as the high volumes of black plastics are among the main challenges in plastics sorting and recycling. From the economic outlook, it is necessary to develop the market that uses secondary raw materials to ensure the profitability of the WEEE chain.

Introduction

Annually millions of tons of electric and electronic equipment (EEE) are placed on the market (POM), leading to a massive generation of waste. Waste of electric and electronic equipment (WEEE) is a particularly complex waste stream due to its material composition. While it contains some high-value materials (such as gold and palladium), it also includes some toxic materials (e.g., mercury and brominated flame retardants) [START_REF] Vadoudi | E-waste management and resources recovery in France[END_REF].

In the European Union, WEEE management is regulated by the WEEE Directive (European Commission, 2012). The existing indicators and targets are measured in an overall mass-based approach, and there are no incentives to recover specific materials (e.g., plastics or critical raw materials). Consequently, there is a lack of monitoring of the quantities of materials collected and recycled, as well as of the quality of the materials recycled.

In this context, this study aims to quantify the plastic flows in e-waste in France and identify the current difficulties to improve plastics recycling. The screens (category II of WEEE Directive) is selected as a case study since it represents well how a change in technology influences the volumes and types of material available for collection and recycling.

Methods

To quantify plastic flows in waste screens in France, the following data are required: (1) waste generation; (2) share of products in waste screens; (3) plastic content in screens; (4) collection rate ; (5) recycling rate.

In order to estimate the screens generation in France, the WEEE Calculation Tool1 is used and manually updated with recent POM data in France from the national registers of the French Environment & Energy Management Agency (ADEME) [START_REF] Deprouw | Rapport annuel du registre des déchets d'équipements électriques et électroniques[END_REF][START_REF] Fangeat | Indicateurs de suivi de la filière de Déchets d'Equipements Electriques et Electroniques Ménagers -Rapport interne ADEME[END_REF]. The methodology to calculate WEEE generated is based on the amount of EEE POM in the previous years and on the corresponding product lifespan. Regarding the share of different types of screens generated, data from the same tool is used together with data from the Urban Mining Platform2 . The screens category comprises both cathode-ray tube (CRT) and flat panel display (FPD) screens. It is comprised of the following products: tablets, laptops, TVs, and monitors.

To track target materials in e-waste flows, data about the composition of products and waste flows is essential. Once the compliance schemes do not regularly track the composition of e-waste categories by type of polymers, data from the literature is used [START_REF] Huisman | ProSUM Project Urban mine and Mining wastes -Final report[END_REF][START_REF] Talens Peiró | Analysis of material efficiency aspects of Energy related Product for the development of EU Ecolabel criteria -Analysis of product groups: personal computers and electronic displays[END_REF][START_REF] Tecchio | Analysis of material efficiency aspects of personal computers product group[END_REF][START_REF] Wagner | Quality Assessment of Plastic Recyclates from Waste Electrical and Electronic Equipment (WEEE): A Case Study for Desktop Computers, Laptops, and Tablets[END_REF] together with characterization assessments performed by the compliance schemes. Information regarding screens collected is also annually gathered and reported by ADEME. It is complemented with data from the ProSUM project [START_REF] Huisman | ProSUM Project Urban mine and Mining wastes -Final report[END_REF] and Ecologic (one of the compliance schemes in France), to estimate the share of different products collected by the official schemes. Lastly, the recycling rate is quantified based on treatment scenarios defined based on the current practices.

Results And Discussions

In 2017, FPD represented 47% of screens generated in France, an increase of 23% in comparison to 2012. The collection of FPD screens by the official schemes has also increased from 5% to 15% in the same period. FPD collection should increase in the following years, and over time CRT amounts will go down to zero.

Changes in the type of screens collected by the official schemes shift the type of materials available for recycling. Besides FPD being richer in terms of precious and critical materials, it also contains more plastics. The amount of plastics in screens generated in France from 2012 to 2017 has doubled. Nevertheless, recycling by the official schemes is still modest. Besides the variety of polymers present in (W)EEE, in this study is considered that only the recycling chain of acrylonitrile butadiene styrene (ABS), polypropylene (PP) and polystyrene (PS) from WEEE are established in France. Figure 1 presents the plastic flows in FPD and CRT screens in 2017. Only 21% of the total plastic generated was potentially recycled, mostly due to the recycling of CRT screens. The quality of the recycled plastic depends both on the product input and on the recycling process [START_REF] Wagner | Quality Assessment of Plastic Recyclates from Waste Electrical and Electronic Equipment (WEEE): A Case Study for Desktop Computers, Laptops, and Tablets[END_REF]. The main difficulties identified on e-waste plastics recycling are: (1) presence of brominated flame retardants; (2) sorting limitations due to black plastics;

(3) presence of plastic additives; (4) significant range of polymers and limited technologies to sort and recycle them [START_REF] Buekens | Recycling of WEEE plastics: A review[END_REF]Deloitte et al., 2015;[START_REF] Ma | Chemical recycling of brominated flame retarded plastics from e-waste for clean fuels production: A review[END_REF][START_REF] Sahajwalla | The present and future of e-waste plastics recycling[END_REF]. Therefore, often the recycled material has a lower quality and functionality than the original material (downcycling). Additionally, the polymers recycling processes may be more expensive than the equivalent raw material.

Conclusion

Besides the increase of plastics generated in end-of-life screens, its recycling is modest. Aiming to boost recycling of plastics from WEEE and ensure compliance with the European recovery targets, it is crucial to improve materials tracking and support the development of recycling technologies. Moreover, it is necessary to develop the market that uses secondary raw materials to ensure the profitability of the WEEE chain.

HAL

  is a multi-disciplinary open access archive for the deposit and dissemination of scientific research documents, whether they are published or not. The documents may come

Figure 1 .

 1 Figure 1. Plastic flows in WEEE screens in France (2017).According to the WEEE Directive, plastic with brominated flame retardants (BFRs) should be sorted from the other e-waste fractions. In 2017, it represented 13% of the amount of plastics collected by the official schemes. Brominated plastics are usually incinerated with energy recovery or landfilled as hazardous waste.

WEEE Calculation Tool is available in: http://ec.europa.eu/environment/waste/weee/data_en.htm

More details on the Urban Mining Platform is available in: www.urbanmineplatform.eu

Acknowledgments

The authors acknowledge the financial support from ADEME and Ecologic.


T Calamoneri

A Monti
email: monti@di.uniroma1.it

B Sinaimeri
email: blerina.sinaimeri@inria.fr

Keywords: Co-phylogeny, Reconciliations, Caterpillars

In reconstructing the common evolutionary history of hosts and parasites, the current method of choice is the phylogenetic tree reconciliation. In this model, we are given a host tree H, a parasite tree P , and a function σ mapping the leaves of P to the leaves of H and the goal is to find, under some biologically motivated constraints, a reconciliation, that is a function from the vertices of P to the vertices of H that respects σ and allows the identification of biological events such as co-speciation, duplication and host switch.

The maximum co-divergence problem consists in finding the maximum number of co-speciations in a reconciliation. This problem is NP-hard for arbitrary phylogenetic trees and no approximation algorithm is known.

In this paper we consider the influence of tree topology on the maximum co-divergence problem. In particular we focus on a particular tree structure, namely caterpillar, and show that -in this case-the heuristics that are mostly used in the literature provide solutions that can be arbitrarily far from the optimal value. Then, we prove that finding the max co-divergence is equivalent to compute the maximum length of a subsequence with certain properties of a given permutation. This equivalence leads to two consequences: (i) it shows that we can compute efficiently in polynomial time the optimal time-feasible reconciliation and (ii) it can be used to understand how much the tree topology influences the value of the maximum number of co-speciations.

Introduction

Symbiotic interactions concern almost every organism in the biosphere and have a great impact in essential fields of human life like health and agriculture. Due to the fact that symbiotic relationships represent a close association that may be continuous over time, the species involved may affect each other's evolution (this is known as co-evolution). Indeed, the closeness of the interaction can lead to co-speciation, that is the joint speciation of the involved species. Studying co-speciation is important for many reasons: it can shed light on the analysis of the rates of evolution between host and parasites, in determining how old the association between the host and the parasite is, and also in helping the design of better ways to combat pathogenic organisms (see for example [START_REF] Page | Tangled Trees: Phylogeny, Cospeciation and Coevolution[END_REF]).

The task of obtaining evidence of co-speciation, presenting exciting opportunities for the study of evolution, poses many theoretical and methodological challenges. One of the principal ways to infer co-speciation is through cophylogeny which allows the reconstruction of the co-evolutionary history of ecologically linked groups of organisms. Nowadays the most used method in co-phylogeny studies is phylogenetic tree reconciliation [1, 3-5, 9, 11, 6, 15]. In this model, we are given a host tree H, a parasite tree P , and a function σ mapping the leaves of P to the leaves of H (σ reflects the current knowledge on which existing parasites inhabit which hosts). The goal is to find a function γ from the vertices of the parasite tree to the vertices of the host tree, that extends σ and associates to each internal vertex of the parasite tree one of the following types of biological events: (a) co-speciation, indicating that the parasite speciates in correspondece to a speciation of the host, (b) duplication, indicating that the parasite speciates independently of the host and (c) host switch, indicating that after a speciation of the parasite one of the new species switches to a new host that is not related to the previous one (see for example [START_REF] Charleston | Jungles: a new solution to the host/parasite phylogeny reconciliation problem[END_REF][START_REF] Charleston | Recent results in cophylogeny mapping[END_REF][START_REF] Merkle | Reconstruction of the cophylogenetic history of related phylogenetic trees with divergence timing information[END_REF][START_REF] Page | Parallel phylogenies: reconstructing the history of host-parasite assemblages[END_REF]).

A high number of co-speciations of the species involved in the symbiotic relationship is usually considered as an indicator of possible co-evolution. Thus, one notion of optimality -that was introduced by Page in [START_REF] Page | Parallel phylogenies: reconstructing the history of host-parasite assemblages[END_REF] and is usually referred as maximum co-divergence-requires to maximize the number of cospeciations [START_REF] Page | Parallel phylogenies: reconstructing the history of host-parasite assemblages[END_REF][START_REF] Tofigh | Simultaneous identification of duplications and lateral gene transfers[END_REF]. If timing information on the host tree is unknown (for real datasets this information is rarely availble and reliable) this problem is NPhard [START_REF] Ovadia | The cophylogeny reconstruction problem is NP-complete[END_REF][START_REF] Tofigh | Simultaneous identification of duplications and lateral gene transfers[END_REF]. The difficulty stems from the presence of host switches. Indeed, a host switch introduces a temporal constraint in the order of the speciations in the host tree. This because for a host switch to happen the donor host and the receiver host must have co-existed in time. Hence, a sequence of host switches may lead to an incompatible sequence of speciation events in the host tree. A reconciliation for which there exists an order of the speciation events in the host tree that respects the partial order induced by the topology of the tree as well as the constraints introduced by the host switches is called time feasible.

In the following we refer to the problem of finding a time feasible reconciliation with maximum co-divergence as TF-MCD.

Considered the NP-hardness of TF-MCD, two natural relaxations are mostly considered in the literature: (i) the host switches are forbidden in the solution, and in this case the problem can be solved optimally using the LCA (the least common ancestor) mapping, and (ii) the host switches are allowed but the solutions are not required to be time feasible, in this case the problem can still be solved in polynomial time using dynamic programming (DP) but may be biologically infeasible [START_REF] Bansal | Efficient algorithms for the reconciliation problem with gene duplication, horizontal transfer and loss[END_REF][START_REF] Doyon | An efficient algorithm for gene/species trees parsimonious reconciliation with losses, duplications and transfers[END_REF][START_REF] Tofigh | Simultaneous identification of duplications and lateral gene transfers[END_REF].

For general instances, both of these relaxations provide reconciliations whose value can be arbitrary far from the value of an optimal time feasible solution. A natural question is whether for particular topologies of phylogenetic trees these algorithms can provide optimal time feasible solutions. This could potentially be used to design efficient heuristics or approximation algorithms that, by locally identifying these structures as subtrees, make optimal local choices. In this context, we consider TF-MCD in the very special case in which both the host and the parasite trees are caterpillars of the same size and function σ is a bijection.

After recalling the basic notations and definitions (Section 2) and proving some properties of time feasible reconciliations on caterpillars (Section 3), we show that even in this case the two algorithms (LCA and DP based) provide solutions that can be arbitrarily far from the optimal time feasible solution (Section 4). Then, in Section 5, we prove that finding the max co-divergence is equivalent to compute the maximum length of a subsequence with certain properties of a given permutation. This equivalence leads to two consequences: (i) it shows that we can compute efficiently in polynomial time the optimal time-feasible reconciliation and (ii) it can be used to understand how much the tree topology influences the value of the maximum number of co-speciations (that, as already pointed out, is considered as an indication of co-evolution). In Subsection 5.1. we show that, choosing the bijection σ between the n leaves of the two caterpillars uniformly at random, the value of the maximum number of co-speciations is Θ( √ n) w.h.p., so implying that -when this number is close to this value-no biological information can be deduced. In Section 6 we explore some structural properties of the set of optimal solutions for our particular instances. Many open problems arise from our work, and we list some of them in Section 7.

Basic notations and definitions

In this section we formalize many concepts already informally introduced in Section 1.

A rooted phylogenetic tree is a leaf-labelled tree that models the evolution of a set of taxa from their most recent common ancestor (placed at the root). The internal vertices of the tree correspond to the speciation events. A direc-tion is intrinsically assumed in the tree, that corresponds to the direction of evolutionary time. Henceforth, by a phylogenetic tree T , we mean a rooted tree with labelled leaves and where every vertex has in-degree 1 (except for the root that has in-degree 0) and out-degree 2 (except for the leaves that have out-degree 0). For such a tree T , the set of vertices is denoted by V (T ), the set of arcs by A(T ), and the set of leaves by Leaves(T ).

For a vertex v ∈ V (T ):

if v is different from the root, we call its parent as par(v); we denote by T v the subtree of T rooted in v and the vertices in T v are the descendants of v; the set of ancestors of v, denoted by Anc(v), is the set of vertices in the unique path from the root of T to v. We denote by Anc -(v) = Anc(v)\{v}.

Two vertices u and v are said to be incomparable if neither u ∈ Anc(v) nor v ∈ Anc(u).

The reconciliation function

Let H, P be the phylogenetic trees for the host and parasite species respectively. We define σ as a function from the leaves of P to the leaves of H that represents the association between currently living parasite and host species.

Definition 1 [START_REF] Tofigh | Simultaneous identification of duplications and lateral gene transfers[END_REF] Given H, P and σ, a function γ :

V (P ) → V (H) is a reconciliation if:
1. for any p ∈ Leaves(P ), γ(p) = σ(p) (γ extends σ); 2. for any internal vertex p ∈ V (P ) \ Leaves(P ) with children p 1 and p 2 :

(a) γ(p i ) ∈ Anc -(γ(p)) for i = 1, 2 (a child cannot be mapped to an ancestor of the father); (b) LCA(γ(p), γ(p 1 )) = γ(p) or LCA(γ(p), γ(p 2 ))) = γ(p) (one of the two children is mapped to the subtree rooted at its father); moreover, γ highlights a subset Ξ γ of A(P ) and partitions the set V (P ) into three sets Θ γ , ∆ γ and Σ γ as follows:

3. given an arc (u, v) ∈ A(P ), (u, v) ∈ Ξ γ ⇔ LCA(γ(u), γ(v)) ∈ {γ(u), γ(v)} (γ(u) and γ(v) are incomparable and arc (u, v) is a host switch); 4. for any p ∈ V (P ) \ Leaves(P ) with children p 1 and p 2 :

(a) p ∈ Θ γ ⇔ (p, p 1 ) ∈ Ξ γ or (p, p 2 ) ∈ Ξ γ (p is associated to a host switch event); (b) p ∈ ∆ γ ⇔ LCA(γ(p 1 ), γ(p 2 )) ∈ {γ(p 1 ), γ(p 2 )} (the children are mapped to comparable vertices and p is associated to a duplication event); (c) p ∈ Σ γ ⇔ LCA(γ(p 1 ), γ(p 2 )) = γ(p) and γ(p 1 ) and γ(p 2 ) are incomparable (p is associated to a co-speciation event).

Time-feasibility of a reconciliation

Time feasibility is an important biological constraint that we require on the reconciliation. We recall here the definition of a time feasible reconciliation presented in [START_REF] Donati | Eucalypt: efficient tree reconciliation enumerator[END_REF][START_REF] Stolzer | Inferring duplications, losses, transfers and incomplete lineage sorting with nonbinary species trees[END_REF].

Definition 2 Given a reconciliation γ, construct directed graph G γ as follows:

the vertex set of G γ coincides with V (H), the arc set of G γ contains the arcs of A(H) and in addition:

for any host switch (u, v) ∈ Ξ γ the following arcs: (1a) (par(γ(u)), γ(v)); (1b) (par(γ(v)), γ(u)); for all the couples of host switches (u, v), (u , v ) ∈ Ξ γ for which u ∈ Anc(u ) the following arcs: (2a) (par(γ(u)), γ(u

)); (2b) (par(γ(u)), γ(v )); (2c) (par(γ(v)), γ(u )); (2d) (par(γ(v)), γ(v )).
γ is time feasible if and only if G γ does not contain any directed cycle.

Max co-divergence problem (TF-MCD)

Given any reconciliation γ, we define its value, val(γ), as the number of cospeciations it contains, i.e. |Σ γ |. In the literature, this value is usually called as co-divergence. We focus on the following problem:

Definition 3
The max co-divergence problem (TF-MCD) is characterized by the following instance and question.

Instance: I = (H, P, σ) containing two phylogenetic trees H, P and a function σ : Leaves(P ) → Leaves(H); Question: Find a time feasible reconciliation γ for which val(γ) is maximum.

Our setting

In this paper we consider the case when the host tree H and the parasite tree P are both caterpillars on n leaves and σ is a bijection.

For the forthcoming definitions refer to Figure 1. We recall that a caterpillar is a tree in which all the vertices are within distance 1 of a central path, called spine. Every rooted phylogenetic tree that is also a caterpillar can be uniquely identified by the sequence of the labels of its leaves ordered from the furthest to the nearest to the root (for what concerns the only two leaves at the same distance from the root, by convention, we put first the one with lexicographic smaller label). Without loss of generality we will assume that P will be identified by the sequence 0, 1, 2, . . . , n -1 and H by l 0 , l 1 , . . . , l n-1 , with l 0 < l 1 .

We will assume that the (internal) vertices on the spine of P are called starting from the furthest from the root as x 1 , x 2 , . . . , x n-1 . Similarly, we call y 1 , . . ., y n-1 the vertices on the spine of H.

Note that x 1 has two children that are the leaves 0 and 1 and y 1 has two children that are the leaves l 0 and l 1 ; for any other 2 ≤ i ≤ n -1, the children of vertex x i are leaf i and internal vertex x i-1 , while the children of y i are leaf l i and internal vertex y i-1 .

Since in our setting H and P have a fixed structure and σ is a bijection, an instance I = (H, P, σ) can be identified simply by sequence S = σ -1 (l 0 ), . . . , σ -1 (l n-1 ) of the leaves of the host, that is a permutation on {0, 1, 2, . . . , n -1}. So, in the rest of this paper, when we speak about S we implicitly assume to have given the two caterpillars H and P , and bijection σ.

0 1 2 3 4 5 6 x 1 x 2 x 3 x 4 x 5 x 6 P !(0)=l 3 !(1)=l 2 !(2)=l 5 !(3)=l 0 !(4)=l 4 !(5)=l 1 !(6)=l 6 l 0 l 1 l 2

Properties of time feasible reconciliations for caterpillars

Here we prove some properties of time feasible reconciliations whose instance is a pair of caterpillars connected by a bijection σ. We will use these properties in the following of the paper.

Theorem 1 Given an instance S, let γ be one of its time feasible reconciliations; it holds that γ(

x i ) ∈ Anc -(γ(x j )) for any 1 ≤ i < j ≤ n -1.
Proof Suppose on the contrary that the claim does not hold, so there exist two indices i < j such that γ(x i ) ∈ Anc -(γ(x j )) and j -i is minimum. This assumption has some immediate consequences:

1. j -i > 1, indeed, in view of Definition 1.2(a) (a child cannot be mapped to an ancestor of its parent), x j cannot be the parent of

x i ; 2. Anc -(γ(x i )) ⊂ Anc -(γ(x j )); 3. γ(x i+1 ) ∈ Anc -(γ(x j )) and γ(x i ) ∈ Anc -(γ(x j-1 )) because j -i is mini- mum.
From item 1. it follows that x i+1 = x j and x j-1 = x i (although x i+1 and x j-1 are not necessarily distinct). We will prove that, in view of our assumption, in γ there necessarily exist two host switches (x i+1 , x i ) and (x j , x j-1 ) making γ time infeasible, so reaching a contradiction. Presence of host switch (x i+1 , x i ). In view of Definition 1.2(a) we have that γ(x i ) ∈ Anc -(γ(x i+1 )). On the other hand, from items 2. and 3. we have

γ(x i+1 ) ∈ Anc -(γ(x j )) ⊃ Anc -(γ(x i )).
It follows that x i+1 is mapped by γ neither in subtree of H γ(xi) , nor in an ancestor of γ(x i ). Hence, it is mapped in some leaf outside H γ(xi) and (x i+1 , x i ) is a host switch. Presence of host switch (x j , x j-1 ). In view of item 3. γ(x i ) ∈ Anc -(γ(x j-1 )). Moreover, from Definition 1.2(a) and item 2. we have γ(

x j-1 ) ∈ Anc -(γ(x j )) ⊃ Anc -(γ(x i )). Thus γ(x j-1 ) is a leaf outside H γ(xi) . Since γ(x i ) ∈ Anc -(γ(x j )), γ(x j ) ∈ H γ(xi)
, so x j and x j-1 are incomparable, implying that (x j , x j-1 ) is a host switch.

Since x j ∈ Anc -(x i ), in graph G γ will be added the four arcs related to the pair of host switches (x i+1 , x i ) and (x j , x j-1 ) with u = x j , v = x j-1 and u = x i+1 , v = x i , and in particular arc (2b), that is (par(γ(x j )), γ(x i )). By hypothesis γ(x i ) ∈ Anc -(γ(x j )), thus in G γ there is already a path from γ(x i ) to par(γ(x j )); hence the addition of arc (par(γ(x j )), γ(x i )) creates a cycle contradicting the hypothesis that γ is time feasible.

The next corollary follows straightforwardly from Theorem 1.

Corollary 1 Given an instance S, let γ be one of its time feasible reconciliations. For any two internal vertices of P , x i and x j , with i < j for which γ(x i ), γ(x j ) ∈ Leaves(H), it holds that γ(x j ) ∈ Anc(γ(x i )).

In other words, for any time feasible reconciliation γ, the order of the mapping of the internal vertices is kept on the spine of the caterpillar H.

The next theorem shows a simple sufficient condition for γ to be time feasible.

Theorem 2 Given an instance S, let γ be one of its reconciliations. Then γ is time feasible if for every two distinct internal vertices a, b of P , with b ∈ Anc -(a), both the following conditions hold:

(i) If γ(a) ∈ Leaves(H) then γ(b) ∈ Leaves(H) (ii) γ(a) ∈ Anc -(γ(b))
Proof Let γ be a reconciliation that satisfies the conditions (i) and (ii) and suppose by contradiction that γ is not time feasible. By Definition 2, this implies that G γ has a cycle C. Note that G γ is formed by the directed caterpillar H and some additional arcs. By construction, in G γ there are no arcs departing from a leaf of H, as every arc departs from par(w) for some w. Thus, no leaf belongs to cycle C (where every vertex must have outdegree at least one). Hence, calling y i the vertex in C with smallest index, there exists y j , with i ≤ j such that arc e = (y i , y j ) is in C. This arc should have necessarily been added because of either : (1) a single host switch (u, v) or (2) a pair of two host switches (u, v) and (u , v ) such that u ∈ Anc -(u ) (moreover, it easily follow that u ∈ Anc -(v ) ∩ Anc -(v)). We show now that (1) and (2) are both not possible by a case by case analysis depicted in Figure 2: (1a) If e is of type (1a) of Definition 2, then y i = par(γ(u)) and

y j = γ(v); hence, γ(v) ∈ Anc -(γ(u)) (see Figure 2(1a)); (1b) if e is of type (1b) of Definition 2, then y i = par(γ(v)) and y j = γ(u); it follows that γ(u) ∈ Anc -(γ(v)) (see Figure 2(1b)).
In both cases we get a contradiction as (u, v) is a host switch and, by item (3) of Definition 1, γ(u) and γ(v) must be incomparable in H.

par(g(u))=y i g(v))=y j g(u) par(g(v))=y i g(u))=y j g(v)
par(g(u))=y i g(u'))=y j g(u) In both cases it follows that γ(u) ∈ Anc -(γ(v)), that is u and v are not incomparable and hence (u, v) cannot be a host switch, a contradiction.

par(g(u))=y i g(v'))=y j g(u) par(g(v))=y i g(u'))=y j g(v) g(u))=y k par(g(v))=y i g(v'))=y j g(v) g(u))=y k (1a) (1b) (2a) (2b) (2c) (2d)
It is worth to note that Theorem 2 defines only sufficient conditions for a reconciliation to be time feasible. Indeed, while condition (ii) of Theorem 2 is necessary for the time feasibility of a reconciliation (see Theorem 1), condition (i) is not, as shown by the example in Figure 3. For every reconciliation γ, here we prove that for every internal vertex x i of P , at least one of the leaves in its subtree is mapped in a leaf of the subtree rooted at γ(x i ) in H.

Lemma 1 Given an instance S, let γ be one of its time feasible reconciliations; for every internal vertex x i there exists a j ∈ Leaves(P xi ) for which σ(j) ∈ Leaves(H γ(xi) ).

Proof The proof is by contradiction, so we assume that there exists ī such that all the leaves of P 0, 1, . . . ,ī are mapped outside H γ(xī) . Then let l be the smallest integer for which γ(x l ) belongs to H γ(xī) . (Observe that such an l is at most ī because at least γ(x ī) ∈ H γ(xī) .)

If l = 1 by our assumption σ(0), σ(1) ∈ H γ(xī) which contradicts Definition 1.2(b) (stating that at least one of the two children is mapped to the subtree rooted at the father).

If l > 1 then x l-1 ∈ H γ(xī) as l is the smallest integer and again by our assumption σ(l) ∈ H γ(xī) which again contradicts Definition 1.2(b).

Note that the previous result holds not only for caterpillars but for any two host and parasite trees.

We now prove that every reconciliation maps co-speciations and duplications to internal vertices of H. Lemma 2 Given an instance S, let γ be one of its time feasible reconciliations. For every internal vertex

x i , if γ(x i ) ∈ Leaves(H) then x i ∈ Θ γ .
Proof Let x i be such that γ(x i ) = l k and suppose on the contrary that x i ∈ Θ γ . Note that clearly x i ∈ Σ γ , hence x i ∈ ∆ γ and then both its children are mapped in l k . Note that i > 1 as the children of x 1 cannot be both mapped in l k (being σ a bijection). Then we should have γ(x i-1 ) = σ(i) = l k . Note that none of the leaves of

P xi-1 is mapped in Leaves(H γ(xi-1) ) = Leaves(H l k ) = {l k }.
Then from Lemma 1 we reach a contradiction.

LCA and DP based algorithms on caterpillar phylogenetic trees

In this section we show that, even in the special case when the two trees are caterpillars, the LCA and DP based algorithms can produce solutions arbitrarily far from the value of an optimal time feasible solution. To this purpose, given an instance S we can define three values:

val(γ LCA ), the number of co-speciations in the unique time feasible reconciliation γ LCA obtained by mapping each internal vertex of P to the least common ancestor of the mapping of its children in H; val(γ OP T ), the number of co-speciations in any time feasible reconciliation γ OP T that has the maximum number of co-speciations; val(γ DP ), the number of co-speciations in a possibly time infeasible reconciliation γ DP that has the maximum number of co-speciations. Note that this can be obtained by a dynamic programming algorithm (see for example [START_REF] Bansal | Efficient algorithms for the reconciliation problem with gene duplication, horizontal transfer and loss[END_REF][START_REF] Donati | Eucalypt: efficient tree reconciliation enumerator[END_REF][START_REF] Tofigh | Simultaneous identification of duplications and lateral gene transfers[END_REF]).

For these three values the following holds:

Fact 3 For every arbitrary instance I = (H, P, σ):

val(γ LCA ) ≤ val(γ OP T ) ≤ val(γ DP ).
Fact 3 provides upper and lower bounds for the maximum number of cospeciations in an optimal time feasible reconciliation. Even in our very simplified setting, these lower and upper bounds can be arbitrarily far as the gap may depend on the size of the trees as shown by the following examples.

Example 1. We define an instance S for which val(γ LCA ) is arbitrarily far from val(γ OP T ).

S is defined by the following bijection σ:

σ(i) =      l n-1 i = 0 l 0 i = n -1 l i otherwise.
Sequence S is obtained from the identity permutation by exchanging the values in the first and last position. As an example, see H 1 in Figure 4 when n = 7.

Observe that γ LCA maps all x i , 1

≤ i ≤ n -1, in the root of H 1 . From Definition 1, Σ γ LCA = {x 1 } and ∆ γ LCA = {x 2 , . . . , x n-1 }. Hence, val(γ LCA ) = 1.
Now, observe that γ defined as γ(x i ) = y i for 1

≤ i ≤ n -1 is a recon- ciliation with Σ γ = {x 2 , . . . x n-2 }, Θ γ = {x 1 } and ∆ γ = {x n-1 }. Hence, val(γ) = n -3,
and γ is a time feasible reconciliation in view of Theorem 2. Then:

1 = val(γ LCA ) < val(γ) = n -3 ≤ val(γ OP T ).
Example 2. We define an instance S for which val(γ DP ) is arbitrarily far from val(γ OP T ).

To this purpose for n odd, let S = 0, n+1 2 , 1, n+1 2 + 1, 2, n+1 2 + 2, . . . , n -1, n+1

2 -1 be defined by the following bijection σ:

σ(i) = l n+i 2 if i is odd l i 2 otherwise
Sequence S is obtained by putting the first n+1 2 integers in the even positions and the remaining n-1 2 integers in the odd positions. As an example, see H 2 in Figure 4 when n = 7. For this example, γ LCA is the following reconciliation:

γ LCA (x i ) = y 2i if 1 ≤ i ≤ n-1 2 y n-1 2 otherwise that produces Σ γ LCA = {x 1 , x 2 , . . . x n-1 2 } and ∆ γ = {x n+1 2 . . . , x n-1 }. Hence, val(γ LCA ) = n-1
2 . By applying Theorem 4 (stated in the next section) we have val(γ LCA ) = val(γ OP T ).

Consider now the following reconciliation γ:

γ(x i ) =      y 2i if 1 ≤ i < n-1 2 σ(n -1) if i = n-1 2 y 2i-n otherwise that produces Σ γ = {x 1 , . . . x n-1 2 -1 , x n-1 2 +1 , . . . x n-1 }, Θ γ = {x n-1 2 , x n+1 2
}, giving val(γ) = n -3. Clearly, as the DP algorithm takes the maximum over all reconciliations (time infeasible and feasible) we conclude:

n -1 2 = val(γ LCA ) = val(γ OP T ) < n -3 = val(γ) ≤ val(γ DP ). 6

TF-MCD is polynomially solvable for identical caterpillars and bijection σ

In this section we show that, although the DP and LCA based algorithms do not provide good solutions in the case of caterpillars, it is however possible to provide the optimal time feasible solution in polynomial time.

As already mentioned in the introduction, if the timing information on the host tree (i.e. the order in which speciation events occurred in the host phylogeny) is not available, TF-MCD is NP-hard [START_REF] Ovadia | The cophylogeny reconstruction problem is NP-complete[END_REF][START_REF] Tofigh | Simultaneous identification of duplications and lateral gene transfers[END_REF]. If timing information on the host tree is known, the problem has been tackled in 7, 1]. However, the optimal solutions produced by the algorithm in [START_REF] Bansal | Efficient algorithms for the reconciliation problem with gene duplication, horizontal transfer and loss[END_REF] can still be time infeasible. This is because the constraint used in [START_REF] Bansal | Efficient algorithms for the reconciliation problem with gene duplication, horizontal transfer and loss[END_REF] to ensure the time feasibility works only locally but two locally time consistent host switch events can be globally inconsistent (see [START_REF] Doyon | An efficient algorithm for gene/species trees parsimonious reconciliation with losses, duplications and transfers[END_REF]). In [START_REF] Ronquist | Reconstructing the history of host-parasite associations using generalised parsimony[END_REF][START_REF] Doyon | An efficient algorithm for gene/species trees parsimonious reconciliation with losses, duplications and transfers[END_REF] the authors propose an algorithm of time complexity O(nm) (for n and m size of the host and parasite tree, respectively) which globally guarantees the time feasibility, but their model is slightly different from the one we used (for example the duplication events are not defined the same way and host switch events are defined on edges).

Based on this, although the structure of caterpillar defines a total order of the speciation events in the host tree, the polynomiality results in [START_REF] Ronquist | Reconstructing the history of host-parasite associations using generalised parsimony[END_REF][START_REF] Doyon | An efficient algorithm for gene/species trees parsimonious reconciliation with losses, duplications and transfers[END_REF][START_REF] Bansal | Efficient algorithms for the reconciliation problem with gene duplication, horizontal transfer and loss[END_REF] do not directly apply to our model. Here we show that such an algorithm can be still found. Moreover it is efficient as it has time complexity O(n log n).

Definition 4 Given a sequence z = z 1 , . . . , z t , t ≥ 2 of integers, a subsequence z i1 , z i2 . . . , z i k , of z is nearly increasing if either (a) i k = 2, or (b) z i2 < . . . < z i k and z i1 < z i3 .
We denote by lnis(z) the length of a longest nearly increasing subsequence of z.

In other words, a subsequence is nearly increasing if either it is increasing or it becomes increasing by exchanging the positions of the first two elements. Observe that the possibility to re-order the first two elements of the sequence mimics the fact that there is no fixed order in the unique pair of leaf siblings of the caterpillar.

We now proceed to prove the main result of this section.

Lemma 3 Given an instance S, let γ be one of its time feasible reconciliations; then lnis(S) ≥ val(γ) + 1.

Proof Let it be val(γ) = r. If r = 0 or r = 1 then the claim is obvious because lnis(S) ≥ 2. So, let it be r ≥ 2. We will show that the r co-speciations of γ will define a nearly increasing subsequence of S of length r + 1. Let

Σ γ = {x i1 , . . . , x ir }, with i 1 < i 2 . . . < i r . From Lemma 2 for all 1 ≤ j ≤ r, γ(x ij ) = y kj . From Corollary 1 we have k 1 < k 2 . . . < k r . The sequence k 1 , . . . , k r identifies a subsequence of length r of S, S = σ -1 (l k1 ), . . . , σ -1 (l kr ) in H.
We show now that S is an increasing subsequence, that is for all 1 ≤ j < r, σ -1 (l kj ) < σ -1 (l kj+1 ). To this purpose is enough to show that for 1 ≤ j < r it holds i j < σ -1 (l kj+1 ) ≤ i j+1 .

(1) Since x ij+1 is associated to a co-speciation event, exactly one of its two children must be mapped on l kj+1 . If the child mapped on l kj+1 is leaf i j+1 then we are done since i j < σ -1 (l kj+1 ) = i j+1 . Otherwise the child mapped on l kj+1 is internal vertex x ij+1-1 . Let t be the largest integer such that x ij+1-1 , . . . , x ij+1-t are all mapped in l kj+1 . This means that σ -1 (l kj+1 ) = i j+1 -t. Since i j+1 -t ≤ i j+1 we have that σ -1 (l kj+1 ) ≤ i j+1 .

On the other hand, x ij is a co-speciation, so it is mapped on the spine of H and so it cannot be mapped in l kj+1 , and thus i j+1 -t > i j . Hence,

i j < i j+1 -t = σ -1 (l kj+1 ).
It remains to show that we can extend S to the left to create a nearly increasing subsequence of length r+1. We show that exists a l j with 0 ≤ j < k 1 such that σ -1 (l j ) < σ -1 (l k2 ).

If i 1 = 1 then, as x 1 is a co-speciation, both its children 0, 1 are mapped in the subtree H γ(x1) and we have two cases:

(a) σ -1 (l k1 ) = 0: then 1 will be mapped in some l j with j < k 1 and we extend S by adding as a first element 1 (note that 1 < σ -1 (l k2 );

(b) σ -1 (l k1 ) = 1: then 0 will be mapped in some l j with j < k 1 and we extend S by adding as a first element 0 obtaining an (r + 1) long increasing subsequence.

Finally, suppose that i 1 > 1, then there exists x i1-1 and Definition 1.4(c) guarantees γ(x i1-1 ) ∈ H γ(xi 1 ) . There are two cases:

(a) γ(x i1-1 ) = l k1 : then, as x i1 is a co-speciation, i 1 is mapped in some l j with j < k 1 . From inequality (1) i 1 < σ -1 (l k2 ) and so we extend to the left S by adding i 1 ;

(b) γ(x i1-1 ) = l k1 : then, by Lemma 1, there exists a leaf l j with j < k 1 such that σ -1 (l j ) ≤ i 1 -1. We extend S to the left by adding σ -1 (l j ). Note that the obtained sequence is increasing as σ -1 (l j ) < σ -1 (l k1 ).

In the following lemma we show it is possible to construct a time feasible reconciliation in correspondence of a nearly increasing subsequence. The main idea is the following: if S is a nearly increasing subsequence of S, for any leaf l ij of H corresponding to the i j -th element of S , except the first one, we map in y ij (that is the corresponding internal node of l ij ) the internal node of P whose leaf is labeled with the same label as l ij (formally this node is x σ -1 (li j ) ). These internal nodes of P will be the co-speciations of γ. Every other internal node of P , x k , that has not been mapped yet, is mapped together with x m with m being the maximum value that is smaller than k and such that x m is already mapped. In this way, we still have to map the first group of internal nodes of P , x 1 , . . . , x t with t = σ -1 (l i2 ) -1. The mapping of these latter nodes will be different according to whether S is increasing or not. However, in both cases, the mapping will guarantee that the first node we mapped x σ -1 (li 2 ) will be a co-speciation. Lemma 4 Given an instance S, there exists a time feasible reconciliation γ such that val(γ) ≥ lnis(S) -1.

Proof Let S be a nearly increasing subsequence of S. Preliminarily observe that |S | ≥ 2; if |S | = 2 then the last element in S is either 0 or 1 (indeed, if there were a value a = 0, 1, then either 0, 1, a or 1, 0, a would be a nearly increasing subsequence of S of length 3); the reconciliation mapping all internal vertices of P on the root of H is time feasible and val(γ) = 1 as Σ γ = {x 1 }.

Let now |S | > 2 and S = σ -1 (l i1 ), . . . , σ -1 (l ir+1 ) be a nearly increasing subsequence of S, of length r+1. We consider two cases: (a) σ -1 (l i1 ) < σ -1 (l i2 ) or (b) σ -1 (l i2 ) < σ -1 (l i1 ) < σ -1 (l i3 ).

(a) σ -1 (l i1 ) < σ -1 (l i2 ) -refer to Fig. 5.a for an example.

We define the following reconciliation γ for all x i with 1 ≤ i ≤ n -1:

γ(x i ) =          σ(0) 1 ≤ i < σ -1 (l i1 ) l i1 σ -1 (l i1 ) ≤ i < σ -1 (l i2 ) y li k σ -1 (l i k ) ≤ i < σ -1 (l i k+1 ), for all 2 ≤ k ≤ r y li r+1 i ≥ σ -1 (l ir+1 ).
Observe that in view of the definition of γ, for every 2 ≤ k ≤ r + 1, x i k is mapped to an internal vertex γ(x i k ). Moreover, its child i k is mapped in the subtree of H γ(xi k ) consisting of only one leaf while the other child, x i k-1 , is mapped in the other subtree. Hence S defines r co-speciations being Σ γ ⊇ {x i2 , x i3 , . . . x ir+1 } and so val(γ) ≥ r. It remains to show that γ is a time feasible reconciliation. To see this, observe that both the conditions of Theorem 2 hold for γ. We define the following reconciliation γ for all x i with 1 ≤ i ≤ n -1:

(b) σ -1 (l i2 ) < σ -1 (l i1 ) < σ -1 (l i3 ) -refer to
γ(x i ) =          σ(0) 1 ≤ i < σ -1 (l i2 ) l i2 σ -1 (l i2 ) ≤ i < σ -1 (l i1 ) y li k σ -1 (l i k ) ≤ i < σ -1 (l i k+1 ), for all 2 ≤ k ≤ r y li r+1 i ≥ σ -1 (l ir+1 ).
Using arguments similar to the previous case, we observe that γ is time feasible and S defines r co-speciations, Σ γ ⊇ {x i2 , x i2 , . . . x ir+1 }. Hence, val(γ) ≥ r.

Given an instance S, Lemma 3 holds for every time feasible γ and in particular for γ OP T , so we get lnis(S) ≥ val(γ OP T ) + 1; on the other hand, val(γ OP T ) ≥ val(γ), so from Lemma 4 it comes out val(γ OP T ) -1 ≥ lnis(S). Observe that lnis(S) can be computed similarly to the length of the longest increasing subsequence of S. Indeed, the latter one can be computed in O(n log n) time [START_REF] Romik | The Surprising Mathematics of Longest Increasing Subsequences[END_REF][START_REF] Bespamyatnikh | Enumerating longest increasing subsequences and patience sorting[END_REF] where the main idea is to scan the sequence from left to right, maintaining at any given time an efficient representation of all the possible Fig. 5 Two instances where: (a) S = 8, 2, 4, 6, 7, 3, 0, 1, 5 and hence σ -1 (l i 2 ) < σ -1 (l i 1 ). (b) S = 8, 4, 2, 6, 7, 3, 0, 1, 5 and hence σ -1 (l i 1 ) < σ -1 (l i 2 ).

increasing subsequences that can be formed with the elements seen so far and then applying binary search to extend them. It is easy to see that lnis(S) can be computed in the same way by keeping also the sequences that can be increasing by exchanging the first two positions. This adds a constant multiplicative factor to the comparisons made by the algorithm and then lnis(S) can be computed in O(n log n). Hence, it follows: Theorem 4 Given an instance S, it holds: val(γ OP T ) + 1 = lnis(S). and it is possible to find an optimal time feasible reconciliation in polynomial time.

Behavior of val(γ OP T ) for randomly chosen instances

Given a sequence S, let lis(S) be the length of the longest increasing subsequence; it is obvious that lis(S) ≤ lnis(S) ≤ lis(S) + 1. We exploit some known results for lis(S) to draw some inferences on lnis(S). To do this, we call π(n) a permutation chosen uniformly at random on the first n positive integers and define the expected value of the longest increasing subsequence length over all permutations of order n as l n = 1 n! π(n) lis(π(n)). It is well known that, for all n ≥ 1, l n ≥ √ n (see for e.g. [START_REF] Romik | The Surprising Mathematics of Longest Increasing Subsequences[END_REF]). The following result shows that in fact the behavior of lis(π(n)) for a typical permutation π(n) is asymptotycally the same as that of its average value. More formally: Theorem 5 (Hammersley's convergence theorem [START_REF] Hammersley | A few seedlings of research[END_REF]) The limit lim n→∞ ln √ n exists. Furthermore, for every permutation π(n) chosen uniformly at random, and for every > 0, Pr{| lis(π(n)) √ n -Λ| > } → 0 as n → ∞, where Λ is a constant.

It is clear that this result holds also for lnis(S). It follows that, for an instance S, in order to deduce some possible biological correlation between the two caterpillars, we should obtain a similarity that is greater than what is expected by chance, in other words we should have lnis(S) = ω( √ n).

Properties of reconciliations for caterpillars

If we do not restrict our attention to optimal reconciliations but consider the whole set of time feasible reconciliations, then it is always possible to have both a reconciliation without host switches (e.g. by the LCA mapping) and a reconciliation with no duplications (e.g. by mapping every internal vertex of the parasite to a leaf of the host). In other words, forbidding either host switches or duplications let us loose the optimality keeping the time feasibility. This is true even when we consider only our special instances. Indeed, Example 1 in Section 4 shows that an optimal time feasible solution without host switches may not exist; the same holds for duplications e.g. for instance S = 3, 1, 8, 2, 7, 5, 0, 4, 6: by checking exhaustively (e.g. using a tool as Eucalypt [START_REF] Donati | Eucalypt: efficient tree reconciliation enumerator[END_REF]) each of its optimal time feasible reconciliations, we realize it contains at least one duplication. Nevertheless, if we drop the time feasibility requirement, we can eliminate duplications keeping the optimality. The next theorem provides a transformation that, given an optimal time feasible reconciliation, outputs a reconciliation without duplications with the same val but not necessarily time feasible.

Theorem 6 Given an instance S, there exists always a (not necessarily time feasible) reconciliation δ with val(δ) = val(γ OP T ) and ∆ δ = ∅.

Proof Let γ OP T = γ be the optimal time feasible reconciliation defined in the proof of Lemma 4. If γ has no duplications then we are done. Otherwise, from Lemma 2, the duplications can be only in the internal vertices of H. Hence, let y d1 , . . . , y d f for some 1 ≤ f ≤ lnis(S), the vertices in which at least one duplication is mapped. By construction, for each d j , let x dj , x dj +1 , . . . , x dj +tj , with t j ≥ 1, be the vertices mapped by γ in y dj . Observe x dj ∈ Σ γ and all the others are in ∆ γ ∪ Θ γ . Let t j be the largest integer for which x dj +t j is a duplication. For each j = 1, . . . , f we construct reconciliation δ from γ by setting δ(x dj ) = . . . = δ(x dj +t j -1 ) = l dj (see Figure 6). On all the other vertices, δ coincides with γ. Notice that:

(i) x dj was a co-speciation in γ and is a host switch in δ;

(ii) x dj+1 , . . . , x dj +t j -1 were either duplications or host switches in γ and are all host switches in δ; (iii) x dj +t j was a duplication in γ and becomes a co-speciation in δ; (iv) x dj +t j +1 , . . . , x dj +tj remain host switches when passing from γ to δ.

Clearly val(δ) = val(γ). As shown in Figure 6, δ is not necessarily time feasible.

Conclusions

In this paper we have considered the problem of finding time feasible reconciliations with the maximum number of co-speciations in the very special case in which both the host and the parasite trees are caterpillars of the same size and function σ is a bijection.

Many open questions and possible research lines raise from this work:

-A natural step consists in relaxing our constraints. Namely, a first question is to study the maximum co-divergence problem for two caterpillars when σ is not a bijection anymore. This research could also lead to a tight relation between the number of co-speciations and the maximum length of a common subsequence with more general constraints than the nearly increasing one.

Moreover, it is certainly interesting to investigate other tree topologies for H and P such as for example complete binary trees. This approach could lead to design approximation algorithms that locally solve TF-MCD on substructures of the input phylogenies that can be reconciled optimally in polynomial time.

-Recall that using the transformation described in Section 6 it is possible to transform an optimal reconciliation to a reconciliation of the same value that does not contain any duplication, but without necessarily ensure the time feasibility. An interesting question may be to reach an optimal time feasible reconciliation that has the minimum number of duplications. A first idea is to procede in a greedy fashion, removing one by one the duplications of an optimal time feasible reconciliation while keeping time feasibility, but this simple procedure seems not to always lead to the optimum.

Fig. 1

 1 Fig.1An example of an instance where host and parasite trees are the caterpillars on 7 leaves together with the mapping σ. Note that S = 3, 5, 1, 0, 4, 2, 6.

Fig. 2

 2 Fig.2The cases in the proof of Theorem 2.

2 Fig. 3

 23 Fig. 3 An example of time feasible reconciliation γ showing that condition (i) of Theorem 2 is not necessary: here S = 0, 1, 4, 2, 3; a = x 1 and b = x 3 , hence b ∈ Anc -(a), γ(a) ∈ Leaves(H) but γ(b) ∈ Leaves(H).

Fig. 4

 4 Fig. 4 The host trees H 1 and H 2 illustrating the two examples where the LCA and the DP based algorithms produce reconciliations whose values are far from the optimum.

Fig. 5 .

 5 b for an example.

Fig. 6 S

 6 Fig. 6 S = 3, 1, 8, 2, 7, 5, 0, 4, 6; (left) optimal time feasible reconciliation γ as defined in the proof of Lemma 4; (right) reconciliation δ as defined in the proof of Theorem 6; δ is time infeasible because of the pair of host switches (u, v) = (x 7 , 7) and (u , v ) = (x 6 , x 5 ); the addition of arc (par(γ(7)), γ(x 5 )) of kind (2d) creates a cycle in G δ .

Research carried on while the third author was visiting the Computer Science Department of This work has been partially supported by Sapienza University of Rome, project "