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

\pdfpageattr {/Group << /S /Transparency /I true /CS /DeviceRGB>>}   

% 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{tabularx}
\usepackage{booktabs}


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


\newcommand{\A}{\bs{\mathcal{A}}}
\newcommand{\x}{\bs{x}}
\newcommand{\e}{\bs{e}}
\newcommand{\PI}{\bs{\pi}}
\newcommand{\one}{\bs{1}}


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

\title[CSoI Annual Review, 2017] % (optional, use only with long paper titles)
{Novel formulations and methods for emerging problems in single cell data analysis}




\author[Grama et al.] % (optional, use only with lots of authors)
{Shahin Mohammadi, Vikram Ravindra, David Gleich, Ananth Grama}

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

\date[Sept 18] % (optional, should be abbreviation of conference name)
{Sept 13, 2018}



\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}{Introduction and Overview}

\begin{itemize}
\item
The wealth of data from various biological screens offers tremendous opportunities and challenges
for Science of Information.
\item
Recent advances in single cell technologies enable us to probe dynamic states of individual cells.
\item
Single cell technologies are also redefining basic understanding of cell types, tissue organization,
pathology, and response.
\item
Single cell technologies result in datasets, models, and information that are orders of magnitude
more than conventional genomic/ transcriptomic/ interactomic technologies.
\item
Powerful new computational/ statistical/ modeling toolkits are necessary for single cell datasets.
\end{itemize}
\end{frame}

\begin{frame}{Introduction: Some Basic Terminology}

\begin{itemize}
\item
DNA is the basic code that governs living systems.
\item
DNA is transcribed into RNA. This process of transcription is controlled by a number of transcriptional
control mechanisms (Transcription Regulation, Post Transcriptional Regulation).
\item
RNA is translated into proteins -- the workhorses in living cells. The process of translation is controlled
by a number of control mechanisms (Translational Controls).
\item
The activity of proteins is controlled by various post translational modifications (phosphorylation,
methylation).
\end{itemize}
\end{frame}


\begin{frame}{Introduction: Some Basic Terminology}

\begin{itemize}
\item
Each cell in an organism (with some noted exceptions) inherits the same genetic code (its genome).
\item
Different cells exhibit different behavior (and function) as a result of different activity
levels of genes.
\item
Cells exhibiting the same profile of genetic activity are generally believed to be of the same type.
\item
Within the set of genes, some genes are generally active across all cell types (housekeeping genes),
other are selective to sets of cell types (tissue selective), others are specific to cell
types (tissue specific).
\item
Genes whose activity is unique to cell types are called markers.
\item
The activity of genes in a cell is impacted by its state, stressors (external stimuli), disease, etc.
\item
The most common tool to interrogate the state of a cell is to study gene expression using
microarrays or RNA Sequencing (RNASeq).
\item
Among the most common single cell technologies is single cell RNA Seq (scRNASeq).
\end{itemize}
\end{frame}


\begin{frame}{Overview of Presentation}
\begin{center}
\includegraphics[width = \textwidth]{figures/ResearchSummary}
\end{center}
\end{frame}

\section{Establishing functional identity of cells}
\begin{frame}{Establishing functional identity of cells}
 \tableofcontents
    [
        currentsection,
        currentsubsection,
        subsectionstyle=show/shaded/hide
    ]
\end{frame}

\begin{frame}{Establishing functional identity of cells}
\begin{center}
\includegraphics[width=0.95\textwidth]{figures/ACTION/main/ACTION_flow}
\end{center}
\end{frame}


\begin{frame}{Component 1: New measures for cell-cell similarity}{Motivation}

\begin{block}{Underlying hypothesis}
%Transcriptional profile of cells is dominated by housekeeping genes, whereas their functional identity is determined by a combination of weakly expressed but highly preferential/selective/specific genes.
Transcriptional profile of cells is dominated by housekeeping genes, whereas their functional identity is determined by a combination of weak but preferentially expressed genes.
\end{block}
\end{frame}



\begin{frame}{Component 1: New measures for cell-cell similarity}{Supporting evidence}

\begin{columns}
\column{0.45\textwidth}
\begin{figure}
\includegraphics[width = \columnwidth]{figures/ACTION/hypothesis/before_EndothelialCells.pdf}
\caption{Endothelial Cells}
\end{figure}

\column{0.45\textwidth}
\begin{figure}
\includegraphics[width = \columnwidth]{figures/ACTION/hypothesis/before_B-Cells.pdf}
\caption{B-Cells}
\end{figure}

\end{columns}

\end{frame}




\begin{frame}{Component 1: New measures for cell-cell similarity}{Supporting evidence}

\begin{columns}
\column{0.45\textwidth}
\begin{figure}
\includegraphics[width = \columnwidth]{figures/ACTION/hypothesis/after_EndothelialCells.pdf}
\caption{Endothelial Cells}
\end{figure}

\column{0.45\textwidth}
\begin{figure}
\includegraphics[width = \columnwidth]{figures/ACTION/hypothesis/after_B-Cells.pdf}
\caption{B-Cells}
\end{figure}

\end{columns}

\end{frame}

\begin{frame}{Component 1: New measures for cell-cell similarity}{Cell similarity kernel in ACTION}
\begin{center}
\includegraphics[width=0.85\textwidth]{figures/ACTION/main/kernel_flow}
\end{center}

\begin{itemize}
\item  The main steps involved in identifying similarity between cells
\end{itemize}

\end{frame}


\begin{frame}{Component 1: New measures for cell-cell similarity}{Reducing the noise contributed by highly expressed but uninformative genes}
\alert{Goal:} Identify the shared subspace of genes

\begin{block}{Low-rank decomposition}
\begin{equation*}
A = U_r \Sigma_r V_r = \sum_{i=1}^{r}\sigma_i u_i {v_i}^{T},
\end{equation*}
\end{block}

Example decomposition choices:

\begin{itemize}
\item Mean vector
\begin{itemize}
\item \textit{Optimal in a least-square sense when the chance of observing a gene is uniform across all cells.}
\end{itemize}
\item Singular Value Decomposition (SVD) 
\item Nonnegative Matrix Underapproximation (NMU)
\item Sparse NMU
\end{itemize}

\end{frame}


\begin{frame}{Component 1: New measures for cell-cell similarity}{Reducing the noise contributed by highly expressed but uninformative genes}
	\alert{Goal:} Remove the effect of common subspace
	
	\begin{columns}
    \column{.55\textwidth}
    \begin{itemize}
    \small
		\item $\Vector{x}_i$ and $\Vector{x}_j$: tissues/cell types $i$ and $j$
		\item \emph{z}-score normalize $\Vector{x}_i$ to compute $\Vector{z}_i$
		\item $\Vector{\beta}_h$: the common signature    
		\item \emph{z}-score normalize $\Vector{\beta}_h$ to compute $\Vector{z}_h$

		
		\item Project to the orthogonal subspace:		
		\begin{eqnarray*}
			\Vector{z}_i^{\perp} &=& %\Matrix{P}^{\perp}\Vector{z}_i\\\nonumber
			%&=&(\Matrix{I} - \Matrix{P})\Vector{z}_i\\\nonumber
			%&=&
			\Big(\Matrix{I} - \frac{\Vector{z}_{h}\Vector{z}_{h}^{T}}{\| \Vector{z}_{h}\|_2^2}\Big) \Vector{z}_i.
		\end{eqnarray*}

		
    \end{itemize}
		
    \column{.45\textwidth}
		\centering 
		\includegraphics[width=0.9\columnwidth]{figures/ACTION/geo}\\
	\end{columns}

	\vspace{1em}
	Similar in nature to the partial Pearson's correlation		
\end{frame}


\begin{frame}{Component 1: New measures for cell-cell similarity}{Enhancing the signal from preferentially-expressed genes}
\alert{Goal: } Estimate expression-specificity of genes across different cells

\begin{columns}[c]
\column{.35\textwidth}
\includegraphics[height=0.4\textheight]{figures/ACTION/Entropy}


\column{.65\textwidth}
\begin{itemize}
\item Entropy as a measure of expression uniformity: $H(i) = -\sum_j p_{ij} log(p_{ij})$
\item How informative is observing a gene with respect to the cell type that it came from
\item Maximum entropy when probability of a gene coming from all cell types is equal
\item For each gene $i$, compute a specificity factor \alert{$w_i$}.
\end{itemize}
\end{columns}
%
	\vspace{1em}
	Similar formulations have been previously used for marker detection.

\end{frame}


