\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}
\usepackage{subfigure}



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

\newcommand{\bs}[1]{\boldsymbol{#1}}
\newcommand{\A}{\bs{\mathcal{A}}}
\newcommand{\x}{\bs{x}}
\newcommand{\e}{\bs{e}}
\newcommand{\PI}{\bs{\pi}}
\newcommand{\one}{\bs{1}}

\newcommand{\R}{\bs{\mathcal{R}}}
\newcommand{\G}{\mathcal{G}}
\newcommand{\V}{\mathcal{V}}
\newcommand{\E}{\mathcal{E}}

\newcommand{\Square}{\bs{\mathcal{S}}}
\newcommand{\Overlap}{\bs{\mathcal{O}}}
\newcommand{\Weight}{\bs{\mathcal{W}}}
\newcommand{\w}{\bs{w}}



\title[Tissue-Specific Networks] % (optional, use only with long paper titles)
{A systems approach to dissecting the tissue-specific architecture of cellular
networks}


\author[Grama et al.] % (optional, use only with lots of authors)
{Ananth Grama}

\institute[Purdue University] % (optional, but mostly needed)
{
  Center for Science of Information\\
  Purdue University
}


\date[Colombia 2015] % (optional, should be abbreviation of conference name)
{Colombia 2015}


\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
\begin{center}
{\tiny Work with S. Mohammadi (Purdue), S. Subramaniam (UCSD), \\
and G. Kollias (IBM)}
\end{center}
\end{frame}

%\begin{frame}
%\vspace*{-0.3in}
%\begin{center}
%        \includegraphics[height=2.7in,angle=-90]{all.pdf}
%\end{center}
%\end{frame}

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



\section{Part 1: Motivation -- Constructing aging pathways in yeast}
\subsection{Overview}
\begin{frame}{Yeast Aging}
  \begin{columns}[c]
    \column{.4\textwidth}
    \begin{center}
		\includegraphics[width=\columnwidth]{figures/bacterial-growth}\\
		\tiny{Courtesy of Alper Uzan, PhD.}
    \end{center}
	  
    \column{.6\textwidth}
		\begin{itemize}
			\item Yeast as a model organism for aging research:
			\begin{itemize} [label={\checkmark}]
				\item Rapid growth
				\item Ease of manipulation
			\end{itemize}			
			\item \alert{Replicative life-span (RLS): } the number of buds a mother cell can produce before senescence occurs
			\item \alert{Chronological life-span (CLS): } duration of viability 
after entering the stationary-phase
		\end{itemize}
  \end{columns}  

\end{frame}





\subsection{Materials and Methods}
\subsubsection{Datasets}
\begin{frame}{Yeast Interactome}
  \begin{columns}[c]
    \column{.4\textwidth}
    \begin{center}
		\includegraphics[width=.8\columnwidth]{figures/Integration}\\
		\includegraphics[width=\columnwidth]{figures/Interactome}\\
    \end{center}
	  
    \column{.6\textwidth}
		\begin{itemize}
		\item \textit{Mixed network: } Contains both directed (biochemical activities) and undirected (protein-protein interactions) edges
		\item 103,619 (63,395 non-redundant) physical interactions among 5,691 proteins.
		\item 5,791 (5,443 non-redundant) biochemical activities (mostly phosphorylation events) among 2,002 kinase-substrate pairs.
	\end{itemize}
  \end{columns}  
\end{frame}


\begin{frame}{Transcriptional regulatory network (TRN) of yeast}
	\begin{itemize}
		\item Directed graph
		\item Downloaded from the Yeast Search for Transcriptional Regulators And Consensus Tracking (YEASTRACT)
		\item Consists of 48,082 interactions between 183 transcription factors (TF) and 6,403
target genes (TG).	
	\end{itemize}
\end{frame}


\begin{frame}{Rapamycin-treatment dataset}
  \begin{columns}[c]
    \column{.25\textwidth}
	\includegraphics[height=.8\textheight]{figures/Rapamycin}\\
	\tiny{Adopted from Fournier et al., 2010}
	  
    \column{.75\textwidth}
		\begin{itemize}
		\item \textbf{Rapamycin}: A lipophilic macrolide that directly binds to and inhibits TOR \textit{in vivo}
		\item Temporal analysis of gene expression changes for 6,000 ORFs in Baker's yeast, \textit{Saccharomyces cerevisiae}, over 6h of rapamycin treatment.
		\item 366 repressed and 291 induced genes at a minimum threshold of 2-fold change.
	\end{itemize}
  \end{columns}  
\end{frame}





\subsubsection{Tracing Information Flow}

\begin{frame}{Directional information flow}{Random walk}
	\begin{definition}
	\alert{Random walk} on a graph $G$, initiated from vertex $v$, is the sequence of transitions among vertices, starting from $v$. At each step, the random walker randomly chooses the next vertex from among the neighbors of the current node.
	\end{definition}

It is a Markov chain with the transition matrix $P$, where $p_{ij} = Prob(S_{n+1} = v_i|S_{n} = v_j)$ and random variable $S_n$ represents the state of the random walk at the time step $n$. 
\end{frame}


\begin{frame}{Directional information flow}{Random walk with restart}

	\begin{definition}
	\alert{Random walk with restart (RWR)} is a modified Markov chain in which, at each step, a random walker has the choice of either continuing along its path, with probability $\alpha$, or jump (teleport) back to the initial vertex, with probability $1-\alpha$.
	\end{definition}
The transition matrix of the modified chain, $M$, can be computed as $M = \alpha P + (1-\alpha) \e_v \one^T$, where $\e_v$ is a stochastic vector of size $n$ having zeros everywhere, except at index $v$, and $\one$ is 
a vector of all ones.
\end{frame}


\begin{frame}{Directional information flow}{Stationary distribution}
The portion of time spent on each node in an infinite random walk with restart 
initiated at node $v$, with parameter $\alpha$.

	\begin{definition}
	\alert{Stationary distribution} of the modified chain
		\begin{eqnarray*}
			\PI_v(\alpha) &=& M \PI_v(\alpha) \nonumber \\
			&=& (\alpha P + (1-\alpha) \e_v \one^T) \PI_v(\alpha)
		\end{eqnarray*}
	\end{definition}

Enforcing a unit norm on the dominant eigenvector to ensure its stochastic property, 
$\parallel \PI_v(\alpha) \parallel_1 = \one^T\PI_v = 1$, we will have:
\end{frame}


\begin{frame}{Directional information flow}{Stationary distribution--continue}
	\begin{definition}
	\alert{Iterative form} of the information flow process:
		\begin{eqnarray*}
			\PI_v(\alpha) &=& \alpha P \PI_v(\alpha) + (1-\alpha) \e_v,
		\end{eqnarray*}
	\end{definition}

	\begin{definition}
	\alert{Explicit (direct) formulation} of the information flow process:
		\begin{eqnarray*}
			\PI_v(\alpha) &=& \underbrace{(1-\alpha)(I - \alpha P)^{-1}}_{Q} \e_v,
		\end{eqnarray*}
	\end{definition}
\end{frame}

\begin{frame}{Directional information flow}{Interpretation}

	\begin{definition}
		Expansion using the Neumann series:		
		\begin{eqnarray*}
			\PI_v(\alpha) &=& (1-\alpha) \sum_{i=0}^{\infty} (\alpha P)^i \e_v
		\end{eqnarray*}
	\end{definition}
	
	Thus, $\PI_v(\alpha)$ is a function of:
	\begin{itemize}
		\item Distance to source node ($v$)
		\item Multiplicity of paths
	\end{itemize}
\end{frame}



\begin{frame} {Sidebar: Functional PageRank (PR)}
\small{ 
{\bf Computing PageRank (PR)}
 \begin{itemize}
\item PageRank as a \emph{random surfer process}: Start surfing from a random node and keep following links with probability $\mu$ restarting  with probability $1 - \mu$; the node for restarting will be selected based on a personalization vector $v$. The ranking value $x_i$ of a node $i$ is the probability of visiting this node during surfing.
\item PR can also be cast in power series representation as
$x =  (1-\mu) \sum_{j=0}^k \mu^{j} S^j v$; $S$ encodes column-stochastic adjacencies.
  \end{itemize}
}

\small{
{\bf Functional rankings} 
 \begin{itemize}
 \item A general method to assign ranking values to graph nodes as $x =  \sum_{j=0}^k \zeta_j S^j v$. PR is a functional ranking, 
$\zeta_j = (1-\mu) \mu^j$.
\item Terms attenuated by outdegrees in $S$ \emph{and} damping coefficients $\zeta_j$.
  \end{itemize}
}
\end{frame}




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
  \frametitle{Functional Rankings Through Multidamping [Kollias, Gallopoulos, AG, TKDE'13]}
%\textbf{Q:} Is there a way to encode functional rankings as surfing processes?\\
%\textbf{A: Multidamping}
\small{
  \begin{columns}[t]    
    \begin{column}{4.cm}
      \begin{figure}[tbh]
        \centering
        \includegraphics[scale=0.5]{figures/montecarlo.pdf}
      \end{figure}
    \end{column}
   
    \begin{column}{7.2cm}
      \begin{block}{Computing $\mu_j$ in multidamping}
        Simulate a functional ranking by random surfers following emanating links with probability $\mu_j$ at step $j$ given by : \\
        
$\mu_{j} = 1  -\frac{1}{1+\frac{\rho_{k-j+1}}{1-\mu_{j-1}}}, j = 1, ..., k,$ \\
$\text{where } \mu_0 = 0$ and $\rho_{k-j+1} =
        \frac{\zeta_{k-j+1}}{\zeta_{k-j}}$
      \end{block}
    \end{column}
  \end{columns}
}

\footnotesize{
\textbf{Examples}\\
\emph{LinearRank (LR)}  
$ x^{\rm LR} =\sum_{j=0}^{k}  \frac{2(k+1-j)}{(k+1)(k+2)}  S^j v$ :
$\mu_j = \frac{j}{j+2}, j = 1, ..., k $.\\
\emph{TotalRank (TR)} 
$x^{\rm TR} = \sum_{j=0}^\infty \frac{1}{(j+1)(j+2)} S^j v$ :
$\mu_j = \frac{k-j+1}{k-j+2}, j =1, ..., k $.
}

\end{frame}
\begin{frame}
  \frametitle{Multidamping and Computational Cost}

{\bf Advantages of multidamping}

\begin{itemize}
\item Interpretability and Design!
\item Reduced computational cost in \emph{approximating} functional rankings using the Monte Carlo approach. A random surfer terminates with probability $1 - \mu_j$ at step $j$.
\item Inherently parallel and synchronization free computation.
\end{itemize}

\end{frame}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
  \frametitle{Multidamping Performance}
\footnotesize{ 
 \begin{columns}[t]    
    \begin{column}{4.cm}
      \begin{figure}[h]
        \includegraphics[width=1.0\textwidth]{figures/tau-TR-1000-crop.pdf}
      \end{figure}
    \end{column}
    \begin{column}{4.cm}
      \begin{figure}[h]
        \includegraphics[width=1.0\textwidth]{figures/shared-LR-20-crop.pdf}
        \end{figure}
      \end{column}
  \end{columns}

{\small
\textbf{Approximate ranking:}
  Run $n$ surfers to completion for graph size $n$. 
  How well does the computed ranking capture the ``reference'' ordering for
$\texttt{top-}k$ nodes, compared to standard iterations of equivalent computational
cost/number of operations? \emph{[Left]}\\

\textbf{Approximate personalized ranking:}
 Run less than $n$ surfers to completion (each called a microstep, x-axis), from a
 selected node (personalized). How well can we capture the ``reference'' $\texttt{top-}k$
 nodes, i.e., how many of them are shared (y-axis),
 compared to the simple approach? \emph{[Right]}
}\\
}
%\scriptsize{[\textsf{uk-2005}: $39,459,925$ nodes, $936,364,282$ edges. 
%\textsf{in-2004}: $1,382,908$ nodes, $16,917,053$ edges]}

\end{frame}





\subsection{Results and Discussion}

\begin{frame}{Experimental settings}
We set the \alert{preference vector} as:
\begin{equation*}
e_{\mathcal{S}}(i) = \begin{cases} \frac{1}{|\mathcal{S}|} & \text{if $v_i \in \mathcal{S}$,}
\\
0 &\text{O.W.}
\end{cases}
\end{equation*}


for $\mathcal{S}$ being the subset of vertices in the yeast interactome corresponding to members of the TORC1 protein complex. The diameter of the network is computed to be $6$ and \alert{$\alpha$ parameter} is set to $\frac{d}{d+1}=\frac{6}{7} \sim 0.85$ accordingly to give all nodes a fair chance of being visited.


\end{frame}


\begin{frame}{Distribution of information flow scores}
\scriptsize Distribution of information flow scores across nodes with similar distance from members of TORC1 are color coded accordingly. The $\mu$ parameter is the average of information flow scores for nodes under each distribution.
\begin{center}
	\includegraphics[height=.6\textheight]{figures/ScoreDistribution}\\
\end{center}
\end{frame}


\begin{frame}{Enrichment map of yeast GOslim terms}
\scriptsize Enriched terms are identified by mHG p-value, computed for the ranked-list of genes based on their information flow scores. Each node represents a significant GO term and edges represent the overlap between genesets of GO terms. Terms in different branches of GO are color-coded with red, green, and blue. Color intensity of each node represents the significance of its p-value, while the node size illustrates the size of its geneset. Thickness of edges is related to the extent of overlap among genesets.
\begin{center}
	\includegraphics[height=.6\textheight]{figures/EM}\\
\end{center}
\end{frame}



\begin{frame}{TOR-dependent control of transcription initiation}
\scriptsize Induced subgraph in the yeast interactome, constructed from the top-ranked genes in the information flow analysis that are annotated with the transcription initiation GO term. Different functional subunits are marked and color-coded appropriately.
\begin{center}
	\includegraphics[height=.6\textheight]{figures/TransInit}\\	
\end{center}
\end{frame}


\begin{frame}{Enrichment plot for Rapamycin-treatment dataset}
\scriptsize Enrichment score as a function of the score percentage. Computations are based on the set of differentially expressed genes in response to Rapamycin treatment. The peak of plot occurs at around
top 15\% of scores, resulting in the minimum hypergeometric (mHG) score  of $\sim 1e-22$. The exact p-value for this score is computed, using dynamic programing, to be $3.3e-19$.

\begin{center}
	\includegraphics[height=.55\textheight]{figures/EnrichmentPlot}\\	
\end{center}
\end{frame}


\begin{frame}{TORC1-dependent regulation of Gap1}
\scriptsize The schematic diagram is based on literature evidence for the interactions. Each node in the signaling pathway is annotated with the rank of its information flow score from TORC1. Ranking of nodes based on their information flow scores respect our prior knowledge on the structure of this pathway.
\begin{center}
	\includegraphics[height=.6\textheight]{figures/Gap1}\\	
\end{center}
\end{frame}




\section{Part 2: Tissue Specific Networks and Comparative Analysis}
\subsection{Motivation}
\begin{frame}{Comparative Network Analysis}{Traditional approach}

\begin{block}{Key Challenge}
  \begin{columns}[c]
    \column{.35\textwidth}
	\includegraphics[width=\columnwidth]{figures/eur-vitruvian_man}

    \column{.1\textwidth}
	\centering \huge
	$\Longleftrightarrow$
			  
    \column{.35\textwidth}
	\includegraphics[width=\columnwidth]{figures/yeast_yellow}

  \end{columns}  
\end{block}
\centering
  To project functional pathways from a well-studied organism, such as yeast, back to a higher-order organism, such as humans.
\end{frame}





%\section{Motivation}
\begin{frame}{Yeast as a key model organism}{Simple yet powerful}
  \begin{columns}[c]
    \column{.35\textwidth}
    \begin{center}
		\includegraphics[width=\columnwidth]{figures/yeast_yellow.jpg}\\
    \end{center}
	  
    \column{.65\textwidth}
"... yeast has graduated from a position as the premier model for eukaryotic cell biology to become the pioneer organism that facilitated the establishment of entirely new fields of study called \textit{functional genomics} and \textit{systems biology}." -- D. Botstein and G. Fink (2011). 
  \end{columns}  
\end{frame}



\begin{frame}{Yeast as a key model organism}{Why yeast?}
    \begin{itemize}
	    \item Rapid growth and ease of manipulation
	    \item Mature genetic and molecular toolbox, including deletion mutants, over-expression libraries, and green fluorescent protein (GFP)-tagged yeast strains	    
		\item Multitude of high-throughput datasets, ranging from genetic arrays, transcriptome, proteome, and metabolome profiles
    	\item Saccharomyces Genome Database (SGD)
		\flushright\includegraphics[width=.3\columnwidth]{figures/SGD3.jpg}\\
    \end{itemize}
\end{frame}



\begin{frame}{Conserved pathways between yeast and higher-order organisms}
\small
    Many of the underlying functionalities and associated machineries are shared
with higher eukaryotes:    
    \begin{itemize}
    	\item Cell cycle
    	\item Programmed cell death
    	\item Protein folding, quality control, and degradation
		\item Signaling pathways, such as MAPK, TOR, and insulin/IGF-I
		\item Aging and CR-mediated pathways
		\begin{itemize}
		\item \textbf{Chronological:} amount of time cells
survive in post-mitotic state
		\item \textbf{Replicative:} number of times a cell can divide before
senescence occurs.				
		\end{itemize}
    \end{itemize}
\end{frame}


\begin{frame}{Conserved pathways}{Continued}
    \begin{center}
		\includegraphics[height=0.75\textheight]{figures/CR.jpeg}\\	      
		\tiny{Fontana \textit{et al}, Science (2010)}
    \end{center}
\end{frame}






\begin{frame}{Yeast as a model organism for human disease}{recent success stories}
  \begin{columns}[c]
    \column{.3\textwidth}
    \begin{center}
		\includegraphics[width=\columnwidth]{figures/NAB.jpg}\\	      
		\tiny{Adopted from D. Tardiff \textit{et al.} (2013)}
    \end{center}
		
    \column{.7\textwidth}
	    \begin{itemize}
	    	\item Heterologous expression of disease gene(s)
	    	\item Yeast as an unbiased phenotypic screen
	    	\item N-aryl benzimidazole (NAB) strongly protects cells from $\alpha$-synuclein toxicity in the humanized yeast model
	    	\item Validated this discovery using iPS cell from Parkinson's patients with $\alpha$-Syn mutation
	    \end{itemize}
    \end{columns}
\end{frame}



\begin{frame}{Problem statement}

  \begin{columns}[c]
    \column{.3\textwidth}
		\alert{For which tissues is yeast a good model organism?}

    \column{.4\textwidth}
    \begin{center}
		\includegraphics[width=\columnwidth]{figures/tissue_types.jpg}\\	      
    \end{center}
		\tiny{Different human tissues, while inheriting a similar genetic code, exhibit unique anatomical and physiological properties.}
	

    \column{.3\textwidth}
		\alert{What are the shared/ missing functional components in yeast, compared to human tissues?}

	\end{columns}
\end{frame}




%-----------------------------------------------------------------------------------
%-----------------------------------------------------------------------------------
%						Materials and Methods
%-----------------------------------------------------------------------------------
%-----------------------------------------------------------------------------------
\subsection{Materials and methods}
\subsubsection{Datasets}
\begin{frame}{Tissue-specific gene expression}
The GNF Gene Atlas dataset:
  \begin{columns}[c]
    \column{.4\textwidth}
    \begin{center}
		\includegraphics[width=\columnwidth]{figures/BioGPS}\\
    \end{center}
	  
    \column{.6\textwidth}
		\begin{itemize}
			\item 79 different tissues
			\item 44,775 human transcripts
			\item Platforms:
			\begin{enumerate}
				\item Affymetrix HG-U133A.
				\item Custom GNF1H array.
			\end{enumerate}
		\end{itemize}
	\end{columns}		
\end{frame}


\begin{frame}{Tissue-specific interactomes}
	\begin{itemize}
		\item Vertex-induced subgraphs of the global human interactome
		\item Based on the GNF Gene Atlas dataset
		\begin{itemize}
			\item[$\Rightarrow$] A gene is considered as present in a tissue, if its normalized expression level is $> 200$ (average difference between match-mismatch pairs).
		\end{itemize}
	\end{itemize}
	
    \begin{center}
		\includegraphics[width=.8\textwidth]{figures/bossi}\\
		\tiny{Adopted from Bossi et al., 2009}
    \end{center}
\end{frame}


\begin{frame}{Sequence similarity of protein pairs}
\begin{itemize}
\item Protein sequences are downloaded from Ensembl database, release 69.
\item Reference genomes:
\begin{itemize}[label=$\triangleright$]
\item \textbf{Human}: GRCh37
\item \textbf{Yeast}: EF4
\end{itemize}
\item Number of protein sequences:
\begin{itemize}[label=$\triangleright$]
\item \textbf{Human}: 101,075
\item \textbf{Yeast}: 6,692
\end{itemize}
\item Low-complexity regions are masked using \textbf{pseg}
\item Smith-Waterman algorithm is used to compute local sequence alignments.
\end{itemize}
\end{frame}




\subsubsection{Algorithmic contributions}
\begin{frame}{Sparse network alignment}
\begin{center}
\small
\alert{Integer Quadratic Program}-- Approximated using Belief Propagation:

\begin{eqnarray*}
\label{eq:IQP}
\max_{\x} & & ( \alpha \w^T\x + \frac{\beta}{2}\mathbf{\x^T \Square \x} )\\
\hbox{Subject to:} & & \left\{
                       \begin{array}{ll}
                        \mathcal{C}\x \leq \mathbf{1}_{n_G*n_H}& \hbox{Matching constraints;} \\
                         x_{ii'} \in \{0, 1\}, & \hbox{Integer constraint.}
                       \end{array}
                     \right. \nonumber
\end{eqnarray*}
\end{center}
\tiny
\begin{itemize}
\item $\x$: Matching vector
\item $L$: Bipartite graph of similarities between pair of proteins in input networks
\item $\w$: Edge-weights in the graph $L$ (based on sequence similarities)
\item $\Square$: Matrix encoding conserved edges in the product graph ($G \otimes H$)
\item $\mathcal{C}$: Incidence matrix of graph $L$
\end{itemize}
\end{frame}





%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
  \frametitle{Sidebar: Network Alignment}
\small{
  \begin{columns}[h]
    \begin{column}{3.8cm}
      \includegraphics[width=\textwidth]{figures/match-graphs.pdf}
    \end{column}
    \begin{column}{5.8cm}
      \begin{itemize}
      \item
        \textbf{Node similarity:} Two nodes are similar if they are linked by other similar node pairs. By pairing similar nodes, the two graphs become \emph{aligned}.
      \end{itemize}
    \end{column}
  \end{columns}
\begin{itemize}
\item
Let $\tilde{A}$ and $\tilde{B}$ be the normalized adjacency matrices of the graphs (normalized by columns),
$H_{ij}$ be the independently known similarity scores (preferences matrix) of nodes $i \in V_B$ and
$j \in V_A$, and $\mu$ be the fractional contribution of topological similarity.
\item To compute $X$, IsoRank iterates:
$$
X \leftarrow \mu \tilde{B} X {\tilde{A}}^{T} + (1-\mu) H
$$
\end{itemize}
}
\end{frame}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\frametitle{Network Similarity Decomposition (NSD) 
[Kollias, Mohammadi, AG, TKDE'12]}
\small{
{\bf Network Similarity Decomposition (NSD)}
\begin{itemize}
\item
In $n$ steps of we reach
$X^{(n)} = (1-\mu) \sum_{k=0}^{n-1} \mu^{k} \tilde{B}^{k} H (\tilde{A}^{T})^{k} + \mu^{n} \tilde{B}^{n} H (\tilde{A}^{T})^{n}$ 
\item
Assume that $H=u v^T$ ($1$ component). Two phases for $X$:
\begin{enumerate}
\item
  $u^{(k)} = \tilde{B}^{k} u$ and $v^{(k)} = \tilde{A}^{k} v$ \emph{(preprocess/compute iterates)}
\item
  $X^{(n)} = (1-\mu) \sum_{k=0}^{n-1} \mu^{k} u^{(k)}{v^{(k)}}^{T} + \mu^{n}  u^{(n)}{v^{(n)}}^{T}$ \emph{(construct $X$)} 
\end{enumerate} 
This idea extends to $s$ components, $H \sim \sum_{i=1}^{s} w_i z_i^{T}$.
\item
NSD computes matrix-vector iterates and builds $X$ as a sum of outer products; these are much cheaper than triple matrix products.
\end{itemize} 

We can then apply Primal-Dual or Greedy Matching (1/2 approximation) to extract the actual node pairs.
}
\end{frame}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\frametitle{NSD: Performance 
[Kollias, Madan, Mohammadi, AG, BMC RN'12]}
{\tiny
\begin{columns}[c]
\begin{column}{4cm}
\begin{center}
\begin{tabular}[h]{lll}
\hline
\textbf{Species}	& \textbf{Nodes} & \textbf{Edges} \\ \hline
celeg (worm) 	& 2805	 & 4572 \\
dmela (fly) 	& 7518	 & 25830 \\
ecoli (bacterium)	& 1821	 & 6849 \\
hpylo (bacterium)	& 706	 & 1414 \\
hsapi (human)	& 9633	 & 36386 \\
mmusc (mouse)	& 290	 & 254 \\
scere (yeast) & 5499	 & 31898 \\
\end{tabular}
\end{center}
\end{column}

\begin{column}{7.2cm}
\begin{center}
\begin{tabular}[h]{|l|p{0.5cm}|p{0.6cm}|p{0.6cm}|p{0.6cm}|p{1cm}|}
\hline
\textbf{Species pair}	& \textbf{NSD (secs)} &   \textbf{PDM (secs)} & \textbf{GM (secs)} &  \textbf{IsoRank (secs)} \\ \hline
celeg-dmela &	 \textbf{3.15}           &    152.12      &   7.29      &	783.48  \\ \hline	
celeg-hsapi &    \textbf{3.28}           &    163.05      &   9.54      &	1209.28	\\ \hline
celeg-scere &    \textbf{1.97}           &    127.70      &   4.16      &	949.58	\\ \hline
dmela-ecoli &    \textbf{1.86}           &    86.80       &   4.78      &	807.93	\\ \hline
dmela-hsapi &    \textbf{8.61}           &    590.16      &   28.10     &	7840.00	\\ \hline
dmela-scere &    \textbf{4.79}           &    182.91      &   12.97     &	4905.00	\\ \hline
ecoli-hsapi &    \textbf{2.41}           &    79.23       &   4.76      &	2029.56	\\ \hline
ecoli-scere &    \textbf{1.49}           &    69.88       &   2.60      &	1264.24	\\ \hline
hsapi-scere &    \textbf{6.09}           &    181.17      &   15.56     &	6714.00	\\ \hline
\end{tabular}
\end{center}
\end{column}
\end{columns}
}
{\footnotesize
\begin{itemize}
\item
We compute similarity matrices $X$ for various pairs of species using Protein-Protein Interaction (PPI)
networks. $\mu = 0.80$, uniform initial conditions (outer product of suitably normalized $\mathrm{1}$'s
for each pair), $20$ iterations, one component. 
\item We then extract node matches using PDM and GM.
\item
\emph{Three orders of magnitude speedup} from \textsf{NSD}-based approaches compared to \textsf{IsoRank}. 
\end{itemize}
}
\end{frame}

\begin{frame}
\frametitle{NSD: Parallelization [KKG JPDC'14 (to appear)]}

\textbf{Parallelization:}
NSD has been ported to parallel and distributed platforms.
\begin{itemize}
\item We have aligned up to million-node graph instances using over 3K cores.
\item We process graph pairs of over a billion nodes and twenty billion edges each (!), on MapReduce-based
distributed platforms.
\end{itemize}

\end{frame}






\begin{frame}{Random model for tissue-specific networks}
\begin{definition}
\footnotesize
\begin{itemize}
\item \alert{Global human interactome:} All potential interactions between human proteins, represented by graph $G = (V_G, E_G)$
\item \alert{Tissue-specific network(s)}: Vertex-induced subgraph(s) of the Global human interactome,  represented by $G_T = (V_T, E_T)$ with $n_T= |V_T|$, $V_T \subset V_G$, and $E_T \subset E_G$
\item \alert{Universal genes}: Ubiquitously expressed subset of human genes corresponding to houskeeping functions, represented by $V_U \subset V_G$, and $n_U = |V_U|$
\item \alert{Random tissue-specific network(s)}: Vertex-induced subgraphs of $G$, constructed from $V_\mathcal{R} = V_U \cup V_\mathcal{S}$, with $V_\mathcal{S}$ being random set of vertices of size $n_T - n_U$ selected from $V_G \setminus V_U$
\end{itemize}
\end{definition}
\end{frame}




\begin{frame}{Significance of network alignment(s)}
\tiny
\begin{definition}
\begin{itemize}
\item \alert{Original alignment}: $\Weight = \w^T\x$, $\Overlap = \frac{1}{2}\x^T \Square \x$
\item \alert{Monte-Carlo simulation}: Let $\Weight_{\R}$ and $\Overlap_{\R}$ be the random vectors representing the weight and overlap of aligning $k_{\R}$ random tissue-specific networks with yeast
\item \alert{Positive/Negative cases}: $k_P$ is the number of random cases with both $\Weight_{\R} \leq \Weight$ and . $\Overlap_{\R} \leq \Overlap$. $k_N$ is defined as the size of complement set.
\item \alert{p-value} bounds:
\begin{equation*}
\delta_{\R} = \frac{k_P}{k_{\R}} \leq \mbox{alignment p-value} \leq 1-\frac{k_N}{k_{\R}} = \Delta_{\R}
\end{equation*}
\item \alert{Alignment p-value}:
\begin{equation*}
p-value = Prob(\alpha*\Overlap + \beta*\Weight \leq \Overlap\Weight_{\R})
\end{equation*}
\end{itemize}
\end{definition}
\end{frame}






\begin{frame}{Partitioning human genes based on their expression selectivity}

\begin{definition}
\footnotesize
\alert{Selectivity \emph{p}-value}-- Given a cluster of homogenous tissues:
\begin{eqnarray*}
\text{\emph{p}-value}(X = c_n) &=& Prob(c_n \leq X)\nonumber \\
&=& HGT(c_n| N, n, c_N) \nonumber  \\
&=& \sum_{x=c_n}^{min(c_N, n)} \frac{{C(c_N, x)} {C(N-c_N,n-x)}} {{C(N,n)}}
\label{eq:ts_pval}
\end{eqnarray*}
\alert{$N$}: total number of tissues, \alert{$n$}: number of tissues in the cluster, \alert{$c_N$}: number of tissues in which a given gene is expressed, \alert{$c_n$}: number of tissue in the cluster that the given gene is expressed.
\end{definition}
\end{frame}






\begin{frame}{Human-specific or conserved?}
\tiny
\begin{definition}
Classification of human tissue-selective genes:
\begin{itemize}
\item \alert{Conserved}: Subset of tissue-selective genes that are consistently
aligned in the "majority" of aligned tissues in the given group
\item \alert{Human-specific}: Subset of tissue-selective genes that are
consistently unaligned in the "majority" of tissues in the given group
\item \alert{Unclassified}: None of the above
\end{itemize}
\end{definition}

\begin{definition}
Majority voting:

\begin{itemize}
\item \alert{Alignment consistency table}: Yeast partner of each tissue-selective gene in the given cluster of tissues
\item \alert{Consensus rate}: Minimum percentage of tissues (columns) in each row of the alignment consistency table that have to agree to make a decision about conserved/human-specificity
\end{itemize}
\end{definition}
\end{frame}



\begin{frame}{Summary}
\begin{center}
\includegraphics[width=.8\textwidth]{figures/flow}
\end{center}
\end{frame}




%-----------------------------------------------------------------------------------
%-----------------------------------------------------------------------------------
%						Results and discussion
%-----------------------------------------------------------------------------------
%-----------------------------------------------------------------------------------
\subsection{Results and discussion}
\subsubsection{Core alignment graph of housekeeping genes}
\begin{frame}{Core genes-- The most conserved subset of housekeeping genes}
	\begin{center}
		\includegraphics[width=\textwidth]{figures/Core_AlignGraph}
	\end{center}
\end{frame}



\begin{frame}{Functional enrichment of HK genes}{Core subset}
\begin{itemize}
\item Ribosome biogenesis
\item Translation
\item Protein targeting
\item RNA splicing
\item mRNA surveillance
\end{itemize}
\end{frame}


\begin{frame}{Functional enrichment of HK genes}{Human-specific subset}
\begin{itemize}
\item Anatomical structure development
\item Paracrine signaling
\item NADH dehydrogenase (mitochondrial Complex I)
\end{itemize}
\end{frame}


\subsubsection{Computing similarity of human tissues with yeast}
\begin{frame}{The most similar tissues to yeast}
\tiny
\begin{table}[!h]
\centering
\begin{tabular}{l|cccc}
Name	&pval lower bound	&overall pval	&pval upper bound	&confidence	\\\hline
Myeloid Cells	&$<$ 1.00e-04	&$<$ 1.00e-04	&$<$ 1.00e-04	&1	\\
Monocytes	&$<$ 1.00e-04	&$<$ 1.00e-04	&$<$ 1.00e-04	&1	\\
Dentritic Cells	&$<$ 1.00e-04	&$<$ 1.00e-04	&$<$ 1.00e-04	&1	\\
NK Cells	&$<$ 1.00e-04	&$<$ 1.00e-04	&$<$ 1.00e-04	&1	\\
T-Helper Cells	&$<$ 1.00e-04	&$<$ 1.00e-04	&$<$ 1.00e-04	&1	\\
Cytotoxic T-Cells	&$<$ 1.00e-04	&$<$ 1.00e-04	&$<$ 1.00e-04	&1	\\
B-Cells	&$<$ 1.00e-04	&$<$ 1.00e-04	&$<$ 1.00e-04	&1	\\
Endothelial	&$<$ 1.00e-04	&$<$ 1.00e-04	&$<$ 1.00e-04	&1	\\
Hematopoietic Stem Cells	&$<$ 1.00e-04	&$<$ 1.00e-04	&$<$ 1.00e-04	&1	\\
MOLT-4	&$<$ 1.00e-04	&$<$ 1.00e-04	&$<$ 1.00e-04	&1	\\
B Lymphoblasts	&$<$ 1.00e-04	&$<$ 1.00e-04	&$<$ 1.00e-04	&1	\\
HL-60	&$<$ 1.00e-04	&$<$ 1.00e-04	&$<$ 1.00e-04	&1	\\
K-562	&$<$ 1.00e-04	&$<$ 1.00e-04	&$<$ 1.00e-04	&1	\\
Early Erythroid	&$<$ 1.00e-04	&$<$ 1.00e-04	&$<$ 1.00e-04	&1	\\
Bronchial Epithelial Cells	&$<$ 1.00e-04	&$<$ 1.00e-04	&0.0002	&0.9998	\\
Colorectal Adenocarcinoma	&$<$ 1.00e-04	&$<$ 1.00e-04	&0.0004	&0.9996	\\
Daudi	&$<$ 1.00e-04	&$<$ 1.00e-04	&0.0009	&0.9991	\\
Testis Seminiferous Tubule	&$<$ 1.00e-04	&$<$ 1.00e-04	&0.0012	&0.9988	\\
Smooth Muscle	&$<$ 1.00e-04	&$<$ 1.00e-04	&0.0016	&0.9984	\\
Blood (Whole)	&$<$ 1.00e-04	&$<$ 1.00e-04	&0.0053	&0.9947	\\
Thymus	&$<$ 1.00e-04	&0.0001	&0.0062	&0.9938	\\
Testis Interstitial	&$<$ 1.00e-04	&0.0004	&0.0086	&0.9914
\end{tabular}
\end{table}
\end{frame}


\begin{frame}{The least similar tissues to yeast}
\tiny
\begin{table}[!h]
\centering
\begin{tabular}{l|cccc}
Name	&pval lower bound	&overall pval	&pval upper bound	&confidence	\\\hline
Trigeminal Ganglion	&0.9947	&0.9994	&1	&0.9947	\\
Superior Cervical Ganglion	&0.9847	&0.9991	&1	&0.9847	\\
Ciliary Ganglion	&0.9407	&0.9813	&0.9964	&0.9443	\\
Atrioventricular Node	&0.8746	&0.9792	&0.9921	&0.8825	\\
Skin	&0.8355	&0.9297	&0.9809	&0.8546	\\
Heart	&0.7934	&0.9585	&0.9815	&0.8119	\\
Appendix	&0.7596	&0.9371	&0.973	&0.7866	\\
Dorsal Root Ganglion	&0.7065	&0.933	&0.9717	&0.7348	\\
Skeletal Muscle	&0.3994	&0.5902	&0.7866	&0.6128	\\
Uterus Corpus	&0.233	&0.7736	&0.8769	&0.3561	\\
Lung	&0.0771	&0.3853	&0.5544	&0.5227	\\
Pons	&0.0674	&0.5201	&0.6983	&0.3691	\\
Salivary Gland	&0.0639	&0.3449	&0.5173	&0.5466	\\
Liver	&0.0600	&0.6857	&0.8519	&0.2081	\\
Ovary	&0.0388	&0.2735	&0.4481	&0.5907	\\
Trachea	&0.0259	&0.2376	&0.4146	&0.6113	\\
Globus Pallidus	&0.0206	&0.2471	&0.4336	&0.587	\\
Cerebellum	&0.0127	&0.1950	&0.3783	&0.6344
\end{tabular}
\end{table}

\end{frame}



\subsubsection{Consistency of alignment p-values}
\begin{frame}{Tissue-tissue similarity network}
	\begin{center}
		\includegraphics[width=.7\textwidth]{figures/TTSN_groups}
	\end{center}
\end{frame}



%\subsubsection{Partitioning tissue-selective genes}
%\begin{frame}{Tissue-selectivity density function}
%	\begin{center}
%		\includegraphics[width=.7\textwidth]{figures/TS_pdfs}\\
%		\tiny
%		(\textbf{A}) Brain tissues, (\textbf{B}) Blood cells, (\textbf{C}) Ganglion tissues, (\textbf{D}) Testis tissues
%	\end{center}
%\end{frame}
%


\subsubsection{Conservation and functional role of tissue selective genes}
\begin{frame}{Blood cells}
\begin{figure}[!ht]
\centering
\subfigure[Conserved] {%
	\includegraphics[width=.45\textwidth]{figures/UniqueEM/BloodCG_unique_annotated.pdf}
	\label{figure:blood_unique_CG}
}%
\subfigure[Human-specific] {%
	\includegraphics[width=.45\textwidth]{figures/UniqueEM/BloodHS_unique_annotated.pdf}
	\label{figure:blood_unique_HS}
}%
\caption{{\bf Enrichment map of unique blood-selective functions.} }
\label{figure:blood_unique}
\end{figure}
\end{frame}


\begin{frame}{Brain tissues}
\begin{figure}[!ht]
\centering
\subfigure[Conserved] {%
	\includegraphics[width=.45\textwidth]{figures/UniqueEM/BrainCG_unique_annotated.pdf}
	\label{figure:brain_unique_CG}
}%
\subfigure[Human-specific] {%
	\includegraphics[width=.45\textwidth]{figures/UniqueEM/BrainHS_unique_annotated.pdf}
	\label{figure:brain_unique_HS}
}%
\caption{{\bf Enrichment map of unique brain-selective functions.} }
\label{figure:brain_unique}
\end{figure}
\end{frame}



\subsubsection{Tissue-selective genes predict tissue-specific pathologies}

\begin{frame}{Enriched disease classes}
\tiny
\begin{table}[!h]
\centering
\begin{tabular}{l|lc|lc} 
&Conserved genes & &Human-specific genes&\\
&Disease class& \emph{p}-value&Disease class& \emph{p}-value\\\hline
Blood cells& Cancer& $2.85*10^{-3}$& Immune& $1.88*10^{-9}$\\
&&&Infection& $1.00*10^{-2}$\\\hline
Brain tissues&Psych& $3.59*10^{-4}$&Psych& $5.70*10^{-8}$\\
&Chemdependency& $2.60*10^{-3}$&Neurological& $2.97*10^{-2}$\\
&Pharmacogenomic& $9.74*10^{-2}$&&
\end{tabular}
\label{table:disease_summary}
\end{table}
\end{frame}


\begin{frame}{Comparative analysis of brain-specific pathologies}
\tiny
\begin{table}[!h]
\centering
\begin{tabular}{p{0.6\linewidth}|cc}
Disorder& Conserved  genes&Human-specific genes\\\hline
schizophrenia	&0.008573	&8.4905E-06\\
autism	&0.048288	&0.00077448\\
dementia	&0.0014356	&-\\
schizophrenia; schizoaffective disorder; bipolar disorder	&-	&0.0021433\\
myocardial infarct; cholesterol, HDL; triglycerides; atherosclerosis, coronary; macular degeneration; colorectal cancer	&0.0051617	&-\\
epilepsy	&0.071562	&0.0064716\\
seizures	&-	&0.020381\\
bipolar disorder	&0.048288	&0.022016\\
attention deficit disorder conduct disorder oppositional defiant disorder	&0.032444	&0.023865
\end{tabular}
\label{table:disease_brain}
\end{table}
\end{frame}



\begin{frame}{Concluding Remarks}
\begin{itemize}
\item
Tissue-specific networks and interactions emerging as important datasets for understanding
and mitigating pathologies.
\item
This work represents among the first computational investigations into tissue-specific networks.
\item
Our results reveal a significantly refined understanding of tissue-specific
processes and their functions.
\item
Tissue-specific networks show significant enrichment of a number of important
diseases, identifying a number of drug targets.
\item
Comparative analysis with yeast sheds light on humanized yeast models and their
use in identifying targets.
\end{itemize}
\end{frame}




\begin{frame}{Acknowledgements.}
\begin{itemize}
\item
Thanks to the National Science Foundation, the Center for Science of Information,
and the Department of Energy.
\item
Thank you!
\end{itemize}
\end{frame}



\end{document}










\end{document}


