Michel Lagarde
email: michel.lagarde@insa-lyon.fr

Catherine Calzada

Charlotte Jouvène

Nathalie Bernoud-Hubac

Marion Létisse

Michel Guichardant

Evelyne Véricel

Functional fluxolipidomics of polyunsaturated fatty acids and oxygenated metabolites in the blood vessel compartment

Keywords: AdA, adrenic acid, ALA, alpha-linolenic acid, ArA, arachidonic acid, COX, cyclooxygenase, Cyp, cytochrome P 450, DAG, diacylglycerol, DHA, docosahexaenoic acid

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Polyunsaturated fatty acids (PUFA) are mainly esterified at the sn-2 position in glycerophospholipids of animal cell membranes, and may be released by phospholipases, especially phospholipases A 2 in response to cell activation. Some of these PUFA may be then quickly oxygenated by cell oxygenases to provide very potent lipid mediators that could lose or change their biological activity following specific metabolic pathways. The kinetics of PUFA release will depend on the phospholipases involved, and the metabolic fate of the resulting non-esterified PUFA will undergo concurrent oxygenation at different rates and reacylation, with preferred routes according to the nature of the PUFA. Similarly, the degradation pathways depend on the different oxygenated products, with even generation of new active mediators instead of inactive products. Measuring the largest possible number of metabolites as a function of time, in an attempt to determine fluxes for each of them, will allow better approaching the phenotype of a biological system, with a global view if the measurements are made in different biological compartments. This lipidomics approach, associated with fluxes determination, justifies the name of fluxolipidomics, as in other approaches lipidomics may be focused on a specific class of lipids giving the names of mediator lipidomics and structure lipidomics. Special attention will be paid in this review to those lipid mediators produced in blood platelets, endothelial cells and leukocytes that play important roles in the athero-thrombosis regulation, and which are close to cell compartments. This review will focus on these aspects, with qualitative considerations for the enzyme kinetics that are not known yet in detail.

PUFA relevant for cell functions

The most abundant PUFA in animal cells are presented in Fig. 1. The major PUFA is arachidonic acid (ArA or 20:4n-6), except in the brain and retina where the major one is docosahexaenoic acid (DHA or 22:6n-3) [START_REF] Crawford | Evidence for the unique function of docosahexaenoic acid during the evolution of the modern hominid brain[END_REF]. However, the PUFA content of most tissues changes in response to environment, notably the remodeling of phospholipid composition by nutrition [START_REF] Lands | Long-term fat intake and biomarkers[END_REF]. The brain may be an exception because of the blood-brain barrier that exerts selective crossing of PUFA, which likely explains its high enrichment in DHA [START_REF] Rapoport | In vivo approaches to quantifying and imaging brain arachidonic and docosahexaenoic acid metabolism[END_REF].

