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

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

The Small-World Model for Amino Acid Interaction Networks

In this paper we introduce the notion of protein interaction network. This is a graph whose vertices are the protein's amino acids and whose edges are the interactions between them. Using a graph theory approach, we identify a number of properties of these networks. We compare them to the general small-world network model and we analyze their hierarchical structure.

I. 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 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 paper we identify some of the properties of the network of interacting amino acids. We believe that understanding these networks can help to better understand the folding process.

The rest of the paper is organized as follows. In section II we briefly present the main types of amino acid interactions which determine the protein structure. In section III we introduce our model of amino acid interaction networks. Section IV presents two general network models, random graphs and small-world networks. In section V we compare protein interaction networks to the general models and empirically characterize them based on all protein structures available in PDB. We show how the properties of these networks are related to the structure of the corresponding proteins. Finally, in section VI we conclude and give some future research directions.

II. PROTEIN STRUCTURE

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

• The amino acid sequence of protein's polypeptide chain is called its primary or one-dimensional (1D) structure.

It can be considered as a word over the 20-letter 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].

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 bonds 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).

III. PROTEIN 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. There are different ways to define the contact between two amino acids [START_REF] Ghosh | Dynamics of lysozyme structure network: probing the process of unfolding[END_REF]. 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 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 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], [START_REF] Atilgan | Small-world communication of residues and significance for protein dynamics[END_REF], [START_REF] Dokholyan | Topological determinants of protein folding[END_REF] the authors rely on 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. Using this model, many problems related to protein structure can be tackled by graph theory tools.

IV. GENERAL MODELS OF 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], [START_REF] Albert | The diameter of the world wide web[END_REF], of social networks [START_REF] Wasserman | Social network analysis : methods and applications , ser. Structural analysis in the social sciences[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 two classes of interaction networks by describing their specific properties. We introduce some empirical measures which will be used in the next section in order to study SSE-INs.

A. Random Graphs

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], [START_REF]On the evolution of random graphs[END_REF]. These works identify two different classes of random graphs, called G n,m and G n,p and defined by the following connection rules:

• G n,m regroups all graphs with n vertices and m edges. To generate a graph sampled uniformly at random from the set G n,m , 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,m 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:

z = 1 n v∈V k v = 2m n = p(n -1)

B. Small-world Networks

This network model was introduced in [START_REF] Watts | Collective dynamics of 'small-world' networks[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:

1) 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. 2) 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 d(v) be the average of d(v, u) over all u ∈ V . Then the characteristic path length is the median of {d(v)}.

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 d(v) 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

L RG = log n log z
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.

C v = |E(Γ v )| kv 2
where |E(Γ v )| is the number of edges in the neighborhood of v and kv 2 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:

C = 1 n v∈V C v
The clustering coefficient of a random graph with mean degree z is

C RG = z n -1
Watts and Strogatz [START_REF] Watts | Collective dynamics of 'small-world' networks[END_REF] defined a network to be a smallworld if it shows both of the following properties:

1) Small world effect:

L ∼ L RG 2) High clustering: C ≫ C RG V. EXPERIMENTAL RESULTS
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 previous section for the four mains classes of SCOP (see Table 1). 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 all α class.

In a previous work [START_REF] Gaci | A general model for amino acid interaction networks[END_REF], we 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. 3) 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% smallworld networks among all SSE-IN. Fig. 4 explains the reason To explain the results presented on Fig. 4, 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. 5). 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. 6). 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 [START_REF] Gaci | A general model for amino acid interaction networks[END_REF] 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 6 . 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

B(t) = u =v,u =t,v =t σ uv (t) σ uv
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 7. 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 there 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

VI. CONCLUSION AND PERSPECTIVES

In this paper we use the notion of interaction network of amino acids of a protein (SSE-IN) and study some of the properties of these networks. The main advantage of this model is that it allows to cope with different biological problems related to protein structure using graph theory tools. Ignoring details, such as the type and the exact position of each amino acid, this abstract and compact description allows to focus on the interactions' structure and organization. The subnetworks corresponding to secondary structure elements satisfy the properties of the small-world network model. Small-world networks are widely studied and their properties are well identified. These properties can give insight on the formation of SSEs. On the other hand, the links between these subnetworks describe the interactions between different SSEs, which determine the tertiary protein structure.

