Functional Characterization of Biological Networks

Jayesh Pandey

Department of Computer Science

December 3, 2009

university-logo

Outline

1 Background & Motivation Biological Networks Pathway Annotation

2 Formal Framework and Statistical Model Formal Framework Statistical Interpretability Statistical Model

3 Algorithms and Software

4 Results General results Case study

5 Functional Coherence & Network Proximity

6 Network Based Phenotype Analysis

7 Conclusions

university-logo

Background & Motivation

Outline

1 Background & Motivation Biological Networks Pathway Annotation

2 Formal Framework and Statistical Model Formal Framework Statistical Interpretability Statistical Model

3 Algorithms and Software

4 Results General results Case study

5 Functional Coherence & Network Proximity

6 Network Based Phenotype Analysis

7 Conclusions

Background & Motivation Biological Networks

Gene Regulatory Networks

Genes (and their products) regulate (promote / suppress) the extent of their expression Abstraction: organization of regulatory interactions in the cell

Genetic network in Tomato Fruit Ripening

Background & Motivation Biological Networks

Protein Interaction Networks

Interacting proteins can be identified via high throughput screening

Two-hybrid

Mass Spectrometry

Tandem affinity purification (TAP)

There are also many computational techniques for predicting functionally associated proteins

PPI network in Huntington’s disease

Background & Motivation Biological Networks

Molecular Annotation

Similar systems that involve different molecules (genes, proteins) in different species Functional annotation of genes provides a unified understanding of the underlying principles Gene Ontology A library of molecular annotations

Molecular function What is the role of a gene?

Biological Process In which processes is a gene involved? Cellular component Where is a gene’s product localized?

We refer to each annotation class as a functional attribute

Background & Motivation Pathway Annotation

From Molecules to Systems

Networks are species-specific Annotation is at the molecular level Map networks from gene space to function space

Network of GO terms based on significance of pairwise interactions in S. cerevisiae Synthetic Gene Array (SGA) network (Tong et al., Science, 2004)

Background & Motivation Pathway Annotation

Indirect Regulation

Assessment of pairwise interactions is simple, but not adequate

university-logo

Formal Framework and Statistical Model

Outline

1 Background & Motivation Biological Networks Pathway Annotation

2 Formal Framework and Statistical Model Formal Framework Statistical Interpretability Statistical Model

3 Algorithms and Software

4 Results General results Case study

5 Functional Coherence & Network Proximity

6 Network Based Phenotype Analysis

7 Conclusions

university-logo

Formal Framework and Statistical Model Formal Framework

Functional Attribute Network

Multigraph model

A gene is associated with multiple functional attributes A functional attribute is associated with multiple genes Functional attributes are represented by nodes Genes are represented by ports, reflecting context

Gene Network Functional Attribute Network

university-logo

Formal Framework and Statistical Model Formal Framework

Frequency of a Multipath

A pathway of functional attributes occurs in various contexts in the gene network

Multipath in the functional attribute network

Frequency of Multipath ?

Formal Framework and Statistical Model Formal Framework

Significance of a Pathway

We want to identify multipaths with unusual frequency

These might correspond to modular pathways

Frequency alone is not a good measure of statistical significance

The distribution of functional attributes among genes is not uniform The degree distribution in the gene network is highly skewed Pathways that contain common functional attributes have high frequency, but they are not necessarily interesting

university-logo

Formal Framework and Statistical Model Statistical Interpretability

Statistical Interpretability

We are interested in identifying statistically over-represented patterns

Null hypothesis: the pattern is sparse Additional positive observation => more significance Additional negative observation => less significance

Frequency is a monotonic measure

If a pathway is frequent, then all of its sub-paths are frequent Algorithmic advantage: enumerate all frequent patterns in a bottom-up fashion Commonly exploited in traditional data mining applications

Statistically interpretable measures are not monotonic!

Statistical significance fluctuates in the search space Existing data mining algorithms do not apply Significance of pathways are non-monotonic in two dimensions: GO Hierarcy & path space

Formal Framework and Statistical Model Statistical Interpretability

GO Hierarchy

A pattern corresponding to child may be more significant or less significant than that corresponding to its parent

Formal Framework and Statistical Model Statistical Interpretability

Pathway Length

A pattern corresponding to path may be more significant or less significant than that corresponding to an extended path

Formal Framework and Statistical Model Statistical Model

Insight

Emphasize modularity of pathways

Condition in frequency of building blocks Evaluate the significance of the coupling of building blocks

university-logo

Formal Framework and Statistical Model Statistical Model

Formulation

We denote each frequency random variable by ϕ, their observed value by φ

Significance of pathway π_{123} ( p_{123} ) is defined as

P(ϕ_{123} ≥ φ_{123}|ϕ_{12} = φ_{12}, ϕ_{23} = φ_{23}, ϕ_{1} = φ_{1}, ϕ_{2} = φ_{2}, ϕ_{3} = φ_{3})