Fig. 1 Biogenesis of the most frequent polyunsaturated fatty acids (PUFA).These PUFA belong to the three n-3/omega-3, n-6/omega-6 and n-9/omega-9 families. E indicates an elongase, and Δ a desaturase, followed by the carbon number of the new double bond issued from the desaturation. However,Δ4 has quotation marks because it means Δ4 desaturation instead of Δ4desaturase in one step. It must be taken as a more complex step than the other desaturation (e.g. Δ5 and Δ6). Indeed Δ4 desaturation includes first a further elongation, followed by Δ6 action, and finally beta-oxidation [START_REF] Voss | The metabolism of 7,10,13,16,19docosapentaenoic acid to 4,7,10,13,16,19-docosahexaenoic acid in rat liver is independent of a 4-desaturase[END_REF].PUFA undergoing oxygenation metabolism and addressed in this review are underlined. They are: 18:3n-3: alpha-linolenic acid (ALA, 9,12,15-octadecatrienoic acid); 20:5n-3: eicosapentaenoic acid (EPA, 5,8,11,14,17-eicosapentaenoic acid); 22:5n-3: docosapentaenoic acid (DPAn-3, In addition to ArA, the other PUFA of interest within the n-6/omega-6 family are linoleic acid (LA or 18:2n-6), the most abundant PUFA in plant oils, dihomo-gammalinolenic acid (DGLA or 20:3n-6), the immediate precursor of ArA, and docosatetraenoic/adrenic acid (AdA or 22:4n-6), the elongation product of ArA. Within the n-3/omega-3 family fatty acids, the essential precursor alpha-linolenic acid (ALA or 18:3n-3), found in some plant oils, and eicosapentaenoic (EPA or 20:5n-3) as well as docosapentaenoic (DPA or 22:5n-3) acids are the main PUFA of marine origin with DHA. They are the major n-3 PUFA of biological interest (Fig. 1). As shown in this figure, other PUFA intermediates belong to both families, but their oxygenation metabolism and the biological action of their metabolites have not been investigated in detail. They will not be discussed in the frame of this review.

Arachidonic acid as a reference PUFA

The main classes of oxygenated PUFA, such as prostanoids, leukotrienes and other oxygenase products, have arachidonic acid (ArA) as the reference precursor [START_REF] Goetzl | Specificity of expression and effects of eicosanoid mediators in normal physiology and human diseases[END_REF]. Fig. 2 shows as a general scheme for the main active metabolites and their stable degradation products, all relevant to the blood and vascular cells compartment. Also, ArA is a major PUFA of the peripheral tissues in mammals, including the blood vessel compartment, where its conversion into oxygenated products is of relevance for cell function. Fig. 3 points out some biological functions of relevant primary and secondary metabolites with a special emphasis to antagonistic and synergistic functions. Also, they must be taken into account for the completion of ArA and DHA metabolism at a rate that includes their transfer to the ethanolamine moiety of PE followed by a specific First, ArA must be released from membrane phospholipids in response to cell activation by extracellular messengers. The main phospholipase involved is the cytosolic phospholipase A 2 (cPLA 2 ) which requires micromolar concentrations of cytosolic calcium ions [START_REF] Yang | Group-specific assays that distinguish between the four major types of mammalian phospholipase A2[END_REF]. This concentration can be reached either by calcium entry from the extracellular space or by release from endoplasmic reticulum [START_REF] Clark | A novel arachidonic acid-selective cytosolic PLA2 contains a Ca(2 +)-dependent translocation domain with homology to PKC and GAP[END_REF]. In the latter case, inositol trisphosphate (IP 3 ) may be the triggering agent, which establishes a link between the cleavage of phosphatidylinositol-4,5-bisphosphate (PIP 2 ) by phospholipase C (PLC), the primary event,

and the activation of cPLA 2 . The other cleavage product is diacylglycerol (DAG), mainly 1palmitoyl,2-arachidonoyl-glycerol, which is generated prior to the activation of cPLA 2 . Then, the release of ArA from phospholipids (mainly phosphatidyl-choline and -ethanolamine) by cPLA 2 may parallel that from ArA-containing DAG by DAG lipase [START_REF] Authi | Diacylglycerol lipase activity in human platelet intracellular and surface membranes. Some kinetic properties and fatty acid specificity[END_REF], although with different kinetics. However, in terms of quantities, ArA released by cPLA 2 is likely higher than that from PIP 2 through the PLC/DAG lipase cascade.

Once released, ArA will be either oxygenated by cyclooxygenases (COX), lipoxygenases (LOX) and cytochrome P 450 (Cyp) monooxygenases, depending on the cell equipment, or re-acylated into membrane phospholipids by re-esterifying the lysophospholipids produced by the primary cleavage [START_REF] Cane | Oxidant-induced arachidonic acid release and impairment of fatty acid acylation in vascular smooth muscle cells[END_REF].

The cyclooxygenation is considered the fastest stage in the ArA oxygenation, with the self-denaturation of the enzyme due to the release within the enzyme of the oxygen radical produced by hydroperoxidase, the second enzymatic function of prostaglandin (PG) H synthase [START_REF] Markey | Quantitative studies of hydroperoxide reduction by prostaglandin H synthase. Reducing substrate specificity and the relationship of peroxidase to cyclooxygenase activities[END_REF]. In other words, the primary product of COX, PGG 2 is a 15-hydroperoxide converted into its 15-hydroxyl derivative PGH 2 by hydroperoxidase that releases oxygen radicals. This occurs within a few minutes with substantial amount of prostanoids already made in less than 1 min. As a matter of fact, fully active quantities of thromboxane A 2 (TxA 2 )

are generated within 30s in activated blood platelets, resulting from the isomerization of PGH 2 by thromboxane synthase [START_REF] Hamberg | Thromboxanes: a new group of biologically active compounds derived from prostaglandin endoperoxides[END_REF]. The pro-aggregatory action of TxA 2 generated by platelets themselves may be modulated by primary prostaglandins concomitantly issued from PGH 2 . This is true for PGE 2 which potentiates platelet aggregation at low concentrations through lowering cyclic AMP (cAMP) in response to the PGE 2 receptor type 3 (EP3) coupled with a Gi-protein. However, platelet aggregation will be inhibited by the rise of cAMP due to both the increased concentrations of PGE 2 and PGD 2 [START_REF] Gray | Interactions between prostaglandin E2 and inhibitors of platelet aggregation which act through cyclic AMP[END_REF][START_REF] Mills | Stimulation of human platelet adenylate cyclase by prostaglandin D2[END_REF] acting through EP2 and DP1, respectively, coupled with Gs-proteins [START_REF] Narumiya | Prostanoid receptors: structures, properties, and functions[END_REF]. So, the early stage (less than 1 min) of platelet stimulation will favor their aggregation through the TxA 2 action, and low concentrations of PGE 2 . Later stages will promote non-enzymatic degradation of TxA 2 (half-life evaluated to 30s in physiological media) into the inactive and stable TxB 2 , and the predominance of PGD 2 and higher concentrations of PGE 2 will inhibit platelet aggregation. Moreover, PGE 2 is further chemically dehydrated into inactive PGA 2 (acidic conditions) or PGB 2 (basic conditions) [START_REF] Amin | Simultaneous determination of prostaglandins (PG) E2, A2 and B2 and stability studies of PGE2 in pharmaceutical preparations by ion-pair reversed phase HPLC[END_REF], and PGD 2 into PGJ 2 , a mitogenic metabolite [START_REF] Fukushima | Biological activities and mechanisms of action of PGJ2 and related compounds: an update[END_REF], and further into 15-deoxy-PGJ 2 , a peroxisome proliferating-activator receptor (PPAR) gamma ligand [START_REF] Ide | Activation of nuclear receptors by prostaglandins[END_REF] both PGF 2α and 12-HHT are inactive in platelets [START_REF] Lagarde | Metabolism of fatty acids by platelets and the functions of various metabolites in mediating platelet function[END_REF]. It must be added that the primary prostaglandin formation does not only follow the kinetics of PGH 2 production, because different PGD, E and F synthases have been described [START_REF] Watanabe | Prostaglandin F synthase[END_REF][START_REF] Hara | Prostaglandin E synthases: understanding their pathophysiological roles through mouse genetic models[END_REF], in addition to the spontaneous isomerization of PGH 2 into PGD 2 and E 2 catalyzed by albumin.

In addition to this cyclooxygenation, ArA is substantially oxygenated by 12lipoxygenase (LOX) for production of 12-hydroperoxy-eicosatetraenoic acid (12-HpETE), that is further reduced to 12-hydroxy-eicosatetraenoic acid (12-HETE) by glutathione peroxidase (GPx)-1 [START_REF] Chang | Effects of reduced glutathione on the 12lipoxygenase pathways in rat platelets[END_REF]. Those two molecules are also able to modulate platelet aggregation;

12-HpETE is an activator of both the release of ArA through cPLA 2 and its oxygenation into prostanoids by stimulating the cyclooxygenase activity [START_REF] Calzada | 12(S)-Hydroperoxyeicosatetraenoic acid increases arachidonic acid availability in collagen-primed platelets[END_REF]. In contrast, the accumulation of 12-HETE may inhibit the reactivity of TxA 2 [START_REF] Croset | Inhibition by lipoxygenase products of TXA2like responses of platelets and vascular smooth muscle. 14-Hydroxy from 22:6n-3 is more potent than 12-HETE[END_REF], at the level of its receptor site [START_REF] Fonlupt | 12-HETE inhibits the binding of PGH2/TXA2 receptor ligands in human platelets[END_REF]. The kinetics of 12-LOX is slower than that of COX, but more stable with time, meaning that the early 12-LOX activity might potentiate the TxA 2 -dependent aggregation whereas the later 12-LOX activity might inhibit it, as do PGD 2 and the late PGE 2 . The measurement of the stable 12-HETE at different times will then complete the picture outlined with prostanoids.

A cellular aspect of the endothelium, is worth to be mentioned relating to platelet aggregation. Indeed, an important oxygenation route of ArA in endothelial cells is its conversion into prostacyclin or PGI 2 , a potent inhibitor of platelet aggregation through a Gscoupled IP receptor on platelet membranes. The half-life of PGI 2 is short (around 2min) leading to the hydrated, stable and inactive product 6-oxo-PGF 1α . Importantly, a transcellular metabolism between endothelial cells and platelets has been demonstrated with some PGH 2 of platelet origin being transformed into PGI 2 by endothelial prostacyclin synthase [START_REF] Nowak | Redirection of prostaglandin endoperoxide metabolism at the platelet-vascular interface in man[END_REF], with subsequent slowing down of platelet aggregation. Even more complex, the inhibition of platelet aggregation by PGI 2 -derived endothelial cells may be enhanced by activated lymphocytes that stimulate endothelial cPLA 2 [START_REF] Merhi-Soussi | M echanisms involved in the stimulation of prostacyclin synthesis by human lymphocytes in human umbilical vein endothelial cells[END_REF]. In addition, a substantial part of ArA may be converted into 15-HpETE by the endothelial 15-LOX, and 15-HpETE has been reported to be an inhibitor of prostacyclin synthase [START_REF] Hong | Tranylcypromine and 15-hydroperoxyarachidonate affect arachidonic acid release in addition to inhibition of prostacyclin synthesis in calf aortic endothelial cells[END_REF], although it may potentiate endothelial cyclooxygenase due to its requirement for peroxides, like all cyclooxygenases [START_REF] Lands | Factors regulating the biosynthesis of various prostaglandins[END_REF] [START_REF] Rådmark | Leu kotriene A: stereochemistry and enzymatic conversion to leukotriene B4[END_REF]. These structural considerations are crucial for the biological activity of LTB 4 , because the unstable LTA 4 is concurrently hydrolyzed into two isomers, namely 12-epi-LTB 4 (with a 12S hydroxyl instead of 12R in LTB 4 ) and 12-epi-all trans-LTB 4 (with an all trans conjugated triene: 6E,8E,10E), that are both biologically inactive [START_REF] Ford-Hutchinson | Comparative biological activities of synthetic leukotriene B4 and its omega-oxidation products[END_REF]. However, the simultaneous measurement of LTB 4 and its two isomers is needed, as well as that of 5-HETE produced by GPx reduction of a fraction of 5-HpETE before its conversion into LTA 4 . These measurements as a function of time will allow evaluating the pro-inflammatory potential of activated PMNs. Importantly, the metabolism of LTB 4 within PMNs also will modulate that pro-inflammatory potential. Indeed, LTB 4 undergoes omega oxidation with first a Cyp P 450dependent hydroxylation of the methyl terminus, providing 20-OH-LTB 4 , followed by double NAD-dependent oxidation of the primary alcohol into a carboxylic acid, the final product being 20-carboxy-LTB 4 . These downstream omega oxidations are supposed to be slower than LTB 4 generation, and represent a major degradation of LTB 4 , as 20-OH-LTB 4 is partly active and 20-carboxy-LTB 4 is inactive. The need for simultaneous measurement of LTB 4 and its two successive metabolites is obvious for evaluation of the pro-inflammatory phenotype of the cells.

A transcellular cooperation between PMNs 5-LOX and platelet 12-LOX has been described in the formation of a geometric and stereo-isomer of LTB 4 . Its structure is 5S,12S-diOH-eicosa-6E,8Z,10E,14Z-tetraenoic acid [START_REF] Borgeat | Studies on the mechanism of formation of the 5S, 12S-dihydroxy-6,8,10[END_REF], also known as LTBX. It is much less chemotactic than LTB 4 , but has later been reported as an inhibitor of platelet aggregation [START_REF] Croset | Stereospecific inhibition of PGH2-induced platelet aggregation by lipoxygenase products of icosaenoic acids[END_REF],

among several other dihydroxylated derivatives of PUFA, called poxytrins, sharing the E,Z,E conjugated triene geometry [START_REF] Chen | Poxytrins, a class of oxygenated products from polyunsaturated fatty acids, potently inhibit blood platelet aggregation[END_REF]. Then, LTBX measured as a function of time in whole blood will indicate cooperation and will reflect both, decreased pro-inflammatory potential of PMNs and platelet reactivity to aggregating agents. The intermediates 5-and 12-HETEs may also be dehydrogenated by a NAD-dependent dehydrogenase into 5-and 12-oxo-derivatives, respectively [START_REF] Powell | Effects of oxo and dihydro metabolites of 12-hydroxy-5,8,10,14-eicosatetraenoic acid on chemotaxis and cytosolic calcium levels in human neutrophils[END_REF]. This metabolism must not be considered as inactivation process because the products have been described with specific biological activities; in particular 5-oxo-ETE promotes eosinophil chemotaxis through specific receptors [START_REF] Powell | The eosinophil chemoattractant 5-oxo-ETE and the OXE receptor[END_REF]. This demands measurements of oxo-ETEs for gaining a better picture of the lipoxygenase-dependent biological functions.

Although eosinophils represent a minor population of leukocytes, their capacity to make LTA 4 followed by its main conversion into LTC 4 by conjugation of LTA 4 with reduced glutathione, is of great biological relevance [START_REF] Rådmark | Leukotriene A4: enzymatic conversion to leukotriene C4[END_REF]. This biosynthesis is catalyzed by glutathione S-transferase that opens the 5,6-epoxide into 5-OH,6-glutathionyl-7E,9E,11Z,14Zeicosatetraenoic acid (LTC 4 ). LTC 4 is further converted into LTD 4 by removing the gammaglutamyl residue from the glutathionyl moiety, as catalyzed by gamma-Glu transferase. A further modification is the removal of the glycine residue by a dipeptidase, leading to LTE 4 keeping the cysteinyl residue at position 6. Because those three LTs have covalently bound one to three amino-acid residues, they are called peptide-LTs. LTC 4 and LTD 4 have the same biological effects, which are vaso-and broncho-constricting activities. The latter activity is especially important as LTC 4 + LTD 4 are considered the active principle of the so-called slow reacting substance of anaphylaxis (SRS-A) [START_REF] Samuelsson | Leukotrienes and lipoxins: structures, biosynthesis, and biological effects[END_REF]. In contrast, LTE 4 is much less active, and has been assumed as a first degradation product [START_REF] Murphy | Biosynthesis and metabolism of leukotrienes[END_REF]. Again, eosinophil action must be evaluated by time-dependent profiling of the three LTs for a better understanding of their biological roles.

In addition to the specific metabolism of each bioactive oxygenated product reported above, more general pathways are worth to be mentioned. Prostanoids, (except 15-dPGJ 2 )

have in common a hydroxyl group at carbon 15 that is targeted by the endothelial 15prostaglandin dehydrogenase (15-PGDH), an NAD-dependent dehydrogenase of this secondary alcohol. 15-PGDH is known to be especially efficient in pulmonary circulation, allowing the formation of 15-oxo-PGs that lose a great part of their biological activities, meaning that most circulating prostanoids will become inactive after a few pulmonary passages [START_REF] Hansen | 15-Hydroxyprostaglandin dehydrogenase. A review[END_REF]. The 15-oxo-PGs derived from this process are further degraded to the 13,14-dehydro-15-oxo-PGs by NADPH reduction [START_REF] Barrow | Identification of 13,14dihydro-15-oxo-prostaglandin F2 alpha in the circulation during infusions of bradykinin and prostaglandin E2 in man[END_REF]. The simultaneous measurement of these two types of metabolites contributes to a better understanding of the PG-dependent phenotypes.

Also, prostanoids being all free fatty acids, they undergo one or two classical betaoxidation steps, leading to dinor-and tetranor-derivatives [START_REF] Diczfalusy | Identification of metabolites from peroxisomal beta-oxidation of prostaglandins[END_REF]. This latter degradation is likely done on a long term base, because it essentially occurs in liver cell peroxisomes, not in mitochondria [START_REF] Diczfalusy | Beta-oxidation of eicosanoids[END_REF]. This means that late measurements of beta-oxidation products are also relevant.

Finally, mono-oxygenation of ArA by several Cyp P 450 must be considered. ArA may be oxygenated on its methyl terminus to provide 20-HETE, a vasoactive product [START_REF] Kaduce | Spector, 20-Hydroxyeicosatetraenoic acid (20-HETE) metabolism in coronary endothelial cells[END_REF], or to generate epoxides at the expense of each double bond, i.e. 5,6-epoxy-eicosatrienoic acid (EET), 8,9-EET, 11,12-EET and 14,15-EET [START_REF] Capdevila | Cytochrome P450 and the arachidonate cascade[END_REF][START_REF] Oliw | Oxygenation of polyunsaturated fatty acids by cytochrome P450 monooxygenases[END_REF]. The latter epoxides are actively hydrolyzed into the corresponding di-hydroxy-eicosatrienoic acids (diHETrE) such as 5,6-diHETrE by specific epoxide hydrolases. In contrast to vasoactive 20-HETE and the epoxyderivatives, di-HETrEs appear to be relatively inactive [START_REF] Imig | Epoxides and soluble epoxide hydrolase in cardiovascular physiology[END_REF]. The measurement of all the Cyp products and hydrolyzed metabolites as a function of time is relevant to evaluate the metabolic fate.

Other prostanoid and dihomo-prostanoid precursors

Other prostanoid precursors are dihomo-gamma-linolenic acid (DGLA or 20:3n-6), the ArA precursor, and eicosapentaenoic acid (EPA or 20:5n-3), the product of the ArA position isomer 8,11,14,17-eicosatetraenoic acid (20:4n-3), in the biogenesis of PUFA (Fig. 1).

As for ArA, DGLA and EPA must be first released from membrane phospholipids.

According to the specificity of cPLA 2 to preferentially release ArA, a double bond proximal to the ester carbon is generally required. EPA should then be released as efficiently as ArA but DGLA would not. Thus, the latter PUFA would mainly be released through the PLC/DAG lipase cascade [START_REF] Authi | Diacylglycerol lipase activity in human platelet intracellular and surface membranes. Some kinetic properties and fatty acid specificity[END_REF]. This means that the release of DGLA would not be favored in comparison to ArA and EPA. Another important consideration is the level of DGLA and EPA in lipid stores, especially in membrane PLs. According to nutritional data, EPA concentrations in membranes are easily increased in response to marine lipids intake, whereas DGLA is hardly modified even by specific nutritional approaches from gamma-linolenic acid (18:3n-6) as DGLA is easily desaturated to ArA [START_REF] Horrobin | Interactions between n-3 and n-6 essential fatty acids (EFAs) in the regulation of cardiovascular disorders and inflammation[END_REF].

In terms of oxygenation, DGLA and EPA roughly undergo the same routes as ArA through cyclooxygenases, providing prostanoids of series one and three, respectively.

However, thromboxane synthase appears to be highly specific of PGH 2 , meaning that the enzyme produces much less TxA 1 and TxA 3 from PGH 1 and PGH 3 [START_REF] Lagarde | Different utilization of arachidonic and dihomogammalinolenic acids by human platelet prostaglandin synthetase[END_REF][START_REF] Needleman | Manipulation of platelet aggregation by prostaglandins and their fatty acid precursors: pharmacological basis for a therapeutic approach[END_REF]. Also, PGI 1 cannot be produced due to the lack of double bond at position 5. In terms of function, the activity of series one prostanoids is not well documented, except for PGE 1 that has been primarily described as a potent activator of cell adenylyl cyclase [START_REF] Wolfe | Inhibition of platelet energy production and release reaction by PGE1, theophylline and cAMP[END_REF]. Regarding series three, TxA 3 is virtually not active compared to TxA 2 [START_REF] Needleman | Thromboxanes: selective biosynthesis and distinct biological properties[END_REF]. In contrast PGI 3 is as potent as PGI 2 [START_REF] Fischer | Prostaglandin I3 is formed in vivo in man after dietary eicosapentaenoic acid[END_REF]. PGD 3 is as potent as PGD 2 to inhibit platelet aggregation [START_REF] Whitaker | Triene prostaglandins: prostaglandin D3 and icosapentaenoic acid as potential antithrombotic substances[END_REF], but has been reported to be antiinflammatory by inhibiting the leukocyte diapedesis induced by PGD 2 [START_REF] Tull | Omega-3 Ffatty acids and inflammation: novel interactions reveal a new step in neutrophil recruitment[END_REF]. In addition, PGD 3 may be converted into 15dPGJ 3 that induces the secretion of adiponectin as does 15-dPGJ 2 from PGD 2 , which contributes to the anti-inflammatory activity of EPA [START_REF] Lefilslacourtablaise | Bernoud-Hubac, The eicosapentaenoic acid metabolite 15-deoxy-δ(12,14)-prostaglandin J3 increases adiponectin secretion by adipocytes partly via a PPARγ-dependent mechanism[END_REF]. Also, PGE 3 appears less pro-inflammatory than PGE 2 [START_REF] Bagga | Differential effects of prostaglandin derived from omega-6 and omega-3 polyunsaturated fatty acids on COX-2 expression and IL-6 secretion[END_REF]. Overall PGD 3 plus PGE 3 express an antiatherothrombogenic profile compared to PGD 2 plus PGE 2 . The production kinetics of series three mediators is assumed to be similar to those of series two. Then we can expect that fluxolipidomics of series three prostanoids should parallel that of series two. The oxygenation of EPA and the main biological actions of the products have been summarized as well in Figs. 2B and3.

The elongation product of ArA, 7,10,13,16-docosatetraenoic acid (22:4n-6), also called adrenic acid (AdA) because of its first discovery in adrenal cells, is a substrate of cyclooxygenases [START_REF] Vanrollins | Metabolism of 7,10,13,16-docosatetraenoic acid to dihomo-thromboxane, 14-hydroxy-7,10,12-nonadecatrienoic acid and hydroxy fatty acids by human platelets[END_REF][START_REF] Harkewicz | Arachidonate-derived dihomoprostaglandin production observed in endotoxin-stimulated macrophage-like cells[END_REF]. The products are dihomo-prostanoids which seem to be produced similarly to prostanoids from ArA. However, much less is known about the release of AdA from membrane phospholipids, and the biological activity of the products are not known, except for dihomo-PGI 2 and dihomo-TxA 2 that are believed to be less active than their counterparts from ArA [START_REF] Campbell | Synthesis of dihomoprostaglandins from adrenic acid (7,10,13,16-docosatetraenoic acid) by human endothelial cells[END_REF]. Also, its structural characteristics enables AdA to be a fairly good substrate of 12-and 15-LOX to produce 14-and 17-oxygenated derivatives, respectively [START_REF] Sprecher | Metabolism of (n-6) and (n-3) polyunsaturated fatty acids by human platelets[END_REF].

AdA is easily produced from released ArA by only one elongation step, and measurement of its expected oxygenated products might be important for the balance sheet of ArA oxygenation at each time of cell activation.

As far as the 5-LOX pathway is concerned, DGLA will not be converted into classical leukotrienes because it lacks the double bond at carbon 5, but EPA is a fairly good substrate [START_REF] Leitch | Immunologically induced generation of tetraene and pentaene leukotrienes in the peritoneal cavities of menhaden-fed rats[END_REF]. Although the routes of EPA to leukotrienes 5 (LT 5s ), as well as the kinetics of production, are not known to be different from those generating LT 4s from ArA, a fluxolipidomics approach would strengthen the observation that LTB 5 is at least ten fold less potent than LTB 4 as a pro-inflammatory agent [START_REF] Lee | Characterization and biologic properties of 5,12-dihydroxy derivatives of eicosapentaenoic acid, including leukotriene B5 and the double lipoxygenase product[END_REF]. So the production of LTB 5 as a function of time will allow anticipating the global LTB-dependent inflammatory state. This will of course depend on the relative concentrations of the precursors ArA and EPA, in turn depending on the nutritional status of the individual. Regarding the peptide-LTs from EPA, LTC 5 and LTD 5 have been reported with a biological activity around five times less potent than LTC 4 and LTD 4 [START_REF] Wallace | Comparison of the damage-promoting effects of leukotrienes derived from eicosapentaenoic acid and arachidonic acid on the rat stomach[END_REF].

Also, EPA has been described as substrate of Cyp-epoxygenases, normally producing EET from ArA [START_REF] Vanrollins | Synthesis and characterization of cytochrome P-450 epoxygenase metabolites of eicosapentaenoic acid[END_REF]. The biological functions of the EPA products are not well-documented, but they must be taken into considerations in all metabolic fluxes.

Finally, regardless of the ArA pathway, a biologically relevant pathway has been described for EPA. The products are called resolvins (Rv) as they accelerate the resolution of inflammation [START_REF] Serhan | Resolvins: a family of bioactive products of omega-3 fatty acid transformation circuits initiated by aspirin treatment that counter proinflammation signals[END_REF]. At least three resolvins (named RvE 1 , E 2 and E 3 ) are initiated upon acetylation of cyclooxygenase-2 by aspirin. As the active site of the enzyme is blocked for generation of prostanoids, yet this modified enzyme oxygenates carbon 18 of EPA leading the R stereo hydroperoxide [START_REF] Oh | Chiral lipidomics of E-series resolvins: aspirin and the biosynthesis of novel mediators[END_REF]. Subsequent action of 5-LOX will make both the 5S,12R,18R-triOH-EPE (RvE 1 ) and 5S,18R-diOH-EPE or 5S,18R-diHEPE (RvE 2 ). An alternative route will convert the 18R-OOH-EPE into 17S,18R-diHEPE (RvE 3 ). The kinetics for resolvins E production are not known, but the fluxolipidomics approach must obviously be applied to this category of metabolites as well.

Lipoxygenation of other PUFA of relevant concentrations in vivo

Many PUFA of biological interest are not oxygenated into prostanoids through cyclooxygenases, but by lipoxygenases. They have 18, 20 or 22 carbons and at least two double bonds (see Fig. 1).

Linoleic acid (LA, 18:2n-6), the well-known indispensable PUFA as precursor of n-6

or omega-6 PUFA, is not only the precursor of ArA but represents the main PUFA in human blood plasma. It is known as a good substrate of 15-/n-6-LOX, especially in plants [START_REF] Hamberg | Steric analysis of hydroperoxides formed by lipoxygenase oxygenation of linoleic acid[END_REF], to be transformed into 13-OOH-18:2 or 13-hydroperoxy-octadecadienoic acid (13-HpODE). The latter is further reduced into its hydroxyl derivative 13-HODE by GPx in animals, and inhibits blood platelet adhesion to vascular endothelium [START_REF] Buchanan | 13-Hydroxyoctadecadienoic acid is the vessel wall chemorepellant factor, LOX[END_REF]. Also, several reports have mentioned the oxygenation of LA by COX-2 into 9-HODE [START_REF] Hamberg | Stereochemistry in the formation of 9-hydroxy-10,12octadecadienoic acid and 13-hydroxy-9,11-octadecadienoic acid from linoleic acid by fatty acid cyclooxygenase[END_REF][START_REF] Kaduce | Formation of 9-hydroxyoctadecadienoic acid from linoleic acid in endothelial cells[END_REF]. 9-HODE might also derive from non-enzymatic peroxidation of LA; then it would be a mixture of 9(R)-and 9(S)-HODE [START_REF] Lê | HDL enrichedwithoxidizedphospholipids and HDL fromdiabetic patients inhibitplateletfunction[END_REF].

The indispensable PUFA for the n-3 or omega-3 family is alpha-linolenic acid (ALA or 18:3n-3). Its required intake in mammals is lower than that 18:2n-6, it is more and more recommended because of the potential benefits of n-3 PUFA to prevent several pathophysiological situations, both by itself and through its conversion into long-chain n-3

PUFA, although such a conversion is assumed to be low. However, 18:3n-3 hardly accumulates in tissues, suggesting that it is actively converted and/or degraded by betaoxidation [START_REF] Cunnane | New developments in alpha-linolenate metabolism with emphasis on the importance of beta-oxidation and carbon recycling[END_REF]. In addition to be desaturated and elongated into long-chain n-3 PUFA [START_REF] Burdge | Alpha-linolenic acid metabolism in men and women: nutritional and biological implications[END_REF], it may be oxygenated through the 15-/n-6-LOX to make the end-product 13-hydroxy derivative, 13-HOTE, and even some 10,16-dihydroxy derivatives, of which the trans,cis,trans/E,Z,E conjugated trienes have blood platelet anti-aggregatory activity through inhibition of cyclooxygenase [START_REF] Liu | Guichardant, Characteriz ation and biological effects of di-hydroxylated compounds deriving from the lipoxygenation of ALA[END_REF].

These two indispensable PUFA are known for years to compete each other for their conversion into long-chain PUFA derivatives. Nothing is known about a possible competition during their lipoxygenation, then a fluxolipidomics approach would certainly unravel pertinent structures and production kinetics for the oxygenated products. One important analytical issue, that is valid for all lipoxygenase products of PUFA, relates to the stereochemistry of the secondary alcohols in the end-products. It is generally assumed that lipoxygenases, as well as cyclooxygenases, provide (S) products whereas the autoxidation of PUFA yield racemic products in approximately equal amounts of (R) and (S) products. It is expected that the rate of autoxidation products is slower than that for the enzyme-derived products. In addition, the aborted oxygenation of 18:2n-6 and 18:3n-3, for instance, by aspirin-treated/acetylated COX-2, will preferentially produce R products (i.e. 13(R)-HODE and 13(R)-HOTE, respectively) [START_REF] Schneider | Stereospecificity of hydrogen abstraction in the conversion of arachidonic acid to 15R-HETE by aspirin-treated cyclooxygenase-2. Implications for the alignment of substrate in the active site[END_REF]. These (R) and (S) stereoisomers have to be distinguished on the basis of their biological activities as well as the kinetics of their production, which again justifies the fluxolipidomics approach, with chiral separation of the stereoisomers in that case.

The 20 carbon PUFA addressed so far are precursors of prostanoids. An exception is Mead acid (20:3n-9). This PUFA is a marker of the n-6 PUFA deficiencies in mammals, mainly linoleic acid (18:2n-6). In these deficiencies, Mead acid is produced from oleic acid (18:1n-9) by successive desaturation and elongation [START_REF] Lundberg | The significance of cis, cis, cis 5,8,11 eicosatrienoic acid in essential fatty acid deficiency[END_REF]. It may partly replace ArA in membrane phospholipids with the same acyl-chain folding having the first three double bonds at carbons 5, 8, 11 in common. However, 20:3n-9 cannot be converted into prostanoids, because of lack of double bond at carbon 14, but is a good substrate of both 5-and 12-LOX [START_REF] Jakschik | Products derived from 5,8,11-eicosatrienoic acid by the 5-lipoxygenaseleukotriene pathway[END_REF]. LTB 3 and C 3 may be produced exactly as do LTB 4 and C 4 from ArA [START_REF] Hammarström | Conversion of 5,8,11-eicosatrienoic acid to leukotrienes C3 and D3[END_REF], but no data on their biological activities are available, nor on the kinetics of their formation. The conversion of 20:3n-9 by platelet 12-LOX has been described, with PGE 2 mimetic action of the end-product 12-OH-20:3 on platelet aggregation [START_REF] Lagarde | Prostaglandin E2-like activity of 20:3n-9 platelet lipoxygenase end-product[END_REF]. The measurement of these LOX products must be taken into consideration as a possible competing process relating to the production of ArA counterparts.

The 22 carbon PUFA are more prominent molecules, especially docosahexaenoic acid (DHA, 22:6n-3) in the cerebrovascular system [START_REF] Salem | Mechanisms of action of docosahexaenoic acid in the nervous system[END_REF]. For that reason and because of its importance in marine lipids, its oxygenation has been extensively studied. Figs. 2 and 3 also show the main features of DHA oxygenation and actions of the metabolites. DHA is a fairly good substrate of the three classical lipoxygenases, 5-, 12-/omega-9, and 15-/omega-6-LOX.

Through 5-LOX, the end-products 4-and 7-OH-22:6 (4-& 7-HDoHE) have been described [START_REF] Lee | Substrate and regulatory functions of eicosapentaenoic and docosahexaenoic acids for the 5-lipoxygenase pathway. Implications for pulmonary responses[END_REF], but no leukotriene-like molecules have been found. Some PPAR gamma agonist activities have been reported, notably relating to the dehydrogenation product 4-oxo- [START_REF] Serhan | Endogenous pro-resolving and anti-inflammatory lipid mediators: a new pharmacologic genus[END_REF]. PDX belongs to a family of double lipoxygenase products, called poxytrins, sharing the same E,Z,E conjugated triene, reported to inhibit platelet aggregation and cyclooxygenases activities [START_REF] Chen | Poxytrins, a class of oxygenated products from polyunsaturated fatty acids, potently inhibit blood platelet aggregation[END_REF][START_REF] Liu | Guichardant, Characteriz ation and biological effects of di-hydroxylated compounds deriving from the lipoxygenation of ALA[END_REF]. Since its structural and functional characterization, PDX has been shown to inhibit the replication of the influenza virus [START_REF] Morita | The lipid mediator protectin D1 inhibits influenza virus replication and improves severe influenza[END_REF][START_REF] Imai | Role of omega-3 PUFA-derived mediators the protectins in influenza virus infection[END_REF], and to restore the insulin sensitivity in diet-induced obese rodents [START_REF] White | Protectin DX alleviates insulin resistance by activating a myokine-liver glucoregulatory axis[END_REF]. The close isomers protectins D1 and DX have to be discriminated by proper analytical tools as they are not produced through the same pathways and have different biological activities. In addition to protectins, DHA has been reported to be doubly oxygenated into a position isomer of PD1 by 12-LOX in macrophages, 7(R),14(S)-diOH-4Z,8E,10E,12Z,16Z,19Z-22:6, called maresin-1, which shares the biological activity of PD1 [START_REF] Serhan | Maresins: novel macrophage mediators with potent antiinflammatory and proresolving actions[END_REF]. A more recent report describes that human macrophages also produce an isomer called maresin-2 (13(R),14(S)-diOH-4Z, 7Z, 9E, 11E, 16Z, 19Z -22:6) that shares the action of maresin-1 [START_REF] Deng | Maresin biosynthesis and identification of maresin 2, a new anti-inflammatory and pro-resolving mediator from human macrophages[END_REF]. Even more complex tri-hydroxylated derivatives are produced from DHA by the combined action of lipoxygenation, and aborted cyclooxygenation (aspirin-treated COX) as well as Cyp P 450 action [START_REF] Arita | The contributions of aspirin and microbial oxygenase to the biosynthesis of anti-inflammatory resolvins: novel oxygenase products from omega-3 polyunsaturated fatty acids[END_REF]. They are called resolvins D (RvD) as they accelerate the resolution of inflammation as do RvE from EPA [START_REF] Ji | Emerging roles of resolvins in the resolution of inflammation and pain[END_REF]. Most of those DHA metabolites have been found in human plasma, and were altered by omega-3 and aspirin intakes, as shown by some investigators [START_REF] Colas | Identification and signature profiles for pro-resolving and inflammatory lipid mediators in human tissue[END_REF], although others failed to find those metabolites in response to high doses of fish oils [START_REF] Skarke | Bioacti ve products formed in humans from fish oils[END_REF]. Interestingly enough however, some metabolites were increased in the corresponding serum versus plasma (PDX as an example), suggesting the involvement of cells sensitive to blood clotting such as platelets [START_REF] Colas | Identification and signature profiles for pro-resolving and inflammatory lipid mediators in human tissue[END_REF]. These numerous oxygenated products of DHA are obviously generated differently with regard to kinetics and location in the vascular compartment that needs elucidation by a fluxolipidomics approach.

Finally, two other 22 carbon PUFA gained attention, namely 22:5n-3 (DPAn-3), as a prominent PUFA in marine lipids, and 22:5n-6 (DPAn-6) as a marker of n-3/omega-3 PUFA

deficiencies. An early report described their oxygenation in platelets [START_REF] Guichardant | Studies on platelet lipoxygenase specificity towards icosapolyenoic and docosapolyenoic acids[END_REF], but no data were available on their biological activities. More recently DPAn-6 [START_REF] Dangi | Biogenic synthesis, purification, and chemical characterization of anti-inflammatory resolvins derived from docosapentaenoic acid (DPAn-6)[END_REF] and DPAn-3 [START_REF] Dalli | Novel n-3 immunoresolvents: structures and actions[END_REF] oxygenation has been described in more details. Whereas DPAn-3 oxygenated products mimicked their DHA counterparts in a way [START_REF] Dalli | Novel n-3 immunoresolvents: structures and actions[END_REF], the biological activity of DPAn-6 oxygenated metabolites was not clear [START_REF] Dangi | Metabolism and biological production of resolvins derived from docosapentaenoic acid (DPAn-6)[END_REF].

Non-enzymatic oxygenation of PUFA

In addition to the stereochemistry of secondary alcohols derived from the reduction of lipoxygenase products by glutathione peroxidases (see above the previous paragraph), a number of cyclic derivatives have been described from ArA, AdA and DHA, and even from the precursors LA and ALA. The cyclic derivatives, called isoprostanes, neuroprostanes and phytoprostanes, became known as markers of oxidative stress in different compartments [START_REF] Roberts | The biochemistry of the isoprostane, neuroprostane, and isofuranpathways of lipid peroxidation[END_REF]. Moreover, there is a trend to consider some of them as bioactive oxygenated products as well [START_REF] Roy | Non-enzymatic cyclic oxygenated metabolites of omega-3 polyunsaturated fatty acid: bioactive drugs?[END_REF]. Recent reviews can be usefully looked at for further data [START_REF] Milne | II, The isoprostanes-25 years later[END_REF][START_REF] Galano | Nonenzymatic cyclic oxygenated metabolites of adrenic, docosahexaenoic, eicosapentaenoic and α-linolenic acids; bioactivities and potential use as biomarkers[END_REF]. However, the kinetics of their production is not known, and because no enzymes are involved in such a production, the different rates might just depend on the number of double bonds in the precursor PUFA. Nevertheless, these molecules must be taken into consideration as well in a fluxolipidomics approach to get a more complete balance sheet of time-dependent oxygenation of PUFA, especially because their release from storage lipids where they are produced by reactive oxygen species might occur at different rates.

Conclusion and perspectives

The great number of oxygenated PUFA metabolites requires appropriate analytical tools to discriminate them. The different pathways for their release from membrane phospholipids, and subsequent oxygenation by different routes (Fig. 2), as well as their potential competition facing the enzymes demand lipidomics approaches that are now commonly used [START_REF] Astarita | Targeted lipidomic strategies for oxygenated metabolites of polyunsaturated fatty acids[END_REF]. However, due to different kinetics in the formation of the primary metabolites, and their catabolism into inactive products and/or active ones with different profiles, those measurements at one time-point and in one compartment do not properly reflect the phenotype of a biological system. A fluxolipidomics approach is then requested.

The vascular compartment is particularly relevant for those considerations because of the easy exchange of metabolic intermediates between blood and vascular cells that are differently equipped with the enzymes involved.Fig. 3 points out specific functions of some metabolites especially relevant in the blood vessel compartment.

Fig. 2

 2 Fig. 2 Main metabolic pathway originating from some of the major PUFA presented in Fig1.The different colors (light and regular blue for 18:2n-6 and 20:4n-6 & dark (Fig. 2A), regular and light green for 18:3n-3, 20:5n-3 and 22:6n-3 (Fig. 2B), respectively) relate to the different pathways and precursor PUFA.The metabolism of 20:5n-3/EPA is simplified as it is similar to that of 20:4n-6/ArA.Although anandamide and synaptamide are not oxygenated products, but are ethanolamide derivatives of ArA and DHA, respectively, they are mentioned as possible substrates for specific oxygenation, providing LOX products and prostamides.

Fig. 3

 3 Fig. 3 Some specific effects of primary and secondary oxygenated metabolites of PUFA.The examples given point out antagonistic and synergistic effects.The green and red colors mean beneficial and deleterious effects, respectively. The purple color means bimodal effects in

  . Although PGJ 2 and 15-dPGJ 2 have no defined biological activities in blood platelets, together with other metabolites such as TxB2, PGE 2 , PGD 2 , PGA 2 , PGB 2 , PGJ 2 , and 15-dPGJ 2 , they form mixtures of metabolites relating to platelet phenotypes at different times. To get an overall picture of ArAcyclooxygenation in activated platelets, the measurement of PGF 2α (another metabolite of PGH 2 produced by a specific reductase) and of the cleavage products of PGH 2 , namely 12hydroxy-heptadecatrienoic acid (12-HHT) plus malondialdehyde (MDA), is needed, although

  . The relative kinetics of these ArA metabolites are not precisely known, but we may reasonably anticipate that only 15-HpETE is active on the generation of PGI 2 , with a decreased formation from PGH 2 of platelet origin. A time-dependent determination of stable metabolites of ArA

	from platelets and from endothelium, namely 6-oxo-PGF 1α and 15-HETE (the reduction
	product of 15-HpETE), appearsto be the only way to properly approach this endothelium-
	platelet antagonism model.
	Other blood cell types are functionally important relating to the oxygenation
	metabolism of ArA. This is the leukocyte compartment, especially polymorphonuclears

(PMNs) and eosinophils that have original oxygenated metabolism of ArA. PMNs have been extensively studied for their production of leukotriene (LT) B 4 (LTB 4 ), a potent chemotactic and pro-inflammatory derivative

[START_REF] Samuelsson | Leukotrienes: mediators of allergic reactions and inflammation[END_REF]

. Its biosynthesis is initiated by 5-LOX which makes first 5-HpETE and second a 5,6-epoxide derivative having a conjugated triene (7E,9E,11Z), called leukotriene A 4 (LTA 4 ). LTA 4 is unstable because of its epoxide next to the conjugated triene. PMNs have an enzyme, called LTA hydrolase or LTB synthase, that specifically adds one molecule of water with the hydroxyl moiety on carbon 12 and the hydrogen making the other hydroxyl at carbon 5 from the opening of the 5,6-epoxide. These additions induce the migration back of the conjugated triene from 7E,9E,11Z to 6Z,8E,10E. The hydrolysis of LTA 4 by LTA hydrolase also is stereospecific with LTB 4 being 5S,12R-diHETE (6Z,8E,10E,14Z)

  22:6[START_REF] Sapieha | 5-Lipoxygenase metabolite 4-HDHA is a mediator of the antiangiogenic effect of ω-3 polyunsaturated fatty acids[END_REF]. Platelet 12-LOX converts DHA into the end-products 11-and 14-OH-22:6 (11-& 14-HDoHE), with the second one being more prominent[START_REF] Aveldaño | Synthesis of hydroxy fatty acids from 4, 7, 10, 13, 16, 19-[1-14C] docosahexaenoic acid by human platelets[END_REF], and both compounds inhibit thromboxane-induced platelet aggregation. Interestingly, 14-OH-22:6 is significantly more potent than 12-HETE[START_REF] Croset | Inhibition by lipoxygenase products of TXA2like responses of platelets and vascular smooth muscle. 14-Hydroxy from 22:6n-3 is more potent than 12-HETE[END_REF]. 15-/omega-6 LOX also converts DHA into the end-product 17-

	OH-22:6 with a possible further conversion into 10(S),17(S)-diOH-4Z,7Z,11E,13Z,15E,19Z-
	22:6 in a double lipoxygenation process [85]. This product has been named protectin DX
	(PDX)	to	differentiate	it	from	protectin	D1	(PD1,	10(R),17(S)-diOH-
	4Z,7Z,11E,13E,15Z,19Z-22:6) previously described as a potent inhibitor of
	inflammation

Acknowledgements

The authors thank the support of Inserm, Inra and INSA-Lyon.


Lhouari Nourine

Jean Marc Petit

Dualization on partially ordered sets: Preliminary Results

The dualization problem on arbitrary posets is a crucial step in many applications in logics, databases, artificial intelligence and pattern mining. The objective of this paper is to study reductions of the dualization problem on arbitrary posets to the dualization problem on boolean lattices, for which output quasi-polynomial time algorithms exist. We introduce convex embedding and poset reflection as key notions to characterize such reductions. As a consequence, we identify posets, which are not boolean lattices, for which the dualization problem remains quasi-polynomial and propose a classification of posets with respect to dualization. As far as we know, this is the first contribution to explicit non-trivial reductions for studying the hardness of dualization problems on arbitrary posets.

Introduction

The dualization problem in arbitrary finite 3 partially ordered sets (poset for short), is a crucial step in many applications in logics, databases, artificial intelligence and pattern mining and has been intensively studied for years [START_REF] Eiter | Identifying the minimal transversals of a hypergraph and related problems[END_REF][START_REF] Fredman | On the complexity of dualization of monotone disjunctive normal forms[END_REF][START_REF] Eiter | New results on monotone dualization and generating hypergraph transversals[END_REF]. The dualization problem can be very di cult and the decision problem associated to dualization is still open, even for lattices. Only a few results exist, mainly dualization is quasi-polynomial whenever (P, ) is isomorphic to a powerset ordered under set inclusion (or boolean lattice) [START_REF] Fredman | On the complexity of dualization of monotone disjunctive normal forms[END_REF], which corresponds to the enumeration of minimal transversal of hypergraph.

The dualization problem on hypergraphs has been studied by many researchers, among which we quote [START_REF] Eiter | Identifying the minimal transversals of a hypergraph and related problems[END_REF][START_REF] Fredman | On the complexity of dualization of monotone disjunctive normal forms[END_REF] while only a few results exist on dualization on other posets [START_REF] Elbassioni | Algorithms for dualization over products of partially ordered sets[END_REF]. Recently Kante et al [START_REF] Kanté | On the enumeration of minimal dominating sets and related notions[END_REF] have shown that the enumeration of minimal transversal of an hypergraph is equivalent to the enumeration of minimal dominating sets of a cobipartite graph. Interestingly, this result brings the dualization problem to the large graph theory community. Some theoretical frameworks for pattern mining have studied dualization, for instance [START_REF] Mannila | Levelwise search and borders of theories in knowledge discovery[END_REF][START_REF] Gunopulos | Discovering all most specific sentences[END_REF][START_REF] Nourine | Extending Set-Based Dualization: Application to Pattern Mining[END_REF]. In [START_REF] Nourine | Extending Set-Based Dualization: Application to Pattern Mining[END_REF], we introduced the idea of weak representations as sets for pattern mining problems and showed how the frequent rigid sequences mining problem benefits from such representation. The embryo of a reduction for the dualization problem on arbitrary posets was present but was clearly implicit in [START_REF] Nourine | Extending Set-Based Dualization: Application to Pattern Mining[END_REF].

To measure the complexity of enumeration algorithms, we always refer to the complexity in the size of the input and the size of the output, see [START_REF] Elbassioni | Incremental algorithms for enumerating extremal solutions of monotone systems of submodular inequality and their applications[END_REF] for details.

The objective of this paper is to study reductions of the dualization problem on arbitrary posets to the dualization problem on boolean lattices. On posets, the dualization problem can be stated as follows: DualizeOnPoset Input: A representation of a poset (P, ), B + an antichain of P .

Output: B such that (B + , B ) are dual sets 4 in P .

Let us consider the particular instance of this problem: DualizeOnSet Input: A finite set E, B + an antichain of P(E) (the powerset of E).

Output: B such that (B + , B ) are dual sets in P(E).

As already mentioned, the complexity of DualizeOnSet is known to be quasi-polynomial while the complexity of DualizeOnPoset is still open in most posets (for example, lattice) [START_REF] Elbassioni | Algorithms for dualization over products of partially ordered sets[END_REF]. In this setting, we are interested in studying the reduction from DualizeOnPoset to DualizeOnSet, i.e. under which conditions DualizeOnSet is at least as hard as DualizeOnPoset. Notice that reductions for the hardness of enumeration problems are not well established as for decision problems. In this paper, we consider only polynomial time reduction as explained in Figure 1 which is inspired from classical polynomial reduction of decision problems.

Contribution on dualization : We introduce convex embedding and poset reflection as key notions to characterize such reductions. As a consequence, we identify posets, which are not boolean lattices, for which the dualization problem remains quasi-polynomial and propose a classification of posets with respect to dualization.

Preliminaries

We briefly recall definitions on partial orders, embeddings and borders [START_REF] Davey | Introduction to Lattices and Order[END_REF][START_REF] Nourine | Extending Set-Based Dualization: Application to Pattern Mining[END_REF].

A partial order is a binary relation  over a set P which is reflexive, antisymmetric, and transitive. Let x, y be elements of P , if x  y or y  x, then x and y are comparable, otherwise they are incomparable. A partial order under which every pair of elements is comparable is called a chain. A subset of a poset in which no two distinct elements are comparable is called an antichain. We say that y covers x if whenever x  z  y then z = x or y = z; we denote by the covering relation. For S ✓ P , # S (resp. " S) is the downward (resp. upward) closed set of S under the relation  (i.e. # S is an ideal and " S a filter of (P, )). In case of ambiguity, # S (resp. " S) will be denoted by #  S (resp. "  S). A subset S ✓ P is convex in P if for all x, y, z 2 P , x, y 2 S and x  z  y implies z 2 S. We denote by Max  (S) (resp. Min  (S)) denotes the maximal (resp. minimal) elements of S with respect to . When  is clear from context, (P, ) (resp. Max  (S) and Min  (S)) will be denoted by P (resp. Max (S), Min(S)).

Let (P,  P ) and (Q,  Q ) be posets and f : P ! Q a mapping (total function). f is an embedding if for all x, y 2 P , x  P y i↵ f (x)  Q f (y). The mapping f is an isomorphism if f is a bijective embedding. In this case P and Q are said to be isomorphic. f is a convex embedding if f is an embedding and f (P ) is convex in (Q,  Q ). Whenever f is injective but not surjective, there exists another mapping g : f (P ) ! P such that g f = Id, the identity function. A reflection of a poset (P, ) is a poset (P,  0 ) on the same ground set P such that for all x, y 2 P , x  0 y ) x  y.

