\documentclass[landscape,dvips]{foils}

\usepackage{amsmath,amsthm,amssymb,amscd}
\usepackage{alltt}
\usepackage{epsf}
\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}{8in}
\setlength{\textwidth}{9in}
\voffset=-0.9in

\def\helv{\sffamily bfseries}
\def\noi{\noindent}
\def\la{\langle}
\def\rf{\rangle}
\def\eod{\vrule height 6pt width 5pt depth 0pt}
\def\parsec{\par\noindent}
\def\big{\bigskip\parsec}
\def\med{\medskip\parsec}
\def\aa{\alpha}
\def\bb{\beta}
\def\dd{\delta}
\def\pr{{\rm Pr}}
\def\l{\ell}
\def\t{\theta}
\def\d{\delta}
\def\eps{\varepsilon}
\def\lf{\lfloor}
\def\rf{\rfloor}
\def\wt{\widetilde}
\def\ol{\widehat}
\def\TG{\wt{G}}
\def\TX{\wt{X}}
\def\TF{\wt{F}}
\def\TV{\wt{V}}
\def\w{{\cal W}}
\def\C{{\cal C}}
\def\S{{\cal S}}
\def\P{{\cal P}}
\def\Var{{\bf Var}}
\def\E {{\bf E }}
\def\kk{\kappa}
\def\TH{\widetilde{H}}
\def\th{\widetilde{h}}
\def\la{\langle}
\def\ra{\rangle}
\def\om{\omega}
\def\L{{\cal L}}
\def\I{{\cal I}}
\def\sign{\hbox{\rm sign}}
\def\w{{\cal W}}
\def\W{{\cal W}}
\def\A{{\cal A}}
\def\M{{\cal M}}
\def\N{{\cal N}}
\def\D{{\cal D}}
\def\B{{\cal B}}
\def\hb{\hat{b}}
\def\MT{{\bf T}}
\def\bb{{\bf b}}
\def\vpi{\mbox{\boldmath $\pi$}}
\def\pstat{{\bf \Pi}}

%\def\bb{\beta}
\def\ee{\epsilon}
\def\GG{\Gamma}
\def\mm{\mu}
\def\oo{\omega}
\def\ss{\sigma}
\def\w{{\cal W}}
\def\E{{\mathbf E}}
\def\G{{\mathbf G}}
\def\V{{\mathbf V}}
\def\vv{{\mathbf v}}
\def\uu{{\mathbf u}}

\def\roh{\rho _{H}}
\def\alph{{\cal S}}
\def\te{{\bf t}}
\def\pat{{\bf p}}
\def\ahz{A_\w(z)}
\def\phb{P(H)}
\def\pht{P_H(H)}
\def\langa{{\cal S}}
\def\lgh{{\cal R}}
\def\lrh{{\cal R}}
\def\llh{{\cal L}}
\def\luh{{\cal U}}
\def\lah{{\cal S}}
\def\lmh{{\cal M}}

\def\lbar{\bar{L} (z)}
\def\ltilde{L_{\w} (z)}
\def\dht{D_{\w}(z)}
\def\mht{{\bf M}(z)}
\def\uht{U_{\w}(z)}
\def\uhit{U_{\w}^i(z)}
\def\aht{A_{\w}(z)}
\def\bht{B_{\w}(z)}
\def\mfz{{F} (z)}
\def\mgz{{\cal G} (z)}
\def\rhi{R_{i}(z)}
\def\fah{A_\w(z)}
\def\fuh{L_\w(z)}
\def\dh{D_\w}
\def\nh{N_\w}
\def\ah{A_{\w}}
\def\dhz{{P(H)z^m+(1-z)A_\w(z)}}
\def\nhz{{P(H)z^m+(1-z)(A_\w(z)-1)}}
\def\ltr{{{\cal T} _r}}
\def\ltt{{{\cal T} }}
\def\lt0{{{\cal T}_0}}
\def\T{{\cal T}}
\def\trn{t_{r,n}}
\def\Var{{\bf Var}}
\def\L{{\cal L}}
\def\R{{\cal R}}
\def\U{{\cal U}}
\def\M{{\cal M}}
\def\TM{M_{\w}}
\def\TU{U_{\w}}
\def\VP{{\bf P}}
\def\VZ{{\bf Z}}

\def\I{{\bf I}}
\def\CD{{\cal D}}
\def\CP{{\cal P}}
\def\cha#1{{[\![\,#1\,]\!]}}

