G Casadei

V Bertrand
email: vadim.bertrand@gipsa-lab.fr

B Gouin

C Canudas-De-Wit
email: carlos.canudas-de-wit@gipsa-lab.fr

Aggregation and Travel Time Calculation over Large Scale Traffic Networks: an Empiric Study on the Grenoble City

Keywords: large scale traffic networks, travel time estimation, clustering and aggregation

In this paper we consider aggregation technique to reduce the complexity of large-scale traffic network. In particular, we consider the city of Grenoble and show that, by clustering adjacent sections based on a similarity of speed condition, it is possible to cut down the complexity of the network without loosing crucial and intrinsic information. To this end, we consider travel time computation as a metric of comparison between the original graph and the reduced one: for each cluster we define four attributes (average speed, primary and secondary length and heading) and show that, in case of an aggregation rate of 95%, these attributes are sufficient in order to maintain the travel time error below the 25%.

Introduction

Large-scale traffic networks are of great interest nowadays due to the impact traffic has in our everyday life, both economically and health-wise. City management are interested in understanding the evolution of traffic and its patterns over the city in order to take decisions to design improved and more functional infrastructure. However, monitoring the current state of a large scale traffic network is a demanding task. The heterogeneity of available measures poses several question on how to merge different sources of information coming from private and public sources. Furthermore, sparsity is an intrinsic issues related to large scale systems: independently from the source we choose to rely on, we cannot expect the measurements to be sufficiently dense to cover the full network in detail. In the past, the main focus of the research on traffic systems has been the analysis of individual roads or small regions (R. [START_REF] Herring | Using mobile phones to forecast arterial traffic through statistical learning[END_REF]; A. [START_REF] Krause | Toward community sensing[END_REF]; H. [START_REF] Liu | A virtual vehicle probe model for time-dependent travel time estimation on signalized arterials[END_REF]; C. [START_REF] De Fabritiis | Traffic Estimation And Prediction Based On Real Time Floating Car Data[END_REF], but less attention has been given to approaches that are capable of giving a global perspective of the state of a large-scale networks (Y. [START_REF] Han | Statistical Traffic State Analysis in Large-scale Transportation Networks Using Locality-Preserving Non-negative Matrix Factorization[END_REF]; P.S. [START_REF] Castro | Urban traffic modelling and prediction using large scale taxi GPS traces[END_REF]; H. [START_REF] Wang | A Simple Baseline for Travel Time Estimation using Large-Scale Trip Data[END_REF]). For large scale urban networks, managing real-time traffic information from thousands of links simultaneously is an overwhelming task and extracting important and meaningful insights from this tangle of data can be even more challenging. However, the study of theoretical models capable of capturing the macroscopic behavior of traffic have been introduced many years ago (N. Geroliminis andC. F. Daganzo (2007, 2012); H. [START_REF] Bar-Gera | Empirical macroscopic evaluation of freeway merge-ratios[END_REF]; C. [START_REF] Buisson | Exploring the impact of homogeneity of traffic measurements on the existence of macroscopic fundamental diagrams[END_REF]) and nowadays continues to be a popular and deeply studied research topic (Z. [START_REF] Zhang | Integration of a cell transmission model and macroscopic fundamental diagram: Network aggregation for dynamic traffic models[END_REF]; L. [START_REF] Leclercq | Estimating MFDs in simple networks with route choice[END_REF]). In recent years more and more data are becoming available from new sources, such as smart phones, GPS navigators, and their technological penetration allows to have an impressive amount of real-time traffic information, as demonstrated by the Mobile Millennium Project (A. [START_REF] Bayen | Mobile Millennium[END_REF]).

The main advantage of these new sources is that they do not require placing physical sensors over the network, thus reducing costs related to installation and maintenance: in other words, each user becomes a moving sensor inside the network (see C. [START_REF] Peng | Collective human mobility pattern from taxi trips in urban area[END_REF], J.A. [START_REF] Deri | Big Data Computation of Taxi Movement in New York City[END_REF], B. [START_REF] Donovan | Using coarse GPS data to quantify city-scale transportation system resilience to extreme events[END_REF]). However many data do not necessarily imply meaningful information, since their interpretation, analysis, treatment and display becomes more and more challenging. From a city management point of view, the availability of huge numbers of GPS traces can be used in a aggregated fashion to determine macro-movements and origin/destination patterns of interest: these information become of great importance in order to monitor and (if possible) adapt the traffic infrastructure to the traffic evolution. To this end, one could consider the possibility to simplify the complexity of the problem by performing an aggregation over the traffic network. A recent research C. Lopez et al. (2017Lopez et al. ( , 2018)), performed on the city of Amsterdam, showed that thanks to network clustering, the traffic pattern of the entire city can be synthesized in only four features composed by only nine clusters. On one hand one could consider a static partition, based on geographic structure of the network (see H. [START_REF] Etemadnia | A network partitioning methodology for distributed traffic management applications[END_REF]; Y. Li and N. Geroliminis (2012); K. [START_REF] An | A Network Partitioning Algorithmic Approach for Macroscopic Fundamental Diagram-Based Hierarchical Traffic Network Management[END_REF]): on the other hand, to capture the dynamic evolution of the network, the natural approach is to apply the clusterization in real-time (see M. [START_REF] Saeedmanesh | Dynamic clustering and propagation of congestion in heterogeneously congested urban traffic networks[END_REF]). A static partition allows to consider and describe the evolution of precise areas of interest, for instance crucial origin/destination zones inside the network. With a dynamic partition a certain point of interest might belong to different cluster in different moments of the day: thus the interest shifts on the evolution of the clusters and their impact/meaning in the network status. Depending on the problem at hand, the two approaches could lead, in terms of performance, to completely different results: if a traffic network presents a regular evolution which repeats daily/weakly following a distinctive pattern, a static analysis/partition of the traffic network will guarantee reliable results. However, if a traffic network has a highly variable evolution, which might depend on different parameters (such as weather, traffic accidents etc etc), a dynamic aggregation allows to be reactive to this variability and to follow the particular evolution in real time.

From a general perspective, the goal of the clustering is to reduce the complexity of an original graph while respecting a certain predefined criterion for the nodes state/edge value (S. [START_REF] Fortunato | Community detection in graphs[END_REF]; F. D. [START_REF] Malliarosa | Clustering and Community Detection in Directed Networks: A Survey[END_REF]). It is common knowledge that there is no single best strategy for graph clustering, which justifies the variety of existing approaches. Moreover, most quality indixes for graph clustering have turned out to be NP-hard to optimize and rather resilient to effective approximations (see G. [START_REF] Ausiello | Complexity and Approximation -Combinatorial Optimization Problems and Their Approximability Properties[END_REF]). The research for clusters can be a demanding task from a computational point of view and this constraint becomes more and more evident as the size of the network increases. Solutions have been proposed in the literature in order to deal with networks of big size (see for instance D. [START_REF] Delling | Orca Reduction and ContrAction Graph Clustering[END_REF]) but they often depend on the particular metric used to evaluate the clustering procedure and in general they are still computationally heavy. Some popular metrics often chosen are coverage (namely the fraction of intra-cluster edges, to be minimized) U. [START_REF] Brandes | Network Analysis: Methodological Foundations[END_REF], performance (namely the fraction of correctly placed vertex pairs, to be maximized) S. M. van Dongen (2000), inter-cluster conductance (namely the thickest bottleneck created by the definition of clusters) R. [START_REF] Kannan | On Clusterings: Good, Bad, Spectral[END_REF] and modularity (namely the coverage ratio between a clustering and the same with randomly rearranged edges, to be minimized) M. E. J. Newman and M. E. J. [START_REF] Newman | Finding and evaluating community structure in networks[END_REF]. For all these metrics however, the optimization problem is NP-hard and thus not feasible in a real-time implementation. Thus, if the aggregation has to be performed in a time window compatible with a real time application, simpler criteria and procedure needs to be defined.

Objective of this paper and Structure

In this paper we investigate and propose an aggregation based analysis of large traffic networks in view of evaluating travel times between areas of interest inside the urban network of Grenoble. In particular, by aggregating roads which belongs to similar categories (highways, national roads, urban roads) and have similar speed (up to a certain cut-off), we will show that it is possible to reduce drastically the complexity of the network while introducing an acceptable error in the travel time calculation. The information and results we obtain are of great interest to understand the macroscopic evolution of a large-scale traffic network and to evaluate the average time that users spend in transiting between different areas along the day. In particular we will focus on the duality of our approach: on one hand aggregation allows to simplify the complexity of representation and calculation over the network. On the other hand, reduction in the granularity affects the precision in evaluating the state of the network.

The error introduced will be calculated for multi-origin multi-destination path, namely given an aggregation, we will show that the travel time calculated between two clusters is consistent with the average of all the possible path between these two clusters in the original graph. We will show that this error grows (nonlinearly) with the aggregation rate and thus a suitable compromise between the reduction of complexity and the error introduced must be found. Furthermore, we show that in the aggregated graph, typical congestion patterns (over a daily and weekly base) can be easily reconstructed and defined. The latter leaves open the possibility to define travel time estimation based on historic data by matching the present condition with a set of typical pre-defined patterns.

The interest for dynamic aggregations is particularly motivated by traffic networks which show erratic and fragile behaviors which frequently diverge from a nominal behavior. In our case study, an analysis of the data available showed that the definition of recurrent traffic patterns in crucial parts of the city is a very difficult task. As it will be explained in the following section, the structure of the Grenoble network is not redundant and, due to the presence of mountain ranges around city, it lacks for highway rings. These limitations translates into a highly fragile network which easily (and ultimately unpredictably) leads to high congestion risks.

The paper is structured as follows. In Section 2, we introduce the basic and practical information about data and map we use in order to describe the Grenoble traffic network. In Section 3, we describe in details the aggregation technique we developed and the attributes which describe the clusters: these parameters play a fundamental role in the calculation of travel times, since they allow to reduce the complexity while preserving some of the physical properties of the real network. Then, in Section 4 we show results and comparisons between travel times calculated over the original detailed graph and the aggregated graph: in particular we will consider two aggregation rates, one that keeps the travel time error small, the other which simplifies drastically the complexity of the graph.

Problem setting

Situated in the south-east of France close to the Alps, Grenoble is the 16th largest city in France with a population of the agglomeration of 451.000 people. The geometry of the city itself is strictly related to the geography of the surrounding mountains: the Chartreuse range on the north, the Vercors range on the west and the Belledonne range on the east determines the alcove in which Grenoble lies. Due to these physical constraints, the urban network of the city can be seen as star-connection, where the urban network as the center and the three arms as the highways from/to Lyon (north-west), Chambery (north-east) and Gap (south).

As shown in Figure 1, these three fundamental entry/exit points are connected to each other only by the south-ring N-87 and the urban network. This critical and fragile connection is one of the main reason of the sensitivity of the network, which places the city as the seventh most congested in France with an average of more than 45 hours per year spent in traffic (source TomTom). Due to its strategic importance, the N-87 has been the target of the project Grenoble Traffic Lab (GTL), started back in 2009 and became operative in 2013, an innovative online platform which collects data coming from a sensor network (130 magnetometers positioned over a stretch of 10 km) and allows to have a detailed and granular monitoring of the traffic condition of one-direction of the N-87 (see C. Canudas de [START_REF] De Wit | Grenoble traffic lab: An experimental platform for advanced traffic monitoring and forecasting[END_REF]). Being GTL a successful experience, in the context of the ERC-Project ScaleFree-Back (C. Canudas de Wit (2015)), the aim is to extend a similar approach to the full scale of the city of Grenoble. There are several reasons of interest in monitoring the status of the traffic network on a city-scale. From the traffic management point of view, it allows to understand the dynamics of traffic, the critical points of the networks, the impact of special events over the normal behavior of the network. At the same time, the status and evolution of the city traffic allow to plan modification in the network infrastructure with the aim to reduce the hours spent by users in traffic jam and incidentally, reduce the pollution. With respect to this last aspect, the city of Grenoble presents again an unfortunate morphology due to the surrounding mountains which limit the air circulation. In the last decade, the city has recorded at least 20 days of pollution peak per year (days in which the pollution level overpass the limits imposed by the EU).

For economical but also practical reasons, it would not be possible to place a dense network of sensor such as the one on the N-87 over a city network. However, as already mentioned, there are nowadays different sources of information which we can exploit to monitor and reconstruct the state of the network. We think in particular to GPS traces from mobiles and cars and the information we are able to retrieve from them. It comes without saying that the number of data available is potentially immense. This is not necessarily a positive aspect since on one hand the availability of information implies robustness but at the same time requires a thorough analysis and manipulation to be exploited and interpreted.

In order to obtain a sufficiently dense and reliable data set, we rely on speed measurements obtained by TomTom. They indeed provide a really granular information with more than twenty thousand sections spanning the urban network. This implies that computation and analysis of these information can be really complex and costly if not opportunely set. Furthermore, despite covering the main arteries of the network, there are several areas where no data is available. Thus it could be of interest, when possible, to infer something about these areas even though a direct measurement is not available. More in general, this paper and the approach presented here are motivated by the possibility to reduce the need of detailed information about a large scale urban network while keeping the error of approximation as small as possible.

Architecture of the platform

To monitor large-scale traffic networks, many ingredients have to come into place and different part of the architecture need to be thoroughly defined. As mentioned before, we acquire speed data from TomTom and thus the first step is to retrieve them and make them available for computation. To this end, beside the data itself, the map-graph plays a fundamental role both in displaying and allowing computation over the traffic network. In this section we present these two main features of the architecture: first we introduce data specifications and details, then we explain how the map is obtained and the conversion/manipulation are performed in order to represent TomTom data over a graph structure.

Data specification and acquisition

We acquire data through a HTTP GET request sent from a white-listed IP using a secure API key. In response we receive a Protocol Buffers -.proto -file. Protocol buffer serializes structured data, as XML does, while producing smaller file and achieving faster reading/writing operations. This allows to transfer and archive a high volume of data in a faster and easier way. A raw data file, in our case a file around 67 Kb, can be seen as a time stamp and a list of samples. Each sample is made of four fields: In particular, we identify four road categories FRC defined by TomTom: red corresponds to FRC0 roads, orange to FRC1, blue to FRC2 and light-blue to FRC3-FRC4.

• Location of Interest: a road stretch and its direction, whose location is encoded using OpenLR representation, a standard for encoding, transmitting and decoding geographical locations developed by TomTom since 2009

• Road Category: an attribute of importance of the road on a range from FRC0 to FRC7 where FRC0 stands for the larger roads and FRC7 for the smaller ones. Typically the can be classified as:

• FRC0-FRC1 represents highways and freeways

• FRC02 represents the most important urban and extra-urban arteries

• FRC03-FRC04 represents the smaller and less important roads in the traffic network

• FRC05-FRC07 represents even less important roads, but information on these class are not available for the Grenoble network

• Travel Time: current travel time in seconds along the location of interest, computed using speed-data measured on the road and aggregated over a time window of 1 up to 2 minutes (the time required from TomTom to acquire and process raw data)

• Average Speed: current average speed in km/h, based on the current travel time and the length of the stretch

• Calculated Data Quality: confidence value from 0% to 100%, that depends on large number of factors, between which: the freshness of the measurements, the volume of the measurements and the deviation between the measurements and the historical records. In France, TomTom guarantees a confidence value greater than 50% which as expected (see Figure 3, source TomTom) is much larger during the day, when more vehicles can provide measurements while it decreases drastically during the night. In particular, during the day, 80% of the data have a confidence value of more than 90% which in other words means that during the crucial moments of the day, TomTom provides highly reliable information. In the Grenoble area, travel time and speed data are available for roads between FRC0 and FRC4. They cover around 550 km which represents more than 50% of the roads in the FRC0-FRC4 class and in a general perspective 20% of the total road network. To validate the correctness of their aggregated measurements, TomTom has performed a posteriori experiments to quantify its data reliability using TISA QBench Calculations methodology and for FRC0 and FRC1 roads TomTom claims an excellent score above 80%.

With respect to data of the FRC0 category, thanks to the GTL project we could further validate the confidence parameter given by TomTom: in particular we compared TomTom profile of velocities with the one we obtain from our ground-sensors over the whole length of the N-87. The results are reported in Figure 4 and clearly confirms that TomTom is highly reliable in high category roads. The small positive bias and the slight delay (in the order of 1 minute) are totally compatible with the case of study: indeed GTL frequency of update (15 sec) is much smaller than the one of TomTom and, thanks to the 130 physical sensors in place, the granularity is much higher. Nevertheless, TomTom recovers perfectly the traffic trends and evolution and on a larger scale confirms the possibility to use aggregated information.

Map and and its conversion

In order to accurately represents Grenoble road network we also need a detailed road map. With this respect, TomTom provides two Shapefiles, one relative to the sections and one to the intersections of the whole urban network. A Shapefile is a geospatial data format that allows to describe vector features such as points, lines or polygons. Each feature can hold attributes used to describe it. In our file the roads are represented by lines with their extremities as intersections. Roads have several attributes such as length, number of lanes, maximum allowed speed, road name and many more. From this Shapefile we construct a first graph where intersections are nodes and stretch of roads are edges (about 49000 nodes and 98000 edges, Figure 5). This graph is directed therefore between two nodes each direction is represented by an individual edge.

In this framework, the speed measurements will be assigned as weight of the edges. To perform this assignment it is necessary to match the locations where TomTom is providing data to the edges of the graph representing the road network. The representation of the road network we just described is easy to understand, graphically convenient and also natural to define paths. On the other hand, in view of performing an aggregation based on speed measurements, it would be much easier to consider a graph where the attribute of speed is referred to the nodes rather than to the edges. To this end, in the following we consider the line graph obtained from the canonical graph, namely the graph where stretches of roads become nodes and intersections become edges. The procedure to transform a road traffic network to its associated line graph is summarized in Figure 6 for the simple case of one intersection (Figure 6

d 2 i -m (1)
In general, the passage to the line graph considers each section as a node and each intersection as a set of edges: this set of edges is directed and has to respect the physical interconnection between sections.

Clustering and aggregation technique

Once the line graph of the urban network is obtained, it is now possible to consider aggregation and clustering techniques to reduce the network complexity. In this section, we first explain the aggregation principle and how the clustering is performed. Then we introduce in details which attributes we assign to each cluster and how to calculate them.

Clustering methodology

The principle of clustering strategy we introduce aims to achieve uniqueness in the clustering and at the same time a simple realization since ultimately the goal of this application is to be feasible in a real-time implementation. In words, two nodes belongs to the same cluster if a path exist between them such that every edge of that path satisfies a given criterion. We implemented this clustering by removing from the graph edges that do not satisfy the criterion. Then we compute weakly connected components of the graph, and those weakly components will be our different clusters. We recall the definition of a weakly connected component. Cut-Off for FRC0-FRC2

G = {N , M} is a maximal subgraph G = { Ñ , M}
that is connected and such that there is no edge with a tail outside Ñ and the head in Ñ .

To perform the clustering over Grenoble traffic network represented by a line graph G L = {V, E}, we choose a criterion based on the speed attribute associated to each section, namely each node. For every pair of adjacent sections i-j, we define the weight of the associated edge e ij in the line-graph as

e ij = |v i -v j | (2)
where v i is the speed of node i. Then we say that an edge satisfies our criterion if the speeds difference of the two ends node is less than a given cutoff ē: formally, we define a new graph G A = {V, A} (where we delete edges that do not satisfy the condition) as

a ij =          e ij ≤ ē ⇒ a ij = 1 e ij > ē ⇒ a ij = 0 (3)
In order to preserve some of the intrinsic structure of the urban network, we have divided the roads in three classes based on their functional road class:

• motorways and freeways (FRC0 and FRC1)

• important urban roads and national roads (FRC2)

• secondary roads (FRC3 to FRC4)

Based on these three groups, sections belonging to different classes can not belong to the same cluster. Thus the cut-off is defined as a vector with a specific entry associated to each of these groups. As mentioned before we perform the aggregation by condensing the weakly connected components of the graph into supernodes and thus obtaining a new graph ḠL = { N , Ā} where N is the number of nodes after the condensation and Ā is the set of edges connecting the super-nodes. We can now formally define the aggregation rate as

AR = N - N N (4)
which measures the percentage of complexity reduction introduced by the clustering. The resulting graph ḠL thus defines zones that are homogeneous in speed and importance. Clearly, the aggregation rate is a function of the present state of the network, namely the speed measurements we retrieve: for the sake of simplicity, in the rest of the paper we refer to the aggregation rate as the average of AR along the day. For a fixed cut-offs combination, we observed that the average aggregation rate is constant between different days while the variance might slightly change. To clarify this point, in Figure 7, we plot the evolution of AR with cut-off ē[0;2] = 2 and ē[3;4] = 4. As it can be observed, the average value is really close to 81% (see Table 1) and varies between a max value 83% and a min value 78%.

In Table 1, we summarize some of the results obtained by setting different cut-off ē[0;1] , ē[2] and ē[3;4] for the three different classes of roads. In particular we show how the aggregation rate evolves in function of how the cut-off are set. For a desired reduction of complexity, one can choose the opportune range of cut-offs.

An interesting feature of the clustering procedure just defined is that ḠL exhibits a tendency to scalefree property. In fact, it is possible to observe that our clustering procedure based on speed similarity and weakly connected components naturally creates hubs (that collects section homogeneous in importance and speed) which represents the crucial areas inside the traffic network. We recall that a scale-free network is a network whose degree distribution can be expressed, at least asymptotically, as a power low where P (k) is the fraction of nodes in the network having k connections to other nodes and 2 < γ < 3. As shown in Figure 8, for increasing cut-of (and as a consequence aggregation rate AR) the scale-free distribution (in dash-dot red) is approximated better, up to a value around AR = 90%: the different degree distribution move from light a grey to a black line. As a matter of fact, in the degree distribution of the aggregated graph it is always possible to identify characteristic peaks, one around d = 4 and one around d = 2: in particular it is possible to see that by aggregation, we reduce the number of nodes having degree d = 4 and thanks to the hub-structure obtain a degree distribution which is centered around d = 2.

P (k) k -γ

Clusters information

By clustering we obtain a reduction of complexity in terms of number of nodes. However, we still have the possibility to define some cluster properties in such a way that the information of the original physical graph are not all lost. The goal of defining these properties is to capture the essential property of the physical nodes that belongs to a certain cluster and to use them to characterize the cluster. For instance, once a cluster is defined, what is the state (in our case, speed) associated to this super-node? How can it be defined from the original nodes that belongs to this super-node? The reason of using clusters and to introduce a set of properties is to forget the detailed physical information of the original graph without loosing too much of its intrinsic properties. In our case, each node has a huge number of properties between which we recall location in GPS coordinate, associated length, associated speed, information about neighbors section and many many more. By clustering we mainly loose the details of the topology of the graph (namely detailed path from a node to another), on the exact speed in a certain section (since each section now belongs to a cluster). As a matter of fact, for each cluster we define four properties:

• the mean speed of a cluster: is the sum of the length of every section belonging to this cluster divided by the sum of those sections' travel time

• the center of gravity of a cluster: depends on the center of mass of each section belonging to this cluster. Each section is considered as unitary mass point and thus the center of gravity coincides with the geometric one.

• the principal direction of a cluster: is the angle between the horizontal axis and the direction defined by the primary axis. The latter is provided by the linear regression of this cluster's nodes coordinates (see Figure 9)

• the lengths of a cluster: is a vector of two distances that defines the size of this cluster along it's principal direction and the perpendicular direction. They are obtained by computing the variance of this cluster's nodes coordinates along those two directions.

Calculation of travel time in the clustered graph

The definition of the last two properties is of great importance in order to simplify drastically the complexity of the network while keeping the approximation error small. First of all, let us introduce a metric to compare the original graph with the clusterized graph. Given two adjacent clusters, C h , C k we define their geometric distance h↔k as the distance between their two center of gravity (see Figure 10), namely

h↔k = h→k 2 + k→h 2 (5) with h←k = cos(θ -ϕ h ) 2 hp + sin(θ -ϕ h ) 2 hs (6) k←h = cos(θ -ϕ k ) 2 kp + sin(θ -ϕ k ) 2 ks ( 7
)
where θ is the angle between the horizontal axes and the the line connecting the two center of gravity. Then, we can compare the length of a path in the original graph with the clustered path and more in general the length of all possible paths connecting nodes of two clusters with the clustered path length h↔k .

Definition 2. For each couple of adjacent clusters C h , C k consider all the nodes v i ∈ C h , v j ∈ C k . For each couple v i , v j consider, if it exists, the shortest path connecting them on the original graph G, denoted as (v i , v j ) G . Then we define the inter-cluster length error E ij as

E ij = vi∈C h vj ∈C k |(v i , v j ) G -h↔k | vi∈C h vj ∈C k (v i , v j ) G (8)
The inter-cluster length error compares the aggregated path length with the average path lenght between two clusters. Clearly, as the size of clusters increases and as a consequence does the simplification, aggregation can introduce huge errors if a single path is considered. Consider Figure 11 and the three paths connecting cluster A and B: it becomes clear that if one compares h↔k with either path 1 (red) or path 2 (green), the error introduced is big. With respect to path 3 (blue) however, the error is quite small and thus the approximation correct. In general, an opportune definition of the aggregated length allows to maintain the error with respect to the average path between two clusters limited. The error introduced depends drastically not only on the size but also on the shape of the cluster: clusters with symmetric shapes are more likely to have regular distribution of path lengths and thus E ij can be maintained small. With the calculation of travel time in mind, we also define the aggregated path length for cluster which are not adjacent. Consider two clusters C h , C h+i not adjacent, we define the aggregated path length as

h↔h+i = h↔h+1 + h+1↔h+2 + . . . + h+i-1↔h+i (9)
namely we consider half of the length for departure/arrival clusters and the full length for clusters which are completely crossed during the path. Consider Figure 12 and two possible aggregated paths (green and red), connecting the origin/destination clusters C O , C D . We have

D↔O a = D↔H + H↔M + M ↔P + P ↔O D↔O b = D↔C + C↔B + B↔E + E↔I + I↔O
Clearly, for origin/destination clusters which are not adjacent, there might be multiple aggregated paths connecting the two and thus multiple aggregated path length: we define the set of aggregated paths connecting C h , C k as L h↔k . In general, depending on which real path we want to compare our approximation with, we could choose the aggregated path that passes through the clusters which contains the sections of the real path. However, being this calculation really tedious and heavy, for non adjacent clusters we define the aggregated path length as h↔k = min

i∈L h↔k { h↔k i } ( 10
)
It is important to stress that the choice of cluster parameters we introduced is light in terms of computational load: being our aim to exploit this clusters in a real time scenario, computing for instance the average path length (which ideally would lead to E ij = 0), for huge graphs is not feasible. Our choice instead, based only on geographic distribution of nodes allows to calculate these parameters in a time-window compatible with real-time applications. In fact, the complexity of calculating these parameters is linear with the number of nodes O(|V|), where |V| is the cardinality of vertexes set. As mentioned in previous sections, the main comparison between original and clustered traffic network is based on traveling time calculation. In particular, we will compared the travel time between clusters with the average travel time between origin/destination section chosen inside the departure/arrival clusters. It is worth recalling that from our point of view, if two clusters are adjacent, the travel time to go from one to another and vice versa is the same and it is unique.

Following the definition of the distance between two adjacent clusters (4), we define the cluster-to-cluster travel time as

τ h↔k = h→k 2v h + k→h 2v k (11)
namely, we consider the sum of the travel time to go from the center of mass of clusters C h , C k to the boarder of the cluster, moving along the line connecting the two center of masses, respectively at the cluster average speeds v h , v k . Consider Figure 12 and suppose that we are interested in the travel time between the adjacent clusters C A , C B then we have

τ A↔B = A→B 2v A + B→A 2v B
with A→B and B→A as in ( 5).

When two clusters C h , C h+i are not adjacent, we define the traveling time as

τ h↔h+i = τ h↔h+1 + τ h+1↔h+2 + . . . + τ h+i-1↔h+i = h→h+1 2v h + h+1→h 2v h+1 + h+1→h+2 2v h+1 + h+2→h+1 2v h+2 + . . . + h+i-1→h+i 2v h+i-1 + h+i→h+i-1 2v h+i-1
namely we consider half of the length for departure/arrival clusters and the full length for clusters which are completely crossed during the path. Consider again the example in Figure 12 Similarly to the case of aggregated length for non-adjacent clusters, we define the aggregated travel time as

τ h↔k = min i∈T h↔k {τ h↔k i } (12)
where T h↔k is the set of possible aggregated travel time between the two clusters. It is worth stressing again that this choice is really conservative but allows to compute aggregated travel time uniquely without considering detailed physical path. In the following Section we will indeed show that all these simplification have a limited impact on the estimation of travel time from an area to another. The following definition explains how we compare in details our aggregated travel time with the ones on the original graph.

Definition 3. For each couple of adjacent clusters C h , C k consider all the nodes v i ∈ C h , v j ∈ C k . For each couple v i , v j consider, if it exists, the shortest path connecting them on the original graph G, denoted as τ (v i , v j ) G . Then we define the inter-cluster travel time error E τij as

E τij = vi∈C h vj ∈C k |τ (v i , v j ) G -τ h↔k | vi∈C h vj ∈C k τ (v i , v j ) G (13)
As a matter of fact, for large aggregation rates AR, there are several interesting paths which could lie inside a unique cluster. In order to take into account for these paths, we define also an intra-cluster aggregated travel time as

τ h = min i∈T h {τ h i } (14)
where T h is the set of all possible travel times inside cluster h and each τ h i depends on a intra-cluster

length h = cos(θ -ϕ h ) 2 hp + sin(θ -ϕ h ) 2 hs .
Clearly, the minimal value coincides with the secondary length hs of the cluster h (namely for θ = ϕ h + π 2 ), namely the shortest distance to cross the cluster.

Definition 4. For a given cluster C h , consider all the nodes v i , v j ∈ C h which are not neighbors. For each couple v i , v j consider, if it exists, the shortest path connecting them on the original graph G, denoted as τ (v i , v j ) G . Then we define the intra-cluster travel time error E τij as

E τij = vi,vj ∈C h |τ (v i , v j ) G -τ h | vi,vj ∈C h τ (v i , v j ) G (15)
This choice of the intra-cluster aggregated travle time is motivated by the fact that, even though we neglect all trivial paths (namely paths which only include two adjacent sections), in our framework possible intra-cluster paths can be really short. More sophisticated choices could be made but we remark again that we are trying to simplify as much as possible the complexity of the overall architecture.

More in general, in terms of macroscopic traffic evolution, one could define a cutoff for the minimal length of the paths to be considered and thus restrict the analysis only to paths which play an important role into the traffic evolution. If short paths were neglected, a more accurate choice would coincide with the average of all possible τ h .

Travel Time Computation and Results

In order to validate our approach we wanted to compare our aggregated travel time with the travel time calculated over the original graph. To this end, we have selected eleven points of interest of the road network (see Figure 13) which represent the entry and exit points to the city network and some locations inside the city. The selection of this set of these points, labeled POI, aims to cover the most important and typical traffic flows in the urban network of Grenoble. The urban targets are for instance the train station, the university campus and Grand Place (commercial area), while the entry/exit point to the city are the highways A41, A48 and A480. Thanks to this selection, we will be able to analyze the travel time evolution for typical paths that stay inside the urban area (typical citizens users) but also paths that cross the urban network (commercial transportation, commuters). As describe in Section 3, our clustering is dynamic and thus during the day these points of interest will belong to different clusters or potentially lie in the same. Thus when calculating the evolution of travel times we will select the shortest travel time path in function of the traffic evolution. The comparison we present in the following relies on Definition 3-4 and in particular on the travel time errors ( 13)-( 15) between the computation over the original graph and the aggregated graph. As mentioned before, these definitions are disadvantageous with many extents: for instance, since in the aggregated graph we chose the shortest traveltime path, this path could be substantially different from the one in the original network. Furthermore, in case two points of interest lie inside the same clusters, we will compare our estimate with the average of all the possible paths inside the clusters, namely we will consider a lot of paths which are not meaningful from a macroscopic perspective. Nevertheless we will show that even with high aggregation rate (AR = 95%) we are able to keep the error limited (around 25%).

Evolution of the Clusters

The first aspect to be analyzed is the evolution of clusters during the evolution of traffic. As already explained in previous sections, the aggregation we perform is dynamic and thus is fundamental to understand how and why clusters changes. As a matter of fact, the more we aggregate the more stable the clusters: this behavior is actually expected by the definition of the clustering procedure since by increasing the cut-off we move towards a scale-free distribution. As shown in R. Albert and A. L. Barabasi (2002), scale-free graphs are more resilient and robust to edges attacks. During the evolution of the traffic, the change of speed in a section such that the condition (2) is met or not can be seen as an attack that erase one of the edges in the graph G A . In the context of traffic, a similar analysis has been performed in D. [START_REF] Li | Percolation transition in dynamical traffic network with evolving critical bottlenecks[END_REF], where the authors analyzed the sensitivity of a traffic network by means of percolation theory.

By increasing the cut-offs of the clustering procedure (and thus the aggregation rate AR) we obtain clusters that are more stable at the price of simplifying/loosing detailed information. In Figure 14 we show 3 samples of the evolution of the clusters during the day for two different aggregation rate, at three crucial moments of the day, namely 08h00, 13h00 and 17h00. We can clearly observe that, for AR = 80% the clusters changes drastically with the traffic evolution and while a repetitive pattern can be observed over a daily basis, it is much harder to find a stable structure in the clusters organization. On the other hand for AR = 95% the clusters are stable along the day and only little and marginal variation can be observed. In terms of travel time calculation, we expect the error introduced by clustering to grow linearly with the aggregation rate. As a matter of fact however, this error does not grow linearly with the aggregation rate and thus an opportune compromise has to be defined between the desired simplification and precision we want to keep. A comparison can be observed in Figure 15 where we considered two origin/destination paths for each of the two cases AR = 80% and AR = 95%: in particular we chose the path where we commit the smallest error (from A41 to Meylan in AR = 80%, from A41 to Grand Place in AR = 95%) and the one where we commit the largest error (from A41 to Eybens in AR = 80%, from A41 to Gare in AR = 95%): the comparison is between the travel time calculated in the aggregated graph (red), the average of all the possible paths connecting the sections in the origin/destination clusters (yellow) and their variance (black). The aggregation were performed with e [0,1] = e [2] = 4 km/h and e [3,4] = 2 km/h to obtain AR = 85% and with e [0,1] = e [2] = 10 km/h and e [3,4] = 6 km/h to obtain AR = 95%. Furthermore, the results presented in the following consider the time interval between 07h00 and 19h00, where TomTom data are more accurate and reliable.

It becomes immediately clear that the error between the aggregated travel time and the average of the traveling times between the two clusters defined in ( 15) is over the day acceptable in both cases (between 8% and 27% for AR = 80%, between 10% and 34% for AR = 95%) while the variance depends strongly on the aggregation rate selection. In particular, with AR = 95%, the variance becomes in the worst case more than 250% of aggregated travel time. It is however interesting to notice that both aggregation rates preserve the traffic evolution over the day with a congestion peak early in the morning and another milder peak late in the evening. An important aspect to be observed is that in case of AR = 80%, the worst case error is mainly a underestimation of the travel time while for AR = 95% the worst case error is clearly an overestimation of the traveling time. The former is due to the fact that, by aggregation, we approximate real paths with projections of clusters dimension: thus, as long as the simplification is not too high, we calculate paths which in general are much shorter than the real ones. The latter mainly comes from the size of clusters which, for really high aggregation rate, produces potentially really high aggregated length. As a consequence, even origin-destination clusters which are close might have aggregated path lengths that are really long. We want to stress that this is however a natural price to pay for the huge simplification introduced.

Another aspect that is interesting to observe is the evolution of the variance during the day. In particular, during rush hours (especially in the morning), travel time is really sensitive to the particular path chosen and thus the aggregated travel time can only aim to be correct in the average but the variance will be potentially important. On the other hand, during the day, when traffic smooths down, the variance is notably smaller until 18/19 p. m. when the second traffic peak is observed.

General Results

More in general, in order to compare the travel time calculation for different aggregation rate AR, we define a global error metric, namely a global inter-cluster travel time error

E G τ = C h ,C k ⊃POI vi∈C h vj ∈C k |τ (v i , v j ) G -τ h↔k | vi∈C h vj ∈C k τ (v i , v j ) G (16)
where the notation C h , C k ⊃ POI means pairs of clusters containing pairs of points of interests. This global travel time error can be computed over different time windows, thus in order to obtain a big picture point of view we considered time windows of one week. This definition allows to estimate the evolution of the travel time error for increasing aggregation rate and the values, calculated over an entire week of datas, are reported in Figure 16. As a matter of fact, even when the aggregation rate is 95%, the global error is limited to 25% which with a certain extent is an astonishing result. Figure 16 shows also that the relationship between the aggregation and the error introduced is not linear, thus it is necessary to carefully choose the aggregation cut-off to obtain the desired trade-off between AR and E G τ . In Figure 17, details about the evolution of the best and worst aggregated path over the week are shown. Both for aggregation rate AR = 80% and AR = 95%, the best case error is below 10% while the worst case in respectively E 80 τ = 27% and E 95 τ = 36%. Daily repetitive patterns can be observed, with congestion forming early in the morning and later in the afternoon: a particular event (namely a snowy day), can be observed on Friday morning resulting in a wide-spread congestion. Both displayed examples suggests however that there is the possibility to predict with a certain accuracy the travel time between different areas as long as the traffic evolution follows its natural behavior. Days with special events, accidents, adverse weather conditions, can be easily recognized even in the aggregated graph.

Complexity reduction

An interesting advantage of our architecture is the reduction of computation time to calculate huge numbers of origin/destination travel time. For different values of AR we thus compare the computation time for 250.000 (randomly chosen) paths in the original graph and the aggregated graph. Obviously, the algorithm to find the shortest path is the same for both cases, namely the Dijkstra's algorithm (see M. L. [START_REF] Fredman | Fibonacci heaps and their uses in improved network optimization algorithms[END_REF]).

The result we present have been obtained with commercially available platforms and software: thus the absolute values of the values obtained might vary depending on the particular hardware setting available. As a reference, we obtained (roughly) 55 minutes of calculation time over the original graph. As it can be observed with the blue plot in Figure 18, the computation time reduces almost linearly with respect to the aggregation rate. Already for AR = 60%, using the aggregated graph allows to save 50% of time: for the aggregation rates we considered in previous simulations (namely AR = 80% and AR = 95%), the computation time save ranges between 75% and 90%. In practical cases, this computation time gain has to find an opportune trade-off with respect to the precision required: in red we plot the error E τ relative to the 1000 paths chosen. As already remarked previously, the error in travel time computation is not linear with respect to AR and thus, depending on the desired accuracy and the time constraints, the compromise between these to aspects have to be clearly defined. It is also worth remarking that the gain in computation time is independent from the number of paths considered. As a matter of fact, the complexity of the Dijkstra's algorithm can be expressed as O |E| + |V|log(|V|) , where |V| and |E| are the cardinality of the vertexes and edges set respectively. After the aggregation both the set of vertexes and edges is highly reduced: we can thus express the complexity of our approach as

O |V | + O | Ê| + | V|log(| V|) (17)
where where | V| and | Ê| are the cardinality of the vertexes and edges sets of the aggregated graph respectively. The first term in ( 17) is relative to the complexity of the aggregation algorithm (and thus depends on the original graph vertexes |V|) while the second term is the complexity of the Dijkstra's algorithm over the reduced graph. As a matter of fact, | V| and | Ê| cardinalities vary along the day according to the aggregation and thus it is not possible to give an exact expression of the complexity reduction. However, guided by the intuition, we know that both the set of vertexes | V| and the set of edges | Ê| in the reduced graph are much smaller than the one of the original graph. Thus, we can conclude that in the average, the complexity of our architecture (namely aggregation plus travel times calculation over the reduced graph) is computationally much more convenient than computing over the original graph.

Discussion of the Result

The result presented in this sections all display that it is possible to reduce the complexity of the traffic network while preserving a fairly accurate description of traffic evolution. On one hand, we obtained that by setting the aggregation rate AR = 95% we introduce a global travel time error E G τ = 25% which in turn implies that the accuracy of multi-origin multi-destination travel time calculation does not require a dense and granular set of information. In other words, if we are interested in understanding traffic evolution from a macroscopic point of view (namely traffic patterns between one zone and another or inside a zone), we need much less information than the ones that are actually available. On the other hands, if we are interested in precision in travel time calculations, namely we seek a small global travel time error E G τ with also a small variance, there is the possibility to trade-off between these factors and the aggregation rate: as a matter of fact, with a aggregation rate AR = 80% we are capable of keeping the error E G τ = 15%. Another interesting and promising element emerging from this analysis is that aggregated traffic evolution presents typical daily patterns. It can be observed that aggregation evolves similarly between similar days (working and not-working day), namely presenting the same congested areas for different moments of the day. Similarly, special events like strikes, adverse weather conditions and accidents in crucial arterial roads can be easily distinguished from the normal behavior of the network. This suggests that a travel-time prediction in a aggregated fashion might be possible: prediction over the aggregated graph would reduce enormously the computation, necessary parameters, measures and would be much more robust to small variations from the nominal behavior recorded in the past. An approach similar to the one proposed in A. [START_REF] Ladino | A real time forecasting tool for dynamic travel time from clustered time series[END_REF] could allow to identify typical aggregated travel time patterns which describes normal and exceptional behavior of the traffic evolution and the prediction would be based on a matching between the historical data and the present time.

Conclusion

In this paper we considered aggregation as a mean to simplify the complexity of a large scale traffic networks. By aggregating neighbor sections which have a similar speed up to a cut-off parameter, we showed that it is possible to reduce drastically the size of the network while preserving the most important information. By defining a set of properties based on the shape each cluster, we showed that the error introduced by the simplification in the calculation of traveling time is absolutely acceptable: reductions in the order of 95% introduce error which in the average are less than 25%.

Clearly the approach we propose reduces the granularity of the data and the precision of calculus, namely over an exact path we can commit huge errors. However, if an average traveling time between two zones is considered, then aggregation allows to simplify the problem while preserving a sufficient accuracy. This allows to consider the traffic evolution from an aggregated point of view and simplifies the analysis of complex traffic patterns over days and weeks.

As already mentioned before, the natural extension of this work is to exploit the proposed technique to predict travel times: the idea we aim to pursue is to define typical patterns for aggregated travel time and compare the present traffic status with those historic clusters. Then, by merging the actual state with the patterns defined, it would be possible to predict the evolution of the aggregated travel time. Another possibility would be to exploit the aggregation in order to reconstruct density by zones: indeed in classic large scale frameworks, density sensors are much more sparse then velocity sensors. Thus density has to be reconstructed from velocity.

Figure 1 :

 1 Figure 1: Map of the city of Grenoble and main arteries: in orange the highways entering/exiting the city, in yellow the most important urban roads. On the right, the daily pollution concentration over the Grenoble area.

Figure 2 :

 2 Figure 2: Urban network with TomTom traffic data: the different colors represent the different category of roads.In particular, we identify four road categories FRC defined by TomTom: red corresponds to FRC0 roads, orange to FRC1, blue to FRC2 and light-blue to FRC3-FRC4.

Figure 3 :

 3 Figure 3: Schematic of the confidence value classification along time for FRC0-FRC2 roads in a typical urban network area.

Figure 4 :

 4 Figure 4: Daily difference between ground truth travel time and TomTom reported travel time.

  Figure5). This graph is directed therefore between two nodes each direction is represented by an individual edge.In this framework, the speed measurements will be assigned as weight of the edges. To perform this assignment it is necessary to match the locations where TomTom is providing data to the edges of the graph representing the road network. The representation of the road network we just described is easy to understand, graphically convenient and also natural to define paths. On the other hand, in view of performing an aggregation based on speed measurements, it would be much easier to consider a graph where the attribute of speed is referred to the nodes rather than to the edges. To this end, in the following we consider the line graph obtained from the canonical graph, namely the graph where stretches of roads become nodes and intersections become edges. The procedure to transform a road traffic network to its associated line graph is summarized in Figure6for the simple case of one intersection (Figure6.A). The classic representation (Figure 6.B) is composed by a node (red) with two directed and two bidirectional edges (6 edges), going to four other intersections (blue). The conversion to the line graph produces a new graph with 6 nodes and 11 edges (Figure 6.C). In terms of representation, the latter is clearly less compact but much easier to manipulate and to use to perform aggregation. More specifically given a graph G = {N , M} with n nodes, m edges and vertex i out-degrees d i , the associated line graph G L = {V, E} contains v = m nodes and e edges with e = 1 2 n

Figure 5 :

 5 Figure 5: Plot of Grenoble area's road network representation as a graph made of about 49000 nodes and 98000 edges.

Figure 6 :

 6 Figure 6: From a road intersection to its representation in a line graph.

Figure 7 :

 7 Figure 7: Evolution of the aggregation rate AR during the day: the value is in the average really close to 80% and slightly varies during the day.

Figure 8 :

 8 Figure8: Degree distribution before and after the clustering: for an increasing AR, the degree distribution approaches the scale free behavior up to a AR = 90% (grey to black plots).

Figure 9 :

 9 Figure 9: From a set of nodes to the cluster geometric representation.

Figure 10 :

 10 Figure 10: Geometric distance between two clusters, C h , C k the angle between the center of masses is θ.

Figure 11 :

 11 Figure 11: Two adjacent clusters and 3 different paths: in red the longest path 1, in green the shortest path 2, in blue path 3 close to the centers of mass.

Figure 12 :

 12 Figure 12: Example of clustered path: considering two origin/destination clusters, CO, CD we have two possible paths in the clustered graph, one in green, one in red.

  and suppose we are interested in the origin/destination travel times between clusters C O , C D : to the two options that passes through clusters C H , C M , C P (in green) and another passing through C C , C B , C E , C I (in red). corresponds two possible travel times τ D↔O a , τ D↔O b .

Figure 13 :

 13 Figure 13: Selected points of interest of Grenoble area.

Figure 14 :

 14 Figure 14: Clustering evolution along the day for AR = 80% and AR = 95%. Different colors mean different fluidity, where green represents high fluidity and red low fluidity. The fluidity is defined for each clusters as the ratio between the actual average speed and the historic average speed.

4. 2 .

 2 Result for AR = 80% and AR = 95%

Figure 15 :

 15 Figure 15: Travel time comparison between the aggregated graph and the detailed graph: evolution over the day, between 07h00 and 19h00, with the aggregated travel time (in red), the average of all the travel times in the detailed graph (in yellow) and the variance of these travel times (black line). Best and worst travel time per origin/destination are displayed for AR = 80% and AR = 95% respectively in the upper and lower line of the image.

Figure 16 :

 16 Figure 16: Evolution of the global inter-cluster travel time error E G τ in function of the aggregation rate AR: both values are in percentage.

Figure 17 :

 17 Figure 17: Travel time comparison between the aggregated graph and the detailed graph: evolution over a week, each day between 07h00 and 19h00, with the aggregated travel time (in red), the average of all the travel times in the detailed graph (in yellow) and the variance of these travel times (black line). Best and worst travel time per origin/destination are displayed for AR = 80% and AR = 95% respectively in the upper and lower line of the image.

Figure 18 :

 18 Figure 18: Trade off between reduction of complexity and precision in the calculation. For different AR, in red we plot the E G τ while in blue we represent the gain in terms of computation time for calculating the shortest paths between 250.000 couples origin/destination.

Table 1 :

 1

aggregation rate in percentage for different selection of the cut-off parameters: by columns the cut-off chosen for roads with category FRC0-FRC2, by rows the cut-off chosen for roads with category FRC3-FRC4, both expressed in km/h. Definition 1. A weakly connected component of a graph

The research leading to these results has received funding from the European Research Council (ERC) under the European Union's Horizon

research and innovation program (grant agreement N • 694209).Preprint submitted to ElsevierDecember 13, 2018


Brice Felden

Luc Paillard

United we stand: Big roles for small RNA gene clusters Bacterial and eukaryotic immunity RNA clusters share unexpected strong structural and functional resemblances in fighting DNA intruders

Corresponding authors: brice.felden@univ-rennes1.fr, luc.paillard@univ-rennes1.fr Regulatory small RNAs (sRNAs) are essential for protecting living cells against potentially harmful DNA challenges. They are found in all domains of life, and the parallels between their functions and mechanistic properties in eukaryotes and prokaryotes are striking. Their shared key role is to specify the targets of their associated effectors. During the interference phase, the sRNAs guide ribonucleoproteic complexes to the proper nucleic acid targets by base-pairing. This guidance capacity is surprisingly conserved in prokaryotes and eukaryotes (Figure 1), so it may be a leftover from an ancestral RNA world where the RNA was responsible both for the interaction specificity and the biochemical fate of the targets.

The sRNAs of each domain differ in their partners and biological consequences. In prokaryotes, CRISPR RNAs (clustered regularly interspaced short palindromic repeat RNAs, crRNAs) guide Cas proteins to foreign DNA to trigger endonucleolytic cleavage, thus preventing bacteriophage infections and plasmid invasions (1). In eukaryotes, PIWI-interacting RNAs (piRNAs) guide complexes that include PIWI, a member of the Argonaute (Ago) superfamily of proteins, to transposon DNA. This induces gene silencing through epigenetic modifications, and hence represses transposition. In eukaryotes too, short, double-stranded RNAs (small interfering RNAs, siRNAs) associate into a complex also containing Ago, and target it to a complementary RNA to trigger its degradation. If the siRNA comes from a double-stranded viral RNA, this mechanism contributes to host antiviral defenses (2,3). Ago proteins are the central hubs of sRNA-mediated silencing devices in eukaryotes, but recent evidences also highlight the involvement of prokaryotic Ago in protecting bacterial genomes against foreign, and possibly invasive, genomic elements such as plasmids (4,5). The molecular mechanisms that control sRNA association with the effector complex differ between crRNAs, piRNAs, and siRNAs. The prokaryotic crRNAs interact by pairing with another RNA, tracrRNA, which tethers them to Cas proteins. There is no known eukaryotic equivalent for tracrRNA, and how a transcribed RNA is recognized as a piRNA to be processed and linked to PIWI is currently not well understood. Meanwhile, a double-strand conformation triggers siRNA recognition by Ago. Thanks to this limited structural requirement, the siRNA pathway is used in reverse genetics to silence gene expression by RNA interference.

Dissimilarities aside, eukaryotic and prokaryotic sRNAs do both act as guide RNAs. Another resemblance is their shared genomic organization as clusters. Gene clusters are associations of genes expressing similar macromolecules with shared functions. Most investigations have focused on protein gene clusters (e.g. the vertebrate hox genes), but sRNAs are also frequently produced from clusters. piRNA cluster sequences are poorly conserved throughout evolution, despite the strong prevalence of the clustered organization itself, and they share extensive sequence conservation with non-functional transposon fragments. This suggests that they may have formed 3), thereby expanding cluster complexity. It is unknown whether this appropriation is due to the random insertion of active transposons into a preexisting piRNA cluster, or if there is a direct capture mechanism. siRNAs are exogenous (viral infections or experimentally introduced nucleic acid sequences), and there are no documented siRNA gene clusters. However, siRNAs substantially resemble another class of eukaryotic sRNAs, the microRNAs (miRNAs). miRNAs differ form siRNAs by their origins, as they are all genomeencoded. Cellular miRNAs have antiviral functions in mammalian cells (6), but their major function is to regulate endogenous gene expression. Most often in animals, they imperfectly pair with their target RNAs, and the primary outcome of miRNA-mediated regulations is translational repression. Interestingly, miRNA genes are clustered. miRNA gene clusters may have come about due to the co-transcriptional recruitment of miRNA processing enzymes, which facilitates the emergence of new sRNAs near existing ones (2). In addition, miRNA genes, within a cluster, share sequence conservation, suggesting that these clusters have expanded by local duplications. miRNA gene clusters may be subjected to duplications and to the subsequent appearance of new miRNA genes as a consequence of genomic imprinting. Indeed, miRNA clusters are enriched in imprinted regions [START_REF] Girardot | Cold Spring Harbor Laboratory Press[END_REF]. However, the driving forces for eukaryotic miRNA cluster formation remain essentially elusive.

