Jean Lieber

Amedeo Napoli

Laszlo Szathmary

Yannick Toussaint

First Elements on Knowledge Discovery Guided by Domain Knowledge (KDDK)

In this paper, we present research trends carried out in the Orpailleur team at loria, showing how knowledge discovery and knowledge processing may be combined. The knowledge discovery in databases process (kdd) consists in processing a huge volume of data for extracting significant and reusable knowledge units. From a knowledge representation perspective, the kdd process may take advantage of domain knowledge embedded in ontologies relative to the domain of data, leading to the notion of "knowledge discovery guided by domain knowledge" or kddk. The kddk process is based on the classification process (and its multiple forms), e.g. for modeling, representing, reasoning, and discovering. Some applications are detailed, showing how kddk can be instantiated in an application domain. Finally, an architecture of an integrated kddk system is proposed and discussed.

Introduction

In this presentation, we present research trends carried out within in the Orpailleur team at loria, showing multiple aspects of knowledge discovery and knowledge processing. The knowledge discovery in databases process -hereafter kdd-consists in processing a huge volume of data in order to extract knowledge units that are significant and reusable. Assimilating knowledge units to gold nuggets, and databases to lands or rivers to be explored, the kdd process can be likened to the process of searching for gold (in the same way, kdd is compared with archeology in [START_REF] Brachman | Knowledge representation support for data archaeology[END_REF]). This explains the name of the research team: the "orpailleur" denotes in French a person who is searching for gold in rivers or mountains. Moreover, the kdd process is iterative, interactive, and generally controlled by an expert of the data domain, called the analyst. The analyst selects and interprets a subset of the extracted units for obtaining knowledge units having a certain plausibility. As a person searching for gold and having a certain knowledge of the task and of the location, the analyst may use its own knowledge but also knowledge on the domain of data for improving the kdd process. Indeed, the objective of this paper is to show the role that can be played by domain knowledge within the kdd process.

From an operational point of view, the kdd process is performed within a kdd system including databases, data mining modules, and interfaces for interactions, Fig. 1. From data to knowledge units: the objective of the knowledge discovery process is to select, prepare and extract knowledge units from different data sources. For effective reuse, the extracted knowledge units have to be represented within an adequate knowledge representation formalism. e.g. editing and visualization. The kdd process is based on three main operations: selection and preparation of the data, data mining, and finally interpretation of the extracted units (see Figure 1).

A way for the kdd process to take advantage of domain knowledge is to be in connection with an ontology relative to the domain of data, a step towards the notion of knowledge discovery guided by domain knowledge or kddk. In the kddk process, knowledge units that are extracted have still a life after the interpretation step: they must be represented in an adequate knowledge representation formalism for being integrated within an ontology and reused for problem-solving needs. In this way, the results of the knowledge discovery process may be reused for enlarging existing ontologies. The kddk process shows that knowledge representation and knowledge discovery are two complementary tasks: no effective knowledge discovery without domain knowledge! Hereafter, we present various instantiations of the kddk process that are all based on the idea of classification. Classification is a polymorphic process involved in various tasks, e.g. modeling, mining, representing, and reasoning (see also [START_REF] Stumme | Formal concept analysis on its way from mathematics to computer science[END_REF][START_REF] Cimiano | Learning Concept Hierarchies from Text Corpora using Formal Concept Analysis[END_REF][START_REF] Wille | Methods of conceptual knowledge processing[END_REF]). Accordingly, a knowledge-based system may be designed, fed up by the kddk process, and used for problem-solving in application domains, e.g. agronomy, astronomy, biology, chemistry, and medicine (these application domains are studied in the Orpailleur team). A special mention has to be made for Semantic Web activities, involving in particular text mining, content-based document mining, and intelligent information retrieval (see for example [START_REF]Spinning the Semantic Web[END_REF][START_REF] Carpineto | Concept Data Analysis: Theory and Applications[END_REF][START_REF]Handbook on Ontologies[END_REF]).

The paper is organized as follows. In the next section, symbolic methods for kdd and the Coron platform are introduced. Then, research trends in kddk are presented and detailed, showing how knowledge can be embedded at each step of the kdd process. In the last section, an architecture for an integrated kddk system is described, and the kdd and kddk processes are studied with respect to this integrated architecture.

Methods and Systems for KDD

The kdd process is based on data mining methods that are either symbolic or numerical [START_REF] Han | Data Mining: Concepts and Techniques[END_REF][START_REF] Hand | Principles of Data Mining[END_REF][START_REF] Dunham | Data Mining -Introductory and Advanced Topics[END_REF]. The methods that are used in the Orpailleur team are the following (mainly symbolic methods):

-Symbolic methods based on lattice-based classification (concept lattice design or formal concept analysis [START_REF] Ganter | Formal Concept Analysis[END_REF]), frequent itemsets search, and association rule extraction [START_REF] Napoli | A smooth introduction to symbolic methods for knowledge discovery[END_REF]. These symbolic methods are more deeply described in the next subsection. -Numerical methods based on second-order Hidden Markov Models (hmm2, initially designed for pattern recognition) [START_REF] Mari | Temporal and spatial data mining with second-order hidden models[END_REF][START_REF] Mari | Automatic Word Recognition Based on Second-Order Hidden Markov Models[END_REF]. Hidden Markov Models have good capabilities for locating stationary segments, and are mainly used for mining temporal and spatial data. The CarottAge system1 is developed in the Orpailleur team for analyzing numerical spatio-temporal data.

In the following, the focus is on symbolic kdd methods. However, an ongoing research work holds on the combination of symbolic and numerical methods, that is discussed in section 3.4.

Lattice Design, Itemset Search and Association Rule Extraction

Classification problems can be formalized by means of a class of individuals (or objects), a class of properties (or attributes), and a binary correspondence between the two classes, indicating for each individual-property pair whether the property applies to the individual or not [START_REF] Barbut | Ordre et classification -Algèbre et combinatoire (2 tomes)[END_REF][START_REF] Ganter | Formal Concept Analysis[END_REF][START_REF] Carpineto | Concept Data Analysis: Theory and Applications[END_REF]. The properties may be features that are present or absent, or the values of a property that have been transformed into binary variables. Lattice-based classification relies on the analysis of such binary tables and may be considered as a symbolic data mining technique to be used for extracting (from a binary database) a set of concepts organized within a hierarchy (i.e. a partial ordering). The extraction of frequent itemsets, i.e. sets of properties or features of data occurring together with a certain frequency, and of association rules emphasizing correlations between sets of properties with a given confidence, are related activities.

The search for frequent itemsets and association rule extraction are wellknown symbolic data mining methods. These processes usually produce a large number of items and rules, leading to the associated problems of "mining the sets of extracted items and rules". Some subsets of itemsets, e.g. frequent closed itemsets (fcis), allow to find interesting subsets of association rules, e.g. informative association rules. This is why several algorithms are needed for mining data depending on specific applications.

Rare Itemsets and Rules

Among useful patterns extracted from a database, frequent itemsets are usually thought to unfold "regularities" in the data, i.e. they are the witnesses of recurrent phenomena and they are consistent with the expectations of the domain experts. In some situations however, it may be interesting to search for "rare" itemsets, i.e. itemsets that do not occur frequently in the data (contrasting frequent itemsets). These correspond to unexpected phenomena, possibly contradicting beliefs in the domain. In this way, rare itemsets are related to "exceptions" and thus may convey information of high interest for experts in domains such as biology or medicine. For example, suppose an expert in biology is interested in identifying the cause of cardiovascular diseases (CVD) for a given database of medical records. A frequent itemset such as "{elevated cholesterol level, CVD}" may validate the hypothesis that these two items are frequently associated, leading to the possible interpretation "people having a high cholesterol level are at high risk for CVD". On the other hand, the fact that "{vegetarian, CVD}" is a rare itemset may justify that the association of these two itemsets is rather exceptional, leading to the possible interpretation "vegetarian people are at a low risk for CVD". Moreover, the itemsets {vegetarian} and {CVD} can be both frequent, while the itemset {vegetarian, CVD} is rare.

Rare cases deserve special attention because they represent significant difficulties for data mining algorithms. The underlying mining problems have been studied in detail, with different names, e.g. exceptions, negative rules (see for example [START_REF] Liu | Efficient Search of Reliable Exceptions[END_REF][START_REF] Suzuki | Undirected Discovery of Interesting Exception Rules[END_REF][START_REF] Weiss | Mining with rarity: a unifying framework[END_REF][START_REF] Wu | Efficient mining of both positive and negative association rules[END_REF]37]. These approaches are, most of the time, based on adaptions of the general levelwise Apriori algorithm. These methods typically retrieve large sets of rare itemsets and association rules, but these methods may remain incomplete -rare associations are be discovered-either due to an excessive computational cost or to overly restrictive definitions. Thus, such methods may fail to collect a large number of potentially interesting patterns.