We have studied the growth of the characteristic path length and the clustering coefficient for networks where each node represents an amino acid, but also for the generalized networks where each node corresponds to a SSE. We have found an alternative way to verify if a protein network verifies the small world properties.

A short term perspective is to give a finer characterization of shortcut edges in order to better understand how different SSEs are linked to each other. Another direction would be to see what are the specific biological properties of the proteins which satisfy the small world properties. As a long term perspective, 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. 1 .

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

Fig. 2 .

 2 Fig. 2. Protein 1DTP (top) and its SSE-IN (bottom)

Fig. 3 .Fig. 4 .Fig. 5 .

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

Fig. 6 .Fig. 7 .

 67 Fig. 6. Average connected component size (top) and shortcut ratio (bottom) as a function of protein SSE-In size

Fig. 8 .Fig. 9 .

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

TABLE I STRUCTURAL

 I CLASSES STUDIED FOR THE SMALL-WORLD PROPERTIES. WE CHOOSE ONLY FAMILIES WITH MORE THAN 100 PROTEINS. THE TOTAL NUMBER OF STUDIED PROTEINS IS 18294.

	Class	Number of	Number of
		families	Proteins
	All α	12	2968
	All β	17	6372
	α/β	18	5197
	α + β	16	3757


Omar Gaci

Stefan Balev

Motif Prediction in Amino Acid Interaction Networks

Keywords: interaction network, protein structure, genetic algorithm

In this paper we represent a protein as a graph where the vertices are amino acids and the edges are interactions between them. We propose a genetic algorithm of reconstructing the graph of interactions between secondary structure elements which describe the structural motifs. The performance of our algorithms is validated experimentally.

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 paper we identify some of the properties of the network of interacting amino acids. We believe that understanding these networks can help to better understand the folding process.

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 * Le Havre University, LITIS EA 4108, BP 540, 76058 Le Havre -France, email: {Omar.Gaci, Stefan.Balev}@univ-lehavre.fr 3 we introduce our model of amino acid interaction networks. In section 4 we propose a genetic algorithm of reconstructing the graph of interactions between secondary structure elements. 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 20-letter 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].

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 Å 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. 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][START_REF] Atilgan | Small-world communication of residues and significance for protein dynamics[END_REF][START_REF] Dokholyan | Topological determinants of protein folding[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.

Motif 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. To fold a SSE-IN, 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. In this paper, we use the same approach: to fold a SSE-IN we limit the toplogical space by associating a strucutral family to a sequence [START_REF] Gaci | Prediction of protein families by topological inference[END_REF]. Since the strucutral motifs which describe a strucutral family are limited, we propose a genetic algorithm (GA) to enumerate all possibilities.

In this section, we present a method based on a GA to predict the graph whose vertices represent the SSE and edges represent spatial interactions between two amino acids involved in two different SSE, further this graph is called Secondary Structure Interaction Network (SS-IN), see Fig

Thereafter, we use a dataset composed by proteins which have not fold families in the SCOP v1.73 classification and for which we have predicted a family in [START_REF] Gaci | Prediction of protein families by topological inference[END_REF].

Overall description

Our GA works on a population of proteins which have the same number of SSE as the studied sequence. The initial population is composed of the proteins of the predicted family with the same number of SSE. Each individual of the population has associated SS-IN adjacency matrix.

At each iteration we apply genetic operators in order to obtain new individuals with new adjacency matrices. Our fitness function does not use a measure based on the adjacency matrices, it is based only on the SSE sizes.

Genome structure

The genome structure of a protein SS-IN is an array of alleles. Each allele represents a SSE notably considering its size that is the number of amino acids which compose it. The size is normalized contributing to produce genomes whose alleles describe a value between 0 and 100. Obviously, the position of an allele corresponds to the SSE position it represents in the sequence, see Fig 4.

In the same time, for each genome we associate its SS-IN incidence matrix. Figure 5: The distance between two chromosomes is the sum of distances between the alleles, in this case (32+92+58+24+58).

Fitness function

We evaluate the performance of a chromosome by using the L 1 distance between this chromosome and the target sequence. An example is given in Fig 5.

Crossover operator

This operator uses two parents to produce two children.

After generating a random cut position, we swap the both parts as shown in Fig 6 . Nevertheless, this operator can produce incidence matrices which are not compatible with the fold family, we discuss this problem below.

Mutation operator

This operator is used for a small fraction (about 1%) of the generated children. It modifies the chromosome and the associated matrix. For the chromosomes, we define two operators: the two position swapping and the one position mutation. Concerning the associated matrix, we define four operators: the row translation, the column translation, the two position swapping and the one position mutation. The crossover and mutation operators may produce matrices which describe incoherent SS-IN compared to the predicted sequence fold family. To eliminate the wrong cases we develop a topological operator.

Topological operator

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 there exists a parallel between biological classification (notably the SCOP fold family level) and the SSE-IN topological properties. Here we exploit these properties to exclude the incompatible children generated by our GA. The principle is the following, we have predicted a fold family for the sequence from which we extract an initial population of chromosomes. Thus, we compute the diameter, the characteristic path length and the mean degree to evaluate the average topological properties of the family for the particular SSE number. Then, after the GA generates a new individual by or mutation, we compare the associated SS-IN matrix with the properties of the initial population by admitting an error rate up to 20%. If the new individual is not compatible, it is rejected.

Algorithm implementation

Starting from an initial population of chromosomes from the predicted family, our algorithm modifies the population using the genetic operators defined above. The process is stopped when the fitness of the population stops increasing between two iterations, see Algorithm 1.

The genetic process is the following: after the initial population is built, we extract a fraction of parents according to their fitness and we reproduce them to produce chil-dren. Then, we select the new generation by including the chromosomes which are not among the parents plus a fraction of parents plus a fraction of children. It remains to compute the new generation fitness. As a side effect, their associated matrices are supposed to be close to the adjacency matrix of the studied protein.

In order to test the performance of our GA, we pick randomly three chromosomes from the final popualtion and we compare their associated matrices to the sequence SS-IN adjacency matrix. To evaluate the difference between two matrices, we use an error rate defined as the number of wrong elements divided by the size of the matrix.

Conclusions and Future Work

In this paper, we are interested in the way the SSEs interact. We propose a genetic algorithm trying to construct the interaction network of SSEs (SS-IN). The GA starts with a population of real proteins from the predicted family. To complete the standard crossover and mutation operators, we introduce a topological operator which excludes the individuals incompatible with the fold family.

The GA produces SS-IN with maximum error rate about 25% in the general case. The performance depends on the number of available sample proteins from the predicted family, when this number is greater than 10, the error rate is below 15%.

The next step would be to use the SS-IN prediction in order to build the interaction graph of the target sequence in amino acid level (SSE-IN).

The characterization we propose constitutes a new approach to the protein folding problem. The properties identified here, but also other properties we studied [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], 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.

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).

  Fig 2 gives an example of a protein and its SSE-IN.

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: Building the chromosome representation for the unclassified protein 2OUF.

