\documentclass{beamer}


% Setup appearance:

%\usetheme{Darmstadt}
%\usefonttheme[onlylarge]{structurebold}
%\setbeamerfont*{frametitle}{size=\normalsize,series=\bfseries}
%\setbeamertemplate{navigation symbols}{}
%

\mode<presentation>
{
  \usetheme{Warsaw}
%  \usecolortheme{lily}
  \usefonttheme[onlylarge]{structuresmallcapsserif}
  \usefonttheme[onlysmall]{structurebold}

  \setbeamertemplate{navigation symbols}{}
  \setbeamercovered{transparent}
}


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


\title[Functional Decomposition of Genetic Networks] % (optional, use only with long paper titles)
{Role of Synthetic Genetic Interactions in Understanding Functional Interactions Among Pathways}


\author[Mohammadi et al.] % (optional, use only with lots of authors)
{S. Mohammadi \and G. Kollias  \and A. Grama}

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

\date[PSB 2012] % (optional, should be abbreviation of conference name)
{The Pacific Symposium on Biocomputing, 2012}


\subject{Computational Biology}


\pgfdeclareimage[height=0.5cm]{university-logo}{figures/purdue}
\logo{\pgfuseimage{university-logo}}


\AtBeginSubsection[]
{
  \begin{frame}<beamer>{Outline}
    \tableofcontents[currentsection,currentsubsection]
  \end{frame}
}

%\beamerdefaultoverlayspecification{<+->}


\begin{document}

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

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

\section{Preliminary }
\subsection{Models and Definitions}
\begin{frame}{Genetic Interactome}

Double mutants exhibit unexpected phenotypes, as compared to joint single mutations.

\begin{definition}
\begin{itemize}
\item {\color{red} \textbf{Negative Interactions}}: more sever phenotype than expected
\begin{itemize}
\item Also known as \textit{aggravating} or \textit{synergistic}
\end{itemize}

\item {\color{green} \textbf{Positive Interactions}}: Less sever phenotype than expected
\begin{itemize}
\item Also known as \textit{alleviating} or \textit{epistatic}
\end{itemize}
\end{itemize}
\end{definition}

Most commonly used:
\begin{description}
\item [Phenotype]: Growth rate
\item[Model]: Multiplicative null model
\end{description}
\end{frame}



\begin{frame}{Organization of Genetic Interactions}

\begin{definition}
\begin{itemize}
\item \alert{Between-Pathway Model}
\begin{itemize}
\item Among genes participating in redundant functions
\end{itemize}
\item \alert{Within-Pathway Model}
\begin{itemize}
\item Among genes with additive effect
\end{itemize}
\item \alert{Indirect Effect}
\begin{itemize}
\item Among genes with distant functions that are not directly related
\end{itemize}
\end{itemize}
\end{definition}

\end{frame}


\begin{frame}{Between-Pathway Model (BPM)}

  \begin{columns}[c]
    \column{.4\textwidth}
	\includegraphics[scale=.25]{figures/BPM}	
	  
    \column{.6\textwidth}
		\begin{itemize}
		\item Bi-cliquish structure
		\item Have been used to:		
		\begin{enumerate}
			\item Predict co-pathway membership of gene pairs
			\item Extract redundant pathways
		\end{enumerate}
	\end{itemize}
  \end{columns}  

\end{frame}



\subsection{Datasets}
\begin{frame}{The Genetic Landscape of a Cell}
  \begin{columns}[c]
    \column{.5\textwidth}
	\includegraphics[width=\columnwidth,height=.8\textheight]{figures/Costanzo}\\
	\tiny{Adopted from Costanzo et al., 2010}
	  
    \column{.5\textwidth}
		\begin{itemize}
		\item Baker's yeast, \textit{Saccharomyces cerevisiae}
		\item Synthetic Genetic Array (SGA)
		\item 1712 query genes
			\begin{enumerate}
				\item 1378 null alleles of non-essential genes
				\item 334 hypomorphic or conditional alleles of essential genes
			\end{enumerate}
		\item 3885 array strains
	\end{itemize}
  \end{columns}  
\end{frame}



\begin{frame}{Functional Annotations}
  \begin{columns}[c]
    \column{.5\textwidth}
	\includegraphics[width=\columnwidth]{figures/KEGG}
		  
    \column{.5\textwidth}
		\begin{itemize}
			\item KEGG Pathway Database
			\item Annotations for 1026 genes in the experiment
			\item 96 Pathways
			\begin{itemize}
				\item 80 pathways after filtering pathways with less than 10 genes.			
			\end{itemize}
		\end{itemize}
  \end{columns}  