By contrast, a framework is proposed in [START_REF] Szathmary | Vers l'extraction de motifs rares[END_REF][START_REF] Szathmary | Symbolic Data Mining Methods with the Coron Platform[END_REF][START_REF] Szathmary | Towards rare itemset mining[END_REF] is specifically dedicated to the extraction of rare itemsets. It is based on an intuitive yet formal definition of rare itemset. Its goal is to provide a theoretical foundation for rare pattern mining, with definitions of reduced representations and complexity results for mining tasks, as well as to develop an algorithmic tool suite (within the Coron platform, see next subsection) together with the guidelines for its use. The method, for computing all rare itemsets is based on two main steps. The first step thereof is the identification of the minimal rare itemsets with an optimized method that limits the exploration to frequent generators only (minimal rare itemsets jointly act as a minimal generation seed for the entire rare itemset family). The second step is performed to restore all rare itemsets from minimal rare itemsets.

The Coron Platform

The Coron platform2 is currently developed in the Orpailleur team [START_REF] Szathmary | Coron: A framework for levelwise itemset mining algorithms[END_REF][START_REF] Szathmary | Zart: A multifunctional itemset mining algorithm[END_REF]. The platform is composed of three main modules: (i) Coron-base, (ii) AssRuleX, (iii) pre-processing and post-processing modules. The Coron-base module is aimed at extracting different kinds of itemsets, e.g. frequent itemsets, frequent closed itemsets, minimal generators, etc. The module contains a collection of important data mining algorithms, such as Apriori, Close, Pascal, Titanic, Charm, Eclat, together with adapted algorithms such as Zart and Eclat-Z (plus some others). This large collection of (efficient) algorithms is one of the main characteristics of the Coron platform. Knowing that each of the algorithms has advantages and disadvantages with respect to the form of the data to be mined, and since there is no universal algorithm for processing any arbitrary dataset, the Coron-base module offers to the user the choice of the algorithm that is the best suited for his needs.

The second module of the system, AssRuleX (Association Rule eXtractor) generates different sets of association rules, such as informative rules, generic basis, and informative basis.

For supporting the whole life-cycle of a data mining task, the Coron platform proposes modules for cleaning the input dataset and reduce its size if necessary. The module RuleMiner facilitates the interpretation and the filtering of the extracted rules. The association rules can be filtered by (i) attribute, (ii) support, and/or (iii) confidence.

The Coron platform is developed entirely in Java, allowing portability. The system is operational, and has been tested within several research projects within the team [START_REF] D'aquin | Case base mining for adaptation knowledge acquisition[END_REF][START_REF] Maumus | Fouille de données biomédicales complexes: extraction de règles et de profils génétiques dans le cadre de l'étude du syndrome métabolique[END_REF].

A Data-Mining Methodology with the Coron Platform

A methodology was initially designed for mining biological cohorts, but it can be generalized to any kind of database. It is worth to mention that the whole kddk process is guided by an analyst. The role of the analyst is important with respect to the following tasks: selecting the data and interpreting the extracted units. This methodology is associated to the Coron platform, that offers various tools necessary for its application in a single platform (nevertheless another platform can be used).

The methodology consists of the following steps: (1) Definition of the study framework, (2) Iterative step: data preparation and cleaning, pre-processing step, processing step, post-processing step, validation of the results and Generation of new research hypotheses, feedback on the experiment. The life-cycle of the methodology is shown in Figure 2.

Definition of the Study Framework.

The analyst defines a specific field for the analysis (called hereafter "framework"). Thus, he may choose the type of data he wants to work on, e.g. biological data, genetic data, or both, unrelated individuals or families, focus on a special metabolic network or on a particular syndrome.

Iterative

Fig. 2. The life cycle of KDD within Coron

values. Moreover, several actions for converting the data can be done at this step, such as:

(1) Addition/creation of new attributes for helping the extraction of association rules by combining attributes (intersection, union and complementary).

(2) Deletion of attributes that are not interesting in the chosen biological framework. This option is close to the projections described below.

(3) Discretization for transforming continuous data into Boolean values, e.g. by using a threshold defined in the literature, or by separating values of each continuous variable into quartiles. Data filtering (pre-processing). Several actions can be carried out that correspond to operations in set theory: complement, union and intersection (with operations of additions and projections).

(1) Apply projections: on the rows: i.e. selecting individuals with one or more attributes specified by the expert, on the columns: i.e. selecting (or deleting) some attributes.

(2) Consider the complement of a set of individuals satisfying a rule, defined by the set of individuals that do not satisfy this rule.

The output of the filtering process is considered as a new dataset on which data mining procedures can be applied again. Applying the data mining procedure. This methodology is related to symbolic data mining methods, as, in particular, frequent itemset search and association rule extraction. With the help of the analyst, the necessary thresholds values can be set for quality measures such as the minimum support and the minimum confidence for generating frequent itemsets and association rules, respectively. As the process is iterative and interactive, the analyst can change these thresholds during a next iteration to carry out new experiments. Post-processing. After filtering and visualizing the rules, those rules containing the most interesting attributes can be found. If a less relevant attribute is always present in the rules, it can be considered as "noisy", and removed from the input dataset. This means that the dataset is another time modified for a new association rule extraction.

The iterative step can be repeated until the most relevant rules are found. The interpretation of the analyst is mobilized both for rule mining and result visualization. Rule-mining. In the rule mining step, the analyst has also to make several choices:

-Choosing rules with a specific form: e.g. selecting rules that only have one attribute on their left side. -Selecting rules with an attribute of interest from the point of view of the analyst, on the left hand side, on the right hand side, or on both sides. -Classifying the extracted rules in ascending or descending order according to their support or confidence values, or according to other statistical values [START_REF] Cherfi | Towards a text mining methodology using association rules extraction[END_REF]. The classification of rules mining step may be dependent on numerical measures, e.g. support and confidence, or on domain knowledge as shown in some experiments [START_REF] Janetzko | Knowledge-based selection of association rules for text mining[END_REF]. -Selecting rules with a support belonging to a given interval [a, b]; returning rules with a support less than (or more than) or equal to a given value c. These selections can also be applied with the other statistical measures cited above.

Visualization of the results. A visualization method adapted to symbolic data mining method procedure has to be chosen. For frequent itemset search leading to the extraction of less frequent itemsets, concept lattices may be used beneficially [START_REF] Jay | Using formal concept analysis for mining and interpreting patient flows within a healthcare network[END_REF].

Research Directions for KDDK

The principle summarizing kddk can be read as follows: going "from complex data units to complex knowledge units guided by domain knowledge" (kddk) or "knowledge with/for knowledge". This principle is discussed below, along research activities such as graph mining, spatio-temporal data mining, text mining and Semantic Web, knowledge discovery in life sciences, combining symbolic and numerical data mining methods for hybrid mining, and finally mining a knowledge base, a kind of "meta-knowledge discovery process". All these research activities share the fact that the mining process is guided and enhanced by domain knowledge (similar ideas are also discussed in [START_REF] Stumme | Conceptual Knowledge Processing with Formal Concept Analysis and Ontologies[END_REF][START_REF] Wille | Methods of conceptual knowledge processing[END_REF]).

KDDK and the Mining of Complex Data

Lattice-based classification, formal concept analysis, itemset search and association rule extraction, are suitable paradigms for symbolic kddk, that may be used for real-sized applications [START_REF] Valtchev | Formal concept analysis for knowledge discovery and data mining: The new challenges[END_REF]. Global improvements may be carried on the ease of using of the data mining methods, on the efficiency of the methods [START_REF] Kuznetsov | Comparing performance of algorithms for generating concept lattices[END_REF], and on adaptability, i.e. the ability to fit evolving situations with respect to the constraints that may be associated with the kddk process. Accordingly, the research work presented hereafter is in concern with the extension of symbolic methods to complex data, e.g. objects with multi-valued attributes, relations, graphs, texts, and real world data.

KDDK in databases of chemical reactions.

The mining of chemical chemical reaction databases is an important task for at least two reasons (see also [START_REF] Kuznetsov | Machine Learning and Formal Concept Analysis[END_REF]): (i) the first reason is the challenge represented by this task regarding kddk to be set on, (ii) the second reason lies in the industrial needs that can be met whenever substantial results are obtained. Chemical reactions are complex data, that may be modeled as undirected labeled graphs. They are the main elements on which synthesis in organic chemistry relies, knowing that synthesis -and accordingly chemical reaction databases-are of first importance in chemistry, but also in biology, drug design, and pharmacology. From a problem-solving point of view, synthesis in organic chemistry must be considered at two main levels of abstraction: a strategic level where general synthesis methods are involved -a kind of meta-knowledge-and a tactic level where specific chemical reactions are applied. An objective for improving computer-based synthesis in organic chemistry is aimed at discovering general synthesis methods from currently available chemical reaction databases for designing generic and reusable synthesis plans. A preliminary research work has been carried on in the Orpailleur team [START_REF] Napoli | An Experiment on Knowledge Discovery in Chemical Databases[END_REF], based on frequent levelwise itemset search and association rule extraction, and applied to standard chemical reaction databases. This work has given substantial results for the expert chemists. At the moment, for extending this first work, a graph-mining process is used for extracting knowledge from chemical reaction databases, directly from the molecular structures and the reactions themselves, This research work is currently under development, in collaboration with chemists, and is in accordance with needs of chemical industry [START_REF] Pennerath | La fouille de graphes dans les bases de données réactionnelles au service de la synthèse en chimie organique[END_REF].