Formal Framework and Statistical Model Statistical Model

Significance of a Pathway

Assume that interactions are independent

There are φ_{12}φ_{23} possible pairs of π_{12} and π_{23} edges The probability that a pair of π_{12} and π_{23} edges go through the same gene (corresponds to an occurrence of π_{123}) is 1/φ_{2}

The probability that at least φ_{123} of these pairs go through the same gene can be bounded by

p_{123} ≤ exp(φ_{12}φ_{23}H_{q}(t)) where q = 1/φ_{2} and t = φ_{123}/φ_{12}φ_{23} H_{q}(t) = t log(q/t) + (1 − t) log((1 − q)/(1 − t)) is divergence

For a single interaction, we use a background model that assumes arbitrary degree distribution

university-logo

Algorithms and Software

Outline

1 Background & Motivation Biological Networks Pathway Annotation

2 Formal Framework and Statistical Model Formal Framework Statistical Interpretability Statistical Model

3 Algorithms and Software

4 Results General results Case study

5 Functional Coherence & Network Proximity

6 Network Based Phenotype Analysis

7 Conclusions

Algorithms and Software

Algorithmic issues

Significance is not monotonic with respect to size

Need to enumerate all pathways?

Strongly significant pathways

A pathway is strongly significant if all of its building blocks and their coupling are significant (defined recursively) Allows pruning out the search space effectively

Shortcircuiting common functional attributes

Transcription factors, DNA binding genes, etc. are responsible for mediating regulation Shortcircuit these terms, consider regulatory effect of different processes on each other directly

Algorithms and Software

Narada

A software for identification of significant pathways Queries

Given functional attribute T , find all significant pathways that originate at T Given functional attribute T , find all significant pathways that terminate at T Given a sequence of functional attributes T_{1}, T_{2}, …, T_{k} find all occurrences of the corresponding pathway

Identified pathways are displayed as a tree

User can explore back and forth between the gene network and the functional attribute network

Algorithms and Software

Screenshot

university-logo

Results

Outline

1 Background & Motivation Biological Networks Pathway Annotation

2 Formal Framework and Statistical Model Formal Framework Statistical Interpretability Statistical Model

3 Algorithms and Software

4 Results General results Case study

5 Functional Coherence & Network Proximity

6 Network Based Phenotype Analysis

7 Conclusions

Results General results

Results

E. coli transcriptional network obtained from RegulonDB

3159 regulatory interactions between 1364 genes Using Gene Ontology, 904 of these genes are mapped to 340 processes

E. coli protein interaction network obtained from DIP

6958 interactions between 1841 proteins Using Gene Ontology, 793 proteins are mapped to 343 processes

Results General results

Global view of E. coli transcriptional Network

Results General results

Shortcircuiting mediators

Results General results

Global view of E. coli interaction Network

Results Case study

Molybdate ion transport

Results Case study

Molybdate ion transport

Results Case study

What is significant?

Molybdate ion transport regulates various processes directly

Mo-molybdopterin cofactor biosynthesis, oligopeptide transport, cytochrome complex assembly

It regulates various other processes indirectly

Through DNA-dependent regulation of transcription, two-component signal transduction system, nitrate assimilation Regulation of these mediator processes is not significant on itself! NARADA captures modularity of indirect regulation!

university-logo

Functional Coherence & Network Proximity

Outline

1 Background & Motivation Biological Networks Pathway Annotation

2 Formal Framework and Statistical Model Formal Framework Statistical Interpretability Statistical Model

3 Algorithms and Software

4 Results General results Case study

5 Functional Coherence & Network Proximity

6 Network Based Phenotype Analysis

7 Conclusions

university-logo

Functional Coherence & Network Proximity

Functional Coherence in Networks

Modularity manifests itself in terms of high connectivity in the network Functional association (similarity) is correlated with network proximity Protein-protein interaction (PPI) networks are used extensively for functional inference In PPI networks, functional coherence manifests itself in terms of network proximity

How about DDI "networks"?

Sharan et al., MSB, 2007

Functional Coherence & Network Proximity

Domain-Domain Interactions

Most proteins are composed of multiple domains Many domains are independent units reused in several related proteins Interactions between domains underlie observed protein-protein interactions Inferred by experimental and computational techniques

Functional Coherence & Network Proximity

Assessing Functional Similarity

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

Functional Coherence & Network Proximity

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}

Functional Coherence & Network Proximity

Functional Similarity of Molecules

Each molecule (protein or domain) is associated with multiple GO terms Available annotations are incomplete Domain annotations are often derived from protein annotations

A domain is associated with terms at the intersection of proteins that contain the domain

Is it possible to compare functional similarity between domains and functional similarity between proteins at all?

Functional Coherence & Network Proximity

