Modularity and Function: Background Modularity in PPIs and DDIs Pathway Maps: Background

Constructing KEGG Crosstalk Map

Functional Characterization and Topological Modularity of Molecular Interaction Networks

Ananth Grama^{1}

1Center for Science of Information and Department of Computer Science, Purdue University

Various parts of this talk involved collaborations with Jayesh Pandey, Mehmet Koyuturk, Shahin Mohammadi, Giorgos Kollias, and Shankar Subramaniam. Acknowledgements to the National Science Foundation.

Modularity and Function: Background Modularity in PPIs and DDIs Pathway Maps: Background

Constructing KEGG Crosstalk Map

Molecular Interaction Networks

Provides a high level description of cellular organization Directed and undirected graph representation Nodes represent cellular components

Protein, gene, enzyme,

metabolite

Edges represent reactions or interactions

Binding, regulation, modification, complex membership, substrate-product relationship

S.cerevisiae Protein-Protein Interaction (PPI) Network

Modularity and Function: Background Modularity in PPIs and DDIs Pathway Maps: Background

Constructing KEGG Crosstalk Map

Function : Gene Ontology

Molecular annotation provides a unified understanding of the underlying principles Gene Ontology: A controlled vocabulary of molecular functions, biological processes, and cellular components Terms (concepts) related by is-a, part-of relationships If a molecule is annotated by a term, then it is also annotated by terms on the paths towards root.

Modularity and Function: Background Modularity in PPIs and DDIs Pathway Maps: Background

Constructing KEGG Crosstalk Map

Function & Topology in Molecular Networks

How does function relate to network topology?

Modularity and Function: Background Modularity in PPIs and DDIs Pathway Maps: Background

Constructing KEGG Crosstalk Map

Prior Work on Topology and Function

Understanding functional composition of biochemical networks Conservation [ISMB 04/Bioinf. 04] Alignment [RECOMB 05/JCB 06] Modularity [RECOMB 06/JCB 07] Inference [Bioinf. 06] Pathway Annotation [ISMB 07/Bioinf. 07, PSB 08] Network Abstractions/ Annotations [ECCB 08/ Bioinf. 08] Modularity and Domain Interactions [APBC 10/ BMC Bioinf. 10] Pathway Interaction Maps [PSB 12, Submitted]

Modularity and Function: Background Modularity in PPIs and DDIs Pathway Maps: Background

Constructing KEGG Crosstalk Map

Functional Coherence in Networks

Modularity manifests itself in terms of high connectivity in the network Functional association (similarity) is correlated with network proximity A measure for annotation proximity of nodes (semantic similarity) A measure for network distance

Sharan et al., MSB, 2007

Grama et al.

Modularity and Function: Background Modularity in PPIs and DDIs Pathway Maps: Background

Constructing KEGG Crosstalk Map

Assessing Functional Similarity

Gene Ontology (GO) provides a hierarchical taxonomy of biological process, molecular function and cellular component Assessment of semantic similarity between concepts in a hierarchical taxonomy is well studied (Resnik, IJCAI, 1995)

Modularity and Function: Background Modularity in PPIs and DDIs Pathway Maps: Background

Constructing KEGG Crosstalk Map

Semantic Similarity of GO Terms

Resnik’s measure based on information content I(c) = − log_{2}(|G_{c}|/|G_{r}|)

δ_{I}(c_{i}, c_{j}) = max_{c∈A_{i}∩A_{j}}I(c)

G_{c}: Set of molecules that are associated with term c, r: Root term A_{i}: Ancestors of term c_{i} in the hierarchy λ(c_{i}, c_{j}) = argmax_{c∈A_{i}∩A_{j}}I(c): Lowest common ancestor of c_{i} and c_{j}

Resnik(c_{3}, c_{4}) = Max(IC(c_{1}), IC(c_{2}))

Modularity and Function: Background Modularity in PPIs and DDIs Pathway Maps: Background

Constructing KEGG Crosstalk Map

