Abdallah Dib

Nicolas Beaufort

Franc ¸ois Charpillet

A Real Time Visual SLAM For RGB-D Cameras Based on Chamfer Distance and Occupancy Grid

We present a feature based visual SLAM method that uses chamfer distance to estimate the camera motion from RGB-D images. The proposed method does not require any matching which is an expensive operation and always generates false matching that affects the estimated camera motion. Our approach registers the input image iteratively by minimizing the distance between the feature points and the occupancy grid using a distance map. We demonstrate with real experiments the capability of the method to build accurate 3D map of the environment with a hand-held camera. While the system was mainly developed to work with RGB-D camera, occupancy grid representation gives the method the ability to work with various types of sensors, we show the capacity of the system to construct accurate 2D maps using telemeter data. We also discuss the similarities between the proposed approach and the traditional ICP algorithm.

I. INTRODUCTION

Our objective is to develop a home assistant robot for elderly people at home. Localization and mapping are a key points for us. We are interested in visual SLAM from RGB-D cameras only. Visual SLAM has been widely investigated in the literature. Recently after the release of the low cost RGB-D cameras (e.g. Kinect, Asus Xtion), indoor visual SLAM has become an active field in the research area of robotics and computer vision.

In this paper, we present a robust visual SLAM method with 6 degrees of freedom using chamfer distance with occupancy grids. Features are first extracted from point cloud and multiple hypotheses are generated from the features by transforming the original set on different axis (for each degree of freedom). Each hypothesis is evaluated with the distance map. The best hypothesis is selected and the process is repeated iteratively, the final transformation matrix of the best hypothesis represents the estimated camera motion. We show with experiments in real conditions the accuracy of the method and we provide a real time implementation of the system using GPGPU technology. The main contribution of this paper is the use of chamfer distance extended to 3D with occupancy grid to minimize the distance between an RGB-D image and the occupancy grid that represents the model of the world. The paper is divided as follow: we start with a background on visual SLAM, occupancy grids and Chamfer distance. Next we present our approach and we discuss the similarities 1 Inria, Villers-lès-Nancy, 54600, France. 2 Université de Lorraine, LORIA, UMR 7503, Vandoeuvre-lès-Nancy, 54506, France.

3 CNRS, LORIA, UMR 7503, Vandoeuvre-lès-Nancy, 54506, France.

(first.second)@inria.fr between the proposed method and the ICP algorithm. Experiments are presented in section V followed by a conclusion.

II. BACKGROUND

A. Visual SLAM

Visual SLAM can be split into two major parts: sparse (feature based) and dense. Sparse SLAM uses few points in the image for pose estimation, while dense SLAM uses the whole image for registration. Dense methods use all pixels in the image for registration. The first dense odometry methods were introduced by [START_REF] Comport | Real-time quadrifocal visual odometry[END_REF].

A dense method based on RGB-D cameras is described in [START_REF] Tykkala | Direct iterative closest point for real-time visual odometry[END_REF]. These methods use the Lucas-Kanade framework [START_REF] Lucas | An iterative image registration technique with an application to stereo vision[END_REF] for image alignment by minimizing the photometric error between two consecutive images. A detailed discussion and various optimizations of the Lucas-Kanade framework is provided in [START_REF] Baker | Lucas-kanade 20 years on: A unifying framework[END_REF].

Alternatively, ICP based methods, as introduced by [START_REF] Besl | A method for registration of 3-D shapes[END_REF], minimize a geometrical error distance. ICP methods require to perform at each iteration of the algorithm an expensive nearest neighbour search. A KD-tree is used by [START_REF] Friedman | An algorithm for finding best matches in logarithmic expected time[END_REF] to accelerate the nearest neighbour search. A cache for accelerating KD-tree based ICP is introduced by [START_REF] Nuchter | Cached k-d tree search for ICP algorithms[END_REF].

Recently, [START_REF] Newcombe | Kinectfusion: Real-time dense surface mapping and tracking[END_REF] introduced KinectFusion, a system developed by Microsoft for the Kinect SDK, that uses a variant of the ICP algorithm to align the whole image to the scene model. Microsoft introduced a real-time implementation of the ICP algorithm using GPGPU technology. While Dense SLAM uses the whole image for registration, sparse methods use visual features extraction such as Harris [START_REF] Harris | A combined corner and edge detector[END_REF], FAST [START_REF] Rosten | Machine learning for high-speed corner detection[END_REF], SIFT [START_REF] Lowe | Object recognition from local scale-invariant features[END_REF] or SURF [START_REF] Bay | Speededup robust features SURF[END_REF]. These features are tracked and used to estimate the camera motion. RANSAC [START_REF] Fischler | Random sample consensus: A paradigm for model fitting with applications to image analysis and automated cartography[END_REF] is used to remove inconsistent featurs matches [START_REF] Torr | MLESAC: A new robust estimator with application to estimating image geometry[END_REF] [15] [START_REF] Nister | Visual odometry for ground vehicle applications[END_REF].

B. Occupancy Grid

Occupancy grids, as introduced by [START_REF] Elfes | Using occupancy grids for mobile robot perception and navigation[END_REF], consist of segmentation of the 3D world into voxels. This grid can be seen as a representation of the world, where each voxel within the map holds a probability of its occupancy state. A high probability signifies that the cell is occupied, while a lower probability signifies that the cell is free (not occupied by objects of the environment). The accuracy of the grid depends on its resolution, which is the size of each cell within the grid. Smaller cell size gives better approximation of the environment, but requires more processing time and memory. Using occupancy grids has many advantages, for example, when working with various sensor data it becomes easy to combine different sensor in the same occupancy grid (e.g. multiple cameras, LIDAR). Another advantage is that, when working with RGB-D cameras, a huge amount of points in the point cloud can be reduced using occupancy grids. Occupancy grids can be seen as a tool for compression.

C. Distance Map

Chamfer distance was originally used in 2D image processing, in order to exploit the information contained in the features present in the input image, notably the edges. [START_REF] Gavrila | 3-d model-based tracking of humans in action: a multi-view approach[END_REF] derived a corrective term from the edge response, using a distance map or chamfer distance. In image processing, a distance map is created from the edge image, where each pixel in the distance map represents the distance to the closest data pixels in the edge image. This distance map can be used for object matching, Matching is done by translating the object (also known as template) at various locations of the distance image. The matching function is determined by the pixel values of the distance image, which lies under the data pixels of the transformed template. The lower these values are, the better the match between image and template at this location is. The distance map can be determined in two passes thought the image feature array, by a process known as chamfering [START_REF] Rosenfeld | Distance functions on digital pictures[END_REF].

In this paper we use a similar process described above for matching a feature set extracted from a point cloud with the occupancy grid. A distance map is created from the occupancy grid, next the set (template) is moved at various locations on the distance map in order to find the transformation (rotation and translation) that minimizes the distance between the feature points and the distance map.

III. APPROACH

In this section we describe our SLAM method for RGB-D cameras. Figure 1 shows the pipeline of the system. First the point cloud is constructed from the depth image received at instant t. Feature points are extracted from the point cloud and a distance map is created from the occupancy grid. Our method does not need features matching, instead it uses the distance map created from the occupancy grid to estimate the camera motion by minimizing the distance between the feature points and the map.

A. System overview

The point cloud is created from the the depth image by back-projecting each pixel into a 3D point using the following equations: pixel coordinates in the image, (f x , f y , c x , c y ) are respectively the focal and optical center of the depth camera called intrinsic parameters. These parameters can be obtained by a camera calibration process [START_REF] Zhang | A flexible new technique for camera calibration[END_REF], and Z(p) is the depth value for each pixel in the depth image. Normal vectors are calculated for the point cloud and features are extracted. Section III-B describes the feature extraction method. These feature points are filtered by projecting them to the occupancy to remove points that project to the same voxel, in order to obtain a correct chamfer distance. This part is described in detail in the section III-D.

