P Carlos

P Yannis

V Rodolphe

C Pierre

Sensitivity of the MIMO Channel Characterization to the Modeling of the Environment

Pereira Carlos, Student Member, IEEE, Pousset Yannis, Vauzelle Rodolphe, and Combeau Pierre

Abstract-An important factor in electromagnetic wave propagation simulation, performed by a 3D ray-tracing method is the modeling of the environment. Results being sensitive to descriptive accuracy, this paper presents a study on the effect of indoor environment modeling precision on multiple input multiple output (MIMO) channel characterization. In order to give some diversity to the results, the investigation takes into account two unfurnished indoor environments. The first environment investigated is the entrance hall of a building at the University of Poitiers, while the second is a more confined environment and is represented by the first floor of the authors' laboratory. For these two indoor environments, four levels of description are proposed in order to establish the geometrical and electrical modeling impact on MIMO channel characterization. Results are obtained by analyzing the capacity, variation in correlation, multipath richness and eigenvalues in relation to the polarization, the presence of line-of-sight (LOS) or non-LOS (NLOS) configurations. The effects of the spacing between antennas and the number of transmitter and receiver antennas are also investigated. Index Terms-Capacity, correlation, environment modeling, multiple input multiple output (MIMO) channel characterization, polarization, 3D ray-tracing.

I. INTRODUCTION

I N MOST situations, mobile communication systems handle multimedia services in the form of wide-band systems, mobile radio channels being considered as wide-band channels. Moreover, these transmission media achieve their information propagation through a multipath mechanism. Received signals arrive from various directions, these variations being closely related to transmission quality. To overcome this drawback, traditional mobile communication systems exploit time or frequency diversity. However, to retain high spectral efficiency, one solution consists in capitalizing on spatial diversity by introducing arrays of antennas at the base and/or mobile stations of cellular networks. In order to optimize the design of array-processing algorithms, these transmissions, named multiple input multiple output (MIMO) systems, call for a thorough knowledge of the radio propagation channel. In most cases, MIMO channel characteristic parameters are evaluated by a set of measurements in studied environments, or by simulating propagation models [START_REF] Kivinen | Empirical characterization of wideband indoor radio channel at 5.3 ghz[END_REF], [START_REF] Abdi | A space-time correlation model for multielement antenna systems in mobile fading channels[END_REF]. The former approach requires MIMO experimental measurement platforms, which give access to pertinent information about the radio channel for both indoor and outdoor wireless communication scenarios. However, this approach presents difficulties: for example, in relation to the calibration step and the high cost.

Consequently, an approach based on simulations is sought. There are two families of models: the statistical type and the deterministic type. The first sort is connected with experimental investigations carried out in both indoor and outdoor environments. They have the advantage of being rapid in terms of computation time. The disadvantage is that they cannot be applied to all environmental configurations. The deterministic approach is more complex, but also more accurate for MIMO characterization applications, whatever the configuration. Unfortunately, the complexity of the environment description entails that this is time-consuming in terms of computation. Considering previous research involving deterministic simulation, several studies investigated MIMO channel characterization in pico-realistic environments [START_REF] Wallace | Experimental characterization of the MIMO wireless channel: Data acquisition and analysis[END_REF]. Variations in the spatial correlation and the capacity of the channel, based on a channel transfer matrix, were considered in relation, on the one hand, to the spacing between antennas, and on the other hand, to the number of antennas. These studies also allowed the polarization-diversity effect on MIMO channel performance to be described [START_REF] Abdi | A space-time correlation model for multielement antenna systems in mobile fading channels[END_REF], [START_REF] Kyritsi | Effect of antenna polarization on the capacity of a multiple element system in an indoor environment[END_REF]. It should be noted that the impact of complex wall structures on the capacity of MIMO wireless communication systems has been investigated [START_REF] Yun | Complex-wall effect on propagation characteristics and MIMO capacities for an indoor wireless communication environment[END_REF], it being found that complex walls cannot be appropriately characterized by simple concrete slab walls. To the authors' knowledge, however, in relation to larger scale description of line-of-sight (LOS) and non-LOS (NLOS) configurations, no investigation has been carried out concerning the influence of the geometric description level and the electrical properties of the environmental materials on MIMO channel characterization. Thus, this investigation addresses the question: Is it necessary or not, for MIMO characterization, to describe the studied area in detail? More precisely, the authors set out to ascertain if an accurate MIMO channel characterization simulation is sensitive to approximations in the description of the environment, as is the case for SISO (Single Input Single Output) characterization [START_REF] Browne | A simple approach to site sensitive modeling of indoor radio propagation[END_REF].

It is to be underlined that environment modeling complexity entails inordinately large computation time. Thus, the aim of this study is also to find the simplest modeling approach that ensures a satisfactory level of accuracy while not involving excessive computation time. In this paper, we consider a deterministic model based on an optimized 3D deterministic ray-tracing method [START_REF] Mora | Optimised scanning of a visibility graph data structure for efficient ray-tracing[END_REF], [START_REF] Escarieu | Outdoor and indoor channel characterization by a 3D simulation software[END_REF] associated with characterization software [START_REF] Chartois | A SISO and MIMO radio channel characterization with a 3D ray tracing propagation model in urban environment[END_REF]. In order to provide statistically robust results, a large number of simulations are undertaken, the approach being considered as a semi-deterministic MIMO characterization. Two indoor environments at the University of Poitiers are studied, the first being a large entrance hall of a building and the second being the first floor of the SIC 1 laboratory. These environments are modeled according to four levels of description, varying from simple parallelepipeds, where all materials are assumed to be concrete, to more complex rooms taking into account the actual electrical properties of materials. Geometrical and electrical effects are analyzed by comparing channel-characteristic parameters generated at each level of description. This paper is organized as follows. Section II presents the tools and characteristic parameters of the MIMO channel (spatial correlation, capacity and eigenvalues). Section III details the indoor environment modeling. It gives the characteristics of modeling levels, including geometrical and electrical descriptions. Section IV defines simulation conditions: polarization, LOS and NLOS, the spacing between antennas and the number of antennas. Finally, Section V presents simulated results for MIMO characteristic parameters.

II. THE MODELING AND CHARACTERIZATION OF A MIMO CHANNEL

A. Modeling of a MIMO Channel

In wireless communication, a received signal is the result of a multipath phenomenon. This is due to electromagnetic interactions (reflection, diffraction and refraction) between an electromagnetic wave and obstacles in the environment. Each path is characterized by a specific loss, polarization, propagation delay, as well as direction of arrival (DoA) and direction of departure (DoD) in azimuth and elevation [START_REF] Steinbauer | The double-directional radio channel[END_REF]. The received signal derives from the sum of all the paths. To simulate this multipath mechanism, a wave propagation simulator was developed in the SIC laboratory [START_REF] Mora | Optimised scanning of a visibility graph data structure for efficient ray-tracing[END_REF]. This allows a deterministic prediction of radio channel behavior. It associates an optimized 3D raytracing technique to an asymptotic frequency method, which is based on the geometrical optic (GO) and the uniform theory of diffraction (UTD). Fig. 1 shows input and output information 1 SIC: Signal Image Communications.

of the wave propagation simulator. The inputs concern information about the environment (geometrical and electrical properties), antennas (position, radiation pattern, polarization and carrier frequency) and electromagnetic interactions. The output information consists of the double-directional complex channel impulse response (CIR). These data are considered in order to arrive at the full characterization of the MIMO radio channel.

B. Characterizing a MIMO Channel

From the previous wave-propagation simulator output data, channel-characterization software, likewise developed in the laboratory [START_REF] Chartois | A SISO and MIMO radio channel characterization with a 3D ray tracing propagation model in urban environment[END_REF], allows the calculation and visualization of characteristic functions and parameters of the SISO and MIMO channels. In this section, the MIMO channel parameters are the focus and relate to correlations between MIMO sub-radio links and the ergodic capacity which are dependent on the eigenvalues. These parameters are based on the channel transfer matrix defined in the following subsection.

Each element of this matrix, calculated for each radio link, is a complex narrow band coefficient. It results from the contributions of all paths making up the CIR of a given radio link . Thus, is given by (2)

(2

)
where designates the total number of paths; and are the magnitude and phase of the th path.

2) Correlation: The first important characteristic parameter enabling the evaluation of the environmental modeling impact on MIMO propagation is the correlation [START_REF] Rodgers | Thirteen ways to look at the correlation coefficient[END_REF]. More precisely, a correlation matrix of dimensions equal to is analyzed. Each element of the matrix is defined by (3)

(3)
where and are the of , with and being, respectively, the variance and covariance operators.

3) Capacity: Ergodic capacity is the second important characteristic parameter. It evaluates the performance of MIMO channels by quantifying the maximum information able to be transmitted by the propagation channel without error [START_REF] Shannon | A Mathematical Theory of Communication Oct[END_REF], [START_REF] Gesbert | Breaking the barriers of Shannon's capacity: An overview of MIMO wireless system[END_REF]. Equations ( 4) and ( 5) or ( 6) and ( 7) define this parameter, expressed in Bit/s/Hz, so long as the power of each transmitting antenna is the same

• if (4)
• if

(6) (7)
where is the eigenvalues of or is the hermitian operator, is SNR (Signal Noise Ratio), and are respectively identity matrix of dimensions equal to and and is the expectation.

C. Semi-Deterministic Characterization

The evaluation of MIMO channel characteristic parameters is obtained via the association (cf. Fig. 2) of the wave-propagation simulator and the channel-characterization software. These types of software are used in order to perform a semi-deterministic study. They are thus applied to a set of a MIMO sub-radio links randomly defined. Note that this study has had to respect the stationary assumptions (WSSUS). As a consequence, the spatial variation of the antennas has been limited to small areas. Thus, the semi-deterministic study enabled by this association of software permitted the channel mean characteristic parameters (cf. Subsection II.B.2 and II.B.3) to be obtained.

III. MODELING OF THE ENVIRONMENT