Two antichains (B + , B ) of P are said to be dual if # B + [ " B = P and # B + \ " B = ;. The relationship between these dual sets is known as the dualization, i.e. given B + , compute B (or inversely). In the sequel, (B + , B ) will be referred to as a "border".

Let f : P ! Q be a mapping and (B + , B ) a border in P . The border

(E + , E ) in Q is an extension of (B + , B ) with respect to f , if f (B + ) ✓ E + and f (B ) ✓ E . The extension (E + , E ) is said to be a polynomial extension of (B + , B ) if |E + | + |E | is polynomial in |B + | + |B |.
The intuition of the reduction of enumeration problems used in this paper is based on finding a mapping between posets such that borders are polynomial preserved, i.e. every border has a polynomial extension.

In the rest of this paper, we assume that a poset is given by an implicit representation L and we shall denote by (L ⇤ , ) the poset defined by L. Clearly, the size of L ⇤ may be exponential in the size of the representation L. For instance, the free monoid ⌃ ⇤ ordered by sub word is implicitly defined by the alphabet ⌃, and a lattice is implicitly defined by its poset of (join and meet) irreducible elements [START_REF] Ganter | Formal Concept Analysis[END_REF].

Classification of posets with respect to dualization

In this section we describe two properties of posets that lead us to have polynomial time reductions to DualizeOnSet. First we show that a convex embedding from a poset (L ⇤ , ) to P(E) for some set E is su cient to re-use algorithms of DualizeOnSet. Second, we show that the convex embedding is not a necessary condition and introduce the reflection of a poset (L ⇤ , ) to obtain a new poset (L ⇤ , 0 ) in which there is a convex embedding. Indeed, a reflection of a poset (L ⇤ , ) corresponds to an embedding which preserves incomparabilities (or antichains), even if some comparabilities could be lost. The previous two embeddings introduce extra-elements to the dualization. Whenever these extra-elements are bounded by a polynomial, the dualization can be polynomial reduced to DualizeOnSet. To do so, we ask the following questions:

