Preliminary Motivation

Constructing KEGG Crosstalk Map Summary

Role of Synthetic Genetic Interactions in Understanding Functional Interactions Among Pathways

S. Mohammadi G. Kollias A. Grama

Department of Computer Science Purdue University

The Pacific Symposium on Biocomputing, 2012

Preliminary Motivation

Constructing KEGG Crosstalk Map Summary

Outline

1 Preliminary

Models and Definitions Datasets

2 Motivation

Functional Similarity of Gene Pairs Performance Evaluation and Identifying Shortcomings

3 Constructing KEGG Crosstalk Map

Overview Methods Results and Discussions

Preliminary Motivation

Constructing KEGG Crosstalk Map Summary Models and Definitions Datasets

Outline

1 Preliminary

Models and Definitions Datasets

2 Motivation

Functional Similarity of Gene Pairs Performance Evaluation and Identifying Shortcomings

3 Constructing KEGG Crosstalk Map

Overview Methods Results and Discussions

Preliminary Motivation

Constructing KEGG Crosstalk Map Summary Models and Definitions Datasets

Genetic Interactome

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

Definition Negative Interactions: more sever phenotype than expected

Also known as aggravating or synergistic

Positive Interactions: Less sever phenotype than expected

Also known as alleviating or epistatic

Most commonly used: Phenotype : Growth rate

Model : Multiplicative null model

Preliminary Motivation

Constructing KEGG Crosstalk Map Summary Models and Definitions Datasets

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

Preliminary Motivation

Constructing KEGG Crosstalk Map Summary Models and Definitions Datasets

Between-Pathway Model (BPM)

Bi-cliquish structure Have been used to:

1 Predict co-pathway membership of gene pairs

2 Extract redundant pathways

Preliminary Motivation

Constructing KEGG Crosstalk Map Summary Models and Definitions Datasets

Outline

1 Preliminary

Models and Definitions Datasets

2 Motivation

Functional Similarity of Gene Pairs Performance Evaluation and Identifying Shortcomings

3 Constructing KEGG Crosstalk Map

Overview Methods Results and Discussions

Preliminary Motivation

Constructing KEGG Crosstalk Map Summary Models and Definitions Datasets

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

Preliminary Motivation

Constructing KEGG Crosstalk Map Summary Models and Definitions Datasets

Functional Annotations

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

80 pathways after filtering pathways with less than 10 genes.

Preliminary Motivation

Constructing KEGG Crosstalk Map Summary Functional Similarity of Gene Pairs Performance Evaluation and Identifying Shortcomings

Outline

1 Preliminary

Models and Definitions Datasets

2 Motivation

Functional Similarity of Gene Pairs Performance Evaluation and Identifying Shortcomings

3 Constructing KEGG Crosstalk Map

Overview Methods Results and Discussions

Preliminary Motivation

Constructing KEGG Crosstalk Map Summary 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).

Preliminary Motivation

Constructing KEGG Crosstalk Map Summary Functional Similarity of Gene Pairs Performance Evaluation and Identifying Shortcomings

Outline

1 Preliminary

Models and Definitions Datasets

2 Motivation

Functional Similarity of Gene Pairs Performance Evaluation and Identifying Shortcomings

3 Constructing KEGG Crosstalk Map

Overview Methods Results and Discussions

Preliminary Motivation

Constructing KEGG Crosstalk Map Summary 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

Preliminary Motivation

Constructing KEGG Crosstalk Map Summary 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

Mohammadi et al.  Functional Decomposition of Genetic Networks

Preliminary Motivation

Constructing KEGG Crosstalk Map Summary Functional Similarity of Gene Pairs Performance Evaluation and Identifying Shortcomings

Predictions Are Not Equally Accurate in Different KEGG Pathways

Preliminary Motivation

Constructing KEGG Crosstalk Map Summary Overview Methods Results and Discussions

Outline

1 Preliminary

Models and Definitions Datasets

2 Motivation

Functional Similarity of Gene Pairs Performance Evaluation and Identifying Shortcomings

3 Constructing KEGG Crosstalk Map

Overview Methods Results and Discussions

Preliminary Motivation

Constructing KEGG Crosstalk Map Summary 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

Preliminary Motivation

Constructing KEGG Crosstalk Map Summary Overview Methods Results and Discussions

Outline

1 Preliminary

Models and Definitions Datasets

2 Motivation

Functional Similarity of Gene Pairs Performance Evaluation and Identifying Shortcomings

3 Constructing KEGG Crosstalk Map

Overview Methods Results and Discussions

Preliminary Motivation

Constructing KEGG Crosstalk Map Summary 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.

Preliminary Motivation

Constructing KEGG Crosstalk Map Summary 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.

Preliminary Motivation

Constructing KEGG Crosstalk Map Summary 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 .

Preliminary Motivation

Constructing KEGG Crosstalk Map Summary 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

Preliminary Motivation

Constructing KEGG Crosstalk Map Summary Overview Methods Results and Discussions

Outline

1 Preliminary

Models and Definitions Datasets

2 Motivation

Functional Similarity of Gene Pairs Performance Evaluation and Identifying Shortcomings

3 Constructing KEGG Crosstalk Map

Overview Methods Results and Discussions

Preliminary Motivation

Constructing KEGG Crosstalk Map Summary Overview Methods Results and Discussions

KEGG Crosstalk Map

Preliminary Motivation

Constructing KEGG Crosstalk Map Summary Overview Methods Results and Discussions

Interaction Port Case Study

Crosstalk Between Protein Processing in ER and Proteasome

Preliminary Motivation

Constructing KEGG Crosstalk Map Summary

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.