Alexandre Bento
email: alexandre.bento@polymtl.ca

Amal Zouaq
email: amal.zouaq@polymtl.ca

Michel Gagnon
email: michel.gagnon@polymtl.ca

Ontology Matching Using Convolutional Neural Networks

Keywords: ontology matching, machine learning, convolutional neural networks

Ontology matching is a key problem to solve in the context of Semantic Web, in order to achieve interoperability of information. As the number of ontologies grows for a given domain, and as overlapping between ontologies follows the same path, developing accurate and reliable techniques to operate this task automatically is becoming more and more crucial. While traditional approaches to solve this problem are based on string metrics and structure analysis, in this paper we present a methodology to align ontologies automatically, using machine learning techniques. We use convolutional neural networks to analyse structure in text data for OAEI ontologies. We obtain state-of-the-art performance, as well as potential cross-domain applications.

Introduction

An ontology is a set of structural rules designed to represent concepts in order to perform logic-based operations to retrieve or infer new information. As Semantic Web technologies are expanding and becoming more popular, the amount of data that needs to be represented grows the same way, and so does its complexity. Since web technologies are designed to be decentralised, redundancy among knowledge bases occurs inevitably. For this reason, finding methods to align equivalent data or their model is becoming crucial. This problem is addressed in this paper. Traditional ontology matching methods are mainly based on string similarity and structure analysis. In this paper we propose another approach, using machine learning techniques. The core of our method is based on the idea that semantic information can be retrieved automatically from text information within ontologies, and within their structure. To complete this task, convolutional neural networks were used.

Previous Works

As explained earlier, the usual way to align ontologies consists in standard string similarity measurement techniques, and the analysis of the ontologies' structure in order to identify equivalent classes and properties [START_REF] Hooi | A survey on ontology mapping techniques[END_REF]. There are three main string analysis techniques: 1) string distances (Levenshtein, Jaccard, string equality, etc.),2) syntactic transformations (tokenisation, lemmatization, stop word removal, etc.) and 3) semantic operations (finding synonyms, translating, categorization, etc.) [START_REF] Cheatham | String similarity metrics for ontology alignment[END_REF]. Although using only string metrics can lead to significant results when aligning ontologies, it is crucial to choose the right metric for the ontologies being studied. Some more advanced string metrics can be defined and show powerful results, such as metrics that take into account both the similarities and the differences between two labels [START_REF] Stoilos | A string metric for ontology alignment[END_REF]. But in any case, a confidence value must be attributed to any of these metrics. Another possible approach consists in analysing similarities between data types of key properties for each studied concept [START_REF] Granitzer | Ontology alignment-a survey with focus on visually supported semi-automatic techniques[END_REF]; however, this approach cannot be used on its own, and must be coupled with a text analysis approach, such as string distance, as discussed above. Also, the structure of an ontology can be used to determine similarity between concepts: if two classes have similar children or parents, they should be considered as equivalent [START_REF] Granitzer | Ontology alignment-a survey with focus on visually supported semi-automatic techniques[END_REF]. Finally, some machine learning approaches have been implemented but are still uncommon in the field of ontology alignment. Some tried and tested algorithms such as K Nearest Neighbors (KNN), Support Vector Machine (SVM) and decision trees, which can outperform state-of-the-art matching tools [START_REF] Nezhadi | Ontology alignment using machine learning techniques[END_REF]. Machine learning techniques can also be used as a side tool for the alignment task, such as word embeddings to determine string similarity [START_REF] Dhouib | An ontology alignment approach combining word embedding and the radius measure[END_REF]. Our methodology goes a step further and uses embeddings as an input to make classification more accurate.

Data

The data we used come from the Ontology Alignment Evaluation Initiative (OAEI)1 . This data is organised in different tracks. For training, we used data from the LargeBio track; for testing, we used other independent tracks, described in Section 3.2.

Training -LargeBio Ontologies

LargeBio consists of three biomedical ontologies:

• Foundational Model of Anatomy (FMA)2 ;

• SNOMED3 ;

• National Cancer Institute Thesaurus (NCI) 4 . OAEI provides alignments between each of these ontologies. We used them to build a dataset. Some classes in these ontologies do not have any label, and since this makes them unusable with our approach, they were excluded from the dataset. We also noticed that classes referenced as equivalent often had the exact same label (after passing labels to lower case), which biased the training process, and were completely irrelevant since these alignments are trivial. Hence these examples were excluded from the dataset as well. With these constraints, we found 18105 references within LargeBio ontologies. In order to make a balanced dataset (same number of positive and negative alignments), we randomly generated the same number of negative examples, matching classes that were not referenced as similar in the ontologies. This leads to a complete dataset containing 36210 examples. Finally, this dataset was divided into training, validation and test sets (this test set is used to choose the model with best predictive capabilities, but was not used to evaluate our methodology and to compare it to others, as this would induce a bias when choosing the best model (final test data is not supposed to be used for any kind of training). The test was performed on other ontologies -see next section). We used 80% of the original dataset for training, 10% for validation and 10% for testing.

Testing -Other OAEI Tracks

In order to evaluate our method and compare it to previous works, we used the ontologies provided by the Ontology Alignment Evaluation Initiative (OAEI). OAEI evaluation is divided in different tracks, based on the domain and complexity of ontologies. We chose to evaluate our method on four OAEI tracks:

• Anatomy

• Phenotype and Disease

• BioDiv

• Conference

To make sure that our method was tested the same way as other competitors in the OAEI workshop, we wrapped our tool with the SEALS platform, which is used by the OAEI organization to evaluate participants.

Description of the Alignment Method

In this section, we explain how our alignment system is built, how input data is processed and how the final alignment is generated.

Preprocessing

The preprocessing step consists in two different actions:

• transforming ontological data into numerical vectors that a neural network model can use as input;

• pre-selecting alignments that are too trivial to be submitted to the model.

Input Data Transformation

For the task we aim to achieve, input data consist in two separate ontologies that must be aligned. As this cannot directly be fed to a machine learning model, it must be transformed into a set of numerical vectors that a model can use as input. The final alignment must be a set of comparisons between each class of both ontologies to be aligned. First, the structure of each ontology is extracted using a dedicated tool (we used Apache Jena for this application). This allows us to make a list of each class of the ontology.

For each class that has a label, we also gather the label of its superclasses, allowing us to use the structure of the ontology as well.

Our convolutional neural network takes as input a pair of class labels and their superclasses (we observed experimentally that using subclasses does not make predictions more accurate) and returns whether they are similar or not. As neural network models require a fixed input vector length, some limits have to be set in order to respect this constraint. First, for each class label, we set a maximum length of 150 characters (shorter labels are filled with blank spaces at the end; longer labels are cropped). We observed that this value led to a minimal prediction error.

As classes have a variable number of superclasses, we must set a limit for this parameter as well. We chose to use 5 superclasses for each class. For classes with fewer superclasses, we use padding with blank spaces; for classes with more superclasses, we only take the first five levels in the structure of its superclasses.

A neural network model cannot take strings of characters as direct input. These must be converted into numerical vectors. A simple character encoding could have been used (such as the ASCII code), but we chose to add more semantic information during this preprocessing step, and hence used a character embedding5 . This embedding provides a representation vector for each possible character. The embedding we used is of dimension 300. Each provided value is normalized between 0 and 1, which is ideal for feeding a neural network model.

To limit noise within the input data, we also lowercased each class label, as well as replaced underscores with blank spaces.

Pre-selecting Trivial Examples

In order to prevent combinatorial explosion when comparing classes from both ontologies (each ontology can have thousands of classes, leading to millions of possible combinations to evaluate), a preselection must be applied before passing input data to the neural network model. Two cases must be studied:

• trivial positive examples: across two different ontologies, some classes can be identified with the exact same name, as discussed in section 3.1. When this happens, these classes are automatically considered as equivalent.

• trivial negative examples: since only a small proportion of the candidate pairs to alignment contain equiv- alent classes, this implies that many completely different classes would have to be evaluated if no preselection was involved. To limit this problem, we chose to apply a distance-based preselection, using two criteria: Levenshtein distance and the length of each class label. If the Levenshtein distance between the labels of two classes is too large, then these classes are considered as different. We also noticed that short labels lead to many mistakes during classification, hence we need to take this problem into consideration. To solve it, we chose to weight the Levenshtein distance with a factor that is inversely proportional to the length of the labels: the shorter the labels, the higher the final distance. Let a and b be the labels of two classes that need to be compared. Let L a and L b their respective length. Then we compute the following index i:

i = levenshtein(a, b) L a * L b (1)
We then define a threshold th. If i > th, we directly classify the two classes as different.

Alignment Using Machine Learning Models

Once input data has been preprocessed, it can be used to train a neural network model. We chose to use convolutional neural networks (noted as CNN in the following paragraphs) in order to capture relevant structural information inside text data.

Neural network model

The model we used is composed of two main sections:

• CNN layers;

• a multilayer perceptron (noted as MLP).

