Comparative Analysis of Networks

Ananth Grama Coordinated Systems Lab and, Computer Science Department,

Purdue University

http://www.cs.purdue.edu/people/ayg

This work is supported by National Institutes of Health, National Science Foundation, Department of Energy, Intel and Microsoft.

Ananth Grama 2001/01/27

Outline

• Interaction Networks

– Modeling, evolution, problems, practical implications

• Algorithms for Analyzing Interaction Networks

– Analyzing biological networks for conserved interaction patterns

– Pairwise Alignment of networks

– Probabilistic models/analyses for assessing statistical significance

• Computational Synthesis of Interaction Networks

– Inferring function from domain co-evolution

Ananth Grama 2001/01/27

Conserved Interaction Patterns

• Given a collection of interaction networks, find sub-networks that are common to an interesting subset of these networks [Koyut^{}ürk,

Grama, & Szpankowski, ISMB, 2004]

– A sub-network is a group of interactions that are tied to each other (connected)

– Frequency: The number of networks that contain a sub-network, is a coarse measure of statistical significance

• Computational challenges

– How to relate nodes (proteins) in different networks (organisms)?

– Requires solution of the intractable subgraph isomorphism problem

– Must be scalable to potentially large number of networks

– Networks are large [in the range of 10K edges]

Ananth Grama 2001/01/27

Graph Analysis

Network database

Interaction patterns that are common to all networks

Ananth Grama 2001/01/27

Problem Statement

• Given a set of proteins V, a set of interactions E, and a manyto-many mapping from V to a set of ortholog groups L = {l_{1}, l_{2}, ..., l_{n}}, the corresponding interaction network is a labeled graph G = (V, E, L).

– v ∈ V (G) is associated with a set of ortholog groups L(v) ⊆ L.

– uv ∈ E(G) represents an interaction between u and v.

• S is a sub-network of G, i.e., S ⊑ G if there is an injective mapping ϕ : V (S) → V (G) such that for all v ∈ V (S), L(v) ⊆ L(ϕ(v)) and for all uv ∈ E(S), ϕ(u)ϕ(v) ∈ E(G).

Ananth Grama 2001/01/27

Computational Problem

• Conserved sub-network discovery

– Instance: A set of interaction networks G = {G_{1} = (V_{1}, E_{1}, L), G_{2} = (V_{2}, E_{2}, L), ..., G_{m} = (V_{m}, E_{m}, L)}, each belonging to a different organism, and a frequency threshold σ^{∗}.

– Problem: Let H(S) = {G_{i} : S ⊑ G_{i}} be the occurrence set of graph S. Find all connected subgraphs S such that |H(S)| ≥ σ^{∗}, i.e., S is a frequent subgraph in G and for all S′ ⊐ S, H(S) ≠ H(S′), i.e., S is maximal.

Ananth Grama 2001/01/27

Algorithmic Insight: Ortholog Contraction

• Contract orthologous nodes into a single node

• No subgraph isomorphism

– Graphs are uniquely identified by their edge sets

• Key observation: Frequent sub-networks are preserved ⇒ No information loss

– Sub-networks that are frequent in general graphs are also frequent in their ortholog-contracted representation

– Ortholog contraction is a powerful pruning heuristic

Ananth Grama 2001/01/27

Example: Ortholog Contraction in Metabolic Pathways

• Directed hypergraph → uniquely-labeled directed graph

– Nodes represent enzymes

– Global labeling by enzyme nomenclature (EC numbers)

– A directed edge from one enzyme to the other implies that the second consumes a product of the first

PSfrag replacements

267 221 668 1172

5.1.3.3 2.7.1.1 2.7.1.2 2.7.1.63

Ananth Grama 2001/01/27

Example: Ortholog Contraction in Protein Interaction Networks

• Interaction between proteins → Interaction between ortholog groups or protein families

PSfrag replacements Rrp4 Rrp43 Mtr3 Ski6 Csr4

KOG3013 KOG1613 KOG1068 KOG3409

Ananth Grama 2001/01/27

Preservation of Sub-networks

Theorem: Let G̃ be the ortholog-contracted graph obtained by contracting the orthologous nodes of network G. Then, if S is a subgraph of G, S̃ is a subgraph of G̃.

Corollary: The ortholog-contracted representation of any frequent sub-network is also frequent in the set of orthologcontracted graphs.

PSfrag replacements

G
G̃

Ananth Grama 2001/01/27

Simplifying the Graph Analysis Problem