X d = (u -c x ) f x × Z(p), Y d = (v -c y ) f y × Z(p), Z d =Z(p),
Next, a distance map is created from the occupancy grid, the feature points are moved (translated and rotated) on the distance map to estimate the camera movement and register the image. This is done by generating multiple hypotheses from the features set. Each hypothesis is obtained by translating and rotating the original set on the different axes X, Y, Z respectively. A score is calculated for each hypothesis by projecting it to the distance map. The hypothesis with lower distance is selected and the process is repeated until the distance reaches a certain threshold. The final transformation matrix of the best hypothesis corresponds to the estimated camera movement. Finally, after registering the new image, the occupancy grid is updated with the point cloud.

Let F i be the set of 3D voxels positions of the occupancy grid, and let F j be the set of feature points positions extracted at instant t. Our objective is to find the transformation that minimizes the distance between these two sets of points. This can be solved using a traditional ICP pipeline, first by Fj Fj1 Fj0 Fji Fjn

...

Generate Hypothesis on X axis

Generate Hypothesis on Y axis

Generate Hypothesis on Z axis

Fig. 2. Hypothesis generation strategy. The algorithm starts on X axis and the hypotheses are obtained by a translation of F j within a defined interval and evaluated using the distance map. The one that has the closest distance (in green) is selected for the next step. This step is repeated for the 6 DOF (translation and rotation on X, Y and Z axis).

associating points using the nearest neighbour search, then by estimating the rigid transformation between the two data sets using a least square method. In contrast to the ICP algorithm, our method does not require point matching.

To find the transformation (rotation and translation) between the two sets, a distance map DM is created from the occupancy grid. Next, hypotheses F j0 , F j1 , ..., F jn are generated from the features set F j for each axis respectively. Each hypothesis is obtained by transforming F j on each axis within an interval I k . The algorithm starts on X axis and the generated hypotheses obtained by a translation on X axis are evaluated using the distance map DM . The best hypothesis that has the closest distance to F i is selected and used for the Y axis and so on. The process is repeated for the 6 DOF (translation and rotation).

For instance, we start on X axis, for an interval of I k = [-2cm..2cm] and a step of 1 cm, five hypothesis are generated, the first one is obtained by translating the original set by -2 cm, the second by translating the set by -1 cm etc... The five hypotheses are evaluated on the distance map, and the one that has the closest distance to F i is selected, the selected hypothesis on X axis is used to generate hypotheses on the Y axis and so on. Figure 2 illustrates the hypothesis generation strategy.

B. Feature Extraction

Our feature extraction method is based on normal vectors. Normal vectors are invariant when observed from different angles. We used a simple normal vector estimation method. We refer the reader to [START_REF] Hoppe | Surface reconstruction from unorganized points[END_REF], where a robust method for normal estimations is proposed by fitting a least square plane to each vertex neighbours. Our implementation of vertex normals estimation is obtained by using an average of the normal vectors of the triangles formed by P and its neighbours as shown in Figure 3. For each Point p in the point cloud, The average of normal vectors composed of the two adjacent vectors is taken within a window. for each adjacent points q j and q j+1 if they are close enough to p we calculate the normal of the triangle composed by the two vectors as follow: pq j and pq j+1 .

N i = pq j ∧ pq j+1 ,
The final normal at point P is the average of the all the normals.

N = N i n ,
where n is equal to the number of triangles. Points that are at a distance greater than a certain threshold are excluded from the normal vector computation. Next, edge features from normal vectors are extracted using a technique similar to the one described in [START_REF] Dryanovski | Real-time pose estimation with rgb-d camera[END_REF] by applying an edge detector filter on the normal vectors. Figure 4 shows the results of the features extraction method.

C. Distance Map Update

This section describes the steps for creating the distance map used to minimize the distance between the feature points and the occupancy grid.

First, Feature points F j are filtered by projecting them to the occupancy grid and removing points that lie within the same voxel (this is described in details in the section III-D). The distance map is initialized by setting the occupied voxels of the grid to 0 and to infinity otherwise. The algorithm 1 describes the steps for creating the distance which is the most expensive process in the algorithm. In order to accelerate it, unlike typical chamfering methods, in our implementation we only shift the 3 x 3 x 3 window up to a certain distance. We consider that after that distance, there is no need to continue updating the map. This is illustrated with the number N in the algorithm 1 that tells the number of iterations to perform the map update.

Algorithm 1: Distance Map update input : F i , F j input : Window(Wx, Wy, Wz) input : Iterations number N output: Distance Map DM / * initialize distance map * / IntializeDistanceMap(DM , F i) 1 / * update distance map * / for iter < N do 2 foreach cell c i in DM do 3 (i x , i y , i z ) = IndexInMap(c i ) 4 dist ← DM (i x , i y , i z ) for i = 1 to W x do 5 for j = 1 to W y do 6 for k = 1 to W z do 7 tmp ← √ i + j + k 8 dist2 ← DM (i, j, k) 9 if (dist + tmp) < dist2 then 10 DM (i, j, k) ← (dist -tmp) 11 D. Score
Each cell in the distance map represents the distance to the closest point in F i . F j is transformed by each interval I k and projected to the distance map.

The distance for each scan F j to F i is calculated as follow:

distance(F i , F j ) = 1 n × n k d 2 k , (1)
where d k is the value read from the distance map that corresponds to where the feature point projects (figure 5). As shown in figure 5, depending on the resolution of the map, multiple points can project to the same cell in the map, which affects the score because the same distance is counted multiple times. A filtering step is required, in order to keep only one point projects to the cell and to remove other 3D points from the features set. This is done by projecting the feature points set F j to the occupancy grid and eliminating points that occupy the same voxel in the gird and keeping only one point.

IV. SIMILARITY WITH THE ICP ALGORITHM

In section, we discuss the similarity between the method described above and the ICP algorithm. In ICP, the nearest neighbour search step consists of finding for each point in the first set the nearest neighbour in the second set of points. The next step in ICP is to find the transformation matrix that minimizes the distance between the associated points, this is done by minimizing the following non-linear least square function:

f (T ) = 1 n × k (A k -T × B k ) 2 , (2)
where A k and B k are the associated points and T is the homogeneous representation of the transformation matrix.

In our method, the value stored in each cell of the distance map corresponds to the distance to the closest point in F i . By comparing equation 1 and 2 it can be seen that the same function is being minimized. In both methods, the sum of squared distance of closest neighbour is being minimized with the only difference that ICP uses a geometrical distance and in the chamfer distance a discrete distance is used. In contrast to the ICP algorithm, our method does not need to perform a nearest neighbour search because the distance map stores in each cell the distance to the closest point in F i .

V. EXPERIMENTAL RESULTS

Experiments were made in real conditions and we used a hand-held Kinect to build the map of the environment. The system runs on an intel i7 processor quad core equipped with a Nvidia Quadro 6000 GPU. The algorithm is implemented on GPU using CUDA. The size of the Occupancy grid is equal to 20 x 20 x 3 meters with a resolution of 5 cm. Figure 6 shows the reference model of the environment. Figure 7 shows the 3D map obtained by the SLAM. The black holes in the map correspond to zones that were not observed by the camera when moving. The furnitures of the 3D model in the image 6 are not placed at the same position as in the real world. Figure 9 shows the superposition of the 3D reference model of the apartment, with the 3D map generated by the SLAM. The image shows that the walls of the reference model (red) match visually the map generated by the SLAM. bounded by a maximum value. Obtaining a distance close to zero does not mean that the algorithm has found the correct transformation matrix of the camera, the algorithm can converge to a local minimum while keeping a distance close to zero. Our SLAM method like all the existing methods depends on scene and on the features extracted. One advantage of our features extraction method that it is based on scene geometry and does not uses the RGB image and works in dark scenes.

