Background Methods Results

Functional Characterization and Topological Modularity of Molecular Interaction Networks

Jayesh Pandey^{1} Mehmet Koyutürk^{2} Ananth Grama^{1}

1Department of Computer Science Purdue University

2Department of Electrical Engineering & Computer Science Case Western Reserve University

Asia Pacific Bioinformatics Conference, 2010 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

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.

Background Methods Results

Function & Topology in Molecular Networks How does function relate to network topology?

Background Methods Results

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

Pandey, Koyutürk, Grama

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)

Background Methods Results

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

Background Methods Results

Functional Similarity of Molecules Each molecule (protein or domain) is associated with multiple GO 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

Pandey, Koyutürk, Grama

Background Methods Results

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

Background Methods Results

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

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!

Background Methods Results

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

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)

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.

Background Methods Results

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

Background Methods Results

Network Proximity & Functional Similarity

Correlation between functional similarity

and network proximity

Pandey, Koyutürk, Grama

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

Background Methods Results

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

Pandey, Koyutürk, Grama

Conclusion & Ongoing work 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 Future work : Using proximity measure to identify disease implicated genes in networks