GQ: A Graph Toolkit for Multicore Environments

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 2003/12/03

Graph Library Components

• Conservation in Networks

• Alignment of Networks

• Modularity in Networks

• Reputation/Rank

• Graph Grammars and Parsers

• Some Ongoing Work

Ananth Grama 2003/12/03

Conservation in Networks

• Given a collection of networks (say, protein interaction networks belonging to different species), find sub-networks that are common to an interesting subset of these networks [Koyut^{}ürk,

Grama, & Szpankowski, ISMB, 2004]

– A sub-network is connected.

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

• 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 and beyond]

Ananth Grama 2003/12/03

Graph Analysis

Network database

Interaction patterns that are common to all networks

Ananth Grama 2003/12/03

Problem Statement

• Given a set of nodes V, a set of edges E, and a many-to-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 2003/12/03

Computational Problem

• Conserved sub-network discovery

– Instance: A set of networks G = {G_{1} = (V_{1}, E_{1}, L), G_{2} = (V_{2}, E_{2}, L), ..., G_{m} = (V_{m}, E_{m}, L)}, 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 2003/12/03

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 2003/12/03

Ortholog Contraction in Real Applications (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 2003/12/03

Ortholog Contraction in Real Applications (PPI Networks)

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

PSfrag replacements Rrp4 Rrp43 Mtr3 Ski6 Csr4

KOG3013 KOG1613 KOG1068 KOG3409

Ananth Grama 2003/12/03

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 2003/12/03

Conserved Protein Interaction Patterns

PSfrag replacements

Pattern C. elegans S. cerevisiae D. melanogaster

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

Ananth Grama 2003/12/03

Conserved Protein Interaction Patterns

PSfrag replacements

Pattern H. sapiens S. cerevisiae

B. taurus

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

Ananth Grama 2003/12/03

Conserved Protein Interaction Patterns

PSfrag replacements

Pattern H. sapiens S. cerevisiae

D. melanogaster

Endosomal sorting (p < 1e − 78)

Ananth Grama 2003/12/03

Runtime Characteristics

Minimum  Runtime  Largest  Number of  Runtime  Runtime
Dataset  Support (%)  (secs.)  pattern  patterns  2 Cores  4 Cores
Glutamate  12  0.10  13  39  0.08  0.07
10  0.29  15  34  0.16  0.10
8  0.99  15  56  0.58  0.37
Alanine  16  0.06  12  21  0.05  0.07
12  1.06  16  25  0.57  0.33
10  1.72  16  34  0.90  0.52

All times on a 2.66 MHz i7 Processor.

Ananth Grama 2003/12/03

Alignment of Networks

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

– Optimization function

– 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]

Ananth Grama 2003/12/03

Match, Mismatch, and Duplication

• Establishing a Cost Measure

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

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

– A duplication ∈ D corresponds to a pair of homologous nodes 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 2003/12/03

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 divergence.

• Problem: Find all subnet pairs with significant alignment score

• A graph equivalent to BLAST

Ananth Grama 2003/12/03

Weighted Alignment Graph

• G(V, E) : V consists of all pairs of homologous nodes 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 2003/12/03

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 2003/12/03

Alignment of Yeast and Fruit Fly PPI 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

Number of  Runtime
Dataset  Patterns  (secs.)  2 Cores  4 Cores
Yeast/Fruit Fly  8  0.16  0.12  0.10
13  1.80  1.02  0.68
20  2.93  1.61  0.94

All times on a 2.66 MHz i7 Processor.

Ananth Grama 2003/12/03

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 2003/12/03

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 2003/12/03

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 2003/12/03

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 25

Ananth Grama 2003/12/03

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 26

Ananth Grama 2003/12/03

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 2003/12/03

SiDeS Algorithm

PSfrag replacements p << 1

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

Ananth Grama 2003/12/03

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]

Number of  Runtime
Dataset  Clusters  (secs.)  2 Cores  4 Cores
Yeast PPI  11  4.80  2.64  1.60
18  7.32  3.70  1.99
26  10.19  5.61  2.90

All times on a 2.66 MHz i7 Processor.

Ananth Grama 2003/12/03

Functional Annotation of Pathways

• Identifying Significant Pathways

• Annotations and Metrics

• Application to Protein/Domain Interaction Networks

• Implementation and Results

Ananth Grama 2003/12/03

Node Annotation

• Node annotation is in the form of an ontology.

• For instance, Gene Ontology provides a library of molecular annotations (we refer to each annotation class as a functional attribute).

Ananth Grama 2003/12/03

Narada Functionality

Ananth Grama 2003/12/03

Narada Network Annotation

* Parallel implementation ongoing.

Ananth Grama 2003/12/03

Graph Grammars and Parsing

Ananth Grama 2003/12/03

Graph Grammars and Parsing: Status

• Serial parser complete.

• Parallel parser currently in implementation.

• Grammar inference currently under implementation.

Ananth Grama 2003/12/03

Science of Information

“An NSF STC focused on post-Shannon Information theory.”