Utilisation de la dominance pour l'identification de familles protéiques

Résumé : L'identification des familles protéique est un challenge de la biologie computationnelle qui nécessite des méthodes efficaces et robustes. Nous introduisons ici le concept de dominance entre instance de comparaison de structures prot'eiques, et proposons une nouvelle approche basée sur DAST (Distance Alignment Search Tool), un algorithme exact auquel nous rajoutons des bornes. Les résultats obtenus montrent que notre méthode résout correctement le problème de l'identification des familles protéique sans avoir besoin de résoudre toutes les instances de comparaison de structures.

Mots-clés : Comparaison de structure protéique, classification, bornes, dominance

Introduction

The 3D structure of macro-molecules underpins all biological functions. Similarities between protein structures may come from evolutionary relationships [START_REF] Orengo | Protein families and their evolutiona structural perspective[END_REF][START_REF] Koehl | Protein structure similarities[END_REF], and similar protein structures relate to similar functions. Thus, the protein structure comparison is a key tool in structural biology, whose primary goal is to understand function through structure. During the last decades, many protein structure comparison approaches have been proposed, each aiming at quantifying the intuitive notion of structural similarity. Most of the proposed methods are either based on optimal rigid-body superimposition (like VAST [START_REF] Gibrat | Surprising similarities in structure comparison[END_REF] or STRUCTAL [START_REF] Gerstein | Using iterative dynamic programming to obtain accurate pair-wise and multiple alignments of protein structures[END_REF]), whose computation is based on the least Root Mean Square Deviation of residue coordinates (RM SDc) as first defined by Kabsch [START_REF] Kabsch | A discussion of the solution for the best rotation to relate two sets of vectors[END_REF], or on the comparison of the internal distances between the residues (like DALI [START_REF] Holm | Protein structure comparison by alignment of distance matrices[END_REF]), CMO [START_REF] Godzik | Flexible algorithm for direct multiple alignment of protein structures and seequences[END_REF] or DAST [START_REF] Malod-Dognin | Maximum clique in protein structure comparison[END_REF]). The main challenge in protein structure comparison is to design efficient algorithms, since the comparison of two protein structures is often NP-complete, as first shown in [START_REF] Lathrop | The protein threading problem with sequence amino acid interaction preferences is np-complete[END_REF].

DAST

DAST (Distance-based Alignment Search Tool) is a protein structure comparison method based on internal distances [START_REF] Malod-Dognin | Maximum clique in protein structure comparison[END_REF]. In DAST, two proteins p 1 and p 2 are represented by their ordered sets of residues N 1 and N 2 . The matching between residues i ∈ N 1 and k ∈ N 2 , denoted by i ↔ k, is allowed only if i and k come from the same kind of secondary structure (i.e. if either i and k both come from α-helices, or both come from β-strands, or both come from loops).

By assumption, for any pair of residues i and j from the same protein we know the euclidean distance between their α-carbons (denoted here by d ij ).

Definition 1. Pair (i, j) from p 1 is compatible with pair (k, l) from p 2 if and only if: (1) i < j and k < l (order preserving) and ;

(2) |d ij -d kl | ≤ τ , where τ is a given distance threshold (isometric relationship).

If (i, j) is compatible with (k, l) we are allowed to match (align) i ↔ k and j ↔ l (i.e. they form a matching pair). An optimal structural alignment is given by the longest sequence of matching pairs "i 1 ↔ k 1 , i 2 ↔ k 2 , . . . , i t ↔ k t " in which any two matching pairs are compatible. As shown in section 3.2, DAST is equivalent to solving a maximum clique problem and is thus is an NP-Complete problem [START_REF] Karp | Reducibility among combinatorial problems[END_REF]. Set ncr (number of common residues) to denote the length of the optimal alignment between p 1 and p 2 . Two similarity scores can be used:

S G DAST (p 1 , p 2 ) = 2 × ncr |N 1 | + |N 2 | and S L DAST (p 1 , p 2 ) = ncr min(|N 1 |, |N 2 |) . (1)
The first score, S G DAST (p 1 , p 2 ), is normalized according to the mean of two proteins and is oriented to detect global similarity between p 1 and p 2 . The second one, S L DAST (p 1 , p 2 ), is normalized according to the smallest between the two proteins and is more suitable to detect local similarity.

Conceptually, DAST is inspired from the CMO approach which has been largely studied in the literature [START_REF] Godzik | Flexible algorithm for direct multiple alignment of protein structures and seequences[END_REF][START_REF] Caprara | optimal pdb structure alignments: integer programming methods for finding the maximum contact map overlap[END_REF][START_REF] Andonov | Maximum contact map overlap revisited[END_REF]. Both approaches aim to maximize the number of compatible matching pairs. However, the CMO compatibility does not consider the isometric condition from definition 1. As a consequence, the underlying optimization problems, the behavior of the corresponding solvers, as well as the characteristics of the provided alignments differ in both approaches. The most interesting feature of DAST is that it always returns an alignment (matching) of good quality, i.e. having a Root Mean Squared Deviation of internal distances (RM SD d ) which is less or equal than the given threshold τ (see [START_REF] Malod-Dognin | Maximum clique in protein structure comparison[END_REF]). This property is not guaranteed in CMO. On the other hand, a very efficient exact algorithm for finding the longest augmented path (the optimization problems in CMO) has been recently proposed in [START_REF] Andonov | Maximum contact map overlap revisited[END_REF]. The associate solver, A_purva, is significantly faster than the nowadays maximum cardinality clique solvers. These issues will be discussed and illustrated in the computational results section.

The protein family identification problem

The exponential growth of the number of known protein structures in the Protein Data Bank [START_REF] Berman | The protein data bank[END_REF] over the past decade led to the problem of protein classification. We mean here how to automatically insert new protein structures into an already existing classified database such as CATH [START_REF] Orengo | Cath -a hierarchic classification of protein domain structures[END_REF] or SCOP [START_REF] Andreeva | Data growth and its impact on the scop database: new developments[END_REF]. The problem of determining in which classes new structures belong, referred here as the Protein Family Identification Problem , can be defined as follows.

Definition 2. Given a set of to-be-classified query protein structures Q = {q 1 , q 2 , . . . ,q m }, a set of classified target protein structures P={p 1 , p 2 , . . . , p n }, and a protein structure similarity function S : Q × P → R + , the Protein Family Identification Problem (FIP) consists in classifying each query structure q i ∈ Q in the class of it's nearest neighbor N N i which is defined as N N i = argmax pj ∈P S(q i , p j ).

There are computational pitfalls in the FIP . The number of similarity scores S(q i , p j ) that need to be computed is |Q| × |P|, where |P| can be very large (there are currently 152920 classified protein structures in the expert classification CATH). Moreover, computing a single similarity score is often equivalent to solving a NP-hard problem (ex: DALI, DAST, CMO, VAST, etc...). Depending on how these NP-hard problems are solved, two cases are possible. First, if the solver is a heuristic (ex: DALI, VAST), then the similarity scores are only approximated, and thus the resulting classification is not optimal (according to the similarity function). Second, if the solver is exact (ex CMO, DAST), and because of the NP-hardness of the problem, some instances cannot be optimally solved within reasonable time, leading to either sub-optimal or to missing similarity scores, both implying that the obtained classification is not optimal, or cannot be computed if too many similarity scores are missing.

