S Akbari
email: sakbari@sharif.edu

Y Bagheri

S Saadat Akhtar

Some Bounds on the Energy of Signed Complete Bipartite Graphs * †

Keywords: Signed graph, Eigenvalues, Complete Bipartite Graphs, Energy. † 2010 Mathematics Subject Classification: 05C50, 05C22, 05C90

A signed graph G σ is a pair (G, σ), where G is a graph, and σ :

is the adjacency matrix of K σ m,n . In this paper we show that for every sign function σ,

) is the energy of K σ m,n . Also it is proved that the equality holds for the upper bound if there exists a Hadamard matrix of order n for which B is an m by n submatrix of H. Also if the equality holds, then every two distinct rows of B are orthogonal. We prove that for the lower bound the equality holds if and only if K σ m,n is switching equivalent to Km,n.

Introduction

Let A be a real symmetric matrix of order n and λ 1 ≥ • • • ≥ λ n be all eigenvalues of A. The energy of A is defined by

E(A) = ∑ n i=1 |λ i |. A signed graph G σ is a pair (G, σ),
where G is a graph, and σ : E(G) -→ {-1, +1} is a function. We call σ the sign function of G σ . The adjacency matrix, A(G σ ) corresponding to G σ on the vertex set V = {v 1 , . . . , v n } is an n × n matrix whose entries are

(A(G σ )) ij =        1 if v i is adjacent to v j with positive sign. 0 if v i is not adjacent to v j .
-1 if v i is adjacent to v j with negative sign.

The spectrum of G σ is the set of all eigenvalues of the adjacency matrix corresponding to the signed graph G σ with multiplicities and denoted by Spec(G σ ) = {λ m1 1 , . . . , λ m k k }, where m i is the multiplicity of λ i . The energy of G σ denoted by E(G σ ), is the energy of the adjacency matrix of G σ . A switching of a signed graph G σ at a vertex v is changing the sign of each edge incident with v. It is easy to see that a switching at a vertex v implies a new sign function σ ′ and new signed graph G σ ′ which is cospectral with G σ . We say that G σ ′ is a switching of G σ if it is obtained from G σ by finitely many switchings at some vertices of G σ . Switching defines an equivalence relation on the set of all signed graphs with underlying graph G. It is easy to check that if G has m edges, n vertices and c components, then there are 2 m-n+c distinct equivalence classes. It is immediately implies that the signed cycles have just two classes and it is not hard to see that every class has at most one negative edge. We denote the cycle of order n, by C n . The sign of a cycle in a signed graph is the product of the signs of its edges. Thus a cycle is positive if and only if it contains an even number of negative edges. A signed graph is said to be balanced if all of its cycles are positive otherwise unbalanced. In this paper K m,n denotes the complete bipartite graph with part sizes m and n. We denote a signed complete bipartite graph with underlying graph of K m,n by K σ m,n . A conference matrix is a square matrix C of order n with zero diagonal, such that CC t = (n -1)I. If C is the adjacency matrix of a signed graph, then the signed graph is called a conference graph. A Hadamard matrix H is an n by n matrix whose entries are either -1 or +1 and whose distinct rows are mutually orthogonal. It implies that HH t = H t H = nI. Haemers in [START_REF] Haemers | Seidel switching and graph energy[END_REF] provided some bounds for the energy of signed complete graphs of order n and proved that E(K σ n ) ≤ n √ n -1 and the equality holds if and only if K σ n is a conference graph. Also he conjectured that E(K σ n ) ≥ 2n -2. This conjecture was proved for n ≤ 12 but it is still open in general. For more information on the energy of graphs, see [START_REF] Akbari | Edge addition, singular values, and energy of graphs and matrices[END_REF], [START_REF] Bhat | On equienergetic signed graphs[END_REF], [START_REF] Sh | Lower bounds for the energy of (bipartite) graphs[END_REF], [START_REF] Chen | Bounds on the matching energy of unicyclic odd-cycle graphs[END_REF], [START_REF] Ch | On energy of graphs[END_REF], [START_REF] Gutman | Resolvent energy of graphs[END_REF], [START_REF] Huang | On comparison between Laplacian-energy-like invariant and Kirchhoff index of graphs[END_REF], [START_REF] Kaya | On the Co-PI spectral radius and the Co-PI energy of graphs[END_REF], [START_REF] Ma | On the minimal energy of tetracyclic graphs[END_REF], [START_REF] Nayak | Spectra and energy of signed graphs[END_REF], [START_REF] Oboudi | Energy and seidel energy of graphs[END_REF], [START_REF] Vaidya | Some New Results on Energy of Graphs[END_REF] and [START_REF] Zhang | On the energy of trees[END_REF]. In this paper we would like to obtain some results for the energy of signed complete bipartite graphs.

Bounds for the Energy of Signed Complete Bipartite Graphs

In this section we wish to obtain a sharp upper bound for the energy of signed complete bipartite graphs.

Theorem 1. If m ≤ n are two positive integers and

A = [ 0 B B t 0 ]
is the adjacency matrix of K σ m,n for an arbitrary sign function σ, then

E(K σ m,n ) ≤ 2m √ n.
Moreover, if there exists a Hadamard matrix of order n, then there is a sign function

σ for K m,n such that E(K σ m,n ) = 2m √ n.
If the equality holds, then every two distinct rows of B are orthogonal.

Proof. Suppose that

A = [ 0 B B t 0 ] ,
is the adjacency matrix of K σ m,n , where B is a (-1, 1)-matrix of size m × n. Let A have the eigenvalues

λ 1 ≥ • • • ≥ λ m+n . Thus the eigenvalues of A 2 are λ 2 1 ≥ • • • ≥ λ 2 m+n . Since A 2 = [ BB t 0 0 B t B ] ,
and all non-zero eigenvalues of BB t and B t B are the same (see [16]), the eigenvalues of BB t have the following form,

λ 2 i1 ≥ λ 2 i2 ≥ • • • ≥ λ 2 im . Now, tr(BB t ) = ∑ m j=1 λ 2 ij .
On the other hand, 2mn = tr(A 2 ) = ∑ m+n i=1 λ 2 i = 2tr(BB t ). It implies that tr(BB t ) = mn. By Cauchy-Schwartz Inequality we have,

( ∑ m j=1 |λ ij |) 2 ≤ ( ∑ m j=1 λ 2 ij )( ∑ m j=1 1) = (mn)m,
and so (

E(K σ m,n ) 2 ) 2 ≤ m 2 n. This yields that E(K σ m,n ) ≤ 2m √ n.
Let H be a Hadamard matrix of order n and B be a submatrix of H of size m × n. Clearly,

A 2 = [ nI m 0 0 B t B ]
.

It

Lemma 1.[2]

The eigenvalues of signed C n are

