Olivier Curé

David Faye
email: dfaye@igm.univ-mlv.fr

Guillaume Blin
email: gblin@univ-mlv.fr

Towards a better insight of RDF triples Ontology-guided Storage system abilities

The vision of the Semantic Web is becoming a reality with billions of RDF triples being distributed over multiple queryable endpoints (e.g. Linked Data). Although there has been a body of work on RDF triples persistent storage, it seems that, considering reasoning dependent queries, the problem of providing an efficient, in terms of performance, scalability and data redundancy, partitioning of the data is still open. In regards to recent data partitioning studies, it seems reasonable to think that data partitioning should be guided considering several directions (e.g. ontology, data, application queries). This paper proposes several contributions: describe an overview of what a roadmap for data partitioning for RDF data efficient and persistent storage should contain, present some preliminary results and analysis on the particular case of ontology-guided (property hierarchy) partitioning and finally introduce a set of semantic query rewriting rules to support querying RDF data needing OWL inferences.

Introduction

The generally encountered use of ontologies consists in performing data inferences and validation using a Semantic Web compliant reasoner. The corresponding reasoning mechanism can be used to generate a set of queries executed over the appropriate data sets. For example, this approach was designed in a medical application [START_REF] Curé | Semi-automatic Data Migration in a Self-medication Knowledge-based System[END_REF] where inferences on chemical molecules were needed to highlight contra indications, side effects of pharmaceutical products. As mentioned in [START_REF] Curé | Semi-automatic Data Migration in a Self-medication Knowledge-based System[END_REF], results of queries with both inference on property (i.e. rdf:property) and concept (i.e. rdf:class) hierarchies are required by the application as well as by data quality or data exchange external tools.

In regards to large ontologies (e.g. OpenGalen or SNOMED in the medical domain) and data sets (e.g. Linked Data), providing efficient performances to reasoning dependent queries is an important issue. We believe that to enable efficient response time to such queries, one has to give a special attention to the storage system associated to the triples. In fact, RDF is basically a data model and its recommendation does not guide to a preferred storage solution. The related work about RDF data management systems can be subdivided into two categories: the ones involving a mapping to a Relational DataBase Management System (RDBMS) and the ones that do not. In this paper, we do not focus on the latter one.

A set of techniques have been proposed for storing RDF data in relational databases. Several research groups think that this is likely the best performing approach for their persistent data store, since a great amount of work has been done on making relational systems efficient, extremely scalable and robust. Efficient storage of RDF data has already been discussed in the literature with different physical organization techniques based on partitioning (cf. Figure 1). On one hand, there exists tools such as Sesame [START_REF] Broekstra | Sesame: A Generic Architecture for Storing and Querying RDF and RDF Schema[END_REF], Jena [START_REF] Wilkinson | Efficient RDF Storage and Retrieval in Jena2[END_REF], Oracle [START_REF] Chong | An efficient SQL-based RDF querying scheme[END_REF] and 3store [START_REF] Harris | 3Store Efficient bulk RDF storage[END_REF] which rely on a straightforward mapping of RDF into an RDBMScalled triple table approach. Each RDF statement of the form (subject, predicate, object) is stored as an entry of one large table with a three-columns schema (i.e. a column for each the subject, predicate and object ). Indexes are then added for each of the columns in order to make joins less expensive. However, since the collection of triples are stored in one single table, the queries may be very slow to execute. Indeed when the number of triples scales, the table may exceed memory size (inducing costly disk-RAM transfers). Nevertheless, simple statement-based queries can be satisfactorily processed by such systems, although they do not represent the most important way of querying RDF data. Still, this storage system scales poorly since complex queries with multiple triple patterns require many self-joins over this single large table as pointed out in [START_REF] Wilkinson | Efficient RDF Storage and Retrieval in Jena2[END_REF][START_REF] Weiss | Hexastore : sextuple indexing for semantic web data management[END_REF][START_REF] Kolas | Efficient Linked-list RDF Indexing in Parliament[END_REF].

Whereas this specific approach does not use partitioning at all, on the other hand, some recent research highlighted two efficient main trends depending on the information one uses to guide the partitioning: guided by (1) the underlying ontology or (2) the data itself. Intuitively, one would expect that a well suited data partitioning will induce a better response time to queries (at least select ones). Indeed, data partitioning will allow queries to be made on smaller sets of entries which, given an adapted RDF data clustering, should be faster. The counterpart of this storage system will be some possible worst performance for data updates.

Considering partitioning guided by the underlying ontology, most of the recent works focus only on the property hierarchy. Among others, the vertical partitioning approach suggested by Abadi et al. in [START_REF] Abadi | Scalable semantic web data management using vertical partitioning[END_REF] is to be mentioned. In this approach, using a fully decomposed storage model (DSM) [START_REF] Copeland | A decomposition storage model[END_REF], the RDF data is divided into n two columns (subject,object ) tables where n is the number of unique predicates in the data. Each of these resulting tables represents a particular predicate, with an entry for each statement of the data containing the corresponding predicate. Sorting the tables according to the subject allows fast merge joins for reconstructing information about multiple predicates for subsets of subjects. The vertically partitioned approach offers a support for multi-valued attributes. Indeed, if a subject has more than one object for a given predicate, each distinct value is listed in a successive row in the corresponding table. For a given query, only the predicates involved in that query need to be read. Finally, the building of the two-columns tables can be done easily -without a clustering algorithm -by only browsing and relying on the property hierarchy of the data. As previously mentioned, as a counterpart, data updates/insertions may be slower in vertically partitioned tables rather than triple ones since multiple tables need to be accessed for statement about the same subject.

In [START_REF] Abadi | Scalable semantic web data management using vertical partitioning[END_REF], the authors described how a column-oriented DBMS [START_REF] Stonebraker | C-store: a column-oriented DBMS[END_REF] (i.e., a DBMS designed especially for the vertically partitioned case, as opposed to a roworiented DBMS, gaining benefits of compressibility [START_REF] Abadi | Integrating compression and execution in column-oriented database systems[END_REF] and performance [START_REF] Abadi | Materialization Strategies in a Column-Oriented DBMS[END_REF]) can be extended to implement the vertically partitioned approach. Roughly, this is done by storing tables as collections of columns rather than collections of rows. The goal is to avoid transferring entire rows into memory from disk, like in roworiented databases, if only a few attributes are accessed per query. Consequently, in column oriented databases only those columns relevant to a query will be read. Note that, in an independent evaluation [START_REF] Sidirourgos | Column-store support for RDF data management: not all swans are white[END_REF] of the techniques presented in [START_REF] Abadi | Scalable semantic web data management using vertical partitioning[END_REF], the authors pointed out potential scalability problems for the vertically partitioned approach when the number of predicates in an RDF data set is high. With a larger number of predicates, the triple table solution manages to outperform the vertically partitioned one.

Depending on the type of reasoning dependent queries, it may be more efficient to consider an intermediate model between triple tables and vertical partitioning approaches. A first contribution of this work will be to provide an analysis of the effectiveness of an intermediate approach -also based on property hierarchy -where a table is created only for top predicates. Another interesting track (for future investigation), would be to consider partitioning the data regarding the concept hierarchy rather than the property one and/or considering both. To the best of our knowledge, such study has not yet been conducted. Considering data guided partitioning, one may distinguish two types of guides. First, one may consider that the RDF data itself may induce an efficient partitioning. The main achievement for this type of guide is the property table technique which was introduced later on [START_REF] Wilkinson | Jena property table implementation[END_REF] for improving RDF data organization by allowing multiple triple patterns referencing the same subject to be retrieved without an expensive join. In this model, RDF tables are physically stored in a representation closer to traditional relational schemas in order to speed up the queries over the triple stores [START_REF] Wilkinson | Jena property table implementation[END_REF][START_REF] Chong | An efficient SQL-based RDF querying scheme[END_REF]. Indeed, each named table includes a subject and several fixed predicates. The main idea is to discover clusters of subjects often appearing with the same set of predicates.

A variant of the property table named property-class table uses the rdf:type of subjects to cluster similar sets of subjects together in the same table. The immediate consequence is that self-joins on the subject column can be avoided. However, the property table technique has the drawback of generating many NULL values since, for a given cluster, not all predicates will be defined for all subjects. A second disadvantage of property table is that multi-valued attributes, that are furthermore frequent in RDF data, are hard to express. In a data model without a fixed schema like RDF, it is common to seek for all defined predicates of a given subject, which, in the property table approach, requires scanning all tables.

Note that, in this approach, adding predicates requires also to add new tables; which is clearly a limitation for applications dealing with arbitrary RDF content. Thus the flexibility in schema is lost and this approach limits the benefits of using RDF. Moreover, queries with triples patterns that involve multiple property tables are still expensive because they may require many union clauses and joins to combine data from several tables and consequently complicate query translation and plan generation. In summary, property tables are poorly used because of their complexity and inability to handle multi-valued attributes. Another type of guide which may worth being studied is queries. Indeed, one may consider an evolutive storage schema in regards to recent queries made on the data. To the best of our knowledge, this track of research has also not been considered yet.

In this article, we will concentrate on giving some preliminary results (on medium-sized datasets) on an intermediate property hierarchy based approach (that will need to be pursued) -namely RDF Ontology-guided Storage system (roStore). After presenting the general approach (Section 2), we will, in Section 3, evaluate the efficiency difference with vertically partitioning on the LUBM benchmark over both row and column oriented databases and on some extra specific queries highlighting limits of vertically partitioning.

The roStore approach

