Ahmed Kheldoun
email: ahmedkheldoun@yahoo.fr

Kamel Barkaoui
email: kamel.barkaoui@cnam.fr

Jiafeng Zhang
email: zhangjiafeng628@gmail.com

Malika Ioualalen
email: mioualalen@usthb.dz

A high level net for modeling and analysis reconfigurable discrete event control systems

Keywords: Reconfigurable control systems, Feature, Recursive Petri nets, Rewriting logic, Maude

This paper deals with automatic reconfiguration of discrete event control systems. We propose to enrich the formalism of recursive Petri nets by the concept of f eature from which runtime reconfigurations are facilitated. This new formalism is applied in the context of automated production system. Furthermore, the enhanced recursive Petri net is translated into rewriting logic, and by using Maude LTL model-checker one can verify several behavioural properties related to reconfiguration.

Introduction

The new generation of discrete event control models is adressing new creteria as flexibility and agility. The need of flexibility and adaptability leads to integrate reconfigurability features in these models, but it makes the system more complex and its development a hard task. Therefore, an approach for the design safe and reconfigurable systems is a crucial need. The Petri net formalism is one of the most used tools to model and analyse discrete event systems [START_REF] Murata | Petri nets: Properties, analysis and applications[END_REF].

Recently, recursive Petri nets (RPNs) [START_REF] Haddad | Recursive Petri nets -Theory and application to discretee event systems[END_REF] are proposed to specify flexible concurrent systems where functionalities of discrete event systems such as abstraction, dynamicity, preemption, recursion are preponderant. In fact, RPNs have ability to model dynamic creation of threads which behave concurrently.

In this paper, we introduce the concept of f eature proposed in [START_REF] Kang | Feature-oriented domain analysis (foda) feasibility study[END_REF] to deal with reconfiguration at runtime. More precisely, the reconfiguration is modelled by combining the interruption and the activation/deactivation of transitions which is ensured by : application condition and update expression.

The remainder of this paper is organized as follows. Section 2 gives a brief overview of related work. Section 3 recalls the syntax and semantic of the formalism RPNs. The formalism which enrich RPN by the concept of f eature, named reconfigurable RPN and denoted by R 2 PN, is presented in Section 4. Section 5 presents a case study of a reconfigurable automated production system, and we present in Section 6 its modelling in terms of R 2 PN. The verification of the obtained model is done by using the LTL model-checker of Maude [START_REF] Clavel | Maude: specification and programming in rewriting logic[END_REF] [START_REF] Eker | The maude LTL model checker[END_REF] and is described in Section 7. Section 8 concludes this paper and depicts further research work.

Related Work

Many researchers have tried to deal with formal modeling of control systems with potential reconfigurations. The author of [START_REF] Valk | Self-modifying nets, a natural extension of petri nets[END_REF] proposed self-modifying nets that can modify their own firing rules at runtime, however, most of the net basic properties such as reachability, boundedness and liveness become indecidable on these nets. In [START_REF] Guan | Modeling adaptable multimedia and self-modifying protocol execution[END_REF], the authors developped a Reconfigurable Petri Nets (RPN) for modeling adaptable multimedia and protocols that can self-modify during execution. They modelled the reconfiguration by introducing the concept of modifier places. The authors of [START_REF] Badouel | Modeling concurrent systems: Reconfigurable nets[END_REF] presented net rewriting systems (NRS) where a reconfiguration of the net is obtained by a rewriting rules execution. The rewriting rules are similar to production of graph grammars. However, the formalism of NRS is Turing powerful and, thus, automatic verification is no longer possible in that case. Recently, in [START_REF] Zhang | R-tnces: A novel formalism for reconfigurable discretee event control systems[END_REF], the authors proposed Reconfigurable timed net condition/event systems (R-TNCES) for modeling reconfigurable discrete event control systems. In this formalism, the system is represented by a set of control componnents and a reconfiguration is modelled by enabling/disabling some control components modules by changing condition/event signals among them.

In this paper, we present a new formalism named Reconfigurable RPN (R 2 PN) enriches RPN by the concept of feature selection introduced in [START_REF] Kang | Feature-oriented domain analysis (foda) feasibility study[END_REF]. Indeed, in R 2 PN, the reconfiguration is modelled by combining the interruption and refinement with the activation/deactivation of transitions which is ensured by : application condition and update expression. Moreover R 2 PN captures the behaviour of entire reconfigurable discrete event control system in a concise modular model, opening the way for efficient analysis and verification.

Recursive Petri nets

The formalism of RPN [START_REF] Haddad | Recursive Petri nets -Theory and application to discretee event systems[END_REF] consider two types of transitions : elementary and abstract. Moreover a starting marking is associated to each abstract transition and a semi-linear set of final markings is defined. [START_REF] Haddad | Recursive Petri nets -Theory and application to discretee event systems[END_REF] is defined by a tuple N = P, T, P re, P ost, Ω, I, Υ, K where:

Definition 1. (Recursive Petri Nets). A Recursive Petri Net

-P is a finite set of places.

-T is a finite set of transitions where T = T el T abs named respectively, the set of elementary and abstract transitions, -I is a finite set of indices called termination indices, -P re is a mapping defined as : P re : T → P ⊕ , where P ⊕ is the set of finite multi-sets over the set P , -P ost is a mapping defined as : P ost : T el ∪ (T abs × I) → P ⊕ , -Ω is a mapping T abs → P ⊕ associating to each abstract transition an ordinary marking, -Υ is a family indexed by I of termination sets, where each set represents a set of final markings (i.e. un element of P ⊕ ), -K : T el → T abs × I, maps a set of interrupted abstract trasitions, and their associated termination indexes, for every elementary transition.

Example 1. Let's use the net presented in Fig. 1(a) to highlight RPN's graphical symbols and associated notations. (i) An elementary transition is represented by a filled rectangle; its name is possibly followed by a set of terms (t , i) ∈ T abs × I. Each term specifies an abstract transition t , which is under the control of t, associated with a termination index to be used when aborting t consequently to a firing of t. For instance, t 0 is an elementary transition where its firing preempts threads started by the firing of t 1 and the associate index is 1. (ii) An abstract transition t is represented by a double border rectangle; its name is followed by the starting marking Ω(t). For instance, t 1 is an abstract transition and Ω(t 1 ) = p 5 means that any thread, named refinement net, created by firing of t 1 starts with one token in place p 5 . (iii) Any termination set can be defined concisely based on place marking. For instance, Υ 0 specifies the final marking of threads such that the place p 6 is marked at least by one token. (iv) The set I of termination indices is deduced from the indices used to subscript the termination sets and from the indices bound to elementary transitions i.e. interruption. In this example, I = {0, 1}. Informally, a RPN generates during its execution a dynamical tree of marked threads called an extended marking, which reflects the global state of a such net. This latter denotes the fatherhood relation between the generated threads (describing the interthreads calls). Each of these threads has its own execution context.

Definition 2. (Extended Marking

). An extended marking [START_REF] Haddad | Recursive Petri nets -Theory and application to discretee event systems[END_REF] of a recursive Petri net is a labelled tree EM = V, M, E, A where:

-V is the (possibly empty) finite set of nodes. When it is non empty, v 0 denotes the root of the tree, -M is a mapping V → P ⊕ associating an ordinary marking for each node, -E ∈ V × V is the set of edges, -A is a mapping E → T abs associating an abstract transition for each edge.

Any ordinary marking can be seen as an extended marking composed by a unique node. The empty tree is denoted by ⊥. Note contrary to ordinary nets, RPNs are often disconnected since each connected component may be activated by the firing of abstract transitions. In a RPN, we have two kinds of markings: extended markings and ordinary markings. An extended marking represents the state of the RPN. An ordinary marking represents an execution context of the thread as in Petri nets.

Definition 3. (Enabled transition or cut step [START_REF] Haddad | Recursive Petri nets -Theory and application to discretee event systems[END_REF]).

-A transition is enabled in a node v of an extended marking EM = ⊥ denoted by

EM v,t --→ if ∀p ∈ P : M (v)(p) ≥ P re(p, t), -A cut step τ i is enabled in a node v if M (v) ∈ Υ i .
The firing of an elementary transition updates the current marking using ordinary firing rule like in Petri nets. The firing of an abstract transition refines it by a new sub-net (i.e. creation of new thread, named its child) which starts its own token game, from a starting marking whose value is attached to the abstract transition. Once a final marking is reached, a cut step closes the corresponding sub net, kills its children and produces tokens, indicated by the P ost function, in the appropriate output places of the abstract transition. Formal definitions of firing rules are defined in [START_REF] Haddad | Recursive Petri nets -Theory and application to discretee event systems[END_REF]. Due to lack of space, we explain their principls through our illustrated example of Fig. 1(a).

Example 2. Fig. 1(b) highlights a firing sequences of RPN represented in Fig. 1(a). The graphical representation of any extended marking EM is a tree where an arc v i (m i ) t abs --→ v j (m j ) means that v j is a child of v i created by firing the abstract transition t abs and m i (reps. m j ) is the marking of v i (reps. v j ). Note that the initial extended marking EM 0 is reduced to a single node v 0 whose marking is p 0 + p 1 . From the intial extended marking EM 0 , the abstract transition t 1 is enabled; its firing leads to the extended marking EM 1 which contains a fresh node v 1 marked by the starting marking Ω(t 1 ). Then, the firing of the elementary transition t 3 from node v 1 of EM 1 leads to an extended marking EM 2 , having the same structure as EM 1 but only the marking of node v 1 is changed. From node v 1 in EM 2 , the cut step τ 0 is enabled; its firing leads to an extended marking EM 3 by removing the node v 1 and change the marking on its node predecessor i.e. v 0 by adding P ost(p 3 , t 1 , 0). Also, another way to remove nodes in extended marking is using the concept of preemption associated to the elementary transitions. For instance, from node v 0 in EM 2 , the elementary transition t 0 with associated preemption (t 1 , 1) is enabled; its firing leads to an extended marking EM 4 by removing the node v 1 .

Reconfigurable Recursive Petri nets

Reconfigurable Recursive Petri nets (R 2 PNs) enriches RPN by the concept of feature selection introduced in [START_REF] Kang | Feature-oriented domain analysis (foda) feasibility study[END_REF]. In fact, R 2 PNs extend RPN by associating transitions and cut steps with application conditions and update expressions. An application condition is a logical formula over a set of features, describing the feature combinations to which the transition applies. It consitutes a necessary (although not sufficient) condition for the transition to fire. In fact, if the application condition is false, means that the transition is desactivated. An update expression, describes the feature selection evolves after firing a transition.

A feature is defined as a prominent or distinctive user-visible aspect, quality or characteristic of a system. A feature is defined in [START_REF] Kang | Feature-oriented domain analysis (foda) feasibility study[END_REF] as follows : Definition 4. (Feature [START_REF] Kang | Feature-oriented domain analysis (foda) feasibility study[END_REF]). A feature is an end-user visible characteristic of a system.

The concept of feature has been introduced by the software design community to specify and distinguish products in product lines [START_REF] Muschevici | Modelling Diversity in Software Product Lines[END_REF] [START_REF] Kang | Feature-oriented domain analysis (foda) feasibility study[END_REF]. Now, let's define the set of application conditions over a set of features.