Functional Similarity of Molecules with Sets of Terms

Average (Lord et al., Bioinformatics, 2003)

ρ_{A}(S_{i}, S_{j}) = \frac{1}{|S_{i}||S_{j}|} ∑_{c_{k}∈S_{i}} ∑_{c_{l}∈S_{j}} δ(c_{k}, c_{l})

Generalize the concept of lowest common ancestor to sets of terms (Pandey et al., ECCB, 2008)

Λ(S_{i}, S_{j}) = ⨆_{c_{k}∈S_{i},c_{l}∈S_{j}} λ(c_{k}, c_{l})

ρ_{I}(S_{i}, S_{j}) = I(Λ(S_{i}, S_{j})) = − log_{2} (\frac{|G_{Λ(S_{i},S_{j})} |}{|G_{r}|})

G_{Λ(S_{i},S_{j})} = ⋂_{c_{k}∈Λ(S_{i},S_{j})} G_{c_{k}} is the set of molecules that are

associated with all terms in the MCA set

Grama et al.

Modularity and Function: Background Modularity in PPIs and DDIs Pathway Maps: Background

Constructing KEGG Crosstalk Map

Functional Coherence of Module

A set of molecules that participates in the same biological processes or functions sub-network with dense intra-connections and sparse interconnections Each module is associated with set of molecular entities, and each molecule associated with set of terms.

S_{1} = {c_{4}}, S_{2} = {c_{4}}, S_{3} = {c_{4}, c_{6}}, S_{4} = {c_{1}, c_{6}},

S_{5} = {c_{1}}, S_{6} = {c_{6}} Sets:

R_{1} = {S_{1}, S_{2}, S_{3}, S_{4}}
R_{2} = {S_{1}, S_{2}, S_{3}}
R_{3} = {S_{3}, S_{4}}

Modularity and Function: Background Modularity in PPIs and DDIs Pathway Maps: Background

Constructing KEGG Crosstalk Map

Existing Measure

Average (Pu et al., Proteomics, 2007)

σ_{A}(R) = \frac{1}{n(n − 1)/2} ∑_{1≤i<j≤n}ρ(S_{i}, S_{j}).

Example: σ_{A}(S_{1}, S_{2}, S_{3}, S_{4}) =

\frac{1}{6}(3 ∗ σ_{A}(S_{1}, S_{2}, S_{3}) + ρ(S_{3}, S_{4}) + ρ(S_{1}, S_{4}) + ρ(S_{2}, S_{4}) )

Modularity and Function: Background Modularity in PPIs and DDIs Pathway Maps: Background

Constructing KEGG Crosstalk Map

Generalized Information Content

Extend the notion of the minimum common ancestor of pairs of terms to tuples of terms λ(c_{i_{1}}, …, c_{i_{n}}) = argmax_{c∈∩_{k=1}^{n}A_{i_{k}}}I(c)

σ_{I}(R) = I(Λ(S_{1}, …, S_{n})) = − log_{2} (\frac{|G_{Λ(S_{i},...,S_{j})} |}{|G_{r}|}) .

where

Λ(S_{1}, S_{2}, …, S_{n}) = ⨆_{c_{i_{j}}∈S_{j},1≤j≤n} λ(c_{i_{1}}, c_{i_{2}}, …, c_{i_{n}})

Example: σ_{I}(S_{1}, S_{2}, S_{3}, S_{4}) = I(r) = 0, no common ancestor!

Modularity and Function: Background Modularity in PPIs and DDIs Pathway Maps: Background

Constructing KEGG Crosstalk Map

Weighted Information Content

Weigh the information content of shared functionality by the number of molecules that contribute to the shared functionality

σ_{W}(R) = 1 − ∑_{1≤i≤n} ∑_{c∈A′_{i}} I(c) ∑_{1≤i≤n} ∑_{c∈A_{i}} I(c)

