\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[] % (optional, use only with long paper titles)
{Functional Characterization of\\ Biological Networks}

\author[] % (optional, use only with lots of authors)
{Jayesh Pandey}

\institute[Purdue University] % (optional, but mostly needed)
{Department of Computer Science}

\date[] % (optional, should be abbreviation of conference name)
{December 3, 2009}

\subject{Bioinformatics}

\pgfdeclareimage[height=0.5cm]{university-logo}{./images/pulogo.PNG}
\logo{\pgfuseimage{university-logo}}


% Delete this, if you do not want the table of contents to pop up at
% the beginning of each subsection:
\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 Interactions}
\begin{itemize}
\bigitem{Regulation of molecular activity}
{
\item Transcriptional regulation: Which genes will be expressed?
\item Post-transcriptional regulation \& signaling: Phosphorylation, degradation, transport...
}  
\bigitem{Protein-protein interactions}
{
\item High-throughput screening: Yeast Two-Hybrid, Affinity Purification
\item Noisy \& incomplete
\item Nature, context, direction not known at a large scale
\item Small scale experiments are more reliable and informative
}
\end{itemize}
\end{frame}

\begin{frame}{Modeling Molecular Interactions: Networks}
\begin{columns}
\column{0.6\textwidth}
\begin{itemize}
  \item High level description of cellular organization
  \bigitem{Nodes represent cellular components}
  {
  	\item Protein, gene, enzyme, metabolite
  }
  \bigitem{Edges represent interactions}
  {
    \item Binding, regulation, modification, complex membership, substrate-product relationship
  }
\end{itemize}
\column{0.45\textwidth}
\centerline{\includegraphics[width=0.5\textwidth]{images/b_sub_grn.png}}
\centerline{\scriptsize{\hspace{0.2in} {\em B.subtilis GRN}}}
\vspace{0.3in}
\centerline{\includegraphics[width=0.5\textwidth]{images/s_pombe_ppi.png}}
\centerline{\scriptsize{\hspace{0.2in} {\em S.pombe PPI}}}
\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.pdf}}
\end{frame}

\begin{frame}{In this Talk}
\begin{itemize}
\bigitem{Recurrent functional interaction patterns}
{
\item Crosstalk between different processes
\item "Periodic table of systems biology"
}
\bigitem{Functional coherence with respect to different types of interaction}
{
\item What does proximity mean in domain-domain interaction networks?
\item Assessing functional similarity between two molecules
\item Development of incompleteness-aware approaches
}
\end{itemize}
\end{frame}


\section{Annotation Patterns}

\begin{frame}{Molecular Annotation}
\begin{columns}[c]
\column{0.6\textwidth}
\begin{itemize}
\bigitem{Significant progress on standardizing knowledge
on biological function at the molecular level}
{
\item Protein/domain families (COG, PFAM, ADDA)
}
\item{\blue{Molecular annotation} provides a unified understanding of the underlying principles}
\bigitem{Gene Ontology}
{\item A controlled vocabulary of molecular functions, biological processes, and cellular components}
\end{itemize}
\column{0.45\textwidth}
\centerline{\includegraphics[width=0.8\textwidth]{images/go1.pdf}}
\end{columns}
\end{frame}

\begin{frame}{From Molecules to Systems}
  \begin{itemize}
    \item Networks are \red{species-specific}
	\item Annotations are described at the molecular level
	\item Map networks from gene space to an abstract function space
  \end{itemize}
  \begin{figure}[t]
	\begin{center}
		\begin{minipage}[t]{0.53\linewidth}
			\includegraphics[width=\linewidth]{images/grnScience.png}
		\end{minipage}\hfill
		\begin{minipage}[b]{0.43\linewidth}
			Network of GO terms based on \green{significance} of 
			pairwise interactions in S. cerevisiae Synthetic Gene 
			Array (SGA) network \blue{(Tong et al., Science, 2004)}
		\vspace{0.3in}
		\end{minipage}
	\end{center}
	\vspace{0.15in}
  \end{figure}
  
\end{frame}

