Amel Ghouila
email: amel.ghouila@lirmm.fr

Nicolas Terrapon
email: terrapon@lirmm.fr

Olivier Gascuel
email: gascuel@lirmm.fr

Fatma Z Guerfali
email: fzguerfali@yahoo.fr

Dhafer Laouini
email: dhafer_l@yahoo.ca

Eric Marechal
email: eric.marechal@cea.fr

Laurent Brehelin
email: brehelin@lirmm.fr

Eric Maréchal

Laurent Bréhélin

EuPathDomains: The Divergent Domain Database for Eukaryotic Pathogens

Keywords: Pathogens, protein domains, functional annotations, Pfam, HMMs, database

à 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

Pathogenic eukaryotes belong to several distinct phylogenetic lineages causing a wide variety of host infections. They have evolved the ability to infect a range of hosts, including humans, animals and plants [1]. Despite the availability of the complete genome of many of these organisms, their exact infection mechanisms and invasion strategies, as well as the function of more than 50% of their proteins, are still under investigation. This is mainly due to their high phylogenetic distance from the classical model organisms, as well as to their evolutionary mechanisms that are quite different from those envisioned in classical models of evolution due to the co-evolution of host and pathogens and the development of both systems in an ongoing process [START_REF] Kreier | Infection, resistance and immunity[END_REF]. In fact, parasites have evolved a variety of mechanisms to evade host immune recognition and elimination. Such evolution is a direct consequence of the fact that they live at the expense of, and are dependent on, host tissues for long periods during their life cycles [START_REF] Ochman | Genes Lost and Genes Found: Evolution of Bacterial Pathogenesis and Symbiosis[END_REF]. This contributed to the development of new gene functions and changes in the parasite's genome repertoire, occurring through gene acquisition and deletion [START_REF] Stefan | book chapter Immune evasion by parsites[END_REF].

Among the relevant annotations that can be attributed to a protein, domains occupy a key position. Protein domains are sequential and structural motifs that are found independently in different proteins and in different combinations and, as such, seem to be functional subunits of proteins above the raw amino acid sequence level [START_REF] Richardson | The anatomy and taxonomy of protein structure[END_REF]. Protein domain composition provides strong clues for the protein function. Indeed, two thirds of mono-domain proteins having the same domain also have the same functions. Likewise, 35% of multidomain proteins having one common domain present similar functions, while this rate increases to 80% when they share two common domains [START_REF] Hegyi | Annotation Transfer for Genomics: Measuring Functional Divergence in Multi-Domain Proteins[END_REF]. Several approaches and databases have been developed to define and identify domains. One of the most widely used domain scheme is the Pfam database [START_REF] Finn | The Pfam protein families database[END_REF], which is a collection of protein domain and families. Each family in Pfam is represented by a multiple sequence alignment and a profile Hidden Markov Model (profile HMM) [START_REF] Durbin | Biological sequence analysis: probabilistic models of proteins and nucleic acids[END_REF]. The Pfam 23.0 release offers a large collection of 10 340 protein domains.

When analyzing a new sequence, each Pfam HMM is used to compute a score measuring the similarity between the sequence and the domain. If the score is above a given threshold provided by Pfam (each domain has a different score threshold), then the presence of the domain can be asserted in the protein. However, applied to divergent proteins, this strategy may miss several domains. This is the case for all eukaryotic pathogens, where no Pfam domains are detected in half or even more of their proteins. While the Pfam domain coverage of the classical model organisms is 73% on average for all organisms (Table 1), this proportion varies for eukaryotic pathogens from 38%, (for Trypanosoma brucei) to 53% (for Plasmodium falciparum). Although this situation may be explained by the existence of genes that are unique to these organisms or specific to a parasitic life style, it is further exacerbated by the high evolutionary distance between these organisms and the other organisms used as model Eukaryotes-such as yeast, worms, arabidopsis, drosophila and human [START_REF] Ward1 | Protein kinases of the human malaria parasite Plasmodium falciparum: the kinome of a divergent eukaryote[END_REF]-, which makes homology detection particularly difficult.

We recently proposed a method named CODD that increases the sensitivity of Pfam domain detection in divergent proteins while controlling the false discovery rate (FDR) of the predictions [START_REF] Terrapon | Detection of new protein domains using co-occurrence: application to Plasmodium falciparum[END_REF]. Our method makes use of the well known tendency of protein domains to appear preferentially with a few other favorite domains in proteins [START_REF] Apic | Domain combinations in archeal, eubacterial and eukayotic proteomes[END_REF]. This enables us to certify the presence of domains below the recommended thresholds, on the basis of the presence of another domain in the same protein. Moreover, a shuffling procedure provides an estimate of the FDR associated with each prediction.

In this paper, we present EuPathDomains, an extended database of known and new protein domains identified by CODD on several major human pathogens (three Leishmania species, three Plasmodium species, Toxoplasma gondii, Cryptospordium parvum, Giardia lamblia and Trypanosoma brucei) selected from EupathDB database [START_REF] Aurrecoechea | EuPathDB: a portal to eukaryotic pathogen databases[END_REF]. In average, EuPathDomains increases the number of domains in a proportion of ~10% in each genome (with an FDR<20%). Several new domains types were discovered, leading to an enrichment of 10% to 16% of the total number of domain families in each genome. Some of these domains are localized in proteins that had no known domain. In addition, these newly predicted domains induce new GO annotations for about 15% of the proteins within each of the studied organisms. EuPathDomains database provides all these predictions along with the already known domains and annotations in a friendly interface that allows easy browsing and querying.

In the following, we briefly describe the studied pathogens. We explain the principle of CODD and the shuffling procedure used to estimate the confidence (FDR) associated with the newly discovered domains. We next present the results achieved on each species, and describe the EuPathDomains database interface. Finally, as a case study, we emphasize the results obtained with the three selected Leishmania species.

Data and Methods

Pathogens included in EuPathDomains

One organism affecting humans, representative of each phylum of the EupathDB 1 database was selected in this study [START_REF] Aurrecoechea | EuPathDB: a portal to eukaryotic pathogen databases[END_REF]. These include L. major that causes leishmaniasis, three apicomplexans -P. falciparum that cause malaria, T. gondii and C. parvum that cause respectively toxoplasmosis and a diarrheal illness called cryptosporidiosis -, T. brucei that causes sleeping sickness, and G. lamblia that causes giardiasis. To allow comparative studies of close species, we also included two additional Leishmania-L. infantum and L. braziliensis-and two Plasmodium-P. vivax and P. yoelli. Leishmania species. Infection by the insect-transmitted Leishmania parasites represents a serious global health problem for which there is no vaccine and few effective but toxic drugs [START_REF] Peacock | Comparative genomic analysis of three Leishmania species that cause diverse human disease[END_REF]. Intramacrophagic protozoan leishmanies are single celled parasites that affect vertebrates including dogs and humans. At least 20 Leishmania species infect humans, and the spectrum of diseases that they cause can be categorized broadly into three types: visceral leishmaniasis, cutaneous leishmaniasis and mucocutaneous leishmaniasis. Three different Leishmania species included in this study, i.e.; L. major, L. infantum and L. braziliensis cause respectively cutaneous, visceral and mucocutanous leishmaniasis. These different Leishmania species contain each approximately 8 000 protein coding genes, more than half of them do not have either GO annotation terms or known protein domains.

Plasmodium species. Plasmodium is a genus of parasitic protists. Infection by these organisms is known as malaria, which is one of the most devastating infectious diseases causing more than 1 million deaths each year worldwide [START_REF] Kooij | A Plasmodium Whole-Genome Synteny Map: Indels and Synteny Breakpoints as Foci for Species-Specific Genes[END_REF]. Currently, over 200 species of this genus are recognized and new species continue to be described. Over all these species, at least 5 infect humans. Various types of malaria are caused by the different species. P. falciparum causes the most severe disease and is responsible for nearly all malaria-related deaths. Other species cause debilitating diseases that are less severe but highly persistent. The parasite always has two hosts in its life cycle: a mosquito vector and a vertebrate host. In this work, we studied three different plasmodium species: P. falciparum, P. vivax and P. yoelli. P. falciparum and P. vivax have approximately 5 500 genes, while P. yoelii genome contains about 7 720 genes. Nearly 50% proteins of each these 3 species do not have any known Pfam domain.

Toxoplasma gondii is a single-celled intracellular parasite that causes a disease known as toxoplasmosis. Infections by T. gondii are highly prevalent in humans and animals and the parasite is widely found throughout the world. The definitive host of T. gondii is the cat, but the parasite can be carried by many warm-blooded animals and cause severe and life-threatening disease in developing fetuses and immune-compromised individuals. The majority of infected persons are asymptomatic due to their protective immune status [START_REF] Blader | communication between Toxoplasma gondii and its host: impact on parasite growth, development, immune evasion, and virulence[END_REF]. T. gondi has about 8 102 protein-coding genes, about 57% of them do not have any known Pfam domain.

Cryptosporidium parvum is a protozoan parasite that causes cryptosporidiosis, a disease affecting the mammalian intestinal tract and mainly characterized by a diarrheal illness. It is transmitted to the host via the fecal-oral route. Among healthy people, an acute self-limiting infection occurs, but cryptosporidiosis could have lethal effects on immuno-compromised individuals (HIV infected, immuno-suppressed etc.). Cryptosporidiosis can be found worldwide, and in developing countries 8-19% of diarrheal diseases are attributed to cryptosporidium [START_REF] Gatei | Cryptosporidiosis: prevalence, genotype analysis, and symptoms associated with infections in children in Kenya[END_REF]. Its genomic sequence shows a small, compact genome of 9.1Mb with a simple organization containing only about 3 805 protein coding genes [START_REF] Abrahamsen | Complete genome sequence of the apicomplexan, Cryptosporidium parvum[END_REF]. A total of 1 123 different Pfam domains are known on these proteins covering 51% of the whole genome.

Giardia lamblia.

Giardiasis is a parasitic disease caused by Giardia species, a flagellated protozoan parasite that occupies the small intestine of numerous hosts including humans. Like Cryptosporidium, infection can occur due to ingestion of contaminated water or food and by the fecal-oral route. Depending on its life cycle stage (external dormant form versus ingested active form), two different parasite forms exist. Through protein-surface modification (with antigenic variation), Giardia can efficiently evade the host's immune defense [START_REF] Svärd | Differentiation-associated surface antigen variation in the ancient eukaryote Giardia lamblia[END_REF][START_REF] Tovar | Mitochondrial remnant organelles of Giardia function in iron-sulphur protein maturation[END_REF]. Like other diplomonads, Giardia is characterized by the presence of two nuclei. Its genome was only recently published and revealed a sequence of roughly 12Mb and about 5 000 protein-coding genes [START_REF] Morrison | Genomic minimalism in the early diverging intestinal parasite Giardia lamblia[END_REF].