Properties of Admissible Measures

What are the basic required properties of an admissible measure of similarity between two sets?

1 Symmetry: ρ(S_{i}, S_{j}) = ρ(S_{j}, S_{i}) for all S_{i}, S_{j} 2 Consistency: ρ(S_{i}, S_{j}) ≤ ρ(S_{j}, S_{j}) for all S_{i}, S_{j} 3 Monotonicity: ρ(S_{i}, S_{j}) ≤ ρ(S_{i} ∪ c_{k}, S_{j} ∪ c_{k}) 4 Generality: ρ(S_{i}, S_{j}) ≤ ρ(S_{i}, S_{j} ∪ S_{k}) for all S_{i}, S_{j}, S_{k}

Incompleteness-aware measures: No conclusions based on negative evidence!

Functional Coherence & Network Proximity

Illustration of Properties

S_{1} = {c_{4}} S_{2} = {c_{7}} S_{3} = {c_{6}} S_{4} = {c_{4}, c_{6}} S_{5} = {c_{6}, c_{7}} Monotonicity: ρ(S_{1}, S_{2}) ≤ ρ(S_{4}, S_{5}) Generality: ρ(S_{2}, S_{3}) ≤ ρ(S_{2}, S_{4})

university-logo

Functional Coherence & Network Proximity

Existing Measures are not Admissible

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

Fails consistency, monotonicity, generality

Maximum (Sevilla et al., IEEE TCBB, 2005)

ρ_{M}(S_{i}, S_{j}) = max_{c_{k}∈S_{i},c_{l}∈S_{j}} δ(c_{k}, c_{l})

Principle: Similarity in a single pair of terms is sufficient Fails monotonicity

Functional Coherence & Network Proximity

Existing Measures are not Admissible

Average of Maxima (Schlicker et al., Bioinformatics, 2007)

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

Principle: Similarity with a single term is sufficient for each term Fails consistency, monotonicity, generality

Functional Coherence & Network Proximity

Information Content Based Set Similarity

Generalize the concept of lowest common ancestor to sets of terms (Pandey, Koyutürk 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

university-logo

Functional Coherence & Network Proximity

Illustration of Information Content Based Measure

S_{1} = {c_{4}, c_{6}, c_{7}} S_{2} = {c_{4}} S_{3} = {c_{4}, c_{6}} S_{4} = {c_{6}, c_{7}} S_{5} = {c_{4}, c_{3}} λ(c_{4}, c_{4}) = c_{4}, λ(c_{6}, c_{4}) = λ(c_{7}, c_{4}) = R Λ(S_{1}, S_{2}) = {c_{4}} ⇒ ρ_{I}(S_{1}, S_{2}) = − log_{2}(|G_{c_{4}}|/|G_{R}|) = log_{2}(5/4) Λ(S_{1}, S_{3}) = {c_{4}, c_{6}} ⇒ ρ_{I}(S_{1}, S_{3}) = log_{2}(5/2)

Functional Coherence & Network Proximity

Information Content Based Measure Is Admissible

1 Symmetry: Trivially, ρ_{I}(S_{i}, S_{j}) = ρ_{I}(S_{j}, S_{i}) for all S_{i}, S_{j}. 2 Consistency: Clearly, c_{k} ⪯ λ(c_{k}, c_{l}) for any c_{k}, c_{l}. Now consider any

c_{m} ∈ Λ(S_{i}, S_{j}). Since c_{m} = λ(c_{k}, c_{l}) for some c_{k} ∈ S_{i} and c_{l} ∈ S_{j}, there always exists c_{n} ∈ Λ(S_{i}, S_{i}) such that c_{n} ⪯ c_{k} ⪯ c_{m}. Consequently, we must have G_{Λ(S_{i},S_{i})} ⊆ G_{Λ(S_{i},S_{j})} , leading to ρ_{I}(S_{i}, S_{j}) ≤ ρ_{I}(S_{i}, S_{i}).

3 Monotonicity: Since c_{k} ≁ c_{n} for all c_{n} ∈ S_{i} ∪ S_{j}, we have Λ(S_{i} ∪ c_{k}, S_{j} ∪ c_{k}) = Λ(S_{i}, S_{j}) ⊔ Λ(S_{i} ⊔ S_{j}, {c_{k}}) ⊔ {c_{k}} ⊇ Λ(S_{i}, S_{j}) ∪ {c_{k}}, leading to G_{Λ(S_{i}∪c_{k},S_{j}∪c_{k})} ⊆ G_{Λ(S_{i},S_{j})} and |G_{Λ(S_{i}∪c_{k},S_{j}∪c_{k})} | ≤ |G_{Λ(S_{i},S_{j})} |. Consequently, ρ_{I}(S_{i} ∪ c_{k}, S_{j} ∪ c_{k}) ≥ ρ_{I}(S_{i}, S_{j}).

4 Generality: Λ(S_{i}, S_{j} ∪ S_{k}) = Λ(S_{i}, S_{j}) ⊔ Λ(S_{i}, S_{k}) ⊒ Λ(S_{i}, S_{j}). Therefore, G_{Λ(S_{i},S_{j}∪S_{k})} ⊆ G_{Λ(S_{i},S_{j})} , leading to ρ_{I}(S_{i}, S_{j} ∪ S_{k}) ≥ ρ_{I}(S_{i}, S_{j}).

Functional Coherence & Network Proximity

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)