• Observation: An ortholog-contracted graph is uniquely determined by the set of its edges.

– Conserved Sub-network Discovery Problem → Frequent Edge set Discovery Problem

PSfrag replacements

a b c d e G_{1} G_{2} G_{3} G_{4}

F_{1}= {ab, ac, de} F_{2}= {ab, ac, bc, de, ea}

F_{3}= {ab, ac, bc, ea} F_{4}= {ab, ce, de, ea}

Ananth Grama 2001/01/27

Extending Frequent Itemset Mining to Graph Analysis

• Given a set of transactions, find sets of items that are frequent in these transactions

– Extensively studied in data mining literature

• Algorithms exploit downward closure property

– An edge set is frequent only if all of its subsets are frequent

– Generate edge sets (sub-networks) from small to large, pruning supersets of infrequent sets

• No redundancy

• No subgraph enumeration

Ananth Grama 2001/01/27

Mule: Analyzing Ortholog-Contracted Networks

PSfrag replacements

E = ∅

H = {1, 2, 3, 4} D = {ab} E = {ab}

C = {ac, ea} H = {1, 2, 3, 4}

D = {ab, ac} E = {ac} C = {ea}

H = {1, 2, 3} D = {ab, ac, de}

E = {de} C = {ea}

H = {1, 2, 4} D = {ab, ac, de, ea}

E = {ea} C = ∅

H = {2, 3, 4} D = {ab, ac} E = {ab, ac}

C = {ea} H = {1, 2, 3}

D = {ab, ac, ea}

E = {ab, ea}

C = {de} H = {2, 3, 4}

Sample run of Mule for identifying maximal sub-networks that are common to at least 3 organisms

Ananth Grama 2001/01/27

Case Study: Analyzing Protein Interaction Networks

• PPI networks for 9 eukaryotic organisms derived from BIND and DIP

– A. thaliania, O. sativa, S. cerevisiae, C. elegans, D. melanogaster, H. sapiens, B. taurus, M. musculus, R. norvegicus

– # of proteins ranges from 288 (Arabidopsis) to 8577 (fruit fly)

– # of interactions ranges from 340 (rice) to 28829 (fruit fly)

• Ortholog contraction

– Group proteins according to existing COG ortholog clusters

– Merge Homologene groups into COG clusters

– Cluster remaining proteins via BLASTCLUST

– Ortholog-contracted fruit fly network contains 11088 interactions between 2849 ortholog groups

• Mule is available at

http://www.cs.purdue.edu/pdsl/

Ananth Grama 2001/01/27

Conserved Protein Interaction Patterns

PSfrag replacements

Pattern C. elegans S. cerevisiae D. melanogaster

Small nuclear ribonucleoprotein complex (p < 2e − 43)

Ananth Grama 2001/01/27

Conserved Protein Interaction Patterns

PSfrag replacements

Pattern H. sapiens S. cerevisiae

B. taurus

Actin-related protein Arp2/3 complex (p < 9e − 11)

Ananth Grama 2001/01/27

Conserved Protein Interaction Patterns

PSfrag replacements

Pattern H. sapiens S. cerevisiae

D. melanogaster

Endosomal sorting (p < 1e − 78)

Ananth Grama 2001/01/27

Runtime Characteristics

Comparison with isomorphism-based algorithms

FSG [Kuramochi & Karypis, IEEE TKDE, 2004], gSpan [Yan & Han, KDD, 2003]

FSG  Mule
Minimum  Runtime  Largest  Number of  Runtime  Largest  Number of
Dataset  Support (%)  (secs.)  pattern  patterns  (secs.)  pattern  patterns
20  0.2  9  12  0.01  9  12
16  0.7  10  14  0.01  10  14
Glutamate  12  5.1  13  39  0.10  13  39
10  22.7  16  34  0.29  15  34
8  138.9  16  56  0.99  15  56
24  0.1  8  11  0.01  8  11
20  1.5  11  15  0.02  11  15
Alanine  16  4.0  12  21  0.06  12  21
12  112.7  17  25  1.06  16  25
10  215.1  17  34  1.72  16  34

Extraction of contracted patterns