As a first step to an efficient RDF storage road map, we propose an intermediate ontology-guided approach -namely roStore -which lies between the two extremes: triple and vertically partitioned tables. The aim of this approach is to try to analyse the efficiency of a compromise approach where less partitions are used. Intuitively, such physical organization will take benefits of requiring less joins in practical queries and with less risk of unmappable table in memory.

As already mentioned, we believe that there should not be a unique generic solution to RDF storage and that depending on the data itself, the underlying ontology, application queries, better performance may be obtained by considering alternative and several dedicated approaches. The major aim of roStore is to provide some clue of this belief. We will demonstrate that roStore is one of them and may, in specific cases, induce better efficiency. In this context, we consider roStore as one among other interesting physical organizations based on property hierarchy that should be present in the RDF storage road map.

Our storage approach derives from the vertically partitioned one and extends this last by putting back together into a single table data related to a topproperty of a property hierarchy. Given a hierarchy, we say that a predicate is a top-property if it is only an rdf:subPropertyOf of itself. For each such topproperty P T , a three-columns table is created by ( 1) merging all the two-columns tables corresponding to predicates being rdf:subPropertyOf P T and (2) adding a third column indicating from which predicate the entry (subject, object) was retrieved (cf. Figure 2).

Let us first notice that, providing with this definition, any predicate that is not an rdf:subPropertyOf of a top-property will still be stored in a twocolumns table. This induces an insignificant expense of the space complexity of this novel approach. Moreover, in case of a cyclic property hierarchy, all predicates are necessarily all semantically equivalent. Hence selecting a single canonical predicate and rewriting triples accordingly is sufficient. Despite the fact that considering top-property seems to be the most natural, one may, depending on the topology of the hierarchy, define other physical organizations inducing better performance too for specific cases. Our preliminiary results demonstrate that an evolutive physical organizations guided by the queries may be efficient. The main impact of merging some tables is obtaining better performance of queries requiring joins over predicates belonging to the same "sub-hierarchy" of the property hierarchy. This is typically the case when one wants to retrieve all the information concerning a family of predicates of the property hierarchy; since they will be quite related. In the following, we will denote by vpStore (resp. roStore) the vertically partitioned (resp. our) approach.

Example 1: Let us consider a small data set (Figure 2b) defined over a given property hierarchy (Figure 2a). With vpStore, the triples would be distributed over six different tables as displayed in Figure 2c. Comparatively, in roStore, one obtains only two different tables (Figure 2d): a single relation named after the top-property pa and a relation named after the property pf.

Thus, if we consider an ontology consisting of n (e.g. 2 in our example) property hierarchies with an average of k (e.g. 3 in our example) properties in each hierarchy, the roStore approach will store k times less tables than a vpStore approach. Moreover, with this approach it is very unlikely to generate tables with no tuples (e.g. pd with vpStore in Example 1). Moreover, the set of tuples stored is the same as in vpStore and only their distribution over database tables is modified (i.e. physical organization).

We now consider the following query: one wants to retrieve all objects involved in a triple with a predicate of the pa hierarchy. Considering vpStore's physical design, the following SQL query is needed: while the same query is answered far more efficiently considering roStore's physical design with: SELECT object FROM pa; Such example highlights the kind of (1) reasoning dependent queries and (2) corresponding improvement one can obtain by using an intermediate physical organization such as roStore over vpStore when property hierarchies are present in the ontology.

In order to analyse more deeply the corresponding efficiency of roStore approach, we will first compare it to the vpStore approach on the LUBM benchmark and on some specific queries that highlight limits of vertically partitioning. In this work, as a first contribution, we focus only on select queries. We are currently investigating the possibly negative impact of partitioning on update queries. As far as we went on this track, it seems that this impact is reasonable. First, we will discuss how to take benefits of the ontology based structure of the data without the needs of heavy inference mechanisms.

Indeed, compared to classical table schema, the ontology is far more meaningfull and can thus be used to enhance the performance even without needing knowledge inference. We propose an efficient use of Semantic Query Rewriting (SQR) adaptable to and usable by most of the data storage approaches. Our semantic query rewriting aims are, first, to guarantee the exhaustiveness of results returned when requiring data that should include rdf:subClassOf and rdf:subPropertyOf; and, a query validation mechanism simply based on the domain and range information related to predicates, i.e. resp. rdfs:domain and rdfs:range. One has to note that the mechanisms we propose are not really needing heavy reasoning nor data inference mechanisms. Indeed, they can be considered as an efficient use of the right-away available information of the ontology.

The semantic aspect of this rewriting is provided by a thorough usage of the OWL entailment mechanism, on one hand, to detect if the answer set of a query will be empty or not, on the other hand, to optimize query in order to guarantee exhaustiveness of the solution returned. The rules can be decomposed into two sets: (i) a set of rules, denoted subsume, dealing with concept and property subsumptions; (ii) a set of rules, denoted propertyCheck, dealing with the rdfs:range and rdfs:domain of a given predicate. The rules processed by the subsume procedure are using the OWL inferences to compute all the subconcepts (resp. sub-properties) of a given concept (resp. property). In fact, the query studied in Example 1 was already using the subsume procedure.

Example 2: Consider that the rdfs:range of the predicate pb of Example 1 is of rdf:type ClassA which is the top-concept in the following concept hierarchy:

ClassC ⊑ ClassA, ClassB ⊑ ClassA and ClassC ⊑ ¬ClassB
That is ClassA has two sub-concepts which are disjoint. Consider a query asking for all subjects and objects of triples where pb is the predicate and all subjects belong to the ClassA hierarchy. Using subsume, the query can be translated in the following SQL query: SELECT subject, object FROM pa, type WHERE type.subject = pa.subject AND pa.property = 'pb' AND type.object IN ('ClassA','ClassB', 'ClassC'); Thus this approach enables to generate a singe SQL query whatever the size of the concept hierarchy is. Note that it also applies to the property hierarchy.

The rules of propertyCheck are being processed as follows: first the SPARQL query is parsed and for each predicate explicitly mentioned in the query with a typed (rdf:type) subject or object, we store a structure containing the predicate name and the rdf:type of the subject and/or object. Then for each subject (resp. object ) in the structure, we search if there is a direct or indirect (via subsumptions) correspondence with the type of the rdfs:domain (resp. rdfs:range) defined in the ontology for this property. The query is satisfiable since there is a model where its answer set is not empty. Anyhow, the query can be optimized. In fact, it is not necessary to check the rdf:type of the object because it corresponds exactly to the one defined as rdf:range in the ontology. Thus this query is rewritten in: SELECT ?s ?o WHERE {?s :diseaseContraIndication ?o.} which once translated into SQL does not require any join and will thus perform far more efficiently than the orginal query. Note that this simplification does not work for property with multiple-range/domain. Those examples demonstrate that it is worth to efficiently use the basic knowledge available directly in the concept and property hierarchies.

Evaluation

Experimental settings

All our experiments have been conducted on four synthetic databases. They all have been generated from the Lehigh University Benchmark (LUBM) [START_REF] Guo | LUBM: A benchmark for owl knowledge base systems[END_REF] which has been developed to facilitate the evaluation of Semantic Web repositories in a standard and systematic way. The RDF data sets generated with LUBM all commit to a single realistic ontology dealing with the university domain. This ontology is composed of 43 concepts, 25 object properties (i.e. relating objects to objects) and 7 data type properties (relating objects to literals). This ontology serves as the schema underlying the four data sets we have created. This is an important requisite for our evaluation since our set of queries will be executed on all data sets in order to provide information on scalability issues. Table 1 summarizes the main characteristics of these data sets in terms of overall number of triples, number of concept and property instances. The RDF data sets are later translated into the different physical organization models we would like to evaluate. They are decomposed into the two main approaches vpStore and roStore. In order to emphasize the efficiency of our solution on queries needing reasoning, we had to test these settings in a context similar to [START_REF] Abadi | Scalable semantic web data management using vertical partitioning[END_REF]. More precisely, we evaluated each approach on a row store and a column store RDBMS. This yields the four following approaches: vpStore resp. on a row (vpRStore) and column (vpCStore) store and roStore resp. on a row (roRStore) and column (roCStore) store. Hence a total of sixteen databases are generated (each data set is implemented on each physical approach).

We have selected postgreSQL and MonetDB as the RDBMS resp. for the row-oriented and the column-oriented databases. We retained MonetDB instead of C-store (the column store used for evaluation in [START_REF] Abadi | Scalable semantic web data management using vertical partitioning[END_REF]) essentially due to (1) the lack of maintenance of the latter one, ( 2) the open-source licence of MonetDB and (3) the fact that MonetDB is considered state of the art in column-oriented databases. The tests were run on MonetDB server version 5 and postgreSQL version 8.3.1. The benchmarking system is an Intel Pentium 4 (2.8 GHz) operated by a Linux Ubuntu 9.10, with 512 Mbytes of memory, 1MB L2 cache and one disk of 60 Gbyte spinning at 7200rpm. The disk can read cold data at a rate of approximatively 55MB/sec.

For the vpRStore, there is a clustered B+ tree index on the subject and an unclustered B+ tree on the object. Similarly, for the roRStore, a clustered B+ tree index is created on the property column and unclustered B+ trees on the subject and object. As noted in [START_REF] Sidirourgos | Column-store support for RDF data management: not all swans are white[END_REF], MonetDB does not include user defined indices. Hence, we relied on the ordering of the data on property, subject and object values. More precisely, any two columns table of roCStore and vpCStore is ordered on subject and object while any three columns table (of roCStore) is ordered on property, subject and object.