\end{frame}


\section{Motivation}
\subsection{Functional Similarity of Gene Pairs}

\begin{frame}{Local Neighborhood Similarity}{A Predictor of Co-Pathway Membership}
\begin{block}{Similarity prediction methods}
\begin{enumerate}
\item Number of Shared Neighbors
\item Congruence Score
\item Pearson Correlation of Interaction Profiles
\end{enumerate}
\end{block}


  \begin{columns}[t]
    \column{.45\textwidth}
	\includegraphics[width=\columnwidth]{figures/CS1}
	  
    \column{.35\textwidth}
	\includegraphics[width=\columnwidth]{figures/CS2}
  \end{columns}  
  

\tiny{Both $v_i$ and $v_j$ have three shared neighbors. However, in the first case their
congruence score is almost 0.6, while in the second case it is approximately 2
(assuming a graph of size 10).}

\end{frame}



\subsection{Performance Evaluation and Identifying Shortcomings}

\begin{frame}{Evaluating Ranking Methods}
Given a pathway \alert{$P_A$} and a cut size (target set) \alert{$l$}.

	\begin{definition}
		\begin{eqnarray*}
			P-value (X = k) &=& Prob(k\leq X) \nonumber \\
			&=&  HGT(k| N, N_A, l) \nonumber  \\
			&=& \sum_{x=k}^{min(N_A, l)} \frac{{C(l, x)} {C(N-l,N_A-x)}} {{C(N,N_A)}}
		\end{eqnarray*}
	\end{definition}

	\alert{$X$}: Random variable denoting the number of true positives in a random sample, \alert{$N$}: Total number of gene pairs, \alert{$N_A$}: Number of gene pairs in pathway $A$, \alert{$l$}: Size of target set
\end{frame}


\begin{frame} {Minimum HyperGeometric (mHG) Score}
Target size unknown:

\begin{definition}{	The \alert{Minimum HyperGeometric (mHG)} score}
\begin{equation*}
mHG(\lambda) = min_{1\leq l \leq N} HGT(b_l(\lambda); N, N_A, l),
\end{equation*}

where $b_l(\lambda) = \sum_{i=1}^l \lambda_i $

\end{definition}

 $\lambda_i$ is 1 if both of the genes in the $i^{th}$ ranked gene pair
are members of $P_A$, and 0 otherwise.

\begin{itemize}
\item mHG Adjusted for Multiple Comparison
\end{itemize}

\end{frame}

\begin{frame}{Predictions Are Not Equally Accurate in Different KEGG Pathways}
\includegraphics[width=.95\columnwidth] {figures/Complete_mHG_Bonferroni_01}

\end{frame}



\section{Constructing KEGG Crosstalk Map}
\subsection{Overview}
\begin{frame}{Highlights}

\begin{block}{Basic Idea}
  \begin{columns}[c]
    \column{.4\textwidth}
	Heterogeneous performance of co-pathway membership predictions		

    \column{.05\textwidth}
	$\Longleftrightarrow$
			  
    \column{.4\textwidth}
	Existence of specific structure around enriched pathways

  \end{columns}  
\end{block}

\begin{itemize}
\item Decomposing neighborhood of each pathway
\item Inferring lethal crosstalk among pathways
\end{itemize}

\end{frame}

\subsection{Methods}
\begin{frame}{Modified Congruence Score (MCS)} {Evaluating Neighborhood Overlap of
Gene Pairs With Respect to a Given Pathway}

\begin{definition}
\begin{eqnarray*}
P-value (X = k_{ij}^B) &=& Prob(k_{ij}^B\leq X)  \\
&=&  HGT(k_{ij}^B| n_B, d_i^B, d_j^B) \\
&=& \sum_{x=k_{ij}^B}^{\min(d_i^B, d_j^B)} \frac{C(d_j^B, x) C(n_B-d_j^B, d_i^B-x)}{C(n_B, d_i^B)}
\end{eqnarray*}
\end{definition}
MCS is defined as $-log_{10}$ of the P-value.

\end{frame}

