In the recent years, web has turned into a \Web of Data" with a signi cant increase in the number of users looking for direct access to the data embedded in web pages. At the same time, a large amount of Linked Open Data (LOD) is available on line which allows e ective exploration and navigation. However, there are still needs to bridge the gap between di erent data sources and formats, for improving data analysis, data integration and information retrieval. This paper focuses on Lattice Based Data Access (LBDA), a framework following the lines of Ontology Based Data Access (OBDA) and which is based on Formal Concept Analysis (FCA) and Relational Concept Analysis (RCA). In this way, operations such as query answering on data are carried out on concept lattices which are acting a representation and an indexing of data. The LBDA framework provides a view over LOD with reference to data and constraints provided by a user, and it helps in information retrieval and knowledge discovery thanks to FCA and RCA.
A signi cant amount of Linked Open Data (LOD) is already available on the
web [
Besides that, life science experiments generate amounts of relational data that
raise new challenges for data modeling and analysis, and make it harder for the
user to select interesting features and links. These experimental datasets can be
enriched with data collected from LOD, for improving data access, information
retrieval and knowledge discovery. Moreover, information required by biologists
is present in LOD at least for a large part, and a user must be able to search
for the point of interest without following a too large set of web links, especially
when a user has no technical knowledge of semantic web [
This paper proposes a new approach that helps a user to search and query
LOD thanks to Formal Concept Analysis (FCA [
By contrast, this paper introduces a new and \parallel" approach, namely
\Lattice Based Data Access" (LBDA), which allows the organization of LOD
into a family of concept lattices (i.e. a lattice space), for data analysis,
knowledge discovery and information retrieval purposes. Moreover, LBDA can further
provide partially ordered oragnization of triples obtained by conjunctive queries
in OBDA, it can also provide classi cation of these results. LBDA allows for
navigation in lattices which in turn gives the capability of of navigation over
RDF triples. [
The paper is organized as follows. After this introduction, Section 2 gives an insight into motivation of the current work and challenges faced by biologists. Section 3 introduces Formal and Relational Concept Analysis while Section 4 de nes LBDA and gives the overall architecture of LBDA systems. Section 5 discusses search and querying with example, and nally Section 6 concludes the paper. 2
Most of the diseases are the e ect of environmental and genetic factors. In order to understand the genetic factors involved in a particular disease, it is important for the biologists to study which pathways and biological processes a gene is involved in. It is admitted that most of the time a collection of genes contribute to the development of classic and complex human diseases (such as cancer). Because gene products are involved in biological pathways, variations in their activity can cause a particular disease. Thus it can be important to help biologists in understanding the role of genes sharing the same pathway in a disease. Following this line, we aim at de ning a methodology based on FCA for answering questions such as: Get genes which are located on Chromosome X and their associated pathways which have enzymes SCAD (short-chain-acyl-CoA-dehydrogenase) and BKR (beta-keto-reductase).
For the rest of the paper we will be considering the following scenario: A user (biologist) has a list of genes related to a disease (Mental Retardation) and he wants to check which genes/group of genes are involved in which pathways (This refers to just one relation - between gene and pathway) and on which chromosomes are genes/group of genes located, and what enzymes the above mentioned pathways release. 3
3.1
In this section we introduce the basics of Formal Concept Analysis (FCA) [
A0 = fm 2 M j gIm f or all g 2 Ag
B0 = fg 2 G j gIm f or all m 2 Bg
The two derivation operators 0 form a Galois connection between the powersets }(G) and }(M ). Maximal sets of objects related to maximal set of attributes correspond to closed sets of the composition of both operators 0 (denoted by 00). Then a pair (A; B) is a formal concept i A0 = B and B0 = A. The set A is the \extent" and the set B is the \intent" of the formal concept (A; B). The set CK of all concepts from K is partially ordered by extent inclusion (or dually intent inclusion), denoted by K as follows: (A1; B1) (A2; B2) , A1
A2(, B2
B1)
Then, LK = hCK; Ki forms the concept lattice of K. This concept lattice can be used for a number of purposes, among which classi cation and data analysis, information retrieval and knowledge discovery.
Beside a class hierarchy provided by the concept lattice, an integrated class
model must include relations available between classes, and possibly,
abstractions of these relations. The abstraction of relations requires an encoding of
(1)
(2)
(3)
association roles into a formal context together with their attributes. The RCA
framework addresses these concerns, allowing FCA to e ectively and e ciently
take into account relational data. Relational Concept Analysis [
More formally, a \relational context family" or RCF is a pair (K; R) that can be de ned as follows: { K = fKigi=1;:::;n is a set of contexts Ki = (Gi; Mi; Ii), { R = frkgk=1;:::;m is a set of relations rk Gi Gj for some i; j = 1; :::; n 3.2
LGene.
A relational context family (RCF) is shown in Tables 1, 2 and 3. Table 1 represents a formal context with gene names w.r.t. HUGO Gene NomenClature (HGNC1), where genes are objects and locations of the genes on the chromosome are attributes. Chromosome locations in the context are \Attribute Chain". For location 9q34.1 we have: P OM T 1 is located on chromosome 9, which is divided into two arms, i.e. a short arm p and a long arm q. Thus P OM T 1 gene is located on the longer arm q in the region 34.1.
Table 2 represents a second formal context which keeps pathways as objects and enzymes contained by pathways as attributes. Finally, Table 3 represents a relational context, encoding the relation involvedIn between the Gene context (Table 1) and the Pathway context (Table 2). Figure 1 illustrates the lattice LP ath corresponding to pathway context and Figure 2 represents the lattice Gene POMT1 ACSL4 HSD17B10 POMGT1 PIGV INPP5E
PIGL
17 17p 17p12 9 9q 9q34.31 1p 1p36.111p34.1X Xp Xp11.29q34.1Xq Xq22.3Xq23 17p11.2 e d y h e ld a i malodneahtyed-sreomPgeTnPase e s phospphhoosipnhoosdiltiipiadacesyelgClycerolkina
In order to provide user with the ability to navigate and query LOD, we introduce the notion of \Lattice Based Data Access" (LBDA). This approach is built over RDF triples returned by SPARQL queries and acts as a compressed representation over LOD by recognizing important information and extracting only web page annotation (where this page annotation works as an index). Lattice Based Data Access System can be considered as a process where a concept lattice is used as an index structure over data repositories to facilitate user data access through complex query answering (SPARQL) and an automated concept lattice navigation (see Figure 3).
KEGG Pathways Gene Ontology Reactome
In this framework, a user de nes some constraints over a list of genes to
be observed. These constraints are mapped to SPARQL queries which are sent
to LOD Cloud (according to the scenario given in the previous section). These
queries retrieve RDF triples from selected data sources, in our case mainly KEGG
[
Lattice-Based Data Access (LBDA) is based on a family of concept lattices (based on an RCF) and associated mappings. More formally we have the following: { L is a family of (relational) concept lattices, { A is a set of RDF triples (or triple store), { M is a set of mappings relating RDF triples to formal concepts within concept lattices.
Actually, the correspondence provided by M allows to perform operations from \both sides", i.e. from the points of view of RDF triples or concept lattices.
Such a correspondence is also the base for ontology-based data access (OBDA)
where querying data can be guided and enhanced through ontological reasoning.
In LBDA, we will have the same kind of capability: querying the RDF triple
store will be carried out through a concept lattice (playing the role of an
index), taking advantage of the lattice organization (i.e. partial ordering) and the
e cient algorithmic machinery of FCA [
Mappings in M between A and L The representation languages used in Semantic Web include RDF, RDFS and OWL. An RDF triple is of the form (subject; predicate; object), e.g. (bio : P OM T 1; rdf : type; bio : gene) meaning that \POMT1 has the type gene" or simply \POMT1 is a gene" (rdf : type is an RDF property). Now let us consider three triples of the form: (subject1; predicate1; object1) (subject2; predicate2; object2) (subject1; predicate3; subject2) (T1) (T2) (T3)
Now, according to the de nition of a formal context and an RCF, we can consider an RDF triple (subject; predicate; object) as an element of a formal context and an RDF triple (subject; predicate; subject) as an element of a relational context. More precisely, given RDF triples of type T1 or T2 are respectively in formal contexts K1 = (G1; M1; I1) and K2 = (G2; M2; I2), while RDF triples of the type T3 determines a relation r (G1 G2).
Examples of these kinds of triples are: (bio : P OM T 1; bio : hasLocation; bio : 9q34:1) and (bio : other types of O glycan biosynthesis; bio : hasEnzyme; bio : DP M P ) for T1 or T2, (bio : P OM T 1; bio : involvedIn; bio : othertypesof Oglycanbiosynthesis) for
Following this line, we obtain an RCF providing an RCA-based view of LOD in which we are interested, i.e. a relational concept lattice materializing this LOD view.
T3. 5 5.1
In order to query complex interlinked structure of relational concept lattices we introduce the notion of lattice space, which includes several concept lattices based on the relations to be examined. Here concept lattices work as an organization of data present in LOD with respect to the underlying schema provided by Relational Concept Analysis. This lattice space then queried by the user.
For the sake of simplicity, we consider here only two lattices and a relation between objects in these two lattices. For example, Figure 4 shows two concept lattices LP ath and LGene, where LP ath is the concept lattice representing \Pathways" and LGene is the concept lattice representing \Genes". The dotted line shows how one concept lattice is referring to the other concept lattice. Figure 5 gives details by focusing on one concept in LGene: C#6 in LGene is referring to C#5, C#6 and C#12 in LP ath. The link involvedIn : C5 between LGene and C5 in LP ath is shown with the help of dotted line.
A node in the concept lattice LGene may have a relational attribute which keeps a reference to a concept in the concept lattice LP ath. In order to provide data access, each lattice in the lattice space is navigated based on the constraints and relations provided.
Data access in LOD is performed through the querying of the lattice space which
implies to navigate a family of concept lattices (produced by the RCA process)
and to follow relations from one concept lattice to another. The form of the
considered \conjunctive queries" over relational concept lattices is introduced
and discussed hereafter (see also [
Query answering.
For answering the query, a concept (A; B) such as (A; B) 6= ? and (A; B) 6= > in both concept lattices is searched. Then the steps for answering the query are the following: { Search for the suitable concepts (C; D) in the LP ath concept lattice. { The most relevant concepts are the more general concepts, i.e. when (C1; D1) (C2; D2), (C2; D2) is selected as C1 C2. { Then, equation 5 is populated as = B ^ r : (C2; D2). { For computing the value of A in equation 4, we search for in the LGene concept lattice verifying = B ^ r : (C2; D2). { The most relevant concepts are again the most general concepts verifying (A1; 1) (A2; 2), i.e. (A2; 2), and the answer is given by A2, the extent of the selected concept.
An Example.
A sample query explained w.r.t. Figure 1 and Figure 2. Suppose a user wants to get genes which are located on Chromosome X, and their associated pathways which have enzymes \short-chain-acyl-CoA-dehydrogenase" (SCAD), \beta-keto-reductase" (BKR). For answering, there is a need to know which are the genes located on chromosome X and the pathways associated with these genes with the enzymes. The query can be formulated as follows, where g refers to the set of genes, p to the corresponding pathways, together with SCAD and BKR denoting the enzymes. The initial query can be read as:
(g; ) ^ (p; fSCAD; BKRg) = X ^ involvedIn(p; fSCAD; BKRg)
The concepts containing fSCAD; BKRg as their intent are searched in the LP ath concept lattice (Figure 1), i.e. C#6 and C#2, which verify C#6 C#2. Thus we get p = fF attyAcidM etabolism; V LIDg which is extent of C#2 (as the extent C#6 is included in the extent of C#2. The query becomes: (g; ) ^ (fF attyAcidM etabolism; V LIDg; fSCAD; BKRg) = X ^ involvedIn(fF attyAcidM etabolism; V LIDg; fSCAD; BKRg) For obtaining the nal answer, the LGene concept lattice is navigated (Figure 2), searching for X ^ involvedIn(Concept2). This returns the list of concepts in LGene fC#1; C#5; C#6g. As C#5 C#1 and C#6 C#1: (fACSL4; HSD17B10g; ) ^ (fF attyAcidM etabolism; V LIDg; fSCAD; BKRg) = X ^ (fF attyAcidM etabolism; V LIDg; fSCAD; BKRg)
The answer to the query is the list of genes which constitutes the extent of concept C#1 in the LGene concept lattice, i.e. fACSL4; HSD17B10g which is located on chromosome X, with the list of pathways fF attyAcidM etabolism; V LIDg which have the enzymes fSCAD,BKRg, i.e. concept C#2 in the LP ath concept lattice, (fF attyAcidM etabolism; V LIDg; fSCAD; BKRg). 6
In this approach, we try to represent interesting parts of the LOD as a set of concept lattices that can be accessed for retrieving relevant information for the biologist. This family of lattices, called here the lattice space, is obtained through the relational concept process, when relations between objects are taken into account. Then, a query mechanism can be de ned for materializing the constraint of a user and to narrow the query space. The query mechanism allows conjunctions between the elements of a query and relations between objects involved in the query. A navigation in the related lattices of the lattice space provides the expected answer. In order to take full bene t from the approach described in this paper the user needs to know the structure of the lattice and the corresponding lattice space. At the moment, we are working on real world experiments related to genes involved in cancer (analysis of gene lists). This approach can be applied to all domains where the extraction of objects described by some attributes is possible. The limitations of the de ned approach are posed when dealing with larger number of objects leading towards huge lattices. Currently, we are dealing with small domain which does not give rise to such limitations. We still have to investigate the parallel between OBDA and LBDA and check how both processes can be continued. On one hand we can take advantage of OBDA capabilities with respect to reasoning within an ontology while LBDA can provide a lattice-based organization of LOD (actually RDF data) that can be navigated and queried, allowing e ective and e cient web data access.