\begin{frame}{Indirect Regulation}
  \begin{itemize}
    \item Assessment of pairwise interactions is \green{simple}, but \red{not adequate} 
  \end{itemize}
  \centerline{
	\includegraphics[width=0.4\textwidth]{images/indirect1.png}
	\hspace{0.05\textwidth}
	\includegraphics[width=0.4\textwidth]{images/indirect2.png}
  }
\end{frame}


\begin{frame}{Functional Attribute Network}
  \begin{itemize}
	\item Multigraph model
	\begin{itemize}
	  \item A gene is associated with \green{multiple} functional attributes
	  \item A functional attribute is associated with \green{multiple} genes
	  \item Functional attributes are represented by nodes
	  \item Genes are represented by ports, reflecting \red{context}
	\end{itemize}
  \end{itemize}
  \vspace{0.2in}
  \centerline{\includegraphics[width=0.8\textwidth]{images/fan.png}}
  \centerline{\hspace{0.1\textwidth}\footnotesize{Gene Network}\hspace{0.2\textwidth}\footnotesize{Functional Attribute Network}}

\end{frame}

\begin{frame}{Frequency of a Multipath}
  \begin{itemize}
	\item A \green{pathway of functional attributes} occurs in various contexts in the gene network 
	\begin{itemize}
	  \item \blue{Multipath} in the functional attribute network
	\end{itemize}
  \end{itemize}
  \vspace{0.2in}
  \centerline{\includegraphics[width=0.8\textwidth]{images/freq1.png}}
  \vspace{0.2in}
  \centerline{\hspace{0.1\textwidth}Frequency of Multipath \hspace{0.02\textwidth}
      \includegraphics[width=0.4\textwidth]{images/freq2.png} \hspace{0.01\textwidth}?}
\end{frame}

\begin{frame}{Frequency {\em vs.} Statistical Significance}
 \begin{itemize}
	\item We want to identify patterns with \green{unusual frequency}
	\begin{itemize}
	  \item These might correspond to \blue{modular pathways}
	\end{itemize}
	\item Frequency alone is not a good measure of statistical significance
	\begin{itemize}
	  \item The distribution of functional attributes among genes is not uniform
	  \item The degree distribution in the network is highly skewed
	  \item Pathways that contain \blue{common} functional attributes have \green{high frequency}, but they are \red{not necessarily interesting}
	\end{itemize}
  \end{itemize}

\end{frame}

\begin{frame}{Statistical Significance of a Pattern}
  \begin{itemize}
    \item Emphasize modularity of pattern (Pandey \etal, {\em ISMB}, 2007)
        \begin{itemize}
          \item Condition on frequency of building blocks
          \item Evaluate the significance of the coupling of building blocks
        \end{itemize}
  \end{itemize}
  \centerline{\includegraphics[width=0.8\textwidth]{images/insight.png}}
\end{frame}

\begin{frame}{Significance of a Pattern}
  \begin{itemize}
    \item We denote each frequency random variable by $\phi$, their observed value by $\varphi$
	\centerline{\includegraphics[width=0.5\textwidth]{images/formulate.png}}
	\item Significance of pattern $\pi_{123}$ ( $p_{123}$ ) is defined as\\
	\small{$P(\phi_{123} \geq \varphi_{123} | \phi_{12}=\varphi_{12},\phi_{23}=\varphi_{23}, \phi_{1}=\varphi_{1},\phi_{2}=\varphi_{2},\phi_{3}=\varphi_{3}) $}
  \end{itemize}
\end{frame}

\begin{frame}{Computing Significance}
\begin{itemize}
    \item Assume that interactions are \green{independent}
	\begin{itemize}
		\item There are $\varphi_{12}\varphi_{23}$ possible pairs of $\pi_{12}$ and $\pi_{23}$ edges
		\item The probability that a pair of $\pi_{12}$ and $\pi_{23}$ edges go through the same gene (corresponds to an occurrence of $\pi_{123}$) is $1/{\varphi_{2}}$
	\end{itemize}
	\item The probability that at least $\varphi_{123}$ of these pairs go through the same gene can be bounded by
	\begin{itemize}
		\item \small{$p_{123} \leq exp(\varphi_{12}\varphi_{23}H_{q}(t))$ where $q=1/\varphi_{2}$ and $t=\varphi_{123}/\varphi_{12}\varphi_{23}$}
		\item \small{$H_{q}(t) = t\log(q/t)+(1-t)\log((1-q)/(1-t))$ is divergence}
		\item \small{Bonferroni-corrected for multiple testing (adjusted by \scriptsize{$\prod_{j=1}^{k}{|\cup_{g_{\ell} \in T_{i_j}}{\mathcal{F}(g_{\ell})}|}$})}
	\end{itemize}