To obtain varied results, two unfurnished indoor environments, differing in their dimensions and shape, are studied. The first one is a large entrance hall (cf. Fig. 3) which measures 28 43 m and is made up of 4 areas. The second environment is the first floor of the SIC laboratory (cf. Fig. 4); with a surface area of 13 57 m, composed of 22 rooms. For these two environments, the impact of geometrical and electrical description on MIMO channel-characterization is investigated. In order to define this impact, four levels of description have been adopted. The first, level A is the simplest [cf. Fig. 5(a)], being described in terms of two parallelepipeds whose walls are considered to be concrete. The thickness of the interior walls is 8 cm and that of the exterior walls is 16 cm. These two boxes represent the minimum level of description still allowing the investigation of LOS and NLOS configurations.

The second level [level B, shown in Fig. 5(b)] is more complex: while dealing with the same boxes as in level A, a fuller [START_REF] Vauzelle | A sensitivity study for an indoor channel[END_REF] geometrical description is provided. Thus, to the parallelepipeds are added doors, windows and radiators according to the architectural plans. In general, doors are taken to be 200 145 cm; windows 177 160 cm at a height of 100 cm. Finally, radiators, 120 40 cm in size and placed at a height of 28 cm are spaced at 156 cm intervals. They are placed only on the left-hand side of the modeled parallelepipeds. Level B retains the electrical description of level A. As a result, a comparison between levels A and B highlights properties deriving from the geometrical description.

Level C [illustrated in Fig. 5(c)] considers additional boxes besides the two of level B and employs the same geometrical precision. Thus, all the boxes making up the environment have the most accurate geometrical description possible. These additional rooms not being directly concerned by the transmission, the comparison between levels B and C shows the effect of external boxes on the characterization.

Finally, an ultimate description level, called level D [cf. Fig. 5(d)], retaining the same geometrical description as that of level C, is considered. At this level, all geometrical elements have their correct electrical properties (taking into account: relative permittivity and conductivity ), as shown in Table I. The comparison between these last two levels shows the effect of electrical properties of the environmental materials independently of their geometry. The best description was used for previous investigation [START_REF] Vauzelle | A sensitivity study for an indoor channel[END_REF], [START_REF] Escarieu | Etude de la propagation dans les milieux indoor autour de 2 GHz[END_REF] which had validated the presented simulator with comparisons between measured and simulated results for the two environments. Consequently, the level D is considered as the reference of this study.

IV. PROPAGATION SIMULATION CONDITIONS

This section presents, on the one hand, the wave-propagation simulator parameters and, on the other, the different configurations investigated.

A. Wave-Propagation Simulator Parameters

A carrier frequency of 5.18 GHz is chosen in accordance with Wifi 802.11n standard. The induced wavelength is thus approximately 6 cm. Transmitter and receiver antennas are half-wave dipoles placed at 1.5 m above the ground. The wave-propagation simulator, which delivers a sinusoidal waveform signal, was parameterized in such a way that a maximum of two reflections, one diffraction and five refractions were allowed for each path. In fact, these parameters had emerged from previous studies [START_REF] Vauzelle | A sensitivity study for an indoor channel[END_REF] of indoor SISO cases based on comparisons between simulations and actual measurements. It is helpful at this point to note that, in the current characterization, CIR are not normalized and that mutual coupling between antennas is not considered.

B. MIMO Configurations

In both of the studied environments, antennas vary randomly according to a uniform law in zones of one meter square. Seven zones are identified (cf. Figs. 3 and4). One of them is dedicated to receiver antennas, the others being reserved for transmitter antennas with respect to LOS and NLOS cases. Each study takes into account three different positions. Thus, the MIMO characteristic parameters presented in Section V result from an averaged set of simulations. In the entrance hall environment, the mean radio link length is approximately 8 m, while in the first floor environment this distance is 4 m. The simulation is achieved with or without polarization diversity. In the first case, all antennas are vertically polarized. In the second, polarization diversity is obtained by inclining the antennas at angles of 45 and 135 . For all the possible scenarios, the variation in the MIMO characteristic parameters is investigated in relation to:

• the spacing between antennas for a MIMO transmission. In transmitter and receiver areas, two antennas are in the first place randomly positioned at a distance of . Afterwards, the spacing is augmented in a stepwise fashion, each spatial step being [cf. Fig. 6(a)]. • the number of antennas. The number of transmitter and receiver antennas grows from one ( SISO) to seven ( MIMO). The first two antennas are randomly positioned and the others follow the alignment of these two. The result is a linear antenna array, the spacing between antennas being fixed at 0.4 [cf. Fig. 6(b)]. This generally corresponds to a minimum correlation [START_REF] Chuah | Capacity scaling in MIMO wireless systems under correlated fading[END_REF], although this value directly depends on what environments and scenarios are considered, as well as the type of antenna used. For each possible combination of parameters, involving the visibility, the spacing between antennas, the number of antennas and the polarization diversity, 7000 simulations were carried out for a particular environment. Overall, this study represents 112000 simulations. In the rest of this work, the gain in capacity is addressed. Defined in [START_REF] Yun | Complex-wall effect on propagation characteristics and MIMO capacities for an indoor wireless communication environment[END_REF], this gain results from the normalization of the average capacities by considering the average capacities of the single transmission, single receiver antenna system (i.e.,

). Moreover, these equivalent SISO capacities are obtained for the highest level of description (level D) and for the considered polarization. Consideration of thus frees the investigation from needing to take account of transmission and reception constraints. These constraints include normalization problems related to CIR, transmission power, reception amplification and SNR. This last-mentioned parameter is kept at 30 dB throughout the study. [START_REF] Escarieu | Outdoor and indoor channel characterization by a 3D simulation software[END_REF] V. RESULTS

A. Variation in Characteristic Parameters in Relation to the Spacing Between Antennas

In this section we present simulation results for the variation in the characteristic parameters (gain in capacity, correlation matrix, multipath richness and eigenvalues) with respect to the spacing between antennas.

1) Los Configuration Without Polarization Diversity:

In this subsection, transmitter and receiver antennas are in LOS and do not involve polarization diversity. This means that CIR are composed of a set of paths, including the direct path, which is the most powerful. Figs. 7 and8 show the increased gain in capacity and highlight this in relation to the spacing between antennas. Whatever the level, this gain increases up to approximately 0.4 [START_REF] Chuah | Capacity scaling in MIMO wireless systems under correlated fading[END_REF]. Fig. 8 shows that the level of description does not affect the evaluation of gain in capacity. For the entrance hall environment, however, there is a great difference between level A and the other three levels. Thus, an oversimplified geometrical description cannot allow a pertinent evaluation of channel characteristic parameters.

To complete these observations, the focus firstly shifts to the correlation between MIMO sub-radio links. Next to be addressed are the cumulative functions associated with multipath richness. Consideration is also given to the eigenvalues of the H non-normalized matrix of the channel for all the studied MIMO radio links. These characteristic parameters are evaluated in the same environments under the same conditions.

In the correlation matrices only the inter-correlations between the different MIMO sub-radio links have been analyzed. The curves shown in Fig. 9(a) and (b) emerge:

• curves and involve CIR emanating from the same transmitter; • curves and involve CIR arriving at the same receiver; • curves and involve CIR coming from both transmitters and going to both receivers. The variation in the correlations is similar to that of a Bessel function, with minimum values at and , in line with previous studies using dipolar antennas [START_REF] Chuah | Capacity scaling in MIMO wireless systems under correlated fading[END_REF].

As shown in Fig. 9(b), correlations vary in a similar way with respect to description levels. This similarity is supported by the results relating to capacity. However, for the entrance hall environment [cf. Fig. 9(a)], inter-correlation characteristic variation at level A is different from that found at the other levels. This means that geometrical description (in this configuration) has an impact on channel-characteristic parameters. This difference can be noted in curves and . Examining these curves suggests that MIMO characterization depends on a minimum of geometric description of rooms that is directly related to the transmission, but seems to be insensitive to an electrical description (cf. comparison between levels C and D).

The previous analysis is reinforced by the curves shown in Figs. 10, 11, 12, and 13, corresponding respectively to the cumulative functions of multipath richness and eigenvalues of the simulated MIMO radio links in the entrance hall and the first floor environments.

In general, it is observed that the large number of multipaths rises from level A to level D, in line with the increasing descriptive precision of the two environments considered. This was the case irrespective of the scenarios investigated. Furthermore, the average eigenvalues associated with level A are lower than those for the other levels for the entrance hall environment ( at 50% for level A, versus approximately for the other levels). This leads to a smaller spread of the eigenvalues for level A and to a weaker capacity. For the first floor environment, the eigenvalues resemble each other for all four levels (approximately at 50%, whatever the level). This leads to changes in capacity close to the level in the other environment. These features were observed for all other scenarios, showing that in the majority of the cases, only the distribution of the eigenvalues associated with level A differs significantly from those of the other levels.

2) LOS Configuration With Polarization Diversity: Picking up on the above results, an attempt is made to determine whether or not polarization diversity increases the effects of environment modeling on MIMO characterization. Figs. 14 and15 show that the pattern of gains in capacity corroborates the findings relating to gains in capacity without polarization diversity [cf. Figs. 7 and8]. Accordingly, comparison between the results in Subsections V.A.1 and V.A.2 indicate that the impact of environment modeling on MIMO characterization is the same, whatever the antenna polarization in a LOS configuration.

It can be noted that the trend in the results shown in Subsections V.A.1 and V.A.2 is similar. This is due to the definition of gain in capacity (normalization of MIMO capacity by SISO capacity) being specified without recourse to units of measurement.

3) NLOS Configuration Without Polarization Diversity: The main difference between the LOS and NLOS configurations is that, in the latter, there is no longer a direct path. A focus on this condition allows the influence of the direct path on environment We observe, however, for the entrance hall environment that the change in capacity associated with level A is greater that for the other levels. This can be explained by the curve in Fig. 18 showing that the eigenvalues of level A give an average ( at 50% for the level A, versus approximately for the other levels) and a dispersal more substantial than those for the other levels. This means not only that level A generates an insufficient number of rays, but also that the rays generated have incorrect amplitudes.