Definition 5. (Application condition

). An application condition ϕ [9] is a logical (boolean) contraint over a set of features F , defined by the following grammar: ϕ ::= true | a | ϕ ∧ ϕ | ¬ϕ, where a ∈ F . The remaining logical connectives can be encoded as usual. We write Φ F to denote the set of all application conditions over F . Definition 6. (Satisfaction of application conditions [START_REF] Muschevici | Modelling Diversity in Software Product Lines[END_REF]). Given an application condition ϕ and a sub set of features F S, called a feature selection, we say that F S satisfies ϕ, written as

F S |= ϕ, iff: (1) F S |= true always; (2) F S |= a iff a ∈ F S; (3) F S |= ¬ϕ iff F S ϕ; (4) F S |= ϕ 1 ∧ ϕ 2 iff F S |= ϕ 1 and F S |= ϕ 2
Definition 7. (Update). An update [START_REF] Muschevici | Modelling Diversity in Software Product Lines[END_REF] is defined by the following grammar: u ::= noop | a on | a of f | u; u, where a ∈ F and F is a set of features. We write U F to denote the set of all updates over F . Given a feature selection F S ⊆ F , an update expression modifies F S according to the following rules: r1:

F S noop ---→ F S; r2: F S a on ---→ F S ∪ {a}; r3: F S a of f ---→ F S \ {a}; r4: F S u 0 -→F S F S u 1 -→F S F S u 0 ;u 1 ---→F S .
We are now in position to introduce R 2 P N s.

Definition 8. (Reconfigurable Recursive Petri nets). A R 2 P N s is a tuple EN = N, F, f, u , where :

-N = P, T, P re, P ost, Ω, I, Υ, K is RPN, -F is a set of features, f : T ∪ {τ i } → Φ F is a function associating to each transition and cut step with an application condition from Φ F where i ∈ I, u : T ∪ {τ i } → U F is a function associating to each transition and cut step with an update from U F where i ∈ I.

We write u t resp. u τi to denote the update expression u(t) resp. u(τ i ) associated to a transition t resp. a cut step τ i .

we write F S |= f (t) if the feature selection F S satisfies the application condition associated with transition t. In the following, graphically, each transition of R 2 PN is annotated by an application condition and an update expression in the following way: - Therefore, the analysis of R 2 PN is based on constructing its extended reachability graph, which is used for checking properties such as reachability, deadlock and liveness.

A transition t is enabled in a node v, if ∀p ∈ P : M (v)(p) ≥ P re(p, t) and F S |= f (t), -A cut step τ i is enabled in a node v, if M (v) ∈ Υ i and F S |= f (τ i ).

Case Study : Automated Production Systems

In this research work, we use a reconfigurable production devices called, FESTO [START_REF] Zhang | R-tnces: A novel formalism for reconfigurable discretee event control systems[END_REF] as a running example. We assume that the device may perform some particular reconfiguration scenarios according to well-defined conditions. FESTO is composed of three units: distribution, test and processing units. The distribution unit is composed of a pneumatic feeder and a converter to forward cylindrical work pieces from a stack to the testing unit which is composed of the detector, the tester and the elevator. The testing unit checks of work pieces for height, material type and color. Work pieces that successfully pass this check are forwarded to the rotating disk of the processing unit, where the drilling of the work piece is performed. We assume in this work two drilling machines Dr1 and Dr2 to drill pieces. The result of the drilling operation is next checked by a checking machine and the work piece is forwarded to another mechanical unit. Three production modes (called local configurations) can be performed by F EST O.

-Light1: For this production mode, only the drilling machine Dr1 is used; -Light2 : To drill work pieces for this production mode, only the drilling machine Dr2 is used; -High: For this production mode, where Dr1 and Dr2 are used at the same time in order to accelerate the production.

Ligth1 is the default production mode of F EST O and the system completely stops in the worst case if the two drilling machines are broken. We assume that F EST O may perform four reconfiguration scenarios as shown in Fig. 2. The adaptor EN Adapt of F EST O is shown in Fig. 3. It is represented by ERPN where each place specifies one beahviour. As shown in Fig. 3, we have three places p L1 , p L2 and p Hi which specify the three production modes Light1, Light2 and High. Each one of these places may contain at most one token and the marking of such place means that its associated production mode is currently applied by the production system F EST O. For instance, the place p L1 is marked, which means the current production mode applied by F EST O is Light1 i.e.the initial production mode. The set of elemenatry transitions represent the set of reconfiguration scenarios of F EST O. For instance, the elementary transition t L1T oL2 models the reconfiguration scenario that allows the production system F EST O to transform from the first production mode Light1 to the second production mode Light2 when drilling machine Dr1 is broken. In fact, the firing of this transition will interrupt the abstract transition Drill L1 , which models the first production mode Light1, and update the current feature selection F S by applying its associated update expression Dr1 of f ;Dr2 on as shown in Fig. 3.

The behaviour EN Beh of F EST O which is a union of multiple R 2 P N s is formalised as follows:

EN Beh = i∈1..3 EN Behi , with EN Behi = P i , T i , P re i , P ost i , Ω i , I i , Υ i , K i , F i , f i , u i is a R 2 PN
models one possible behaviour of reconfigurable control system of F EST O. Fig. 4 models the behaviour of F EST O using ERPN. All the transitions shown in Fig. 4, where their application condition and update expression are omitted, are annotated by the term : true noop . This means that this set of transitions are common to all behaviours of F EST O. The set of features F contains the set of drilling machines which may be used to select the proper behaviour of F EST O i.e. F = {Dr1, Dr2}. As noted in Fig. 4, the abstract transitions Distribute, T est and P rocess models the distribution, tester and processing unit. The firing of one of these transitions will create a thread representing the behaviour of associating unit. For instance, the firing of the abstract transition P rocess creates a thread, models the behaviour of processing unit, which starts by one token i.e. workpiece in place p 12 . The workpiece is then forwarded to the drilling machines by firing the elementary transition Rotate. After, three abstract transitions Drill L1 , Drill L2 and Drill Hi may be enabled; they model the drilling's step according to the three production modes Light1, Light2 and High. But each one of these abstract transitions is associated an application condition which restricts its activation (firing) to the set of bound features F . As described above, the default production mode of F EST O is Light1, where only the drilling machine Dr1 is used, so the initial feature selection F S 0 = {Dr1}. In this case, only the abstract transition Drill L1 is enabled. The firing of this abstract transition will create a thread, models the drilling's step, which starts by one token in place p 17 . Note that the created thread can use only the drilling machine Dr1 represented by the elementary transition Dr1-L1. Moreover, this thread presents two types of termination :

-P roperly termination : it means that the workpiece is well drilled and the place p 18 is marked. So, a final marking belongs to termination's set Υ 4 is reached, then the cut step τ 4 may be enabled. The firing of τ 4 terminates the current thread and puts a workpiece in the place p 14 in order to perform the remains operations such as Checker and Evacuate. -T ermination by interruption: this termination occured when the production system F EST O applies a reconfiguration as described above for adaptor module. For instance,from Fig. 3, firing the elementary transition t L1T oL2 will interrupt the thread created by the absract transition Drill L1 with termination index 5 and update the feature selection F S 0 . The new obtained feature selection F S 1 = {Dr2}.

In fact, the workpiece is put it in the place p 13 and only the abstract transition Drill L2 may be enabled, which specify the drilling's step according to the second production mode Light2.

Verification of Reconfigurable control systems

In this section, we outline the conversion from R 2 PNs to a Maude specification [START_REF] Clavel | Maude: specification and programming in rewriting logic[END_REF] and the use of its Linear Temporal Logic (LTL) model checker [START_REF] Eker | The maude LTL model checker[END_REF].

Maude and its Model-Checker

Maude is a high-performance reflective language and system supporting rewriting logic specification [START_REF] Meseguer | Conditioned rewriting logic as a united model of concurrency[END_REF]. It has been developed at SRI (URL: http://maude.cs.uiuc.edu/) International for over two decades. A system, under Maude, is represented using membership equational logic describing its set of states and a set of rewrite rules representing its state transitions. Maude is stricly typed, where the types are called sorts and can be built hierarchically using subsorts. Maude's basic programming statements are equations and rules, and have in both cases a simple rewriting semantics in which instances of the left-hand side pattern are replaced by corresponding instances of the right-hand side. One aim using Maude is its LTL model-checker which can be used to verify properties as reachability, deadlock or liveness for a specified model. Model checking can be used to prove properties, specified in LTL when the set of states reachable from an initial state in a system module is finite. In [START_REF] Eker | The maude LTL model checker[END_REF], the author presents more details about syntax and semantic of LTL.

Conversion of R 2 PN to a Maude specification

Like in [START_REF] Barkaoui | Towards analysis of flexible and collaborative workflow using recursive ecatnets[END_REF], the state of a R 2 PN is described by a term State(EM, f s) of sort ST AT E where:

-EM is an extended marking represented, in a recursive way, as a dynamical tree by the term [M T h , tabs, T hreadChilds] of sort T hread where M , of sort M arking, represents the internal marking of T h. The term tabs represents the name of the abstract transition whose firing (in its thread father) gave birth to the thread T h. Note that the root thread is not generated by any abstract transition, so the abstract transition which gave birth to it, is represented by the constant nullT rans. The term T hreadChilds represents a finite multiset of threads generated by the firing of abstract transitions in the thread T h. We denote by the constant nullT hread, the empty thread. f s is a feature selection, of sort F S, represented by a list of terms of sort T erm.

We denote by the constant empty, the empty list of feature selection.

We have also impleneted two functions in the module F eatureSel needed by our formalism R 2 PN. The first function is SAT AC(ac : AC, f s : F S) : Bool which checks the truth value of an application condition ac, of sort AC, for a given feature selection f s. The second function is U P DAT E(u : U E, f s : F S) : F S which returns the new feature selection after applying the update expression u, of sort U E, for a given feature selection f s.

Moreover, each transition firing and cut step execution is formally specified in Maude by a labelled rewrite rule as follows :

-Rule associated to an elemetary transition t with K(t) = φ , application condition ac(t) and update expression ue(t)

Implementation using the Maude Tool

Since we give a Maude specification for the formalism R 2 PN, we can benefit from the use of the LTL model-checker of the Maude system for verification purpose where the generated state space must be finite. For instance, one can check the liveness property over EN F EST O for its initial behaviour Ligth1. We suppose that the system starts by100 tokens i.e. workpieces, this is specified in Maude by : eqinitialState = State(< p0; 100 > ( * ) < pL1; 1 >, Dr1). A liveness condition is : each workpiece must reach (from all reachable markings) the final state where the place p 4 is marked.This can be phrased as "For all paths and from all states, State(< p4; 100 > ( * ) < pL1; 1 >, Dr1) can finally be reached". In Maude, this is stated by [] <> State([< p4; 100 > ( * ) < pL1; 1 >, nullT rans, nullT hread], Dr1)., and proven to be valid by its model checker in Fig. 5(a). We suppose in this case that there is no f ail during the workpieces's test process.

Let take another example and we focus on the case, when an error occurs, whether the control module can respond and select a proper behaviour. We define the following LTL formula : α : [](Behaviour(Light1)/ Drill -Down(Dr1) => <> Behaviour(Light2))), where, the predicate Behaviour allows to know the current behaviour applied by the production system F EST O. The predicate Drill-Down indicates which among drilling machines Dr1 ord Dr2 is break-down.