In this paper, we propose a notion of dominance between the protein structure comparison instances that allows the computation of optimal protein structure classifications without optimally solving all the comparison instances, and thus reduces the effect of the NP-Hardness of the similarity score. As presented in section 2, using dominance supposes to compute both upper and lower bound on the similarity score. In section 3.3, we propose an efficient bounding strategy for DAST.

Dominance

The idea behind the dominance is that in FIP problem, given a query protein structure q ∈ Q and a classified set of target protein structures P = {p 1 , p 2 , . . . , p n }, we are interested only in finding the nearest neighbor of q in P, i.e. N N q = argmax pj ∈P S(q, p j ). If a protein structure p j can be proved not to be N N q before S(q, p j ) is optimally computed, then spending more time on proceeding S(q, p j ) is useless.

Let us suppose that the solving process can be stopped with a time limit t, and can then return both a lower-bound S min (q, p i ) and an upper-bound S max (q, p i ) on the similarity score S(q, p i ), i.e S min (q, p i ) ≤ S(q, p i ) ≤ S max (q, p i ) (if the instance is optimally solved, then S min (q, p i ) = S(q, p i ) = S max (q, p i )). Definition 3. Given a query q ∈ Q and two target protein structures p 1 ∈ P and p 2 ∈ P, the instance (q, p 2 ) dominates the instance (q, p 1 ) if S min (q, p 2 ) ≥ S max (q, p 1 ).

If the instance (q, p 2 ) dominates the instance (q, p 1 ), then S(q, p 2 ) ≥ S(q, p 1 ). Thus, p 1 is not the nearest neighbor of q and there is no need to continue computing S(q, p 1 ). Moreover, if one instance (q, p i ) dominates all the other instances (q, p j ), p j ∈ P, then N N q = p i , and the entire procedure can be stopped (including the instance (q, p i )).

From now on, we use the dominances to fasten the FIP as follows.

1. All instances (q i , p j ), q i ∈ Q, p j ∈ P are put in a queue, and a time limit argument t is set to a small value.

2. For each instances (q i , p j ) in the queue, the similarity S(q i , p j ) is evaluated (by computing S min (q i , p j ) and S max (q i , p j )) within the time limit t.

3. All dominated instances are removed from the queue. If an instance (q i , p j ) dominates all the other instances (q i , p k ), p k ∈ P, then the nearest neighbor of q i is set to p j , and the instance (q i , p j ) is also removed from the queue.

4. If the queue is empty, then the nearest neighbors of all the queries have been found and the FIP is optimally solved. Otherwise, the time limit t is increased, and steps 2 to 4 are repeated until the queue is empty.

Modifying DAST for using dominance

Using dominances supposes that the solution process can return upper and lower-bounds on the similarity score. Unfortunately, as presented in [START_REF] Malod-Dognin | Maximum clique in protein structure comparison[END_REF], DAST does not possess such features. This section presents how these bounds were added into DAST. First, in sections 3.2, we briefly recall DAST principle. Then, in section 3.3, we present our bounding strategy.

Notation and definitions

Let us first introduce some notations and definitions coming from [START_REF] Andonov | Maximum contact map overlap revisited[END_REF] and [START_REF] Malod-Dognin | Maximum clique in protein structure comparison[END_REF].

RR n°7688

Definition 4. A m × n alignment graph G = (V, E) is a graph in which the vertex set V is depicted by a (m-rows) × (n-columns) array T , where each cell T [i][k] contains at most one vertex i.k from V (note that for both arrays and vertices, the first index stands for the row number, and the second for the column number). Two vertices i.k and j.l can be connected by an edge (i.k, j.l) ∈ E only if i < j and k < l. An example of such alignment graph is given in the figure 1:Right.

Definition 5. Given graph G = (V, E), a clique is a subset S of V such that for any two vertices u ∈ S and v ∈ S, u = v, u and v are connected by an edge (u, v) in E.

Definition 6. The maximum clique problem consists in finding in a graph G = V, E a largest (in terms of vertices) clique, denoted by M CC(G). The maximum clique problem is one of the first shown to be NP-complete [START_REF] Karp | Reducibility among combinatorial problems[END_REF].

In a n × m alignment graph G = (V, E), the subset of V restricted to the vertices in the rows j > i and in the columns l > k is denoted by V i.k . Similarly, V i.k is the subset of V restricted to the vertices in the rows j, 0 ≤ j ≤ i and in the columns l, 0 ≤ l ≤ k. The subgraph of G induced by the vertices in V i.k is denoted by G i.k , and the subgraph of G induced by the vertices in V i.k is denoted by Ĝi.k . The vertex j.l is a successor of the vertex i.k if i < j, k < l and edge (i.k, j.l) is in E, and the set of successors of a vertex i.k is denoted by

Γ + (i.k). The vertex a.b is a predecessor of the vertex i.k if a < i, b < k and edge (a.b, i.k) is in E,
{i 1 .k 1 , i 2 .k 2 , . . ., i t .k t } of V , such that ∀j ∈ [1, t-1], i j < i j+1 , k j < k j+1 . LIS(G) is the longest, in terms of vertices, increasing subset of vertices of G. Definition 8. An increasing path in an alignment G = {V, E} is an in- creasing subset of vertex {i 1 .k 1 , i 2 .k 2 , . . ., i t .k t } such that ∀j ∈ [1, t -1], (i j .k j , i j+1 .k j+1 ) ∈ E. The longest, in terms of vertices, increasing path in G is denoted by LIP (G) Lemma 1: |M CC(G)| ≤ |LIP (G)| ≤ |LIS(G)|. Proof:
Since any two vertices in a clique are adjacent, definition 4 implies that a clique in G is both an increasing subset of vertices and an increasing path, thus

|M CC(G)| ≤ |LIP (G)|. Moreover, LIP (G) is by definition an increasing subset of vertices, which implies that |LIP (G)| ≤ |LIS(G)|.

Maximum clique formulation of DAST

DAST is rephrased as a maximum clique problem in an alignment graph as follows. Let G be a |N 1 | × |N 2 | alignment graph, where each row corresponds to a residue of N 1 and each column corresponds to a residue of N 2 . A vertex i.k is in V only if residues i ∈ N 1 and k ∈ N 2 both come from the same kind of secondary structure (i.e. if matching i ↔ k is possible). An edge (i.k, j.l) is in E if and only if (i) i < j and k < l, for order preserving, and (ii) if |d ij -d kl | ≤ τ . As illustrated in figure 1, an optimal matching between two protein structures p 1 and p 2 corresponds to a maximum clique in G. For example the maximum clique {(1.1), (2.2), (3.3)} in figure 1:Right corresponds to the optimal matching between residues (1, 2, 3) from p 1 and residues (1, 2, 3) from p 2 .

Bounding strategy

Both DAST similarity scores 1 use ncr, the number of common residues, which is equal to |M CC(G)|. Thus, bounding DAST score is equivalent to provide a lower and upper-bound on the cardinality of the maximum clique in G, when the time limit t is reached. The case of the lower-bound is trivial, since the best clique found so far, Best, is by definition a lower-bound of ncr. Computing an efficient upper-bound on |M CC(G)| is less straightforward.

Intermediate state of execution

As explained in [START_REF] Malod-Dognin | Maximum clique in protein structure comparison[END_REF], the maximum clique solver of DAST visits the vertices of V in decreasing order of column (first) and decreasing order of row (second). For each visited vertex i.k, the clique solver computes (or upper-bounds) the maximum clique in G i.k . If a clique larger than the current best one (Best) is found, then Best is updated. Finally, an array C is used to store, in each entry C[i][k], the upper-estimated size of the maximum clique in G i.k . This array is later used to fasten the maximum clique computation starting from a vertex having lower row and column indexes, and this implies that computation of

