Assessing and Predicting Protein
Interactions Using Both Local andGlobal Network Topological Metrics
Guimei LiuSingapore
Jinyan LiUniversity
Limsoon Wong
Singapore

National University ofNanyang Technological
National University of1

Outliney Backgroundy Related worky Our method
y Local network topological metricy Global network topological metricy Experimentsy Summary2

Backgroundy Protein-protein interactions play a critical role in mostcellular processes and form the basis of biologicalmechanisms.
y High-throughput experimental techniques enable thestudy of protein-protein interactions at the proteome
scale.
y However, high-throughput protein interaction data areoften associated with high false positive and false
negative rates
y limitations of the associated experimental techniques
y dynamic nature of protein interaction maps
3y…

Computational methodsy A weight is assigned to each interaction such that thehigher the weight is, the more likely the interaction istrue
y Various Information have been usedy 3D protein structuresy co-evolution
y co-localizationy gene fusion
y literature
y network topology
y protein domains/motifs
4y…

Methods based on network topology
y Represents PPI networks as undirected graphs, where vertices are proteins, and edges

represent interactions between proteins.

y IG1 [Saito et al. 2002]y The first one on evaluating the reliability of PPIs using solely PPI network topology
y Mainly for PPI data generated by yeast-two-hybrid experimentsy Given a protein pair (u,v), IG1 is calculated based on the number of proteins that interact

with and only with either u or v

y IG2 [Saito et al. 2002]
y Uses 5 local network motifs
y Performs better than IG1

y IRAP [Chen et al. 2005]
y the collective reliability of the strongest alternative path between two proteinsy Expensive to computey CD-distance [Brun et al. 2003] and FSWeight [Chua et al. 2006]
yyyy

Based on the number of common neighbors of two proteins
Easy to compute
They are initially proposed for function prediction
Outperforms the previous three methods on large PPI networks [Chen et al. 2006]

5CD-distancey Given a pair of proteins (u, v) in a PPI network G=(V,E)
y Nu: the set of neighbors of u in G
y Nv: the set of neighbors of v in G

y CD (u,v) =2 | Nu ∩ Nv || Nu | + | Nv |y Consider relative intersection size of the two neighborsets, not absolute intersection sizey Case 1: |Nu| = 1, |Nv |= 1, |Nu∩Nv|=1, CD(u,v)=1
y Case 2: |Nu| = 10, |Nv |= 10, |Nu∩Nv|=10, CD(u,v)=16

FSWeighty Try to overcome the weakness of CD-distancey FS(u,v) =2 | Nu ∩ Nv |2 | Nu ∩ Nv |×| Nu | + | Nu ∩ Nv | + λ u | N v | + | Nu ∩ Nv | + λ v

Where λu and λv are used to penalize those proteinswith very few neighbors∑| N |∑| N |
λu = max{0,}, λv = max{0,−| N |−| N ||V ||V |}y Suppose the average degree is 4, thenxx∈Gxux∈Gvy Case 1: |Nu| = 1, |Nv|= 1, |Nu∩Nv|=1, FS(u,v)=4/25=0.16
7y Case 2: |Nu| = 10, |Nv |= 10, |Nu∩Nv|=10, FS(u,v)=1

Our methody CD-distance and FSWeight are local metrics
y We use both local and global network topologicalmetricy Local metricy a variant of CD-distancey Computed iterativelyy Global metricy Computed using interacting protein group pairsy These two metrics are combined to get the final score of

an interaction

8

Local topological metricy A variant of CD-distance which penalizes proteins

with few neighbors
2 | Nu ∩ Nv || Nu | + λ u + | Nv | + λ v

wL(u,v) =∑| N |∑| N |
λu = max{0, | V | − | N | }, λv = max{0, | V | − | N |}(same as in FSWeight)
y Iterate local topological metricxxx∈Gx∈Guv

y Motivation: the weight of an interaction reflects its

reliability, so can we get better results if we use thisweight to re-calculate the score of other interactions?

9Iterate local metricy wL0(u,v) = 1 if (u,v)∈G, otherwise w0(u,v)=0| Nu ∩ Nv | + | Nu ∩ Nv || Nu | + λ u + | Nv | + λ v