\def\noi{\noindent}
\def\lf{\lfloor}
\def\rf{\rfloor}
\def\la{\langle}
\def\ra{\rangle}
\def\eod{\vrule height 6pt width 5pt depth 0pt}
\def\parsec{\par\noindent}
\def\big{\bigskip\parsec}
\def\med{\medskip\parsec}
\def\ol{\overline}
\def\P{{\bf P}}
\def\l{\ell}
\def\eps{\varepsilon}
\def\r{\bar R}
\def\R{\bar R}
\def\A{{\cal A}}
\def\E{{\bf E}}
\def\CR{{\cal R}}
\def\P{{\cal P}}
\def\S{{\cal S}}
\def\a{\alpha}
\def\M{{\cal M}}
\def\H{{\cal H}}
\def\SF{{\cal SF}}
\def\Z{{\Bbb Z}}
\def\Real{{\Bbb R}}
\def\RR{\Real}
\def\CC{{\Bbb C}}
\def\th{\theta}
\def\Var{{\rm Var ~}}
\def\phb{P(H)}
\def\VP{{\bf P}}
\def\pstat{{\bf \Pi}}
\def\VT{{\bf T}}
\def\F{{\Bbb F}}
\def\l{\ell}
\def\W{{\cal W}}
\def\VZ{{\bf Z}}
\def\vpi{\mbox{\boldmath $\pi$}}
\def\I{{\bf I}}
\def\wt{\widetilde}
\def\pr{{\rm Pr}}
\def\eps{\varepsilon}
\def\lef{\preceq}

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

\begin{document}

\title{{\color{red}
Building Cellular Interaction Databases: Analysis, Synthesis, and
Interfaces}}

\author{Ananth Grama, Computer Sciences, Purdue University}
\date{}

\maketitle

\begin{center}

{\small In collaboration with \\ \vspace{0.2in}
Mehmet Koyut\"urk (Purdue University), \\
Yohan Kim and Shankar Subramaniam (UC-San Diego)} \\ \vspace{2.0in}

{\small Work supported by \\
National Institutes of Health and \\
National Science Foundation}
\end{center}


\thispagestyle{empty}

% Outline
\stitle{Outline}
\begin{enumerate}

\bigitem{Biological Networks}
{\item Definitions, problems, applications}

\bigitem{Current Work}
{
 \item Analyzing biological networks for conserved molecular interaction patterns
 \item Alignment of protein interaction networks based on evolutionary models
 \item Module identification based on phylogenetic profiles
}

\bigitem{Ongoing and Future Work}
{
 \item Projecting modules extracted from available networks to
 other genomes
 \item Phylogenetic analysis at modular level
 \item Constructing reference module maps
 \item Building a fully functional interoperable signaling database
}

\end{enumerate}

% Biological networks -- definition
\stitle{Biological Networks}

\begin{itemize}

\bigitem{Interactions between \green{biomolecules} that drive cellular
\blue{processes}}
{\item \green{Genes, proteins, enzymes, chemical compounds}
 \item \blue{Chemical transformation \& energy generation,
information transfer}
 \item  Coarser level than sequences in life's complexity pyramid
}

\bigitem{Experimental/inferred data in various forms} {\item
Protein-protein interaction (PPI) networks
 \item Gene regulatory networks
 \item Metabolic \& signaling pathways
}

\bigitem{What do we gain from analysis of cellular networks?}
{\item Modular analysis of cellular processes
 \item Understanding evolutionary relationships at a higher level
 \item Assigning functions to proteins through interaction information
 \item Intelligent drug design: block protein, preserve pathway
}

\end{itemize}

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

\begin{itemize}
\bigitem{Interacting proteins can be discovered experimentally}
{\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.5in}
\leavevmode
\end{psfrags}
\hspace{1.7in}
\epsfig{file=pinsample.eps, height=2.8in}
\hspace{0.3in}
}
\centerline{\hspace{4in} {\sl S. Cerevisiae} protein interaction network}
\centerline{\hspace{4in}\scriptsize{Source: Jeong et al. Nature 411: 41-42, 2001.}}

%Slide
\stitle{Gene Regulatory Networks}

\begin{itemize}
\bigitem{Genes regulate each others' expression}
{\item A simple model: Boolean networks
 \item Can be derived from gene expression data
}
\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}
\hspace{0.3in}
}
\centerline{\hspace{4in}Genetic network that controls}
\centerline{\hspace{4in}flowering time in {\sl A. Thaliania}}
\centerline{\hspace{4in}\scriptsize{Source: Blazquez et al. EMBO Reports  2: 1078-1082, 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 Directed hypergraph/ graph models
}
\end{itemize}

\vspace{0.1in}
\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=4in}
\hspace{0.3in}
}
\centerline{\hspace{4in} Glycolysis pathway in {\sl S. Cerevisiae}}
\centerline{\hspace{4in}\scriptsize{Source: Hynne et al. Biophysical Chemistry, 94, 121-163, 2001.}}