%\begin{frame}{Component 1}{Enhance signal from preferentially-expressed genes-- Changes}
%
%\begin{itemize}
%\item We work with the projection of $\mathcal{Z}^{\perp}$ onto the space of positive real values: $\mathcal{P}^{(+)}(\mathcal{Z}^{\perp})$.
%\item Compute uniformity of expression for each gene using entropy-based method
%\item Estimate the number of genes with high specificity using \textit{participation ratio ($\Loss_2^2/\Loss_4$)}.
%\item Limit the range of weights to a band of 4 order of magnitudes ($10^{[-2, 2]}$), in order to remove the effect of outliers.
%\end{itemize}
%\end{frame}
%



\begin{frame}{Component 1: New measures for cell-cell similarity}{Putting the pieces together}

\begin{block}{ACTION-adjusted cell signatures}
\begin{equation*}
\Matrix{Y} = \diag(\Vector{w})\Matrix{\mathcal{Z}^{\perp}}
\end{equation*}
\end{block}

\begin{block}{ACTION metric (kernel)}
\begin{eqnarray*}
\Matrix{K}_{ACTION} &=& \Matrix{Y}^{T}\Matrix{Y}\\ &=&\big(\Matrix{\mathcal{Z}^{\perp}}\big)^{T}\diag(\Vector{w}^2)\big(\Matrix{\mathcal{Z}^{\perp}}\big)
\end{eqnarray*}

\end{block}
\end{frame}


\begin{frame}{Component 1}{Cell similarity kernel -- revisited}
\begin{center}
\includegraphics[width=0.85\textwidth]{figures/ACTION/main/kernel_flow}
\end{center}

\begin{itemize}
\item  Now we have computed the ACTION kernel
\end{itemize}

\end{frame}


\begin{frame}{Benchmark datasets}
\begin{itemize}
\small
\item \textbf{Immune:} \alert{1,522 immune cells} from mouse hematopoietic system (\alert{30 different types} of stem, progenitor, and fully differentiated cells)
\item \textbf{Melanoma:} \alert{4,645 malignant, immune, and stromal cells} isolated from 19 freshly procured human melanoma tumors (\alert{7 major types}, including T, B, NK, CAF, Endo, Macro, and Tumor)
\item \textbf{MouseBrain:} \alert{3005 cells}  from the mouse cortex and hippocampus (\alert{7 major types}, including \textit{astrocytes-ependymal, endothelial-mural, interneurons, microglia, oligodendrocytes, pyramidal CA1}, and \textit{pyramidal SS}).
\item \textbf{Pollen:} Small set of \alert{301 cells} spanning \alert{11 different cell types} in developing cerebral cortex
\end{itemize}
\end{frame}



\begin{frame}{Performance of ACTION Kernel}
  \begin{columns}[c]   
    \column{.3\textwidth}
			\includegraphics[width=\columnwidth]{figures/ACTION/kernelComp_mean_NMI}\\
			\includegraphics[width=\columnwidth]{figures/ACTION/kernelComp_mean_ARI}\\

    \column{.7\textwidth}
	\begin{itemize}
	\small
		\item Benchmarks:
		\begin{itemize}
		\item SIMLR: Specifically designed for single-cell data
		\item IsoMap,MDS: General purpose dimension reduction
		\end{itemize}
		\item Tested a range of parameters (5:5:50). Reported best case for each method.
%		\item Used \emph{t}-test for evaluating differences
		\item Ties:
		\begin{itemize}
			\tiny
			\item \textit{Immune} (NMI: ACTION/MDS/SMLR, ARI: ACTON/MDS)
			\item \textit{Melanoma} (ARI: ACTION/SIML)
		\end{itemize}
		\item In all other cases, \textit{ACTION} metric significantly outperforms all other methods.
	\end{itemize}		
	
	\end{columns}

\vspace{1em}
\begin{itemize}
\item \underline{Overall, \textit{ACTION} metric performs better than other methods}
\end{itemize}

\end{frame}

\begin{frame}{Overall Workflow}{Component 2}
\begin{center}
\includegraphics[width=0.95\textwidth]{figures/ACTION/main/ACTION_flow}
\end{center}
\end{frame}



\begin{frame}{Component 2: Characterizing principal functional profiles}{Motivation}

\begin{block}{General framework}
		\begin{equation*}
\centering
\begin{aligned}
& \underset{\Matrix{C}, \Matrix{H}}{\argmin}
& & \parallel \Matrix{Y} - \underbrace{\Matrix{Y} \Matrix{C}}_{\Matrix{W}} \Matrix{H} \parallel \\
& \text{subject to:} 
& & \parallel \Matrix{C}(:, i) \parallel_1 = 1.\\
& & & \parallel \Matrix{H}(:, i) \parallel_1 = 1.\\
&& &  0 \leq \Matrix{C},  0 \leq \Matrix{H}
\end{aligned}	
		\end{equation*}
\end{block}

Various algorithms can be cast using this formulation
\begin{itemize}
\item \alert{K-means}: $\Matrix{C} \in \R^{+}, \Matrix{H} \in\{0, 1\}$
\item \alert{K-medoids}: $\Matrix{C}  \in\{0, 1\}, \Matrix{H} \in\{0, 1\}$
\end{itemize}
\end{frame}



%\begin{frame}{Component 2: Characterizing principal functional profiles}{Motivation}
%There are fundamental problems with K-means/medoids:
%
%	\begin{itemize}
%		\item They use hard assignment, whereas many cell types are believed to form a continuum.
%		\item They are sensitive to initialization.
%		\item They are dependent on $k$.
%	\end{itemize}
%\end{frame}
%



\begin{frame}{Component 2: Characterizing principal functional profiles}{Convex Nonnegative Matrix Factorization (NMF) }
\begin{block}{Convex NMF}
		\begin{equation*}
\centering
\begin{aligned}
& \underset{\mathcal{K}, \Matrix{H}}{\argmin}
& & \parallel \Matrix{Y} - \Matrix{Y}(:, \mathcal{S}) \Matrix{H} \parallel \\
& \text{subject to:} 
& & \parallel \Matrix{H}(:, i) \parallel_1 = 1, \Matrix{H} \in \R^{+}.\\
\end{aligned}	
		\end{equation*}				
\end{block}

\begin{itemize}
\item It uses the same formulation as k-medoid, but relaxes the hard assignment of cells: $ \Matrix{C} \in \{0, 1\},  \Matrix{H} \in \R^{n}$
\item Unlike k-medoid and k-means, it has an \alert{optimal global solution}.
\begin{itemize}
\item Under \alert{near-separability} assumption: there exists, for each cell type, an ideal example in the population.
\end{itemize}
\item A modification of the \textit{Gram Schmidt} process.
\end{itemize}	
	
\end{frame}



\begin{frame}{Component 2: Characterizing principal functional profiles}{Convex NMF-- Geometric interpretation}
	
  \begin{columns}[c]   
    \column{.4\textwidth}
			\includegraphics[width=\columnwidth]{figures/ACTION/polytope}\\
	    \alert{Geometry of functional space:} each point is a cell and red points are the ``pure cells''

    \column{.6\textwidth}
	\begin{itemize}
	\item Picking $k$ corner points/archetypes from the convex hull of the cells, such that they optimally ``contain" the rest of cells.
	\item Each archetype is an ideal example of a cell type with a distinct set of \alert{principal functions}.
	\end{itemize}
	\end{columns}


\end{frame}





%\begin{frame}{Component 2: Characterizing principal functional profiles}{Preconditioning -- theorems}
%	\alert{Goal:} Understand the behavior of near-separable NMF
%
%\begin{block}{Performance guarantee}
%\begin{equation*}
%\max_{1 \leq  j\leq r}\min_{s \in \mathcal{S}} \parallel \Matrix{Y}(:, s)-\Matrix{W}(:, j) \parallel \leq \mathcal{O}\Big( \epsilon \kappa^2(\Matrix{W})\Big)
%\end{equation*}
%\end{block}	
%
%
%\begin{itemize}
%\item For any near-separable matrix, multiplying it by any nonsingular matrix $\Matrix{Q}$ preserves separability, where matrix $\Matrix{W}$ is replaced with $\Matrix{Q}\Matrix{W}$. 
%
%\item In this case, we have the following modified upper bound: \alert{$\mathcal{O}\Big( \epsilon \kappa(\Matrix{W})\kappa^3(\Matrix{Q}\Matrix{W})\Big)$}.
%\end{itemize}
%
%\end{frame}