KDDK and the mining of spatio-temporal data. Temporal and spatial data are complex data to be mined because of their internal structure, that can be considered as multi-dimensional. Indeed, spatial data may involve two or three dimensions for determining a region and complex relations as well for describing the relative positions of regions between each others (as in the RCC-8 theory for example [START_REF] Ber | Design and comparison of lattices of topological relations for spatial representation and reasoning[END_REF][START_REF] Napoli | On characterization and discovery of minimal unexpected patterns in rule discovery[END_REF]). Temporal data may present a linear but also a two-dimensional aspect, when time intervals are taken into account and have to be analyzed (using Allen relations for example). In this way, mining temporal or spatial data are tasks related to kddk. Spatial and temporal data may be analyzed with numerical methods such as Hidden Markov Models, but also with symbolic methods, such as levelwise search for frequent sequential or spatial patterns.

In the medical domain, the study of chronic diseases is a good example of kddk process on spatio-temporal data. An experiment for characterizing the patient pathway using the extraction of frequent patterns, sequential and not sequential, from the data of the pmsi3 system associated with the "Lorraine Region" is currently under investigation. Details on this work are given in [START_REF] Jay | Using formal concept analysis for mining and interpreting patient flows within a healthcare network[END_REF].

KDDK, Text Mining and Semantic Web

KDDK and text mining. The objective of a text mining process is to extract new and useful knowledge units in a large set of texts [START_REF] Janetzko | Knowledge-based selection of association rules for text mining[END_REF][START_REF] Cimiano | Learning Concept Hierarchies from Text Corpora using Formal Concept Analysis[END_REF][START_REF] Cherfi | Towards a text mining methodology using association rules extraction[END_REF]. The text mining process shows some specific characteristics due to the fact that texts are complex objects written in natural language. The information in a text is expressed in an informal way, following linguistic rules, making the mining process more complex. To avoid information dispersion, a text mining process has to take into account -as much as possibleparaphrases, ambiguities, specialized vocabulary, and terminology. This is why the preparation of texts for text mining is usually dependent on linguistic resources and methods. In addition, from a kddk perspective, the text mining process is aimed at extracting new knowledge units from texts with the help of background knowledge. The interpretation of a text relies on knowledge units shared by the authors and the readers. A part of these knowledge units is expressed in the texts and may be extracted by the text mining process. Another part of these knowledge units, background knowledge, is not explicitly expressed in the text and is useful to relate notions present in a text, to guide and to help the text mining process. Background knowledge is encoded in a knowledge base associated to the text mining process. Text mining is especially useful in the context of semantic Web, for manipulating textual documents by their content.

The studies on text mining carried out in the Orpailleur team hold on realworld texts in application domains such as astronomy, biology and medicine, using mainly symbolic data mining methods such as i.e. frequent itemset search and association rule extraction [START_REF] Bendaoud | Textbased ontology construction using relational concept analysis[END_REF]. This is in contrast with text analysis approaches dealing with specific language phenomena. The language in texts is considered as a way for presenting and accessing information, and not as an object to be studied for its own. In this way, the text mining process may be involved in a loop used to enrich and to extend linguistic resources. In turn, linguistic and ontological resources can be exploited to guide a "knowledge-based text mining process".

KDDK within the context of Semantic Web.

Semantic Web constitutes a good platform for experimenting ideas on knowledge discovery -especially text mining-, knowledge representation and reasoning. In particular, the knowledge representation language associated with the Semantic Web is the owl language, based on description logics (or dls, see [START_REF]The Description Logic Handbook[END_REF]). In owl, knowledge units are represented within concepts (or classes), with attributes (properties of concepts, or relations, or roles), and individuals. The hierarchical organization of concepts (and relations) relies on a subsumption relation that is a partial ordering. The inference services are based on subsumption, concept and individual classification, two tasks related to "classification-based reasoning". Concept classification is used for inserting a new concept at the right location in the concept hierarchy, searching for its most specific subsumers and its most general subsumees. Individual classification is used for recognizing the concepts an individual may be an instance of. Furthermore, classification-based reasoning may be extended into case-based reasoning (cbr), that relies on three main operations: retrieval, adaptation, and memorization. Given a target problem, retrieval consists in searching for a source (memorized) problem similar to the target problem. Then, the solution of the source problem is adapted to fulfill the constraints attached to the target problem. When there is enough interest, the target problem and its solution may be memorized in the case base to be reused. In the context of a concept hierarchy, retrieval and adaptation may be both based on classification (and "adaptation-guided retrieval" [START_REF] Fuchs | An Algorithm for Adaptation in Casebased Reasoning[END_REF]).

In the framework of Semantic Web, the mining of textual documents on the Web, or "Web document mining" [START_REF] Stumme | Towards Semantic Web Mining[END_REF], can be considered from two main points of view: (i) mining the content of documents, involving text mining, (ii) mining the internal and external -hypertext links-structure of pages, involving information extraction. Web document mining is a major technique for the semi-automatic design of real-scale ontologies, the backbone of Semantic Web. In turn, ontologies are used for annotating the documents, enhancing document retrieval and document mining. In this way, Web document mining improves annotation, retrieval, and the understandability of documents, with respect to their structure and their content. The extracted knowledge units can then be used for completing domain ontologies, that, in turn, guide text mining, and so on.

A research carried on in the team aims at understanding the structure of documents for analyzing and for improving text mining. The design of a system for extracting information units -that have to be turned into knowledge units after interpretation-from Web pages involves a wrapper-based machine learning algorithm combined with a classification-based reasoning process, taking advantage of a domain ontology implemented within the Web Ontology Language (owl). The elements returned by the process are used as "semantic annotations" for understanding and manipulating the documents with respect to their structure and content [START_REF] Ténier | Semantic annotation of webpages[END_REF][START_REF] Ténier | Instantiation of relations for semantic annotation[END_REF]. The application domain of this research work is the study of research themes in the European Research Community. This study supports the analysis of research themes and detection of research directions.

KDDK for Life Science: Organizing and Navigating Biological Sources

The application domains that are currently investigated at the moment by the Orpailleur team are related with life sciences, with a particular emphasis on biology (bioinformatics) and medicine. Indeed, there are various reasons explaining why life sciences are a major application domain. In general, life sciences are getting more and more importance as a domain application for computer scientists. In this context, the collaboration between biologists and computer scientists is very active, and the understanding of biological systems provides complex problems for computer scientists. When these problems are solved (at least in part), the solutions bring new ideas not only for biologists but also for computer scientists in their own research work. Thus, advances in research appear on both sides, life and computer sciences. Knowledge discovery is gaining more and more interest and importance in life sciences for mining either homogeneous databases (dbs) such as protein sequences or structures, heterogeneous dbs for discovering interactions between genes and environment, or between genetic and phenotypic data, especially for public health and pharmacogenomics domains. The latter case appears to be one main challenge in knowledge discovery in biology and involves knowledge discovery from complex data and thus kddk. The interactions between researchers in biology and researchers in computer science improve not only knowledge about systems in biology, but knowledge about computer science as well. Solving problems for biologists using kddk methods may involve the design of specific modules that, in turn, leads to adaptations of the kddk process, especially in the preparation of data and in the interpretation of the extracted units.

A research work carried on in the team is in concern with the search and the access to relevant biological sources (including biological dbs) satisfying a set of given constraints, expressed with respect to concepts lying in a domain ontology -as in the BioRegistry repository [START_REF] Smaïl-Tabbone | Bioregistry: A structured metadata repository for bioinformatic databases[END_REF]. The sources may be described in terms of these concepts, yielding a formal context, from which a concept lattice can be built [START_REF] Napoli | Querying a Bioinformatic Data Sources Registry with Concept Lattices[END_REF]. Given a specific query, a lattice-based information retrieval process is set on. The classification of the query in the lattice returns a ranked list of relevant sources, according to the characteristics of the sources with respect to the characteristics of the query (see [START_REF] Messai | Br-explorer: An fcabased algorithm for information retrieval[END_REF]). The next step is to generalize the approach, and to use a "fuzzy concept lattice" and "fuzzy formal concept analysis" (see for example [START_REF] Quan | Automatic generation of ontology for scholarly semantic web[END_REF]). Moreover, studies hold on complex question answering methods taking into account fuzzy concept lattices, nested queries (intersection, union, and complement), analogical queries, and composition of answers elements. These techniques are still under study.

Another challenge is to extract knowledge from heterogeneous dbs for understanding interactions between clinical, genetic and therapeutic data. For example, a given genotype, i.e. a set of selected gene versions, may explain adverse clinical reactions (e.g. hyperthermy, toxic reaction. . . ) to a given therapeutic treatment. This requires first the integration of both genomic and clinical data into a data warehouse on which kddk methods have to be applied. This research work is connected with Semantic Web purposes, and in particular with the following elements: (i) data preparation and extracted units interpretation based on domain ontologies, (ii) knowledge edition for building and enriching domain ontologies, (iii) knowledge management for access to knowledge units, querying and reasoning (for problem-solving).

Combining Symbolic and Numerical Methods for KDDK

Why combining symbolic and numerical methods.