Our evaluation contains fifteen queries out of which eleven are coming from the LUBM benchmark and four tackling the LUBM ontology to evaluate some particular aspects of roStore. An interesting aspect using LUBM Benchmark queries is that do not aim to emphasize on the performances of a given storage model. Moreover, these queries tackle a wide range of possibilities on volume of input (number of tuples retrieved) and selectivity rate (i.e. number of conditions in the WHERE clause of a query). Among the eleven evaluated queries, three do not require any form of reasoning (#1, #2 and #14) and the eight remaining queries can be divided in two groups whether they are involving reasoning on the concept hierarchy (#3,#4,#6,#7,#9,#10) or both concept/property hierarchies (#5,#8). We now present the purpose of each of these queries:

Q1: retrieves instances of the GraduateStudent class who have taken the course http://www.Department0.University0.edu/GraduateCourse0.

Q2: retrieves three instances of respectively the GraduateStudent, University and Department concepts for those students that are member of a department, this department is a sub-organization of a University and this student has an undergraduate degree from this university.

Q3: selects all kinds of publications which have been authored by a given assistant professor.

Q4: retrieves all kinds of professors, their name, email address and telephone number for those professors working for a given department.

Q5: the result contains instances of the Person concept hierarchy for those persons that are related to a given department by either the memberOf, workingFor or headOf properties.

Q6: displays URIs of instances of the Student concept hierarchy. Q7: retrieves instances of all kind of students and all kinds of courses for courses that are related by the takesCourse property for those courses that are taught by a given professor.

Q8: displays instances of all kinds of students with their email addresses and department instances of a given university these students are member of.

Q9: the retrieved dataset contains instances of the Student, Faculty and Course concept hierarchies for those students that are advised by faculties, have taken some courses taught by those faculties.

Q10: selects instances of all the Student class hierarchy who have taken a given course.

Q14: selects all undergraduate students. We have introduced Q15 to emphasize roStore performances when values are needed for a property hierarchy. In fact, it retrieves all subjects involved in triples where the predicate is one of the properties of the memberOf property hierarchy, i.e. memberOf, headOf and worksFor. This query is similar to Q5 but does not refer to any concepts.

Finally, the following three queries aim to highlight the efficiency of our SQR approach. Q16: selects the subject and object in triples where the predicate is teacherOf and subject is of rdf:type AdministrativeStaff. This query returns an empty answer set since the rdfs:domain of teacherOf is the Faculty concept which is disjoint with AdministrativeStaff. In the next section, we confront the performances of this query to the simple detection of unsatisfiability of our SQR solution.

Q17: selects the subject and the object in triples where the predicate is teacherOf and subject is of rdf:type Faculty. This query requires a join.

Q18: has the same purpose as Q17 but exploits one of our rewriting rules to improve its performances. In fact, the join in Q17 is not necessary if one knows that the rdfs:domain of teacherOf is the concept Faculty.

In the experiments, we will store the LUBM ontology in main-memory and perform reasoning using the Jena framework. We provide more details concerning the experimental settings and results on the following web site: http://sites.google.com/site/wwwrostore.

Experimental results

The results presented in this section correspond to the average of 5 hot runs (i.e. repeated runs of the same query without stopping the DBMS) of real time (i.e. execution time of a query defined as the wall clock passed between the server receiving the query and before returning the results to the client) executions. All performance times, except for query Q16 and Q17, include the time needed to perform the inferences. Finally, in order to highlight the differences in terms of performances between the various approaches, we either present the results in bar or line diagrams. Analysis of Q1. Not surprisingly, column stores outperform row stores. Indeed, the results will only contain a unique column which will clearly benefit column store advantage. Moreover, since the query does not involve sub-properties, the performances of vpStore and roStore are quite similar. Analysis of Q2. This time, the row stores are more efficient than the column ones. The results require, in this case, to retrieve two columns of three tables, hence in a row store both columns will be transfered from the hard drive to main memory in a single step while two transfers will be needed for column stores. Moreover, two out of these three tables corresponds to predicates being part of a group of related predicates in the property hierarchies, namely memberOf and undergraduateDegreeFrom. Since we voluntarily decided to perform no inferences on these two predicates3 (i.e. not including sub-properties in the query), it is not surprising that vpStore outperforms roStore since each predicate corresponds in the vpStore to a table. Analysis of Q3. Despite the fact that this query has a similar structure as Q1 (i.e. only two triples are present in the WHERE clause), it requires to retrieve all concepts of a wide hierarchy. Due to the ordered organization of tuples, column stores outperform row ones which rely on indices and on a less effective I/O transfers. In a similar manner to Q1, the difference between vpStore and roStore is not significant. Analysis of Q4. Once again, in this query, we do not use inference on the worksFor predicate to include results on sub-properties of this last. This is motivated by the will to emphasize on the weaknesses of the roStore approach. As expected, vpStore is, in this context, outperforming roStore. In fact, even vpRStore is outperforming roCStore; which can be induced by the high selectivity nature of the query (four attributes in result set). Analysis of Q5. Due to the exploitation of the sub-properties of the predicate memberOf in this query, it is not surprising that roStore outperforms vpStore. Indeed in vpStore, the results of the query comes from the union of three distinct queries (one for each predicates involved) while roStore only requires a single query. Analysis of Q6. This query retrieves the subjects from a two columns table (i.e. type). Because the column stores primarily order these relations on the subject, they are more efficient than their row store counterparts. This is due to better I/O efficiency. Similarly to Q3, the roStore approach outperforms vpStore. Analysis of Q7. Again query processes in roStore (resp. column store) is more efficient than vpStore (resp. row store). The reasons are similar to the ones for Q3.

Analysis of Q8. The analysis of the results for this query confirm the ones of Q5. Analysis of Q9. This query does not require inferences on property hierarchies but some on several concept ones. As seen previously, in this situation column stores is more efficient than row stores. On column stores, vpStore and roStore have close performance results, with roStore slighty better than vpStore. Analysis of Q10. The results are similar to Q9. Analysis of Q14. This query has large input and low selectivity with no inferences. As expected, roCStore is faster than vpCstore which is more efficient than roRStore; the less effective being vpRStore. Note that this is due to distinguished variable being placed at the subject position of the only triple of the WHERE clause. A similar query pattern with the distinguished variable mapped to the object position of a triple would emphasize the superiority of the vpStore approach. Analysis of Q15. This query clearly demonstrates the efficiency of roStore over vpStore. Even the row oriented roStore outperforms the column oriented vpStore. This is due to the presence of UNION SQL operators in the queries executed on the vpStore while roStore only requires a complete scan of the tuples of one table. Analysis of Q16, Q17 and Q18. Finally, queries Q16, Q17 and Q18 emphasize the importance of reasoning over the ontology before executing queries over any of the store solutions. Figure 16 displays the duration times for all databases, ranging from approximately 42ms (column store with 1 university) to 1450ms (row store with 10 universities). This can be considered rather long to propose an empty answer set since, according to the ontology, the query is incoherent.

Comparatively, the propertyCheck method we have implemented needs an average time of 1ms to reply that the query is coherent or not. Hence, a system implemented on top of an OWL compliant reasoner is able to determine almost instantly if the answer set is empty. Moreover, it could also provide some explanations concerning the inconsistency of the query. We believe that such optimization are quite useful especially when end-users are not confident with all the details of a given ontology. The performance results of Q17 and Q18 are provided together in Figure 17 in order to highlight their comparisons. The purpose of Q17 and Q18 is to emphasize the importance of analyzing predicate rdfs:domain and rdfs:range in a property table approach. The execution of Q17 does not perform any optimization while Q18 checks that the concept Faculty is the rdfs:domain of the teacherOf predicate and hence a join to the rdf:type relation is not necessary. Several conclusions can be drawn from our evaluation. Considering the adoption of a database solution, we confirm the evaluations of [START_REF] Abadi | Scalable semantic web data management using vertical partitioning[END_REF] and [START_REF] Sidirourgos | Column-store support for RDF data management: not all swans are white[END_REF] stating that column stores outperform row stores for RDF triple storage. The only exception in our experiments consists in Q2 which is rather due to the partitioning approach.

Concerning the partitioning approach, all our intuitions were confirmed by this evaluation. That is roStore outperforms vpStore whenever queries retrieve information from triples where properties belong a given property hierarchy (e.g. Q5 and Q15). On the contrary, vpStore is more efficient than roStore where only a subset of the properties of a property hierarchy are necessary to reply to a query (e.g. Q2). This result was expected since the roStore approach then requires to add additional conditions on the properties one wants to retrieve from a 'top property' relation.

Finally, the SQR approach seems to be quite useful since it does not slow down the processing of satisfiable queries and enables to detect unsatisfiable queries efficiently (e.g. Q17 and Q18). Anyhow, we consider that more evaluations need to be conducted on larger ontologies to confirm these results.

Conclusion

The first contribution of this paper is to show that depending on the type of applications and queries asked to the RDF triple stores, different partitioning approaches can be considered. Between the two extremes of triple and vertical partitioning, we introduced the roStore approach which is particularly advantageous for a certain class of queries, i.e. those relying on deep property hierarchies (e.g. the OpenGalen ontology contains a property hierarchy of depth 6). Moreover, this novel approach is a simple extension to the existing RDF column store work and can thus be easily adopted by other RDF stores. A second contribution of this work is to propose a semantic query rewritting solution that can be adopted by most of the RDF triples we have presented in this paper (triples tables, vertical partitioning, roStore, property-class tables). This approach seems promising since it can be quite useful to detect unsatisfiable queries and optimizing other queries by analyzing property domains and ranges.

Our list of future works is large since we consider that several investigations need to be performed to complete the road map on efficient and persistent RDF triple storage. The first directions we would like to follow are ontology schema evolution in roStore (e.g. a new property hierarchy emerges or is removed from the ontology) and the consideration of concept hierarchies at the storage and querying levels.

Fig. 2 .

 2 Fig. 2. Storage comparison of vpStore and roStore

Example 3 :Fig. 3 .

 33 Fig. 3. Sample of the contraIndication relation

Fig. 4 .Fig. 5 .Fig. 6 .Fig. 7 .

 4567 Fig. 4. Performance results for Q1

Fig. 8 .Fig. 9 .Fig. 10 .Fig. 11 .

 891011 Fig. 8. Performance results for Q5

Fig. 12 . 13 .Fig. 14 .Fig. 15 .

 12131415 Fig. 12. Performance results for Q9

Fig. 16 .Fig. 17 .

 1617 Fig. 16. Performance results for Q16

Table 1 .

 1 Synthetic data sets

	DB name # Universities # Concept instances # Property instances # Triples
	lubm1	1	15195	60859	100868
	lubm2	2	62848	189553	236336
	lubm5	5	114535	456137	643435
	lubm10	10	263427	1052895	1296940

since it will be specifically considered in query Q15.


Guillaume Blin
email: blin@lina.univ-nantes.fr

Romeo Rizzi
email: romeo.rizzi@unitn.it

Conserved Interval Distance Computation between Non-trivial Genomes ⋆

Keywords: Conserved interval distance, Exemplar string, Matching, Computational complexity, Longest Common Substring, Duplicated genes

. In this paper, we study the time complexity of the conserved interval distance computation considering duplicated genes using both those two strategies.

Introduction

In comparative genomics, gene order study in a set of organisms has been intensively led essentially in phylogenetic research field [START_REF] Bourque | Reconstructing the genomic architecture of ancestral mammals: lessons from human, mouse and rat genomes[END_REF][START_REF] Blanchette | Gene order breakpoint evidence in animal mitochondrial phylogeny[END_REF][START_REF] Bourque | Genome-scale evolution: Reconstructing gene orders in the ancestral species[END_REF]. Most of the methods associated to gene order study are based on a distance computation. This distance has to reflect the number of genetic operations needed to transform a source genome into a target genome. For this purpose, a set of distances and associated methods have been developed in the past decade. Among others, we can mention three intensively studied distances: edit [START_REF] Marron | Genomic distances under deletions and inversions[END_REF][START_REF] Swenson | Approximating the true evolutionary distance between two genomes[END_REF], breakpoint [START_REF] Blin | The breakpoints distance for signed sequences[END_REF], and conserved interval [START_REF] Bergeron | On the similarity of sets of permutations and its applications to genome comparison[END_REF] distances.

From an algorithmic point, distances can roughly be defined as follows: given a set F of gene families, two genomes G and H, represented as sequences of signed elements (genes) from F, and a set of evolutionary operations that operate on segments of genes (like reversals, transpositions, insertions, duplications, deletions for example), the distance between G and H is the minimum number of operations needed to transform G into H.

Until recently, the assumption that in a genome there is no copy of a gene was a requirement of most of the methods associated to gene order study. This restriction reduces the problem to the comparison of signed permutations [START_REF] Gascuel | Mathematics of Evolution and Phylogeny[END_REF]. It is known that this assumption is very restrictive and is only justified in small virus genomes, therefore one needs to consider genomes containing duplicated genes.

In [START_REF] Sankoff | Genome rearrangement with gene families[END_REF], Sankoff has proposed a method to select, from the set of copies of a gene, the common ancestor gene such that the distance between the reduced genomes is minimized. In [START_REF] Bryant | The complexity of calculating exemplar distances[END_REF], Bryant proved that the corresponding problem, so called exemplar string, was NP-complete for two distances: the signed reversals and the breakpoint distances. Marron et al. have proposed in [START_REF] Swenson | Approximating the true evolutionary distance between two genomes[END_REF] methods relying on a matching between genes of two genomes. Provided with a matching between genes of the two genomes, one can, by a rewriting of the genomes according to the matching, create genomes without duplicated genes and solve the reduced problem.

In this paper, we investigate the complexity of both the use of exemplar strategy and of matchings to compute the conserved interval distance between genomes containing duplicated genes. First we prove that the use of both strategies unfortunately induces NP-completeness. To overstep NP-hardness of problems, many techniques have been developed: heuristic, parameterized complexity and approximation algorithm. For biological problems those alternative techniques have been intensively used, since in most cases specific properties of the problem are not taken into account in the NP-hardness proof.

This paper is organized as follows. After presenting some preliminaries in Section 2, we show in Section 3 that both the use of exemplar strategy and of matchings to compute the conserved interval distance between genomes containing duplicated genes induces NP-completeness. Then in Section 4, we present a heuristic approach based on the Longest Common Substring which have been implemented and tested over a set of 20 bacteria.

Preliminaries

Genomes, gene families and gene. Following terminology introduced in [START_REF] Sankoff | Genome rearrangement with gene families[END_REF], a genome G is a sequence of elements of an alphabet F (referred as the set of gene families) such that each element is provided with a sign (+ or -). Each occurrence of a gene family from F in G is called a gene. Given a genome G = g 1 g 2 . . . g n , we say that gene g i precedes gene g i+1 . For two genomes G and H and a gene family f , the number of occurrences of f in G and H is called the cardinality of family f . A gene family f is said to be trivial if f has cardinality exactly 1 or 2. Otherwise, f is said to be non-trivial. A gene belonging to a trivial (resp. non-trivial) family is said to be trivial (resp. non-trivial). A segment (i.e. a substring) of G that contains only non-trivial genes is called a non-trivial segment. We say that two genomes G and H are balanced if, for any gene family f , there are as many occurrences of f in G as in H.

Conserved interval, conserved interval distance. Following terminology introduced in [START_REF] Bergeron | On the similarity of sets of permutations and its applications to genome comparison[END_REF], given a set of n genomes G and two genes a, b ∈ F, an interval [a, b] is a conserved interval of G if (1) either a precedes b, or -b precedes -a in each genome of G and (2) the set of unsigned genes (i.e. not considering signs) appearing between genes a and b is the same for all genomes of G. Given two set of genomes G and H, the conserved interval distance between G and H is defined by

d(G, H) = N G + N H -2N G S H where N G (resp. N H and N G S H
) is the number of conserved intervals in G (resp. H and G H). For example, let G = {G 1 , G 2 } and H = {H 1 , H 2 } be two sets of genomes where G 1 and G 2 are as above and

H 1 = a e -f b g c -d h and H 2 = a f -c -g b -e -d h.
We obtain d(G, H) = 7 + 3 -4 = 6. In the rest of the paper, for readability, we denote the conserved interval distance between two singleton sets d({G}, {H}) by d(G, H).

Gene matching. Let G = g 1 g 2 . . . g n and H = h 1 h 2 . . . h m be two genomes on F. A gene matching M between G and H is a maximal matching between genes of G and H such that, for every pair (g i , h j ) ∈ M, g i and h j belong to the same family. By maximal matching, we mean that for any gene family f , it is forbidden to have at the same time an occurrence of f in G and one in H that do not belong to M. It follows from the maximality condition of matchings that in any matching M between balanced genomes G and H, every gene of G is matched to a gene of H and conversely. Given a matching M and a segment

s = s 1 s 2 . . . s m of G if, for all 1 ≤ i ≤ m, (s i , t i ) ∈ M such that: (1) s i = t i and t = t 1 t 2 . . . t m is a segment of H or (2) s i = -t i and t = t m t m-1 . . . t 1 is a segment of H

Hardness results

In this section, we first prove that, even if there is no non-trivial segment containing more than one gene, Exemplar Conserved Interval Distance (ECID) problem (formalized hereafter) is NP-complete. Then, we prove that, even with just one non-trivial gene family, the problem of finding a Minimum Conserved Interval Matching (MCIM) is NP-complete. This last result is based on a polynomial time reduction which is inspired from the one presented in [START_REF] Blin | The breakpoints distance for signed sequences[END_REF] which proves that a connected problem, Minimum Breakpoint Matching, is NPcomplete.

Theorem 1. Exemplar Conserved Interval Distance problem is NPcomplete even when all non trivial segments are composed of only one duplicated gene.

To prove the correctness of Theorem 1, we provide a polynomial time reduction from the NP-complete problem Minimum Set Cover [START_REF] Garey | Computers and Intractability: A Guide to the Theory of NP-Completeness[END_REF]. Following terminology introduced in [START_REF] Garey | Computers and Intractability: A Guide to the Theory of NP-Completeness[END_REF], we recall that given a collection C of subsets of a finite set E, a cover for E is a subset C ′ ⊆ C such that every element of E belongs to at least one member of C ′ . For the sake of clarity, we now state formally the two decision problems we consider: ECID and Minimum Set Cover. Given two genomes G and H, and a positive integer k, ECID problem asks whether it is possible to find two exemplar genomes G ′ and H ′ of resp. G and H such that

d(G ′ , H ′ ) ≤ k. Given a collection C of subsets of a finite set E and a positive integer k ′ , Minimum Set Cover problem asks whether C contains a cover C ′ for E s.t. |C ′ | ≤ k ′ .
Hereafter, we consider, w.l.o.g., that in each C i ∈ C, any e j ∈ C i is also in C j with 1 ≤ i, j ≤ m and i = j. In fact, by definition, if an element is covered by only one subset then this subset must be part of C ′ . In the following, we will prove that, even if G does not contain more than one occurrence of each duplicated gene, ECID problem is NP-complete. Given an integer k ′ , two exemplar genomes G ′ and H ′ , one can compute polynomially d(G ′ , H ′ ) and check if d(G ′ , H ′ ) ≤ k ′ (see [START_REF] Bergeron | On the similarity of sets of permutations and its applications to genome comparison[END_REF]). Therefore, ECID problem is in NP. The remainder of the section is devoted to proving that it is also NP-hard. For this purpose, we reduce Minimum Set Cover problem to ECID problem. Let C = {C 1 , C 2 . . . C m } be a collection of m subsets of a finite set E = {e 1 , e 2 . . . e n } of n elements.

In the rest of this section, we consider that F ⊆ N but any genome is built with elements of F provided with signs (i.e. R). In other words, genes 3 and -3 are of the same family. Let us detail the construction of the two genomes G and

H. Let y = |E| + 2 if |E| is even, y = |E| + 1 otherwise. Let z i = (y + 2).(i -1)
for any 1 ≤ i ≤ m + 1. From (C, E), we construct two genomes G and H as described below (an illustration is given in Figure 1):

G1 = γ |E|+1 γ |E|+2 . . . γ |E|+m-1 α1 β1 . . . αm βm γ1 γ |E|+m γ2 γ |E|+m+1 . . . γ 2|E|+m-1 γ |E| H1 = α1 θ1 γ |E|+1 α2 θ2 γ |E|+2 . . . γ |E|+m-1 αm θm γ |E|+m γ |E|+m+1 . . . γ 2|E|+m-1
We now detail the substrings that compose G 1 and H 1 :

for 1 ≤ i ≤ m, we construct the sequences of genes α i = z i and

β i = z i +1 z i +2 . . . z i +y+1; -for 1 ≤ i ≤ 2|E| + m -1, we construct a gene γ i = z m+1 + i; -for 1 ≤ i ≤ m, we construct a gene θ i = z i +2 z i +4 . . . z i +y z i +1 z i +3 . . . z i + y-1 z i +y+1.
Note that G 1 and H 1 are two exemplar genomes. Genome G is, thus, a copy of G 1 .

We now turn to transform H 1 into a non-exemplar genome H: for 1 ≤ i ≤ m and 1 ≤ j ≤ |E|, if e j ∈ C i then gene γ j is inserted between the j th and the j+1 th genes of θ i . We denote by ECID-construction any construction of this type. An illustration of an ECID-construction is given in Figure 1. Intuitively, θ i is a shuffle of β i with some inserted γ j s (i.e. no conserved adjacencies) for 1 ≤ i ≤ m. Clearly, our construction can be carried out in polynomial time. Moreover, the result of such a construction is indeed an instance of ECID problem. We now turn to proving that our construction is a polynomial time reduction from Minimum Set Cover to ECID problem where G is an exemplar genome whereas H is not. Let first note that, by construction, there are only |E| duplicated gene families in G and H, namely the γ i s for 1 ≤ i ≤ |E|.

Lemma 1. The only conserved intervals that can exist between G and any exemplar genome H ′ of H are intervals [α i , z i + y + 1] such that all the γ j s of Proof. (⇒) Suppose C contains a cover C ′ of E of size less than or equal to k ′ . Let f : e i → {C 1 , C 2 , . . . C m } be the function which, given an element of E, returns the index of the subset covering this element in C ′ . Let I ′ = (G, H, k) be the instance obtained from an ECID-construction of I. We look for an exemplar genome H ′ of H such that d(G, H ′ ) ≤ k. We define H ′ as follows: for each e j ∈ E, delete γ j of θ p for all p ∈ {1, 2, .., m}/{f (e j )}.

[α i , z i + y + 1] in H ′ have been deleted, with 1 ≤ i ≤ m and 1 ≤ j ≤ |E|.
By construction, E denotes the set of duplicated gene families and by construction the only duplicated genes in H are the γ i s. Therefore, H ′ is exemplar since one deletes all occurrences but one of γ i with 1 ≤ i ≤ |E|. Remains us to prove that d(G, H ′ ) ≤ k. By definition, for each C j ∈ C ′ and each e i ∈ C j , f (e i ) = p with p = j and γ i of θ j has been deleted. Since all the γ i s of θ j in H ′ have been deleted, there is a conserved interval [α j , z j +y +1] between G and H ′ . Globally, there are at least m-k ′ such subsets. Therefore, there are at least m-k ′ conserved intervals between G and H ′ . Thus, (⇐) Suppose we have an exemplar genome H ′ of H such that d(G, H ′ ) ≤ k. Assume, w.l.o.g., that d(G, H ′ ) = d ′ ≤ k. We define C ′ as follows: in H ′ , if γ j ∈ θ p then f (e j ) = p and C p ∈ C ′ . We now turn to proving that C ′ defines a cover of E of size at most k ′ . Since H ′ is an exemplar genome of H, there is exactly one occurrence of each gene family in H ′ . Therefore, C ′ contains a set of subsets that covers E. Remains us to prove that

d(G, H ′ ) ≤ |G|.|G -1| -2(m -k ′ ),
|C ′ | ≤ k ′ .
By definition, since d ′ ≤ |G|.|G -1| -2(mk ′ ), there are at least mk ′ conserved intervals between G and H ′ . By Lemma 1, the only conserved intervals that can exist between G and any exemplar genome H ′ of H are intervals [α i , z i + y + 1] such that all the γ j s of [α i , z i + y + 1] in H ′ have been deleted. Therefore, by construction, there are at least mk ′ such intervals [α i , z i + y + 1] in H ′ . Correctness of Theorem 1 follows.

⊓ ⊔

Given Theorem 1, one can ask if instead of deleting the duplicated genes, one can compute the interval distance taking into account duplicated genes [START_REF] Blin | The breakpoints distance for signed sequences[END_REF][START_REF] Swenson | Approximating the true evolutionary distance between two genomes[END_REF]. For this purpose, we propose the MCIM problem: finding a minimum conserved interval matching between two genomes. Unfortunately, as we will show hereafter, this problem is also NP-complete. Theorem 2. Minimum Conserved Interval Matching problem is NPcomplete.

To prove the correctness of Theorem 2, we provide a polynomial time reduction from the NP-complete problem Minimum Bin Packing [START_REF] Garey | Computers and Intractability: A Guide to the Theory of NP-Completeness[END_REF]. For the sake of clarity, we now state formally the two decision problems we consider: MCIM and Minimum Bin Packing. Given two genomes G and H, and an integer k, MCIM problem asks whether it is possible to find a matching between G and H such that d(G, H) ≤ k. Given a finite set U = {u 1 , u 2 , . . . , u n }, a size s(u) ∈ Z + for each u ∈ U and two positive integers k ′ and C, Minimum Bin Packing problem asks whether there is a partition of

U into k ′ disjoint sets U 1 , U 2 , . . . , U k ′ such that (s(u)|u ∈ U i ) ≤ C for each U i .
It is easily seen that MCIM is in NP since given an integer k and a set of matchings between two genomes we can polynomially compute the number of conserved intervals between G and H and thus check if the distance is less than or equal to k (see [START_REF] Bergeron | On the similarity of sets of permutations and its applications to genome comparison[END_REF]). The remainder of the section is devoted to proving that MCIM is also NP-hard even when there is only one non trivial family in F, which implies Theorem 2. For this, we reduce Minimum Bin Packing problem to MCIM problem.

Let N = k ′ .C - n i=1 s(u i ).
Let us first detail the construction of genomes G and H from a Minimum Bin Packing instance (U, k ′ , C). The gene families are F = {α, β, x, A 1 , A 2 . . . , A n+N , B 1 , B 2 , . . . , B k ′ +1 }. On the whole, there are k ′ + N + n + 4 families of genes, and x is the unique non-trivial family. For 1 ≤ i ≤ n (resp. n + 1 ≤ i ≤ n + N ), we denote by u ′ i a sequence of s(u i ) consecutive genes x (resp. one gene x). For 1 ≤ j ≤ k ′ , U ′ j represents a sequence of C consecutive genes x. G and H are defined as follows:

G = α u ′ 1 A1 u ′ 2 A2 . . . u ′ n+N An+N B1 B2 . . . B k ′ +1 β H = α B1 U ′ 1 B2 U ′ 2 . . . B k ′ U ′ k ′ B k ′ +1 A1 A2 . . . An+N β
An illustration of such a construction, that can obviously be achieved in polynomial time, is given in Figure 2 In the next three lemmas, that establish that MCIM is NP-complete, we consider an instance (U, k ′ , C) of Minimum Bin Packing and the corresponding instance (G, H, k) of MCIM according to the above construction. Lemma 3. Given a matching M, a non trivial segment of size p perfectly matched in M induces more conserved intervals ( i.e. p(p-1)

2

) than a non-trivial segment of size k not-perfectly matched. ). Therefore, by Lemma 3, any non-trivial segment u ′ i , with 1 ≤ i ≤ n, in G should be matched with a sequence of consecutive genes x in H. Precisely, for any 1 ≤ i ≤ n, there is a given 1 ≤ j ≤ k ′ such that the sequence u ′ i is perfectly matched with a substring of U ′ j as illustrated in Figure 2. Therefore, such a matching induces a partition P of the set of sequences