Finally, it should be noted that these analyses confirm those in the literature [START_REF] Tang | Indoor multipath characterization for MIMO wireless communications[END_REF]- [START_REF] Svantesson | On signal strength and multipath richness in multi-input multi-output systems[END_REF] showing that the power of the rays has a more important impact on the performance of the MIMO channel than impact associated with the multipath richness.

However, characteristic parameters seem again to be insensitive to electrical description and additional architectural elements. This demonstrates that a direct path modifies the effects of environment modeling. Supporting this, the same results are obtained with polarization diversity.

B. Summary

Before turning attention to MIMO characterization in relation to the number of antennas, the above results are summarized. It has been shown that channel characteristic parameters are not sensitive to electrical description, whatever the configuration of the environment and whatever the polarization.

Furthermore, it is asserted that geometrical description has an impact on MIMO characterization. This fact is amplified in the NLOS configuration because of the lack of a direct path. At larger-scale description, it is shown that architectural elements outside the rooms involved in wireless transmission have little influence on MIMO channel characterization. Accordingly, level B would seem to be a satisfactory level of description for accomplishing an adequate characterization of a MIMO channel. This allows a gain in computation time over level D roughly to the order of two.

C. Variation of Characteristic Parameters in Relation to the Number of Antennas

To build on the above findings, the following results evaluate gains in capacity in relation to the number of antennas (cf. Section IV.B), for LOS and NLOS cases, with and without polarization diversity. The aim of this part is to examine previous assumptions for more than two transmitter and receiver antennas.

1) LOS Configuration Without Polarization Diversity: Figs. [START_REF] Svantesson | On signal strength and multipath richness in multi-input multi-output systems[END_REF] and 20 show an increasing gain in capacity in relation to the number of antennas. This is line with the study of Yun and Iskander [START_REF] Yun | Complex-wall effect on propagation characteristics and MIMO capacities for an indoor wireless communication environment[END_REF]. Moreover, these figures clearly show that a minimum level of modeling is necessary as the number of antennas increases. In fact, where there are more than two transmitter and receiver antennas, the simplest modeling (level A) is not sufficient to adequately evaluate MIMO channel characteristic parameters. It thus appears that a geometric level of description is of major importance for MIMO characterization. A minimum level of description is required to take into account the propagation of predominant paths. In spite of this, it is not necessary to consider all geometric elements (i.e., all rooms). In the end, an electrical description of materials has less impact on MIMO channel characterization than a geometrical description. and20). Thus, these results corroborate the analysis of the previous section.

3) NLOS Configuration Without Polarization Diversity:

The study of the lack of a direct path in the Section V.A.3 has shown that the influence of environment modeling emerges in this condition. The contrast of these results (see Figs. 23 and24) and those presented in Section V.A.3 supports this assumption.

VI. CONCLUSION

This work has investigated environment modeling effects on MIMO channel characterization. The goal was to answer to the question: What degree of accuracy is required to describe the indoor environment, both geometrically and electrically, to arrive at an adequately accurate MIMO channel characterization involving a minimum of computation time?

To highlight modeling effects, correlation matrices and gain in capacity values, multipath richness and eigenvalues were used. These characteristic parameters were investigated in relation to the spacing between antennas on the one hand, and the number of antennas on the other hand. Moreover, environment modeling effects were studied in LOS and NLOS cases, with or without polarization diversity. All the cases studied revealed that MIMO characterization is quite insensitive to the electrical properties of materials. In the same context, the results show that rooms beside those directly concerned by the transmission have a little impact on MIMO channel characterization. However, geometrical precision in the description of rooms is a crucial parameter in achieving an accurate characterization. Indeed, characteristic parameters vary strongly where modeling of the environment involves poor geometric description. This fact is amplified in NLOS configurations where a direct path is lacking. It is concluded that pertinent environment modeling requires a minimum level of description of geometric elements involved in propagation configurations. Further, materials can be described uniformly as having the electrical properties of concrete. It is consequently assumed that level B ensures an adequate level of descriptive accuracy, while offering a gain in computation time roughly of the order of two, when compared with level D descriptions.

Fig. 1 .

 1 Fig. 1. Summary chart of wave propagation simulation.

1 )

 1 Channel Transfer Matrix: The channel transfer matrix, is an narrow band matrix, and being respectively the numbers of receiver and transmitter antennas. The expression of is shown in[START_REF] Kivinen | Empirical characterization of wideband indoor radio channel at 5.3 ghz[END_REF]

Fig. 2 .

 2 Fig. 2. Association between the wave-propagation simulator and the characterization software.

Fig. 3 .

 3 Fig. 3. Entrance hall environment.

Fig. 4 .

 4 Fig. 4. First floor environment.

Fig. 5 .

 5 Fig. 5. Levels of description for the first floor environment. (a) Level A. (b) Level B. (c) Level C. (d) Level D.

Fig. 5

 5 Fig. 5 illustrates these levels of description for the first floor environment.The first, level A is the simplest [cf. Fig.5(a)], being described in terms of two parallelepipeds whose walls are considered to be concrete. The thickness of the interior walls is 8 cm and that of the exterior walls is 16 cm. These two boxes represent the minimum level of description still allowing the investigation of LOS and NLOS configurations.The second level [level B, shown in Fig.5(b)] is more complex: while dealing with the same boxes as in level A, a fuller

Fig. 6 .

 6 Fig. 6. Scenarios of antennas. (a) Spacing between antennas. (b) Number of antennas.

Fig. 7 .

 7 Fig. 7. Entrance hall environment: variation in the gain in capacity in relation to the spacing between antennas in LOS, without polarization diversity.

Fig. 8 .

 8 Fig. 8. First floor environment: variation in the gain in capacity in relation to the spacing between antennas in LOS, without polarization diversity.

Fig. 9 .Fig. 10 .Fig. 11 .

 91011 Fig. 9. Variation in correlation in relation to the spacing between antennas in LOS, without polarization diversity. (a) Entrance hall, (b) First floor.

Fig. 12 .Fig. 13 .

 1213 Fig. 12. First floor environment: cumulative functions associated with the multipath richness in a LOS configuration, without polarization diversity.

Fig. 14 .

 14 Fig. 14. Entrance hall environment: variation in gain in capacity in relation to spacing between antennas in LOS, with polarization diversity.

Fig. 15 .

 15 Fig. 15. First floor environment: variation in gain in capacity in relation to the spacing between antennas in LOS, with polarization diversity.

Fig. 16 .

 16 Fig. 16. Entrance hall environment: variation in the gain in capacity in relation to the spacing between antennas in a NLOS, without polarization diversity.

Fig. 17 .

 17 Fig. 17. First floor environment: variation in the gain in capacity in relation to the spacing between antennas in a NLOS, without polarization diversity.

Fig. 18 .

 18 Fig. 18. Entrance hall environment: cumulative functions associated with the eigenvalues in NLOS configuration, without polarization diversity.

Fig. 19 .Fig. 20 .

 1920 Fig. 19. Entrance hall environment: variation in the gain in capacity in relation to the number of antennas in a LOS configuration, without polarization diversity. (The element spacing is equal to).

Fig. 21 .

 21 Fig. 21. Entrance hall environment: variation in the gain in capacity in relation to the number of antennas in a LOS configuration, with polarization diversity. (The element spacing is equal to).

Fig. 22 .

 22 Fig. 22. First floor environment: variation in the gain in capacity in relation to the number of antennas in a LOS configuration, with polarization diversity. (The element spacing is equal to).

Fig. 23 .

 23 Fig. 23. Entrance hall environment: variation in the gain in capacity in relation to the number of antennas in a NLOS configuration, without polarization diversity. (The element spacing is equal to).

Fig. 24 .

 24 Fig. 24. First floor environment: variation in the gain in capacity in relation to the number of antennas in a NLOS configuration, without polarization diversity. (The element spacing is equal to).

TABLE I ELECTRICAL

 I PROPERTIES OF THE MATERIALS IN THE STUDIED ENVIRONMENTS, AS DEDUCED FROM MEASUREMENTS

Authorized licensed use limited to: CNRS -XLIM UMR 6172. Downloaded on November 13, 2009 at 11:10 from IEEE Xplore. Restrictions apply.


T Dreyfus
email: tom.dreyfus@sophia.inria.fr

V Doye

F Cazals

Probing a Continuum of Macro-molecular Assembly Models with Graph Templates of Complexes

Keywords: Macro-molecular assembles, Reconstruction by data integration, Nuclear Pore Complex, Model assessment, Toleranced Models, isomorphic graphs, maximum common sub-graphs assemblage macro-moléculaire, reconstruction par intégration de données, pore nucléaire, évaluation de modèles, modèles tolérancés, graphes isomorphes, plus grands graphes communs

Reconstruction by data integration is an emerging trend to reconstruct large protein assemblies, but uncertainties on the input data yield average models whose quantitative interpretation is challenging. This paper presents methods to probe fuzzy models of large assemblies against atomic resolution models of sub-systems. More precisely, consider a Toleranced Model (TOM) of a macro-molecular assembly, namely a continuum of nested shapes representing the assembly at multiple scales. Also consider a template namely an atomic resolution 3D model of a sub-system (a complex) of this assembly. We present graph-based algorithms performing a multi-scale assessment of the complexes of the TOM, by comparing the pairwise contacts which appear in the TOM against those of the template. We apply this machinery to recent average models of the Nuclear Pore Complex, and confront our observations to the latest experimental work. The software implementing the algorithms of this paper, Graph_matcher, is available from the VORATOM suite, see http://team.inria.fr/abs/software/voratom.

Introduction

Reconstruction by data integration.

Small protein complexes involving a handful of polypeptide chains are typically studied with X ray crystallography and/or NMR. The situation is completely dierent for macro-molecular assemblies involving from tens to hundreds of chains (nuclear pore complex, chaperonin cavities, the proteasome, ATP synthases, etc), for which the impossibility to obtain thorough information using the aforementioned experimental techniques motivated the development of reconstruction by data integration (RDI) [AFK + 08]. In RDI, plausible coarse-grain models of the assembly, which typically use of the order of 10 balls per protein (or nucleic acid), are selected by a non-convex optimization function maximizing the agreement of the model with various experimental data (cryo-electron microscopy (cryo-EM), centrifugation, immuno-labeling experiments, tandem anity purication, etc).