C[i][k] requires that C[i + 1][j], C[i + 1][j + 1] and C[i][j + 1] are already computed. Since the evaluation of a given cell T [i][k] (i.e. the computation of C[i][k]) only occurs after C[i + 1][j], C[i + 1][j + 1] and C[i][j + 1]
have been computed, an intermediate state of execution of DAST can be represented as in figure 2. In such intermediate state, the cells of T can be split in the following way.

• Cells in which C[i][k] has already been evaluated will be referred to as evaluated cells. They correspond to the horizontally striped area in Figure 2:Left. The current best clique, Best, has been found in this set. have not yet been evaluated will be referred to as unevaluated cells.

RR n°7688

• Unevaluated cells which are adjacent to an evaluated cell (either side-wise or diagonally) will be referred to as boundary cells, and are shown in black in

Upper bounding strategy

It is important to remember that in an intermediate state of execution, even if the possible contribution of a given vertex i.k into a maximum clique of G is completely unknown if i.k lies in the unevaluated region, the contribution of i.k in a maximum clique in G i.k is tightly estimated by C[i][k] if the vertex lies in the evaluated region. Here, we propose an upper-bound on |M CC(G)| that takes advantages of this property. We define G i.k L , hereafter referred to as local induced subgraph, as the subgraph of G induced by the vertex set

V i.k L = V i+1.k+1 ∪ V i.k . Figure 2:Right, describes G i.k
L where i.k is the black square. Lemma 2: For any unevaluated cell T [i][k] and any evaluated cell T [j][l] such that i < j and k < l, there exists a boundary cell T [p][q] such that i ≤ p < j and k ≤ q < l.

Proof: Consider the rectangle R ⊂ T induced by cells

T [i][k] and T [j][l] (R = {T [a][b] such that i ≤ a ≤ j and k ≤ b ≤ l}). By definition, R contains both unevaluated (at least T [i][k]
) and evaluated cells (at least T [j][l]), so there exists an unevaluated cell T [p][q] ∈ R, which is adjacent to an evaluated cell, and since T [p][q] ∈ R, then i ≤ p < j and k ≤ q < l.

Lemma 3:

M CC(G) = max i.k|T [i][k] is boundary M CC(G i.k L )
, and thus

M CC(G) = max i.k|T [i][k] is boundary M CC(G i.k L )
Proof: Proving Lemma 3 is equivalent to proving that the maximum clique lies in one of the local induced subgraphs of G that is induced by a boundary cell. Toward this goal, we will assume that we are in an intermediate state of execution, which implies that T

[1][1] is an unevaluated cell and that T [m][n] RR n°7688
has been evaluated (where m = number of rows in G, n = number of columns in G).

Any clique K in an alignment graph G is an increasing subset of vertices, namely, K = {i 1 .k 1 , i 2 .k 2 , . . . , i |K| .k |K| }, where i l < i l+1 and k l < k l+1 for all 1 ≤ l < |K|. To prove that K lies completely inside one locally induced subgraph, we instead prove that K = {i 0 .k 0 , i 1 .k 1 , . . . , i |K| .k |K| , i |K|+1 .k |K|+1 } lies completely inside one locally induced subgraph, where i 0 .k 0 = 1.1 and i |K|+1 .k |K|+1 = m.n. Since K intersects with both the evaluated and the unevaluated region, there exists l, such that vertices i 0 .k 0 , i 1 .k 1 , . . . , i l .k l lie in the unevaluated region and vertices i l+1 .k l+1 , . . . , i |K| .k |K| , i |K|+1 .k |K|+1 lie in the evaluated region. By invoking Lemma 2 with i = i l , k = k l , j = i l+1 , l = k l+1 , we obtain that there exists a boundary cell T [p][q] such that i l ≤ p < i l+1 and k l ≤ q < k l+1 . Thus, K and hence the clique K lies entirely in the local induced subgraph induced by the boundary cell T

[p][q].
Since any clique in G i.k L implicitly defines a clique over V i.k (that is in the unevaluated region) and another clique over

V i+1.k+1 (that is in the evaluated region), M CC(G i.k L ) ≤ M CC( Ĝi.k ) + M CC(G i+1.k+1 ). Then, |M CC(G)| is upper-bounded by: M CC(G) = max i.k|T [i][k] is boundary M CC( Ĝi.k ) + M CC(G i+1.k+1 ), (2)
where Computing all |LIP ( Ĝi.k )|) can be done in O(n 2 × m 2 ) time using the algorithm presented in [START_REF] Malod-Dognin | Maximum clique in protein structure comparison[END_REF]. Moreover, there are no more than n + m boundary cells in T . The global upper-bound M CC(G) can be either computed once when the time limit is attained, or also can be maintained at each execution step for the need of branch and bounds strategy.