hmm2 have proved to be a valuable tool for extracting knowledge from complex numerical data, e.g. spatio-temporal data. In this way, the CarottAge system has been involved for data mining purposes in two main application domains, namely biology and agronomy. In collaboration with biologists, genome segmentation and interpretation have been investigated [START_REF] Eng | Data mining using hidden markov models (HMM2) to detect heterogeneities into bacteria genomes[END_REF]. In collaboration with agronomists, spatial and temporal land-use data have been mined for extracting and understanding crop successions, i.e. the way how crops are carried out during a given period of time [START_REF] Ber | Studying crop sequences with CarrotAge, a HMM-based data mining software[END_REF][START_REF] Mari | Temporal and spatial data mining with second-order hidden models[END_REF]. In these two applications, the effort has focused on two main points, with respect to the questions of the biologists and of the agronomists: (i) the elaboration of a mining process for extracting dependencies in temporal and spatial data involving an unsupervised classification process based on hmm2, (ii) the specification of associated and adequate visualization tools giving a synthetic view of the extraction process results to the experts in charge of interpreting the extracted classes and/or of specifying new experiment directions.

However, some operations remain very difficult to be carried out and could be eased using symbolic methods: (i) the modeling of the hmm2 process for a set of given data, (ii) the interpretation of units extracted by hmm2, (iii) the organization and the visualization of the extracted units for further reuse, e.g. as knowledge units in a knowledge-based system. A proposition is to combine hmm2 with symbolic methods, such as case-based reasoning and concept lattices, for helping the modeling and interpretation process.

A challenge is to set on a methodology for hybrid kddk, coupling hmm2 and symbolic methods, that can be adapted and reused as a general kddk method on various data, leading to a multi-functional and multi-purpose kddk system.

Combining CBR and HMM. Case-based reasoning seems to be especially interesting since researchers in an application domain often use their own knowledge or knowledge resulting from first experiments to improve steps within the data mining process, e.g. modeling and interpretation. In this way, the elements of the cases within the case-based reasoner can be composed of knowledge units about parameters of the hmm2, and as well of knowledge units on the design -modeling, data preparation-, and the interpretation -relying on ontological knowledge-of the hmm2. In addition, cbr can be of great interest for recording mining strategies that can be adapted and reused in similar situations. Indeed, a study on cbr for guiding mining scenarios in a given situation -with retrieval and adaptation of a similar situation-has not yet been carried on and should give substantial results. More generally, hmm2based data mining process may take advantage of being coupled with cbr, that can be used at a strategic level for guiding the hmm2-based data mining process.

Combining concept lattices and HMM.

For their part, concept lattices can be used to organize and to visualize the results of the hmm2-based data mining process. The objects resulting of the application of the hmm2 process can be characterized by a set of properties. For example, in a spatio-temporal framework, space regions may be considered as objects and characteristics of the region at a given time can be considered as properties, yielding a kind of formal context. In addition, itemsets and association rules may also be extracted from such a context, offering an easy way of interpreting results of the hmm2 process.

The analysis of complex data in biology also calls for the coupling of symbolic and numerical data mining methods. There are complex data on which hmm2 show a good behavior, for recognizing and extracting regular structures. Such complex data hold on interactions between processes or agents, such as data from transcriptomic biochips -dna chips or microarrays-experiments (used for extracting knowledge on interactions between plants and microorganisms). Still, an important objective of this kind of study is to investigate and to understand more deeply the modeling of biological systems, at symbolic and numerical levels.

Meta-knowledge Discovery of Mining Knowledge Bases

The Kasimir system. The main tasks of the Kasimir system are decision support and knowledge management for the treatment of cancer. The system is developed within a multidisciplinary research project in which participate researchers from different community (computer science, ergonomics, and oncology). For a given cancer localization, a treatment is based on a protocol similar to a medical guideline. For most of the cases (about 70%), a straightforward application of the protocol is sufficient and provides a solution, i.e. a treatment, that can be directly reused. A case out of the 30% remaining cases is said to be out-of-the-protocol, i.e. either the protocol does not provide a treatment for this medical case, or the proposed solution raises some difficulties, e.g. contraindication, treatment impossibility, etc. For such an out-of-the-protocol case, oncologists try to adapt the protocol. In turn, these adaptations can be used to propose evolutions of the protocol based on a confrontation with actual cases. The idea is then to make suggestions for protocol evolutions based on frequently performed adaptations.

In knowledge-intensive cbr, the reuse of cases is generally based on adaptation, the goal of which is to solve the target problem by adapting the solution of a source case. The adaptation process is based on adaptation knowledge that -for the main part-is domain-dependent, and thus needs to be acquired for a new application of cbr. Adaptation knowledge plays a key issue in applications, e.g. in knowledge-intensive case-based reasoning systems [START_REF] Aamodt | Knowledge-Intensive Case-Based Reasoning and Sustained Learning[END_REF].

In parallel, the Semantic Web technology relies on the availability of large amount of knowledge in various forms [START_REF]Spinning the Semantic Web[END_REF][START_REF]Handbook on Ontologies[END_REF]. The acquisition of ontologies is one of the important issues that is widely explored in the Semantic Web community. Moreover, the acquisition of decision and adaptation knowledge for the Semantic Web has not been so deeply explored, though this kind of knowledge can be useful in numerous situations. For example, given a decision protocol and an adaptation knowledge base, the Kasimir system can be used to apply and/or to adapt the protocol to specific medical situations.

Semi-automatic acquisition of adaptation knowledge.

The goal of adaptation knowledge acquisition (aka) is to mine a case base, to extract adaptation knowledge units, and to make these units operational. Until now, the research work on cbr in the Orpailleur team has mainly focused on the design of algorithms and knowledge representation formalisms for implementing the adaptation process in a cbr system. A next step is to investigate the aka process, a research topic that has still not received so much in the cbr community. A parallel research topic is to apply aka to the extraction of decision knowledge units. Indeed, adaptation knowledge is closely related with decision theory, e.g. the Wald pessimistic criterion is frequently applied when pieces of information about a patient are missing.

Accordingly, the objective of the research work on aka is to study how kdd techniques can be used for feeding a knowledge server embedded in a semantic portal -as the Kasimir semantic portal [START_REF] D'aquin | Knowledge Edition and Maintenance Tools for a Semantic Portal in Oncology[END_REF]-and thus to instantiate the kddk process. In the Kasimir semantic portal, owl-based formalisms for representing medical ontologies, decision protocols (the case base), and adaptation knowledge, are designed. Web services associated to the cbr process are developed. Several protocols are implemented, with a few of them including adaptation knowledge.

Practically, aka can be considered from two main points of view. aka from experts is based on 'manual" analysis of documents related to current problems. The aka from expert process leads to the elaboration of adaptation rules, depending on formal parameters and associated with explanations. The adaptation rules are human-understandable -thanks to explanations-but they need additional knowledge for instantiating the parameters and being applied (more on aka from experts is given in [START_REF] Lieber | Adaptation knowledge acquisition, a study for breast cancer treatment[END_REF][START_REF] Mollo | Usage des ressources, adaptation des savoirs et gestion de l'autonomie dans la décision thérapeutique[END_REF]).

Semi-automatic aka is based on the principles of kdd, and involves data preparation, data mining, and interpretation of the extracted units, under the control of an analyst. The input of the aka process is a set of adaptations -thus elements at the knowledge level-and the output is a set of adaptation rules. Such an adaptation rule is an operational association rule, that lack explanations. Mixed aka combines aka from experts and semi-automatic aka for supplying operational and human-understandable adaptation knowledge.

In the current experiments within the Kasimir system, semi-automatic aka is based on frequent itemset search. A system for aka, named CabamakA-case base mining for aka, is currently under development within the Kasimir system and relies on semi-automatic aka [START_REF] D'aquin | Case base mining for adaptation knowledge acquisition[END_REF]. The CabamakA system analyzes a simple representation of the variations Δu between units of knowledge u 1 and u 2 , where Δu encodes the substitutions transforming u 1 into u 2 . The variations are represented in an expressive dl-based formalism, allowing a high-level expression of the extracted adaptation rules.

Beyond cbr, such a research work can be useful for ontology alignment: an alignment expresses a correspondence between the elements of two ontologies, but it could also express the variations between corresponding elements, within a rich representation formalism for the variations.

Towards an Integrated KDDK System

From a global point of view, the research objectives for kddk can be summarized as follows:

-A methodology for a "knowledge discovery from complex data guided by domain knowledge process" (kddk), i.e. a process leading from complex data units to complex knowledge units taking advantage of domain knowledge, at each step of the knowledge discovery process. -A combination of symbolic and numerical data mining methods for setting up a complete and hybrid mining methodology to be applied on various types of data. -An implementation of the "knowledge discovery from complex data guided by domain knowledge process" within an operational system, to be used on a large set of data types, e.g. textual documents, genomic data, spatiotemporal data, graphs, and even on sets of knowledge units (a kind of metaknowledge mining), i.e. mining a knowledge base instead of a database. -Accordingly, the design of a kddk system, based on the above principles, and involved in application domains such as astronomy, agronomy, biology, chemistry, medicine, for decision support and problem-solving.

From a middle-term perspective, a system for kddk can be considered as a "decentralized system" the architecture of which is described hereafter. Fig. 3. An architecture for a system aimed at "knowledge discovery (from complex data) guided by domain knowledge process (kddk)". The classical kdd process can be read from left to right, while, by contrast, the kddk system can be read from right to left.

