Comparative Analysis of Molecular Interaction Networks

Ananth Grama Coordinated Systems Lab and, Computer Science Department, Purdue University

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

Various parts of this work involve collaborations with Yohan Kim and Shankar Subramaniam (UCSD), Wijtek Szpankowski (Purdue), Mehmet Koyuturk (Case Western)

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

Ananth Grama 2003/12/03

Outline

• Molecular Interaction Networks

– Modeling, evolution, problems, practical implications

• Algorithms for Analyzing Molecular Interaction Networks

– Analyzing biological networks for conserved molecular interaction patterns

– Pairwise Alignment of protein-protein interaction networks

– Probabilistic models/analyses for assessing statistical significance

• Computational Synthesis of Interaction Networks

– Inferring function from domain co-evolution

• Ongoing Work

Ananth Grama 2003/12/03

Protein-Protein Interaction (PPI) Networks

• Interacting proteins can be identified via high-throughput screening

– Two-hybrid

– Mass spectrometry

– Tandem affinity purification (TAP)

PSfrag replacements

Protein Interaction

Undirected Graph Model S. Cerevisiae PPI network

[Jeong et al., Nature, 2001]

Ananth Grama 2003/12/03

Gene Regulatory Networks

• Expression of genes is dynamically orchestrated through genes controlling each other’s transcription

– Computationally induced from gene expression data and/or sequence level analysis

PSfrag replacements

Gene

Down-regulation Up-regulation

Boolean Network Genetic network that controls

Model flowering time in A. Thaliania

[Blazquez et al, EMBO Reports, 2001]

Ananth Grama 2003/12/03

Metabolic Pathways

• Chains of reactions that perform a particular metabolic function

– Reactions are linked to each other through substrate-product relationships

– Experimentally derived & computationally extended

PSfrag replacements Enzyme Substrate Product

Compound

Directed Hypergraph Model Glycolysis pathway in S. Cerevisiae

[Hynne et al., Biophys. Chem., 2001]

Ananth Grama 2003/12/03

Evolution of Molecular Interactions

• “Evolution thinks modular”[Vespignani, Nature Gen., 2003]

• Cooperative tasks require all participating units

– Selective pressure on preserving interactions & interacting proteins

– Interacting proteins follow similar evolutionary trajectories [Pellegrini et al., PNAS, 1999]

• Orthologs of interacting proteins are likely to interact [Wagner,

Mol. Bio. Evol., 2001]

– Conservation of interactions may provide clues relating to conservation of function

• Modular conservation and alignment hold the key to critical structural, functional, and evolutionary concepts in systems biology

Ananth Grama 2003/12/03

Conserved Interaction Patterns

• Given a collection of 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 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 molecules (proteins) in different 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 2003/12/03

Graph Analysis

Network database

Interaction patterns that are common to all networks

Ananth Grama 2003/12/03

Relating Proteins in Different Species

• Ortholog Databases

– PPI networks: COG, Homologene, Pfam, ADDA

– Metabolic pathways: Enzyme nomenclature

– Reliable, but conservative

– Domain families rely on domain information, but the underlying domains for most interactions are unknown ⇒ Multiple node labels

• Sequence Clustering

– Cluster protein sequences and label proteins according to this clustering

– Flexible, but expensive and noisy

• Labels may span a large range of functional relationships, from protein families to ortholog groups

– Without loss of generality, we call identically labeled proteins as orthologs

Ananth Grama 2003/12/03

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

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

• Discovered frequent sub-networks are still biologically interpretable!

– Interaction between proteins becomes interaction between ortholog groups

Ananth Grama 2003/12/03

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

Ortholog Contraction in 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

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

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

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

Results: Analyzing PPI 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 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

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

Discussion

• Ortholog contraction is fast & scalable

– Graph cartesian product based methods [Sharan et al., PNAS, 2004], [Koyutürk et al., RECOMB, 2005] create m^{n} product nodes for an ortholog group that has m proteins in each of n organisms

– Ortholog contraction represents the same group with only n contracted nodes

– Isomorphism-based graph analysis algorithms do not scale to large networks

• Ortholog contraction implicitly accounts for noise by eliminating false positives by thresholding frequency, and false negatives by contraction