σ_{W}(S_{1}, S_{2}, S_{3}, S_{4}) = 0.86  σ_{W}(S_{1}, S_{2}, S_{3}) = 0.75

Modularity and Function: Background Modularity in PPIs and DDIs Pathway Maps: Background

Constructing KEGG Crosstalk Map

Accounting for Multiple Paths

Is "shortest path" a good measure of network proximity?

Multiple alternate paths might indicate stronger functional association In well-studied pathways, redundancy is shown to play an important role in robustness & adaptation (e.g., genetic buffering)

Modularity and Function: Background Modularity in PPIs and DDIs Pathway Maps: Background

Constructing KEGG Crosstalk Map

Random walks with restarts

Consider a random walker that starts on a source node s. At every tick, the walker chooses randomly among available edges or goes back to node s with probability c.

Modularity and Function: Background Modularity in PPIs and DDIs Pathway Maps: Background

Constructing KEGG Crosstalk Map

Proximity Based On Random Walks

Simulate an infinite random walk with random restarts at protein i Proximity between proteins i and j is given by the relative amount of time spent at protein j

Φ(0) = I, Φ(t + 1) = (1 − c)AΦ(t) + cI, Φ = lim_{t→∞}Φ(t)

Φ(i, j): Network proximity between protein i and protein j A: Stochastic matrix derived from the adjacency matrix of the network I: Identity matrix c: Restart probability

Define proximity between proteins i and j as {Φ(i, j) + Φ(j, i)}/2

Modularity and Function: Background Modularity in PPIs and DDIs Pathway Maps: Background

Constructing KEGG Crosstalk Map

Network Proximity & Functional Similarity

Correlation between functional similarity and network proximity

Modularity and Function: Background Modularity in PPIs and DDIs Pathway Maps: Background

Constructing KEGG Crosstalk Map

Topological Proximity and Functional Similarity

Comparison of the DDI and PPI networks with respect to the relation between semantic similarity vs proximity and network distance

Modularity and Function: Background Modularity in PPIs and DDIs Pathway Maps: Background

Constructing KEGG Crosstalk Map

Comparison of Coherence Meaures

Index of Dectectability vs. complex sizes

d(σ) = \frac{mean_{t∈T}(σ(t))−mean_{t∈C}(σ(t))}{\sqrt{((std_{t∈T}(σ(t)))^{2}+(std_{t∈C}(σ(t)))^{2})/2}}

Modularity and Function: Background Modularity in PPIs and DDIs Pathway Maps: Background

Constructing KEGG Crosstalk Map

Lessons Learned

Random walk based measures of topological proximity are better suited to existing interaction data Measures that quantify coherence among entire sets are superior to aggregares of known pair-wise measures

Modularity and Function: Background Modularity in PPIs and DDIs Pathway Maps: Background

Constructing KEGG Crosstalk Map

Part II

Building Pathway Maps Using Synthetic Lethality Networks

Modularity and Function: Background Modularity in PPIs and DDIs Pathway Maps: Background

Constructing KEGG Crosstalk Map Models and Definitions Datasets Functional Similarity of Gene Pairs Performance Evaluation and Identifying Shortcomings

Genetic Interactome

Double mutants exhibit unexpected phenotypes, as compared to joint single mutations.

Definition Negative Interactions: more severe phenotype than expected

Also known as aggravating or synergistic

Positive Interactions: Less severe phenotype than expected

Also known as alleviating or epistatic

Most commonly used: Phenotype : Growth rate

Model : Multiplicative null model

Modularity and Function: Background Modularity in PPIs and DDIs Pathway Maps: Background

Constructing KEGG Crosstalk Map Models and Definitions Datasets Functional Similarity of Gene Pairs Performance Evaluation and Identifying Shortcomings

Organization of Genetic Interactions

Definition Between-Pathway Model

Among genes participating in redundant functions

Within-Pathway Model

Among genes with additive effect

Indirect Effect

Among genes with distant functions that are not directly related

Modularity and Function: Background Modularity in PPIs and DDIs Pathway Maps: Background