%
%
%\begin{frame}{Component 2}{Preconditioning -- Minimum volume ellipsoid method}
%	\alert{Goal:} Enhance conditioning of the problem
%
%\begin{itemize}
%\item Ideally, we would like $\Matrix{Q} = \Matrix{W}^{-1}$, but if we knew that there was nothing to solve!
%\item It turns out that we can approximate $\Matrix{W}^{-1}$ using a \textit{minimum volume ellipsoid} centered around the origin that that contains all columns of the original matrix $\Matrix{X}$.
%\item This can be solved using the following SDP to identify spd matrix $\Matrix{A^{*}}$:
%
%\begin{alignat*}{2}
%\Matrix{A}^{(*)}  &= \argmax_{\Matrix{A} \in \mathbb{S}_{+}^{k}} \textbf{det}(\Matrix{A})\\
%\mbox{S.t.} & \Matrix{X}(:, j)^{T}\Matrix{A}\Matrix{X}(:, j) \leq 1; \forall j
%\end{alignat*}
%
%\item Since $\Matrix{A^{T}}$ is s.p.d., we can compute $\Matrix{A^{T}} = \Matrix{Q}^T\Matrix{Q}$ using Cholesky factorization. 
%\end{itemize}
%
%\end{frame}
%


\begin{frame}{Component 2: Characterizing principal functional profiles}{Archetypal Analysis (AA)}
\begin{itemize}
\item  AA further relaxes matrix $\Matrix{C}$: $\Matrix{C}, \Matrix{H} \in \R^{+}$.
\item It can handle cases where pure pixel assumption is violated.
\item But it no longer has global convergence guarantee $\rightarrow$ it is also dependent on the initialization
\begin{itemize}
\item To address this, we use the solution of convex NMF for initializing AA.
\end{itemize}
\item In essence, this allows local adjustment of the Convex NMF solution.
\item This can be thought of as a variant of \alert{block-coordinate descent} for optimization.
\end{itemize}

\end{frame}




\begin{frame}{Component 2: Characterizing principal functional profiles}{Finding the number of archetypes ($k$)}
\alert{Goal:} To identify when we should stop adding new archetypes.

\vspace{1em}

	\begin{itemize}
	\small
	\item Underlying concept: add archetypes until we sense "oversampling."
	\item Oversampling happens when we start adding archetypes that are ``too close" to each other.
	\item Each archetype is a cell $\rightarrow$ we can compute their similarity of using the ACTION metric.
	\end{itemize}

\end{frame}


\begin{frame}{Component 2: Characterizing principal functional profiles}{Statistical significance of oversampling}
\begin{columns}[c]
    \column{.25\textwidth}
		\includegraphics[width=\columnwidth]{figures/ACTION/ER}\\

    \column{.75\textwidth}
    \footnotesize
	\begin{itemize}
	\item We build and threshold an archetype-archetype similarity graph.
	\item For each connected component in this graph, we assess its statistical significance using an Erdos Renyi graph model.
	\item Probability that there exists in $\Graph{G}$ a subgraph of density $\delta(\Set{Z})$ and size 
at least $|\Set{Z}|$: 
\begin{align*}
	\Pr[\exists \Set{H} \subseteq \Graph{G}, |\Set{H}|\geq |\Set{Z}| ~:~ \delta(\Set{H}) = \delta(\Set{Z})].
\end{align*}
	
	\end{itemize}
\end{columns}

\end{frame}





\begin{frame}{Component 2: Characterizing principal functional profiles}{Test 1: Identifying cell types using closest archetype}
    	\includegraphics[width=\columnwidth]{figures/ACTION/main/CellType_ID}

\vspace{4em}
	\begin{itemize}
	\item \underline{ACTION excels at identifying underlying cell types in \alert{all cases}}
	\end{itemize}
\end{frame}



\begin{frame}{Component 2: Characterizing principal functional profiles}{Visualizing the functional space}
	\begin{itemize}
	\item Use matrix $\Matrix{H}$ instead of $\Matrix{Y}$ in visualization:
	\begin{itemize}
		\item We are interested in the relationship between cells and their surrounding archetypes.
	\end{itemize}	
	\item Initialize using Fiedler embedding
	\begin{itemize}
		\item Position according to the dominant eigenvectors of the Laplacian matrix: $\Matrix{L} = \mathbf{diag}(\Delta_\Matrix{Y}) - \Matrix{Y}$.
	\end{itemize}	
	\item Update using \emph{t}-SNE
	\end{itemize}
\end{frame}


\begin{frame}{A continuous view of transcriptional profiles}{Case study in the Melanoma dataset}
\begin{columns}[c]
\column{0.45\textwidth}
    		\includegraphics[width=\columnwidth]{figures/ACTION/main/Melanoma_map_cox}

\column{0.5\textwidth}
\begin{itemize}
\small
\item T-cells reside in a continuum of states (\alert{Thogerson \textit{et al.}}). 
\item Tumor cells form compact groups.
\item Two subclasses of MITF-associated tumors significantly differ in terms of their survival.
\end{itemize}
\end{columns}

\vspace{0.5em}

\begin{itemize}
\item \underline{ACTION highlights the underlying topology of cell types}
\end{itemize}

\end{frame}


%\begin{frame}{Stats of tumor cells}
%\begin{itemize}
%\item Patients 58, 67, 72, 74 have no measured tumor cells    
%\item Patients 53, 60, 65, 75, 84, and 94 have less than 20 sampled cells
%\item There are 9 cells with sufficient tumor cell samples
%\end{itemize}
%\end{frame}

%\begin{frame}{Archetype 4}{A \textit{de novo} identified subclass of Melanoma cancer patients}
%\begin{itemize}
%\item There are a total of 4 patients with NRAS Q61L mutation among 19 total patients.
%\item Archetype 4 identifies 5 patients, 4 of which coincide with patients with NRAS Q61L mutation
%\item This has \emph{p}-value of $1.3 \times 10^{-3}$.
%\end{itemize}
%\end{frame}

\begin{frame}{Overall Workflow}{Component 3: Identifying the interactions underlying architypes}
\begin{center}
\includegraphics[width=0.95\textwidth]{figures/ACTION/main/ACTION_flow}
\end{center}
\end{frame}


\begin{frame}{Component 3: Identifying the interactions underlying architypes}{Constructing TRN}
\begin{center}
    		\includegraphics[width=0.95\textwidth]{figures/ACTION/main/TRN_flow}\\    		
\end{center}
\end{frame}


\begin{frame}{Component 3: Identifying the interactions underlying architypes}{Constructing TRN}
\alert{Goal:} Identifying key regulatory elements that drive each cell type

\vspace{1em}

\begin{enumerate}
\item \alert{Archetype Orthogonalization} ($\rightarrow$ Only over positive projection)\\
\begin{equation*}
\Vector{a}_i^{\perp} 
= \Big(\Matrix{I} - \Matrix{A}_{-i}^{} 
	(\Matrix{A}_{-i}^{T}\Matrix{A}^{}_{-i})^{-1}
    \Matrix{A}_{-i}^{T}\Big)
\Vector{a}_i
\end{equation*}

\item \alert{Assessing significance of TFs/TGs}\\
\begin{eqnarray*}
\text{\emph{p}-value} (Z = b_l(\lambda)) &=& \text{Prob}(b_l(\lambda)\leq Z) \nonumber \\
&=& \sum_{x=b_l(\lambda)}^{min(T, l)} \frac{{T \choose x} {m-T \choose l-x}} {{m \choose l}} \nonumber\\
\end{eqnarray*}
Use Dynamic Programming to compute exact \emph{p}-value.
\end{enumerate}

\end{frame}


\begin{frame}{Functional activity of transcription factors (TFs)}
\begin{block}{Key point!}
We identify ``functional activity'' of transcription factors (TFs) by aggregating transcriptional activity of their downstream targets, not the transcriptional level of TFs themselves. TFs can, and typically do, get regulated through post-translational mechanisms.
\end{block}
\end{frame}


\begin{frame}{Identifying transcriptional controls of Melanoma subtypes}{Proliferative versus invasive status}

\begin{itemize}
\small
\item Both \textit{Subtype A} and \textit{Subtype C} exhibit high activity of \textit{MITF} and \textit{Sox10} transcription factors, which are canonical markers for melanoma cells in the ``proliferative'' (as opposed to ``invasive'') state (\alert{Verfaiilie \textit{et al.}}).
\item These two subtypes are significantly enriched for marker genes in the proliferative state:
\begin{itemize}
\item \textit{Subtype A: } $9.3 \times 10^{-14}$
\item \textit{Subtype B: } $7.9 \times 10^{-11}$
\end{itemize}
\item Subtype A has higher MITF activity (according to its activated targets):
\begin{itemize}
\item \textit{GPNMB, M1ANA, PMEL,} and \textit{TYR} are shared between two subtypes.
\item \textit{ACP5, CDK2, CTSK, DCT, KIT,} and {TRPM1/P1} are uniquely upregulated in subtype A.
\end{itemize}
\end{itemize}
\end{frame}



