\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{Comparative Analysis of\\Molecular Interaction Networks}
}

\author{\\\\
\blue{Mehmet Koyut\"{u}rk, Ananth Grama}\\
\green{Purdue University}\\\\
\blue{Yohan Kim, Shankar Subramaniam} \\
\green{University of California, San Diego} \\ \\
\\
}

\date{}
\maketitle

\vspace{1.0in}
{\small{\blue{Acknowledgment:} Funding for this work was provided by the 
\red{National Institutes of Health} Grant \# R01 GM068959-01.}}

\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 \green{Analyzing} biological networks for \blue{conserved molecular interaction patterns}
\item Pairwise \green{Alignment} of protein-protein interaction networks
\item \green{Probabilistic} models/analyses for assessing \blue{statistical significance}
}
\bigitem{Computational Synthesis of Interaction Networks}
{
\item Inferring function from domain co-evolution
}

\item Ongoing Work \& Conclusion

\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}
\item Computational problem is known as \blue{graph mining}
}

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

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

\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 Mining 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 Mining}
\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/homes/koyuturk/mule/}}
\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 mining 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{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 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/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}

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

%Slide

\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 PPI 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 generalize 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{Generalizing Results to Complex Models}
\begin{itemize}
\bigitem{Piecewise $G(n,p)$ model} {
\item The size of largest dense subgraph is still proportional to
$\log n/ \kappa$ with a constant factor depending on \blue{number of hubs}}

\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{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/koyuturk/proximus/}}
}
\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}