• Frequency-based approach is not easily extensible to

weighted graphs [Zhou et al., ISMB, 2005]

Ananth Grama 2003/12/03

Alignment of PPI Networks

• Given two PPI networks that belong to two different organisms, 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 2003/12/03

Evolution of PPI Networks

• Duplication/divergence models for the evolution of protein interaction networks

– Interactions of duplicated proteins are also duplicated

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

Match, Mismatch, and Duplication

• Evolutionary events as graph-theoretic concepts

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

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

– A duplication ∈ D corresponds to a pair of homolog proteins that are in the same organism. 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

Scoring Matches, Mismatches and Duplications

• Quantizing similarity between two proteins

– Confidence in two proteins being orthologous

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

Pairwise Alignment of PPIs 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 2003/12/03

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

Discussion

• Comparison to other approaches: NetworkBlast [Sharan et al.,

PNAS, 2005], NUKE [Novak et al., Genome Informatics, 2005]

– Much faster than NetworkBLAST, but provides less coverage

– Comparable to NUKE depending on speed vs coverage trade-off

• Scores evolutionary events

– Flexible, allows incorporation of different evolutionary models, experimental bases, target structures

– Somewhat ad-hoc, what is a good weighting of scores?

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 37

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 38

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]

Ananth Grama 2003/12/03

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

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

Functional Annotation of Biochemical Pathways

• Identifying Significant Pathways

• Annotations and Metrics

• Application to Protein/Domain Interaction Networks

• Implementation and Results

Ananth Grama 2003/12/03

Molecular Annotation

• Functional annotation of genes provides an understanding of the underlying principles

– Molecular function: role of a gene.

– Biological process: processes a gene is involved in.

– Cellular component: localization of genes product.

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

Ananth Grama 2003/12/03

From Molecules to Systems

• Networks are species-specific

• Annotation is at the molecular level

• Map networks from gene space 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)

Slide 46 Ananth Grama 2003/12/03

Indirect Regulation

Ananth Grama 2003/12/03

Key Results

• Statistically interpretable measures of significance are not monotonic.

• There is no monotonicity in the GO space either.

• Develop an alternate (weaker) measure of significance that builds on modularity of sub-components.

• Need to short-circuit common terms (transcription factors, DNA binding genes, etc.)

• Comprehensive software infrastructure built on these results.

Ananth Grama 2003/12/03

Narada Functionality

Ananth Grama 2003/12/03

Narada Network Annotation

Ananth Grama 2003/12/03 Slide 51 Ananth Grama 2003/12/03 Slide 52 Ananth Grama 2003/12/03 Slide 53 Ananth Grama 2003/12/03 Slide 54 Ananth Grama 2003/12/03 Slide 55 Ananth Grama 2003/12/03 Slide 56 Ananth Grama 2003/12/03 Slide 57 Ananth Grama 2003/12/03 Slide 58 Ananth Grama 2003/12/03 Slide 59 Ananth Grama 2003/12/03 Slide 60 Ananth Grama 2003/12/03 Slide 61 Ananth Grama 2003/12/03 Slide 62 Ananth Grama 2003/12/03 Slide 63 Ananth Grama 2003/12/03 Slide 64 Ananth Grama 2003/12/03

References

• J. Pandey, M. Koyuturk, S. Subramaniam, and A. Grama. Functional coherence in domain interaction networks, Bioinformatics Suppl. on ECCB’08.

• M. Koyuturk, W. Szpankowski, and A. Grama, Assessing significance of connectivity and conservation in protein interaction networks, Journal of Computational Biology, 14(6), 747-764, 2007.

• M. Koyuturk, Y. Kim, S. Subramaniam, W. Szpankowski, and A. Grama, “Detecting conserved interaction patterns in biological networks”, Journal of Computational Biology, 13(7), 1299-1322, 2006.

• M. Koyuturk, Y. Kim, U. Topkara, S. Subramaniam, W. Szpankowski, and A. Grama, Pairwise Alignment of Protein Interaction Networks, Journal of Computational Biology, 13(2), 182-199, 2006.

• Y. Kim, M. Koyuturk, U. Topkara, A. Grama, and S. Subramaniam, Inferring Functional Information from Domain Co-evolution, Bioinformatics, 22(1), pp. 40-49, 2006.

