1.1 Alignment of PPI networks of human, yeast, fly

Table S1 lists the functional consistency (i.e., the percentage of
aligned proteins sharing common GO terms) of all the pairwise
alignments generated by six different methods: HubAlign,
IsoRank, PISwap, MI-GRAAL, GHOST and NETAL. The humanyeast alignment is already presented in the main paper, so it is not
included in this section.
worm-fly
Alignment of PPI networks of human, yeast, fly,
worm and mouse
mouse-yeast
1.1
mouse-worm
NETAL
HubAlign
79.27
63.93
34.51
80.65
>=2
39.19
14.61
55.96
48.58
6.1
60.36
>=3
29.78
6.87
40.84
38.96
1.59
52.53
>=4
23.88
2.79
27.57
31.20
0.5
45.49
>=5
19.18
1.24
19.25
26.37
0.16
38.26
>=1
24.85
0
34.11
25.11
11.92
43.52
>=2
13.05
0
17.74
13.19
1.64
27.02
>=3
7.67
0
8.93
7.68
0.43
16.43
>=4
4.28
0
4.26
4.15
0.15
9.34
>=5
2.24
0
1.96
2.08
0.07
4.90
>=1
38.02
24.34
48.69
37.95
21.43
50.18
>=2
16.64
6.00
24.12
16.60
2.42
30.67
>=3
8.32
2.13
12.11
7.90
0.35
18.76
>=4
3.61
0.76
5.08
3.20
0.07
9.95
>=5
1.50
0.11
2.01
1.39
0.0
4.97
>=1
16.11
0
21.98
16.25
8.04
32.87
>=2
7.28
0
10.88
7.30
0.77
19.55
>=3
4.24
0
5.34
4.19
0.14
11.57
>=4
2.02
0
2.29
1.97
0.02
5.71
>=5
0.78
0
0.81
0.81
0.0
2.50
>=1
43.39
27.8
44.14
42.07
17.7
54.20
>=2
21.39
7.09
20.72
20.65
2.77
31.00
>=3
12.06
1.93
10.67
11.77
0.92
18.13
>=4
5.89
0.57
4.19
5.83
0.4
9.01
>=5
2.78
0.15
1.86
2.72
0.34
4.76
worm-yeast
PISwap
46.18
mouse-fly
GHOST
61.30
Average over all
alignments
MI-GRAAL
>=1
#shared GO
terms
IsoRank
fly-yeast
human-worm
human-fly
human-mouse
alignment
Table S1: Comparison between HubAlign and the others in terms of functional consistency of the alignments. MI-GRAAL and GRAAL do not
produce any results for human-fly and yeast-fly alignment.
>=1
37.63
13.85
43.77
36.91
8.01
44.66
>=2
20.52
3.71
23.40
19.84
1.29
27.66
>=3
9.95
1.39
11.07
9.56
0.41
16.05
>=4
3.94
0.78
4.74
3.90
0.36
8.00
>=5
2.01
0.43
2.04
2.01
0.32
4.14
>=1
33.09
26.73
44.26
33.17
19.0
49.28
>=2
9.74
5.79
19.9
10.13
2.12
26.57
>=3
4.83
1.79
10.35
4.99
0.56
16.40
>=4
2.35
0.67
4.53
2.47
0.34
8.37
>=5
1.23
0.23
1.56
1.19
0.26
4.74
>=1
21.96
14.56
26.12
22.01
12.95
27.49
>=2
6.98
2.59
10.44
6.87
1.61
13.58
>=3
3.49
0.59
4.93
3.38
0.45
7.64
>=4
1.20
0.14
1.86
1.27
0.26
3.83
>=5
0.54
0.03
0.73
0.65
0.22
2.13
>=1
31.82
23.71
39.69
31.97
12.91
48.67
>=2
19.01
6.91
20.75
18.88
2.09
31.58
>=3
11.85
2.71
10.57
11.18
0.57
21.39
>=4
6.70
0.88
5.33
6.84
0.47
13.89
>=5
4.08
0.34
2.34
4.02
0.47
7.92
>=1
34.24
19.68
42.44
34.37
16.27
47.72
>=2
17.08
5.18
22.65
18.00
2.31
29.77
>=3
10.24
1.93
12.75
11.06
0.60
19.87
>=4
5.98
0.73
6.65
6.75
0.28
12.62
>=5
3.81
0.28
3.61
4.58
0.20
8.25
90
80
70
60
50
40
30
20
10
0
(a)
9000
8000
7000
6000
5000
4000
3000
2000
1000
0
(b)
S.Hashemifar et al.
60
50
40
30
20
10
0
(c)
Fig. S1: Performance of HubAlign and the other methods in terms of EC
(a), LCCS (b) and
(c) of the alignments. MI-GRAAL and GRAAL do
not produce any result for human-fly and yeast-fly alignment.
1.2
Alignment of bacterial PPI networks
In terms of functional consistency (FC), HubAlign has a much
larger advantage over IsoRank, MI-GRAAL, NETAL and PISwap
and a small advantage over GHOST. HubAlign cannot obtain a
larger advantage over GHOST possibly because it is very challenging to align these two PPI networks. As shown in Table S2, although both species are bacteria, the absolute FC of all the alignments is not very big (<50%). This may be due to that these two
PPI networks are very sparse. On average, each protein in these
two networks has 4-6 PPIs. By contrast, in the yeast PPI network
each protein has on average 20 PPIs.
Fig. S2: Performance of HubAlign in term of S3(a) and LCCS(b) of the
alignments for different values of λ between 0 and 1 in increment of 0.1.
1.3
IsoRank
MI-GRAAL
GHOST
PISwap
NETAL
HubAlign
#shared GO
terms
Table S2: Functional consistency of the bacterial network alignments
generated by five methods.
20.10
29.6
46.69
17.93
21.62
46.82
3.29
12.7
33.07
5.41
7.97
35.79
2.86
6.48
23.15
2.45
3.08
28.01
0.20
4.44
17.04
0.51
1.93
21.40
0.0
2.92
12.08
0.12
1.28
17.12
Evaluation of parameters λ and α
As shown in Fig. S2, AFS increases as λ gets close to 1, while
and LCCS decrease. As mentioned in main paper, we believe
the reason could be that the higher values of λ give more importance to the edge weights which in turn, makes the proteins
with important interactions align together. As shown in Fig. S3,
increasing α from 0 to 1 decreases AFS, while
and LCCS increase. This is because a larger value of α decreases effect of the
sequence information.
1.4
Pure topological comparison
In this section, we do a comprehensive pure topological based
(i.e. α=1) evaluation of the HubAlign against the other methods in
pure topological setup i.e. MI-GRAAL, NETAL and GHOST. We
ran NETAL with the default parameters. MI-GRAAL was run
using degree, signature similarity and clustering coefficient. For
GHOST we set
and
to do a purely topological
alignment. As shown in Table S3, the alignment produced by HubAlign greatly outperforms the other methods in 5 out of 10
alignments (i.e. mouse-yeast, mouse-fly, mouse-worm, worm-yeast
and worm-fly) and slightly outperforms them for the remaining 5
alignments. This result indicates that our algorithm can yield biologically meaningful alignment more efficiently than the others,
even without using sequence information. Moreover table S4
shows that the alignment produces by HubAlign outperforms those
by the other methods in terms of AFS under all three categories
BP, MF and CC. HubAlign also produces alignments with larger
EC and LCCS than the other algorithms (see Fig. S4). These results indicate that HubAlign in pure topological based setup is able
to align more functionally similar proteins and find larger complexes that are significant either topologically or biologically.
mouse-worm
worm-yeast
worm-fly
human-mouse
human-worm
fly-yeast
human-fly
yeast-human
0.40
0.36
0.50
CC
mouse-fly
0.63
0.61
0.57
0.68
BP
0.35
0.48
0.50
0.56
MF
0.34
0.34
0.33
0.39
CC
0.38
0.35
0.34
0.41
MF
0.35
0.35
0.31
0.38
CC
0.27
0.25
0.25
0.27
BP
0.27
0.27
0.26
0.29
MF
0.22
0.21
0.23
0.24
CC
0.23
0.24
0.24
0.26
BP
0.28
0.29
0.31
0.33
MF
0.15
0.17
0.18
0.18
CC
0.12
0.13
0.13
0.14
BP
0.67
0.67
0.73
0.73
MF
0.72
0.71
0.70
0.72
CC
0.74
0.73
0.66
0.75
BP
0.38
0.39
0.40
0.41
MF
0.32
0.31
0.23
0.34
CC
0.25
0.23
0.25
0.26
BP
0
0.35
0.38
0.39
MF
0
0.23
0.23
0.25
CC
0
0.35
0.36
0.36
BP
0
0.40
0.41
0.41
MF
0
0.28
0.28
0.28
CC
0
0.30
0.30
0.31
BP
0.58
0.58
0.58
0.59
MF
0.46
0.45
0.46
0.46
CC
0.70
0.69
0.71
0.70
>=1
37.17
35.37
34.51
37.96
>=2
7.23
7.29
6.1
7.54
>=3
2.28
2.24
1.59
2.76
>=4
0.80
0.67
0.5
1.23
>=5
0.20
0.42
0.16
0.49
>=1
22.84
20.57
19.0
26.34
>=2
1.97
2.08
2.12
2.80
0.64
Alignment
#shared GO
terms
HubAlign
0.46
0.47
NETAL
MF
0.42
GHOST
0.57
0.43
MI-GRAAL
0.47
human-mouse
0.50
HubAlign
GHOST
0.53
NETAL
MI-GRAAL
mouse-yeast
BP
AFS
alignment
Table S3: Performance of HubAlign and the other methods in terms of AFS of the alignments in categories BP,
MF and CC in the pure topological setup. MI-GRAAL
does not produce any result for human-fly and yeast-fly
alignment.
0.42
Table S4: Performance of HubAlign and the other methods in terms of
functional consistency in the pure topological setup. MI-GRAAL does not
produce any result for human-fly and yeast-fly alignment.
mouse-yeast
Fig. S3: Performance of HubAlign in term of S3(a) and LCCS(b) of the
alignments for different values of α between 0 and 1 in increment of 0.1.
BP
>=3
0.29
0.21
0.56
>=4
0.04
0.24
0.34
0.38
>=5
0.0
0.0
0.26
0.30
S.Hashemifar et al.
>=2
>=3
human-worm
human-fly
>=4
0
0
0
0
7.56
8.04
9.50
0.63
0.77
0.12
0.14
0.02
0.02
0.02
0.79
0.15
0.05
>=5
0
0.0
0.0
>=1
0
11.75
11.92
12.36
>=2
0
1.78
1.64
2.25
>=3
0
0.37
0.43
0.65
>=4
0
0.14
0.15
0.18
>=5
0
0.03
0.07
0.07
>=1
19.87
19.91
21.43
21.46
>=2
1.38
2.11
2.42
2.56
>=3
0.0
0.31
0.35
0.56
>=4
0.0
0.0
0.07
0.15
0.0
>=5
0.0
0.0
0.0
>=1
21.73
21.51
17.7
22.01
>=2
2.47
2.24
2.77
2.77
>=3
0.85
0.28
0.92
0.98
>=4
0.22
0.11
0.4
0.50
>=5
0.17
0.05
0.34
0.41
>=1
6.89
8.21
8.01
9.18
>=2
0.76
0.77
1.29
1.47
>=3
0.13
0.04
0.41
0.48
>=4
0.04
0.0
0.36
0.20
>=5
0.0
0.0
0.32
0.05
>=1
11.70
11.27
12.95
13.13
>=2
0.86
0.57
1.61
1.69
>=3
0.11
0.07
0.45
0.54
>=4
0.03
0.03
0.26
0.04
>=5
0.0
0.0
0.22
0.0
>=1
13.12
12.48
12.91
15.94
>=2
2.27
2.38
2.09
3.15
>=3
0.93
0.49
0.57
0.87
>=4
0.31
0.14
0.47
0.34
>=5
0.05
0.09
0.47
0.09
>=1
25.59
24.78
26.03
26.08
>=2
2.67
2.31
2.95
2.97
>=3
0.55
0.37
0.67
0.42
>=4
0.14
0.08
0.24
0.18
>=5
0.06
0.0
0.14
0.02
>=1
Average over all
alignments
fly-yeast
>=1
>=2
15.89
1.96
17.34
17.25
19.39
2.21
2.37
2.80
0.79
>=3
0.51
0.45
0.60
>=4
0.15
0.14
0.28
0.32
0.05
0.19
0.14
>=5
0.04
100
90
80
70
60
50
40
30
20
10
0
12000
yeast-human
mouse-fly
worm-yeast
worm-fly
mouse-worm
10000
8000
6000
4000
2000
0
(b)
Fig. S4: Performance of HubAlign and the other methods in terms of EC
(a) and LCCS (b). MI-GRAAL does not produce any result for human-fly
and yeast-fly alignment.

Download Report