\begin{frame}{Dissecting transcriptional controls of Melanoma subclasses}{Case study in MITF$\upuparrows$/MYC$\uparrow$ subtype}
\begin{center}
    		\includegraphics[height=0.53\textheight]{figures/ACTION/main/TRN}\\    		    		
\end{center}

\begin{itemize}
\small
\item 19 ``functionally'' active transcription factors in subtype A (\emph{p}-value $\leq 0.05$)
\item We focus on the five most significant TFs and their targets (\emph{p}-value $\leq 10^{-3}$)
\end{itemize}
\end{frame}


\begin{frame}{Case study in MITF$\upuparrows$/MYC$\uparrow$ subtype}{Core transcription factors}
\begin{itemize}
\footnotesize
\item MITF is among the best-known markers for classifying melanoma patients (\alert{Hartman \textit{et al.}}: MITF in melanoma: mechanisms behind its expression and activity).
\item Overexpression of the E2F1 is common in high-grade tumors that are associated with poor survival in melanoma patients (\alert{Alla \textit{et al.}}: E2F1 in melanoma progression and metastasis).
\item Melanoma cell phenotype switching, between proliferative an invasive states, is regulated by differential expression of LEF1/TCF4 (\alert{Eichhoff \textit{et al.}}:Differential LEF1 and TCF4 expression is involved in melanoma cell phenotype switching).
\item Amplification and overexpression of the c-myc have been associated with poor outcome (\alert{Kraehn \textit{et al.}}: Extra c-myc oncogene copies in high risk cutaneous malignant melanoma and melanoma metastases).
\end{itemize}
\end{frame}


\begin{frame}{Inferring transcriptional controls of Melanoma subtypes}{Survival analysis}
\begin{columns}[c]
\column{0.35\textwidth}
\includegraphics[width=\columnwidth]{figures/ACTION/SubtypeA_Cox}\\
\tiny \textit{Subtype A:} \emph{p}-value = $5.4 \times 10^{-10}$

\includegraphics[width=\columnwidth]{figures/ACTION/SubtypeC_Cox}\\
\tiny \textit{Subtype C:} \emph{p}-value = $ 0.31$

\column{0.6\textwidth}
\begin{itemize}
\item OncoLnc (\alert{Jordan Anaya})
\item Multivariate Cox regressions
\item Gene expression, sex, age, and grade or histology  as factors
\item Genes associated with Subclass A have significantly worse outcome, compare to the background of all genes
\end{itemize}
\end{columns}
\end{frame}


\begin{frame}{Case study in MITF$\upuparrows$/MYC$\uparrow$ subtype}{Survival analysis revisited -- Kaplan-Meier plots}
\begin{center}
    		\includegraphics[height=0.6\textheight]{figures/ACTION/TRN_Cox}\\
\end{center}
\end{frame}


\begin{frame}{Recap}
\begin{enumerate}
\item A novel cell similarity metric that is robust to biological noise, while at the same time is sensitive enough to identify weak cell type-specific signals
\item New notion of functional identity of cells
\begin{itemize}
\item Under the pure cell assumption, this metric induces a convex topology that embeds functional identity of cells
\end{itemize}
\item Use functional identity of cells to identify both discrete cell types and continuous cell states
\item Identify driving transcriptional controls that mediate the functional identity of cells
\end{enumerate}

\begin{center}
\alert{Clinical significance:} Characterization of  two MITF-associated subclasses of Melanoma patients, one of which has substantially worse outcomes, along with their underlying regulatory elements.
\end{center}
\end{frame}



\begin{frame}{Forthcoming Results}{Mystery of inflated zeros: a curse or a blessing?}
\begin{itemize}
\item Use ACTION to infer cell types. 
\item Use inferred cell types to distinguish true zeros from missing values
\begin{itemize}
\item There is a significant biological signal embedded merely within the sparsity pattern of the single-cell profiles.
\end{itemize}
\item Use SVR to impute missing values.
\end{itemize}
\end{frame}


\begin{frame}{Forthcoming Results}{Use ACTION to infer lineage paths within the functional space of the cells}
\begin{itemize}
\item Identify stable attractor states within the continuous functional space of cells.
\item Trace the most likely transition paths between the states.
\item Identify regulatory factors that stimulate these transitions/fate decisions
\end{itemize}
\end{frame}




\begin{frame}{Forthcoming Results}{Applications}
\begin{itemize}
\item Use ACTION to identify cell types in human brain, construct cell type-specific region-region gene correlation networks, and compare them with the networks constructed from the resting state fMRI
\item Impact of exposing RAW 264.7 macrophage cell line to exosomes from: (i) non-metastatic PEDF expressing A375 cells, and (ii) metastatic A375 melanoma cells (Joint project with Anindita Basu, University of Chicago).
\end{itemize}
\end{frame}


\section{Part II: Constructing tissue/cell type-specific networks}
\begin{frame}{Constructing tissue-specific interactome}
 \tableofcontents
    [
        currentsection,
        currentsubsection,
        subsectionstyle=show/shaded/hide
    ]
\end{frame}


\begin{frame}{Motivation}{Global interactome is not context-specific}
Global human interactome is a superset of all \alert{possible} physical interactions that can take place 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}.

\begin{center}
\includegraphics[height=0.6\textheight]{figures/ActPro/interactome}
\end{center}
\end{frame}


\begin{frame}{Key Question}

\begin{center}
Can we predict which links/edge are \alert{active} in a given \alert{context}?
\end{center}
\end{frame}


\begin{frame}{Roadmap}{Exemplar Networks}

\begin{figure}
\centering
\subfigure[Original]{\includegraphics[height=0.3\textheight]{figures/ActPro/example_before}}%
\hspace{5em}
 \subfigure[Diffusion]{\includegraphics[height=0.3\textheight]{figures/ActPro/example_after}}
\\%
 \subfigure[Projection]{\includegraphics[height=0.3\textheight]{figures/ActPro/example_final}}%
\hspace{5em}
 \subfigure[Pruning]{\includegraphics[height=0.25\textheight]{figures/ActPro/example_pruned}}%
%  \caption{Example}
\end{figure}

\end{frame}


\begin{frame}{Genotype-Tissue Expression (GTEx) Project}
\begin{columns}[c]
\column{0.55\textwidth}
\includegraphics[width=\columnwidth]{figures/ActPro/GTEx}\\
\tiny Adopted from: NIH CommonFund

\column{0.45\textwidth}
\begin{itemize}
\item RNA-Seq dataset v4.0
\item 2,916 samples
\item 30 different tissues
\item Processed each sample individually using UPC/SCAN
\end{itemize}
\end{columns}
\end{frame}



%
%\begin{frame}{Genotype-Tissue Expression (GTEx) Project}{Sample counts}
%\begin{center}
%\includegraphics[width=0.85\textwidth]{figures/ActPro/Num_samples}
%\end{center}
%\end{frame}

%
%\begin{frame}{Transcriptional Activity of Genes}{Processing samples}
%\alert{Goal}: To normalize gene expression profiles on the same scale so they will be comparable across genes
%\vspace{1em}
%
%  \begin{columns}[c]   
%    \column{.45\textwidth}
%		\includegraphics[width=\columnwidth]{figures/ActPro/Blood-Liver-Testis}\\
%	    \footnotesize Distribution of transcriptional activities in three tissues with low, medium, and high number of expressed genes
%    \column{.55\textwidth}
%		\begin{itemize}\small
%		\item Universal exPression Codes (UPC)
%		\item Process each sample individually
%		\item Correct for platform-specific biases
%		\item Transcriptional activity between [0, 1]
%		\end{itemize}
%	\end{columns}
%\end{frame}
%
%
%
%\begin{frame}{Transcriptional Activity of Genes}{Functional enrichment}
%\begin{columns}[c]
%\column{0.55\textwidth}
%		\includegraphics[width=\columnwidth]{figures/ActPro/markers_comparison}\\
%
%\column{0.4\textwidth}
%	GO enrichment for tissues with high, medium, and low number of markers
%\end{columns}
%\end{frame}
%
%



\begin{frame}{Activity Propagation (ActPro)}{From transcriptional activity to functional activity}