However, both the data used in RDI and the results provided need to be handled with care. For example, the maps obtained in cryo-EM are often noisy, so that choosing a density level to contour a surface enclosing the model is not trivial [START_REF] Frank | Three-dimensional electron microscopy of macromolecular assemblies: visualization of biological molecules in their native state[END_REF]. Protemomics data are often diculty to interpret. In particular Tandem Anity Purication Data (TAP) [PCR + 01] , which provide proximity information between protein types, are inherently ambiguous since the protein types identied do not provide any information on the number of complexes involving the tagged proteinletting alone the stoichiometry issues. Immuno labeling experiments, which consist of locating a protein thanks to specic immunoglobulins tagged with gold particles, suer from localization uncertainties. Other types of data present similar issues.

Consequently, the problem of selecting models which best comply with the data is inherently ill-posed, and the output typically consists of an ensemble of plausible models. This state of aairs is illustrated by the reconstruction of the Nuclear Pore Complex (NPC) [ADV + 07a, ADV + 07b], a protein assembly with eight-fold axial symmetry regulating the nucleo-cytoplasmic transport, and made of ∼ 456 protein instances of 30 protein types. Based on the reconstruction by data integration approach, the authors were able to select 1000 coarse-grain structures. These structures were further averaged to produce one probability density map per protein type, i.e. a map encoding the probability of presence of the instances of that type in the NPC.

Parameterized assembly models and their assessment.

The maps produced for the NPC are of probabilistic nature and actually mirror the uncertainties on the input data [ADV + 07a, ADV + 07b]. For a given map, while identifying high condence landmarks is rather easy, e.g. the local maxima of the probability, making statements of the rest of the map is more challenging. For example, the mere problem of placing a prescribed number of protein instances within a map is an ill-posed problem, as the volume of the union of the voxels with a strictly positive value can be signicantly larger than the volume of these instances, a fact which motivated the introduction of Toleranced Models (TOM) [START_REF] Latombe | Assembly sequencing with toleranced parts[END_REF]. Prosaically, a TOM is a mathematical model whose modeling primitive is toleranced ball, namely two nested concentric balls [START_REF] Cazals | Multi-scale Geometric Modeling of Ambiguous Shapes with Toleranced Balls and Compoundly Weighted α-shapes[END_REF]: the inner ball represents a high condence region, while the outer one delimits the range of interest. The exploration of the region between these two balls is achieved by interpolating between the inner and the outer radii, a process governed by a parameter λ ∈ [0.1]. Because a TOM inherently denes a continuum of model, probing this continuum against an atomic resolution structure or a structure within which the pairwise contacts are believed to be correct is a key endeavor.

TOM: previous work and contribution.

TOM were introduced in [START_REF] Cazals | Multi-scale Geometric Modeling of Ambiguous Shapes with Toleranced Balls and Compoundly Weighted α-shapes[END_REF], and two types of analysis were developed in [START_REF] Dreyfus | Assessing the reconstruction of macro-molecular assemblies with toleranced models[END_REF]. We rst introduced the notion of contact probability, namely the probability to observe k dimers involving two specic protein types, as a function of λ. Second, we analyzed isolated copies i.e. protein complexes involving a given set of protein types with prescribed stoichiometry, and discussed their number with respect to the symmetry properties of the assemblythis latter analysis relies on so-called Hasse diagrams, see Fig. 1(D) in [START_REF] Cazals | Multi-scale Geometric Modeling of Ambiguous Shapes with Toleranced Balls and Compoundly Weighted α-shapes[END_REF].

These analysis actually suer from two main limitations. First, isolated copies do not allow reporting protein complexes which involve the given set of protein types but whose stoichiometry diers from the imposed one. Second, the connectivity of a protein complex cannot be assessed, so that two complexes having the same stoichiometry (for each protein species) cannot be distinguished even if they have dierent connectivity.

In the sequel, we provide tools circumventing these limitations, with one key application in mind, namely the comparison of a protein complex from a TOM model, against a high resolution model obtained by crystallography and/or modeling.

Methods

Hasse Diagram and Isolated Copies

Since our tools shall be applied to nodes of the Hasse diagram of a TOM, we rst recall some fundamental notions (see also supplemental section in [START_REF] Dreyfus | Assessing the reconstruction of macro-molecular assemblies with toleranced models[END_REF]).

The growth process mentioned in introduction results in merges between growing proteins and complexes, which occur for specic values of the parameter λ (see Fig. 1(C) in [START_REF] Dreyfus | Assessing the reconstruction of macro-molecular assemblies with toleranced models[END_REF]). We record such events in a directed acyclic graph, also called a Hasse diagram: its nodes correspond to protein complexes; an edge corresponds to an ancestor -successor pair in the merge process. Prosaically, the Hasse diagram records the protein contact history (see Fig. 1(D) in [START_REF] Dreyfus | Assessing the reconstruction of macro-molecular assemblies with toleranced models[END_REF]). The Hasse diagram can be constructed in the monocolor setting where all the protein types are indistinguishable. But it can also be constructed in the bicolor setting, where some protein types of interest have been painted in red, the remaining types being painted in blue. For example, the red proteins may represent the types seen in a Tandem Anity Experiment, or the types present in a complex. In this bicolor setting, given a stoichiometry for each red protein type, a node of the Hasse diagram is called an isolated copy if it contains the prescribed number of instances of each red protein type.

Note that the larger the value of λ at which a complex appears, the weaker the accuracy of the contacts between its constituting instances. To quantify this accuracy, the volume ratio V λ (C) measures the ratio between the volume of the toleranced balls of the protein complex C interpolated at λ, and a reference volume of C computed from the sequences of the proteins [START_REF] Dreyfus | Assessing the reconstruction of macro-molecular assemblies with toleranced models[END_REF].

2.2

Comparing a Protein Complex to a Template

In the sequel, we assume that a Hasse diagram associated to a set of protein types in a TOM is given. Denote C the protein complex associated to a node of the Hasse diagram. We endow this node with its skeleton graph G C , which encodes the pairwise contacts within C. We wish to compare the skeleton graph G C against the skeleton graph G t of a template T of C (Fig. 1). Practically, T shall be a co-crystallized complex or a high-resolution model built in-silico, and the protein types in T identify the red proteins of the bicolor setting.

Search of protein complexes similar to a template.

The skeleton graph G C corresponds to a complex C whose nodes are protein instances i.e. each instance carries a unique identifying label in the assembly. On the one hand, the nodes of G t are protein types; assuming that the Inria template contains at most one instance of each type, a node of G C (a protein instance) can be uniquely mapped to a node of G t (a protein type).

We assume that all the types of the instances present in the protein complex C are present in the template skeleton graph T . But the complex C may not feature instances of all the types found in the template T . We therefore denote G t|C the restricted template i.e. the graph obtained by removing from G t all the nodes whose protein types are not found in the protein instances of G C , and the edges incident on these nodes. To compare the graphs G t|C and G C , we use the concept of matching. Since matchings are intimately related to Maximal Common Induced Sub-graphs (MCIS) and Maximal Common Edge Sub-graphs (MCES), we rst recall these notions (Supplemental Fig. 4):

Maximal Common Sub-graphs. Let G 1 = (V 1 , E 1 ) and G 2 = (V 2 , E 2 ) be two undirected labelled graphs. Denition. 1. A Maximal Common Edge Sub-graph (MCES) of G 1 and G 2 is a graph H which is isomorphic to sub-graphs G ′ 1 of G 1 and G ′ 2 of G 2 , such that there is no other Common Edge Sub-graph H ′ of G 1 and G 2 containing H. Denition. 2. An induced sub-graph G ′ of G is a sub-graph of G such that for all pairs of vertices (u, v) of G ′ , (u, v) is an edge of G ′ i it is an edge of G. Denition. 3. A Maximal Common Induced Sub-graph (MCIS) of G 1 and G 2 is a graph H which is isomorphic to induced sub-graphs G ′ 1 of G 1 and G ′ 2 of G 2 , such that there is no other Common Induced Sub-graph H ′ of G 1 and G 2 containing H.
Notice in particular that a MCES or MCIS calculation yields in general several matchings. Computationally, the computation of MCES and MCIS is tantamount to the computation of maximal cliques [START_REF] Cazals | An algorithm for reporting maximal c-cliques[END_REF].

2.3

Matchings: Depleted, Complete, Exact and Perfect

Matchings and their signatures. We dene a matching as the mapping between vertices and edges of G t|C and G C , dened either by a MCIS or a MCES. That is, the matching maps vertices of G t|C (protein types of the template) to vertices of G C (protein instances of the complex), and edges of G t|C (contacts within the template) to edges of G C (contacts within the complex).

Taking the template as reference, we assess a matching with its signature (Fig. 1):

Matched protein type(s): a protein type of G t|C with a corresponding instance in G C . This

set is denoted V ∼ .
Missing protein type(s): a protein type of

G t with no corresponding instance in G C . This set is denoted V -. Matched contact(s): a contact in G t|C with a counterpart in G C . This set is denoted E ∼ . Missing contact(s): a contact in G t|C whose protein types match instances in G C but with no corresponding contact in G C . This set is denoted E -.
Extra contact(s): a contact in G C whose protein instances match types in G t|C but with no corresponding contact in G t|C . This set is denoted E + .

Using these sets, the signature of the matching A is dened by:

S(G t ; G C ; A) = {V ∼ , V -, E ∼ , E -, E + }.
(1)

To further classify matchings, we use the two sets V -and E -∪ E + . Each such set faces two situations, namely is empty or not, which yields four types of matchings:

Denition. 4. A matching is called depleted when

V -= ∅ and E -∪ E + = ∅ (2)
A matching is called complete when

V -= ∅ and E -∪ E + = ∅ (3)
A matching is called exact when

V -= ∅ and E -∪ E + = ∅ (4)
A matching is called perfect when