Constructing KEGG Crosstalk Map Models and Definitions Datasets Functional Similarity of Gene Pairs Performance Evaluation and Identifying Shortcomings

Between-Pathway Model (BPM)

Bi-cliquish structure Have been used to:

1 Predict co-pathway membership of gene pairs

2 Extract redundant pathways

Modularity and Function: Background Modularity in PPIs and DDIs Pathway Maps: Background

Constructing KEGG Crosstalk Map Models and Definitions Datasets Functional Similarity of Gene Pairs Performance Evaluation and Identifying Shortcomings

The Genetic Landscape of a Cell

Adopted from Costanzo et al., 2010

Baker’s yeast,

Saccharomyces cerevisiae Synthetic Genetic Array (SGA) 1712 query genes

1 1378 null alleles of non-essential genes 2 334 hypomorphic or conditional alleles of essential genes

3885 array strains

Modularity and Function: Background Modularity in PPIs and DDIs Pathway Maps: Background

Constructing KEGG Crosstalk Map Models and Definitions Datasets Functional Similarity of Gene Pairs Performance Evaluation and Identifying Shortcomings

Functional Annotations

KEGG Pathway Database Annotations for 1026 genes in the experiment 96 Pathways

80 pathways after filtering pathways with less than 10 genes.

Modularity and Function: Background Modularity in PPIs and DDIs Pathway Maps: Background

Constructing KEGG Crosstalk Map Models and Definitions Datasets Functional Similarity of Gene Pairs Performance Evaluation and Identifying Shortcomings

Local Neighborhood Similarity

A Predictor of Co-Pathway Membership

Similarity prediction methods

1 Number of Shared Neighbors 2 Congruence Score 3 Pearson Correlation of Interaction Profiles

Both v_{i} and v_{j} have three shared neighbors. However, in the first case their congruence score is almost 0.6, while in the second case it is approximately 2 (assuming a graph of size 10).

Modularity and Function: Background Modularity in PPIs and DDIs Pathway Maps: Background

Constructing KEGG Crosstalk Map Models and Definitions Datasets Functional Similarity of Gene Pairs Performance Evaluation and Identifying Shortcomings

Evaluating Ranking Methods

Given a pathway P_{A} and a cut size (target set) l.

Definition

P − value(X = k) = Prob(k ≤ X)
= HGT (k|N, N_{A}, l)
= ∑_{x=k}^{min(N_{A},l)} \frac{C(l, x)C(N − l, N_{A} − x)}{C(N, N_{A})}

X: Random variable denoting the number of true positives in a random sample, N: Total number of gene pairs, N_{A}: Number of gene pairs in pathway A, l: Size of target set

Modularity and Function: Background Modularity in PPIs and DDIs Pathway Maps: Background

Constructing KEGG Crosstalk Map Models and Definitions Datasets Functional Similarity of Gene Pairs Performance Evaluation and Identifying Shortcomings

Minimum HyperGeometric (mHG) Score

Target size unknown:

Definition The Minimum HyperGeometric (mHG) score

mHG(λ) = min_{1≤l≤N}HGT (b_{l}(λ); N, N_{A}, l),

where b_{l}(λ) = ∑_{i=1}^{l} λ_{i}

λ_{i} is 1 if both of the genes in the i^{th} ranked gene pair are members of P_{A}, and 0 otherwise.

mHG Adjusted for Multiple Comparison

Modularity and Function: Background Modularity in PPIs and DDIs Pathway Maps: Background

Constructing KEGG Crosstalk Map Models and Definitions Datasets Functional Similarity of Gene Pairs Performance Evaluation and Identifying Shortcomings

Predictions Are Not Equally Accurate in Different KEGG Pathways

Modularity and Function: Background Modularity in PPIs and DDIs Pathway Maps: Background

Constructing KEGG Crosstalk Map Overview Methods Results and Discussions

Highlights