Trypanosoma brucei are obligate parasitic protists of mammals to which they are transmitted by an insect vector commonly called tsetse fly. They cause African trypanosomiasis, commonly known as sleeping sickness. Its adaptation to different hosts, a common strategy among parasites, occurs through complex changes during its life cycle, and different parasite forms are known. A particular feature of kinetoplastids, in comparison with other eukaryotes, is a mitochondrial genome-containing kinetoplast associated with the basal body of the flagellum. Its genome is composed of 11 chromosomes and contains nearly 9800 protein coding genes. About 62% of these genes do not have any known Pfam domain.

CODD: Co-occurrence based domain detection

CODD is a computational approach that increases the sensitivity of HMMs for domain detection, while controlling the false discovery rate (FDR) associated with the predictions [START_REF] Terrapon | Detection of new protein domains using co-occurrence: application to Plasmodium falciparum[END_REF]. CODD utilizes the tendency (observed through the three kingdoms of life) of many domain families to occur preferentially with a few other favorite families of proteins [START_REF] Beaussart | Automated Improvement of Domain ANnotations using context analysis of domain arrangements (AIDAN)[END_REF]. Thus, the presence of one domain in a protein may be a strong clue for the presence of another one. CODD uses this tendency to warrant the presence of Pfam domains, on the basis of the presence of another domain in the same protein. The "validating domain" used for this purpose may be another Pfam domain or any other type of domain from the InterPro database [START_REF] Mulder | New developments in the InterPro database[END_REF]. CODD has been assessed both in Yeast and P. falciparum genomes [START_REF] Terrapon | Detection of new protein domains using co-occurrence: application to Plasmodium falciparum[END_REF]. It enabled the discovery of several hundreds new Pfam domain occurrences in both organisms, and contributed to the enrichment of the Gene Ontology (GO) annotation of their proteins.

The CODD principle is summarized in Figure 1. It involves five different steps:

1.

The first step involves the identification of the Conditionally Dependent Pairs of domains (CDP), i.e. the domain pairs that tend to appear preferentially together in the same protein. The CDP list is computed from the whole set of domain pairs observed in Uniprot proteins of all organisms.

2.

The second step involves the identification of potential domains in the proteins of the target organism. This is done by searching the protein sequences against Pfam HMM profiles with a loose score threshold.

3.

The third step is the certification procedure that uses the CDP list to certify the presence of potential domains thanks to the presence of other domains in the same protein.

4.

A shuffling procedure is then used to estimate the confidence (False Discovery Rate or FDR) of the newly certified domains.

5.

Finally, GO annotations are deduced from the newly discovered domains themselves and also from their combinations with others.

We further detail below how this general method has been implemented and used to build the EuPathDomains database.

Selecting the CDPs

The list of Conditionally Dependent Pairs (CDP) of domains was built from the whole set of domain pairs observed in UniProt proteins. These pairs must reveal a conditional dependence between a Pfam domain and an InterPro (Pfam or non-Pfam) domain, that is, the presence of the InterPro domain has to be a strong clue of the presence of the Pfam domain. For each pair, the number of proteins where both domains are present and where at least one domain is present is computed and used to measure the conditional dependence with a Fisher's exact test. All pairs with a p-value < 1% are considered as conditionally dependent and are added into the CDP list.

Selecting the potential domains