This LTL formula means that, always, if the current production mode of F EST O is Light1, drill machine Dr1 is broken, the production system F EST O will eventually select the production mode Light2. This LTL formula is proved to be valid in Fig. 5(b). Now, let's define a LTL proprty β by replacing in the formula α the production mode Light2 by High. In Fig. 5(c), this formula is proved to be not valid and the model-checker returns the expected counterexample. This research work copes with the reconfiguration issue of discrete control systems. We have proposed Renconfigurable RPN (R 2 PN) which enriches RPN by the concept of f eature to deal with reconfigurations at runtime. R 2 PN allows instance of threads in RPN to be renconfigurable. We have shown the efficiency of R 2 PN through a case study represented by a reconfigurable production system. A verification method for R 2 PN has also been presented by using the LTL model-cheker of Maude.

In the future, we will plan to extend our formalism in order to model time constraints which are of great importance in real-time systems. Therefore, one can verify some properties with respect to time constraints using Real-Time Maude model-checker [START_REF] Ölveczky | Real-Time Maude: A tool for simulating and analyzing real-time and hybrid systems[END_REF].

Fig. 1 .

 1 Fig. 1. A recursive Petri net and Two possible firing sequences

Definition 9 .

 9 (A state of Reconfigurable RPN). A state of a Reconfigurable RPN EN = N, F, f, u is a tuple S = (EM, F S) where EM = V, M, E, A is an extended marking and F S ⊆ F is a feature selection. Definition 10. (Enabled transition or cut step). Let S = ( V, M, E, A , F S) be a state of R 2 PN EN = N, F, f, u where N = P, T, P re, P ost, Ω, I, Υ, K . Let a node v ∈ V .

Definition 11 .

 11 (Firing rules of Reconfigurable RPN). Let S = (EM, F S) be a state of R 2 PN EN = N, F, f, u where N = P, T, P re, P ost, Ω, I, Υ, K . Let a node v ∈ V . -The firing of an elementary transition t from a node v leads to a state S = (EM , F S ) where EM v,t --→ EM as Definition12. in [3]. and F S u(t) --→ F S , -The firing of an abstract transition t from a node v leads to a state S = (EM , F S ) where EM v,t --→ EM as Definition13. in [3]. and F S u(t) --→ F S , -The firing of a cut step τ i from a node v leads to a state S = (EM , F S ) where EM v,τi --→ EM as Definition14. in [3]. and F S u(τi) ---→ F S .

Fig. 2 .

 2 Fig. 2. Reconfiguration scenarios of F EST O