{u ′ 1 , u ′ 2 , . . . , u ′ n } into at most k ′ disjoint sequences U ′ 1 , U ′ 2 , . . . , U ′ k ′ . As, by con- struction, |U ′ i | = C for 1 ≤ i ≤ k ′ , P
corresponds to an answer to the corresponding Minimum Bin Packing instance.

(⇒) Suppose we have a partition P of U into disjoint sets U 1 , U 2 , . . . , U k ′ each of cardinality at most C. We compute a gene matching M between G and H as follows: (1) each trivial gene in G is matched with its corresponding gene in H and (2) for 1 ≤ j ≤ k ′ , for each u i ∈ U , if u i ∈ U j , then the sequence of genes x of u ′ i in G is perfectly matched with the first free (i.e. not already matched) sequence of genes x of U ′ j in H. Since M is built according to P , we claim that each non-trivial segment u ′ i , with 1 ≤ i ≤ n, is matched to a contiguous sequence of genes x in H. Thus, any non-trivial segment u ′ i , with 1 ≤ i ≤ n, in G induces s(ui).(s(ui)-1) In this section, we present a heuristic approach to solve MCIM problem that performs well on real data. This approach uses the following intuition: long segments of genes that match, up to a complete reversal, in two genomes are likely to belong to a Minimum Conserved Interval Matching. Remark that given two trivial genomes this intuition gives the optimal solution. Unfortunately, this is not always the case when considering non trivial genomes. Even so, this approach works very well on real genomes. In the rest of this section, we consider two genomes G and H build with elements of F ⊆ N and provided with signs.