\begin{frame}{Modified Congruence Score (MCS)} {continued}
\begin{example}
  \begin{columns}[c]
    \column{.45\textwidth}
	\includegraphics[width=\columnwidth,height=.5\textheight]{figures/MCS}
	  
    \column{.45\textwidth}
	A sample neighborhood configuration for $v_i$ and $v_j$. Here $n = 15, D_i = 6, D_j = 5, n_B = 6, d_i = 3, d_j = 4$ and $k = 2$.
  \end{columns}  
\end{example}

\end{frame}


\begin{frame}{Constructing Neighborhood Overlap Graph \\ For a Given Pathway Pair}
\begin{definition}
The neighborhood overlap graph (NOG) of a given pathway $P_A$ with respect to
pathway $P_B$, denoted by $H_{A\rightarrow B} = (V_H, E_H)$, is an unweighted,
undirected graph defined over same vertices as $P_A$. In this graph, there is a
link between vertices $v_i$ and $v_j$ if the network structure around them
with respect to $P_B$ is statistically significant .
\end{definition}
\end{frame}

\begin{frame}{Pruning neighborhood overlap graph, finding cohesive subgraphs,
and identifying interaction ports}


  \begin{columns}[c]
    \column{.5\textwidth}
	\includegraphics[width=\columnwidth]{figures/KCore}\\
	\tiny{	Adopted from Batagelj and Zaversnik, 2002}		  
    \column{.5\textwidth}
    \begin{enumerate}
		\item Iterative peeling of K-shells\\Pruning hairy components
		\item Connected components in each core
		\item Evaluating the significance of components
			\begin{itemize}
				\item Evaluating significance using ER random graph model
			\end{itemize}		
	\end{enumerate}
  \end{columns}  
  
  
\end{frame}


\subsection{Results and Discussions}
\begin{frame}{KEGG Crosstalk Map}
  \begin{columns}[c]
    \column{.6\textwidth}
	\includegraphics[width=\columnwidth, height=.8\textheight]{figures/KEGG_final}
	  
    \column{.4\textwidth}
	\includegraphics[width=\columnwidth]{figures/Thresholding}
  \end{columns}  
\end{frame}



\begin{frame}{Interaction Port Case Study} {Crosstalk Between Protein Processing in ER and Proteasome}

 \begin{columns}[t]
    \column{.9\textwidth}
     \includegraphics[width=\textwidth]{figures/ProtER}
	  
  \end{columns}  
  

\end{frame}


\section*{Summary}

\begin{frame}{Summary}

  % Keep the summary *very short*.
  \begin{itemize}
  \item
    The \alert{local neghborhood similarity} gives heterogeneous performance in predicting co-pathways membership of gene pairs.
  \item
    This phenomena is due to the specific structure around enriched pathways
  \item
	\alert{Decomposing the neighborhood} around each pathway sheds light on the cellular machinery.
  \end{itemize}
  
  % The following outlook is optional.
  \vskip0pt plus.5fill
  \begin{itemize}
  \item
    Future works:
    \begin{itemize}
    \item
      Analysing the hierarchy of ports instead of the most significant interaction port.
    \item
		Using our methodology to uncover dependencies among functional pathways.
    \end{itemize}
  \end{itemize}
\end{frame}



\appendix
\section<presentation>*{\appendixname}
\subsection<presentation>*{For Further Reading}

\begin{frame}[allowframebreaks]
  \frametitle<presentation>{For Further Reading}
    
  \begin{thebibliography}{10}
    
%  \beamertemplatebookbibitems
 
  \beamertemplatearticlebibitems
  \bibitem{Costanzo}
    M.~Costanzo et al.
    \newblock The Genetic Landscape of a Cell
    \newblock {\em Science}, 425
    2010.

  \bibitem{Dixon}
	SJ.~Dixon et al.
    \newblock Systematic Mapping of Genetic Interaction Networks
    \newblock {\em Annual review of genetics}, 43, 601
    2009.

  \bibitem{Segre}
	D.~Segre et al.
    \newblock Modular Epistasis in Yeast Metabolism
    \newblock {\em Nature Genetics}, 37, 77
    2005.

  \bibitem{Tucker}
	C.L.~Tucker and S.~Fields
    \newblock Lethal Combinations
    \newblock {\em Nature Genetics}, 35, 204
    2003.
        
%  \bibitem{CS}
%	P.~Ye et al.
%    \newblock Gene function prediction from congruent synthetic lethal interactions in yeast
%    \newblock {\em Molecular Systems Biology }, 1, msb4100034
%    2005.


  \end{thebibliography}
\end{frame}

\end{document}