λ k = { 2cos 2kπ n if C n is balanced. 2cos (2k+1)π n if C n is unbalanced. (1)
3 Proof. By a suitable labeling of vertices, the adjacency matrix of K σ m,n has the following form:

for k = 1, . . . ,
A(K σ m,n ) = [ 0 B B t 0 ] .
Thus we have

(A(K σ m,n )) 2 = [ BB t 0 0 B t B ] .
The √ mn, 0, . . . , 0, -√ mn.

Suppose that K σ m,n contains a negative cycle. By switching one can assume that this cycle has exactly one negative edge. First we show that there exists a negative 4-cycle. To see this let v 1 , v 2 , . . . , v r be a negative cycle such that v 1 v 2 is negative. If v 3 v r is positive, then v 1 v 2 v 3 v r is a negative 4-cycle, as desired. So v 3 v r is negative. Similarly, v 4 v r-1 is a negative edge. By continuing this procedure we find that v r 2 v r 2 +1 v r 2 +2 v r 2 +3 is a negative 4-cycle, as desired. The eigenvalues of a negative 4-cycle are: -√ 2, -√ 2, √ 2, √ 2. So by Interlacing Theorem, (see [START_REF] Brouwer | Spectra of Graphs[END_REF]), K σ m,n has at least two positive eigenvalues, a contradiction. Thus every cycle of K σ m,n is positive. So by Theorem 2, K σ m,n is switching equivalent of K m,n . Other side of theorem is clear and the proof is complete.□

  n. Two signed graphs G σ1 and G σ2 are switching equivalent if and only if they have the same set of unbalanced cycles. Subsequently, G σ is switching equivalent to G if and only if all of its cycles are balanced.

	Theorem 2.[14] Now, we are ready to prove the following theorem.
	Theorem 3. Let m ≤ n be two positive integers. Then for any sign function σ, E(K σ m,n ) ≥ 2 √ mn,
	and the equality holds if and only if K σ m,n is the switching equivalent to K m,n .

  non-zero eigenvalues of BB t and B t B are the same. Obviously, every eigenvalue of B t B is non-negative. Assume that λ 1 ≥ • • • ≥ λ m are the first largest eigenvalues of B t B. Thus

	A(K σ m,n ) has at least n -m eigenvalues 0. Hence we find that E(K σ m,n ) = 2 ( ∑ m i=1 √ λ i ) 2 ≥ ∑ m i=1 λ ∑ m+n i=1 λ 2 i = 2mn and ∑ m+n i=1 λ i = 0, the eigenvalues of ∑ m i=1 √ λ i . Obviously,
	K σ m,n are as follows:

i = tr(B t B) = mn. This implies that E(K σ m,n ) ≥ 2 √ mn. Now, if B t B

has at least two positive eigenvalues, then clearly, E(K σ m,n ) > 2 √ mn. Therefore the multiplicity of zero in Spec(E(K σ m,n )) is m + n -2. Since


Rawdha Dekhili

Thomas H Kauffmann

Hassen Aroui

Marc D Fontana

Raman spectra in LiH 2 PO 4 and KLi(H 2 PO 4 ) 2 : Mode assignment

Keywords: crystal, vibrational modes, mode assignment, phosphate compounds, thermal behavior

We report and analyze Raman spectra recorded on crystals of LiH 2 PO 4 (LDP) and KLi(H 2 PO 4 ) 2 (KLDP). We provide a new and complete assignment of Raman lines in both crystals from their behavior as function of temperature. Among internal vibrations we discern the modes within PO 4 tetrahedra, the modes related to Li-O bonds and those due to the O-H vibrations. In the wavenumber range between 300 and 600 cm -1 the lines associated with O-P-O or Li-O show different temperature dependencies. The bands of PO 4 are red-shifted with increasing temperature according to thermal dilatation, while the positions related to Li-O are temperature independent.

Introduction

Phosphate materials MH 2 PO 4 (M= K, Li, Rb, NH 4 , Cs) have a current interest for both basic science and applied research. Among this family, potassium dihydrogen phosphate (KH 2 PO 4 KDP), ammonium dihydrogen phosphate (NH 4 H 2 PO 4 ADP) and potassium titanium phosphate (KTiOPO 4 KTP) are widely investigated for their interest in piezoelectricity, ferroelectricity and nonlinear optics. 1,2,3 LiH 2 PO 4 (LDP) and KLi(H 2 PO 4 ) 2 (KLDP) were studied only recently. 4,5 The peculiarity in the structure of both materials is the presence of tetrahedra LiO 4 when compared to other crystals of MH 2 PO 4 family. In LDP and KLDP the structure constitutes on PO 4 and LiO 4 tetrahedra which are bonded together by the oxygen atoms to form a tridimensional network. 6 LDP has an orthorhombic structure while KLDP crystallizes in the P2 1 /c (C 2h ) space group of the monoclinic system.

It is therefore of particular interest to investigate the vibrational modes in LDP and KLDP in relation with the peculiarities of their structure.

In any phosphate material, PO 4 3-group shows four fundamental modes: Modes ν 1 and ν 3 corresponding to elongations of the P-O bonds and the ν 2 and ν 4 modes corresponding to angular deformation (O-P-O). All these modes are Raman active: ν 1 and ν 3 are lying in wavenumber range 900-1100 cm -1 and ν 2 and ν 4 in the domain 400-600 cm -1 . 7,8 The wavenumbers of internal vibration modes of LiO 4 groups are expected in the spectral range 390-500 cm -1 . 9 As a consequence, the LiO 4 vibrational modes may occur within the same wavenumber range as those of ν 2 (PO 4 ) and ν 4 (PO 4 ). Since LiO 4 group shares oxygen atoms with two neighbouring PO 4 , the decoupling between the vibrational modes of the two entities is not so easy. Lee et al. 10 have reported on Raman data in LDP recorded between 70 and 300 K. Within their attribution of the lines between 390 and 500 cm -1 , they did not elucidate if they are due to PO 4 or LiO 4 . 10 Furthermore these authors considered the bands between 1053 and 1222 cm -1 as due to PO 4 bending or OH vibrations. More recently, within a similar Raman investigation, Rhimi et al. attributed all Raman bands in the range 400-470 cm -1 to vibrations of ν 1 (LiO 4 ) from data recorded at room temperature. 5 Regarding LDP the aim of our study is to attempt to solve these ambiguities in the Raman line assignment from new studies as function of temperature from 30 to 176°C. The second crystal, KLDP was still less investigated than LDP and only recently Rhimi et al., 5 reported on X ray diffraction, Raman and IR data. They attributed the vibrational modes to H 2 PO 4 , LiO 4 entities, or O-H bond, according to different wavenumber regions, from the comparison with spectra in LDP and KDP.

We propose here a new and complete assignment of the main Raman lines of LDP and KLDP. For this we show that the groups LiO 4 and PO 4 differ in their behavior as function of temperature. For internal PO 4 modes we use the mode positions of the free H 2 PO 4 and we compare the spectra in both crystals as well. Finally we briefly analyze OH vibrations.

Preparation and structural properties of LDP and KLDP

The LDP and KLDP crystals were grown by slow evaporation solution growing technique at ambient temperature. The crystals were prepared from highly pure reagents Li 2 CO 3 (purity of 99.99%) and K 2 CO 3 (purity 99.99 %). These salts were dissolved in phosphoric acid (purity of 95%) and ultra-pure water according to the following reactions for LDP and KLDP respectively:

Li The resulting solutions were stirred for 12 hours. After they have been deposited in Petri dishes. Transparent and good quality crystals of KLDP and LDP were collected after a few days. The LDP and KLDP samples have the following dimensions 1.5 x 1.2 x 0.5 cm 3 and 1.2 x 0.9 x 0.5 cm 3 respectively. LiH 2 PO 4 has the orthorhombic structure at room temperature with the space group Pna2 1 -C 2 9v (Z = 4) and lattice parameters a = 6.241 Å, b =7.643 Å, c = 6.870 Å. 6 It contains two different types of tetrahedra LiO 4 and PO 4 as shown in Fig. 1. The structure presents two different hydrogen bridges O-H 1 ---O and O-H 2 ---O, with a length of 2.684 Å and 2.564 Å respectively. 4 The structure contains PO 4 and LiO 4 tetrahedra interconnected by oxygen atoms, to form a tridimensional network (see Fig. 1). Moreover four hydrogen bonds consolidate the structure.

Raman data and lines assignment

Raman spectra have been recorded in the back-scattering geometry with LabRAM HR Evolution (Horiba) under confocal Raman microscope. The system has a spectral resolution of 1 cm -1 using a 1800 grooves per millimeter grating and is equipped with an ultra-low wavenumber module to detect wavenumbers down to 5 cm -1 . A 532 nm diode laser light was focused on the sample with a 50x objective (Olympus). Raman spectra were obtained in a wide spectral range 5-3500 cm -1 as a function of temperature using a HFS temperature stage (Linkam).

Measurements were performed from 30 up to 176°C on a polycrystalline LDP sample and from 30 up to 120°C on a KLDP single crystal. These temperature ranges have been chosen below the first structural transformations occurring at about 176°C in LDP 11 and 125°C in KLDP. Thus nonmonotonous changes in Raman lines caused by structural transitions were not considered here.

For aiming to attribute Raman lines to various vibrational modes in both crystals, at first we look at the thermal behavior of the spectra in LDP, in order to discern between PO 4 and LiO 4 groups, and then we consider the positions of Raman lines of the free tetrahedra hydrogenated phosphate anion H 2 PO 4 -for the assignment of internal modes of PO 4 entities. At last the assignment of peaks in KLDP is deduced from both the analysis of their own temperature dependence and the comparison with LDP. It is reminded that the free anion H 2 PO 4 -has the symmetry C 2v , and possesses 9 modes of vibration. [START_REF] Nakamato | Infrared and Raman Spectra of Inorganic and Coordination Compounds[END_REF] Likewise in PO 4 , the main vibrations are labeled ν 1 for the symmetric stretching mode P(OH) 2 , ν 2 for the in-plane bending vibration PO 2 , ν 3 for the asymmetric stretching vibration P(OH) 2 and ν 4 for the out-of-plane bending mode PO 2 . These modes are shown in Fig. S1 (Supporting Information).

The vibrational modes of H 2 PO 4 -in solution are located respectively at 886 cm -1 (ν 1 ), 356 cm -1 (ν 2 ), 1085 cm -1 (ν 3 ) and 495 cm -1 (ν 4 ). [START_REF] Fontana | [END_REF] The peak positions of the modes are influenced by the environment of the molecular groups and therefore they may shift. The Raman spectra recorded at room temperature in both crystals are shown in Fig. 2. Both spectra present some similarities according to the wavenumber range, so that they can be compared each to the other. Furthermore we can note that, in this range, the number of lines in KLDP is much larger than in LDP. This can reflect the lower symmetry in KLDP.

We can therefore distinguish different wavenumber ranges: below 300 cm -1 are lying the bands generally associated to external modes, between 300 and 600 cm -1 two groups of lines, and between 800 and 1100 cm -1 intense and narrow peaks. Above 1200 cm -1 (not shown in Fig. 2) are located very weak bands corresponding to OH vibrations.

Below we describe and analyze the results according to these successive wavenumber ranges.

The bands below 300 cm -1 in the vibrational spectra are generally attributed to external modes or lattice modes and correspond to freedom degrees of translations and rotations of the isolated entities. Here the external modes (reported in the insert of Fig. 2) result from the relative translations and librations of the two groups LiO 4 and PO 4 . As shown in Fig. 3 the Raman spectrum of LDP displays 4 relatively distinct bands between 300 and 440 cm -1 . The lines lying at 328 cm -1 , 358 cm -1 and 375 cm -1 (positions of the intensity maximum at room temperature) exhibit a clear down-shift on heating, while their intensity continuously decreases and their linewidth slightly increases. This behavior is expected regarding the thermal dilatation and increasing anharmonicity. The chemical bonds are expected to increase on heating so that the force constant diminishes and consequently the wavenumber of the vibration decreases.

These three lines are assigned to the ν 2 internal vibrations inside the group PO 4 . Indeed they are close to the wavenumber of the free molecular group H 2 PO 4 (356 cm -1 ) and it is well known that the wavenumber of a vibrational mode can be shifted due to the surrounding of the molecular group. By contrast of these 3 lines ν 2 -PO 4 , the band located at 399 cm -1 shows a remarkably different behavior since its position does not shift and its profile is nearly unchanged with temperature. Due to these differences this line is assumed to arise from internal vibration of LiO 4 group.

When analyzing the three bands of LDP in the range 450-600 cm -1 (Fig. 3) we observe in their temperature behaviors some analogies with the lower wavenumber range, described above. Therefore we propose a similar and consistent assignment of the peaks. On the one hand, the lines located at 491 cm -1 and 556 cm -1 (at room temperature) present on heating a down-shift of the maximum position and consequently are attributed to ν 4 -PO 4 vibrations (close to the wavenumber 495 cm -1 in the free molecular group H 2 PO 4 ). On the other hand, the peak at 520 cm -1 is unaffected by the temperature change and is consequently assigned to internal mode of LiO 4 group. This attribution is supported by the observation of Li-O vibrations in other compounds, such as Li 2 CO 3 , in which Hase et al. assigned 4 vibrational modes between 375 and 500 cm -1 . 14 We now turn to the analysis of the Raman spectra recorded in KLDP, also shown in Fig. 3. At first, if we compare these data with spectrum on LDP at room temperature, we can note that the number of lines is larger in KLDP. This can be due to the presence of two different H 2 PO 4 in KLDP. Furthermore the two groups of lines within 300-600 cm -1 are shifted with respect of LDP. For the assignment of Raman lines in KLDP, we can use the same approach as above in LDP. The bands lying around 338, 344, 370, 427 and 454 cm -1 in the first group, and 534 and 574 cm -1 in the second group, are slightly shifted towards lower wavenumber on heating, and are attributed to PO 4 (ν 2 -PO 4 for the first group and ν 4 -PO 4 for the second group). The lines located at 398 and 513 cm -1 have positions unchanged with temperature, and are therefore assumed to derive from LiO 4 internal vibrations. It is remarkable that these peaks are lying at nearly the same positions as in LDP (at 399 and 520 cm -1 respectively). This reinforces our interpretation within the attribution of these lines to LiO 4 in both crystals.

The thermal independence of the line positions attributed to LiO 4 can be explained by the relative rigidity of this molecular group since it is linked to other LiO 4 along chains (see Fig. 1). Moreover the fact that the internal vibrations of Li-O appear at nearly the same positions in LDP and KLDP as well shows that these vibrations are relatively unaffected by the environment. On contrary the positions of the vibrations ν 2 -PO 4 and ν 4 -PO 4 are changed from one crystal to the other, and are therefore sensitive to the environment and the temperature as well. Now we look at the spectra in the range 850-1100 cm -1 , for both crystals as reported in Fig. 4. We use a similar approach as above for the lower wavenumber range. Regarding the LDP spectra, the first and narrow peaks lying at 888 cm -1 and 923 cm -1 are assigned to ν 1 -PO 4 vibrations regarding their temperature dependence and the position of ν 1 vibration in the free molecular group H 2 PO 4 (886 cm -1 ). Then we attribute the band at 1053 cm -1 to ν 3 -PO 4 vibration since its position is relatively close to this of the free molecular group lying at 1085 cm -1 . However we can point out that the position of this line is unaffected by the temperature change contrary to other peaks attributed to the PO 4 vibrations. This difference may be due to the antisymmetric character of this vibration, rendering it insensitive to temperature.

If we turn on the spectra of KLDP within the same wavenumber range (Fig. 4) we note a strong similarity with LDP, which is useful to deduce the assignment of the different lines. Thus the peaks observed at room temperature around 898 and 946 cm -1 , which are affected by temperature change, are attributed to ν 1 -PO 4 vibrations, whereas the bands around 1026 and 1065 cm -1 are assumed to be assigned to ν 3 -PO 4 vibrations.

Lines occurring above 1100 cm -1 characterize O-H---O vibrations of the hydroxyl groups of the anion H 2 PO 4 -involved in hydrogen bonding and correspond to ν O-H and γ O-H motions. These lines shown in Fig. 5 for both crystals are generally weaker in intensity and higher in wavenumber than the internal modes of PO 4 . In LDP, consistently with the attribution given by Lee et al. they are attributed to γ(O-H) at 1156 cm -1 and 1185 cm -1 and δ(O-H) around 1217 cm -1 and 1323 cm -1 . 10 In KLDP by analogy, the lines lying at 1089 and 1136 cm -1 are assigned to γ(O-H) and the bands around 1226 and 1316 cm -1 to δ(O-H).

Broad bands were detected at higher wavenumber. Similar bands called as A,B,C bands were observed in a large variety of solids 15,16,17 and have been interpreted as OH vibrations with strong O-H-O bonds. Furthermore, the broadening of these OH features reflects the high conductivity of materials. 18 In our case this feature is in agreement with direct measurements in LDP 19 and KLDP 20 and is confirmed by the increase of widening of these bands at higher temperature.

The bands located in LDP around 1612, 2332 and 2767 cm -1 are respectively labeled C, B and A for OH 2 while the peak at 3109 cm -1 is attributed to the OH 1 motion. 21 In KLDP we found wide bands around 2422 and 2934 cm -1 which are attributed to B and A, by comparison with LDP.

According to Novak 22 the bands may be classified according to hydrogen bond length. Thus the fact that the B band is located around 2332 cm -1 in LDP and around 2422 cm -1 in KLDP, can be related to the hydrogen bond longer in KLDP and therefore a higher wavenumber. The same observation can be made for the band A.

Finally we summarize the proposed assignment of the lines on LDP and KLDP in Table 1.

Discussion and conclusion

Our assignment of the various Raman peaks to the different internal vibrational modes can be compared with the previous attributions proposed by Lee et al. and Rhimi et al. 10,5 The main novelty of our investigations results into the attribution of bands lying at 398 or 399 cm -1 and around 513 or 520 cm -1 to LiO 4 vibrations in LDP and KLDP as well.

Regarding specifically LDP, it should be noted that Rhimi et al. 5 assigned a line at 402 cm -1 to LiO 4 whereas Lee et al.did not choose between PO 4 and LiO 4 . 10 The main discrepancy compared with our investigations concerns the peak at 520 cm -1 attributed to P-O vibration in earlier descriptions. Furthermore in our study the peak around 1053 cm -1 in LDP is attributed to PO 4 motion in agreement with Rhimi et al. 5 whereas Lee et al. did not exclude the OH vibration. 10 Regarding KLDP, our assignment of Raman lines notably differs from the previous one by Rhimi et al. 5 In particular these authors attributed the whole group of bands between 400 and 470 cm -1 to vibration modes of LiO 4 , in agreement with earlier investigation on LDP by Lee et al. 10 They invoked the fact that these lines are absent in KDP. In fact, to our opinion, this does not exclude the presence of P-O vibration modes in the same range, like in our attribution above. Indeed in LDP and KLDP, PO 4 tetrahedra are coupled with LiO 4 tetrahedra so that it is not inconsistent to find both internal vibration modes of these entities within the same region.

The analysis of the behavior of Raman spectrum spectra of LDP and KLDP crystals as function of temperature has been used to propose a new assignment of Raman lines to PO 4 and LiO 4 entities in both crystals. Instead of 4 lines in free molecular group H 2 PO 4 , we detect 7 lines attributed to internal modes of PO 4 in LDP, and 12 lines in KLDP, due to symmetry lowering of the structure.

These peaks in both crystals display a down-shift of the position and broadening on heating. The lines, the positions of which are independent of temperature, were by contrast attributed to internal modes of LiO 4 . The positions of these vibrations around 400 cm -1 and 520 cm -1 are close in LDP and KLDP. This last result is consistent with neutron-diffraction data reported by Hwan Oh et al. who observed that Li+ ions are quite immobile and stable in the structure. 4

  PO 4 groups are linked together with the hydrogen bridges and develop a three dimensional framework along zig-zag [100] and [001] chains. The cell parameters of our KLDP crystal have been achieved from X ray diffraction using 4 circle apparatus Bruker SMART CCD with a graphite monochromator using MoKα radiation (λ = 0.71073 Å). The unit cell is monoclinic with the space group P 21/c (C 2h ), and 4 entities inside, each one on site C 1 . The cell parameters are a = 7,5010(5) Å ; b = 12,8842(7) Å and c = 7,3876(4) Å ; β = 98,412(2)° and V = 706,29(7) Å 3 . Li, P, O and H atoms are located in the 4e Wyckoff positions.

Figure 1 .

 1 Figure 1. The crystal structure of KLDP (A) and LDP (B). P and Li atoms are coordinated with four O atoms, building PO 4 and LiO 4 tetrahedra. PO 4 ions are linked each to the other by hydrogen bonds. LiO 4 coordination tetrahedra shares two O atoms with PO 4 tetrahedra.

Figure 2 .

 2 Figure 2. Raman spectrum of KLi(H 2 PO 4 ) 2 and LiH 2 PO 4 recorded at room temperature in the region from 5 to 1200 cm -1 . The spectra within the low wavenumber range are reported in the insert.

Figure 3 .

 3 Figure 3. Raman spectra of LDP and KLDP recorded at three different temperatures in the region from 300 to 600 cm -1 . The spectra are shifted with respect to each other, in order to show their relative changes with temperature.

Figure 4 .

 4 Figure 4. Raman spectra of LiH 2 PO 4 and KLi(H 2 PO 4 ) 2 recorded at three different temperatures in the region from 850 to 1100 cm -1 . The spectra are shifted with respect to each other, in order to show their relative changes with temperature.

Figure 5 .

 5 Figure 5. Raman spectra of LDP and KLDP recorded at room temperature for high wavenumbers.Insert is a zoom of the range 1100-1350 cm -1 .

  2 CO 3 (solid) + 2 H 3 PO 4 (liquid) → 2 Li(H 2 PO 4 ) 2 (solid) + CO 2 (gas) + H 2 O(liquid) Li 2 CO 3 (solid) + K 2 CO 3 (solid) + 4 H 3 PO 4 (liquid) → 2 KLi(H 2 PO 4 ) 2 (solid) + 2 CO 2 (gas) + 2 H 2 O(liquid).

Table 1 .

 1 Observed Raman modes of LDP and KLDP and tentative modes assignment. s: strong, m: medium, and w: weak refer to the relative intensity of the Raman lines.

	LDP


Maksim Koptelov
email: maksim.koptelov@unicaen.fr

Albrecht Zimmermann
email: albrecht.zimmermann@unicaen.fr

Bruno Crémilleux
email: bruno.cremilleux@unicaen.fr

Link Prediction in Multi-Layer Networks and its Application to Drug Design

Keywords: Chemoinformatics, Link prediction, Multi-layer graphs

published or not. The documents may come   L'archive ouverte pluridisciplinaire

Introduction

Predicting links between biological or chemical compounds, and targets, such as therapeutic targets, binding sites or disease phenotypes, is an integral part of research in biology and medicinal chemistry. While the main approach to reliably identifying such links still depends on in vitro testing, computational methods are employed more and more frequently to fine-tune the set of candidates to be tested in silico, cutting down on time and money invested in real-world testing.

A number of methods have been introduced since the problem was first formulated in this form. A straight-forward manner consists of formulating a classification problem: given a particular target, and a number of compounds that have been tested against it, one decides on a representation for the compounds and creates a binary prediction problem that can be solved using any number of existing machine learning techniques. The problem can also be turned around, treating a compound as the class, and targets as data instances, or learning on both entities' representation [START_REF] Yamanishi | Prediction of drug-target interaction networks from the integration of chemical and genomic spaces[END_REF].

A problem such approaches have to overcome is sparsity: whether it is because a target has only recently been identified, because a disease is rare (hence commercially unattractive), or because the relation between certain compounds and targets has not been evaluated for plausible biological reasons, the total space of possible links remains largely under-explored. Concretely, this means that negative examples are often not available, ruling certain techniques out.

A semantically similar problem setting that also faces the sparsity problem is that of product recommendation, and recommender systems have therefore been adapted for the problem setting [START_REF] Lim | Improved genome-scale multi-target virtual screening via a novel collaborative filtering approach to cold-start problem[END_REF]. A simple recommender system-like approach implements, for instance, the reasoning that if two compounds are both linked with several shared targets, and one of them is linked to an additional one, it is reasonable to assume that the other one should be as well. Such an approach has the advantage of exploiting information that is not directly linked to the chosen target yet is still faced with a sparsity problem since, as mentioned, most compounds do not have many links to start with. This makes some approaches to recommendation, such as matrix factorization, difficult or impossible to use.

One relatively recent proposal to address this problem consists of using network data: vertices represent entities, i.e. compounds and targets, and edges between them their relation. While this does not solve the sparsity problem per se, it allows to introduce additional information: chemical or genetic similarity, for instance, or drug-drug/target-target interactions reported in the literature. There are two obvious question related to this idea: 1) Which information sources should one use? 2) How can different networks be integrated?