Ananth Grama 2003/12/03

References

• M. Koyutürk, A. Grama, and W. Szpankowski, An Efficient Algorithm for Detecting Frequent Subgraphs in Biological Networks, Bioinformatics, Vol. 20, Suppl. 1, pp i200-i207, 2004.

• M. Koyuturk, A. Grama, and W. Szpankowski, Assessing Significance of Connectivity and Conservation in Protein Interaction Networks, 10th International Conference on Research in Computational Molecular Biology (RECOMB), LNBI 3909, pp. 45-59, 2006.

• M. Koyutürk, A. Grama and W. Szpankowski, Pairwise Local Alignment of Protein Interaction Networks Guided by Models of Evolution, RECOMB 2005.

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

Ananth Grama 2003/12/03

Ongoing Work and Other results

Ananth Grama 2003/12/03

Synteny and Transcriptional Relationships

• It is widely believed that neighboring genes have stronger transcriptional relationships.

• Can this signal be amplified by identifying syntenic blocks first?

Ananth Grama 2003/12/03

Local vs. Global Alignment of Networks

• It is widely believed that local alignment identifies modularity and global alignment identifies functional orthology.

• Is this really true?

• How do we do global alignment anyway?

Ananth Grama 2003/12/03

Identifying SNPs in NGS Data

• Crossreferencing NGS reads with SNP databases seems simple.

• However, at 30 bp reads, one often gets multiple hits (mutations or not).

• How can we stack a p-value on the existence of a SNP in this case?

Ananth Grama 2003/12/03

Phylogenetic Analysis for Predicting Interactions

• Functionally related proteins are likely to have co-evolved

– Construct phylogenetic profile for each genome: Vector of E-values signifying existence of an orthologous protein in each organism

– Identify pairwise functional associations based on mutual information between phylogenetic profiles [Pellegrini et al., PNAS, 1999]

– Mutual information:

I(X, Y) = H(X) − H(X|Y) = ∑_{x} ∑_{y} p(x, y) log(p(x, y)/p(x)p(y))

– Shown to identify functionally associated protein pairs at a coarser level than high-throughput methods

• However, domains, not proteins, co-evolve

– How can we incorporate domain information to enhance performance of phylogeny-based interaction prediction?

Ananth Grama 2003/12/03

Inferring Function from Domain Co-evolution

• Residue-level phylogenetic analysis [Kim, Koyut^{}ürk, Topkara, Grama,

& Subramaniam, Bioinformatics, 2006]

– No a-priori knowledge about domains

– Construct residue phylogenetic profiles from local alignment results

– Construct mutual information matrix

– High-information contiguous submatrices that are sufficiently large correspond to putative co-evolved domains

Mutual Information Matrix Single vs. Domain Profile

Ananth Grama 2003/12/03

BiClustering/Pattern Identification

• Proximus: Non-orthogonal decomposition of binary matrices

[Koyutürk, Grama, Ramakrishnan, IEEE TKDE, 2005]

– Find a compact set of vectors that represent the entire matrix

– Recursive decomposition through rank-one approximations

– Fast (linear-time) iterative heuristics for computing approximations

– Source code available at

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

Patterns of regulation Biclustering

“Algorithms for bounded-error correlation of “Biclustering gene-feature matrices for high dimensional data in microarray experiments” statistically significant dense patterns”

[Koyutürk, Grama, Szpankowski: CSB’03.] [Koyutürk, Grama, Szpankowski: CSB’04.] Ananth Grama 2003/12/03

Modular Phylogenetics

Replication Factor C complex identified on yeast PPI network by

MCODE [Bader & Hogue, BMC Bioinformatics, 2003] algorithm

and the phylogenetic profiles of its proteins on 25 eukaryotic genomes

Conserved in all eukaryotic species!

Ananth Grama 2003/12/03

Modular Phylogenetics

A component of mitochondrial ribosome identified on

yeast PPI network by MCODE algorithm and the phylogenetic profiles of its proteins on 25 eukaryotic genomes

Conserved in only yeast species!

• Models and algorithms for quantifying, analyzing, and evaluating modular conservation and divergence across species

Ananth Grama 2003/12/03

Thank You!