\documentclass[english]{beamer}
%\usetheme{Warsaw}


% Setup appearance:
\usetheme{Boadilla}
\usecolortheme{purdue}
\setbeamercovered{transparent}
\usefonttheme[onlylarge]{structurebold}
\setbeamerfont*{frametitle}{size=\normalsize,series=\bfseries}
\setbeamertemplate{navigation symbols}{}


\usepackage{amstext,amsmath,amssymb,amsfonts}
\usepackage{algorithmic,algorithm}
\usepackage{mathtools,cuted}
\usepackage{subfigure}
\usepackage{url}
\usepackage{listings}


\usepackage{enumitem}
\setenumerate[1]{label=\protect\usebeamerfont{enumerate item}%
        \protect\usebeamercolor[fg]{enumerate item}%
        \insertenumlabel.}
\setitemize{label=\usebeamerfont*{itemize item}%
  \usebeamercolor[fg]{itemize item}
  \usebeamertemplate{itemize item}}        



\DeclareMathOperator*{\argmin}{\arg\!\min}
\DeclareMathOperator*{\argmax}{\arg\!\max}
\newcommand{\bs}[1]{\boldsymbol{#1}}

\newcommand{\Vector}[1]{\bs{#1}}
\DeclareMathAlphabet\mathbfcal{OMS}{cmsy}{b}{n}
\newcommand{\Matrix}[1]{\mathbf{#1}}
\newcommand{\Tensor}[1]{\mathbf{\mathcal{#1}}}

\newcommand{\Graph}[1]{\mathit{\mathbf{\bs{#1}}}}
\newcommand{\Set}[1]{\mathit{#1}}


\newcommand{\R}{\mathbb{R}}
\newcommand{\diag}{\boldsymbol{diag}}

\newcommand{\Loss}{\bs{\mathcal{L}}}
\newcommand{\Reg}{\bs{\mathcal{R}}}

\renewcommand{\algorithmicrequire}{\textbf{Input:}}
\renewcommand{\algorithmicensure}{\textbf{Output:}}

\title[Tissue-specific interactomes] % (optional, use only with long paper titles)
{A Convex Optimization Approach for Identification of Human Tissue-specific Interactomes}




\author[S. Mohammadi and A. Grama] % (optional, use only with lots of authors)
{Shahin Mohammadi and Ananth Grama}

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

\date[ISMB] % (optional, should be abbreviation of conference name)
{July, 2016}



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

\begin{frame}{Thanks}
Travel funding to ISMB/ECCB 2016 was generously provided by ISCB

\begin{center}
\textbf{Thank you!}
\end{center}
\end{frame}

\section{Background}
\begin{frame}{Motivation}
Global human interactome is a superset of all \alert{possible} physical interactions that can take places in the cell. It does not provide any information as to which one of these interactions do take place in a given \alert{tissue/cell-type context}.
\end{frame}

\subsection{Problem statement}
\begin{frame}{What we have -- What we want}
Available data sources:
\begin{enumerate}
\item A global interactome, which contains the set of \textit{possible} interacting pairs.
\item A tissue-specific measurement of gene/protein activity within each tissue/cell type.
\end{enumerate} 


\begin{block}{Problem}
How can we optimally utilize transcriptional activity of gene products to construct the most informative tissue-specific sub-network?
\end{block}
\end{frame}


\subsection{Previous work}
\begin{frame}{Overview}

\begin{definition}
	\begin{enumerate}
		\item \alert{Node Removal (NR): } Tissue-specific network is generated by removing from the global network proteins that are not expressed in the relevant tissue.
		\item \alert{Edge Reweight (ERW): } It modify the edge weights to reflect the probability that the corresponding interactions take place in the specific tissue.	
		\begin{equation*}
		w_{ij}' = w_{ij}*\alpha^k
		\end{equation*}
		where $0 \leq \alpha \leq 1$ is the re-weighting factor and $k \in \{0, 1, 2\}$ is the number of end-points for the protein-protein interaction that are expressed in the tissue of interest.
	\end{enumerate}

\end{definition}
\end{frame}


\begin{frame}{Problems with Previous Methods}
\begin{itemize}
\item Rely on an ad hoc threshold for identifying expressed genes.
\item Utilize only local topology around each edge, specifically its end-points, to decide about existence/probability of an interaction.
\end{itemize}
\end{frame}

\subsection{Example}
\begin{frame}{Example subnetwork}

\begin{figure}
\includegraphics[width=.80\columnwidth]{figures/ActPro/AgPresenting}
\caption{Example of an upregulated pathway in blood cells-- Antigen processing and presentation}
\end{figure}

\end{frame}




\section{Activity Propagation (ActPro)}
\subsection{Standardizing gene expression profiles}
\begin{frame}{Universal exPression Codes (UPC)}{Computing transcriptional activity of genes}
  \begin{columns}[c]   
    \column{.55\textwidth}
		\begin{itemize}\small
		\item Processes each sample individually
		\item Corrects for platform-specific background noise
		\item Uses a mixture model to estimate whether a gene transcriptional activity
		\item Has been demonstrated that, for tissue samples profiled using both microarrays and RNA-Seq, UPC values can be highly concordant
		\end{itemize}
    \column{.45\textwidth}
    \begin{center}
		\includegraphics[width=\columnwidth]{figures/ActPro/Blood-Liver-Testis}\\
	    \tiny Distribution of transcriptional activities in three tissues with low, medium, and high number of expressed genes
    \end{center}	
	\end{columns}
\end{frame}


\begin{frame}{Universal exPression Codes (UPC)}{Validating tissue-specific markers}
    \begin{center}
		\includegraphics[height=0.75\textheight]{figures/ActPro/markers_comparison}\\
	    \tiny GO enrichment for tissues with high, medium, and low number of markers
    \end{center}	
\end{frame}

\subsection{Computing functional activity of genes}
\begin{frame}{Optimization problem}{Inferring functional activity of genes}
Minimal number of changes that smooths transcriptional activities over adjacent nodes in the network:

\begin{alignat*}{2}
\Vector{x}^* = \argmin_{\Vector{x}} &\bigg\{ (1-\alpha) \Vector{x}\Matrix{L}\Vector{x} +  \alpha \parallel \Vector{x} - \Vector{z}  \parallel_1\bigg\}\nonumber\\
\mbox{Subject to:} & \begin{cases}
	\Vector{1}^{T}\Vector{x} = 1&\\
	0 \leq \Vector{x}
\end{cases}
\end{alignat*}
\begin{itemize}
\item Vector $\Vector{z}$ initial value of transcriptional activities estimated by UPC
\item Matrix $\Matrix{L}$ is the \textit{Laplacian} matrix, defined as $\Matrix{A} - \Matrix{D}$, where $d_{ii}$ is the weighted degree of $i^{th}$ vertex in the global interactome.
\item Parameter $\alpha$ controls the relative importance of regularization
\end{itemize}
\end{frame}



\begin{frame}{Interpretation}{Loss function}
\begin{itemize}
\item The first term defines a \textit{diffusion kernel} that propagates activity of genes through network links.
\item We can expand it as $\sum_{i, j} w_{i, j} (x_i - x_j)^2$, which is the accumulated difference of  values between adjacent nodes scaled by the weight of the edge connecting them.
\item The Laplacian operator $\Matrix{L}$ acts on a given function defined over vertices of a graph, such as $\Vector{x}$, and computes the smoothness of $\Vector{x}$ over adjacent vertices.
\item It can be also computed as $\parallel \Matrix{B}\Vector{x} \parallel_2^2$, where $\Matrix{B}$ is the incident matrix of the graph
\end{itemize}
\end{frame}


\begin{frame}{Interpretation}{Regularizer}
\begin{itemize}
\item  The second term is a \textit{regularizer} which penalizes changes or deviations
\item We can expand it as $\sum_{i} |x_i - z_i|$, where $x_i$ and $z_i$ are the (inferred) \underline{functional} and the \underline{transcriptional} activity of gene $i$, respectively.
\item It enforces sparsity over the vector of differences between \textit{transcriptional} and \textit{functional} activities. 
\end{itemize}

\end{frame}

%\begin{frame}{Implementation}{CVX formulation}
%\begin{itemize}
%
%\end{itemize}
%
%\end{frame}

\subsection{Updating global interactome}
\begin{frame}{Constructing tissue-specific interactome}
\begin{block}{Updating edges}
\begin{equation*}
\hat{\Matrix{A}} = \diag (\Vector{x}^*) * \Matrix{A} * \diag(\Vector{x}^*)
\end{equation*}
\end{block}

\begin{itemize}
\item $\Vector{x}^*$ is the solution of optimization problem\
\item It represents functional activity of genes
\item Functional activities are inferred from the global network context
\item We update each edge according to the functional activity of its end-points
\end{itemize}
\end{frame}




\section{Results}
\subsection{Network statistics}
\begin{frame}{Decomposition of global interactome}

\begin{figure}
\includegraphics[width=.75\columnwidth]{figures/ActPro/decomp}
\end{figure}

Brain-specific network using ERW and ActPro ($\alpha=0.5$) methods
\centering

\end{frame}


\subsection{Predicting known biology}
\begin{frame}{Results}{Predicting tissue-specific interactions in known functional pathways}
\begin{columns}[c]
	\column{0.55\textwidth}
	\begin{center}
		\includegraphics[width=\columnwidth]{figures/ActPro/ESEA_AUC}\\
		\tiny Average performance of different methods in predicting differential interactions
	\end{center}
		
	\centering Edge Set Enrichment Analysis (ESEA)
	
	\column{0.45\textwidth}
	\begin{center}
		\includegraphics[height=0.2\textheight]{figures/ActPro/Fallopian_Tube_ROC.pdf}\\
		\includegraphics[height=0.2\textheight]{figures/ActPro/Cervix_Uteri_ROC.pdf}\\
		\includegraphics[height=0.2\textheight]{figures/ActPro/Vagina_ROC.pdf}\\
		\tiny Tissues with the highest gain of AUC for predicting tissue-specific pathway edges
	\end{center}

\end{columns}
\end{frame}


\begin{frame}{Results}{Compactness of disease-related genes}

\begin{table}\tiny
\centering
\begin{tabular}{l|cccccc}
	&	\textbf{global	}&	\textbf{ActPro\_0.15	}&	\textbf{ActPro\_0.50	}&	\textbf{ActPro\_0.85	}&	\textbf{ERW	}&	\textbf{NR}\\\hline
Alzheimer's disease	&\textbf{4.12E-3}	&6.96E-3	&5.98E-3	&5.44E-3	&5.32E-3	&9.60E-2\\
breast carcinoma	&1.83E-3	&1.11E-3	&8.40E-4	&\textbf{8.30E-4}	&4.09E-3	&8.15E-2\\
chronic lymphocytic leukemia	&8.20E-4	&7.40E-4	&\textbf{4.80E-4}	&5.10E-4	&8.50E-4	&2.94E-2\\
coronary artery disease	&3.95E-1	&1.58E-1	&1.09E-1	&1.03E-1	&1.33E-1	&\textbf{1.93E-2}\\
Crohn's disease	&2.56E-2	&1.93E-2	&1.50E-2	&\textbf{1.44E-2}	&8.54E-2	&4.14E-1\\
metabolic syndrome X	&1.11E-2	&1.09E-2	&\textbf{1.07E-2}	&1.12E-2	&1.02E-1	&7.39E-1\\
Parkinson's disease	&1.59E-2	&1.25E-2	&9.89E-3	&\textbf{9.50E-3}	&1.34E-2	&9.62E-2\\
primary biliary cirrhosis	&\textbf{7.20E-4}	&1.32E-3	&3.16E-3	&3.40E-3	&2.80E-2	&6.86E-1\\
psoriasis	&\textbf{2.10E-4}	&1.10E-3	&1.16E-3	&9.50E-4	&4.67E-3	&3.24E-1\\
rheumatoid arthritis	&1.70E-2	&\textbf{9.28E-3}	&1.06E-2	&1.10E-2	&6.39E-2	&3.61E-1\\
systemic lupus erythematosus	&4.98E-2	&1.19E-2	&7.56E-3	&7.22E-3	&2.55E-3	&\textbf{1.60E-4}\\
type 1 diabetes mellitus	&2.64E-2	&3.01E-2	&\textbf{2.38E-2}	&2.40E-2	&2.64E-1	&9.39E-1\\
type 2 diabetes mellitus	&1.57E-3	&2.90E-4	&2.40E-4	&\textbf{1.80E-4}	&5.60E-4	&7.90E-3\\
vitiligo	&\textbf{1.17E-3}	&2.13E-3	&3.04E-3	&3.54E-3	&1.84E-2	&5.69E-1\\
schizophrenia	&3.47E-1	&2.13E-1	&1.93E-1	&1.84E-1	&1.40E-1	&\textbf{4.10E-2}\\\hline
combined	&1.53E-13	&1.24E-17	&6.62E-19	&\textbf{3.70E-19}	&9.03E-14	&2.43E-03\\
\end{tabular}
\end{table}

\begin{itemize} \small
\item Symmetric random-walk as a measure of distance
\item Empirical \emph{p}-value for each tissue
\item \emph{p}-value combination using Edgington method
\end{itemize}

\begin{center}
$\Rightarrow$ \textit{ActPro} yields more significant compactness for known disease genes
\end{center}
\end{frame}

\subsection{Identifying disease-related pathways}
\begin{frame}{Results}{Identifying novel disease-related pathways}
\begin{columns}[c]
	\column{.45\textwidth}
	\begin{center}	
		\includegraphics[height=.35\textheight]{figures/ActPro/Alzheimer}\\
		\tiny Alzheimer's Disease\\
		\vspace{1em}
		\includegraphics[height=.35\textheight]{figures/ActPro/Parkinson}\\
		\tiny Parkinson's Disease\\
	\end{center}
	\column{0.55\textwidth}
		\begin{itemize}
			\item Prize Collecting Steiner Tree (PCST)
			\begin{equation*} 
				\argmin_{<v, e> \in T} \Big\{  \sum_{e} c_e - \lambda \sum_{v} b_v \Big\}
			\end{equation*}
			\item Solved using known message-passing algorithm
		\end{itemize}
\end{columns}
\end{frame}


\begin{frame}{Questions}

\begin{figure}
\includegraphics[width=.85\textwidth]{figures/questions}
\end{figure}

\alert{PS: I am defending this summer and will be in the job marker for PostDocs.}
\end{frame}

\end{document}