(2) (4) (3) (5) (7A) (7B) (8A) (8B) (9A) (6A) (6B) (9B) (10B) (11B) User A User B Semantic portal Knowledge base (1) (1) (1)
-One or several ontologies (knowledge bases) include knowledge from different domains with different points of view, and as well, a case base. A set of services are related through a semantic portal, for knowledge editing, navigating, and visualizing the ontologies. -An inference engine provides, in association with the knowledge bases, a collection of inference rules for problem-solving purposes, among which subsumption, classification (lattice-based classification, clustering), case-based reasoning. Reasoning services are present for handling concrete datatypes such as strings or numbers (and possibly, for controlling procedural or functional reasoning modes if-needed). -A set of heterogeneous databases holding on a domain to be mined for providing knowledge units enriching domain ontologies. -A platform for kddk proposes a collection of data mining modules -such as the Coron platform-and a set of services for data preparation and extracted unit interpretation.

Moreover, the system has to provide channels for allowing communications with human agents, such as experts and end-users. The resulting kddk system architecture has to be reusable in any application domain. Accordingly, the integration of such a kddk system in the framework of the semantic Web can be seen as follows. The data sources, i.e. databases, sets of documents, are explored, navigated, and queried, under the supervision of an analyst, thanks to a kddk process guided by knowledge bases of the domain. The data are prepared and manipulated by the kddk process, while the knowledge units are validated by the analyst, and then manipulated by the inference engine.

The figure 3 presents the architecture proposal for a kddk system, in which different scenarios can be made operational. Heterogeneous sources (e.g. databases) feed the kdd system (1), under the supervision of an analyst (2), using available domain knowledge (3). The kdd system returns new knowledge units for extending and enriching a knowledge base (4), that may be queried through a semantic portal (5) by distant geographically distributed users (users A and B). The users A and B query the portal (6A, 6B), that in turn may use the services of a knowledge base and the associated inference engine (7A, 7B). When the available knowledge provides, with the help of the inference engine, an answer to the request (8A), this answer is transmitted to the user (9A). Otherwise (8B), the request is transferred in a filtering module used by the kdd system (9B) for mining the available data, trying to extract information related to the request. The resulting extracted knowledge units relying on this filter (10B) may provide an answer to the user (11B).

Conclusion

In this paper, we have presented the research work carried out in the Orpailleur team at loria. Multiple and combined aspects of knowledge discovery and knowledge processing have been introduced and discussed: symbolic kdd methods such as lattice-based classification itemset search, and association rule extraction, and numeric methods such as hmm2. Next, the kdd process has been considered from a knowledge representation perspective, explaining how and why the kdd process may take advantage of domain knowledge embedded in ontologies relative to the domain of data. This perspective leads to the idea of kddk, for knowledge discovery (from complex data) guided by domain knowledge. The kddk process is based on classification tasks, for modeling, representing, reasoning, and discovering. Various instantiations of the kddk process have been described, among which the mining of molecular graphs -for knowledge discovery in chemical reaction databases-, text mining and Semantic Web for designing and enlarging ontologies from documents, knowledge discovery in life sciences, and hybrid knowledge discovery, combining numerical and symbolic methods for data mining. An original experiment has also been introduced and discussed: meta-knowledge mining, or mining a knowledge base instead of a database. This research work has been carried out for the need of adaptation knowledge acquisition (aka), that is a promising research domain, and that can be reused for mining various kind of strategical knowledge units, e.g. decision knowledge units. At the end of the paper, an architecture of an integrated kddk system has been proposed and discussed.

  Step. Data preparation and cleaning. Data cleaning is necessary. This step includes the detection and the possible removal of incomplete and out-of-range

Analyst

Validation of the results and generation of new research hypotheses.

	The evaluation of the rules can be done either by statistical tests, data analysis
	methods, i.e. automatic classification, component analysis, or with knowledge-

based methods, e.g. classification-based reasoning, formal concept analysis. The generated results allow the expert to suggest new directions of research. Accordingly, these new hypotheses are tested by new experiments, for example, managed at the biological level, like genetic epidemiological studies or wet laboratory experiments.

CarottAge is a free software developed in the Orpailleur team, with a gpl license since

2002, see http://www.loria.fr/ ∼ jfmari/App/

http://coron.loria.fr

For "Programme de Médicalisation des Systèmes d'Informations". This is the name of the information system collecting the administrative data for an hospital.


Amedeo Napoli
email: amedeo.napoli@loria.fr

Why and How Knowledge Discovery Can Be Useful for Solving Problems with CBR (Extended Abstract)

Keywords: knowledge discovery in databases, Formal Concept Analysis, knowledge representation and reasoning

In this talk, we discuss and illustrate links existing between knowledge discovery in databases (KDD), knowledge representation and reasoning (KRR), and case-based reasoning (CBR). KDD techniques especially based on Formal Concept Analysis (FCA) are well formalized and allow the design of concept lattices from binary and complex data. These concept lattices provide a realistic basis for knowledge base organization and ontology engineering. More generally, they can be used for representing knowledge and reasoning in knowledge systems and CBR systems as well.

Introduction

In this talk, we will discuss and illustrate links existing between knowledge discovery in databases (KDD), case-based reasoning (CBR), and knowledge representation and reasoning (KRR). KDD techniques especially based on Formal Concept Analysis (FCA) are well formalized and allow the design of concept lattices (from binary and complex data). These concept lattices provide a realistic basis for knowledge base organization, ontology engineering, and hierarchical reasoning. They can be used as a backbone for an ontology by transforming formal concepts into concepts representing knowledge [START_REF] Bendaoud | Pactole: A methodology and a system for semi-automatically enriching an ontology from a collection of texts[END_REF][START_REF] Bendaoud | Formal concept analysis: A unified framework for building and refining ontologies[END_REF]. From the point of view of CBR, concept lattices may be used for a series of tasks such as:

case retrieval: assessing similarity between cases with similarity paths, and case or information retrieval [START_REF] Messai | Many-valued concept lattices for conceptual clustering and information retrieval[END_REF][START_REF] Messai | Using domain knowledge to guide lattice-based complex data exploration[END_REF], -case adaptation: traversing the lattice structure for building adaptation paths between cases [START_REF] Diaz-Agudo | Classification based retrieval using formal concept analysis[END_REF][START_REF] Diaz-Agudo | Formal Concept Analysis as a support technique for CBR[END_REF], -case learning: organizing and updating the case base and the underlying concept lattice.

Moreover, FCA is related to data mining techniques, such a as itemset search and association rule extraction. The use of such techniques can improve the scalability of FCA w.r.t. the volume of data to be analyzed [START_REF] Szathmary | Constructing iceberg lattices from frequent closures using generators[END_REF][START_REF] Szathmary | Efficient Vertical Mining of Frequent Closures and Generators[END_REF].

I. Bichindaritz and S. Montani (Eds.): ICCBR 2010, LNAI 6176, pp. 12-19, 2010. c Springer-Verlag Berlin Heidelberg 2010

By contrast, we will also investigate some aspects of CBR that can be reused in KDD and ontology learning, such as searching and managing ontology design patterns.

Knowledge Discovery in Databases (KDD)

Knowledge discovery in databases (KDD) consists in processing a large volume of data in order to extract useful and reusable knowledge units from these data. An expert of the data domain, the analyst, is in charge of guiding the extraction process, on the base of his/her objectives and domain knowledge. The extraction process is based on data mining methods returning information units from the data. The analyst selects and interprets a subset of the units for building "models" that may be further interpreted as knowledge units with a certain plausibility. The KDD process is performed with a KDD system based on components such as domain ontologies, data mining modules (either symbolic or numerical), and interfaces for interactions with the system, e.g. editing and visualization.

The KDD process can be considered along three main steps: data preparation, data mining, and interpretation of the extracted units. At each step, domain knowledge, possibly represented within ontologies, can play a substantial role for improving the KDD process [START_REF] Lieber | First Elements on Knowledge Discovery guided by Domain Knowledge (KDDK)[END_REF]. Moreover, data mining methods can be either numeric or symbolic. In this talk, we will mainly focus on the second type and especially itemset search, association rule extraction, and Formal Concept Analysis (and extensions) [START_REF] Napoli | A smooth introduction to symbolic methods for knowledge discovery[END_REF].

The search for frequent itemsets consists in extracting from binary tables itemsets occurring with a support that must be greater than a given threshold [START_REF] Pasquier | Discovering frequent closed itemsets for association rules[END_REF][START_REF] Bastide | Mining frequent patterns with counting inference[END_REF][START_REF] Szathmary | Efficient Vertical Mining of Frequent Closures and Generators[END_REF][START_REF] Zaki | Efficient algorithms for mining closed itemsets and their lattice structure[END_REF]. Given a set of objects and a set of properties, an item corresponds to an attribute or a property of an object, and an itemset (a pattern) to a set of items. The support of an itemset corresponds to the proportion of objects owning the itemset, with respect to the whole population of objects. An itemset is frequent if its support is greater than a given frequency threshold σ S : a proportion at least equal to σ S of objects own all items included in the itemset. The search for frequent itemsets is based on monotony constraints (base of the Apriori algorithm [START_REF] Agrawal | Fast Discovery of Association Rules[END_REF]). The search of frequent itemsets begins with the search of frequent itemsets of minimal length (or length 1). Then, the frequent itemsets are recorded and combined together to form the candidate itemsets of greater length. The non-frequent itemsets are discarded and all their super-itemsets. The candidate itemsets are tested and the process continues in the same way, until no more candidates can be formed.