The sets of potential domains were inferred from the results of Pfam HMM searches using HMMER software [START_REF] Eddy | Profile hidden Markov models[END_REF]. Given a set of proteins and an HMM, this tool computes a score that measures the similarity between each protein sequence and the domain modeled by the HMM. Additionally, this score can be used to compute an E-value estimate that represents the expected number of random sequences that would obtain a score above that achieved by the protein. Here, the set of potential domains of each protein was built by considering all HMM hits that differ from the already known Pfam domains and which have an E-value below a given permissive threshold (e.g. [START_REF] Terrapon | Detection of new protein domains using co-occurrence: application to Plasmodium falciparum[END_REF]. This E-value threshold is chosen to be much less conservative than the thresholds recommended by Pfam for each HMM.

Certification process

Each potential domain identified in the previous step is then queried for certification by another domain: if both domains are in the CDP list, the potential domain is certified. Three kinds of certifications are considered. The first and most accurate one involves the certification of the potential domain by a known Pfam domain of the protein. A complementary solution is to certify the potential domain with an InterPro non-Pfam known domain. This allows us to increase the number of certifications. However, due to the heterogeneity of the InterPro database, the certifications achieved in this way may be of lower quality than those achieved with Pfam domains. The first two solutions certify domains solely in proteins where at least one domain is already known. To overcome this limitation, a third solution is to certify the potential domain by another potential domain of the protein. With this solution, all pairs of potential domains of the protein are enumerated, and if the pair belongs to the CDP list, the two domains are certified. Of course this procedure is more prone to false positives than the two others.

Estimating the number of false certifications

The certification procedure allows certifying several new domains among all the potential domains identified in the proteins of the organism. One issue is then to estimate the proportion of false positives among these new domains. To this end, one estimates the probability of certifying a potential domain under the null hypothesis H0 that it has been randomly predicted. This is done through computer simulations, by shuffling the potential domains of all proteins. The certification procedure is applied to the shuffled domains, and the number of certified random domains is computed. The entire procedure is repeated several times (typically 1000 times) to get a reliable estimate of the expected number of domains this procedure would certify under H0, and this number is used to compute an estimate of the False Discovery Rate (FDR), i.e. the proportion of false positives in the new domains.

Gene Ontology annotations

The GO currently serves as the dominant approach for machine-legible functional annotation. GO is a controlled and structured vocabulary describing three aspects of gene product function: molecular function, biological process and cellular location. Attempts have been made to link the Pfam and InterPro domains with the terms of the GO. The pfam2go mapping associates a specific GO term with a Pfam domain if all proteins in which this domain is known share the term [START_REF] Forslund | Predicting protein function from domain content[END_REF]. Thanks to this mapping, when a new domain is certified in a protein, all terms associated with this domain (if any) can be transferred to the protein.

Protein function usually results from combination of domains rather than from a single one [START_REF] Forslund | Predicting protein function from domain content[END_REF]. Thus, we generated a second mapping that links whole domain combinations to GO annotations. This second mapping is built on the same principle as the pfam2go mapping. All observed domain combinations of the Swiss-Prot proteins are enumerated. Then, for each combination present in more than 10 proteins, if all proteins in which the combination is present share a specific GO term, this term is assigned to the combination. As with the pfam2go mapping, this second mapping can be used to transfer new annotations to the protein in which a new domain is certified, if this domain forms an annotated combination with other known or certified domains.

Building the database

CODD was applied to all selected and above described organisms, with the three types of certification (known Pfam, known non-Pfam, and potential Pfam). The set of known InterPro domains (Pfam and non Pfam) were downloaded from each organism's specific database. For each organism, two E-value thresholds (typically 1 and 50) were used to identify the potential domains. This led to the construction of two different sets of potential domains of increasing size. CODD was run on each set, and the FDR associated with the certifications achieved was computed. High E-value thresholds usually allow more certifications, but with also higher FDRs. All certifications with an FDR below 20% were transferred to the EuPathDomains database. For each newly certified domain, the GO annotations that can be deduced from this domain, either solely or in combination with other known or newly certified domains, were also transferred to the database.

Results and discussion

The EuPathDomains database

EuPathDomains (for "Eukaryotic Pathogens Domains database") is freely available at http://www.atgc-montpellier.fr/EuPathDomains/. A friendly interface allows easy browsing and querying. The database can be queried in various ways, by protein names, domain IDs, Pfam or Interpro identifiers, with the possibility to limit the search on an organism or a taxon (Plasmodiums, Apicomplexans, ...), and with a given FDR threshold. The result includes the list of proteins where the domain is already known and those where it has been predicted with the associated FDRs.

Figure 2 illustrates a typical output obtained when querying for the L. major protein LmjF36.4590. This figure shows the known domains for this protein as well as the predicted domains (with the domains that allowed their certification) and the related GO terms transferred to the protein. Some terms, such as "zinc ion binding" and "intracellular" are already known in the protein, but other annotations, such as "regulation of transcription, DNA dependent", are new.

The database contains several hundred new Pfam domains in each species. Some of the newly predicted domains have never previously been seen in these species. Thus, these predictions enabled the set of known domain families in all studied organisms to be expanded. With a FDR below 20%, the database expands the set of domains between 13% in G. lamblia to up to 28% in C. parvum. It also expands the set of known domain families in each organism, between 10% in P. falciparum to up to 16% in C. parvum. Moreover, the newly discovered domains also provide new functional annotations for the proteins of the different species. The number of additional GO terms ranges from 302 in G. lamblia to 684 in T. brucei. Table 2 details the number of new domains found in each species for the three types of certification. The numbers of new GO annotations that can be deduced from these domains are detailed in Table 3.

For example, in L. major, EuPathDomains contains a total of 719 new domains with a FDR below 20% (Table 2). This is an increase of 14% compared to the 5 216 already known Pfam domains in this organism (only one occurrence of each known/new domain per protein is considered here; Pfam release 23.0). Among these, 607 involve a new InterPro domain family in the protein. The known Pfam domains allow for the certification of 385 out of the 719 new domains, the known non-Pfam domains 417, and the potential domains themselves 316 (several new domains are certified by 2 or the 3 types of certifications). As we can see, the potential domains allow the certification of fewer domains than the known domains for a given FDR. This is not surprising, as these domains are potentially false. Hence, very low E-value thresholds are required to achieve low FDRs, which induce the selection of small amounts of potential domains. Moreover, 184 new domain types were discovered-i.e. which had never been previously detected in L. major proteins-, an increase of 11% in the total number of domain types known in this parasite. With an FDR<20%, the newly discovered domains led to the identification of 466 new GO terms (Table 3), representing 6% of the already known GO terms in L. major proteins. This allows us to propose GO annotations for 53 proteins without any annotation. Similar results were also achieved on the two other Leishmania species (L. infantum and L. braziliensis; see Supplementary Table S1 andS2, respectively).

Description of the newly discovered domains

We sought to characterize the specificities of the newly discovered domains, compared to the already known domains in each species. One of the first characteristics involves the length of the new domains. Usually, domains vary in length from about 25 to 500 amino acids. A comparison of the known and new Pfam domains shows that, on average, the newly certified domains are shorter than the already known domains (see Figure 3). This difference between known and new domains is not surprising, as short domains carry less information than longer ones, and are more difficult to detect, especially in divergent proteins. Thus, our certification procedure primarily enables recovery of these domains.

We next investigated the GO annotations provided by the newly predicted domains via Pfam2go mapping. GO annotations provided by combination of several domains are generally more specific than those deduced from the presence of a single one. For previously annotated proteins, this enables the discovery of more accurate functions confirming the already known annotations. For example, the term « RNA polymerase II transcription factor activity », which catalyzes DNA transcription to synthesize precursors of mRNA and most snRNA and microRNA, is assigned to different Leishmania proteins by combining both predicted and already known domains.

For hypothetical or very poorly annotated proteins, two major cases are observed based on the level of annotation of the newly detected domains. On the one hand, the new domains are ascribed to no or poorly informative GO terms. In this case, no precise functional annotation can be deduced from the present work, but the structural categorization of the proteins is refined, providing clues for future functional inferences. On the other hand, newly detected domains can be sufficiently informative and have accurate GO annotations, which are transferred to the hypothetical or poorly annotated protein.

Next, we used the GOstat tool [START_REF] Beißbarth | GOstat: find statistically overrepresented Gene Ontologies within a group of gene[END_REF] to compare the GO annotations associated with the known and the newly certified domains according to the three axis of the Gene Ontology: molecular function, biological processes and cellular component. For each species, we uploaded in GOstat the set of newly discovered domain families, the set of known domain families, and the Pfam2go mapping. Then, we asked GOstat for the GO annotations that are over-represented in the new domain families in comparison with the known domain families. Table 4 lists the results achieved in each species for domains certified with an FDR<10%. With the exception of G. lamblia, several terms appear to be overrepresented in the different organisms. For example, several overrepresented terms are related to DNA-or RNA-binding in Plasmodium species. This finding might be useful to decipher the currently debated mode of regulation of transcription in these organisms [START_REF] Essien | Conservation and divergence of known apicomplexan transcriptional regulons[END_REF][START_REF] Bischoff | In silico and biological survey of transcription-associated proteins implicated in the transcriptional machinery during the erythrocytic development of Plasmodium falciparum[END_REF].

Leishmania as a case study

We emphasized our analysis on the genus Leishmania with three species included in EuPathDomains database. At first glance, we notice that many terms related to DNA and RNA stability and transcription are found in the new described domains (Table 4) of these species, in comparison with the known ones. This should help to identify novel key elements involved in the complex mechanisms driving polycistronic mRNA transcription in Leishmania. Indeed, and although extensively studied, this process remains one of the major focuses of Leishmania biology research [START_REF] Haile | Developmental regulation of gene expression in trypanosomatid parasitic protozoa[END_REF][START_REF] Clayton | Post-transcriptional regulation of gene expression in trypanosomes and leishmanias[END_REF].

First analyses of the predictions achieved in these species show that a great number of newly discovered domains are strikingly shared between them (see Table 5), which increases our confidence in the correctness of the approach. Indeed, the majority of newly discovered domains in L. major (87% with FDR<10%) were also newly discovered in L. Infantum, while 18 new domains were already known in L. infantum species.

When looking to new domain families that were previously unknown in the three Leishmania species, 45 domains with an FDR<10% (~40%) are common between them. RQC (PF09382) is one of these new domains that are common to the three species. This DNA-binding domain is specific to the RecQ family of helicases that bind and unwind G4-DNA. A recently described potential role [START_REF] Hanakahi | High affinity interactions of nucleolin with G-G-paired rDNA[END_REF][START_REF] Parkinson | Crystal structure of parallel quadruplexes from human telomeric DNA[END_REF][START_REF] Maizels | Dynamic roles for G4 DNA in the biology of eukaryotic cells[END_REF] of this G4-DNA in gene regulation and genome stability is its participation in gene transcription by maintaining the DNA in an open conformation [START_REF] Du | Genome-wide analysis reveals regulatory role of G4 DNA in gene transcription[END_REF]. Moreover, RQC has a helix-turn-helix structure (HTH) that is commonly found in gene regulatory proteins, and known to bind DNA in a sequence-specific manner [START_REF] Struhl | Helix-turn-helix, zinc-finger, and leucine-zipper motifs for eukaryotic transcriptional regulatory proteins[END_REF][START_REF] Mathee | Detection of DNA-Binding Helix-Turn-Helix Motifs in Proteins Using the Pattern Dictionary Method[END_REF]. RQC could thus represent a relevant feature of Leishmania gene regulatory processes. Related to another regulatory level is the "Response reg" domain (PF00072), which is associated in other organisms with a "two-component signal transduction system" (TCS) involved in signal transduction events [START_REF] Krauss | Biochemistry of Signal transduction and regulation[END_REF][START_REF] Pao | Response regulators of bacterial signal transduction systems: selective domain shuffling during evolution[END_REF]. The TCS pathway was originally described in bacteria, and more recently in eukaryotes, as involved in sensing the environment for changes in stress or growth conditions [START_REF] Skerker | Two-Component Signal Transduction Pathways Regulating Growth and Cell Cycle Progression in a Bacterium: A System-Level Analysis[END_REF][START_REF] Whitworth | Evolution of prokaryotic two-component systems: insights from comparative genomics[END_REF]. As TCS is involved in drug resistance, osmoregulation and motility among others, one can think that the associated Response_reg new domain could contribute to pathogen physiological status adaptation to a wide variety of stimuli.

The new 45 conserved protein domains have annotations related to different pathways. We classified them into nine different functional groups based on the pfam2go mapping but also on literature mining (Figure 4). The two most represented families are related to transcription and DNA binding functions. Besides the existence of all these common domains, a small proportion of the new families (16% in L. major for example) appear to be species specific, even if we cannot exclude the possible existence of false positives. As some of these domains may be related to species-specific mechanisms (e.g. tropism), they are worth further investigations.

Common new predicted domains between different pathogens

Within EuPathDomains database, eight domain families, which were previously unknown in the different studied pathogens, are identified in all these organisms. The presence of these new domains addresses the question of their specific occurrence in pathogens and on their potential relation with parasitic life style, including common infectious or surviving strategies that have already been described for pathogens with various clinical outcomes [START_REF] Hybiske | Exit strategies of intracellular pathogens[END_REF].

In the eight common domain families, three (Utp12, Utp21 and PWP2) are associated with proteins involved in the small-subunit (SSU) processome for the processing of the smallribosomal-subunit rRNA [START_REF] Dragon | A large nucleolar U3 ribonucleoprotein required for 18S ribosomal RNA biogenesis[END_REF]. It has been suggested that, through its association with specific ribosomal proteins, the SSU processome was probably involved in both pre-rRNA processing and ribosome assembly [START_REF] Bernstein | The small-subunit processome is a ribosome assembly intermediate[END_REF].

A fourth newly predicted domain family is the polyadenylate-binding protein (PABP)-interacting motif PAM2 that has been identified in several eukaryotic proteins, including ataxin-2 [START_REF] Albrecht | Survey on the PABC recognition motif PAM2[END_REF]. This domain interacts with a particular family of RNA helicases and participates in the recognition of the 3'end of mRNAs, with an essential contribution to eukaryotic translation initiation and mRNA stabilization/degradation [START_REF] Nonhoff | Ataxin-2 Interacts with the DEAD/H-Box RNA Helicase DDX6 and Interferes with P-Bodies and Stress Granules[END_REF]. In addition, a domain PF08147-DBP10CT corresponding to hypothetical RNA helicase has also been identified in all studied organisms using our approach. This could reflect the common need for rapid synthesis of molecules favoring survival of any organism and its resistance to environmental stress.

The last three new domains found in all organisms correspond to proteins involved in distinct functions. MutS_II is a domain found in the MutS family of proteins involved in mismatch repair [START_REF] Lamers | The alternating ATPase domains of MutS control DNA mismatch repair[END_REF]. Another domain with an unknown function, referenced as PF08953, has been associated in Leishmania with the LmjF23.1165 gene, coding for a putative Coronin, a WD-repeat containing protein. It is worth noting that the previously described Utp12 and PWP2 domains are members of this WD-repeat family. Hence, PF08953 domain might be involved in protein interactions in different biological processes such as signal transduction, transcriptional regulation, cytoskeleton remodeling, and regulation of vesicle trafficking [START_REF] Coronin | Diversity of WD-repeat proteins[END_REF]. Finally, PF09279, a domain called EFhand-like is newly described in the studied pathogens except Plasmodium species where it was already known. This domain is found in the phosphoinositide-specific phospholipase C family. The phospholipase activity has been described as participating in the degradation membranes containing pathogens by decreasing the number of phospholipids causing the weakening of membrane integrity [START_REF] Cummings | Phospholipase A2s in cell injury and death[END_REF].

We thus speculate that some of these new domains might be associated to some aspects of the parasitic life style. It is therefore now important to explore their occurrence in other organisms. Overall, all these new identified protein domains highlight the importance of domain discovery in assigning and fine tuning biological functions for poorly, and also for well annotated eukaryotic organisms, including important pathogens.

Conclusion

Domains are the building blocks of proteins and one of the key features to help decipher protein function. Indeed, identification of protein domain content is a crucial step in understanding their role. HMMs have proved to be a powerful and accurate tool for this purpose, and are the basis of the Pfam database, one of the most widely used resources for protein domains. However, these models may miss numerous domains in divergent proteins. This is especially true in eukaryotic pathogens where no Pfam domains are detected in more than half of the proteins of these organisms. We recently proposed a method named CODD that uses domain co-occurrence to help detect divergent domains. In this paper, this method is applied on ten human eukaryotic parasites. All predictions, along with their confidence values and GO annotations, have been integrated in a dedicated database named EuPathDomains.

On the whole, the EuPathDomains database significantly improves the domain coverage in all genomes, by localizing new occurrences of domains that are already known and, more interestingly, by detecting new domain families that have never previously been reported. For example, with an FDR<20%, EuPathDomains increases the number of domain occurrence between 13% to up to 28% in each organism, and the total number of domain families between 10% to up to 16%. Moreover, several of these new domains also provide new GO annotations. Thus, EuPathDomains appears to be a valuable new resource for domain annotation in eukaryotic pathogens, and should help deciphering the biology of these complex and crucial organisms.

Legend of figures

Figure 1: The CODD certification process. The CDP list was computed from all domain pairs found in the UniProt proteins. The protein sequences were matched against the set of 10 340 Pfam profile HMMs with loose E-value thresholds to allow detection of more domains. Domains overlapping with known Pfam domains were discarded. In the remaining overlaps, domains with the best E-value were kept. The CDP list was used for the certification process of the set of potential domains. An FDR estimation process was then carried out to assess the level of confidence of the certified domains.

Figure 2 :

 2 Figure2: Known and newly predicted domains of L. major gene LmjF36.4590. One InterPro domain is already known (SSF57903). Localization as well as known GO annotation terms are given. Three new Pfam domains PF02178, PF00628 and PF00643 are predicted with E-values of 0.93 and 0.6 and 0.27 respectively. They have been certified by several validating domains with various FDRs. For example, the second domain have been certified by the known InterPro SSF57903 with an FDR equal to 20%, and the potentials Pfam PF02178 and PF00643 with FDRs below 10%. New GO terms are transferred to this protein from the predicted Pfam PF00628 itself: "zinc ion binding" and "protein binding". The "zinc ion binding" is already known for that protein. Combined with other predicted domains, it brings new annotations such as "regulation of transcription, DNA related".

Figure 3 :

 3 Figure 3: Comparison of frequency of known (blue) and newly certified (red) L. Major domains according to their lengths.

Figure 4 :

 4 Figure 4: GO functions of common new domain families predicted in L.major, L. infantum and L. braziliensis.

Table 3 : New GO annotations on different species proteins

 3 . "Single Domains" is the number of new GO annotations supplied by a single domain certified by our approach; "Combined domains" is the number of supplementary GO annotations (different from the previous column) that can be deduced from combinations of the newly certified domain and another known or new domain; "Unannot. Prot." is the number of proteins without any annotation for which an annotation is now proposed.

	Organism	FDR	Single Domains	Combin. With Certified Dom.	Unannot. Prot.
	L. major	≤ 10%	158	108	28
		≤ 20%	302	164	53
	P.	≤ 10%	117	77	20
	falciparum	≤ 20%	250	111	39
	T. gondii	≤ 10%	226	129	38
		≤ 20%	412	165	71
	C. parvum	≤ 10%	176	114	44
		≤ 20%	258	141	56
	G. lamblia	≤ 10%	51	37	14
		≤ 20%	203	99	59
	T. brucei	≤ 10%	246*	175	37*
		≤ 20%	402	282	79

*: results achieved with an FDR= 12%; no certifications with FDR<10% were achieved in T. brucei with the Interpro non-Pfam domains

Table 4 : GO terms that appear as overrepresented in the newly discovered domains for each organism compared to already known ones

 4 (black boxes). L. m for L. major; P. f for P. falciparum; T. g for T. gondii; G. l for G. lamblia; C. p for C. parvum and T. b for T. brucei.

	GO term	L. m P. f	T. g	G. l	C. p T. b
	Molecular function
	Signal transducer activity
	Protein_kinase activity
	Transmembrane receptor protein kinase
	activity
	Zinc ion binding
	Purine ribonucleotide binding
	ATP binding
	Structure specific DNA binding
	Enzyme inhibitor activity
	GTP binding
	Biological process
	Post-translational protein modification
	Cell communication
	Cell surface receptor linked signaling pathway
	Signal transduction
	DNA replication, synthesis of RNA primer
	Glucose catabolic process
	Cellular component
	Nucleus
	Receptor complex
	Intracellular membrane-bounded organelle
	Clathrin adaptor complex
	Phosphopyruvate hydratase complex

Table 5 : Proportion of known and new Pfam domains in L. major proteins with a known L. infantum homolog that are also present in the known/new Pfam domains of their L. infantum homolog.

 5 For example, 5279 known Pfam domains are in a L. major protein with a known L. infantum homolog. Among these, 5114 are also found in the L. infantum homolog. Similarly, 448 new domains with a FDR<10% in L. major are in proteins with a known homolog in L. infantum. Among these, 18 are already known in the L. infantum homolog, and 390 are also detected in the L. infantum homologue with an FDR<10%.

	L. Infantum

Tables


N Delprat

Compatibility conditions, modulation mechanisms and preferred modes in incompressible flow over a cavity

Keywords: cavity-flow oscillations, non linear interactions and wave modulations, frequency coincidence, amplitud modulated regimes, preferred modes

Self-sustained oscillations in cavity-flows can be strongly influenced by shear layer instability acting together with feedback and modulation mechanisms. When coherently organized, these oscillations lock-on at a fundamental frequency and compatibility conditions exist between shear layer forcing, non linear interactions and low-frequency modulations. Special attention is given to the frequency coincidence which may appear in spectral distributions due to combinations between the dominant peak and its sidebands. Hence, the possible existence of two preferred modes in incompressible cavity-flows at medium Reynolds numbers is shown. This leads to a detailed categorization of the flow modulated regimes and to the specification of a persistent mode involved in modulation process whatever the oscillation stage.

Introduction

-Besides the predominant frequency (denoted f a in the following), multiple peaks are generally present in spectra of the velocity fluctuations recorded in cavityflows. They are usually referred to as secondary peaks even though their amplitude may be of the same order as the one of the primary frequency. Thus, sideband peaks around f a (f -, f + ) and its harmonics nf a (f -n , f +n ) have been identified as the result of an amplitude modulation of the fundamental oscillations by a low-frequency component (denoted f b ). Rockwell and Knisely proposed to relate this modulation process to variations in the vortex-corner impingement, assuming that its upstream influence is compatible with the whole oscillation system and feedback forcing of the shear layer instability [START_REF] Knisely | Self-sustained low-frequency components in an impinging shear layer[END_REF]. Non-linear interactions between primary oscillation modes and secondary ones may also occur, yielding the generation of spectral components in the form of sum and difference frequencies and their combination. From a modulation analysis point of view, several interaction mechanisms which may coexist or combine with a feedback process must satisfy definite compatibility conditions and frequency selection rules for the oscillations to be self-sustained and coherent [START_REF] Delprat | Rossiter 's formula: A simple spectral model for a complex amplitude modulation process?[END_REF][3] [START_REF] Delprat | Low-frequency components and modulation processes in compressible cavity-flows[END_REF]. We propose to point out these conditions and to show how they may help to clarify the complex relationships between the frequencies involved in cavity-flows.

Feedback cycle forcing and modulation mechanism

-As demonstrated by Miksad and co-authors for non-impinging shear layer excited by sound, non linear interactions between close instability modes f i and f i' generate amplitude and phase modulations through the generation of a low-frequency difference mode d = (f i -f i' ) [START_REF] Miksad | Experiments on the role of amplitude and phase modulations during transition to turbulence[END_REF]. Resulting spectra have a multiple sideband distribution around the frequency of the most unstable mode f i , predicted by linear stability theory, and its harmonics (nf i ± d, n integer). Depending on the ratio of the interacting frequencies, some peaks may be superimposed and the number of spectral components is significantly reduced. For instance, when f i' /f i = 3/4, the second and fourth harmonics of f i' verify 2f i' = 3/2f i , 4f i' = 3f i and the subharmonic of f i is such that 1/2f i = 2/3f i' [START_REF] Miksad | Experiments on the role of amplitude and phase modulations during transition to turbulence[END_REF]. For free shear layers artificially excited by a single frequency, spectral energy is partitionned between f i , nf i and 1/2f i , 3/2f i [START_REF] Miksad | Experiments on nonlinear interactions in the transition of a free shear layer[END_REF]. Note that the existence of spectral components at 1/2f i and 3/2f i is a specific feature of natural excited instability [START_REF] Miksad | Experiments on the nonlinear stages of free-shear-layer-transition[END_REF].

