Protein Complex Prediction based on
Mutually Exclusvie Interactions in PPIN
Suk-hoon Jung, Woo-hyuk Jang, Dong-soo Han
Information & Communications UniversityContents
 Background Method– Mutually Exclusive Interaction (MEI)– Simultaneous Protein Interaction Cluster (SPIC) Evaluation
 Result Conclusion

Page  2

Background Protein complex– Molecular component playing crucial roles in cellular process.
– A group of two or more associated proteins formed by protein-protein
interaction that is stable over time Protein-Protein Interaction network (PPIN)– Static representation of the union of protein-protein interactions– Visualized with edges (interactions) and nodes (proteins).

 Protein complex prediction via PPIN clustering– Protein complexes often correspond to dense regions in PPIN– MCODE, LCMA, RNSC, STM…
Page  3

Network clustering on PPIN

Page  4

Network clustering on PPIN Issues– Protein complexes are stable– Interactions are mainly dynamic• so network clusters may include dynamic/unstable interactions
Page  5

Network clustering on PPIN Issues– Protein complexes are stable

Mismatched– Interactions are mainly dynamic• so network clusters may include dynamic/unstable interactions
Page  6

Network clustering on PPIN Clustering must exclude unstable/dynamic interactions tocorrespond with protein complex
 Elucidating dynamic nature of interactions is difficult, butexclusion of unstable interactions may partly be possible
 Idea: eliminating Mutually Exclusive Interactions(MEI) as arefinement process excluding unstable interactions beforeclustering

Page  7

Mutually Exclusive Interactions (MEI) Clues– Most proteins can interact with several alternative interaction partners
mediated by the same interface, and such interactions are likely to be
mutually exclusive (Hu et al, 2005)– Several proteins are reported to have MEI partners

 Only one of MEI can be activated at a time
– Activation of an interaction guarantees deactivation of other interactions– Interactions are in competition for protein complex formation.

 By eliminating MEI, it is able to extract stable clusters which
are more likely to be protein complexes
Page  8

Mutually Exclusive Interactions
 Computational MEI identification using interface data of proteins– Interface: contact surface of protein interaction pair
P1

Common interfaces
P2

P3

P1

Only one of interactions isactivated at a moment
P1

P2

P3Interface

Such interactions are
Mutually Exclusive

P2P3

Page  9

MEI identification
 Interfaces are extracted at the domain level– Protein domain is evolutionary conserved unit of functional and structure– Domain-domain interactions are regarded as the mediator of PPI– Many proteins share a domain, so a domain-domain interface may generate anumber of protein-protein interfaces

 By analyzing 3D structures recorded in Protein Data Bank (PDB)– PSIMAP( park et al ,2001) detects interfacial residues between domains
3D structures in PDBd1 :
d2 :
d3 :
d4 :

PSIMAPHHRDSASDFEWETDVPMGQHNFQASDFAVERVEREFXADSFADNGKISTTDVPMGQHERFFEWFTLRTOTMHBTE
HHWEFNMAGEISNDOFKENSLEOFMTLRTKSQKKRFEHASDFASSDSTTDVPMSDFAADSFEERFELRTKSASDA

Overlapped on d3
Page  10C

i t fi l

MEI identification

d1d3

d2

d4+d2 and d4 are in competition

for the interaction with d3
d1
d2
d3
d4orProtein
Domaind3d3{ d1, (d2 or d4) }d3+Many PPIs inherit interactions from aMEI

domain-domain interaction+so such a mutually exclusive domain-domain Interactions may generate many
PPIs having MEI feature

Page  11

Simultaneous Protein Interaction Cluster (SPIC) The cluster that excludes Mutually Exclusive Interactions

Page  12

Simultaneous Protein Interaction Cluster (SPIC) The cluster that excludes Mutually Exclusive Interactions
PPIN

Clustering

Cluster

Page  13