Our approach to solve MCIM problem is based on the following loop:

1. Identify a longest common segment s of genes between G and H (by common segment, we mean a segment appearing, up to a complete reversal, both in G and H); 2. Replace s in both genomes by an integer g c , further call compressed gene, s.t. g c ∈ F (this induces that g c is a trivial gene); 3. Mark g c as treated; 4. Store the number of genes of s in N s [g c ] and the set of genes of s in C[g c ].

While a common segment of unmarked genes exists, the algorithm performs the loop described above on the modified genomes. In the following, we will refer to the modified versions of the genomes G and H as G ′ and H ′ . Once the algorithm exits of the loop, any unmarked gene g u of G ′ and H ′ is deleted since, by definition, g u is not common (i.e. there are more genes g u in one of the genomes). This first step of the algorithm leads to the computation of two exemplar genomes G ′ and H ′ of resp. G and H. Clearly, this step gives the gene to gene matching of G and H in a compressed version: the corresponding matching M is obtain by perfectly matching the segments of genes corresponding to each compressed gene of G as illustrated in Figure 3.

In a second step, the algorithm computes the interval distance induced by M. By Lemma 3, each compressed gene g c of G ′ induces k(k-1) 2 conserved intervals between G and H with k = N s [g c ]. Moreover, some conserved intervals between G ′ and H ′ may exist. Therefore, since G ′ and H ′ are trivial genomes, the algorithm computes the set of conserved intervals S ci between G ′ and H ′ in Fig. 3. The matching of the genes of G and H deduced from the exemplar genomes G ′ and H ′ . polynomial time using the algorithm defined in [START_REF] Bergeron | On the similarity of sets of permutations and its applications to genome comparison[END_REF]. Since G ′ and H ′ are composed of compressed genes, for each conserved interval