Figure 6 :

 6 Figure 6: The crossover operators for the chromosomes (top) and for the associated matrix (bottom).

Algorithm 1 :

 1 Genetic algorithm for SS-IN adjacency matrix determination. Data: pop: Current chromosome population parents: Set of parents children: Set of children begin pop ←-setInitialPopulation(); while fitness(pop) is increasing do parents ←-parentExtraction(pop); children ←-parentCrossing(parents); children ←-childrenMutation(children) ; children ←-exclusionByTopology(children); pop ←-selection(pop, children); end 4.8 Algorithm performance At the end of our GA, the final population contains individuals close to the target protein in terms of SSE length distribution because of the choice of our fitness function.

Figure 7 :

 7 Figure 7: The dataset we use is composed by 698 proteins from the All alpha class (top) and by 413 proteins from the All beta class (bottom).

Figure 8 :

 8 Figure 8: Error rate as a function of the initial population size. When the initial size is more than 10, the error rate becomes less than 15%.

  The dataset we use is composed of 698 proteins belonging to the All alpha class and 413 proteins belonging to the All beta class, seeFig 7.

	The average error rate for All alpha class is 16.7% and
	for All beta class it is 14.3%. The maximum error rate is
	25%. As shown in Fig 8, the error rate strongly depends
	on the initial population size. Indeed, when the initial
	population contains sufficient number of individuals, the
	genetic diversity ensures better SS-IN prediction. When
	we have sufficient number of sample proteins from the
	predicted family, we expect more reliable results. Note
	for example that when the initial population contains at
	least 10 individuals, the error rate is always less than
	15%.