We used several layers of CNN, with a different filter size for each. This allows capturing patterns at different scales, which are obtained by successive applications of average pooling (which is the equivalent of a x2 zoom each time). We define a super-convolution layer with the following:

• a convolution layer with a kernel size of 5;

• an activation layer (we use ReLU);

• a second convolution layer with a kernel size of 5;

• a second activation layer (ReLU);

• an average pooling layer of size 2.

A diagram of a super-convolution layer is shown in Figure 1.

The CNN part of the model is composed of 8 superconvolution layers (which allows processing all scales with a division factor 2 in between each layer). CNN layers are then followed by MLP layers. We observed experimentally that the depth of the network had a more significant impact on performance than the size of the layers. Thus the model we used was composed of 10 MLP layers, of size 500 each. We used ReLU to activate each layer.

Finally, the last layer of the model leads to a single neuron (with sigmoid activation) in order to make a binary classifier.

Training strategy

In a real-life situation, when aligning two ontologies, the number of positive and negative examples that have to be classified are heavily unbalanced. Indeed, for two ontologies with 2000 classes each, we need to process 4000000 different examples in order to complete the alignment, when only a few hundred classes are equivalent in between these ontologies. If this issue is not considered during training (i.e., if the training dataset has the same number of positive and negative examples), the trained model can generate a large number of false positive alignments (which remains marginal when the test dataset is balanced as well, but in a real-life situation, this is no longer the case).

In order to face this problem, a proper training strategy must be adopted. We We found that a value of 10 -5 gives decent results. We also used learning rate decay, with β 1 = 0.9 and β 2 = 0.999.

In order to make the training process automatic, we used early stopping to prevent overfitting. As training is not perfectly stable, it is necessary to use a patience value of 2 in order to avoid local minima. Validation loss was used as the early stopping criterion.

To get the best alignment performance, it is good practice to train several models and pick the one with best prediction capability on a test dataset. As discussed in section 3.1, a dedicated test set was created for this purpose. We trained 5 models and chose the one with the lowest error on test data.

Evaluation and Results

This methodology was evaluated on OAEI tracks described in Section 3.2. As shown in Table 1, our methodology leads to similar results as state-of-the-art competitors. Also, as the results for the Conference track show, our system produces relevant performance for non-biomedical ontologies. This means that our network was successful in aligning classes from different domains, which is a valuable result.

Conclusion and future works

We showed that a machine learning approach to the ontology matching problem using convolutional neural networks leads to state-of-the-art results. As there is no domaindependant variable in our methodology, it can be applied to any domain, with no necessary adaptation. We also showed that a model trained on biomedical data gives consistent results on other domains; however this needs to be confirmed on more datasets. This approach could be improved using other types of neural networks, or a combination of different models: recurrent networks, especially LSTM, are very appropriate for 6 2018 OAEI results: http://oaei.ontologymatching.org/2018/results/ text data, as they allow analysing sequences, and may improve performance for ontology matching. Similarly transformers might lead to better results and are a research direction we would like to explore, together with different inputs to the network. The preprocessing part of the methodology presented in this article could also be replaced with more advanced techniques (possibly machine learning as well). This could help solve the false-positive problem presented in Section 4.2.2 with more accurate results.

Figure 1 :

 1 Figure 1: A super-convolution layer which takes 64 features of size 32x32 as input.

  chose to grant more weight to negative examples during training, as the false positive problem comes from them. We found experimentally that a weight of 40 (versus a weight of 1 for positive examples) works best. Below this value, too many false positives still appear. Above it, the model fails to identify some positive examples correctly. As the model needs to be symmetrical (i.e., if class a is equivalent to class b, then b is equivalent to a), the training dataset was duplicated and the class positions were swapped. Adam optimizer was used to manage training. Considering the high number of training examples, the learning rate must be set to a low value in order to get stable training.

Table 1 :

 1 Three of them are composed of biomedical data (Anatomy, Phenotype and Disease, and BioDiv; same domain as the training data), and the last one (Conference) is different and is based on conference organisation data. We wrapped our tool with the SEALS platform so that we could evaluate it in the same conditions as other participants for the OAEI workshop; we then compared the results we obtained with the 2018 OAEI results 6 . Results are presented in Table1. Final results on OAEI tracks. HP/MP and Doid/Ordo are tasks from the Phenotype and Disease track. Flopo/Pto is a task from BioDiv. Best F1 corresponds to the F1-measure of the best participant for each task. Pos represents the position of our system in the competition based on the best F1.

	Task	Prec. Recall	F1	Best F1 Pos.
	Anatomy	0.871 0.890 0.881	0.943	5/16
	HP/MP	0.882 0.819 0.850	0.855	3/9
	Doid/Ordo	0.870 0.795 0.831	0.848	4/10
	Flopo/Pto	0.872 0.790 0.829	0.86	2/8
	Conference 0.80	0.70	0.75	0.77	3/15

http://oaei.ontologymatching.org

http://sig.biostr.washington.edu/projects/fm/

http://www.ihtsdo.org/index.php?id=545

http://ncit.nci.nih.gov/

https://github.com/minimaxir/char-embeddings


Omar Gaci

Stefan Balev

A study of protein structure using amino acid interaction networks

 and SCOP (Murzin.1995). Proteins from the same class have similar structures and most often, similar functions. In this paper we show that structure classes can also be defined in the terms of the properties of amino acid networks.

Protein Structure

Unlike other biological macromolecules (e.g., DNA), proteins have complex, irregular structures. They are built up by amino acids that are linked by peptide bonds to form a polypeptide chain. We distinguish four levels of protein structure:

1. The amino acid sequence of a protein's polypeptide chain is called its primary or one-dimensional (1D) structure. It can be considered as a word over the 20-letter letter amino acid alphabet.

2. Different elements of the sequence form local regular secondary (2D) structures, such as α-helices or β-strands. 3. The tertiary (3D) structure is formed by packing such structural elements into one or several compact globular units called domains. 4. The final protein may contain several polypeptide chains arranged in a quaternary structure.

By formation of such tertiary and quaternary structure, amino acids far apart in the sequence are brought close together to form functional regions (active sites). The reader can find more on protein structure in [START_REF] Branden | Introduction to protein structure[END_REF]. One of the general principles of protein structure is that hydrophobic residues prefer to be inside the protein contributing to form a hydrophobic core and a hydrophilic surface. To maintain a high residue density in the hydrophobic core, proteins adopt regular secondary structures that allow non covalent hydrogen-bond and hold a rigid and stable framework. There are two main classes of secondary structure elements (SSE), α-helices and β-sheets (see Fig 1). Fig. 1. Left: an α-helix illustrated as ribbon diagram, there are 3.6 residues per turn corresponding to 5.4 Ǻ. Right: A β-sheet composed by three strands.

An α -helix adopts a right-handed helical conformation with 3.6 residues per turn with hydrogen bonds between C'=O group of residue n and NH group of residue n+4. A β-sheet is build up from a combination of several regions of the polypeptide chain where hydrogen bonds can form between C'=O groups of one β strand and another NH group parallel to the first strand. There are two kinds of β-sheet formations, anti-parallel β-sheets (in which the two strands run in opposite directions) and parallel sheets (in which the two strands run in the same direction). Based on the local organization of the secondary structure elements (SSE), proteins are divided in the following four classes [START_REF] Levitt | Structural patterns in globular proteins[END_REF]:

1. All α, proteins have only α -helix secondary structure. 2. All β, proteins have only β -strand secondary structure.

3. α / β, proteins have mixed α -helix and β-strand secondary structure. 4. α + β, proteins have separated α -helix and β-strand secondary structure. From this first division, a more detailed classification can be done. The most frequently used ones are SCOP, Structural Classification Of Proteins [START_REF] Murzin | SCOP: a structural classification of the protein database for the investigation of sequence and structures[END_REF], and CATH, Class Architecture Topology Homology [START_REF] Orengo | CATH -a hierarchic classification of protein domain structures[END_REF]. They are hierarchical classifications of proteins' structural domains. A domain corresponds to a part of a protein which has a hydrophobic core and not much interaction with other parts of the protein.

Models and Methods