%Slide
%\stitle{Discrete Algebraic Techniques in Analysis}
%\begin{itemize}
%\bigitem{Non-orthogonal decomposition of binary matrices}
%{\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
%}
%\end{itemize}
%
%\centerline{\blue{Analysis of gene expression data}}
%\vspace{0.2in}
%\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{Koyut\"urk, Grama, Szpankowski: {\sl CSB'03.}}\hspace{1in}
%\scriptsize{Koyut\"urk, Grama, Szpankowski: {\sl CSB'04}.}}
%%Slide
\stitle{Analysis of Biological Networks}

\begin{itemize}
\bigitem{Evolution thinks in a modular fashion}
{\item Selective pressure on preserving interactions
 \item Functional modules, protein complexes are highly conserved
}
\bigitem{Computational methods for discovery and analysis of modules and complexes}
{\item \blue{Graph clustering:} Functionally related entities are densely connected
 \item \green{Graph analysis:} Common topological motifs, conserved interaction patterns reveal
       modularity
 \item \green{Graph alignment:} Conservation/divergence of modules and pathways
 \item \red{Module maps:} Canonical pathways across species
 \item \red{Phylogenetic analysis:} Genes/proteins that belong to a common module
       are likely to have co-evolved
}
\end{itemize}

% Graph mining
\stitle{How do we detect conserved subgraphs?}
[Koyut\"urk, Grama, Szpankowski, ISMB04, Bioinformatics04]

\begin{itemize}
\bigitem{Given a collection of biological networks that belong to
several organisms, discover sets of related interactions that
frequently occur together} { \item  \blue{Protein interaction
networks:} Common interactions between orthologous proteins,
possibly a conserved functional module \item \green{Metabolic
pathways:} Sub-pathways common to a group of organisms, may reveal
functional conservation/divergence }

\bigitem{Earlier work focused on identifying common topological
motifs} {\item We can discover orthologous subgraphs by taking
into account the identity of molecules \item Contract orthologous
proteins to relate networks between species
\item Contracting orthologs simplifies the computational problem as well}

\end{itemize}

\stitle{Graph Analysis: An Example}

\vspace{0.5in} \centerline{While mining PPI networks,
\blue{orthologous} proteins} \centerline{are modeled by
\blue{identically colored} nodes}

\vspace{0.8in} \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.3in}
\centerline{Graph database} \vspace{0.8in} \centerline{
\epsfig{file=subgraph1.eps,width=4in} \hspace{0.5in}
\epsfig{file=subgraph2.eps,width=4in} } \vspace{0.3in}
\centerline{Subgraphs with frequency 3}

%Slide
\stitle{Extending Frequent Itemset Mining to Graph Analysis}
\begin{itemize}
\item {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 A set is frequent only if all of its subsets are frequent
 \item Generate itemsets from small to large, pruning supersets of
       infrequent sets}
\bigitem {Can be generalized to mining graphs}
{\item \blue{transaction} $\rightarrow$ \green{graph}
 \item \blue{item} $\rightarrow$ \green{node}, \green{edge}
 \item \blue{itemset} $\rightarrow$ \green{subgraph}
}
\item However, the graph analysis problem is considerably more difficult!
\end{itemize}

%Slide
\stitle{Analyzing Graphs: Challenges}
\begin{itemize}
\bigitem {Subgraph Isomorphism}
{\item For counting frequencies, it is necessary to check whether a given graph
       is a subgraph of another one
 \item NP-complete
}
\bigitem{Canonical labeling}
{\item To avoid redundancy while generating subgraphs, canonical labeling of
       graphs is necessary
 \item Equivalent to subgraph isomorphism
}
\bigitem{Connectivity}
{\item Patterns of interest are generally connected, so it is necessary to 
       generate only connected subgraphs
}
\bigitem{Existing algorithms mainly focus on minimizing redundancy and
      mining \& extending simple substructures}
{\item AGM, FSG, gSpan, SPIM, {\sc CloseGraph}}

\end{itemize}

%Slide
\stitle{Contracting Orthologous Nodes}

\begin{itemize}
\item {\blue{Contract orthologous nodes (proteins, enzymes) into a single node}}
\bigitem {\green{No} subgraph isomorphism}
{\item Graphs are uniquely identified by their edge sets}
\bigitem{Frequent subgraphs are \green{preserved} $\Rightarrow$ No information loss}
{\item Subgraphs that are frequent in general graphs are also frequent in
       their ortholog-contracted representation}
\bigitem{Discovered frequent subgraphs are still
\green{biologically interpretable}!} {\item Interaction between
proteins becomes interaction between protein families}
\end{itemize}
\vspace{0.3in}
\centerline{
\epsfig{file=unique1.eps,width=4.5in}
}

%Slide
\stitle{Node Contraction in Metabolic Pathways}

\begin{itemize}
\bigitem{Enzyme-contracted directed graph model} {\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{Node Contraction in Protein Interaction Networks}

\begin{itemize}
\bigitem{Relating proteins in different organisms}
{\item Clustering: Orthologous proteins show sequence similarities
 \item Phlyogenetic analysis: Allows multi-resolution analysis among distant species
 \item Literature, ortholog databases}
\bigitem{Contraction} {\item Interaction between proteins
$\rightarrow$ interaction between protein families \item Must
avoid distant paralogs}
\end{itemize}

\vspace{0.2in}
\centerline{\begin{psfrags}\begin{small}
\psfrag{548}[c][c]{\blue{KAPA}}
\psfrag{549}[c][c]{\blue{KAPB}}
\psfrag{550}[c][c]{\blue{KAPC}}
\psfrag{1735}[c][c]{\green{YPT7}}
\psfrag{2025}[c][c]{\green{YPT53}}
\psfrag{Kinase}[c][c]{\blue{cAMP}}
\psfrag{GTP}[c][c]{\green{GTP-binding}}
\epsfig{file=pincontract.eps,height=3in}
\end{small}\end{psfrags}}

%Slide
\stitle{Preservation of Subgraphs}

\blue{Theorem:} Let $\tilde{G}$ be the ortholog-contracted graph
obtained by contracting the orthologous nodes of graph $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 subgraph is 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}

\green{Labeling:} Assign a unique label to each ortholog group.
\blue{Observation:} Since each label is unique in an
ortholog-contracted graph, it is uniquely determined by the set of
its edges.

\vspace{0.5in}
\centerline{\blue{Maximal Frequent Subgraph Mining Problem}}
Given a set of \green{labeled graphs} $\{G_1, G_2, ..., G_m\}$, find all
\green{connected graphs} $S$ such that $S$ is a \green{subgraph} of at
least $\sigma m$ of the \green{graphs} (is frequent) and no \green{supergraph}
of $S$ is frequent (is maximal).

\vspace{0.5in} \centerline{\blue{Maximal Frequent Edgeset Mining
Problem}} Given a set of \green{edge (interaction) sets} $\{E_1,
E_2, ..., E_m\}$, find all \green{connected edge sets} $F$ such
that $F$ is a \green{subset} of at least $\sigma m$ of the
\green{edge sets} (is frequent) and no \green{superset} of $F$ is
frequent (is maximal).

%Slide
\stitle{From Graphs to Edgesets}

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

\vspace{1in} \centerline{We can construct the graphs on the left}
\centerline{ if we know the sets on the right}

%Slide
\stitle{{\sc Mule}: Mining Uniquely Labeled Graphs}

\vspace{0.5in}  \centerline{Depth-first enumeration of frequent
subgraphs}\centerline{using downward closure property}

\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.3in} 
\centerline{\small{\blue{$E$}: frequent subgraph, 
                   \green{$H$}: graphs that contain $E$,}}
\centerline{\small{\red{$D$}: already explored edges,
                   \blue{$C$}: edges to be added to $E$}}

%Slide
\stitle{Frequent Sub-Pathways in KEGG}

\vspace{0.5in}
\centerline{Glutamate metabolism (155 organisms)}

\vspace{0.5in}
\centerline{
\begin{psfrags}
\small
\psfrag{gltX}[c][c]{gltX} \psfrag{glnA}[c][c]{glnA}
\psfrag{glmS}[c][c]{glmS} \psfrag{guaA}[c][c]{guaA}
\psfrag{nadE}[c][c]{nadE} \psfrag{purF}[c][c]{purF}
\psfrag{B}[l][l]{\blue{45 (29\%) organisms}}
\psfrag{R}[l][l]{\red{30 (19\%) organisms}}
\psfrag{G}[l][l]{\green{22 (14\%) organisms}}
\leavevmode
\epsfig{file=glutamate.eps, width=4.5in}\hspace{2in}
\end{psfrags}
}

%Slide
\stitle{Frequent Interaction Patterns in DIP}

\begin{itemize}
\bigitem{Protein interaction networks for 7 organisms}
{\item Ecoli, Hpylo, Scere, Celeg, Dmela, Mmusc, Hsapi
 \item 44070 interactions between 16783 proteins}
\bigitem{Clustering with TribeMCL \& node contraction}
{\item 30247 interactions between 6714 protein families}
\end{itemize}

\centerline{
\begin{psfrags}
\scriptsize
\psfrag{0}[c][c]{KI}
\psfrag{1}[c][c]{MY}
\psfrag{2}[c][c]{ME}
\psfrag{3}[c][c]{ZF}
\psfrag{4}[c][c]{PR}
\psfrag{7}[c][c]{PN}
\psfrag{8}[c][c]{GR}
\psfrag{9}[c][c]{GT}
\psfrag{12}[c][c]{HO}
\psfrag{16}[c][c]{RH}
\psfrag{17}[c][c]{PH}
\psfrag{19}[c][c]{RB}
\psfrag{20}[c][c]{KR}
\psfrag{25}[c][c]{HS}
\psfrag{28}[c][c]{CA}
\psfrag{29}[c][c]{DK}
\psfrag{32}[c][c]{AC}
\psfrag{57}[c][c]{FH}
\psfrag{58}[c][c]{AR}
\psfrag{65}[c][c]{TU}
\psfrag{69}[c][c]{FT}
\psfrag{88}[c][c]{TI}
\psfrag{152}[c][c]{SK}
\psfrag{168}[c][c]{CK}
\psfrag{169}[c][c]{KA}
\psfrag{207}[c][c]{MI}
\psfrag{248}[c][c]{SF}
\psfrag{332}[c][c]{CD}
\psfrag{353}[c][c]{PI}
\psfrag{kinase}[l][l]{\green{Protein kinase}}
\psfrag{myosin}[l][l]{\blue{Myosin heavy chain}}
\psfrag{membrane}[l][l]{\blue{Membrane protein}}
\psfrag{prion}[l][l]{\blue{Prion-like Q/N rich domain}}
\leavevmode
\epsfig{file=./dip3.eps, width=5.5in}
\end{psfrags}
}

%Slide
\stitle{Runtime Characteristics}

\begin{center}
\blue{Comparison with isomorphism-based algorithms}\\
%\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 patters}
\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{Aligning Protein Interaction Networks} [Koyut\"urk, Grama,
Szpankowski, RECOMB05]