[g c1 , g c2 ] ∈ S ci , N s [g c1 ].N s [g c2 ]
conserved intervals between G and H are induced. Indeed, if [g c1 , g c2 ] ∈ S ci then a segment of genes g c1 λg c2 appears in G ′ and either a segment of genes g c1 λ ′ g c2 or -g c2 λ ′g c1 appears in H ′ with λ and λ ′ being similar segments of genes not considering genes order and sign. Therefore, considering M, for any genes

g i ∈ C[g c1 ] and g j ∈ C[g c2 ], [g i , g j ] is a conserved interval between G and H. This step returns d(G, H, M) = |G|.|G -1| -2( gc∈G ′ Ns[gc].(Ns[gc]-1) 2 + [gc1,gc2]∈Sci N s [g c1 ].N s [g c2 ])
We implemented our approach using a suffix tree. Indeed, longest common segments between G and H can be found in linear time by browsing a suffix tree built on G, H and the reversed of H. To test our algorithm and get an estimate of its performance in practice, we applied our heuristic approach to a set of 20 bacteria from NCBI.

Data and programs used and mentioned in this article can be found at http://www.sciences.univ-nantes.fr/info/perso/permanents/blin/Cocoon05/ Interesting characteristics of this set are given on the web page. We implemented the brute force algorithm which consists in computing all possible matchings and we compared the obtained results. In average, the gap between the optimal solution opt and the solution given by our algorithm is less than 0, 12% of opt. We noticed that more than 2 3 of the bacteria have duplicated genes with, for most of them, duplicated families of cardinality 2. The effectiveness of our algorithm relies on the fact that the number of duplicated genes are not significant compared to the size of the genomes. Moreover, since our algorithm gives the optimal solution for trivial genomes, duplicated genes have a very little impact on the results.

Conclusion

The assumption of uniqueness of each gene in a genome has been a requirement of traditional methods in comparative genomics but is only justified in small virus genomes, since in general, there are more than one copy of a gene in a genome. In this paper, we investigate the time complexity of the conserved interval distance computation considering duplicated genes. We proved that both use of exemplar and matching methods leads to NP-completeness. We are doing thorough experimental testing which will determine how well our algorithm does in practice under different regimes of duplication, but our preliminary results are extremely encouraging.

Note that, since the Brute Force Algorithm is in O(k k.l n) with k being the maximal cardinality of any non-trivial gene family, l being the number of nontrivial families and n being the size of the genomes, MCIM problem is in FPT for parameter k and l. In order to be usable in many reconstruction algorithms, it would be of interest to determine if the problem is in FPT for other parameters.

  For example, given two genomes G 1 = a b c g e f -d h and G 2 = a g -c -b e -f -d h, there are seven conserved intervals between G 1 and G 2 : [a, -d], [a, e], [a, h], [b, c], [e, -d], [e, h] and [-d, h].

  then s is perfectly matched in M; not-perfectly matched otherwise. Minimum Conserved Interval Matching. Given two genomes G, H and a gene matching M, we denote by d(G, H, M) the conserved interval distance between G and H with respect to M, and by d(G, H) the conserved interval distance between G and H, defined as the minimum d(G, H, M) among all matchings M. The matching M such that d(G, H, M) = d(G, H) is a minimum conserved interval matching.

Fig. 1 .

 1 Fig. 1. Example of an ECID-construction where E = {e1, e2, e3} and y = 4.

Lemma 2 .

 2 Let I = (C, E, k ′ ) be an instance of the problem Minimum Set Cover with a collection C = {C 1 , C 2 . . . C m } of m subsets of a finite set E = {e 1 , e 2 . . . e n }, and I ′ = (G, H, k) an instance of ECID problem obtained by an ECID-construction from I. C contains a cover C ′ of E of size less than or equal to k ′ iff d(G, H ′ ) ≤ k where H ′ is an exemplar genome of H and k = |G|.|G -1| -2(mk ′ ).

  since the number of conserved intervals between a genome G and itself is |G|.|G-1| 2 and |G| = |H ′ |.

2 +

 2 . To complete the construction of the instance of MCIM, it remains to us to define k: k = |G|.(|G|-1) |H|).(s(ui)-1) 2

Lemma 4 .

 4 d(G, H) ≥ k and in any matching M between G and H, any conserved interval I with respect to M is either [α, β] or I = [p, q] with S[p..q] being a non trivial segment. Lemma 5. There is a partition of U into k ′ disjoint sets U 1 , U 2 , . . . , U k ′ such that the sum of the sizes of the elements in each U i is at most C if and only if d(G, H) ≤ k. Proof. (⇐) Suppose that d(G, H) ≤ k. By Lemma 4, we know that d(G, H) = k, and any conserved interval I with respect to a minimum conserved interval matching between G and H is either [α, β] or I = [p, q] with S[p..q] being a non trivial segment. Moreover, if d(G, H) = k then the number of conserved intervals should be maximal (i.e. 1 + n i=1 s(ui).(s(ui)-1) 2

Fig. 2 .

 2 Fig. 2. Instance of MCIM associated to the Minimum Bin Packing instance where k ′ = 3, C = 8 and U = {u1, . . . , u6} with s(u1) = s(u5) = 5, s(u2) = s(u6) = 4, s(u3) = 3 and s(u4) = 2 and the gene to gene matching corresponding to the following partition of U : U1 = {u1, u3}, U2 = {u2, u6} and U3 = {u4, u5}

4

  ).(s(ui)-1) 2 conserved intervals (see proof of Lemma 4). This leads to d(G, H, M) ≤ k, and so to d(G, H) ≤ k. Correctness of Theorem 2 follows. ⊓ ⊔ Using the L.C.Substring to approximate MCIM

⋆ This work was partially supported by the French-Italian PAI Galileo project number 08484VH


O V Ogievetsky

L Poulain D'andecy

On representations of cyclotomic Hecke algebras

An approach, based on Jucys-Murphy elements, to the representation theory of cyclotomic Hecke algebras is developed. The maximality (in the cyclotomic Hecke algebra) of the set of the Jucys-Murphy elements is established. A basis of the cyclotomic Hecke algebra is suggested; this basis is used to prove the flatness of the deformation without use of the representation theory.

. Introduction

