\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{Ananth Grama}
\rightheader{\filedate}                % \filedate is defined above

\begin{document}

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

\author{\\\\
\blue{Ananth Grama}\\
\blue{Coordinated Systems Lab and,}\\
\blue{Computer Science Department,}\\
\blue{Purdue University}\\\\
\blue{{\tt http://www.cs.purdue.edu/people/ayg}} \\
}

\date{}
\maketitle

\noindent
{\small{Various parts of this work involve collaborations with 
Yohan Kim and Shankar Subramaniam (UCSD),
Wijtek Szpankowski (Purdue),
Mehmet Koyuturk (Case Western)}}

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

\thispagestyle{empty}

%Slide
\stitle{Outline}

\begin{itemize}
\bigitem{Molecular Interaction Networks}
{\item Modeling, evolution, problems, practical implications}

\bigitem{Algorithms for Analyzing Molecular Interaction Networks}
{
\item {\em Analyzing} biological networks for \em{conserved molecular interaction patterns}
\item Pairwise {\em Alignment} of protein-protein interaction networks
\item {\em Probabilistic} models/analyses for assessing \em{statistical significance}
}
\bigitem{Computational Synthesis of Interaction Networks}
{
\item Inferring function from domain co-evolution
}

\item Ongoing Work 

\end{itemize}


%Slide
\stitle{Protein-Protein Interaction (PPI) Networks}

\begin{itemize}
\bigitem{Interacting proteins can be identified via \green{high-throughput}
screening}
{\item Two-hybrid
 \item Mass spectrometry
 \item Tandem affinity purification (TAP)
}
\end{itemize}

\vspace{-0.15in}
\centerline{
\begin{psfrags}
\psfrag{P}[c][c]{\blue{Protein}}
\psfrag{I}[c][c]{\red{Interaction}}
\epsfig{file=pin.eps, height=2.3in}
\leavevmode
\end{psfrags}
\hspace{1.7in}
\epsfig{file=pinsample.eps, height=2.8in}
%\hspace{0.3in}
}
\vspace{0.3in}
\centerline{\blue{Undirected Graph Model}\hspace{1.1in} \blue{{\sl S. Cerevisiae} PPI network}\hspace{0.3in}}
\centerline{\hspace{4.3in}\mcite{Jeong et al.}{Nature}{2001}}

%Slide
\stitle{Gene Regulatory Networks}

\begin{itemize}
\bigitem{Expression of genes is dynamically orchestrated through genes
controlling each other's transcription}
{%\item A simple model: Boolean networks
 \item Computationally induced from gene expression data and/or sequence level
       analysis
}
\end{itemize}
\vspace{0.5in}
\centerline{
\begin{psfrags}
\psfrag{G}[c][c]{\blue{Gene}}
\psfrag{D}[c][c]{\red{Down-regulation}}
\psfrag{U}[c][ct]{\green{Up-regulation}}
\epsfig{file=grn.eps, height=2.8in}
\leavevmode
\end{psfrags}
\hspace{1.7in}
\epsfig{file=grnsample.eps, height=3.1in}
}
\vspace{0.3in}

\centerline{\blue{Boolean Network} \hspace{1.6in} \blue{Genetic network that controls}}
\centerline{\hspace{0.7in}\blue{Model} \hspace{2.5in} \blue{flowering time in {\sl A. Thaliania}}}
\centerline{\hspace{4in}\mcite{Blazquez et al}{EMBO Reports}{2001}}

%Slide
\stitle{Metabolic Pathways}
\begin{itemize}
\bigitem{Chains of reactions that perform a particular metabolic function}
{\item Reactions are linked to each other through substrate-product relationships
 \item Experimentally derived \& computationally extended
}
\end{itemize}

\vspace{0.2in}
\centerline{
\begin{psfrags}
\psfrag{E}[l][r]{\blue{Enzyme}}
\psfrag{S}[l][r]{\red{Substrate}}
\psfrag{P}[l][r]{\red{Product}}
\psfrag{C}[l][r]{\green{Compound}}
\epsfig{file=pat.eps, height=2.8in}
\leavevmode
\end{psfrags}
\hspace{2.5in}
\epsfig{file=patsample.eps, height=3in}
\hspace{0.3in}
}

\vspace{0.3in}
\centerline{\blue{Directed Hypergraph Model}\hspace{0.5in}\blue{Glycolysis pathway in {\sl S. Cerevisiae}}}
\centerline{\hspace{4.5in}\mcite{Hynne et al.}{Biophys. Chem.}{2001}}

%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}
\item{\blue{Interacting proteins} follow similar \green{evolutionary trajectories}
\mcite{Pellegrini et al.}{PNAS}{1999}}
}

\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 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 \green{common} to an \blue{interesting} subset of these
         networks~\mcite{Koyut\"urk, Grama, \& Szpankowski}{ISMB}{2004}}
{
\item A sub-network is a group of interactions that are tied to each
      other (\blue{connected})
\item \green{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 (proteins) in different 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{Graph Analysis}

\vspace{1in}
\centerline{
\epsfig{file=graph1.eps,width=2.2in}
\hspace{0.5in}
\epsfig{file=graph2.eps,width=2.2in}
\hspace{0.5in}
\epsfig{file=graph3.eps,width=2.2in}
}
\vspace{0.5in}
\centerline{Network database}
\vspace{1in}
\centerline{
\epsfig{file=subgraph1.eps,width=4in}
\hspace{0.5in}
\epsfig{file=subgraph2.eps,width=4in}
}
\vspace{0.5in}
\centerline{Interaction patterns that are common to all networks}

\stitle{Relating Proteins in Different Species}{
\begin{itemize}
\bigitem{Ortholog Databases}
{
\item \green{PPI networks:} COG, Homologene, Pfam, ADDA
\item \green{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{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{Simplifying the Graph Analysis Problem}

\begin{itemize}
\bigitem{\blue{Observation:} An ortholog-contracted graph is uniquely determined by the set of its edges.}
{\item Conserved \red{Sub-network} Discovery Problem $\rightarrow$ Frequent \green{Edge set} Discovery Problem
}
\end{itemize}

\vspace{0.3in}
\centerline{
\begin{psfrags}
\small
\psfrag{a}[c][c]{$a$}
\psfrag{b}[c][c]{$b$}
\psfrag{c}[c][c]{$c$}
\psfrag{d}[c][c]{$d$}
\psfrag{e}[c][c]{$e$}
\psfrag{G1}[c][c]{\green{$G_1$}}
\psfrag{G2}[c][c]{\green{$G_2$}}
\psfrag{G3}[c][c]{\green{$G_3$}}
\psfrag{G4}[c][c]{\green{$G_4$}}
\psfrag{F1}[l][l]{\green{$F_1$}$=\{ab,ac,de\}$}
\psfrag{F2}[l][l]{\green{$F_2$}$=\{ab,ac,bc,de,ea\}$}
\psfrag{F3}[l][l]{\green{$F_3$}$=\{ab,ac,bc,ea\}$}
\psfrag{F4}[l][l]{\green{$F_4$}$=\{ab,ce,de,ea\}$}
\leavevmode
\epsfig{file=graphs.eps, height=4in}\hspace{2in}
\end{psfrags}
}


%Slide
\stitle{Extending Frequent Itemset Mining to Graph Analysis}
\begin{itemize}
\bigitem {Given a set of transactions, find sets of items that
are frequent in these transactions}
{
\item Extensively studied in data mining literature
}
\bigitem {Algorithms exploit \blue{downward closure} property}
{\item An edge set is frequent only if all of its subsets are frequent
 \item Generate edge sets (sub-networks) from small to large,
       \green{pruning} supersets of infrequent sets
}
\item No \red{redundancy}
\item No \red{subgraph enumeration}

\end{itemize}

%Slide
\stitle{{\sc Mule}: Analyzing Ortholog-Contracted Networks}

\vspace{0.5in}
\centerline{
\begin{psfrags}
\scriptsize
\psfrag{e0}[c][c]{$E=\emptyset$}
\psfrag{h0}[c][c]{$H=\{1,2,3,4\}$}
\psfrag{v1}[r][r]{$D=\{ab\}$}
\psfrag{e1}[c][c]{$E=\{ab\}$}
\psfrag{c1}[c][c]{$C=\{ac,ea\}$}
\psfrag{h1}[c][c]{$H=\{1,2,3,4\}$}
\psfrag{v2}[l][l]{$D=\{ab,ac\}$}
\psfrag{e2}[c][c]{$E=\{ac\}$}
\psfrag{c2}[c][c]{$C=\{ea\}$}
\psfrag{h2}[c][c]{$H=\{1,2,3\}$}
\psfrag{v3}[l][l]{$D=\{ab,ac,de\}$}
\psfrag{e3}[c][c]{$E=\{de\}$}
\psfrag{c3}[c][c]{$C=\{ea\}$}
\psfrag{h3}[c][c]{$H=\{1,2,4\}$}
\psfrag{v4}[l][l]{$D=\{ab,ac,de,ea\}$}
\psfrag{e4}[c][c]{$E=\{ea\}$}
\psfrag{c4}[c][c]{$C=\emptyset$}
\psfrag{h4}[c][c]{$H=\{2,3,4\}$}
\psfrag{v5}[r][r]{$D=\{ab,ac\}$}
\psfrag{e5}[c][c]{$E=\{ab,ac\}$}
\psfrag{c5}[c][c]{$C=\{ea\}$}
\psfrag{h5}[c][c]{$H=\{1,2,3\}$}
\psfrag{v6}[l][l]{$D=\{ab,ac,ea\}$}
\psfrag{e6}[c][c]{$E=\{ab,ea\}$}
\psfrag{c6}[c][c]{$C=\{de\}$}
\psfrag{h6}[c][c]{$H=\{2,3,4\}$}
\leavevmode
\epsfig{file=estree.eps, width=8in}
\end{psfrags}
}
\vspace{0.5in}
\centerline{Sample run of {\sc Mule} for identifying maximal}
\centerline{sub-networks that are common to at least 3 organisms}

%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{Runtime Characteristics}

\begin{center}
\blue{Comparison with isomorphism-based algorithms}\\
\green{FSG}~\mcite{Kuramochi \& Karypis}{IEEE TKDE}{2004}, \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{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 Frequency-based approach is \red{not} easily extensible to \blue{weighted}
graphs \mcite{Zhou et al.}{ISMB}{2005}

\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 \mcite{Koyut\"urk et al.}{RECOMB}{2005}
\mcite{Koyut\"urk et al.}{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{Scoring Matches, Mismatches and Duplications}

\begin{itemize}
\bigitem{Quantizing 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 Much \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{Functional Annotation of Biochemical Pathways}

\begin{itemize}
\item
Identifying Significant Pathways
\item
Annotations and Metrics
\item
Application to Protein/Domain Interaction Networks
\item
Implementation and Results
\end{itemize}


\stitle{Molecular Annotation}

\begin{itemize}
\item
Functional annotation of genes provides an understanding of the
underlying principles
\begin{itemize}
\item
Molecular function: role of a gene.
\item
Biological process: processes a gene is involved in.
\item
Cellular component: localization of genes product. 
\end{itemize}
\item
Gene Ontology provides a library of molecular annotations
(we refer to each annotation class as a functional attribute).
\end{itemize}


\stitle{From Molecules to Systems}

\begin{itemize}
\item
Networks are species-specific
\item
Annotation is at the molecular level
\item
Map networks from gene space to function space
(can generate a library of annotated modular (sub-) networks)
\end{itemize}

\centerline{\psfig{file=tong.ps,height=3.0in}}
{\small
Network of Gene Ontology terms based on significance of pairwise interactions in yeast synthetic gene array (SGA)
(Tong et al., Science, 2004)}


\stitle{Indirect Regulation}

\centerline{\psfig{file=indirect1.ps,height=4.0in}}


\stitle{Key Results}

\begin{itemize}
\item
Statistically interpretable measures of significance are not monotonic.
\item
There is no monotonicity in the GO space either.
\item
Develop an alternate (weaker) measure of significance that builds on
modularity of sub-components.
\item
Need to short-circuit common terms (transcription factors, DNA binding
genes, etc.)
\item
Comprehensive software infrastructure built on these results.
\end{itemize}


\stitle{Narada Functionality}

\centerline{\psfig{file=screen.ps,height=6.0in}}


\stitle{Narada Network Annotation}

\centerline{\psfig{file=narada_result.ps,width=9.0in}}


\newpage

\centerline{\psfig{file=sl1.ps,width=9.0in}}

\newpage

\centerline{\psfig{file=sl2.ps,width=9.0in}}

\newpage

\centerline{\psfig{file=sl3.ps,width=9.0in}}

\newpage

\centerline{\psfig{file=sl4.ps,width=9.0in}}

\newpage

\centerline{\psfig{file=sl5.ps,width=9.0in}}

\newpage

\centerline{\psfig{file=sl6.ps,width=9.0in}}

\newpage

\centerline{\psfig{file=sl7.ps,width=9.0in}}

\newpage

\centerline{\psfig{file=sl8.ps,width=9.0in}}

\newpage

\centerline{\psfig{file=sl9.ps,width=9.0in}}

\newpage

\centerline{\psfig{file=sl10.ps,width=9.0in}}

\newpage

\centerline{\psfig{file=sl11.ps,width=9.0in}}

\newpage

\centerline{\psfig{file=sl12.ps,width=9.0in}}

\newpage

\centerline{\psfig{file=sl13.ps,width=9.0in}}

\newpage

\centerline{\psfig{file=sl14.ps,width=9.0in}}


\stitle{Ongoing Work}

\begin{itemize}
\item
Domain identification and domain-domain networks.
\item
(Sub)Network phylogenies.
\item
Network inference and stability.
\end{itemize}


\stitle{References}


{\small
\begin{itemize}

\item
J. Pandey, M. Koyuturk, S. Subramaniam, and A. Grama. Functional coherence
in domain interaction networks, Bioinformatics Suppl. on ECCB'08.

\item
M. Koyuturk, W. Szpankowski, and A. Grama,  Assessing significance of
connectivity and conservation in protein interaction networks, Journal of
Computational Biology, 14(6), 747-764, 2007.

\item
M. Koyuturk, Y. Kim, S. Subramaniam, W. Szpankowski,
and A. Grama, ``Detecting conserved interaction patterns in biological
networks",
{\em Journal of Computational Biology}, 13(7), 1299-1322, 2006.

\item
M. Koyuturk, Y. Kim, U. Topkara, S. Subramaniam,
W. Szpankowski, and A. Grama, Pairwise Alignment of
Protein Interaction Networks, {\em Journal of Computational Biology},
13(2), 182-199, 2006.

\item
Y. Kim, M. Koyuturk, U. Topkara, A. Grama, and
S. Subramaniam, Inferring Functional Information from Domain
Co-evolution, {\em Bioinformatics}, 22(1), pp. 40-49, 2006.
\end{itemize}
}

\stitle{References}

{\small
\begin{itemize}
\item
M. Koyut\"{u}rk, A. Grama, and W. Szpankowski,
An Efficient Algorithm for Detecting Frequent Subgraphs in
Biological Networks,
{\em Bioinformatics}, Vol. 20, Suppl. 1, pp i200-i207, 2004.

\item
M. Koyuturk, A. Grama, and W. Szpankowski,             
Assessing Significance of Connectivity and Conservation in Protein
Interaction Networks,
{\em 10th International Conference on Research in
Computational Molecular Biology (RECOMB)}, LNBI 3909, pp. 45-59, 2006.

\item
M. Koyut\"{u}rk, A. Grama and W. Szpankowski,          
Pairwise Local Alignment of Protein Interaction Networks          
Guided by Models of Evolution,
RECOMB 2005.
\end{itemize}
}

Available from \url{http://www.cs.purdue.edu/pdsl}


\stitle{Thank you!}

\stitle{Phylogenetic Analysis for Predicting Interactions}

\begin{itemize}
\bigitem{Functionally related proteins are likely to have co-evolved}
{
\item Construct \blue{phylogenetic profile} for each genome: Vector of E-values
signifying existence of an orthologous protein in each organism
\item Identify \blue{pairwise functional association}s based on mutual
information between phylogenetic profiles~\mcite{Pellegrini et al.}{PNAS}{1999}
\item \green{Mutual information:}\\
$I(X,Y)= H(X)-H(X|Y) = \sum_{x}\sum_{y} p(x,y) \log(p(x,y)/p(x)p(y))$
\item Shown to identify functionally associated protein pairs at
a coarser level than high-throughput methods
}

\bigitem{However, \green{domains}, \red{not proteins}, co-evolve}
{
\item How can we incorporate domain information to enhance performance
of phylogeny-based interaction prediction?
}
\end{itemize}

\stitle{Inferring Function from Domain Co-evolution}

\begin{itemize}
\bigitem{Residue-level phylogenetic analysis
\mcite{Kim, Koyut\"urk, Topkara, Grama, \& Subramaniam}{Bioinformatics}{2006}}
{
\item No a-priori knowledge about domains
\item Construct \blue{residue phylogenetic profiles} from \green{local alignment}
results
\item Construct mutual information matrix
\item High-information contiguous submatrices that are sufficiently large correspond
to putative co-evolved domains
}
\end{itemize}

\centerline{\epsfig{file=miMatrixPts.eps,width=3.5in}\hspace{1in}\epsfig{file=stringAccuCov.eps,width=4in}}
\centerline{\small{\blue{Mutual Information Matrix}}\hspace{1.2in}\small{\blue{Single vs. Domain Profile}}}

\stitle{Conclusion}
\begin{itemize}

\item{A lot to learn from comparative network analysis}
\item {We have \green{fast algorithms}}
\bigitem{We need}
{ {\item
\green{Enhanced} \& more \green{detailed} network models} {\item
\blue{High quality} \& \blue{comprehensive} data} {\item Detailed
\red{statistical models}} }

\end{itemize}


\stitle{Other Work on Pattern Identification}
\begin{itemize}
\bigitem{{\sc Proximus}: Non-orthogonal decomposition of binary matrices
\mcite{Koyut\"urk,  Grama, Ramakrishnan}{IEEE TKDE}{2005}}
{\item Find a compact set of vectors that represent the entire matrix
 \item Recursive decomposition through rank-one approximations
 \item Fast (linear-time) iterative heuristics for computing approximations
 \item Source code available at \\
 \blue{\url{http://www.cs.purdue.edu/homes/pdsl/}}
}
\end{itemize}
\centerline{\green{Patterns of regulation} \hspace{1.8in} \green{Biclustering}\hspace{0.6in}}
\vspace{0.1in}
\centerline{
\epsfig{file=regpattern.eps, width=3.5in}
\hspace{0.5in}
\epsfig{file=bicluster.eps, width=3.5in}
}
\vspace{0.1in}
\centerline{\scriptsize{``Algorithms for bounded-error correlation of}\hspace{0.9in}
\scriptsize{``Biclustering gene-feature matrices for}\hspace{0.1in}}
\vspace{-0.1in}
\centerline{\scriptsize{high dimensional data in microarray experiments''}\hspace{0.7in}
\scriptsize{statistically significant dense patterns''}\hspace{0.4in}}
\vspace{-0.1in}
\centerline{\scriptsize{\red{[Koyut\"urk, Grama, Szpankowski: {\sl CSB'03.}]}}\hspace{1in}
\scriptsize{\red{[Koyut\"urk, Grama, Szpankowski: {\sl CSB'04}.]}}}


\stitle{Identifying "Canonical" Regulatory Pathways}
\begin{itemize}
\bigitem{Can we derive rules in terms of \green{GO terms}, {\sl e.g.}, $P_i \rightarrow P_j \dashv P_k$?}
{
\item \red{Statistical challenge:} Such patterns have to be \blue{significantly} abundant
\item \red{Computational challenge:} When statistical significance is the basis (as opposed to \red{frequency}),
\green{monotonicity} properties ({\sl e.g.}, downward closure) no longer hold!
\item \green{Our approach:} \blue{conditional significance}, \ie, evaluate significance
of a pattern based on the background constructed by its substructures
}
\item \green{Final goal:} Database of (computationally derived) canonical modules and pathways
\end{itemize}

\centerline{\epsfig{file=gonet.eps, height=2.5in}}
\centerline{\small{A network of GO terms \mcite{Tong et al.}{Science}{2004}}}

\stitle{Cell as a State Machine}
\begin{itemize}
\bigitem{\blue{Signaling pathways} can be modeled as a series of \green{transitions} between
\red{states} of protein or peptide molecules, non-protein molecules, (non-)protein complexes,
and modules}
{
\item \green{Signaling Gateway} provides a database of network states for proteins, a mirror
is available to our group via our collaboration with S. Subramaniam
}
\bigitem{Constructing signaling pathways from state information for individual molecules}
{\item \blue{Smallest common supergraph} problem
 \item Identification of \green{specified pathways}
}

\vspace{0.3in}
\centerline{\epsfig{file=cdk8.eps, height=2.5in}}
\centerline{\small{State diagram for Cdk8 protein (\red{from Molecule Pages})}}

%Slide
\stitle{Modular Phylogenetics}

\vspace{0.5in}
\centerline{\epsfig{file=repl.eps,width=3in}\hspace{0.5in}\epsfig{file=replprf.eps,width=5in}}

\vspace{0.5in}
\centerline{\blue{Replication Factor C} complex identified on yeast PPI network by}
\centerline{\green{MCODE} \mcite{Bader \& Hogue}{BMC Bioinformatics}{2003} algorithm}
\centerline{and the \green{phylogenetic} \green{profiles} of its proteins on}
\centerline{25 eukaryotic genomes}

\vspace{1in}
\centerline{\red{Conserved in all eukaryotic species}!}
\end{itemize}

%Slide
\stitle{Modular Phylogenetics}

\vspace{0.5in}
\centerline{\epsfig{file=ribo.eps,width=3in}\hspace{0.5in}\epsfig{file=riboprf.eps,width=5in}}

\vspace{0.25in}
\centerline{A component of \blue{mitochondrial ribosome} identified on}
\centerline{yeast PPI network by \green{MCODE} algorithm and the}
\centerline{ \green{phylogenetic profiles} of its proteins on 25 eukaryotic genomes}

\vspace{0.5in}
\centerline{\red{Conserved in only yeast species}!}
\begin{itemize}
\item Models and algorithms for quantifying, analyzing, and evaluating
modular conservation and divergence across species
\end{itemize}

\end{document}