Glutamate metabolism, σ = 8%  Alanine metabolism, σ = 10%
Size of  Extraction time  Size of  Size of  Extraction time  Size of
contracted  (secs.)  extracted  contracted  (secs.)  extracted
pattern  FSG gSpan  pattern  pattern  FSG gSpan  pattern
15  10.8  1.12  16  16  54.1  10.13  17
14  12.8  2.42  16  16  24.1  3.92  16
13  1.7  0.31  13  12  0.9  0.27  12
12  0.9  0.30  12  11  0.4  0.13  11
11  0.5  0.08  11  8  0.1  0.01  8
Total number of patterns: 56  Total number of patterns: 34
Total runtime of FSG alone: 138.9 secs.  Total runtime of FSG alone :215.1 secs.
Total runtime of Mule+FSG: 0.99+100.5 secs.  Total runtime of Mule+FSG: 1.72+160.6 secs.
Total runtime of Mule+gSpan: 0.99+16.8 secs.  Total runtime of Mule+gSpan: 1.72+31.0 secs.

Slide 17 Ananth Grama 2001/01/27

Alignment of Networks

• Given two networks, identify sub-networks that are similar to each other

– Biological implications

– Mathematical modeling

• Existing algorithms

– PathBLAST aligns pathways (linear chains) to simplify the problem while maintaining biological meaning [Kelley et al., PNAS, 2004]

– NetworkBLAST compares conserved complex model with null model to identify significantly conserved subnets [Sharan et al., J. Comp. Biol., 2005]

• Our approach [Koyutürk et al., RECOMB, 2005] [Koyutürk et al., J. Comp. Biol., 2006]

– Guided by models of evolution

– Scores evolutionary events

– Identifies sets of proteins that induce high-scoring sub-network pairs

Ananth Grama 2001/01/27

Evolution of Networks

• Many networks evolve through the process of Duplication/ and Divergence.

– Interactions of duplicated nodes are also duplicated

– Duplicated nodes rapidly lose interactions through mutations

• Allows defining and scoring evolutionary events as graphtheoretical concepts

PSfrag replacements u_{1} u′_{1} u_{2} u_{3}

Duplication Elimination Emergence

Ananth Grama 2001/01/27

Match, Mismatch, and Duplication

• Evolutionary events as graph-theoretic concepts

– A match ∈ M corresponds to two pairs of homolog nodes from each network such that both pairs interact in both networks. A match is associated with score μ.

– A mismatch ∈ N corresponds to two pairs of homolog nodes from each graph such that only one pair is interacting. A mismatch is associated with penalty ν.

– A duplication ∈ D corresponds to a pair of homolog nodes that are in the same network. A duplication is associated with score δ.

PSfrag replacements

u_{1}
u_{2}
u_{3}
u_{4}
v_{1}
v_{2}
v_{3}
e_{1}
e_{2}
e_{3}
G:
H:

Ananth Grama 2001/01/27

Scoring Matches, Mismatches and Duplications

• Quantizing similarity between two nodes

– Confidence in two nodes being orthologous

– E-value: S(u, v) = log_{10} \frac{p(u,v)}{prandom}

– Ortholog clustering: S(u, v) = c(u)c(v)

• Match score

– μ(uu′, vv′) = μ̄ min{S(u, v), S(u′, v′)}

• Mismatch penalty

– ν(uu′, vv′) = ν̄ min{S(u, v), S(u′, v′)}

• Duplication score

– δ(u, u′) = δ̄(δ̂ − S(u, u′))

– δ̂ specifies threshold for sequence similarity to be considered functionally conserved

Ananth Grama 2001/01/27

Pairwise Alignment of Networks as an Optimization Problem

• Alignment score:

σ(A(P)) = ∑_{M∈M} μ(M) − ∑_{N∈N} ν(N) + ∑_{D∈D} δ(D)

– Matches are rewarded for conservation of interactions

– Duplications are rewarded/penalized for functional conservation/differentiation after split

– Mismatches are penalized for functional divergence (what about experimental error?)

• Scores are functions of similarity between associated proteins

• Problem: Find all protein subset pairs with significant alignment score

– High scoring protein subsets are likely to correspond to conserved modules

• A graph equivalent to BLAST

Ananth Grama 2001/01/27

Weighted Alignment Graph

• G(V, E) : V consists of all pairs of homolog proteins v = {u ∈ U, v ∈ V }

• An edge vv′ = {uv}{u′v′} in E is a

– match edge if uu′ ∈ E and vv′ ∈ V, with weight w(vv′) = μ(uv, u′v′)

– mismatch edge if uu′ ∈ E and vv′ ∉ V or vice versa, with weight w(vv′) = −ν(uv, u′v′)

– duplication edge if S(u, u′) > 0 or S(v, v′) > 0, with weight w(vv′) = δ(u, u′) or w(vv′) = δ(v, v′)