In cavity-flows, oscillations lock on a frequency selected in the band of dominant instability modes through a feedback mechanism between the two cavity corners. This frequency always lies in the neighbourhood of the frequency f i at which the shear layer is the most unstable [START_REF] Knisely | Self-sustained low-frequency components in an impinging shear layer[END_REF]. As established from various experimental data, its corresponding Strouhal number based on the cavity length L (St L = f a L/U with U free-stream velocity) is generally about St L ≈ 1 [START_REF] Rockwell | Prediction of oscillation frequencies for unstable flow past cavities[END_REF]. When expressed in terms of a locking condition (denoted lc), this means that the second oscillation mode of the phase-locked feedback cycle f lc is preferentially chosen by the cavity-flow [START_REF] Gharib | The effects of flow oscillations on cavity drag[END_REF]. As usually verified on the basis of phase measurements, this result requires that U c /U ≈ 0.5 and implies that f lc ≈ U c /L ≈ U/2L (with U c convective velocity) [1][10]. Hence, the fundamental frequency of the cavity-flow oscillations satisfies f a ≈ 2f lc . Note that in some experiments, cavity-flows have been found to oscillate in mode III, that is to say St L ≈1.5 and f a ≈ 3f lc [START_REF] Gharib | The effects of flow oscillations on cavity drag[END_REF].

When the predominant peak at frequency f a is modulated by a low-frequency f b such as f b /f a ≈ 0.4 (stage II in the paper by Rockwell and Knisely [START_REF] Knisely | Self-sustained low-frequency components in an impinging shear layer[END_REF]), it is of interest to point out that its associated Strouhal numbers St θ 0 is found to be lower than the ones predicted with inviscid stability theory (St θ 0 ≈ 0.017) [START_REF] Michalke | On spatially growing disturbances in an inviscid shear layer[END_REF] [START_REF] Ho | Perturbated free shear layers[END_REF]. It is rather in the same range than the Strouhal numbers of natural instability frequencies that is to say from 0.012 to 0.015 [START_REF] Husain | Natural intability of free shear layers[END_REF]. This feature is not specific to Rockwell's experiments. We have found similar Strouhal numbers with our experimental data obtained from LDV measurements for an air flow past an open cavity at medium Reynolds range numbers (free-stream velocities from 0.99 m/s to 2.84 m/s) and different cavity aspect ratios (R = 1.5, 1.75, 2) with (L = 0.075 m, 0.0875 m, 0.1 m) [14][15]. This remark is illustrated in table 1 where Strouhal numbers of predominant peaks and sideband ones (f -, f + ) are given for several configurations. Strouhal numbers estimates of the fundamental feedback cycle in mode II (2f lc = U/L) are also listed.

Table 1 Strouhal numbers associated with predominant peaks (f a ), sideband peaks (f -, f + ) and second harmonic of the fundamental feedback cycle (2f lc ). Details on the estimation of the momentum thickness θ 0 at the cavity leading edge are available in the paper by [START_REF] Basley | Experimental investigation of global structures in an incompressible cavity flow using time-resolved PIV[END_REF].

Despite the uncertainty in the initial momentum thickness θ 0 due to its experimental estimation, the data confirm that the self-excited oscillations are forced by the feedback cycle configuration (agreement within 4% between the two first lines in Table 1). For the (R = 1.5, U = 2.84 m/s) configuration, the shear layer oscillates in mode III (3f lc θ 0 /U ≈ 0.0192) at a frequency close to its inherent most unstable mode (St θ 0 ≈ 0.0182). Moreover, the lower Strouhal numbers observed for the (R = 2, U = 2.18 m/s) configuration can be explained by the fact that the cavity-flow regime is near a frequency jump between two stages of oscillation (transition from mode II to mode III) [1][10]. One may also easily verify that the St θ 0 value associated with the right sideband f + (f + = f a + f b ) is equal to 0.0178 on average and that the St θ 0 value associated with the left sideband

R = 2 U =1.71m/s R = 2 U=1.90m/s R = 2 U=2.18m/s R = 1.5 U=1.77m/s R = 1.5 U=2.10m/s R = 1.5 U=2.84m/s f a θ 0 /U 0.
f -(f -= f a -f b ) is such that 2f -≈ f + (agreement within 2%).
From an amplitude modulation point of view, this equality simply means that the modulating to fundamental oscillation frequency ratio satisfies f b /f a ≈ 1/3. Except for the last two configurations, which will be discussed in detail later, the corresponding frequency ratios are found to be in good agreement with this value (cf Table 2). Note that for the cavity-flows under consideration, spectral components have been identified without ambiguity (as an illustration, see figure 1).

Dual instability modes and frequency matching