Current solutions often limit themselves to a single similarity network for both compounds and targets, choosing a single similarity measure such as the Tanimoto, Cosine, Simcomp [START_REF] Hattori | Development of a chemical structure comparison method for integrated analysis of chemical and genomic information in the metabolic pathways[END_REF] similarity, or Smith-Waterman scores [START_REF] Smith | Identification of common molecular subsequences[END_REF] (typically based on empirical validation). In addition, networks are not integrated as such but typically treated separately, with the similarity networks inducing new edges in the interaction network.

In our work, we propose to use a multi-layer network to solve this problem. We illustrate our proposal in the context of ligand-protein interactions, ligands being organic compounds, and proteins biological targets identified as relevant for diseases. Instead of picking and choosing between different sources of information, we propose to use all of them, exploiting different similarity measures and interaction information available. Our main contribution is an improvement on the previously introduced NRWRH method [START_REF] Chen | Drug-target interaction prediction by random walk on the heterogeneous network[END_REF] that allows us to exploit multilayer networks assembled from an arbitrary number and type of layers. As we show in the experimental evaluation, the algorithm effectively exploits the combination of different types of incomplete data to perform drug-target prediction.

The rest of the paper is organized as follows. Section 2 provides basic notations and problem formulation. Section 3 discusses related work in the given field. Section 4 describes how we adapt existing algorithms to the multi-layer setting. Section 5 describes how we prepare and integrate different data sources, the experimental setup, and presents empirical results. Finally, Section 6 concludes and outlines future work.