Simultaneous Protein Interaction Cluster (SPIC) The cluster that excludes Mutually Exclusive Interactions
PPIN

MEI

Clustering

Cluster

Page  14

Simultaneous Protein Interaction Cluster (SPIC) The cluster that excludes Mutually Exclusive Interactions
PPINMEIClustering

Cluster+Protein complex cannot haveboth of those interactions

Page  15

Simultaneous Protein Interaction Cluster (SPIC) The cluster that excludes Mutually Exclusive Interactions
Sub-networks

PPIN

MEI

MEI
Exclusion

Only one interaction is chosen
between MEIPage  16

Simultaneous Protein Interaction Cluster (SPIC) The cluster that excludes Mutually Exclusive Interactions
Sub-networks

PPIN

SPIC

MEI

MEI
Exclusion

PostClustering

Clusters without MEI,
More stable.
Only one interaction is chosen
between MEIPage  17

Evaluation
Proposed approach (SPIC based)
Sub-networks

Conventional methodPPINMEI
Exclusion

SPIC

PostClustering

Clustering

ClusterComparison

Knowncomplexes
Page  18

Evaluation
Proposed approach (SPIC based)
Sub-networks

Conventional method

PPIN

MEI
Exclusion

Clustering

Cluster

SPIC

PostClustering Proposed approach deals with networkrefinements, so post-clustering borrows
conventional algorithms, MCODE and LCMA
 Comparisons for two clustering algorithms
 MCODE
Comparison
vs. SPIC_MCODE LCMA vs. SPIC_LCMA
Known Parameters are the same forcomplexes
conventionaland SPIC based

Page  19

Evaluation
Sub-networks

PPINSPIC

MEI

MEI
ExclusionPostClustering

Clustering

 yeast PPIN from MIPS
Cluster

 5,668 proteins 29,683 interactions

Page  20

Evaluation
Sub-networks

PPINSPICMEIMEI
Exclusion

PostClustering

Clustering

 PSIMAP analyzes 3D structures form PDB
 64985 domain-domain interfaces from14594 PDB entity

Cluster Our computation detects 3512 pairs ofoverlapping interfaces on domains

Page  21

Evaluation
Sub-networks

PPIN

SPIC

MEI

MEI
Exclusion

PostClustering

Clustering

Cluster In MEI Exclusion process, generating subnetwork spends a lot of computational cost
- n-MEIs generate at most 2n sub-networks- So, split PPIN into small sub network to reducethe cost- Using original clustering methods with moderate
thresholds

Page  22

Evaluation
Sub-networks

PPIN

SPIC

MEI

MEI
Exclusion

PostClustering

Clustering

In MEI
used with moderate
thresholds Twopost-clustering
algorithms,
respectively

Cluster SPIC_MCODE SPIC_LCMAPage  23

Evaluation
Sub-networks

PPIN

SPIC

MEI

MEI
Exclusion

PostClustering

Clustering Identical results are trimmedCluster Two set of results
 SPIC_MCODE found 176 SPICs
 SPIC_LCMA found 3217 SPICs

Page  24

Evaluation
Sub-networks

PPIN

SPIC

MEI

MEI
Exclusion

PostClustering

Clustering Identical results are trimmed
 Two set of results

Cluster SPIC_MCODE found 176 SPICs
 SPIC_LCMA found 3217 SPICs

Page  25

Evaluation
Sub-networks

PPIN

SPIC

MEI

MEI
Exclusion

PostClustering

Clustering

 For
In MEI
comparison
used withwith
moderate
proposedthresholds
methods
Cluster

Page  26

 Clusters generated by conventional
methods include Mutually Exclusive
Interactions

Evaluation
Sub-networks

PPIN

SPIC

MEI

MEI
Exclusion

PostClustering

Clustering MCODE
found140
clustersthresholds
In MEI usedwithmoderate 11 clusters have one or more MEIs
 Total number of MEIs : 620
 LCMA found 2737 clusters
 238 clusters have one or more MEIs
 Total number of MEIs : 4431