From frequent itemsets it is possible to generate association rules of the form A -→ B relating an itemset A with an itemset B, that can be interpreted as follows: the objects owning A also own B with a support and a confidence [START_REF] Agrawal | Fast Discovery of Association Rules[END_REF][START_REF] Pasquier | Pruning closed itemset lattices for association rules[END_REF]. More precisely, an association rule A -→ B has a support defined as the support of the itemset A ∪ B and a confidence defined as the quotient support(A ∪ B)/support(A) (that can be interpreted as a conditional probability). Then, a rule is valid if its confidence is greater than a confidence threshold σ C , and its support is greater than the frequency threshold for itemsets σ S (a valid rule can only be extracted from a frequent itemset).

The numbers of extracted itemsets and rules may be very large, and thus there is a need for pruning the sets of extracted itemsets and rules for ensuring a subsequent interpretation of the extracted units. This is especially true when the interpretation has to be done -and this is usually the case-by the analyst who is in charge of interpreting the results of the KDD process [START_REF] Brachman | The Process of Knowledge Discovery in Databases[END_REF].

Actually, the search for itemsets and association rules are related to concept lattices: they correspond to a breadth-first search in the concept lattice associated with the formal context under study.

Formal Concept Analysis and Derived Formalisms

The Basic Framework of FCA

The framework of FCA is fully detailed in [START_REF] Ganter | Formal Concept Analysis[END_REF]. FCA starts with a formal context (G, M, I) where G denotes a set of objects, M a set of attributes, or items, and I ⊆ G × M a binary relation between G and M . The statement (g, m) ∈ I is interpreted as "the object g has attribute m". Two operators (•) define a Galois connection between the powersets (2 G , ⊆) and

(2 M , ⊆), with A ⊆ G and B ⊆ M : A = {m ∈ M | ∀g ∈ A : gIm} and B = {g ∈ G | ∀m ∈ B : gIm}. For A ⊆ G, B ⊆ M , a pair (A, B)
, such that A = B and B = A, is called a formal concept. In (A, B), the set A is called the extent and the set B the intent of the concept (A, B). Concepts are partially ordered by

(A 1 , B 1 ) ≤ (A 2 , B 2 ) ⇔ A 1 ⊆ A 2 (⇔ B 2 ⊆ B 1 )
. With respect to this partial order, the set of all formal concepts forms a complete lattice called the concept lattice of (G, M, I). As already mentioned above, natural links exist between between concept lattices, itemsets, and association rules [START_REF] Bastide | Mining frequent patterns with counting inference[END_REF][START_REF] Zaki | Efficient algorithms for mining closed itemsets and their lattice structure[END_REF][START_REF] Szathmary | Constructing iceberg lattices from frequent closures using generators[END_REF].

When one consider non binary contexts, e.g. numerical or interval data, conceptual scaling is often used for binarizing data and for obtaining a binary formal context [START_REF] Ganter | Formal Concept Analysis[END_REF]. Then, a numerical dataset is described by a many-valued context. (G, M, W, I) is a many-valued context where G is a set of objects, M a set of numerical attributes, W a set of values (e.g. numbers), and I a ternary relation defined on the Cartesian product G × M × W . The fact (g, m, w) ∈ I or simply m(g) = w means that the object g takes the value w for the attribute m.

Then, classical algorithms can be applied for designing concept lattices from scaled contexts [START_REF] Kuznetsov | Comparing performance of algorithms for generating concept lattices[END_REF]. However, adapted algorithms for designing a concept lattice may be directly applied on more complex data such as numbers, intervals, or graphs [START_REF] Kuznetsov | Learning closed sets of labeled graphs for chemical applications[END_REF][START_REF] Kuznetsov | Pattern structures for analyzing complex data[END_REF][START_REF] Kaytoue-Uberall | Two FCA-Based Methods for Mining Gene Expression Data[END_REF][START_REF] Kaytoue | Two Complementary Classication Methods for Designing a Concept Lattice from Interval Data[END_REF].

Pattern Structures

Instead of applying discretization leading to space and time computational hardness, one may directly work on original data. A pattern structure is defined as a generalization of a formal context describing complex data [START_REF] Ganter | Pattern structures and their projections[END_REF][START_REF] Kuznetsov | Pattern structures for analyzing complex data[END_REF].

In classical FCA, object descriptions are sets of attributes, which are partially ordered by set inclusion, w.r.t. set intersection: let P, Q ⊆ M two attributes sets, then P ⊆ Q ⇔ P ∩ Q = P , and (M, ⊆), also written (M, ∩), is a partially ordered set of object descriptions. Set intersection ∩ behaves as a meet operator and is idempotent, commutative, and associative. A Galois connection can then be defined between the powerset of objects (2 G , ⊆) and a meet-semi-lattice of descriptions denoted by (D, ) (standing for (M, ∩)). This idea is used to define pattern structures in the framework of FCA as follows.

Formally, let G be a set of objects, let (D, ) be a meet-semi-lattice of potential object descriptions and let δ : G -→ D be a mapping associating each object with its description. Then

(A 1 , d 1 ) ≤ (A 2 , d 2 ) ⇔ A 1 ⊆ A 2 (⇔ d 2 d 1 )
, the set of all concepts forms a complete lattice called pattern concept lattice. More importantly, the operator (.) is a closure operator and pattern intents are closed patterns. Existing FCA algorithms (detailed in [START_REF] Kuznetsov | Comparing performance of algorithms for generating concept lattices[END_REF]) can be used with slight modifications to compute pattern structures, in order to extract and classify concepts. Details can be found in [START_REF] Ganter | Pattern structures and their projections[END_REF][START_REF] Kaytoue-Uberall | Two FCA-Based Methods for Mining Gene Expression Data[END_REF][START_REF] Kuznetsov | Pattern structures for analyzing complex data[END_REF].

Below, we analyze object descriptions as interval in numerical data. Pattern structures allows to directly extract concepts from data whose object descriptions are partially ordered. Considering a numerical dataset with objects in G and attributes in M , a meet operator on interval patterns can be defined as follows. Given two interval patterns c = [a i , b i ] i∈{1,...,|M|} , and d = [e i , f i ] i∈{1,...,|M|} , then:

c d = [minimum(a i , e i ), maximum(b i , f i )] i∈{1,...,|M|}
meaning that a convexification of intervals on each vector dimension is operated. The meet operator induces the following subsumption relation on interval patterns:

[a i , b i ] [c i , d i ] ⇔ [a i , b i ] ⊇ [c i , d i ], ∀i ∈ {1, ..., |M |}
where larger intervals are subsumed by smaller intervals.

A numerical dataset with objects G and attributes M can be represented by an interval pattern structure. Let G be a set of objects, (D, ) a meet-semi-lattice of interval patterns (|M |-dimensional interval vectors), and δ a mapping associating to any object g ∈ G an interval pattern δ(g) ∈ (D, ). The triple (G, (D, ), δ) is an interval pattern structure (see examples and details in [START_REF] Kuznetsov | Pattern structures for analyzing complex data[END_REF][START_REF] Kaytoue | Two Complementary Classication Methods for Designing a Concept Lattice from Interval Data[END_REF]).

Pattern structures are very useful for building concept lattices where the extents of concepts are composed of "similar objects" with respect to a similarity measure associated to the subsumption relation in (D, ) [START_REF] Kaytoue | Two Complementary Classication Methods for Designing a Concept Lattice from Interval Data[END_REF].

Relational Concept Analysis

Relational datasets are composed of a binary tables (objects × attributes) and inter-object relations (objects × objects). Formally, these binary tables introduce a set of objects G i described by a set of attributes M i , and, as well, a set of relations r k ⊆ G i × G j . Relational datasets arise in a wide range of situations, e.g. Semantic Web applications [START_REF]Handbook on Ontologies, 2nd edn[END_REF], relational learning and data mining [START_REF]Relational Data Mining[END_REF], refactoring of UML class models and model-driven development [START_REF] Stahl | Model-Driven Software Development: Technology[END_REF].

Relational Concept Analysis (RCA) extends FCA to the processing of relational datasets in a way allowing inter-objects links to be materialized and incorporated into formal concept intents. Links are thus scaled to become relational attributes connecting first objects to concepts and then concepts to concepts as role restrictions do in Description Logics (DL) [START_REF]The Description Logic Handbook[END_REF]. The new attributes are complex properties reflecting the relational aspects of a formal concept. They nevertheless abide to the same classical concept formation mechanisms from FCA which means that the relational concept intents can be produced by standard FCA methods. Due to the strong analogy between role restrictions and relational attributes in RCA, formal concepts can be readily translated into a DL-based formalism [START_REF] Rouane-Hacene | A proposal for combining formal concept analysis and description logics for mining relational data[END_REF], e.g. for ontology engineering purposes as in [START_REF] Bendaoud | Pactole: A methodology and a system for semi-automatically enriching an ontology from a collection of texts[END_REF][START_REF] Bendaoud | Formal concept analysis: A unified framework for building and refining ontologies[END_REF][START_REF] Rouane-Hacene | Ontology Learning from Text using Relational Concept Analysis[END_REF].