%	\item For a single interaction, we use a background model that assumes arbitrary degree distribution
	
  \end{itemize}
\end{frame}

\begin{frame}{Algorithmic issues}
  \begin{itemize}
	\bigitem{Significance is \red{not monotonic} with respect to size}
	{\item Need to \blue{enumerate} all pathways?}
	\bigitem{\green{Strongly significant} patterns}
	{\item A pathway is strongly significant if all of its building blocks and their coupling are significant (defined \blue{recursively})
	\item Allows \blue{pruning out} the search space effectively}
	\bigitem{\green{Shortcircuiting} \red{common} functional attributes}
	{\item Transcription factors, DNA binding genes, etc. are responsible for mediating regulation
	\item Shortcircuit these terms, consider regulatory effect of different processes on each other \blue{directly}}
  \end{itemize}
\end{frame}

\begin{frame}{{\sc Narada}}
  \begin{itemize}
    \bigitem{A software for identification of significant pathways (Pandey \etal, {\em PSB}, 2008)}
        {\item Given functional attribute $T$, find all significant pathways that originate (terminate) at $T$
        \item User can explore back and forth between the gene network and the functional attribute network}
  \end{itemize}
  \centerline{\includegraphics[width=2.5in]{images/screenshot.png}}
\end{frame}

\begin{frame}{An Example: Molybdate Ion Transport}
  \vspace{0.1in}
  \centerline{\includegraphics[width=0.6\textwidth]{images/casestudy1.pdf}}
   \begin{itemize}
    \item modE regulates various processes directly
    \bigitem{It regulates various other processes indirectly}
        { \item Regulation of these mediator processes is not significant on itself
        \item {\sc Narada} captures modularity of indirect regulation!}
  \end{itemize}
\end{frame}

\begin{frame}{An Example: Molybdate Ion Transport}
  \vspace{0.1in}
  \centerline{\includegraphics[width=0.6\textwidth]{images/casestudy2.pdf}}
  \begin{itemize}
    \item modE regulates various processes directly
    \bigitem{It regulates various other processes indirectly}
        { \item Regulation of these mediator processes is not significant on itself
        \item {\sc Narada} captures modularity of indirect regulation!}
  \end{itemize}
\end{frame}

%\begin{frame}{What is significant?}
%  \begin{itemize}
%    \bigitem{\green{Molybdate ion transport} regulates various processes \blue{directly}}
%	{\item Mo-molybdopterin cofactor biosynthesis, oligopeptide transport, cytochrome complex assembly}
%	\bigitem{It regulates various other processes \blue{indirectly}}
%	{\item Through DNA-dependent regulation of transcription, two-component signal transduction system, nitrate assimilation
%	\item \red{Regulation of these mediator processes is not significant on itself!}
%	\item NARADA captures \green{modularity} of indirect regulation!}
%  \end{itemize}
%\end{frame}

\begin{frame}{Functional View of {\em E. coli} Regulatory Network}
  \centerline{\includegraphics[width=0.8\textwidth]{images/ecoli_global.pdf}}
\end{frame}

\begin{frame}{Short-Circuiting Mediator Processes}
  \centerline{\includegraphics[width=0.8\textwidth]{images/ecoli_shortcircuit.pdf}}
\end{frame}

\begin{frame}{Significant Patterns in Bacteria}
\begin{itemize}
  \bigitem{We use {\sc Narada} to identify significant patterns in the transcriptional networks of two bacterial species}
  {
	\item {\em E. coli}: 1502 genes, 3586 regulatory interactions (RegulonDB)	
    \item {\em B. subtilis}: 996 genes, 1381 regulatory interactions (DBTBS)
  }
