Keywords: . . . . . . . . . GAIA, CORK, GraphSig, LEAP, LPGBCMP, GAIA, CORK, GraphSig, LEAP, LPGBCMP, COM, gBoost, gPLS

select 100 representatives among 10000 subgraphs with variation of the number of graphs. . . . . . . .

List of Figures

Aims

In this chapter, we introduce the context and the main motivations of this thesis. We briey present and discuss the proposed contributions. We also highlight the outline of each chapter in the manuscript as well as the appendices.

Context and motivations

This thesis is in the intersection of two of the most expanding research elds, namely data mining and bioinformatics. Data mining is one of the most active elds in computer science. It consists in analyzing complex data to extract useful information and transform them into understandable and more convenient format enabling and/or facilitating further use. The main goal of data mining is to provide useful tools and technical knowledge through algorithmic solutions for real world applications. Bioinformatics is an important application eld for data mining. This is due to the complexity of biological processes and data that keep increasingly growing everyday. Manual work alone is unable to match the explosive growth of the amount of biological data. This rises an urgent need for automatic mining techniques to study these data.

Proteins are biological macromolecules that play crucial roles in almost every biological process. They are responsible in one form or another for a variety of physiological functions. Proteins are made of complex structure composed of a number of amino acids that are interconnected in space. The amino acids themselves are composed of a set of interconnected atoms. Thanks to both computational and biological advances we are witnessing these years, huge amounts of protein structures are currently available in online databases in computer analyzable formats. The biological importance of proteins, their complexity, and their availability in computer analyzable formats made us consider them as the main application data in this thesis.

Biologically speaking, the tertiary structure (shortly 3D-structure) of protein already contains its primary structure besides the connections between distant amino acids. It is the native form that controls the basic function of the protein. During the evolution some distantly related proteins may lose sequence homology while retaining some common folding. Hence, studying the tertiary structure of proteins is of great importance. A crucial step in the computational study of protein 3D-structures is to look for a convenient representation of their spatial conformation. Since a protein is composed of a set of connected amino acids, it can then be easily transformed into graphs where the amino acids are the graph nodes and their connections are the graph edges. Transforming protein 3D-structures into graphs enables using graph mining and more generally data mining techniques to study them.

Pattern mining is one of the most important tasks in data mining. The main purpose behind pattern mining is to nd hidden relations and behaviors in data in order to better analyze them and to help in understanding the observed phenomena. Pattern mining has been extensively addressed during the last two decades for dierent types of patterns including association rules and itemsets. In the last few years, many eorts have been devoted to mine 1.2. Context and motivations 3 patterns from graph data. This is not an easy task especially because of the combinatorial nature of graphs that makes the search space exponential.

Graph patterns can be in the form of properties (density, diameter, ...) or in the form of substructures. In this thesis, we are interested in patterns in the form of substructures and more specically in the form of subgraphs. In this context, pioneer works were interested in mining subgraphs that are frequent in graph databases. This is mainly because of the benet of antimonotonicity that oers the frequency measure. However, in the later studies, frequency taken by its own, is no longer enough to justify the importance of subgraphs. First, because many of the discovered frequent subgraphs are redundant or just useless for the user. Second, because of the high number of frequent subgraphs that hinder and even sometimes makes unfeasible further explorations. In the literature, this problem is sometimes referred to as the curse of dimensionality or information overload.

Several attempts have been made trying to resolve both mentioned issues by selecting only a small yet more interesting subset of subgraphs using interestingness measures that are dened according to the application needs. However, it is not always obvious to integrate the selection in the extraction process because most of the interestingness measures are neither monotonic nor antimonotonic.

Many approaches have been proposed for selecting interesting subgraphs, some of them are integrated in the extraction process, others perform the selection in post-processing. These approaches are investigated in Chapter 3. An interesting observation in existing subgraph selection approaches is that the prior information and knowledge about the application domain are often ignored. However, the latter provides valuable knowledge that may help building dedicated approaches that best t the studied data. In this thesis, we propose two selection approaches for subgraphs. Both approaches aim to select representative subgraphs among the frequent ones in order to remove redundancy. Redundancy in frequent subgraphs is mainly caused by structural and/or semantic similarity, since most discovered subgraphs dier slightly in structure and may infer similar or even the same meaning. We attempt to overcome these shortcomings. Each of the proposed approaches addresses one type of redundancy, i.e., the rst approach focuses on semantic redundancy using the prior domain knowledge, while the second approach focuses on structural redundancy. In existing subgraph selection approaches, the prior domain knowledge is often ignored. However, it can be exploited to build dedicated approaches that best t the studied data. In our context, proteins evolve during the evolution where amino acids mutate from one type of amino acid into another through the action of DNA mutations. These mutations are quantied in the so-called substitution matrices. These matrices represent valuable domain knowledge that can be exploited. We propose UnSubPatt (Unsubstituted patterns), a subgraph selection approach that uses the substitution matrices to detect similarities between subgraphs. We show that this allows UnSubPatt to detect similarities between subgraphs that current subgraph selection approaches ignore. This also enabled UnSubPatt to select a small yet more representative and informative subset of subgraphs among frequent ones, enabling easier and more ecient further explorations. UnSubPatt is unsupervised, thus, it can be used in any subgraph-based task. It is also worth noting that Un-SubPatt can be used for other sub-classes of patterns like trees and strings (represented as line graphs). Although UnSubPatt is currently tested only on protein structures, this represents an immediate application example due to the availability of the substitution matrices. Indeed, UnSubPatt can be used in any other application context whenever it is possible to dene a matrix that quanties similarities between the nodes labels.

TRS

The similarity between subgraphs in UnSubPatt is purely semantic as it depends on the relations between nodes' labels, dened in the matrix. We introduce another subgraph selection approach, we term TRS (Topological Representative Subgraphs), that focuses on the structural similarity rather than the semantic similarity. Existing works for structural subgraph selection are based on exact or approximate structural similarity. This similarity detection strategy is not ecient enough in many real-world applications. On one hand, the combinatorial nature of graphs makes looking for a possible matching between every pair of subgraphs computationally very costly. On the other hand, exact and even approximate structural similarity are not ecient enough to detect all similar subgraphs in real-world data. Indeed, exact structural similarity does not allow detecting similar yet slightly dierent subgraphs, and approximate structural similarity has the problem of threshold setting. A tight threshold prevent detecting similar subgraphs that slightly 1.4. Outline of the manuscript 5 dier in structure beyond the tolerance threshold. In contrast, a loose threshold will hinder the soundness of the selection because of false positives.

Unlike these approaches that look into every single detail, TRS follows a more meaningful selection by considering the overall structural similarity between subgraphs through a set of topological descriptors. This makes it easily extendable with any user-specied set of descriptors depending on the application and the sought information. TRS involves two steps. First, it encodes each subgraph into a topological description-vector containing the corresponding values for each one of the topological descriptors. Secondly, subgraphs with similar topological descriptions are clustered together and the central subgraph in each cluster is considered as a representative delegate.

We show that TRS is able to select a set of topologically non-redundant and informative subgraph-delegates by considering hidden topological similarities between subgraphs that are ignored by current selection approaches. In addition, TRS is easily extendable with other types of descriptors and is not limited to biological data or to protein 3D-structures but can be used with any graph data. Moreover, TRS is unsupervised and can be used in any subgraph-based tasks.

Outline of the manuscript

The rest of this thesis is organized as follows. Chapter 2 presents the research eld of this thesis namely, data mining as well as the application domain which is bioinformatics. It denes the basic notions and the preliminary concepts needed for the understanding of the rest of the thesis. We also focus on dening bioinformatics data and more precisely protein structures. We show the complexity of the latter and we review methods from the literature that allow transforming protein 3D-structures into graphs. We implemented these methods and made them available for public in a website which is presented at the end of the chapter and in the appendices.

In Chapter 3, we make a survey on related works over three levels. Since subgraph selection is always coupled with the extraction, in the rst part we detail and discuss frequent subgraph mining algorithms in graph databases as well as existing approaches that address this task. The second part of the chapter focuses on the problem of feature selection in general and the last part of it reviews the most interesting subgraph selection approaches.

In Chapter 4, we propose a novel feature selection approach, termed Un-SubPatt, for selecting a subset of representative unsubstituted subgraphs among frequent ones. UnSubPatt detects similarity between subgraphs by incorporating a specic domain knowledge which, in our context, consists of Chapter 1. Introduction the protein substitution matrices. Experimental evaluation of UnSubPatt and comparison with other subgraph selection approaches from the literature are presented in the end of the chapter.

In Chapter 5, we propose another approach for subgraph selection, termed TRS. It selects a subset of topological representative subgraphs among the frequent ones. TRS focuses on the structural similarity to detect redundancy between subgraphs. It uses a set of user-dened measures to characterize the subgraphs, then it groups similar subgraphs into clusters to detect the representative subgraphs. We dene a set of topological attributes then we use them to perform experimental analysis of TRS on a set of real and synthetic graph datasets.

Chapter 6 concludes the thesis by summarizing the proposed contributions and revealing ongoing works.

Appendix A describes the data format that we used in the experiments.

Part I Background and related works

Aims

In this chapter, we present the preliminary concepts and the basic notions of the two main research elds of this thesis, namely data mining and bioinformatics. Specically, we investigate the task of pattern mining, its main problem and how to resolve it. We also focus on dening bioinformatics data, precisely protein structures. We show their complexity and we review methods from the literature that allow transforming protein 3D-structures into graphs.

This enables further analysis of protein structures using graph mining and more generally data mining techniques.

Chapter 2. Data mining and biological background

Data mining

In recent years, data mining has become one of the most active elds in computer science. This can be explained by the availability of increasingly huge amounts of data with an urgent need to analyze them. Besides, the huge advances we have witnessed in recent years in computational and storage technologies allow running greedy algorithms and analyzing more and more amounts of data.

Data mining is an interdisciplinary eld in computer science. Dierent denitions have been given to data mining. One of the pioneer denitions was given in [Fayyad 1996]: "Data mining is the application of specic algorithms for extracting patterns from data". In Wikipedia,1 it is dened as the compu- tational process of discovering patterns in large data sets involving methods at the intersection of articial intelligence, machine learning, statistics, and database systems. Han and Kamber dened it in [Han 2006] as: "data mining refers to extracting or mining knowledge from large amounts of data" . Zaki and Meira Jr. gave a similar denition in [Zaki 2014]: "Data mining comprises the core algorithms that enable one to gain fundamental insights and knowledge from massive data". A cross view over the existing denitions allows us to simply consider data mining as the process of analyzing data to extract useful information and transform them into understandable and more convenient format, enabling and/or facilitating further use. Data mining often uses algorithms and techniques from statistics, articial intelligence and databases, but may sometimes also involve techniques inspired from other domains such as physics, biology, chemistry, and so on.

Knowledge discovery in databases

Data mining is sometimes referred to as Knowledge Discovery in Databases or simply KDD [START_REF] Fayyad | [END_REF]]. Yet, it only represents a part of the KDD process. In fact, KDD involves two other parts besides data mining, namely data pre-processing and data post-processing. Nevertheless, data mining may sometimes cover these two parts which makes it equivalent to KDD. Figure 2.1 illustrates the dierent levels of the KDD process.

It is necessary to dierentiate between data, information and knowledge.

From a computer science perspective, numbers, text, signals or in general any raw facts that can be processed by a computer is considered as data.

Patterns, associations, and relationships among data can provide information.

Thus, information is simply any meaning that could be understood from data.

Pattern mining is one of the core tasks and most important research elds in data mining. It consists on nding existing patterns in data. In fact, patterns can be in dierent forms ranging from simple patterns such as itemsets and association rules to more complex patterns such as sequences, trees and even to extremely complex patterns such as graphs and temporal or time evolving patterns. The main purpose behind pattern mining is to nd hidden relations and behaviors in data in order to better analyze them and to help understanding the observed phenomena. Many of the pioneer works in pattern mining have been devoted to association rules. Indeed, the original motivation for nding association rules in data came from the desire to understand customers behavior in terms of the associations between purchased products in supermarket transactions. For example, how often do costumers buy milk and sugar, i.e., nd the support of the association rule "milk → sugar". Such associations are very valuable to the supermarket owners as they may help, for instance, reorganizing the products positions according to the costumers preferences which may yield the increase of sales. Besides supermarket transactions, association rules and pattern mining in general are used in many other real application contexts such as identifying terrorists' activities and music information retrieval.

The identication of patterns in a given population is a hard task, since the miner has to answer to, at least, these questions in the rst place:

-Which patterns are we seeking? -How do they look like?

-How can we characterize them? -How can we identify them? Answering these questions before starting the pattern mining process is crucial, since each one of them highly aects the mining process.

Curse of dimensionality in pattern mining

A pattern can be identied in data based on one or several parameters such as its frequency in the population, its rarity or other user-dened criteria. The most common criterion used for pattern mining is frequency where the aim is to mine patterns that often occur in data. A pattern is considered as frequent if it occurs at least a minimum-number of times in the database.

The minimum-number is user-dened and called minimum support. Mining frequent patterns stands under the assumption that patterns which frequently occur in data can be considered as features (events, relations, transactions, ...) to characterize them. Indeed, it helps discovering interesting information and common behaviors in data. Yet, a serious problem that arises directly after mining frequent patterns consists in the huge number of discovered patterns that may reaches thousands and even millions. Such huge number of patterns may hinder or even makes unfeasible any further exploration. For example, it would make no sense to provide millions of patterns for visual inspection.

In such case, instead of helping to resolve the problem, using frequent patterns will add a supplementary problem layer to resolve. This problem is referred to as the information overload. This problem has several side eects and consequences especially if the large set of patterns are used as attributes (dimensions) for further knowledge discovery tasks. This problem is referred to as the curse of dimensionality. It can be observed with simple patterns as well as with complex and sophisticated ones. Facing this problem, the main raised questions are:

-Are all the discovered patterns interesting?

-If not, how can we decrease the number of patterns without loosing (at least approximately) any knowledge, such that only the signicant patterns remain?

Measuring the quality of patterns

Resolving the problem of dimensionality is one of the biggest challenges in pattern mining, since a pattern mining algorithm will potentially generate a tremendous number of patterns especially in real world cases.

Denition 5 (Interesting pattern) A pattern is considered as interesting if it represents knowledge, i.e., it brings additional information regarding the mining problem or the information that is sought by the user.

In order to overcome the dimensionality problem and to identify the truly interesting patterns that represent knowledge, some interestingness measures can be adopted to assist the pattern mining process. Interestingness measures are in the form of statistical functions. So far, there is no agreement on a formal denition of a universal measure that quanties the importance of a pattern, or that allows distinguishing between the interesting patterns and the uninteresting ones. This is obvious, because in diverse applications and for dierent users the denition of the word interesting is relative and related to the goals. For this reason, a panoply of interestingness measures have been proposed in the literature.

Chapter 2. Data mining and biological background Naive bayes Naive bayes is a probabilistic classier based on Bayes theorem [START_REF] Stigler | [END_REF], Wasserman 2010]. The idea is to use probability conditions to compute probability of each class. The predicted class is the one that maximizes the posterior probability. Naive bayes is called naive or simple because it assumes the independence of variables. Naive bayes is powerful and works well in many cases, however, in many applications, variables are not independent. Naive bayes is not suitable in such cases. Some variants of naive bayes were proposed attempting to overcome this drawback by assuming that variables can be related. Although this may contribute enhancing the results, it highly increases the computational cost. Thus, according to the no-free-lunch theorem [START_REF] Wolpert | [END_REF]], no method is better than the others, every method counts and is appropriate for specic cases.

Decision trees Decision trees are ones of the most popular classiers [Li 2008]. The most popular algorithms are ID3 [START_REF][END_REF]] and C4.5 [Quinlan 1993]. The goal consists in nding with the best possible accuracy the values taken by the variables to predict from a set of descriptors, i.e., to best predict the class aliation using the descriptors as features. The main idea is to consider the features as classication rules' conditions, then, try to nd the best combinations of rules that best optimize the classier prediction. Using the features, it constructs a tree-like model where the nodes are the features, the branches are the features' values, and the leaves are the predicted classes. Each path from the root node to a leaf present a classication rule.

Support vector machines Support Vector Machines, or shortly SVM [START_REF] Vapnik | [END_REF], Bi 2003], is a powerful classier. SVM attempts to separate between positive and negative examples in the training set. Each example is represented by a feature vector. SVM seeks the hyperplane that best separates positive from negative examples, by ensuring that the margin between the closest positive and negative is maximal. New examples are encoded using the same features and predicted to belong to a class based on which side of the hyperplane.

Clustering

Clustering, also known as unsupervised classication, is the task of creating groups of objects based on one or more similarity criteria. The created groups of objects are also called clusters. Unlike classication, in clustering the class labels are unknown. Clusters presents homogeneous groups of objects that are created based on objects similarity. Thus, a good clustering tends to maximize similarity between objects within the same cluster (intra-cluster similarity) while minimizing the overall similarity between dierent clusters (inter-cluster similarity).

There exists dierent clustering techniques depending on how the clustering is performed. Clustering techniques involves partitioning methods, hierarchical methods, density-based methods and others. In the following, we present some of the most known clustering algorithm. The list of existing clustering algorithms is not limited to the ones detailed below, namely k-Means [MacQueen 1967] and k-Medoids [START_REF] Kaufman | Clustering by means of medoids[END_REF]], but it also involves other well known algorithms like EM [START_REF] Dempster | Maximum likelihood from incomplete data via the EM algorithm[END_REF], DBSCAN [Ester 1996],

BIRCH [START_REF] Zhang | [END_REF]], OPTICS [Ankerst 1999] and so on. We do only explain k-Means and k-Medoids as examples since clustering is not the main subject of this thesis, besides, k-Medoids is used later in Chapter 5.

K-Means K-Means is the most known clustering algorithm [MacQueen 1967[START_REF] Jain | [END_REF].

It is considered as a partitioning method.

It takes as input a set of objects to be partitioned and a user-dened parameter k which corresponds to the number of clusters. The main goal of k-Means is to partition the objects into k clusters such that the intra-cluster similarity is maximized and the inter-cluster similarity is minimized according to a similarity (or inversely to a dissimilarity) function that computes distance between pairs of objects. K-Means proceeds as follows. It starts by randomly generating k ctive points as the clusters means (centroids). Then iteratively, it assigns each data point to the same cluster of the closest centroid. After assigning all the data points, the new mean point is computed and the assignment is reinitialized. K-Means iterates the cluster assignment and mean update until no change or local minima of criterion function converges.

K-Medoids K-Medoids [START_REF] Kaufman | Clustering by means of medoids[END_REF]] is another partitioning method. It is considered as a variant of k-Means. It also accepts as input a set of objects to be partitioned and a user-dened number of clusters k. Then, it tries to partition the objects into k clusters following almost the same clustering procedure as k-Means. The main dierence between k-Medoids and k-Means is that the latter denes the cluster's centers as ctive points, whereas, k-Medoids requires that the cluster's centroids be real points. This makes k-Medoids less sensitive to noise and outliers in the data. In addition, this makes it suitable for applications that looks for representative objects among data such that each centroid can be considered as the representative for all objects within the same cluster.