V -= ∅ and E -∪ E + = ∅ (5)
Note that for an exact matching, all the contacts between the protein types of V ∼ are present, but some protein types are missing, i.e. contacts incident to missing protein types are not considered as missing contacts. The support and the instantiation of a matching. As just explained, matchings are sought by performing MCES and MCIS calculations. Consider a complex C for which a matching has been found. The complex associated to the node C is said to host the matching. Equivalently the complex is called the support of the matching, and abusing terminology, the node associated to C may also be called the support of the matching. If the protein instances involved in the matching form a sub-complex of C, these instances are called the instantiation of the matching.

Note in particular that a given complex C may be the support of several matchings. As system under scrutiny, we use the NPC, the largest protein assembly of the eukaryotic cell known to date, which consists of about n ∼ 456 instances of k = 30 protein types, the stoichiometry of a protein type being 8 or 16. So far, two types of results have been obtained on the NPC. On the one hand, global yet qualitative results have been obtained based on data integration, in particular the aforementioned maps [ADV + 07a, ADV + 07b]. On the other hand, a number of complexes of the NPC have been modeled at atomic resolution, using in particular crystal structures of dimers or trimers. This is in particular the case of the so-called Y -complex, an heptameric complex playing a major role to form the NPC scaold [LKB + 02] (Fig. 2(A)).

Yet, the embedding of its 16 Speaking of these pairwise contacts, six of them involving the seven protein species were previously established (in the sequel, we use the nomenclature dened in [BLS + 08]); in particular, two dimers (the Y X -long-arm involving (Nup85,Seh1)[BLS + 08], and the Y X -tail involving (Nup133,Nup84) [START_REF] Whittle | Architectural nucleoporins Nup157/170 and Nup133 are structurally related and descend from a second ancestral element[END_REF]), and one trimer (the Y X -edge involving (Nup84,Nup145C, Sec13) [NHD + 09]) were solved by crystallography. These contacts dene the template skeleton G t (Y ) (Fig. 2(A)). Moreover, an additional contact between Nup145C and Nup85 was recently proposed in [FMPS + 12] and further characterized in [START_REF] Bilokapic | Molecular basis for nup37 and ely5/elys recruitment to the nuclear pore complex[END_REF]. Since this last contact was never observed in the TOM of the NPC (see Fig. 4 in [START_REF] Dreyfus | Assessing the reconstruction of macro-molecular assemblies with toleranced models[END_REF]), we dene the template skeleton G t (Y ) from the six previous pairwise contacts (Fig. 2(A)).

Since our previous analysis [START_REF] Dreyfus | Assessing the reconstruction of macro-molecular assemblies with toleranced models[END_REF] focused on the Y -complex as a whole, we now use our graphical tools to assess the coherence between the TOM of the whole NPC and the pairwise contacts just recalled. The analysis presented in [START_REF] Dreyfus | Assessing the reconstruction of macro-molecular assemblies with toleranced models[END_REF], based on the tools recalled in section 2.1, concluded that 11 isolated copies of the Y -complex were present in the TOM, out of the 16 expected (Fig. 2(B,C)). To understand this discrepancy, recall that the Y -complex consists of a tail known as the edge element E i = (Y X -tail,Y X -edge) and two arms A i = (Nup120, Y X -long-arm) (Fig. 2(A)). Also recall that in the ring model, 8 copies of the Y -complex form an annulus on the cytoplasmic (and likewise on the nuclear side), so that these 8 copies can be cyclically ordered. Now, let us focus on one of these 8 complexes in the TOM, say the ith one. If, along the growth process of the TOM, the merge of the arms A i-1 with the edge E i (, or that of the arms A i with the edge E i+1 ,) occurs before the merge between E i and A i , then, this ith copy does not appear as an isolated copy since the stoichiometry condition is violated.

We now show how matchings circumvent this limitation, and also provide information of pairwise contacts. Along the way, we shall refer to the matchings of the Table 3(A,B,C), each of them being referred to by a tag, e.g. M D (i) for a depleted matching, M C (i) for a complete matching, M E (i) for an exact matching, and M P (i) for a perfect matching.

Depleted and Complete Matching

To identify the 16 copies of the Y -complex, we rst compute the depleted and complete matchings of the protein complexes at the roots of the Hasse diagram with G t|C (Y ) (Fig. 2 (C, (a) and (b), and Fig. 3(A,B)). Ten depleted matchings are obtained for (Y X -tail,Y X -edge) (M D (1), M D (2)), and likewise for (Nup120 ,Y X -long-arm) (M D (3)). These matchings correspond to ten instances of the Y -complex split into two complexesthat is another protein instance (from this precise Y -complex, or from another Y -complex, or another NUP) disrupts the connectivity (Nup145C, Nup120). To value the interest of matchings, we also counted the number of matchings having a support which is one of the 11 isolated copies of the Y -complex (i.e, the green nodes in Fig.

2(C))

. Counts of 0 and 1 (M C (1)) for the depleted and complete matchings illustrate the radically dierent nature of the information encoded by both constructions. By inspecting the instantiations of the depleting matchings M D (1), M D (2) and M D (3), it turns out that each of the ten split Y -complex admits two possible reconstructions. Indeed, as explained in Sec. 4.1, one does not know whether two successive pieces are part of the same Y -complex instance or of two distinct instances. Further inspection of the six matchings for the whole Y -complex (two depleted (M D (4) with only one missing protein type, and four complete matchings M C (1))) shows that once embedded into the two rings (Fig 1 (B)), ve Y -complex instances have the same orientation in a ring, the last one having the opposite orientation in the other ring. Note that the split Y -complex instances neighboring a complete Y -complex instance have only one possible reconstruction. Phrased dierently, the complete Y -complexes impose a unique conguration for each of the 16 instances of the Y -complex.

Inspection of the signatures of all these matchings also shows that the number of extra contacts observed is bounded by seven for a maximum of fteen, see max E + column in Fig. 3(B). Indead, seven proteins make at most twenty one pairwise contacts, out of which six belong to the template.

To assess the geometric accuracy of these complexes, we observe that the volume ratio does not exceed 5.83 (M D (3)), namely twice the maximal volume ratio of the 11 isolated copies (V λ ∈ [0.86, 2.14]). This degradation in moving from isolated copies to depleted or complete matchings is actually expected: the connectivity constraint specifying a matching being more stringent than the mere presence constraint qualifying an isolated copy, larger values of λ (whence larger volumes) are required to meet the constraint imposed by the template skeleton.

4.3

Exact and Perfect Matching Since we did not observe any perfect matching, we successively analyze the largest exact matchings obtained, and proceed with those corresponding to crystallographic complexes. (Fig. 2 (C,(c)), and Fig. 3(C)) Largest exact matchings. Five exact matchings involving four protein types (M E (1) with Nup84, Nup145C, Nup120 and Nup85) are found, but no exact matching containing a superset of these proteins is observed.

We also note that a single matching in M E (1) has as support which is an isolated copy, this copy being also the support of the complete matching M C (1) (bicolored node in Fig. 1(C,(b) and (c))). Y X -tail. We found 16 exact matchings containing the Y X -tail (M E (1)+M E (2)), 15 of them strictly matching the Y X -tail (M E (2)), and a supplementary one also containing Nup145C (M E (3)). The absence of exact matching containing the Y X -tail (if one omits M E (3)) shows that instances of Nup145C make spurious contacts with Nup133 before Nup84 during the growth process. We note in passing that these extra contacts prevent from nding exact matchings but Inria do not provide any hindrance for depleted and complete matchingsthis actually owes to the dierence between MCIS and MCES.

We also observe that no exact matching with the Y X -tail whose support is an isolated copy. Y X -edge. We found only ve exact matchings containing the Y X -edge (M E (4)). However, we found 18 exact matchings containing the contact (Nup145C, Nup84) (ve in M E (1), one in M E (3), ve in M E (4) and seven in M E (5)). Since our previous study based on contact probabilities revealed that the 16 instances of Nup84 are connected to instances of Nup145C (see Fig. 4(A) and (C) in [START_REF] Dreyfus | Assessing the reconstruction of macro-molecular assemblies with toleranced models[END_REF]), selected instances of Nup84 or Nup145C actually appear in several exact matchings, reecting their poor positioning. Also, there are six exact matchings containing exactly Nup145C and Sec13 (M E (6)): since we observe the 16 instances of the contacts (Nup84, Nup145C), we deduce that these six instances of Sec13 and six instances of Nup84 make an extra contact. Four instances of Sec13 making no valid contact with Nup145C are evidenced (M E (8)): while the poor placement of instances of Sec13 had previously been established using contact probabilities [START_REF] Dreyfus | Assessing the reconstruction of macro-molecular assemblies with toleranced models[END_REF], the matchings M E (8) provide additional information on the missed contacts.

Finally, we found one exact matching with four protein types (Sec13, Nup145C, Nup120, Nup85) (M E (7)) whose support is an isolated copy, namely that also supporting the complete matching M E (1)).(bicolored node in Fig. 1(C, (b) and(c))) Y X -long-arm. There are 16 exact matchings containing exactly the Y X -long-arm (M E (9)): since our previous analysis revealed that there are 16 instances of the contact (Nup85, Nup120) (see Fig. 4 in [START_REF] Dreyfus | Assessing the reconstruction of macro-molecular assemblies with toleranced models[END_REF]), an extra contact exists between the 16 instances of Seh1 and Nup120. We also note that there are two exact matchings (M E (9)) having as support two dierent isolated copies. Nup120. We found 17 exact matchings with Nup120 (ve in M E (1), one in M E (5), ten in M E (10) and one in M E (11)). In other words, distinct instances of Nup120 are present in several exact matchings with dierent restrained templates.

Discussion

The notions of isolated copy and contact frequency introduced in [DDC12] improved the contact frequencies and subsequent analysis presented in [ADV + 07a, ADV + 07b], allowing in particular to make a quantitative assessment of pairwise contacts and protein complexes in large protein assembly reconstructed by data integration. Yet, connectivity analysis were beyond reach, a limitation circumvented by the graph-based tools presented in this paper.