Definitions and problem formulation

Basic notations

The most important concept in our work is that of a graph.

Definition 1 (Labeled Graph).

A labeled graph is a tuple V, E, λ v , λ e , with V a set of vertices, E ⊆ V × V a set of edges, λ v : V → A v a labeling function mapping vertices to elements of an alphabet of possible vertex labels, and λ e : E → A e a labeling function for edges. We call the degree of a vertex the number of edges in which it is involved:

deg(v) = |{(u, w) ∈ E | u = v ∨ w = v}|.
We exploit this representation in two ways: First, ligands are represented by their molecular 2D-structure, with A v a subset of atoms, and A e = {single covalent bond, double covalent bond, triple covalent bond}. For example, Pyridin-4-amine has chemical equation C 5 H 6 N 2 and can be presented as in Fig. 1. Second, the relationships between ligands, proteins, or between ligands and proteins, are represented as networks. These include ligand-ligand (ll) and proteinprotein (pp) similarity networks, in which A v is the set of ligand/protein identifiers, respectively, and A e = [0, 1]. The other type of network are interaction networks, both ligand-ligand/protein-protein interaction networks derived from the literature, with A e = {0, 1}, and ligand-protein (lp) interaction networks, which contain two set of vertices V l , V p and edges ∀(u, v) ∈ E : u ∈ V l , v ∈ V p , and A e = {0, 1} or A e = R. The former labeling is usually derived from the latter by thresholding. An example of relationships between ligands and/or proteins as networks is presented in Fig. 2.

Definition 2 (Connected component). Given a graph G, we call a subgraph G = V , E , λ v , λ e , V ⊆ V, E ⊆ E a connected component (CC) iff for any two vertices u, v ∈ V , there exists a path {(v 1 , v 2 ), . . . , (v m-1 , v m )}, v i ∈ V, (v i , v i+1 ) ∈ E, such that v 1 = u, v m = v and there is no supergraph of G , G = V , E , λ v , λ e , V ⊃ V , E ⊃ E that is a CC. Definition 3 (Multi-layer graph). A multi-layer graph is a tuple V, E, λ v , λ e , with V a set of vertices, E a multi-set of edges, i.e. tuples (u, v), u, v ∈ V . In a multi-layer graph, E can be decomposed into disjunct sets E l ⊆ V × V , called layers, E = i E li .
As becomes clear from this definition, an arbitrary number of networks can be aggregated into a multigraph, as long as there is overlap in their vertex sets. Trivially, even networks with disjunct vertex sets can be aggregated but since such vertices will not have any edges in the graphs from which they are missing, this will probably be of little use.

Problem formulation

The problem setting we address in this paper is one of link prediction between ligands (drug candidates) and proteins (biological targets).

Definition 6 (Ligand-protein activity prediction). For a given number of ligand-protein activity networks

G i lp = V l ∪ V p , E i , λ v , λ ei , with u ∈ V l la- beled with ligands identifiers, v ∈ V p labeled with protein identifiers, ∀(u, v) ∈ E, u ∈ V l , v ∈ V l , and A e = {0, 1}, ligand-ligand networks G i l = V l , E i l , λ v , λ e i l , protein-protein networks G i p = V p , E i p , λ v , λ e i p and a given (u, v) ∈ E, u ∈ V l , v ∈ V p predict, whether λ e ((u, v)) = 1.
We limit ourselves to the relatively easier task of predicting whether there is activity or not, leaving the prediction of its strength as future work.

Related work

The literature on compound-target activity prediction, even using networks, is too vast to discuss here. We therefore present a number of works illustrating the characteristics we discussed in the introduction. Ligand-protein activity, the use case we explore here, has been addressed in [START_REF] Yamanishi | Prediction of drug-target interaction networks from the integration of chemical and genomic spaces[END_REF], which selects a ligand and target similarity measure each, and multiplies activity vectors of known ligands/targets with the similarity to new ligands/targets to derive predictions. In [START_REF] Yamanishi | Drug-target interaction prediction from chemical, genomic and pharmacological data in an integrated framework[END_REF], the same group used ligand structural and pharmacological similarity, as well as genetic protein similarity, mapped ligands and targets into a shared feature space and predicted activity. The authors of [START_REF] Cheng | Prediction of chemical-protein interactions network with weighted network-based inference method[END_REF] used three networks: ligand-ligand similarity, target-target similarity, ligand-target activity, evaluated four ligand similarity measures, settling on Tanimoto distance. The proposed method, NWNBI, exploits similarity weights and log-values of activity measurements to perform four-step network traversals. In [START_REF] Chen | Drug-target interaction prediction by random walk on the heterogeneous network[END_REF], ligand similarity is calculated as weighted average of two similarity measures, and combined with a target similarity, and the interaction network into a three-layer network, which they refer to as "heterogeneous". They simulate random walk with restart by matrix multiplication, and show that only using a single similarity measure or ignoring the interaction network deteriorates results. Three networks are also used in [START_REF] Lim | Improved genome-scale multi-target virtual screening via a novel collaborative filtering approach to cold-start problem[END_REF], the authors discuss different options for similarity measures, and perform low-rank matrix factorization on the adjacency/similarity matrices. They address sparsity by giving non-existing links a small non-negative weight. Ligand-protein activity is also the subject of [START_REF] Buza | Aladin: A new approach for drug-target interaction prediction[END_REF], which exploits the three-layer network to perform weighted nearest-neighbor classification. Gene-disease interactions have been considered in [START_REF] Xie | Prioritizing disease genes by bi-random walk[END_REF], using three layers, simulating random walk by matrix multiplication, using different numbers of steps for the two similarity networks. Using a similar bi-random walk idea, [START_REF] Luo | A novel approach for predicting microrna-disease associations by unbalanced bi-random walk on heterogeneous network[END_REF] consider microRNA-disease interactions, exploiting a three-layer network. The random walk with restart in [START_REF] Liu | Inferring microrna-disease associations by random walk on a heterogeneous network with multiple data sources[END_REF] is symmetric (and functionally the same as in [START_REF] Chen | Drug-target interaction prediction by random walk on the heterogeneous network[END_REF]), with the similarity networks constructed by averaging two similarity measures. They evaluate different parameter settings.