Applications of data mining

The main goal of data mining is to provide useful tools and technical knowledge through algorithmic solutions for real-world applications. Data mining can be useful in a variety of domains of application ranging from market analysis to chemistry and physics. One of the currently most expanding domains of application of data mining is bioinformatics. The main goal is to discover meaningful information and useful knowledge from biological data in order to help understanding biological phenomena such as the study of viruses [START_REF] Diallo | [END_REF]], metabolic pathways [Morgat 2012], protein docking [Ritchie 2010], etc. In the following section, we try to dene and detail the biological background as well as the biological data used in this thesis.

2.3 Biological background : bioinformatics and biological data

Bioinformatics

Bioinformatics is an interdisciplinary eld. It can be simply dened by the application of computer science concepts and techniques to deal with biological data. Bioinformatics involves not only the collection, storage, prediction and analysis of molecules (nucleic acids, proteins, etc.) but also the development of tools for modeling biological systems through mathematical, statistical and computer science methods. Due to technological advances, bioinformatics has exponentially evolved during the past few years becoming one of the most expanding research elds nowadays. The emergence of bioinformatics did not only create a new application eld for computer science, but also brought to biology many valuable benets [START_REF] Viari | How Does Computer Science Change Molecular Biology[END_REF]]. Indeed, some tasks that used to require tremendous eorts and weeks or even months of lab work, do only need minutes or even seconds with the help of bioinformatics tools to perform the same task with often nearly similar quality. This is thanks to the high computational ability of current computer processors and to the algorithmic advances in the analysis and modeling of biological systems.

Biological data

Mainly, bioinformatics data revolve around three biological macromolecules namely DNA, RNA and protein. These three macromolecules are the essential component for all known forms of life. The central dogma of molecular biology, detailed in [START_REF] Crick | On protein synthesis[END_REF][START_REF] Crick | On protein synthesis[END_REF], describes the biological macromolecules and the ow of genetic information between them (Figure 2.6). DNA is transcribed into RNA and the RNA is translated into proteins. The circular arrow around DNA denotes its ability to replicate which is the process of producing two identical copies from one original DNA molecule. From a computational perspective, these data can 22 Chapter 2. Data mining and biological background attached to the C α atom. It is the side chain that dierentiates one amino acid to another and gives it its physico-chemical properties. The common parts between the amino acids compose the so called backbone [START_REF] Branden | Introduction to protein structure[END_REF]].

The four levels of protein structures

Amino acids constitute the building blocks of proteins. All amino acids of any protein are joined together by peptide bonds. Most proteins fold into unique three dimensional structures. However, it is possible to dierentiate between four levels of protein structure as illustrated in Figure 2.8.

-Primary structure: The sequence of the amino acid residues in the chain is called the protein primary structure.

-Secondary structure: The chains of amino acids in the primary structure can fold to form complex three dimensional structures due to a combination of chemical interactions. These three dimensional fragments can take the form of one of three standard forms: a spiral conformation called αhelix, a twisted pleated sheet called βsheet and a turn where the polypeptide chain reverses its overall direction.

-Tertiary structure: The nal folded state of a protein gives it its overall shape, i.e., what is known as the protein tertiary structure (or simply protein 3D-structure). Precisely, it is formed by the spatial relations of the secondary structures such that even residues that are far away in the chain can be very close in the 3D-space.

-Quaternary structure: In reality, proteins are often composed of several sequences of amino acids. The quaternary structure of a protein consists on the combination of its sequences where each one has a primary, a secondary and a tertiary structure.

During the evolution, proteins go through changes. From one generation to another, the amino acids forming protein sequences are exposed to changes where they gradually mutate from one type of amino acid into another through the action of DNA mutations. Mutations of amino acids are quantied in the so-called substitution matrix.

Protein substitution matrices

A protein substitution matrix is a 20*20 matrix where each value v between a pair of amino acids (x, y) presents the score of mutation of the amino acid x to the amino acid y, such that x, y

∈ [1..20]. Σ A Σ ∀l, l ∈ Σ A A : Σ 2 → [⊥, ] ⊂ R (l, l ) → s s l l substitution score s is in [⊥, ]
. If s = ⊥ then the substitution is impossible, and if s = then it is certain. The values ⊥ and may appear or not in A.

The most known protein substitution matrices are PAM [Dayho 1978] and BLOSUM [START_REF] Heniko | [END_REF]] :

PAM matrices PAM (Point Accepted Mutation) matrix was developed by Dayho [Dayho 1978]. This mutation matrix corresponds to a substitution accepted for 100 sites in a particular time of evolution, i.e., a mutation that does not destroy the activity of the protein. This is known as a one-percentaccepted-mutation matrix (1PAM). If we multiply the matrix by itself a few times, we obtain a matrix X PAM that gives the probabilities of substitution for larger evolutionary distances under the assumption that repeated mutations would follow the same pattern as those in the 1PAM matrix. To be more easily used in sequence comparison programs, each X PAM matrix is transformed into a matrix of similarities PAMX called mutation matrix of Dayho [Dayho 1978]. This transformation is performed by considering the relative frequencies of mutation of amino acids and by taking the logarithm of each element of the matrix.

BLOSUM matrices A dierent approach was undertaken to highlight the substitution of amino acids. While PAM matrices derive from very similar proteins, here the degree of substitution of amino acids is measured by observing blocks of amino acids from more distant proteins. Each block present a short and highly conserved region. These blocks are used to group all segments of sequences having a minimum percentage of identity within their block. The frequency of substitution is deduced for each pair of amino acids then a logarithmic probability matrix called BLOSUM (BLOcks SUbstitution Matrix) is calculated over these frequencies. Every percentage of identity is a particular matrix. For instance, the BLOSUM62 matrix (see Table 2.2) is obtained using an identity threshold of 62%. Heniko and Heniko [START_REF] Heniko | [END_REF]] conducted such process from a database containing more than 2000 blocks.

Biological background : bioinformatics and biological data 25

Table 2.2: The amino acids substitution matrix BLOSUM62.

C S T P A G N D E Q H R K M I L V F Y W C 9 -1 -1 -3 0 -3 -3 -3 -4 -3 -3 -3 -3 -1 -1 -1 -1 -2 -2 -2 S -1 4 1 -1 1 0 1 0 0 0 -1 -1 0 -1 -2 -2 -2 -2 -2 -3 T -1 1 4 1 -1 1 0 1 0 0 0 -1 0 -1 -2 -2 -2 -2 -2 -3 P -3 -1 1 7 -1 -2 -1 -1 -1 -1 -2 -2 -1 -2 -3 -3 -2 -4 -3 -4 A 0 1 -1 -1 4 0 -1 -2 -1 -1 -2 -1 -1 -1 -1 -1 -2 -2 -2 -3 G -3 0 1 -2 0 6 -2 -1 -2 -2 -2 -2 -2 -3 -4 -4 0 -3 -3 -2 N -3 1 0 -2 -2 0 6 1 0 0 -1 0 0 -2 -3 -3 -3 -3 -2 -4 D -3 0 1 -1 -2 -1 1 6 2 0 -1 -2 -1 -3 -3 -4 -3 -3 -3 -4 E -4 0 0 -1 -1 -2 0 2 5 2 0 0 1 -2 -3 -3 -3 -3 -2 -3 Q -3 0 0 -1 -1 -2 0 0 2 5 0 1 1 0 -3 -2 -2 -3 -1 -2 H -3 -1 0 -2 -2 -2 1 1 0 0 8 0 -1 -2 -3 -3 -2 -1 2 -2 R -3 -1 -1 -2 -1 -2 0 -2 0 1 0 5 2 -1 -3 -2 -3 -3 -2 -3 K -3 0 0 -1 -1 -2 0 -1 1 1 -1 2 5 -1 -3 -2 -3 -3 -2 -3 M -1 -1 -1 -2 -1 -3 -2 -3 -2 0 -2 -1 -1 5 1 2 -2 0 -1 -1 I -1 -2 -2 -3 -1 -4 -3 -3 -3 -3 -3 -3 -3 1 4 2 1 0 -1 -3 L -1 -2 -2 -3 -1 -4 -3 -4 -3 -2 -3 -2 -2 2 2 4 3 0 -1 -2 V -1 -2 -2 -2 0 -3 -3 -3 -2 -2 -3 -3 -2 1 3 1 4 -1 -1 -3 F -2 -2 -2 -4 -2 -3 -3 -3 -3 -3 -1 -3 -3 0 0 0 -1 6 3 1 Y -2 -2 -2 -3 -2 -3 -2 -3 -2 -1 2 -2 -2 -1 -1 -1 -1 3 7 2 W -2 -3 -3 -4 -3 -2 -4 -4 -3 -2 -2 -3 -3 -1 -3 -2 -3 1 2 11
PAMX, BLOSUMX : Which one is the best substitution matrix?

The choice of protein substitution matrices depends on the type of experiments, the desired results, and the nature of data. Although many comparative studies have been conducted in this context [START_REF] Yu | [END_REF], Mount 2008[START_REF] Brick | A novel series of compositionally biased substitution matrices for comparing Plasmodium proteins[END_REF][START_REF] Zimmermann | [END_REF], no matrix is considered as the ideal one yet. However, it is clear from these studies that the matrices rather based on comparisons of sequences or 3D-structures usually give better results than those based primarily on the model of Dayho. For the most known substitution matrices, X is among {45, 52, 60, 80, 90} for BLOSUMX, and among {100, 120, 160, 200, 250} for PAMX. Higher BLOSUM matrices and lower PAM matrices are used to compare sequences that are relatively close and short while to compare more divergent and longer sequences, it is better to use lower BLO-SUM or higher PAM. Most of current bioinformatics tools use BLOSUM62 (Table 2.2) as the substitution matrix selected by default.

Availability of biological data

The fast development we have witnessed in the past few years and still nowadays in both computer science and biological technologies, has highly facilitated the acquisition of biological data, transforming them into a computer readable format, and storing them into big databases. Indeed, this engendered the emergence of many online databases containing data that concerns dierent research areas from biology including genomics, proteomics, phylogenetics, metabolomics, and others. According to the Nucleic Acids Research (NAR) online molecular Biology Database Collection, 4 the number of databases registered in NAR has grown from 202 databases in the year 1999 to 1512 in 2013. This increase has not only been noticed on the number of databases but also on their sizes. This fact is illustrated in Figure 2.9 which shows the exponential increase in size of some of the most known biological databases.

Manual work alone is unable to match the explosive growth of the amount of biological data. This arises an urgent need for new bioinformatics tools and new data mining algorithms for automatic analysis and knowledge retrieval.

From protein 3D-structures to protein graphs

For many years, proteins have been mainly studied based on their primary structure. This is because the primary structure is more simple to represent than all the other structures since it can be seen as string of characters where each character represents one corresponding amino acid from the chain. In addition, there has been a huge gap between the number of unique protein Chapter 2. Data mining and biological background 2.3.4.1 PDB: Protein Data Bank One of the most known databases is the Protein Data Bank5 (shortly PDB) [Berman 2000] which is a free online repository of information about the 3Dstructures of large biological molecules, including proteins and nucleic acids. The PDB was created in 1971 at Brookhaven National Laboratory, and is continuously expanding. By the end of September 2013, it contains already 94540 structures, and the repository gets updated every week. In addition, the PDB website allows users to perform simple and complex queries on the data, analyze them, and visualize the results.

Protein structures are available in the PDB website in a special data format also called PDB. In fact, the PDB le is simply a textual format describing the coordinates of atoms of a molecule in the 3D-space (see Section A.1 for more details).

Parsing protein 3D-structures into graphs

A crucial step in the computational study of protein 3D-structures is to look for a convenient representation of their spatial conformation. Since a protein can be seen as a set of connected elements (amino acids and atoms), it can then be easily transformed into a graph where the elements are the graph nodes and the connections are the graph edges. In most existing works, proteins are transformed into graphs of amino acids where each one of the latter is represented by a node in the graph and the graph edges represent the connections between the amino acids.

Transformation techniques: Some approaches have been proposed in the literature for transforming protein 3D-structures into graphs of amino acids [Saidi 2009]. These approaches use dierent techniques. In the following, we present the most known approaches. In all these approaches, nodes of the graphs represent the amino acids. However, they dier in the way of considering the edges in attempt to reect the truly existing interactions. Some of them express the edges by the strength of interaction between amino acids' side chains, while, others express the edges based on the distance between pairs of amino acids.

-Triangulation Triangulation is used to transform an object, represented by a set of points in a plane or in a 3D-space, into a set of triangles. It is possible to have multiple triangulation for the same object. The Delaunay triangulation [Delaunay 1934] is a special way 2.3. Biological background : bioinformatics and biological data 29 of triangulation. It was used to build protein graphs in several works [Bostick 2004[START_REF] Huan | [END_REF][START_REF] Stout | [END_REF]]. The main idea is to consider the amino acids as a set of points in the space, then to iteratively try to create tetrahedrons such that no point is inside the circum-sphere6 of any tetrahedron, i.e., empty spheres (see the example in Figure 2.10). -Main Atom This is the main approach used in the literature. The main idea is to abstract each amino acid only to a main atom M A of it. This main atom can be real, like the C α or the C β atoms, or ctive, like the amino acid centroid or the side chain centroid [Lovell 2003[START_REF] Huan | [END_REF].

Two nodes representing the amino acids u and v are linked by an edge e(u, v) = 1, if the euclidean distance between their two main atoms

Δ(M A (u), M A (v)) is below a threshold distance δ. Formally: e(u, v) = 1, if Δ(M A (u), M A (v)) ≤ δ 0, otherwise (2.1)
In the literature, many works used this method basically with C α atom and with usually δ ≥ 7Å on the argument that C α atoms dene the overall shape of the protein conformation [START_REF] Huan | [END_REF]].

-All Atoms Some extensions have been made to the main atom method.

For instance in [Saidi 2009], authors proposed all atoms where instead of considering the distances only between the main atoms of amino acid, Chapter 2. Data mining and biological background they consider it between all the atoms of the amino acids ( A A ). Formally:

e(u, v) = 1, if Δ(A A (u), A A (v)) ≤ δ 0, otherwise (2.2)
Discussion Here, we discuss the above mentioned transformation techniques of protein 3D-structures into graphs. We assume that the correctness of each technique is measured by its ability to reect in the edges of the graph it generates, the really existing links in the protein. The Delaunay triangulation method suers from two main drawbacks because of the empty circum-spheres condition. First, we can nd many false links between very far nodes in the protein especially at the surface of the protein where the circum-spheres get easily out of the cloud of atoms. Second, the empty sphere condition does not allow a node to make connection with any other one outside of its tetrahedron sphere. This makes it omit many edges even in the presence of real interactions.

The main atom method suers a drawback. Since it abstracts the amino acids into one main atom, it may omit possible edges between other atoms in the amino acids that are more close than the main atoms. Moreover, in the case of considering the centroids of the amino acids as the main atoms, it may also suer from two problems. In the case where the amino acids are big, if the centroids of the amino acids are farther than the given distance threshold then they will be considered with no links while a real connection could be established between other close atoms. In the case where the amino acids are small, if the distance between the centroids of the amino acids is smaller than the given distance threshold then they will be considered as connected while they can be disconnected in reality. To overcome main atom drawbacks, all atoms method considers theoretically the distance between all the atoms in the amino acids, this highly increases the complexity of the execution time.

Besides, among the heuristics the authors proposed to alleviate the complexity of their approach, they do consider only the distance between the centroids of the side chains of amino acids to decide whether they are connected or not, without considering their chemical properties. This may engender many false edges.

As biologically speaking the C α atoms dene the overall shape of the pro- tein conformation [START_REF] Huan | [END_REF]], we choose to use the main atom method in the experiments we conduct, using C α as the main atom. A real example of a protein 3D-structure (the hemochromatosis protein) transformed into a graph is illustrated in Figure 2.11. Although using such representation may omit some edges and contains some false ones, it opens new challenges and

C α δ ≥ 7
methods to transform protein 3D-structures into graphs which enables using graph mining and more generally data mining techniques to study them. In the next chapter, we will review existing works in the area of pattern mining over graph data, and we will focus on the problem of feature selection for graph patterns as a way to tackle the curse of dimensionality.

Aims

In this chapter, we present works in the literature that are relevant to this thesis. These works are presented over three levels. As many of the subgraph Chapter 3. Related works selection approaches as well as the ones proposed in this thesis perform the selection over the set of frequent subgraphs, the rst part of the chapter details and explains the problem of frequent subgraph mining in graph databases and lists the main used approaches to address this task. In the second part of the chapter, we present in general the problem of feature selection and discuss the dierent possible techniques and search strategies. In the last part, we review a panoply of the most interesting subgraph selection approaches. We try to partition these approaches into dierent groups depending on the selection strategy and or the type of the selected subgraphs. A descriptive table presenting the characteristics of the mentioned subgraph selection approaches is presented as well.

Graph mining

Graphs are one of the most powerful structures to model complex data [Cook 2006]. In fact, any data composed of entities having relationships can be represented by a graph where the entities will be seen as the graph nodes and the relationships as the graph edges. Recently and thanks to the increasingly cheaper cost of storage devices and the availability of high processing power, graphs are becoming ubiquitous. They are increasingly used in the modeling and the analysis of many real world applications such as the world wide web, blogs, cell phone communications, XML documents, and even electronic circuits. In chemoinformatics and bioinformatics, graphs are used to model various types of molecules and biological data such as chemical compounds, gene and metabolic networks, protein structures and protein-protein interaction networks. Graphs are also used in the analysis of social networks such as Facebook and Google+, where graphs represents networks of connected users and are used to understand phenomenons such as rumors propagation and criminal networks or to predict links or to detect central users.

One of the most powerful techniques to analyze and study graph data is to look for interesting subgraphs among them. Subgraphs are said to be interesting if they obey to one or dierent constraints. These constraints can be structural and topological, based on frequency, coverage, discrimination or even semantic if the graphs are labeled.

Subgraph mining

One of the main and most challenging tasks in graph mining is to look for recurrent substructures, i.e., to extract frequent subgraphs [START_REF] Cheng | [END_REF]]. In fact, there exists two types of frequent subgraph discovery namely 3.4. Frequent subgraph discovery

