\documentclass[landscape,dvips]{foils}

%\documentclass[a4paper,landscape,headrule]{foil


%\usepackage[latin1]{inputenc}
%\usepackage{graphicx}

\MyLogo{Slide}

\usepackage{amsmath,amsthm,amssymb,amscd}
\usepackage{alltt}
\usepackage{epsf}
%\usepackage{amsfonts}
\def\w{{\cal W}}
\usepackage{latexsym}
\usepackage{times}
\usepackage{bookman}
\usepackage{graphics}
\usepackage{color}
\usepackage{epsfig}
\usepackage{psfrag}
\usepackage[ps2pdf]{hyperref}

\newcommand{\img}[2]{{\\epsfxsize=#1truecm\epsfbox{Images/PS/#2}}}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{corollary}{Corollary}
\newtheorem{definition}{Definition}
\newtheorem{proposition}{Proposition}

\def\basswidt{4.0in}
\def\gutter{0.2in}

\newenvironment{comment}{\setbox0=\vbox\bgroup}{\egroup}
\newenvironment{singlespace}{\def\baselinestretch{1.0}\large\normalsize}{\par}

%\setlength{\textheight}{8.5in}
%\setlength{\textwidth}{6in}
\setlength{\textheight}{8in}
\setlength{\textwidth}{9in}
\voffset=-0.9in

\newcommand{\ie}{{\sl i.e.}}

\newcommand{\support}{{\sigma}}
\newcommand{\freq}{{\xi}}
\newcommand{\minsup}{{\sigma^{*}}}
\newcommand{\minfreq}{{\xi^{*}}}
%\newcommand{\I}{{\cal{I}}}
%\newcommand{\T}{{\cal{T}}}
\newcommand{\A}{{\cal{A}}}
\newcommand{\G}{{\cal{G}}}
\newcommand{\F}{{\cal{F}}}
\newcommand{\E}{{\cal{E}}}
\newcommand{\V}{{\cal{V}}}
\newcommand{\La}{{\cal{L}}}
\newcommand{\lgraph}{{G=(V,E,\La)}}
\newcommand{\ugraph}{{\bar{G}=(\bar{V},\bar{E},\La)}}
\def\M{{\cal M}}
\def\N{{\cal N}}
\def\D{{\cal D}}
\def\vv{{\mathbf v}}
\def\uu{{\mathbf u}}

\newcommand{\blue}[1]{{\color{blue} #1}}
\newcommand{\green}[1]{{\color{green} #1}}
\newcommand{\red}[1]{{\color{red} #1}}
\newcommand{\stitle}[1]{\foilhead{\red{#1}}}
\newcommand{\bigitem}[2]{\item{#1\begin{small}\begin{itemize}#2\end{itemize}\end{small}}}
\newcommand{\mcite}[3]{\small{\red{[#1, {\sl #2}, #3]}}}
\newcommand{\eg}{{\sl e.g.}}

\leftheader{Comparative Analysis of Networks}
\rightheader{Chania, 2008}                % \filedate is defined above

\begin{document}

\title{
\red{Comparative Analysis of\\Molecular Interaction Networks}
}

\author{\\\\
\blue{Jayesh Pandey$^1$, Mehmet Koyuturk$^2$, Shankar Subramaniam$^3$,} \\
\blue{Ananth Grama$^1$}\\ \\
{$^1$Purdue University, $^2$Case Western Reserve University}\\
{$^3$University of California, San Diego}\\
}

\date{}
\maketitle


\noindent
{\small{This work is supported by National Institutes of Health,
National Science Foundation, and Intel.}}

\thispagestyle{empty}



%Slide
\stitle{Outline}

\begin{itemize}
\item
Why is comparative interactomics computationally challenging?
\item
Some results in conservation, alignment, and modularity.
\item
Statistical significance as an optimization metric for algorithms.
\item
Some open problems in computational interactomics.
\end{itemize}

\stitle{Challenges in Computational Analysis}

\begin{itemize}
\item
Isomorphism Hurts!
  \begin{itemize}
  \item
	Given two networks (unlabeled or labeled with potentially
	repeating node labels), are they identical?
	(complexity unknown)
  \item
	Given two networks (unlabeled or labeled with potentially
        repeating node labels), what is the largest common
	component (NP Hard!).
  \end{itemize}
\item
Must rely on nature of model and network -- emphasizes analysis!
\item
Analytical modeling of specific network structures is in relative infancy.
(e.g., what is the expected size of a clique in a scale-free graph?)
\item
Quantification of significance (e.g., p-values) is hard!
\end{itemize}


\stitle{Challenges in Computational Analysis: Thesis}

\begin{itemize}
\item
	Use a mix of modeling and measures to render problems easier.
\item
	Use nature of underlying networks to develop effective algorithms.
\item
	Use analysis to support claims of algorithmic effectiveness and
	efficiency.
\end{itemize}

\stitle{Conservation in Interaction Networks}

\begin{itemize}

\item{``Evolution thinks modular''\mcite{Vespignani}{Nature Gen.}{2003}}

\bigitem{Cooperative tasks require all participating units}
 {\item Selective pressure on preserving \blue{interactions} \& \blue{interacting proteins}
\item{\blue{Interacting proteins} follow similar evolutionary trajectories
\mcite{Pellegrini et al.}{PNAS}{1999}}
}

\bigitem{Orthologs of \blue{interacting proteins} are likely to interact \mcite{Wagner}{Mol. Bio. Evol.}{2001}}
{\item Conservation of \blue{interactions} may provide clues relating to
conservation of \blue{function}}

\item Modular conservation and alignment hold the key to critical structural,
functional, and evolutionary concepts in \blue{systems biology}
\end{itemize}

\stitle{Conserved Interaction Patterns}

\begin{itemize}
\bigitem{Given a collection of interaction networks
         (belonging to different species), find \blue{sub-networks} that
         are common to an \blue{interesting} subset of these
         networks.}
{
\item A sub-network is a group of interactions inducing a single network
      (\blue{connected})
\item Frequency: The number of networks that contain a sub-network,
      is a coarse measure of \blue{statistical significance}
}

\bigitem{Computational challenges}
{
\item How to \red{relate} molecules in different contexts/ organisms?
\item Requires solution of the intractable \red{subgraph isomorphism} problem
\item Must be scalable to potentially \red{large} number of networks
\item Networks are \red{large} [in the range of $10K$ edges]
}
\end{itemize}


\stitle{Relating Proteins in Different Species}{
\begin{itemize}
\bigitem{Ortholog Databases}
{
\item PPI networks: COG, Homologene, Pfam, ADDA
\item Metabolic pathways: Enzyme nomenclature
\item \blue{Reliable}, but \red{conservative}
\item Domain families rely on domain information, but the underlying
domains for most interactions are unknown $\Rightarrow$ \red{Multiple
node labels}
}

\bigitem{Sequence Clustering}
{
\item Cluster protein sequences and label proteins according to this clustering
\item \blue{Flexible}, but \red{expensive} and \red{noisy}
}

\bigitem{Labels may span a large range of \blue{functional relationships},
from protein families to ortholog groups}
{
\item Without loss of generality, we call identically labeled proteins as
\green{orthologs}
}

\end{itemize}


%Slide
\stitle{Problem Statement}

\begin{itemize}
\bigitem{Given a set of \blue{proteins} $V$, a set of
\green{interactions} $E$, and a \red{many-to-many} mapping from $V$ to
a set of \blue{ortholog groups} $\La=\{l_1,l_2,...,l_n\}$,
the corresponding interaction network is a \green{labeled graph}
$G=(V,E,\La)$.}
{
 \item $v \in V(G)$ is associated with a set of
ortholog groups $L(v) \subseteq \La$.
 \item $uv \in E(G)$ represents an interaction between $u$ and $v$.
}
\item
$S$ is a \green{sub-network} of  $G$, \ie, $S \sqsubseteq G$
if there is an \blue{injective} mapping  $\phi:V(S)\rightarrow V(G)$ such
that for all $v\in V(S)$, $L(v) \subseteq L(\phi(v))$ and for all
$uv \in E(S)$, $\phi(u)\phi(v)\in E(G)$.

\end{itemize}

\stitle{Computational Problem}

\begin{itemize}
\bigitem{\green{Conserved sub-network discovery}}
{
\item
\blue{Instance:} A set of interaction networks
$\G=\{G_1=(V_1,E_1,\La),G_2=(V_2,E_2,\La),...,G_m=(V_m,E_m,\La)\}$,
each belonging to a different organism, and a \green{frequency} threshold
$\minsup$.
\item
\blue{Problem:} Let $H(S)=\{G_i:S\sqsubseteq G_i\}$ be the \green{occurrence} set
of graph $S$. Find all \blue{connected} subgraphs $S$ such that
$|H(S)|\geq \minsup$, \ie, $S$ is a \green{frequent} subgraph
in $\G$ and for all $S' \sqsupset S$, $H(S) \neq H(S')$, \ie,
$S$ is \red{maximal}.
}
\end{itemize}

%Slide
\stitle{Algorithmic Insight: Ortholog Contraction}

\begin{itemize}
\item {\blue{Contract orthologous nodes into a single node}}
\bigitem {\green{No} \red{subgraph isomorphism}}
{\item Graphs are \blue{uniquely identified} by their edge sets}
\bigitem{\blue{Key observation:} Frequent sub-networks are \green{preserved} $\Rightarrow$ \green{No} \red{information loss}}
{\item Sub-networks that are frequent in general graphs are also frequent in
       their ortholog-contracted representation
 \item Ortholog contraction is a powerful \blue{pruning heuristic}
}
\bigitem{Discovered frequent sub-networks are still \green{biologically interpretable}!}
{
\item Interaction between proteins becomes interaction between ortholog groups
}

\end{itemize}
}

%Slide
\stitle{Ortholog Contraction in Metabolic Pathways}

\begin{itemize}
\bigitem{Directed hypergraph $\rightarrow$ uniquely-labeled directed graph}
{\item Nodes represent enzymes
 \item Global labeling by enzyme nomenclature (EC numbers)
 \item A directed edge from one enzyme to the other implies that the second consumes
       a product of  the first}
\end{itemize}

\vspace{0.2in}
\centerline{\begin{psfrags}\begin{small}
\psfrag{C267}[c][c]{\green{267}}
\psfrag{C221}[c][c]{\green{221}}
\psfrag{C668}[c][c]{\green{668}}
\psfrag{C1172}[c][c]{\green{1172}}
\psfrag{5133}[c][c]{\blue{5.1.3.3}}
\psfrag{2711}[c][c]{\blue{2.7.1.1}}
\psfrag{2712}[c][c]{\blue{2.7.1.2}}
\psfrag{27163}[c][c]{\blue{2.7.1.63}}
\epsfig{file=patcontract.eps,height=4in}
\end{small}\end{psfrags}}




%Slide
\stitle{Ortholog Contraction in PPI Networks}

\begin{itemize}
\item Interaction between \blue{proteins} $\rightarrow$ Interaction between \green{ortholog groups} or \green{protein families}
\end{itemize}

\vspace{0.5in}
\centerline{\begin{psfrags}\begin{small}
\psfrag{Rrp4}[c][c]{Rrp4}
\psfrag{Rrp43}[c][c]{Rrp43}
\psfrag{Mtr3}[c][c]{Mtr3}
\psfrag{Ski6}[c][c]{Ski6}
\psfrag{Csr4}[c][c]{Csr4}
\psfrag{3013}[c][c]{\red{KOG3013}}
\psfrag{1613}[c][c]{{\color{yellow}KOG1613}}
\psfrag{1068}[c][c]{\green{KOG1068}}
\psfrag{3409}[c][c]{\blue{KOG3409}}
\epsfig{file=lgraph.eps,height=2.5in}
\end{small}\end{psfrags}}

%Slide
\stitle{Results: Analyzing PPI Networks}

\begin{itemize}
\bigitem{PPI networks for \blue{9 eukaryotic organisms} derived from BIND and DIP}
{\item {\sl A. thaliania, O. sativa, S. cerevisiae, C. elegans, D. melanogaster,
            H. sapiens, B. taurus, M. musculus, R. norvegicus}
 \item \# of \green{proteins} ranges from 288 ({\sl Arabidopsis}) to 8577 ({\sl fruit fly})
 \item \# of \green{interactions} ranges from 340 ({\sl rice}) to 28829 ({\sl fruit fly})
}
\bigitem{Ortholog contraction}
{\item Group proteins according to existing \blue{COG} ortholog clusters
 \item Merge \blue{Homologene} groups into COG clusters
 \item Cluster remaining proteins via \blue{BLASTCLUST}
 \item Ortholog-contracted {\sl fruit fly} network contains 11088 \green{interactions}
 between 2849 \green{ortholog groups}
}

\item {\sc Mule} is available at \\
\blue{\url{http://www.cs.purdue.edu/pdsl/}}
\end{itemize}

\stitle{Conserved Protein Interaction Patterns}

\vspace{1in}
\centerline{
\begin{psfrags}
\scriptsize
\psfrag{Pattern}[c][c]{{\sl Pattern}}
\psfrag{CE}[lt][lt]{{\sl C. elegans}}
\psfrag{SC}[l][l]{{\sl S. cerevisiae}}
\psfrag{DM}[ct][ct]{{\sl D. melanogaster}}
\leavevmode
\epsfig{file=ribon.eps, width=4.5in}
\end{psfrags}
}
\vspace{0.5in}
\centerline{\blue{Small nuclear ribonucleoprotein complex} (\green{$p < 2e-43$})}

\stitle{Conserved Protein Interaction Patterns}

\vspace{1in}
\centerline{
\begin{psfrags}
\scriptsize
\psfrag{Pattern}[c][c]{{\sl Pattern}}
\psfrag{HS}[c][c]{{\sl H. sapiens}}
\psfrag{SC}[c][c]{{\sl S. cerevisiae}}
\psfrag{BT}[c][c]{{\sl B. taurus}}
\leavevmode
\epsfig{file=arp23.eps, width=4.5in}
\end{psfrags}
}
\vspace{0.5in}
\centerline{\blue{Actin-related protein Arp2/3 complex} (\green{$p < 9e-11$})}

\stitle{Conserved Protein Interaction Patterns}

\vspace{1in}
\centerline{
\begin{psfrags}
\scriptsize
\psfrag{Pattern}[c][c]{{\sl Pattern}}
\psfrag{HS}[c][c]{{\sl H. sapiens}}
\psfrag{DM}[c][c]{{\sl S. cerevisiae}}
\psfrag{SC}[l][l]{{\sl D. melanogaster}}
\leavevmode
\epsfig{file=vac.eps, width=6in}
\end{psfrags}
}
\vspace{0.5in}
\centerline{\blue{Endosomal sorting} (\green{$p < 1e-78$})}


%Slide
\stitle{Discussion}
\begin{itemize}
\bigitem{Ortholog contraction is \green{fast} \& \green{scalable}}
{
\item \blue{Graph cartesian product} based methods \mcite{Sharan et al.}{PNAS}{2004},
\mcite{Koyut\"urk et al.}{RECOMB}{2005} create \blue{$m^n$} product
nodes for an ortholog group that has $m$ proteins in each of $n$ organisms
\item \green{Ortholog contraction} represents the same group with only
\green{$n$} contracted nodes
\item Isomorphism-based graph analysis algorithms \red{do not scale} to large networks
}
\item Ortholog contraction implicitly \green{accounts for noise} by eliminating false positives by
thresholding frequency, and false negatives by contraction

\item
Key Open Problems: (i) Frequency is not significance (ii) How do we
compute optimal ortholog groups?

\end{itemize}


%Slide
\stitle{Alignment of PPI Networks}

\begin{itemize}

\bigitem{Given two PPI networks that belong to two different organisms,
identify sub-networks that are \blue{similar} to each other}
{\item \blue{Biological implications}
 \item \green{Mathematical modeling}}

\bigitem{Existing algorithms}
{\item PathBLAST aligns \blue{pathways} (linear chains) to simplify the problem while maintaining biological meaning
\mcite{Kelley et al.}{PNAS}{2004}
\item NetworkBLAST compares \blue{conserved complex model} with \green{null model} to identify significantly conserved subnets
\mcite{Sharan et al.}{J. Comp. Biol.}{2005}
}

\bigitem{Our approach:}
{\item Guided by \blue{models of evolution}
 \item \blue{Scores} evolutionary events
 \item Identifies sets of proteins that induce \green{high-scoring sub-network pairs}
}

\end{itemize}

%Slide
\stitle{Match, Mismatch, and Duplication}

\begin{itemize}
\bigitem{Evolutionary events as graph-theoretic concepts}
{\item A \green{match} $\in \M$ corresponds to two pairs of homolog proteins from each organism
       such that both pairs interact in both PPIs. A match is associated with
       \green{score} $\mu$.
\item A \red{mismatch} $\in \N$ corresponds to two pairs of homolog proteins from each organism such that
      only one pair is interacting. A mismatch is associated with
       \red{penalty} $\nu$.
\item A \blue{duplication} $\in D$ corresponds to a pair of homolog proteins that are in the same organism. A duplication is associated with \blue{score} $\delta$.
}
\end{itemize}

\centerline{
\begin{psfrags}
%\small
\psfrag{u1}[c][c]{$u_1$}
\psfrag{u2}[c][c]{$u_2$}
\psfrag{u3}[c][c]{$u_3$}
\psfrag{u4}[c][c]{$u_4$}
\psfrag{v1}[c][c]{$v_1$}
\psfrag{v2}[c][c]{$v_2$}
\psfrag{v3}[c][c]{$v_3$}
\psfrag{e1}[c][c]{$e_1$}
\psfrag{e2}[c][c]{$e_2$}
\psfrag{e3}[c][c]{$e_3$}
\psfrag{G}[c][c]{$G$:}
\psfrag{H}[c][c]{$H$:}
\leavevmode
\epsfig{file=alignment.eps, width=5in}
\end{psfrags}
}

%Slide
\stitle{Scoring Matches, Mismatches and Duplications}

\begin{itemize}
\bigitem{Quantifying similarity between two proteins}
{ \item \blue{Confidence} in two proteins being \blue{orthologous}
   \item BLAST E-value: $S(u,v) = log_{10}\frac{p(u,v)}{p_{random}}$
  \item Ortholog clustering: $S(u,v)=c(u)c(v)$
}

\bigitem{\green{Match score}}
{\item $\mu(uu',vv') = \bar{\mu} \min\{S(u,v),S(u',v')\}$}

\bigitem{\red{Mismatch penalty}}
{\item $\nu(uu',vv') = \bar{\nu} \min\{S(u,v),S(u',v')\}$}

\bigitem{\blue{Duplication score}}
{\item $\delta(u,u') = \bar{\delta} (\hat{\delta}-S(u,u'))$
\item $\hat{\delta}$ specifies threshold for sequence similarity to be considered functionally conserved
}
\end{itemize}

%Slide
\stitle{Pairwise Alignment of PPIs as an Optimization Problem}

\begin{itemize}
\bigitem {\blue{Alignment score:}\\
$\sigma(\A(P))= \sum_{M \in \M}{\mu(M)} - \sum_{N \in \N}{\nu(N)}
           + \sum_{D \in \D}{\delta(D)}$}
{ \item Matches are rewarded for \green{conservation} of interactions
 \item Duplications are rewarded/penalized for functional \green{conservation}/\red{differentiation} after split
 \item Mismatches are penalized for functional \red{divergence} (what about experimental error?)
}

\item Scores are functions of similarity between associated proteins

\bigitem{\green{Problem:} Find all protein subset pairs with significant alignment score}
{\item High scoring protein subsets are likely to correspond to conserved
       modules}

\item A graph equivalent to BLAST
\end{itemize}


%Slide
\stitle{Weighted Alignment Graph}

\begin{itemize}
\item $\mathbf{G}(\mathbf{V},\mathbf{E}):$ $\mathbf{V}$ consists of all pairs of homolog proteins $\mathbf{v}=\{u\in U, v \in V\}$
\bigitem{An edge $\mathbf{vv'}=\{uv\}\{u'v'\}$ in $\mathbf{E}$ is a}
{\item \green{match edge} if $uu' \in E$ and $vv' \in V$, with weight
       $w(\mathbf{vv'})=\mu(uv,u'v')$
 \item \red{mismatch edge} if $uu' \in E$ and $vv' \notin V$ or vice versa, with weight
       $w(\mathbf{vv'})=-\nu(uv,u'v')$
 \item \blue{duplication edge} if $S(u,u') > 0$ or $S(v,v')>0$, with weight
       $w(\mathbf{vv'})=\delta(u,u')$ or $w(\mathbf{vv'})=\delta(v,v')$}

\end{itemize}

\vspace{0.3in}
\centerline{
\begin{psfrags}
\small
\psfrag{u1v1}[r][r]{$\{u_1,v_1\}$}
\psfrag{u2v1}[l][l]{$\{u_2,v_1\}$}
\psfrag{u3v3}[c][c]{$\{u_3,v_3\}$}
\psfrag{u4v2}[l][l]{$\{u_4,v_2\}$}
\psfrag{u4v4}[r][r]{$\{u_4,v_4\}$}
\psfrag{m}[c][c]{$\mu$}
\psfrag{n}[c][c]{-$\nu$}
\psfrag{d}[c][c]{-$\delta$}
\leavevmode
\epsfig{file=product.eps, height=3in}
\end{psfrags}
}

%Slide
\stitle{Maximum Weight Induced Subgraph Problem}

\begin{itemize}
\bigitem{\blue{Definition:} (\green{{\sc MaWISh}})}
{\item Given graph $\G(\V,\E)$ and a constant $\epsilon$,
find $\tilde{\V} \in \V$ such that
$\sum_{\vv,\uu \in \tilde{\V}}{w(\vv\uu)} \geq \epsilon$.
 \item NP-complete by reduction from Maximum-Clique
}

\bigitem{\blue{Theorem:} (\green{{\sc MaWISh} $\equiv$ Pairwise alignment})}
{\item If $\tilde{\V}$ is a solution for the {\sc MaWISh} problem on $\G(\V,\E)$,
then $P=\{\tilde{U}, \tilde{V}\}$ induces an alignment
$\A(P)$ with $\sigma(\A) \geq \epsilon$ , where
$\tilde{\V} = \tilde{U} \times \tilde{V}$.}

\bigitem{\blue{Solution:} \green{Local} graph expansion}
{
\item Greedy graph growing + iterative refinement
\item Linear-time heuristic
}

\item{Source code available at \\
\blue{\url{http://www.cs.purdue.edu/pdsl/}}}
\end{itemize}

\stitle{Alignment of Yeast and Fruit Fly PPI Networks}

\begin{center}
\begin{small}
\begin{tabular}{lcccccc}
\hline\hline
\blue{Rank} & \green{Score} & \red{$z$-score} & \blue{\# Proteins} & \green{\# Matches} & \red{\# Mismatches} & \blue{\# Dups.}\\
\hline\hline
1 & 15.97 & 6.6 & 18 (16, 5) & 28 & 6 & (4, 0)\\
 & \multicolumn{6}{l}{protein amino acid phosphorylation (69\%)}\\
  &  \multicolumn{6}{l}{JAK-STAT cascade (40\%)}\\
\hline
2 & 13.93 & 3.7 & 13 (8, 7) & 25 & 7 & (3, 1)\\
 & \multicolumn{6}{l}{endocytosis (50\%) / calcium-mediated signaling (50\%)}\\
\hline
5 & 8.22 & 13.5 & 9 (5, 3) & 19 & 11 & (1, 0)\\
 & \multicolumn{6}{l}{invasive growth (sensu Saccharomyces) (100\%)}\\
 &  \multicolumn{6}{l}{oxygen and reactive oxygen species metabolism (33\%)}\\
\hline
6 & 8.05 & 7.6 & 8 (5, 3) & 12 & 2 & (0, 1)\\
 & \multicolumn{6}{l}{ubiquitin-dependent protein catabolism (100\%)}\\
 &  \multicolumn{6}{l}{mitosis (67\%)}\\
\hline
21 & 4.36 & 6.2 & 9 (5, 4) & 18 & 13 & (0, 5)\\
 & \multicolumn{6}{l}{cytokinesis (100\%, 50\%)}\\
\hline
30 & 3.76 & 39.6 & 6 (3, 5) & 5 & 1 & (0, 6)\\
 & \multicolumn{6}{l}{DNA replication initiation (100\%, 80\%)}\\
\hline\hline
\end{tabular}
\end{small}
\end{center}

\stitle{Subnets Conserved in Yeast and Fruit Fly}

\vspace{0.5in}
\centerline{Proteosome regulatory particle subnet}
\vspace{0.2in}
\begin{psfrags}
\begin{scriptsize}
\psfrag{SC}[c][c]{{\sl S.Cerevisiae}}
\psfrag{DM}[c][c]{{\sl D.Melanogaster}}
\centerline{\epsfig{file=4932_7227_6.eps, width=5.0in}}
\end{scriptsize}
\end{psfrags}

\vspace{0.5in}
\centerline{Calcium-dependent stress-activated signaling pathway}
\vspace{0.2in}
\begin{psfrags}
\begin{scriptsize}
\psfrag{SC}[c][c]{{\sl S.Cerevisiae}}
\psfrag{DM}[c][c]{{\sl D.Melanogaster}}
\centerline{\epsfig{file=4932_7227_2.eps, width=5.0in}}
\end{scriptsize}
\end{psfrags}

\stitle{Discussion}

\begin{itemize}
\bigitem{Comparison to other approaches: NetworkBlast~\mcite{Sharan et al.}{PNAS}{2005}, NUKE~\mcite{Novak et al.}{Genome Informatics}{2005}}
{\item \green{Faster} than NetworkBLAST, but provides \red{less coverage}
 \item Comparable to NUKE depending on speed vs coverage trade-off
}

\bigitem{Scores evolutionary events}
{\item \green{Flexible}, allows incorporation of different evolutionary models,
experimental bases, target structures
 \item Somewhat \red{ad-hoc}, what is a good weighting of scores?
}
\end{itemize}


\stitle{Analytical Assessment of Statistical Significance}

\begin{itemize}

\item{What is the \green{significance} of a \blue{dense} component in a network?}

\item{What is the \green{significance} of a \blue{conserved} component in multiple networks?}

\bigitem{Existing techniques}
{
\item Mostly computational (\eg, Monte-Carlo simulations)
\item Compute probability that \red{the} pattern exists rather than
      \green{a} pattern with \blue{the property} (\eg, size, density) exists
\item \red{Overestimation of significance}
}
\end{itemize}

\stitle{Random Graph Models}

\begin{itemize}

\item Interaction networks generally exhibit \blue{power-law} property (or
exponential, geometric, etc.)
\item Analysis simplified through \green{independence} assumption \mcite{Itzkovitz et al.}{Physical Review}{2003}
\item Independence assumption may cause problems for networks with
\blue{arbitrary degree distribution}
\item $P(uv \in E) = d_ud_v/|E|$, where $d_u$ is expected degree
of $u$, but generally $d_{\max}^2 > |E|$ for PPI networks

\bigitem{Analytical techniques based on simplified
 models~\mcite{Koyut\"urk, Grama, Szpankowski}{RECOMB}{2006}}
{\item \green{Rigorous analysis} on $G(n,p)$ model
 \item Extension to piecewise $G(n,p)$ to \blue{capture network characteristics}
       more accurately}
\end{itemize}

\stitle{Significance of Dense Subgraphs}
\begin{itemize}
\item{A subnet of $r$ proteins is said to be \blue{$\rho$-dense} if
$F(r) \geq \rho r^2$, where $F(r)$ is the number of interactions
between these $r$ proteins}

\bigitem{What is the expected size of the \green{largest}
$\rho$-dense subgraph in a \red{random graph}?} {\item Any
$\rho$-dense subgraph with \green{larger size} is
\blue{statistically significant}!}

\bigitem{$G(n,p)$ model}{
\item $n$ proteins, each interaction occurs with probability $p$
\item \blue{Simple} enough to facilitate rigorous analysis
\item If we let $p=d_{\max}/n$, largest $\rho$-dense subgraph in $G(n,p)$
\green{stochastically dominates} that in a graph with arbitrary
degree distribution }

\bigitem{Piecewise $G(n,p)$ model}{
\item \green{Few proteins} with \blue{many interacting partners}, \green{many proteins} with \blue{few interacting
partners}
\item Captures the basic characteristics of PPI networks
\item Analysis of $G(n,p)$ model immediately generalized to this model
}
\end{itemize}

\stitle{Largest Dense Subgraph}

\begin{itemize}
\item
\blue{Theorem:}
If $G$ is a random graph with $n$ nodes, where every edge exists
with probability $p$, then
\begin{equation}
~~~~~~~~~~~~~\lim_{n\rightarrow \infty} \frac{R_{\rho}}{\log n}=
\frac{1}{\kappa(p,\rho)}~~~~~~~~~~~~~~~~~~(pr.),
\end{equation}
where
\begin{equation}
\kappa(p,\rho) = \rho \log \frac{\rho}{p} + (1-\rho) \log
\frac{1-\rho}{1-p}.
\end{equation}
More precisely,
\begin{equation}
P(R_{\rho} \geq r_0) \leq  O\left(\frac{\log
n}{n^{1/\kappa(p,\rho)}}\right),
\end{equation}
where
\begin{equation}
r_0 = \frac{\log n -\log\log n + \log \kappa(p,\rho)}
{\kappa(p,\rho)} \label{eq:r0}
\end{equation}
for large $n$.
\end{itemize}

\stitle{Piecewise $G(n,p)$ model}

\begin{itemize}
\item The size of largest dense subgraph is still proportional to
$\log n/ \kappa$ with a constant factor depending on \blue{number of hubs}
\item
{\blue{Model:}} \\
\begin{displaymath}
P(uv \in E(G)) = \left\{
\begin{array}{ll}
p_h & \text{if}~u,v\in V_h\\
p_l & \text{if}~u,v\in V_l\\
p_b & \text{if}~u\in V_h, v\in V_l~\text{or}~u\in V_l, v\in V_h
\end{array}
\right.
\end{displaymath}
\item
\green{Result:}\\
Let $n_h = |V_h|$. If $n_h=O(1)$, then
$
P(R_n(\rho) \geq r_1) \leq  O\left(\frac{\log n}{n^{1/\kappa(p_l,\rho)}}\right),
$
where
\begin{displaymath}
r_1 = \frac{\log n - \log\log n + 2n_h\log B + \log \kappa(p_l,\rho) - \log e + 1}
{\kappa(p_l,\rho)}
\end{displaymath}
and
$B=\frac{p_bq_l}{p_l}+q_b$,  where $q_b=1-p_b$ and $q_l=1-p_l$.
\end{itemize}

\stitle{Algorithms Based on Statistical Significance}
\begin{itemize}
\item Identification of \green{topological modules}
\item Use \blue{statistical significance} as a \green{stopping
criterion} for graph clustering heuristics

\bigitem{HCS Algorithm~\mcite{Hartuv \& Shamir}{Inf. Proc.
Let.}{2000}} {
\item Find a minimum-cut bipartitioning of the network
\item If any of the parts is \blue{dense enough}, record it as a
dense cluster of proteins
\item Else, further partition them recursively
}

\bigitem{\blue{{\sc SiDeS}:} Use \green{statistical significance} to determine whether
a subgraph is sufficiently dense}{
\item For given number of proteins and interactions between them,
we can determine whether those proteins induce a significantly
dense subnet}
\end{itemize}

\stitle{{\sc SiDeS} Algorithm}

\begin{psfrags}
\psfrag{p}[c][c]{\red{$p << 1$}}
\centerline{\epsfig{file=sides.eps,width=0.8\textwidth}}
\end{psfrags}

\blue{{\sc SiDeS} is available at \url{http://www.cs.purdue.edu/pdsl}}

\stitle{Performance of {\sc SiDeS}}
\begin{itemize}
\bigitem{Biological relevance of identified clusters is
assessed with respect to \blue{Gene Ontology (GO)}}
{\item Estimate the
statistical significance of the \green{enrichment} of each GO term
in the cluster
}
\bigitem{\green{Quality} of the clusters with respect to GO
annotations}
{
\item
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$
\item
\blue{specificity} = $100 \times n_{CT}/{n_C}$
\item
\blue{sensitivity} = $100 \times n_{CT}/{n_T}$
}

\begin{small}
\begin{center}
\begin{tabular}{lccccccc}
\hline
 & \multicolumn{3}{c}{\blue{{\sc SiDeS}}} & & \multicolumn{3}{c}{\red{MCODE}} \\
\cline{2-4}
\cline{6-8}
 & Min. & Max. & Avg. & & Min. & Max. & Avg. \\
\hline
\green{Specificity (\%)} & 43.0 &  100.0 & 91.2 & & 0.0 & 100.0 & 77.8 \\
\green{Sensitivity (\%)} & 2.0 &  100.0 & 55.8 & & 0.0 & 100.0 & 47.6 \\
\hline
\end{tabular}
\end{center}
\end{small}
\centerline{Comparison of {\sc SideS} with MCODE~\mcite{Bader \& Hogue}{BMC Bioinformatics}{2003}}
\end{itemize}

\stitle{Performance of {\sc SiDeS}}

\vspace{0.75in}
\begin{psfrags}
\begin{small}
%psfrag{-log(Significance)}[b][b]{$-\log$($p$-value)}
\psfrag{Cluster size}[t][t]{Cluster size}
\psfrag{SiDeS}[bc][bc]{\blue{{\tiny{\sc SiDeS}}}}
\psfrag{MCODE}[tc][tc]{\red{{\tiny{\sc mcode}}}}
\psfrag{Sensitivity (\%)}[t][t]{Sensitivity (\%)}
%psfrag{Specifity(\%)}[b][b]{Specificity (\%)}
\psfrag{0}[c][c]{{\tiny 0}}
\psfrag{10}[c][c]{{\tiny 10}}
\psfrag{20}[c][c]{{\tiny 20}}
\psfrag{30}[c][c]{{\tiny 30}}
\psfrag{40}[c][c]{{\tiny 40}}
\psfrag{50}[c][c]{{\tiny 50}}
\psfrag{60}[c][c]{{\tiny 60}}
\psfrag{70}[c][c]{{\tiny 70}}
\psfrag{80}[c][c]{{\tiny 80}}
\psfrag{90}[c][c]{{\tiny 90}}
\psfrag{100}[c][c]{{\tiny 100}}
\centerline{
  \epsfig{file=size_vs_sig.eps, width=0.49\textwidth}
  \hspace{0.1in}
  \epsfig{file=spec_vs_sens.eps, width=0.49\textwidth}
}
\end{small}
\end{psfrags}

\vspace{0.5in}
\centerline{\hspace{0.03\textwidth}\blue{Size} vs \green{Significance}
\hspace{0.2\textwidth}\blue{Sensitivity} vs \green{Specifity}}

\vspace{0.5in}
\centerline{\green{Correlation} \hspace{0.5\textwidth}}

\vspace{0.1in}
\centerline{\blue{{\sc SiDeS:}} 0.76 \hspace{0.5\textwidth}}
\centerline{\red{MCODE:} 0.43 \hspace{0.5\textwidth}}



\stitle{Performance of {\sc SiDeS}}

\vspace{0.75in}
\begin{psfrags}
\begin{small}
\psfrag{Cluster size}[t][t]{Cluster size}
\psfrag{SiDeS}[bc][bc]{\blue{{\tiny{\sc SiDeS}}}}
\psfrag{MCODE}[tc][tc]{\red{{\tiny{\sc mcode}}}}
%psfrag{Sensitivity (\%)}[b][b]{Sensitivity (\%)}
%psfrag{Specifity (\%)}[b][b]{Specificity (\%)}
\psfrag{0}[c][c]{{\tiny 0}}
\psfrag{10}[c][c]{{\tiny 10}}
\psfrag{20}[c][c]{{\tiny 20}}
\psfrag{30}[c][c]{{\tiny 30}}
\psfrag{40}[c][c]{{\tiny 40}}
\psfrag{50}[c][c]{{\tiny 50}}
\psfrag{60}[c][c]{{\tiny 60}}
\psfrag{70}[c][c]{{\tiny 70}}
\psfrag{80}[c][c]{{\tiny 80}}
\psfrag{90}[c][c]{{\tiny 90}}
\psfrag{100}[c][c]{{\tiny 100}}
\centerline{
  \epsfig{file=size_vs_spec.eps, width=0.49\textwidth}
  \hspace{0.1in}
  \epsfig{file=size_vs_sens.eps, width=0.49\textwidth}
}
\end{small}
\end{psfrags}

\vspace{0.5in}
\centerline{\blue{Size} vs \green{Specificity}
\hspace{0.3\textwidth}\blue{Size} vs \green{Sensitivity}}

\vspace{0.5in}
\centerline{\green{Correlation} }

\vspace{0.1in}
\centerline{\blue{{\sc SiDeS:}} 0.22 \hspace{0.3\textwidth} \blue{{\sc SiDeS:}} 0.27}
\centerline{\red{MCODE:} -0.02 \hspace{0.3\textwidth} \red{MCODE:} 0.36}


\stitle{Statistical Significance as an Optimization Criteria}

\begin{itemize}
\item
Most algorithms satisfy queries and quantify the significance of the
answer.
\item
Can we pose this as an optimization problem on the signficance -- give me
the most significant result for the query?
\item
We address this problem in the simple context of finding significant pathways.
\end{itemize}

\stitle{Finding Statistically Significant Functional Pathways}

\begin{itemize}
\item
	Stack functional annotation of a molecule (gene) from an ontology on
	to the network.
\item
	Generate a null-hypothesis for node functional annotation.
\item
	Find all pathways with p-values lower than a threshold.
\end{itemize}


\stitle{Finding Statistically Significant Functional Pathways}

\begin{itemize}
\item
	Statistical significance is not monotonic in pathway space
	(cannot build longer pathways from known significant pathways)
\item
	Statistical significance is not monotonic in ontology space
	(cannot build pathways at coarse levels in ontology and refine)
\item
	The above statements are true for a broad class of measures of
	statistical significance we refer to as statistically interpretable.
\end{itemize}


\stitle{Finding Statistically Significant Functional Pathways}


\centerline{\includegraphics[width=90mm]{Figure1.eps}}

\noindent
From interactions between functional attributes to
pathways of functional attributes: (a) statistically significant
regulatory interactions between {\em DNA-dependent regulation of
transcription}, {\em positive regulation of transcription}, and {\em
cillary and flagellar motility},
(b) the two regulatory interactions are connected in the gene network as well,
(c) these separate interactions may be combined into
a pathway of functional attributes.


\stitle{Finding Statistically Significant Functional Pathways}

\centerline{\includegraphics[width=90mm]{Figure2.eps}}

\noindent
Pairwise assessment of interactions between functional attributes
does not necessarily imply indirect paths: (a) regulation of
{\em protein modification} by {\em sensory perception} is significantly
overrepresented, as well as the regulation of {\em biotin biosynthetic process}
by {\em protein modification}; (b) the two frequent interactions never
go through the same gene.


\stitle{Finding Statistically Significant Regulatory Pathways}

\noindent
Greedy Enumeration to the Rescue!

\centerline{\includegraphics[width=0.9\textwidth]{Screenshot.eps}}


\stitle{Finding Statistically Significant Regulatory Pathways}

\centerline{\includegraphics[width=0.9\textwidth]{sigMap.eps}}

\noindent
A global view of {\em E. coli} transcriptional network mapped to
cellular processes described by GO.


\stitle{Finding Statistically Significant Regulatory Pathways}

\centerline{\includegraphics[width=0.9\textwidth]{shortMap.eps}}

\noindent
A global view of {\em E. coli} transcriptional network obtained after
short-circuting common mediator processes related to transcription and
translation.


\stitle{Finding Statistically Significant Regulatory Pathways}

\noindent
{\footnotesize
\begin{tabular}{lll}
        \hline
        Frequency & $p$-value & Pathway\\
        \hline
        276 & 5E-94 & metabolic process $\dashv$ flagellum biogenesis $\rightarrow$ transport\\
        136 & 3.1E-71 & regulation of translation $\dashv$ DNA recombination $\rightarrow$ transport\\
        38 & 4.9E-47 & response to stimulus $\dashv$ transcription $\rightarrow$ cell motility\\
        36 & 6.6E-35 & flagellum biogenesis $\rightarrow$ ciliary or flagellar motility\\
        56 & 1.4E-24 & regulation of translation $\dashv$ transcription $\rightarrow$ carboxylic acid metabolism\\
        178 & 8.3E-21 & signal transduction $\dashv$ transcription $\rightarrow$ transport \\
        14 & 8.6E-20 & phosphate transport $\rightarrow$ transcription $\rightarrow$ phosphonate transport\\
        16 & 2E-16 & SOS response $\dashv$ regulation of transcription $\dashv$ DNA repair\\
        501 & 1.2E-13 & regulation of transcription, DNA-dependent $\rightarrow$ transport\\
        12 & 3.6E-10 & proteolysis $\dashv$ regulation of transcription $\dashv$ response to external stimulus \\
        15 & 3.8E-7 & nitrate assimilation $\dashv$ cytochrome complex assembly\\
        10 & 1.4E-6 & cell morphogenesis $\dashv$ protein secretion\\
        178 & 3.8E-4 & transcription $\rightarrow$ carbohydrate metabolic process\\
\hline
\end{tabular}
}

\noindent
Narada available at:  \\ \\
\url{http://www.cs.purdue.edu/homes/jpandey/narada/}


\stitle{Outstanding Challenges}

\begin{itemize}
\item
Models, measures, algorithms and analysis!
\item
Data and data quality.
\item
Discriminative analysis.
\end{itemize}


\end{document}