Fig. 4 .

 4 Fig. 4. R 2 PN represents FESTO's behaviour

  Maude> in R2PN/MAIN.maude . ========================================== reduce in R2PN-CHECK : modelCheck(initialState, []<> State([< pL1 ; 1 >(*)< p4 ; 100 >,nullTrans,nullThread],Dr1)) . rewrites: 16284 in 13344662529ms cpu (160ms real) (0 rewrites/second) result Bool: true Maude> (a) Maude> in R2PN/MAIN.maude . ========================================== reduce in R2PN-CHECK : modelCheck(initialState, []( Behaviour(Light1) /\ Drill-Down(Dr1) => <> Behaviour(Light2))) . rewrites: 50184 in 13601982251ms cpu (341ms real) (0 rewrites/second) result Bool: true Maude> (b) Maude> in R2PN/MAIN.maude . ========================================== reduce in R2PN-CHECK : modelCheck(initialState, []( Behaviour(Light1) /\ Drill-Down(Dr1) => <> Behaviour(High))) . rewrites: 19774 in 6091294694ms cpu (124ms real) (0 rewrites/second) result ModelCheckResult: counterexample(... {State([< pL1 ; 0 >(*)< pL2 ; 1 >(*)< dr1-error ; 0 >(*)< pone ; 0 >(*)< p0 ; 0 >(*)< p4 ; 99 >,nullTrans,[< p12 ; 0 >(*)< p13 ; 0 >(*)< p14 ; 1 >,Process,nullThread]],Dr2),'Checker} {State([< pL1 ; 0 >(*)< pL2 ; 1 >(*)< dr1-error ; 0 >(*)< pone ; 0 >(*)< p0 ; 0 >(*)< p4 ; 99 >,nullTrans,[< p12 ; 0 >(*)< p13 ; 0 >(*)< p14 ; 0 >(*)< p15 ; 1 >,Process,nullThread]], Dr2),'Evacuate} {State([< pL1 ; 0 >(*)< pL2 ; 1 >(*)< dr1-error ; 0 >(*)< pone ; 0 >(*)< p0 ; 0 >(*)< p4 ; 99 >,nullTrans,[< p12 ; 0 >(*)< p13 ; 0 >(*)< p14 ; 0 >(*)< p15 ; 0 >(*)< p16 ; 1 >,Process,nullThread]],Dr2), 'cut-3}, {State([< pL1 ; 0 >(*)< pL2 ; 1 >(*)< dr1-error ; 0 >(*)< pone ; 1 >(*)< p0 ; 0 >(*)< p4 ; 100 >,nullTrans,nullThread],Dr2),deadlock}) Maude> (c)

Fig. 5 .

 5 Fig. 5. (a) Model checking of the liveness condition for first production mode of F EST O, (b) Model checking of the LTL property α and (c) Counterexample generated by model checking of the LTL property β

  Rule associated to a cut step τ i with application condition ac(τ i ) and update expression ue(τ i )

	crl[t]: State(<p; N+Pre(p,t)> ( * ) <p'; M> , fs) =>State(<p; N
	)> ( * ) <p'; M + Post(p',t)> , UPDATE(ue(t), fs) if SATAC(
	ac(t), fs).
	-Rule associated to an elemetary transition t with K(t) = {(t absi , k), (t absj , m), ..},
	application condition ac(t) and update expression ue(t)
	crl[t]: State([<p;N+Pre(p,t)>( * )<p';M>( * )<p i ;A>( * )<p j ;B>,
	absTrans,Thread],fs) => State([<p; N>( * )<p'; M+Post(p',t)
	>( * )<p i ; A+Post(p i , t absi ,k)>( * )<p j ; B+Post(p j ,t absj ,m)>,
	absTrans, DeleteThread(t absi ,t absj ,...,Thread)], UPDATE(ue(t
	), fs) if SATAC(ac(t), fs).
	crl[t]: State([<p;N+Pre(p,t)>, absTrans, Thread] , fs) =>
	State([<p; N)>, absTrans, Thread[<p'; Ω(t)>, t, nullThread
	]] , UPDATE(ue(t), fs) if SATAC(ac(t), fs).
	crl[τi]: State([<p;N>, absTrans, Thread[<p';N'> , tabs,
	Thread1]] , fs) => State([<p; N+Post(p, tabs, i)>,
	absTrans, Thread, UPDATE(ue(τi), fs) if (Υi and SATAC(ac(τi
	), fs)).

-Rule associated to an abstract transition t with starting marking Ω(t), application condition ac(t) and update expression ue(t) -


Chahrazed Mediani
email: chahrazed_mediani@yahoo.fr

Marie-Hélène Abel
email: marie-helene.abel@utc.fr

Mahieddine Djoudi
email: mahieddine.djoudi@univ-poitiers.fr

Towards a recommendation system for the learner from a semantic model of knowledge in a collaborative environment

Keywords: Collaboration, Trace, Indicator, Recommendation system

Collaboration is a common work between many people which generates the creation of a common task. A computing environment can foster collaboration among peers to exchange and share knowledge or skills for succeeding a common project. Therefore, when users interact among themselves and with an environment, they provide a lot of information. This information is recorded and classified in a model of traces to be used to enhance collaborative learning. In this paper, we propose (1) the refinement of a semantic model of traces with indicators calculated according to Bayes formulas and (2) the exploitation of these indicators to provide recommendations to the learner to reinforce learning points with learners, of his/her community of collaboration, identified as "experts".

Introduction

The advent of Information and Communication Technologies and particularly Web 2.0 technologies have facilitated learning based primarily on exchanges and resource sharing between learners of the same community [START_REF] Abel | Apport des Mémoires Organisationnelles dans un contexte d'apprentissage[END_REF]. On its side, collaborative learning is a process leading to the progressive construction of knowledge. This learning derived from the current of constructivism allows a person to build knowledge from interaction with his surroundings. When these interactions are performed using digital technology, they leave traces. These traces are usually saved in a model of traces [START_REF] Settouti | Système à base de traces pour l'apprentissage humain[END_REF] and thus made usable for various purposes such as updating a learner model. Taking account the learner activities within a Computing Environment for Human Learning (CEHL) to guide him in his learning is complex. The learner model allows to consider knowledge of all kinds (preferences, motivations, acquired knowledge or not, mistakes, etc.). As part of our work, we focus on the interactions between learners via a CEHL and with a CEHL to make recommendations to guide learner in their learning. To this end, we have chosen to characterize a number of actions that a learner can perform in a CEHL to define learning indicators to establish recommendations. Learning is the result of personal and collaborative actions. We therefore consider the traces resulting of these two axes.

To do this, we have chosen to refine the collaboration model of traces proposed by [START_REF] Wang | Towards a Recommender System from Semantic Traces for Decision Aid[END_REF] and illustrated in the environment E-MEMORAe 2.0 [START_REF] Abel | Knowledge Proc of sharing via the E-EMORAe2.0 platform[END_REF]). So we have introduced measures to estimate some parameters, unmeasurable and unobservable by observable indicators describing the state of the learner activities and the progression of his knowledge when interacting within a community of learners.

In the following, we state our problem before presenting the limitations of existing work related to measures established to make recommendations to learners. We then detail our approach based on a model of traces increased by indicators and its exploitation through a case study before concluding and advancing the prospects for this work.

Motivation

The Information and Communication Technologies and the emergence of collaborative learning platforms have enabled the implementation of collaborative CEHL and related issues such as the lack of information on the learner evolution within the community and the state of his knowledge and his activities in his group. This information is needed to measure the contribution of each member in the community and may be useful in defining the responsibilities of each member of the group. This information is also useful for the learner himself; this allows him to have a state of his learning and to allow him to prepare himself for a more relevant evaluation. To remedy these problems, the analysis of the leaner interaction traces with a learning environment has become a research topic that is rapidly evolving.

Related work

In the context of CEHL, trace-based study is not just about how to analyze the traces but also how to complete them and exploit them to improve learning (Ollagnier-Belbame et al., 2007). Among the works that have been done in the context of CEHL to support observation, we can mention the work treating the analyzing of the learner behavior and the characterization of his activities [START_REF] Georgeon | Abstract : un outil et une méthodologie pour analyser une activité humaine médiée par un artefact technique complexe[END_REF], and those that treat the interpretation of learner interactions with computing environments and with other users [START_REF] Siebra | A learning interaction memory using contextual information[END_REF], [START_REF] George | Analyse automatique de conversations textuelles synchrones d'apprenants pour la détermination de comportements sociaux[END_REF]. There are several learning environments where interactions between the system and users are traced, we mention, for example: the collaborative learning environment Drew (Dialogical Reasoning Educational Web tool) [START_REF] Corbel | DREW : A Dialogical Reasoning Web tool[END_REF]

Our Approach

Our approach is to refine the collaborative model of traces of [START_REF] Li | Facilitating Experience Groups Sharing Collaborative Trace[END_REF], and taken up by [START_REF] Wang | Towards a Recommender System from Semantic Traces for Decision Aid[END_REF], by a number of measures to build indicators on the state of the learner knowledge and the progression of his knowledge within a group in a learning session. Among These parameters: we retain the mastery degree of knowledge represented by a concept. To achieve these goals, we have adopted the following approach: (i) propose a semantic model to measure indicators of the contribution of each student in the group, (ii) estimate the contribution of indicators using Bayesian formulas [START_REF] Triola | Baye's Theorem[END_REF], this contribution should take into account the knowledge of the learner and his activities, (iii) propose a set of recommendations to assist the learner in his learning and prepare him for a more appropriate evaluation. As shown in Figure 1, the architecture of the recommendation system that we propose is composed of two modules operating three models: a trace collection module, a pedagogical content model, a learner model, a collaboration model and a recommendation module. This system is used to collect traces of users and store them in a database of traces. A trace is a time sequence of observed containing all user actions to perform a given task.

The first module of our system treats the collecting primary traces in native format. The second module classifies the primary traces coming from the first module as high-level traces along the trace model (Li, 2013). Depending on the content of traces model and pedagogical content model, algorithms for learning indicators calculations of the learner are applied in the recommendation module. For that, the recommendation system must select good recommendations that guide the user in achieving his learning task. We will illustrate this system of recommendations within the collaborative learning platform E-MEMORAe 2.0 [START_REF] Abel | Knowledge Proc of sharing via the E-EMORAe2.0 platform[END_REF].

In the next subsections, we present the principle of the main components of the recommendation system, namely the pedagogical content model, collaborative model, collection of traces and the learner model. The calculation of learning indicators and the recommendation module will be presented in the following sections.

Pedagogical content model

The content model of learning environments usually consists of a set of elements representing elementary fragments of domain knowledge studied. These elements, often organized in a hierarchy, are named (concepts, notions, knowledge elements, subjects) and they can be of different types. Our content model consists of application ontologies. The application ontology specifies the concepts of a particular application. These concepts represent concepts to be learned of a training unit. A concept is therefore a particular concept that needs to be assimilated by the learner during learning. The concepts are used to index the pedagogical resources treating them. This provides a way to reuse these resources. These concepts are organized in a hierarchy that also represents several types of relationships (specialization and others). Among the ontologies of applications built as part of the E-MEMORAe 2.0 environment: Ontology for the teaching unit "Information Technology". For these applications ontologies, we propose to add the attribute "weight" to the relationship of type "is a" between each concept and its sub concepts (0<= weight<= 1) with the sum of the weights of subconcepts equal to 1. This value is determined by the responsible of training and represents the degree of contribution of this concept in the acquisition of the father concept (Figure 2).

.4 0.6 is is is is is is is is 4.2

Collaboration model

Our model allows organizing collaborative spaces for students working in groups on the same problem. Thus forming a work site and exchange for the group and allowing, on the one hand, to each member of the group to access resources (documents and other) for the group and, on the other hand, to memorize his work (documents, ideas, knowledge, solutions, etc.) on the Treaty problem. The MEMORAe 2.0 environment allows each user to choose to access a private space or spaces of groups to which he belongs.

• The private space: space where each user can set his own resources. The content of this space is accessible only by that user.

• Space group: space is only accessible by members of the group and in which they share and exchange resources.

Collect of traces

The traces collection is to observe the student in a learning situation and memorize his activities traces to infer the learner model. This collection mode is interesting because it captures the learner interaction the learner without distracting him from his main task. In E-Memorae2.0, these actions are stored in the database traces and classified according to the actions model of the E-MEMORAe 2.0 platform. According to this model, we have three types of traces: Private traces belonging to the private space, traces of collaboration that belong to the space of collaboration and individual traces that are private traces and traces of collaboration. For each type of traces, we have three types of activities that can be conducted by the learner: learning resources consultations (documents), resources creation (conversations, meetings, questions, answers, notes and wikis) and resources additions (documents and annotations).

Example: Figure 3 shows an example of interaction on different concepts, of a group of users using a histogram. Each line represents the collaboration traces of a user for each concept.

Fig. 3. Example of collaborative interactions in a group

The following table summarizes the actions, of figure 2, performed by members of the group 1. For a given concept, each cell of the table represents the number of actions performed by the learner for each type of activity (C: Consultation, R: Creation, A: Addition). The number before the parenthesis is the sum of the learner actions for the concept. C : Consultation, R : Creation, A : Addition.

Learner model

Our learner model is a subset of the pedagogical content model. The pedagogical content is decomposed into a set of elements and the learner model is represented by a set of measurable values associated to these elements. These values vary between 0 (not mastered) and 1 (mastered). The structure of the learner model is the same as the Bayesian network (Figure 4). The elements (concepts and activities) of the learner model become nodes in the Bayesian network. The weight of each element is replaced, for each variable, by a probability to estimate the mastery degree of the learner knowledge. These probabilities vary between 0 (not mastered) and 1 (mastered). The relationship of type "is-a" in the learner model become conditional dependencies between variables forming arcs of the Bayesian network. The elements of knowledge or concepts represent unobservable variables while other elements which are the learning activities used to measure the mastery degree of the learner knowledge (tests, exercises, forums, etc.), represent the observable variables which are added to the Bayesian network.

Construction of the learner model from indicators

For a given concept, we aim to measure the degree of mastery of this concept by the learner from the activities related to the concept which he conducted in his group space (contribution by activities) and also from the knowledge acquired by navigating the sub concepts and implementation of activities related to his sub-concepts (contribution by the sub-knowledge). For each concept, we assign a weight P1 to the contribution activities and a weight P2 to the contribution by the sub-concepts. The sum of these weights must be equal to one.

Example: P1 = 0.6, P2 = 0.4. Each concept is linked to a set of activities, so we can estimate the degree of the learner contribution based on the number of the learner activities carried out in his group. We assign to each type of activity a weight (parameter) which represents the degree of contribution of his activities in the calculation of the mastery degree of this concept by the learner. This setting can distinguish concepts that require a more theoretical activity (consultation) from practical (realization of an exercise, creating a resource). The sum of the weights of the types of activities should be equal to one.

Example: For a given concept, Poids_consultation = 0.2, Poids_création = 0.5 and Poids_addition = 0.3. (These weights can vary from one concept to another).

To realize our contribution model, we use the format of Resource Description Framework (RDF). RDF graph is a model that is used to formally describe Web resources and metadata. Figure 5 shows the RDFS graph of our knowledge model. An ellipse is a class resources and a rectangle represents a property. Generally, the learner model information is related to each other. In other words, the learner's knowledge affects each other, for example, motivation to learn, has a direct influence on the ability to perform the task. And as the student model has an hypothetical character, using probabilities, uncertainty is processed. The calculation we retain is based on the following formula: Consider a partition A 1 , A 2 , …, A n of the set E of events: A 1  A 2  …  A n = E, A i  A j =  for i  j, P (E) = 1. For any event B: P(B) = P(A 1 ) . P(B  A 1 ) + P(A 2 ) . P(B  A 2 ) + …+ P(A n ) . P(B  A n ).

(

P(B  A) : the conditional probability that event B is true given that the event A is already true. We apply equation ( 1) to calculate the previous indicators. achieved enough of activities in his workspace. If this is the case, the algorithm also determines if it is consultation, addition or creation activities. And in this case, he recommends the learner to perform more activities and provides a list of students in his group identified as "experts" that can assist him in the implementation of these activities. The algorithm can also determine if the problem is due to the lack of mastery of one or more sub-concepts and in this case, the algorithm recommends the learner to work more on these sub-concepts with learners who have already acquired skills for these sub-concepts.

Discussion

Our approach allows measuring some learning indicators such as the mastery level, of a concept by a learner, which is calculated according to the different activities that he has carried out within a group (collaboration space) on the concept and its sub concepts. Returning to the previous example, we calculated the learning indicators of Marie-Hélène, within the group1 composed of four members, for each concept of the application ontology that contains the concepts to be learned of a training unit. If we apply the recommendation algorithm to Marie-Hélène on the concept "Information Technology" with a threshold of 0.25 (1/4), we obtain: KL (Marie-Hélène InfTech) = 0.119 <0.25

We have: AC (Marie-Hélène, InfTech) = 0.05 (consultation_value = 0.25, creation_value = 0, addition_value = 0). Marie-Hélène will be recommended to work on creating and adding resources with members of his group productive on these actions. KC (Marie-Hélène InfTech) = 0.3 * 0,356 + 0.7 * 0,228 = 0,227 <0.25

The recommendation also focuses on sub concepts. KL (Marie-Hélène Software) = 0.228 <0.25 and KL (Marie-Hélène, Hardware) = 0.356> 0.25 The work should be done especially on the sub-concept Software.

Let us now apply the recommendation algorithm to Marie-Hélène on the concept Software with the same threshold, we get: AC (Marie-Hélène, Software) = 0.274> 0.25 and KC (Marie-Hélène Software) = 0.159 <0.25 Marie-Hélène must therefore be recommended to work on the sub-concepts of Software with learners who have already had expertise on these sub concepts.

We have: KL (Marie-Hélène, Java) = 0 <0.25, KL (Marie-Hélène, WP) = 0.4> 0.25, KL (Marie-Hélène, Android) = 0.1425 <0.25, KL (Marie-Hélène, Ios) = 0.075 <0.25. These sub-concepts are: Java, Android and Ios.

Conclusion

The traces are very important elements in collaborative environments. Their analysis aims to understand and follow the learning of a learner or group of learners and qualify the use, usability and acceptability of collaborative environment to make it more adaptive. In this paper, we proposed an architecture for a recommendation system for the learner. This architecture is based on an original model of the learner tak-ing into account the definition of data (learning indicators). A knowledge base containing this information was constructed. Interaction data recorded were used to construct indicators of learners' state, group state and the progression of the training session. The absence of such indicators in current learning and teaching environments has allowed us to justify our work. We have chosen to use a Bayesian formula to calculate the knowledge level of a learner on a concept of the application ontology describing the pedagogical content of training.

We are currently working to deploy the recommendation module within the environment E-MEMORAe2.0 in order to test it with students from the University of Setif.

Fig. 1 .

 1 Fig. 1. Architecture of the recommendation system

Fig. 2 .

 2 Fig. 2. Part of the application ontology "Information Technology"

Fig. 4 .

 4 Fig. 4. Relationship between our learner model and a Bayesian network.

Fig. 5 .

 5 Fig. 5. The knowledge model in the platform E-MEMORAe 2.0

Table 1 .

 1 Summary of users' actions of group 1

		Elsa	Jean-Paul	Ning	Marie-Hélène	Total
	Java	0(0C,0R,0A)	0(0C,0R,0A)	0(0C,0R,0A)	0(0C,0R,0A)	0(0C,0R,0A)
	WP	0(0C,0R,0A)	2(1C,1R,0A)	1(0C,0R,1A)	2(0C,1R,1A)	5(1C,2R,2A)
	Android	4(1C,3R,0A)	8(4C,3R,1A)	3(1C,1R,1A)	5(4C,1R,0AS)	20(10C,8R,2A)
	Ios	5(2C,1R,2A)	0(0C,0R,0A)	5(2C,2R,1A)	1(0C,0R,1A)	11(4C,3R,4A)
	Tablet	0(0C,0R,0A)	1(0C,1R,0A)	2(1C,0R,1A)	3(0C,2R,1A)	6(1C,3R,2A)
	Computer	3(2C,0R,1A)	0(0C,0R,0A)	2(0C,0R,2A)	0(0C,0R,0A)	5(2C,0R,3A)
	Software	4(2C,1R,1A)	0(0C,0R,0A)	4(1C,2R,1A)	3(1C,1R,1A)	11(4C,4R,3A)
	Hardware	2(1C,1R,0A)	1(0C,1R,0A)	2(1C,0R,1A)	3(0C,2R,1A)	8(2C,4R,2A)
	Info_Tech	1(1C,0R,0A)	1(1C,0R,0A)	1(1C,0R,0A)	1(1C,0R,0A)	4(4C,0R,0A)
	Total	19(9C,6R,4A)	13(6C,6R,1A)	20(7C,5R,8A) 18(6C,7R,5A)	60(28C,24R,18A)

The contribution by the activities.

For a learner i in a space S, the index of the contribution by activities AC(i, j) for a concept j is calculated as follows:

With n: the number of types of activities, in our case n = 3. P(k): the weight of the type of activity k (consultation, creation or addition), contribution_value(k) : is relative frequency estimated by the ratio between the number of activities of type k performed by the learner in the group and the number of all activities of type k performed by all the members of the group S. contribution_value is either consulta-tion_value, creation_value or addition_value.

Example: for the concept "Android", suppose that: Poids_consultation = 0.2, Poids_création = 0.5 and Poids_addition = 0.3. Using table1, we calculate the contribution by the activities of the members of group 1 for this concept (Table 2). Table 2. Contributions by the activities of the users of group1 for "Android". We calculate the contribution by activities of Marie-Hélène for all the concepts. The contribution by sub-knowledge .

Consulta-tion_value

Crea-tion_value

Addi-tion_value

For a learner i, the index of contribution by sub-knowledge for a concept j KC(i, j) is equal to:

n is the number k of the sub-concepts related to the father concept j. P (k): the weight attached to each sub-concept k. (These weights are defined in the ontology of application).

Example: The concept "Android" has no sub concepts thus: KC(Marie-Hélène, Android) = 0

The Global contribution (mastery degree). Now, the mastery degree or the knowledge level of the learner i on the concept j KL(i, j) is equal to: KL(i, j) = P1 * AC(i, j) + P2 * KC(i, j) (4) P1 and P2 are the weights connected to both contributions (activities_contribution and knowledge_contribution respectively).

Example: The concept "Android" has no sub-concept. So the only contribution for this concept is the contribution by activities (P1 = 1, P2 = 0). KL(Marie-Hélène, Android) = P1 * AC (Marie-Hélène, Android) + P2 * KC (Marie-Hélène, Android) KL (Marie-Hélène, Android) = 1*0.1425 + 0*0 = 0.1425 Table 5 summarizes Marie-Hélène mastery levels for high-level concepts. Now, we will infer the mastery degree of Marie-Hélène for the concepts Software, Hardware and Information Technology. Suppose, for these concepts, the weight attached to activities P1 = 0. 5 summarizes Marie-Hélène mastery levels for high-level concepts.

Table 5. Knowledge levels of "Marie-Hélène" for high-level concepts. • task: the task we have to recommend the user to do it. It is either consult resources, add resources, create resources or consult other concepts.

• (o1, o2, ..., on): all users of the space s that can help the user u in achieving the task task.

Recommendation algorithm.

Input: Indicators model, P: Person, S: Space, C: Concept,  : threshold between 0 and 1/n (n: of members of the group). RB : Recommandations Base.

Output: Recommendations Knowledge. According to our model, if the mastery degree of a concept is below a certain threshold. Our algorithm can determine if this is due to the fact that the student has not


Tahar Mehenni
email: tmehenni@univ-msila.dz

Multiple Guide Trees in a Tabu Search Algorithm for the Multiple Sequence Alignment Problem

Keywords: Multiple sequence alignment, Tabu search, Neighborhood, Guide tree

Nowadays, Multiple Sequence Alignment (MSA) approaches do not always provide consistent solutions. In fact, alignments become increasingly difficult when treating low similarity sequences. Tabu Search is a very useful meta-heuristic approach in solving optimization problems. For the alignment of multiple sequences, which is a NP-hard problem, we apply a tabu search algorithm improved by several neighborhood generation techniques using guide trees. The algorithm is tested with the BAliBASE benchmarking database, and experiments showed encouraging results compared to the algorithms studied in this paper.

Introduction

Multiple sequence alignment (MSA) is a very interesting problem in molecular biology and bioinformatics. Although the most important regions of DNA are usually conserved to ensure survival, slight changes or mutations (indels) do occur as sequences evolve. Methods such as sequence alignment are used to detect and quantify similarities between different DNA and protein sequences that may have evolved from a common ancestor.

Sequence alignment is the way of inserting dashes into sequences in order to minimize (or maximize) a specified scoring function [START_REF] Abbas | Bioinformatics and management science: some common tools and techniques[END_REF][START_REF] Shyu | Multiple sequence alignment with evolutionary computation[END_REF]. There are two classes of sequencing; pairwise sequence alignment (PwSA) and multiple sequence alignment (MSA). The latter is simply an extension of pairwise alignments that align 3 or more sequences. Both MSA and PwSA can further be categorized as global or local methods. As global methods attempt to align entire sequences, local methods only align certain regions of similarity.

The majority of multiple sequence alignment heuristics is now handled using progressive approach [START_REF] Kemena | Upcoming challenges for multiple sequence alignment methods in the high-throughput era[END_REF]. Progressive also known as hierarchical or tree methods, generate a multiple sequence alignment by first aligning the most similar sequences and then adding successively less related sequences or groups to the alignment until the entire query set has been incorporated into the solution. Sequence relatedness is described by the initial tree that is based on Pair wise alignments which may include heuristic Pair wise alignment methods. Some well-known programs using progressive strategies are ClustalW [START_REF] Thompson | ClustalW: improving the sensitivity of progressive multiple sequence weighting, position-specific gap penalties and weight matrix choice[END_REF], Muscle [START_REF] Edgar | MUSCLE: Multiple sequence alignment with high accuracy and high throughput[END_REF], MULTAL [START_REF] Higgins | Multiple sequence alignment, Protein Structure Prediction -Methods and Protocols[END_REF] and T-COFFEE [START_REF] Notredame | T-Coffee: a novel method for fast and accurate multiple sequence alignment[END_REF]. This approach has the advantages of speed and simplicity. However, its main disadvantage is the local minimum problem, which comes from the greedy nature of the approach.

Another approach is to prune the search space of the Dynamic Programming (DP) algorithm for simultaneously aligning multiple sequences, e.g., MSA [START_REF] Gupta | Improving the practical space and time efficiency of the shortest-paths approach to sum-of-pairs multiple sequence alignment[END_REF][START_REF] Lipman | A tool for multiple sequence alignment[END_REF], OMA [START_REF] Reinert | An iterative method for faster sum-of-pairs multiple sequence alignment[END_REF] etc. Algorithms of this approach often find better quality solutions than those of the progressive approach. However, they have the drawbacks of complexity, running time and memory requirement, so they can only be applied to problems with a limited number of sequences (about 10).

The iteration-based approach is also applied to the multiple sequence alignment. Iterative alignment methods produce alignment and refine it through a series of cycles (iterations) until no further improvements can be made. It is deterministic or stochastic depending on the strategy used to improve the alignment. This approach includes iterative refinement algorithms, e.g,. PRRP [START_REF] Gotoh | Significant improvement in accuracy of multiple protein sequence alignments by iterative refinement as assessed by reference to structural alignments[END_REF], simulated annealing [START_REF] Kim | Multiple sequence alignment using simulated annealing[END_REF], genetic algorithms (SAGA [START_REF] Notredame | SAGA: Sequence alignment by genetic algorithm[END_REF], MAGA [START_REF] Yokoyama | A web server for multiple sequence alignment using genetic algorithm[END_REF]), Ant Colony [START_REF] Blum | An ant colony optimization algorithm for DNA sequencing by hybridization[END_REF] and Swarm Intelligence [START_REF] Lalwani | A review on particle swarm optimization variants and their applications to multiple sequence alignments[END_REF]. Therefore, they can evade being trapped in local minima.

In this paper, we present an iteration-based approach using tabu search features to find the global alignment of multiple sequences, where the neighbors are generated using a set of operations on the guide tree of the initial solution.

The remaining of the paper is organized as follows. In section 2, we present the related work in MSA using tabu search. Section 3, describes our algorithm. Experimental results are presented in section 4 and the study is concluded in section 5.

Related Work

Tabu Search (TS) [START_REF] Glover | Tabu Search[END_REF][START_REF] Glover | A user's guide to tabu search[END_REF] was developed by Fred Glover in 1988. It was initiated as an alternative local search algorithm addressing combinatorial optimization problems in many fields like scheduling, computer channel balancing, cluster analysis, space planning etc. Tabu search is an iterative heuristic approach that uses adaptive memory features to align multiple sequences. The adaptive memory feature, a tabu list, helps the search process to avoid local optimal solutions and explores the solution space in an efficient manner.

In [START_REF] Riaz | Multiple sequence alignment using tabu search[END_REF], authors propose a tabu search algorithm for multiple sequence alignment. The algorithm implements the adaptive memory features typical of tabu searches to align multiple sequences. Both aligned and unaligned initial solutions are used as starting points for this algorithm. Aligned initial solutions are generated using Feng and Doolittles progressive alignment algorithm [START_REF] Feng | Progressive sequence alignment as a prerequisite to correct phylogenetic trees[END_REF]. Unaligned initial solutions are formed by inserting a fixed number of gaps into sequences at regular intervals. The quality of an alignment is measured by the COFFEE objective function [START_REF] Notredame | COFFEE: an objective function for multiple sequence alignments[END_REF]. In order to move from one solution to another, the algorithm moves gaps around within a single sequence and performs block moves. This tabu search uses a recency-based memory structure. Thus, after gaps are moved, the tabu list is updated to avoid cycling and getting trapped in a local solution.

[17] develops in his thesis several tabu searches that progressively align sequences. He begins by a simple tabu, called Tabu A, using Dynamic Programming (DP). Then, he proposes other modified versions of tabu search, using at each time a new feature for the previous algorithm, like subgroups alignment, intensification and diversification.

In this paper, we develop a novel tabu search algorithm, by adapting similar procedures of Tabu search developed by [START_REF] Lightner | A Tabu Search Approach to Multiple Sequence Alignment[END_REF], and adding a new and efficient technique for generating neighbors using guide trees.

Algorithm overview

We first give a general description of the tabu search components of our method (initial solution, neighborhood generation and intensification method), and then provide a summarizing pseudo-code description of the main algorithm.

Tabu search works by starting from an initial solution, and iteratively explores the neighborhood of current solution by generating the moves called neighbors. In each iteration, the neighbors are evaluated through the alignment score and the best neighbor, provided it is not in the tabu list, is selected and applied to the current solution. This produces a new current solution for the next iteration. The applied neighbor is added to the tabu list and it is not allowed for a specified number of iteration called tabu tenure.

Initial Solution

The generation of an initial solution is an important step towards getting a final improved alignment. A good initial solution can effectively converge faster and hence cut the computational cost. The initial solution of the tabu search is represented by a tree that is generated using the neighbor-joining guide tree (NJ) [START_REF] Saitou | The neighbor-joining method: a new method for reconstructing phylogenetic trees[END_REF], which fixes the order of the partial alignments in the progressive alignment.

The NJ method constructs guide trees by clustering the nearby sequences in a stepwise manner. In each step of the sequence clustering, it minimizes the sum of branch lengths, selecting the two nearest sequences/nodes and joining them. Next, the distance between the new node and the remaining ones is recalculated. This process is repeated until all sequences are joined to the root of the guide tree. Figure 1 gives an example of a guide tree produced by 5 sequences.

The MSA is obtained from the tree as follows: the pair of sequences on the lowest level are aligned first. Then, the entire branch containing these two sequences is aligned starting from the lowest level and progressing upward to sequences on higher levels. After the MSA is determined, the alignment is scored. The most popular scoring scheme is the sum of all pairwise alignments score: Sum-of-Pairs Score (SP).

SP = n-1 i=1 n j=i Score(S i , S j ) (1)
where

Score(S i , S j ) = max        (S i-1 , S j-1 ) + s(x i , y j ) (S i-1 , S j ) -d (S i-1 , S j ) + d
where s(x i , y j ) is the score for matching symbols x i and y j and d is the penalty for introducing a gap.

Neighborhood Generation

The neighborhood of the current solution may be generated by one of the four ways: swapping, node insertion, branch insertion or distance variation.

Generation by swapping The simplest way of generating a neighborhood is swapping the order of the sequences (i.e. leaves) while maintaining the same guide tree topology. the number of guide trees generated by swapping is n(n -1)/2, where n is the number of sequences to be aligned. Figure 2 shows two guide trees (b and c) generated from the initial guide tree a by swapping the order of the sequences.

Generation by node insertion Neighbors can be generated from the current solution (i.e. the current guide tree) by performing certain insertions of nodes. The node insertion makes it possible to move a sequence node to another location of the guide tree. This will change the topology of the initial guide tree, and the new guide tree can be considered as a neighbor of the original one.

The neighborhood can be generated randomly by this technique, since the topology of the initial guide tree is not predetermined. However, we can make only n node insertions to obtain exactly n neighbors, by selecting randomly a node to share one of the sequences (leaves) of the guide tree. More precisely, for each sequence, we choose randomly a node and move it to share this sequence, and so on. Generation by branch insertion Another way to generate neighbors from the current guide tree is the branch insertion, which is moving a branch of the guide tree (or a sub-tree) to another location. The new guide tree resulting of this move is considered as a neighbor of the current guide tree. This will change the topology of the initial guide tree. Neighbors are generated randomly by branch insertion move. However, we can make only n branch insertions to generate exactly n neighbors for the current guide tree. For each sequence, we choose randomly a branch (or sub-tree) and move it to share this sequence, and so on. Generation by distance variation The last technique used to generate a neighborhood is the distance variation. Since the initial guide tree is obtained using NJ clustering algorithm, we can produce N different guide trees based on the NJ clustering algorithm, N being defined by the user. Each tree corresponds to a variation of the original obtained by NJ but adding some random noise into the distances in order to introduce some variability. The variation introduced in the guide tree is low enough to keep the distance criteria but significant enough to provide the necessary flexibility to generate multiple alternative trees [START_REF] Orobitg | High performance computing improvements on bioinformatics consistency-based multiple sequence alignment tools[END_REF]. Figure 5 shows two guide trees (b and c) produced by adding variation to distances in the NJ clustering algorithm used to obtain the initial guide tree a.

Intensification Method

Generally, an intensification procedure revisits and examines good solutions. It maintains the good portions of this solution and searches to find a better neighboring solution. When a single MSA continues to have the highest score for many iterations, the intensification phase aims to escape the local minima by taking out a solution from the tabu list and restart another search process.

Tabu Search Algorithm

Our Tabu Search algorithm consists of generating a neighborhood of a multiple sequence σ using the techniques cited above, i.e. Swapping (SWP), Node insertion (NI), Branch insertion (BI) and Distance variation (DV). The best MSA σ having the higher score S max is selected for the next iteration and put in the tabu list T abuList. This process is iterated until a T max global running time is met . The pseudo-code of our tabu search algorithm is given in Algorithm 1. The details of this algorithm are explained below.

After generating an initial solution using NJ clustering algorithm, its score is computed. While a time execution T max is not reached, the tabu search is iteratively executed. Each iteration begins by generating the neighborhood of the current solution by one of the techniques among: Swapping, Node insertion, Branch insertion, Distance variation. For each neighbor, we compute its score in order to set the best neighbor having the highest score as the new current solution. This new solution is inserted in the tabu list which has a variable length depending on the number of iterations with or without improvement. If there is improvement in a certain number of continuously iterations, the length is increased in order to insert other possible solutions. The length of tabu list is decreased if within many iterations there is no improvement. In this case, a solution will be get out from the tabu list in order to restart another search process in the intensification mode.

Algorithm 1 Tabu Search Algorithm for MSA

1: procedure GTreeTabu 2:
Generate σ an initial MSA using NJ algorithm; 3:

Smax:=Score(σ); σmax := σ; TabuList:=[]; 4:

while not Tmax do 5:

Generate a neighborhood N (σ) using: SWP, NI, BI or DV. 6: set σ such that 7:

S σ :=max η∈N (σ) Score(η) and σ / ∈ TabuList 8:

if S σ > Smax then 9:

Smax := S σ ; σmax := σ 10:

Insert σ in TabuList 11:

end if 12:

set σ:=σ 13:

end while 14: end procedure

Experimental results and discussion

The proposed approach is implemented in MATLAB and tested on Intel Core i3-380M Laptop with 2 GB. To demonstrate the effectiveness of our approach, we have evaluated it on BAliBASE 2 benchmark base [START_REF] Bahr | BAliBASE (benchmark alignment database): enhancements for repeats, transmembrane sequences and circular permutations[END_REF]. BAliBASE is a database of manually refined multiple sequence alignments. It can be viewed at http://wwwigbmc.u-strasbg.fr/BioInfo/BAliBASE2/index.html or can be downloaded from ftp://ftp-igbmc.u-strasbg.fr/pub/BAliBASE2/.

BAliBASE database is divided into five reference sets. Reference 1 contains alignments of equidistant sequences of similar length, with no large insertions or extensions. Reference 2 aligns up to three "orphan" sequences (less than 25% identical) from reference 1 with a family of at least 15 closely related sequences. Reference 3 consists of up to 4 sub-groups, with less than 25% residue identity between sequences from different groups. The alignments are constructed by adding homologous family members to the more distantly related sequences in reference 1. Reference 4 contains alignments of up to 20 sequences including N/Cterminal extensions (up to 400 residues), and Reference 5 consists of alignments including internal insertions (up to 100 residues) [START_REF] Bahr | BAliBASE (benchmark alignment database): enhancements for repeats, transmembrane sequences and circular permutations[END_REF].

We analyzed the tabu search results from two aspects. The very first set of tests was aimed at to verify the efficiency of our techniques of generating the neighborhood. The techniques are: Swapping (SWP), Node Insertion (NI), Branch Insertion (BI) and Distance Variation (DV). For each neighborhood technique, we ran an extensive set of tests on all the datasets provided by BAliBASE, and computed the scores. The scores using tabu search with each neighborhood generation technique are shown in Table 1. The Number of Test Cases in Reference 1, Reference 2, Reference 3, Reference 4 and Reference 5 are respectively 82, 23, 12, 12 and 12. One can see in Table 1 that all the neighborhood generation techniques perform well in average for all the reference sets. However, it seems that Branch In order to verify the efficiency of our algorithm, we performed another set of tests where the results of our tabu search algorithm using a certain neighborhood technique is compared to other MSA tools. For each references set, we use the adequate neighborhood generation technique which gives the best results, and compare it to the most competitive MSA tools in the literature, such as CLUSTALW 1.83 [START_REF] Thompson | ClustalW: improving the sensitivity of progressive multiple sequence weighting, position-specific gap penalties and weight matrix choice[END_REF], SAGA [START_REF] Notredame | SAGA: Sequence alignment by genetic algorithm[END_REF], MUSCLE [START_REF] Edgar | MUSCLE: Multiple sequence alignment with high accuracy and high throughput[END_REF], ProbCons [START_REF] Do | ProbCons: Probabilistic consistency-based multiple sequence alignment[END_REF], T-Coffee [START_REF] Notredame | T-Coffee: a novel method for fast and accurate multiple sequence alignment[END_REF], SPEM [START_REF] Zhou | SPEM: improving multiple sequence alignment with sequence profiles and predicted secondary structures[END_REF], PRALINE [START_REF] Simossis | PRALINE: a multiple sequence alignment toolbox that integrates homology-extended and secondary structure information[END_REF], IMSA ( [4] and Tabu Search developed by [START_REF] Riaz | Multiple sequence alignment using tabu search[END_REF] (called in this paper TS-Riaz) . Except for SAGA and TS-Riaz, which are taken from [START_REF] Riaz | Multiple sequence alignment using tabu search[END_REF], the results of the other programs are taken from the work of Layeb et al. [START_REF] Layeb | A new greedy randomized adaptive search procedure for multiple sequence alignment[END_REF].

The results of our method illustrate clearly the effectiveness of using Tabu Search to perform the multiple sequence alignment. As it can be seen in Table 2, our algorithm performs well in all the references sets. Our method gives good results compared to the other MSA tools. In fact, it gives the second best score for the sequences set Reference 4, the third best score for Reference 3 and Reference 5, and it is in the fourth place for the remaining sets, i.e. Reference 1 and Reference 2. We can see in Table 2 that our Tabu search using Branch Insertion neighborhood technique has a good place for three sequences sets over five, i.e. Reference 2, Reference 4 and Reference 5. Using the Distance Variation

Conclusion

In this paper we have demonstrated the efficiency of using tabu search to align multiple sequences. Our algorithm uses several neighborhood generation techniques. To evaluate our approach, we have used BAliBASE benchmark. Firstly, we studied different techniques to produce the neighborhood, then we compared our algorithm to the most recent and competitive MSA tools. We have observed through experiments on BAliBASE that for Reference 1 and Reference 2, the alignments generated by our method are encouraged. For the remaining references, tabu search performs better than most of the other methods studied in this paper.

There are several issues for future work. First, tabu search comes with a number of parameters that can be experimented with to observe the respective effect on the search process. The parameters like tabu list size, tabu tenure, termination criteria, and neighborhood size can have a direct influence on the quality of the final alignment. Further studies are needed to test different scoring schemes and tabu search features.

Fig. 1 :

 1 Fig. 1: An example of a guide tree generated by NJ Clustering Algorithm as Initial solution for the Tabu Search.

2 Fig. 2 :

 22 Fig. 2: Two examples of neighbors generated by swapping technique from the initial solution.

Fig. 3 :

 3 Fig. 3: Two examples of neighbors generated by node insertion technique from the initial solution.

Figure 4 2 Fig. 4 :

 424 Fig. 4: Two examples of neighbors generated by branch insertion technique from the initial solution.

a)Fig. 5 :

 5 Fig. 5: Examples of neighbors generated by distance variation technique from the initial solution.

Table 1 :

 1 Results given by tabu search using four neighborhood generation techniques on the BAliBASE benchmark database.Insertion and Distance Variation give the best results for all the sequences of Reference 2, Reference 3, Reference 4 and Reference 5. Node insertion gives best results for sequences of Reference 1. We can see that, for all the datasets provided by BAliBASE, Swapping is not the adequate neighborhood technique. This can be explained by the nature of the neighbors generated by a certain technique. For the Swapping technique, the neighbors have the same topology, so they are not very different and this will not give more amelioration of the alignment score. For the rest of techniques, the neighbors have not the same topology, but Branch insertion and Distance variation techniques seem to generate more complex guide trees, and this will give more chances to explore different solution spaces and thus, ameliorate the alignment score.

	Neighbor-Reference Reference Reference Reference Reference Average
	hood	1	2	3	4	5
	SWP	90.0	93.0	76.3	87.4	85.1	86.36
	NI	90.1	90.0	78.5	85.6	93.3	87.50
	BI	90.05	93.8	80.7	93.7	97.9	91.23
	DV	90.0	93.5	82.0	91.8	95.1	90.48

Table 2 :

 2 Results given by Tabu Search using neighborhood techniques compared with other methods on the BAliBASE benchmark database. neighborhood technique gives the third best score for Reference 3 set, and Node Insertion gives the fourth best score for Reference 1. It can be seen overall, that our tabu search method using Branch Insertion neighborhood technique gives in average the second best score compared to the other algorithms studied in the paper.

	Method Reference Reference Reference Reference Reference Average
		1	2	3	4	5
	CLUSTALW	85.8	93.3	72.3	83.4	85.8	84.12
	SAGA	82.5	95.4	77.7	78.0	86.8	84.08
	MUSCLE	90.3	64.4	82.2	91.8	98.1	85.36
	ProbCons	90.0	94.0	82.3	90.9	98.1	91.06
	T-Coffee	86.8	93.9	76.7	92.1	94.6	88.82
	SPEM	90.8	93.4	81.4	97.4	97.4	92.08
	PRALINE	90.4	94.0	76.4	79.9	81.8	84.5
	IMSA	83.4	92.1	78.6	73.0	83.6	82.14
	TS-Riaz	76.0	88.9	71.5	77.3	90.5	80.84
	TS-SWP	90.0	93.0	76.3	87.4	85.1	86.36
	TS-NI	90.1	90.0	78.5	85.6	93.3	87.50
	TS-BI	90.05	93.8	80.7	93.7	97.9	91.23
	TS-DV	90.0	93.5	82.0	91.8	95.1	90.48


Zianou Ahmed Seghir
email: zianou_ahmed_seghir@yahoo.fr

Fella Hachouf

Full-reference image quality assessment measure based on color distortion

Keywords: Gradient similarity, quality assessment, test image, Color distortion, color space

The purpose of this paper is to introduce a new method for image quality assessment (IQA). The method adopted here is assumed to be Full-reference measure. Color images that are corrupted with different kinds of distortions are assessed by applying a color distorted algorithm on each color component separately. This approach use especially YIQ color space in computation. Gradient operator was successfully introduced to compute gradient image from the luminance channel of images. In this paper, we propose an alternative technique to evaluate image quality. The main difference between the new proposed method and the gradient magnitude similarity deviation (GMSD) method is the usage of color component for the detection of distortion. Experimental comparisons demonstrate the effectiveness of the proposed method.

Introduction

Over the past decade, image quality assessment methods based objective methods have grown significantly to tackle problems of image assessment. The challenge of these problems is to construct an algorithm that can automatically predict perceived quality of image.

There is no doubt that the subjective test is the most accurate measure for quality assessment because it reflects the true human perception. On the other hand, it is time consuming and expensive. There are three kinds of measures that are used for objective image quality assessment, full-reference (FR), reduced-reference (RR) and noreference (NR). In this paper, the discussion is confined to FR metrics, where the reference images are available.

There has been extensive work on objective image quality assessment. The most popular method for full reference image quality assessment is the Structural Similarity Index [START_REF] Wang | Image quality assessment: From error measurement to structural similarity[END_REF] (SSIM). It contains three parts: Luminance Comparison, Contrast Compari-son and Structure Comparison. However, it fails in measuring the badly blurred images [START_REF] Guan-Hao | Gradient-based structural similarity for image quality assessment[END_REF]. In [START_REF] Seghir | Edge-region information measure based on deformed and displaced pixel for Image Quality Assessment[END_REF], an approach based on edge-region information, distorted and displaced pixels (ERDDM) is developed. Initially, the test and reference images are divided into blocks of 11×11 pixels, and then distorted and displaced pixels are calculated which can be used to compute the global error. In [START_REF] Zhang | Practical image quality metric applied to image coding[END_REF], DTex metric is proposed with consideration of the texture masking effect and contrast sensitivity function. In [START_REF] Liu | Image quality assessment based on gradient similarity[END_REF], it was shown that the masking effect and the visibility threshold can be combined with structure, luminance and contrast comparison to create the image quality measure (gradient similarity measure (GSM)). Most Apparent Distortion (MAD) designed in [START_REF] Larson | Most apparent distortion: Full-reference image quality assessment and the role of strategy[END_REF][START_REF] Larson | Full-Reference Image Quality Assessment and the Role of Strategy: The Most Apparent Distortion[END_REF] yields two quality scores, i.e., visibility-weighted error and the differences in log-Gabor subbands statistics. The proposed measure in [START_REF] Zhang | FSIM: A feature similarity index for image quality assessment[END_REF] applies phase congruency [START_REF] Kovesi | Image features from phase congruency[END_REF] to image quality measure. This measure differs in their correlations with the subjective quality and carrying out times. Gradient magnitude similarity deviation (GMSD) is proposed [START_REF] Xue | Gradient Magnitude Similarity Deviation: A Highly Efficient Perceptual Image Quality Index[END_REF], where the pixel-wise gradient magnitude similarity (GMS) is used to capture image local quality, and the standard deviation of the overall GMS map is computed as the final image quality index.

The gradient images are sensitive to image distortions, whereas different local structures in a distorted image suffer different degrees of degradations. This motivates us to investigate the use of global variation of gradient based local quality map for overall image quality prediction. In fact, color deformation cannot be well differentiated by gradient. In addition, the gradient is computed from the luminance channel of images. Therefore, to make the image quality assessment measures own the ability to deal with color distortions, chrominance information should be taken into consideration.

The aim of this paper is to improve the GMSD to take color distortion in consideration. As a result, we use a proposed gradient operator and YIQ color space [START_REF] Yang | Efficient gamut clipping for color image processing using LHS and YIQ[END_REF] to produce gradient image and color distortion from the reference and test images, respectively.

The rest of the paper is organized as follows. In Section 2, our proposed image quality measure is defined. In section 3, performance of the proposed method is compared with others measures using images with different types of distortion. We finish by the conclusion.

Proposed method

Before introducing the proposed measure notion, some useful concepts must be visited. The reference and test images are represented by and respectively. The proposed method uses gradient similarity and Color distortion to form map. In addition, all variables used in the proposed method are defined next:

Ref

Gradient similarity

In order to reflect the differences between Ref and Dis at the local level, we compute image gradient of the reference and test images. Different operators are used to compute the image gradient, such as the Sobel operator [START_REF] Jain | Machine Vision[END_REF], the Prewitt operator [START_REF] Jain | Machine Vision[END_REF] and the Scharr operator [START_REF] Jähne | Handbook of Computer Vision and Applications[END_REF], and in this paper a new gradient operator is proposed, which shows very favorable outcome. It defines as:

Gx Gy Mask ( )/11 111( )
This later consists of a pair of 3×3 convolution kernels and is used for detecting vertical and horizontal edges in images.

The partial derivatives Gx and Gy of an image are computed as:

√ (1)
Also, the gradient operators (G) of the reference and test images are computed. As a result, the G 2 and G 1 of the test and reference images are produced, respectively.

The gradient similarity is computed in proposed method and hence the Gradient map (

) is formed as

(2)

Color space transformation

The color distortion cannot be differentiating by gradient. Hence, to make the image quality assessment measures possess the ability to deal with color distortions, special considerations are given to chrominance information. As a result, these formulas approximate the conversion between the RGB color space and YIQ

[1] [ ] [ ] [ ] (3)
Let I 1 (I 2 ) and Q 1 (Q 2 ) be the I and Q chromatic channels of the reference and distorted images respectively. Similar to the definitions of CFI_map and CFQ_map, the similarity between chromatic features is defined as follows: [START_REF] Seghir | Edge-region information measure based on deformed and displaced pixel for Image Quality Assessment[END_REF] The similarity between the chrominance components (color distortion map) is simply defined as:

(5)

Global error

Finally, the gradient similarity based Color distortion map (GSCD_map) is expressed as: [START_REF] Zhang | Practical image quality metric applied to image coding[END_REF] The total gradient similarity based Color distortion measure (GSCDM) is defined as the standard deviation of the GSCD map:

√ ∑ ∑( ̅̅̅̅̅̅̅̅ ) (7)
Where

̅̅̅̅̅̅̅̅ ∑ ∑ (8)
Flowchart depicting computation of the proposed measure is shown in Fig. 1.

Results

In order to evaluate the accuracy of the proposed method; we follow the standard performance assessment procedures utilized in the video quality expert's group (VQEG) FR-TV Phase II test In equation ( 9), the logistic regression function is introduced which is employed for the nonlinear regression.

(9) ( 9
)
Where VQR is the value of the objective method and θ 1 , θ 2 , θ 3 , θ 4 , θ 5 are selected for the most excellent fit.

In this test, four metrics are used [START_REF] Wang | Information content weighting for perceptual image quality assessment[END_REF]: the Root mean square prediction error (RMSE), the Spearman rank-order correlations coefficient (ROCC), Kendall rankorder correlation coefficient (KROCC) and The Pearson linear correlation coefficient (CC). ROCC and KROCC evaluate the prediction monotonicity. CC and RMSE assess the prediction accuracy. ROCC, KROCC and CC are better with values closer to 1 or -1. Thus, RMSE is better when its values are small. The first index CC (Pearson linear correlation coefficient) is defined by: [START_REF] Larson | Categorical Image Quality (CSIQ) Database[END_REF] Where the index i denotes the image sample and n denotes the number of samples. The second index is the Spearman rank-order correlations coefficient (ROCC); it is defined by:

         2 2 1 ) ) ( ( ) ) ( ( ) ) ( )( ) ( ( p p n i p p DMOS i DMOS DMOS i DMOS DMOS i DMOS DMOS i DMOS CC
) 1 ( )) ( ) ( ( 6 1 2 2      n n i DMOS i DMOS ROCC p (11)
The third index is Kendall rank-order correlation coefficient (KROCC) [START_REF] Chok | Pearson's Versus Spearman's and Kendall's Correlation Coefficients for Continuous Data[END_REF]. It is designed to capture the association between two ordinal variables. Its estimate can be expressed as follows:

∑ ∑ (12) where: ( ) { ( ) ( ) ( ) and ( ) { ( ) ( )
( )

The forth one is the Root mean square prediction error (RMSE) between subjective (DMOS) and objective (DMOS P ) scores. It is defined by:

      n i p i DMOS i DMOS n RMSE 1 2 ) ( ) ( 1 (13)
To judge the performance of the proposed approach, four kinds of databases are used: TID2008 database [START_REF] Ponomarenko | Tampere Image Database 2008 TID2008[END_REF], CSIQ database [START_REF] Larson | Categorical Image Quality (CSIQ) Database[END_REF], LIVE database [START_REF] Sheikh | Image and Video Quality Assessment Research at LIVE 2004[END_REF] and TID2013 database [START_REF] Ponomarenko | Color image database TID2013: Peculiarities and preliminary results[END_REF]. The characteristics of these four databases are summarized in table 3.

The performance of GSCD metric is compared with PSNR, SSIM [START_REF] Wang | Image quality assessment: From error measurement to structural similarity[END_REF][START_REF] Gaubatz | Metrix MUX Visual Quality Assessment Package: MSE, PSNR, SSIM[END_REF], Multiscale-SSIM (MS-SSIM) [START_REF] Wang | Multi-scale structural similarity for image quality assessment[END_REF][START_REF] Gaubatz | Metrix MUX Visual Quality Assessment Package: MSE, PSNR, SSIM[END_REF], Visual Singal-to-Noise Ratio (VSNR) [START_REF] Chandler | VSNR: A wavelet-based visual signal-to-noise-ratio for natural images[END_REF][START_REF] Gaubatz | Metrix MUX Visual Quality Assessment Package: MSE, PSNR, SSIM[END_REF], Visual Information Fidelity (VIF) [START_REF] Sheikh | Image information and visual quality[END_REF][START_REF] Gaubatz | Metrix MUX Visual Quality Assessment Package: MSE, PSNR, SSIM[END_REF], Information Fidelity Criterion (IFC) [START_REF] Sheikh | An information fidelity criterion for image quality assessment using natural scene statistics[END_REF][START_REF] Gaubatz | Metrix MUX Visual Quality Assessment Package: MSE, PSNR, SSIM[END_REF], Noise Quality Measure (NQM) [START_REF] Damera-Venkata | Image quality assessment based on degradation model[END_REF][START_REF] Gaubatz | Metrix MUX Visual Quality Assessment Package: MSE, PSNR, SSIM[END_REF], DTex [START_REF] Zhang | Practical image quality metric applied to image coding[END_REF], GSM [START_REF] Liu | Image quality assessment based on gradient similarity[END_REF], MAD [START_REF] Larson | Most apparent distortion: Full-reference image quality assessment and the role of strategy[END_REF][START_REF] Larson | Full-Reference Image Quality Assessment and the Role of Strategy: The Most Apparent Distortion[END_REF], ERDDM [START_REF] Seghir | Edge-region information measure based on deformed and displaced pixel for Image Quality Assessment[END_REF], GSMD [START_REF] Xue | Gradient Magnitude Similarity Deviation: A Highly Efficient Perceptual Image Quality Index[END_REF] and FSIM [START_REF] Zhang | FSIM: A feature similarity index for image quality assessment[END_REF].

A comparative study of Sobel, Perwitt, Scharr and proposed operator is presented in Table 1 (TID2008 database is used in this experience), from which proposed operator could accomplish better performance than the other three. Furthermore, the choice of YIQ color space needs to be proved. To this end, we run the proposed method with different four color spaces. The results are summarized in table 2 (TID2008 database is used in this experience). The classification of the performance of all measures according to their ROCC values is presented in Table 8 reveal the reliability of the GSCD. Tables 4, 5, 6 and7 show the obtained results. The top three measures for each assessment measure are highlighted in bold. We can see that the top methods are mostly GSCD, GMSD, FSIM and MAD. GSCD correlates much better with the subjective results than the other measures. Looking at the curves (Fig. 2), the GSCD values are very close to DMOS and MOS, proving the efficiency of this measure. Moreover, an interesting result is obtained from the comparison of the GSCD with GMSD, FSIM and MAD in Tables 5 (TID2008 database). The values of ROOC are close to 1; this means that GSCD has a similar performance as the methods or earlier works. Results clearly indicate that our GSCD measure performs quite well and is competitive with other IQA measures.

In addition, to compare the efficiency of different models, the average execution time required an image of size 512×384 is calculated (the image is taken from TID2008 database). All metrics were run on a TOSHIBA Satetillete T130-11U notebook with Intel Core U4100 CPU@1.30 GHz and 3G RAM. The software platform used to run all metrics was MATLAB R2007a (7.4.0). Table 8 shows the required time in seconds per image. It is shown in Table 9 that the proposed measure takes more time than the PSNR, the GMSD, and the SSIM and it is faster than the Fsim.

VIF, VSNR, IFC, MS-SSIM, GSM, MAD, DCTex, NQM and ERDDM also take much longer processing time than the proposed method.

Moreover, we adjusted the parameters based on a dataset of TID2008 database. The adjusting measure was that the parameters values giving to a higher ROCC would be chosen. As a result, the parameters required in the proposed method were set as: C 1 = 100, C 2 =2050.

Conclusion

This paper describes an efficient method for image quality assessment. Its main feature is that this new method uses the gradient similarity and color distorted measure. The reference and test images are transformed respectively using color distorted and gradient mask. The difference between the reference and test images is computed using simple function. A comparative study has been carried in this work.

The obtained results are competitive with the previous works. Future works following this study will include the use of others characteristics to assess image quality.

  [5]. The objective and subjective scores [5], are fitted with the logistic function. Five parameters non-linear mapping (θ 1 , θ 2 , θ 3 , θ 4 and θ 5 ) are utilized to change the set of quality ratings by the objective quality measures to a set of the predicted Difference Mean Opinion Score (DMOS/MOS) values denoted DMOS P /MOS P .

Fig. 1 .

 1 Fig. 1. Image quality assessment method

Fig. 2 .

 2 Fig. 2. Scatter plots of subjective scores versus scores from the proposed scheme on IQA databases

Table 1 .

 1 ROCC and KROCC values using four gradient operators

	Gradient operator	Sobel	Perwitt	Scharr	Proposed operator
	ROCC	0.8983	0.8996	0.8963	0.9000
	KROCC	0.7143	0.7171	0.7104	0.7175

Table 2 .

 2 ROCC and KROCC values using four color spaces

	Color space	Lab	ycbcr	HSV	YIQ
	ROCC	0.7684	0.8937	0.2983	0.9000
	KROCC	0.5789	0.7110	0.2125	0.7175

Table 3 .

 3 Four databases and their characteristics

	Database	Source Images	Distorted Images	Distortio n Types	Image Type	Observers
	TID2008	25	1700	17	color	838
	CSIQ	30	866	6	color	35
	LIVE	29	779	5	color	161
	TID2013	25	3000	25	color	971

Table 4 .

 4 Performance comparison for image quality assessment measures on live database

	Method	ROCC	KROCC	CC	RMSE
	PSNR	0.8756	0.6865	0.8723	13.3597
	SSIM	0.9479	0.7963	0.9449	8.9454
	MS-SSIM	0.9513	0.8044	0.9409	9.2593
	VSNR	0.9280	0.7625	0.9237	10.4694
	VIF	0.9632	0.8270	0.9598	7.6670
	IFC	0.9259	0.7579	0.9268	10.2643
	NQM	0.9086	0.7413	0.9122	11.1926
	ERDDM	0.9496	0.8128	0.9619	6.3204
	DCTex	0.9483	0.8066	0.9443	8.9897
	GSM	0.9554	0.8131	0.9437	9.0376
	MAD	0.9669	0.8421	0.9674	6.9235
	Fsim	0.9645	0.8363	0.9613	7.5296
	GMSD	0.9603	0.8271	0.9603	7.622
	GSCD	0.9596	0.8222	0.9538	8.2074

Table 5 .

 5 Performance comparison for image quality assessment measures on TID2008 database

	Method	ROCC	KROCC	CC	RMSE
	PSNR	0.5794	0.4210	0.5726	1.1003
	SSIM	0.7749	0.5768	0.7710	0.8546
	MS-SSIM	0.8542	0.6568	0.8451	0.7173
	VSNR	0.7049	0.5345	0.6823	0.9810
	VIF	0.7496	0.5868	0.8090	0.7888
	IFC	0.5675	0.4236	0.7340	0.9113
	NQM	0.6243	0.4608	0.6142	1.0590
	ERDDM	0.5961	0.4411	0.6685	0.998
	DCTex	0.4973	0.4095	0.5605	1.1113
	GSM	0.8554	0.6651	0.8462	0.7151
	MAD	0.8340	0.6445	0.8306	0.7474
	Fsim	0.8840	0.6991	0.8762	0.6468
	GMSD	0.8907	0.7094	0.8788	0.6404
	GSCD	0.9000	0.7175	0.8830	0.629

Table 6 .

 6 Performance comparison for image quality assessment measures on TID2013 database

	Method	ROCC	KROCC	CC	RMSE
	PSNR	0.6396	0.4698	0.669	0.9214
	SSIM	0.7417	0.5588	0.7895	0.7608
	MS-SSIM	0.7859	0.6047	0.8329	0.6861
	VSNR	0.6812	0.5084	0.7402	0.8392
	VIF	0.6769	0.5147	0.7720	0.7880
	IFC	0.5389	0.3939	0.5538	1.0322
	NQM	0.6432	0.474	0.6858	0.9023
	ERDDM	0.5623	0.4124	0.6352	1.230
	DCTex	0.5863	0.4573	0.6495	0.9425
	GSM	0.7946	0.6255	0.8464	0.6603
	MAD	0.7807	0.6035	0.8267	0.6975
	Fsim	0.8510	0.6665	0.8769	0.5959
	GMSD	0.8044	0.6343	0.859	0.6346
	GSCD	0.8681	0.6855	0.8819	0.5844

Table 7 .

 7 Performance comparison for image quality assessment measures on CSIQ database

	Method	ROCC	KROCC	CC	RMSE
	PSNR	0.8005	0.5984	0.7998	0.1576
	SSIM	0.8756	0.6907	0.8612	0.1334
	MS-SSIM	0.9133	0.7393	0.8990	0.1150
	VSNR	0.8104	0.6237	0.7993	0.1578
	VIF	0.9195	0.7537	0.9277	0.0980
	IFC	0.7671	0.5897	0.8384	0.1431
	NQM	0.7402	0.5638	0.7433	0.1756
	ERDDM	0.8626	0.6781	0.8295	0.1466
	DCTex	0.8042	0.6420	0.7915	0.1605
	GSM	0.9126	0.7403	0.8979	0.1156
	MAD	0.9467	0.7970	0.9502	0.0818
	Fsim	0.9310	0.7690	0.9192	0.1034
	GMSD	0.957	0.8133	0.9541	0.0786
	GSCD	0.9602	0.8194	0.9578	0.0755

Table 8 .

 8 Ranking of IQA metrics' performance on four databases

	Method	Live	TID2008 TID2013	CSIQ
	PSNR	14	12	11	12
	SSIM	10	7	7	8
	MS-SSIM	7	5	5	6
	VSNR	11	9	8	10
	VIF	2	8	9	5
	IFC	12	13	14	13
	NQM	13	10	10	14
	ERDDM	8	11	13	9
	DCTex	9	14	12	11
	GSM	6	4	4	7
	MAD	1	6	6	3
	Fsim	3	3	2	4
	GMSD	4	2	3	2
	GSCD	5	1	1	1

Table 9 .

 9 Running time of the competing IQA models

	Method	Time (second)	Method	Time (second)
	PSNR	0.0493	ERDDM	9.6089
	SSIM	0.1917	DCTex	0.5327
	MS-SSIM	1.1304	GSM	1.4003
	VSNR	1.5018	MAD	15.6235
	VIF	5.1429	Fsim	2.4990
	IFC	4.6738	GMSD	0.1602
	NQM	1.8846	GSCD	0.4361