35

-From a single large graph: In this case, we wish to determine all subgraphs that occur at least a certain number of times in a one large graph (e.g., the World Wide Web graph).

-From a database of many graphs: In this case, we have a database of graphs (e.g., a family of protein 3D-structures represented by graphs)

and we wish to determine all subgraphs that occur at least in a certain number of graphs of the database.

In dierent applications, we may be interested in dierent kinds of subgraphs, such as subtrees, cliques (or complete graphs), bipartite cliques, dense subgraphs, and so on. These subgraphs are used later as patterns to describe the data under consideration. Indeed, they may represent, for example, communities in social networks, hubs and authority pages on the WWW, clusters of proteins involved in similar biochemical functions in protein-protein interaction networks, and so on. But in the most common case, subgraphs are mined from data based on their frequency.

Frequent subgraph discovery

The problem of frequent pattern mining has been widely addressed in data

mining. Yet, in the case of graph data, mining frequent patterns is more challenging mainly because of the combinatorial nature of graphs [Zaki 2014].

Indeed, in the case of graphs the process of determining support is dierent.

As in this thesis we are more interested in the mining of frequent subgraphs from a graph database, this subsection denes and gives the formal statement of the problem of frequent subgraph discovery in graph databases.

Problem denition

Let G be a graph database. Each graph G = (V, E) of G is given as a collection of nodes V and edges E. We denote by |V | the number of nodes of G (also referred as the graph order) and by |E| the number of edges of G (also called the graph size). If two nodes u and v ∈ V and {u, v} ∈ E then u and v are said to be adjacent nodes. The nodes and edges of G can be labeled within an alphabet

Σ such that G becomes G = (V, E, Σ, L) where Σ = Σ V ∪ Σ E
G = (V, E, Σ, L) G = (V , E , Σ , L ) f V → V ∀u, v ∈ V : ∀{u, v} ∈ E ⇔ {f (u), f(v)} ∈ E ∀v ∈ V : L(v) = L (f (v)) ∀{u, v} ∈ E : L{u, v} = L {f (u), f(v)} L L G G G G G ⊆ G f : V → V ∀u, v ∈ V : ∀{u, v} ∈ E → {f (u), f(v)} ∈ E ∀v ∈ V, L(v) = L (f (v)) ∀{u, v} ∈ E : L{u, v} = L {f (u), f(v)} f G G G G G G g G τ G g G g i.e. g G g g | G g | g support(g) = | G g | | G | ≥ τ 3 3 = 1 1+1+1 3 = 1 i.e. τ ∈ i.e. 2 3 1 3 5 2
The DFS (Figure 3.3 (b)) follows the same branch until the bottom of the tree before visiting the other branches. Supposing that nodes on the right are visited before those on the left, candidates in the tree are constructed using the following order:

-n 0 , n 1 , n 4 , n 2 , n 5 , n 3 , (n 4 : but pruned for duplication since already generated from n 1 ), (n 5 : but pruned for duplication since already generated from n 2 ).

Frequent subgraph discovery approaches

Many approaches for frequent subgraph mining have been proposed [Jiang 2013, Lakshmi 2012, Krishna 2011]. A pioneer work is [START_REF] Cook | [END_REF],

where authors proposed an approximate and greedy search algorithm named SU BDU E for discovering frequent graph patterns based on a minimum description length and background knowledge. Other works have been proposed based on the principles of articial intelligence, like W ARMR [START_REF] King | [END_REF]] and F ARMER [START_REF] Nijssen | Faster association rules for multiple relations[END_REF]]. They successfully mined frequent subgraphs from chemical compounds data. Although these approaches allow to completely discover all frequent subgraphs, they suer from the high consumption in terms of time and computational resources. In addition, the discovered subgraphs are semantically very complex since the graphs where initially transformed into datalog facts. Besides these studies, there exists two main categories of the approaches of frequent subgraph discovery namely: the apriori-based approaches and the pattern-growth approaches.

Apriori-based approaches

Generally, apriori-based approaches start from subgraphs of small sizes. Then, in a bottom-up manner, they generate subgraph candidates by adding a node or an edge to an existing frequent subgraph. The main idea behind aprioribased approaches is that subgraph candidates of size k + 1 are generated by means of a join operation on two frequent subgraphs of size k having a common subgraph of size k-1. Thus, in order to be able to generate subgraph candidates of level k + 1, all subgraphs of size k have to be already generated. Hence, the name apriori-based approaches. Consequently, all apriori-based approaches has to use the BFS strategy since they follow a level-wise candidate generation.

The main algorithms that have been proposed in this category are AGM [Inokuchi 2000], FSG [Kuramochi 2001] and DPMine [Vanetik 2002]. AGM and FSG are very similar, but the main dierence between them is that AGM generates a candidate by extending a frequent subgraph with a node. While, FSG generates a candidate by extending a frequent subgraph with an edge. DPMine uses edge-disjoint paths as the expansion units for candidate generation. It starts by identifying all frequent paths, then, all subgraphs with two paths. After that, it starts generating subgraphs with k paths by merging pairs of frequent subgraphs of k-1 paths having k-2 paths in common.

Pattern-growth approaches

Pattern-growth approaches extend an already discovered frequent subgraph by adding an edge in every possible position. Adding an edge may result adding a new node. Extensions are recursively performed until no more frequent subgraph is generated. In contrast to apriori-based approaches, pattern-growth approaches are more exible on the search method. Both BFS and DFS can work. Pattern-growth approaches do not need the expensive join operations used in the apriori-based approaches, nevertheless, they highly suer the problem of duplicates generation. Indeed, the edge extension strategy can results generating the same subgraph multiple times from dierent extensions. Hence, existing pattern-growth approaches tried to propose ways to avoid or at least minimize the generation of duplicate subgraph candidates.

The main algorithms that have been proposed in this category are MoFa [START_REF] Borgelt | [END_REF]], gSpan [START_REF][END_REF]], FFSM [Huan 2003] and GASTON [START_REF] Nijssen | [END_REF]]. MoFa is mainly proposed to mine frequent subgraphs in a set of molecules. In order to accelerate the mining process, MoFa stores the embedding list of previously found subgraphs such that the extensions will be restricted only to these embeddings. Even though MoFa also uses structural and background knowledge for pruning, it still generates many duplicates.

The gSpan algorithm addresses the problem of duplication dierently. It rst starts generating candidates using the right-most extension technique. In this technique, according to a DFS on the graph, the path that goes straightly from the starting node to the target node is called the right-most path. Only extensions on the right-most path are allowed. It was proved that candidates generation using the right-most extension technique is complete. To alleviate the cost of isomorphism between subgraphs, gSpan uses a canonical representation where each subgraph is simply represented by a unique code called the minimum DFS code, allowing an easy detection of isomorphic subgraphs.

FFSM also uses a canonical representation, in a matrix form, called the Canonical Adjacency Matrix (CAM) to represent graphs and to detect isomorphism. It generates new subgraph candidates either by extension of a CAM or by joining two CAMs using a set of adapted operators.

In many contexts, GASTON is considered as the fastest subgraph mining algorithm. In contrast to all existing approaches, it exploits the fact that a wide range of the discovered frequent patterns are paths and trees, and only a portion (that is sometimes very small) represents subgraphs with cycles. Hence, GASTON considers them dierently by splitting the frequent subgraph mining into path mining, then subtree mining, and nally subgraph mining. Consequently, the subgraph isomorphism is only performed in the nal step.

GASTON also records the embedding list to save unnecessary isomorphism detection by extending only patterns that appear in the list.

Variants of frequent subgraph mining: closed and maximal subgraphs

According to the antimonotonicity property, all subgraphs of a frequent subgraph are also frequent. This arises a problem of dimentionality. Indeed, this problem becomes even more serious with large subgraphs as they contain an exponential number of smaller frequent subgraphs. To overcome this problem, variants of frequent subgraph mining have been proposed, namely closed subgraph mining and maximal subgraph mining.

Denition 10 (Closed subgraph) A frequent subgraph g is said to be closed, if it has no supergraph g (g ⊂ g ) that is also frequent and has the same support.

Denition 11 (Maximal subgraph) A frequent subgraph g is said to be maximal, if it has no supergraph g (g ⊂ g ) that is also frequent.

According to the denitions 10 and 11, both closed and maximal frequent subgraphs present a compact representation of the frequent subgraphs. Closed subgraph compactness is lossless since it contains all the information about the frequent subgraphs and their supports. However, maximal subgraph compactness does not consider the whole information since although all frequent subgraphs can be restored, the exact support of each subgraph is lost. The main approach that have been proposed in the literature for closed subgraph mining is CloseGraph [START_REF][END_REF]] and those for maximal subgraph mining are SPIN [Huan 2004b] and MARGIN [Thomas 2006]. Although the set of closed or maximal subgraphs is much smaller than the set of frequent ones, the number of subgraphs is still very high in real-world cases.

Feature selection

Feature selection is also known in the literature as pattern selection, attribute selection, variable selection or variable subset selection [Liu 1998[START_REF] Guyon | An Introduction to Variable and Feature Selection[END_REF], Liu 2007a[START_REF] Saeys ; Yvan Saeys | A review of feature selection techniques in bioinformatics[END_REF][START_REF] Ladha | [END_REF]]. The task of feature selection has been widely addressed in data mining not only for subgraphs but also for other types of patterns such as association rules, itemsets and sequential motifs. Although many approaches have been proposed in the literature allowing an ecient computation of frequent patterns, the number of discovered patterns is often very high. This is an obvious impact of the high dimensional nature of many types of data. Besides, most frequent pattern discovery approaches were not originally designed to consider the relevance of features.

The main goal of feature selection is to reduce the number of features by removing the redundant and irrelevant ones such that only a subset of interesting features is retained.

Relevance of a feature: According to an interestingness criterion, a feature is redundant if it does not bring any additional information over the currently selected features and thus it can be replaced by at least one of the already selected features. A feature is considered as irrelevant if it does not provide any useful information in any context such that it does not have any inuence on the output of the prediction.

Feature selection techniques

Many approaches have been proposed for feature selection to resolve the dimensionality problem when the number of patterns is high. It is possible to categorize the existing approaches in dierent ways depending on the criterion used for classication. For instance, according to their relation to the learning task, feature selection approaches can be classied into:

-Learning task dependent selection approaches they attempt to nd a subset of features that enhance the prediction capabilities of a target learning task, i.e., classication, clustering, etc. -Learning task independent selection approaches they tend to enhance the quality of the feature set and to remove irrelevant features without regards to the learning task. The most conventional classication of feature selection approaches comprises three categories, namely wrapper, embedded or lter approaches [Liu 2007a].

Wrapper approaches

Wrapper approaches [Cadenas 2013] are used to optimize the feature set to best t a specic learning model. As shown in the Figure 3.4, they start approaches have been proposed for selecting signicant subgraphs. Although the main goal of these approaches is to obtain a smaller yet more informative subset of subgraphs, each approach has a dierent way of evaluation.

Problem statement

In general, the process of feature selection for subgraphs can be formulated as follows. Given a graph database G = {G 1 , ..., G n } and an evaluation function F , nd all signicant subgraphs g * ∈ G such that :

g * are the set of subgraphs that maximize the evaluation function F , i.e., g * = argmax g (F (g)). Or, g * are the subgraphs having an evaluation score that is greater or equal to a given threshold, i.e., g * = F (g) ≥ τ , if F is a threshold based function. Or, g * are the k subgraphs having successively the best score with F , i.e., g * = T op k F (g).

In all three cases, the best scenario is that when the evaluation function F is embedded within the subgraph mining such that the signicant subgraphs are directly mined from G without needing to exhaustively generate all the set of subgraphs. However, it is not always simple to do, especially if the evaluation function is not antimonotonic. As many approaches have been (and are being) proposed for signicant subgraph selection, in the following subsections, we present and discuss some of the recent and most interesting methods in the literature. We try to group them into categories based on their selection strategy.

Mining top-k subgraphs

The main idea behind top-k selection approaches is that in many application domains a user may be interested in nding a specic number of patterns that best qualify to a given evaluation criteria. Thus, in this selection strategy, the methods accept a parameter k and a criterion F , then return the best k frequent subgraphs which are ranked according to F .

An interesting top-k approach was proposed in [START_REF] Xin | [END_REF]]. Authors proposed a greedy algorithm that approximates an optimal solution with performance bound for mining redundancy-aware top-k patterns. Their algorithm was applied on graph patterns aiming to nd subgraphs with the highest signicance and the minimal redundancy simultaneously. The signicance of a pattern p is measured using a function S such that S(p) is associated to a real value, and S is dened by the context of application. The redundancy between pairs of patterns R(p, q) is measured by their structural similarity, i.e., by computing the edit distance between them. It is worth mentioning that authors assume that the combined signicance of two patterns is no less than the signicance of any individual pattern and does not exceed the sum of two individual signicance. Authors showed experimentally the eciency of the their approach on two real world applications namely document theme extraction and correlation-directed disk block prefetch. However, to mine the redundancy-aware top-k patterns, the user needs to nd all frequent patterns and assess their signicance in the rst place.

A recent work, termed TGP [START_REF] Li | [END_REF]], mainly motivated by the fact that in most real-world cases it is dicult to select a proper value of minimum support. Indeed, if the value of the minimum support is too low thousands of patterns are extracted, but many of them are irrelevant. However, if the the value of the minimum support is too high, several large subgraphs will be excluded from the extraction result. TGP is an approach for mining topk frequent closed graph patterns with size no less than a minimum size but without specifying a minimum support. It adopts a new structure called Lexicographic Pattern Net to store the patterns and relationships between them which helps facilitating the mining process. Indeed, it helps in both dynamically raising the minimum support threshold to ensure the completeness and correctness of results, and in avoiding to generate again the same candidate patterns in the next mining step. Experimental evaluation was conducted on nancial, chemical compound, and synthetic datasets. Authors showed that in the case where the user is unable to provide a minimum support threshold, TGP is able to nd the top-k frequent closed graph patterns completely and accurately. Although TGP allows to avoid specifying a minimum support threshold, the user still has to dene a proper number of patterns to select, i.e., the k constraint.

Clustering-based subgraph selection

The task of clustering-based subgraph selection aims generally at obtaining a set of representative patterns, where each representative resembles a cluster centroid. In fact, clustering is the process of bringing together a set of objects into classes of similar objects. The denition of similarity between the input objects varies from one clustering model to another. In most of these models the concept of similarity is based on distances, such as Euclidean distance or cosine distance.

RP-FP and RP-GD [Liu 2007b] are two approaches for summarizing frequent graph patterns by a smaller number of representatives. Authors ex-ploited and extended the concepts of δ-cover and δ-jump, to eciently nd the representative subgraphs. A graph g is δ-covered by another graph g if g ⊆ g and the distance between them D(g, g ) is lower than δ. A δ-jump subgraph g is a graph pattern such that the distance between g and any proper supergraph of g is greater than δ. The rst approach, RP-FP, selects a subset of representative patterns from a set of closed frequent subgraphs. The RP-FP method works well when the size of the set of frequent closed subgraphs is not very large. However, in real applications where the number of frequent closed patterns is usually high, RP-FP does not scale well. Therefore, authors proposed the second approach RP-GD which directly mines representative graph patterns from graph databases with lower tightness on the summarization quality. RP-GD calculates the representative set of patterns simultaneously during the extraction of frequent closed patterns. Thus, when the number of closed graph patterns is very large, RP-GD is much more ecient than RP-FP. Experiments conducted by authors on chemical compound and synthetic graph databases showed that RP-GD is much more ecient than RP-FP while achieving comparable summarization quality. Yet, the user has to dene the right value of δ.

RING [START_REF] Zhang | [END_REF]] is another clustering-based subgraph selection approach. It aims at nding a subset of N representative subgraphs among the frequent ones. The representative subgraphs should satisfy the distinction where all representative subgraphs should be dissimilar to each other, and the completeness where the number of frequent subgraph patterns which cannot be delegated by the representative patterns should be as small as possible. RING adopts the idea of transforming each subgraph into a vector of invariants. Then, it uses the euclidean distance between these vectors to compute the distance between subgraphs instead of using the costly edit distance measure (the minimum amount of deletion/insertion of nodes and edges to transform one graph into another). To nd the N representative subgraphs, all frequent subgraphs are grouped into N clusters, and the subgraphs that are closest to the clusters centers are selected as representatives. Authors also proposed a way of integrating RING selection into the mining process of frequent subgraphs to directly discover the representative subgraphs. They process the subgraph discovery in a DFS manner. For any frequent subgraph P 1 represented by another representative subgraph P 2 . If while P 1 is being extended another pattern P 11 represented by the same representative P 2 has been reached then the growing stops. If such subgraph has not been reached, the growing continue and if the frequent subgraph is not covered by any one of the representatives, then it is considered as a new representative. The DFS mining algorithm stops when all the supergraphs of existing representative are not frequent. RING was tested on a synthetic graph dataset as well as on a graph representing a protein-protein interaction network. RING was able to select representative subgraphs in a fast way. Yet, its pruning condition assumes that the supergraphs of the pruned subgraph will be also represented by the same representative which is not always true. This may prevent reaching many representatives and thus leading to poor selection.

Sampling-based approaches

In statistics, sampling can simply be dened by the task of selecting a subset of individuals among a given statistical population to estimate the characteristics of the whole set. In our context (i.e., pattern selection), sampling is a method for selecting a subset of n patterns out of N such that the sampled n patterns allows (or approximately) estimating the characteristics of all the N patterns. Sampling-based approaches are mainly proposed due to the assumption that in many real application contexts, it is very costly or even impossible to generate the entire set of frequent patterns. Thus, sampling-based selection approaches tries to approximately generate the set of signicant patterns by only considering a sample of the entire set of patterns.

ORIGAMI [START_REF] Hasan | [END_REF]] is a method for the extraction of representative subgraphs. Unlike most of the existing selection approaches that considers relations between patterns in the transaction space to obtain representatives, ORIGAMI considers the distances in the pattern space which is obviously more complex especially in the case of graph patterns. ORIGAMI is composed of two steps. First, it starts by extracting a sample of frequent maximal subgraphs through a random walk along the frequent subgraph lattice. Then straightforwardly, it selects a subset of α-orthogonal (non-redundant) and β-representative subgraphs. Two subgraphs are α-orthogonal if their similarity is bounded above by α, and a subgraph is said to be β-representative for another if their similarity is at least β. The similarity between two subgraphs is computed they nding how much their maximal common subgraph [Abu-Khzam 2007] represent from their overall structure. Experiments were conducted on various types of datasets: chemical coumpounds, protein structures, protein-protein interaction network and a synthetic dataset. They showed the eciency and scalability of the approach. However, the selection in ORIGAMI is straightforward and is performed after discovering the frequent maximal subgraphs. In addition, the randomized search used in ORIGAMI risks walking only over a portion of the frequent subgraph space while the rest of it is ignored. This may leads to discover poor quality representatives.