A. Robustness and Convergence Speed

In terms of convergence speed, the algorithm converges in few iterations. In all the tests we did, the algorithm converges in less then 20 iterations. The number of iterations required for convergence depends on the camera movement between two frames, for small camera movement, the algorithm converges in less then 10 iterations.

B. 2D SLAM using telemeter

An important feature of using the occupancy grid, is that it can be adapted to various type of sensors. In this section we tested the SLAM with a Hokuyo telemeter with 30 meters and 270 degrees detection range with 0.25 degrees of angular resolution. The only modification to the method is that no feature extraction is performed. The whole scan is used for matching with the occupancy grid. Figure 10 shows the 2D map generated by the system.

VI. CONCLUSION

In this paper, a new SLAM method is presented that uses chamfer distance with occupancy grid for RGB-D cameras. The approach does not require feature matching. Instead, the distance between feature points and the occupancy grid is minimized using a distance map. We showed with experiments in real conditions the capacity of the method to construct 3D map of an environment using a hand-held RGB-D camera. We also showed the method works with other type of sensors (the telemeter). We provided a real time implementation using GPGPU technology. We also discussed the similarities between our SLAM and the traditional ICP method.

FilteringFig. 1 .

 1 Fig. 1. The pipeline of SLAM system.

Fig. 3 .

 3 Fig. 3. Normal vectors estimation for point cloud

Fig. 4 .

 4 Fig. 4. a) Point cloud. b) Normal vectors. c) Derivation of normal vectors. d) Features points displayed in red.

Fig. 5 .

 5 Fig. 5. Projection of a features set to the distance map. Multiple points can project to the same cell position, that is why a filtering step is needed.

Fig. 6 .

 6 Fig. 6. A 3D model of the apartment with different rooms.

Fig. 7 .

 7 Fig. 7. The 3D map obtained by the SLAM.

Figure 8 Fig. 8 .

 88 Figure8shows the evolution in time of the distance between the final transformed feature points obtained by the pose estimation algorithm and the occupancy grid. The figure shows that the chamfer distance is close to zero and

Fig. 9 .

 9 Fig. 9. The superposition of a 3D model (only ground and walls displayed in red) with the map obtained by the SLAM.

Fig. 10 .

 10 Fig. 10. The 2D map obtained by the SLAM using the telemeter..

2014 IEEE/ASME International Conference on Advanced Intelligent Mechatronics (AIM) Besançon, France, July 8-11, 2014 978-1-4799-5736-1/14/$31.00 ©2014 IEEE


Jiuqiang Chen
email: chenj@lri.fr

Sarah Cohen-Boulakia

Christine Froidevaux
email: christine.froidevaux@lri.fr

Carole Goble
email: carole.goble@manchester.ac.uk

Paolo Missier
email: paolo.missier@ncl.ac.uk

Alan R Williams
email: alanrw@cs.man.ac.uk

DistillFlow: Removing redundancy in Scientific Workflows [Demonstration proposal]

Keywords: Scientific workflows structures, Refactoring, Anti-patterns

Scientific workflows management systems are increasingly used by scientists to specify complex data processing pipelines. Workflows are represented using a graph structure, where nodes represent tasks and links represent the dataflow. However, the complexity of workflow structures is increasing over time, reducing the rate of scientific workflows reuse. Here, we introduce DistillFlow, a tool based on effective methods for workflow design, with a focus on the Taverna model. Dis-tillFlow is able to detect "anti-patterns" in the structure of workflows (idiomatic forms that lead to over-complicated design) and replace them with different patterns to reduce the workflow's overall structural complexity. Rewriting workflows in this way is beneficial both in terms of user experience and workflow maintenance.

INTRODUCTION

Scientific workflows management systems [START_REF] Missier | Taverna, reloaded[END_REF][START_REF] Goecks | Galaxy: a comprehensive approach for supporting accessible, reproducible, and transparent computational research in the life sciences[END_REF][START_REF] Ludäscher | Scientific workflow management and the kepler system[END_REF] are increasingly used to specify and manage in-silico experiments to easily design complex data processing pipelines. However, while the number of available scientific workflows is increasing, workflows are not (re)used and shared as much as they could be [START_REF] Starlinger | re)use in public scientific workflow repositories[END_REF][START_REF] Cohen-Boulakia | Search, adapt, and reuse: the future of scientific workflows[END_REF]. Several causes for the limited workflow reuse have been identified (e.g., [START_REF] Zhao | Why workflows breakunderstanding and combating decay in taverna workflows[END_REF]). In the present work we focus on the complexity of workflow structure -that involves the number of nodes and links but is also related to intricate workflow structure features -as the important cause that we want to consider.

In recent prior work [START_REF] Cohen-Boulakia | Distilling structure in taverna scientific workflows: a refactoring approach[END_REF], we have proposed a workflow refactoring approach that aims at automatically detecting parts of the workflow structure which can be simplified by removing explicit redundancy (we call these idiomatic structures "anti-patterns"). The workflow rewriting process which reduces the complexity is then performed without altering the original workflow semantics (defined as the ability of both workflows to provide the same outputs given the same inputs). Our main contention is that such a reduction in complexity can be performed automatically, and that it will be beneficial both in terms of user experience and operational efficiency. Extensive comparison of our approach to related work is provided in [START_REF] Cohen-Boulakia | Distilling structure in taverna scientific workflows: a refactoring approach[END_REF].

In this companion demo paper, we introduce the DistillFlow system which implements a full refactoring approach of the workflows from the Taverna workflow management system [START_REF] Missier | Taverna, reloaded[END_REF], which for the past ten years has been popular especially within the bioinformatics community.

In the remainder of this paper we summarize the main principles of the refactoring approach we propose (Section 2); Section 3 introduces the architecture of DistillFlow while Section 4 provides the main functionalities of the tool that will be highlighted during the demonstration. We conclude the paper in Section 5.

REFACTORING

The aim of our approach is to provide a refactoring procedure to reduce the complexity of workflows. More precisely, our goal is to replace several occurrences of the same processor with one single occurrence whenever possible, while following several assumptions: (i) the processors we consider are deterministic (the same output is produced given the same input); (ii) only processors implemented using the exact same code can be merged (in our setting, two processors are equivalent if they represent identical web service calls, or they contain the same script, or they are bound to the same executable Java program). In practice, condition (ii) is often realized, because processors are duplicated during workflow design by means of a graphical "copy and paste" operation. Figure 1 introduces the two generic patterns and the transformation rules we have so far considered ; these rules allow the rewritting of anti-patterns into patterns without redundancy. Figure 2 provides an example of workflow where equivalent processors have been highlighted.

More precisely, anti-pattern A deals with simple redundancy where the same processor P appears with r occurrences (denoted P (1) ...P (r) in the figure) and each occurrence takes the exact same input (and can be thus replaced by one single occurrence). Anti-pattern B depicts a more complex case where the various occurrences of the same processor have only part of their inputs in common. In the rewritten pattern, input data that differ from one occurrence to another (L l t+1 to L l k ) have been merged using the merge processors provided by Taverna (the circle icon) to construct lists of data from the original data items to exploit the implicit it-erative process of Taverna. As a consequence, the rewritten pattern contains a list split processor called SP LITr to decompose the list obtained as output into r pieces to ensure that the downstream fragment of the workflow remains unchanged.