\alert{Goal}: Estimate functional activity of genes

\begin{block}{Convex program}
\begin{alignat*}{2}
\Vector{x}^* = \argmin_{\Vector{x}} &\bigg\{ (1-\alpha) \Vector{x}^T\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*}
\end{block}

\begin{itemize}
\item Vector $\Vector{z}$ encodes transcriptional activity of genes, 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}{Activity Propagation (ActPro)}{Interpretation -- Loss function}

\begin{block}{Convex program}
\begin{alignat*}{2}
\Vector{x}^* = \argmin_{\Vector{x}} &\bigg\{ (1-\alpha) \Vector{x}^T\Matrix{L}\Vector{x} +  \alpha \parallel \Vector{x} - \Vector{z}  \parallel_1\bigg\}
\end{alignat*}
\end{block}

\begin{itemize}
\item The Laplacian operator $\Matrix{L}$ acts on a given function defined over vertices of a graph, such as $\Vector{x}$, and computes the \alert{smoothness} of $\Vector{x}$ over adjacent vertices.
\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 First term is a \alert{diffusion kernel}. It propagates activity of genes through network links.
\end{itemize}
\end{frame}


\begin{frame}{Activity Propagation (ActPro)}{Interpretation -- Regularizer}

\begin{block}{Convex program}
\begin{alignat*}{2}
\Vector{x}^* = \argmin_{\Vector{x}} &\bigg\{ (1-\alpha) \Vector{x}^T\Matrix{L}\Vector{x} +  \alpha \parallel \Vector{x} - \Vector{z}  \parallel_1\bigg\}
\end{alignat*}
\end{block}

\begin{itemize}
\item  The second term is a \alert{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) \alert{functional} and the \alert{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}{Results}

\begin{block}{What do we gain?}
Tissue-specific networks have higher power/accuracy in predicting tissue-specific biology and pathobiology
\end{block}
\end{frame}