In [START_REF] Hasan | [END_REF]], authors proposed an output space sampling approach for subgraphs. It samples interesting subgraph patterns without enumerating the entire set of candidate frequent patterns. The sampling is driven by a distri-bution that is predened by the user. This is performed through a random walk on the candidate subgraph partial order. When the walk converges to a desired distribution, the algorithm stops and returns the discovered subgraph samples. Experimental analysis was performed on graph datasets (namely chemical coumpound, protein interaction and cell-graphs datasets) as well as on an itemset dataset. Results showed that the output space sampling approach is scalable and able to discover a sample of signicant patterns according to the desired distribution. This approach is useful in the case where traditional approaches fail to run. Although authors successfully performed experiments on small and large graph datasets, their approach stores the entire database in the memory which makes it inecient if the database does not t the memory. Besides, the user should carefully dene the distribution parameter since it highly aects the quality of the sampling.

In [START_REF] Schietgat | Eective feature construction by maximum common subgraph sampling[END_REF]], authors proposed an approach for mining a specic type of subgraph patterns. The main idea of their approach is to mine the maximum common subgraphs (MCSs) [START_REF] Abu-Khzam | The Maximum Common Subgraph Problem: Faster Solutions via Vertex Cover[END_REF] between pairs of graphs in the database. The pairs of graphs are randomly selected from the database and thus the mined subgraphs represent only a sample from the entire set (MCSs sample). Experimental evaluation was performed on 60 benchmark datasets of molecular compounds representing problems from chemoinformatics. To evaluate the quality of the mined subgraphs, they were used as features for classication. Results show that their approach produces a smaller and less redundant set of subgraph patterns, and allows better prediction performance in classication than other state-of-the-art approaches. Besides, it is parameter free and runs in polynomial time. However, the proposed approach is restricted to outerplanar graphs [START_REF] Schietgat | Eective feature construction by maximum common subgraph sampling[END_REF]]. Although it works well with chemical compounds datasets, this approach may not scale well with larger graphs (such as the case of graphs representing protein 3Dstructures), and larger datasets since the search is pairwise.

Approximate subgraph mining

Approximation is usually used when the exact result is unknown or dicult to obtain such that the obtained inexact result are within required limits of accuracy. In many applications, mining the whole set of frequent subgraphs is very dicult. Besides, in applications like the analysis of protein interaction networks and social networks, slight dierences between subgraphs may not be important. In such cases, approximation is a way to handle both issues by only enumerating an approximate set of subgraphs such that similar but slightly dierent subgraphs will collapse into one representative. Approximation in subgraph mining is performed by structural approximation or label 50 Chapter 3. Related works approximation.

An interesting work that falls in this category is [Chen 2008], where authors proposed an approach for mining a set of structural representative subgraphs among the whole set of frequent ones. After mining all frequent subgraphs, they perform a smoothing-clustering selection that is based on approximate structural similarity on micro and macro sides. In the smoothing step, they consider a tolerance threshold to summarize approximately isomorphic subgraphs into one representative. In the clustering step, they collapse multiple structurally similar subgraphs into one representative using a clustering algorithm where the center of the cluster is considered to be the representative subgraph delegate. They used K-Medoids [START_REF] Ng | [END_REF]] for non-overlapping clustering and ε-bounded clustering [Hochbaum 1997] for overlapping clustering where each subgraph may belong to multiple clusters and thus may be represented by more than one structural representative. Eciency of the smoothing-clustering approach was evaluated through experiments on chemical compounds and synthetic graph dataset. Yet, in order to nd the representatives, all frequent subgraphs have to be discovered rst. Besides, the method contains many parameters that need to be properly dened in order to prevent poor selection.

Unlike structural approximation, less attention have been devoted to label approximation. A very recent work have been developed in [Anchuri 2013] for mining signicant subgraphs based on label approximation. This work operates in the context of single large graph, however, we are here interested in approaches devoted to graph databases. Thus, this approach is more discussed in chapter 4 as a matter of comparison. Structural approximation is also more discussed in chapter 5.

Discriminative subgraph selection

Supervised classication is one of the important applications that use frequent subgraphs and in general frequent patterns. In the case where graphs in the database are labeled (i.e., each graph is aliated to a class), it is possible to extract discriminative frequent subgraphs. These subgraphs are lately used as attributes for machine learning classiers to help building models that best discriminate between classes. Several selection methods and algorithms have been proposed for mining discriminative frequent graph patterns. In the following, we list and explain some of the best known in the literature.

3.6. Feature selection for subgraphs 51 3.6.5.1 Filter methods

In [START_REF][END_REF]], authors proposed LEAP, an approach for mining the most discriminative subgraphs. LEAP is designed to exploit the correlation between patterns through both structural similarity and signicance. It iteratively looks for the optimal patterns until all graphs are covered. LEAP was tested on a collection of molecular compound datasets transformed into graphs. It is able to quickly locate few number of highly discriminative subgraphs without exploring the whole pattern space. The selected subgraphs facilitate the training of a classication model and help enhancing its accuracy.

GraphSig [START_REF] Ranu | [END_REF]] provides a solution to mining discriminative subgraph patterns with low frequencies. It starts by converting graphs into feature vectors through a random walk with restarts on each node. Domain knowledge is used to select a meaningful feature set. GraphSig assumes that graphs with similar feature vectors share highly frequent subgraphs. Thus, it clusters the graphs having similar feature vectors into small groups. After that, it mines frequent subgraphs in each group with high frequency thresholds ensuing a high reduction in the computation cost. GraphSig was tested on molecular compound datasets. Results show that GraphSig is scalable and able to nd discriminative patterns in large graph datasets and even with low frequencies.

GAIA [START_REF][END_REF]] is another approach for mining discriminative subgraphs for graph classication. GAIA adopts evolutionary computation in discriminative subgraph mining through a randomized exploration of the candidate subgraphs search space. Further, as the search is randomized, GAIA uses parallel computation to improve the quality of the set of selected discriminative patterns by integrating the results from independent instances of pattern evolution. After discovering the discriminative patterns, GAIA employs sequential coverage and uses the mined patterns to generate association rules as graph classiers. Experimental evaluation of GAIA was performed on a number of protein and chemical compound datasets. It showed that due its parallelization technique, GAIA is scalable and able to quickly nd highly discriminative subgraphs.

CORK [Thoma 2010] is a subgraph selection method for mining discriminative subgraphs. The main idea in CORK is to preserve subgraphs that eliminate the correspondence between graphs of dierent classes and that also enhance the discrimination power of the set of already selected subgraphs.

It attempts to discover frequent subgraphs that are most discriminative for classication using a submodular quality function. Authors showed that the used submodular quality function criterion can be integrated into the stateof-the-art tool for frequent subgraph mining gSpan, allowing fast pruning of Chapter 3. Related works the search space for discriminative frequent subgraphs mining. Eciency of CORK was evaluated on various protein and chemical compound datasets.

Results showed that CORK works well with two classes as well as with multiclass classication problems.

In [START_REF] Zhu | [END_REF]], authors proposed an approach for mining diversied discriminative subgraphs termed D&D. The main idea in D&D is that besides a discrimination measure it additionally explores the diversity between subgraphs. Diversity is considered by reducing the overlapping between a new candidate subgraph and the already selected subgraphs, based on an edgecover. To further enhance diversity, it also considers how to reduce the overlapping between the occurrence list of the candidate subgraph and those of all the already selected subgraphs. Experimental analysis on protein and chemical compound datasets showed that besides the discriminative power, considering the diversity between subgraphs during the selection highly affects the results and enhances the classication by making the positive and negative graphs more separable.

Boosting methods

In the previously mentioned selection methods, the training and building of classication models are performed separately, i.e., after mining the set of discriminative features. There exists other methods in the literature where the search for discriminative subgraphs is performed at the same time as the construction of the classication models. In the following, we try to cover some of the most interesting works in the literature.

An approach termed gPLS was proposed in [START_REF] Saigo | [END_REF]]. It uses DFS to mine the frequent graph patterns. It adapts the powerful mathematical tool of PLS (Partial Least Squares) regression to graph mining to select informative subgraphs then uses them to directly build a classier with fewer iterations than typical boosting methods. The gPLS algorithm was evaluated on chemical compound datasets. It creates latent variables involving response variables, thus leading to better predictions. However, these latent variables have the known disadvantage of poor interpretability.

COM [Jin 2009] is a graph classication method which follows a process of pattern mining and classier learning. COM employs a pattern exploration order such that the complementary discriminative patterns are examined rst.

Based on the subgraphs co-occurrences information, it constructs classication rules by assembling weak features in order to generate strong ones. Patterns are grouped into co-occurrence rules during the pattern exploration, leading to an integrated process of pattern mining and classier learning. Evaluation of COM on protein and chemical compound datasets showed that it has com-3.6. Feature selection for subgraphs 53 petitive results in terms of classication accuracy and execution time. Besides, it produces an interpretable classier.

The gBoost algorithm [START_REF] Saigo | [END_REF]] is a mathematical programming boosting method for classifying labeled graphs. It progressively collects discriminative subgraph patterns through a branch-and-bound pattern search algorithm based on the DFS code tree. The search algorithm of gBoost is integrated into gSpan. It uses the class labels as an extra information source for pruning the search space and also reuse the constructed search space in later iterations to minimize the computation time. gBoost repeatedly constructs multiple weak classiers where each weak classier (called decision stump) uses a subgraph as a classication feature. Experiments of gBoost were conducted on chemical compound datasets. They showed that gBoost scores very high in classication as well as in regression. In addition, it is exible and can be coupled with any pattern mining algorithm.

In [START_REF] Fei | Boosting with structure information in the functional space: an application to graph classication[END_REF]], authors designed LPGBCMP, a boosting method for graph classication. It selects clustered features by considering the structure relationship between subgraph patterns in the functional space. The selected subgraphs are used as weak classiers (also called base learners) to obtain high quality classication models. Authors theoretically proved that LPGBCMP exhibits a natural grouping eect for nearby spatial or overlapping features, and they showed that the proposed method can be naturally extended to other semi-structured data such as sequences. Experimentally, they evaluated LPGBCMP on classifying a set of protein datasets. Results showed that their approach provides high classication performance.

A common drawback of all these methods is that in the case where graphs in the database has no class labels, they become useless. Besides, they considers the discrimination power of patterns individually. This may fail if no individual pattern has high discrimination power, yet, jointly some patterns may have higher discrimination. Moreover, the selected patterns may be individually discriminative but redundant if there exists a signicant overlap in their supporting graphs. This makes them more vulnerable to overtting.

Other signicant subgraph selection approaches

Some other selection approaches have been proposed for mining signicant subgraphs, not necessarily for a specic application context, but only for extracting relevant or hidden information or to simply characterize a given dataset. Many of these approaches have their own original and unique selection technique and thus it is dicult to classify all of them under one of the above subgraph-selection categories. In the following, we present some of the most interesting approaches.

In [START_REF] Pennerath | The Model of Most Informative Patterns and Its Application to Knowledge Extraction from Graph Databases[END_REF]], authors were interested in mining a small number of patterns for characterizing a given dataset. The selected patterns should guarantee maximum informativeness and minimum redundancy. They introduced the class of Most Informative Patterns (MIPs). In fact, structural redundancy is assessed in MIPs through mining only the closed patterns and not all the frequent ones, and the informativeness of a pattern is measured with respect to a scoring function given by the expert. Authors presented two algorithms for extracting MIPs: the rst one directly searches for MIPs in a dataset while the second one selects MIPs from frequent patterns. They showed that MIPs can be used on dierent kinds of patterns and they applied it on itemsets and subgraphs. Experimental analysis was performed on dierent itemset datasets and a chemical compound graph dataset. Results showed that MIPs is able to provide a reduced set of patterns that are representative of a dataset. Yet, the selected MIPs still contains some redundancy. In addition, the redundancy function is user-dened. Although this makes the approach exible, it may be a hard task in some applications.

Recently, some approaches for patterns selection have adopted the notion of dominance between patterns to mine skyline patterns [START_REF] Papadopoulos | [END_REF], Soulet 2011, Bouker 2012]. In [START_REF] Papadopoulos | [END_REF]], authors proposed Sky-Graph a selection approach dedicated to graph patterns. The main goal of this approach is to consider simultaneously, in the selection, a set of user-dened criteria. These criteria are usually in the form of interestingness measures.

The set of dened measures are considered together through skyline processing. In skyline processing, the patterns returned to the user are the ones that are not dominated by any other pattern. A pattern P 1 dominates another pat- tern P 2 if P 1 is as good as P 2 with all measures and P 1 scores better than P 2 in at least one measure. The higher the subgraph scores with the measures, the more important it becomes. SkyGraph was applied in the context of graphs towards retrieving skyline subgraphs. Experiments were conducted on graph databases representing a microarray network, road network of San Francisco, and co-authors network using two measures to determine the importance of subgraphs namely the order of the subgraph (the number of nodes) and the subgraph edge connectivity. They showed that the dominance relation allows SkyGraph to detect important subgraphs. However, SkyGraph risks selecting only one subgraph in the case were the latter outperforms all the other subgraphs for the considered measures. Thus, analyzing the correlation between the considered measures may help avoiding such problem. Besides, introducing a ranking function to score the patterns may help specifying a sucient number of patterns in the case were the selected ones is not enough for the application. Some other works addressed the interestingness of patterns dierently, 3.7. Discussion 55 they assessed the signicance of patterns based on their structure. Depending on the application, it may be interesting to target patterns having a specic type of structure. An interesting example of such approaches was proposed in [Saidi 2012] were authors proposed an approach for extracting the so-called ant-motifs from protein 3D-structures. First, they transform protein 3D-structures into protein graphs, then they try to discover common substructures having an ant-like shape such that each substructure is mainly composed of a fragment from the primary structure that is enriched with other distant amino acids that are directly linked to the considered fragment. Experimental evaluation was conducted on real protein graph datasets for classication.

They showed that ant-motifs outperform frequent subgraphs in classication.

Besides, ant-motifs are based on biological basis and their number is significantly smaller than that of frequent subgraphs. Although theoretically the approach can be used with traceable graphs (having Hamiltonian paths), it still currently limited to protein graphs and no other application contexts have been tested so far.

Discussion

As there exists currently many subgraph selection approaches, it is dicult and even unfair to compare them in general since the majority of the approaches were originally designed to solve a particular issue. Hence, the choice of an appropriate selection method highly depends on the users' needs and the application constraints. In order to help assisting such choice, in Table 3.1, we list all the subgraph selection approaches that have been investigated in this chapter and we state their characteristics according to a set of descriptors.

Frequent subgraph discovery is one of the most important mining techniques in graph mining. Because of the high number of frequent subgraphs, many subgraph selection approaches have been proposed in the literature. In general, they attempt to resolve the dimentionality problem by assessing the redundancy or the relevance of subgraphs through similarity or interestingness measures. In this chapter, we rst presented the context and formalization of frequent subgraph discovery and the main approaches and techniques proposed in the literature. We also presented the general framework for feature selection and the complexity of adopting the old techniques for frequent subgraphs. We further investigated a panoply of the most interesting subgraph selection approaches proposed in the literature. In the next two chapters, we propose and discuss two novel selection approaches for subgraph patterns namely UnSubPatt and TRS.

Aims

In the previous two chapters, we investigated methods for transforming protein structures into protein graphs enabling using graph mining techniques to study them. We also mentioned that mining frequent subgraphs is one of the best ways to analyze graph data, yet, it suers from the curse of dimentionality. We showed how to overcome this issue through feature selection, and we reviewed methods from the literature for subgraph seclection. In existing subgraph selection approaches, the prior information and knowledge about the application domain are often ignored. However, the latter provide valuable knowledge that may help building dedicated approaches that best t the studied data. In our context, the existence of substitution matrices for the amino acids composing protein structures, represents a valuable domain knowledge that can be exploited. In this chapter, we propose a novel feature selection approach for subgraphs. It selects a subset of so-called representative unsubstituted subgraphs from the frequent ones by incorporating a specic domain knowledge which, in our context, consists of the protein substitution matrices.

Introduction

Studying protein structures can reveal relevant structural and functional information which may not be derived from protein sequences alone. During recent years, various methods that study protein structures have been elaborated based on diverse types of descriptors such as proles [von Öhsen 2004],

spatial motifs [Kleywegt 1999[START_REF] Sun | Smolign: A Spatial Motifs-Based Protein Multiple Structural Alignment Method[END_REF]] and others [START_REF] Mavridis | [END_REF]]. Besides, the exponential growth of online databases such as the Protein Data Bank (PDB) [Berman 2000], CATH [Cu 2011], SCOP [START_REF] Andreeva | [END_REF]] and others, arises an urgent need for more accurate methods that will help to better understand the studied phenomenons such as protein evolution, functions, etc.

In this scope, proteins have recently been interpreted as graphs of amino acids and studied based on graph theory concepts [Vishveshwara 2002, Huan 2004a]. This representation enables the use of graph mining techniques to study protein structures in a graph perspective. In fact, in graph mining, any problem or object under consideration is represented in the form of nodes and edges and studied based on graph theory concepts [START_REF] Bartoli | [END_REF][START_REF] Hasan | [END_REF], Jin 2009[START_REF] Cheng | [END_REF]. As mentionned in the previous chapter, one of the powerful and current trends in graph mining is frequent subgraph discovery. It aims to discover subgraphs that frequently occur in a graph dataset and use them as patterns to describe the data. These patterns are lately analyzed by domain experts to reveal interesting informa-tion hidden in the original graphs, such as discovering pathways in metabolic networks [START_REF] Faust | [END_REF]], identifying residues that play the role of hubs in the protein and stabilize its structure [START_REF] Vallabhajosyula | [END_REF]], etc.

The graph isomorphism test is one of the main bottlenecks of frequent subgraph mining. Yet, many algorithms have been proposed in the literature and made it feasible for instance FFSM [Huan 2003], gSpan [START_REF][END_REF]],

GASTON [START_REF] Nijssen | [END_REF]], etc. Unfortunately, the exponential number of discovered frequent subgraphs is another serious issue that still needs more attention, since it may hinder or even make any further analysis unfeasible due to time, resources, and computational limitations. This problem becomes even more serious with graphs of higher density such as those representing protein structures. In fact, the issues raised from the huge number of frequent subgraphs are mainly due to two factors, namely redundancy and signicance [Thoma 2010]. Redundancy in a frequent subgraph set is caused by structural and/or semantic similarity, since most discovered subgraphs dier slightly in structure and may infer similar or even the same meaning. Moreover, the signicance of the discovered frequent subgraphs is only related to frequency.