PSfrag replacements {u_{1}, v_{1}}

{u_{2}, v_{1}}
{u_{3}, v_{3}}
{u_{4}, v_{2}}
{u_{4}, v_{4}}
μ
-ν
-δ

Ananth Grama 2001/01/27

Maximum Weight Induced Subgraph Problem

• Definition: (MaWISh)

– Given graph G(V, E) and a constant ϵ, find Ṽ ∈ V such that ∑_{v,u∈Ṽ} w(vu) ≥ ϵ.

– NP-complete by reduction from Maximum-Clique

• Theorem: (MaWISh ≡ Pairwise alignment)

– If Ṽ is a solution for the MaWISh problem on G(V, E), then P = {Ũ, Ṽ } induces an alignment A(P) with σ(A) ≥ ϵ , where Ṽ = Ũ × Ṽ.

• Solution: Local graph expansion

– Greedy graph growing + iterative refinement

– Linear-time heuristic

• Source code available at

http://www.cs.purdue.edu/pdsl/

Ananth Grama 2001/01/27

Case Study: Alignment of Yeast and Fruit Fly Networks

Rank Score z-score # Proteins # Matches  # Mismatches  # Dups.
1  15.97  6.6  18 (16, 5)  28  6  (4, 0)

protein amino acid phosphorylation (69%) JAK-STAT cascade (40%)

2 13.93 3.7 13 (8, 7) 25 7 (3, 1)

endocytosis (50%) / calcium-mediated signaling (50%)

5 8.22 13.5 9 (5, 3) 19 11 (1, 0)

invasive growth (sensu Saccharomyces) (100%) oxygen and reactive oxygen species metabolism (33%)

6 8.05 7.6 8 (5, 3) 12 2 (0, 1)

ubiquitin-dependent protein catabolism (100%) mitosis (67%)

21 4.36 6.2 9 (5, 4) 18 13 (0, 5)

cytokinesis (100%, 50%)

30 3.76 39.6 6 (3, 5) 5 1 (0, 6)

DNA replication initiation (100%, 80%)

Subnets Conserved in Yeast and Fruit Fly

Proteosome regulatory particle subnet

PSfrag replacements

S.Cerevisiae D.Melanogaster

Calcium-dependent stress-activated signaling pathway

PSfrag replacements

S.Cerevisiae D.Melanogaster Ananth Grama 2001/01/27

Analytical Assessment of Statistical Significance

• What is the significance of a dense component in a network?

• What is the significance of a conserved component in multiple networks?

• Existing techniques

– Mostly computational (e.g., Monte-Carlo simulations)

– Compute probability that the pattern exists rather than a pattern with the property (e.g., size, density) exists

– Overestimation of significance

Ananth Grama 2001/01/27

Random Graph Models

• Interaction networks generally exhibit power-law property (or exponential, geometric, etc.)

• Analysis simplified through independence assumption [Itzkovitz

et al., Physical Review, 2003]

• Independence assumption may cause problems for networks with arbitrary degree distribution

• P (uv ∈ E) = d_{u}d_{v}/|E|, where d_{u} is expected degree of u, but generally d_{max}^{2} > |E| for PPI networks

• Analytical techniques based on simplified models [Koyutürk, Grama, Szpankowski, RECOMB, 2006]

– Rigorous analysis on G(n, p) model

– Extension to piecewise G(n, p) to capture network characteristics more accurately

Ananth Grama 2001/01/27

Significance of Dense Subgraphs

• A subnet of r proteins is said to be ρ-dense if F (r) ≥ ρr^{2}, where F (r) is the number of interactions between these r proteins

• What is the expected size of the largest ρ-dense subgraph in a random graph?

– Any ρ-dense subgraph with larger size is statistically significant!

• G(n, p) model

– n proteins, each interaction occurs with probability p

– Simple enough to facilitate rigorous analysis

– If we let p = d_{max}/n, largest ρ-dense subgraph in G(n, p) stochastically dominates that in a graph with arbitrary degree distribution

• Piecewise G(n, p) model

– Few proteins with many interacting partners, many proteins with few interacting partners

– Captures the basic characteristics of PPI networks

– Analysis of G(n, p) model immediately generalized to this model

Ananth Grama 2001/01/27

Largest Dense Subgraph

• Theorem: If G is a random graph with n nodes, where every edge exists with probability p, then

lim_{n→∞} \frac{R_{ρ}}{log n} = \frac{1}{κ(p, ρ)}  (pr.),  (1)

where