Given a poset of patterns (L ⇤ , ), -Does there exist a convex embedding of (L ⇤ , ) into (P(E), ✓) for some finite set E? If not, -Does there exist a reflection (L ⇤ , 0 ) of (L ⇤ , ) such that there exists a convex embedding of (L ⇤ , 0 ) into (P(E), ✓) for some finite set E? These two questions and their associated computational costs allow to come up with new classes of posets with respect to dualization. Figure 2 gives an illustration with a diagram where posets and borders are placed side by side.

Convex embedding

First, let us recall that any poset has an embedding into a boolean lattice. Proposition 1. [START_REF] Davey | Introduction to Lattices and Order[END_REF] For any poset (L ⇤ , ), there exists an embedding from (L ⇤ , ) to (P(E), ✓), for some finite set E.

It follows that any poset has a set representation but obviously the dualization on (L ⇤ , ) may be much more complex than the dualization on (P(E), ✓) [START_REF] Nourine | Extending Set-Based Dualization: Application to Pattern Mining[END_REF]. We define the RAS class as follows:

Definition 1. (L ⇤ , ) 2 RAS i↵ (L ⇤ ,
) and (P(E), ✓) are isomorphic, for some finite set E. This class of posets gathers together many patterns such as frequent itemsets (FIM) [START_REF] Agrawal | Mining associations between sets of items in massive databases[END_REF], functional dependencies (FD) [START_REF] Mannila | Algorithms for inferring functional dependencies from relations[END_REF], inclusion dependencies (IND) [START_REF] De Marchi | Zigzag: a new algorithm for mining large inclusion dependencies in databases[END_REF]. This class is known as the representation as sets class of pattern mining problems defined in [START_REF] Mannila | Levelwise search and borders of theories in knowledge discovery[END_REF].