ClusterPage  27

Evaluation
Sub-networks
PPIN are compared with 267
 Results
known yeast
complexes from MIPS
MEIvs. SPIC_MCODE- MCODEMEI- LCMA vs. SPIC_LCMAPostExclusion
Clustering Overlapping Score(OS) determines how effectively apredicted cluster(Pc) matches a known complex(Kc)Clustering

OS (Pc, Kc ) =| Pc ∩ Kc |2| Pc,| • | Kc |Cluster

MIPS Yeast
267 manually curated
Known complexes

Page  28SPIC

Result: Conventional vs. SPIC_based methods
MCODE
MCODE

# clusters found# identical clusters# unique clusters# clusters with MEILCMASPIC_MCODE

LCMA

176

2737

140
139
1111

SPIC_LCMA

3217
2499

370

238
238

7180 Since SPIC based approaches borrow conventionalalgorithms with the same parameters for post-clustering– Each SPIC cluster is a sub-cluster of one of the conventional results.
– Many SPIC clusters are identical with conventional results.
– Only conventional clusters having MEI are split into SPIC clusters, sothey are refined– Splitting leads to improvement in SPIC_based prediction
Page  29

Number of matched MIPS

Results: MCODE vs. SPIC_MCODE

overlapping score threshold Overall, SPIC_MCODE outperforms original MCODE All refined clusters have higher overlapping scores than corresponding
conventional clusters

Page  30

Number of matched MIPS

Results: LCMA vs. SPIC_LCMA

overlapping score threshold0 Overall, SPIC_LCMA outperforms original LCMA Refined clusters have higher overlapping scores than correspondingconventional clusters except one case.

Page  31Refinement effect Trimming/ splitting over-predicted clusters

known Complex– 16 cases for MCODE– 74 case for LCMA

LCMA predicted
SPIC_LCMA predicted

YER111C, YDL074C, YGR104C, YOL122C, YEL036C,, YGL167C,YDL246C, YJR142W, YLR342W, YDR414C, YBR200W, YGL215W,YMR306W, YPL075W, YNL271C, YLR425W, YGR078C, YLR371W,YJR075W, YJL101C, YOL020W, YPL254W, YML115C,, YHL028W,YCR081W, YOL119C, YML122C, YJR073C, YNL199C, YDR150W,
YPL161C, YLR360W, YBR260C, YOR106W, YDR456W, YOR008C,
YGR157W, YDR207C, YNL298W, YNL079C, YJL095W, YJR159W,
YOR014W, YGR161C, YER096W, YLR372W, YMR212C, YNL201C,
YBR081C, YHR063C, YLR200W, YDR473C, YER155C, YDR245W,
YHR030C, YGL015C,,YER049W, YPL253C, YMR307W, YNL323W,YGR229C
YDL179W, YER059W,YHR071W, YIL050W,YOR140W
YDR443C,YPL042C,YHR012W,
YJL154C,

YNL025C,YCR081W

YJL053W

Page  32

YNL289W,
YOL001W,
YPL031C, YDL127W,
YGL134W,
YPL219W,

XYDR118w

X

YDL008w

X

YFR036w
A.

YNL172w

YGL240w

YLR127c
YFL039c

YBL084c
YKL022c

YHR166c

Conclusion
 We propose the SPIC based approach for protein complex prediction– To eliminate unstable interactions in PPI network clusters using Mutually
Exclusive Interactions (MEI) .
– MEIs are identified by 3D analysis on PDB entity.

 Comparison with two conventional algorithms, MCODE and LCMA,
showed that proposed approach– outperforms conventional methods.
– rarely has adverse effects– correctly predicts what conventional method does and additional complexes
more.

 The more stable a cluster is, the more likely it is to correspond with protein
complexes.

Page  33