y wL1 (u,v) =y wLk (u,v) =∑w∑wx∈Nuy λky λk
10∑ w ( v, x )(u, x) + λ + ∑ w (v, x) + λk −1Lx∈Nu ∩ Nvk −1Lu = max{0,v = max{0,k −1L(u, x) +kux∈Nu ∩ Nv
k −1Lkx∈Nv∑ ∑w

k −1L( x, y )x∈V y∈Nx

|V |

∑ ∑w

k −1Lx∈V y∈Nx

|V |− ∑ wLk −1 (u , x)}x∈Nu( x, y )− ∑ wLk −1 (v, x)
x∈Nv}

v

Global topological metricy Observation:y if one group of proteins interact with another group ofproteins, then it is likely that the interaction between these two
protein groups is mediated by an underlying complementarybinding domain/motif pair.
y In a protein pair participates in an interacting group pair, thenthe interaction between them is likely to be true

11

Calculating global topologicalmetricy Three steps:y Step1: generate protein groups that have common

interacting partners
y Step 2: calculate the interacting score of the generated
protein groupsy Step 3: calculate the global topological score of a proteinpair12

Step 1: generate protein groupsy A protein group is considered if ity Contains at least s proteins
y Its members have at least t common interacting partners
y The adjacency matrix of an undirected graph can beregarded as a transaction databasey Each adjacency list is a transaction
y Each protein is an item

⇒finding protein groups can be mapped to finding

13

frequent itemsets that contain at least s items andappear in at least t transactions.
⇒We use a frequent itemset mining algorithm to findqualified protein groups

Step 2: calculate interaction
score of protein groupsy Let V1 and V2 be two protein groups generated in Step

1, the interacting confidence score of V1 and V2 isdefined as# interactions between V 1 and V 2# possible protein pairs between V 1 and V 2conf(V1, V2 ) =y Example

y #interactions: 10y #possible protein pairs: 12y conf(V1, V2 ) = 10/12 = 0.833
V114V2