\begin{itemize}

\bigitem{Defining graph alignment is difficult in general}
{\item Biological significance
 \item Mathematical modeling}

\bigitem{Existing algorithms are based on simplified formulations}
{\item PathBLAST aligns \blue{pathways} (linear chains) to render problem
       computationally  tractable
\item Motif search algorithms look for small \blue{topological motifs}, do
      not take into account conservation of proteins
}

\bigitem{Our approach}
{\item Aligns \green{subsets of proteins} based on the observation
       that modules and complexes are conserved
 \item Guided by models of evolution: Detailed understanding of 
       conservation/ divergence
}

\end{itemize}

%Slide
\stitle{Evolution of Protein Interaction 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 This provides us with a simplified basis for solving a very hard
      problem
\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]{\green{Deletion}}
\psfrag{Insertion}[c][c]{\green{Insertion}}
\leavevmode
\epsfig{file=evolution.eps,width=8in}
\end{psfrags}}

%Slide
\stitle{Aligning Protein Interaction Networks: \blue{Input}}

\begin{itemize}
\item PPI networks $G(U,E)$ and $H(V,F)$
\bigitem{Sparse similarity function $S(u,v)$ for all $u,v \in U \cup V$}
 {\item If $S(u,v)>0$, $u$ and $v$ are potentially \green{orthologous}}