Regarding the Y -complex, we were able to reconstruct the 16 existing copies of the Y -complex in the TOM of the NPC using depleted and complete matchings. However, at least half of the instances of the Y -complex are split in two pieces due to the disruption of the contact (Nup145C, Nup120). We also show using the exact matchings that all protein contacts observed in crystal structures of complexes of the Y -complex are present in our toleranced model. However, with the exception of an exact matching involving Y X -tail (M E (3)), no exact matching strictly contains the template of a crystallographic dimer or trimer. Instead, larger complexes are found as pairs of smaller exact matchings. In fact, the ve exact matchings M E (1) show that with a better positioning of Sec13 and Seh1, a exact matching involving the union of crystal based templates Nup120, Y X -long-arm and Y X -edge would be obtained.

From the modeling standpoint, the methods presented in this paper complement those developed in our initial work [START_REF] Dreyfus | Assessing the reconstruction of macro-molecular assemblies with toleranced models[END_REF], based on isolated copies. While isolated copies focus on the separability and the lifetime of complexes involving prescribed protein types, matchings aim at assessing the connectivity of protein instances involving the contacts of a template. Ideally, an isolated copy should support matchings, a failure of this property witnessing a situation where the connectivity of the copy diers radically from that of the template skeleton. Reciprocally, a matching whose instantiation does not belong to an isolated copy corresponds to a complex which is not well separated from the protein types dening the isolated copies.

All in all, our tools serve two purposes in the context of reconstruction by data integration. On the one hand, selecting the models which best comply with experimental data is important in a complex modeling pipeline, as such decisions are likely to improve the convergence of the optimization process. On the other hand, the ability to test any hypothesis, in terms of protein contacts, may orientate experiments so as to conrm or falsify putative 3D models. That is, we believe that our tools are particularly well suited to leverage reconstruction by data integration, by initiating a virtuous loop mixing modeling and experiments.

Figure 1 Signature of a matching between the skeleton graph G C of a complex C and a restricted template G t|C . The match between a protein instance of G C and a type of G t|C is materialized by an identical geometric shape (disk, square, triangle, hourglass

(p2, c2) (p4, c4) (p3, c3) (p2, c2) (p1, c1) A (p4, c4) (p3, c3) Matching Missing Contacts Extra Contacts A A (p3, c3) (p4, c4) (p2, c2) (p3, c3) (p4, c4) (p2, c2) (p1, c1) (c1, c3) (p1, p2) (p1, c1) (p2, c2) A Exact matching: A (p1, c1) ∅ ∅ (p2, c2)
Depleted matching: Complete matching:

GC G t|C GC G t|C GC G t|C A c1 c2 c3 c4 c1 c2 c3 c4 Matching Contacts ↔ p2 p3 c2 c3 , , ↔ p1 p4 c1 c4 , , ( ) ( )
↔ p2 p3 c2 c3 , , ( ) ( ) ↔ p3 p4 c3 c4 , , ( ) ( ) ↔ c1 c2 , ( ) p1 p2 , ( )
( ) ( ) c1 ∅ c3 V ∼ V - E ∼ E - E + Matching Matchings Signature Signature Signature Matching Protein Types Missing Protein Types Missing Contacts Extra Contacts V ∼ V - E ∼ E - E + Matching Protein Types Missing Protein Types Missing Contacts Extra Contacts V ∼ V - E ∼ E - E +

Matching Protein Types Missing Protein Types

Matching Contacts

Matching Contacts

p1 p2 p2 p4 , ( ) c5 p5 (p5, c5) (p5, c5) c3 c5 , ( )
↔ p4 p5 c4 c5 , , (
) ( ) The table is split into three sections, delimited by double vertical bars. The rst section gives the template skeleton, the tag of the depleted matching used in the text, and the number of depleted matchings with the same set of protein types. The second section provides the sizes of the sets involved in the signature of the matchings for each matching we also indicate the number of possible extra contacts that is the number of pairs of matching protein types minus the number of matching contacts. The third section supplies the min and max volume ratios computed over the protein complexes associated to the concerned matchingsthe volume ratio of a given complex being computed at the λ value at which this complex appears. (B) All complete matchings of protein complexes in the Hasse diagram with G t (Y ). (C) All exact matchings of protein complexes in the Hasse diagram with G t (Y ). between the labels of the two graphs, there is one MCES and there are two MCIS the circled graphs. Practically, the graph G 1 shall represent the skeleton graph G C of a complex associated to a node of the Hasse diagram of a toleranced model, while the graph G 2 shall represent the skeleton graph G t|C of a template. In this context, the aforementioned correspondence reads as follows: the label p i of G C is identical to the label c i of G t|C , that is, they represent the same protein type.

p2 p3 p4 p1 ↔ p3 p4 c3 c4 , , ( ) ( )
p3 c3 p1 p2 p3 p4 V -= ∅ and (E -= ∅ or E + = ∅) (p1, c1) (p3, c3) A ′ A ′ (p1, c1) (p3, c3) c2 ↔ c1 c3 , ( ) p1 p3 , ( )
∅ ∅ V -= ∅ and (E -= ∅ or E + = ∅) V -= ∅ and (E -= ∅ and E + = ∅) p1 p3 c1 c2 p2 (A) (B) (C) Inria
Template; tag # V ∼ (sub-complexes) | V -| | E ∼ | | E -| min | E + | max | E + | min V λ max V λ G t (Y );M D (1) 2 4 2 0 1/1 1/

  matchings. To maximize the number of common contacts between the skeletons of complexes C of the Hasse diagram and a given restricted template G t|C , we carry out MCES calculation as follows. First, for each complex C which is as root of the Hasse diagram, we compute the MCES between G C and G t|C . Second, let A be a matching returned by the MCES calculation. We search in the Hasse diagram the ancestor D of C involving the protein instances and contacts of C matched by A, and which minimizes the number of extra contacts. Exact and Perfect matchings. An exact matching associated to a node C of a Hasse diagram is maximal provided that there does not exist in the Hasse diagram any exact matching for a successor of C. Such complexes are easily obtained from the matchings provided by a MCIS calculation between the graphs G C and G t|C in each node of the Hasse diagram.

Figure 2 Figure 3

 23 Figure2Analysis of the Y -complex in the TOM of the NPC: Hasse diagram, isolated copies and matchings. (A) Pairwise contacts between protein instances of the Y -complex, adapted from[BLS + 08]; the template skeleton graph G t (Y ) consists of nodes (colored blobs), connected by edges (black lines). The solved crystal structures of four Y -complex sub-complexes are also shown: the Y X -short-arm [BLS + 08], Nup120 [SMD + 09], the Y X -edge [NHD + 09] and the Y X -tail[START_REF] Whittle | Architectural nucleoporins Nup157/170 and Nup133 are structurally related and descend from a second ancestral element[END_REF]. (B) TOM of the NPC at λ = 0 and λ = 1 restricted to the seven protein types of the Y -complex. An isolated copy of the Y -complex, involving one instance of each type, is colored on both pictures. Note that when λ increases, protein complexes (the grey domains) merge. (C) Hasse diagram of the Y -complex in the whole NPC, the three columns respectively presenting depleted, complete and exact matchings. The rst row displays all the nodes hosting matchings of a given type (cyan for depleted, purple for complete, and dark blue for exact) accompanied by the number of associated matchings, except for the exact matchings where only nodes with multiplicity at least two are decorated to avoid cluttering. An isolated copy of the Y -complex is represented by a green node, except when it hosts a matching, in which case it is also circled by the color associated to the matching (purple for complete and blue for exact). The orange nodes correspond to the supports of the matchings singled out by the dashed arrow on the second row, each support being represented by colored balls. The edges representing contacts in the support are depicted with the conventions of Fig.1The last row presents the types and the contacts of the template with the same conventions. As discussed in section 2.4, note that the same node of the Hasse diagram may host several matchings e.g. a depleted one (C,a) and an exact one (C,c).(B) (A)

  [ADV + 07b] (or possibly 32 [DMS + 08]) copies within the NPC remains under controversy with three competing models: the rst one supports the presence of two closed rings containing each eight copies of the Y -complex arranged in a head-to-tail manner [ADV + 07b, SMD + 09, M. 11]; in the second one (lattice model), the two sets of eights copies display a vertical head-to-head orientation [BLS + 08, BS12]; nally a fence-like arrangement based on the organization of Seh1-Nup85 as hetero-octamer was proposed [DMS + 08]. While this question is still under debate, the interfaces i.e. the pairwise contacts reported in [FMPS + 12] are incompatible with the third model.

  ). For nodes, bold contours indicate matching protein types, while dashed contours indicate missing protein types. For edges, bold lines indicate matching contacts, dashed lines indicate missing contacts, and dotted lines indicate extra contacts. Note that the adjectives matching/missing/extra qualify G C w.r.t. G t|C . (A) Depleted matching: a Maximal Common Edge Sub-graph calculation yields a matching with at least one missing protein type, and missing contacts (dotted lines) and/or extra contacts (dashed lines). (B) Complete matching: a Maximal Common Edge Sub-graph calculation yields a matching with no missing protein type. (C) Exact matching: a Maximal Common Induced Sub-graph calculation yields one or more matchings without any missing or extra edge.

  Computing matchings of two graphs G 1 and G 2 is tantamount to computing maximal cliques[START_REF] Cazals | An algorithm for reporting maximal c-cliques[END_REF], and of particular interests are the matchings associated to the so-called Maximal Common Induced Sub-graph (MCIS) and Maximal Common Edge Sub-graph (MCES) of G 1 and G 2 .These notions are illustrated on the Supplemental Figure4. Notice in particular that a MCES or MCIS calculation yields in general several matchings. Comparing graphs with matchings: illustration of the Maximal Common Edge Subgraph (MCES) and Maximal Common Induced Sub-graph (MCIS) constructions. Top. Two labelled graphs G 1 and G 2 . Bottom Left. The 6 MCES of G 1 and G 2 Bottom Right.: The 12 MCIS of G 1 and G 2 . If we impose a correspondence, e.g. ((p 1 ↔ c 1 ), (p 2 ↔ c 2 ), (p 3 ↔ c 3 ))

	6 Supplement Figure 4
	(A)		Depleted matchings
							1	4.49	4.71
	G t (Y );M D (2) 8	3	3	0	3/3	3/3	4.49	5.65
	G t (Y );M D (3) 10	4	2	0	1/1	1/1	1.17	5.83
	G t (Y );M D (4) 2	1	5	0	2/10	2/10	3.68	4.56
	6.1	Graph theory
	(B)	Complete matchings
	Template; tag # V ) 4	6	0	4/15	7/15	1.00	4.95
	(C)		Exact matchings
		) 5			3	1.02	3.42
		G t (Y );M E (2) 15			5	0.77	0.89
		G t (Y );M E (3) 1			4	0.86	0.86
		G t (Y );M E (4) 5			4	0.78	0.86
		G t (Y );M E (5) 7			5	0.81	0.86
		G t (Y );M E (6) 6			5	0.80	0.84
		G t (Y );M E (7) 1			3	1.05	1.05
		G t (Y );M E (8) 4			6	0.54	0.63
		G t (Y );M E (9) 16			5	0.77	1.27
		G t (Y );M E (10) 10			5	0.88	0.91		Inria
		G t (Y );M E (11) 1			4	2.15	2.15

