\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}}\vspace{-0.5in}}
\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.}}

\begin{document}

\title{
\red{Algorithms and Analyses of Molecular Interaction Networks}
}

\author{
\blue{Ananth Grama} \\
\blue{Center for Science of Information, Purdue University} \\ \\
With significant contributions from \\
Mehmet Koyuturk, Jayesh Pandey, Young Kim, \\
Shahin Mohammadi, and Shankar Subramaniam \\ \\ \\
Thanks to the Indian Institute of Science and \\
the US National Science Foundation.
}

\date{}

\maketitle

\thispagestyle{empty}


\stitle{Function \& Topology in Molecular Networks}

How does function relate to network topology? \\
\centerline{\includegraphics[width=0.8\textwidth]{images/functionaltopology.eps}}

\stitle {Prior Work on Topology and Function}

\begin{itemize}
\item
Conservation [ISMB 04/Bioinf. 04]
\item
Alignment [RECOMB 05/JCB 06]
\item
Modularity [RECOMB 06/JCB 07]
\item
Inference [Bioinf. 06]
\item
Pathway Annotation [ISMB 07/Bioinf. 07, PSB 08]
\item
Network Abstractions/ Annotations [ECCB 08/ Bioinf. 08]
\item
Modularity and Domain Interactions [APBC 10/ BMC Bioinf. 10]
\item
Pathway Interaction Maps [PSB 12]
\item
Pathway Inference [ISMB 12]
\end{itemize}






%Slide
\stitle{Evolution of Molecular Interactions}

\begin{itemize}

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

\bigitem{Cooperative tasks require all participating units}
 {\item \green{Selective pressure} on preserving \blue{interactions} \& \blue{interacting proteins}}

\bigitem{\blue{Proteins} organized in cohesive patterns are highly \green{conserved}
\mcite{Wuchty et al.}{Nature Gen.}{2003}}
{\item \blue{Functional modules} are likely to be consistently conserved}

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

\item{\blue{Interacting proteins} follow similar \green{evolutionary trajectories}
\mcite{Pellegrini et al.}{PNAS}{1999}}
\end{itemize}

%Slide
\stitle{Computational Analysis of Biological Networks}

\begin{itemize}

\bigitem{\blue{Clustering}}
{\item \green{Interaction network:} Proteins in functional modules densely
       interact with each other
 \item \green{Gene expression:} Genes coding cooperating proteins are likely to be
co-regulated
 \item \green{Phylogenetic profiles:} Interacting proteins are likely to have co-evolved
}

\bigitem{\blue{Graph Mining}}
{
\item Common topological motifs and \red{frequent interaction patterns}
reveal conserved modularity
}

\bigitem{\blue{Graph Alignment}}
{
\item \red{Conservation/divergence} of pathways, complexes, and functional
modules
}

\end{itemize}


\stitle{Frequent Interaction Patterns: Computational Problem}

\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)$.

\bigitem{\red{Maximal frequent 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{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{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}
\bigitem{Discovered frequent sub-networks are still \green{biologically interpretable}!}
{
\item Interaction between proteins becomes interaction between ortholog groups
\item Ortholog-contraction may be thought of as going back in evolutionary history (to what point?)
}

\end{itemize}
%\vspace{0.3in}
%\centerline{
%\epsfig{file=unique1.eps,width=4.5in}
%}

%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{Preservation of Sub-networks}

\blue{Theorem:} Let $\tilde{G}$ be the ortholog-contracted graph obtained
by contracting the orthologous nodes of network $G$. Then, \green{ if $S$
is a subgraph of $G$, $\tilde{S}$ is a subgraph of $\tilde{G}$}.

\blue{Corollary:} The ortholog-contracted representation of any frequent
sub-network is also frequent in the set of ortholog-contracted graphs.

\vspace{1in}
\centerline{\begin{psfrags}
\psfrag{G}[c][c]{$G$}
\psfrag{G2}[c][c]{$\tilde{G}$}
\epsfig{file=preserve.eps,height=2.5in}
\end{psfrags}}

%Slide
\stitle{Results: Mining 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/homes/koyuturk/mule/}}
\end{itemize}

\stitle{Frequent 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=ribo.eps, width=4.5in}
\end{psfrags}
}
\vspace{0.5in}
\centerline{\blue{Small nuclear ribonucleoprotein complex} (\green{$p < 2e-43$})}

\stitle{Frequent 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{Frequent 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$})}