Exploring a multi-layer graph

As the preceding section shows, the standard setting employed consists of three networks, and to adhere to this setting, authors either choose a single similarity measure empirically, or combine similarity measures via user-specified weights. Instead, we propose to combine all available networks into a multi-graph having more than three layers. Once we have such a network, the question is how to exploit it, however, and here we hew close to the literature.

The random walk model

A long-established method for exploring a network is the random walk [START_REF] Pearson | The problem of the random walk[END_REF], which proceeds roughly as follows: starting from a randomly selected node, it performs walks along edges of the graph at random. In every step, the edge to follow is chosen uniformly from all outgoing links (in the case of an unweighted graph) or proportional to link weights (in the case of a weighted graph). Node importance is based on how frequently the walker visits the node: a node with higher frequency is considered more important than a node with a low value (Fig. 3). This idea can be modified in a number of ways to improve network Fig. 3. Nodes importance example in a graph, taken from [START_REF] Leskovec | Mining of massive datasets[END_REF] exploration: the walker can be constrained to perform at most max steps steps, to not visit any of the last c vertices it encountered, or with small probability 1 -β the process can be restarted at any time to avoid getting trapped by those vertices it mustn't visit. The product of the probabilities of edges the walker traversed gives the cumulative probability of a path between two nodes and can be used to predict a link between a starting node and an end node: if the path probability is greater than a given threshold, a new edge is predicted.

To extend this approach to multi-layer graphs, one needs to add how to choose the layer to walk in. We propose to select a network uniformly at random from the set of networks, and multiply the path strength by

1 |{G i l }|+|{G j p }|+|{G k lp }| .
Repeat the process until a user-defined target vertex is reached or the maximum number of steps have been performed. Due to the randomized nature, random walks are usually repeated several times to derive more robust estimates.

Network-based Random Walk on Multi-layer network

Instead of explicitly random walking as described above, random walks are often simulated via matrix multiplication of transition matrices. This is notably the approach proposed in [START_REF] Chen | Drug-target interaction prediction by random walk on the heterogeneous network[END_REF], abbreviated as NRWRH. They define a transition matrix

M = M pp M pl M lp M ll
, in the manner described above, i.e. uniform probabilities for lp/pl-transitions, proportional probabilities for similarities, with an additional user-specified parameter λ ∈ [0, 1] affecting moves from ligands to proteins and vice versa. Given a ligand l i , a starting vector v 0 ∈ [0, 1] |V l |+|Vp| is initialized with 1 at the position for v ∈ V l , λ v (v) = l i , 1 |{(v,u)∈E lp }| at the positions for the proteins linked to it, 0 otherwise. Protein entries in v 0 are multiplied with 1 -η, ligand entries with η, a user-defined parameter to bias the walk towards proteins (η < 0.5), or ligands (η > 0.5). The vector representing the probabilities that a walker starting with l i finds itself in any of the nodes is calculated iteratively as p t+1 = (1-β)M T p t +βp 0 until |p t+1 -p t | < 10 -10 . This can be understood as the random walker walking "in all directions at the same time". The approach can be considered a simplified version of Personalized PageRank [START_REF] Haveliwala | Topic-sensitive pagerank: A context-sensitive ranking algorithm for web search[END_REF], simplified because edges are undirected and there is only a single starting vertex. Removing the starting vertices from the final state vector, and ranking entries gives predicted edges. We adapt this approach to a setting with |{G i l }| + |{G j p }| + |{G k lp }| ≥ 3. While the algorithm stays essentially the same, we decompose the transition matrix into a matrix M for within-network/layer transitions, and a matrix N for between-network/layer transitions. We also do away with the user-dependent λ. Explicitly creating M in the manner shown above is easy for three layers but becomes much harder when different numbers can be involved. We hence con-

struct M =   M Gp 0 0 0 M G l 0 0 0 M G lp   , with M Gp =    M 1 Gp 0 . . . 0 0 M 2 Gp . . . 0 0 0 . . . M |{G i p }| Gp    derived from protein-protein similarity networks (M G l , M G lp accordingly). The tran- sition matrix N =     N G 1 p →G 1 p N G 2 p →G 1 p . . . N G G i lp lp →G 1 p . . . . . . . . . . . . N G 1 p →G G i lp lp N G 2 p →G G i lp lp . . . N G G i lp lp →G G i lp lp   
 explicitly models possible layer transitions, with 1s on the main diagonal of a submatrix N Gj →Gi for all nodes present in both layers, 0s otherwise. Note that this means that transition matrixes from ligand to protein layers (and vice versa) have zeros everywhere including the main diagonal. The initial state vector v 0 has dimensionality

(|V p | • |{G pi }| + |V l | • |{G li }| + |V l ∪ V p | • |{G lpi }|)
with entries for all vertices in all layers. It is initialized by setting the entry for the starting ligand and each linked protein to 1 in every network they are present. Matrices and state vectors are column-normalized -the entries of a column must sum to 1.

Our algorithm, NEtWork-basEd Random walk on MultI-layered NEtwork (NEWERMINE), is summarized in Algorithm 1. (M norm N ) norm can be precomputed, giving us a matrix that is functionally equivalent to M as defined in NRWRH, and used on every iteration of NEWERMINE to save computation time. At the end, v f inal needs to be summarized by summing up for each vertex all corresponding entries, leading to a vector with dimensionality |V l ∪ V p | from which the edge ranking can be derived.

Experimental Evaluation

In order to allow reproducibility of our work, we evaluated our approach on publicly available data. In this part we provide a description of the data used Algorithm 1: The NEWERMINE algorithm Input : adjacency matrix M , transition matrix N , starting vertex, max steps, η, β, max diff Output: Probability scores v f inal V0 l ← initialize starting vertex V0 p ← initialize targets for which an interaction with starting vertex is known

V0 ← (1 -η) • V0 l norm + η • V0 p norm step ← 0 repeat step ← step + 1 Vstep ← β • (MnormN )normVstep-1 + (1 -β) • V0 until (|vstep -vstep-1| ≤ max diff) ∨ (step > max steps) return vstep
and the details of the experimental protocol. This is followed by the results and the discussion.

Experimental Settings

Datasets In total we have used 4 datasets:

1. IUPHAR -an open-access database of ligands, biological targets and their interactions. We used version 2017.5 (released on 22/08/2017). The full dataset has 8978 ligands, 2987 proteins, and 17198 interactions (edges) between them 2 . In order to satisfy the designed setting conditions, we removed duplicate interactions (based on different affinity measures), leaving 12456 interactions in total. For existing interactions, we label an edge with 1 if the negative logarithm of the affinity measure is ≥ 5, non-interacting otherwise. 3We treat all affinity measures available in the data (pKi, pIC50, pEC50, pKd, pA2, pKB) as equivalent. 1. Data set and network characteristics to IUPHAR using the RefSeq attribute (human protein sequence identifier) available in IUPHAR. The database was accessed 20/12/2017.

Ligands were mapped between networks by numerical identifiers provided by IUPHAR as well as by INN (International Non-proprietary Name) and Common name attributes. Proteins were mapped by IUPHAR identifiers as well as by Human Entrez Gene attribute. 5 In total we have built 6 networks:

1. a drug interaction network based on DrugBank, 2. a drug similarity network based on similarities calculated using the Tanimoto coefficient on binary vectors constructed by frequent subgraphs, 3. the drug-target interaction network based on IUPHAR, 4. a target interaction network based on BioGrid, and 5. two target similarity networks calculated using the Tanimoto coefficient on feature vectors constructed by frequent substrings and Prosite motifs.

Similarity networks' edges were labeled with labels ∈ [0, 1], interaction networks with labels ∈ {0, 1}. Table 1 shows the characteristics of the data sets, and of the networks we derived from them. It is noticeable how sparse the data is, and also how this sparsity translates into disconnected parts of the network. Sparsity might result in a low performance of the traditional recommender systems approaches, while disconnected networks are challenging for random walker approaches.

Evaluation Protocol To evaluate our approach, we used leave-one-out crossvalidation: for each of the 12456 edges in the IUPHAR network, we remove it from the network, set the ligand as starting vertex, infer strengths for all possible ligand-target paths, remove ligand-target edges contained in the training data, and check whether the removed edge is found in the top-20 remaining paths 6 according to their strengths. If this is the case for an interacting edge, we consider it a true positive, otherwise a false negative. For negative examples, the relationship is inverse.