\end{itemize}

\small{
  \centerline{Significant patterns ($p < 0.01$) }
  \begin{table}[t]
  \begin{center}
  \begin{tabular}{| c | c c | c c | }\hline
	Patterns	& B. subtilis	& E. coli	& BS in EC	& EC in BS 	\\\hline
	linear path	& 34 	        & 308      	& 0        	& 0	    	\\
	feedback   	& 27 	        & 114      	& 25       	& 25    	\\
	feedforward	& 77 	        & 659      	& 77 	  	& 86 	 	\\
	sink hub   	& 18 	        & 344      	& 18       	& 18    	\\
	source hub 	& 4907 	        & 8331     	& 4270     	& 4815    	\\\hline
  \end{tabular}
  \end{center}
  \end{table}
}
\end{frame}

\begin{frame}{Domain Annotation Patterns}
\begin{columns}
\column{0.5\textwidth}
\centerline{\includegraphics[width=0.95\textwidth]{images/ResultA.png}}
\centerline{\scriptsize{\hspace{0.2in} {\em B. subtilis GRN}}}
\column{0.5\textwidth}
\centerline{\includegraphics[width=0.95\textwidth]{images/ResultsD.png}}
\centerline{\scriptsize{\hspace{0.2in} {\em D. mela. PPI } \& {\em S. cere. PPI }}}
\end{columns}
\end{frame}


\section{Functional Coherence \& Network Proximity}

\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
	\bigitem{In PPI networks, functional coherence manifests itself in terms of network proximity}
	{\item How about DDI "networks"?}
\end{itemize}
\centerline{
	\includegraphics[width=0.35\textwidth]{images/funmod.png}
	\hspace{0.1\textwidth}
	\includegraphics[width=0.35\textwidth]{images/funpro.pdf}
}
\centerline{\small{Sharan \etal, {\em MSB}, 2007}}
\end{frame}

\begin{frame}{Domain-Domain Interactions}
\begin{itemize}
	\item Most proteins are composed of multiple domains
	\item Many domains are independent units reused in several related proteins
	\item Interactions between domains underlie observed protein-protein interactions
	\item Inferred by experimental and computational techniques
\end{itemize}
\centerline{\includegraphics[width=0.5\textwidth]{images/ddi.png}}
\end{frame}

\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/gene_ontology.png}}
\end{columns}
\end{frame}

\begin{frame}{Semantic Similarity of GO Terms}
\begin{itemize}
\bigitem{Resnik's measure based on information content:
\begin{displaymath}
I(c) = -\log_2(|G_c|/|G_r|)
\end{displaymath}
\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$
\item $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$
}
\end{itemize}
\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?
\end{itemize}
\end{frame}


\begin{frame}{Properties of Admissible Measures}
What are the basic required properties of an admissible measure of
similarity between two sets?
\vspace{0.2in}
\begin{enumerate}
\item Symmetry: $\rho(S_i, S_j) = \rho(S_j, S_i)$ for all $S_i, S_j$
\item Consistency: $\rho(S_i, S_j) \leq \rho(S_j, S_j)$ for all $S_i, S_j$
\item Monotonicity: $\rho(S_i, S_j) \leq \rho(S_i \cup c_k, S_j \cup c_k)$ 
\item{Generality: $\rho(S_i, S_j) \leq \rho(S_i, S_j \cup S_k)$ for all $S_i, S_j, S_k$
\begin{itemize}
\item Incompleteness-aware measures: No conclusions based on negative evidence!
\end{itemize}
}
\end{enumerate}
\end{frame}

\begin{frame}{Illustration of Properties}
\begin{columns}[c]
\column{0.5\textwidth}
\begin{center}
  	\includegraphics[width=0.6\linewidth]{images/sample_tree.pdf}\\
  \vspace{0.02in}
  $S_1 = \{c_4\}$, $S_2 = \{c_7\}$\\$S_3 = \{c_6\}$, $S_4 = \{c_4, c_6\}$\\
  $S_5 = \{c_6, c_7\}$