The 3D structure of a protein is determined by the coordinates of its atoms. This information is available in Protein Data Bank (PDB) [START_REF] Berman | The protein data bank[END_REF], which regroups all experimentally solved protein structures. Using the coordinates of two atoms, one can compute the distance between them. We define the distance between two amino acids as the distance between their Calpha atoms. Considering the Calpha atom as a "center" of the amino acid is an approximation, but it works well enough for our purposes. Let us denote by N the number of amino acids in the protein. A contact map matrix is a N x N 0-1 matrix, whose element (i,j) is one if there is a contact between amino acids i and j and zero otherwise. It provides useful information about the protein. For example, the secondary structure elements can be identified using this matrix. Indeed, α-helices spread along the main diagonal, while β-sheets appear as bands parallel or perpendicular to the main diagonal [START_REF] Ghosh | Dynamics of lysozyme structure network: probing the process of unfolding[END_REF]. There are different ways to define the contact between two amino acids. Our notion is based on spacial proximity, so that the contact map can consider non-covalent interactions. We say that two amino acids are in contact iff the distance between them is below a given threshold. A commonly used threshold is 7 Ǻ and this is the value we use. Consider a graph with N vertices (each vertex corresponds to an amino acid) and the contact map matrix as incidence matrix. It is called contact map graph. The contact map graph is an abstract description of the protein structure taking into account only the interactions between the amino acids. Now let us consider the subgraph induced by the set of amino acids participating in SSE. We call this graph SSE interaction network (SSE-IN) and this is the object we study in the present chapter. The reason of ignoring the amino acids not participating in SSE is simple. Evolution tends to preserve the structural core of proteins composed from SSE. In the other hand, the loops (regions between SSE) are not so important to the structure and hence, are subject to more mutations. That is why homologous proteins tend to have relatively preserved structural cores and variable loop regions. Thus, the structure determining interactions are those between amino acids belonging to the same SSE on local level and between different SSEs on global level. Fig. 2 gives an example of a protein and its SSE-IN. In [START_REF] Muppirala | A simple approach for protein structure discrimination based on the network pattern of conserved hydrophobic residues[END_REF] and [START_REF] Brinda | A network representation of protein structures: implications for protein stability[END_REF] the authors rely on similar models of amino acid interaction networks to study some of their properties, in particular concerning the role played by certain nodes or comparing the graph to general interaction networks models. Thanks to this point of view the protein folding problem can be tackled by graph theory approaches. As we will see in the next section, there are three main models of interaction networks, extensively studied and whose properties are identified. The purpose of our work is to identify specific properties which associate the proteins SSE-IN with a general network model. Based on such a pattern description of SSE-IN, one can plan the study of their formation, dynamics and evolution.

General Models of Interactions Networks

Many systems, both natural and artificial, can be represented by networks, that is, by sites or vertices bound by links. The study of these networks is interdisciplinary because they appear in scientific fields like physics, biology, computer science or information technology. These studies are lead with the aim to explain how elements interact with each other inside the network and what are the general laws which govern the observed network properties. From physics and computer science to biology and social sciences, researchers have found that a broad variety of systems can be represented as networks, and that there is much to be learned by studying these networks. Indeed, the studies of the Web [START_REF] Broder | Graph structure in the Web[END_REF], of social networks [START_REF] Wasserman | Social network analysis : methods and applications[END_REF] or of metabolic networks [START_REF] Jeong | The large-scale organization of metabolic networks[END_REF] contribute to put in light common non-trivial properties of these networks which have a priori nothing in common. The ambition is to understand how the large networks are structured, how they evolve and what are the phenomena acting on their constitution and formation. In this section we present the three main models of interaction networks by describing their specific properties. We also define several measures that we use in the next section in order to study SSE-IN empirically.

The Random Graph Model

The random graph models are one of the oldest network models, introduced in [START_REF] Solomonoff | Connectivity of random nets[END_REF] and further studied in [START_REF] Erdõs | On random graphs {I}[END_REF] and [START_REF] Erdõs | On the evolution of random graphs[END_REF]. These works identify two different classes of random graphs, called Gn,ù and Gn,p and defined by the following connection rules:

-G n,u regroups all graphs with n vertices and m edges. To generate a graph sampled uniformly at random from the set G n,u , one has to put m edges between vertex pairs chosen randomly from n initially unconnected vertices.

-G n,p is the set of all graphs consisting of n vertices, where each vertex is connected to others with independent probability p. To generate a graph sampled randomly, one has to begin with n initially unconnected vertices and join each pair by an edge with probability p.

In G n,u the number of edges is fixed whereas in G n,p the number of edges can fluctuate but its average is fixed. When n tends to be large the two models are equivalent. Definition 1 The degree of a vertex v, k v , is the number of edges incident to v. The mean degree, z, of a graph G is defined as follows:

) 1 ( 2 1       n p n m k n z V v v
The degree distribution is one of the important characteristics of this kind of networks because it affects their properties and behavior [START_REF] Réka | Topology of evolving networks: local events and universality[END_REF]. The random graph G n,p has a binomial degree distribution. The probability p k that a randomly chosen vertex is connected to exactly k others is [START_REF] Newman | Random graphs with arbitrary degree distributions and their applications[END_REF]:

  k n k n k k p p p    ) 1 (
When n tends to infinity, this becomes:

! ) 1 ( ) 1 ( ! lim k e z p p p k n p z k n k k n k       
As we see in Fig. 3, Poisson distributions have different behavior for different mean degrees z. Each distribution has a clear peak close to k = z, followed by a tail that decays as 1/k! which is considerably quicker than exponential.

Small-World Networks

This network model was introduced in [START_REF] Watts | Small Worlds[END_REF] as a model of social networks. It has been since adopted to treat phenomena in physics, computer science or social sciences. The model comes from the observation that many real-world networks have the following two properties:

-The small-world effect, meaning that most pairs of vertices are connected by a short path through the network. This phenomenon has two explanations. First, the concept of "shortcuts" through a network allows to join two distant vertices by a small number of edges [START_REF] Watts | Small Worlds[END_REF].

. Second, the concept of "hubs", vertices whose connectivity is higher than others provide bridges between distant vertices because most vertices are linked to them.

-High "clustering'", meaning that there is a high probability that two vertices are connected one to another if they share the same neighbor. To determine if a network is a small-world, one can use the measures described below and compare them to the corresponding measures of a random graph. Definition 2 The characteristic path length [START_REF] Watts | Small Worlds[END_REF], denoted L, of a graph G is the median of the means of the shortest path lengths connecting each vertex v to all other vertices. More precisely, let d(v, u) be the length of the shortest path between two vertices v and u and let v d be the average of d (v, u)

over all V u  . Then the characteristic path length is the median of { v d }.
This definition applies when the graph consists of single connected component. However, the SSE-IN we consider in the next section may have several connected components. In this case, when we calculate the mean of the shortest path lengths

) (v d

we take into account only the vertices u which are in the same connected component as v.

Since the mean and the median are practically identical for any reasonably symmetric distribution, the characteristic path length of a random graph is the mean value of the shortest path lengths between any two vertices. The characteristic path length of a random graph with mean degree z is z n L RG log log  It increases only logarithmically with the size of the network and remains therefore small even for large systems. Definition 3 The local clustering coefficient [START_REF] Watts | Small Worlds[END_REF], C v , of a vertex v with k v neighbors measures the density of the links in the neighborhood of v.

  v k v v E C 2 ) ( 
where the numerator is the number of edges in the neighborhood of v and the denominator is the number of all possible edges in this neighborhood. The clustering coefficient C of a graph is the average of the local clustering coefficients of all vertices:

   V v v C n C 1
The clustering coefficient of a random graph with mean degree z is Watts and Strogatz (Watts, 1999) defined a network to be a small-world if it shows both of the following properties:

1   n z C RG
1. Small world effect:

RG L L  2. High clustering: RG C C 

Scale-Free Networks

The most important property of scale-free systems is their invariance to changes in scale. The term "scale-free" refers to a system defined by a functional form f(x) that remains unchanged within a multiplicative factor under rescaling of the independent variable x. Indeed, this means power-law forms, since these are the only solutions to f(an

) = b f(n),
where n is the number of vertices [START_REF] Newman | The structure and function of networks[END_REF]. The scale-invariance property means that any part of the scale-free network is stochastically similar to the whole network and parameters are assumed to be independent of the system size [START_REF] Jeong | The large-scale organization of metabolic networks[END_REF]. If n k is the number of vertices having the degree k, we define p k as the fraction of vertices that have degree k in the network:

n n p k k 
The degree distribution can be expressed via the cumulative degree function [START_REF] Newman | The structure and function of networks[END_REF], [START_REF] Erdõs | On random graphs {I}[END_REF]:

    ' ' ' k k k k p P
which is the probabilty for a node to have a degree greater or equal to k. By plotting the cumulative degree function one can observe how its tail evolves, following a power law or an exponential distribution. The power law distribution is defined as following [START_REF] Newman | The structure and function of networks[END_REF]:

) 1 ( ' '          k k P k k k
and the exponential distribution is defined by the next formula:

  / ' / ' k k k k k e e P       
Between this two distributions, there is a mixture of them where the distribution has a power law regime followed by a sharp cut-off, with an exponential decay of the tail, expressed by the next formula:

    / ) 1 ( / ' ' ' ' k k k k k e k e k P         
Like a power law distribution, it decreases polynomially, so that the number of vertices with weak degree is important while a reduced proportion of vertices having high degree exists. The last are called "hubs" that is sites with large connectivity through the network, see Fig. 4. The scale-free model depends mainly on the kind of degree distribution, thus a network is defined as a scale-free if:

-The degree distribution is a power law distribution P(k) ≈ k -α over a part of its range.

-The distribution exposant satisfies 2 < α ≤ 3 [START_REF] Goh | Universal behavior of load distribution in scale-free networks[END_REF]). Amaral and al [START_REF] Amaral | Classes of small-world networks[END_REF] have studied networks whose cumulative degree distribution shape lets appear three kinds of networks. First, scale-free networks whose distribution decays as a power law with an exposant α satisfying bounds seen above. Second, see Fig. 4, broad-scale or truncated scale-free networks whose the degree distribution has a power law regime followed by a sharp cutoff. Third, single-scale networks whose degree distribution decays fast like an exponential. Fig. 4. Degree distribution described in [START_REF] Amaral | Classes of small-world networks[END_REF]. The red line follows a power law, as for scale-free networks. The green line corresponds to truncated scale-free networks. The black curve corresponds to single-scale networks.