Quality Measures

To evaluate our methods we use several performance measures: -Accuracy: the ratio of true positives (TP) -drug-target links correctly classified as positives -and true negatives (TN) -drug-target links correctly classified as negatives -over all predictions: Acc = T P +T N T P +F P +T N +F N . -Area under receiver operating curve (AUC): evaluates whether true positives are usually ranked above or below false positives when sorting predictions by confidence. -Precision: the ratio of TP over all drug-target links classified as positives:

P rec = T P T P +F P . Precision measures whether a model is specific enough to mainly classify links of the positive class as positive. This gives additional insight into the accuracy score.

-Recall: the ratio of TP over all positive links in the test data: Rec = T P T P +F N . Recall measures whether a model is general enough to classify a large proportion of the positive class as positive.

In addition to this, we also report weighted versions of accuracy, precision, and recall that give us a more accurate assessment for unbalanced datasets. Due to the fact that the number of negative examples are smaller than that of the positives in our data, we assign a classification cost of 1 to positives and cost neg cost to negatives, derived by: neg cost = |D| 2×|N | , where |D| -number of examples, |N | -number of negative examples. We then perform evaluation based on the costs defined: FN and TN receive score neg cost for every negative example w.r.t. its real class, while FP and TP receives score 1 for positives.

Implementation We implemented NEWERMINE in Python7 . We used the networkx library to model the multi-layer network, the NumPy library to perform all matrix computations and the sklearn library for cost-based evaluation.

Experimental results

Using three-layer graphs We first use NEWERMINE on a number of multigraphs aggregated from three networks each, the ligand-target network, one ligand-ligand network, and one target-target network. This is the setting used in the papers discussed in Section 3.

For the experiments we defined 6 possible combinations with IUPHAR, only ligand-target interaction network we have: (1) DrugBank + BioGrid, (2) Drug-Bank + Target similarity (TS) (substrings:str), (3) DrugBank + TS (motifs:mot), (4) Ligand similarity (LS) + BioGrid, (5) LS + TS (str), ( 6) LS + TS (mot). The basic properties of the combinations compared to the full graph are presented in Table 2. The results of the use of NEWERMINE with parameters η = 0.2, β = 0.7 (taken from [START_REF] Chen | Drug-target interaction prediction by random walk on the heterogeneous network[END_REF]) are presented in Fig. 4. This is a rather conservative setting, equivalent to relatively few steps before the walker restarts.

The number of vertices in different networks depend on available IDs and structural information. In any case, the networks are sparse and they are not Fig. 4 shows that using different three-layer graphs leads to rather different results. The arguably most notable result is that using ligand structural similarity instead of DrugBank network significantly improves accuracy and recall.

Using the full, six-layer graph The results for NEWERMINE on the full multi-layer graph are also presented in the Fig. 4. We show additional values for η and β: η = 0 strongly biases the walk towards targets, we also consider β = 0.8 for η = 0.2. Using more layers decreases recall somewhat, but improves weighted accuracy (taking the lower proportion of negative examples into account), AUC score and precision. Different parameter values do not have a large effect on the results but change running times: increasing β also increases the number of steps necessary for convergence, and decreasing η decreases this number.

Conclusion and perspectives

We have presented an approach for exploiting an arbitrary number of networks combined into a multi-layer network, proposing general matrix formulations to form intra-and inter-network transitions.

As we have demonstrated experimentally, combining different networks improves vertex reachability and therefore interaction prediction. So far, we have only exploited more than one protein similarity network, already achieving very good results. In future work, we intend to also integrate different ligand similarity semantics, and different databases indicating ligand-protein activity. Additionally, we intend to employ our approach for different target settings, e.g. for miRNG-disease links. Finally, we aim to move from the "active"/"inactive" setting to one where we predict the strength of the activity.

Fig. 1 .

 1 Fig. 1. Example of a molecule 2D representation (left) and its corresponding graph in hydrogen suppressed form (right)