This yields an urgent need for ecient approaches allowing to select relevant patterns among the large set of frequent subgraphs.

In this chapter, we propose a novel selection approach which selects a subset of representative patterns from a set of labeled subgraphs, we term them unsubstituted patterns. In order to select these unsubstituted patterns and to shrink the large size of the initial set of frequent subgraphs, we exploit a specic domain knowledge, which is the substitution between amino acids represented as nodes. The main contribution of this work is to dene a new approach for mining a representative summary of the set of frequent subgraphs by considering the ability of substitution between nodes' labels of the graph which is dened in the domain knowledge. In this work, we apply the proposed approach on protein structures because of the availability of substitution matrices in the literature. However, it can be considered as general framework for other applications whenever it is possible to dene a matrix quantifying the possible substitutions between the labels. For instance, in graphs representing protein-protein interaction networks, each node of the graph represent a protein in the network and these proteins share structural and sequential similarities. Since it is possible to measure such similarity using for instance an alignment tool, then it would be possible to dene a matrix quantifying similarities between the labels. Another possible application example is ontology alignment. Ontology alignment refer to the process of determining correspondences between concepts. Each ontology can be represented in the form of a graph were the nodes represent the concepts. Since the concepts are semantically similar, it is possible to dene a matrix quantifying these simi-Chapter 4. UnSubPatt: Mining representative unsubstituted graph patterns by means of substitution matrices larities and thus to adapt our approach to be used for detecting similarities between ontologies. Our approach can also be used on any type of subgraph structure such as cliques, trees and paths (sequences). In addition, it can be easily coupled with other pattern selection methods such as discrimination or orthogonality based approaches. Moreover, unlike other approaches that are supervised and learning task dependent, this approach is unsupervised and can help in various mining tasks.

Recently, several approaches have been proposed for pattern selection in subgraph mining.

To the best of our knowledge, in all existing subgraph selection approaches, the selection is usually based on structural similarity [START_REF] Hasan | [END_REF]] and/or statistical measures (e.g. frequency and coverage (closed [START_REF][END_REF]], maximal [Thomas 2006]), discrimination [Thoma 2010], etc). Yet, the prior information and knowledge about the application domain are often ignored. However, these prior knowledge may help building dedicated approaches that best t the studied data.

A very fresh work have been proposed in [Anchuri 2013], where the authors presented an approach for mining an approximate set of frequent subgraph patterns from a single large graph database in the presence of a cost matrix label. This approach is very similar to the one we propose in this chapter, in the sense that both approaches aim to nd representative subgraphs, and incorporate a matrix that denes distances ( i.e., similarities) between the labels. In addition, both approaches preserve the topology of subgraphs but allow bounded label mismatches. However, they have many dierences. First of all, their approach is used in the context of mining representative subgraphs from a single large graph, however our approach is used with graph databases.

In addition, both approaches dier in the way of exploiting the label matrix,

i.e., in the way they measure similarities between subgraphs. Moreover, their approach is based on sampling and thus it generates an approximate set of representative subgraphs, but our approach ensures generating the optimal set of representatives.

A major advantage of their approach is that it is incorporated in the extraction process of frequent representative subgraphs, while our approach operates in post-processing. Although this makes their approach more appropriate to very large graphs, our approach is more ecient in the case of moderate and small graph databases. Here, we present the preliminaries and the formal statement of the proposed approach. Let G be a dataset of protein structures represented as graphs.

Each graph G = (V, E, Σ, L) of G is given as a collection of nodes (amino acids) V and edges (interactions) E. The nodes of V are labeled within an alphabet Σ (amino acids types) and L is the label function that maps each node in V to a label in Σ. We denote by |V | the number of nodes (the graph order) and by |E| the number of edges (the graph size). Let also Ω be the set of frequent subgraphs extracted from G, also referred here as patterns.

Denition 12 (Substitution matrix) Let A be a substitution matrix dened over Σ. A is dened as follows:

A : Σ 2 -→ [⊥, ] ⊂ R (l, l ) -→ x (4.1)
where l, l ∈ Σ and x is the substitution score between the labels l and l .

The higher the value of x is, the more likely is the substitution of l by l. If x = ⊥ then the substitution is impossible, and if x = then it is certain, i.e., the substitution should happen. The values ⊥ and are optional and user-specied. They may appear or not in A. Table 2.2 shows a real example of a protein substitution matrix dened over the amino acids types.

In proteins' substitution matrices, both positive and negative values represent possible substitutions. However, positive scores are given to the more likely substitutions while negative scores are given to the less likely ones. In order to give more magnitude to higher values of x, we dene M over Σ such that ∀ l, l ∈ Σ: M(l, l ) = e A(l,l ) . As we consider only substitutions between patterns having the same structure, we dene the structural isomorphism as follow:

Denition 13 (Structural isomorphism) Two patterns P = (V P , E P , Σ, L) and P = (V P , E P , Σ, L) are said to be structurally isomorphic (having the same shape), we note shape(P, P ) = true, i:

-P and P have the same order and size, i.e.,

|V P | = |V P | and |E P | = |E P |, -∃ a bijective function f : V P → V P : ∀u, v ∈ V P , if {u, v} ∈ E P then {f (u), f(v)} ∈ E P and inversely.

graph patterns by means of substitution matrices

It is worth mentioning that in this denition, we consider only the isomorphism on structure and we ignore the labels.

As we are seeking the most representative patterns based on the substitution of amino acids, the best representatives are supposed to be the ones that represent as much other patterns as possible. Thus, each representative should have the highest probability of mutation to all the patterns it substitutes, i.e. the most mutable one. It is also possible to choose the least mutable pattern over the most mutable one, however, a good representative pattern is supposed to be the one having the maximal overall similarity to all the other patterns it represents. Patterns with higher ability of mutation are supposed to substitute more other patterns which allows a better summarization of the pattern set. Based on these assumptions, we are considering the most mutable patterns as the representatives. We dene the pattern mutation score as follows:

Denition 14 (Pattern mutation score) Given a pattern P = (V P , E P , Σ, L) ∈ Ω, the pattern mutation score M patt (P ), measures the possibility that P mutates to any other pattern having the same order.

M patt (P ) = 1 -

|V P | i=1 M el (V P [i]) (4.2)
where

|V P | i=1 M el (V P [i]
) represents the score that the pattern P does not mutate to any other pattern (i.e. P stays itself ), and M el (V P [i]) represents the elementary conservation score for each node V P [i] ∈ V P . Precisely, given a node v having a label (amino acid type) l ∈ Σ, M el (v) measures the possibility that v does not mutate to any other node depending on its label l:

M el (v) = M(l, l) |Σ| i=1 M(l, l i ) (4.3)
The lower the values of elementary conservation of nodes are, the more is the mutation ability of the pattern.

Based on the pattern mutation score, we are able to rank patterns and thus to chose between each substitutable pair of patterns which one is supposed to be the representative. We dene the pattern substitution score which measures the possibility that a pattern substitutes another one.

Denition 15 (Pattern substitution score) Given two structurally isomorphic patterns P and P , we denote by S patt (P, P ) the substitution score of P by P . It measures the possibility that P mutates to P . Formally:

S patt (P, P ) =

|V P | i=1 S el (V P [i], V P [i]) | V P | (4.4)

Mining representative unsubstituted patterns 69

S el (V P [i], V P [i]) measures the possibility that the node V P [i] substitutes the node V P [i] based on the substitution scores between their amino acids types. Obviously and according to all proteins' substitution matrices, for any amino acid l there is only another one that best substitutes it. It is obviously itself. Accordingly, given two nodes v and v having correspondingly the labels l, l ∈ L, the elementary substitution score between v and v , denoted by S el (v, v ), is computed as follows:

S el (v, v ) = M(l, l ) M(l, l) (4.5)
Denition 16 (Pattern substitution) Based on denitions 13 and 15, we say that a pattern P substitutes P , we note subst(P, P , τ) = true, i:

1. P and P are structurally isomorphic (i.e., shape(P, P ) = true),

2. The score of substitution of P by P is greater then a given user-threshold τ (i.e., S patt (P, P ) ≥ τ ), where 0% ≤ τ ≤ 100%.

Since we are proposing a pattern selection approach, the output set of representative patterns should be as small as possible. It is not supposed to have any pair of substitutable patterns such that it contains only the representative ones which guarantees a maximal summarization.

Denition 17 (Unsubstituted pattern) Ω * ⊂ Ω represents the subset of rep- resentative unsubstituted patterns if and only if there does not exist any pair of patterns (P 1 , P 2 ) in Ω * that are substitutable, with respect to the minimum substitution threshold τ .

A pattern P * is considered as representative unsubstituted pattern, i.e., P * in Ω * , if there does not exists any pattern P in Ω * such that M patt (P ) is greater than M patt (P * ) and P substitutes P * . P * ∈ Ω * , if P ∈ Ω * | M patt (P ) > M patt (P * ) and subst(P, P * , τ) = true (4.6) Denition 18 (Joint support) Given two patterns P and P , if P substitutes P then P should represent P in the graphs where P occurs. In Ω * , the occurrence list of P will contain both the occurrences of P as well as those of P (the occurrence lists are joined). Formally: ∀P, P ∈ Ω, if subst(P, P , τ) = true then D P = D P ∪ D P (4.7) where D P and D P are correspondingly the occurrence list of P and that of P .

Algorithm

Given a set of patterns Ω and a substitution matrix M, we propose UnSub-Patt (see Algorithm 1), a pattern selection algorithm which enables detecting the set of unsubstituted patterns Ω * within Ω. Based on our similarity concept, all the patterns in Ω * are dissimilar, since it does not contain any pair of patterns that are substitutable. The general process of the algorithm is

Algorithm 1: UnSubPatt Data: Ω, M, τ Result: Ω * : {unsubstituted patterns} 1 begin 2 divide Ω into k subsets | ∀P , P " ∈ Ω k , |V P | = |V P " | and |E P | = |E P " |; 3 foreach Ω k ⊂ Ω do 4 Ω k ← sort(Ω k by M patt ); 5 foreach P ∈ Ω k do 6 if M patt (P ) > 0 then 7 foreach P ∈ Ω k \{P } | M patt (P ) < M patt (P ) do 8 if M patt (P ) >
Ω * ← Ω * ∪ Ω k ;
described as follows: rst, Ω is divided into subsets of patterns having the same number of nodes and edges. In order to preserve the most mutable patterns, each subset is sorted in a descending order by the pattern mutation score M patt . Then, each subset is browsed starting from the pattern having the highest M patt . For each pattern, we look for all the other patterns it is able to substitute, with respect to the substitution threshold. The test of substitution is performed iteratively for every possible mapping between pairs of patterns until a substitution is found. If a substitution is found with a particular mapping then there is no need to proceed testing the substitution with the rest of the mappings since we are not looking for the best substitution but we are only looking for a possible one, with respect to the given threshold. For each pattern, we remove all the patterns it substitutes and we add their supports' lists to that of the preserved pattern such that the latter will represent all the patterns it substitutes wherever they occur. The remaining patterns represent the representative unsubstituted pattern set.

Property 2 Let Ω be a set of patterns and Ω * its subset of unsubstituted patterns based on a substitution matrix M and a threshold τ , i.e., UnSubPatt (Ω, M, τ) = Ω * . Ω * can not be summarized by one of its proper subsets but only by itself, with respect to τ . Formally:

UnSubPatt(Ω * , M, τ) = Ω * (4.8)
Proof 1 Lets suppose that :

hypothesis 1:

Ω * \ UnSubPatt(Ω * , M, τ) = ∅ -hypothesis 2: UnSubPatt(Ω * , M, τ) \ Ω * = ∅
Hypothesis 1 supposes that Ω * still contains substitutable patterns. This is impossible, since according to Denition 17, there does not exist any pair of patterns in Ω * that are substitutable. Given a threshold τ , Ω * cannot be summarized by one of its proper subsets but only by itself. Formally: ∀P ∈ Ω * , P ∈ Ω * |M patt (P ) > M patt (P ) and subst (P, P , τ) As for hypothesis 2 to be true, UnSubPatt is supposed to generate new patterns that were not originally in Ω * . This contradicts UnSubPatt basics especially Denition 17 since UnSubPatt is supposed to remove substituted patterns, not to generate new ones.

The minimum description length (MDL) principle [START_REF] Rissanen | Modeling by shortest data description[END_REF], Grünwald 2007] suggests that given a set of observed data, the best explanation is the one that permits the greatest compression of the data. According to the MDL, Ω * represents a reliable summarization of Ω.

Complexity Suppose

Ω contains n patterns. Ω is divided into g groups, each containing patterns of order k. This is done in O(n). Each group Ω k is sorted in O(|Ω k | * log|Ω k |).
Searching for unsubstituted patterns requires browsing Ω k (O(|Ω k |)) and for each pattern, browsing in the worst case all remaining patterns (O(|Ω k |)) to check the shape O(k) and the substitution O(k). This means that searching for unsubstituted patterns in a group Ω k can be done in O(|Ω k | 2 * k 2 ). Hence, in the worst case, the complexity of our

algorithm is O(g * m 2 max * k 2 max ),
where k max is the maximum pattern order and m max is the number of patterns of the largest group Ω k .

• x ∈ Blosum62, x ← e x • M el (A) = M(A,A) 20 i=1 M(A,l i ) 0.840 M el (C) = M(C,C) 20 i=1 M(C,l i ) 0.999 M el (T ) = M(T,T ) 20 i=1 M(T,l i ) 0.936 M el (S) = M(S,S) 20 i=1 M(S,l i ) 0.776 • M patt (G1) = 1 -(M el (A) * M el (C) * M el (T )) 1 -(0.840 * 0.999 * 0.936) 1 -0.786 0.214 M patt (G2) = 1 -(M el (A) * M el (C) * M el (S)) 1 -(0.840 * 0.999 * 0.776) 1 -0.652 0.348 M patt (G1) < M patt (G2) • shape(G1, G2) = true G1 G2 τ 68.32%

Experiments 73

In UnSubPatt, we compute the substitution score for every possible mapping between G1 and G2, until a substitution score with a value greater or equal to the given substitution threshold is found or no other mapping is possible. Here, we only show, as an example, how the substitution score is computed for only one mapping between G1 and G2 among the possible ones. The considered mapping for this example is: A ↔ A, C ↔ C, S ↔ T .

• Pattern substitution score:

-S patt (G2, G1) = ( M(A,A) M(A,A) + M(C,C) M(C,C) + M(S,T ) M(S,S) ) |G2|
0.6832 -Thus, G2 substitutes G1 for all substitution thresholds 0% ≤ τ ≤ 68.32%

If the user-specied substitution threshold is greater than 68.32% (i.e., ∀τ ≥ 68.32%) then UnSubPatt proceed checking the other possible mappings. Otherwise (i.e., ∀τ ≤ 68.32%), G2 substitutes G1. In this case, supports of G2 and G1 are joined then G1 is removed:

• Joining support: D G2 = D G2 ∪ D G1 (D Gi is the occurrence list of Gi) • Remove G1
4.4 Experiments

Datasets

In order to experimentally evaluate our approach, we use four datasets of protein 3D-structures, which also have been used in [START_REF][END_REF]] and [START_REF] Fei | Boosting with structure information in the functional space: an application to graph classication[END_REF]].

Each dataset consists of two classes equally divided into positive and negative samples. Positive samples are proteins selected from a considered protein family whereas negative samples are proteins randomly gathered from the Protein Data Bank [Berman 2000]. Table 4.1 summarizes the characteristics of each dataset:

-SCOP ID: identier of the protein family in SCOP [START_REF] Andreeva | [END_REF]] Proteins are parsed into graphs of amino acids using the main atom method (see section 2.3.4.2). Each node represents an amino acid residue and is labeled with its amino acid type. Two nodes u and v are linked by an edge e(u, v) = 1 if the euclidean distance between their two C α atoms Δ(C α (u), C α (v)) is below a threshold distance δ. In the literature, many methods use this denition with usually δ ≥ 7Å on the argument that C α atoms dene the overall shape of the protein conformation [START_REF] Huan | [END_REF]]. In our experiments, we use δ = 7Å.

Protocol and settings

Generally, in a pattern selection approach two aspects are emphasized, namely the number of selected patterns and their interestingness. In order to evaluate our approach, we rst use the state-of-the-art method of frequent subgraph discovery gSpan [START_REF][END_REF]] to nd the frequent subgraphs in each dataset with a minimum frequency threshold of 30%. Then, we use UnSubPatt to select the unsubstituted patterns among them with a minimum substitution threshold τ =30% and Blosum62 (see Table 2.2) as the substitution matrix. We use Blosum62 because it turned out that it performs well on detecting the majority of weak protein similarities [Eddy 2004], and it is used as the default matrix by most biological applications such as BLAST [START_REF] Altschul | [END_REF]]. It is worth mentioning that the choice of 30% as minimum frequency threshold for frequent subgraph extraction is to have fewer patterns in order to make the experimental evaluation feasible due to time and computational limitations.

In order to evaluate the number of selected subgraphs, we dene the selection rate as the rate of the number of unsubstituted subgraphs from the initial set of frequent subgraphs. Formally :

Selection rate = |Ω * | * 100 |Ω| (4.9)
To evaluate the interestingness of the selected patterns, we use them as features for classication. We perform a 5-fold cross-validation classication (5 runs) on each protein dataset. We encode each protein into a binary vector, denoting by "1" or "0" the presence or the absence of the feature in the considered protein. For classication, we use classiers from the workbench Weka [Witten 2005].

Results and discussion

In this section, we conduct experiments to examine the eectiveness and eciency of UnSubPatt in nding the representative unsubstituted subgraphs. Moreover, we test the eect of changing the substitution matrix and the substitution threshold on the results. We further study the size-based distribution of patterns and we compare the classication results of our approach with those of other subgraph selection methods from the literature.

Empirical results

We show the results of our experiments in terms of number of patterns and classication results. The obtained average results are reported in the Tables 4.2 and 4.3. The high number of discovered frequent subgraphs is due to their combinatorial nature. It may increase or decrease depending on the number of graphs, their density and mainly on the similarity between graphs since the more similar they are, the more common fragments they would have. The results reported in Table 4.2 show that our approach decreases considerably the number of subgraphs. The selection rate shows that the number of unsubstituted patterns | Ω * | does not exceed 13% of the initial set of frequent subgraphs | Ω | in the worst case with DS3 and even reaches less than 1% with DS1 and DS4. This proves that exploiting the domain knowledge by incorporating, in our case, the substitution matrix in the selection enables detecting many similarities between patterns that are possibly ignored by current subgraph selection approaches.