RCA was introduced and detailed in [START_REF] Rouane-Hacene | A proposal for combining formal concept analysis and description logics for mining relational data[END_REF]. The data structure is described by a relational context family, composed of a set of contexts {K i } and a set of binary relations {r k }. A relation r k ⊆ G j × G connects two object sets, a domain G j (dom(r k ) = G j ) and a range G (ran(r k ) = G ). RCA is based on a "relational scaling" mechanism that transforms a relation r k into a set of relational attributes that are added to the context describing the object set dom(r k ). To that end, relational scaling adapts the DL semantics of role restrictions.

For each relation r k ⊆ O j × O , there is an initial lattice for each object set, i.e. Actually, RCA is a powerful mechanism for managing relations in the framework of FCA. In CBR, it could be used for example for associating elements of problem statements with elements of problem solutions, an association that was not possible in [START_REF] Diaz-Agudo | Formal Concept Analysis as a support technique for CBR[END_REF].

Elements for Discussion

Usually, considering knowledge systems, and CBR systems as well, knowledge units may have two major different origins: explicit knowledge (and cases) can be given by domain experts and implicit knowledge can be extracted from databases of different kinds, e.g. domain data or textual documents. Moreover, a KDD system, as any other knowledge system, improves its performance when it is guided by domain knowledge [START_REF] Lieber | First Elements on Knowledge Discovery guided by Domain Knowledge (KDDK)[END_REF]. Hereafter, some requirements for KDD systems, adapted from [START_REF] Brachman | The Process of Knowledge Discovery in Databases[END_REF][START_REF] Wille | Why can concept lattices support knowledge discovery in databases[END_REF], are listed for discussion: -A KDD system is a knowledge system: it should present to the user the underlying domain in an appropriate fashion and rely on domain knowledge (e.g. an ontology). -Extending the system knowledge: domain representation should be extensible by addition of new concepts or classes resulting from mining or querying processes. Concepts and their instances must be reusable in queries. The question of extracting cases from data, which have to be made precise, remains open [START_REF] D'aquin | Case base mining for adaptation knowledge acquisition[END_REF]. -Alternative classification and mining tools: it should be possible to define alternative classifications of data, e.g. alternative concept lattices. A set of different classification and mining tools should be available, possibly combining numerical and symbolic methods. -Support to analysts: analysts should be supported by adequate visualization tools and in the interpretation of extracted units as well, in particular by domain knowledge. -Monitoring and documenting the system evolution: tools managing versions can be used for monitoring changes in classes or concepts over time. The system should document the different steps of the knowledge discovery process. -KDD is a flexible process and its results should reflect the plural nature of knowledge, i.e. extracting procedural or declarative knowledge units, and, as well, meta-knowledge units.

-KDD provides knowledge units for extending ontologies, and, reciprocally, knowledge systems and CBR systems can be used to guide and improve KDD.

Finally, the relations between knowledge representation, reasoning, and knowledge discovery with FCA, are explained as follows in [START_REF] Wille | Why can concept lattices support knowledge discovery in databases[END_REF]. Formal concepts and concept lattices provide a mathematization of real-world concept hierarchies. This yields a mathematical support to human reasoning, especially using the graphical representation of concept lattices. Then, conceptual knowledge discovery, considered as pattern discovery plus knowledge creation, can be guided by the design of concept lattices and a subsequent representation of the formal concepts within a knowledge representation formalism such as description logics.

The process can be repeated until a satisfactory knowledge base is obtained.

  (G, (D, ), δ) is a pattern structure. Elements of D are patterns and are ordered by a subsumption relation : ∀c, d ∈ D, c d ⇐⇒ c d = c. A pattern structure (G, (D, ), δ) gives rise to two derivation operators (•) : A = g∈A δ(g), for A ⊆ G and d = {g ∈ G|d δ(g)}, for d ∈ (D, ). These operators form a Galois connection between (2 G , ⊆) and (D, ). Pattern concepts of (G, (D, ), δ) are pairs of the form (A, d), A ⊆ G, d ∈ (D, ), such that A = d and A = d . For a pattern concept (A, d), d is a pattern intent and is the common description of all objects in A, the pattern extent. When partially ordered by

  L j for O j and L for O . For a relation r k ⊆ O j × O , a relational attribute, is associated to an object o ∈ O j whenever r k (o) satisfies a given constraint, where r k (o) denotes the set of objects in O in relation with o through r k . The relational attribute is denoted by ∀r k .C (universal scaling) when r k (o) ⊆ extent(C) with r k (o) possibly empty. The relational attribute is denoted by ∃r k .C (existential scaling) when r k (o) ∩ extent(c) = ∅. Other relational scaling operators exist in RCA and follow the classical role restriction semantics in DL.


Marie Cognet

Agnès Nougayrede

Valérie Malan

Patrick Callier

Celia Cretole

Laurence Faivre

David Genevieve

Alice Goldenberg

Delphine Heron

Sandra Mercier

Nicole Philip

Sabine Sigaudy

Alain Verloes

Sabine Sarnaki

Arnold Munnich

Michel Vekemans

Stanislas Lyonnet

Heather Etchevers

Jeanne Amiel

Loïc De Pontual

Loïc De Pontual
email: loic.de-pontual@inserm.fr

Dissection of the MYCN locus in Feingold Syndrome and isolated esophageal atresia

Feingold syndrome (FS) is a syndromic microcephaly entity for which MYCN is the major disease-causing gene. We studied the expression pattern of MYCN at different stages of human embryonic development and collected a series of 17 FS and 12 isolated oesophageal atresia (IOA) cases. A MYCN gene deletion/mutation was identified in 47% of FS cases exclusively. We hypothesized that mutations or deletions of highly conserved non-coding elements (HCNEs) at the MYCN locus could lead to its misregulation and thereby to FS and/or IOA. We subsequently sequenced 5 HCNEs at the MYCN locus and designed a highdensity tiling path comparative genomic hybridization array of 3.3 Mb at the MYCN locus.

We found no mutations or deletions in this region, supporting the hypothesis of genetic heterogeneity in FS.

INTRODUCTION

Feingold syndrome (FS, MIM164280) combines characteristic digital anomalies (i.e. brachymesophalangy of the 2 nd and 5 th fingers and brachysyndactyly of the toes), microcephaly, oesophageal/duodenal atresia, and variable learning disabilities 1 . FS has been mapped to 2p23-24 [START_REF] Celli | Familial syndromic esophageal atresia maps to 2p23-p24[END_REF] and is the consequence of MYCN gene (MIM 164840) loss-of-function either by germline deletions or coding sequence mutations [START_REF] Van Bokhoven | MYCN haploinsufficiency is associated with reduced brain size and intestinal atresias in Feingold syndrome[END_REF][START_REF] Marcelis | Genotype-phenotype correlations in MYCNrelated Feingold syndrome[END_REF] . Conversely, MYCN amplification is a prognostic factor for a bad outcome and found in about 10% of neuroblastoma [START_REF] Brodeur | Amplification of Nmyc in untreated human neuroblastomas correlates with advanced disease stage[END_REF] .

In this study, we studied the expression pattern of MYCN at different stages of human embryonic development and screened a cohort of 17 patients suspected of FS and 12 cases with isolated oesophageal atresia (IOA). We identified a heterozygous mutation/deletion in 7 FS cases (47%) and no mutation or deletion in IOA. Some HCNEs, able to direct N-myc expression, have been identified in transgenic mice 6 7 8 . We hypothesized that deregulation of tissue-or stage-specific MYCN expression following mutation or disruption of regulatory highly conserved non-coding elements (HCNEs) at the MYCN locus could lead to FS and/or IOA. We subsequently sequenced 5 HCNEs at the MYCN locus and searched for small deletions in the 3.3 Mb vicinity of MYCN.

PATIENTS AND METHODS

A total of 29 patients were included in the study: 17 patients with possible FS (Table 1) and 12 patients with IOA. Diagnostic criteria for FS were the presence of three or more of the core features: i) microcephaly, ii) brachymesophalangy of the 2 nd and 5 th finger, iii) 2/3 or 4/5 toe syndactylies, and iv) oesophageal or duodenal atresia. Whereas post-natal microcephaly was constant after 3 years of age, head circumference was normal at birth in 3 cases. All patients showed mild to moderate mental retardation and eight developed postnatal growth retardation. Brachymesophalangy of the 2 nd and 5 th finger was noted in 15, syndactylies in 12 and oesophageal atresia in 14 of the 17 cases (Figure 1, Table 1).