Topological Measures

Here, we present some measures that we use to describe proteins' SSE-IN. Among them, there are simple ones, the most frequently used, but also more subtle, which allow a more precise discrimination between interaction networks.

Diameter and mean distance

The distance in a graph G = (V,E) between two vertices u,v V, denoted by d(u,v), is the length of the shortest path connecting u and v [START_REF] Diestel | Graph Theory[END_REF].

If there is no path between u and v, we suppose that d(u,v) is undefined. A graph diameter, D, is the longest shortest path between any two vertices of a graph [START_REF] Diestel | Graph Theory[END_REF]:

  V v u v u d D   , / ) , ( max
The mean distance is defined as the average distance between each couple of vertices: 2Density The density, denoted δ, is defined as the ratio between the number of edges in a graph and the maximum number of edges which it could have:

    V v u G v u d n n d , ) , ( ) 1 (
2 2 ) 1 ( 2 ) ( n m n n m G    
The density of a graph is a number between 0 and 1. When the density is close to one, the graph is called dense, when it is close to zero, the graph is called sparse [START_REF] Coleman | Estimation of sparse jacobian matrices and graph coloring problems[END_REF]. Clustering coefficients Watts and Strogatz proposed a measure of clustering [START_REF] Watts | Small Worlds[END_REF] and defined it as a measure of local vertices density, thus for each node v, the local clustering around its neighborhood is defined in the following way:

) 1 ( 2 1   v v v k k C
The clustering coefficient is a ratio between the number of edges and the maximum number of possible edges in the vertice neighborhood. If we extend the previous defintion to the entire graph, the clustering is given by the expression:

   V v v local C pairs neighbour connected of number n C 1
The last defintion is mainly local because for each node, it involves only its neighborhood.

The global clustering was studied by Newman et al. [START_REF] Newman | The strucuture of scientific collaboration networks[END_REF] and can be mesuared by the following formula:

vertices of triplets connected of number graph the in triangles of number C global   3
A triangle is formed by three vertices which are all connected and a triplet is constituted by three nodes and two edges. The global clustering coefficient C global is the mean probability that two vertices that are neighbors of the same other vertex will themselves be neighbors.

A First Topological Description

In this section, we present a publication (Gaci & Balev, 2008b) where we study the protein SSE-IN behavior. We want to observe how proteins from a same structural family provide similar SSE-IN according to their topological properties. To do that, we propose topological measures which we apply on a sample of proteins to put in evidence the existence of equivalence between structural similarity and topological homogeneity in the resulting SSE-IN. The first step before studying the proteins SSE-IN is to select them according to their SSE arrangements. Thus, a protein belongs to a CATH topology level or a SCOP fold level iff all its domains are the same. We have worked with the CATH v3.1.0 and SCOP 1.7.1 files. We have computed the measures from the previous section for three families of each hierarchical classification, namely SCOP and CATH (see Table 1). We have chosen these three families by classification, in particular because of their huge protein number. Thus, each family provides a broad sample guarantying more general results and avoiding fluctuations. Moreover, these six families contain proteins of very different sizes, varying from several dozens to several thousands amino acids in SSE. Table 1. Families studied, mainly due to their protein number.

Diameter and mean distance

Table 2 shows the average diameter for each one of the studied families. We observe very close diameters between TIM Barrel and TIM beta/alpha-barrel and also between Lysozyme and Lysozyme-like families. This is explained by the fact that each pair of families contains almost the same proteins, in other worlds, Lysozyme topology in CATH is the equivalent of Lysozyme-like fold level in SCOP. Figure 5 shows the distribution of the diameter values for two of the studied families. We observe that the distribution follows roughly a Poisson law. These results confirm that the mean diameter is a suitable property to discriminate families between them.

The diameter being an upper bound of distances in interaction networks, we expect that the mean distance z will be lower than D. Table 3 confirms Table 3. Average of mean distances for each family.

Density and mean degree

As defined earlier, the density measures the ratio between the number of available edges and the number of all possible edges. Results presented in Table 4 show that the two families TIM Barrel and TIM beta/alpha-barrel have the minimum density. It has a consequence on their SSE-IN topology. When the density is low, the network is less connected and consequently, the diameter and the average distance are higher. Comparing these results to Tables 2 and3 Table 5. Average of mean degrees for each family.

Degree distribution

We compute the cumulative degree distribution for all proteins SSE-IN of studied families.

A sample of our results is presented on Figure 6. We can remark that the curves follow a power law distribution and can be approximated by the following power-law function: We observe the same results for all studied proteins. To explain this phenomenon, we have to rely on two facts. First, the mean degree of all proteins SSE-IN is nearly constant (see Table 5). Second, the degree distribution, see Figure 7, follows a Poisson distribution whose peak is reached for a degree near z. These two facts imply that for degree lower than the peak the cumulative degree distribution decreases slowly and after the peak its decrease is fast compared to an exponential one. Consequently, all proteins SSE-IN studied have a similar cumulative degree distribution which can be approximated by a unique power-law function.

Clustering Coefficients

The local clustering Clocal measures the fraction of pairs of a vertex's neighbors and the global clustering Cglobal gives the probability that among three vertices at least two are connected. The results presented in Table 6 show that the clustering coefficients are close for different families and cannot be correlated to density values. Consequently, the neighbour density remains independent of the previously studied properties. Table 6. Clustering coefficients for each family.

Consequences

In this first part we introduce the notion of interaction network of amino acids of a protein (SSE-IN) and study some of the properties of these networks. We give different means to describe a protein structural family by characterizing their SSE-IN. Some of the properties, like diameter and density, allow discriminating two distinct families, while others, like mean degree and power law degree distribution, are general properties of all SSE-IN. Thus, proteins having similar structural properties and biological functions will also have similar SSE-IN properties. In this way our model allows us to draw a parallel between biology and graph theory.

Comparisons with the Scale-Free Networks

We have worked on the entire PDB file available the 18th October 2007, that is 46679 files. We lead our simulations by considering all proteins SSE-IN without limiting us on a particular protein family or basing us on a classification. Indeed, our goal is to identify a general model for proteins SSE-IN and so that we don't discriminate proteins due to their biological function. Thus, despite the heterogeneity we can expect among folded proteins, we assume that a general model of Interaction Networks emerge and can be identified from protein SSE-IN which came from combinaison of the 20 amino acids.

General Behavior

We compute the cumulative degree distribution for all proteins SSE-IN, a sample of our results is presented on Fig 8 . We can remark that the curves describe a power law regime followed by the sharp cut-off. The power law function is expressed as following: We observe the same result for all studied proteins that is a cumulative degree distribution approximed by the function P k . Here, we discuss about characterisitcs or conditions which involve a such behavior. First, we are interested in the degree distribution and mainly its shape, see Fig 9 . We can see that degree distribution follows a Poisson distribution whose peak is reached for a degree near z. This result provides precision about how the vertices are connected within SSE-IN. It implies that the degree of the vertices is homogenous. In other words, a major part of them has a connectivity enough close to the mean degree. Consequently, the cumulative distribution depends on the mean degree value which acts as a threshold beyond which it decreases as an exponential since it's approximed via P k . To recapitulate, we show that the mean degree values constitute a threshold for protein SSE-IN cumulative degree distribution. For degrees lower than the mean degree it decreases slowly and after this threshold its decrease is fast compared to an exponential one, as shown Fig 8, 9 and 10. Consequently, we find a way to approximate all proteins SSE-IN cumulative degree distribution by the function P k which can be adjusted. This function describes a power law regime followed by a sharp cut-off which arises for degree values exceeding the mean degree. Proteins SSE-IN are so truncated scale-free networks. Since the degree distribution depends on the mean degree value, we compare for each node its degree as function of z, see Fig 12, to illustrate how nodes interact and in particular to highlight the weak fraction of highly connected nodes, also called hubs, less than 5 % of the total node number. An interesting study is to put in evidence the biological properties of nodes whose connectivity is marginal. Thus, we search to identify nodes which highly interact with their neighbors in the folded proteins. To do that, we have proceeded by grouping the proteins according to their secondary structure. Indeed, we have already shown (Gaci & Balev, 2008b) that the protein SSE-IN topologies from structural classifications are homogeneous and established a parallel between structural and topological properties. Based on the SCOP classification and more precisely on the fold families, we have selected a total of 18294 proteins, see If we consider that the role played by an amino acid inside a folded protein is equivalent to its interaction degree, then these plots show that despite a functional diversity between the 4 SCOP classes, there are globally the same amino acids which interact most, namely the Ala, Cys, Gly, Leu, Val. Therefore, the amino acids having a high connectivity interact independently of the protein biological function, we will explain this behavior further. Thus, the figure shows clearly that the amino acid Ala plays a central role in the studied proteins independently of the classification of their secondary structure. We also compute the occurrence level of hubs, that is their number of appearances on each protein SSE-IN. We cumulated this score at the SCOP class level to obtain the probability for each amino acid to be a hub having a high connected occurrence in a protein SSE-IN, see Fig The results show the existence of favorable region in which the hub apparition is higher than somewhere else. This favorable localization is strongly visible for the All Alpha class where the hubs have a tendency to interact around the positions 20, 40 or 80. The distribution of the hub positions is the most homogenous for the alpha/beta class which involve a dependence to the SSE-IN topology since it not possible to find more than one strong favorable area which appear around the position 60. To illustrate the existence of hubs favorable localization in the SSE-IN, we rely on the richclub phenomenon [START_REF] Colizza | Detecting rich-club ordering in complex networks[END_REF] according to which highly connected nodes have tendancy to be connected to one another. We compute the rich-club connectivity of a hub as the ratio of the number of links to the maximum number of links between nodes belonging to the rich-club. It appears, see Fig 16, that certain hubs are isolated mainly when the rich-club connectivity is low (position 0, 30, 60 for All Alpha SSE-IN) where as the favorable hub localizations correspond to a high coefficient.

The main observations about hubs behaviour are the following. First, there are four amino acids which have higher probability to have a high connectivity. Second, hubs have tendency to act in particular region in the SSE-IN. These two observations lead us to compute only the occurrence rate of the most frequently encountered hub Ala according to its positions, see Fig 17.

By comparing the figure 15 and 17, it appears clearly that the most highly occurrence rate for the 4 classes correspond to the position of the amino acid Ala. Therefore, we can establish a relation between amino acid position in the primary structure and hub apparition. Then, certain amino acid that is the Ala, Cys, Gly, Leu and Val act as hub because they appear in the protein sequence in favourable region which involve a high interaction within the folded structure.

Mean Degree Evolution

Since the mean degree plays the role of a threshold beyond which the cumulative degree distribution decreases exponentially, it is interesting to study its evolution with the size of the network, see Fig. 10. It appears that the mean degree increases very slightly with the size of the network. Even for networks with size ratio of 100, the mean degree ratio is only 1.15, see Fig. 11. Whatever the size of the network is, we observe that the mean degree is always between 5 and 8. This mean degree interval is a common property characterizing all SSE-IN. In order to explain this property, let us consider the structure of our networks. They are composed of densely connected subgraphs corresponding to secondary structure elements (see Fig. 18.

The number of edges connecting different subgraphs is relatively small, but these edges are the most important, since they correspond to interactions determining the tertiary structure. We start by computing the mean degree in each SSE subgraph. The results are shown on Fig. 19. We can see that the mean degree evolution at microscopic level is almost the same as at macroscopic level (compare to Fig. 10). Independently of the SSE size and type, the mean degree of each SSE subgraph, z SSE , is always bounded:

max min z z z SSE   (1)
when the size of the network is more than 10. In the general case z min = 5 and z max = 8, but when we consider a specific SSE size and type, finer bounds can be found (see Fig. 19). (3) On the other hand, from (1) it follows that

s i n z m n z i i i , , 1 , 2 2 max min     (4)
By summing up the last equation we obtain The last equation gives finer bounds on the mean degree. It shows that the bounds on z depend not only on the bounds on z SSE , but also on the ratio of inter-SSE edges. A higher proportion of inter-SSE edges shifts up the bounds. Proteins with bigger size have more SSEs and hence more links between different SSEs. This explains the increase of the mean degree with the size of the networks. Fig. 20 shows that the number of inter-SSE edges is quite variable, but is bounded and does not exceed 20%, it's the consequence of the excluded volume effect, since the number of residues that can physically reside within a given radius is limited. Fig. 20. Ratio of inter-SSE edges (r) as a function of the network size for the four classes of studied proteins.

Consequences

During our study, we have identified a means to approximate the cumulative degree distribution of the SSE-IN. This function describes a power law regime followed by a sharp cut-off. The SSE-In studied are consequently truncated scale-free networks. The study of the hubs shows that certain amino acid play a central role independently of the protein classification. The nature of these hubs depends on their positions in the primary structure.

Comparisons with the Small-World Networks

In this section we present an empirical characterization of SSE-IN properties. In order to choose our data sample, we have used the SCOP classification. We have worked with the SCOP 1.7.3 files. We have computed the measures from the section (4.2.) for the four mains classes of SCOP (see Table 7). Each class provides a broad sample guarantying more general results and avoiding fluctuations. Moreover, these four classes contain proteins of very different sizes, varying from several dozens to several thousands amino acids in SSE. The results obtained for the different classes are very similar, that is why in the rest of this section we show only the results for In a previous work (Gaci & Balev, 2008a), we have studied the two properties of SSE-IN related to the small-world model, namely their L/L RG and C/C RG ratios. Our results show (see Fig. 21) that nearly 60% of the proteins have SSE-IN consisting of between 100 and 500 amino acids. The small-world properties are satisfied mainly when the size of the network does not exceed 500 amino acids and there are about 15.3% small-world networks among all SSE-IN. Fig. 4 explains the reason for this low rate. One can see that although highly clustered, most SSE-IN do not satisfy the first small-world property.

To explain the results presented on Fig. 22, note that the mean degree z is not very different from one SSE-IN to another and is generally independent from the size. When the mean degree is fixed, the characteristic path length of a random graph grows like log n and its clustering coefficient has n -1 behavior. We can see that there is no clear relationship between the characteristic path length and the SSE-IN size. There are proteins with close sizes but very different path lengths. However, in general it grows faster than logarithmically with the size. The figure also shows that SSE-IN are very highly clustered. The C/C RG has clearly linear behavior, hence the clustering coefficient (like the mean degree) is independent from the size. On the other hand, the subnetworks corresponding to single SSEs are almost all small world networks. The last observation brings us to consider the edges whose extremities belong to different SSEs (see Fig. 18). These "shortcuts" represent the interactions between different SSEs and they determine the tertiary protein structure. They provide short paths between different network regions and bigger number of shortcuts implies smaller characteristic path length.

Computing the average connected component size, we observe that this size does not exceed 100 for the smallworld networks (see Fig. 23). Consequently, we identify a necessary condition for SSE-INs to be small-world, their average connected component size has to be less than 100. In (Gaci & Balev, 2008a) we show that the protein SSE-IN components interact with each other in the same way, no matter if they are small-world or not, see Fig 23 . Then, it is interesting to study not the quantity of interaction inter-SSE but rather their quality, that is we want to put in evidence the role of nodes allowing interaction between different SSEs. In graph theory, the betweenness of a node is defined as the total number of shortest paths between pairs of nodes that pass through this node. It measures the influence of a node in a network. The betweenness of a node t, denoted B(t) is defined as follows: where σ uv is the number of shortest paths between the nodes u and v, and σ uv (t) is the number of shortest paths between u to v that pass through t. The average betweenness of nodes interacting with other secondary structure motifs is shown on Fig 24 . We can see that the average betweenness of the small-world networks is similar to the average betweenness of the other networks. This means that neither the quantity nor the quality of nodes that link different SSEs guarantees a short characteristic path length. To better understand the properties of SSE-IN which are small-world, we introduce the secondary structure components interaction network, SSC-IN. This is a network in which each SSE is contracted to a single node. There is an edge between two SSEs s 1 and s 2 if theres is at least one interaction between an amino acid belonging to s 1 and an amino acid is at least one interaction between an amino acid belonging to s 1 and an amino acid belonging to s 2 . A weight is associated to each edge. The weight of the edge between s 1 and s 2 is the average distance (measured in the corresponding SSE-IN) between all pairs of amino acids belonging to s 1 and s 2 . SSC-IN is an abstraction of SSE-IN which puts in evidence the interactions between SSEs. Fig. 25 shows an example of SSC-IN. We computed the characteristic path lengths and the clustering coefficients for all protein SSC-IN, the results show once again that the small world effect is the discriminant property in the SSC-IN. Indeed, for a small-world SSC-IN the characteristic path length grows linearly with the size of the underlying SSE-IN and it never exceeds 4. The last observation can be correlated with the necessary condition for a SSE-IN to satisfy the small world model. Indeed, the average connected component size is bounded by 100 nodes in small world SSEIN. This has for consequence that the corresponding SSC-IN has bounded average connected component size and therefore a bounded characteristic path length. Then, a protein SSE-IN with size n > 25 is small world if and only if its SSC-IN characteristic path length is on the line shown in Fig 26

     t v t u v u uv uv t t B , , ) ( ) (  

Consequences

In this study, we put in evidence in which proportion the SSE-IN satisfy the small-world model. Their constituent that is the subgraphs representing the SSE are in the most majority small-world. The interactions between these SSE being limiting, it not allows to conserve a short distance when the SSE-IN size increases. Thus, to a SSE-IN belongs to the small-world model, it necessary that the average connected component size doesn't exceed 100 residues.

Conclusion

In this chapter, we exploit the possibilities offer by a modelisation using interaction networks. The main hypothesis we use is the conservation from structural toward topological properties. The comparison of the SSE-IN with the general model of interaction networks allows us to describe the consequence of the folding dynamic. The characterization we propose constitutes a first step of a new approach to the protein folding problem. The properties identified here, but also other properties we plan to study, can give us an insight on the folding process. They can be used to guide a folding simulation in the topological pathway from unfolded to folded state.

Fig. 2 .

 2 Fig. 2. Protein 1DTP (left) and its SSE-IN (right).

Fig

  Fig. 3. Poisson distribution

  Figure5shows the distribution of the diameter values for two of the studied families. We observe that the distribution follows roughly a Poisson law. These results confirm that the mean diameter is a suitable property to discriminate families between them. The diameter being an upper bound of distances in interaction networks, we expect that the mean distance z will be lower than D. Table3confirms this. Again, we observe very close values between the equivalent SCOP and CATH families for the reasons discussed above. But we can also see that different families have values which allow discrimination between them based on this parameter. It is interesting to note that the ratio D / z is about 2.5 for all the families. The last property is a characterization of all proteins' SSE-IN.

Fig. 6 .

 6 Fig. 6. Cumulative degree distribution for 1RXC from Rossman fold, left, and 1HV4 from TIM beta/alpha-barrel, right.

Fig. 7 .

 7 Fig. 7. Degree distribution for 1RXC from Rossman fold, left, and 1HV4 from TIM beta/alpha-barrel, right.Name z RossmannFold 7.2 TIM Barrel 7.17 Lysozyme 6.82 Globin-like 7.69 TIM β/α-barrel 7.15 Lysozyme-like 6.81

Fig. 8 .

 8 Fig. 8. Cumulative degree distribution for protein 1COY SSE-IN.

Fig. 9 .

 9 Fig. 9. Degree and cumulative distribution for 1COY SSE-IN. They decrease for degree values greater than the mean degree. Second, we study how the mean degree evolves through all SSE-IN. Its distribution, see Fig 10, indicates a relative weak variation according to the size. Even if two protein SSE-IN have size ratio around 10 or 100, their mean degree ratio is esimated to 1.05 or 1.15 and remains in the same scale order.

Fig. 10 .

 10 Fig. 10. Mean degree distribution according to protein SSE-IN size. It evolves with values enough close, between 6 and 8.

Fig. 11 .

 11 Fig. 11. Cumulative degree distribution of 1SE9 and 1AON SSE-IN whose size equal 50 and and 4988. Despite their important size difference, their mean degree stay close and worth respectively 6.6 and 7.5

Fig. 12 .

 12 Fig. 12. Degree of nodes in protein SSE-IN as function of z. Less than 5 % of nodes are hubs that is having a 'high' connectivity.

Fig. 13 .

 13 Fig. 13. Normalisation of the amino acid cumulative connectivity when they act as hubs for each SCOP class level. The amino acid Ala interacts higher than the others independently of proteins classification.We can remark the existence of peaks which show clearly a higly tendency of amino acids Ala, Cys, Gly, Leu and Val to have a high interactivy within the folded protein. Thus, there are the same amino acids which play the role of hubs independently of the structural family, we provide below the cause of this result. Now, we want to describe the way in which the hubs appear in the folded protein. Indeed, we study the distribution of the hubs position as a function of the structural class of the SSE-IN to identify variations dependent or not on the biological function of proteins. To make this study, we attribute an incremental position so that the H extremity has a position 100. Then, each time a hub exists in a SSE-IN, we increment its position occurence number and finally normalize by the maximum to obtain the occurence rate of hubs according to their positions in the SSE-IN, see Fig.15.

Fig. 15 .

 15 Fig. 15. Occurrence rate of hubs according to their position for each SCOP Class level.

Fig. 16 .

 16 Fig. 16. Hub rich-club connectivity as function of hub position for each SCOP class level.

Fig. 17 .

 17 Fig. 17. Occurrence rate of the hub amino acid Ala for each SCOP Class level.

Fig. 18 .

 18 Fig. 18. SSE-IN of 1DTP protein. The edges connecting different SSE are green.

Fig. 19 .

 19 Fig. 19. SSE subgraphs size distribution and mean degree as a function of the size. Now let us consider a whole protein. Suppose that it contains s secondary structure elements and let the element i has ni vertices and mi edges, i = 1,...,s. Then the total number of vertices is

Fig. 21 .

 21 Fig. 21. Size distribution of proteins SSE-IN and small-world networks ratio.

Fig. 22 .

 22 Fig. 22. L/L RG (left) and C/C RG (right) ratios as a function of SSE-IN size.

Fig. 23 .

 23 Fig. 23. Average connected component size (left) and shortcut ratio (right) as a function of protein SSE-In size.

Fig. 24 .

 24 Fig. 24. Betweenness of nodes which link different SSEs.

  Further, we consider a SSE-IN abstraction, called SSC-IN in which each node represents a SSE. Then, their study provides an alternative way to verify the SSE-IN behavior. Indeed, the characteristic path length in the SSC-IN is enough to infer to deduct if the SSE-IN belongs or not to the small-world model.

Fig. 25 .

 25 Fig. 25. Protein 1DTP SSC-IN. The edges weight corresponds to the mean distance between the two motifs in the SSE-IN.

Fig. 26 .

 26 Fig. 26. Characteristic path length in SSC-IN. The distance in SW SSC-IN grows linearly and is bounded by 4.

Table 2 .

 2 Average diameter for each family.

	Name	D
	RossmannFold	18.84
	TIM Barrel	19.83
	Lysozyme	12.81
	Globin-like	15.65
	TIM β/α-barrel	20.09
	Lysozyme-like	12.85

Table 4 .

 4 one can see the inversely proportional relation between density in one hand, and diameter and average distance on the other. Average density for each family.The mean degree, z, is presented in Table5. The observed values are close enough from one family to another. That is why the mean degree is not discriminating property, but rather a property characterizing all proteins' SSE-IN.

	Name		(G	)
	RossmannFold	0.033
	TIM Barrel		0.03
	Lysozyme	0.038
	Globin-like	0.034
	TIM β/α-barrel	0.029
	Lysozyme-like	0.042
	Name		z
	RossmannFold		7.2
	TIM Barrel		7.17
	Lysozyme		6.82
	Globin-like		7.69
	TIM β/α-barrel		7.15
	Lysozyme-like		6.81

Table 7 .

 7 Table7, and studied their SSE-IN to describe the specificities of the hubs. Structural families studied for the Scale-Free properties. We choose only families which count more than 100 proteins, for a total of 18294 proteins.We have worked with the SCOP 1.7.3 classification, a protein belongs to a SCOP fold level if all its domains are the same.

	Class	Number of Families	Number of Proteins
	All Alpha	12	2968
	All Beta	17	6372
	Alpha / Beta	18	5197
	Alpha + Beta	16	3757

For each protein SSE-IN from a SCOP fold level we identify the nodes whose degree is high, see Fig 12. By grouping nodes as a function of amino acids they represent, we finally obtain the amino acid connectivity score by fold families. By repeating this process at the SCOP class level, we calculate and normalize the cumulated connectivity level of amino acids playing the role of hubs, see Fig 13.


Omar Gaci
email: omar.gaci@univ-lehavre.fr

Stefan Balev
email: stefan.balev@univ-lehavre.fr

Ant Colony Approach to Predict Amino Acid Interaction Networks

In this paper we introduce the notion of protein interaction network. This is a graph whose vertices are the proteins amino acids and whose edges are the interactions between them. We consider the problem of reconstructing protein's interaction network from its amino acid sequence. An ant colony approach is used to solve this problem.

Introduction

Proteins are biological macromolecules participating in the large majority of processes which govern organisms. The roles played by proteins are varied and complex. Certain proteins, called enzymes, act as catalysts and increase several orders of magnitude, with a remarkable specificity, the speed of multiple chemical reactions essential to the organism survival. Proteins are also used for storage and transport of small molecules or ions, control the passage of molecules through the cell membranes, etc. Hormones, which transmit information and allow the regulation of complex cellular processes, are also proteins.

Genome sequencing projects generate an ever increasing number of protein sequences. For example, the Human Genome Project has identified over 30,000 genes which may encode about 100,000 proteins. One of the first tasks when annotating a new genome, is to assign functions to the proteins produced by the genes. To fully understand the biological functions of proteins, the knowledge of their structure is essential.

In their natural environment, proteins adopt a native compact three-dimensional form. This process is called folding and is not fully understood. The process is a result of interactions between the protein's amino acids which form chemical bonds.

In this study, we treat proteins as networks of interacting amino acid pairs [START_REF] Atilgan | Small-world communication of residues and significance for protein dynamics[END_REF]. In particular, we consider the subgraph induced by the set of amino acids participating in the secondary structure also called Secondary Structure Elements (SSE). We term this graph SSE interaction network (SSE-IN). We carry out a study to identify the interactions involved between the amino acids in the folded protein. To achieve this topological folding, we build an interaction probability between two amino acids as a function of their physicochemical properties and we rely on this probability building an ant colony system to fold a SS-IN.

The rest of the paper is organized as follows. In section 2 we briefly present the main types of amino acid interactions which determine the protein structure. In section 3 we introduce our model of amino acid interaction networks. In section 4 we propose an ant colony approach to reconstruct the graph of interactions between amino acids involved in the secondary structure. Finally, in section 5 we conclude and give some future research directions.

Protein structure

Unlike other biological macromolecules (e.g., DNA), proteins have complex, irregular structures. They are built up by amino acids that are linked by peptide bonds to form a polypeptide chain. We distinguish four levels of protein structure:

• The amino acid sequence of a protein's polypeptide chain is called its primary or one-dimensional (1D) structure. It can be considered as a word over the 20letter amino acid alphabet. • Different elements of the sequence form local regular secondary (2D) structures, such as α-helices or βstrands. • The tertiary (3D) structure is formed by packing such structural elements into one or several compact globular units called domains. • The final protein may contain several polypeptide chains arranged in a quaternary structure. By formation of such tertiary and quaternary structure, amino acids far apart in the sequence are brought close together to form functional regions (active sites). The reader can find more on protein structure in [START_REF] Branden | Introduction to protein structure[END_REF].

In their natural environment, proteins adopt a native compact three-dimensional form. This process is called folding and is not fully understood. The process is a result of interactions between the protein's amino acids which form chemical bonds. One of the general principles of protein structure is that hydrophobic residues prefer to be inside the protein contributing to form a hydrophobic core and a hydrophilic surface. To maintain a high residue density in the hydrophobic core, proteins adopt regular secondary structures that allow non covalent hydrogen-bond and hold a rigid and stable framework. There are two main classes of secondary structure elements (SSE), α-helices and β-sheets (see Fig. 1).

An α-helix adopts a right-handed helical conformation with 3.6 residues per turn with hydrogen bonds between C'=O group of residue n and NH group of residue n + 4.

A β-sheet is build up from a combination of several regions of the polypeptide chain where hydrogen bonds can form between C'=O groups of one β strand and another NH group parallel to the first strand. There are two kinds of β-sheet formations, anti-parallel β-sheets (in which the two strands run in opposite directions) and parallel sheets (in which the two strands run in the same direction).

Amino Acid Interaction Networks

The 3D structure of a protein is determined by the coordinates of its atoms. This information is available in Protein Data Bank (PDB) [START_REF] Berman | The protein data bank[END_REF], which regroups all experimentally solved protein structures. Using the coordinates of two atoms, one can compute the distance between them. We define the distance between two amino acids as the distance between their C α atoms. Considering the C α atom as a "center" of the amino acid is an approximation, but it works well enough for our purposes. Let us denote by N the number of amino acids in the protein. A contact map matrix is a N ×N 0-1 matrix, whose element (i, j) is one if there is a contact between amino acids i and j and zero otherwise. It provides useful information about the protein. For example, the secondary structure elements can be identified using this matrix. Indeed, α-helices spread along the main diagonal, while β-sheets appear as bands parallel or perpendicular to the main diagonal [START_REF] Ghosh | Dynamics of lysozyme structure network: probing the process of unfolding[END_REF]. There are different ways to define the contact between two amino acids. Our notion is based on spacial proximity, so that the contact map can consider non-covalent interactions. We say that two amino acids are in contact iff the distance between them is below a given threshold. A commonly used threshold is 7 Å [START_REF] Dokholyan | Topological determinants of protein folding[END_REF] and this is the value we use.

Consider a graph with N vertices (each vertex corresponds to an amino acid) and the contact map matrix as incidence matrix. It is called contact map graph. The contact map graph is an abstract description of the protein structure taking into account only the interactions between the amino acids. Now let us consider the subgraph induced by the set of amino acids participating in SSE. We call this graph SSE interaction network (SSE-IN) and this is the object we study in the present paper. The reason of ignoring the amino acids not participating in SSE is simple. Evolution tends to preserve the structural core of proteins composed from SSE. In the other hand, the loops (regions between SSE) are not so important to the structure and hence, are subject to more mutations. That is why homologous proteins tend to have relatively preserved structural cores and variable loop regions. Thus, the structure determining interactions are those between amino acids belonging to the same SSE on local level and between different SSEs on global level. Fig. 2 gives an example of a protein and its SSE-IN.

In [START_REF] Muppirala | A simple approach for protein structure discrimination based on the network pattern of conserved hydrophobic residues[END_REF], [START_REF] Brinda | A network representation of protein structures: implications for protein stability[END_REF] the authors rely on similar models of amino acid interaction networks to study some of their properties, in particular concerning the role played by certain nodes or comparing the graph to general interaction networks models. Thanks to this point of view the protein folding problem can be tackled by graph theory approaches.

Interaction Prediction

In previous works [START_REF] Gaci | Proteins: From structural classification to amino acid interaction networks[END_REF], [START_REF] Gaci | Hubs identification in amino acids interaction networks[END_REF], [START_REF] Gaci | The small-world model for amino acid interaction networks[END_REF], we have studied the protein SSE-IN. We have identified notably some of their properties like the degree distribution or also the way in which the amino acids interact. These works have allowed us to determine criteria discrimminating the different strucutral families. We have established a parallel between structural families and topological metrics describing the protein SSE-IN.

Using these results, we have proposed a method to predict the family of an unclassified protein based on the topological properties of its SSE-IN, see [START_REF] Gaci | Prediction of protein families by topological inference[END_REF]. Thus, we consider a protein defined by its sequence in which the amino acids participating in the secondary strucutre are known. This preliminary step is usually ensured by threading methods [START_REF] Mirny | Protein structure prediction by threading: Why it works and why it does not[END_REF] or also by hidden Markov models [START_REF] Asai | Prediction of protein secondary structure by the hidden markov model[END_REF]. Then, we apply a method able to associate a family from which we rely to predict the fold shape of the protein. This work consists in predicting the family which is the most compatible to the unknown sequence. The following step, is to fold the unknown sequence SSE-IN relying on the family topological properties.

Once a family has been predicted, we have been interested in the way that the different SSEs interact each others that is we want to predict the motifs involved in this sequence, see Fig. 3. In [START_REF] Gaci | Motif prediction in amino acid interaction networks[END_REF] we consider that the motifs formed by the SSEs in the unclassified sequence can be represented by an adjacency matrix where a 1 means that the two SSEs are in contact. Then, we use a comparative model built from the template proteins belonging to the predicted family and we rely on a genetic algorithm to predict the unclassified sequence matrix of motifs.

In this paper, we consider that the matrix of motif is correct. Our goal is to add inter-SSE edges to rebuild the sequence SSE-IN, see Fig. 4. We use a two-step approach following the hierarchical structure of the network. The first step consists in considering separately each pair of SSEs in interaction. We use an ant algorithm to identify the suitable interactions between amino acids belonging to these SSEs. When this step is done for all pairs of SSEs in interaction, we go back to global level and use another ant algorithm to select the final set of inter-SSE edges.

Prediction of the edge quantity

In [START_REF] Gaci | The small-world model for amino acid interaction networks[END_REF] we have studied the quantity of edges between SSEs, also called shortcuts, and we have shown that it is bounded mainly due to the excluded volume effect. Nevertheless, even if the shortcut number can be estimated knowing its upper bound, the distribution of shortcuts between the different SSEs composing the sequence stays difficult to predict (actually it is too variable from one protein SSE-IN to another).

To predict the shortcut edge rate of the sequence, we rely on the template proteins. We represent a protein as an array with one element by SSE in their order in the primary structure. Each cell is equals to the normalized size of the corresponding SSE, see Fig. 5.

From the predicted family, we choose the proteins with the same number of SSEs as the unclassified protein and we construct their arrays. Let s = (s 1 , . . . , s n ) be the sequence array and t = (t 1 , . . . , t n ) be the template protein array. We use the standard

L 1 distance d(s, t) = n i=1 |s i -t i |.
We admit 20% of difference, if d(s, t) < 0.2 n i=1 s i , we consider that the template protein is near the sequence. Finally, we compute the average shortcut rate of the near proteins to predict the quantity of edges to add in the initial disconnected graph of the sequence. If no near proteins are found, we compute the edge quantity to add as the average of the template proteins shortcut rate.

Prediction of the nodes to be connected

To add an edge between two SSEs we use a probability built from the predicted family. First, we choose to add the same quantity of edges between SSEs in contact, then the number of edges between two SSEs is equal to the number of shortcut predicted previously divided by the number of SSEs in contact. Second, to add an edge between two SSEs we use a probability built from the predicted family. Indeed, we consider the occurrence of a shortcut as a function of the amino acids it links. Fig. 6 shows the shortcut occurrence matrix of the families All alpha 47472 and All beta 50813. We remark that shortcuts between amino acids Leucine are the most frequent.

The problem of deciding how to add edges between two SSEs can be stated as follows. Let A = a 1 . . . a s and B = b 1 . . . b 1 . . . b t be two SSEs.

We want to add k edges among the s × t possibilities. For i ∈ [1, s] and j ∈ [1, t] the probability to link the amino acids a i and b j will be proportional to the number of occurrences of the shortcut (a i , b j ) denoted S(a i , b j ):

w ij ∼ S(a i , b j )
In order to add approximately k edges, we need

Local algorithm

This algorithm is used to identify the suitable shortcuts between a pair of SSEs in interaction. We start with a graph in which each node form the first SSE is connected to each node from the second SSE. The edges have weights w ij corresponding to the relative frequency of each kind of shortcut in the family, computed as explained previously. Each ant walks on the graph dropping pheromone on its way. This ant system has to reinforce the suitable shortcuts. When the emergence of specific shortcuts is done, we keep these edges for the next global research. An overall description is given as algorithm 1. The local research process by ant colony is the following. First, we create n ants which is equals is equal to the total number of nodes involved in the two SSEs which are respectively composed of s and t amino acids. The initial positions of the ants are chosen randomly, so at the beginning more ants may be at the same node. If an ant is on the node i, the probability to choose the next node j, denoted p ij , is defined as follows:

p ij = [τ ij ] α . [w ij ] β k∈V (i) [τ ij ] α . [w ij ] β
The heuristic vector or also the weight, w ij , associated to the shortcut edges has been already computed:

w ij = kS(a i , b j ) s i=1 t j=1 S(a i , b j )
For the edges connecting nodes from the same SSE, we take as weight the average of the weights of inter-SSE edges:

w = 1 st s i=1 j = 1 t w ij
After each move we update the pheromone quantity on the inter-SSE edges using the formula

xτ ij ← (1 -ρ)τ ij + a ij Δτ
where a ij is the number of ants that moved on the edge (i, j) and Δτ is the quantity of pheromone dropped by each ant. As far as the edges belonging to the same SSE are concerned, we keep the pheromone rate on them equal to the average pheromone rate on the inter-SSE edges

τ = 1 st s i=1 j = 1 t τ ij
In this way ants move inside an SSE completely randomly, while if they decide to change the SSE they are guided by the edge weights ant the pheromone rates.

The algorithm stops when a maximum number of iterations is reached. It can also stop earlier if the maximum pheromone rate is k times bigger than the average pheromone rate on the edges. In this case we consider that the reinforcement is sufficient. At the end, we keep only edges with pheromone quantity exceeding a threshold phero min .

Global algorithm

Once the local algorithm has provided inter-SSE edges, we build the SSE-IN composed by these edges. Now our goal is to keep only the most appropriate among them. The number of edges to keep, m P , we choose as in section 4.1. Global algorithm works similarly to the local one, but this time the ants move on the entire SSE-IN graph. Their number is equal to the total number of nodes. After the end of this algorithm we sort the edges by decreasing pheromone rate and keep only the first m P of them.

Finally, we compare the topological properties of the obtained graph to the average properties of the corresponding family and accept or reject, we discuss this step in the next section

Measure and Reliability

In [START_REF] Gaci | Characterization of amino acid interaction networks in proteins[END_REF], [START_REF] Gaci | Proteins: From structural classification to amino acid interaction networks[END_REF] we have shown that the protein SSE-IN can be described by their topological properties. We have shown that it exists a parallel between biological classification (notably the SCOP fold family level) and the SSE-IN topological properties. Here we exploit these properties to excluded the incompatible SSE-IN built by our ant colony approach. The principle is the following, we have predicted a fold family for the sequence from which we extract the template proteins. Thus, we compute the diameter, the characteristic path length and the mean degree to evaluate the average topological properties of the family for a particular SSE number. Then, after we have built the sequence SSE-IN, we compare its topological properties with the themplate ones. We admit an error up to 20% to accept the built sequence SSE-IN. If the built SSE-IN is not compatible, it is rejected.

As well, we evaluate the prediction of edge inter-SSE added. We compare the predicted value, denoted m P , with the real value, denoted m R :

accuracy = 1 - |m R -m P | m P

Simulations and Results

We have tested our method according to the predicted family because the probability of adding edge is determined by the family occurrence matrix. We have used the same dataset of sequences whose family has been predicted. For each protein, we have launched 180 simulations and we accept the built SSE-IN only when its topological properties are compatible to the template properties. The results are presented in Tab. 1. The score is the percentage of correctly predicted shortcut edges between the sequence SSE-IN and the SSE-IN we have reconstructed.

Since the edge quantity to add is in the most cases accurate, we understand that the global intersection score depends on the local researches lead for each pair of SSEs in contact. The plot, see Fig. 8, confirms this tendancy, if the local researches select at least 75% of the correct shortcuts edge, the global intersection score stays superior to 75% and evolves around 78% for the All alpha class and 76% for the All beta class.

To recapitulate, we show that the global score evolves around 70% of precision. The average score decreases for big proteins (of size more than 200). For these proteins there

Conclusion

We propose in this paper a means to fold a protein SSE-IN. To do that, we rely on the Levinthal hypothesis also called the kinetic hypothesis. Thus, the folding process is oriented and the proteins don't explore their entire conformational space. Here, we use the same approach: to fold a SSE-IN we limit the toplogical space by associating to a sequence a strucutral family [START_REF] Gaci | Prediction of protein families by topological inference[END_REF].

Since the strucutral motifs which are described in a strucutral family are limited, we predict by this way the SSE-IN motifs [START_REF] Gaci | Motif prediction in amino acid interaction networks[END_REF].

Then, we use an ant colony system to predict the nodes involved when two SSEs are in contact. We predict the inter-SSE edges by an ant colony approach and we repeat the same process at the global level. By measuring the resulting SSE-IN, we remark that their topology depends on the local research. If, during the local folding, we collect the right edges (more than 75%) then the global score stays close to 76% of the real edges inter-SSE.

The characterization we propose constitutes a new approach to the protein folding problem. Here we propose to fold a protein SSE-IN relying on topological properties. We use these properties to guide a folding simulation in the topological pathway from unfolded to folded state.

Figure 1 .

 1 Figure 1. Left: an α-helix illustrated as ribbon diagram, there are 3.6 residues per turn corresponding to 5.4 Å. Right: A β-sheet composed by three strands.

Figure 2 .

 2 Figure 2. Protein 1DTP (left) and its SSE-IN (right).

Figure 3 .

 3 Figure 3. 2OUF SS-IN (left) and its associated incidence matrix (right). The vertices represent the different α-helices and an edge exists when two amino acids interact.

Figure 4 .

 4 Figure 4. Protein 1DTP SSE-IN. Shortcut edges we want to predict are plotted in green.

Figure 5 .

 5 Figure 5. Building the array representation for the unclassified protein 2OUF.

Figure 6 .

 6 Figure 6. Occurrence matrix of edges inter-SSE for the family 47472, All alpha class (left) and 50813, All beta class (right).

  a i , b j ) Actually, for each pair of SSEs in contact we add the s×t possible edges whose weight is w ij .

Algorithm 1 :

 1 Algorithm to the emergence of shortcut edges between two SSEs using an ant colony. begin create n ants while stop condition do for each ant a do moveAnt(a) updatePheromone() selectShortcut(phero min ) end

Figure 7 .

 7 Figure 7. Precision of the edge quantity to add, the most prediction are close to the real values.

Figure 8 .

 8 Figure 8. The global score depends on the local researches. When the local researches provide the correct edges, the global score stays close to 78% for the All alpha class and 76% for the All beta class.

Table 1 .

 1 Shortcut edge research by an ant colony approach. The score measures the intersection between the effective and predicted shortcut edges. The algorithm parameter values are: α = 25, β = 12, ρ = 0.7, Δτ = 4000, k = 2, phero min = 0.8.

	SCOP	Protein	Score	Standard
	Family	Number and		Deviation
		Size
	46688 (All α) 17 -[27 ; 46]	79.136	8.11
	47472	10 -[98 ; 125]	70.69	15.53
	46457	25 -[129 ; 135] 74.56	9.04
	48112	11 -[194 ; 200] 68.3	14.94
	48507	18 -[203 ; 214] 64.48	7.84
	46457	16 -[241 ; 281] 63.37	16.93
	48507	20 -[387 ; 422] 61.94	9.42
	50629 (All β) 6 -[54 ; 66]	76.13	6.39
	50813	11 -[90 ; 111]	72.56	5.86
	48725	24 -[120 ; 124] 76.69	11.96
	50629	13 -[124 ; 128] 71.3	14.44
	50875	14 -[133 ; 224] 74.48	14.14