file=proximity.eps,width=0.9

Functional Coherence & Network Proximity

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

Functional Coherence & Network Proximity

Network Proximity & Functional Similarity

file=proxcomp.eps,width=0.75

Correlation between functional similarity and network proximity on nine PPI and DDI networks

Functional Coherence & Network Proximity

Comparison of PPI and DDI Networks

network distance[c][c]Network distance

semantic similarity[c][c]Average normalized semantic similarity

file=MFNr4.eps,width=0.9

Network distance vs. functional similarity based on molecular functions

Functional Coherence & Network Proximity

Comparison of PPI and DDI Networks

network distance[c][c]Network distance

semantic similarity[c][c]Average normalized semantic similarity

file=BPNr4.eps,width=0.9

Network distance vs. functional similarity based on biological processes

university-logo

Network Based Phenotype Analysis

Outline

1 Background & Motivation Biological Networks Pathway Annotation

2 Formal Framework and Statistical Model Formal Framework Statistical Interpretability Statistical Model

3 Algorithms and Software

4 Results General results Case study

5 Functional Coherence & Network Proximity

6 Network Based Phenotype Analysis

7 Conclusions

Network Based Phenotype Analysis

Proteomic Studies of Disease Markers

Human colorectal cancer

One out of every 19 individuals will be diagnosed with this disease in their lifetime We have to identify markers (for diagnosis), drug targets (for intervention), and mechanisms (for intelligent intervention)

file=coloncancer.eps,width=0.8

Network Based Phenotype Analysis

Traditional Approach

Differential gene expression

Collect tissue samples from affected and control individuals Measure mRNA expression for each gene, identify differentially expressed genes

Problems

Many differentially expressed genes (driver vs. passenger genes) mRNA expression captures activity to a limited extent Weak signals may be lost

file=difexp.eps,width=

Network Based Phenotype Analysis

Incorporating Protein Expression

Protein expression captures post-transcriptional activity better Can be measured using various screening techniques

2D-PAGE, Mass Spectrometry

Significantly less coverage compared to mRNA expression

Transcriptomic (mRNA expression) and proteomic (protein expression) data complement each other

file=./foldchange.eps, width=0.6

Network Based Phenotype Analysis

Proteomics-First Approach

Premise: Small changes in mRNA expression may lead to significant changes in post-transcriptional activity

Find "seed proteins" using 2D-PAGE

Map seed proteins on the PPI network

Refine subgraphs based on "collective" change in mRNA expression

file=pipeline.eps,width=

Network Based Phenotype Analysis

Finding Implicated Subgraphs

Compute topological scores for all proteins in the network

Proteins with high proximity to seed proteins have high topological scores Combine topological scores with differential expression to identify subgraphs with high topological score and significant differential expression when considered together

file=proteomic.eps,width=0.6

Network Based Phenotype Analysis

Computing Topological Scores

Proximity to a set of seed proteins

Generalize random walk with restarts: Restart at any of the seed proteins!

ϕ(0) = r, ϕ(t + 1) = (1 − c)Aϕ(t) + cr, ϕ = lim_{t→∞}ϕ(t)

ϕ(j): Proximity of protein j to seed proteins r : Restart vector, ||r||_{1} = 1 r(i) = |z_{i}| if fold change z_{i} of protein i is significant Prioritize all proteins in the network based on ϕ(j)

Network Based Phenotype Analysis

Genes Implicated by Network Proximity

file=./topological.eps, width=0.6

university-logo

Conclusions

Outline

1 Background & Motivation Biological Networks Pathway Annotation

2 Formal Framework and Statistical Model Formal Framework Statistical Interpretability Statistical Model

3 Algorithms and Software

4 Results General results Case study

5 Functional Coherence & Network Proximity

6 Network Based Phenotype Analysis

7 Conclusions

Conclusions

Conclusions

aaaaaa

further research

Avenues for Future Research

Avenues for Future Research

aaaaaa

further research

Thanks...

For their guidance and support

Ananth Grama Mehmet Koyuturk (Case Western)

For constructive feedback

Prof. Shankar Subramaniam of UCSD Wojciech Szpankowski Daisuke Kihara Alex Pothen

For productive and intriguing discussions

Members of Parallel & Distributed Systems Lab