The molecular events that direct prokaryotic crRNA cluster dynamics are far better understood (Figure 1). During adaptation, bacteria and archaea acquire new sequences from foreign DNA, and once integrated these spacers serve as templates for crRNA synthesis. Three recent studies explained foreign DNA acquisition preference and how spacer invaders are captured. Spacer acquisition is replication-dependent, and replication forks are more frequent on multicopy plasmids than on the chromosome. In addition, Chi sites, highly repeated octamer sequences on the bacterial chromosome, negatively impact spacer acquisition. Together, these observations explain how nonself DNA is preferred over the self for spacer acquisition [START_REF] Levy | [END_REF]. Two structural studies revealed how the Cas1-Cas2 complex acts as an integrase (9,10). This conserved complex binds a protospacer sequence to catalyze spacer acquisition. These recent works showed how protospacer length is predetermined, selected, processed into a spacer and integrated into the bacterial genome. These studies also showed that the Cas1-Cas2 complex has a similar structure to the eukaryotic transposases used by transposons to integrate into chromosomes.

The comparison of eukaryotic and prokaryotic sRNA clusters raises many questions. Are similar mechanisms at play in both domains? Can the growing knowledge gleaned from bacteria help us to understand eukaryotic cluster dynamics? What selection pressure induced such a peculiar genomic organization throughout evolution? Bringing together genes involved in similar functions is often seen to ease their co-regulation. Furthermore, piRNA clusters have specific epigenetic profiles (11) that may help to tag the transcribed RNAs as being piRNAs. Assembling sRNA genes into functional immunity clusters is probably a way to improve the efficiency of defenses against DNA intruders in cells from all domains of life.

  Cold Spring Harbor Laboratory Press on November 25, 2016 -Published by rnajournal.cshlp.org Downloaded from A c c e p t e d M a n u s c r i p t by aggregating captured transposons sequentially (

Figure 1 .

 1 Figure 1. Comparison showing the close resemblance of prokaryotic and eukaryotic immunity cluster RNA. Molecular defense against DNA intruders in the two domains was subdivided into nine distinct steps. During the initial adaptation phase, invasive DNAs (phages, plasmids, or transposons) are inserted into specialized genomic clusters. During the following interference phase, RNAs transcribed from these clusters associate into ribonucleoproteic complexes (yellow ovals) to target the invasive phage DNA for destruction in prokaryotes, or the transposon DNA for transcriptional gene silencing (TGS) in eukaryotes. sRNAs transcribed from clustered miRNA genes, as well as viral siRNAs, regulate post-transcriptionally gene expression by translational inhibition and/or RNA degradation (post-transcriptional gene silencing, PTGS).

9 .

 9 Effect on target nucleic acid 6'. viral dsRNA recognition RNA Cold Spring Harbor Laboratory Press on November 25, 2016 -Published by rnajournal.cshlp.org Downloaded from A c c e p t e d M a n u s c r i p t