\begin{frame}{Tissue-specific Pathology}{Predicting 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{enumerate} \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{enumerate}

\begin{center}
\begin{itemize}
\item \textit{ActPro} excels in prioritizing disease-related genes
\end{itemize}
\end{center}
\end{frame}



\begin{frame}{Tissue-specific Biology}{Predicting tissue-specific interactions in known pathways -- Average performance}
\begin{columns}[c]
\column{0.4\textwidth}
		\includegraphics[width=\columnwidth]{figures/ActPro/ESEA_AUC}\\
		
\column{0.6\textwidth}
\begin{itemize}
\item Edge Set Enrichment Analysis (ESEA).
\item Differential correlation score:
\begin{equation*}
EdgeScore = \bs{MI}_{all}(i, j) - \bs{MI}_{control}(i, j)
\end{equation*}
\item Gain of Correlation (GoC) edges
\end{itemize}
\end{columns}
\end{frame}


%\begin{frame}{Tissue-specific Biology}{Predicting tissue-specific interactions in known pathways -- individual tissues}
%\begin{center}
%		\includegraphics[width=0.75\columnwidth]{figures/ActPro/ESEA_ActPro_AUC}\\
%		Accuracy of GoC edge is not equal across different tissues
%\end{center}
%\end{frame}
%
%\begin{frame}{Tissue-specific Biology}{Predicting tissue-specific interactions in known pathways -- top tissue}
%\begin{center}
%		\includegraphics[width=0.7\columnwidth]{figures/ActPro/Fallopian_Tube_ROC}\\
%\end{center}
%\end{frame}


\begin{frame}{Novel Insights}{Identifying disease-related pathways in brain}
\begin{columns}[c]
	\column{.25\textwidth}
	\begin{center}	
		\includegraphics[width=\columnwidth]{figures/ActPro/Alzheimer}\\
		\tiny Alzheimer's Disease\\
		\vspace{1em}
		\includegraphics[width=\columnwidth]{figures/ActPro/Parkinson}\\
		\tiny Parkinson's Disease\\
	\end{center}
	\column{0.7\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 $c_e = \frac{1}{w_e}$ and $b_v = \begin{cases} \infty; v \in markers \\ 1; O.W.\end{cases}$
			\item Red nodes are novel factors 
		\end{itemize}
\end{columns}

\vspace{1em}
\begin{itemize}
\item \textit{ActPro} identifies novel disease-related pathways
\end{itemize}
\end{frame}

\begin{frame}{Forthcoming Results}{Differential network analysis}
\alert{Goal}: Identify driver network perturbations that mediate drug resistance.	\\

\begin{columns}[c]
	\column{.35\textwidth}
	\begin{center}	
		\includegraphics[width=\columnwidth]{figures/ActPro/distr_example}\\
	\end{center}
	\column{0.65\textwidth}
		\begin{itemize}
		\item Use single-cell profiles to construct an ensemble of cell type-specific networks, one for before and one for after treatment.
		\item Combine individual networks within each ensemble to construct a meta-network with a distribution over each edge.
		\item Identify \alert{differential edges} that are significantly rewired across conditions.
		\end{itemize}
\end{columns}

\vspace{1em}
\alert{Key idea}: A majority of perturbations do not disable proteins, but they affect individual interactions.

\end{frame}



%
%
%
%
%\section{Higher-order network alignment}
%\begin{frame}{Higher-order network alignment}
% \tableofcontents
%    [
%        currentsection,
%        currentsubsection,
%        subsectionstyle=show/shaded/hide
%    ]
%\end{frame}
%
%\begin{frame}{Network Motif Meets Network Alignment!}
%\begin{center}
%\includegraphics[width=0.8\textwidth]{figures/TAME/netalign-triangle}\\
%\end{center}
%\end{frame}
%
%\begin{frame}{So, What is a Network Motif?}
%\begin{columns}[c]
%\column{0.5\textwidth}
%\includegraphics[height = 0.75\textheight]{figures/TAME/motifs}
%
%\column{0.45\textwidth}
%``Reoccurring subgraphs in complex networks that are significantly over-represented compared to random graphs with similar characteristics''
%\end{columns}
%\end{frame}
%
%
%\begin{frame}{Encoding Motif Occurrences in a Motif-Tensor}
%
%Let us use \alert{triangle motif} as an example $\cdots$
%
%\begin{block}{Triangle tensor}
%\begin{equation*}
%\Tensor{T}(i, j, k) = 1 \Leftrightarrow \begin{cases} 
%(v_i, v_j) \in E_{\Graph{G}} \\
%(v_j, v_k) \in E_{\Graph{G}} \\
%(v_k, v_i) \in E_{\Graph{G}} 
%\end{cases}
%\end{equation*}
%\end{block}
%
%For undirected graphs, any \alert{motif-tensor is symmetric}. That is:
%
%\begin{block}{Symmetric tensor}
%\begin{equation*}
%\Tensor{T}(i_1, i_2,\ldots, i_k) = \Tensor{T}(i_{\pi(1)}, i_{\pi(2)},\ldots, i_{\pi(k)})
%\end{equation*}
%\end{block}
%
%\noindent for all $\pi \in \Pi_k$, where $\Pi_k$ is the set of all permutations of $(1,2, \ldots, k)$, and $k$ is size of the motif. 
%
%\end{frame}
%
%
%\begin{frame}{Application of Tensor Eigenpairs as an Optimization Tool}
%
%\begin{block}{Interesting fact!}
%\begin{center}
%$\Tensor{T}\Vector{x}^{m-1} = \lambda \Vector{x}; \text{ with } \| \Vector{x} \|_2 = 1
%\Leftrightarrow
%\begin{array}{ll}
% \displaystyle \mathop{\text{maximize}}_{\Vector{x} \in \R^n} & \Tensor{T} \Vector{x}^m \\
% \text{subject to} & \| \Vector{x} \|_2 = 1. 
%\end{array}$
%\end{center}
%\end{block}
%
%\noindent where $ (\Tensor{T} \Vector{x}^{m-1})$ is the $(m-1)^{th}$ \alert{tensor-vector product} and is defined as: 
%
%\begin{equation*}
%(\Tensor{T} \Vector{x}^{m-1})_{i_1} = \sum_{i_2=1}^n \sum_{i_3=1}^{n} \cdots \sum_{i_m=1}^{n} \Tensor{T}_{i_1, i_2,\ldots, i_m} x_{i_2}   x_{i_3} \ldots  x_{i_m}
%\end{equation*}
%
%Using this notation, $\Tensor{T} \Vector{x}^m = \Vector{x}^{T} (\Tensor{T} \Vector{x}^{m-1})$.
%\end{frame}
%
%
%\begin{frame}{Higher-order Generalization of Global Network Alignment Problem}
%
%\begin{block}{Optimization problem}
%\begin{equation*}
% \begin{array}{ll}
%  \displaystyle \mathop{\text{maximize}}_{\Vector{x}} & \displaystyle (1-\beta) \Vector{w}^T \Vector{x} + \frac{\beta}{m!} \Tensor{T} \Vector{x}^{m} \\
% \text{subject to} & \Matrix{C} \Vector{x} \le \Vector{1}_{|V_G|+|V_H|} \\
%  & \Vector{x}(ii') \in \{0, 1\}.
% \end{array}
%\end{equation*}
%\end{block}
%\end{frame}
%
%
%\begin{frame}{Scalability issue}
%\begin{center}
%\begin{tabular}{lccc}
%\toprule
%	&\# nodes	&\# edges	&\# triangles\\	\midrule
%Human	&14,867	&126,593	&407,650\\
%Yeast	&5,850	&79,458	&347,079\\ 
%\bottomrule
%\end{tabular}
%\end{center}
%
%\begin{itemize}
%\item $\Tensor{T} = \Tensor{T}_H \otimes \Tensor{T}_G$
%\item $347,079 \times 407,650 = 141,486,754,350$ pair of triangles!
%\item But we can use structure $\Tensor{T}$ to build an implicit kernel
%\end{itemize}
%
%\end{frame}
%
%
%\begin{frame}{Using Structure of $\Tensor{T}$}
%
%\begin{block}{Implicit tensor-vector product for triangle tensor}
%\begin{equation*}
%\begin{aligned}
%& (\Tensor{\bigtriangleup}_{H \times G}\Vector{x}^2)_{ii'} \\
%& \quad = \sum_{\mathclap{jj', kk'}} \Tensor{\bigtriangleup}_{H \times G} (ii', jj', kk') \Vector{x}(jj')\Vector{x}(kk') \\
%& \quad = \sum_{\mathclap{j, j', k, k'}} \Tensor{\bigtriangleup}_G(i, j, k)\Tensor{\bigtriangleup}_H(i', j', k') \Matrix{X}(j, j')\Matrix{X}(k, k')\\ 
%& \quad = \sum_{\mathclap{j, k}} \Tensor{\bigtriangleup}_G(i, j, k)\sum_{j'} \Matrix{X}(j, j')\sum_{k'}\Tensor{\bigtriangleup}_H(i', j', k') \Matrix{X}(k, k')
%\end{aligned}
%\end{equation*}
%\end{block}
%
%\noindent where $\Tensor{\bigtriangleup}_{H \times G} =  \Tensor{T}_H \otimes \Tensor{T}_G$, when $\Tensor{T}_G$ and $\Tensor{T}_H$ are triangle-tensors.
%\end{frame}
%
%
%\begin{frame}{Identify dominant eigenpair of $\Tensor{T}$}
%
%\footnotesize
%\begin{algorithmic}[1]
%\REQUIRE Triangle tensors $\Tensor{\bigtriangleup}_G, \Tensor{\bigtriangleup}_H$;   Sequence similarities $\Vector{w}$; Shift parameter $\alpha$
%\ENSURE The best topological scores $\Matrix{X}$ from any iteration
%\STATE $k = 0$ \COMMENT{Iteration number}
%\STATE $\Vector{w} \leftarrow \Vector{w}/\|\Vector{w} \|$
%\STATE $\Vector{x_0} = \Vector{w}$
%\STATE $t_0 = 0$
%\REPEAT
%\STATE $\tilde{\Vector{x}}_{k+1} = \textbf{impTTV}(\Tensor{\bigtriangleup}_G, \Tensor{\bigtriangleup}_H, \Vector{x}_k)$ 
%\STATE $\lambda_{k+1} = \Vector{x}_{k}^{T} \tilde{\Vector{x}}_{k+1}^{} $
%\STATE $\hat{\Vector{x}}_{k+1} = \tilde{\Vector{x}}_{k+1} + \alpha \Vector{x}_{k} $ 
%\STATE $\Vector{x}_{k+1} = \frac{\hat{\Vector{x}}_{k+1}}{\| \hat{\Vector{x}}_{k+1} \|}$
%\STATE $\Matrix{X}_{k+1} = \bf{unvec}(\Vector{x}_{k+1})$
%\STATE $ t_{k+1} =  \bf{score}(\Matrix{X}_{k+1})$
%\STATE Update $(\Matrix{X}, t)_{\text{best}}$ to $(\Matrix{X}, t)_{k+1}$ if $t_{k+1} > t_{\text{best}}$
%\STATE $k = k+1$
%\UNTIL {$\lambda_k - \lambda_{k-1}$ is small or the max iteration is hit}
%\RETURN $\Matrix{X}_{\text{best}}$
%\end{algorithmic}
%
%Inspired from \alert{Shifted Symmetric Higher-Order Power Method (SS-HOPM)}
%\end{frame}
%
%
%
%
%\begin{frame}{Convergence Behavior}
%
%\begin{figure}[!t]
%\centering
%\subfigure[Iteration 1]{\includegraphics[width=.19\textwidth]{figures/TAME/X1}%
%\label{fig:NAPA_X1}}
%\hfil
%\subfigure[Iteration 2]{\includegraphics[width=.19\textwidth]{figures/TAME/X2}%
%\label{fig:NAPA_X2}}
%\hfil
%\subfigure[Iteration 3]{\includegraphics[width=.19\textwidth]{figures/TAME/X3}%
%\label{fig:NAPA_X3}}
%\hfil
%\subfigure[Iteration 4]{\includegraphics[width=.19\textwidth]{figures/TAME/X4}%
%\label{fig:NAPA_X4}}
%\hfil
%\subfigure[Iteration 5]{\includegraphics[width=.19\textwidth]{figures/TAME/X5}%
%\label{fig:NAPA_X5}}
%
%\subfigure[Iteration 6]{\includegraphics[width=.19\textwidth]{figures/TAME/X6}%
%\label{fig:NAPA_X6}}
%\hfil
%\subfigure[Iteration 7]{\includegraphics[width=.19\textwidth]{figures/TAME/X7}%
%\label{fig:NAPA_X7}}
%\hfil
%\subfigure[Iteration 8]{\includegraphics[width=.19\textwidth]{figures/TAME/X8}%
%\label{fig:NAPA_X8}}
%\hfil
%\subfigure[Iteration 9]{\includegraphics[width=.19\textwidth]{figures/TAME/X9}%
%\label{fig:NAPA_X9}}
%\hfil
%\subfigure[Iteration 10]{\includegraphics[width=.19\textwidth]{figures/TAME/X10}%
%\label{fig:NAPA_X10}}
%
%\subfigure[Iteration 11]{\includegraphics[width=.19\textwidth]{figures/TAME/X11}%
%\label{fig:NAPA_X11}}
%\hfil
%\subfigure[Iteration 12]{\includegraphics[width=.19\textwidth]{figures/TAME/X12}%
%\label{fig:NAPA_X12}}
%\hfil
%\subfigure[Iteration 13]{\includegraphics[width=.19\textwidth]{figures/TAME/X13}%
%\label{fig:NAPA_X13}}
%\hfil
%
%\end{figure}
%
%\end{frame}
%
%
%\begin{frame}{Aligning Yeast vs Human Interactomes}{Topological validation}
%\begin{columns}[c]
%\column{0.45\textwidth}
%\includegraphics[width=\columnwidth]{figures/TAME/Edges}
%
%\column{0.45\textwidth}
%\includegraphics[width=\columnwidth]{figures/TAME/Tris}
%\end{columns}
%\end{frame}
%
%\begin{frame}{Aligning Yeast vs Human Interactomes}{Timing}
%\begin{columns}[c]
%\column{0.5\textwidth}
%\includegraphics[width=\columnwidth]{figures/TAME/Timing}
%
%\column{0.5\textwidth}
%\begin{itemize}
%\item SeqSim $\leq 1s$
%\item GHOST $\sim 611$ days!
%\end{itemize}
%
%\end{columns}
%
%\end{frame}
%
%
%\begin{frame}{Aligning Yeast vs Human Interactomes}{Biological validation}
%\begin{center}
%\includegraphics[width=0.9\textwidth]{figures/TAME/ConservedEdges_CoExpr_full}
%\end{center}
%\end{frame}
%
%
%\begin{frame}{Future Work}
%
%\begin{itemize}
%\item Extend this framework to general motifs
%\end{itemize}
% 
%\end{frame}


\section{Part III: Deconvolving expression profiles of complex tissues}
\begin{frame}{Constructing tissue-specific interactome}
 \tableofcontents
    [
        currentsection,
        currentsubsection,
        subsectionstyle=show/shaded/hide
    ]
\end{frame}


\begin{frame}{Motivation}
Tumor heterogeneity, including its internal diversity, as well as interaction with surrounding microenvironment, is one of the most fundamental determinants of treatment response, drug resistance, and patient relapse.

    \begin{center}
		\includegraphics[height=0.6\textheight]{figures/Decon/liver_cancer}\\
		\tiny Adopted from Moffitt \textit{et al.}, 2015
    \end{center}  
\end{frame}

\begin{frame}{Deconvolution: Formal Definition}{Notation}
\alert{Goal:} To decompose a heterogeneous expression profile into its purified cell types

\vspace{1em}

\begin{columns}
\column{.45\textwidth}
\includegraphics[width=\columnwidth]{figures/Decon/decon_mat}
\column{.45\textwidth}
\begin{itemize}
\item $\Matrix{M} \in \R^{n \times p}$: Expression matrix of mixed samples

\item $\Matrix{G} \in \R^{n \times q}$: Reference signature matrix of primary cell types.

\item $\Matrix{C} \in \R^{q \times p}$: Relative proportions of each cell-type in mixture 
samples. 
\end{itemize}
\end{columns}

\end{frame}


\begin{frame}{Deconvolution: Formal Definition}{Problem definition}	
Given an observed mixture matrix $\Matrix{M}$, find optimal $\Matrix{G}$ and $\Matrix{C}$	that approximate mixture matrix as closely as possible, according to a distance function $\delta$, while satisfying a set of desired constraints:

\begin{block}{Objective}
	\begin{equation*}
	\min_{\Matrix{G}, \Matrix{C} \in \mbox{\tiny{feasible region}}} \bs{\delta}(\Matrix{G}\Matrix{C}, \Matrix{M}) 
	\end{equation*}	
\end{block}


%	\begin{figure}
%	\centering
%	\includegraphics[width=.6\columnwidth]{figures/Decon/BCD}\\
%	\caption {\color{red} Block Coordinate Descent (BCD)}
%	\end{figure}

\end{frame}


\begin{frame}{Deconvolution: Formal Definition}{Scope of this study}
\alert{Goal:} To systematically evaluate different configurations and their performance in gene expression deconvolution


\vspace{1em}

\begin{itemize}
\item Different loss functions for evaluating estimation error
\item Constraints on solutions
\item Preprocessing and data filtering
\item Feature selection
\item Regularization
\end{itemize}

\end{frame}



\begin{frame} {Loss functions}

\begin{columns}
\begin{column}{0.5\textwidth}
\begin{figure}
\centering
\includegraphics[width=\columnwidth]{figures/Decon/LossPlot}
\end{figure}
\end{column}


\begin{column}{0.5\textwidth}

\begin{enumerate}
\item $\Loss_{2}(r_i) = r_i^2 = (y_i - \Vector{w}^T\Vector{x}_i)^2$\hfill

\item $\Loss_{1}(r_i)=|r_i| = |y_i - \Vector{w}^T\Vector{x}_i|$\hfill

\item $\Loss_{Huber}^{(M)}(r_i)=$\\ $\begin{cases}
r_i^{2}, & \mbox{if $|r_i|\leq M$}\\
M (2|r_i|- M), & \mbox{otherwise}
\end{cases}$\hfill

\item $\Loss_{\epsilon}^{(\epsilon)}(r_i)=$\\ $
\begin{cases}
0, & \mbox{if $|r_i| \leq \epsilon$}\\
|r_i|-\epsilon, & \mbox{otherwise}
\end{cases}$

\end{enumerate}
\end{column}
\end{columns}
\end{frame}




\begin{frame} {Regularizers}

\begin{itemize}
\item Shrinking/smoothing regression coefficients $\Vector{w}$:

\begin{equation*}
\Reg_2(\Vector{w}) = \parallel\Vector{w}\parallel_2^2 = \sum_{i=1}^{k} w_i^2.
\end{equation*}


\item Sparsifying solutions :
\begin{equation*}
\Reg_1(\Vector{w}) = \parallel\Vector{w}\parallel_1 = \sum_{i=1}^{k} |w_i|.
\end{equation*}

\end{itemize}
\end{frame}


\begin{frame}{Examples}{Some of existing combinations}

\begin{itemize}
\item Ordinary Least Squares (OLS):
\begin{eqnarray*}
\bs{\min}_{\Vector{w}} \{ \sum_{i=1}^m \Loss_2 (r_i) \} &=& \bs{\min}_{\Vector{w}} \{ \sum_{i=1}^m (y_{i}-\Vector{w}^{T}\Vector{x}_{i})^{2} \} \\ \nonumber
&=& \bs{\min}_{\Vector{w}}  \parallel y-\Matrix{X}\Vector{w}\parallel_{2}^{2}
\end{eqnarray*}

\item Least Absolute Selection and Shrinkage Operator (LASSO) Regression:
\begin{alignat*}{2}
&\bs{\min}_{\Vector{w}} \{ \sum_{i=1}^m \Loss_2 (r_i)  + \lambda \Reg_1(\Vector{w})\}&\\
&= \bs{\min}_{\Vector{w}} \parallel y-\Matrix{X}\Vector{w}\parallel_{2}^{2} + \lambda \parallel \Vector{w}\parallel_{1}&
\end{alignat*}

\item Support Vector Regression (SVR):
\begin{equation}
\bs{\min}_{\Vector{w}} \{ \sum_{i = 1}^m \mathcal{L}_{\epsilon}(y_{i}-\Vector{w}^T\Vector{x}_{i})  +  \lambda \Reg_2(\Vector{w})  \}
\label{eq:SVR_primal_alt}
\end{equation}
\end{itemize}
\end{frame}


\begin{frame}{Constraints}

\begin{itemize}
\item Non-negativity (NN)
\item Sum-to-one (STO)
\item Similar cell quantity (SCQ)
\end{itemize}
\end{frame}



\begin{frame}{Selecting genes to include in basis matrix}
Updating $\Matrix{C}$ is highly over-determined. We try to select genes to simultaneously minimize noise and enhance conditioning of the basis matrix $\Matrix{G}$:

\begin{itemize}
\item Range filtering
\item Marker selection
\end{itemize}

\begin{block}{New criteria: Sum-To-One (STO) violations}
\begin{itemize}
\item \alert{Violating reference gene}: 
\begin{equation*}
\Vector{m}(i) \leq \Matrix{G}_{min}(i); \forall 1 \leq i \leq n
\end{equation*}

\item \alert{Violating mixture gene}: 
\begin{equation*}
\Matrix{G}_{max}(i) \leq \Vector{m}(i); \forall 1 \leq i \leq n 
\end{equation*}
\end{itemize}
\end{block}

\end{frame}



\begin{frame}{Summary of results}

We performed comprehensive, unbiased evaluation for all combinations of these factors on the following datasets:

\begin{center}
\begin{tabular}{l|c|c|c}
Dataset	&\# features	&\# samples	&\# references\\ \hline
BreastBlood	&54675	&9	&2\\
CellLines	&54675	&12	&4\\
LiverBrainLung	&31099	&33	&3\\
PERT\_Cultured	&22215	&2	&11\\
PERT\_Uncultured	&22215	&4	&11\\
RatBrain	&31099	&10	&4\\
Retina	&22347	&24	&2\\
\end{tabular}
\end{center}
\end{frame}


\begin{frame}{Summary of results}{Take home message}
\centering
\includegraphics[width=0.8\textwidth]{figures/Decon/combined_results}

\begin{itemize}
\item With the right choice of preprocessing and objective function, we can limit error levels in all test datasets
\end{itemize}
\end{frame}



\begin{frame}{Summary of results}{Key observation}
Selecting the \alert{"right" set of genes} for deconvolution has one of the \alert{strongest effects} on the overall deconvolution performance.

\begin{figure}
\centering
\includegraphics[width=.75\textwidth]{figures/Decon/gene_class}
\end{figure}

\begin{itemize}
\item Selecting genes that are not:
\begin{itemize}
\item Time-dependent, such as cell cycle genes.
\item Microenvironment-dependent factors, such as genes involved in cell signaling pathways.
\end{itemize}
\end{itemize}
\end{frame}




\begin{frame}{Forthcoming Results}{Use single-cell profiles as basis for deconvolution}
\begin{block}{Motivation}
\begin{itemize}
\item Bulk-tissue RNA-seq profiling is still more cost effective and the preferred choice for large population studies.
\item Fresh specimens needed for single-cell profiling is not always available (for example in archived formalin fixed paraffin embedded (FFPE) tissue samples).
\item There is a significant body of knowledge in existing databases using bulk-tissue profiling. 
\end{itemize}
\end{block}

\end{frame}


\begin{frame}

Thank you!

\end{frame}

\end{document}

\begin{frame}{Future directions}{Use single-cell profiles as basis for deconvolution-- Sketch of the method}
Joint project with Yu Li @MIT.

\begin{itemize}
\item Bulk and single-cell each have their own unique signatures in their measurements.
\item Unlike \textit{BSEQ-sc}, we first aim to develop a deep-learning technique to map expression profiles from single-cell space to their corresponding bulk, purified projection.
\item We use projected profiles as an initial estimate of $\Matrix{G}$ and jointly estimate $\Matrix{C}$ and update $\Matrix{G}$.
\end{itemize}


\end{frame}


\begin{frame}{Future directions}{Hierarchical deconvolution}
\alert{Challenge}: Emergence of complex underlying structure as we increase the total number cell types.

\begin{itemize}
\item Infer a hierarchy for cell types, first.
\item Use parent(s) of each node as a prior.
\item Orthogonalize cell types w.r.t. the prior of all ancestor cells.
\item Deconvolve each layer with the residual subspace.
\end{itemize}


\end{frame}


%
%\begin{frame}{Feature Selection}
%
%\centering
%\includegraphics[width=0.8\columnwidth]{figures/Decon/fixed_Delta_mAD.pdf}
%
%\begin{itemize}
%\item Feature selection enhances deconvolution quality when references are collected from other labs. 
%\end{itemize}
%\end{frame}






\end{document}


\begin{frame} {Acknowledgement}
\begin{columns}[c]
    \column{.25\textwidth}
	\textbf{Advisors}
	
    \column{.25\textwidth}
	\textbf{Visiting labs}
		
    \column{.45\textwidth}
	\textbf{Colleagues}
\end{columns}

\vspace{1em}

\begin{columns}[c]
    \column{.25\textwidth}
	\includegraphics[height=0.3\textheight]{figures/photos/ananth}\\
	\includegraphics[height=0.3\textheight]{figures/photos/wojtek}
	
    \column{.25\textwidth}
	\includegraphics[height=0.3\textheight]{figures/photos/shankar}\\
	\includegraphics[height=0.3\textheight]{figures/photos/andrea}
	
    \column{.45\textwidth}
	\includegraphics[width=0.45\columnwidth]{figures/photos/david}
	\includegraphics[width=0.45\columnwidth]{figures/photos/tamara}
	\\
	\includegraphics[width=0.45\columnwidth]{figures/photos/neta}
	\includegraphics[width=0.45\columnwidth]{figures/photos/vikram}		
\end{columns}

\end{frame}


\begin{frame}[allowframebreaks]
  \frametitle<presentation>{Relevant Publications}
    
  \begin{thebibliography}{10}
    
%  \beamertemplatebookbibitems
 
  \beamertemplatearticlebibitems

\bibitem{Kavosh}
Z.~R.~M. Kashani, H.~Ahrabian, E.~Elahi, A.~Nowzari-Dalini, E.~S. Ansari,
  S.~Asadi, \textbf{S.~Mohammadi}, F.~Schreiber, and A.~Masoudi-Nejad (2009)
  \href{http://www.biomedcentral.com/1471-2105/10/318/}{Kavosh: a new algorithm
  for finding network motifs.}
\newblock \emph{BMC bioinformatics}, \textbf{10}(318).

\bibitem{AlignmentChapter}
\textbf{S.~Mohammadi} and A.~Grama (2011)
  \href{http://www.springerlink.com/content/t18030hh8x02w635/fulltext.pdf}{Biological
  Network Alignment}.
\newblock In M.~Koyut\"{u}rk, S.~Subramaniam, and A.~Grama (eds.),
  \emph{Functional Coherence of Molecular Networks in Bioinformatics},
  Springer, pages 97--136.

\bibitem{NSD}
G.~Kollias, \textbf{S.~Mohammadi}, and A.~Grama (2011)
  \href{http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=5975146}{Network
  Similarity Decomposition (NSD): A Fast and Scalable Approach to Network
  Alignment}.
\newblock \emph{IEEE Transactions on Knowledge and Data Engineering (TKDE)},
  \textbf{24}(12):2232--2243.

\bibitem{SGA}
\textbf{S.~Mohammadi}, G.~Kollias, and A.~Grama (2012)
  \href{http://psb.stanford.edu/psb-online/proceedings/psb12/abstracts/2012\_p43.html}{Role
  of Synthetic Genetic Interactions in Understanding Functional Interactions
  Among Pathways}.
\newblock In \emph{Pacific Symposium on Biocomputing (PSB)}.

\bibitem{FastAlign}
G.~Kollias, M.~Sathe, \textbf{S.~Mohammadi}, and A.~Grama (2013)
  \href{http://www.ncbi.nlm.nih.gov/pubmed/23363457}{A fast approach to global
  alignment of protein-protein interaction networks.}
\newblock \emph{BMC research notes}, \textbf{6}(1):35.

\bibitem{TOR_paper}
\textbf{S.~Mohammadi}, S.~Subramaniam, and A.~Grama (2013)
  \href{http://www.biomedcentral.com/1752-0509/7/84}{{Inferring the Effective
  TOR-Dependent Network: A Computational Study in Yeast}}.
\newblock \emph{BMC Systems Biology}, \textbf{7}(1):84.

\bibitem{scvshs}
\textbf{S.~Mohammadi}, B.~Saberidokht, S.~Subramaniam, and A.~Grama (2015)
  \href{https://bmcsystbiol.biomedcentral.com/articles/10.1186/s12918-015-0253-0}{{Scope
  and limitations of baker's yeast as a model organism for studying human
  tissue-specific pathways}}.
\newblock \emph{BMC Systems Biology}, \textbf{96}(9).

\bibitem{TAME}
\textbf{S.~Mohammadi}, D.~F. Gleich, T.~G. Kolda, and A.~Grama (2016)
  \href{http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=7524736}{{Triangular
  Alignment (TAME): A Tensor-based Approach for Higher-order Network
  Alignment}}.
\newblock \emph{IEEE/ACM Transactions on Computational Biology and
  Bioinformatics (TCBB)}.


\bibitem{ActPro}
\textbf{S.~Mohammadi} and A.~Grama (2016)
  \href{http://bioinformatics.oxfordjournals.org/lookup/doi/10.1093/bioinformatics/btw245}{{A
  convex optimization approach for identification of human tissue-specific
  interactomes}}.
\newblock \emph{Bioinformatics}, \textbf{32}(12):i243--i252.

\bibitem{ACTION_kernel}
\textbf{S.~Mohammadi} and A.~Grama (2016)
  \href{http://dl.acm.org/citation.cfm?doid=10.1145/2975167.2975193}{{De novo
  identification of cell type hierarchy with application to compound marker
  detection}}.
\newblock In \emph{Proceedings of the International Conference on
  Bioinformatics, Computational Biology and Biomedical Informatics - BCB'16}.
  pages 251--261.


\bibitem{Deconvolution_CEstim}
\textbf{S.~Mohammadi}, N.~Zuckerman, A.~Goldsmith, and A.~Grama (2016)
  \href{https://arxiv.org/abs/1510.04583}{{A Comprehensive Survey of
  Deconvolution Methods for Separating Cell types in Complex Tissues}}.
\newblock \emph{Proceedings of IEEE, Special Issue on Principles and Applications of Science
  of Information}.
  
\bibitem{PubMed}
\textbf{S.~Mohammadi}, S.~Kylasa, G.~Kollias, and A.~Grama (2016) {A
  Context-specific Recommendation System for Predicting Similar PubMed
  Articles}.
\newblock In \emph{IEEE ICDM Workshop on Semantics-Enabled Recommender System}.

\bibitem{ACTION_report}
\textbf{S.~Mohammadi}, V.~Ravindra, D.~Gleich, and A.~Grama (2016) Take ACTION
  to identify high resolution cell types and associated transcriptional
  pathways.
\newblock Tech report on \emph{bioRxiv}.



  \end{thebibliography}
\end{frame}

\begin{frame}{Questions?}

\includegraphics[width=0.9\textwidth]{figures/questions}
\end{frame}


\end{document}

