1

Supplementary Material For: Global Network
Alignment In The Context Of Aging
Fazle Elahi Faisal, Han Zhao, and Tijana Milenković

✦S1

S UPPLEMENTARY METHODS

S1.1

Topological properties of our predictions

As explained in Section 3.5.2 in the main paper, weanalyze the topological position of a node in the network with respect to seven node centrality measures
as follows.
Degree centrality (DEGC) measures the degree of anode in the network, i.e., the number of the node’s
neighbors. The higher the degree of a node, the more
central the node according to DEGC.
Clustering coefficient centrality (CLUSC) measures,for a given node, how many pairs of neighbors of thenode are connected by an edge, out of all pairs of thenode’s neighbors. Intuitively, the more interconnected
the neighborhood of the node, the more central thenode is according to CLUSC.
K-core of a network is a maximal subset of nodes
in the network such that each node is connected to atleast k others in the subset. K-coreness centrality (KC)of a node is k if the node is in k-core.
Graphlet degree centrality (GDC) measures howmany graphlets a node participates in, for 2-5-nodegraphlets [1]. Intuitively, the more graphlets a node
touches, the more central the node is according toGDC. Since it captures the extended network neighborhood of a node, GDC is a sensitive measure.
Betweenness centrality (BETWC) measures the involvement of a node in the shortest paths in thenetwork. Intuitively, nodes that occur in many shortest paths have high centrality according to BETWC. BETWC of node v, Cbetwc (v), is: Cbetwc (v) =X σst (v), where V is the set of nodes in theσsts6=v6=t∈Vnetwork, σst is the number of shortest paths between
nodes s and t, and σst (v) is the number of shortest
paths between s and t that go through v.
Closeness centrality (CLOSEC) measures the “closeness” of a node to all other nodes in the network.
Intuitively, nodes with small shortest path distances
to all other nodes have high centrality according toCLOSEC. CLOSEC of node v, Cclosec (v), is: Cclosec (v) =1
P, where σ(u, v) is the shortest path distanceu∈V σ(u,v)
between nodes u and v. In a PPI network, CLOSEC

of a protein indicates the “likelihood” of the protein
to reach or be reachable from all other proteins [2].
Eccentricity centrality (ECC) is very related toCLOSEC, except that it measures the “closeness” ofa node only to the farthest node in the network [3].
Intuitively, nodes with small shortest path distances
to the furthest node in the network have high centrality according to ECC. ECC of node v, Cecc (v), is:Cecc (v) = maxu∈V 1{σ(u,v)} .

2

Supplementary Fig. S1. Biological alignment quality of different cost functions under MI-GRAAL’s alignmentstrategy. Experimental GO correctness of MI-MI-T, MI-MI-TS, Iso-MI-T, Iso-MI-TS, and X-MI-S is shown when
they are used on each pair of networks of yeast (Y), fly (F), worm (W), and human (H). In all figure, the higher
the values, the better the alignment quality.

(A)(B)(C)(D)

Supplementary Fig. S2. Overlap of new predictions from different aligners under MI-GRAAL’s alignment strategyin (A) yeast, (B) fly, (C) worm, and (D) human.
Supplementary Table S1Statistical significance (in terms of p-values) of the difference between centrality values of Complement andcentrality values of each of the following: 1) Novel-All, 2) ExpressionAge, 3) DyNetAge, and 4) GenAge, foreach centrality measure (BEWTC, CLOSEC, CLUSC, DEGC, ECC, GDC, and KC).
Data set
12
34

Novel-All
ExpressionAge
DyNetAge
GenAge

BETWC

CLOSEC

CLUSC

DEGC

ECC

GDC

KC

3.5 × 10−19
8.8 × 10−3
1.8 × 10−11
9.1 × 10−24

1.5 × 10−13
0.03
1.4 × 10−5
9.9 × 10−15

5.2 × 10−143.2 × 10−3
1.7 × 10−4
3.3 × 10−15

4.6 × 10−24
5.5 × 10−4
1.4 × 10−11
8 × 10−26

4.1 × 10−06
0.11
1.3 × 10−3
1.7 × 10−10

1.8 × 10−17
8.7 × 10−3
2.4 × 10−7
1.1 × 10−18

2.1 × 10−21
8.9 × 10−4
2 × 10−10
6.3 × 10−20

Supplementary Table S2
The number of GO terms (“N”) enriched in Novel-All, ExpressionAge, DyNetAge, GenAge, and Complement,
according to any evidence code (“any”) or experimental evidence codes only (“exp”).
Data set
Novel-AllExpressionAgeDyNetAge
GenAgeComplement

N (any)105
190
1537688N (exp)263728191
0

R EFERENCES[1] T. Milenković, V. Memišević, A. Bonato, and N. Pržulj, “Dominating biological networks,” PLOS ONE, vol. 6, no. 8, p. e23016, 2011.
[2] G. Scardoni, M. Petterlini, and C. Laudanna, “Analyzing biological network parameters with centiscape,” Bioinformatics, vol. 25, no. 21,
pp. 2857–2859, 2009.
[3] S. Wuchty and P. F. Stadler, “Centers of complex networks,” Journal of Theoretical Biology, vol. 223, no. 1, pp. 45–53, 2003.