-The presence of a low-frequency component f b equals to the difference frequency of the predominant peak and sidebands is typical of an amplitude modulation spectrum produced by non-linear interactions involving a low-frequency difference mode [5][16]. When this component satifies f b /f a ≈ 1/3, it follows that f -≈ 1/2f + and f a ≈ 3/4f + . Hence, the frequency coincidence, previously described for a free shear layer artificially excited by two frequencies in the same ratio, is verified (see Table 3) This remark suggests that spectral distributions may be described with the help of two frequency families which are: (1/2f + , f + , 3/2f + ) and (1/3f a , 2/3f a , f a , 4/3f a , 2f a ). In terms of nonlinear interaction, this particular feature may be interpreted as the consequence of a dualfrequency excitation caused by two instability modes (f i , f i' ). The first one would be due to the shear layer mode associated with the most amplified wave of the initial velocity profile (f + ≈ f i ). The second one would be related to the instability mode whose frequency is compatible with the phase locking condition imposed by the cavity (f a ≈ f i' ). By analogy with the so-called preferred mode in jets [START_REF] Ho | Perturbated free shear layers[END_REF][17], we propose to name the fundamental oscillation mode f a the preferred mode of the cavity-flow and the most unstable mode f i the preferred mode of the shear layer. We will see in the following that the differentiation between f i and f a , even when they are very close in frequency, is essential to explain the connections between lowfrequency modulations and flow lock-on features.