M CC(G i+1.k+1

Computational Results

All presented results were obtained on a cluster under Linux RedHat Enterprise 5 architecture 64 Bits, 64 GB RAM, 2.8GHZ Intel Xeon. The efficiency of the dominance strategy for solving FIP was evaluated through two benchmarks. We tackled the FIP problem using the following protocol: any of the proteins has been considered as a query, then removed from the dataset and compared with the remaining proteins in order to find its family based on its nearest neighbor.

First, we used Skolnick set, described in [START_REF] Caprara | optimal pdb structure alignments: integer programming methods for finding the maximum contact map overlap[END_REF]. It is a popular benchmark that contains 40 protein domains having from 97 to 256 residues and classified in SCOP (v1.73) into five families. The second benchmark comes from 3D SHape Recognition Contest 2010 (SHREC'10) [START_REF] Mavridis | Shrec-10 track: Protein models[END_REF] and consists of 50 query protein structures and 1000 target protein structures, all classified into 100 superfamilies in the CATH classification. The goal of this contest was to identify the family of each query. Identifying the 50 queries implies solving 50000 comparison instances. The best results have been obtained by the structure comparison tool A_purva [START_REF] Andonov | Maximum contact map overlap revisited[END_REF]. We will us it to compare with the results of DAST. Table 1: Three steps of the FIP computation over the Skolnick set. We use the following abbreviations: # ins -number of instances proceeded for the given lapse of time T (in seconds); # sol_ins -number of solved instances; # uns_ins -number of unsolved (unclassified) instances; # dom_ins -number of dominated instances when using DAST b and dominance; # ins_left -number of instances to reload; # ass_q -number of assigned (classified) queries.

RR n°7688

DASTa

DAST on Skolnick set

Running time comparison

Computing the upper-bound at each intermediate state slowdowns the solving process. DAST a (without bounds computation) solves more instances than DAST b (with upper-bounds computation) when both methods are given the same distance threshold and the same time limit. For example, for a threshold of 3 Å and when the running time was bounded by 2 seconds per instance DAST a solved 506 instances, versus 338 for DAST b (i.e. DAST a is about 1.5 times faster than DAST b ). However, as we will see below, the advantages of DAST b for solving FIP using the dominances recompense notably this slowdown.

Solving FIP without dominance

Classifying all proteins from the Skolnick set without dominances (i.e. using DAST a ) requires solving 1560 instances. As shown in Table 1 when the running time was bounded by 2 seconds per instance, 1054 instances remained unsolved and none of the query could be assigned. Table 1 presents the evolution of the number of solved instances by DAST a with different time limits. Even with the larger time limit that we used (one hour per instance), 21 instances remained unsolved. The whole computation time was about 15 days, and all of the 29 queries that could be classified were correctly classified.

Solving FIP with dominance

As mentioned above, when the execution time was bounded by two seconds per instance, DAST b solved only 338 over 1560 instances. However, by applying the dominance relation, 29 queries where correctly assigned into their family by the nearest neighbor measure. Only 137 instances required further processing in order to complete the analysis. These instances were then reloaded with a larger time limit and this process was repeated until the family identification was fully completed. Table 1 details the 3 steps that were needed for Skolnick set. The entire computation time was about 5 hours and 45 minutes. So we observe that DAST b is significantly faster than DAST a when solving FIP. Moreover, using the dominance relations guarantees that the exact nearest neighbor is found without solving all instances, which is not true for DAST a , neither for any algorithm that does not provide bounds.

DAST b versus A_purva on SHREC'10 set

A_purva is an exact solver based on Contact Map Overlap maximization (CMO) similarity measure [START_REF] Andonov | Maximum contact map overlap revisited[END_REF][START_REF] Malod-Dognin | Comparing protein 3d structures using a_purva[END_REF] 1 . It has been shown to be both efficient (notably faster than the previous exact algorithms), and reliable (providing accurate upper and lower bounds of the solution). A_purva is based on an integer programming formulation of CMO, and it converges to the optimal solution using a branch and bound strategy. At each node, A_purva provides two numbers derived from a Lagrangian relaxation: a lowerbound LB and an upperbound U B of the maximum number of common contacts (ncc). When an instance is optimally solved, the relation LB = U B holds. Otherwise, U B > LB and the so called relative gap value RG = (U B -LB)/U B gives the precision of the results. This property is very useful in the context of large-scale database comparisons where the execution time is usually bounded. The above properties make A_purva applicable for large-scale protein comparison and classification. Since it is an exact solver, it is often used to evaluate the quality of various heuristic approaches [START_REF] Di | Fast overlapping of protein contact maps by alignment of eigenvectors[END_REF][START_REF] Shibberu | A spectral approach to protein structure alignment[END_REF].

In this section, we compare DAST b with A_purva when solving FIP on SHREC'10 set. Both tools provide the best local matching (alignment) between proteins p 1 and p 2 in their corresponding feasible sets (compatible matching pairs), and according to their specific objective functions-maximum number of isometric pairs of amino-acids for DAST and, respectively, maximum number of common contacts for A_purva. On SHREC'10 dataset DAST b was more precise than A_purva. This can be explained by the isometric constraint in definition 1. Table 2 presents the different steps of this process. A_purva assigned all the 50 queries, 46 of them were correctly predicted according to the CATH classification. However, A_purva failed for the queries 1tteA02, 1wwjA00, 1jftA01 and 3bioA02. DAST b also assigned 50 queries and correctly predicted 49 of them (DAST failed for 3bioA02). Furthermore, A_purva was significantly faster than DAST b (the corresponding total running time on SHREC'10 benchmark dataset was 28 hours versus 60 days).

Neither of the methods correctly classified the query 3bioA02. A_purva and DAST found two nearest neighbors from different families with similarity scores of 0.6059 and 0.2 respectively. These low values of DAST similarity score indicate that there is no true nearest neighbor for it in SHREC'10 data set. We contacted an expert from the domain2 who confirmed the CATH classification of 3bioA02 and suggested us to study its similarity with protein 1f06. As a consequence, we observed that adding the domain 1f06A02 to SHREC'10 dataset allows to assign the query 3bioA02 correctly (i.e. SHREC'10 data set is not enough representative).

Figure 3 visualizes the alignments provided by A_purva and DAST for the query 1tteA02 which was wrongly predicted by A_purva but was correctly identified by DAST with 1ixrB03 as its nearest neighbor. Aiming to maximize the number of common contacts, A_purva matched non-isometric residues in the middle loop and at both ends. On the contrary, DAST matched closed substructures only (here the three helices of 1tteA02) and ignored the middle loop and extremities. For comparison purpose we also present here the alignment given by TM-align-well know protein structure comparator [START_REF] Zhang | Tm-align: a protein structure alignment algorithm based on the tm-score[END_REF]. The TM-align alignment is very similar the DAST alignment.

Towards a combined tool These results led us to propose a combined strategy for protein family identification. It uses the normalized RM SDc, defined as N RM SDc = RM SDc length(Query) . First we ran A_purva on SHREC'10 set and computed the corresponding N RM SDc values. We observed that they were higher than 0.1 only for four instances (query,NN)-an indication for a strong deviation between the corresponding structures. For all other instances the N RM SDc value was obviously smaller, less than 0.05. We also realized that these four instances correspond to the four wrongly predicted by A_purva couples (query-NN). Then DAST b was executed for these four queries only (it required computing new 4000 instances). This combined strategy achieved an accuracy of 50/50 correctly assigned queries (better than any of DAST or A_purva results) but for much less computational time than DAST running time.

RR n°7688

Conclusion and future work

In this paper we enrich the local structure comparator tool DAST with bounds. This permits to use it in the context of a new dominance relation. The last one is very useful for the protein family identification problem since avoids solving all instances. Moreover, this relation is applicable to any NP-complete comparison methods and can be used for solving the FIP or for clustering large sets of protein structures.

  and the set of predecessor of a vertex i.k is denoted by Γ -(i.k). The maximum clique in a graph G is denoted by M CC(G), and its cardinality is denoted by |M CC(G)|. An upper-bound on |M CC(G)| is denoted by |M CC(G)|. Definition 7. An increasing subset of vertices in an alignment graph G = {V, E} is an ordered subset

Figure 1 :

 1 Figure 1: Left: An optimal matching (represented by the arrows) between protein 1 and 2, when using a distance threshold of 1Å. Right: the corresponding maximum clique in the |N 1 | × |N 2 | alignment graph.

Figure 2 :

 2 Figure 2: Left: An intermediate state of DAST computation; Right: G i.k L

Figure 2 :

 2 Left. The unevaluated cells for which C[i][k] can be computed (i.e. for which C[i + 1][j], C[i + 1][j + 1] and C[i][j + 1] are already computed), belong by definition to the subset of the boundary cells, and are marked with a white square in Figure 2:Left. Finally, unevaluated cells that are not boundary cells are shown as vertically striped.

  ) is tightly estimated by C[i+1][k+1], and where M CC( Ĝi.k ) is estimated in a preprocessing step by using the longest increasing path in Ĝi.k (i.e. M CC( Ĝi.k ) = |LIP ( Ĝi.k )|).

Figure 3 :

 3 Figure 3: The instance 1ixrB03-1tteA02 aligned by A_purva (left), DAST (center) and TM-align (right). The parameters for DAST were τ = 5.0Å and sse1(filter 1). The length of the associated alignment, (len_align), as well as the corresponding RMSDc and TM-score are given. We observe that A_purva matches as much as possible residues, while DAST and TM-align focuse on the local similar structures only.

1 . 2 2 5 3 3 . 1 3 . 2 3 . 3 11 5

 122531323311 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 The protein family identification problem . . . . . . . . . . . . . 4 Dominance Modifying DAST for using dominance 5 Notation and definitions . . . . . . . . . . . . . . . . . . . . . . . 5 Maximum clique formulation of DAST . . . . . . . . . . . . . . . 6 Bounding strategy . . . . . . . . . . . . . . . . . . . . . . . . . . 7 3.3.1 Intermediate state of execution . . . . . . . . . . . . . . . 7 3.3.2 Upper bounding strategy . . . . . . . . . . . . . . . . . . 8 4 Computational Results 9 4.1 DAST on Skolnick set . . . . . . . . . . . . . . . . . . . . . . . . 10 4.1.1 Running time comparison . . . . . . . . . . . . . . . . . . 10 4.1.2 Solving FIP without dominance . . . . . . . . . . . . . . . 10 4.1.3 Solving FIP with dominance . . . . . . . . . . . . . . . . 10 4.2 DAST b versus A_purva on SHREC'10 set . . . . . . . . . . . . Conclusion

Table 2 :

 2 Number of dominated instances, of instances to reload and of assigned queries at each of the three steps of the FIP computation over the SHREC'10 set when using dominance, for both DAST b and A_purva

		A_purva	DAST	TM-align
	len_align	53	43	45
	cRMSD	5.35	2.37	2.71
	TM-score	0.43	0.51	0.53

RR n°7688

A_purva is available at http://apurva.genouest.org

Alexey Murzin from the Laboratory of Molecular Biology, Cambridge RR n°7688

Acknowledgements

Thanks to Inken Wohlers from CWI for discussions and suggestions. R. Andonov is supported by BioWIC ANR-08-SEGI-005 project. All computations were done on the Ouest-genopole bioinformatics platform (http://genouest.org).


Gilles Vanwormhoudt
email: gilles.vanwormhoudt@lifl.fr

Areski Flissi
email: areski.flissi@lifl.fr

Session-Based Role Programming for the Design of Advanced Telephony Applications

Stimulated by new protocols like SIP, telephony applications are rapidly evolving to offer and combine a variety of communications forms including presence status, instant messaging and videoconferencing. This situation changes and complicates significantly the programming of telephony applications that consist now of distributed entities involved into multiple heterogeneous, stateful and long-running interactions. This paper proposes an approach to support the development of SIP-based telephony applications based on general programming language. Our approach combines the concepts of Actor, Session and Role. Role is the part an actor takes in a session and we consider a session as a collaboration between roles. By using these concepts, we are able to break the complexity of SIP entities programming and provide flexibility for defining new ones. Our approach is implemented as a coding framework above JAIN-SIP.

Introduction

In recent years, telephony services have endorsed significant changes by integrating a variety of communication forms including video, text and presence while managing aspects like mobility, security, etc. This evolution has created a need for telephony applications to involve an increasing widely range of distributed entities with capacities for participating into multiple, heterogeneous, stateful and long-running interactions. This requirement, compounded with the intricacies of underlying communications, make the programming of new telephony applications a daunting task.

By supporting a rich range of communication forms, the 'Session Initiation Protocol' (SIP) has contributed a lot to this evolution and many advanced telephony applications are now SIP-based. For programming the entities involved in these applications, two main categories of approaches have been proposed over the years. In the first category, we find domain-specific languages (DSL) like LESS [START_REF] Wu | Handling feature interactions in the Language for End System Services[END_REF], SPL [START_REF] Palix | A stepwise approach to developing languages for SIP telephony service creation[END_REF], ECharts [START_REF] Smith | ECharts for SIP Servlets: a state-machine programming environment for VoIP applications[END_REF], StratoSIP [START_REF] Zave | Abstractions for Programming SIP Back-to-Back User Agents[END_REF] to program specific kind of SIP entities such as routing server, end user-agent or back-to-back user agents. All these DSLs provide high-level concepts to hide the intricacies of the underlying SIP technologies but they are usually limited to coarse-grained and dedicated operations and therefore prevent from implementing arbitrary telephony services. The second category of approaches is based on general purpose programming P. Felber and R. Rouvoy (Eds.): DAIS 2011, LNCS 6723, pp. 77-91, 2011. c IFIP International Federation for Information Processing 2011 language and the providing of large, powerful and generic APIs or frameworks such as JAIN-SIP, SIP-Servlet and JAIN-SLEE for the Java language 1 . However, although they enable the programming of unrestricted SIP applications, these approaches provide little support to layer the design of entities that are involved into multiples sessions or participate into sessions with complex message flow, two requirements often meet in advanced telephony applications.

In this paper, our goal is to facilitate the development of SIP-based applications programmed with general-purpose languages. To do so, we provide the developer with a programming model that raises the abstraction level with Actor, Session and Role as key concepts. Our notion of role encapsulates one fragment of the behavior played by an entity similarly to other existing role-based programming approaches [START_REF] Steimann | On the representation of roles in object-oriented and conceptual modelling[END_REF][START_REF] Graversen | The nature of roles. A taxonomic analysis of roles as a language constructs[END_REF] but in our model this notion is specifically related with the notion of session of interactions to provide session-based role programming. The roles played by a SIP entity, which is represented by an Actor, depend automatically on the sessions it participates in at runtime. Advantages provided by this model is to simplify the reasoning on entities description, to achieve a better modularization between session-dependent parts of entities and to improve the capacities for constructing SIP entities from reusable components. In addition to this model, we propose a lightweight implementation over JAIN-SIP that supports the definition of the proposed notions through a set of Java annotations.

The rest of this paper is organized as follows. After pointing out some issues underlying the design of advanced SIP applications in the next section, section 3 presents our programming model. Section 4 illustrates the model and discusses its benefits. Section 5 describes a lightweight implementation of the model in Java. Section 6 presents related works prior to conclude with section 7.

Issues in SIP-Based Applications Design

For supporting applications ranging from simple VoIP routing or instant messaging to sophisticated multimedia sessions involving multiple parties with presence management, SIP provides a rich range of communications forms. Communications can be stateless for simple messages exchange, session-based to exchange messages over a period of time or event-based to propagate information like state-change of an entity. One main benefit of SIP is that it enables mixing its communication forms to design advanced telephony applications. As an example of such application, which will serve in the following, we propose to consider an application that manages presence-based redirection2 of invitation to a dialog combining voice and text. In this application, a server manages the incoming invitation for registered users depending on their status: when available, the server replies with the current user's address to directly invite him, otherwise the invitation is rejected. Figure 1 shows the architecture of this application and a use case of presence-based redirection leading to a successful dialog. In this figure, Alice updates its status because she leaves its office for a meeting [START_REF] Baldoni | Interaction among objects via roles: sessions and affordances in java[END_REF][START_REF] Braek | Model-Driven Service Engineering[END_REF]. Then, Bob calls Alice during her meeting and he receives a BUSY response [START_REF] Dezani-Ciancaglini | Session Types for Object-Oriented Languages[END_REF][START_REF] Graversen | The nature of roles. A taxonomic analysis of roles as a language constructs[END_REF]. When Alice becomes available [START_REF] Herrmann | A Precise Model for Contextual Roles: The Programming Language ObjectTeams/Java[END_REF][START_REF] Vallejos | The Context-Dependent Role Model[END_REF], a new invitation from Bob results in a redirect response including Alice's address to initiate a dialog [START_REF] Monpratarnchai | The Implementation and Execution Framework of a Role Model Based Language, EpsilonJ[END_REF][START_REF] Palix | A stepwise approach to developing languages for SIP telephony service creation[END_REF]. Thanks to the returned address, Bob can directly contact Alice to establish a successful dialog (9 to 18). Despite SIP features for supporting multiple communications forms, developing advanced applications like the previous one remains a complex task. In the following, we give three of the typical issues that complicate the programming of SIP entities.

1) Complex messages flow within a session : Within a session, SIP entities exchange and handle messages at each end. The handling of these messages consists generally in checking that the received message is valid with the entity's current state, performing actions and then changing to next state. There are several difficulties related to the handling of messages in a SIP application.

-A first difficulty is that messages can be received at any time. This entails that SIP entities may be prepared to react to any received messages, including while others are processed. In general, this is achieved by adopting an eventdriven approach for message handling.

-Another difficulty related to message handling is that interpretation of messages in the flow is generally state-dependent. In the example, OK responses have a meaning that depends upon the current state or the previous request. Distinguishing between these interpretations generally require that the application maintains a session state according to the exchanged messages.

-Sometimes, the messages flow of a session may contain messages that are related to distinct concerns. For each concern, the related messages are not necessarily in separate sequences but may be interleaved with those from others concerns. In the example, this is illustrated in the lower part of Figure 1 where we can identify three groups of messages corresponding to session setup, user message exchange and session ending concerns.

-A last difficulty is that message flow can be inverted during the session. Illustrations in the example are given by MESSAGE and BYE requests. This implies that entities must be able to provide behaviours for handling session flow in both directions and to act both as requestor and responder.

Because of the difficulties described previously, the behaviour of entities handling some part of the session flow like the previous one is usually not easy to design and there is a need to provide the developer with appropriate abstractions and decomposition mechanisms to facilitate the handling of messages related to a particular concern or a particular state inside the code.

2) Multi-branches session : A SIP session is not always restricted to a peer-topeer conversation. There are some classical calling or presence scenarios which involve more than two peers in the same session. In these scenarios, one or several SIP entities generally act as facilitator between several participants to the session. For such an entity, this entails to handle more that one conversation within the same session and to coordinate all the conversations in order to serve the communication partners properly. In our example, we initially assume a redirect behaviour for the server but we can easily imagine changing this behaviour to a proxy-like one in order to extend the status of a user according to its participation in an existing dialog 3 . Compared to the previous behaviour, adopting this change requires that the server manages and coordinates two communication paths within a session : one to the callee and one to the caller, switching back and forth being a client and a server at the same time. When a SIP entity is involved in more than one conversation within a session, the complexity for describing its behaviour is inherently increased. To help the developer designing behaviour for multiple interwoven conversations, mechanisms should be provided. Such mechanism should enable expressing the state and behaviour related to each conversation separately but also simplify their coordination.

3) Multi-sessions management : The need to handle multiple sessions is another situation than makes the development of SIP applications and their entities complicated. Two cases may be distinguished for multi-sessions management. The first case is the one where the sessions managed by a SIP entity have the same type and typically occur concurrently. We generally encounter this case when designing SIP server. In our example, the redirect server is an illustration of this case as it must be able to manage calling session coming from multiple requestors. Here, the difficulty is that multiple session states must be maintained separately and concurrently. The second case is the one where each session has a different type. This case can be found particularly in the development of rich user agents and rich servers. In our example, Alice's user agent illustrates this case as it must be able to manage several sessions related to registration, incoming invitation and status modification. For this case, an additional difficulty besides maintaining multiple states is that each session may require the handling of distinct set of messages resulting in a significant amount of messages to handle. Note that a combination of the two cases may sometimes be required for the design of a SIP entity as it is illustrated by the redirect server. For SIP entities, supporting multiple sessions makes their design more complicated because they must include characteristics for many states and behaviours. Therefore, some facilities are needed to limit the complexity. Such facilities should make possible to describe and manage part of the entity related to each session separately from others while simplifying the selection of the appropriate parts during interaction.

Regarding the previous issues, it appears that existing SIP APIs or frameworks do not provide abstractions to solve them. Because of this lack of abstractions, it is common for application developers using SIP frameworks to express the multiple states and behaviours related to parts like concerns, conversations or sessions in a monolithic way and manage them manually with intricate and scattered if-statements. This greatly complicates the application development task and results in cluttered code that is harder to understand, reuse and maintain. To cope with these issues and fill the gap, we present our role-based programming model in the next section.

Programming Model with Actor, Session and Role

As explained previously, development of advanced SIP applications is complex, leading to intricate structure of behaviour for SIP entities. In this section, we propose a programming model based on Actor, Session and Role concepts to help this development. By relying on these concepts, we are able to break the complexity of actor behaviour and to define this behaviour in a flexible way.

In our model, an actor is a top level component which represents a distributed SIP entity. During its lifetime, an actor is involved into one or several SIP sessions that may have the same nature or being different and exist concurrently. To handle sessions programmatically, we define two related concepts : session and session part. The session concept is orthogonal to actors : it aims to group the definition of roles that characterize a specific session. The session part concept establishes the link between an actor and a specific session : it aims to define one or several roles played by an actor when it participates to a particular session. Role concept is the basic unit of our programming model. It is used to describe one of the behaviour involved in a session. Within a particular session, an actor communicates with other actors that play dual or consistent roles.

Figure 2 summarizes the idea of actor, session and role concepts and shows capabilities of the model. Related actors A1 and A2 participate to a SIP session S1. Within this session, actor A1 plays a single role R1 and communicates with A2 that plays dual roles R2 and R2'. Figure 2 also shows a second SIP session S2 independent from S1 that involves actors A3 and A4 but also A1, already engaged in S1. For this session, we may observe that actor A1 plays a role R1' distinct from R1 played in S1. Actor A3 plays two distinct roles to communicate with A1 and A4 actors.

The combined use of actor, session and role proposed by our model allows to deal with the issues identified above. The first issue can be managed by defining multiple roles for a particular session (e.g. A2), each role dealing with one session concern. The capacity for an actor to play multiple roles for distinct communication path (e.g. A3) of a session may be exploited to solve the second issue. Concerning the last issue, the solution is provided by the ability of an actor to participate in multiple sessions with separate roles (e.g. A2 and A4).

In the following subsections, we present the structure of each concept and how they relate. We also explain how session parts and their related roles are created and activated during the actor life-cycle.

Session and Role

In our programming model, sessions are defined independently of actors. A session definition is a kind of module construct containing declarations of interacting roles types that are intended to be played by participating actors. There are two ways to achieve the declaration of roles types inside the session definition : by nesting a role type definition or by importing a role type. This second way enables reusing role types existing in libraries. Role types of a particular session are declared independently of other sessions. Indeed, it is possible for two sessions to rely on a same imported role type if they need the same slice of behaviour.

Code 1 gives, with a Java-like syntax, the definition of CallingSession, a session from our example that defines role types for dialog establishment and user message exchange. We can see that this session definition declares three roles types, the first two (Callee and Caller ) by nesting and the third (MessageHandler )b y importing thanks to the 'includerole' keyword.

A role type describes one behaviour involved in a session. Such a behaviour consists in handling incoming and outgoing SIP messages from and to the other roles while realizing the relevant logic. We provide three fixed kinds of role type to specify their capacities in terms of received and sent messages and help the analysis and the correlation of role types : -Client role represents an asymmetric role type that sends requests and receives related responses.

-Server role represents an asymmetric role that receives request and sends related responses.

-Client Server role represents a symmetric role that sends and receives both requests and responses. The definition of a role type is quite similar to a class in the sense that it may include attributes, operations and may inherit from another role type. Beside operations, a role type may also contain handlers that are special operations designed to handle an incoming SIP request or response. These operations have a specific signature that matches the type of the SIP message.

In the example above, the RegRequestor role type of RegisterSession session is a 'client' role that registers current user's address sending the REGISTER request and handles its related OK responses. It owns a sendRegister operation and a onOK response handler for that purpose. The RegAcceptor role type is a dual 'server' role that has only a message handler to respond to REGISTER request. From sessions, it is possible to define actors that interact by playing the related roles.

Actor and Session Part

Actors are described using actor type. An actor type usually includes one or several session parts. Like a class, an actor type may also contain declaration of attributes and methods that can serve to share some common data or operations between session parts. Furthermore, to specify which session parts are created on the basis of a particular request, an actor type may also have a special block containing rules which specify a condition coupled with a reference to a session part. The meaning of a rule is that an instance of the corresponding session part will be created if the condition is verified for the current state of the actor and the received request.

Code 2 illustrates the actor type for presence-enabled user agents (Alice's one) discussed in Section 2. This actor type includes attributes for managing the history of callers. It also contains declaration of session parts for the three sessions this actor type takes part: RegisterSession, PublishSession,a n dCallingSession. Preceding the session parts, we find a 'sessionControl' block containing a rule to specify that the SPI:CallingSession session part should be created when an INVITE request is received. Other session parts are intended to be created explicitly as they only contain client roles.

A session part defines the participation of an actor type to a specific session in terms of played roles. In a session part, this participation is specified by referencing the targeted session and declaring which roles defined in the session is played by actors of this type. If we take a look at the actor type given above, we can see that the session part named SPI is connected to the CallingSession defined previously. For this session part, two roles are specified using the 'play' keyword : Callee and MessageHandler. As illustrated by this example, introduction of attributes (caller ) and methods to share common data and operations between played roles is also possible.

Similarly to actor type, each session part may include a special block containing rules for determining the roles to create on a particular request and the current actor state. Rule conditions can use predefined boolean functions to query the roles of the session. In Code 2, we have an example of this block introduced by the 'roleControl' keyword. This block contains two rules to state that the Callee (resp. MessageHandler ) role should be played on reception of an INVITE (resp. MESSAGE) request.

In addition to the previous elements, a session part may also introduce extension of roles defined for the referenced session and played by the actors. A role extension enables refining its behaviour. Such extension may be needed to add interactions between sessions inside a role or between roles of a session. This capacity is used in the SPI session part to extend the behaviour defined in Call-ingSession for the Callee role. Here, this extension introduced by the 'extension' keyword is required to update the status of the user when he enters or leaves a dialog. It is achieved by redefining the handlers attached to INVITE and BYE messages with operations to interact with PresencePublisher role.

From Concept to Runtime Entities

In our programming model, actor type, session parts and role types are instantiated to form the state and behaviour of an actor. At runtime, a session part must be considered as the reification of a session from an actor's point of view.

Actors are created from actor type and represents SIP entity at runtime. During the lifetime of an actor, session parts are instantiated to reflect its participation in real SIP sessions. This instantiation can be done explicitly on demand by means of a new-like construct or occurs implicitly on the basis of received request. For a receiving request, the decision to create a session part instance depends if there already exists a session part matching the session-id included in the request. If none exists, rules attached to the actor for session parts are evaluated to create a matching session. A session part may be instantiated more than once per actor. This corresponds to the situation when an actor participates to several sessions of the same kind during its lifetime.

At runtime, each session part instance representing a real session aggregates roles that are played by the actor. The creation of roles attached to a session can be done in two ways, like session part instantiation: either explicitly by means of a new-like construct or implicitly on the basis of a received request. In the latter case, rules attached to the session part are evaluated to determine if a corresponding role must be created.

Message handlers provided by roles are automatically executed on the basis of incoming messages through a forwarding process from actor. When an actor is requested to handle an incoming SIP message, the forwarding process is based first on a selection of the session part instance matching the session-id of the request4 . After that, the processing continues by choosing a role attached to the selected session or by creating a new one if necessary. At last, the message is forwarded to the role by triggering its corresponding message handler.

Revisiting the Example

To illustrate our approach, we propose to revisit our example in terms of Actors, Sessions, Session parts and Roles. Figure 3 shows the resulting architecture which is composed of three actor types: PresenceEnabledUA, RedirectServer and UserAgent. These actors are involved in four sessions which are represented by horizontal boxes crossing actors. The first session, named RegisterSession,t a k e s place when a PresenceEnableUA actor registers its current address to the server. PublishSession is the session to update the user status. The LocateSession is initiated when an external UserAgent actor communicates with the Redirect-Server to locate a registered user agent (PresenceEnabledUserAgent ). Finally, CallingSession is the session for handling the dialog between PresenceEnable-dUA and UserAgent actors types. For the above sessions, we can see that the involved actors play separate roles which are figured by class-like box (session parts are not shown but just indicated by dotted lines).

Figure 4 shows the relationships between the flow of SIP messages and instances of session parts and roles for a dialog setup between Alice and Bob. After receiving the response containing Alice's address from the server, the Lookup role instance played by Bob's UserAgent actor explicitly creates a new CallingSession-related session part and an associated Caller role. Next, this role is invoked to send the INVITE message establishing the real session. When the Alice's PresenceEnabledUA actor receives the message, it detects that there is no matching session, so it evaluates its rules for determining the session part to create and activate. In the current case, it is a CallingSession-related session part which is instantiated. Then, this session part instance evaluates its own rules for determining which role must be played by the actor from the current message and this kind of session. The result is the creation of a Callee role which is finally invoked for processing the message. When playing the Callee role, the PresenceEnabledUA actor returns an OK response to the UserAgent actor for t h es a m es e s s i o n .B e c a u s et h eUserAgent actor is already active in this session and already has a Caller role to handle OK response, no new role is created and this role is selected to process the responses and confirm the dialog establishment with an ACK request. After dialog establishment is complete, both actors can play the MessageHandler role that deals with sending and reception of user messages inside the session.

Through this example, we have illustrated how our model supports the decomposition of behaviour into multiple sessions parts with their respective roles and accomplishes some properties to cope with the issues and requirements identified in section 2. This model also offers the following advantages :

-It raises the level of abstraction as the developer can think about the behaviour of its actor at a higher level thanks to session part and role. This -The encapsulation of behaviour and state into multiple session parts and role components with delimited scope contributes to increase the modularity of actors. As a result of this enhanced modularity, maintenance and evolution of SIP entities and services are made easier. This modularity allows, for instance, to change the server with a proxy behaviour by just replacing its Locator role with two coordinated forwarder roles supporting multi-branches communications.

-Automatic selection of sessions and roles as well as automatic messages forwarding to roles allow to reduce the coding effort since number of controls and extra-state to ensure execution of the appropriate behaviour is minimized compared to SIP frameworks.

-Finally, our approach gives the ability to capture some recurrent behaviour into reusable role types and reuse them by inclusion into sessions. This is an main advantage over existing DSLs for SIP where the question of reusability is generally eluded and over SIP frameworks where reusability is limited by the hardwiring of session-related parts into methods.

A Coding Framework above JAIN-SIP

We have implemented our approach in Java through a coding framework which is presented at Figure 5. Actor-annotated Java code is transformed to produce executable actors, that is to say Java classes that specialize an actor framework. The main classes of the actor framework are SipActor, SipSessionPart, SipClientRole, SipServerRole and SipClientServerRole. These classes implement the proposed concepts and a runtime engine above JAIN-SIP.

To leverage building of SIP applications using our framework, a set of annotations presented in Table 1 has been defined. A class with the @actor annotation will inherit from the SipActor class of the framework, whereas a class annotated with @sessionPart will inherit from SipSessionPart class. The @session annotation is used with an abstract class to define a session. Such a class can declare inner role classes to define the related role types or use the @includeRole(type) annotation to import existing role classes from a library. The three kinds of role types provided by the model are declined in corresponding annotations for classes: @clientRole, @serverRole, @clientserverRole. An actor declares its sessions part with @useSessionPart(type, method, condition) annotation on its class. The mandatory type attribute determines the session part class that has to be imported and activated. The mandatory method attribute provides the type of SIP request method (e.g. INVITE message) that triggers the activation of the session part. The optional condition attribute is a string that refers to the name of a boolean method that describes some particular conditions for the activation of the session part. The principle is similar for declaring roles of a session part, thanks to @useRole annotations, except that it is used with a session part class. Code 3 gives the annotated version of CallingSession session and PresenceEnableUserAgent actor type.

A preliminary study on performance was conducted using the SIPp traffic generator and a JAIN-SIP and framework version of the same user agent server. Results were produced for 1000 calling sessions with a rate of 5/sec. These results show that the framework overhead is about 10 percent compared to JAIN-SIP which is relatively low given that the framework is not yet optimized.

Related Works

In earlier role-based programming approaches, roles are meant to capture the dynamic and temporal aspects of real worlds objects and the view adopted for roles is object-centric: roles are defined as being independent from the interaction. From an object-centric view, our role model have similarities with some earlier approaches and their variants [START_REF] Steimann | On the representation of roles in object-oriented and conceptual modelling[END_REF][START_REF] Graversen | The nature of roles. A taxonomic analysis of roles as a language constructs[END_REF] : it enables multiple role instances for a player and it links the roles to its player using aggregation relationships. However, some features like the distinction between client and server roles, the event-based triggering of roles and the capacity to have roles running in parallel threads are also unique to our role model.

A few works combine roles with a notion of context to express the fact that the interaction possibilities change according to the properties of the interacting objects. In powerJava [START_REF] Baldoni | Interaction among objects via roles: sessions and affordances in java[END_REF], roles represent the possibilities offered by an object to interact with it. For a client, the interaction with such an object is made by acquiring one of its offered role. Similar ideas have been proposed in ActorFrame [START_REF] Braek | Model-Driven Service Engineering[END_REF], a Java-based framework for the design of distributed services with actors and roles. The work described in [START_REF] Vallejos | The Context-Dependent Role Model[END_REF] presents a programming model with contextdependent roles for actors. Roles represents adaptations of an actor that are automatically selected for each message based on the context of the message sender and receiver. In our approach, contexts for roles are provided by sessions. This make our approach different by two main points: selection of a role is not controlled by an interacting entity but only by the owner (actor) and our notion of context is long-lived, i.e persistently activated between messages.

The notion of role is also related to the concept of collaboration that aims to describe the interactions among different objects in a given context. Object-Team/J [START_REF] Herrmann | A Precise Model for Contextual Roles: The Programming Language ObjectTeams/Java[END_REF] and EpsilonJ [START_REF] Monpratarnchai | The Implementation and Execution Framework of a Role Model Based Language, EpsilonJ[END_REF] are extensions of Java that group roles which interact into collaboration modules. Roles inside a collaboration module are played by objects of base classes either explicitly or implicitly, enabling them to interact. In our approach, sessions and session parts provide similar capacities with the main difference that they are supported in a distributed context.

Finally, authors of [START_REF] Dezani-Ciancaglini | Session Types for Object-Oriented Languages[END_REF] have proposed the notion of session type as a language construct to support description and type-checking of protocols between parallels threads. A session type is implemented in dual operations of interacting components using a correlated sequence of receive and send instructions. Compared to the use of one or more role for describing the behaviour of a component related to a session, an operation implementing a session-type is more fine-grained and offers a concise and clearer view of the interaction structure but they also provide less capacities for reuse and flexible composition of behaviour.

7C o n c l u s i o n

To tackle some issues arising from the design of advanced telephony applications based on SIP, we have proposed an approach that enables involved entities to be constructed as actors playing roles in multiples sessions. Proposed approach and its implementation have been experimented through the development of various SIP entities such as user-agents, third-party agents as well as presence and proxy servers. Currently, we are working on elaborating a library of reusable roles from these experiments. In future works, we plan to enhance the programming model with inheritance for sessions and actor types and event-based mechanisms to support coordination between roles and between session parts. We also plan to explore the extensibility of SIP for typing exchanged messages with sessions and roles to enable dynamic roles alignment and synchronization between actors. A last perspective is to better integrate our concepts with the host programming language by using capabilities of some languages for embedding DSL.

Fig. 1 .

 1 Fig. 1. Example of Presence-based Redirection

Fig. 2 .

 2 Fig. 2. Illustration of Actors, Sessions and Roles

Fig. 3 .

 3 Fig. 3. Architecture of our example with Actors, Sessions and Roles Types

Fig. 4 .

 4 Fig. 4. Relationships between SIP messages and actor components contrasts with conventional SIP frameworks which require to examine implementation code in detail to get a similar view.-The encapsulation of behaviour and state into multiple session parts and role components with delimited scope contributes to increase the modularity of actors. As a result of this enhanced modularity, maintenance and evolution of SIP entities and services are made easier. This modularity allows, for instance, to change the server with a proxy behaviour by just replacing its Locator role with two coordinated forwarder roles supporting multi-branches communications.-Automatic selection of sessions and roles as well as automatic messages forwarding to roles allow to reduce the coding effort since number of controls and extra-state to ensure execution of the appropriate behaviour is minimized compared to SIP frameworks.-Finally, our approach gives the ability to capture some recurrent behaviour into reusable role types and reuse them by inclusion into sessions. This is an main advantage over existing DSLs for SIP where the question of reusability is generally eluded and over SIP frameworks where reusability is limited by the hardwiring of session-related parts into methods.

Fig. 5 .

 5 Fig. 5. Coding framework architecture

  Code 3. Example of annotations use to code the presence server example

	@session // Declaration of session
	public abstract class CallingSession {
	@clientserverRole // Declaration of role class
	public class Callee {
	public void onInvite (Request req, ServerTransaction tx) { ... }
	public void sendBye () {...}
	} ...
	}
	@sessionPart // Declaration of session part
	@useRole(type=ExtCallee.class,method="INVITE")
	@useRole(type=MessageHandler.class,method="MESSAGE")
	public class CallingSessionPartPUA {
	@extension(Callee.class) // Extension of role class
	public class ExtCallee {
	public void onInvite (Request req, ServerTransaction tx) { ... } ...
	}
	}
	@actor // Declaration of actor class
	@useSessionPart(type=RegisteringSessionPartPUA.class)
	@useSessionPart(type=PublishingSessionPartPUA.class)
	@useSessionPart(type=CallingSessionPartPUA.class,method="INVITE",condition="hasNoCallingSsn"))
	public class PresenceEnableUA {
	public boolean hasNoCallingSsn() { ... }
	}

http://java.sun.com/products/jain/

In SIP, redirection consists in directing the client to contact an alternate address.

Proxy behaviour in SIP consists in relaying each request and response between user agents of a session.

As explained before, the incoming message may entail a creation of session instance.