Fig. 2 . 1 Definition 5 (

 215 Fig. 2. An example of a multi-layer graph with 6 networks: ligand-protein network is in deep blue (IUPHAR), ligand-ligand networks are in light blue (ligand similarity network) and violet (DrugBank), protein-protein networks are in green (BioGrid), grey (protein similarity network based on substrings) and brown (protein similarity network based on motifs)

Fig. 4 .

 4 Fig. 4. Evaluation results of NEWERMINE for different combinations of three networks and the six-layer graph

  2. DrugBank (DB) -an open-access database of drug-drug interactions. We used version 5.0.11 (released 20-12-2017). It has 658079 interactions of 3138 distinct drugs. 242922 of these interactions involve 1254 distinct ligands that are present in IUPHAR. The database was also used as a source of 2D representations of ligands to compute ligand similarities. 3. BioGrid (BG) -an open-access database of protein-protein interactions mined from a corpus of biomedical literature. We used version 3.4.154 (25/10/2017). It has 1482649 interactions of 67372 distinct proteins. Only 15410 of these interactions involve proteins present in IUPHAR (1925 distinct proteins). 4. NCBI Protein database -The National Center for Biotechnology Information proteins database 4 was used to obtain amino acids sequences to represent targets. The data was parsed from the website of NCBI and mapped

						Network
	Data set	Entities Relations Sparsity Vertices Edges Sparsity CC
	IUPHAR	11965	12456 0.00017 11965	12456 0.00017 443
	DrugBank	3138	658079 0.1337 1254	122808 0.15631 1
	BioGrid	67372 1482649 0.00065 1898	8658	0.0048 11
	Ligand similarity 6821 23259610	1	6821 23259610	1	1
	NCBI	1818 1651653	1	1818 1651653	1	1
		Table

Table 2 .

 2 Basic properties of different combinations of networks

	Combination Ligands Targets |V |	|E|	Sparsity CC
	DB + BG	7025	2307 9332 143922 0.003 87
	DB + TS (str) 7025	2101 9126 1786917 0.042 103
	DB + TS (mot) 7025	2101 9126 1786917 0.042 103
	LS + BG	8056	2307 10363 23280724 0.434 21
	LS + TS (str) 8056	2101 10157 24923719 0.4832 22
	LS + TS (mot) 8056	2101 10157 24923719 0.4832 22
	Six layers	8137	2502 10639 26706838 0.4719 1

An open-access database is available at http://prosite.expasy.org

in ligands.csv, interactions.csv, and targets and families.csv, respectively

Cutoff proposed by researchers from CERMN (http://cermn.unicaen.fr)

https://www.ncbi.nlm.nih.gov/protein/

https://zimmermanna.users.greyc.fr/supplementary-material.html


Adilla Susungi
email: adilla.susungi@mines-paristech.fr-norman.rink@tu-dresden.de

Norman A Rink

Albert Cohen

Jerónimo Castrillón

Claude Tadonki

Meta-programming for Cross-Domain Tensor Optimizations

Keywords: program ::= stmt program Texpression | Lexpression Texpression ::= tensor ([ ints ]) | eq ( id, iters ? → iters ) | vop ( id, id, [ iters ?, iters ?]) | op ( id, id, [ iters ?, iters ?] → iters | stripmine ( id, int, int

Design and semantics of a tensor optimization meta-language

Functional transformation meta-language with high-level abstractions for tensor computations to enable the composition of different type of transformations (e.g. loop, algebraic or layout transformations). Formal specification of tensor operations and loop transformations using denotational semantics.

Examples of use: empirical tuning engines, meta-programming optimizations by experts.

iters ::= [ ids ] ids ::= id (, id )* ints ::= int (, int )*

Code Sample

# --Begin program specification w = tensor(double, [13]) u = tensor (double, [13, 13, 13]) L = tensor(double, [13,13]) M_ = outerproduct ([w, w, w]) Lh = div (L, w, [[i1, i2]

, [i2]] -> [i1, i2]) → M = entrywise_mul(M_, u) r1 = contract(Lh, M, [[2, 1]]) r2 = contract(Lh, M, [[2, 2]]) r3 = contract(Lh, M, [[2, 3]]) # --End program specification # Code generation without transformations l1 = build(M_) l2 = build(Lh) l3 = build(M) l4 = build(r1) l5 = build(r2) l6 = build(r3)
codegen ([l1, l2, l3, l4, l5, l6]) # Code generation with loop fusions only l7 = fuse(l4, l5, 3) l8 = fuse(l7, l6, 3) codegen ([l1, l2, l3, l7]) # Code generation with fusion, parallelism and vectorization → l9 = parallelize(l1, 1, None) l10 = parallelize(l2, 1, None) l11 = parallelize(l3, 1, None) l12 = parallelize(l8, 1, None) l13 = vectorize(l9, 3) l14 = vectorize(l10, 2) l15 = vectorize(l11, 3) codegen ([l13, l14, l15, l12])

Semantics Foundations

Domains and state

T = { (op, S, I), ts | (ts = []) ∨ (ts = [t 1 , . . . , t k ] ∧ t i ∈ T)} L = { id, [x 1 , . . . , x k ] | x i ∈ L ∪ T } σ : identifier → (T + L)
Valuation functions

P prog s p = P prog p • P stmt s E t tensor(S) = λσ. ( , S, ), [] E t eq(t, I 0 → I 1 ) = λσ.let (op, S, I ), ys = σ(t) y = (op, S, I ), ys x = ( , S , I 1 ), [] in (=, •, •), [x, y] ,
where

I = ∧ I = I , if I 0 = I = ∧ I = I 0 , if I 0 = E l build(t) = λσ.let r = "number of iterators in σ(t)" i k = (0, ub k , 1) for k = 1, . . . , r in i 1 , . . . , i r , [σ(t)] . . . , where σ(t) = (=, •, •), [x, y] E l stripmine(l, r, v) = λσ.let i 1 , . . . i r , xs . . . = σ(l) (b, e, 1) = i r i r = (0, (e -b)/v -1, 1) i r+1 = (b + v • i r , b + v • i r + (v -1), 1) in i 1 , . . . i r , [ i r+1 , xs ] . . . E l interchange(l, r 1 , r 2 ) = λσ.let i 1 , . . . i r 1 , . . . i r 2 , xs . . . . . . = σ(l) in i 1 , . . . i r 2 , . . . i r 1 , xs . . . . . .

Tensor Expressions

Matrix transposition

A = tensor([N1, N2]) B = eq(A, [i1, i2] -> [i2, i1]) (=, •, •) (B, [N2, N1], [i2, i1]) (A, [N1, N2], [i1, i2]) E l build(B) σ 2 = i1, [ i2, [σ 2 (B)] ] : for (int i1 = 0; i1 <= (N1-1); i1++) for (int i2 = 0; i2 <= (N2-1); i2++) B[i2][i1] = A[i1][i2];
Compositions Contraction

P stmt t = contract(t 0 , t 1 , [r 0 , r 1 ]) = P prog t 2 = vmul(t 0 , t 1 , [I, J]) t = add(t , t 2 , [I , ] → I
) where I = [i0, . . . , i(r 0 -1), k, i(r 0 + 1), . . . , is 0 ] J = [j0, . . . , j(r 1 -1), k, j(r 1 + 1), . . . , js 1 ] I = (I \{k}) || (J \{k}) Tiling Initial loop nest

i 1 i 3 i 5 xs stripmine n( , 3, v) has introduced i 2 , i 4 , and i 6 i 1 i 2 i 3 i 4 i 5 i 6 xs
* After three times interchange n.

i 1 i 3 i 5 i 2 i 4 i 6 xs

Experiments

  90GHz, 8 hyperthreads, 8192KB of shared L3 cache), Ubuntu 16.04. Generated C programs compiled with the Intel C compiler ICC 18.02 (flags: -O3 -xHost -qopenmp) With TeML: Pluto (v 0.11.4) optimizations reproducible Capability to express better optimization paths Future Work Abstractions for memory virtualization, stencil patterns, sparse tensors and corresponding semantics, extensions for parallelism support, type system This work was partially supported by the German Research Council (DFG) through the Cluster of Excellence 'Center for Advancing Electronics Dresden' (cfaed) and by PSL University through the ACOPAL project.


Augustin Fruchard

Fixing and almost fixing a planar convex body

Keywords: AMS Classification: 52A15, 52A40, 52B10 Immobilisation, convex body

Fixing and almost fixing a planar convex body

Augustin Fruchard

Notation. The plane R 2 is endowed with its euclidean norm . The origin of R 2 is denoted by 0. The unit cercle of centre 0 and radius 1 is denoted by S 1 . The group of planar affine rotations and translations is denoted by Isom + R 2 . The identity of R 2 is denoted by id. The rotation of centre ω ∈ R 2 and angle α ∈ R is denoted by R ω,α . Given an oriented line D, the open half-plane on the left of D is denoted by D + . As usual, for M ⊂ R 2 , bd M denotes its boundary and int M denotes its interior.

Throughout this note, K is a convex compact subset of R 2 of nonempty interior, and a 1 , . . . , a n are points on bd K. Definition 1. The points a 1 , . . . , a n fix K if there is a neighbourhood V of id in Isom + R 2 such that, for every f ∈ V satisfying f (K) = K, at least one of the a i belongs to int f (K). This is slightly different from the commonly used definition of fixing points, e.g. in [START_REF] Bracho | Immobilization of smooth convex figures[END_REF][START_REF] Bracho | Immobilization of solids and mondriga quadratic forms[END_REF], where a subset H of bd K is said to fix K if id is isolated in the set f ∈ Isom + R 2 ; H ∩ f (int K) = ∅ . In particular, we consider that a rotation of a disc around its centre does not move the disc. If K is not a disc, then both definitions are equivalent, since in this case there is a neighbourhood

V of id in Isom + R 2 such that every f ∈ V \ {id} satisfies f (K) = K.
Although most convex bodies in the sense of Baire categories can be fixed by three points, there are convex bodies which cannot be fixed by any set of three points, e.g. parallelograms. Other examples can be found in [START_REF] Czyzowicz | Immobilizing a Shape[END_REF].

Another commonly used definition of fixing points, closer to the intuition, is the following one, see e.g. [START_REF] Czyzowicz | Immobilizing a Shape[END_REF].

Definition 2. The points a 1 , . . . , a n ∈ bd K weakly fix K if, for any path γ : [0, 1] → Isom + R 2 , t → γ t such that γ 0 (K) = K and γ 1 (K) = K, there exist i ∈ {1, . . . , n} and t ∈ [0, 1] such that a i ∈ int γ t (K).

Obviously, if a 1 , . . . , a n fix K in the sense of Definition 1, then they weakly fix K. The converse is false, as shows the following example.

Example 3. Choose K admitting S 1 as an inscribed circle and such that bd K ∩ S 1 is the union of an arc of circle of length greater than π and a countable number of points accumulating to some point of S 1 , say:

bd K ∩ S 1 = {(cos θ, sin θ) ; |θ| ∈ [π/4, π] or ∃n ∈ N ; |θ| = π/2 n }.
This can be done by completing the arc of circle of length 3π/2 by segments tangent to S 1 at these points (cos(π/2 n ), sin(±π/2 n )); this could also be done such that K is strictly convex and smooth. Then the four points a i = (cos(iπ/2), sin(iπ/2)), i = 1, 2, 3, 4, weakly fix K but do not fix it in the sense of Definition 1.

A first order condition to fix K.

We want to give an almost necessary and sufficient condition of first order for a 1 , . . . , a n to fix K. "Of first order" means that these conditions make use of the left and right tangents of bd K at the a i s. "Almost" means that the necessary condition involves non-strict inequalities, whereas the sufficient condition involves the corresponding strict inequalities. In the case of three points, we find again the well-known necessary condition that the three normals are concurrent. In [START_REF] Bracho | Immobilization of smooth convex figures[END_REF] an almost necessary and sufficient condition of second order, i.e. using the curvature of bd K, is given such that three points fix a C 2 convex body K.

We first introduce some notation. We orient bd K counterclockwise. Given a ∈ bd K, let T ℓ (a), resp. T r (a), be the left, resp. right, tangent at bd K in a. We orient these lines as bd K; thus we have

K ⊂ T ℓ (a) + ∩ T r (a) + . Let N ℓ (a), resp. N r (a)
L(a) = N ℓ (a) + ∪ N r (a) + .
Let L(a) be the corresponding closed sector, and let #» L(a) = {x ∈ S 1 ; a + x ∈ L(a)} be the set of directions of L(a). Let R(a) and R(a) be the analogous sectors for the right half-planes. The set of directions of R(a) is -#» L(a), hence will not be needed.

If bd K is differentiable at a, then L(a) = R 2 \ R(a), otherwise L(a) ∩ R(a)
is the union of two sectors of vertex a. Theorem 4. Let K be a planar convex body and a 1 . . . , a n ∈ bd K.

(i) If a 1 , ..., a n weakly fix K, then both intersections L(a 1 ) ∩ ... ∩ L(a n ) and R(a 1 ) ∩ • • • ∩ R(a n ) are empty. (ii) If the three intersections L(a 1 ) ∩ • • • ∩ L(a n ), R(a 1 ) ∩ • • • ∩ R(a n ), and #» L(a 1 ) ∩ • • • ∩ #» L(a n ) are empty, then a 1 , . . . , a n fix K.
Remark. The set of directions is needed in item (ii). For instance, if

K = [-2, 2] × [0, 1], then the three points a = (-1, 0), b = (1, 0), c = (0, 1) do not fix K, although the intersections L(a) ∩ L(b) ∩ L(c) and R(a) ∩ R(b) ∩ R(c) are empty.
For the proof of Theorem 4, we will need the following statement. Recall that R ω,α is the rotation of centre ω and angle α.

. Let T ′ ℓ (δ) = R a,-δ (T ℓ (a)) and T ′ r (δ) = R a,δ (T r (a))
. By definition of the left and right tangents, there exists r > 0 such that D(a, r) ∩ T ′ ℓ (δ)

+ ∩ T ′ r (δ)
+ is entirely included in K, where D(a, r) denotes the disc of centre a and radius r. Then, as soon as α ν < r D , we have R ων ,-αν (a) ∈ int K.

(iii) By contraposition, assume x / ∈ #» L(a). Let δ > 0 be so small that x / ∈ R 0,-2δ #» L(a) ∪R 0,2δ #» L(a) . Then, for ν large enough, we have

ων ων / ∈ R 0,-δ #» L(a) ∪ R 0,δ #» L(a)
. With the above notation, let r > 0 be such that D(a, r) ∩ T ′ ℓ (δ) + ∩ T ′ r (δ) + ⊂ K. Then, as soon as α ν ω ν < r, we have R ων ,-αν (a) ∈ int K.

Proof of Theorem 4. (i) By contraposition, assume L(a 1 ) ∩ • • • ∩ L(a n ) nonempty and choose a point ω in this intersection. By Lemma 5 (i), for each i ∈ {1, . . . , n}, since ω ∈ L(a i ), there exists ε i > 0 such that R ω,-α (a i ) / ∈ K for all α ∈]0, ε i [. As a consequence, for all α < min(ε 1 , . . . , ε n ), none of the a i belongs to int R ω,α (K), hence a 1 , . . . , a n do not weakly fix K. The case R(a 1 ) ∩ • • • ∩ R(a n ) = ∅ is similar, using clockwise rotations.

(ii) By contraposition, if a 1 , . . . , a n do not fix K then, for any neighborhood V of id in Isom + R 2 , there exists

f ∈ V \ {id} such that ∀i = 1, . . . , n a i / ∈ int f (K). ( 1
)
It follows that there is a sequence (f ν ) ν∈N tending to id in Isom + R 2 \ {id} and satisfying [START_REF] Bracho | Immobilization of solids and mondriga quadratic forms[END_REF]. At least one of the following cases must occur:

-an infinite number of f ν are direct (i.e. counterclockwise) rotations, -an infinite number of f ν are indirect rotations, -an infinite number of f ν are translations.

In the first case, considering a subsequence if necessary, we assume without loss of generality that the whole sequence (f ν ) consists of direct rotations, of centres ω ν ∈ R 2 and angles α ν > 0 tending to 0.

-If the sequence (ω ν ) ν∈N is bounded, then a subsequence converges to some point ω ∈ R 2 . Then, Lemma 5 (ii) and ( 1) imply that ω belongs to

L 1 ∩ • • • ∩ L n .
-If the sequence (ω ν ) ν∈N is unbounded, then a subsequence (ω ν k ) k∈N tends to infinity. By compactness of S 1 , a subsequence of ων k ων k k∈N converges to some

x ∈ S 1 . Then Lemma 5 (iii) and [START_REF] Bracho | Immobilization of solids and mondriga quadratic forms[END_REF]

imply that x ∈ #» L 1 ∩ • • • ∩ #» L n .
The second case of indirect rotations yields similarly

R 1 ∩ • • • ∩ R n = ∅ or #» L 1 ∩ • • • ∩ #» L n = ∅.
In the third case, we also assume without loss of generality that every f ν is a translation of vector v ν . Then a subsequence of vν vν ν∈N converges to some x ∈ S 1

and we obtain similarly to the proof of Lemma 5 (iii

) that R 0,-π/2 (x) ∈ #» L 1 ∩• • •∩ #» L n .
A first order condition to almost fix K.

Definition 6. The points a 1 , . . . , a n almost fix K if, for any neighbourhoods V i of a i (i = 1, . . . , n), there are pairs of points

a ′ i , a ′′ i ∈ V i ∩ bd K, such that a ′ 1 , a ′′ 1 , . . . , a ′′ n fix K.
In [START_REF] Fruchard | Short cages holding convex bodies[END_REF] it is proven that any planar convex body can be almost fixed by two or three points.

It seems natural that, if a 1 , . . . , a n almost fix K, then one can choose a ′ i and a ′′ i on each side of a i . The following example shows that this is not the case! Example 7. For any integer n ≥ 2, let p n = 1 cos(π/4 n ) cos(3π/4 n ), sin(3π/4 n ) and choose for K the convex hull of S 1 ∪ {p 2 , p 3 , . . . }. Then K admits S 1 as an inscribed circle and, for any θ ∈ R, we have

(cos θ, sin θ) ∈ bd K ∩ S 1 ⇔ θ ∈ [π/4, 2π] or ∃n ∈ N ; π/4 n ≤ θ ≤ 2π/4 n .
The rest of bd K is made of segments tangent to S 1 , crossing at the p n .

Then the four points a k = (cos(kπ/2), sin(kπ/2)), k = 1, 2, 3, 4, almost fix K but in the neighbourhood of a 4 one has to choose both points a ′ 4 and a ′′ 4 on the same side of a 4 .

Our next statement is the analog of Theorem 4. The only difference is that the large sectors L and R are replaced by the following small sectors ℓ and r: Proof. The notation a ′ → ℓ a (resp. a ′ → r a) means that a ′ tends to a from the left (resp. from the right) on bd K, with a ′ = a. The semicontinuity of the left and right tangents can be expressed as follows:

ℓ(a) = N ℓ (a) + ∩ N r (a) + = R 2 \ R(a),
lim a ′ → ℓ a N ℓ (a ′ ) = lim a ′ → ℓ a N r (a ′ ) = N ℓ (a), lim a ′′ →r a N ℓ (a ′′ ) = lim a ′′ →r a N r (a ′′ ) = N r (a). (2)
Here we use the topology of uniform convergence on every compact set: A subset M ′ of R 2 tends to M ⊂ R 2 if, for all r > 0, the Pompeiu-Hausdorff distance between M ′ ∩ D(0, r) and M ∩ D(0, r) tends to 0, where D(0, r) is the closed disc of centre 0 and radius r. As a consequence of (2), we have lim

a ′ → ℓ a,a ′′ →r a L(a ′ ) ∩ L(a ′′ ) = ℓ(a), lim a ′ → ℓ a,a ′′ →r a R(a ′ ) ∩ R(a ′′ ) = r(a), (3) lim
a ′ → ℓ a,a ′′ →r a #» L(a ′ ) ∩ #» L(a ′′ ) = #» ℓ (a).
(i) Assume ℓ(a 1 ) ∩ ... ∩ ℓ(a n ) nonempty and choose a point ω in this intersection. Let us fix the index i ∈ {1, . . . , n}. By (2), there exists ε > 0 such that, for all a ′ i , a ′′ i ∈ bd K satisfying |a i a ′ i | < ε and |a i a ′′ i | < ε, we have ω ∈ L(a ′ i ) ∩ L(a ′′ i ). By Theorem 4 (i), it follows that a ′ 1 , . . . , a ′′ n do not fix K. (ii) By contraposition, if a 1 , . . . , a n do not almost fix K, then there exists ε > 0 such that, for all a ′ i , a ′′ i ∈ bd K satisfying |a i a ′ i | < ε, one on each side of a i , a ′ 1 , . . . , a ′′ n do not fix K. Given sequences (a ′ i,ν ) ν∈N and (a ′′ i,ν ) ν∈N tending to a i , using Theorem 4 (ii) and choosing adequate subsequences if necessary, it follows that one of the intersections L(a ′

  , be the left and right normals at bd K in a, oriented in the directions T ℓ (a) + , resp. T r (a) + , i.e. the line orthogonal to T ℓ (a), resp. T r (a), containing a, and pointing (as) inward K (as possible). Let L(a) be the open sector, union of the left open half-planes bounded by N ℓ (a) and N r (a):

Lemma 5 .

 5 Let K be a planar convex body, let a ∈ bd K, and let ω ∈ R 2 .(i) If ω ∈ L(a) then there exists ε > 0 such that R ω,-α (a) / ∈ K for all α ∈ ]0, ε[.(ii) Let (α ν ) ν∈N be a sequence of positive numbers tending to 0 and (ω ν ) ν∈N be a sequence of points of R 2 tending to ω. If R ων ,-αν (a) / ∈ int K for all ν ∈ N, then ω ∈ L(a).

(

  iii) Let (α ν ) ν∈N be a sequence of positive numbers tending to 0 and (ω ν ) ν∈N be a sequence of points of R 2 tending to infinity (i.e. ω ν → +∞) such that the sequence ων ων ν∈N converges to some x ∈ S 1 . We assume that the sequence of rotations (R ων ,-αν ) ν∈N tends to id ∈ Isom + R 2 , i.e. lim ν→+∞α ν ω ν = 0. If R ων ,-αν (a) / ∈ int K for all ν ∈ N, then x ∈ #» L(a).Proof. (i) If ω ∈ L(a) ∩ T ℓ (a) + then one can choose ε = 2∠naω, where n is any point on N ℓ (a) ∩ T ℓ (a) + . If ω ∈ L(a) \ T ℓ (a) + , then ε = π suits. (ii) By contraposition, let ω / ∈ L(a) be fixed, at a distance 2d > 0 from L(a) and at a distance D/2 from a. Then, for ν large enough, ω ν is at a distance at least d from L(a) and at most D from a, hence aω ν makes an angle at least δ = arctan d D with N ℓ (a) ∩ T ℓ (a) + and with N r (a) \ T r (a) +

  r(a) = R 2 \ L(a), ℓ(a) and r(a) are the corresponding closed sectors and#» ℓ (a) = {x ∈ S 1 ; a + x ∈ ℓ(a)}.Theorem 8. Let K be a planar convex body and a 1 . . . , a n ∈ bd K.

  (i) If a 1 , ..., a n almost fix K, then both intersections ℓ(a 1 ) ∩ ... ∩ ℓ(a n ) and r(a 1 ) ∩ • • • ∩ r(a n ) are empty. (ii) If the three intersections ℓ(a 1 ) ∩ • • • ∩ ℓ(a n ), r(a 1 ) ∩ • • • ∩ r(a n ), and #» ℓ (a 1 ) ∩ • • • ∩ #» ℓ (a n) are empty, then a 1 , . . . , a n almost fix K.

  1,ν ) ∩ • • • ∩ L(a ′′ n,ν ), R(a ′ 1,ν ) ∩ • • • ∩ R(a ′′ n,ν ), or #» L(a ′ 1,ν ) ∩ • • • ∩ #» L(a ′′ n,ν ), is nonempty for all ν ∈ N. By (3), we obtain ℓ(a 1 ) ∩ • • • ∩ ℓ(a n ) nonempty in the first case, r(a 1 ) ∩ • • • ∩ r(a n ) nonempty in the second case, and #» ℓ (a 1 ) ∩ • • • ∩ #» ℓ (a n) nonempty in the last case.