\documentclass[landscape,dvips]{foils}

%\documentclass[a4paper,landscape,headrule]{foil


%\usepackage[latin1]{inputenc}
%\usepackage{graphicx}

\MyLogo{Slide}

\usepackage{amsmath,amsthm,amssymb,amscd}
\usepackage{alltt}
\usepackage{epsf}
%\usepackage{amsfonts}
\def\w{{\cal W}}
\usepackage{latexsym}
\usepackage{times}
\usepackage{bookman}
\usepackage{graphics}
\usepackage{color}
\usepackage{epsfig}
\usepackage{psfrag}
\usepackage[ps2pdf]{hyperref}

\newcommand{\img}[2]{{\\epsfxsize=#1truecm\epsfbox{Images/PS/#2}}}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{corollary}{Corollary}
\newtheorem{definition}{Definition}
\newtheorem{proposition}{Proposition}

\def\basswidt{4.0in}
\def\gutter{0.2in}

\newenvironment{comment}{\setbox0=\vbox\bgroup}{\egroup}
\newenvironment{singlespace}{\def\baselinestretch{1.0}\large\normalsize}{\par}

%\setlength{\textheight}{8.5in}
%\setlength{\textwidth}{6in}
\setlength{\textheight}{8in}
\setlength{\textwidth}{9in}
\voffset=-0.9in

\newcommand{\ie}{{\sl i.e.}}

\newcommand{\support}{{\sigma}}
\newcommand{\freq}{{\xi}}
\newcommand{\minsup}{{\sigma^{*}}}
\newcommand{\minfreq}{{\xi^{*}}}
%\newcommand{\I}{{\cal{I}}}
%\newcommand{\T}{{\cal{T}}}
\newcommand{\A}{{\cal{A}}}
\newcommand{\G}{{\cal{G}}}
\newcommand{\F}{{\cal{F}}}
\newcommand{\E}{{\cal{E}}}
\newcommand{\V}{{\cal{V}}}
\newcommand{\La}{{\cal{L}}}
\newcommand{\lgraph}{{G=(V,E,\La)}}
\newcommand{\ugraph}{{\bar{G}=(\bar{V},\bar{E},\La)}}
\def\M{{\cal M}}
\def\N{{\cal N}}
\def\D{{\cal D}}
\def\vv{{\mathbf v}}
\def\uu{{\mathbf u}}

\newcommand{\blue}[1]{{\color{blue} #1}}
\newcommand{\green}[1]{{\color{green} #1}}
\newcommand{\red}[1]{{\color{red} #1}}
\newcommand{\stitle}[1]{\foilhead{\red{#1}}}
\newcommand{\bigitem}[2]{\item{#1\begin{small}\begin{itemize}#2\end{itemize}\end{small}}}
\newcommand{\mcite}[3]{\small{\red{[#1, {\sl #2}, #3]}}}
\newcommand{\eg}{{\sl e.g.}}

\leftheader{Ananth Grama}
\rightheader{\filedate}                % \filedate is defined above

\begin{document}

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

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

\date{}
\maketitle

\noindent
{\small{Various parts of this work involve collaborations with 
Shankar Subramaniam (UCSD) and Mehmet Koyuturk (Case Western)}}

\noindent
{\small{This work is supported by National Institutes of Health and
National Science Foundation.}}

\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 Conservation, Inference, Projection, Up- and Down-scaling }

\bigitem{Networks, Annotations, and Phenotypic Characterization}
{\item Correlations across genotype, SNPs, transcriptional relationships, etc.}

\end{itemize}


\stitle{The AfCS Molecule Pages}

\centerline{\epsfig{file=molecule_pages.eps,width=0.6\textwidth}}

\noindent
The complete state network of Molecule Pages, which currently
consists of 13883 states and 20556 transitions among these states
({\tt http://www.signaling-gateway.org/molecule/}).




%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 Subgraph Isomorphism!
}
\end{itemize}



\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{Results: Analyzing PPI Networks}

\begin{itemize}
\bigitem{PPI networks for \blue{9 eukaryotic organisms} derived from BIND and DIP}
{\item {\sl A. thaliania, O. sativa, S. cerevisiae, C. elegans, D. melanogaster,
            H. sapiens, B. taurus, M. musculus, R. norvegicus}
 \item \# of \green{proteins} ranges from 288 ({\sl Arabidopsis}) to 8577 ({\sl fruit fly})
 \item \# of \green{interactions} ranges from 340 ({\sl rice}) to 28829 ({\sl fruit fly})
}
\bigitem{Ortholog contraction}
{\item Group proteins according to existing \blue{COG} ortholog clusters
 \item Merge \blue{Homologene} groups into COG clusters
 \item Cluster remaining proteins via \blue{BLASTCLUST}
 \item Ortholog-contracted {\sl fruit fly} network contains 11088 \green{interactions}
 between 2849 \green{ortholog groups}
}

\item {\sc Mule} is available at \\
\blue{\url{http://www.cs.purdue.edu/pdsl/}}
\end{itemize}

\stitle{Conserved Protein Interaction Patterns}

\vspace{1in}
\centerline{
\begin{psfrags}
\scriptsize
\psfrag{Pattern}[c][c]{{\sl Pattern}}
\psfrag{CE}[lt][lt]{{\sl C. elegans}}
\psfrag{SC}[l][l]{{\sl S. cerevisiae}}
\psfrag{DM}[ct][ct]{{\sl D. melanogaster}}
\leavevmode
\epsfig{file=ribon.eps, width=4.5in}
\end{psfrags}
}
\vspace{0.5in}
\centerline{\blue{Small nuclear ribonucleoprotein complex} (\green{$p < 2e-43$})}

\stitle{Conserved Protein Interaction Patterns}

\vspace{1in}
\centerline{
\begin{psfrags}
\scriptsize
\psfrag{Pattern}[c][c]{{\sl Pattern}}
\psfrag{HS}[c][c]{{\sl H. sapiens}}
\psfrag{SC}[c][c]{{\sl S. cerevisiae}}
\psfrag{BT}[c][c]{{\sl B. taurus}}
\leavevmode
\epsfig{file=arp23.eps, width=4.5in}
\end{psfrags}
}
\vspace{0.5in}
\centerline{\blue{Actin-related protein Arp2/3 complex} (\green{$p < 9e-11$})}

\stitle{Conserved Protein Interaction Patterns}

\vspace{1in}
\centerline{
\begin{psfrags}
\scriptsize
\psfrag{Pattern}[c][c]{{\sl Pattern}}
\psfrag{HS}[c][c]{{\sl H. sapiens}}
\psfrag{DM}[c][c]{{\sl S. cerevisiae}}
\psfrag{SC}[l][l]{{\sl D. melanogaster}}
\leavevmode
\epsfig{file=vac.eps, width=6in}
\end{psfrags}
}
\vspace{0.5in}
\centerline{\blue{Endosomal sorting} (\green{$p < 1e-78$})}



\stitle{State of the Art}

\begin{itemize}
\item
Data is the bottleneck (in-silico construction of the network?).
\item
Reliable data on no more than ten organisms. Networks with thousands of
nodes and tens of thousands of interactions.
\item
The exponential complexity of these algorithms makes them ideal candidates
for large-scale platforms.
\item
Current implementations scale to thousands of processors and take days of
runtime.
\end{itemize}

%Slide
\stitle{Alignment of 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}

\stitle{Subnets Conserved in Yeast and Fruit Fly Using our Technique}

\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{State of the Art}

\begin{itemize}
\item
Local methods are suited to identification of modularity.
\item
Global methods (IsoRank, Berger et al.) support functional orthology.
\item
Can we improve the search efficiency and coverage of greedy (local) methods?
\item
Speed up the eigenvalue computations of spectral methods.
\item
Current algorithms scale to thousands of processors.
\item
Data quality is a key concern.
\end{itemize}

\stitle{Continuing Developments}

\begin{itemize}
\item
Building comprehensive maps that model crosstalk and weak signals
(inference, modularity).
\item
Constructing accurate flux models (data?)
\item
Full scale flux analysis for molecular processes.
\end{itemize}


\stitle{Continuing Developments}

\begin{itemize}
\item
Scaling molecular networks in space and time.
\item
Spatial scales must integrate atomistic models, scaling to cellular
scale, tissue scale, individual, populations, ecosystems.
\item
Temporal scales must reconstruct evolution and project trajectories.
\end{itemize}


\stitle{Functional and Phenotypic Characterization}

\begin{itemize}
\item
Integrate large-scale SNP data, genomic data into functional characterization
of networks.
\item
Comprehensively characterize causality in disease specific networks.
\item
Supporting full-scale in-silico design of molecules.
\end{itemize}


\stitle{References}


{\small
\begin{itemize}

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

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

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

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

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

\stitle{References}

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

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

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

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



\end{document}