\end{itemize}

\vspace{0.4in}
\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{v4}[c][c]{$v_4$}
\leavevmode
\epsfig{file=instance.eps, width=5in}
\end{psfrags}
} \centerline{$G$ \hspace{2.5in} $H$} \vspace{0.4in}
\centerline{Identical color $\Rightarrow$ $S > 0$}

%Slide
\stitle{Local Alignment Induced by Subsets of Proteins}

\begin{itemize}
\bigitem{\blue{Alignment} induced by \blue{protein subset pair}
$P=\{\tilde{U}\in U ,\tilde{V}\in V\}$:
$\cal{A}(P)=\{\cal{M},\cal{N},\cal{D}\}$}
{\item A \green{match} $\in \M$ corresponds to two pairs of homolog proteins from each
       protein subset
       such that both pairs interact in both PPI networks. A match is associated with
       \green{score} $\mu$.
\item A \red{mismatch} $\in \N$ corresponds to two pairs of homolog proteins from each
      PPI network such that
      only one pair is interacting. A mismatch is associated with
       \red{penalty} $\nu$.
\item A \red{duplication} $\in D$ corresponds to a pair of homolog proteins that are
      in the
      same protein subset. A duplication is associated with \red{penalty} $\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}
}
\centerline{\small{Alignment induced by protein subset pair}}
\centerline{\small{$\{\{u_1,u_2,u_3,u_4\},\{v_1,v_2,v_3\}\}$}}