The DistillFlow algorithm removes as many anti-patterns as possible, following a recursive process. This paper omits the details about the way we carefully apply rewriting rules and how we consider the various strategies followed by the processors when dealing with lists of input data (cross and dot strategies, see [START_REF] Cohen-Boulakia | Distilling structure in taverna scientific workflows: a refactoring approach[END_REF] for more information on this point).

DISTILLFLOW ARCHITECTURE

The architecture of DistillFlow, implemented in Java, is introduced in Figure 3. The process of transforming a Taverna workflow is described as follows. The user provides the specification of the workflow to be considered. The TavernaLoader module is then responsible for loading the workflow into the DistillFlow internal graph structure. The Anti-pattern Checker module determines whether or not the workflow taken in contains anti-patterns and provides a report with graph features, including the identification of antipatterns (if any) and a list of anti-patterns that the system recommends to remove. The user can interact (using the UserCollaboration module) with each item of such a list to visualize the corresponding information on the specification graph. If the workflow contains anti-patterns, then the list of anti-patterns selected by the user (possibly all anti-patterns) is sent to the Anti-pattern Remover module which removes them. The user can visualize the workflow obtained and decide to stop considering additional anti-patterns. When the user is fine with the workflow obtained, the TavernaLoader module produces the rewritten workflow into the Taverna XML format. Our implementation is flexible and includes both a library of anti-patterns and a library of rewriting rules (algorithms) making it possible and easy to consider more anti-patterns and rewriting rules in the future.

DEMONSTRATION SKETCH

Users communicate with DistillFlow by loading and interacting with original and rewritten workflows. The demonstration will present the following functionalities of the system, based on the workflow of Figure 2.

Loading Data. Users start using DistillFlow by loading a workflow specification into the system (see Figure 4). The original picture of the workflow from myExperiment is displayed by DistillFlow if available (panel (4)), together with a report on graph features (metadata on the workflow, panel (2)). The anti-patterns are determined and the list of antipatterns displayed in panel (3) while using colors to help users easily distinguish different anti-patterns on the workflow graph ("brown" is related to anti-pattern A while "purple" is related to anti-pattern B). The same color is systematically used on the workflow (to display the nodes involved in an anti-pattern) and on the text listing the anti-patterns (panel (3)).

Refactoring the workflow. Anti-patterns can be removed either all-at-once or in a step-by-step process (selected by the user).

Refactoring all-at-once: DistillFlow allows to automatically remove all the anti-patterns by clicking on the "Remove All anti-patterns" main button (top of Figure 4). Selecting anti-patterns in collaboration with the user: Dis-tillFlow allows the selection of which anti-patterns users want to be removed. By clicking on the anti-patterns information (panel (3)), DistillFlow highlights the corresponding processors on the graph (panel (1)). Then an operation menu (panel (3)) allows the user to perform the remove operations on the anti-patterns. Once all the selected anti-patterns have been removed, the user can click on the Result Overview button (top of Figure 4). The window entitled "Result Overview" depicted in Figure 5 appears. The original (panel (a1)) and distilled workflows (panel (b1)) are displayed.

Interacting with the initial and distilled workflows. To understand which changes have been done between the initial and distilled workflows, users can interact with the two workflows depicted on Figure 5. By clicking on a node of one graph (initial or transformed graph), DistillFlow highlights the "corresponding" processors in the other graph (it shows the correspondence between a set of occurrences of a given processor P in the original graph and a set of occurrences of the processor P in the (possibly partly) distilled workflow). A detailed report of all the anti-patterns is also displayed (panel (d)). By clicking on the items of the anti-pattern information panel, the corresponding processors will be highlighted on the initial workflow and on the rewritten workflow. As an example in Figure 5, the user has clicked on anti-pattern "7-8-9" in the anti-pattern information panel (d) which has automatically highlighted the corresponding anti-pattern both in the initial workflow (panel (a1), in which three nodes are involved) and in the distilled workflow (panel (b1), in which the anti-pattern has been removed by the system, merging nodes "7", "8" and "9", resulting in only one vertex, numbered "7").

Running the distilled workflow : Any workflow distilled by DistillFlow can be opened and run with Taverna. In our demonstration, we will show that the original and transformed workflows have the same semantics: given the same input, they provide the same output using the Taverna engine. The paper introduces a demonstration proposal for DistillFlow, a tool able to aid workflow designers in the minimization of explicit redundancy in scientific workflows. Our tool is available to the community and it is effective in that it is able to take in workflows from the Taverna system and produces to its turn runnable workflows in the Taverna system.

CONCLUSION

Recent keynote talks, tutorials and research papers from the scientific database community show that scientific workflows play a crucial role in data integration and graph-structured data are increasingly complex to deal with. Techniques to reduce the complexity of graph structures and improve the readability and maintenance of scientific workflows are thus of increasing interest. This demonstration is at the intersection of these topic areas, and provides a refactoring tool that is interesting to the scientific database community.

Figure 1 :

 1 Figure 1: Rewritting rules for anti-patterns of kind A and B.

Figure 2 :

 2 Figure 2: Example of workflow where anti-patterns of kind A and B have been highlighted

Figure 3 :

 3 Figure 3: Architecture of DistillFlow

Figure 4 :

 4 Figure 4: Loading a workflow in DistillFlow and visualizing the set of anti-patterns detected.

Figure 5 :

 5 Figure 5: Visualizing both initial workflow and distilled workflow.

DistillFlow is available for use at http://www.lri.fr/


Bryan Brancotte

Bastien Rance

Alain Denise

Sarah Cohen-Boulakia

ConQuR-Bio: Consensus ranking with Query Reformulation for Biological data

This paper introduces ConQuR-Bio which aims at assisting scientists when they query public biological databases. Various reformulations of the user query are generated using medical terminologies. Such alternative reformulations are then used to rank the query results using a new consensus ranking strategy. The originality of our approach thus lies in using consensus ranking techniques within the context of query reformulation. The ConQuR-Bio system is able to query the Entrez-Gene NCBI database. Our experiments demonstrate the benefit of using ConQuR-Bio compared to what is currently provided to users.

Introduction

In Biological research, findings are derived from the proper analysis of experiments which involves comparing at various scales new results obtained to existing data. Over the last three decades, scientists have had to face with an avalanche of data, of different kinds, and reported in a myriad of databases. Public biological databases thus contain more biological data than ever, all available to the scientific community. Large amounts of data can be easily obtained using portals such as Entrez NCBI 6 [14] daily used by the bioinformatics community by submitting key-phrase queries (list of keywords). However, properly querying such portals is not as easy as one may think. Two very similar queries may provide different sets of answers leading to the need for users to try various reformulations of their questions, considering synonymous terms, alternative spellings, various levels of granularity in the concepts involved in their queries (making use or not of the terminologies available such as MeSH [START_REF] Lipscomb | Medical subject headings (mesh)[END_REF] or SNOMED CT [START_REF] Michael Q Stearns | Snomed clinical terms: overview of the development process and project status[END_REF]). Results obtained should then be gathered, compared, and redundancies filtered out... Each set of results is ranked by the portal usually using the relevance as a ranking criteria (number of occurrences of the key-phrase in each piece of results instance). However, when several reformulations are considered, it is not clear how to rank the set of all the collected results, which may involve hundreds of elements. The expected ranking should be able to emphasize answers provided by various reformulations while putting less importance on elements classified as "good" by only a few.

The need for on-the-fly solutions both able to reformulate automatically queries exploiting the various terminologies available and rank answers provided to the user is thus of paramount importance.