\stitle{Modular Phylogenetics}

\begin{itemize}
\item Top eight groups of three organisms
that contain most frequent connected sub-networks and interactions
\end{itemize}

\begin{center}
\small{
\begin{tabular}{lcc}
\hline
 & \green{\# frequent} & \blue{\# frequent} \\
\red{Organism set} & \green{sub-networks} &  \blue{interactions} \\
\hline
{\sl C. elegans}, {\sl D. melanogaster}, {\sl H. sapiens} & 8 & 134\\
{\sl S. cerevisiae}, {\sl D. melanogaster}, {\sl H. sapiens} & 20 & 126\\
{\sl D. melanogaster}, {\sl H. sapiens}, {\sl M. musculus} & 17 & 86\\
{\sl S. cerevisiae}, {\sl C. elegans}, {\sl D. melanogaster} & 15 & 77\\
{\sl S. cerevisiae}, {\sl C. elegans}, {\sl H. sapiens} & 6 & 50\\
{\sl S. cerevisiae}, {\sl H. sapiens}, {\sl M. musculus} & 10 & 26\\
{\sl C. elegans}, {\sl H. sapiens}, {\sl M. musculus} & 5 & 23\\
{\sl H. sapiens}, {\sl M. musculus}, {\sl R. norvegicus} & 10 & 23\\
\hline
\end{tabular}
}
\end{center}

%Slide
\stitle{Runtime Characteristics}

\begin{center}
\blue{Comparison with isomorphism-based algorithms}\\
\green{FSG}~\mcite{Kuramochi \& Karypis}{ICDM}{2001}, \green{gSpan}~\mcite{Yan \& Han}{KDD}{2003}
%\begin{small}
\begin{scriptsize}
\begin{tabular}{lccccccccc}
\hline
        &             & \hspace{0.3cm} & \multicolumn{3}{c}{FSG} & \hspace{0.3cm} & \multicolumn{3}{c}{{\sc Mule}}\\
        & Minimum    &  & Runtime & Largest & Number of & & Runtime & Largest & Number of \\
Dataset & Support (\%)& & (secs.) & pattern & patterns  & & (secs.) & pattern & patterns \\
\hline
 & 20 & & 0.2 & 9 & 12 & & 0.01 & 9 & 12\\
 & 16 & & 0.7 & 10 & 14 & & 0.01 & 10 & 14\\
 Glutamate & 12 & & 5.1 & 13 & 39 & & 0.10 & 13 & 39\\
 & 10 & & 22.7 & 16 & 34 & & 0.29 & 15 & 34\\
 & 8 & & 138.9 & 16 & 56 & & 0.99 & 15 & 56\\
\hline
 & 24 & & 0.1 & 8 & 11 & & 0.01 & 8 & 11\\
 & 20 & & 1.5 & 11 & 15 & & 0.02 & 11 & 15\\
 Alanine & 16 & & 4.0 & 12 & 21 & & 0.06 & 12 & 21\\
 & 12 & & 112.7 & 17 & 25 & & 1.06 & 16 & 25 \\
 & 10 & & 215.1 & 17 & 34 & & 1.72 & 16 & 34\\
\hline
\end{tabular}
%\end{small}
\end{scriptsize}
\end{center}

\center{
\blue{Extraction of contracted patterns}
\begin{scriptsize}
\begin{tabular}{cccccccccc}
\hline
\multicolumn{4}{c}{{Glutamate metabolism, $\sigma=8\%$}} &\hspace{0.7cm} &\multicolumn{4}{c}{{Alanine metabolism, $\sigma=10\%$}}\\
Size of & \multicolumn{2}{c}{Extraction time} & Size of & & Size of & \multicolumn{2}{c}{Extraction time} & Size of \\
contracted &  \multicolumn{2}{c}{(secs.)} & extracted  & & contracted &  \multicolumn{2}{c}{(secs.)}  & extracted\\
pattern    & FSG & gSpan & pattern & & pattern & FSG & gSpan & pattern\\
\hline
15 & 10.8 & 1.12 & 16 & & 16 & 54.1 & 10.13 & 17 \\
14 & 12.8 & 2.42 & 16 & & 16 & 24.1 & 3.92  & 16 \\
13 & 1.7  & 0.31 & 13 & & 12 & 0.9  & 0.27  & 12 \\
12 & 0.9  & 0.30 & 12 & & 11 & 0.4  & 0.13  & 11 \\
11 & 0.5  & 0.08 & 11 &  & 8 & 0.1  & 0.01  & 8  \\
\hline
\multicolumn{4}{l}{Total number of patterns: 56} & & \multicolumn{4}{l}{Total number of patterns: 34}\\
\multicolumn{4}{l}{Total runtime of FSG alone: 138.9 secs.} & & \multicolumn{4}{l}{Total runtime of FSG alone :215.1 secs.}\\
\multicolumn{4}{l}{Total runtime of {\sc Mule}+FSG: 0.99+100.5 secs.} & & \multicolumn{4}{l}{Total runtime of {\sc Mule}+FSG: 1.72+160.6 secs.}\\
\multicolumn{4}{l}{Total runtime of {\sc Mule}+gSpan: 0.99+16.8 secs.} & & \multicolumn{4}{l}{Total runtime of {\sc Mule}+gSpan: 1.72+31.0 secs.}\\
\hline
\end{tabular}
\end{scriptsize}}


%Slide
\stitle{Pairwise 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 meaning}
 \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~\mcite{Koyut\"urk, Kim, Topkara, Subramaniam, Szpankowski, \& Grama}{J. Comp. Biol.}{2006}}
{\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{Evolution of PPI  Networks}

\begin{itemize}
\bigitem{\blue{Duplication}/\green{divergence} models for the evolution
of protein interaction networks}
{\item \blue{Interactions of duplicated proteins are also duplicated}
 \item \green{Duplicated proteins rapidly lose interactions through mutations}
}
\item Allows defining and scoring evolutionary events as graph-theoretical concepts
\end{itemize}

\vspace{0.6in}
\centerline{
\begin{psfrags}
\psfrag{u1}[c][c]{$u_1$}
\psfrag{u1p}[c][c]{$u_1'$}
\psfrag{u2}[c][c]{$u_2$}
\psfrag{u3}[c][c]{$u_3$}
\psfrag{Duplication}[c][c]{\blue{Duplication}}
\psfrag{Deletion}[c][c]{\red{Elimination}}
\psfrag{Insertion}[c][c]{\green{Emergence}}
\leavevmode
\epsfig{file=evolution.eps,width=8in}
\end{psfrags}}

%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{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{conservatio}n 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
}

\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 partitioning}
{
\item Greedy graph growing + iterative refinement
\item Linear-time heuristic
}

\item{Source code available at \\
\blue{\url{http://www.cs.purdue.edu/homes/koyuturk/mawish/}}}
\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}

%Slide

\stitle{Statistical Significance of Modularity}

\begin{itemize}
\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}
}

\bigitem{Random graph models} {
\item PPI networks generally exhibit \blue{power-law} property (or
exponential, geometric, etc.)
\item Analysis simplified through \green{independence} assumption
\item Independence assumption may cause problems for networks with
\red{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
 }

 \item Analytical techniques based on simplified
 models~\mcite{Koyut\"urk, Grama, \& Szpankowski}{RECOMB}{2006}
\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 }
\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{Generalizing Results to Complex Models}
\begin{itemize}
\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 The size of largest dense subgraph is still proportional to
$\log n$ }

\bigitem{More general models} {
\item Increasing the number of pieces, we approach models with
characteristic degree distributions
\item Analysis of power-law graphs in progress}

\bigitem{Multiple networks: \blue{Conservation}}
{\item Superpose
graphs based on sequence homology}

\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{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{Largest Dense Subgraph for Varying Density}

\vspace{1in}
\begin{psfrags}
\begin{scriptsize}
\psfrag{Density threshold}[t][t]{Density threshold} \psfrag{Size
of largest dense subgraph}[b][b]{Size of largest dense subgraph}
\psfrag{Size of largest conserved dense subgraph}[b][b]{Size of
largest conserved dense subgraph}
\centerline{
    \epsfig{file=scere.eps,width=4.5in}
    \hspace{0.5in}
    \epsfig{file=schs.eps,width=4.5in}
}
\end{scriptsize}
\end{psfrags}

\vspace{0.5in} \centerline{\hspace{0.8in}{\sl Yeast} PPI network
\hspace{1.6in} {\sl Yeast} \& {\sl Fruit Fly} PPI networks}



\stitle{Pathway Organization: Genetic Interactome}

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

\begin{definition}
\begin{itemize}
\item {\color{red} \textbf{Negative Interactions}}: more severe phenotype than expected
\begin{itemize}
\item Also known as \textit{aggravating} or \textit{synergistic}
\end{itemize}

\item {\color{green} \textbf{Positive Interactions}}: Less severe phenotype than expected
\begin{itemize}
\item Also known as \textit{alleviating} or \textit{epistatic}
\end{itemize}
\end{itemize}
\end{definition}

Most commonly used:
\begin{description}
\item [Phenotype]: Growth rate
\item[Model]: Multiplicative null model
\end{description}



\stitle{Organization of Genetic Interactions}

\begin{definition}
\begin{itemize}
\item {Between-Pathway Model}
\begin{itemize}
\item Among genes participating in redundant functions
\end{itemize}
\item {Within-Pathway Model}
\begin{itemize}
\item Among genes with additive effect
\end{itemize}
\item {Indirect Effect}
\begin{itemize}
\item Among genes with distant functions that are not directly related
\end{itemize}
\end{itemize}
\end{definition}



\stitle{Between-Pathway Model (BPM)}

  \begin{columns}[c]
    \column{.4\textwidth}
	\includegraphics[scale=.25]{figures/BPM}	
	  
    \column{.6\textwidth}
		\begin{itemize}
		\item Bi-cliquish structure
		\item Have been used to:		
		\begin{enumerate}
			\item Predict co-pathway membership of gene pairs
			\item Extract redundant pathways
		\end{enumerate}
	\end{itemize}
  \end{columns}  




\stitle{The Genetic Landscape of a Cell}
  \begin{columns}[c]
    \column{.5\textwidth}
	\includegraphics[width=\columnwidth,height=.8\textheight]{figures/Costanzo}\\
	\tiny{Adopted from Costanzo et al., 2010}
	  
    \column{.5\textwidth}
		\begin{itemize}
		\item Baker's yeast, \textit{Saccharomyces cerevisiae}
		\item Synthetic Genetic Array (SGA)
		\item 1712 query genes
			\begin{enumerate}
				\item 1378 null alleles of non-essential genes
				\item 334 hypomorphic or conditional alleles of essential genes
			\end{enumerate}
		\item 3885 array strains
	\end{itemize}
  \end{columns}  



\stitle{Functional Annotations}
  \begin{columns}[c]
    \column{.5\textwidth}
	\includegraphics[width=\columnwidth]{figures/KEGG}
		  
    \column{.5\textwidth}
		\begin{itemize}
			\item KEGG Pathway Database
			\item Annotations for 1026 genes in the experiment
			\item 96 Pathways
			\begin{itemize}
				\item 80 pathways after filtering pathways with less than 10 genes.			
			\end{itemize}
		\end{itemize}
  \end{columns}  



\stitle{Local Neighborhood Similarity}{A Predictor of Co-Pathway Membership}
\begin{block}{Similarity prediction methods}
\begin{enumerate}
\item Number of Shared Neighbors
\item Congruence Score
\item Pearson Correlation of Interaction Profiles
\end{enumerate}
\end{block}


  \begin{columns}[t]
    \column{.45\textwidth}
	\includegraphics[width=\columnwidth]{figures/CS1}
	  
    \column{.35\textwidth}
	\includegraphics[width=\columnwidth]{figures/CS2}
  \end{columns}  
  

\tiny{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).}





\stitle{Evaluating Ranking Methods}
Given a pathway {$P_A$} and a cut size (target set) {$l$}.

	\begin{definition}
		\begin{eqnarray*}
			P-value (X = k) &=& Prob(k\leq X) \nonumber \\
			&=&  HGT(k| N, N_A, l) \nonumber  \\
			&=& \sum_{x=k}^{min(N_A, l)} \frac{{C(l, x)} {C(N-l,N_A-x)}} {{C(N,N_A)}}
		\end{eqnarray*}
	\end{definition}

	{$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


\stitle {Minimum HyperGeometric (mHG) Score}
Target size unknown:

\begin{definition}{	The {Minimum HyperGeometric (mHG)} score}
\begin{equation*}
mHG(\lambda) = min_{1\leq l \leq N} HGT(b_l(\lambda); N, N_A, l),
\end{equation*}

where $b_l(\lambda) = \sum_{i=1}^l \lambda_i $

\end{definition}

 $\lambda_i$ is 1 if both of the genes in the $i^{th}$ ranked gene pair
are members of $P_A$, and 0 otherwise.

\begin{itemize}
\item mHG Adjusted for Multiple Comparison
\end{itemize}


\stitle{Predictions Are Not Equally Accurate in Different KEGG Pathways}
\includegraphics[width=.95\columnwidth] {figures/Complete_mHG_Bonferroni_01}




\stitle{Highlights}

\begin{block}{Basic Idea}
  \begin{columns}[c]
    \column{.4\textwidth}
	Heterogeneous performance of co-pathway membership predictions		

    \column{.05\textwidth}
	$\Longleftrightarrow$
			  
    \column{.4\textwidth}
	Existence of specific structure around enriched pathways

  \end{columns}  
\end{block}

\begin{itemize}
\item Decomposing neighborhood of each pathway
\item Inferring lethal crosstalk among pathways
\end{itemize}


\stitle{Modified Congruence Score (MCS)} {Evaluating Neighborhood Overlap of
Gene Pairs With Respect to a Given Pathway}

\begin{definition}
\begin{eqnarray*}
P-value (X = k_{ij}^B) &=& Prob(k_{ij}^B\leq X)  \\
&=&  HGT(k_{ij}^B| n_B, d_i^B, d_j^B) \\
&=& \sum_{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)}
\end{eqnarray*}
\end{definition}
MCS is defined as $-log_{10}$ of the P-value.


\stitle{Modified Congruence Score (MCS)} {continued}
\begin{example}
  \begin{columns}[c]
    \column{.45\textwidth}
	\includegraphics[width=\columnwidth,height=.5\textheight]{figures/MCS}
	  
    \column{.45\textwidth}
	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$.
  \end{columns}  
\end{example}



\stitle{Constructing Neighborhood Overlap Graph \\ For a Given Pathway Pair}
\begin{definition}
The neighborhood overlap graph (NOG) of a given pathway $P_A$ with respect to
pathway $P_B$, denoted by $H_{A\rightarrow 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 .
\end{definition}

\stitle{Pruning neighborhood overlap graph, finding cohesive subgraphs,
and identifying interaction ports}


  \begin{columns}[c]
    \column{.5\textwidth}
	\includegraphics[width=\columnwidth]{figures/KCore}\\
	\tiny{	Adopted from Batagelj and Zaversnik, 2002}		  
    \column{.5\textwidth}
    \begin{enumerate}
		\item Iterative peeling of K-shells\\Pruning hairy components
		\item Connected components in each core
		\item Evaluating the significance of components
			\begin{itemize}
				\item Evaluating significance using ER random graph model
			\end{itemize}		
	\end{enumerate}
  \end{columns}  
  
  


\stitle{KEGG Crosstalk Map}
  \begin{columns}[c]
    \column{.6\textwidth}
	\includegraphics[width=\columnwidth, height=.8\textheight]{figures/KEGG_final}
	  
    \column{.4\textwidth}
	\includegraphics[width=\columnwidth]{figures/Thresholding}
  \end{columns}  



\stitle{Interaction Port Case Study} {Crosstalk Between Protein Processing in ER and Proteasome}

 \begin{columns}[t]
    \column{.9\textwidth}
     \includegraphics[width=\textwidth]{figures/ProtER}
	  
  \end{columns}  
  


























\end{document}



\end{document}