(L ⇤ , ) (L ⇤ , 0 ) (P(E), ✓) (B + , B ) (C + , C ) (E + , E )
Nevertheless, requirements to be in RAS are restrictive, since the poset must be isomorphic to a boolean lattice, and then its size has to be equal to 2 n where n = |E|. Now we will relax the bijective constraint of RAS but we keep the convexity property on the set representation. Hence, we extend RAS to a new class, called X RAS, for conveX RAS. Definition 2. (L ⇤ , ) 2 X RAS i↵ there exists a convex embedding from (L ⇤ , ) to (P(E), ✓), for some finite set E.

The idea is still to require an isomorphism but just between the poset of patterns and some subset of P(E), instead of the entire set P(E) (see Figure 3). Note also that f is injective since f is an embedding. The following proposition points out a simple yet important characterization of X RAS problems.

Proposition 2. (L ⇤ , ) 2 X RAS i↵ (L ⇤ , ) is isomorphic to (P(E)\(# B + 0 [ " B 0 ), ✓) for some antichains B + 0 ✓ P(E) and B 0 ✓ P(E).
Proof. Let f be a convex embedding from (L ⇤ , ) to (P(E), ✓) and

F = f (L ⇤ ). Let us consider F + = Min(F) and F = Max(F) two antichains of F. More- over, let B + 0 = Max({X 2 P(E)|X ⇢ Y, Y 2 F + }) and B 0 = Min(P(E) \ (F[ # B + 0 )). Let X 2 P(E). Then either X 2# B + 0 , or X 2" B 0 or X 2 P(E) \ (# B + 0 [ " B 0 ).
In the latter case, there exists

Y 1 2 F + , Y 2 2 F such that Y 1 ✓ X ✓ Y 2 . Since F is convex, X 2 F and the result follows.
The other direction holds since

P(E) \ (# B + 0 [ " B 0 ) is a convex set of P(E). u t
Figure 3 gives an illustration of the proposition 2. Note that the sets B + 0 and B 0 can be exponential in the size of E. The next definition introduces e cient problems of X RAS, called EX RAS.

(L ⇤ , ) 2 EX RAS if (L ⇤ , ) 2 X RAS and |B + 0 [ B 0 | is poly- nomial in |E|.
The following proposition points out that a polynomial extension of any border of (L ⇤ , ) exists if (L ⇤ , ) 2 EX RAS. Proof. It su ces to notice that (B + , B ) is a border of (L ⇤ , ) i↵ (f (B + ), f(B )) is a border of (P(E)\(#

B + 0 [ " B 0 ), ✓) since (L ⇤ , ) is isomorphic to (P(E)\(# B + 0 [ " B 0 ), ✓). u t

Polynomial reflection of posets

We now consider posets that are not in X RAS. Our idea is to transform the initial poset to a new poset over the same ground set, in order to get a convex embedding. As a consequence, two natural question arise:

(1) For a given poset (L ⇤ , ), does there exist a "polynomial reflection" (L ⇤ , 0 ) such that (L ⇤ , 0 ) belongs to EX RAS?

(2) How to quantify the "lost comparabilities" induced by a reflection?

In the sequel, we study poset reflection to give answers to the previous questions. Since the reflection of a poset induces the lost of some comparabilities in the original poset, we have to recover them e ciently.

Before that, we consider di↵erent examples of posets over sequences.

Examples with di↵erent posets of sequences Let us consider sequences with or without wildcard (denoted ?), see e.g. [START_REF] Arimura | Polynomial-delay and polynomial-space algorithms for mining closed sequences, graphs, and pictures in accessible set systems[END_REF]. Let ⌃ be an alphabet. A sequence is an element of ⌃ ⇤ and a rigid sequence an element of (⌃ [ {?}) ⇤ of the form P = P .n] 2 ⌃ ⇤ . We have:

-P  s Q if there exists integers i 1 < . . . < i m in [1..n] such that P [j] = Q[i j ] for all j 2 [1..m]. -P  f Q if P  s Q and i j = i j+1 1 for all j 2 [1..m 1] -P  p Q if P  f Q and i m = m.
These di↵erent posets are illustrated in Figure 4 on a simple example. In Figure 4, let us consider the set {aa, ab} for the di↵erent posets. Its dual set is equal to {ba, aab, aaa} for (a) and (b) and {b, aab, aaa, aba} for (c).

Second, we consider two posets for rigid sequences, one similar to the factor poset and another one to the prefix poset, denoted

(⌃ ⇤ R , v) and (⌃ ⇤ R , v 1 ). Let P [1..m], Q[1..n] 2 ⌃ ⇤ R .
We have:

-P v Q if there exists p 2 [1.
.n] such that for every i 2 [1..m], either

P [i] = Q[p + i 1] or P [i] = ? -P v 1 Q if for every i 2 [1..m], either P [i] = Q[i] or P [i] = ?
These two posets are illustrated in Figure 5, where the poset (b) suggests the existence of hidden hypercubes in the poset (a). Now, we claim that the posets (⌃ ⇤ ,  s ), (⌃ ⇤ ,  f ), (⌃ ⇤ ,  p ) and (⌃ ⇤ R , v) do not have any convex embedding. Consider again the example given in Figure 4 and the two following sets: A = {a, b, ab, ba} and A 0 = {a, aa, aaa}. -A is convex in (⌃ ⇤ ,  s ) (Figure 4.(a)) but its image by any embedding cannot be convex in (P(E), ✓) since (P(E), ✓) is a lattice. The same reasoning applies for (⌃ ⇤ ,  f ) and (⌃ ⇤ R , v). -A 0 is convex in (⌃ ⇤ ,  p ) but its image by any embedding cannot be convex in (P(E), ✓) since P(E) cannot contain a convex set which is a chain of length 3.

However, Figure 5 also shows a reflection that leads to a convex embedding. Consider (⌃ n R , v 1 ). Let f : ⌃ n R \ {✏} ! P(E) be an embedding, for some finite set E [START_REF] Arimura | Polynomial-delay and polynomial-space algorithms for mining closed sequences, graphs, and pictures in accessible set systems[END_REF][START_REF] Nourine | Extending Set-Based Dualization: Application to Pattern Mining[END_REF]: f associates to each letter of a sequence a couple (indice, letter). These examples point out that we have to study poset reflection to be able to obtain some convex embedding.

Reaching convexity by poset reflection

As shown in previous examples involving sequences, whenever possible, we have now to quantify the lost comparabilities induced by a poset reflection.

For a given element of a poset, we define its successors and its predecessors induced by a poset reflection. Definition 4. Let (P,  0 ) a reflection of a poset (P, ) and x 2 P . The lost predecessors of x in the reflection of (P, ) to (P,  0 ), denoted by LostPred(x), are defined by: LostPred(x) = Max  0 {y 2 P |y  x, y 6 < 0 x}. Similarly, the lost successors are defined by: LostSucc(x) = Min  0 {y 2 P |x  y, x 6 < 0 y}.

By extension, we note LostPred(X) =

S x2X LostPred(x) (resp. LostSucc(X)) for X ✓ P . Example 1. Let us consider the reflection (⌃ n R , v 1 ) of (⌃ n R , v) [8]. Let S 2 ⌃ n R . We have LostPred(S) = {S[i..|S|] | 1  i  |S|, S[i] 6 = ?} and LostSucc(S) = {x ? . . . ? | {z } i S | 0  i  n |S| 1, x 2 ⌃}.
For instance with n = 5, LostPred(a?ba) = {a?ba, ba, a} and LostSucc(ba) = {aba, bba, a ? ba, b ? ba, a ? ?ba, b ? ?ba}.

As shown in the following lemma, we can recover the initial poset from any reduced poset with LostPred and LostSucc. Lemma 1. Let x 2 P and (P,  0 ) a reflection of (P, ). Then:

1. #  x =#  0 LostPred(x) and 2. " x ="  0 LostSucc(x).
Proof.

(1) Let y 2#  x. We have either y  0 x or y 6 < 0 x. If y  0 x, then y 2#  0 LostPred(x) since x 2 LostPred(x). If y 6 < 0 x, then there exists z 2 P such that y  0 z, z 2 LostPred(x), i.e. y 2#  0 LostPred(x). The same reasoning applies for (2).

u t Some remarks have to be made: First, for any poset, there always exists a reflection that has a convex embedding into a boolean lattice. It su ces to take a reflection which is an antichain, i.e. that deletes all comparabilities. In this case, the number of lost comparabilities can be exponential in the size of the description of the poset. Second, we would like to be able to recover lost comparabilities in polynomial time. This is formalized with the notion of polyreflection as follows. Definition 5. (L ⇤ , 0 ) is a poly-reflection of (L ⇤ , ) if (L ⇤ , 0 ) is a reflection of (L ⇤ , ) and for all x 2 L ⇤ , LostPred(x) and LostSucc(x) are computable in polynomial time in the size of the description L.

Example 2. Continuing the previous example, for all S 2 ⌃ n R , LostPred(S) is polynomial in n and for all s v S, there exists s 0 2 LostPred(S) such that s v 1 s 0 . Therefore, (⌃ n R , v 1 ) is a poly-reflection of (⌃ n R , v).

Now we show the relationship between borders in a poset and its reflection. For a given border on the initial poset, we define its extension in the reduced poset to take into account lost comparabilities. Definition 6. Let (L ⇤ , 0 ) be a poly-reflection of (L ⇤ , ) and (B + , B ) a border of (L ⇤ , ). The extension of (B + , B ) in (L ⇤ , 0 ), denoted by (ext(B + ), ext(B )), is defined by:

ext(B + ) = Max  0 {LostPred(x) | x 2 B + } ext(B ) = Min  0 {LostSucc(x)|x 2 B }.
The "preservation" of borders can now be formally stated.

Proposition 4. Let (L ⇤ , 0 ) be a poly-reflection of (L ⇤ , ) and (B + , B ) a border of (L ⇤ , ). Then (ext(B + ), ext(B )) is a polynomial extension of (B + , B ). (1) Any reflection preserves all incomparabilities and x 2 LostPred(x) (resp x 2 LostSucc(x)) for all x 2 L ⇤ . Then B + ✓ ext(B + ) and B ✓ ext(B ). By definition, ext(B + ) and ext(B ) are antichains in (L ⇤ , 0 ). By Lemma 1, the result follows.

(2

) |ext(B + )| + |ext(B )| is polynomial in |B + | + |B | since (L ⇤ , 0
) is a polyreflection of (L ⇤ , ) since computing LostPred(x) and LostSucc(x) can be done in polynomial time in the size of the description of L.

u t

The notion of poly-reflection allows to define the last class of posets, called EWRAS, meaning E cient weak representation as sets. EWRAS is the more general class ensuring the existence of quasi-polynomial algorithms. It combines both poly-reflection of posets and EX RAS. Definition 7. (L ⇤ , ) 2 EWRAS i↵ there exists a poly-reflection (L ⇤ , 0 ) of (L ⇤ , ) such that (L ⇤ , 0 ) 2 EX RAS.

Then, this definition means that if some comparabilities can be forgottenup to a polynomial cost to recover them -to get a new poset satisfying the condition of EX RAS, then the dualization problem on the initial poset can be reduced to DualizationOnSet. The main result concerning the EWRAS class is now given: Theorem 1. Let (L ⇤ , ) 2 EWRAS. Assume that (L ⇤ , 0 ) is a poly-reflection of (L ⇤ , ) such that (L ⇤ , 0 ) belongs to EX RAS, i.e. (L ⇤ , 0 ) isomorphic to P(E) \ (B + 0 [ B 0 ). Then, for any border (B + , B ) of (L ⇤ , ):

-(B + 0 [ f (ext(B + )), B 0 [ f (ext(B ))) is a border in (P(E), ✓), -(B + 0 [ f (ext(B + )), B 0 [ f (ext(B ))
) is a polynomial extension of (B + , B ), The following corollary gives the relationship between all the classes introduced so far.

Corollary 1. Let (L ⇤ , 0 ) be a poly-reflection of (L ⇤ , ) such that (L ⇤ , 0 ) belongs to X RAS, i.e. (L ⇤ , 0 ) isomorphic to P(E) \ (B + 0 [ B 0 ). We have:

1. (L ⇤ , ) 2 RAS if (L ⇤ , ) = (L ⇤ , 0 ) and B + 0 = B 0 = ;. 2. (L ⇤ , ) 2 X RAS if (L ⇤ , ) = (L ⇤ , 0 ). 3. (L ⇤ , ) 2 EX RAS if (L ⇤ , ) = (L ⇤ , 0
) and the size of B + 0 [ B 0 is polynomial in the size of the description of (L ⇤ , ). 4. (L ⇤ , ) 2 EWRAS if the size of B + 0 [ B 0 is polynomial in the size of the description of (L ⇤ , ).

DualizeOnSeq is equivalent to DualizeOnSet

Recall that we consider rigid sequences only. The dualization problem can be stated as follows:

DualizeOnSeq Input: ⌃ a totally ordered alphabet with a minimal element ?, n a positive integer, B + a positive border of ⌃ n R . output: B such that (B + , B ) is a border of ⌃ n R . We have already showed that DualizeOnSeq is at least as hard as Dual-izeOnSet in [START_REF] Nourine | Extending Set-Based Dualization: Application to Pattern Mining[END_REF]. In the sequel, we point out that DualizeOnSet is at least as hard as DualizeOnSeq, and therefore the two problems are polynomially equivalent. Indeed, we show that DualizeOnSet is a particular case of Dual-izeOnSeq.

Let ⌃ = {1, 2, ..., n, ?} be an ordered alphabet (i.e. ? < 1 < 2... < n and S 2 ⌃ n . The sequence S is said to be an ordered sequence if for any i, j 2 [1..n] such that i < j, S[i] 6 = ? and S[j] 6 = ? we have S[j] S[i] = j i. We denote ⌃ n O ✓ ⌃ n the set of all ordered sequences of size at most n. For example, the sequence 2 ? ?5 is an ordered sequence but 2 ? 5 is not.

The following lemma characterizes ordered sequences. Let V = {1, ..., n} be a set. We define the mapping f : P(V ) ! ⌃ n such that for any E 2 P(V ), f (E) = S with S[i] = i if i 2 E and S[i] = ? otherwise. Without loss of generality, we delete the symbols ? that are prefix or su x of f (E). Note that f (E)[i] = ? means that i / 2 E. For example f ({2, 5}) = 2 ? ?5 and f ({}) is the empty sequence. Proposition 5. Let V = {1, ..., n} be a set. Then the mapping f is a convex embedding of P(V ) into ⌃ n

. Moreover f (P(V )) = ⌃ n O .

Proof. Let P, Q be two sequences that are images of two sets A ⇢ B ✓ V , i.e. f (A) = P and f (B) = Q. Clearly f (A) @ f (B). Now suppose there is a sequence S such that P @ S @ Q.

For every i 6 = j 2 [1.

.n] we have either S .n]} is clearly defined. Moreover f (C) = S and A ⇢ C ⇢ B, since for any x 2 ⌃, x 6 @ ?, but ? @ x.

We have f (P(V )) = ⌃ n O by construction. u t Theorem 2. DualizeOnSeq and DualizeOnSet are polynomially equivalent.

Proof. We have shown that DualizeOnSeq is polynomially reducible to Du-alizeOnSet [START_REF] Nourine | Extending Set-Based Dualization: Application to Pattern Mining[END_REF]. In Proposition 5, we have shown the existence of a convex embedding from P(V ) into ⌃ n . Moreover we have shown that B + 0 = ; and according to Lemma 2 the size of B 0 is bounded by O(n 3 ). Thus DualizeOnSet is polynomially reducible to DualizeOnSeq. u t

We have shown that the dualization on rigid sequences with wildcard is equivalent to the dualization on set, i.e. enumerating minimal transversals of a given hypergraph.

Fig. 1 .

 1 Fig. 1. Reduction from DualizeOnPoset to DualizeOnSet

Fig. 2 .

 2 Fig. 2. Reflection and convex embedding

Fig. 3 .

 3 Fig. 3. The class X RAS

Proposition 3 .

 3 Let (L ⇤ , ) 2 EX RAS and f : L ⇤ ! P(E) a convex embedding, for some finite set E. Then for any border (B + , B ) of (L ⇤ , ), (Max(B + 0 [f (B + )), Min(B 0 [f (B ))) is a polynomial extension of (B + , B ) in (P(E), ✓).

[ 1 ]

 1 • • • P [m] such that P [1] 6 = ? and P [m] 6 = ?. Let ⌃ ⇤ R be the set of rigid sequences and ⌃ ⇤ the set of sequences. We denote by ⌃ n the set of all sequences in ⌃ ⇤ of size at most n. Di↵erent partial orders over ⌃ ⇤ R and ⌃ ⇤ exist. Let us first consider sub-word (resp. factor and prefix) posets over ⌃ ⇤ , denoted (⌃ ⇤ ,  s ) (resp. (⌃ ⇤ ,  f ) and (⌃ ⇤ ,  p )). Let P [1..m], Q[1.

Fig. 4 .

 4 Fig. 4. (a) The sub word poset induced by the word w=aaba on ⌃ = {a, b}; (b) the factor poset which is a reflection of (a); and (c) the prefix poset which is a reflection of posets (b) and (a).

Fig. 5 .

 5 Fig. 5. (a) The factor poset of rigid sequences induced by the word w=aaba on ⌃ = {a, b}; (b) the prefix poset of rigid sequences which is a reflection of posets (a).

  For instance, let ab and ba be two patterns. Then f (ab) = {(1, a), (2, b)} and f (ba) = {(1, b), (2, a)}. It is easy to verify that f (⌃ n R \{✏}) is convex in (P(E), ✓) [8]. Let us again consider A = {a, b, ab, ba}: we only have a v 1 ab, b v 1 ba, i.e. two comparabilities (a 6 v 1 ba, b 6 v 1 ab) are lost, allowing to reach the convexity constraint.

Proof.

  We have to show: 1. (ext(B + ), ext(B )) is a border of (L ⇤ , 0 ) with B + ✓ ext(B + ) and B ✓ ext(B ), 2. |ext(B + )| + |ext(B )| is polynomial in |B + | + |B |.

Example 3 .

 3 Continuing previous examples, we have (⌃ ⇤ R , v 1 ) is a poly-reflection of (⌃ ⇤ R , v) and (⌃ ⇤ R , v 1 ) belongs to EX RAS. Then, (⌃ ⇤ R , v) belongs to EWRAS.

Lemma 2 .

 2 Let ⌃ = {1, 2, ..., n, ?} be an ordered alphabet and S 2 ⌃ n . Then S 2 ⌃ n O i↵ S does not contain a subsequence of the form i ? . . . ? | {z } k j with either i < j and k 6 = j i 1, or i j with k 2 [0..n 2]. Consider the set B 0 = {i ⇤ k j | i j, k 2 [0..n 2]}[ {i ⇤ k j | i < j, k 2 [0..n 2], k 6 = j i 1}. For example for ⌃ = {1, 2, 3, ⇤} we have B 0 = {11, 1 ⇤ 1, 22, 2 ⇤ 2, 33, 3 ⇤ 3, 21, 2 ⇤ 1, 31, 3 ⇤ 1, 32, 3 ⇤ 2} [ {13}. Lemma 3. ⌃ n \ " B 0 = ⌃ n O .

[i] 6 =

 6 S[j] or S[i] = S[j] = ?, by definition of the embedding f . Then the set C = {x 2 V | S[i] = x, i 2 [1.

It also works for infinite partially ordered sets that are well ordered, i.e. all antichains are finite.

Dual sets are also known as blocker and anti-blocker or positive and negative borders