In this paper, we introduce the ConQuR-Bio approach, which allows users to query public databases from NCBI while generating automatically all the possible reformulations and provides ranked answers using consensus ranking techniques.

The remainder of this paper is organized as follows. After a description of a set of use cases which have driven the design of our solution (Section 2), Section 3 introduces the architecture of our system. We present the original consensus ranking strategy we follow in Section 4. Section 5 introduces the interface and the main functionalities of the system we have implemented based on the ConQuR-Bio approach (available for use to the community at: http://conqur-bio.lri. fr). Section 6 provides the results obtained by ConQuR-Bio on several biological queries while Section 7 concludes the paper.

Use cases

Our approach is based on one of the most popular tool for querying biological sources, namely, the Entrez portal [START_REF] Sayers | Database resources of the national center for biotechnology information[END_REF] from the National Center for Biotechnology Information (NCBI). More specifically, the kind of queries we consider consists in searching the gene names associated to a given disease by consulting the EntrezGene database [START_REF] Maglott | Entrez gene: gene-centered information at ncbi[END_REF] and focusing answers to human genes. We describe here-after a set of four use cases that we want to consider. Use Case 1 (equivalent reformulations): Let us consider the case of a single user interested in genes involved in the cervical cancer. To express her query, she may type cervix cancer in the search field of EntrezGene. As a result, 460 genes are obtained. Interestingly, her query could have been expressed in two other ways, namely using cervical cancer and cancer of the cervix, leading respectively to 20 and 2 results, with 9 new genes of interest obtained (compared to the original query). Use Case 2 (abbreviations): Another use case is related to the use of abbreviations in queries. Consider searching for genes associated to Attention deficit hyperactivity disorders also known as ADHD. While the full name of the disease returns 144 genes, its abbreviation provides 109 genes with only 74 in common.

Use Case 3 (lexical-based reformulation): Another typical use case consists in considering two users, one from the US the other from the UK, searching for tumor suppressor genes associated to the breast cancer. While the first one enters breast cancer tumor suppressor, the other enters breast cancer tumour suppressor. This orthographic variation leads to huge differences when querying the EntrezGene database: 681 genes are returned with tumor and 291 with tumour, and only 246 genes are common to both queries. Use Case 4 (narrower-term-based reformulation): In a last use case, we consider the case of diseases presenting a variety of subtypes (usually corresponding to multiple phenotypes or a gradient of phenotypes associated with the disease). For example, when the colorectal cancer is hereditary and without polyposis it can be described by various names, including Hereditary Nonpolyposis Colon Cancer, also known as Lynch syndrome. Interestingly, querying the EntrezGene database with Hereditary Nonpolyposis Colon Cancer, and Lynch syndrome, allows to respectively find 1, and 6 genes which were not found when typing colorectal cancer.

From these use cases, the need for automatic reformulation of queries appears clearly as a necessity. Even more importantly, faced with the high number of answers obtained as result of each query (especially when several reformulations are considered), users should be guided in the order to which consider results. The originality of our approach lies in considering alternative reformulations of the user query and exploiting these reformulations to rank the results by order of interest (roughly, genes obtained by a large number of reformulations should be ranked before genes returned by only a few).

The ConQuR-Bio approach

In this section, we introduce ConQuR-Bio (Consensus ranking with Query Reformulation for Biological data) which aims at helping users finding genes associated to a given disease by considering various reformulations of each user query and exploiting such reformulations to rank the list of results. More precisely, our approach takes in several input rankings (several lists of genes, each provided by one reformulation) and outputs a consensus ranking, that is, a unified list considering all the input data ordered such that the disagreements between the list and the input rankings are minimized.

In the following, the main architecture of our approach is first presented, then two focuses are given, on the reformulation module and queries generator module.

General architecture

The standard use of ConQuR-Bio consists in the user providing a key-phrase k (i.e., a list of keywords). The key-phrase is sent (arrow in Figure 1) to the Reformulation Module which decomposes k into a list T of terms and leverage various terminologies to generate the set S of synonyms (cf 3.2). S is then trans-

mitted (through arrow

) to the Queries Generator to be expressed as a set Q of queries (cf 3.3). Q are run online (arrow ) on the selected search engine (in our case, the NCBI web search engine for EntrezGene which provides sets of results ranked by relevance). When all the ranked results R of queries Q have been collected, they are sent to the Median Ranking Module which is in charge of computing a unique consensus ranking, providing an ordering of all the answers (cf 4). Finally, the Results Formatting module enriches the ranking of gene identifiers with names and descriptions.

A few parameters may be tuned by users, such as the selection of the species of interest (by default, Human) or the "Search deeper" option in which the Reformulation Module intends to find more reformulations for each term (details in 3.2). A default configuration is provided.

Reformulation Module

One of the two main modules of ConQuR-Bio is the Reformulation Module. It takes the user key-phrase as input, splits it into a list of terms and returns sets of reformulations for each term. The Reformulation Module leverages several medical terminologies within the UMLS [START_REF] Bodenreider | The unified medical language system (umls): integrating biomedical terminology[END_REF]. The terminologies are described here-after followed by the presentation of the process used to exploit such terminologies in ConQuR-Bio. Terminologies used. ConQuR-Bio makes use of the Unified Medical Language System (UMLS) 7 , a terminology integration system developed at the U.S. Na-tional Library of Medicine (NLM). ConQuR-Bio uses the UMLS API to interact with the Metathesaurus integrating more than 160 medical vocabularies. Our approach particularly benefits from the use of five terminologies covering a wide range of biomedical domains: (i) MeSH [START_REF] Lipscomb | Medical subject headings (mesh)[END_REF], developed at the U.S. NLM and designed for indexing PubMed; (ii) SNOMED CT [START_REF] Michael Q Stearns | Snomed clinical terms: overview of the development process and project status[END_REF], a worldwide used clinical terminology often used as a core for Electronic Health Records; (iii and iv) The two latest versions of the International Classification of Diseases (ICD 9 CM and ICD 10 CM), developed by the World Health Organization and used in hospitals; (v) The Online Mendelian Inheritance in Man (OMIM), cataloging all known genetic diseases in the human genome. Each UMLS concept is categorized with at least one Semantic Type (out of 150+) from the Semantic Network.

The UMLS also provides a broad categorization of Semantic Types into 15 Semantic Groups (including Disorders). Using the Metathesaurus allows to access synonymous terms from the terminologies.

From key-phrase to MeSH terms. MeSH being de facto a lingua franca for biomedical literature querying, ConQuR-Bio starts with finding the largest recognized MeSH terms in the key-phrase provided by the user. More precisely, the key-phrase is decomposed into a list of terms where each term belongs to one terminology, but no concatenation of two or more consecutive terms belongs to any terminology. For example, the query "breast cancer oncogene" matches four MeSH terms "breast" "cancer", "oncogene" but also "breast cancer". The keyphrase is thus decomposed into the two terms "breast cancer" and "oncogene". Reformulation modes. Once the MeSH terms in the query have been identified, ConQuR-Bio may follow two modes to find reformulated terms, leveraging the UMLS to identify synonyms of ( ) the MeSH terms from the original query (default search mode), or ( ) more precise (i.e. narrower) terms and their synonyms. In any case, alternative formulations of the query are generated. When only one reformulation is returned by the default search mode (meaning that the term is recognized but has no synonym) then the second mode (using narrower terms and their synonyms) is used. The second mode is also used in complement of the first mode when the search deeper mode is enabled.

Identifying synonyms (arrow

). The default mode uses the UMLS API exact match search strategy to find UMLS concepts associated with each term. From these concepts, we extract all the synonymous terms from SNOMED CT, ICD9, ICD10 and MeSH, associated with this UMLS concept. For example, the term cervix carcinoma is mapped to the UMLS concept C0302592. This concept includes several synonyms, including Cancer of cervix (from SNOMED CT) and Uterine Cervical Cancer (from MeSH). Identifying narrower terms (arrow ). This alternative mode provides reformulations using narrower terms (in the sense of the organization of the hierarchy), which are thus more precise terms than the terms used in the original query. Synonyms of the narrower terms are also exploited. This mode corresponds to use UMLS API word search strategy. For example, using the "word" search strategy from with the term Long QT syndrome (UMLS concept C0023976) allows to identify several narrower concepts, including Long QT syndrome type 1 (UMLS concept C0035828, for which Romano-Ward syndrome is a synonym). Semantic filtering. As searched terms are all expected to be diseases, only mappings to concepts from the UMLS semantic group Disorders are considered.

Queries generator module

The Queries generator module produces queries from the synonyms found for the terms identified in the user's key-phrase by the Reformulation Module (see 3.2). When the key-phrase has been split into multiple terms, we consider the Cartesian product of the reformulations of each term. Considering a key-phrase k composed of two terms a and b such as k = "a b" and a, resp. b, is reformulated into {a, a }, resp. {b, b }. This module generates queries to search for "a b", "a b", "a b ", "a b ".

The Median ranking module

In this section we present the Median Ranking module, one of the major modules of ConQuR-Bio which provides a unique ranking to the user. This module takes in lists of elements (here, lists of genes), each list being obtained by a given reformulation. It outputs a consensus ranking, that is, a list of all the elements present in the inputs, ordered such that the disagreements between the consensus and the input rankings is minimized.

In the following, we first define the median ranking problem; we then show that a new metric is needed for our approach, and, for this purpose, we define a pseudometric for comparing rankings. Finally, we describe the heuristic that we have developed and tuned to compute consensus ranking, driven by the need to provide an on-the-fly solution.

The Median Ranking Problem

Starting with multiple rankings called input rankings, the Median Ranking Problem consists in finding one ranking able to minimize the distance to the input rankings. When the Kendall-τ distance is considered [START_REF] Kendall | A new measure of rank correlation[END_REF], the input rankings must be over the same elements and the problem of finding an optimal solution is known to be NP-Hard when more than 3 rankings are considered [START_REF] Dwork | Rank aggregation methods for the web[END_REF]. Polynomial-time approximation algorithms and heuristics have thus been proposed (e.g. [START_REF] Fagin | Comparing and aggregating rankings with ties[END_REF][START_REF] Ailon | Aggregation of Partial Rankings, p-Ratings and Top-m Lists[END_REF]). In this paper, we will call consensus the solutions proposed by consensus algorithms (including heuristics or approximation algorithms), while we will use the term median rankings to denote optimal solutions.

We consider here rankings with ties, that is, rankings where some elements may be grouped into one bucket and may thus not been compared to each others. More precisely, each bucket contains at least one element, and two elements have a different rank iff they are in two different buckets. For instance, in the ranking r = [{B, A}, {C}, {D}], the elements A and B are tied in a bucket and thus equally good, they are also better than C and D, and C is better than D.

As underlined in the use cases introduced in section 2, two reformulations may not necessarily provide the same sets of data (i.e., sets of genes obtained may be different from one reformulation to another). Unifying the data sets taken as input is then the first step to achieve to compute the corresponding consensus ranking. ConQuR-Bio makes use of the unification process introduced by [START_REF] Cohen-Boulakia | Using medians to generate consensus rankings for biological data[END_REF] to consider input rankings over different sets of elements. This treatment adds a single bucket at the end of each ranking and places in this bucket all the elements that appear in other rankings but not in the current one. We call such buckets unifying buckets. For example, consider r = [{C}, {E}] and the ranking r introduced above. The unifying process provides the two unified input rankings: r unif ied = [{C}, {E}, {A, B, D} u ] and r unif ied = [{B, A}, {C}, {D}, {E} u ], leading to two input rankings over the same sets of elements (A to E). Note that unified buckets are suffixed: {...} u .

When considering ranking with ties, the distance used in the median ranking problem is the generalized Kendall-τ distance [START_REF] Fagin | Comparing and aggregating rankings with ties[END_REF][START_REF] Cohen-Boulakia | Using medians to generate consensus rankings for biological data[END_REF] defined as follows:

Definition 1. Let r and c be two ranking with ties over n elements, c being a consensus. Let r[i] be the rank of i in ranking r. The generalized Kendall-τ distance is:

K (p) (r, c) = #{(i, j) :r[i] < r[j] and c[i] > c[j] or r[i] > r[j] and c[i] < c[j]} +p * #{(i, j) :r[i] = r[j] and c[i] = c[j] or r[i] = r[j] and c[i] = c[j]} where 0 < p ≤ 1
This distance counts 1 for each pair of elements when their order is inverted, and counts p when two elements are tied in one ranking and not in the other.

The distance between a consensus c and a set of input rankings R is the sum of the distances between c and the rankings in R: K (p) (R, c) = r∈R K (p) (r, c). A median of a set of input rankings is defined as follows:

Definition 2. Let R be the set of all rankings with ties over n elements, and let R ⊆ R be a set of rankings. A ranking c * is called a median ranking of R iff:

K (p) (R, c * ) ≤ K (p) (R,

A new pseudometric to compare rankings

The intuition behind the need for a new metric can be illustrated on the above example. Two points should be emphasized. First, elements A and D are tied in r 3 because the search engine ranked them at the same position, they thus should be considered as equally relevant. Second, elements B and C are tied in r 1 and r 2 due to the unification process, contrary to the previous situation, no search engine has ever indicated any rank between such two elements (neither one before the other, nor both at the same position). The generalized Kendall-τ distance does not allow to make a distinction between elements tied in an unification bucket from those tied in a classical one. A new metric taking into account the nature of buckets has thus to be defined. In particular, the metric should consider true disagreements between elements ranked by several reformulations while not penalizing any difference between the relative positions of elements present in the unifying buckets: our aim is to consider that untying elements from the unifying bucket has no cost. Definition 3. Let r and c be two rankings with ties over n elements. Let r[i] be the rank of i in ranking r. Let unif (r) denote the unification bucket of r. (unif (r) = ∅ if r has no unification bucket.) Let us define M(r, c) as follows:

M(r, c) = #{(i, j) :r[i] < r[j] and c[i] > c[j] or r[i] > r[j] and c[i] < c[j]} +p#{(i, j) :r[i] = r[j] and c[i] = c[j] and i / ∈ unif (c) or r[i] = r[j] and c[i] = c[j] and j / ∈ unif (r)}
Clearly M is not a distance as it may not be always possible to distinguish two different rankings: M([{A}, {B}], [{A, B} u ]) = 0. However, it is a pseudometric [START_REF] Arthur Steen | Counterexamples in topology[END_REF] as the symmetry and triangular inequality properties are respected, and any element has a metric at zero compared to itself: M(r, r) = 0. Similarly to the generalized Kendall-τ distance, when considering a consensus c and a set of input rankings R: M(R, c) = r∈R M(r, c).

(R, c) = 2 + p > M(R, c ) = 2 (note that K (p) (R, c ) = 2 + 3p
). From a user perspective, c is a better median than c as it still promotes A and D, but also makes use of information provided by r 3 such as the fact that B is more relevant than C.

Other strategies have been developed in [START_REF] Dwork | Rank aggregation methods for the web[END_REF] in order to deal with sets of rankings which are not necessarily over the same elements: the induced Kendallτ distance allows to compare a ranking c over all elements with a ranking r over a subset of these elements. The idea is to consider the projection of c onto r, by removing from c all elements that are missing in r. However, this distance is not relevant for our purpose as it does not allow to consider missing elements as being less relevant than the returned ones (the missing elements of r are completely removed from c and thus do not contribute to any (dis)agreement).

Median Ranking in the context of query reformulations

BioConsert [START_REF] Cohen-Boulakia | Using medians to generate consensus rankings for biological data[END_REF] is an heuristic designed in the context of biological data and considers a distance between rankings with ties. It uses each input ranking as starting point, and refines them by iteratively applying two edit operators (moving an element to an existing/new bucket) as long as the distance between the current consensus obtained and the input rankings is reduced. Finally, it returns the best consensus computed. Our approach differs from [START_REF] Cohen-Boulakia | Using medians to generate consensus rankings for biological data[END_REF] by using the pseudometric M, presented in §4.2, instead of the generalized Kendall-τ distance. M is parametrized by 0 < p ≤ 1 which expresses the importance of tying and untying elements. In our setting, tying and untying elements should be penalized while when two elements have the same number of rankings placing one element before and after the other, the two elements should be tied. As a consequence, we have set p = 0.5 in ConQuR-Bio.

Tuning BioConsert. ConQuR-Bio is an on-the-fly system which intends to quickly provide a consensus ranking from the reformulations obtained. To do so, it requires to have a fast and good algorithm to produce the consensus of answers. The time complexity of BioConsert depends, among other parameters, on the number of input rankings m. In order to speed up the computation, we consider a smaller and constant amount of rankings to start the algorithm (and not all input rankings as in [START_REF] Cohen-Boulakia | Using medians to generate consensus rankings for biological data[END_REF]). More precisely, we selected three state-of-theart algorithms: BordaCount [START_REF] De Borda | Mémoire sur les élection au scrutin[END_REF], MEDRank [START_REF] Fagin | Efficient similarity search and classification via rank aggregation[END_REF], and Ailon's 2-approximation [START_REF] Ailon | Aggregation of Partial Rankings, p-Ratings and Top-m Lists[END_REF] which do not provide as good results as BioConsert, but provide solution in at most complexities of nm log(nm), where n is the number of elements to be ranked. Experiments (not shown here) performed to compare this new strategy to the default strategy of BioConsert show that the time to compute a consensus is reduced up to one hundred times while the quality of the results is not significantly altered.

The ConQuR-Bio system

The main interface of ConQuR-Bio is provided in Figure 2 and composed of three areas, the query area (top left panel), the running and progression details (top right panel), and the results (bottom).

In the query area, the key-phrase provided by the user is split into MeSH terms on-the-fly (cf. 3.2) and displayed into colored boxes next to the key-phrase field. Colors indicate different status for a term: green when the term is recognized as a MeSH term, red when the term is not recognized, and orange when the term is matched with an existing MeSH term while the spelling is different. In addition to the orange semantics, when a term is matched with an alternative spelling, a check mark allows the user to accept the correction and update the key-phrase field, while a cross mark forces the system to use the given spelling. Several options are made available to the user, and are by default hidden. They can be displayed/hidden by clicking on "[+]"/"[-]" like in Figure 2). Options are the species considered, the "Search deeper" mode which allows to use reformulations with narrower terms (cf. in 3.2), and the type of biological object ranked.

The results area presents a ranking (with ties) of genes with their official descriptions as it can be found when browsing the NCBI website. Each gene is linked to its associated page in the NCBI Website, allowing the user to navigate in a familiar environment. Close to the rank of each gene, a symbol (hidden in the default mode) allows users to know whether the rank of the gene is raised ( ), equal ( ), lowered ( ), or new ( ) in ConQuR-Bio compared to the results returned in the NCBI ranking.

Another interesting feature is the ability of ConQuR-Bio to provide users with information on the number of publications associated with each gene returned. This functionality is obtained by calling the GeneValorization [START_REF] Brancotte | Gene List significance at-a-glance with GeneValorization[END_REF] tool able to quickly browse PubMed.

Results on medical queries

We have tested our approach over a set of queries collected from collaborators of the Institut Curie (France) and the Children's Hospital of Philadelphia (PA, USA) and linked to their respective fields of expertise. The results presented considered 9 diseases: 7 cancers (bladder, breast, cervical, colorectal, neuroblastoma, prostate, retinoblastoma), one heart disease (the Long QT Syndrome), and one psychiatric disorder (the attention deficit (with) hyperactivity disorder ). For cancers, we searched for information on the name of the cancer while also using additional words (and reformulations of such words) to refine the query, namely tumor suppressor and oncogene. The exact list of words used are shown in Figure 3.

Evaluating such an approach is a difficult task as we face the users' perception of the results. We have chosen to consider three criteria of evaluation, focusing on the 20 first results returned for each key-phrase (top-20). The first criterion is based on Gold Standards and compares the results obtained to the list of expected genes according to our experts. We classically use the area under the ROC curve [START_REF] Bradley | The use of the area under the roc curve in the evaluation of machine learning algorithms[END_REF] in this series of experiments. The next two criteria are bibliometrics ones: the second criterion is the number of publications associated with each gene of the list and the key-phrase while the last criterion is a "freshness" indicator, measuring the average number of days since such an article has been published. The assumptions behind such measures is that well-studied genes are more likely to be relevant and experts can be interested in the latest, up-to-date, information.

Using expertise

We constructed with our clinician collaborators the list l d of the most relevant genes known to be associated with each disease d. The "goodness" of a consensus ranking c d provided by ConQuR-Bio thus relies on the presence of elements of l d in the top-ranked elements of c d . In order to compare the results returned by ConQuR-Bio and the EntrezGene NCBI Web search engine with respect to Gold Standards, we used the Area Under the ROC Curve [START_REF] Bradley | The use of the area under the roc curve in the evaluation of machine learning algorithms[END_REF] (ROC standing for Receiver Operating Characteristic) or AUC (closely related to precision and recall measures [START_REF] Bradley | The use of the area under the roc curve in the evaluation of machine learning algorithms[END_REF]). The AUC aims at differentiating the presence of expected data versus non expected data, taking into account the place of pieces of data (roughly, placing expected data before unexpected data increases the score of the AUC). AUC provides numbers ranged in [0, 1], 1 being the highest score.

In Figure 3, we plot AUCs for the top-20 first results obtained for each key-phrases with both NCBI search engine and ConQuR-Bio. Globally, using ConQuR-Bio compared to NCBI allows to increase in average the AUC of 44.24%. More precisely, four points deserve attention.

First, when focusing on single term key-phrases (i.e., considering the name of the disease only without adding oncogene or tumo[u]r suppressor, corresponding to Figure 3.a and all use cases), ConQuR-Bio returns better results than the NCBI in 88.89% of the cases and always provides as good results as the NCBI. The average AUC is increased of 58.52% with ConQuR-Bio compared to NCBI.

Second, multi-term key-phrases (Fig 3 .b,c (use case 3)) have an AUC increased of 37.70% in average when using ConQuR-Bio compared to NCBI. This relatively less good results (37% vs. 58% of improvement) is actually due to the fact that the term oncogene has, in addition, one reformulation (gene transforming) less interesting (considered as "too vague" by our experts) than others.

Third, considering ADHD and its unabbreviated name (use case 2), the AUC is drastically increased using ConQuR-Bio. Also, as expected the complete name and its abbreviation have different AUCs with the NCBI while remaining the same with ConQuR-Bio (since all the reformulations are considered). In the same spirit, lexical variations around the cervical cancer tumor suppressor ( Finally, there were a few key-phrases, namely colorectal cancer and neuroblastoma, for which only plural reformulations were actually available (no actual synonyms available). The results obtained for such queries are then less impressive than in the previous cases while some of their respective AUCs are still increased compared to NCBI. Our experiments have shown that all the reformulations associated to use cases 1, 2, 3 were taken into account and that using our approach based on consensus ranking systematically improved the answers provided to the user. However, we have not yet provided specific information on the use case 4 which made use of lexical narrower terms. Two points should thus be mentioned.

First, interestingly, narrower terms have actually automatically been exploited in the previous results for the long QT syndrome as this term did not have any synonym. Specific forms of the disease, such as the Romano Ward Syndrome, raise the AUC from 0.51 to 0.53.

Second, the use of narrower terms can be done manually by selecting the "search deeper" option. Back to the example illustrating the use case 4, using narrower terms drastically change the results: among the 11 genes provided by our experts as being very relevant for colorectal cancer, only 2 are in the top-20 results of the NCBI (AUC=0.09) while 6 are in the ConQuR-Bio first 20 answers (AUC=0.43).

A last point that deserves attention is the time taken by ConQuR-Bio to provide answers: While the NCBI search engine provides a ranking in at most 2s, ConQuR-Bio takes 41s in average for the 9 single term key-phrases listed in Figure 3.a. This difference lies in the fact that the average number of synonyms retrieved by ConQuR-Bio (and thus the average number of queries to be answered and which elements should be ranked) is 17.

Using the number of publications

The second measure considers the top-20 genes obtained and sums the number of publications co-citing each gene name and the query key-phrase. As an example, the numbers of publications associated with the top-20 first genes returned for retinoblastoma by the NCBI and ConQuR-Bio are represented in Figure 4. It clearly shows that the top-20 genes provided by ConQuR-Bio are associated to more publications than the top-20 genes provided by NCBI. More generally, over the 28 key-phrases studied, 25 provide more (or, in 2 situation equal) publications than the NCBI. Overall in average, ConQuR-Bio returns top-20 results associated with 56% more publications.

Using publication freshness

While the number of publications is one important factor for determining the level of interest associated to a result, another complementary factor is the freshness of the associated publications (i.e. how recently studies based on a given gene have been published). The measure we consider in this subsection computes the average number of days since the last publication co-citing the gene name and the key-phrase has been published.

Over the 28 key-phrases studied, and when considering the top-20 genes, ConQuR-Bio returns genes with fresher results for 22 of them. In average, the top-20 genes returned by ConQuR-Bio have one associated article which was published within 25% less days that the NCBI ones.

Discussion

With ConQuR-Bio, we made the connection between the query expansion field and the median ranking field. We leveraged terminologies integration in the UMLS system (an approach and system shown to be effective [START_REF] Demner-Fushman | A knowledge-based approach to medical records retrieval[END_REF]) to propose reformulations. From two UMLS search modes, we provided reformulations based on MeSH terms identified in the users key-phrases. To generate a consensus answer to the user emphasizing the agreements between the reformulations, we backed its computation on a new pseudometric, extending the state-of-the-art generalized Kendall-τ distance. With this new pseudometric, we adapted and combined several median ranking algorithms, allowing the system to quickly compute a consensus. We compared our approach to the main portal used to browse gene-centric biological data, namely the EntrezGene database from the NCBI website and its ranking function based on relevance. We showed that when measuring the presence and order of expected results (based on Gold standards), ConQuR-Bio outperforms the NCBI with an AUC increased of 69.30%. When focusing on biometrics indicators and compared to the NCBI relevance sorting, ConQuR-Bio returned genes associated with 56% more publications, published in 25% less days. Last but not least, we made the system available and free to use at http://conqur-bio.lri.fr as a website.

We now provide a discussion and perspectives considering the various steps of our approach.

ConQuR-Bio starts with identifying MeSH terms from key-phrases. We have currently chosen to follow a greedy (and naive) process enabling a very fast answer rate, compatible with the on-the-fly feature of our approach. This strategy is entirely satisfactory on evaluated key-phrases. Future work will explore the detection of concepts from the users key-phrases by deploying concept recognition software such as MetaMap [START_REF] Alan R Aronson | Effective mapping of biomedical text to the umls metathesaurus: the metamap program[END_REF] or BioAnnotator, enabling advanced reformulation options (e.g. different levels of granularity). Providing results in a few seconds while augmenting their overall quality will be the most challenging point.

The reformulation module plays a major role in the quality of the results. This module is based on two components: the set of terminologies used and the way such terminologies are queried and exploited.

As for the terminologies, we currently use terminology sources from the UMLS which allowed us to have manageable and relevant amounts of reformulations. Ongoing work includes selecting a larger and customizable number of sources from the main two biological terminology integration systems (namely, the UMLS and the BioPortal [START_REF] Whetzel | Bioportal: enhanced functionality via new web services from the national center for biomedical ontology to access and use ontologies in software applications[END_REF]) to cover a broader scope of biological domains. To cope with the possibly too broad aspect of reformulations, we plan to allow (experienced) users to select the reformulations to be or not to be used by our system.

As for the way terminologies are exploited, in our current version, the "search deeper" mode provides narrower reformulations. However, work still have to be done as the semantics of this mode is very permissive and does not exploit the hierarchical feature of the links between concepts. The UMLS system provides typed links for broader and narrower concepts unified between terminologies, and their adequacy should be evaluated. Ongoing work consists in exploiting the hierarchical relations from the sources to improve the detection of concepts and their synonyms.

Fig. 1 .

 1 Fig. 1. Architecture of ConQuR-Bio. Solid arrows represent requests and dotted arrows responses. Two headed arrows represent possibly iterative requests. When several actions have to be done successively, their are numbered with a squared number. When alternative actions can be done, actions are represented with a diamonded number.

Example 1 .

 1 r), ∀r ∈ R; Let us consider the set of input rankings R = {r 1 , r 2 , r 3 } where r 1 = r 2 = [{A}, {D}, {B, C} u ], r 3 = [{B}, {A, D}, {C}]. The median ranking is c * = [{A}, {D}, {B, C}]. The disagreements are: the order inversion of B-A and B-D (+2) plus A-D untying (+p) plus B-C tying (+p) thus K (p) (R, c * ) = 2+2p.

Example 2 .

 2 Let us consider a set of input rankings R = {r 1 , r 2 , r 3 } where r 1 = r 2 = [{A}, {D}, {B, C} u ], r 3 = [{B}, {A, D}, {C}]. Under the generalized Kendall-τ distance, the median ranking is c = [{A}, {D}, {B, C}] (cf. Example 1) while under the pseudometric M the median ranking is c = [{A}, {D}, {B}, {C}] as M

Fig. 2 .

 2 Fig. 2. ConQuR-Bio interface and the window open after clicking on BRCA2.

  Fig 3.b) show the importance of taking into account all lexical and orthographic variations: ConQuR-Bio returns identical results for the four variants with an AUC of 0.53 while NCBI results have systematically inferior and variable AUCs.

Fig. 3 .

 3 Fig. 3. The Area under the ROC curve (AUC) for the 20 first genes returned by ConQuR-Bio and the NCBI WebSearch for (a) Single-term key-phrases, (b) lexical variation around cervix cancer tumor suppressor, and (c) the remaining key-phrases.

Fig. 4 .

 4 Fig. 4. #publications for each of the 20 first ranked genes for retinoblastoma

http://www.ncbi.nlm.nih.gov/Entrez

Version 2013AB of the UMLS is used in the current version of ConQuR-Bio and for the evaluation we provide in the next section