In the paper [START_REF] Isaev | On Baxterized solutions of reflection equation and integrable chain models[END_REF] a Hamiltonian for an open chain model was suggested. This Hamiltonian is written on the universal level, as an element of (a certain localization of) the group ring of an "affine Hecke algebra", see [START_REF] Isaev | On Baxterized solutions of reflection equation and integrable chain models[END_REF] for details; the model induces an integrable system for any representation of the affine Hecke algebra. For the study of the model it is important to understand different aspects of the representation theory of the affine Hecke algebra. In the present article we discuss finite-dimensional representations of the affine Hecke algebra. A finite dimensional representation of the affine Hecke algebra factors through a certain finitedimensional quotient of the affine Hecke algebra, a "cyclotomic Hecke algebra". The cyclotomic Hecke algebra is a particular example of a Hecke-type deformation which group rings of Coxeter groups and, more generally, of complex reflection groups admit (the usual Hecke algebra is a deformation of the Coxeter group of type A, that is, the symmetric group). The cyclotomic Hecke algebras H(m, 1, n) are the Hecke algebras associated to the complex reflection groups of type G(m, 1, n); for m = 1 and m = 2, these are the Hecke algebras associated to the Coxeter groups of type A and type B. The cyclotomic Hecke algebras have been introduced in [START_REF] Ariki | A Hecke algebra of (Z/rZ) ≀ S n and construction of its irreducible representations[END_REF] wherein the representation theory was established and used to prove that the deformation is flat. Section 2 contains necessary definitions. In Section 3 we exhibit a basis of the algebra H(m, 1, n), quite different from the basis presented in [START_REF] Ariki | A Hecke algebra of (Z/rZ) ≀ S n and construction of its irreducible representations[END_REF]; we use this basis it to prove the flatness of the deformation without appealing to the representation theory.

In Sections 4-6 an inductive approach to the representation theory of the algebras H(m, 1, n) is developed. It uses heavily the Jucys-Murphy elements which form a maximal commutative set in the algebras H(m; 1; n). This approach generalizes the approach developed in [START_REF] Okounkov | A new approach to representation theory of symmetric groups II[END_REF] for the symmetric groups (and generalized to the Brauer algebras and their q-deformations in [START_REF] Isaev | Jucys-Murphy elements for Birman-Murakami-Wenzl algebras[END_REF]). Our aim is not the construction of the representation theory, it has been already constructed in [START_REF] Ariki | A Hecke algebra of (Z/rZ) ≀ S n and construction of its irreducible representations[END_REF]. We rather rederive the representation theory directly from the properties of the Jucys-Murphy operators; we encode the representation bases and the Young multi-tableaux by sets of common eigenvalues of the Jucys-Murphy elements. The irreducible representations of H(m, 1, n) are constructed with the help of a new associative algebra; the underlying vector space of this algebra is the tensor product of the cyclotomic Hecke algebra with a free associative algebra generated by standard m-tableaux. The proofs of statements are often omitted in the present letter; details of the results and proofs and also the classical limit of the approach will be published in [START_REF] Ogievetsky | Cyclotomic Hecke algebras: Jucys-Murphy elements[END_REF].

Throughout the paper the ground field is the field C of complex numbers.

. Cyclotomic Hecke algebras and Jucys-Murphy elements

The braid group of type A (or simply the braid group) on n strands is generated by elements σ 1 , . . . , σ n-1 with the relations:

σ i σ i+1 σ i = σ i+1 σ i σ i+1
for all i = 1, . . . , n -2 , σ i σ j = σ j σ i for all i, j such that |i -j| > 1 .

(2.1)

(2.2)
The braid group of type B (sometimes called affine braid group) is obtained by adding to the generators σ i the generator τ with the relations:

τ σ 1 τ σ 1 = σ 1 τ σ 1 τ , τ σ i = σ i τ for i > 1 .
(

(2.4)

The elements J i , i = 1, . . . , n, of the braid group of type B defined inductively by the following initial condition and recursion:

J 1 = τ , J i+1 = σ i J i σ i , (2.5)
are called Jucys-Murphy elements. It is well known that they form a commutative set of elements. In addition, J i commutes with all σ k except σ i-1 and σ i ,

J i σ k = σ k J i if k > i and if k < i -1 . (2.6)
The affine Hecke algebra Ĥn is the quotient of the group algebra of the braid group of type B by: σ 2 i = (q -q -1 )σ i + 1 for all i = 1, . . . , n -1 .

(2.7)

The usual Hecke algebra H n is the algebra generated by elements σ 1 , . . . , σ n-1 with the relations (2.1)-(2.2) and (2.7).

The cyclotomic Hecke algebra H(m, 1, n) is the quotient of the affine Hecke algebra Ĥn by

(τ -v 1 ) . . . (τ -v m ) = 0 . (2.8)
The algebra

H(m, 1, n) is a deformation of the group algebra CG(m, 1, n) of the complex reflection group G(m, 1, n). In particular, H(1, 1, n) is isomorphic to the Hecke algebra of type A and H(2, 1, n) is the Hecke algebra of type B.
The group G(m, 1, n) is isomorphic to S n ≀ C m , the wreath product of the symmetric group S n with the cyclic group of m elements.

The specialization of H(m, 1, n) is semi-simple if and only if the numerical values of the parameters satisfy (see [START_REF] Ariki | On the semi-simplicity of the Hecke algebra of (Z/rZ) ≀ S n[END_REF])

1 + q 2 + • • • + q 2N = 0 for all N : N < n
(2.9) and q 2i v j -v k = 0 for all i, j, k such that j = k and -n < i < n .

(2.10)

In the sequel we work either with a generic cyclotomic Hecke algebra (that is, v 1 , . . . , v m and q are indeterminates) or in the semi-simple situation with an additional requirement:

v j = 0 , j = 1, . . . , m .
(2.11)

As n varies, the algebras H(m, 1, n) form an ascending chain of algebras :

{e} ⊂ H(m, 1, 0) ⊂ H(m, 1, 1) ⊂ • • • ⊂ H(m, 1, n) ⊂ . . . . (2.12)
We shall denote by the same symbols J i the images of the Jucys-Murphy elements in the cyclotomic Hecke algebra. As a by-product of our construction, we shall see that the set of the Jucys-Murphy elements {J 1 , . . . , J n } is maximal commutative in the generic algebra H(m, 1, n); more precisely, the algebra of polynomials in Jucys-Murphy elements coincides with the algebra generated by the union of the centers of H(m, 1, k) for k = 1, . . . , n.

. Normal form for H(m, 1, n)

We exhibit a basis for the algebra H(m, 1, n). Several known facts about the chain (with respect to n) of the algebras H(m, 1, n) are reestablished with the help of this basis. In particular, we show that H(m, 1, n) is a flat deformation of the group ring of G(m, 1, n). This was proved in [START_REF] Ariki | A Hecke algebra of (Z/rZ) ≀ S n and construction of its irreducible representations[END_REF] with the use of the representation theory.

Let W be the subalgebra of H(m, 1, n) generated by the elements τ, σ 1 , . . . , σ n-2 .

Proposition 1. If B is a linear basis of W , the elements

σ -1 j σ -1 j-1 . . . σ -1 1 τ α σ 1 σ 2 . . . σ n-1 b , (3.1)
where j ∈ {0, . . . , n -1}, α ∈ {0, . . . , m -1} and b is a basis element of B, form a linear basis of H(m, 1, n).

Corollary 2. (i) The algebra H(m, 1, n) is a flat deformation of the group ring CG(m, 1, n); in other words, H(m, 1, n) is a free C[q, q -1 , v 1 , . . . , v m ]-module of dimension dim H(m, 1, n) = |G(m, 1, n)| = n!m n . (3.2) (ii) Moreover the subalgebra W is isomorphic to H(m, 1, n -1).
We can construct recursively a global normal form for elements of H(m, 1, n) using now the Proposition 1 and the Corollary 2, statement (ii). Let R k be the following set of elements:

R k = {σ -1 j σ -1 j-1 . . . σ -1 1 τ α σ 1 σ 2 . . . σ k-1 , j = 0, . . . , k -1, α = 0, . . . , m -1}. Corollary 3. Any element x ∈ H(m, 1, n) can be written uniquely as x = u n u n-1 . . . u 1 where u k ∈ R k for k = 1, . . . , n.

. Spectrum of Jucys-Murphy elements and Young mtableaux

We begin to develop an approach, based on the Jucys-Murphy elements, to the representation theory of the chain (with respect to n) of the cyclotomic Hecke algebras H(m, 1, n). This is a generalization of the approach of [START_REF] Okounkov | A new approach to representation theory of symmetric groups II[END_REF].

1. The first step consists in construction of all representations of H(m, 1, n) verifying two conditions. First, the Jucys-Murphy elements J 1 , . . . , J n are represented by semi-simple (diagonalizable) operators. Second, for every i = 1, . . . , n -1 the action of the sub-algebra generated by J i , J i+1 and σ i is completely reducible. We shall use the name C-representations (C is the first letter in "completely reducible") for these representations. At the end of the construction we shall see that all irreducible representations of H(m, 1, n) are C-representations.

Following [START_REF] Okounkov | A new approach to representation theory of symmetric groups II[END_REF] we denote by Spec(J 1 , . . . , J n ) the set of strings of eigenvalues of the Jucys-Murphy elements in the set of C-representations: Λ = (a

(Λ) 1 , . . . , a (Λ)
n ) belongs to the set Spec(J 1 , . . . , J n ) if there is a vector e Λ in the space of some C-representation such that J i (e Λ ) = a (Λ) i e Λ for all i = 1, . . . , n. Every C-representation possesses a basis formed by vectors e Λ (this is a reformulation of the first condition in the definition of C-representations). Since σ k commutes with J i for k > i and k < i -1, the action of σ k on a vector e Λ , Λ ∈ Spec(J 1 , . . . , J n ), is "local" in the sense that σ k (e Λ ) is a linear combination of e Λ ′ such that a

(Λ ′ ) i = a (Λ) i for i = k, k + 1.
2. Affine Hecke algebra Ĥ2 . Consider the affine Hecke algebra Ĥ2 , which is generated by X, Y and σ with the relations:

XY = Y X, Y = σXσ, σ 2 = (q -q -1 )σ + 1 . (4.1)
It is realized by J i , J i+1 and σ i for all i = 1, . . . , n -1. We reproduce here the result of [START_REF] Isaev | On representations of Hecke algebras[END_REF] concerning the classification of irreducible representations with diagonalizable X and Y of Ĥ2 .

There are one-dimensional and two-dimensional irreducible representations.

• The one-dimensional irreducible representations are given by

X → a, Y → q ±2 a, σ → ±q ±1 . (4.2)
• The two-dimensional irreducible representations are given by

σ → 0 1 1 q -q -1 , X → a -(q -q -1 )b 0 b , Y → b (q -q -1 )b 0 a ,
with b = a in order for X and Y to be diagonalizable and with b = q ±2 a to ensure irreducibility. By a change of basis we transform X and Y to a diagonal form:

σ → (q-q -1 )b b-a 1 -(q-q -1 ) 2 ab (b-a) 2 1 -(q-q -1 )a b-a , X → a 0 0 b , Y → b 0 0 a . (4.3)
3. We return to strings of eigenvalues of Jucys-Murphy elements.

Proposition 4. Let Λ = (a 1 , . . . , a i , a i+1 , . . . , a n ) ∈ Spec(J 1 , . . . , J n ) and let e Λ be a corresponding vector. Then:

(a) We have a i = a i+1 . (b) If a i+1 = q ±2 a i then σ i (e Λ ) = ±q ±1 e Λ .
(c) If a i+1 = q ±2 a i then Λ ′ = (a 1 , . . . , a i+1 , a i , . . . , a n ) ∈ Spec(J 1 , . . . , J n ); moreover, the vector σ i (e Λ ) -(q-q -1 )a i+1 a i+1 -a i e Λ corresponds to the string Λ ′ (see (4.3) with b = a i+1 and a = a i ).

4. Content strings. Definition 5. A content string (a 1 , . . . , a n ) is a string of numbers satisfying the following conditions:

(c1) a 1 ∈ {v 1 , . . . , v m };
(c2) for all j > 1: if a j = v k q 2z for some k and z = 0, then {v k q 2(z-1) , v k q 2(z+1) }∩{a 1 , . . . , a j-1 } is non-empty;

(c3) if a i = a j = v k q 2z with i < j for some k and z, then {v k q 2(z-1) , v k q 2(z+1) } ⊂ {a i+1 , . . . , a j-1 }.

The set of content strings of length n we denote by Cont(n).

Here is the "cyclotomic" analogue of the Theorem 5.1 in [START_REF] Okounkov | A new approach to representation theory of symmetric groups II[END_REF] and the Proposition 4 in [START_REF] Isaev | On representations of Hecke algebras[END_REF].

Proposition 6. If a string of numbers (a 1 , . . . , a n ) belongs to Spec(J 1 , . . . , J n ) then it belongs to Cont(n). Let the length of the m-tuple be n. We place the numbers 1, . . . , n in the nodes of these diagrams in such a way that in every diagram the numbers in the nodes are in ascending order along rows and columns in right and down directions. This is a standard Young m-tableau of shape λ (m) .

We associate to each node of a Young m-diagram a number (the "content") which is v k q 2(s-r) for the node in the line r and column s in the k th tableau of the m-tuple. Proposition 7. There is a bijection between the set of standard Young m-tableaux of length n and the set Cont(n).

. Construction of representations

We proceed as in [START_REF] Ogievetsky | Lecture on Hecke algebras[END_REF]. We first define an algebra structure on a tensor product of the algebra H(m, 1, n) with a free associative algebra generated by the standard m-tableaux corresponding to m-partitions of n. Then, by evaluation (with the help of the simplest one-dimensional representation of H(m, 1, n)) from the right, we build representations. Define, for any σ i among the generators σ

1 , . . . , σ n-1 of H(m, 1, n), σ i (α, β) := σ i + (q -q -1 ) β α -β . (5.1)
This is called the "Baxterization" of the elements σ i . The parameters α and β are called spectral parameters. We collect the relations for the Baxterized generators σ i .

changes but the expression stays always linear in X ) then we obtain a combination of terms of the form "X times relation of H(m, 1, n)".