%Slide
\stitle{Pairwise Local Alignment of PPI networks}

\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 conservation of interactions
 \item Duplications are penalized for differentiation after split
 \item Mismatches are penalized for divergence and experimental error
}

\item All scores and penalties are functions of similarity between
      associated proteins

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

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


%Slide
\stitle{Weighted Alignment Graph $\mathbf{G}(\mathbf{V},\mathbf{E})$}

\begin{itemize}
\item $\mathbf{V}$ consists all pairs of ortholog 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 \red{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}$.}

\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=wsub.eps, height=3in}
\end{psfrags}
}

%Slide
\stitle{A Greedy Algorithm for {\sc MaWISh}}

\begin{itemize}
\bigitem{\blue{Greedy graph growing}}
{\item Start with a \green{heavily connected} node, put it in $\tilde{\V}$
 \item Choose $\vv$ that is most heavily connected to $\tilde{\V}$
       and put it in $\tilde{\V}$ until no $\vv$ is \green{positively
       connected} to $\tilde{\V}$.
 \item If total weight of the subgraph induced by $\tilde{\V}$ is statistically significant,
       return $\tilde{\V}$
 \item Works in linear time.
}

\item As modules and complexes are \green{densely connected} within the module
      and loosely connected to the rest of the network, this algorithm is
      expected to be effective.

\item For all local alignments, remove discovered subgraph and run the greedy
      algorithm again.

\item If the number of homologs for each protein is constant, construction
      of alignment graph and solution of the {\sc MaWISh} takes $O(|E|+|F|)$ time.

\end{itemize}

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

\begin{itemize}
\bigitem{Quantizing similarity between two proteins}
{ \item \blue{Confidence} in two proteins being \blue{orthologous}
        (\blue{paralogous})
  \item BLAST E-value: $S(u,v) =
  log_{10}\frac{p(u,v)}{p_{random}}$, where $p(u,v)$ is the
  probability of true homology between $u$ and $v$, given BLAST
  $E$-value
  \item Ortholog clustering: $S(u,v)=c(u)c(v)$, where $0\leq c(u) \leq 1$
  is the confidence of the INPARANOID algorithm in assigning $u$
  to its corresponding cluster
}

\bigitem{\green{Match score}} {\item Two interactions are
orthologous only if both interacting partners are orthologous
\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{\red{Duplication penalty}}
{\item $\delta(u,u') = \bar{\delta} (d-S(u,u'))$}
\end{itemize}

%Slide
\stitle{Alignment of Human and Mouse PPI Networks}

\vspace{0.8in}
\begin{small}
\begin{psfrags}
\psfrag{252}[c][c]{BMRB}
\psfrag{520}[c][c]{AVR2}
\psfrag{5793}[c][c]{ALK3}
\psfrag{5795}[c][c]{BMP4}
\psfrag{5796}[c][c]{BMRA}
\psfrag{5797}[c][c]{BMP6}
\psfrag{5798}[c][c]{AVR1}
\psfrag{5799}[c][c]{AVRB}
\psfrag{5800}[c][c]{BMP7}
\psfrag{5823}[c][c]{GDF5}
\centerline{\sl \blue{Homo Sapiens}}
\vspace{0.1in}
\centerline{\epsfig{file=Hsapi2.eps, width=8in}}
\vspace{0.5in}
\centerline{\sl \green{Mus Musculus}}
\vspace{0.1in}
\centerline{\epsfig{file=Mmusc2.eps, width=8in}}
\end{psfrags}
\end{small}
\vspace{0.5in}
\centerline{\red{A conserved subnet that is part of}}
\centerline{\red{transforming growth factor
beta receptor signaling pathway}}

%Slide
\stitle{Alignment of Yeast and Fly PPI Networks}

\vspace{0.8in}
\begin{small}
\begin{psfrags}
\psfrag{2262}[c][c]{HS82}
\psfrag{1524}[c][c]{HS83}
\psfrag{2329}[c][c]{STI1}
\psfrag{1271}[c][c]{CNS1}
\psfrag{17366}[c][c]{HS83}
\psfrag{19288}[c][c]{CG2720-PA}
\psfrag{20630}[c][c]{CG5393-PB}
\centerline{\sl \blue{Saccharomyces Cerevisiae}}
\vspace{0.1in}
\centerline{\epsfig{file=Scere5.eps, width=2.5in}}
\vspace{0.5in}
\centerline{\sl \green{Drosophila Melanogaster}}
\vspace{0.1in}
\centerline{\epsfig{file=Dmela5.eps, width=2.5in}}
\end{psfrags}
\end{small}
\vspace{0.5in} \centerline{\red{A conserved subnet that is part
of}} \centerline{\red{response to stress}} \vspace{0.3in}
\centerline{\small{Penalties need to be relaxed while analyzing
distant species}}