\end{center}
\column{0.5\textwidth}
\begin{itemize}
\item Monotonicity:\\ $\rho(S_1, S_2) \leq \rho(S_4, S_5)$
\item Generality:\\ $\rho(S_2, S_3) \leq \rho(S_2,S_4)$
\end{itemize}
\end{columns}
\end{frame}

\begin{frame}{Existing Measures are not Admissible}
\begin{itemize}
\bigitem{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}}
{\item Fails consistency, monotonicity, generality}
\bigitem{Maximum (Sevilla \etal, {\em IEEE TCBB}, 2005)
\begin{displaymath}
\rho_M(S_i, S_j) = \displaystyle\max_{c_k \in S_i, c_l \in S_j} \delta(c_k, c_l)
\end{displaymath}}
{
\item Principle: Similarity in a single pair of terms is sufficient
\item Fails monotonicity}
\end{itemize}
\end{frame}

\begin{frame}{Existing Measures are not Admissible}
\begin{itemize}
\bigitem{Average of Maxima (Schlicker \etal, {\em Bioinformatics}, 2007)
\begin{small}
\begin{displaymath}
\rho_H(S_i, S_j) = \max\left\{\displaystyle\frac{1}{|S_i|}\displaystyle\sum_{c_k \in S_i} \displaystyle\max_{c_l \in S_j}{\delta(c_k, c_l)},
\displaystyle\frac{1}{|S_j|}\displaystyle\sum_{c_l \in S_j} \displaystyle\max_{c_k \in S_i}{\delta(c_k, c_l)}\right\}
\end{displaymath}
\end{small}
}
{\item Principle: Similarity with a single term is sufficient for each term
\item Fails consistency, monotonicity, generality}
\end{itemize}
\end{frame}

\begin{frame}{Information Content Based Set Similarity}
\begin{itemize}
\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}{Illustration of Information Content Based Measure}
\begin{columns}[c]
\column{0.5\textwidth}
\begin{center}
  	\includegraphics[width=0.7\linewidth]{images/sample_tree.pdf}\\
  \vspace{0.02in}
  $S_1 = \{c_4, c_6, c_7\}$\\$S_2 = \{c_4\}$\\$S_3 = \{c_4, c_6\}$\\
  $S_4 = \{c_6, c_7\}$\\$S_5 = \{c_4, c_3\}$
\end{center}
\column{0.5\textwidth}
\begin{itemize}
\item $\lambda(c_4, c_4) = c_4$,\\ $\lambda(c_6, c_4)=\lambda(c_7, c_4)=R$
\item $\Lambda(S_1, S_2)=\{c_4\}$ $\Rightarrow$ $\rho_I(S_1, S_2)=-\log_2(|G_{c_4}|/|G_R|)=\log_2(5/4)$
\item $\Lambda(S_1, S_3)=\{c_4, c_6\}$ $\Rightarrow$ $\rho_I(S_1, S_3)=\log_2(5/2)$
\end{itemize}
\end{columns}
\end{frame}

\begin{frame}{Information Content Based Measure Is Admissible}
\begin{enumerate}
{
\color{gray}
%\begin{scriptsize}
\item
	Symmetry: Trivially, $\rho_I(S_i, S_j) = \rho_I(S_j, S_i)$ for all $S_i, S_j$.
\item
	Consistency: Clearly, $c_k \preceq \lambda(c_k, c_l)$ for any $c_k, c_l$. Now consider
	any $c_m \in \Lambda(S_i, S_j)$. Since $c_m = \lambda(c_k, c_l)$ for some $c_k \in S_i$ and
	$c_l \in S_j$, there always exists $c_n \in \Lambda(S_i, S_i)$ such that $c_n \preceq c_k \preceq c_m$.
	Consequently, we must have $G_{\Lambda(S_i, S_i)} \subseteq G_{\Lambda(S_i, S_j)}$, leading to
	$\rho_I(S_i, S_j) \leq \rho_I(S_i, S_i)$.
\item
	Monotonicity: Since $c_k \nsim c_n$ for all $c_n \in S_i \cup S_j$, we have
    $\Lambda(S_i \cup c_k, S_j \cup c_k) = \Lambda(S_i, S_j) \sqcup \Lambda(S_i \sqcup S_j, \{c_k\}) \sqcup \{c_k\}
    \supseteq \Lambda(S_i, S_j) \cup \{c_k\}$, leading to
    $G_{\Lambda(S_i \cup c_k, S_j \cup c_k)} \subseteq G_{\Lambda(S_i, S_j)}$ and
    $|G_{\Lambda(S_i \cup c_k, S_j \cup c_k)}| \leq |G_{\Lambda(S_i, S_j)}|$. Consequently,
    $\rho_I(S_i \cup c_k, S_j \cup c_k)\geq \rho_I(S_i, S_j)$.
\item
	Generality: $\Lambda(S_i, S_j\cup S_k) = \Lambda(S_i, S_j) \sqcup \Lambda(S_i, S_k) \sqsupseteq \Lambda(S_i, S_j)$.
	Therefore, $G_{\Lambda(S_i, S_j \cup S_k)} \subseteq G_{\Lambda(S_i, S_j)}$, leading to
	$\rho_I(S_i, S_j \cup S_k) \geq \rho_I(S_i, S_j)$.
%\end{scriptsize}
}
\end{enumerate}
\end{frame}