Let | be a "vacuum" -a basic vector of a one-dimensional H(m, 1, n)-module; for example, σ i | = q| for all i and τ | = v 1 | . Moving, in the expressions φX λ (m) | , φ ∈ H(m, 1, n), the elements X 's to the left and using the module structure, we build, due to the compatibility, a representation of H(m, 1, n) on the vector space V λ (m) spanned by X λ (m) | . We shall, by a slight abuse of notation, denote the symbol X λ (m) | again by X λ (m) . This procedure leads to the following formulas for the action of the generators τ, σ 1 , . . . , σ n-1 on the basis vectors {X λ (m) } of V λ (m) :

σ i : X λ (m) → -(q -q -1 ) c(X λ (m) |i + 1) c(X λ (m) |i) -c(X λ (m) |i + 1) X λ (m)
+ qc(X λ (m) |i + 1) -q -1 c(X λ (m) |i) c(X λ (m) |i + 1) -c(X λ (m) |i) X λ (m) s i

(5.5) and τ : X λ (m) → c(X λ (m) |1)X λ (m) .

(5.6)

As before, it is assumed here that X λ (m) s i = 0 if X λ (m) s i is not a standard m-tableau.

Completeness

We conclude the study of representations of H(m, 1, n). First, with the construction of the preceding Section, we complete the description of the set Spec(J 1 , . . . , J n ) started in Section 4. Then we check that we obtain within this approach all irreducible representations of the algebra H(m, 1, n).

We underline that the restrictions (2.9)-(2.11) are essential for the statements below.

Proposition 10. The set Spec(J 1 , . . . , J n ), the set Cont(n) and the set of standard m-tableaux are in bijection.

Theorem 11. The representations V λ (m) (labeled by the m-partitions) of the algebra H(m, 1, n) constructed in the Section 5 are irreducible and pairwise non-isomorphic. Moreover the sum of the squares of the dimensions of the constructed representations equals the dimension of H(m, 1, n).

As a by-product we obtain that the algebra H(m, 1, n) is semi-simple under the restrictions (2.9)-(2.11).

5 .

 5 Young m-diagrams and m-tableaux. A Young m-diagram, or m-partition, is an mtuple of Young diagrams λ (m) = (λ 1 , . . . , λ m ). The length of a Young diagram λ is the number of nodes of the diagram and is denoted by |λ|. By definition the length of an m-tuple λ (m) = (λ 1 , . . . , λ m ) is |λ (m) | := |λ 1 | + • • • + |λ m | . (4.4)

On leave of absence from P. N. Lebedev Physical Institute, Leninsky Pr. 53, 117924 Moscow, Russia

Unité Mixte de Recherche (UMR 6207) du CNRS et des Universités Aix-Marseille I, Aix-Marseille II et du Sud Toulon -Var; laboratoire affilié à la FRUMAM (FR 2291)

Proposition 8. The following relations hold:

with f (α, β) = qα-q -1 β α-β , σ i (α, β)σ i+1 (α, γ)σ i (β, γ) = σ i+1 (β, γ)σ i (α, γ)σ i+1 (α, β),

(5.2)

Let λ (m) be an m-partition of length n. Consider a set of free generators labeled by standard m-tableaux of shape λ (m) ; for a standard m-tableau X λ (m) we denote by X λ (m) the corresponding free generator and by c(X λ (m) |i) the content (see the preceding Section for the definition) of the node carrying the number i.

Proposition 9. The relations

are compatible with the relations for the generators τ, σ 1 , . . . , σ n-1 of the algebra H(m, 1, n).

The element X λ (m) s i corresponds to the m-tableau obtained from X λ (m) by exchanging the nodes with numbers i and (i + 1). The tableau X λ (m) s i is of the same (as X λ (m) ) shape λ (m) . If the resulting m-tableau is not standard, we put X λ (m) s i = 0.

We explain the meaning of the word "compatible" used in the formulation of the Proposition.

Let F be the free associative algebra generated by τ , σ1 , . . . , σn-1 . The algebra H(m, 1, n) is naturally the quotient of F .

Let C[X ] be the free associative algebra whose generators X λ (m) range over all standard m-tableaux of shape λ (m) for all m-partitions λ (m) of n.

Consider an algebra structure on the space C[X ] ⊗ F for which: (i) the map ι

is an isomorphism of F with its image with respect to ι 2 ; (iii) the formulas (5.3)-(5.4), extended by associativity, provide the rules to rewrite elements of the form

The "compatibility" means that we have an induced structure of an associative algebra on the space C[X ]⊗H(m, 1, n). More precisely, if we multiply any relation of the cyclotomic Hecke algebra H(m, 1, n) (the relation is viewed as an element of the free algebra F ) from the right by a generator X λ (m) (this is a combination of the form "relation of H(m, 1, n) times X λ (m) ") and use the "instructions" (5.3)-(5.4) to move all appearing X 's to the left (the free generator