%Slide
\stitle{Ongoing Work on PPI Network Alignment}

\begin{itemize}
\bigitem{Assessing statistical significance}
{\item Constructing a refence model based on models of evolution}

\bigitem{BLAST-like search queries for network alignment}
{\item Given a query graph, find all high-scoring local alignments in a
       database of PPI networks}

\bigitem{Multiple Graph Alignment (CLUSTAL, BLASTCLUST)}
{\item How to combine graph mining and pairwise alignment}


\end{itemize}

%Slide
\stitle{Inferring Functional Modules from Phylogenetic
Information} [Kim, Koyut\"urk, Topkara, Grama, Subramaniam, \\ECCB05
(submitted)]

\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 [Pellegrini et al. (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}

%Slide
\stitle{Identification of Co-evolved Domains}

\begin{itemize}

\item{While sequence information is widely available,
domain information is not generally comprehensive}

\bigitem{Approximating domains between \blue{fixed-size} segments
[Kim \& Subramaniam (2004)]}
{
\item Chop proteins into overlapping ({\em e.g.}, 30 residues)
fixed-size ({\em e.g.}, 120 residues) segments
\item Construct phylogenetic profile for each segment, find
maximum-mutual-information segment pair for each protein pair
\item Improves single-profile based approach
\item However, there is no fixed domain size
}

\bigitem{Can we \blue{identify} domains from phylogenetic information as well?}
{
\item \green{Residue phylogenetic profiles}!
}

\end{itemize}

%Slide
\stitle{Residue-Level Phylogenetic Analysis}

\begin{itemize}

\bigitem{\green{Residue phylogenetic profile}}
{
\item For each residue $r_{ij}$ on protein $P_i$, the existence of $r_{ij}$ in
genome $G_k$ is signified by the minimum e-value of alignments between $P_i$ and
$G_k$ that contain $r_{ij}$
}
\bigitem{\blue{Mutual information matrix}}
{
\item Matrix of mutual information between any pair of residues each from one protein
\item $M(P_i, P_j)=[m_{kl}]$,\\
   where $m_{kl}=I(profile(r_{ik}), profile(r_{jl}))$
}
\item A sufficiently large contiguous submatrix of the mutual information
matrix that contains consistently high entries may correspond to a
pair of co-evolved domains.
\end{itemize}

%Slide
\stitle{Mutual Information Matrix}

\centerline{\epsfig{file=miMatrixChemotaxis.eps,width=6in}}

\centerline{\blue{Mutual information matrix} for proteins \green{CheA} and \green{CheB}
 in E-coli.}
\centerline{Darker pixels indicate higher mutual information.}
\vspace{0.5in}

\centerline{\red{Co-evolved domains identified by dark submatrices!}}

%Slide
\stitle{Clustering Residue Phylogenetic Profiles}

\begin{itemize}

\item{Cluster residues to identify co-evolved domains }

\bigitem{For each protein pair}
{
\item Downsample residues of each protein (for computational efficiency)
\item Construct residue phylogenetic profiles
\item Compute mutual information matrix
\item Identify \blue{sufficiently large contiguous submatrices} of mutual information
      matrix with \green{consistently high mutual-information scores}
\item Set \red{phylogenetic association score} of the two proteins to the
      maximum of mutual information of such matrices
}
\item{Can be used for \blue{domain identification} as well!}
\end{itemize}

%Slide
%\stitle{Comparison of Domain-Profile and Single-Profile Methods}
%
%\centerline{\epsfig{file=miDistributions.eps,width=6in}}
%\centerline{\blue{Distribution of  Mutual Information}}
%
%\centerline{Two proteins are considered \green{functionally associated}}
%\centerline{if they co-occur in a metabolic pathway derived from KEGG}
%
%%Slide
\stitle{Comparison of Domain-Profile and Single-Profile Methods}

\centerline{\epsfig{file=stringAccuCov.eps,width=6in}}
\centerline{\blue{Accuracy vs Coverage}}

\centerline{\green{Accuracy:} Fraction of true-positives among}
\centerline{ all predicted functional associations}
\centerline{\red{Coverage:} Number of functionally associated}
\centerline{protein pairs that are identified by the algorithm}

%Slide
\stitle{Phylogenetic Analysis of Computationally Identified Functional Modules}

\begin{itemize}
\item ``Comprehensive'' PPI network for \blue{Saccharomyces Cerevisiae}
is available
\bigitem{We can identify \green{functional modules} in this network based on
      density of interactions}
{\item Proteins in a functional module are expected to densely interact with
each other}
\bigitem{Whole genome sequences for many other species are available}
{\item \red{12 yeast species:} \sl{S. Bayanus, S. Kluyveri, 
S. Kudriavzevii, S. Paradoxus, S. Mikatae, S. Castellii, K. Lactis, 
D. Hansenii, A. Gossypii, C. Glabrata, Y. Lipolytica, S. Pombe}
}
\item Can we analyze the conservation of \blue{S. Cerevisiae} modules by 
projecting them on other yeast species based on sequence comparison?

\end{itemize}

% Sample module
\stitle{Computational Identification of Functional Modules \\
on {\sl S. Cerevisiae} PPI Network}

\vspace{0.5in}
\begin{psfrags}
\begin{scriptsize}
\psfrag{YER022W}[c][c]{SRB4}
\end{scriptsize}
\centerline{\epsfig{file=mainmodule.eps,width=4.5in}}
\end{psfrags}
\vspace{0.3in}
\centerline{A group of \green{densely interacting}}
\centerline{proteins involved in \red{RNA processing}}
\centerline{as identified by the \blue{MCODE} algorithm}

% Module Phylogenetic matrix
\stitle{Module Phylogenetic Matrix}

\begin{itemize}
\bigitem{For each protein in module, find orthologs in other yeast 
proteomes}
{\item If BLAST $E$-value for the best match of \blue{protein $P_i$} in 
\green{organism $G_j$} is $E_{ij}$, set the \red{$(i,j)^{th}$ entry} of 
\blue{module phylogenetic matrix} to \red{$1-1/\log(E_{ij})$}.}
\end{itemize}
\centerline{\epsfig{file=mainmoduleprf.eps,width=5in}}
\vspace{0.3in}
\centerline{Module phylogenetic matrix for the module in previous slide}
\centerline{\small{\blue{Rows: Proteins}, \green{Columns: Organisms}}} 
\centerline{Darker box indicates higher significance}

%Module conservation
\stitle{Module Conservation}
\vspace{0.3in}
\centerline{\epsfig{file=protcons.eps,width=3.8in}
            \hspace{0.2in}
            \epsfig{file=genomecons.eps,width=3.6in}}

\centerline{\small{\blue{First principal component}}\hspace{1.2in}
            \small{\green{First principal component}}}
\centerline{\small{\blue{in protein space}}\hspace{2.2in}
            \small{\green{in organism space}}}

\begin{itemize}
\bigitem{Principal component analysis provides a broad idea about conservation}
{\item \blue{ MED8, MED7, RRP46, SNP1, PCF11, TIF6, RRP25, SKI6,
       RRP4, SRP1, ERB1,} and \blue{HAS1} are almost perfectly conserved in 
       all genomes, while others are partially conserved
 \item \green{S. Bayanus, S. Paradoxus, S. Mikatae, S. Castellii, K. Lactis, A. Gossypii,} and \green{Y. Lipolytica} contain orthologs of almost all proteins in the module, while others contain only some of them}
\item{\red{Which proteins are conserved in which organisms? Why?}}
\end{itemize}

% An example
\stitle{An Example for Module Specification}
\vspace{0.2in}

\centerline{\hspace{1in}\blue{Module}\hspace{1.4in}\green{Conservation on NCBI Taxonomy}}
\centerline{\epsfig{file=module12.eps,width=3.5in}
            \hspace{0.2in}
            \epsfig{file=tree.eps,width=4in}}
\vspace{0.2in}
\centerline{Lower sub-module (\blue{RNA polymerase II transcription mediator activity})}\centerline{is completely conserved in \green{Y. Lipolytica}, \green{S. Pombe}, and \green{D. Hansenii},}
\centerline{while the upper sub-module (\red{3'-5'-exoribonuclease activity})}
\centerline{almost disappears in these organisms}

% Conservation in detail
\stitle{Ongoing Work on Module Phylogenetics}
\begin{itemize}
\bigitem{Which \blue{proteins} are conserved in which \green{organisms}? Why?}
{\item Does partial loss of proteins in a module imply \red{loss of function}?
 \item Are there modules that are divided due to \red{functional divergence}?
 \item Are there modules that are completely lost due to \red{functional divergence}?
 \item If a module is completely conserved, what does this imply in terms
       of \green{functional conservation} and \green{evolutionary pressure}?
 \item Are \blue{module-specific phylogenetic tree}s consistent with the 
       \green{whole-proteome phylogenotic tree}?
 \item How is \blue{topology} in PPI network related to \green{conservation}?
}
\item How do we quantify the conservation of a module in a given organism?
\end{itemize}

\stitle{So many questions, so little time!}



\end{document}
