\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

\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\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} Analysis of Biological Networks: Pattern Discovery
and Module Detection}}

\author{{\color{green}Mehmet Koyut\"{u}rk and Ananth Grama}}

\maketitle

\vspace*{2.0in}

\begin{center}
Acknowledgements: National Institutes of Health.
\end{center}

\thispagestyle{empty}

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

\bigitem{Biological Networks}
{\item Definition, problems, practical implications}

\bigitem{Current Work}
{\item Mining biological networks for frequent molecular interaction patterns
 \item Alignment of protein interaction networks
}

\bigitem{Ongoing and Future Work}
{\item Module detection based on phylogeny profiles
 \item Constructing reference module maps
}

\end{enumerate}

%Slide
\stitle{Biological Networks}

\begin{itemize}

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

\bigitem{Experimental/induced data in various forms}
{\item Protein interaction 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 Interaction Networks}

\begin{itemize}
\bigitem{Interacting proteins can be discovered experimentally}
{\item Two-hybrid
 \item Mass spectrometry
 \item Phage display
}
\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{Analysis of Biological Networks}

\begin{itemize}
\bigitem{Evolution thinks modular}
{\item Selective pressure on preserving interactions
 \item Functional modules, protein complexes are highly conserved
}
\bigitem{Computational methods for discovery and analysis modules and complexes}
{\item \blue{Graph clustering:} Functionally related entities are densely connected
 \item \green{Graph mining:} Common topological motifs, frequent 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}

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

%Slide
\stitle{Extending Frequent Itemset Mining to Graph Mining}
\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 mining problem is considerably more difficult
\end{itemize}

%Slide
\stitle{Graph Mining 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 only 
       generate 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{Uniquely-Labeled Graphs}

\begin{itemize}
\item {\blue{Contract nodes with identical label 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 uniquely-labeled representation}
\item Discovered frequent subgraphs are still \green{biologically interpretable}!
\end{itemize}
\vspace{0.3in}
\centerline{
\epsfig{file=unique1.eps,width=4.5in}
}

%Slide
\stitle{Node Contraction in Metabolic Pathways}

\begin{itemize}
\bigitem{Uniquely-labeled 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}
\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 uniquely-labeled graph obtained
by contracting the same-label nodes of graph $G$. Then, \green{ if $S$ 
is a subgraph of $G$, $\tilde{S}$ is a subgraph of $\tilde{G}$}.

\blue{Corollary:} The uniquely-labeled representation of any frequent subgraph 
is frequent in the set of uniquely-labeled 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}

\blue{Observation:} A uniquely-labeled graph 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 transactions} $\{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 transactions} (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}
}

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

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

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

\begin{itemize}

\bigitem{Defining graph alignment is difficult in general}
{\item Biological meaning
 \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 
 \item Guided by models of evolution
}  

\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 PINs $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 \green{homologous}}
\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$}


%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 PINs. A match is associated with 
       \green{score} $\mu$.
\item A \red{mismatch} $\in \N$ corresponds to two pairs of homolog proteins from each 
      PIN 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 PINs}

\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 alignment score
larger than a certain threshold.}
{\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 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 \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 greater
       than a threshold, 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}}$
  \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{\red{Duplication penalty}}
{\item $\delta(u,u') = \bar{\delta} (d-S(u,u'))$}
\end{itemize}

%Slide
\stitle{Alignment of Human and Mouse PINs}

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

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

%Slide
\stitle{Ongoing Work on PIN 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 PINs}

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

\item {Web-based interface for PIN alignment queries}

\end{itemize}

%Slide
\stitle{Constructing Module Maps}

\begin{itemize}
\item Find functional modules in a comprehensive PIN (\green{yeast}) through
       \blue{graph clustering}
\item Find best matches to these modules in several species through
      \blue{pairwise alignment}
\item Construct \blue{canonical module maps} using these alignments
\item Analyze \blue{canonical pathways} on these maps
\end{itemize}

%Slide
\stitle{Clustering Phylogeny Profiles for Module Detection}

\begin{itemize}
\item Interacting proteins are likely to have \blue{co-evolved}
 \item Phylogeny profiles have been successful in predicting
       interactions
 \item We can discover functional modules and complexes through
       \blue{clustering phylogeny profiles}
 \item However, significant challenges remain
\end{itemize}

\vspace{0.3in}
\centerline{\epsfig{file=phylo.eps, height=3.5in}}

%Slide
\stitle{Thank You.}

\end{document}