\begin{frame}{Functional Coherence of Module}
Each module is associated with set of molecular entities, and each molecule
associated with set of terms.
\begin{columns}[c]
\column{0.5\textwidth}
\begin{center}
  \includegraphics[width=0.6\linewidth]{images/sample_tree.pdf}\\
  \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(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)})
\end{displaymath}}
\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 
(Pandey \etal, {\em APBC}, 2010)
$\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$
\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.png}\\
\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.png}\\
\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.pdf}}
\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
}
\end{itemize}
\end{frame}

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

\end{frame}

\begin{frame}{Comparison of Similarity Measures}
\centerline{\includegraphics[width=0.9\linewidth]{images/semA.pdf}}
\centerline{Network distance {\em vs.} functional similarity on {\em C. elegans} PPI network}
\end{frame}

\begin{frame}{Comparison of Similarity Measures}
\centerline{\includegraphics[width=0.9\linewidth]{images/semB.pdf}}
\centerline{Distribution of functional similarity scores for structurally inferred DDIs}
\end{frame}

\begin{frame}{Comparison of PPI and DDI Networks}
\centerline{\includegraphics[width=0.9\linewidth]{images/mfN.pdf}}
\centerline{Network distance {\em vs.} functional similarity based on molecular functions}
\end{frame}

\begin{frame}{Comparison of PPI and DDI Networks}
\centerline{\includegraphics[width=0.9\linewidth]{images/bpN.pdf}}
\centerline{Network distance {\em vs.} functional similarity based on biological processes}
\end{frame}

\begin{frame}{Comparison of Coherence Meaures}
\centerline{\includegraphics[width=0.9\linewidth]{images/Figure4.pdf}}
\centerline{Index of Dectectability vs. complex sizes}
\end{frame}

\section{Conclusions \& Avenues for Future Research}

\begin{frame}{Conclusions \& Avenues for Future Research}
  \begin{itemize}
  \item Computational tools to analyze biological networks in context of 
		functions of individual bio-molecules
  \bigitem{Conclusions}
  {
	\item Patterns describe essential mechanisms in biological systems
	\item Coherence and proximity measures suitable to work with noisy and incomplete data
  }
  \bigitem{Avenues for Future Research}
  {	
   	\item Pattern-based protein function prediction
   	\item Phylogenetic analysis of identified patterns
   	\item Using proximity measure to find disease implicated genes
  }
  \end{itemize}  
\end{frame}

\begin{frame}{Thanks...}
\begin{itemize}
\bigitem{For their guidance and support}
{
	\item \blue{Ananth Grama}
	\item \blue{Mehmet Koyuturk} (CWRU)
}

\bigitem{For constructive feedback}
{
	\item \blue{Wojciech Szpankowski}
	\item \blue{Shankar Subramaniam} of UCSD
	\item \blue{Daisuke Kihara}
	\item \blue{Alex Pothen}
}

\bigitem{For productive and intriguing discussions}
{
	\item Members of \red{Parallel \& Distributed Systems Lab}
}
\end{itemize}
\end{frame}

\end{document}