The classication results using naive bayes (NB) is reported in Table 4.3. They help evaluating the quality of the selected patterns. Indeed, they will demonstrate if the unsubstituted patterns are really representative or arbitrarily selected. Table 4.3 shows that the classication accuracy signicantly increases with all datasets. We notice a huge leap in accuracy especially with DS1 and DS4 with a gain of more than 17% and reaching almost full accuracy with DS4. To better understand the accuracy results, we report the average precision, recall, F-measure and AUC values for all cases. We also notice an enhancement of performance with all the mentioned quality metrics. This Table 4.3: Accuracy, precision, recall (sensitivity), F-score and AUC of the classication of each dataset using NB coupled with frequent subgraphs (FSg) then representative unsubstituted subgraphs (USP)

Dataset

Accuracy Precision Recall F-score AUC FSg USP FSg USP FSg USP FSg USP FSg USP DS1 0.62 0.78 0.61 0.69 0.70 0.90 0.64 0.78 0.64 0.78 DS2 0.80 0.90 0.86 0.94 0.74 0.86 0.79 0.89 0.79 0.89 DS3 0.86 0.94 0.89 1.00 0.86 0.89 0.86 0.94 0.86 0.94 DS4 0.79 0.98 0.86 0.92 0.70 0.98 0.76 0.94 0.76 0.94 supports the reliability of our selection.

Results using other substitution matrices

Besides Blosum62, biologists also dened other substitution matrices describing the likelihood that two amino acid types would mutate to each other in evolutionary time. We want to study the eect of using other substitution matrices on the experimental results. Hence, we perform the same experiments following the same protocol and settings but using two other substitution matrices, namely Blosum80 and P am250. The results are reported in Table 4.4. We compare the obtained results in terms of number of subgraphs and classication accuracy with those obtained using the whole set of frequent subgraphs and those using subgraphs previously selected by UnSubPatt with Blosum62. A high selection rate accompanied with a clear enhancement of the classication accuracy is noticed using UnSubPatt with all the substitution matrices. It is clearly noticed that even using dierent substitution matrices, UnSubPatt is able to select a small yet relevant subset of patterns. It is also worth mentioning that for all the datasets, the best classication accuracy is obtained using Blosum62 and the best selection rate is achieved using Pam250. This is simply due to how distant proteins within the same dataset are, since each substitution matrix was constructed to implicitly express a particular theory of evolution.

Impact of varying the substitution threshold

In our experiments, we used a substitution threshold (of 30%) to select the unsubstituted patterns from the set of discovered frequent subgraphs. Here, we study the impact of varying the substitution threshold on both the number of selected subgraphs and the classication results. We perform the same experiments following the same protocol and settings while varying the substitution threshold from 0% to 90% with a step-size of 10. Figure 4.4 presents the selection rate for all substitution thresholds. In order to check if the enhancements of results are due to our selected patterns or to the classier, we perform the same experiments using naive bayes (NB) (Figure 4.5) and two other well-known classiers namely the support vector machine (SVM) (Figure 4.6) and decision tree (C4.5) (Figure 4.7). The classication accuracy of the initial set of frequent subgraphs (gSpan) is considered as a standard value for comparison. Thus, the accuracy values of UnSubPatt that are above the line of the standard value are considered as gains, and those under the standard value are considered as losses.

In Figure 4.4, we notice that UnSubPatt reduces considerably the number of patterns especially with lower substitution thresholds. In fact, the number of representative unsubstituted patterns does not exceed 50% for all substitution thresholds below 80% and even reaches less than 1% in some cases. This important reduction in the number of patterns comes with a notable enhancement of the classication accuracies over all datasets. Figures 4.5,4.6 and 4.7 show that the unsubstituted patterns allow better classication performance compared to the original set of frequent subgraphs.

UnSubPatt scores very well with the three used classiers and even reaches full accuracy in some cases. Overall, the same behavior is noticed with the three datasets. A cross view over the gures is possible, showing that there is no bias of the datasets nor of the classier. This conrms our assumptions and shows that our selection is reliable and contributes to the enhancement of the accuracy. UnSubPatt can be easily parallelized, since it tests separately the substitution among each group of subgraphs having the same size and order. Hence, these groups can be distributed and treated separately in dierent processes.

Ω * Ω τ τ = 30% max t p = 30% t n = 0% max var = 1 δ = 0.25 max O(g * m 2 max * k 2 max ) g k max m max Ω k O(g * (m max * log(m max ) * (k max * log(k max ))

Conclusion

In this chapter, we proposed a novel selection approach for mining a representative subset of patterns from a set of frequent subgraphs. Unlike current methods that are based on the relations between patterns in the transaction space, our approach considers the distance between patterns in the pattern space. Experimental results revealed the importance of incorporating the prior domain knowledge and showed that using the information of substitution between amino acids allowed UnSubPatt to detect many similarities between patterns that current subgraph selection approaches ignore. UnSubPatt is able to considerably reduce the number of subgraphs by selecting a more representative and informative subset enabling easier and more ecient further explorations. UnSubPatt can also be used on protein sequences (seen as line graphs) and it is unsupervised which allows it to be used in dierent mining tasks and in other motif-based analysis.

It is also worth mentioning that UnSubPatt is not limited to protein 3Dstructures but can be generalized to other types of data whenever it is possible to dene a matrix representing the similarity between the nodes labels.

A promising future direction is to consider also the insertions and deletions over patterns with dierent sizes. Although this increases exponentially the complexity and the diculty of the selection, it is closer to the real world substitution phenomenon. Another interesting future work could be to embed the selection within the extraction process in order to directly mine the representative patterns from data. This is further discussed in Section 6. 4.1.2. This chapter was the subject of a number of publications, namely a poster paper in ACM BCB [Dhii 2012b], a conference paper at JOBIM [Dhii 2013c] and a journal paper in JCB [Dhii 2013b]. It was also the subject of two oral presentations given at MLCB [Dhii 2012a] and JFD [Dhii 2013a].

Chapter 5 TRS : Towards an ecient discovery of topological representative subgraphs Contents Chapter 5. TRS : Towards an ecient discovery of topological representative subgraphs labels that is dened in the substitution matrix. In this chapter, we introduce another subgraph selection approach that focuses on the structural similarity rather than the semantic similarity. Unlike existing structural-based selection approaches that look into every single detail, this approach considers the overall topological similarity between subgraphs by means of a set of topological descriptors. This makes it easily extendable with a user-specied set of descriptors depending on the application and the sought information.

Introduction

Feature selection for graph data is a way to tackle the information overload problem caused by the high number of frequent subgraphs. As structural similarity represents one major cause of redundancy in frequent subgraphs, many works have been proposed for subgraph selection based on exact or approximate structural similarity [START_REF][END_REF], Thomas 2006[START_REF] Hasan | [END_REF], Chen 2008].

Two pioneer works that fall in this type are [START_REF][END_REF]] for mining closed subgraphs and [Thomas 2006] for mining maximal subgraphs. In both works, only the closed or maximal subgraphs are maintained and the rest of frequent subgraphs are removed. Many works have been proposed based on closed and maximal subgraphs such as [START_REF] Takigawa | Ichigaku Takigawa and Hiroshi Mamitsuka. Eciently mining δ-tolerance closed frequent subgraphs[END_REF][START_REF] Li | [END_REF]. Although the set of closed or maximal subgraphs is much smaller than the set of frequent ones, the number of subgraphs is still very high in real-world cases.

Many works have been proposed for subgraph selection based on approximate structural similarity. In [START_REF] Hasan | [END_REF]], authors proposed an approach for subgraphs extraction and selection. For selection, the structural similarity between two subgraphs is measured by how much does their maximum common subgraph [START_REF] Abu-Khzam | The Maximum Common Subgraph Problem: Faster Solutions via Vertex Cover[END_REF] represents from their overall structure.

A very close work is [Chen 2008], where authors proposed an approach for mining a set of structural representative subgraphs among the frequent ones.

They adopted a two-step approach that is based on approximate structural similarity on micro and macro sides. In the rst step, they consider a tolerance threshold to summarize approximately isomorphic subgraphs into one representative. In the second step, they collapse multiple structurally similar subgraphs into one representative using a clustering algorithm.

Existing selections approaches that are based on exact or approximate structural similarity, look into every single detail and test the structural similarity of subgraphs by establishing a matching between them. This similarity detection strategy is not ecient in many real-world applications. On one hand, because the combinatorial nature of graphs makes computing every possible matching between pairs of subgraphs very costly. On the other hand, exact and even approximate structural similarity are not ecient enough to detect all similar subgraphs in real-world data. Indeed, exact structural similarity does not allow detecting similar yet slightly dierent subgraphs, and approximate structural similarity has the problem of threshold setting. Since a tight threshold will prevent detecting many similar subgraphs that slightly dier in structure beyond the tolerance threshold and thus preserve a high number of subgraphs. In contrast, a loose threshold will hinder the soundness of the selection because of false positives. This rises the need for a dierent way to consider the structural similarity such that both close and distant structural similarities would be detected with respect to the soundness of results.

Considering topological properties instead of exact or approximate structural isomorphism was inspired by works like [START_REF] Rodenacker | Quantication of tissue sections: Graph theory and topology as modelling tools[END_REF], Leskovec 2005[START_REF] Veeramalai | A novel method for comparing topological models of protein structures enhanced with ligand information[END_REF][START_REF] Li | [END_REF][START_REF] Ranu | [END_REF][START_REF] Tong | [END_REF], Gibert 2012] where authors showed the importance and eciency of topological attributes in describing graph data. For instance, in [START_REF] Li | [END_REF]], authors proposed a classication framework based on the assumption that graphs belonging to the same class have similar topological descriptions. Our approach is based on similar assumption and consider that structurally similar subgraphs should have similar topological properties such that even a slight dierence does not aect the overall topological similarity. Besides, depending on the application context, a user may be interested only in some specic structural properties. However, considering exact or approximate structural similarity approaches does not allow this specicity.

In order to overcome these drawbacks and to select a small yet structurally non-redundant set of subgraphs, we propose a novel approach that mines the top-k topological representative subgraphs among the frequent ones. At a glance, our approach involves two steps. In the rst step, each subgraph is encoded into a topological description-vector containing the corresponding values for a set of topological attributes. In the second step, subgraphs with similar topological descriptions are clustered together and the central subgraph in each cluster is considered as the representative delegate. Our approach overcomes the costly isomorphism needed to perform the exact or approximate structural similarity and allows detecting hidden similarities like spectral radius or closeness centrality, that exact or approximate structural similarity approaches are unable to detect. Besides, our approach can be easily extended by enabling the user to target a specic set of topological attributes depending on how important each one is to the application. Even though the existing approaches for subgraph selection greatly enhanced the selection process, the number of selected subgraphs is still high. Yet, we want to show as few subgraphs as possible so that the user's reviewing eorts are minimized. The general framework of our selection strategy is as follows. Given a set of frequent subgraphs Ω and an integer k ∈ [1.

.|Ω|],

we want to select up to k representative subgraphs Ω k ⊆ Ω such that each frequent subgraph g ∈ Ω has one representative subgraph-delegate g ∈ Ω k , and each representative subgraph is the closest one to all the subgraphs it represents. To do so, the set of frequent subgraphs is divided into k clusters using a clustering algorithm, then the cluster centroids are selected to be the representative subgraph-delegates such that each centroid is representative for all subgraphs within the same cluster.

Naïve approach

As we are attempting to select top-k representative subgraphs based on clustering, a fundamental part in our selection framework is the graph encoding which consists in the transformation of each subgraph into a dierent format that is accepted by the clustering algorithm. A naïve solution is to transform the input subgraphs into a context-matrix where each subgraph is represented by a binary vector denoting by 1 or 0 the presence or the absence of the subgraph in each graph in the database. After that, the context-matrix is considered as input for clustering (see Algorithm 2).

Algorithm 2: Naïve approach Data: Frequent subgraphs Ω, number of representatives k Result: Representative subgraphs

Ω * = {g 1 , g 2 , ..., g k } 1 begin 2 M ← ∪ |Ω| i=1 V i : each subgraph g i ∈ Ω
is encoded into a binary vector V i denoting by 1 or 0 correspondingly the presence or the absence of the subgraph in each graph in the database; 3 Ω * ←Clustering(M, k);

Topological representative subgraph selection

The main idea of our approach is based on the assumption that structurally similar subgraphs should have similar topological properties such that even a slight dierence in the structure does not aect the overall similarity [Ingram 2006, Knabe 2008[START_REF] Li | [END_REF]]. Accordingly, we adopt a two-step selection framework, where in the rst step we encode each subgraph into a topological description-vector containing the corresponding values for a set of topological attributes. In the second step, we perform a clustering using the topological description-vectors in order to select one representative subgraph delegate from each set of topologically similar subgraphs.

Topological attributes

In the rst step of our approach each subgraph is encoded into a topological description-vector. We select a set of topological attributes from the literature [START_REF] Li | [END_REF], Leskovec 2005] that are interesting and ecient in describing connected graphs. In the following, we list and dene the selected attributes:

1. where k u is the number of neighbors of u and e u is the number of connected pairs of neighbors. If all the neighbor nodes of u are connected, then the neighborhood of u is complete and we have a clustering coecient of 1. If no nodes in the neighborhood of u are connected, then the clustering coecient is 0. The average clustering coecient of an entire graph G having n nodes, is given as the average value over all the nodes in G. Formally: 16. Neighborhood impurity: The impurity degree of a node u belonging to a graph G, having a label L(u) and a neighborhood (adjacent nodes) N (u), is dened as

C(G) = 1 n n i=1 c(u i ).
ImpurityDeg(u) =| L(v) : v ∈ N (u), L(u) = L(v) |.
The neighborhood impurity of a graph G represents the average impurity degree over all nodes with positive impurity. 17. Link impurity: An edge {u, v} is considered to be impure if L(u) = L(v). The link impurity of a graph G with k edges is dened as: As eciency and scalability remain big challenges for graph mining algorithms, the proposed description is unied which helps to overcome both challenges. On one hand, these attributes present an ecient description that is able to reveal hidden topological similarities that exact and approximate structural isomorphism do not consider. On the other hand, considering a xed number of descriptors guarantee that the encoded vectors would be of a xed size no matter what the number of graphs in the database is. This makes the approach scalable and computationally ecient in real-world applications. Oppositely, the context-vectors in the the naïve approach are as big as the number of graphs in the database which is usually very high in realworld applications. This can highly aect the scalablity and computational consumption of the naïve approach.

K-Medoids clustering

As previously mentioned, our approach follows a two-step selection framework. First, we discussed the rst part of the framework which consists of the description of the data whether by the context-vectors or by the topological description-vectors. Here, we discuss the second part of our selection approach which is the clustering step. We use k-Medoids [START_REF] Kaufman | Clustering by means of medoids[END_REF] which is a well known clustering algorithm that is widely used in unsupervised learning [START_REF] Jain | [END_REF]]. It takes as input a set of objects Ω and a number of clusters k, and gives as output the k clusters' centers (called medoids ). To do so, k-Medoids uses these denitions:

Denition 19 (Pairwise distance between objects) Given two objects O 1 and O 2 correspondingly described by the vectors X and Y , the distance between them, denoted d(O 1 , O 2 ), is dened as follows:

d(O 1 , O 2 ) = |X| i=1 |x i -y i |
Denition 20 (Global distance between objects) Given a set of objects Ω, the total distance between an object O and all the other ones in Ω is dened by:

D O = ∀O i ∈Ω\O d(O, O i )
Denition 21 (Cluster medoid) An object O * is said to be cluster's medoid (the most centrally located object of the cluster), if it has the minimum sum of distances to all the other objects O i within the cluster C. Formally:

D O * = minO i ∈ C(D O i )
Using real objects as the clusters' centers makes k-Medoids less sensitive to noise and outliers than many other clustering algorithms. Besides, in k-Medoids, medoids are real data objects. Each medoid represents the most similar object to all the other ones within the same cluster. Thus, medoids can be directly considered as the representative-delegates for all the objects in the same cluster.

The general algorithm of k-Medoids is described in Algorithm 3. First, it starts by randomly selecting k objects from Ω to be the medoids, i.e. Ω * . Then, it assigns each non-selected object to the cluster of the nearest medoid. After that, it swaps the k medoid objects with other non-medoid objects aiming to minimize the overall distance. D(Ω * ) is the total distance before the swap and D(Ω k ) is the total distance after the swap. If the cost of the swap (C = D(Ω k ) -D(Ω * )) is strictly negative then the swap is considered as benecial, otherwise it is ignored. The assignment and swap steps are iteratively performed until no change or until a user-dened maximum number of iteration is reached. Many implementations of k-Medoids have been proposed in the literature. PAM [START_REF] Kaufman | Clustering by means of medoids[END_REF]] is a pioneer implementation of k-Medoids. Later, two other implementations have been proposed which are CLARA [START_REF] Kaufman | [END_REF]] and CLARANS [Ng 1994[START_REF] Ng | [END_REF]]. The main difference between these implementations is in the way of performing the swap where in attempt to make the algorithm more scalable to larger amounts of data. In this work, we use CLARANS since it was shown [START_REF] Ng | [END_REF]] that it is an ecient implementation for large-scale data clustering and it gives similar clustering quality to PAM and CLARA. We propose TRS, an approach for selecting Topological Representative Subgraphs. The general algorithm of the approach is described in Algorithm 4. TRS follows a two steps framework. As previously mentioned, TRS assumes that structurally similar subgraphs have similar topological properties. Thus, in the rst step of the approach, each subgraph is encoded into a topological description-vector using the previously dened topological attributes. The second step uses the topological description-vectors to select the representative subgraphs. Each representative subgraph is supposed to have the maximal overall similarity to all the other subgraphs it represents. Hence, the topological description-vectors are considered for clustering using k-Medoids. The selected medoids are considered as the topological representative subgraph-delegates.

* = {g 1 , g 2 , ..., g k } 1 begin 2 M ← ∪ |Ω| i=1 V i : each subgraph g ∈ Ω is
encoded into a topological description vector V using the topological attributes; To experimentally evaluate our approach, we use dierent types of graph datasets: protein 3D-structures and chemical compounds. Table 5.1 summarizes the characteristics of the four datasets: dataset, |G|, Avg.|V | and Avg.|E| correspond respectively to the name of the corresponding protein family or chemical compound dataset, number of graph, average number of nodes, average number of edges in each dataset.