. configuration R = 2 U=1.71m/s R = 2 U=1.90m/s R = 2 U=2.18m/s R = 1.5 U=1.77m/s R = 1.5 U=2.10m/s R = 1.5 U=2.84m/s f b (
Our recent study on the modal spatial structures associated with the most characteristic frequencies of the (R = 2, U = 1.90m/s) cavity-flow has already shown that the contributions of (f a , f + ) and their harmonics are central to the global organization of the flow [START_REF] Basley | Experimental investigation of global structures in an incompressible cavity flow using time-resolved PIV[END_REF]. For the (R = 2, U = 2.18m/s) configuration, mode competition between f a and f + revealed by timefrequency and phase-space analyses of velocity signals also supports the presence of dual instability modes [START_REF] Pastur | Quantifying the nonlinear mode competition in the flow over an open cavity at medium Reynolds number[END_REF]. The existence of several admissible sources in mode generation expresses the well-known duality between non-linear interactions and wave modulations observed in free excited shear layers. In cavity-flow oscillations, the important point is that the excitation sources are inherent to the flow system and produce components which are compatible with the frequency selection rules of both excitation modes. This compatibility does not depend on the nature of their relationships (competition, combination or coexistence). As we will see in the next section, it is mainly related to the characteristics of the amplitude modulation process which may arise from their interaction.

Amplitude-modulated regimes

-A flow system which is self-excited by two instability modes may develop various dynamic behaviors. Depending on the frequency ratio and relative amplitudes of these modes, several regimes will be distinguished. In the present study, the frequency sequence (1/3f a , 2/3f a , f a , 4/3f a , 2f a ) associated with the preferred mode f a of the cavity-flow is similar to the ones found for self-modulated impinging jets [19][20]. On the other hand, the frequency family related to f + ≈ f i is typical of self-excited shear layer (1/2f i , f i , 3/2f i ). Each family are representative of modulation processes which may combine through the non-linear interaction of f a and f i (see figure 2). Under this condition, several (modulated and non-modulated) regimes can governe the flow dynamics. Depending on the dual influence of the preferred modes, the flow may be mainly structured either by the free part of the shear layer, promoting non-linear interactions or by the oscillating system forced by the feedback mechanism, involving modulations [START_REF] Gharib | The effects of flow oscillations on cavity drag[END_REF]. In the boundary lock-on region, both kinds of regime may interact via the coupling of f i anf f a and a transitional state will appear in the form of mode switching. Whatever the case and even though they may physically compete in an intermittent way, the regimes will always spectrally act in harmony owing to their frequency coincidence. The upstream influence of the amplitude fluctuations at the downstream corner strongly depends on the strength of these fluctuations. Most of the time, this influence is amplitudemodulated [START_REF] Knisely | Self-sustained low-frequency components in an impinging shear layer[END_REF]. Since sideband energy comes from the modulating wave in amplitude modulation process, the f + mode may be reinforced through its interaction with the lowfrequency mode f b . Hence, the modulation process coud play a central role in the spectral transfer of energy between modes. This aspect is of particular interest in boundary regimes where frequency competition occurs between f a and f + . It will be discussed more fully in a forthcoming paper with the help of time-frequency and bicoherence analyses.

Very low-frequency modulations

-It is clear that the complexity and variety of modulated cavity-flow regimes cannot be exhaustively described by figure 2. For instance, there exist very low-frequency modulated regimes characterized by modulation ratios around 1/10. In this case, the sideband components around the fundamental oscillation frequency f a have to be differentiate from the (f -, f + ) frequencies previously defined. For the sake of clarity, we propose to denote them f -' and f +' and to name the very-low frequency mode Δ f . The spectral distribution of the (R = 1.5, U = 2.10m/s) cavity-flow depicted in figure 3 provides an illustration of this flow regime.

Here, the preferred mode of the cavity-flow (f a ≈ 27 Hz) and its harmonic are amplitude modulated by a low-frequency at Δ f ≈ 3.3 Hz. Contrary to the f b modulation, the left sideband peak (f -' ≈ 23.8 Hz) has a greater amplitude than the right sideband ones (f +' ≈ 30.2 Hz). Barely discernable peaks at f -≈ 16.1 Hz and f + ≈ 38.9 Hz might correspond to an extremely weak f b modulation process around 11.4 Hz (mean value). Note that if f -≈ 1/2f i (estimated f i ≈ 32.53 Hz), the 2f -≈ f + relation no longer holds. However, it is an interesting case because it reveals a second kind of modulation process whose effects might be masked by the f b -modulation otherwise. Indeed, it has been established by one of us that two modulation processes present in an oscillating cavity-flow can spectrally combine when their modulating frequencies satisfy a specific compatibility condition (cf section 4 in [START_REF] Delprat | Low-frequency components and modulation processes in compressible cavity-flows[END_REF]). This condition simply expresses the agreement between the f b -modulation ratio f b /f a and the modulating frequency ratio Δ f /f b . In particular when f b /f a =1/3, then Δ f /f a should be equal to 1/9 for the condition to be verified (f b /f a = Δ f /f b ). This value is strikingly close to the ones found in the present configuration (Δ f /f a ≈ 0.12). The result suggests that the Δ f -modulation could be on the same nature than the newly identified low-frequency modulation in compressible flows at subsonic Mach numbers and therefore be an inherent feature of cavity-flows [START_REF] Delprat | Low-frequency components and modulation processes in compressible cavity-flows[END_REF] [START_REF] Brès | Three dimensional instabilities in compressible flow over open cavities[END_REF]. If as supposed in the compressible case, the very low-frequency mode is linked to the internal flow then the studied spectral distribution could simply represent a recirculation induced modulation. Thus, the global dynamics of the flow could be structured by oscillations at the fundamental frequency f a , modulated via delayed non-linear interactions through the recirculating flow. An extensive study of the local and global properties of the Δ f and f -' modes has been recently performed and their relationships with the f a mode will be described in detail in a separate paper.

Cavity-flow resonances and persistent mode

-When a cavity-flow oscillates in mode III, the change in phase locking condition (f a ≈ 3f lc ) leads to noticeable modifications in spectra with regard to the spectral features examined in section 2. The (R = 1.5, U = 2.84m/s) configuration listed in Table 1 illustrates this kind of flow regime with f a ≈ 53.9 Hz and f lc ≈ 18.9 Hz. Its spectral distribution shown in figure 4 exhibits a well-defined low-frequency peak at the difference frequency between f a and its left sideband peak f -(cf Table 4). Since the corresponding modulation ratio lies between 1/4 and 1/3 (f b /f a ≈ 0.282), we have identified it as the component f b . The preferred mode of the shear layer and its subharmonic are also present (f i ≈ 50.3 Hz from linear stability analysis). Contrary to regimes in mode II, the f i peak frequency is slightly smaller than the f a ones (about 4 Hz) and no right sideband peak at f + is detected.

At high free-stream velocities, increase of the random background fluctuations as well as strong non-linear activity are expected to occur. The observed spiky structure of the spectrum in figure 4 expresses the former feature. The latter is confirmed by the multiple sum and difference modes, which may contribute to the existence of some peaks. For instance, the following combinations (f -+ f a ), (2f af b ) or (2f -+ f b ) may generate the f 7 frequency. Another interesting characteristic is the extended influence of the cavity feedback forcing on the sideband component f -, which is one of the predominant peaks in the spectrum. Indeed, f -is very close to the second harmonic of f lc (2f lc ≈ 37.8 Hz) and 2f -to its forth ones (4f lc ≈75.6 Hz). Note also that 5f lc ≈ 94.5 Hz (f 7 ≈ 92.2 Hz). Thus, the cavity-flow resonances at (2f lc , 3f lc , 4f lc , 5f lc ) seem to strongly structure the flow behavior. In particular, the large amplitude of the f - mode is apparently due to its frequency coincidence with mode II of the fundamental feedback cycle. Table 4 Frequencies identified in the spectrum of the (R = 1.5, U = 2.84m/s) cavity-flow.

In boundary regimes oscillating in mode II, we have established that the dominant peaks are located at f a and f + with f a ≈ 3/4f i ≈ 2f lc and f + ≈ f i . In the present configuration, they are positionned at f -≈ 2f lc and f a ≈ 3f lc with f -≈ 3/4f i (see Table 5). This indicates that the peak at 3/4f i is always involved in modulation process. When non-linear effects are sufficiently significant, it may interact with another dominant mode to generate an amplitude modulation at their difference frequency. The modulation mechanism will be triggered under two conditions. Firstly, the amplitudes of the interacting modes have to be large enough for the interaction to be efficient. This will be obviously verified when both modes lie in the vicinity of a cavity-flow resonance. Secondly, their difference frequency must be in tune with the modulating frequency inherent to the modulated impinging flow, that is to say f b must be in the neighborhood of 1/3f a . These remarks make it appropriate to think that the 3/4f i mode could play a central role in the coupling between non-linear aspects of the shear layer and self-modulation of the cavity-flow. Its persistence between two stages of oscillation is an additional argument for considering its contribution as an essential feature of the oscillation mechanism. For that reason, it will be called the persistent mode and denoted f pm . Concluding remarks -The above considerations allow us to clearly characterize each stage of oscillation through their modulation features. For stage II, the frequencies involved in the modulation process are such that:

f a ≈ f pm and f b ≈ f + -f a with f + ≈ f i and f b /f a ≈ 1/3. (1)
In terms of an amplitude modulation, this means that the sideband peaks (f -n , f +n ) may simply be predicted by:

f ±n = (nf a ± f b ) ≈ (n ± 1/3) f a n integer, n ≥ 1. (2)
In stage III, we have:

f -≈ f pm and f b ≈ f a -f -. (3)
Morover, the preferred mode frequencies f i and f a are very close. For instance, in the (R = 1.5, U = 2.84m/s) configuration, f i /f a ≈ 0.928. From these results, it follows that the corresponding modulation ratio may be written in the form:

f b /f a ≈ 1 -3/4 f i /f a . (4)
Eq. ( 4) allows us to quantify the observed deviation of the f b /f a ratio from it expected value 1/3, while remaining close to it. It is clear that reasonably good estimates can also be found when the frequency difference between f a and f i is not taken into account. In this case, the modulation ratio is approximated by f b /f a ≈ 1/4 and the sideband peaks are defined by: f ±n ≈ (n ± 1/4) f a n integer, n ≥ 1 .

(

Expressed in terms of a Strouhal number, Equation (5) becomes : f ±n L/U ≈ κ 3 (n ± γ) with γ = 1/4 and κ 3 = 3κ (κ ≈ 0.5).

It follows that the sequence of the left sideband peaks is predicted by: f -n L/U ≈ κ 3 (nγ) with γ = 1/4 and κ 3 = 3κ = 1.5

Eq. ( 7) does not exactly correspond to the Rossiter formula [START_REF] Rossiter | Wind-tunnel experiments on the flow over rectangular cavities at subsonic and transonic speeds[END_REF] applied in the zero Mach number limit, which is : f -n L/U ≈ κ (nγ) with γ =1/4 and κ = 0.57. [START_REF] Rockwell | Prediction of oscillation frequencies for unstable flow past cavities[END_REF] However, it is to be pointed out that when n = 2 in Eq. ( 8) the dimensionless frequency is close to 1 (St L ≈ 0.99). Thus, the associated mode can be identified as the f -mode, defined in Eq. ( 7) with n = 1 (St L ≈ 1.12). Note also that n = 3 in Eq. ( 8) will give the estimated Strouhal number associated with f a (St L ≈ 1.56). In state II, the same can be verified for f a (St L ≈ 1) and f + (St L ≈ 1.33). This remark gives a key to explain why the usual extension of the Rossiter formula to incompressible cavity-flows may provide an empirical way of predicting dominant mode frequencies with standard values (γ =1/4, κ = 0.57) and n ≥ 2 (see for instance [START_REF] Suponitsky | On three-dimentionality and control of incompressible cavity flow[END_REF] and references therein). It also highly supports the view that modulation processes with similar characteristics could be involved in compressible and incompressible flows, even though the primary oscillation frequencies are not identically defined owing to the difference in the nature of the feedback mechanism (aeroacoustic loop or hydrodynamic forcing).

Fig. 1

 1 Fig. 1 Spectral distribution obtained for the (R=2, U=1.71m/s) cavity-flow. Signals have been recorded near the downstream corner above the cavity top.

Fig. 2

 2 Fig.2Schematic description of the possible combinations of the f a at f i frequency families when f a = 3/4f i and f a = 2f lc . Frequency coincidence are indicated by rectangles. Note that f i is very close but not equals to 3f lc (3f lc = 9/8f i ).

Fig. 3

 3 Fig.3 Spectral distribution of the (R = 1.5, U = 2.10m/s) cavity-flow. Presence of a very low-frequency peak Δ f and new sideband frequencies (f -' , f +' ). Peaks associated with a weak f b modulation process (f -, f + ) are barely discernable.

Fig. 4

 4 Fig.4 Spectral distribution of the (R = 1.5, U = 2.84m/s) cavity-flow. Dominant mode f a corresponds to mode III of the feedback cycle f lc .

Table 2

 2

Modulating frequency and fundamental oscillation frequency for different cavity-flow configurations. Reported values have been estimated from spectral distributions.

Table 3

 3 Frequency matching between subharmonics of fundamental oscillation frequency f a and right sideband frequency f + .

	Hz)	6.4	7.4	8.9	8	3.3	15.2
	f a (Hz)	17.9	20	23.7	22.9	27	53.9
	f b /f a	0.36	0.37	0.38	0.35	0.12	0.28

Table 5

 5 Frequency coincidence between cavity-flow resonances and subharmonics of the f i mode.

	15.2	24.9	38.8	49.7 Hz	53.9	78.2	92.2	107.7

f b (Hz) 1/2f i (Hz) f -(Hz) f i (Hz) f a (Hz) 2f -(Hz) f 7 (Hz) 2f a (Hz)


Alessio Guglielmi

Tom Gundersen

Lutz Strassburger

Lutz Straßburger

Breaking Paths in Atomic Flows for Classical Logic

published or not. The documents may come   L'archive ouverte pluridisciplinaire

Introduction

The investigation of the cut elimination property of logical systems is a central topic in current proof theory, and, as pointed out by Girard [START_REF] Girard | Proof Theory and Logical Complexity[END_REF], the lack of modularity is one of its main technical limitations. More precisely, the argument for showing cut elimination is usually based on heavy syntactic arguments and a tedious case analysis depending on the shape of the inference rules. A slight change in design makes the whole proof break down, and if one wishes to add some rules, one usually has to redo the whole cut elimination proof from scratch.

Our work in this paper suggests that the source of this "lack of modularity" might not be in the nature of the cut elimination property, but in the method that is used for proving it. We present here a cut elimination procedure for classical propositional logic that is independent from the shape of the logical rules. It is not based on the permutation of inference rules but on the manipulation of atomic flows [START_REF] Guglielmi | Normalisation control in deep inference via atomic flows[END_REF].

Atomic flows capture the structural skeleton of a proof and ignore the logical content. Due to their "graphical nature", atomic flows can be seen as relatives of Girard's proof nets [START_REF] Girard | Linear logic[END_REF][START_REF] Danos | The structure of multiplicatives[END_REF] and Buss' logical flow graphs [START_REF] Buss | The undecidability of k-provability[END_REF]. Proof nets have originally been proposed only for linear logic, but there have been various proposals for proof nets for classical logic with different purpose and design, e.g., by

Laurent [START_REF] Laurent | Polarized proof-nets: proof-nets for LC (extended abstract)[END_REF], by Robinson [19] and by Lamarche and Straßburger [START_REF] Lamarche | Naming proofs in classical propositional logic[END_REF]. Logical flow graphs have only been defined for classical logic, but their definition for linear logic would be literally the same. In fact, for the multiplicative fragment of linear logic (MLL) the two notions essentially coincide. This, however, is no longer the case for classical logic, which can be obtained from MLL by adding the rules for contraction and weakening. Atomic flows can be seen as a development that takes the best out of both worlds. Like proof nets they simplify proof normalization because they avoid unnecessary bureaucracy due to trivial rule permutations, and like logical flow graphs they precisely capture the information flow inside the proof. In this respect, they are very similar to the variant of proof nets discussed in [START_REF] Straßburger | From deep inference to proof nets via cut elimination[END_REF]. Since atomic flows contain for each atom occurrence every contraction and weakening that is applied to it, they can be used for controlling the size of proofs, and thus can also play a role in proof complexity (see [START_REF] Bruscoli | A quasipolynomial cut-elimination procedure in deep inference via atomic flows and threshold formulae[END_REF]).

Atomic flows are also very similar to string diagrams for representing morphisms in monoidal categories (see [START_REF] Selinger | A survey of graphical languages for monoidal categories[END_REF] for a survey). However, in (classical) logic one usually finds two dual monoidal structures and not just one. Thus, atomic flows are, in spirit, more closely related to coherence graphs in monoidal closed categories [START_REF] Kelly | Coherence in closed categories[END_REF]. Nonetheless, it should be stressed that atomic flows do not form a monoidal closed category. The following two flows are not the same and

(1)

although, during the normalization process, we wish to reduce the atomic flow on the left (a cut connected to an identity) to the atomic flow on the right (a single edge). In linear logic one can simply "pull the edges" and directly reduce the left atomic flow in (1) to the right one, whereas in classical logic this step might involve duplication of large parts of the proof. The main insight coming from atomic flows is that this duplication and the whole normalization process is independent from the logical content of the proof and independent from the design of the logical rules in use, as is discussed in [START_REF] Guglielmi | Normalisation control in deep inference via atomic flows[END_REF].

This paper is structured into three parts:

• In the first part (Sections 2 and 3) we introduce atomic flows. For doing so, we use the language of twodimensional diagrams [START_REF] Lafont | Equational reasoning with 2-dimensional diagrams[END_REF], originally due to Penrose (see also [START_REF] Joyal | The geometry of tensor calculus[END_REF]). The atomic flows as they are defined here are different from those defined in [START_REF] Guglielmi | Normalisation control in deep inference via atomic flows[END_REF], but the differences can be easily reconciled. We chose this slightly different definition for the sake of convenience when composing and manipulating atomic flows independently from their associated derivations. • In the second part (Sections 4 and 5) we first define local transformations on atomic flows that are similar to the reduction steps in linear logic proof nets or in interaction nets [START_REF] Lafont | Interaction nets[END_REF], and that have the goal to normalize the proof. However, due to the presence of contractions, the atomic flows can contain cycles that prevent these local reductions from terminating. To solve this problem, we define a global transformation on the atomic flows, called the path breaker, that treats the proof as a black box; it simply duplicates the whole proof and combines the copies. Note that this is conceptually different from the cut elimination in standard proof nets [START_REF] Girard | Linear logic[END_REF][START_REF] Laurent | Polarized proof-nets: proof-nets for LC (extended abstract)[END_REF][START_REF] Robinson | Proof nets for classical logic[END_REF], where cut reduction steps are mixed local/global: A single step involves a local cut reduction and some duplication of a part of a proof (a box or an empire). In our case the procedure consists of two phases, a purely global one followed by a purely local one. However it remains an important research objective to investigate the computational meaning of these reductions. • In the third part (Sections 6 and 7) we show how formal proofs in a deductive system are mapped to atomic flows, and how the operations on atomic flows that we defined before can be lifted to the deductive system, and thus can be used to provide a cut elimination procedure. This can be done because the symmetry of the deductive system we use allows to reduce the cut to its atomic form, in the same as it is done for the identity rule in traditional systems.

Atomic Flows

We start from a countable set A of atomic types, equipped with an involutive bijection (•) : A → A, such that for all a ∈ A, we have ā = a and ā = a. A (flow) type is a finite list of atomic types, denoted by p, q, r, . . ., and we write p | q for the list concatenation of p and q, and we write 0 for the empty list. An atomic flow φ : p → q is a two-dimensional diagram [START_REF] Lafont | Equational reasoning with 2-dimensional diagrams[END_REF], written as where p is the input type and q is the output type. The number of edges corresponds to the lengths of the lists, and each edge is labelled by the corresponding list element. For each type q, we have the identity flow id q :

• • •
We can compose atomic flows horizontally: for φ : p → q and φ ′ :

p ′ → q ′ , we get φ | φ ′ : p | p ′ → q | q ′ of the shape • • • φ • • • • • • φ ′ • • •
And we can compose atomic flows vertically: for φ : p → q and ψ : q → r, we get ψ • φ : p → r of the shape

• • • ψ • • • φ • • • For φ : p → q we have φ • id p = φ = id q • φ and φ | id 0 = φ = id 0 |φ. We also have (ψ•φ)|(ψ ′ •φ ′ ) = (ψ|ψ ′ )•(φ|φ ′ )
which is pictured as

• • • ψ • • • φ • • • • • • ψ ′ • • • φ ′ • • •
Finally, we have to give a set of generators and relations, which is done in Figures 1 and2. It is easy to see that atomic flows form a (strict) monoidal category, that we denote by AF.

The generators in Figure 1 are called ai↓ (atomic interaction down), ac↓ (atomic contraction down), aw↓ (atomic weakening down), ae (atomic exchange), aw↑ (atomic weakening up), ac↑ (atomic contraction up), and ai↑ (atomic interaction up). Note that some of them have already been studied, e.g., [START_REF] Burroni | Higher dimensional word problem[END_REF][START_REF] Lafont | Equational reasoning with 2-dimensional diagrams[END_REF][START_REF] Ehrhard | Differential interaction nets[END_REF][START_REF] Melliès | Resource modalities in tensor logic[END_REF]. The typing information in Figure 1 says that • for ai↓ (resp. ai↑) the two output edges (resp. input edges) carry opposite atomic types,

• for ac↓ (resp. ac↑) all input and output edges carry the same atomic type, • for aw↓ (resp. aw↑) there are no typing restrictions, and

= = = = = = = = = = a ā = ā a a ā = ā a
• for ae, the left input has to carry the same type as the right output, and vice versa.

When picturing an atomic flow we will omit the typing when this information is irrelevant or clear from context, as done in Figure 2. The typing is needed for two reasons: first, we need to exclude illegal flows like .

Note, that for this it would suffice to have only two types, + and -, as done in [START_REF] Guglielmi | Normalisation control in deep inference via atomic flows[END_REF]. The second reason for having the types here is the use of the flows as tool for proof transformations later in this paper.

Definition 2.1. For a given atomic flow diagram φ, we define its atomic flow graph G φ to be the directed acyclic graph whose vertices are the generators ai↓, ai↑, ac↓, ac↑, aw↓, aw↑ (i.e., all except ae) appearing in φ, whose incoming (resp. outcoming) edges are the incoming (resp. outcoming) edges of φ, and whose inner edges are downwards oriented as indicated by the flow diagram for φ. A path in φ is a path in G φ .

Remark 2.2. If we label the edges in G φ by the corresponding atomic type, then for every path in φ, all its edges carry the same label.

Remark 2.3. In [START_REF] Guglielmi | Normalisation control in deep inference via atomic flows[END_REF], atomic flows have been defined as directed graphs, as done in Definition 2.1. Indeed, G φ is the "canonical representative" of a class of flow diagrams wrt. to the equalities in Figure 2. However, with this definition the order of the input/output edges is lost, which makes the vertical composition and the mapping from formal derivations (done in Section 6) more difficult to define.

Remark 2.4. We could add the relations = and =

and their duals to the ones given in Figure 2, and this would equip every object in AF with a monoid and a comonoid structure. However, the results in this paper do not rely on that, and we decided to keep the set of relations minimal.

Notation 2.5. For making large atomic flows easier to read, we introduce the following notation:

abbreviates • • •
This can be extended to all generators: abbreviates

••• abbreviates ••• ••• ••• ••• abbreviates ••• ••• ••• abbreviates ••• ••• •••
And similarly for aw↑, ac↑, and ai↑. In each case we allow the number of edges to be 0, which then yields the empty flow. Moreover, if we label an abbreviation with atomic type a, we mean that each edge being abbreviated has type a. For instance:

a ā abbreviates a a ā ā ••• ••• ••• .
Remark 2.6. The category AF of atomic flows is strictly monoidal, but it is not compact closed, basically because we do not have an equality between the two atomic flows shown in [START_REF] Brünnler | Deep Inference and Symmetry for Classical Proofs[END_REF]. More precisely, although we can for a given atomic flow φ : p | x → q | x define the atomic flow Tr x (φ) : p → q as φ , the category AF is not traced [START_REF] Joyal | Traced monoidal categories[END_REF], because it does not obey yanking:

= Notation 2.7. A box containing some generators stands for an atomic flow generated only from these generators, and a box containing some generators crossed out stands for an atomic flow that does not contain any of these generators. For example, the two diagrams and stand for a flow that contains only ai↓ and aw↓ generators and a flow that does not contain any ac↑ and ai↑ generators, respectively.

Proposition 2.8. Every atomic flow φ can be written in the following form:

(

Proof. Let φ be given and pick an arbitrary occurrence of ai↓ inside φ. Then φ can be written as shown on the left below.

φ ′ φ ′′ = φ ′ φ ′′ (3)
The equality follows by induction on the number of vertical edges to cross, For ai↑ we proceed dually.

Definition 2.9. An atomic flow is weakly streamlined (resp., streamlined and strongly streamlined) if it can be represented as the flow on the left (resp., in the middle and on the right):

. Proposition 2.10. An atomic flow φ is weakly streamlined if and only if in G φ there is no path from an ai↓-vertex to an ai↑-vertex.

Proof. Immediate from (3), read from right to left.

Definition 2.11. An atomic flow φ is streamlined with respect to an atomic type a if in G φ there is no path from an ai↓-vertex to an ai↑-vertex, whose edges are labelled by a or ā.

Properties of Atomic Flows

In this section we show some properties of atomic flows. Apart from Proposition 3.3 they are not needed in later sections of this paper, but they lead to an interesting normal form for atomic flows (Theorem 3.8).

Remark 3.1. Lafont [START_REF] Lafont | Equational reasoning with 2-dimensional diagrams[END_REF] has shown that the generator ae together with the first two relations in Figure 2 defines the category of permutations. Definition 3.2. Let a be an atomic type. An atomic flow φ is ai-free with respect to a if φ does not contain any ai↓ generators whose outputs are typed by a and ā, and φ does not contain any ai↑ generators whose inputs are typed by a and ā. Proposition 3.3. Let a be an atomic type. Then every atomic flow φ can be written as

a ā φ ′ a ā , (4)
where φ ′ is ai-free with respect to a.

Proof. We apply the construction of the proof of Proposition 2.8 together with Remark 3.1 and the relations in the last line of Figure 2. Note that a pure atomic flow cannot contain any ai↓ nor ai↑ generators. Proposition 3.6. Every atomic flow can be written as

φ 1 • • • φ n
where φ 1 , . . . , φ n are all semi-pure.

Proof. We proceed by induction on the size of φ. If φ is a generator or id a for some atomic type a, then the result is trivial. If φ = φ ′ | φ ′′ , then by induction hypothesis we have that φ is equal to

φ ′ 1 • • • φ ′ n φ ′′ 1 • • • φ ′′ m
and the result follows from Proposition 3.4. If φ = φ ′ • φ ′′ , then by induction hypothesis we have that φ is equal to

φ ′ 1 • • • φ ′ n φ ′′ 1 • • • φ ′′ m
Because of Proposition 3.4, we can assume that the edges in φ ′ i and φ ′′ i carry the same atomic types, and by allowing the empty flow, we can assume that n = m. Then, the two exchange boxes in the middle must compose to the identity (see Remark 3.1).

Proposition 3.7. Every semi-pure atomic flow φ can be written as

φ + φ -
where φ + and φ -are both pure.

Proof. First apply Proposition 3.3 to get a flow of shape (4).

Then apply the construction of the previous proof to φ ′ . The result then follows by Remark 3.1.

Theorem 3.8. Every atomic flow can be written as

φ + 1 φ - 1 • • • φ + n φ - n where φ + 1 , φ - 1 , . . . , φ + n , φ - n are all pure.
Proof. Immediate from Propositions 3.6 and 3.7.

Local Flow Transformations

We denote by cw → the rewrite relation on atomic flows generated by the rules shown in Figure 3. Proof. The result follows from a case analysis on the critical peaks, which are:

, and ,

and their duals.

However, in general the reduction cw → is not terminating. This can easily be seen by the following example: The reason is that there can be cycles composed of paths connecting instances of the ai↓ and ai↑ generators. The purpose of the notion "weakly streamlined" (Definition 2.9) is precisely to avoid such a situation.

Theorem 4.2. Every weakly streamlined atomic flow has a unique normal form with respect to

cw →, and this normal form is strongly streamlined.

Proof. We do not show the proof of termination here since it can be found in [START_REF] Guglielmi | Normalisation control in deep inference via atomic flows[END_REF]. We only note that the crucial point is Proposition 2.10. Then, by Proposition 4.1, we have uniqueness of the normal form. Since cw → preserves the property of being weakly streamlined, and in the normal form there are no more redexes for cw →, there is no generator ai↓, aw↓, ac↓ above a generator ai↑, aw↑, ac↑.

Global Flow Transformations

The purpose of this section is to present a method for transforming any atomic flow into a weakly streamlined one. The challenge is acually to find an operation that can be lifted to proofs in a deductive system. Here, we present one that breaks paths in the flow without removing any edge. This construction can be considered to be the heart of this paper.

Definition 5.1. Let φ be an atomic flow of the shape

φ = a ā ψ a ā , (5)
where the edges of the selected ai↓ and ai↑ generators carry the same atomic types, as indicated in [START_REF] Buss | The undecidability of k-provability[END_REF], and let φ ′ be the atomic flow

φ ′ = a ā ψ a ā ā ψ a ā a ψ a ā . (6)
Then we call φ ′ a path breaker of φ with respect to a, and write φ pb → a φ ′ .

Lemma 5.2. Let φ and φ ′ be given with φ pb → a φ ′ , and let b be any atomic type. If φ is weakly streamlined with respect to b, then so is φ ′ .

Proof. The only edges connecting an output of one copy of ψ to an input of another copy of ψ are typed by a and ā. Thus, the lemma is evident for b = a and b = ā. Let us now assume b = a and proceed by contradiction. Assume there is an ai↓ generator connected to an ai↑ generator via a path typed by a. If this is inside a copy of ψ, we have a contradiction; if it passes through the a-edge between the upper and the middle copy of ψ in [START_REF] Danos | The structure of multiplicatives[END_REF], then this path connects to the ai↓ in [START_REF] Buss | The undecidability of k-provability[END_REF], which also is a contradiction. Similarly for a path typed by ā. Lemma 5.3. Let φ, ψ, and a be given as in [START_REF] Buss | The undecidability of k-provability[END_REF], and let φ pb → a φ ′ . If ψ is ai-free with respect to a, then φ ′ is weakly streamlined with respect to a.

Proof.

For not being weakly streamlined with respect to a, we would need a path connecting the upper ai↓ in (6) to the lower ai↑. However, such a path must pass through both the evidenced edge of type a and the evidenced edge of type ā, which is impossible (see Remark 2.2). Lemmas 5.2 and 5.3 justify the name path breaker for the atomic flow in [START_REF] Danos | The structure of multiplicatives[END_REF]. It breaks all paths between the upper ai↓ and the lower ai↑ in (5), and it does not introduce any new paths. Furthermore, the interior of the flow ψ is not touched.

We now have to find a way to convert any atomic flow φ into one of shape [START_REF] Buss | The undecidability of k-provability[END_REF] with ψ being ai-free with respect to a. For this, notice that by Proposition 3.3, we can write φ as

φ = a ā θ a ā , (7)
where θ is ai-free with respect to a. This can be transformed into a flow φ ′ :

φ ′ = a ā θ a āψ , (8)
which is of the desired shape and fulfills the condition of Lemma 5.3.

Definition 5.4. Let φ and φ ′ of shape ( 7) and ( 8) be given. If θ is ai-free with respect to a, then we call φ ′ a taming of φ with respect to a, and write φ tm → a φ ′ .

Lemma 5.5. Let φ and φ ′ be given with φ tm → a φ ′ , and let b be any atomic type. If φ is weakly streamlined with respect to b, then so is φ ′ . Proof. Immediate from ( 7) and (8). Definition 5.6. On atomic flows, we define the path breaking relation PB → as follows. We have φ PB → φ ′ if and only if there is a flow φ ′′ and an atomic type a, such that φ tm → a φ ′′ pb → a φ ′ and φ is not weakly streamlined with respect to a. Proof. Let φ be given. We proceed by induction on the number of atomic types occurring in φ, with respect to which φ is not weakly streamlined. Whenever we have φ PB → φ ′ , this number is decreased by one for φ ′ (by Lemmas 5.2, 5.3 and 5.5). By the constructions in ( 6) and ( 8), there is always such a φ ′ if φ is not weakly streamlined.

From Formal Deductions to Atomic Flows

We consider formulas that are generated from the set A of atomic types via the binary connectives ∧ and ∨, and the nullary connectives (constants) t and f. We interpret the duality bijection (•) : A → A on atomic types as negation and extend the definition of negation to all formulas via the usual DeMorgan laws. Sequents are finite lists of formulas, separated by comma. Formulas are denoted by A, B, C, D, and sequents are denoted by Γ, ∆. We can assign to each formula, sequent, or list of sequents its flow type by forgetting the structural information of ∧, ∨, t and f, and simply keeping the list of atomic types as they occur in the formulas. For a formula A, we denote this type by fl (A).

Similarly, we will assign flows to inference rules. Rules like In this manner, we could translate whole sequent proofs into atomic flows. However, atomic flows carry more symmetries than present in the sequent calculus. In order to be able to mirror the richness of atomic flows inside a sound and complete deductive system for classical logic, we use here a deep inference system.

⊢ Γ, A ⊢ B, ∆ ∧ --------------------- ⊢ Γ, A ∧ B, ∆ and ⊢ Γ, A, B ∨ ------------- ⊢ Γ, A ∨ B
More precisely, in this paper, we concentrate on system SKS [START_REF] Brünnler | A local system for classical logic[END_REF], whose rules are given in Figure 4. Recall that these rules can, like rewrite rules, be applied inside arbitrary contexts. For example,

[a ∨ (c ∧ [(b ∧ b) ∨ ā])] ∨ (b ∧ c) ai↑ ---------------------------------- [a ∨ (c ∧ [f ∨ ā])] ∨ (b ∧ c) is a correct application of the rule ai↑ inside the context [a ∨ (c ∧ [{•} ∨ ā])] ∨ (b ∧ c).
Note that here we allow negation only on atoms, and therefore all contexts are positive. A derivation Φ : A → B in SKS is a rewrite path from A to B using the rules in Figure 4. We call A the premise and B the conclusion of Φ. A derivation is also denoted as

A Φ ' ' ' ' 'S B .
where S is the set of inference rules used in Φ.

K{t} ai↓ ----------- K{a ∨ ā} K{A ∧ [B ∨ C]} s -------------------- K{(A ∧ B) ∨ C} K{a ∧ ā} ai↑ ----------- K{f} K{f} aw↓ ------ K{a} K{(A ∧ B) ∨ (C ∧ D)} m --------------------------- K{[A ∨ C] ∧ [B ∨ D]} K{a} aw↑ ------ K{t} K{a ∨ a} ac↓ ----------- K{a} K{f} nm f ---------- K{f ∧ f} K{t ∨ t} nmt ---------- K{t} K{a} ac↑ ----------- K{a ∧ a} K{A ∨ [B ∨ C]} =α∨ ------------------- K{[A ∨ B] ∨ C} K{A ∨ B} =σ∨ ------------ K{B ∨ A} K{A ∧ B} =σ∧ ------------ K{B ∧ A} K{A ∧ (B ∧ C)} =α∧ -------------------- K{(A ∧ B) ∧ C} K{A} = f ----------- K{A ∨ f} K{A ∨ f} = f ----------- K{A} K{t ∧ A} = t ----------- K{A} K{A} =t ----------- K{t ∧ A}
K{A ∨ A} c↓ ------------ K{A} and K{A} c↑ ------------ K{A ∧ A} are derivable in system SKS. [2] Definition 6.2. A proof of a formula A in SKS is a deriva- tion Π : t → A.
A proof is cut-free if it does not contain any instances of the rules ai↑, aw↑, or ac↑.

We refer the reader to [START_REF] Brünnler | A local system for classical logic[END_REF][START_REF] Brünnler | Deep Inference and Symmetry for Classical Proofs[END_REF] for the precise correspondence between cut-freeness in SKS and cut-freeness in the sequent calculus.

We use SKS to denote the category whose objects are the formulas and whose arrows are the derivations of SKS. This system has the additional advantage that the rules for weakening, contraction, and identity and cut are already in atomic form. Thus, it is straightforward to translate SKS derivations into atomic flows. Formally, we assign to each context K{•} a left type and a right type denoted by l(K{•}) and r(K{•}), containing the lists of atomic types appearing in K{•} on the left, respectively on the right of the hole {•}. A derivation Φ is mapped to the atomic flow φ = fl (Φ), which is the vertical composition of the atomic flows obtained from the inference steps in Φ. This translation defines a forgetful functor fl : SKS → AF. Note that this functor is independent from the fact whether the binary connectives ∧ and ∨ are bifunctors in SKS (with or without monoidal structure), whether the inference rules s and m are natural transformation, and whether = α∨ , = α∧ , etc., are isomorphisms in SKS or not (see [START_REF] Straßburger | On the axiomatisation of Boolean categories with and without medial[END_REF] for details on this issue). This functor has, however, an interesting property: for every atomic flow there is a derivation that maps to it: Theorem 6.3. For every flow φ : p → q is a derivation Φ : A → B with fl (A) = p and fl (B) = q and fl (Φ) = φ. [START_REF] Guglielmi | Normalisation control in deep inference via atomic flows[END_REF] Theorem 6.3 only works because the flows forget the structural information about ∧, ∨, t and f. If we fix φ : p → q together with A and B with fl (A) = p and fl (B) = q, we can in general not provide a derivation Φ : A → B with fl (Φ) = φ. We are thus interested in properties of atomic flows that can be lifted to derivations, in the following sense: Definition 6.4. We say that a binary relation R on atomic flows can be lifted to SKS, if R(φ, φ ′ ) implies that for every derivation Φ : A → B with fl (Φ) = φ there is a derivation Φ ′ : A → B with fl (Φ ′ ) = φ ′ .

Figure 1 :

 1 Figure 1: Generators for atomic flows

Figure 2 :

 2 Figure 2: Relations for atomic flows

Proposition 3 . 4 . 1 . 3 . 5 .

 34135 For any two atomic flows φ and ψ, we haveWhere the first equality follows by induction on the size of φ, the second by induction on the size of ψ, and the third from Remark 3.Definition An atomic flow φ is called pure if all edges carry the same atomic type. It is called semi-pure if only two different atomic types a and b occur in φ with b = ā.

Proposition 4 . 1 .

 41 rewrite relation cw → is locally confluent.

Figure 3 :

 3 Figure 3: Local rewrite rules

Theorem 5 . 7 .

 57 The relation PB → is terminating, and its normal forms are weakly streamlined.

  will be translated into the identity flows id fl(Γ) | id fl(A) | id fl(B) |id fl(∆) and id fl(Γ) |id fl(A) |id fl(B) , respectively. And the rules⊢ Γ, A, A cont ------------⊢ Γ, A and ⊢ Γ weak --------⊢ Γ, Awill be translated into flows of the shape and .

Figure 4 : 6 . 1 .

 461 Figure 4: The inference rules of system SKS

  For example, for K{•} = [a ∨ (c ∧ [{•} ∨ ā])] ∨ (b ∧ c) we have l(K{•}) = a,c and r(K{•}) = ā, b, c . Then, for each rule r of SKS we define the rule flow fl (r) as follows: we map the rules ai↓, ai↑, ac↓, ac↑, aw↓, and aw↑ to the corresponding generator (with the appropriate typing), and we map the rules = σ∨ , = σ∧ , and m to the permutation flows shown below: = σ∨ , = σ∧ : m : All remaining rules are mapped to the identity flow. Then an inference step K{A} r -------K{B} is mapped to id l(K{•}) | fl (r) | id r(K{•})

Definition 6.5. A derivation Φ : A → B is weakly streamlined (resp. streamlined, resp. strongly streamlined) if fl (Φ) is weakly streamlined (resp. streamlined, resp. strongly streamlined).

The property strongly streamlined can indeed be seen as the up-down symmetric generalization being cut-free: Proposition 6.6. Every strongly streamlined proof in SKS is cut-free.

Proof. If the premise of a derivation is t, then the upper box of its flow, as given in Definition 2.9, must be empty.

Normalizing Derivations via Atomic Flows

In this section we show that the relations defined in Sections 4 and 5 on atomic flows can be lifted to SKS. This gives us a procedure to transform an arbitrary SKS derivation first into a weakly streamlined one, and then into a strongly streamlined one, without changing premise and conclusion during the process. In other words we are going to show the following: Theorem 7.1. For every SKS derivation from A to B, there is a SKS-derivation from A to B that is strongly streamlined.

From which we get immediately the cut elimination theorem for SKS: Corollary 7.2. For every SKS-proof of A, there is a cut-free SKS-proof of A.

Proof. By Theorem 7.1 and Proposition 6.6.

It has already been shown in [START_REF] Guglielmi | Normalisation control in deep inference via atomic flows[END_REF] that the local transformation discussed in Section 4 can be lifted to SKS: Theorem 7.3. The relation cw → can be lifted to SKS. [START_REF] Guglielmi | Normalisation control in deep inference via atomic flows[END_REF] For the remainder of this section, we use the following convention: For saving space we use a new inference rule =, which stands for any derivation using only the = .. rules in Figure 4. More precisely,

Lemma 7.4. Given a context K{•} and a formula A, there exist derivations

Proof. By structural induction on K{•}. [START_REF] Straßburger | Linear Logic and Noncommutativity in the Calculus of Structures[END_REF][START_REF] Brünnler | Deep Inference and Symmetry for Classical Proofs[END_REF].

We use this lemma to show that the transformation in the proof of Proposition 2.8, which does nothing to the flows can "be lifted" to SKS in the following sense. Let Φ be a derivation. Then for every instance of the rule ai↓, we can do the transformation:

which does not change the atomic flow, and dually for ai↑. Proof. Let Φ : A → B with fl (Φ) = φ and a be given. By repeatedly applying (9) we get the derivation

with fl (Θ) = θ, from which we can obtain a derivation

whose flow is as shown in (8).

Lemma 7.6. The relation pb → a can be lifted to SKS.

Proof. Let Φ : A → B with fl (Φ) = φ and a be given. By applying [START_REF] Girard | Proof Theory and Logical Complexity[END_REF] we have a derivation

with fl (Ψ) = ψ. We also have the derivations

and

that we call Φ a and Φ ā, respectively. We can now build