Additional features are listed in Table 1. All IOA cases were sporadic (10 type III and 2 type I) with no additional malformations. Blood samples were obtained with informed consent and DNA was extracted according to standard protocols. DNA sequencing of the 3 coding exons and intronic flanking regions was performed by the fluorometric method on both strands [ABI BigDye Terminator Sequencing Kit V.2.1, Applied Biosystems]. Comparative genomics analysis of the MYCN locus indicated 5 highly conserved non-coding elements (HCNEs) with >75% identity over direct sequencing in all patients with no coding sequence mutation (primers available on request). A 3.3 Mb region extending 1.94 Mb centromeric (5') and 1.36 Mb telomeric (3') to MYCN (chr2:12,800,000-16,590,000; NCBI Build 36.1) was studied by fine-tiling array-based comparative genomic hybridization (CGH; NimbleGen Systems) on 6 FS patients and 10 IOA with no MYCN coding sequence (CDS) mutation as well as 550 normal-banded chromosomes on blood karyotype. The average spacing of probes in Nimblegen fine-tiling array is 52 bp. A deletion was considered when at least 10 probes were abnormal, giving a deletion detection resolution of about 500bp at the MYCN locus. Genome wide Array-CGH with a resolution of 50 kb was performed in the 5 FS patients with no MYCN mutation and normal Nimblegen fine-tiling array, using the Agilent Human Genome CGH Microarray Kit 244 K (Agilent Technologies, Santa Clara, CA).

To study MYCN expression during human development, embryos were collected from terminated pregnancies in agreement with French bioethics laws (94-654 and 04-800) and the Necker Hospital ethics committee. Probe synthesis and hybridization were carried out as described previously [START_REF] Delous | The ciliary gene RPGRIP1L is mutated in cerebello-oculo-renal syndrome (Joubert syndrome type B) and Meckel syndrome[END_REF] .

RESULTS

Direct sequencing and searching for deletion in MYCN locus

We identified a heterozygous coding sequence mutation in 7 patients (five novel, table1). All mutations resulted in a premature stop codon that removed the basic helix-loophelix (b-HLH) and the leucine-zipper (LeuZ) domains or modified a conserved amino acid essential for DNA binding (figure 2). One patient had a deletion of 425Kb encompassing the MYCN gene only. Six mutations occurred de novo and one was inherited from the affected father (AO28, Table 1) who showed brachymesophalangy of the 2 nd and 5 th fingers, syndactyly between the 4 th and 5 th toes, microcephaly and mild mental retardation. Additional features observed in patients harboring a MYCN coding sequence mutation or deletion were congenital heart malformations (2 cases), kidney hypoplasia (2 cases), asplenia (1 case) and diaphragmatic hernia (1 case). This last malformation had never been reported previously and CGH analysis showed no additional rearrangements in this patient. The MYCN locus was further investigated in patients with no coding sequence mutations; we sequenced 5 HCNE identified in the MYCN locus (Figure 2) and identified no nucleotide variations in either FS or IOA patients. Fine-tiling array-based CGH identified no micro-rearrangements in the 3.3 Mb region encompassing MYCN. Genome wide array-CGH 244 K was normal in the 5 patients with no MYCN CDS mutation and normal Nimblegen fine-tilling array (Table1).

MYCN expression in early human development

Additional features observed in patients with a MYCN mutation motivated the study of MYCN expression at different stages of human embryonic development (Figure 3). At Carnegie stage (CS) 13, MYCN appears ubiquitously expressed, with higher expression in the limb bud mesenchyme (Fig 2A-B). At CS15, MYCN is differentially and highly expressed in the CNS/PNS, the oesophageal and bronchic epithelia, Rathke's pouch, sympathetic ganglia, and both ectodermal and mesenchymal components of the forelimb. At CS17-18, MYCN is highly expressed throughout the CNS/PNS and in both Rathke's pouch and the corresponding precursor of the neurohypophysis, the infundibulum (Fig 3T-U), the smooth muscle of the umbilical arteries, the adrenal gland and the hindgut as well as other sites (Fig3Q-U).

However, despite low levels of cardiac expression seen in situ at C13, we no longer observed any cardiac expression at CS18 (Fig 3V -W).

DISCUSSION

We identified a MYCN mutation in 50% of our cases (8/17). No major phenotypic differences could be found among the core features of FS retrospectively, between patients with and without a MYCN mutation (Table 1). Only syndactyly of toes 4 and 5 was more frequent in the group with MYCN mutations. The high frequency of oesophageal atresia in our series is due to a recruitment bias through paediatric surgeons. Importantly, no additional malformations were present in the group of patients without mutations. Although head circumference can be normal at birth, post-natal microcephaly is constant in our series. Most patients were sporadic cases, contrasting with a previous report [START_REF] Marcelis | Genotype-phenotype correlations in MYCNrelated Feingold syndrome[END_REF] . This discrepancy could be ascribed to both a recruitment bias for familial cases before the gene was identified, and the fact that clinically, the entity is better recognized since then. Several additional congenital malformations have been reported in FS; i.e, vertebral malformations, congenital cardiac defects and renal hypoplasia [START_REF] Marcelis | Genotype-phenotype correlations in MYCNrelated Feingold syndrome[END_REF] . Renal hypoplasia needs to be detected early on in order to prevent renal failure 2 . One of our patients presented asplenia. This has not hitherto been reported in FS but is present in the N-myc hypomorphic mouse model [START_REF] Moens | A targeted mutation reveals a role for N-myc in branching morphogenesis in the embryonic mouse lung[END_REF] . A diaphragmatic hernia was detected in the same patient at birth. Facial features reported in FS are tenuous and combine short palpebral fissures, broad nasal bridge and micrognathia.

We studied the pattern of expression of MYCN at different stages of normal human embryonic development. MYCN is widely expressed in forelimb mesenchyme at the stages we studied, consistent with the constant distal bone malformations observed in FS. Expression in Rathke's pouch raises the question of involvement of the pituitary gland in the growth deficit.

We observed MYCN expression in both bronchial tubes and the oesophagus at CS15, but not in the diaphragm at CS17-18. N-myc knockout mice had been generated concomitantly by three independent groups 11 12 13 . Embryonic lethality was consistently observed between embryonic days E10.5 and E12.5 of gestation, with developmental delay and small size of mesonephros, lung, heart and gut. Interestingly, mutant mice with 25% of wild-type levels of N-myc protein die at birth and are unable to breathe, due to a severe deficiency in lung branching morphogenesis [START_REF] Moens | A targeted mutation reveals a role for N-myc in branching morphogenesis in the embryonic mouse lung[END_REF] .

The molecular mechanisms underlying the regulation of MYCN expression have not been totally elucidated. It has been shown, by replacing endogenous N-myc coding sequences by the c-myc ones, that c-myc can complement N-myc functions [START_REF] Malynn | N-myc can functionally replace c-myc in murine development, cellular growth, and differentiation[END_REF] . Therefore, specificity of both genes resides in their controlled expression patterns. No mutation/deletion of MYCN regulatory elements could be identified in human. Altogether, these results are suggestive of genetic heterogeneity in FS.

Legends to table and figures

Table 1: Clinical features in the series of 17 FS patients with and without MYCN mutation. M: male; F: female; SD; standard deviation, ASD: atrial septal defect, VSD: ventricular septal defect, AC: Aortic coarctation, MA: mitral atresia, del: deletion. NP: not performed. *The father and one sister of AO39 are microcephalic and have hands anomalies (brachymesophalangy of the 2 nd and 5 th fingers and brachysyndactyly of the toes). The sister has also learning disabilities. **The mother of AO41 is microcephalic and has hands anomalies (brachymesophalangy of the 2 nd and 5 th fingers). Antisense and sense (negative control) riboprobes are presented side by side A to P in panels.

A, At Carnegie stage (CS) 13 (37 days'gestation) MYCN is ubiquitously expressed. C, CS15 (36 days' gestation), transverse section in head, showing MYCN expression is still widespread but particularly strong in brain and craniofacial mesenchyme, as well as the precursors to the pituitary gland. E, CS15, transverse section through the cervical neural tube. G, CS15, section at level of forelimb. As compared with the control (H), no expression is observed in the liver but is specific to both epithelia and mesenchyme of bronchi and oesophagus (I-J) and forelimb bud (M-N) as well as at levels of the central and peripheral nervous system (CNS/PNS; I-L, O-P). Q, Hematoxylin-eosin stain of sagittal section at CS17-18 (42-45 days'gestation). MYCN expression in an adjacent section (R) shows continued but diminished expression in the CNS/PNS and craniofacial mesenchyme, and presence of transcripts in the adrenal gland, hindgut and genital tubercule. T, MYCN continues to be expressed in the developing pituitary, unlike in the ventricular myocardium (V vs W).

Abbreviations: ad: adrenal gland, aer: apical ectodermal ridge, ao: aorta, br: bronchi, di: diencephalon, drg: dorsal root ganglia, eg: enteric ganglia, g:gut, g/IX/X: cranial ganglia IX/X, gt: genital tubercule, h: heart, hg: hindgut, inf: infundibulum, lb: limb bub, lv: liver, mes: mesencephalon, mx: maxilla, nt: neural tube, oe: oesophagus, rb: rathke's pouch, rh: rhombencephalon, sc: spinal cord, sg: sympathetic ganglion, st: stomach, tel: telencephalon, tg: tongue, umb: umbilical cord.

Scale bars: 0.5 mm except for Q-S, 1mm.

Figure 1 :

 1 Figure 1: Patient AO68 with Feingold syndrome and MYCN deletion. Note round face, brachymesophalangy of the 2 nd and 5 th finger, and short feet with brachydacty.

Figure 2 :

 2 Figure 2: Schematic representation of the MYCN locus (6647 bp). The deletion and mutations

Figure 3 :

 3 Figure 3: MYCN expression in early human development.

Micrognatia

Conflict of interest:

The authors declare no conflict of interest.