The rst two datasets were previously used in [START_REF] Fei | Boosting with structure information in the functional space: an application to graph classication[END_REF]] and [START_REF][END_REF]]. Both datasets will be used to evaluate the interestingness of the selected subgraphs. In fact, each dataset is composed of two groups of protein 3Dstructures equally divided between positive and negative samples. Positive The C1 set domains composing the second dataset are immunoglobulinlike domains, similar in structure and sequence. They resemble the antibody constant domains. They are mostly found in molecules involved in the immune system, in the major histocompatibility complex class I and II complex molecules, and in various T-cell receptors. The two other datasets are used to evaluate the runtime and the distribution of subgraphs according to their sizes. The dataset of Enzymes, previously used in [Dobson 2003] and [Thoma 2010], is composed of 664 proteins. Enzymes act as biological catalysts. They are large biological molecules responsible for the thousands of chemical interconversions that sustain life. The last dataset shows a set of antiviral screen data (AIDS). It contains the activity test information of 43850 chemical compounds. This dataset was previously used in many studies such as [Chen 2008] and is publicly available on the website of the Developmental Therapeutics Program.2

Protocol and settings

Graph building: For chemical compounds, each atom is represented by a node and labeled with the atom type (Hydrogen (H), Carbon (C), etc.). An edge exists between two nodes if there exists a chemical bond between their corresponding atoms. For protein 3D-structures, each protein is parsed into a graph of amino acids using the main atom (C α ) method (see section 2.3.4.2). In the literature, many methods use this method with usually δ ≥ 7Å on the argument that C α atoms dene the overall shape of the protein conformation [START_REF] Huan | [END_REF]]. In our experiments, we use δ = 7Å.

Frequent subgraph mining: We use the state-of-the-art method of frequent subgraph discovery gSpan [START_REF][END_REF]] to nd the frequent subgraphs in each dataset. We tried dierent minimum frequency threshold in order to obtain a reasonable number of frequent subgraphs from each dataset. The retained minimum frequency threshold are 30% for G-proteins and C1 set domains, 10% for Enzymes, and 5% for AIDS antiviral screen dataset. Table 5.2 shows the number of frequents subgraphs obtained from each dataset.

Representative subgraph selection: Both selection frameworks, i.e., the To measure the quality of subgraphs, each one of them is encoded into a binary vector by denoting 1 or 0, the presence or the absence of the subgraph in each graph in the dataset. The quality of the selected subgraphs is measured over their encoding vectors.

Results and discussion

Empirical results

As previously mentioned, we rst evaluate our approach over the classication datasets G-proteins and C1 set domains. We measure the quality of the selected subgraphs using the information gain which is one of the most popular interestingness measures in data mining. Given a set of training examples Ω and an attribute att. The information gain of att is computed using the following formulas:

Inf ormationGain(Ω, att) = Entropy(Ω) -Entropy(Ω|att)
where Entropy(Ω) is calculated as follows:

Entropy(Ω) = -Σ |Ω| i=1 p(x i )log p(x i ) 100
Chapter 5. TRS : Towards an ecient discovery of topological representative subgraphs where p(x i ) is the probability of getting the x i value when randomly selecting an example from the set. The information gain is measured over all the frequent subgraphs then over the subgraphs selected by TRS and those selected by the naïve approach using dierent number of representatives. The information gain value obtained over all the frequent subgraphs is considered as standard value for comparison. Table 5.3 shows the obtained results. Table 5.3 shows that TRS is able to select a subset of subgraphs that are more informative than either the initial frequent ones or those selected by the naïve approach. Whereas, the quality of the subsets of representative subgraphs selected by the naïve approach did not even reach the information gain value of the whole set of frequent subgraphs. Both previous interpretations goes with all the used numbers of representatives. This proves the reliability of our selection approach and shows that using the topological attributes for description is more ecient than using the occurrence information. It enables k-Medoids to better detects similarities between subgraphs and thus to select a subset of representative subgraphs that are most informative.

It is also worth mentioning that the topological attributes used in TRS are not limited to the ones mentioned in this chapter. They can be extended by removing or adding other attributes depending on the data and the application

Aims

In this chapter, we conclude the thesis by summarizing the proposed contributions and highlighting some ongoing works for both UnSubPatt and TRS. 110 Chapter 6. Conclusion and future works

Summary of contributions

In this thesis, we proposed two feature selection approaches for subgraphs.

Here, we recall both approaches as well as the main results and conclusions.

UnSubPatt

The rst approach we proposed is termed UnSubPatt. It aims to selecting a subset of representative subgraphs among frequent ones. The selected subgraphs are termed representative unsubstituted patterns. Unlike existing subgraph selection approaches where the prior domain knowledge is often ignored, UnSubPatt incorporates matrices that quantify the similarities between nodes labels. UnSubPatt uses similarity scores of the matrix to detect the overall similarity between pairs of subgraphs. Graphs representing protein structures are an immediate application example due to the availability of amino acids substitution matrices. However, UnSubPatt can be used in any other application context whenever it is possible to dene a matrix that quanties similarities between the nodes' labels. UnSubPatt is unsupervised, thus, it can be used in any subgraph-based task.

Experimental evaluation of UnSubPatt was performed by classifying a set of protein structure datasets. Results showed that UnSubPatt is able to select a small yet representative and informative subset of subgraphs among the frequent ones. Moreover, UnSubPatt outperformed many other subgraph selection approaches in classifying the considered protein structure datasets. It even reached full accuracy with one dataset. This shows that UnSubPatt is a very competitive and promising approach, and that using the substitution between amino acids allows it to select a very informative subset of subgraphs.

TRS

Similarity in UnSubPatt is purely semantic as the similarity between a pair of isomorphic subgraphs depends on how similar their labels are. We also introduced another subgraph selection approach, we term TRS (Topological Representative Subgraphs). Redundancy in UnSubPatt is based on semantic similarity, while redundancy in TRS is based on structural similarity. Existing subgraph selection approaches that are based on structural similarity are either exact or approximate. We discussed, in 5.2, how current exact and approximate structural similarity approaches are less ecient in many realworld applications. Unlike these approaches, TRS follows a more meaningful selection by considering the overall structural similarity between subgraphs through a set of topological descriptors. This makes it easily extendable with any user-specied descriptors depending on the application and the sought information.

Experimental evaluation of TRS was performed mainly on protein structure datasets but also on a chemical compound dataset. Results showed that TRS is able to select a set of topologically non-redundant and informative subgraph-delegates. In addition, it considers hidden topological similarities between subgraphs (density, diameter, clustering coecient, etc) that are ignored by current selection approaches. Moreover, TRS is extendable and unsupervised, thus it can be used in any subgraph-based task. It is also worth noting that the application domain of TRS is not limited to protein 3D-structures or to biological data but it can also be used with any graph data.

Discussion

We resume the discussion previously reported in 3.7. As previously discussed, many subgraph selection approaches are currently available. It is dicult to compare them, in general, since the majority of them were originally designed to resolve a particular issue. The choice of an appropriate selection method highly depends on the users preferences and the application constraints. In Table 6.1, we list all the subgraph selection approaches that have been investigated along Chapter 3 and we state their characteristics according to a set of descriptors. In addition to what was reported in Table 3.1, Table 6.1 lists our proposed approaches, UnSubPatt and TRS. It also contains an additional descriptor which indicates whether the selection approach considers the prior domain knowledge in the selection or not. It is possible to consider similarity functions and measures, that are dened by the user, as domain knowledge like in Redundancy aware top-k, SkyGraph, Mips or TRS. However, here we refer to prior domain knowledge as specic external data or information from the application domain that a method exploits during the selection, as in Un-SubPatt which uses the substitution matrices that are already dened by domain experts. 6.4. Ongoing works and prospects 113 6.4 Ongoing works and prospects Like any algorithm, the proposed selection approaches have their limitations. In the following, we discuss some of the major limitations and we propose possible extensions to enhance them. Even though UnSubPatt scales well with higher numbers of subgraphs, the problem still of high complexity due to the combinatorial test of substitution between subgraphs. In real-world applications, the number of subgraphs can be exponential. It would be interesting to make UnSubPatt runs faster to be able to deal with exponential numbers of subgraphs and to be more ecient in real-world applications. A possible way to make UnSubPatt run faster is parallelization. UnSubPatt tests separately the substitution among groups of subgraphs having the same size and order. Hence, an easy way to parallelize it is to test the substitution in groups in parallel threads or processors or even machines as in a grid or a cloud environment.

Approximate early termination

Another possible way to make UnSubPatt runs faster and more eciently is to integrate the selection in the subgraph extraction process through an early termination condition. Introducing such condition is very dicult in either breadth or depth rst search approach, as there is no guarantee that the resulting set of selected subgraphs is the optimal representative set. Moreover, the resulting set may only cover a small portion of the search space since the search would not be complete in many branches of the search tree. Indeed, in a breadth rst search approach, the output subgraphs would be only up to some levels of the search tree, and in a depth rst search, the selected subgraphs would cover other branches of the search tree only to a certain levels. In both cases, there is no guarantee that the cut branches do contain only irrelevant and redundant subgraphs. Thus, many representative subgraph candidates may be lost.

A possible way to perform UnSubPatt selection during the extraction of subgraphs is through approximation. Although this do not guarantee selecting the optimal set of representatives, we claim that this may provide a near optimal solution. For any frequent subgraph P 1 , if it substitutes another subgraph P 2 and a child node P 11 of P 1 (in the search tree) also substitutes a child node P 21 of P 2 , then the growing stops from P 21 . Otherwise, the growing continues until the same condition is veried or no other frequent subgraph is discovered. The frequent subgraphs that have not been substituted represent the set of representative unsubstituted patterns. 6.4.2 TRS extensions 6.4.2.1 Parallel TRS In real-world applications, the number of subgraphs can be exponential. Although TRS scales well with higher numbers of subgraphs, making TRS runs faster would be very interesting for real-world applications. Since TRS is composed of two steps, parallelization should cover both of them. The rst step consists in computing the corresponding values of the topological attributes for each subgraph. This step can be parallelized easily in two ways: the rst way is to compute the values of each attribute in parallel processes such that each process deals with one attribute for all subgraphs. The second way, is to divide the subgraph set in dierent groups then to compute the values of all attributes for each group in parallel processes such that each process computes the values of all attributes for a single group. The second step of TRS consists in clustering subgraphs based on their description-vectors into groups using k-Medoids. In [START_REF] Gamblin | [END_REF]], authors proposed CAPEK, a massively scalable parallel version of k-Medoids clustering algorithm. TRS can use CAPEK in the second step. Hence, TRS can be fully parallelized.

Removing the k constraint

In many applications, the user may not be able to dene a specic number of clusters. An interesting extension of TRS is to remove the k constraint. This can be performed using a clustering algorithm that do not require specifying the number of clusters. For instance, CAPEK [START_REF] Gamblin | [END_REF]] can determine the value of k automatically and thus it eliminates the need to specify the number of clusters in advance. This can also be performed using Medoidshift [Sheikh 2007] which is a non-parametric partitioning algorithm that automatically computes the number of clusters. Many other clustering techniques also oer this possibility such as hierarchical and density-based clustering.

Topological and Domain Knowledge-based Subgraph

Mining: Application on Protein 3D-Structures Abstract: This thesis is in the intersection of two proliferating research elds, namely data mining and bioinformatics. With the emergence of graph data in the last few years, many eorts have been devoted to mining frequent subgraphs from graph databases. Yet, the number of discovered frequent subgraphs is usually exponential, mainly because of the combinatorial nature of graphs. Many frequent subgraphs are irrelevant because they are redundant or just useless for the user. Besides, their high number may hinder and even makes further explorations unfeasible. Redundancy in frequent subgraphs is mainly caused by structural and/or semantic similarities, since most discovered subgraphs dier slightly in structure and may infer similar or even identical meanings. In this thesis, we propose two approaches for selecting representative subgraphs among frequent ones in order to remove redundancy. Each of the proposed approaches addresses a specic type of redundancy. The rst approach focuses on semantic redundancy where similarity between subgraphs is measured based on the similarity between their nodes' labels, using prior domain knowledge. The second approach focuses on structural redundancy where subgraphs are represented by a set of user-dened topological descriptors, and similarity between subgraphs is measured based on the distance between their corresponding topological descriptions. The main application data of this thesis are protein 3D-structures. This choice is based on biological and computational reasons. From a biological perspective, proteins play crucial roles in almost every biological process. They are responsible of a variety of physiological functions. From a computational perspective, we are interested in mining complex data. Proteins are a perfect example of such data as they are made of complex structures composed of interconnected amino acids which themselves are composed of interconnected atoms. Large amounts of protein structures are currently available in online databases, in computer analyzable formats. Protein 3D-structures can be transformed into graphs where amino acids are the graph nodes and their connections are the graph edges. This enables using graph mining techniques to study them. The biological importance of proteins, their complexity, and their availability in computer analyzable formats made them a perfect application data for this thesis. Implementation of the research works are available on my personal home page http://fc.isima.fr/∼dhii or upon email request. Fouille de Sous-graphes Basée sur la Topologie et la Connaissance du Domaine: Application sur les Structures 3D de Protéines Résumé: Cette thèse est à l'intersection de deux domaines de recherche en plein expansion, à savoir la fouille de données et la bioinformatique. Avec l'émergence des bases de graphes au cours des dernières années, de nombreux eorts ont été consacrés à la fouille des sous-graphes fréquents. Mais le nombre de sous-graphes fréquents découverts est exponentiel, cela est due principalement à la nature combinatoire des graphes. Beaucoup de sous-graphes fréquents ne sont pas pertinents parce qu'ils sont redondants ou tout simplement inutiles pour l'utilisateur. En outre, leur nombre élevé peut nuire ou même rendre parfois irréalisable toute utilisation ulterieure. La redondance dans les sous-graphes fréquents est principalement due à la similarité structurelle et / ou sémantique, puisque la plupart des sous-graphes découverts dièrent légèrement dans leur structures et peuvent exprimer des signications similaires ou même identiques. Dans cette thèse, nous proposons deux approches de sélection des sousgraphes représentatifs parmi les fréquents an d'éliminer la redondance. Chacune des approches proposées s'intéresse à un type spécique de redondance. La première approche s'adresse à la redondance sémantique où la similarité entre les sous-graphes est mesurée en fonction de la similarité entre les étiquettes de leurs noeuds, en utilisant les connaissances de domaine. La deuxième approche s'adresse à la redondance structurelle où les sous-graphes sont représentés par des descripteurs topologiques dénis par l'utilisateur, et la similarité entre les sous-graphes est mesurée en fonction de la distance entre leurs descriptions topologiques respectives. Les principales données d'application de cette thèse sont les structures 3D des protéines. Ce choix repose sur des raisons biologiques et informatiques. D'un point de vue biologique, les protéines jouent un rôle crucial dans presque tous les processus biologiques. Ils sont responsables d'une variété de fonctions physiologiques. D'un point de vue informatique, nous sommes intéressés à la fouille de données complexes. Les protéines sont un exemple parfait de ces données car elles sont faites de structures complexes composées d'acides aminés interconnectés qui sont eux-mêmes composées d'atomes interconnectés. Des grandes quantités de structures protéiques sont actuellement disponibles dans les bases de données en ligne. Les structures 3D des protéines peuvent être transformées en graphes où les acides aminés représentent les noeuds du graphe et leurs connexions représentent les arêtes. Cela permet d'utiliser des techniques de fouille de graphes pour les étudier. L'importance biologique des protéines et leur complexité ont fait d'elles des données d'application appropriées pour cette thèse. Les implémentations des ces travaux de recherche sont disponibles sur ma page personnelle http://fc.isima.fr/∼dhii ou sur demande par courriel.

Keywords:

Mots clés:

2. 1

 1 The dierent levels of the KDD process. . . . . . . . . . . . . 11 2.2 Using interestingness measures to mine interesting patterns. . 14 2.3 Pattern mining as pre-processing step in a pattern-based data mining framework. . . . . . . . . . . . . . . . . . . . . . . . . 15 2.4 The structure of DNA (right) and RNA (left). . . . . . . . . . 20 2.5 A representation of the 3D-structure of the hemochromatosis protein. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.6 Simplied process of transcription and translation. . . . . . . . 21 2.7 The common structural scheme of amino acids. . . . . . . . . 21 2.8 The four levels of protein structure. . . . . . . . . . . . . . . . 23 2.9 Exponential growth of the size of biological databases. . . . . 27 2.10 Triangulation example in a 2D-space. Left: Triangulation do meet the Delaunay condition. Right: Triangulation do not meet the Delaunay condition. . . . . . . . . . . . . . . . . . . 29 2.11 Example of protein 3D-structure (hemochromatosis) transformed into graph of amino acids (272 nodes and 1059 edges) using the main atom methods with C α as the main atom and a distance thresholds δ ≥ 7Å. . . . . . . . . . . . . . . . . . . 31 3.1 Example of an unlabeled graph (a) and a labeled graph (b). . 36 3.2 Example of a subgraph (g) that is frequent in the graphs(a), (b) and (c) with a support of 3 3 = 1. . . . . . . . . . . . . . . . 37 3.3 Example of a candidates search tree in a BFS manner (a) and in a DFS manner (b). Each node in the search tree represents a subgraph candidate. . . . . . . . . . . . . . . . . . . . . . . 38 3.4 General schema of wrapper approaches for feature selection. . 43 3.5 General schema of embedded approaches for feature selection. 43 3.6 General schema of lter approaches for feature selection. . . . 44 4.1 An example of two representative unsubstituted patterns sampled from our experiments (from C-type lectin domains (DS3)). The gure also shows the corresponding position of each node of the subgraphs in the real protein 3D-structure. . . . . . . . 65 4.2 Unsubstituted pattern selection framework. . . . . . . . . . . . 66 4.3 An example of two substitutable subgraphs. . . . . . . . . . . 72 4.4 Rate of representative unsubstituted patterns Ω * from all fre- quent subgraphs Ω depending on the substitution threshold (τ ). 79 iv List of Figures 4.5 Classication accuracy of the four protein datasets using naive bayes (NB) and all frequent subgraphs (gSpan+NB) then the representative unsubstituted ones with dierent substitution thresholds (UnSubPatt+NB). . . . . . . . . . . . . . . . . . 4.6 Classication accuracy by support vector machine (SVM). . . 4.7 Classication accuracy by decision trees (C4.5). . . . . . . . . 4.8 Distribution of patterns of DS1 for all the frequent subgraphs and for the representative unsubstituted ones with dierent substitution thresholds (left: standard arithmetic scale. Right: logarithmic scale.). . . . . . . . . . . . . . . . . . . . . . . . . 4.9 Distribution of patterns of DS2 for all the frequent subgraphs and for the representative unsubstituted ones with dierent substitution thresholds (left: standard arithmetic scale. Right: logarithmic scale.). . . . . . . . . . . . . . . . . . . . . . . . . 4.10 Distribution of patterns of DS3 for all the frequent subgraphs and for the representative unsubstituted ones with dierent substitution thresholds (left: standard arithmetic scale. Right: logarithmic scale.). . . . . . . . . . . . . . . . . . . . . . . . . 4.11 Distribution of patterns of DS4 for all the frequent subgraphs and for the representative unsubstituted ones with dierent substitution thresholds (left: standard arithmetic scale. Right: logarithmic scale.). . . . . . . . . . . . . . . . . . . . . . . . . 4.12 Classication accuracy comparison with Blast, Dali and pattern selection approaches. . . . . . . . . . . . . . . . . . . . . . . . 5.1 An example of a graph of a chemical compound. . . . . . . . . 5.2 Distribution of subgraphs by size for the Enzymes dataset. . . 5.3 Distribution of subgraphs by size for the AIDS antiviral screen dataset. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.4 Distribution of subgraphs by size for the Enzymes dataset using dierent values of k (number of representatives). . . . . . . . . 5.5 Distribution of subgraphs by size for the AIDS antiviral screen dataset using dierent values of k (number of representatives). 5.6 Runtime of clustering for TRS and the naïve approach with dierent number of clusters (k). . . . . . . . . . . . . . . . . . 5.7 Runtime of clustering for TRS and the naïve approach to select 100 representatives among dierent number of subgraphs. . . . 5.8 Runtime of clustering for TRS and the naïve approach to select 500 representatives among dierent number of subgraphs. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Context and motivations . . . . . . . . . . . . . . . . . 2 1.3 Contributions . . . . . . . . . . . . . . . . . . . . . . . . 4 1.3.1 UnSubPatt . . . . . . . . . . . . . . . . . . . . . . . 4 1.3.2 TRS . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.4 Outline of the manuscript . . . . . . . . . . . . . . . . 5