Basic Idea Heterogeneous performance of co-pathway membership predictions

⟺

Existence of specific structure around enriched pathways

Decomposing neighborhood of each pathway Inferring lethal crosstalk among pathways

Modularity and Function: Background Modularity in PPIs and DDIs Pathway Maps: Background

Constructing KEGG Crosstalk Map Overview Methods Results and Discussions

Modified Congruence Score (MCS)

Evaluating Neighborhood Overlap of Gene Pairs With Respect to a Given Pathway

Definition

P − value(X = k_{ij}^{B}) = Prob(k_{ij}^{B} ≤ X)
= HGT (k_{ij}^{B}|n_{B}, d_{i}^{B}, d_{j}^{B})

= ∑_{x=k_{ij}^{B}}^{min(d_{i}^{B},d_{j}^{B})} \frac{C(d_{j}^{B}, x)C(n_{B} − d_{j}^{B}, d_{i}^{B} − x)}{C(n_{B}, d_{i}^{B})}

MCS is defined as −log_{10} of the P-value.

Modularity and Function: Background Modularity in PPIs and DDIs Pathway Maps: Background

Constructing KEGG Crosstalk Map Overview Methods Results and Discussions

Modified Congruence Score (MCS)

continued

Example

A sample neighborhood configuration for v_{i} and v_{j}. Here n = 15, D_{i} = 6, D_{j} = 5, n_{B} = 6, d_{i} = 3, d_{j} = 4 and k = 2.

Modularity and Function: Background Modularity in PPIs and DDIs Pathway Maps: Background

Constructing KEGG Crosstalk Map Overview Methods Results and Discussions

Constructing Neighborhood Overlap Graph For a Given Pathway Pair

Definition The neighborhood overlap graph (NOG) of a given pathway P_{A} with respect to pathway P_{B}, denoted by H_{A→B} = (V_{H}, E_{H}), is an unweighted, undirected graph defined over same vertices as P_{A}. In this graph, there is a link between vertices v_{i} and v_{j} if the network structure around them with respect to P_{B} is statistically significant .

Modularity and Function: Background Modularity in PPIs and DDIs Pathway Maps: Background

Constructing KEGG Crosstalk Map Overview Methods Results and Discussions

Pruning neighborhood overlap graph, finding cohesive subgraphs, and identifying interaction ports

Adopted from Batagelj and Zaversnik, 2002

1 Iterative peeling of K-shells Pruning hairy components

2 Connected components in each core

3 Evaluating the significance of components

Evaluating significance using ER random graph model

Modularity and Function: Background Modularity in PPIs and DDIs Pathway Maps: Background

Constructing KEGG Crosstalk Map Overview Methods Results and Discussions

KEGG Crosstalk Map

Modularity and Function: Background Modularity in PPIs and DDIs Pathway Maps: Background

Constructing KEGG Crosstalk Map Overview Methods Results and Discussions

Interaction Port Case Study

Crosstalk Between Protein Processing in ER and Proteasome

Modularity and Function: Background Modularity in PPIs and DDIs Pathway Maps: Background

Constructing KEGG Crosstalk Map Overview Methods Results and Discussions

Summary

The local neghborhood similarity gives heterogeneous performance in predicting co-pathways membership of gene pairs. This phenomena is due to the specific structure around enriched pathways Decomposing the neighborhood around each pathway sheds light on the cellular machinery.

Future works:

Analysing the hierarchy of ports instead of the most significant interaction port. Using our methodology to uncover dependencies among functional pathways.

Appendix  For Further Reading

For Further Reading I

M. Costanzo et al. The Genetic Landscape of a Cell Science, 425 2010.

SJ. Dixon et al. Systematic Mapping of Genetic Interaction Networks Annual review of genetics, 43, 601 2009.

D. Segre et al. Modular Epistasis in Yeast Metabolism Nature Genetics, 37, 77 2005.

C.L. Tucker and S. Fields Lethal Combinations Nature Genetics, 35, 204 2003.