Template; tag # V ∼ (sub-complexes) | V -| min V λ max V λ G t (Y );M E (1∼ (sub-complexes) | E ∼ | | E -| min | E + | max | E + | min V λ max V λ G t (Y );M C (1

RR n°8118


Alban Gaignard

Johan Montagnat

Catherine Faron Zucker

Olivier Corby

Semantic Federation of Distributed Neurodata

Neurodata repositories federation is increasingly needed to implement multi-centric studies. Data federation is difficult due to the heterogeneous nature of distributed data repositories and the technical difficulties faced in addressing simultaneously multiple data sources. This paper describes a data federation system based on a semantic mediation layer and an advanced distributed query engine able to interface to multiple heterogeneous neurodata sources. Both performance and usability indicators are shown, demonstrating the soundness of the approach and its practical feasibility.

Introduction

Computational neurosciences are highly dependent on the availability of large neurological datasets. An increasing effort has been invested in distributed computing infrastructures to face the challenges raised by modern multi-centric neuroscience studies [START_REF] Geddes | The Challenges of Developing a Collaborative Data and Compute Grid for Neurosciences[END_REF][START_REF] Helmer | Enabling collaborative research using the Biomedical Informatics Research Network (BIRN)[END_REF][START_REF] Anjum | Reusable Services from the neuGRID Project for Grid-Based Health Applications[END_REF]. In particular, distributed neurodata federation is considered to harness the large neurodata resources available [START_REF] Barillot | Federating Distributed and Heterogeneous Information Sources in Neuroimaging: The NeuroBase Project[END_REF][START_REF] Weiner | The Alzheimer?s Disease Neuroimaging Initiative: A review of papers published since its inception[END_REF][START_REF] Michel | Grid-wide neuroimaging data federation in the context of the NeuroLOG project[END_REF]. Federation of heterogeneous data sources is a complex problem due to the need to align the different data models used, and the lack of tools to efficiently query and process distributed databases. The Semantic Web community has developed methodologies and tools to clearly define the semantics of data using models and computerinterpretable metadata. This paper describes how these approaches can be applied to neurodata alignment, and introduce new methods to integrate legacy neurodata sources in a federated platform.

An approach often considered to deliver federated data repositories is data warehousing which consists in statically importing all data sources in a centralized repository after semantic alignment. Although simple, this solution has many drawbacks such as the need to transform legacy data entities to different representations, the scalability of the centralized repository, the central point of failure thus created, etc. When considering medical data, it is often even not possible to create a central data repository for legal and ethical reasons. The alternative solution studied in this paper is a dynamic distributed data federation mechanism which aligns the data models and the query capability of the heterogeneous repositories to deliver a unified view over the complete data set. This approach pushes queries to the distributed data sources and gathers results. From the client point of view, distributed data sources are thus virtually integrated as if a single data source was queried. It raises new issues such as the need for expressing queries that can be mapped to multiple data sources, network communication overhead, coherency of distributed queries, and transforming data entities on-the-fly to different representations while preserving their semantics.

We developed the KGRAM distributed query system to align multiple neurodata sources semantically and map queries to the heterogeneous federation. System utilisability is considered by taking into account both the query language expressiveness and performance issues. KGRAM is generic in the sense that it does not require any prior knowledge on the data sources content, and robust in a distributed environment as it transparently adapts to topology changes caused by the addition or the removal of data sources.

Distributed data query engine

Different neurodata repositories generally use different data models and store heterogeneous data. The dynamic data federation approach addresses simultaneously the problems of data source heterogeneity and data distribution. It relies on a central federator, and a set of federated data providers. From a unique query, the federator is responsible for the coherent sub-querying of the federated data providers and for unifying all results found into a global result set. It avoids consistency and synchronization issues generally observed in data warehouses where data transformation is performed periodically.

A single main query language is needed to express federation-wide queries. The SPARQL3 language v1.1 is considered in this work as a highly expressive, versatile, and de facto standard semantic data query language. Semantic data is viewed as a collection of triple patterns formalized as (s, p, o), where a subject s is linked to an object o through a predicate p, and usually represented as RDF triples 4 . A collection of triples constitutes a knowledge graph. Semantic querying through SPARQL is equivalent to the matching of a graph-based query pattern into the complete knowledge graph.

More precisely, the SPARQL-based query engine KGRAM described below (i) transforms a graph-based semantic query into the target data sources query languages and (ii) combines the triple results to assemble the reply at runtime. To efficiently perform distributed queries, the engine implements several optimizations including query rewriting and intermediate results exploitation.

The KGRAM query engine

KGRAM stands for Knowledge Graph Abstract Machine [START_REF] Corby | The kgram abstract machine for knowledge graph querying[END_REF]. It is a versatile system aiming at representing, querying and reasoning over semantic data represented as Knowledge Graphs [START_REF] Corby | Querying the semantic web with corese search engine[END_REF]. It enables querying different data source models, provided that they are able to produce a graph view of their data, e.g. RDF but also XML or relational databases. For the sake of generality, KGRAM introduces a set of abstract operators manipulating abstract graph data structures (abstract Nodes and Edges forming abstract Graphs). Graphs are navigated through so-called Producers responsible for the iteration over their Nodes and Edges. For each data source kind, a specific Producer is needed that abstracts its representation to answer SPARQL queries by returning data represented as graph elements. Knowledge graphs are matched with queries through Matchers. Depending on their implementations, the comparison may consist in simple labels equality or it may take into account domain knowledge through class and property subsumption (RDS entailment) or eventually approximate matching based on semantic similarities. Finally, Filter operators are responsible for evaluating value constraints over knowledge graphs.

Distributed query processing

In KGRAM, the evaluation of SPARQL queries basically consists in searching for matching edges in a knowledge graph delivered by a Producer. To mashup linked data over distributed data sources, KGRAM introduces the notion of Metaproducer responsible for the enumeration of Nodes and Edges coming from several Producers interfaced to several data sources. All producers implement the same query interface, receiving the same messages from the Metaproducer and rewriting the input queries into native data source ones, to shield KGRAM core from data source heterogeneity. To handle distributed data repositories, we extended KGRAM implementation by providing a web service implementation of its Producer interface. Figure 1 illustrates the main elements involved in the semantic distributed query processing. The principle of the algorithm consists in iterating over each triple pattern forming the initial SPARQL query (line 1). For each triple pattern, all remote Producers are queried concurrently (line 3). The federator then waits for all federated endpoints to finish through a synchronization barrier (line 4). Results are finally accumulated for the current triple pattern (lines 5 and 6) and the next triple pattern iteration can be processed (line 1). To soften the synchronization barrier a pipelining strategy was implemented, in which a synchronized blocking queue allows the federator to post-process results as soon as they become available. Due to space constraints, the pipelining algorithms are not detailed.

Distributed query optimization strategies

In KGRAM, the query distribution principle consists in iterating over each triple pattern request occurring in the SPARQL query. Each triple pattern request is dynamically wrapped into a unitary SPARQL query and pushed to remote data sources. Resulting triples are returned back and accumulated into the KGRAM result graph. To enhance the efficiency of distributed query processing, a set of static and dynamic optimizations were implemented.

The filter pushing strategy consists in analyzing the initial SPARQL query to extract value constraints expressed in FILTER clauses. When iterating over each triple pattern request, each applicable value constraint is extracted from the initial FILTER and propagated as a new FILTER clause added to the triple pattern query. This reduces drastically the communication cost since it prevents the federator from transferring irrelevant results that would be finally filtered.

The same idea is exploited at query runtime through bind joins. The KGRAM query processor manages an index of already known mappings between variables and values, thus forming intermediate results. This cache is exploited at query runtime in order to dynamically replace triple pattern variables by their associated values in the queries pushed to federated endpoints. Similarly to the filter pushing strategy, bind joins reduce drastically the size of transferred results.

Relational data sources

In neurosciences, it is common that the underlying legacy environments rely on traditional relational databases. KGRAM comes with a default implementation of its Producer interface for RDF sources. To cope with relational sources, a specific Producer that rewrites triple patterns forming the initial SPARQL query into SQL queries is needed. Query results can then be mapped to the variables of the original SPARQL query to build result graph triples. A generic SQL Producer is out of scope of this paper. An ad-hoc Producer implementation was considered in the case of the NeuroLOG platform described below.

Experimentation in the NeuroLOG platform

The NeuroLOG platform [START_REF] Montagnat | NeuroLOG: a community-driven middleware design[END_REF] federates data and computational resources from collaborating neuroscience centers. The prime objective of NeuroLOG is to adapt non-invasively to the legacy environments deployed in each participating center, so that each site remains autonomous in the management of its internal resources and tools, while benefiting from the multi-centric medical studies support from the middleware. The platform is federating 5 neuroscience centers spread over France. On each site, the data source is composed of raw neuroradiology files, and description metadata linked to these files (information on image data acquisition, data content, neuropsychological tests associated to images, etc) [START_REF] Michel | Grid-wide neuroimaging data federation in the context of the NeuroLOG project[END_REF]. The source metadata is often represented and managed in relational databases for historical reasons.