Figure 2 .

 2 Figure 2.10: Triangulation example in a 2D-space. Left: Triangulation do meet the Delaunay condition. Right: Triangulation do not meet the Delaunay condition.

  and L is the label function that maps a node or an edge to a label (Figure 3.1 shows an example of an unlabeled graph (a) and a labeled graph (b)). G is called a labeled graph and the labels of nodes and edges are denoted respectively by L(u) and L{u, v}.

Chapter 4 .

 4 UnSubPatt: Mining representative unsubstituted graph patterns by means of substitution matrices

-

  |G|: number of proteins in the datase -Avg.|V|: average number of nodes -Avg.|E|: average number of edges -Max.|V|: maximal number of nodes Chapter 4. UnSubPatt: Mining representative unsubstituted graph patterns by means of substitution matrices -Max.|E|: maximal number of edges G-proteins : DS1 contains protein 3D-structures from the G-protein family, also known as guanine nucleotide-binding proteins. These proteins are mainly involved in transmitting chemical signals originating from outside a cell into the inside of it. G-proteins are able to activate a cascade of further signaling events resulting a change in cell functions. They regulate metabolic enzymes, ion channels, transporter, and other parts of the cell machinery, controlling transcription, motility, contractility, and secretion, which in turn regulate diverse systemic functions such as embryonic development, learning and memory, and homeostasis. C1-set domains : The C1-set domains composing DS2 are immunoglobulinlike domains, similar in structure and sequence. They resemble the antibody constant domains. They are mostly found in molecules involved in the immune system, in the major histocompatibility complex class I and II complex molecules, and in various T-cell receptors. C-type lectin domains : Lectins occur in plants, animals, bacteria and viruses. In DS3, the C-type (Calcium-dependent) lectins are family of lectins which share structural homology in their high-anity carbohydraterecognition domains. There are at least twelve structural families of lectins, of which C-type lectins is one. This family involves groups of proteins playing divers functions including cell-cell adhesion, immune response to pathogens and apoptosis. Protein kinases, catalytic subunit : Protein kinases, catalytic subunit composing DS4 play a role in various cellular processes, including division, proliferation, apoptosis, and dierentiation. They are mainly proteins that modies other ones by chemically adding phosphate groups to them. This usually results in a functional change of the target protein by changing enzyme activity, cellular location, or association with other proteins. The catalytic subunits of protein kinases are highly conserved, and several structures have been solved, leading to large screens to develop kinase-specic inhibitors for the treatments of a number of diseases.

Chapter 4 .

 4 UnSubPatt: Mining representative unsubstituted graph patterns by means of substitution matrices

4 .

 4 Density: The density of a graph G = (V, E) measures how many edges are in E compared to the maximum possible number of edges between the nodes in V . Formally: den(G) = 2|E| (|V | * (|V |-1)) . 5. Average clustering coecient: The clustering coecient of a node u, denoted by c(u), measures how complete the neighborhood of u is, i.e., c(u) = 2eu ku(ku-1)

92Chapter 5 .

 5 TRS : Towards an ecient discovery of topological representative subgraphs 6. Average eective eccentricity: For a node u, the eective eccentricity represents the maximum length of the shortest paths between u and every other node v in G, i.e., e(u) = max{d(u, v) : v ∈ V }. If u is isolated then e(u) = 0.The average eective eccentricity is dened as Ae(G) = 1 n n i=1 e(u i ), where n is the number of nodes of G. 7. Eective diameter: The eective diameter represents the maximum value of eective eccentricity over all nodes in the graph G, i.e., diam(G) = max{e(u) | u ∈ V } where e(u) represents the eective eccentricity of u as dened above. 8. Eective radius: The eective radius represents the minimum value of eective eccentricity over all nodes in the graph G, i.e., rad(G) = min{e(u) | u ∈ V } where e(u) represents the eective eccentricity of u. 9. Closeness centrality: The closeness centrality measures how fast information spreads from a given node to other reachable nodes in the graph. For a node u, it represents the reciprocal of the average shortest path length between u and every other reachable node in the graph, i.e., C c (u) = n-1 v∈{V \u} d(u,v) where d(u, v) is the length of the shortest path between the nodes u and v. For a graph G, we consider the average value of closeness centrality of all the nodes, i.e., C c (G) = 1 n n i=1 u i . 10. Percentage of central nodes: Here, we compute the ratio of the number of central nodes from the number of nodes in the graph. A node u is considered as central point if the value of its eccentricity is equal to the eective radius of the graph, i.e., e(u) = rad(G). 11. Percentage of end points: It represents the ratio of the number of end points from the total number of nodes of the graph. A node u is considered as end point if deg(u) = 1. 12. Number of distinct eigenvalues: Any graph G can be represented by an adjacency matrix A. As the adjacency matrix A has a set of eigenvalues, these eigenvalues are not necessarily dierent. Here, we count the number of distinct eigenvalues of A. 13. Spectral radius: Let A be the adjacency matrix of the graph G and 1 , 2 , ..., m be the set of eigenvalues of A. The spectral radius of G, denoted ρ(G), represents the largest magnitude eigenvalue, i.e., ρ(G) = max(| i |) where i ∈ {1, .., m}. 14. Second largest eigenvalue: The value of the second largest eigenvalue of the adjacency matrix of the graph.

  : The energy of an adjacency matrix A of a graph G is dened as the squared sum of the eigenvalues of A. Formally: E(G) = n i=1 2 i .

.Figure 5 . 1 :

 51 Figure 5.1: An example of a graph of a chemical compound. 1 Example Given the graph in Figure 5.1, the corresponding values of each of the dened attributes are as follows: -Number of nodes = 20, -Number of edges = 21, -Average degree = 2.1, -Density = 0.11, -Average clustering coecient = 0, -Average eective eccentricity = 5.75, -Eective diameter = 8, -Eective radius = 4,

  of objects Ω, number of clusters k, maximum number of iterations max iter Result: Set of medoids Ω * = {O 1 , O 2 , ..., O k } 1 begin 2 Ω * ← Ω k : start with K objects randomly selected from Ω; of the non-selected ob jects to the cluster having the most similar medoid; 5 Calculate the cost C i = (D(Ω k ) -D(Ω * )) for each swap of one medoid with another object; 6 if C i < 0 then 7 Ω * ← Ω k ; 8 end 9 nb iter = nb iter + 1; 10 until (no change) or (nb iter ≥ max iter ); 11 end the algorithm must choose a new partitioning. Consequently, after a nite number of iterations, bounded by a user-dened maximum number of iterations, the algorithm will run out of partitionings or no improvement will be observed. Hence, the algorithm terminates. 5.3.3.3 Why k-Medoids and not k-Means? K-Means [MacQueen 1967] is one of the most used algorithms for clustering. We adopt the k-Medoids clustering instead of k-Means because the latter denes the clusters' centers as ctive points. Thus, in order to detect the subgraph delegates, we have to compute the distance between the subgraphs and the center within the same cluster and consider the closest subgraph to the centeroid as the representative subgraph delegate. Whereas, the k-Medoids algorithm requires that the clusters' centroids be real points instead of being ctive. Hence, the clusters' medoids are directly considered as the representative subgraph delegates which prevents performing unnecessary computation needed to detect the delegates with k-Means. Besides k-Medoids is less sensitive to noise and outliers.

Algorithm 4 :

 4 TRSData: Frequent subgraphs Ω, number of representatives k Result: Topological representative subgraphs Ω

98Chapter 5 .

 5 TRS : Towards an ecient discovery of topological representative subgraphs

  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 6.2 Summary of contributions . . . . . . . . . . . . . . . . 110 6.2.1 UnSubPatt . . . . . . . . . . . . . . . . . . . . . . . 110 6.2.2 TRS . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 6.3 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . 111 6.4 Ongoing works and prospects . . . . . . . . . . . . . . 113 6.4.1 UnSubPatt extensions . . . . . . . . . . . . . . . . . 113 6.4.2 TRS extensions . . . . . . . . . . . . . . . . . . . . . . 114

  Aims . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.2 Data mining . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.2.1 Knowledge discovery in databases . . . . . . . . . . . .

	Chapter 2 Data mining and biological background
	Contents
	2.1

10 2.2.2 Pattern mining in knowledge discovery . . . . . . . . . 11 2.2.3 Curse of dimensionality in pattern mining . . . . . . . 12 2.2.4 Measuring the quality of patterns . . . . . . . . . . . . 13 2.2.5 Applications of patterns in data mining . . . . . . . . 15 2.2.6 Applications of data mining . . . . . . . . . . . . . . . 18 2.3 Biological background : bioinformatics and biological data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.3.1 Bioinformatics . . . . . . . . . . . . . . . . . . . . . . 18 2.3.2 Biological data . . . . . . . . . . . . . . . . . . . . . . 18 2.3.3 Protein structure . . . . . . . . . . . . . . . . . . . . . 21 2.3.4 From protein 3D-structures to protein graphs . . . . . 26 2.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . 31

  Aims . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 3.2 Graph mining . . . . . . . . . . . . . . . . . . . . . . . . 34

	Chapter 3 Related works
	Contents
	3.1

3.3 Subgraph mining . . . . . . . . . . . . . . . . . . . . . . 34 3.4 Frequent subgraph discovery . . . . . . . . . . . . . . . 35 3.4.1 Problem denition . . . . . . . . . . . . . . . . . . . . 35 3.4.2 Candidates generation . . . . . . . . . . . . . . . . . . 38 3.4.3 Frequent subgraph discovery approaches . . . . . . . . 39 3.4.4 Variants of frequent subgraph mining: closed and maximal subgraphs . . . . . . . . . . . . . . . . . . . . . . 41 3.5 Feature selection . . . . . . . . . . . . . . . . . . . . . . 41 3.5.1 Feature selection techniques . . . . . . . . . . . . . . . 42 3.5.2 Feature selection search strategy . . . . . . . . . . . . 44 3.6 Feature selection for subgraphs . . . . . . . . . . . . . 44 3.6.1 Mining top-k subgraphs . . . . . . . . . . . . . . . . . 45 3.6.2 Clustering-based subgraph selection . . . . . . . . . . 46 3.6.3 Sampling-based approaches . . . . . . . . . . . . . . . 48 3.6.4 Approximate subgraph mining . . . . . . . . . . . . . 49 3.6.5 Discriminative subgraph selection . . . . . . . . . . . . 50 3.6.6 Other signicant subgraph selection approaches . . . . 53 3.7 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . 55 3.8 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . 57

Table 4

 4

	.1: Characteristics of the experimental datasets
	Dataset SCOP ID Family name DS1 52592 G-proteins DS2 48942 C1-set domains DS3 56437 C-type lectin domains DS4 88854 Protein kinases, catalytic subunit	|G| 66 76 76 82	Avg.|V| Avg.|E| Max.|V| Max.|E| 246 971 897 3 544 238 928 768 2 962 185 719 755 3 016 275 1077 775 3 016

Table 4

 4

	.2: Number of frequent subgraphs (Ω), representative unsubstituted subgraphs (Ω * ) and the selection rate
	Dataset	| Ω |	| Ω * | Selection rate (%)
	DS1 DS2 DS3 DS4 1073393 9958 799094 7291 258371 15898 114792 14713	0.91 6.15 12.82 0.93

Table 4 .

 4 4: Number of subgraphs (#SG) and accuracy (Acc) of the classication of each dataset using NB coupled with frequent subgraphs (FSg) then representative unsubstituted subgraphs using Blosum62 (USP 62 ), Blosum80 (USP 80 ) and Pam250 (USP 250 )

	Dataset	FSg #SG Acc #SG Acc #SG Acc #SG Acc USP 62 USP 80 USP 250
	DS1 DS2 DS3 DS4 1073393 0.79 9958 0.98 10417 0.90 9148 0.90 799094 0.62 7291 0.78 7328 0.67 6137 0.68 258371 0.80 15898 0.90 15930 0.87 15293 0.87 114793 0.86 14713 0.94 14792 0.91 14363 0.93

Table 4 .

 4 5: Runtime analysis of UnSubPatt with dierent substitution

	thresholds	Number of	Substitution thresholds
		patterns 10000 20000 30000 40000 50000 60000 70000 80000 90000 100000	τ = 10% τ = 30% τ = 50% 4s 4s 4s 8s 8s 10s 13s 13s 17s 18s 18s 25s 23s 23s 33s 28s 28s 41s 35s 35s 52s 40s 42s 66s 46s 49s 80s 53s 57s 136s

  Number of nodes: The total number of nodes in the graph, also called the graph order |V |. 2. Number of edges: The total number of edges in the graph, also called the graph size |E|. 3. Average degree: The degree of a node u, denoted deg(u), represents the number of nodes adjacent to u. The average degree of a graph G is the average value of the degrees of all nodes in G. Formally: deg(G) = ) where deg(u i ) is the degree of the node u i and n is the number of nodes in G.

	1 n	n i=1 deg(u i

Table 5

 5 Berman 2000]. G-proteins are also known as guanine nucleotide-binding proteins. These proteins are mainly involved in transmitting chemical signals originating from outside a cell into the inside of it. They regulate metabolic enzymes, ion channels, transporter, and other parts of the cell machinery, controlling transcription, motility, contractility, and secretion, which in turn regulate diverse systemic functions such as embryonic development, learning and memory, and homeostasis.

	.1: Benchmark datasets |G| Avg.|V| Avg.|E| 66 246 971 C1 set domains Dataset G-proteins 76 238 928 Enzymes 664 358 910 AIDS antiviral screen 43850 28 30
	proteins are sampled from a selected protein family, namely G-proteins and C1 set domains, whereas negative proteins are randomly sampled from the Protein Data Bank [

Table 5 .

 5 2: Number of frequent subgraphs (Ω) extracted from each dataset

	Dataset G-proteins 114792 | Ω | C1 set domains 258371 Enzymes 253404 Sida 6749
	naïve approach and TRS, were implemented in R. Subgraph encoding:

Table 5 .

 5 3: Comparison of average information gain of the topological representative subgraphs (TRS) with those selected by the naïve approach (NA) and the initial set of all frequent subgraphs (FSG).

		G-proteins	C1 set domains
	FSG	0.216	0.148
	# representatives 50 100 200 300 400 500 600 700 800 900 1000	NA 0.104 0.092 0.096 0.097 0.094 0.090 0.096 0.097 0.098 0.094 0.094	TRS 0.324 0.342 0.343 0.347 0.339 0.348 0.340 0.343 0.352 0.358 0.353	NA 0.068 0.061 0.044 0.058 0.051 0.052 0.054 0.055 0.054 0.054 0.056	TRS 0.254 0.285 0.273 0.267 0.276 0.269 0.267 0.272 0.274 0.276 0.276
	Average	0.095 +0.008 -0.005	0.344 +0.013 -0.020	0.055 +0.012 -0.011	0.271 +0.013 -0.017

  Sélection de motifs, fouille de motifs, sous-

	graphe graphe	fréquent, représentant	sous-graphe topologique,	représentant structure	non-substitué, de protéine

http://en.wikipedia.org/wiki/Data_mining (October

2013)

http://en.wikipedia.org/wiki/Nucleic_acid_analogue(October 2013)

http://en.wikipedia.org/wiki/Protein_structure(October 2013)

http://www.oxfordjournals.org/nar/database/a/

http://www.rcsb.org/pdb/ (August 2013)

A tetrahedron is a polyhedron composed of four triangular faces that meet at each corner. A circum-sphere of a polyhedron is a sphere that contains the polyhedron and touches each of its vertices.

4.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . 85

Source:[Li

2012]. Labels of nodes represent the atoms: O=oxygen, H=hydrogens, N=nitrogen, C=carbon.

Property 3 (Termination) There is only a nite number of possible partitionings of the set of objects Ω into k groups. As we are looking for the partitioning that best minimizes the overall distance, we do not go from one partitioning to another only if it improves the clustering. Thus, in each swap

http://dtp.nci.nih.gov/docs/aids/aids_data.html

Appendix B gives a brief survey about Protein Graph Repository (PGR) which is an online website that contains a tool for transforming protein 3D-structures into graphs and a repository mainly dedicated to protein graphs. The le describes the coordinates of the atoms that are part of the protein.

Part II Contributions

For example, the rst ATOM line above describes the alpha-N atom of the rst residue of peptide chain A, which is a proline residue, the rst three oat numbers are its x, y and z coordinates and are in units of Angstroms. The next three columns are respectively the occupancy, temperature factor, and the element name. -The user upload his set of PDB les -Specify : the graph construction method, the appropriate parameters values, and the output format -Run the parser A more detailed description is reported in the site.

B.2.2 Repository

The repository (see Figure B.4) represents a protein graph data bank that is freely available online. It is coupled with a ltering tool allowing the selection and targeting of a specic set of protein graphs. The repository is fed each time the parser is run. A download option is enabled making the existing protein graphs available for any further purpose.