κ(p, ρ) = ρ log \frac{ρ}{p} + (1 − ρ) log \frac{1 − ρ}{1 − p}.  (2)

More precisely,

P (R_{ρ} ≥ r_{0}) ≤ O (\frac{log n}{n^{1/κ(p,ρ)}}) ,  (3)

where

r_{0} = \frac{log n − log log n + log κ(p, ρ)}{κ(p, ρ)}  (4)

for large n.

Slide 30

Ananth Grama 2001/01/27

Piecewise G(n, p) model

• The size of largest dense subgraph is still proportional to log n/κ with a constant factor depending on number of hubs

• Model:

P (uv ∈ E(G)) = \{ \begin{matrix}p_{h} & if u, v ∈ V_{h} \\ p_{l} & if u, v ∈ V_{l} \\ p_{b} & if u ∈ V_{h}, v ∈ V_{l} or u ∈ V_{l}, v ∈ V_{h} \end{matrix}

• Result:

Let n_{h} = |V_{h}|. If n_{h} = O(1), then P (R_{n}(ρ) ≥ r_{1}) ≤ O (\frac{log n}{n^{1/κ(p_{l},ρ)}}) , where

r_{1} = \frac{log n − log log n + 2n_{h} log B + log κ(p_{l}, ρ) − log e + 1}{κ(p_{l}, ρ)}

and B = \frac{p_{b}q_{l}}{p_{l}} + q_{b}, where q_{b} = 1 − p_{b} and q_{l} = 1 − p_{l}.

Slide 31

Ananth Grama 2001/01/27

Algorithms Based on Statistical Significance

• Identification of topological modules

• Use statistical significance as a stopping criterion for graph clustering heuristics

• HCS Algorithm [Hartuv & Shamir, Inf. Proc. Let., 2000]

– Find a minimum-cut bipartitioning of the network

– If any of the parts is dense enough, record it as a dense cluster of proteins

– Else, further partition them recursively

• SiDeS: Use statistical significance to determine whether a subgraph is sufficiently dense

– For given number of proteins and interactions between them, we can determine whether those proteins induce a significantly dense subnet

Ananth Grama 2001/01/27

SiDeS Algorithm

PSfrag replacements p << 1

                 SiDeS is available at http://www.cs.purdue.edu/pdsl

Ananth Grama 2001/01/27

Performance of SiDeS

• Biological relevance of identified clusters is assessed with respect to Gene Ontology (GO)

– Estimate the statistical significance of the enrichment of each GO term in the cluster

• Quality of the clusters with respect to GO annotations

– Assume cluster C containing n_{C} genes is associated with term T that is attached to n_{T} genes and n_{CT} of genes in C are attached to T

– specificity = 100 × n_{CT} /n_{C}

– sensitivity = 100 × n_{CT} /n_{T}

SiDeS  MCODE
Min. Max. Avg.  Min. Max. Avg.
Specificity (%)  43.0 100.0 91.2  0.0 100.0 77.8
Sensitivity (%)  2.0 100.0 55.8  0.0 100.0 47.6

Comparison of SideS with MCODE [Bader & Hogue, BMC Bioinformatics, 2003]

Ananth Grama 2001/01/27

Performance of SiDeS

PSfrag replacements

Cluster size

SiDeS mcode

Sensitivity (%)

0 10 20 30 40 50 60 70 80 90 100

PSfrag replacements

Cluster size

SiDeS mcode

Sensitivity (%)

0 10 20 30 40 50 60 70 80 90 100

Size vs Significance Sensitivity vs Specifity

Correlation SiDeS: 0.76 MCODE: 0.43

Ananth Grama 2001/01/27

Performance of SiDeS

PSfrag replacements

Cluster size

SiDeS mcode

0 10 20 30 40 50 60 70 80 90 100

PSfrag replacements

Cluster size

SiDeS mcode

0 10 20 30 40 50 60 70 80 90 100

Size vs Specificity Size vs Sensitivity

Correlation SiDeS: 0.22 SiDeS: 0.27 MCODE: -0.02 MCODE: 0.36

Ananth Grama 2001/01/27

Functional Annotation of Pathways: From Molecules to Systems

• Annotation is at the node level

• Map networks to function space (can generate a library of annotated modular (sub-) networks)

Network of Gene Ontology terms based on significance of pairwise interactions in yeast synthetic gene array (SGA) (Tong et al., Science, 2004)

Ananth Grama 2001/01/27

Narada Functionality

Ananth Grama 2001/01/27

Narada Network Annotation