\documentclass{beamer}

\mode<presentation>
{
  \usetheme{Purdue}
  \setbeamercovered{transparent}
}

\usepackage[english]{babel}
\usepackage[latin1]{inputenc}
\usepackage{times}
\usepackage[T1]{fontenc}

\newcommand{\blue}[1]{{\color{blue} #1}}
\newcommand{\dblue}[1]{{\color{dblue} #1}}
\newcommand{\green}[1]{{\color{green} #1}}
\newcommand{\red}[1]{{\color{red} #1}}
\newcommand{\bigitem}[2]{\item{#1\begin{small}\begin{itemize}#2\end{itemize}\end{small}}}

\newcommand{\ie}{{\em i.e.}}
\newcommand{\eg}{{\em e.g.}}
\newcommand{\etal}{{\em et al.}}

\title[]
{Functional Characterization and Topological Modularity of Molecular Interaction Networks}

\author[Pandey, Koyut\"urk, Grama]
{Jayesh~Pandey\inst{1} \and
 Mehmet~Koyut\"urk\inst{2} \and
 \textcolor{red}{Ananth~Grama}\inst{1}
}

\institute[Purdue and CWR University]
{
  \inst{1}%
  Department of Computer Science\\
  Purdue University
  \and
  \inst{2}%
  Department of Electrical Engineering \& Computer Science\\
  Case Western Reserve University}

\date[APBC 2010] 
{Asia Pacific Bioinformatics Conference, 2010}

\subject{Bioinformatics}

%\AtBeginSection[]
%{
%  \begin{frame}<beamer>{Outline}
%    \tableofcontents[currentsection]
%  \end{frame}
%}


\begin{document}

\begin{frame}
  \titlepage
\end{frame}

%\begin{frame}{Outline}
%  \tableofcontents
%\end{frame}


\section{Background}

\begin{frame}{Molecular Interaction Networks}
\begin{columns}
\column{0.6\textwidth}
\begin{itemize}
  \item Provides a high level description of cellular organization
  \item Directed and undirected graph representation
  \bigitem{Nodes represent cellular components}
  {
  	\item Protein, gene, enzyme, metabolite
  }
  \bigitem{Edges represent reactions or interactions}
  {
    \item Binding, regulation, modification, complex membership, substrate-product relationship
  }
\end{itemize}
\column{0.45\textwidth}
\centerline{\includegraphics[height=\textwidth]{./images/pinsample.eps}}
\centerline{\scriptsize{\hspace{0.2in} {\em S.cerevisiae}}}
\centerline{\scriptsize{Protein-Protein Interaction (PPI) Network}}
\end{columns}
\end{frame}

\begin{frame}{Function : Gene Ontology}
\begin{columns}[c]
\column{0.6\textwidth}
\begin{itemize}
\item{\blue{Molecular annotation} provides a unified understanding of the underlying principles}
%\item{Significant progress on standardizing knowledge at the molecular level}
\item Gene Ontology: A controlled vocabulary of molecular functions, biological 
processes, and cellular components
\item Terms (concepts) related by {\em is-a, part-of} relationships
\item If a molecule is annotated by a term, then it is also annotated by terms on
the paths towards root.
\end{itemize}
\column{0.45\textwidth}
\centerline{\includegraphics[width=0.8\textwidth]{images/go1.eps}}
\end{columns}
\end{frame}

\begin{frame}{Function \& Topology in Molecular Networks}
How does function relate to network topology?
\centerline{\includegraphics[width=0.8\textwidth]{images/functionaltopology.eps}}
\end{frame}

\begin{frame}{Functional Coherence in Networks}
\begin{itemize}
	\item Modularity manifests itself in terms of high connectivity in the network
	\item Functional association (similarity) is correlated with network proximity
%	\item Protein-protein interaction (PPI) networks are used extensively for functional inference
%	\item In PPI networks, functional coherence manifests itself in terms of network proximity
	\item A measure for annotation proximity of nodes (semantic similarity)
	\item A measure for network distance
\end{itemize}
\centerline{
	\includegraphics[width=0.35\textwidth]{images/funmod.eps}
	\hspace{0.1\textwidth}
	\includegraphics[width=0.35\textwidth]{images/funpro.eps}
}
\centerline{\small{Sharan \etal, {\em MSB}, 2007}}

\end{frame}

\section{Methods}

\begin{frame}{Assessing Functional Similarity}
\begin{columns}[c]
\column{0.5\textwidth}
\begin{itemize}
\item Gene Ontology (GO) provides a hierarchical taxonomy of biological process, molecular function and cellular component
\item Assessment of semantic similarity between concepts in a hierarchical taxonomy is well studied (Resnik, {\em IJCAI}, 1995)
\end{itemize}
\column{0.5\textwidth}
\centerline{\includegraphics[width=\textwidth]{images/go.eps}}
\end{columns}
\end{frame}

\begin{frame}{Semantic Similarity of GO Terms}
\begin{itemize}
\bigitem{Resnik's measure based on information content $I(c) = -\log_2(|G_c|/|G_r|)$
\begin{displaymath}
\delta_{I}(c_i, c_j) = \displaystyle\max_{c \in A_i \cap A_j} I(c)
\end{displaymath}
}
{\item$G_c$: Set of molecules that are associated with term $c$, $r$: Root term
\item $A_i$: Ancestors of term $c_i$ in the hierarchy
\item $\lambda(c_i, c_j)=\displaystyle\text{argmax}_{c \in A_i \cap A_j} I(c)$: Lowest common ancestor of $c_i$ and $c_j$
}
%\item {Normalize score:  
%$\delta_{JC}(c_i, c_j) = \frac{1}{1 - 2\delta_{I}(c_i, c_j) + I(c_i) + I(c_j)}$ (Jiang \& Conrath, {\em ICRCL}, 1997)}
\end{itemize}

\begin{columns}[c]
\column{0.3\textwidth}
\centerline{\includegraphics[height=\textwidth]{images/resnik.eps}}
\column{0.7\textwidth}
Resnik($c_3, c_4$) = Max(IC($c_1$), IC($c_2$)) \\
%JiangConrath($c_3, c_4$) = $\frac{1}{1 - 2*Resnik(c_3, c_4) + I(c_3) + I(c_4)}$ 
\end{columns}
\end{frame}

\begin{frame}{Functional Similarity of Molecules}
\begin{itemize}
\item Each molecule (protein or domain) is associated with multiple GO terms
%\item Available annotations are incomplete
%\item Domain annotations are often derived from protein annotations
%\item Is it possible to compare functional similarity between domains and functional similarity between proteins at all?
\item{Average (Lord \etal, {\em Bioinformatics}, 2003)
\begin{displaymath}
\rho_A(S_i, S_j) = \frac{1}{|S_i||S_j|}\displaystyle\sum_{c_k \in S_i} \displaystyle\sum_{c_l \in S_j} \delta(c_k, c_l)
\end{displaymath}}
\bigitem{Generalize the concept of lowest common ancestor to sets of terms (Pandey \etal, {\em ECCB}, 2008)
\begin{displaymath}
\Lambda(S_i, S_j) = \displaystyle\bigsqcup_{c_k\in S_i, c_l\in S_j}{\lambda(c_k,c_l)}
\end{displaymath}
\begin{displaymath}
\rho_I(S_i, S_j) = I(\Lambda(S_i, S_j)) = -\log_2\left(\frac{|G_{\Lambda(S_i, S_j)}|}{|G_r|}\right)
\end{displaymath}
}
{\item $G_{\Lambda(S_i, S_j)}=\displaystyle\bigcap_{c_k \in \Lambda(S_i, S_j)}{G_{c_k}}$
is the set of molecules that are associated with all terms in the MCA set}
\end{itemize}
\end{frame}

\begin{frame}{Functional Coherence of Module}
\begin{itemize}
\item A set of molecules that participates in the same biological processes or functions
\item sub-network with dense intra-connections and sparse interconnections
\item Each module is associated with set of molecular entities, and each molecule
associated with set of terms.
\end{itemize}
\begin{columns}[c]
\column{0.5\textwidth}
\begin{center}
  \includegraphics[width=0.6\linewidth]{images/sample_tree.eps}\\
  \vspace{0.02in}
  $S_1 = \{c_4\}$, $S_2 = \{c_4\}$, $S_3 = \{c_4, c_6\}$,\\ 
  $S_4 = \{c_1, c_6\}$, $S_5 = \{c_1\}$, $S_6 = \{c_6\}$
\end{center}
\column{0.5\textwidth}
Sets:
\begin{itemize}
\item $\mathcal{R}_1=\{S_1, S_2, S_3, S_4\}$
\item $\mathcal{R}_2=\{S_1, S_2, S_3\}$
\item $\mathcal{R}_3=\{S_3, S_4\}$
\end{itemize}
\end{columns}
\end{frame}

\begin{frame}{Existing Measure}
\begin{itemize}
\item{Average (Pu \etal, {\em Proteomics}, 2007)
\begin{displaymath}
\sigma_A(\mathcal{R}) = \displaystyle\frac{1}{n(n-1)/2}\displaystyle\sum_{1\leq i < j\leq n} \rho(S_i, S_j).
\end{displaymath}}
\item{
%Example: $\sigma_A(\{ c_4\}, \{ c_4\}, \{ c_4, c_6\}, \{ c_1, c_6\}) = $
Example: $\sigma_A(S_1, S_2, S_3, S_4) = $
\begin{displaymath}
\displaystyle\frac{1}{6}(3*\sigma_A(S_1, S_2, S_3) + \rho(S_3, S_4) +  \red{\rho(S_1, S_4)+ \rho(S_2, S_4)})
% $\rho(S_1, S_4) = \rho(S_2, S_4) = 0$
\end{displaymath}}
% \item N^2 comparisons!
\end{itemize}
\end{frame}

\begin{frame}{Generalized Information Content}
Extend the notion of the minimum common ancestor of pairs of terms to tuples of terms 
$\lambda(c_{i_1},\ldots, c_{i_n})=\textrm{argmax}_{c \in \cap_{k=1}^{n} A_{i_k}}{I(c)}$

\begin{displaymath}
\sigma_I(\mathcal{R}) = I(\Lambda(S_1, \ldots ,S_n))
= -\log_2\left(\frac{|G_{\Lambda(S_i, \ldots, S_j)}|}{|G_r|}\right).
\end{displaymath}
where
\begin{displaymath}
\Lambda(S_1, S_2, \ldots, S_n) = 
\displaystyle\bigsqcup_{c_{i_j}\in S_j, 1\leq j\leq n} 
{\lambda(c_{i_1},c_{i_2},\ldots,c_{i_n})}
\end{displaymath}
Example: $\sigma_I(S_1, S_2, S_3, S_4) = I(r) = 0$, no common ancestor!
\end{frame}

\begin{frame}{Weighted Information Content}
Weigh the information content of shared functionality by the number of molecules 
that contribute to the shared functionality 
\begin{displaymath}
\sigma_W(\mathcal{R}) = 1 - \displaystyle\frac{\displaystyle\sum_{1\leq i\leq n}{\sum_{c \in {\mathcal{A}'}_i}{I(c)}}}{\displaystyle\sum_{1\leq i\leq n}{ \sum_{c \in \mathcal{A}_i}{I(c)} }}
\end{displaymath}

\begin{columns}[c]
\column{0.5\textwidth}
$\sigma_W(S_1, S_2, S_3, S_4) = 0.86$
\begin{center}
  \includegraphics[width=0.6\linewidth]{images/tree2.eps}\\
\end{center}
\column{0.5\textwidth}
$\sigma_W(S_1, S_2, S_3) = 0.75$
\begin{center}
  \includegraphics[width=0.6\linewidth]{images/tree1.eps}\\
\end{center}
\end{columns}

\end{frame}


\begin{frame}{Accounting for Multiple Paths}
\begin{itemize}
\bigitem{Is "shortest path" a good measure of network proximity?}
{
	\item Multiple alternate paths might indicate stronger functional association
	\item In well-studied pathways, redundancy is shown to play an important role in robustness \& adaptation (\eg, genetic buffering)
}
\end{itemize}
\vspace{0.2in}
\centerline{\includegraphics[width=0.9\linewidth]{images/proximity.eps}}
\end{frame}

\begin{frame}{Random walks with restarts}
\begin{itemize}
\item Consider a random walker that starts on a source node {\em s}. At every tick,
the walker chooses randomly among available edges or goes back to node {\em s} with
probability {\em c}.
\end{itemize}
\vspace{0.2in}
\centerline{\includegraphics[width=0.6\linewidth]{images/rwr.eps}}
\end{frame}

\begin{frame}{Proximity Based On Random Walks}
\begin{itemize}
\item Simulate an infinite random walk with random restarts at protein $i$
\bigitem{Proximity between proteins $i$ and $j$ is given by the relative amount of time spent
at protein $j$
	\begin{displaymath}
	\Phi(0)=I,~\Phi(t+1) = (1-c) A \Phi(t) + c I,~ \Phi = \lim_{t\rightarrow \infty}{\Phi(t)}
	\end{displaymath}
}
{
	\item $\Phi(i,j)$: Network proximity between protein $i$ and protein $j$
	\item $A$: Stochastic matrix derived from the adjacency matrix of the network
	\item $I$: Identity matrix
	\item $c$: Restart probability
}
\item Define proximity between proteins $i$ and $j$ as $\{ \Phi(i,j) + \Phi(j,i) \}/2$
\end{itemize}
\end{frame}

\section{Results}

\begin{frame}{Network Proximity \& Functional Similarity}
\centerline{\includegraphics[width=0.75\linewidth]{images/proxcomp.eps}}
\centerline{\small{Correlation between functional similarity}}
\centerline{\small{and network proximity}}
\end{frame}


\begin{frame}{Topological Proximity and Functional Similarity}
\begin{columns}
\column{0.6\textwidth}
\centerline{\includegraphics[width=0.9\textwidth]{images/proxDistA.eps}}
\column{0.6\textwidth}
\centerline{\includegraphics[width=0.9\textwidth]{images/proxDistB.eps}}
\end{columns}
\vspace{0.5in}
Comparison of the DDI and PPI networks with respect to the relation 
between semantic similarity vs proximity and network distance
\end{frame}

\begin{frame}{Comparison of Coherence Meaures}
\centerline{\includegraphics[width=0.7\linewidth]{images/coherence.eps}}
\centerline{Index of Dectectability vs. complex sizes}
\vspace{0.2in}
\small{\centerline{
$d(\sigma) = \frac{{\textrm{mean}_{t\in T}(\sigma(t)) - \textrm{mean}_{t\in C}(\sigma(t))}}
{\sqrt{((\textrm{std}_{t\in T}(\sigma(t)))^2+(\textrm{std}_{t\in C}(\sigma(t)))^2)/2}}$}}
\end{frame}

\begin{frame}{Conclusion \& Ongoing work}
  \begin{itemize}
%  \bigitem{Summary}
%  {
	\item Random walk based measures of topological proximity are better suited to existing interaction data
	\item Measures that quantify coherence among entire sets are superior to aggregares of known pair-wise measures
%  }
  \item Future work : Using proximity measure to identify disease implicated genes in networks
%  \item
  \end{itemize}
\end{frame}

%\begin{frame}{Acknowledgments}
%
%\begin{itemize}
% \item \blue{Mehmet Koyut\"urk} (Case Western Reserve)
% \item \blue{Jayesh Pandey} (Purdue)
% \item \blue{Prof. Shankar Subramaniam} (UCSD)
%\end{itemize}
%
%\begin{itemize}
% \item NIH \& NSF
%\end{itemize}
%
%\end{frame}


\end{document}