Step 3: calculating global metricscore
y The global interacting score of a protein pair iscomputed based on the interacting confidence score ofthe interacting group pairs it participates in and thedegree of its participationy Given a protein pair (u,v)
2 | Nu ∩ V 2 | 2 | Nv ∩ V 1 |×| u ∈ V 1, v ∈ V 2}
wG(u,v)= max{conf (V 1,V 2) ×| Nu | + | V 2 | | Nv | + | V 1 |2 | Nu ∩ V 2 |is u’s participation degree in interacting
protein group pair (V1, V2 )y 2 | Nv ∩ V 1 | is v’s participation degree in (V1, V2 )y | Nu | + | V 2 || Nv | + | V 1 |15Combine local metric and global
metricy The final score of a protein pair (u,v) is defined as thesum of its local metric score and global metric score
LGTweight(u, v) = wkL(u, v) + wG(u, v)

16

Experiments
y PPI dataset: DIP yeast (dated 07-Oct-2007)
y 4932 proteins and 17491 interactionsy Core dataset: 6459 interactions

y Evaluation methods:
y Functional homogeneity
y Use Gene Ontology (GO) annotationsy Localization coherence
y use Gene Ontology (GO) annotations
y 5-fold cross validationy DIP core dataset

17

GO annotations
y Select only informative GO terms.
y A GO term is informative if no less than 30 proteins areannotated with that term, and none of its descendantterms has at least 30 proteinsy 50 molecular function terms and 110 biologicalprocess terms
y 3251 proteins and 11229 interactions have functionalannotations.
y 42 cellular component terms
y 1615 proteins and 4246 interactions have cellularcomponent annotations
18

Functional Homogeneityy Given a set of protein pairs, its functional homogeneity

is defined as# protein pairs sharing same function annotation# protein pairs that have function annotationsy Similarly, localization coherence is defined as# protein pairs sharing same localization annotation# protein pairs that have localization annotations

19

Experiment 1: the effect of k to
local metricy Assessing the reliability of PPIs in DIP dataset

0.90.80.70.6
0.501000

2000
3000
4000
#interactions

5000

Functional homogeneity
20

1

k=1
k=2
k=10
k=50

Localization coherence

Functional homogeneity

1

6000

k=1
k=2
k=10
k=50

0.95
0.9
0.85
0.8
0.75
0.70500

1000
1500
2000
#interactions

2500

Localization coherence

3000

The effect of k to local metricy Predicting new PPIs
1

k=1
k=2
k=10
k=50

0.8

Localization coherence

Functional homogeneity

1
0.9

0.7
0.6
0.5
0.4
0.301000

2000
3000#predicted interactions

4000

0.8
0.7
0.60.5

5000

k=1
k=2
k=10
k=500.90

Functional homogeneity

1000

2000
3000
#predicted interactions

4000

5000

Localization coherence

21Experiment 2: comparing
different scoring methodsy Assessing the reliability of PPIs in DIP datasety For global topological metric, we set s=5, t=1

0.9
0.8
0.7
0.6
0.5

22

1

LGTweight
Local score (k=2)
Local score (k=1)
Global score
FSweight
CD-distance

Localization coherence

Functional homogeneity

101000

2000

3000

4000

5000

6000

LGTweight
Local score (k=2)
Local score (k=1)
Global score
FSweight
CD-distance

0.95
0.9
0.85
0.8
0.75
0.7

05001000

1500

2000

2500

#interactions#interactions

Functional homogeneity

Localization coherence

3000Comparing different scoring
methodsy Predicting new PPIs
LGTweight
Local score (k=2)
Local score (k=1)
Global score
FSweight
CD-distance

0.8
0.6
0.4
0.2
0200

400

600

800

LGTweight
Local score (k=2)
Local score (k=1)
Global score
FSweight
CD-distance

1.2
Localization coherence

Functional homogeneity

11000#predicted interactions

Functional homogeneity

10.8
0.6
0.4
0.2

0200

400600800#predicted interactions

Localization coherence

23Experiment 3: 5-fold crossvalidationy Use the DIP core dataset as the golden standard
y Divide the proteins in the DIP full yeast dataset into 5disjoint groups.
y For each group of proteinsy Training data: remove the interactions between proteinsin the group, and use the remaining interactions as
training datay Testing data: all the protein pairs within this groupy Correct answer PPIs: the pairs of proteins in the groupthat are in the core dataset

2410005-fold cross-validationy Average number of proteins in 5 groups: 986
y Average number of interactions in 5 training datasets:

16723
y Average number of interactions in 5 testing datasets:
486591y Average number of correct answer interactions: 307
y Measures:y sensitivity =TP/(TP + FN)
y specificity =TN/(TN + FP)
y #negatives >> #positives, specificity is always very highy >97.8% for all scoring methods
25

y precision =TP/(TP + FP)

5-fold cross-validation
1

LGTweight
Local score (k=2)
Local score (k=1)
Global score
FSweight
CD-distance

Precision

0.8
0.6
0.4
0.2
026

0

0.1

0.2
0.3
Sensitivity

0.4

0.5

Summary and Conclusiony Assessing the reliability of PPIsy CD-distance, FSWeight, and Local metric show similarperformancey Iterating local metric can improve the performance slightly
y Predicting new interactionsy CD-distance is not good at predicting new interactionsy Iterating local metric can improve the performance

significantly
y CD-distance and FSWeight can also be iterated, and27

they show similar improvement as local metricy The global metric does not improve the performancemuch, but if an interaction has both high local metricscore and high global metric score, then the interaction

Q&A
y Thank you for your attention

28Rank difference and score
differencey Given an interaction (u,v), the rank difference of (u,v)

atk-th iteration is
rank_diff k(u,v) = |rankk(u,v)-rankk-1(u,v)|
y Given a set of interactions E, the average ranking
difference of all the interactions in E at k-th iteration isdefined as∑ | rank k (u, v) − rank k −1 (u, v) |( u ,v )∈E|E|

avg_rank_diff k(E) =y Similarly, we can define average score difference of all
the interactions in E at k-th iteration| score k (u , v) − score k −1 (u , v) |∑( u ,v )∈E

29|E|

avg_score_diff k(E) =Results on the DIP dataset
0.2

CD-distance
FSWeight
Local metric800

average score difference

average rank difference

1000

600
400
200
00102030
iteration no.

Rank difference
304050CD-distance
FSWeight
Local metric

0.15

0.1

0.05

0010203040

iteration no.

Score difference50