Blue components in Figure 2 sketches the architecture of the NeuroLOG middleware. On each neuroscience site an independently managed legacy relational database is deployed. It is completed by a NeuroLOG middleware database. The multi-centric studies conducted by neuroscientists may be perceived under several facets, involving both the native relational data representation and a semantic data representation enabling richer queries. The DataFederator commercial tool 5 is used to dynamically federate relational data sources into a unified view. It can perform SQL queries that are distributed over all platform data sources. It includes both a mediation layer that aligns heterogeneous relational databases schemas, and rewrite SQL queries applying to the federated view to match the various source schemas. The data mediation semantic alignment is based on a domain ontology, called OntoNeuroLOG that was developed in the context of this project. A federated relational schema is derived from OntoNeuroLOG, serving as the federated view schema. In addition to this relational representation, a semantic representation of the same data sources was created to enable richer querying features delivered by Semantic Web query engines. A centralized approach was adopted, where all relational data sources are mapped to RDF triples (using the MetaMORPHOSES tool 6 ) and aggregated in a unique semantic repository. The NeuroLOG platform thus exposes a dual view of the federation metadata, enabling both dynamic SQL querying and static SPARQL querying. Although very flexible, this system is also confusing for end users due to the dual view of all data entities. The semantic repository is also subject to limitations of a static, centralized warehouse. To overcome these issues, the NeuroLOG platform was extended with the KGRAM query engine introduced in section 2.1 (see green components in Figure 2). A KGRAM remote producer was deployed on top of each site legacy database. This endpoint exposes the site data content in RDF through its Producer. Depending on the site deployment option, it either interfaces dynamically to the site native relational database (option 1 in Figure 2), or accesses an RDF repository representation of this legacy database (option 2 ) which is periodically regenerated using MetaMORPHOSES. Consequently, NeuroLOG's centralized RDF repository (crossed over in red in Figure 2) is not needed anymore. It is replaced by a completely dynamic semantic federation (all sites using 1 ), a distributed version periodically updated (all sites using option 2 ), or a mixture of both. This setting enables the unified querying of the RDF repositories and the platform legacy relational databases through the SPARQL language. It solves the central repository limitation, distributing the query load over the federation data servers. It proposes a single view over all data. The experiments reported below demonstrate the query expressiveness and the performance of the KGRAM engine. The NeuroLOG platform both provides a real use case for these experiments and serves as a performance measurement reference.

Collaborating site #1 Centralized semantic repository

NeuroLOG client

Experimental setup

Three query environments are compared. The relational federation only exposes heterogeneous relational databases, virtually integrated through the DataFederator commercial middleware. It corresponds to the seminal NeuroLOG platform deployment. Two other environments (semantic federations) expose heterogeneous data sources virtually integrated through the KGRAM framework. In the RDF semantic federation environment, all sites are configured with option 2 . It corresponds to a modification of the NeuroLOG platform where the central semantic repository is spread over all participating sites but native repositories are transformed to RDF before being accessed. In the RDF+SQL semantic federation environment, a mixture of RDF sources and SQL sources (dynamically accessed through 1 ) is used to evaluate a completely heterogeneous set up.

Figure 3 (top) illustrates a real clinical use case involving querying neurodata distributed over several centers. It aims at searching for datasets (acquired with Gadolinium contrast agent) associated to patients (join performed at line 4) in the context of multi-centric studies addressing the Multiple Sclerosis pathology. During the evaluation of this query, all types of medical images will be searched in order to match a "GADO" tag (indicating use of the Gadolinium contrast agent). But the evaluation of this query can be considerably enhanced by exploiting clinical knowledge represented in an RDFS vocabulary. Indeed Gadolinium is only used in the context of the MR modality. By exploiting this domain knowledge with KGRAM, the query time can be significantly reduced since all non-MR datasets are excluded. This results from the triple pattern (?dataset rdf:type dataset:MRDataset) added to the query which leads, under RDFS entailment, to less intermediate results to be transferred and thus an overall faster distributed query evaluation.

The bottom query from Figure 3 achieves the same clinical objective but makes use of SPARQL property path expressions. This language feature aims at representing paths between two resources by only specifying, in the form of patterns, the sequence of mandatory, optional, reverse, or multiple repetition of properties linking the resources together. It brings a high expressivity to SPARQL queries and it is particularly adapted in the context of graph-based querying. This kind of query cannot be easily expressed in SQL. It is thus difficult to implement it with traditional relational databases. As a full SPARQL 1.1 interpreter, compliant with property path expressions, KGRAM allows for performing this kind of graph-based information retrieval against SQL data sources, which would not have been possible wit traditional SQL query engines.

1 SELECT distinct ?patient ?study ?dataset ?dsName WHERE { 2 ?dataset linguistic-expression:has-for-name ?dsName .

3

?patient examination-subject:has-for-subject-identifier ?clinID .

4

?patient iec:is-referred-to-by ?dataset .

5

?study study:involves-as-patient ?patient .

6 FILTER (regex(?clinID, 'MS') && regex(?dsName, 'GADO')) } ?study study:involves-as-patient ?patient .

12 FILTER (regex(?clinID, 'MS') && regex(?dsName, 'GADO')) } Fig. 3. Top: sample SPARQL query Q1, aiming at retrieving patient, study and dataset information in the context of the Multiple Sclerosis disease. Bottom: SPARQL 1.1 property path expressions simplifying the previous query.

Qualitative evaluation

KGRAM implements the RDFS entailment regime (subsumption between classes or properties), and other inferences based on algebraic properties like the transitivity or symmetry of properties and inverse properties. It thus provides a richer query interface to legacy databases participating into the federation. In addition, in the context of collaborative platforms exposing legacy relational databases, we argue that the design of queries is more intuitive through knowledge-based languages such as SPARQL than through traditional relational languages such as SQL. Indeed, the navigation through links between entities is explicit in SPARQL while it is implicit in SQL and generally requires for intermediate joins. The following SQL query corresponds to the SPARQL query of Figure 3 Whereas joins are naturally expressed in the SPARQL query (line 4 of Figure 3), it is not the case in SQL since a join table may be needed (Rel Subject Study table, line 3) and must be explicit (line 4, 5 and 6). This definitely complicates the query design, generally considered as complex, error-prone, and time consuming.

Quantitative evaluation

The distributed query processing times of the relational federation (using DataFederator) and both semantic federations (RDF and RDF+SQL) are compared using KGRAM through two queries. Query Q1 corresponds to Figure 3 and query Q2 searches for datasets acquired through the T2-weighted MRI modality. Q2 leads to only 5 results and is thus, a very selective query. To be robust against variability observed in real distributed systems, results are averaged over three query runs. The average query execution time ± one standard deviation is displayed in the following table showing that for Q1, leading to 336 remote invocations, the query times are lower with the optimized SQL federation engine DataFederator than with the semantic federation, but it remains in the same order of magnitude. For very selective queries such as Q2, we observe comparable query times for all environments:

Semantic federation: RDF or RDF+SQL Relational federation Q1 (s) 6.13 ± 0.05 11.76 ± 0.05 3.03 ± 0.25 Q2 (s) 0.60 ± 0.03 1.53 ± 0.14 1.52 ± 0.62

Concluding remarks

Transparent data federation approaches generally address performance issues. For instance, DARQ [START_REF] Quilitz | Querying distributed rdf data sources with sparql[END_REF], SPLENDID [START_REF] Görlitz | SPLENDID: SPARQL Endpoint Federation Exploiting VOID Descriptions[END_REF] or FedX [START_REF] Schwarte | Fedx: optimization techniques for federated query processing on linked data[END_REF] propose a set of static and dynamic optimizations. KGRAM implements similar strategies to exploit value constraints at query rewriting time and to enhance the querying at runtime through bind joins. Moreover, in line with FedX, KGRAM also exploits the parallelism of both distributed data sources and modern multi-core CPUs with a multithreaded implementation. There remain other optimization opportunities for KGRAM such as data sources selection and subsequent query planning techniques, but to the best of our knowledge, none of the state-of-the art transparent federating approaches address both the issues of efficient and heterogeneous distributed querying. The strength of the KGRAM model is to provide an extensible framework allowing to efficiently and dynamically access to multiple query sources internally using different data representations. In the future, the query rewriting capability of KGRAM is also thought to be a mean to implement fine-grained access control to data sources. KGRAM eases the federation of distributed and heterogeneous neurodata repositories. Concrete examples in the context of the NeuroLOG platform, mixing both semantic and relational repositories, demonstrate the feasibility and the efficiency of this approach. Beyond performance, the query environment is enriched by the high expressivity of semantic query language. End-users gain from using knowledge with a well-defined semantics. Moreover, through an ontology and its associated entailments, the querying process can exploit domain knowledge to implement smart queries. The current implementation of KGRAM enables read-only access to data sources. Modifying heterogeneous distributed data sources is a challenging problem that we intend to tackle in the future.

Fig. 1 .Algorithm 1 :

 11 Fig. 1. KGRAM distributed query architecture

Fig. 2 .

 2 Fig. 2. Data management layer of the NeuroLOG platform

7 8 9 ? 10 ?

 7910 SELECT distinct ?patient ?study ?dsName WHERE { patient iec:is-referred-to-by/linguistic-exp:has-for-name ?dsName . patient examination-subject:has-for-subject-identifier ?clinID .

11

 11

: 1

 1 SELECT Subject.subject id, Subject.subject common identifier, Dataset.name 2 FROM Study, Subject, Dataset, Rel Subject Study AND 3 WHERE Rel Subject Study.Subject subject id = Subject.subject id AND

	4	Rel Subject Study.Study study id = Study.study id AND
	5	Dataset.Subject subject id = Subject.subject id AND
	6	Subject.subject common identifier LIKE '%MS%' AND Dataset.name LIKE '%GADO%'

SPARQL: http://www.w3.org/TR/rdf-sparql-query/

RDF: http://www.w3.org/TR/rdf-primer/

Data Federator: http://www.sap.com/solutions/sapbusinessobjects/large/ information-management/data-integration

MetaMORPHOSES: http://metamorphoses.sourceforge.net

Acknowledgments

This work was partly funded by the French National Agency for Research under grants ANR-06-TLOG-024 (NeuroLOG project).